Introduction

In mathematics, interpolation can be defined as the estimation of unknown data points based on the range of a discrete set of known data points. Interpolation has many applications in the field of computer graphics. For example, it can be used to generate paths for animating objects or cameras, to control the timing of a fading transition between two images, or to dynamically generate the glyphs of a font for different resolutions and sizes.

A sophisticated interpolation method can produce a smooth and granular animation that allows the user to intuitively fine tune the path traversed between a set of end points.

Interpolation methods are usually implemented in the form of a function that receives as input two points a and b, an auxiliary set of parameters and a weight value t in the [0,1] range, and calculates a new point p in-between a and b. Points in N-dimensional space can be generated by independently interpolating values in each dimension.

Below, we’ll explore some commonly used interpolation methods.

Step

The crudest way to interpolate between two values is to use the step function. The t value is simply discretized and becomes either 0 or 1, based on a threshold e. A threshold of 0.5 will distribute the weight equally to the two endpoints.

The mathematical formulation is:

\[a,b,p \in \mathbb{R^n} \\ t,e \in \mathbb{R} \mid 0 \le \{ t,e \} \le 1 \\ p = \begin{cases} \displaystyle a, \;\; t \lt e \\ b, \;\; t \geq e \end{cases}\]

It can be implemented as follows in GLSL for 2d points:

vec2 interpolate(vec2 a, vec2 b, float t, float e)
{
    return t < e ? a : b;
}

Linear

In linear interpolation, the path connecting the two endpoints a, b is a line (hence the name), and the t value is used to smoothly calculate an interpolated position between them, across that line. In other words, for each value of t, a linear combination of a and b is computed.

The mathematical formulation is:

\[a,b,p \in \mathbb{R^n} \\ t \in \mathbb{R} \mid 0 \le t \le 1 \\ p(t) = (1 - t)a + tb\]

It can be implemented as follows in GLSL for 2d points:

vec2 interpolate(vec2 a, vec2 b, float t)
{
    return mix(a, b, t);
}

Bézier Curve, Quadratic

Quadratic Bézier curves use a control point \(m\) to parameterize the curvature of the derived path. It can be interpreted as a two tier linear interpolation where we first interpolate from endpoint \(a\) to control point \(m\) and from control point \(m\) to endpoint \(b\) respectively for given \(t\), and then interpolate linearly across the calculated points, using the same t value again.

The mathematical formulation is:

\[a,b,m,p \in \mathbb{R^n} \\ t \in \mathbb{R} \mid 0 \le t \le 1 \\ G(a,b,t)=(1-t)a+tb\\ p(t)=G(G(a,m,t),G(m,b,t),t)=(1-t)((1-t)a + tm) + t((1-t)m + tb)\]

Rearranging the formula yields:

\[p(t)=(1-t)^2a + 2(1-t)tm + t^2b\]

It can be implemented as follows in GLSL for 2d points:

vec2 interpolate(vec2 a, vec2 b, vec2 m, float t)
{
    vec2 v0 = mix(a, m, t);
    vec2 v1 = mix(m, b, t);
    return mix(v0, v1, t);
}

Bézier Curve, Qubic

A cubic Bézier curve uses two control points instead of one, and extends its quadratic counterpart by adding one more layer of linear interpolation.

The mathematical formulation is:

\[a,b,m_0,m_1,p \in \mathbb{R^n} \\ t \in \mathbb{R} \mid 0 \le t \le 1 \\ p(t)=(1-t)^3a + 3(1 - t^2)tm_0 + 3(1 - t)t^2m_1 + t^3b\]

It can be implemented as follows in GLSL for 2d points:

vec2 interpolate(vec2 a, vec2 b, vec2 m0, vec2 m1, float t)
{
    vec2 v0 = mix( a, m0, t);
    vec2 v1 = mix(m0, m1, t);
    vec2 v2 = mix(m1,  b, t);
    vec2 v3 = mix(v0, v1, t);
    vec2 v4 = mix(v1, v2, t);
    return mix(v3, v4, t);
}

Following the same process, it’s trivial to derive the formula for a Bézzier curve that uses n control points

Catmull-Rom Spline

To provide some context, we’ll start with the basics and work our way to the definition of Catmull-Rom splines.

Definition of a Spline

A spline is a piecewise polynomial parametric curve. The term comes from the flexible spline devices used by shipbuilders and draftsmen to draw smooth shapes. It also is an acronym for Smooth Polynomial Lines Interpolating Numerical Estimates [2].

Hermite Splines

Hermite splines are named after Charles Hermite. The cubic Hermite spline; an order 3 polynomial, at unit interval and for endpoints \(p_0\), \(p_1\) is defined as:

\[p_0, p_1, m_0, m_1, p \in \mathbb{R^n} \\ t \in \mathbb{R} \mid 0 \le t \le 1 \\ p(t) = (2t^3 - 3t^2 + 1)p_0 + (t^3 - 2t^2 + t)m_0 + (-2t^3 + 3t^2)p_1 + (t^3 - t^2)m_1\]

the control points \(m_0\), \(m_1\) configure the tangents at \(t = 0\) and \(t = 1\) respectively.

For an arbitraty number of endpoints \(p_i\) with \(i \in \mathbb{Z}\) it’s often more convenient to express the spline on an arbitrary interpolation range with \(t \in [x_i, x_{i+1}]\). The formulation becomes:

\[p_i, m_i, p \in \mathbb{R^n} \\ x_i \in \mathbb{R} \\ t = \frac{(x - x_i)}{x_{i+1} - x_i} \\ p(x) = h_{00}(t)p_i + h_{10}(t)(x_{i+1} - x_i)m_i + h_{01}(t)p_{i+1} + h_{11}(t)(x_{i+1} - x_i)m_{i+1}\]

where \(p_i\) are the points of the path, \(k_i\) are the corresponding tangent parameterization points, and \(h_i(t)\) are the Hermite basis functions, defined below. Notice the similarities of the two formulas.

Basis Function Definition
\(h_{00}(t)\) \(2t^3 - 3t^2 + 1\)
\(h_{10}(t)\) \(t^3 - 2t^2 + t\)
\(h_{01}(t)\) \(-2t^3 + 3t^2\)
\(h_{11}(t)\) \(t^3 - t^2\)

Cardinal Splines

A Catmull–Rom spline is a special case of a cardinal spline and is named after Edwin Catmull and Raphael Rom. They exhibit \(C^1\) continuity, which means that their first order derivative exists and is continuous.

A set of points can be smoothly interpolated by applying piecewise interpolation at each interval, if the tangents are carefully selected so that they are equal at the shared endpoints. The interpolated curve then consists of piecewise cubic Hermite splines, and is globally continuously differentiable across its length. The choice of tangents is non-unique, and there are several options available. A Cardinal spline, sometimes called a canonical spline is obtained if the tangent control points \(m_i\) of the Hermite spline are calculated as follows:

\[m_i, p_i \in \mathbb{R^n} \\ t_i,c \in \mathbb{R} \mid 0 \le t,c \le 1 \\ m_i = (1 − c)\frac{p_{i + 1} − p_{i − 1}}{t_{i + 1} − t_{i − 1}}\]

The parameter c is a tension parameter that must be in the interval [0,1]. In some sense, this can be interpreted as the length of the tangent. Choosing \(c = 1\) yields all zero tangents, and choosing \(c = 0\) yields a Catmull–Rom spline [3].

We can define a Catmull-Rom spline as follows:

\[q(t) = 0.5 * \begin{pmatrix} t^3,t^2,t,1 \end{pmatrix} * M * \begin{pmatrix} p_1\\\ p_2\\\ p_3\\\ p_4 \end{pmatrix}\]

where M is:

\[\begin{pmatrix} +0 & +2 & +0 & +0\\\ -1 & +0 & +1 & +0\\\ +2 & -5 & +4 & -1\\\ -1 & +3 & -3 & +1 \end{pmatrix}\]

and \(p_1, p_2, p_3, p_4\) are points along the curve.

It can be implemented as follows in GLSL for 2d points:

vec2 interpolate(vec2 a, vec2 b, vec2 m0, vec2 m1, float t)
{
    // CatmullRoms are cardinals with a tension of 0.5
    vec2 P = -m0 + (3. * (a - b)) + m1;
    vec2 Q = (2. * m0) - (5. * a) + (4. * b) - m1;
    vec2 R = b - m0;
    vec2 S = 2. * a;

    float t2 = t * t;
    float t3 = t * t2;

    return .5 * ((P * t3) + (Q * t2) + (R * t) + S);
}

References / Further Reading