Catmull–Rom spline

Catmull–Rom spline is a special case of a cardinal spline. This assumes uniform parameter spacing. For tangents chosen to be

${\displaystyle {\boldsymbol {m}}_{k}={\frac {{\boldsymbol {p}}_{k+1}-{\boldsymbol {p}}_{k-1}}{2}}}$

in the definition formula of cubic Hermite spline:

${\displaystyle {\boldsymbol {p}}(t)=\left(2t^{3}-3t^{2}+1\right){\boldsymbol {p}}_{k}+\left(t^{3}-2t^{2}+t\right){\boldsymbol {m}}_{k}+\left(-2t^{3}+3t^{2}\right){\boldsymbol {p}}_{k+1}+\left(t^{3}-t^{2}\right){\boldsymbol {m}}_{k+1}}$

the following formula for the Catmull–Rom spline is obtained:

${\displaystyle {\boldsymbol {p}}(t)={\frac {1}{2}}{\begin{bmatrix}t^{3}&t^{2}&t&1\end{bmatrix}}{\begin{bmatrix}-1&3&-3&1\\2&-5&4&-1\\-1&0&1&0\\0&2&0&0\end{bmatrix}}{\begin{bmatrix}{\boldsymbol {p}}_{k-1}\\{\boldsymbol {p}}_{k}\\{\boldsymbol {p}}_{k+1}\\{\boldsymbol {p}}_{k+2}\end{bmatrix}}}$

The curve is named after Edwin Catmull and Raphael Rom. The principal advantage of this technique is that the points along the original set of points also make up the control points for the spline curve.^[1]

Example of Catmull–Rom spline^[2]

Two additional points are required on either end of the curve. The uniform Catmull–Rom implementation can produce loops and self-intersections. The chordal and centripetal Catmull–Rom implementations^[3] solve this problem, but use a slightly different calculation.^[4] In computer graphics, Catmull–Rom splines are frequently used to get smooth interpolated motion between key frames. For example, most camera path animations generated from discrete key-frames are handled using Catmull–Rom splines. They are popular mainly for being relatively easy to compute, guaranteeing that each key frame position will be hit exactly, and also guaranteeing that the tangents of the generated curve are continuous over multiple segments.

Definition (by Catmull and Rom)

Referenced paper^[1] is for a class of splines passing through their defining points. Graphs and experimental results for the following blending functions are shown, with "case 3" being a Catmull–Rom spline curve. ^[5]

	Interval Width	Differentiability	Type	Degree of Polynomial for Cardinal Function
case 1	3	1	B-SPLINE
case 2	4	2	BEZIER
case 3	4	1	B-SPLINE	1
case 4	6	2	B-SPLINE	2

The model of the spline is:

${\displaystyle \mathbf {F} (t)=\sum _{j}^{}{\mathbf {p} }_{j}C_{jk}(t)}$

where ${\displaystyle {\mathbf {p} }_{j}}$ are defining points, ${\displaystyle C_{jk}(t)}$ are shifted blending functions ${\displaystyle C_{0,k}(t)}$ into interval ${\displaystyle 0\leq t<1}$.

Below are, from left, an example of blending functions ${\displaystyle C_{0,k}(t)}$, its shifted ${\displaystyle C_{jk}(t)}$, and a curve ${\displaystyle \mathbf {F} (t)}$.

The blending functions are following cardinal functions: ^{[note 1]}

${\displaystyle C_{0,k}(t)=\sum _{i=0}^{k}\left[\prod _{\begin{array}{c}j=i-k\\j\neq 0\end{array}}^{i}\left({\frac {t}{j}}+1\right)\right]w(t+i)}$

Linear Lagrange interpolation is used, so ${\displaystyle k=1}$, resulting in:

${\displaystyle C_{0,1}(t)=(1-t)w(t)+(1+t)w(1+t)}$

where ${\displaystyle w(t)}$ is a blending function obtained by shifting the basis functions of a quadratic uniform B-spline.

Below are, from the left, blending functions of a quadratic uniform B-spline and the basis functions before shifting.

The graphs of each term in ${\displaystyle C_{0,1}(t)}$ are as follows:

Applying this ${\displaystyle w(t)}$ to ${\displaystyle C_{0,1}(t)}$:

${\displaystyle C_{0,1}(t)=\left\{{\begin{array}{ll}{\frac {1}{2}}t^{3}+{\frac {5}{2}}t^{2}+4t+2&for\quad -2\leq t<-1\\-{\frac {3}{2}}t^{3}-{\frac {5}{2}}t^{2}+1&for\quad -1\leq t<0\\{\frac {3}{2}}t^{3}-{\frac {5}{2}}t^{2}+1&for\quad 0\leq t<1\\-{\frac {1}{2}}t^{3}+{\frac {5}{2}}t^{2}-4t+2&for\quad 1\leq t<2\end{array}}\right.}$

are obtained. Shifting these to the interval ${\displaystyle 0\leq t<1}$ gives ${\displaystyle C_{j1}(t)}$, and arrange them into matrix form gives:

${\displaystyle \mathbf {F} (t)={\frac {1}{2}}{\begin{bmatrix}t^{3}&t^{2}&t&1\end{bmatrix}}{\begin{bmatrix}-1&3&-3&1\\2&-5&4&-1\\-1&0&1&0\\0&2&0&0\end{bmatrix}}{\begin{bmatrix}{\mathbf {p} }_{j}\\{\mathbf {p} }_{j+1}\\{\mathbf {p} }_{j+2}\\{\mathbf {p} }_{j+3}\end{bmatrix}}}$

which coincides with the definition by a cubic Hermite spline.

Properties

Comparison with B-spline

A Catmull–Rom spline curve is interpolation that passes through its defining points, whereas a B-spline curve is approximation that do not pass through its control points.^[6]

Below are, from left, an example of blending functions, basis functions before shifting, and a curve of cubic uniform B-spline.

Continuity

A Catmull–Rom spline curve is C1 continuous by its definition and the following, but not C2 continuous:

${\displaystyle {\mathbf {F} }_{k}'(1)={\frac {1}{2}}{\begin{bmatrix}0&-1&0&1\end{bmatrix}}{\begin{bmatrix}{\mathbf {p} }_{k-1}\\{\mathbf {p} }_{k}\\{\mathbf {p} }_{k+1}\\{\mathbf {p} }_{k+2}\end{bmatrix}}={\mathbf {F} }_{k+1}'(0)={\frac {1}{2}}{\begin{bmatrix}-1&0&1&0\end{bmatrix}}{\begin{bmatrix}{\mathbf {p} }_{k}\\{\mathbf {p} }_{k+1}\\{\mathbf {p} }_{k+2}\\{\mathbf {p} }_{k+3}\end{bmatrix}}}$

${\displaystyle {\mathbf {F} }_{k}''(1)={\begin{bmatrix}-1&4&-5&2\end{bmatrix}}{\begin{bmatrix}{\mathbf {p} }_{k-1}\\{\mathbf {p} }_{k}\\{\mathbf {p} }_{k+1}\\{\mathbf {p} }_{k+2}\end{bmatrix}}\neq {\mathbf {F} }_{k+1}''(0)={\begin{bmatrix}2&-5&4&-1\end{bmatrix}}{\begin{bmatrix}{\mathbf {p} }_{k}\\{\mathbf {p} }_{k+1}\\{\mathbf {p} }_{k+2}\\{\mathbf {p} }_{k+3}\end{bmatrix}}}$

Self-intersection

If the difference in the intervals between the defining points is large in the middle of a curve, cusps or self-intersections may occur. ^{[note 2]}

Below is an example of a self-intersection:

Converting to Bézier curve

Example of converted Bézier curve (red: control points of Bézier curve)

Since the matrix form of a cubic Bézier curve is:

${\displaystyle \mathbf {P} (t)={\begin{bmatrix}t^{3}&t^{2}&t&1\end{bmatrix}}{\begin{bmatrix}-1&3&-3&1\\3&-6&3&0\\-3&3&0&0\\1&0&0&0\end{bmatrix}}{\begin{bmatrix}{\mathbf {p_{bz}} }_{0}\\{\mathbf {p_{bz}} }_{1}\\{\mathbf {p_{bz}} }_{2}\\{\mathbf {p_{bz}} }_{3}\end{bmatrix}}}$

the control points of a cubic Bézier curve equivalent to the Catmull–Rom spline curve are:

${\displaystyle {\begin{bmatrix}{\mathbf {p_{bz}} }_{0}\\{\mathbf {p_{bz}} }_{1}\\{\mathbf {p_{bz}} }_{2}\\{\mathbf {p_{bz}} }_{3}\end{bmatrix}}={\begin{bmatrix}-1&3&-3&1\\3&-6&3&0\\-3&3&0&0\\1&0&0&0\end{bmatrix}}^{-1}{\frac {1}{2}}{\begin{bmatrix}-1&3&-3&1\\2&-5&4&-1\\-1&0&1&0\\0&2&0&0\end{bmatrix}}{\begin{bmatrix}{\mathbf {p} }_{k-1}\\{\mathbf {p} }_{k}\\{\mathbf {p} }_{k+1}\\{\mathbf {p} }_{k+2}\end{bmatrix}}={\frac {1}{6}}{\begin{bmatrix}0&6&0&0\\-1&6&1&0\\0&1&6&-1\\0&0&6&0\end{bmatrix}}{\begin{bmatrix}\mathbf {p} _{k-1}\\\mathbf {p} _{k}\\\mathbf {p} _{k+1}\\\mathbf {p} _{k+2}\end{bmatrix}}}$

Extension to Surfaces (bicubic interpolation)

By taking the cartesian cross product of two Catmull-Rom splines, one can get a bivariate surface that interpolates a grid of points.^[7]。

It is a bicubic patch expressed by the following formula:

${\displaystyle \mathbf {F} (t,u)={\begin{bmatrix}t^{3}&t^{2}&t&1\end{bmatrix}}\mathbf {M} {\begin{bmatrix}{\mathbf {p} }_{11}&{\mathbf {p} }_{12}&{\mathbf {p} }_{13}&{\mathbf {p} }_{14}\\{\mathbf {p} }_{21}&{\mathbf {p} }_{22}&{\mathbf {p} }_{23}&{\mathbf {p} }_{24}\\{\mathbf {p} }_{31}&{\mathbf {p} }_{32}&{\mathbf {p} }_{33}&{\mathbf {p} }_{34}\\{\mathbf {p} }_{41}&{\mathbf {p} }_{42}&{\mathbf {p} }_{43}&{\mathbf {p} }_{44}\end{bmatrix}}\mathbf {M} ^{T}{\begin{bmatrix}u^{3}\\u^{2}\\u\\1\end{bmatrix}}}$

where

${\displaystyle \mathbf {M} ={\frac {1}{2}}{\begin{bmatrix}-1&3&-3&1\\2&-5&4&-1\\-1&0&1&0\\0&2&0&0\end{bmatrix}}}$

The patch interpolates the middle four points. Adjoinging patches have continuity of the first derivative.

Expansion of tension parameter

An example of visual effect of the tension parameter on interpolated motion between keyframes (white circle: keyframe, blue: ${\displaystyle \tau =0.2}$, green: ${\displaystyle \tau =0.5}$, red: ${\displaystyle \tau =1.0}$)

In some cases, Catmull–Rom spline is:

${\displaystyle {\boldsymbol {m}}_{k}=\tau ({\boldsymbol {p}}_{k+1}-{\boldsymbol {p}}_{k-1})}$,

where the coefficient of the tangent vector ${\displaystyle 1/2}$ is replaced with ${\displaystyle \tau }$.^[8]。

In this case, the definition formula is as follows:

${\displaystyle {\boldsymbol {p}}(t)={\begin{bmatrix}t^{3}&t^{2}&t&1\end{bmatrix}}{\begin{bmatrix}-\tau &2-\tau &\tau -2&\tau \\2\tau &\tau -3&3-2\tau &-\tau \\-\tau &0&\tau &0\\0&1&0&0\end{bmatrix}}{\begin{bmatrix}{\boldsymbol {p}}_{k-1}\\{\boldsymbol {p}}_{k}\\{\boldsymbol {p}}_{k+1}\\{\boldsymbol {p}}_{k+2}\end{bmatrix}}}$

The relationship between ${\displaystyle \tau }$ and the tension parameter of Kochanek–Bartels spline (denoted as ${\displaystyle \tau _{KB}}$) is as follows: ^[9]

${\displaystyle \tau ={\frac {1-\tau _{KB}}{2}}}$

Example of converted Bézier curve (${\displaystyle \tau =1.0}$)

And the control points of the equivalent cubic Bézier curve are as follows:

${\displaystyle {\begin{bmatrix}{\mathbf {p_{bz}} }_{0}\\{\mathbf {p_{bz}} }_{1}\\{\mathbf {p_{bz}} }_{2}\\{\mathbf {p_{bz}} }_{3}\end{bmatrix}}={\frac {1}{3}}{\begin{bmatrix}0&3&0&0\\-\tau &3&\tau &0\\0&\tau &3&-\tau \\0&0&3&0\end{bmatrix}}{\begin{bmatrix}\mathbf {p} _{k-1}\\\mathbf {p} _{k}\\\mathbf {p} _{k+1}\\\mathbf {p} _{k+2}\end{bmatrix}}}$

See also

• Cubic Hermite spline
• Centripetal Catmull–Rom spline
• Bicubic interpolation
• Bézier curve
• B-spline
• Kochanek–Bartels spline

Notes

1. The product notation stands for "${\displaystyle i-k\leq j\leq i}$, excluding ${\displaystyle 0}$", which is equivalent to:

   ${\displaystyle C_{0,k}(t)=\sum _{i=0}^{k}w(t+i)\prod _{j=i-k}^{i}\left\{{\begin{array}{ll}1&for\quad j=0\\{\frac {t}{j}}+1&otherwise\end{array}}\right.}$

2. It is safe for the first or last definition point to overlap with an adjacent definition point. This is sometimes used intentionally as a technique to hide "extra" definition points, and the example at the top was created in this way.