Curves
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
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:
| Type | Form | Example 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.