Linear interpolation draws straight segments between adjacent sample points:

Linear interpolation is simple, but gives unnatural motion for character animation (unless the intervals between key frames are very small).

Let $t_1, t_2, \ldots, t_n$ be the times at which the keyframes occur.

Then let $q_i = q(t_i)$, where $q(t)$ is a continuous, interpolated curve from sample points $q(t_1), q(t_2), \ldots, q(t_n)$.

From now on, $q_i$ means a particular value, $q(t_i)$, on the curve $q(t)$.

How do we interpolate between $q_i$ and $q_{i+1}$?

As we've seen with linear interpolation of vectors, $$\displaystyle q(t) = q_i + {t-t_i \over t_{i+1} - t_i}\ (q_{i+1} - q_i)$$

For $t_i \leq t \leq t_{i+1}$, define $$u = {t-t_i \over t_{i+1}-t_i}$$

Note that $u$ is always in $[0,1]$.

Using $u$, one form of the interpolated curve in the range $[t_i,t_{i+1}]$ is $$\displaystyle q(u) = q_i + u\ (q_{i+1} - q_i)$$

This first form has separate weights for $u^0$ and $u^1$. Above, those weights are $q_i$ for $u^0$ and $(q_{i+1}-q_i)$ for $u^1$. The powers of $u$ form a monomial basis.

Another form is $$\displaystyle q(u) = (1-u)\ q_i + u\ q_{i+1}$$

This other form has separate weights for the control points $q_i$ and $q_{i+1}$. These weights are $(1-u)$ for $q_i$ and $u$ for $q_{i+1}$. The control points $q_i$ and $q_{i+1}$ form a control point basis.

Here are the two forms written with matrices: $$\begin{array}{rll} q(u) &= \left[ 1\ \ \ u \right]\ \ \left[ \begin{array}{c} q_i \\ q_{i+1}-q_i \end{array} \right] & \textrm{monomial basis form} \\ &= \left[ 1-u\ \ \ u \right]\ \ \left[ \begin{array}{c} q_i \\ q_{i+1} \end{array} \right] & \textrm{control point basis form} \\ \end{array}$$

The monomial basis form provides the coefficients of the monomials, $u^0$ and $u^1$, while the control point form provides weights to the control points, $q_i$ and $q_{i+1}$.

These can be unified in one form, with the monomial basis on the left and the control point basis on the right: $$\begin{array}{rl} q(u) &= \left[ 1\ \ \ u \right] \ \ \left[ \begin{array}{rr} 1 & 0 \\ -1 & 1 \end{array} \right] \ \ \left[ \begin{array}{c} q_i \\ q_{i+1} \end{array} \right] \\ \end{array}$$

Verify that this works: $$\begin{array}{rl} \left( \left[ 1\ \ \ u \right] \ \ \left[ \begin{array}{rr} 1 & 0 \\ -1 & 1 \end{array} \right] \right) \ \ \left[ \begin{array}{c} q_i \\ q_{i+1} \end{array} \right] = \left[ 1-u\ \ \ u \right]\ \ \left[ \begin{array}{c} q_i \\ q_{i+1} \end{array} \right] \\ \end{array}$$

and $$\begin{array}{rl} \left[ 1\ \ \ u \right]\ \ \left( \left[ \begin{array}{rr} 1 & 0 \\ -1 & 1 \end{array} \right] \ \ \left[ \begin{array}{c} q_i \\ q_{i+1} \end{array} \right] \right) = \left[ 1\ \ \ u \right]\ \ \left[ \begin{array}{c} q_i \\ q_{i+1}-q_i \end{array} \right] \end{array}$$

Most interpolation methods can be cast into the form above, like $$q(u) = \left[ 1\ \ \ u\ \ \ u^2\ \ \ u^3\ \ldots \right] \ \ \left[ \begin{array}{cccc} & \cdots & \cdots & \cdots \\ \vdots & & & \\ \vdots & & & \\ \vdots & & & \\ \end{array} \right] \ \ \ \left[ \begin{array}{c} q_1 \\ q_2 \\ q_3 \\ q_4 \\ \vdots \end{array} \right] $$

where

• the left array is the monomial basis,
• the right array contains the control point vector (or "basis"), and
• the middle array is the change-of-basis matrix.

Two important points:

1. The change-of-basis matrix permits us to convert between two bases: monomials and control points. Some operations are more conveniently done in one basis, rather than the other.
   
   
2. Each interpolation method (linear, Catmull-Rom, b-spline, etc.) has its own change-of-basis matrix. So interpolation code that uses the change-of-basis matrix can switch interpolation methods simply by switching the change-of-basis matrix. Always write your interpolation code using a change-of-basis matrix.