Motivation§

Keyframe

Often in computer animation, the artist provides keyframes and an algorithm interpolates between keyframes.

Anything can be keyframed:

Position and Orientation over Time

Joint Angles

An arm with joint angles $\theta_1, \theta_2, $ and $\theta_3$.
Plot of how $\theta_1, \theta_2, $ and $\theta_3$ change over time.

This then leaves us with the question of how we would interpolate between keyframes?

Representation of Curves§

There are a few ways to express a curve:

TypeFormExample for Circle
Explicit$y = f(x)$$y = \pm \sqrt{1 - x^2}$
Implicit$f(x, y) = 0$$x^2 + y^2 - 1 = 0$
Parametric$x = f(t), y = g(t)$$x = \cos t, y = \sin t$

Explicit§

  • + Easy to generate
  • – Only one value of $y$ for each $x$
  • – Heavily dependent on choice of independent variable

Implicit§

  • + $f(x, y)$ is a measure of the distance of a point to curve (level-set information).
  • – Difficult to generate points on a curve

Parametric§

  • + Easy to generate points on a curve
  • + Can have multiple $y$ for a given $x$

Cubic Bézier Curve§

Cubic Bézier Curve

Specify 4 “control” points, $(a_0, b_0), \dots, (a_3, b_3),$ then the cubic Bézier can be given in parametric form by

$$ \begin{align*} x(u) &= a_0 + a_1u + a_2u^2 + a_3u^3\\ y(u) &= b_0 + b_1u + b_2u^2 + b_3u^3 \end{align*} $$

Alternatively in vector notation:

$$ \begin{align*} \vec{p}(u) &= (1-u)^3\vec{p}_0 + 3u(1-u)^2\vec{p}_1 + 3u^2(1-u)\vec{p}_2 + u^3\vec{p}_3\\ \vec{p}(0) &= \vec{p}_0,\ \vec{p}(1) = \vec{p}_3 \end{align*} $$

And in matrix form: $$ \begin{align*} \vec{p}(u) &= \underbrace{\begin{pmatrix} \vec{p}_0 & \vec{p}_1 & \vec{p}_2 & \vec{p}_3 \end{pmatrix}}_{G} \underbrace{\begin{pmatrix} 1&-3&3&-1\\ 0&3&-6&3\\ 0&0&3&-3\\ 0&0&0&1 \end{pmatrix}}_{B} \underbrace{\begin{pmatrix} 1\\ u\\ u^2\\ u^3 \end{pmatrix}}_{\vec{u}}\\ \vec{p}(u) &= G\underbrace{B}_{\mathclap{\textrm{cubic Bezier basis}}}\vec{u} \end{align*} $$

Q: Why use 4 control points?

A: The parametric equations have 8 unknowns; each point gives us 2 pieces of information.

Continuity in Concatenated Bézier Curves§

Thare different classes of curve continuity

  • $C^0$, the curves are connected
  • $C^1$, tangents are the same
  • $G^1$, tagent directions are the same

They can be visualised with the following illustration

There exists an infinite number of $C^n$ and $G^n$ curves where the $n$th derivative matches, but typically $C^2$ or $G^2$ is good enough in most cases.

Cubic Catmull-Rom Spline§

The Catmull-Rom spline is $C^1$ everywhere, but not $C^2$ (not $C^2$ @ control points).

Catmull-Rom Spline

The basis for the Catmull-Rom spline can be given by

$$ B = \frac{1}{2} \begin{pmatrix} 0 & -1 & 2 & -1\\ 2 & 0 & -5 & 3\\ 0 & 1 & 4 & -3\\ 0 & 0 & -1 & 1 \end{pmatrix} $$

Connecting Sequence of Control Points

Connecting a sequence of 3D/2D points can be done using a Catmull-Rom spline.

$$ \begin{align*} \vec{p}(u) &= \langle\vec{p}_0,\ \overbrace{\vec{p}_1,\ \vec{p}_2}^{\mathclap{\text{the curve passes through the middle 2 points}}},\ \vec{p}_3\rangle B\,\vec{u},\ u \in [0, 1]\\ \vec{p}(u) &= \langle\vec{p}_1,\ \vec{p}_2,\ \vec{p}_3,\ \vec{p}_4\rangle B\,\vec{u},\ u \in [0, 1]\\ \vec{p}(u) &= \langle\vec{p}_2,\ \vec{p}_3,\ \vec{p}_4,\ \vec{p}_5\rangle B\,\vec{u},\ u \in [0, 1] \end{align*} $$

  • Every set of 4 control points define a segment of the curve
  • “Concatenated” $u$ goes from $[0, n - 3]$ where $n$ is the number of control points.
  • To convert between $u$ concatenated to $\hat{u} \in [0, 1]$ $$ \begin{align*} k &= \lfloor u\rfloor\\ \hat{u} &= u_k = u - k\\ G &= \big[\vec{p}_k, \vec{p}_{k+1}, \vec{p}_{k+2}, \vec{p}_{k+3}\big]_{4 \times 4} \end{align*} $$

Then, the curve can be computed using

$$ \vec{p}(u) = G_kB\vec{u_k}, u \in [0, n - 1] $$

where $n$ is the number of control points.