Option type: Difference between revisions
en>Dkasak →The option monad: Fix error in fmap type (it should accept two arguments and return a monad, not a function from monad to monad). |
en>Nbarth nullable |
||
Line 1: | Line 1: | ||
[[File:Smoothstep and Smootherstep.svg|thumb|A plot of the smoothstep(x) and smootherstep(x) functions.]] | |||
'''Smoothstep''' is a scalar [[interpolation]] function commonly used in [[computer graphics]]<ref>[http://msdn.microsoft.com/en-us/library/bb509658(VS.85).aspx Smoothstep at Microsoft Developer Network]</ref><ref>[http://www.opengl.org/registry/doc/GLSLangSpec.Full.1.40.05.pdf GLSL Language Specification, Version 1.40]</ref> and [[Game engine|video game engines]].<ref>[http://unity3d.com/support/documentation/ScriptReference/Mathf.SmoothStep.html Unity game engine SmoothStep documentation]</ref> The function interpolates [[Smooth function|smoothly]] between two input values based on a third one that should be between the first two. The returned value is clamped between 0 and 1. | |||
The slope of the smoothstep function tends toward zero at both edges. This makes it easy to create a sequence of transitions using smoothstep to interpolate each segment rather than using a more sophisticated or expensive interpolation technique. | |||
As pointed out in [[Microsoft Developer Network|MSDN]] and [[OpenGL]] documentation, smoothstep implements cubic [[Hermite interpolation]] after doing a clamp: | |||
:<math> \operatorname{smoothstep}(t) = 3t^2 - 2t^3 </math> | |||
An example implementation provided by AMD<ref>[http://ati.amd.com/developer/SIGGRAPH03/ATI_HardwareShading_SIGGRAPH2003.pps ATI R3x0 Pixel Shaders]</ref> follows. | |||
<source lang="c"> | |||
float smoothstep(float edge0, float edge1, float x) | |||
{ | |||
// Scale, bias and saturate x to 0..1 range | |||
x = saturate((x - edge0)/(edge1 - edge0)); | |||
// Evaluate polynomial | |||
return x*x*(3 - 2*x); | |||
} | |||
</source> | |||
== Variations == | |||
[[Ken Perlin]] suggests<ref>[http://www.amazon.com/Texturing-Modeling-Third-Procedural-Approach/dp/1558608486 Texturing and Modeling, Third Edition: A Procedural Approach]</ref> an improved version of the smoothstep function which has zero 1st and 2nd order derivatives at t=0 and t=1: | |||
:<math> \operatorname{smootherstep}(t) = 6t^5 - 15t^4 + 10t^3 </math> | |||
Reference implementation: | |||
<source lang="c"> | |||
float smootherstep(float edge0, float edge1, float x) | |||
{ | |||
// Scale, and clamp x to 0..1 range | |||
x = clamp((x - edge0)/(edge1 - edge0), 0.0, 1.0); | |||
// Evaluate polynomial | |||
return x*x*x*(x*(x*6 - 15) + 10); | |||
} | |||
</source> | |||
== Origin == | |||
=== 3rd order equation === | |||
We start with a generic third order [[polynomial]] function and its first [[derivative]]: | |||
:<math>\begin{alignat}{9} | |||
f(t) &&\; = \;&& a_3 t^3 &&\; + \;&& a_2 t^2 &&\; + \;&& a_1 t &&\; + \;&& a_0 & \\ | |||
f'(t) &&\; = \;&& 3 a_3 t^2 &&\; + \;&& 2 a_2 t &&\; + \;&& a_1 & | |||
\end{alignat}</math> | |||
Applying the desired values for the function at both endpoints we get: | |||
:<math>\begin{alignat}{13} | |||
f(0) &&\; = \;&& 0 \;\;\;\;\;&& \Rightarrow &&\;\;\;\;\; 0 \;&& + &&\; 0 \;&& + &&\; 0 \;&& + &&\; a_0 &&\; = \;&& 0 & \\ | |||
f(1) &&\; = \;&& 1 \;\;\;\;\;&& \Rightarrow &&\;\;\;\;\; a_3 \;&& + &&\; a_2 \;&& + &&\; a_1 \;&& + &&\; a_0 &&\; = \;&& 1 & | |||
\end{alignat}</math> | |||
Applying the desired values for the first derivative of the function at both endpoints we get: | |||
:<math>\begin{alignat}{11} | |||
f'(0) &&\; = \;&& 0 \;\;\;\;&& \Rightarrow &&\;\;\;\; 0 \;&& + &&\; 0 \;&& + &&\; a_1 \;&& = \;&& 0 & \\ | |||
f'(1) &&\; = \;&& 0 \;\;\;\;&& \Rightarrow &&\;\;\;\; 3 a_3 \;&& + &&\; 2 a_2 \;&& + &&\; a_1 \;&& = \;&& 0 & | |||
\end{alignat}</math> | |||
Solving the system of 4 unknowns formed by the last 4 equations we obtain the values of the polynomial coefficients: | |||
:<math>a_0 = 0 , \;\;\;\;\;\; a_1 = 0 , \;\;\;\;\;\; a_2 = 3 , \;\;\;\;\;\; a_3 = -2</math> | |||
Introducing these coefficients back into the first equation gives the third order smoothstep function: | |||
:<math>f(t) = -2t^3 + 3t^2</math> | |||
=== 5th order equation === | |||
We start with a generic fifth order [[polynomial]] function, its first derivative and its second derivative: | |||
:<math>\begin{alignat}{13} | |||
f(t) &&\; = \;&& a_5 t^5 &&\; + \;&& a_4 t^4 &&\; + \;&& a_3 t^3 &&\; + \;&& a_2 t^2 &&\; + \;&& a_1 t &&\; + \;&& a_0 & \\ | |||
f'(t) &&\; = \;&& 5 a_5 t^4 &&\; + \;&& 4 a_4 t^3 &&\; + \;&& 3 a_3 t^2 &&\; + \;&& 2 a_2 t &&\; + \;&& a_1 & \\ | |||
f''(t) &&\; = \;&& 20 a_5 t^3 &&\; + \;&& 12 a_4 t^2 &&\; + \;&& 6 a_3 t &&\; + \;&& 2 a_2 & | |||
\end{alignat}</math> | |||
Applying the desired values for the function at both endpoints we get: | |||
:<math>\begin{alignat}{17} | |||
f(0) &&\; = \;&& 0 \;\;\;\;\;&& \Rightarrow &&\;\;\;\;\; 0 \;&& + &&\; 0 \;&& + &&\; 0 \;&& + &&\; 0 \;&& + &&\; 0 \;&& + &&\; a_0 &&\; = \;&& 0 & \\ | |||
f(1) &&\; = \;&& 1 \;\;\;\;\;&& \Rightarrow &&\;\;\;\;\; a_5 \;&& + &&\; a_4 \;&& + &&\; a_3 \;&& + &&\; a_2 \;&& + &&\; a_1 \;&& + &&\; a_0 &&\; = \;&& 1 & | |||
\end{alignat}</math> | |||
Applying the desired values for the first derivative of the function at both endpoints we get: | |||
:<math>\begin{alignat}{15} | |||
f'(0) &&\; = \;&& 0 \;\;\;\;&& \Rightarrow &&\;\;\;\; 0 \;&& + &&\; 0 \;&& + &&\; 0 \;&& + &&\; 0 \;&& + &&\; a_1 \;&& = \;&& 0 & \\ | |||
f'(1) &&\; = \;&& 0 \;\;\;\;&& \Rightarrow &&\;\;\;\; 5 a_5 \;&& + &&\; 4 a_4 \;&& + &&\; 3 a_3 \;&& + &&\; 2 a_2 \;&& + &&\; a_1 \;&& = \;&& 0 & | |||
\end{alignat}</math> | |||
Applying the desired values for the second derivative of the function at both endpoints we get: | |||
:<math>\begin{alignat}{15} | |||
f''(0) &&\; = \;&& 0 \;\;\;\;&& \Rightarrow &&\;\;\;\; 0 \;&& + &&\; 0 \;&& + &&\; 0 \;&& + &&\; 2 a_2 \;&& = \;&& 0 & \\ | |||
f''(1) &&\; = \;&& 0 \;\;\;\;&& \Rightarrow &&\;\;\;\; 20 a_5 \;&& + &&\; 12 a_4 \;&& + &&\; 6 a_3 \;&& + &&\; 2 a_2 \;&& = \;&& 0 & | |||
\end{alignat}</math> | |||
Solving the system of 6 unknowns formed by the last 6 equations we obtain the values of the polynomial coefficients: | |||
:<math>a_0 = 0 , \;\;\;\;\;\; a_1 = 0 , \;\;\;\;\;\; a_2 = 0 , \;\;\;\;\;\; a_3 = 10 , \;\;\;\;\;\; a_4 = -15 , \;\;\;\;\;\; a_5 = 6</math> | |||
Introducing these coefficients back into the first equation gives the fifth order smoothstep function: | |||
:<math>f(t) = 6t^5 - 15t^4 + 10t^3</math> | |||
== References == | |||
{{reflist}} | |||
== External links == | |||
* [http://www.fundza.com/rman_shaders/smoothstep/index.html Using smoothstep] (in the [[RenderMan Shading Language]]) by Prof. Malcolm Kesson. | |||
* [http://sol.gfxile.net/interpolation/ Interpolation tricks] by Jari Komppa | |||
[[Category:Computer graphics algorithms]] |
Revision as of 12:00, 5 October 2013
Smoothstep is a scalar interpolation function commonly used in computer graphics[1][2] and video game engines.[3] The function interpolates smoothly between two input values based on a third one that should be between the first two. The returned value is clamped between 0 and 1.
The slope of the smoothstep function tends toward zero at both edges. This makes it easy to create a sequence of transitions using smoothstep to interpolate each segment rather than using a more sophisticated or expensive interpolation technique.
As pointed out in MSDN and OpenGL documentation, smoothstep implements cubic Hermite interpolation after doing a clamp:
An example implementation provided by AMD[4] follows.
float smoothstep(float edge0, float edge1, float x)
{
// Scale, bias and saturate x to 0..1 range
x = saturate((x - edge0)/(edge1 - edge0));
// Evaluate polynomial
return x*x*(3 - 2*x);
}
Variations
Ken Perlin suggests[5] an improved version of the smoothstep function which has zero 1st and 2nd order derivatives at t=0 and t=1:
Reference implementation:
float smootherstep(float edge0, float edge1, float x)
{
// Scale, and clamp x to 0..1 range
x = clamp((x - edge0)/(edge1 - edge0), 0.0, 1.0);
// Evaluate polynomial
return x*x*x*(x*(x*6 - 15) + 10);
}
Origin
3rd order equation
We start with a generic third order polynomial function and its first derivative:
Applying the desired values for the function at both endpoints we get:
Applying the desired values for the first derivative of the function at both endpoints we get:
Solving the system of 4 unknowns formed by the last 4 equations we obtain the values of the polynomial coefficients:
Introducing these coefficients back into the first equation gives the third order smoothstep function:
5th order equation
We start with a generic fifth order polynomial function, its first derivative and its second derivative:
Applying the desired values for the function at both endpoints we get:
Applying the desired values for the first derivative of the function at both endpoints we get:
Applying the desired values for the second derivative of the function at both endpoints we get:
Solving the system of 6 unknowns formed by the last 6 equations we obtain the values of the polynomial coefficients:
Introducing these coefficients back into the first equation gives the fifth order smoothstep function:
References
43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.
External links
- Using smoothstep (in the RenderMan Shading Language) by Prof. Malcolm Kesson.
- Interpolation tricks by Jari Komppa