This page was generated from doc/euclidean/catmull-rom-properties.ipynb. Interactive online version: .

Properties of Catmull–Rom Splines

[CR74] presents a whole class of splines with a whole range of properties. Here we only consider one member of this class which is a cubic polynomial interpolating spline with \(C^1\) continuity and local support. Nowadays, this specific case is typically simply referred to as Catmull–Rom spline.

This type of splines is very popular because they are very easy to use. Only a sequence of control points has to be specified, the tangents are calculated automatically from the given points. Using those tangents, the spline can be implemented using cubic Hermite splines. Alternatively, spline values can be directly calculated with the Barry–Goldman algorithm.

To calculate the spline values between two control points, the preceding and the following control points are needed as well. The tangent vector at any given control point can be calculated from this control point, its predecessor and its successor. Since Catmull–Rom splines are \(C^1\) continuous, incoming and outgoing tangent vectors are equal.

The following examples use the Python class splines.CatmullRom to create both uniform and non-uniform splines. Only closed splines are shown, other end conditions can also be used, but they are not specific to this type of spline.

import matplotlib.pyplot as plt
import numpy as np

Apart from the splines module …

import splines

… we also import a few helper functions from helper.py:

from helper import plot_spline_2d, plot_tangent_2d

Let’s choose a few points for an example:

points1 = [
    (0.2, -0.5),
    (0, 2.3),
    (1, 1),
    (4, 1.3),
    (3.8, -0.2),
    (2.5, 0.1),
]

Without specifying any time values, we get a uniform spline:

s1 = splines.CatmullRom(points1, endconditions='closed')

fig, ax = plt.subplots()
plot_spline_2d(s1, ax=ax)

Tangent Vectors

In the uniform case, the tangent vectors at any given control point are parallel to the line connecting the preceding point and the following point. The tangent vector has the same orientation as that line but only half its length. In other (more mathematical) words:

\begin{equation*} \boldsymbol{\dot{x}}_i = \frac{\boldsymbol{x}_{i+1} - \boldsymbol{x}_{i-1}}{2} \end{equation*}

This is illustrated for two control points in the following plot:

for idx, color in zip([2, 5], ['purple', 'hotpink']):
    plot_tangent_2d(
        s1.evaluate(s1.grid[idx], 1),
        s1.evaluate(s1.grid[idx]), color=color, ax=ax)
    ax.plot(
        *s1.evaluate([s1.grid[idx - 1], s1.grid[idx + 1]]).T,
        '--', color=color, linewidth=2)
fig

We can see here that each tangent vector is parallel to and has half the length of the line connecting the preceding and the following vertex, just as promised.

However, this will not be true anymore if we are using non-uniform time instances:

times2 = 0, 1, 2.2, 3, 4, 4.5, 6

s2 = splines.CatmullRom(points1, grid=times2, endconditions='closed')

plot_spline_2d(s2, ax=ax)
for idx, color in zip([2, 5], ['green', 'crimson']):
    plot_tangent_2d(
        s2.evaluate(s2.grid[idx], 1),
        s2.evaluate(s2.grid[idx]), color=color, ax=ax)
fig

In the non-uniform case, the equation for the tangent vector gets quite a bit more complicated:

\begin{equation*} \boldsymbol{\dot{x}}_i = \frac{ (t_{i+1} - t_i)^2 (\boldsymbol{x}_i - \boldsymbol{x}_{i-1}) + (t_i - t_{i-1})^2 (\boldsymbol{x}_{i+1} - \boldsymbol{x}_i) }{ (t_{i+1} - t_i)(t_i - t_{i-1})(t_{i+1} - t_{i-1}) } \end{equation*}

Equivalently, this can be written as:

\begin{equation*} \boldsymbol{\dot{x}}_i = \frac{ (t_{i+1} - t_i) (\boldsymbol{x}_i - \boldsymbol{x}_{i-1}) }{ (t_i - t_{i-1})(t_{i+1} - t_{i-1}) } + \frac{ (t_i - t_{i-1}) (\boldsymbol{x}_{i+1} - \boldsymbol{x}_i) }{ (t_{i+1} - t_i)(t_{i+1} - t_{i-1}) } \end{equation*}

The derivation of this equation is shown in a separate notebook.

Some sources use a simpler equation which is (arguably) not correct (except in the uniform case):

\begin{equation*} \boldsymbol{\dot{x}}_i = \frac{1}{2} \left( \frac{\boldsymbol{x}_i - \boldsymbol{x}_{i-1}}{t_i - t_{i-1}} + \frac{\boldsymbol{x}_{i + 1} - \boldsymbol{x}_i}{t_{i + 1} - t_i} \right) \end{equation*}

There are even sources (e.g. Wikipedia) which show yet a simpler (but even less correct, except in the uniform case) equation:

\begin{equation*} \boldsymbol{\dot{x}}_i = \frac{\boldsymbol{x}_{i + 1} - \boldsymbol{x}_{i - 1}}{t_{i + 1} - t_{i - 1}} \end{equation*}

Cusps and Self-Intersections

Uniform parametrization typically works very well if the (Euclidean) distances between consecutive vertices are all similar. However, if the distances are very different, the shape of the spline often turns out to be unexpected. Most notably, in extreme cases there might be even cusps or self-intersections within a spline segment.

def plot_catmull_rom(*args, **kwargs):
    plot_spline_2d(splines.CatmullRom(*args, endconditions='closed', **kwargs))

points3 = [
    (0, 0),
    (0, 0.5),
    (1.5, 1.5),
    (1.6, 1.5),
    (3, 0.2),
    (3, 0),
]

plot_catmull_rom(points3)

We can try to compensate this by manually selecting some non-uniform time instances:

times3 = 0, 0.2, 0.9, 1, 3, 3.3, 4.5

plot_catmull_rom(points3, times3)

Time values can be chosen by trial and error, but there are also ways to choose the time values automatically, as shown in the following sections.

Chordal Parameterization

One way to go about this is to measure the (Euclidean) distances between consecutive vertices (i.e. the “chordal lengths”) and simply use those distances as time intervals:

distances = np.linalg.norm(np.diff(points3 + points3[:1], axis=0), axis=1)
distances

array([0.5       , 1.80277564, 0.1       , 1.91049732, 0.2       ,
       3.        ])

times4 = np.concatenate([[0], np.cumsum(distances)])
times4

array([0.        , 0.5       , 2.30277564, 2.40277564, 4.31327296,
       4.51327296, 7.51327296])

plot_catmull_rom(points3, times4)

This makes the speed along the spline nearly constant, but the distance between the curve and its longer chords can become quite huge.

Centripetal Parameterization

As a variation of the previous method, the square roots of the chordal lengths can be used to define the time intervals.

times5 = np.concatenate([[0], np.cumsum(np.sqrt(distances))])
times5

array([0.        , 0.70710678, 2.04978159, 2.36600935, 3.74821676,
       4.19543036, 5.92748116])

plot_catmull_rom(points3, times5)

The curve takes its course much closer to the chords, but its speed is obviously far from constant.

Centripetal parameterization has the very nice property that it guarantees no cusps and no self-intersections, as shown by [YSK11]. The curve is also guaranteed to never “move away” from the successive vertex:

When centripetal parameterization is used with Catmull–Rom splines to define a path curve, the direction of motion for the object following this path will always be towards the next key-frame position.

—[YSK11], Section 7.2: “Path Curves”

Parameterized Parameterization

It turns out that the previous two parameterization schemes are just two special cases of a more general scheme for obtaining time intervals between control points:

\begin{equation*} t_{i+1} = t_i + |\boldsymbol{x}_{i+1} - \boldsymbol{x}_i|^\alpha, \text{ with } 0 \le \alpha \le 1. \end{equation*}

In the Python class splines.CatmullRom, the parameter alpha can be specified.

def plot_alpha(alpha, label):
    s = splines.CatmullRom(points3, alpha=alpha, endconditions='closed')
    plot_spline_2d(s, label=label)

plot_alpha(0, r'$\alpha = 0$ (uniform)')
plot_alpha(0.5, r'$\alpha = 0.5$ (centripetal)')
plot_alpha(0.75, r'$\alpha = 0.75$')
plot_alpha(1, r'$\alpha = 1$ (chordal)')
plt.legend(loc='center', numpoints=3);

<matplotlib.legend.Legend at 0x7fabe0ac4950>

As can be seen here (and as [YSK11] shows to be generally true), the uniform curve is farthest away from short chords and closest to long chords. The chordal curve behaves contrarily: closest to short chords and awkwardly far from long chords. The centripetal curve is closer to the uniform curve for long chords and closer to the chordal curve for short chords, providing a very good compromise.

Any value between \(0\) and \(1\) can be chosen for \(\alpha\), but \(\alpha = \frac{1}{2}\) (i.e. centripetal parameterization) stands out because it is the only one of them that guarantees no cusps and self-intersections:

In this paper we prove that, for cubic Catmull–Rom curves, centripetal parameterization is the only parameterization in this family that guarantees that the curves do not form cusps or self-intersections within curve segments.

—[YSK11], abstract

[…] we mathematically prove that centripetal parameterization of Catmull–Rom curves guarantees that the curve segments cannot form cusps or local self-intersections, while such undesired features can be formed with all other possible parameterizations within this class.

—[YSK11], Section 1: “Introduction”

Cusps and self-intersections are very common with Catmull–Rom curves for most parameterization choices. In fact, as we will show here, the only parameterization choice that guarantees no cusps and self-intersections within curve segments is centripetal parameterization.

—[YSK11], Section 3: “Cusps and Self-Intersections”