This page was generated from doc/euclidean/re-parameterization.ipynb. Interactive online version: .

Re-Parameterization

As we have seen previously – for example with Hermite splines and Catmull–Rom splines – changing the relative amount of time (or more generally, the relative size of the parameter interval) per spline segment leads to different curve shapes. Given the same underlying polynomials, we cannot simply re-scale the parameter values without affecting the shape of the curve.

However, sometimes we want to keep the shape (or more accurately, the image) of a curve intact and only change its timing.

This can be done by introducing a function that maps from a new set of parameter values to the parameter values of the original spline.

Arc-Length Parameterization

Instead of using a curve \(\boldsymbol{x}(t)\) with a free parameter \(t\) (which we often interpret as time), it is sometimes useful to have a curve \(\boldsymbol{x}_\text{arc}(s)\) with the same image but where the parameter \(s\) represents the distance travelled since the beginning of the curve. The length of a piece of curve is called arc length and therefore \(\boldsymbol{x}_\text{arc}(s)\) is called arc-length parameterized. Sometimes, this is also called “natural” parameterization – not to be confused with natural splines and natural end conditions.

An interesting (and slightly confusing) thing to do now, is to use \(\boldsymbol{x}_\text{arc}(s)\) with time as a parameter. Note that the speed along a curve is calculated as distance per time interval (\(v = \frac{ds}{dt}\)), but if time and distance are the same (\(s \equiv t\)), we get a constant speed \(v = \frac{ds}{ds} = 1\). In other words, the tangent vector of an arc-length parameterized curve always has unit length.

To turn an existing curve \(\boldsymbol{x}(t)\) into its arc-length parameterized counterpart \(\boldsymbol{x}_\text{arc}(s)\), we need the parameter \(t\) as function of travelled distance \(s\), i.e. \(t(s)\):

\begin{equation*} \boldsymbol{x}_\text{arc}(s) = \boldsymbol{x}(t(s)) \end{equation*}

Sadly, we don’t know \(t(s)\), but we can find \(s(t)\) and then try to find the inverse function.

Let’s look at the tangent vector \(\frac{d}{d\tau} \boldsymbol{x}(\tau)\) (i.e. the velocity) at every infinitesimally small time interval \(d\tau\). The length travelled along the curve in that time interval is the length of the tangent vector \(\left|\frac{d}{d\tau} \boldsymbol{x}(\tau)\right|\) (i.e. the speed) multiplied by the time interval \(d\tau\). Adding all these small pieces from \(t_0\) to \(t\) results in the arc length

\begin{equation*} s(t) = \int\limits_{t_0}^t \left| \frac{d}{d\tau}\boldsymbol{x}(\tau) \right| d\tau. \end{equation*}

This looks straightforward enough, but it turns out that this integral cannot be solved analytically if \(\boldsymbol{x}(t)\) is cubic (or of higher degree). The reason for that is the Abel–Ruffini theorem.

We’ll have to use numerical integration instead.

Finally, we need to invert this function. In other words, given an arc length \(s\), we have to provide a way to obtain the corresponding \(t\). This can be reduced to a root finding problem, which can be solved with different numerical methods, for example with the bisection method.

Arc-length re-parameterization is implemented in the Python class splines.UnitSpeedAdapter. This is using scipy.integrate.quad() for numerical integration and scipy.optimize.bisect() for root finding.

Let’s show an example spline using the vertices from the section about centripetal parameterization:

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

import splines
from helper import plot_spline_2d

First we create a centripetal Catmull–Rom spline …

s1 = splines.CatmullRom(points4, alpha=0.5, endconditions='closed')

… which we then convert to an arc-length parameterized spline:

s2 = splines.UnitSpeedAdapter(s1)

%%time
plot_spline_2d(s1, dots_per_second=10)

CPU times: user 36.1 ms, sys: 4 ms, total: 40.1 ms
Wall time: 39.9 ms

Evaluating the arc-length parameterized spline takes quite a bit longer:

%%time
plot_spline_2d(s2, dots_per_second=10)

CPU times: user 2.65 s, sys: 2.62 ms, total: 2.65 s
Wall time: 2.65 s

We are plotting 10 dots per second, and we can count about 10 dots per unit of distance, which confirms that the spline has a speed of 1.

Spline-Based Re-Parameterization

We can choose any function to map a new parameter to old parameter values. Since we are already talking about splines, we might as well use a one-dimensional spline. To rule out backwards movement along the original spline, we should use use a monotone spline as implemented, for example, in the class splines.MonotoneCubic.

A tool for re-parameterizing an existing spline is available in the class splines.NewGridAdapter.

This is especially useful when applied to an already arc-length parameterized spline, because then the slope of the parameter re-mapping function directly corresponds to the speed along the spline.

Not all new parameter values have to be explicitly given. If unspecified, they are interpolated from the surrounding values.

For closed curves it might be useful to have the same slope at the beginning and the end of the spline. This can be achieved by using cyclic=True.

new_grid = [-1, -0.5, None, None, 2, None, 3]
s3 = splines.NewGridAdapter(s2, new_grid, cyclic=True)
s3.grid

[-1, -0.5, 1.0334250405837566, 1.0992464899992567, 2, 2.0730953134961054, 3]

%%time
plot_spline_2d(s3, dots_per_second=10)

CPU times: user 1.39 s, sys: 0 ns, total: 1.39 s
Wall time: 1.39 s