CAGD-banner.gif
On-Line Geometric Modeling Notes
CATMULL-ROM SPLINES


Ferguson's Parametric Cubic Curves

The Catmull-Rom Spline is a local interpolating spline developed for computer graphics purposes. Its initial use was in design of curves and surfaces, and has recently been used several applications. This paper presents a simple development of the matrix form of this spline, using only intuitive concepts. The matrix form will arise from a simple geometrical argument that attempts to fix the tangents at certain control points to be the average of the slopes of the two line segments of the control polygon adjacent to each control point. The matrix equation is then just a simple result of matrix algebra.


Ferguson's Parametric Cubic Curves

Given the two control points $ {\bf P} _0$ and $ {\bf P} _1$, and the slopes of the tangents $ {\bf P} ' _0$ and $ {\bf P} ' _1$ at each point, we can define a parametric cubic curve that passes through $ {\bf P} _0$ and $ {\bf P} _1$, with the respective slopes $ {\bf P} ' _0$ and $ {\bf P} ' _1$ by equating the coefficients of the polynomial function

$\displaystyle {\bf P} (t) \: = \: a_0 + a_1 t + a_2 t^2 + a_3 t^3
$

with the values above. Namely
$\displaystyle {\bf P} (0)$ $\displaystyle =$ $\displaystyle a_0$  
$\displaystyle {\bf P} (1)$ $\displaystyle =$ $\displaystyle a_0 + a_1 + a_2 + a_3$  
$\displaystyle {\bf P} '(0)$ $\displaystyle =$ $\displaystyle a_1$  
$\displaystyle {\bf P} '(1)$ $\displaystyle =$ $\displaystyle a_1 + 2 a_2 + 3 a_3$  

Solving these equations simultaneously for $ a_0$, $ a_1$, $ a_2$ and $ a_3$, we obtain

$\displaystyle a_0$ $\displaystyle =$ $\displaystyle {\bf P} (0)$  
$\displaystyle a_1$ $\displaystyle =$ $\displaystyle {\bf P} ' (0)$  
$\displaystyle a_2$ $\displaystyle \: =$ $\displaystyle 3 \left[ {\bf P} (1) - {\bf P} (0) \right] - 2 {\bf P} '(0) - {\bf P} '(1)$  
$\displaystyle a_3$ $\displaystyle =$ $\displaystyle 2 \left[ {\bf P} (0) - {\bf P} (1) \right] + {\bf P} ' (0) + {\bf P} '(1)$  

Substituting these into the original polynomial equation and simplifying to isolate the terms with $ {\bf P} (0)$, $ {\bf P} (1)$, $ {\bf P} ' (0)$, and $ {\bf P} '(1)$, we have

$\displaystyle {\bf P} (t)$ $\displaystyle =$ $\displaystyle ( 1 - 3 t^2 + 2 t^3 ) {\bf P} (0)$  
    $\displaystyle \;\;\;\;\;+ ( 3 t^2 - 2 t^3 ) {\bf P} (1)$  
    $\displaystyle \;\;\;\;\;+ ( t - 2 t^2 + t^3 ) {\bf P} ' (0)$  
    $\displaystyle \;\;\;\;\;+ ( -t^2 + t^3 ) {\bf P} '(1)$  

which is clearly in a cubic polynomial form. Alternatively, this can be written in the following matrix form

$\displaystyle {\bf P} (u) \: = \:
\left[
\begin{array}{cccc}
1 & t & t^2 & t^3...
...) \\
{\bf P} (1) \\
{\bf P} '(0) \\
{\bf P} '(1) \\
\end{array}\right]
$

This method can be used to obtain a curve through a more general set of control points $ \left\{ {\bf P} _0 , {\bf P} _1 , ... , {\bf P} _n \right\}$ by considering pairs of control points and using the Ferguson method for two points as developed above. It is necessary, however, to have the slopes of the tangents at each control point.


Development of the Catmull-Rom Spline

Given $ n+1$ control points $ \left\{ {\bf P} _0 , {\bf P} _1 , ... , {\bf P} _n \right\}$, we wish to find a curve that interpolates these control points (i.e. passes through them all), and is local in nature (i.e. if one of the control points is moved, it only affects the curve locally). We define the curve on each segment $ \widehat{ {\bf P} _i {\bf P} _{i+1}}$ by using the two control points, and specifying the tangent to the curve at each control point to be

$\displaystyle \frac{ {\bf P} _{i+1} - {\bf P} _{i-1}}{2} {\rm and}
\frac{ {\bf P} _{i+2} - {\bf P} _i}{2}
$

respectively.

Substituting these tangents into Ferguson's method, we obtain the matrix equation

$\displaystyle {\bf P} (t) \: = \:
\left[
\begin{array}{cccc}
1 & t & t^2 & t^3...
...f P} _{i-1}}{2} \\
\frac{ {\bf P} _{i+2} - {\bf P} _i}{2}
\end{array}\right]
$

or

$\displaystyle {\bf P} (t) \: = \:
\left[
\begin{array}{cccc}
1 & t & t^2 & t^3...
...1} \\
{\bf P} _i \\
{\bf P} _{i+1} \\
{\bf P} _{i+2}
\end{array}\right]
$

Multiplying the two inner matrices, we obtain

$\displaystyle {\bf P} (t) \: = \:
\left[
\begin{array}{cccc}
1 & t & t^2 & t^3...
...1} \\
{\bf P} _i \\
{\bf P} _{i+1} \\
{\bf P} _{i+2}
\end{array}\right]
$

where

$\displaystyle {\bf M} \: = \:
\frac{1}{2}
\left[
\begin{array}{cccc}
0 & 2 & 0...
...
-1 & 0 & 1 & 0 \\
2 & -5 & 4 & -1 \\
-1 & 3 & -3 & 1
\end{array}\right]
$

This matrix representation defines the cubic curve that represents the portion of the total curve between two successive control points. It can be applied to all segments of the curve except for the first and last segments in which $ {\bf P} '_0$ and $ {\bf P} '_n$ must be defined by a different method.


Bibliography

1.
Catmull, E. and R. Rom, ``A Class of Local Interpolationg Splines,'' in Barnhill R.E. and R.F. Riesenfled (eds.), Computer Aided Geometric Design, Academic Press, New York, 1974.
2.
Faux, I.D. and M.J. Pratt, Computational Geometry for Design and Manufacture, Ellis Horwood Publishing, Chichester, UK, 1979.


\begin{singlespace}
\noindent
\footnotesize\bfseries All contents copyright (c) ...
...ment, University of California, Davis \\
All rights reserved.
\end{singlespace}


Ken Joy
2000-11-28