Interpolation (3 different ones)

Just been writing tomorrow's lecture on interpolation and decided to write a simple function to demonstrate the 3 different types I would be using. Most of the maths in this post is based on the Excellent "Mathematics for Computer Graphics" by John Vince every computer graphics person should own this book it's only £20.

Linear Interpolation

We can use linear interpolation to blend between two values using a floating point scalar value which ranges from 0-1

The basic formula given two values a and b and a real number t is \(
p=a+(b-a)*t \text{ where } 0\leq t\leq1 \). If we overload operators for our vector class so that we can subtract a vector from a vector, add a vector to a vector and multiply by a floating point scalar we can implement a Lerp function as

def Lerp(self, _a, _b, _t) :
  return _a+(_b-_a)*_t

In C++ it makes sense to make this a template function and the ngl:: library contains this template

/// @brief a simple template function for Linear Interpolation requires that any classes have
///    + - and * scalar (i.e. Real) overloaded operators
///    In the graphics lib this will work  for Vector and Colour
/// @param [in] _a the template value for the first parameter
/// @param [in] _b the template value for the first parameter
/// @param [in] _t the value for the blend between _a and _b must be between 0 - 1
template <class T> T lerp(
                          T _a,
                          T _b,
                          ngl::Real _t
                          )
{
 T p;
 p=_a+(_b-_a)*_t;
 return p;
}

And the C++ version can be used by including Util.h as follows

#include "ngl/Util.h"

ngl::Colour c1(0.0,0.0,0.0);
ngl::Colour c2(1.0,0.0,0.0);
ngl::Colour c3=Lerp(c1,c2,0.3);

ngl::Vector v1(1.0,2.0,1.0);
ngl::Vector v2(1.0,0.0,2.0);
ngl::Colour v3=Lerp(v1,v2,0.3);

Trigonometric Interpolation
A Linear interpolant ensures that equal steps in the parameter t give rise to equal steps in the interpolated values. However it is often required that equal steps in t give rise to unequal steps in the interpolated values. We can achieve this using a variety of mathematical techniques.

From the basic trigonometric ratios we know that \(\sin^2\beta+\cos^2\beta=1\) This satisfies one of the requirements of an interpolant that the terms must sum to 1. If \(\beta\) varies between 0 and \(\frac{\pi}{2}\) then \(\cos^2\beta\) varies between 1 and \(\sin^2\beta\) varies between 0 and 1 which can be used to modify the interpolated values. We can write this as

$$n=n_1\cos^2t+n_2\sin^2t \text{ where } \left[0 \leq t \leq \frac{\pi}{2} \right] $$
plotting these values we get the following curves

If we calculate this for a point starting at (1,1) and ending at (4,3) we get the following graph

You will notice that the path along the line is now non-linear, to write a Trigonometric interpolation function we need to form our values to range from 0-90 for a range of 0.0 - 1.0, further to this we need to convert these values to radians.

def TrigInterp(self, _a,_b,_t) :
  angle=math.radians(self.Lerp(0.0,90.0,_t))
  return _a*math.cos(angle)*math.cos(angle)+_b*math.sin(angle)*math.sin(angle)

Cubic Interpolation
In cubic interpolation we need to develop a cubic function to do our blending.
In mathematics a cubic function is one of the form
$$f(x)=ax^3+bx^2+cx+d$$
Applying this to our interpolant we get
$$v_{1}=at^3+bt^2+ct+d$$
or in Matrix form
$$n=\left[ v_{1} v_{2}\right]\left[\begin{array}{c} n_{1} \\ n_{2}\end{array}\right]$$

The task is to find the values of the constants associated with the polynomials v1 and v2
The requirements are

1. The cubic function v2 must grow from 0 to 1 for 
2. The slope at point t must equal the slope at the point (1-t) this ensures the slope symmetry over the range of the function
3. The value v2 at any point t must also produce (1-v2) at (1-t) this ensures curve symmetry

To satisfy the first requirement :

$$v_{2}=at^3+bt^2+ct+d$$

and when \(t=0\), \(v_2=0\) and \(d=0\). Similarly, when \(t=1\), \(v_2=a+b+c\).

To satisfy the second requirement, we differentiate \(v_2\) to obtain the slope
$$ \frac{dv_2}{dt}=3at^2+2bt+c=3a(1-t)^2+2b(1-t)+c $$
equating the constants we discover \(c=0\) and \(0=3a+2b\)

To satisfy the third requirement
$$a^3+bt^2=1-\left[a(1-t)^3+b(1-t)^2\right]$$
where we can compute \(1=a+0\). But \(0=3a+2b\), therefore \(a=2\) and \(b=3\) and we get
$$v_2=-2t^3+3t^2$$
We must now find the previous curve's mirror, which starts at 1 and collapses to 0 as \(t\) moves from 0 to 1. To do this we subtract the previous equation from 1 and get
$$v_1=2t^3-3t^2+1$$
These can be used as the interpolants
$$n=v_1n_1+v_2n_2$$
$$n=\left[ \begin{array}{cc} 2t^3-3t^2+1 & -2t^3+3t^2\end{array}\right]
\left[\begin{array}{c} n_1\\n_2\end{array}\right]$$
expanded in matrix form to
$$n=\left[ \begin{array}{cccc} t^3 & t^2 & t &1 \end{array}\right]
\left[\begin{array}{cc}
2 & -2 \\
-3 & 3 \\
0 & 0 \\
1 & 0 \\

\end{array}\right]
\left[\begin{array}{c} n_1\\n_2 \end{array}\right]$$

Plotting the two sets of polynomials gives us the following curves

applying this to the points (1,1) to (4,3) over a range 0-1 we get the following point spread

We can write a function to do this as follows

def Cubic(self, _a,_b,_t) :
  v1=(2.0*_t*_t*_t)-3.0*(_t*_t)+1.0
  v2=-(2.0*_t*_t*_t)+3*(_t*_t)
  return (_a*v1)+(_b*v2)

The following movie shows all 3 functions in action on a teapot, the top one is Trigonometric interpolation, the middle linear interpolation and the bottom one Cubic

You can see the ease in / out effect of the two non-linear interpolants and the linear one moving at a constant rate.

References

Vince, John (2010). Mathematics for Computer Graphics. 2nd. ed. London: Springr Verlag.

and for the title http://en.wikipedia.org/wiki/Pigs_(Three_Different_Ones)