This page was generated from doc/euclidean/kochanek-bartels-non-uniform.ipynb. Interactive online version: Binder badge.

Non-Uniform Kochanek–Bartels Splines#

Kochanek and Bartels [KB84] mainly talk about uniform splines. Only in section 4 – “Adjustments for Parameter Step Size” – do they briefly mention the non-uniform case and provide equations for “adjusted tangent vectors”:

The formulas […] assume an equal time spacing of key frames, implying an equal number of inbetweens within each key interval. A problem can exist if the animator requests a different number of inbetweens for adjacent intervals. […] If the same parametric derivative is used for both splines at \(P_i\), these different step sizes will cause a discontinuity in the speed of motion. What is required, if this discontinuity is not intentional, is a means of making a local adjustment to the interval separating successive frames before and after the key frame so that the speed of entry matches the speed of exit. This can be accomplished by adjusting the specification of the tangent vector at the key frame based on the number of inbetweens in the adjacent intervals. […] Once the tangent vectors have been found for an equal number of inbetweens in the adjacent intervals, the adjustment required for different numbers of inbetweens (\(N_{i-1}\) frames between \(P_{i-1}\) and \(P_i\) followed by \(N_i\) frames between \(P_i\) and \(P_{i+1}\)) can be made by weighting the tangent vectors appropriately:

\begin{align*} \text{adjusted } DD_i &= DD_i \frac{2 N_{i-1}}{N_{i-1} + N_i}\\ \text{adjusted } DS_i &= DS_i \frac{2 N_i}{N_{i-1} + N_i} \end{align*}

Kochanek and Bartels [KB84], section 4

In their notation, \(DS_i\) is the source derivative (i.e. the incoming tangent vector) at point \(P_i\), and \(DD_i\) is the destination derivative (i.e. the outgoing tangent vector). The point \(P_i\) corresponds to \(\boldsymbol{x}_i\) in our notation.

To be able to play around with that, let’s implement it in a function. It turns out that for the way we will be using this function, we have to use the reciprocal value of the adjustment mentioned in the paper:

[1]:
def kochanek_bartels_tangents(xs, ns):
    """Adjusted tangent vectors according to Kochanek & Bartels."""
    x_1, _, x1 = xs
    N_1, N0 = ns
    uniform = (x1 - x_1) / 2
    # NB: the K&B paper uses reciprocal weighting factors:
    incoming = uniform * (N_1 + N0) / (2 * N0)
    outgoing = uniform * (N_1 + N0) / (2 * N_1)
    return incoming, outgoing

We can see that the uniform tangents are re-scaled but their direction is unchanged.

This is a hint that – although the paper claims to be using Catmull–Rom splines – we’ll get different results than in the notebook about Catmull–Rom splines.

[2]:
import numpy as np
import matplotlib.pyplot as plt

Let’s import some helper functions from helper.py:

[3]:
from helper import plot_vertices_2d, plot_spline_2d

We’ll need the Hermite basis matrix that we derived in the notebook about uniform Hermite splines and which is also shown by Kochanek and Bartels [KB84] in equation 2:

[4]:
hermite_matrix = np.array([
    [ 2, -2,  1,  1],
    [-3,  3, -2, -1],
    [ 0,  0,  1,  0],
    [ 1,  0,  0,  0]])

Since the paper uses a different (implicit) re-scaling of parameter values (based on the numbers of inbetweens), we cannot use the classes from the splines module and have to re-implement everything from scratch:

[5]:
def pseudo_catmull_rom(xs, ns):
    """Closed Catmull-Rom spline according to Kochanek & Bartels."""
    xs = np.asarray(xs)
    L = len(xs)
    assert L >= 2
    assert L == len(ns)
    tangents = [
        tangent
        for i in range(L)
        for tangent in kochanek_bartels_tangents(
            [xs[i], xs[(i + 1) % L], xs[(i + 2) % L]],
            [ns[i], ns[(i + 1) % L]])
    ]
    # Move last (outgoing) tangent to the beginning:
    tangents = tangents[-1:] + tangents[:-1]
    ts = [
        np.linspace(0, 1, n + 1, endpoint=False).reshape(-1, 1)
        for n in ns]
    return np.concatenate([
        t**[3, 2, 1, 0] @ hermite_matrix @ [xs[i], xs[(i + 1) % L], v0, v1]
        for i, (t, v0, v1)
        in enumerate(zip(ts, tangents[::2], tangents[1::2]))])

Note

The @ operator is used here to do NumPy’s matrix multiplication.

Let’s plot an example:

[6]:
vertices1 = [
    (0, 0),
    (1, 1),
    (2, 0),
]
inbetweens1 = [
    5,
    20,
    15,
]
[7]:
plt.scatter(*pseudo_catmull_rom(vertices1, inbetweens1).T, marker='.')
plot_vertices_2d(vertices1, chords=False)
../_images/euclidean_kochanek-bartels-non-uniform_17_0.svg

This doesn’t look too bad, let’s plot the same thing with splines.CatmullRom for comparison.

[8]:
from splines import CatmullRom

In oder to be able to compare the results, we have to convert the discrete numbers of inbetweens into re-scaled parameter values:

[9]:
def inbetweens2times(inbetweens):
    return np.cumsum([0, *(n + 1 for n in inbetweens)])
[10]:
times1 = inbetweens2times(inbetweens1)

Now we have everything to create a non-uniform Catmull–Rom spline …

[11]:
cr_spline1 = CatmullRom(vertices1, times1, endconditions='closed')

… and plot it for direct comparison with the one suggested by Kochanek and Bartels:

[12]:
plt.plot(
    *pseudo_catmull_rom(vertices1, inbetweens1).T,
    marker='.', linestyle='', label='K&B')
plot_spline_2d(cr_spline1, dots_per_second=1, label='ours')
plt.legend(numpoints=3);
../_images/euclidean_kochanek-bartels-non-uniform_26_0.svg

Here we can clearly see that not only the lengths of the tangent vectors but also their directions have been adjusted according to the neighboring parameter intervals.

Let’s look at a different example:

[13]:
vertices2 = [
    (0, 0),
    (0, 0.5),
    (4.5, 1.5),
    (5, 1),
    (2, -1),
    (1.5, -1),
]
inbetweens2 = [
    2,
    15,
    3,
    12,
    2,
    10,
]
[14]:
times2 = inbetweens2times(inbetweens2)
[15]:
cr_spline2 = CatmullRom(vertices2, times2, endconditions='closed')
[16]:
plt.plot(
    *pseudo_catmull_rom(vertices2, inbetweens2).T,
    marker='.', linestyle='', label='K&B')
plot_spline_2d(cr_spline2, dots_per_second=1, label='ours')
plt.legend(numpoints=3);
../_images/euclidean_kochanek-bartels-non-uniform_32_0.svg

This should illustrate the shortcomings of the tangent vectors suggested by Kochanek and Bartels.

Instead of sticking with their suggestion, we use the correct expression for tangent vectors of non-uniform Catmull–Rom splines:

\begin{equation*} \boldsymbol{\dot{x}}_{i,\text{Catmull–Rom}} = \frac{ (t_{i+1} - t_i) \, \boldsymbol{v}_{i-1} + (t_i - t_{i-1}) \, \boldsymbol{v}_i }{ t_{i+1} - t_{i-1} }, \end{equation*}

where \(\boldsymbol{v}_i = \frac{\boldsymbol{x}_{i+1} - \boldsymbol{x}_i}{t_{i+1} - t_i}\).

To this equation, we can simply add the TCB parameters like we did in the notebook about uniform Kochanek–Bartels splines, leading to the following equations for the incoming tangent \(\boldsymbol{\dot{x}}_i^{(-)}\) and the outgoing tangent \(\boldsymbol{\dot{x}}_i^{(+)}\) at vertex \(\boldsymbol{x}_i\):

\begin{align*} a_i &= (1 - T_i) (1 + C_i) (1 + B_i)\\ b_i &= (1 - T_i) (1 - C_i) (1 - B_i)\\ c_i &= (1 - T_i) (1 - C_i) (1 + B_i)\\ d_i &= (1 - T_i) (1 + C_i) (1 - B_i) \end{align*}

\begin{align*} \boldsymbol{\dot{x}}_i^{(+)} &= \frac{ a_i (t_{i+1} - t_i) \, \boldsymbol{v}_{i-1} + b_i (t_i - t_{i-1}) \, \boldsymbol{v}_i }{t_{i+1} - t_{i-1}}\\ \boldsymbol{\dot{x}}_i^{(-)} &= \frac{ c_i (t_{i+1} - t_i) \, \boldsymbol{v}_{i-1} + d_i (t_i - t_{i-1}) \, \boldsymbol{v}_i }{t_{i+1} - t_{i-1}} \end{align*}

These equations are used in the implementation of the class splines.KochanekBartels.