Catmull–Rom spline

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

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

in the definition formula of cubic Hermite spline:

${\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:

${\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.

Example of Catmull–Rom spline

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 solve this problem, but use a slightly different calculation. 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 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.

	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:

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

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

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

The blending functions are following cardinal functions:

$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 $k=1$, resulting in:

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

where $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 $C_{0,1}(t)$ are as follows:

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

$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 $0\leq t<1$ gives $C_{j1}(t)$, and arrange them into matrix form gives:

$\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.

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:

${\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}}$

${\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.

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:

$\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:

${\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.。

It is a bicubic patch expressed by the following formula:

$\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

$\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: $\tau =0.2$, green: $\tau =0.5$, red: $\tau =1.0$)

In some cases, Catmull–Rom spline is:

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

where the coefficient of the tangent vector $1/2$ is replaced with $\tau$.。

In this case, the definition formula is as follows:

${\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 $\tau$ and the tension parameter of Kochanek–Bartels spline (denoted as $\tau _{KB}$) is as follows:

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

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

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

${\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

References

Works cited

• de Boor, Carl (1978). A Practical Guide to Spline. ISBN 0-387-90356-9.
• Gordon, William J.; Riesenfeld, Richard F. (1974), "B-spline curves and surfaces", in Barnhill, Robert E.; Riesenfeld, Richard F. (eds.), Computer Aided Geometric Design - Proceedings of a Conference Held at The University of Utah, Salt Lake City, Utah, March 18-21, 1974, New York: Academic Press, pp. 95–126, ISBN 0-12-079050-5