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

Non-Uniform Kochanek–Bartels Splines

[KB84] mainly talks about uniform splines. Only in section 4, “Adjustments for Parameter Step Size”, they briefly mention the non-uniform case.

TODO: show equations for adjusted tangents

Unfortunately, this is wrong.

TODO: show why it is wrong.

Instead, we should start from the correct tangent vector for non-uniform Catmull–Rom splines:

\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*}

Parameters

In general incoming tangent \(\boldsymbol{\dot{x}}_i^{(-)}\) and 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)^2 (\boldsymbol{x}_i - \boldsymbol{x}_{i-1}) + b_i (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})}\\ \boldsymbol{\dot{x}}_i^{(-)} &= \frac{ c_i (t_{i+1} - t_i)^2 (\boldsymbol{x}_i - \boldsymbol{x}_{i-1}) + d_i (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{align*}

In the calculation below, we consider the outgoing tangent at \(\boldsymbol{x}_4\) and the incoming tangent at \(\boldsymbol{x}_5\).

\begin{align*} a_4 &= (1 - T_4) (1 + C_4) (1 + B_4)\\ b_4 &= (1 - T_4) (1 - C_4) (1 - B_4)\\ c_5 &= (1 - T_5) (1 - C_5) (1 + B_5)\\ d_5 &= (1 - T_5) (1 + C_5) (1 - B_5) \end{align*}

\begin{align*} \boldsymbol{\dot{x}}_4^{(+)} &= \frac{ a_4 (t_5 - t_4)^2 (\boldsymbol{x}_4 - \boldsymbol{x}_3) + b_4 (t_4 - t_3)^2 (\boldsymbol{x}_5 - \boldsymbol{x}_4) }{(t_5 - t_4) (t_4 - t_3) (t_5 - t_3)}\\ \boldsymbol{\dot{x}}_5^{(-)} &= \frac{ c_5 (t_6 - t_5)^2 (\boldsymbol{x}_5 - \boldsymbol{x}_4) + d_5 (t_5 - t_4)^2 (\boldsymbol{x}_6 - \boldsymbol{x}_5) }{(t_6 - t_5) (t_5 - t_4) (t_6 - t_4)} \end{align*}

Calculation

import sympy as sp
sp.init_printing()

from utility import NamedExpression, NamedMatrix

x3, x4, x5, x6 = sp.symbols('xbm3:7')

t, t3, t4, t5, t6 = sp.symbols('t t3:7')

Same control values as Catmull-Rom …

control_values_KB = sp.Matrix([x3, x4, x5, x6])
control_values_KB

$\displaystyle \left[\begin{matrix}\boldsymbol{x}_{3}\\\boldsymbol{x}_{4}\\\boldsymbol{x}_{5}\\\boldsymbol{x}_{6}\end{matrix}\right]$

… but three additional parameters per vertex. In our calculation, the parameters belonging to \(\boldsymbol{x}_4\) and \(\boldsymbol{x}_5\) are relevant:

T4, T5 = sp.symbols('T4 T5')
C4, C5 = sp.symbols('C4 C5')
B4, B5 = sp.symbols('B4 B5')

a4 = NamedExpression('a4', (1 - T4) * (1 + C4) * (1 + B4))
b4 = NamedExpression('b4', (1 - T4) * (1 - C4) * (1 - B4))
c5 = NamedExpression('c5', (1 - T5) * (1 - C5) * (1 + B5))
d5 = NamedExpression('d5', (1 - T5) * (1 + C5) * (1 - B5))
display(a4, b4, c5, d5)

$\displaystyle a_{4} = \left(1 - T_{4}\right) \left(B_{4} + 1\right) \left(C_{4} + 1\right)$

$\displaystyle b_{4} = \left(1 - B_{4}\right) \left(1 - C_{4}\right) \left(1 - T_{4}\right)$

$\displaystyle c_{5} = \left(1 - C_{5}\right) \left(1 - T_{5}\right) \left(B_{5} + 1\right)$

$\displaystyle d_{5} = \left(1 - B_{5}\right) \left(1 - T_{5}\right) \left(C_{5} + 1\right)$

xd4 = NamedExpression(
    'xdotbm4^(+)',
    (a4.name * (t5 - t4)**2 * (x4 - x3) + b4.name * (t4 - t3)**2 * (x5 - x4)) /
    ((t5 - t4) * (t4 - t3) * (t5 - t3)))
xd5 = NamedExpression(
    'xdotbm5^(-)',
    (c5.name * (t6 - t5)**2 * (x5 - x4) + d5.name * (t5 - t4)**2 * (x6 - x5)) /
    ((t6 - t5) * (t5 - t4) * (t6 - t4)))
display(xd4, xd5)

$\displaystyle \boldsymbol{\dot{x}}^{(+)}_{4} = \frac{a_{4} \left(- t_{4} + t_{5}\right)^{2} \left(- \boldsymbol{x}_{3} + \boldsymbol{x}_{4}\right) + b_{4} \left(- t_{3} + t_{4}\right)^{2} \left(- \boldsymbol{x}_{4} + \boldsymbol{x}_{5}\right)}{\left(- t_{3} + t_{4}\right) \left(- t_{3} + t_{5}\right) \left(- t_{4} + t_{5}\right)}$

$\displaystyle \boldsymbol{\dot{x}}^{(-)}_{5} = \frac{c_{5} \left(- t_{5} + t_{6}\right)^{2} \left(- \boldsymbol{x}_{4} + \boldsymbol{x}_{5}\right) + d_{5} \left(- t_{4} + t_{5}\right)^{2} \left(- \boldsymbol{x}_{5} + \boldsymbol{x}_{6}\right)}{\left(- t_{4} + t_{5}\right) \left(- t_{4} + t_{6}\right) \left(- t_{5} + t_{6}\right)}$

display(xd4.subs_symbols(a4, b4))
display(xd5.subs_symbols(c5, d5))

$\displaystyle \boldsymbol{\dot{x}}^{(+)}_{4} = \frac{\left(1 - B_{4}\right) \left(1 - C_{4}\right) \left(1 - T_{4}\right) \left(- t_{3} + t_{4}\right)^{2} \left(- \boldsymbol{x}_{4} + \boldsymbol{x}_{5}\right) + \left(1 - T_{4}\right) \left(B_{4} + 1\right) \left(C_{4} + 1\right) \left(- t_{4} + t_{5}\right)^{2} \left(- \boldsymbol{x}_{3} + \boldsymbol{x}_{4}\right)}{\left(- t_{3} + t_{4}\right) \left(- t_{3} + t_{5}\right) \left(- t_{4} + t_{5}\right)}$

$\displaystyle \boldsymbol{\dot{x}}^{(-)}_{5} = \frac{\left(1 - B_{5}\right) \left(1 - T_{5}\right) \left(C_{5} + 1\right) \left(- t_{4} + t_{5}\right)^{2} \left(- \boldsymbol{x}_{5} + \boldsymbol{x}_{6}\right) + \left(1 - C_{5}\right) \left(1 - T_{5}\right) \left(B_{5} + 1\right) \left(- t_{5} + t_{6}\right)^{2} \left(- \boldsymbol{x}_{4} + \boldsymbol{x}_{5}\right)}{\left(- t_{4} + t_{5}\right) \left(- t_{4} + t_{6}\right) \left(- t_{5} + t_{6}\right)}$

Same as with Catmull-Rom, try to find a transformation from cardinal control values to Hermite control values. This can be used to get the full basis matrix.

control_values_H = sp.Matrix([x4, x5, xd4.name, xd5.name])
control_values_H

$\displaystyle \left[\begin{matrix}\boldsymbol{x}_{4}\\\boldsymbol{x}_{5}\\\boldsymbol{\dot{x}}^{(+)}_{4}\\\boldsymbol{\dot{x}}^{(-)}_{5}\end{matrix}\right]$

From the notebook about non-uniform Hermite splines:

M_H = NamedMatrix(
    r'{M_{\text{H},4}}',
    sp.Matrix([[2, -2, 1, 1],
               [-3, 3, -2, -1],
               [0, 0, 1, 0],
               [1, 0, 0, 0]]) * sp.diag(1, 1, t5 - t4, t5 - t4))
M_H

$\displaystyle {M_{\text{H},4}} = \left[\begin{matrix}2 & -2 & - t_{4} + t_{5} & - t_{4} + t_{5}\\-3 & 3 & 2 t_{4} - 2 t_{5} & t_{4} - t_{5}\\0 & 0 & - t_{4} + t_{5} & 0\\1 & 0 & 0 & 0\end{matrix}\right]$

M_KBtoH = NamedMatrix(r'{M_{\text{KB$,4\to$H},4}}', 4, 4)
M_KB = NamedMatrix(r'{M_{\text{KB},4}}', M_H.name * M_KBtoH.name)
M_KB

$\displaystyle {M_{\text{KB},4}} = {M_{\text{H},4}} {M_{\text{KB$,4\to$H},4}}$

NamedMatrix(control_values_H, M_KBtoH.name * control_values_KB)

$\displaystyle \left[\begin{matrix}\boldsymbol{x}_{4}\\\boldsymbol{x}_{5}\\\boldsymbol{\dot{x}}^{(+)}_{4}\\\boldsymbol{\dot{x}}^{(-)}_{5}\end{matrix}\right] = {M_{\text{KB$,4\to$H},4}} \left[\begin{matrix}\boldsymbol{x}_{3}\\\boldsymbol{x}_{4}\\\boldsymbol{x}_{5}\\\boldsymbol{x}_{6}\end{matrix}\right]$

If we substitute the above definitions of \(\boldsymbol{\dot{x}}_4^{(+)}\) and \(\boldsymbol{\dot{x}}_5^{(-)}\), we can directly read off the matrix elements:

M_KBtoH.expr = sp.Matrix([
    [expr.coeff(cv).simplify() for cv in control_values_KB]
    for expr in control_values_H.subs([xd4.args, xd5.args]).expand()])
M_KBtoH

$\displaystyle {M_{\text{KB$,4\to$H},4}} = \left[\begin{matrix}0 & 1 & 0 & 0\\0 & 0 & 1 & 0\\\frac{a_{4} \left(t_{4} - t_{5}\right)}{t_{3}^{2} - t_{3} t_{4} - t_{3} t_{5} + t_{4} t_{5}} & \frac{- a_{4} t_{4}^{2} + 2 a_{4} t_{4} t_{5} - a_{4} t_{5}^{2} + b_{4} t_{3}^{2} - 2 b_{4} t_{3} t_{4} + b_{4} t_{4}^{2}}{t_{3}^{2} t_{4} - t_{3}^{2} t_{5} - t_{3} t_{4}^{2} + t_{3} t_{5}^{2} + t_{4}^{2} t_{5} - t_{4} t_{5}^{2}} & \frac{b_{4} \left(- t_{3} + t_{4}\right)}{t_{3} t_{4} - t_{3} t_{5} - t_{4} t_{5} + t_{5}^{2}} & 0\\0 & \frac{c_{5} \left(t_{5} - t_{6}\right)}{t_{4}^{2} - t_{4} t_{5} - t_{4} t_{6} + t_{5} t_{6}} & \frac{- c_{5} t_{5}^{2} + 2 c_{5} t_{5} t_{6} - c_{5} t_{6}^{2} + d_{5} t_{4}^{2} - 2 d_{5} t_{4} t_{5} + d_{5} t_{5}^{2}}{t_{4}^{2} t_{5} - t_{4}^{2} t_{6} - t_{4} t_{5}^{2} + t_{4} t_{6}^{2} + t_{5}^{2} t_{6} - t_{5} t_{6}^{2}} & \frac{d_{5} \left(- t_{4} + t_{5}\right)}{t_{4} t_{5} - t_{4} t_{6} - t_{5} t_{6} + t_{6}^{2}}\end{matrix}\right]$

delta3, delta4, delta5 = sp.symbols('Delta3:6')
deltas = {
    t3: 0,
    t4: delta3,
    t5: delta3 + delta4,
    t6: delta3 + delta4 + delta5,
}

M_KBtoH.subs(deltas).simplify()

$\displaystyle {M_{\text{KB$,4\to$H},4}} = \left[\begin{matrix}0 & 1 & 0 & 0\\0 & 0 & 1 & 0\\- \frac{\Delta_{4} a_{4}}{\Delta_{3} \left(\Delta_{3} + \Delta_{4}\right)} & \frac{- \Delta_{3}^{2} b_{4} + \Delta_{4}^{2} a_{4}}{\Delta_{3} \Delta_{4} \left(\Delta_{3} + \Delta_{4}\right)} & \frac{\Delta_{3} b_{4}}{\Delta_{4} \left(\Delta_{3} + \Delta_{4}\right)} & 0\\0 & - \frac{\Delta_{5} c_{5}}{\Delta_{4} \left(\Delta_{4} + \Delta_{5}\right)} & \frac{- \Delta_{4}^{2} d_{5} + \Delta_{5}^{2} c_{5}}{\Delta_{4} \Delta_{5} \left(\Delta_{4} + \Delta_{5}\right)} & \frac{\Delta_{4} d_{5}}{\Delta_{5} \left(\Delta_{4} + \Delta_{5}\right)}\end{matrix}\right]$

M_KB = M_KB.subs_symbols(M_H, M_KBtoH).doit()
M_KB.subs(deltas).expand()

$\displaystyle {M_{\text{KB},4}} = \left[\begin{matrix}- \frac{\Delta_{4}^{2} a_{4}}{\Delta_{3}^{2} + \Delta_{3} \Delta_{4}} & \frac{\Delta_{3}^{2} \Delta_{4} b_{4}}{- \Delta_{3}^{2} \Delta_{4} - \Delta_{3} \Delta_{4}^{2}} - \frac{\Delta_{4}^{3} a_{4}}{- \Delta_{3}^{2} \Delta_{4} - \Delta_{3} \Delta_{4}^{2}} - \frac{\Delta_{4} \Delta_{5} c_{5}}{\Delta_{4}^{2} + \Delta_{4} \Delta_{5}} + 2 & \frac{\Delta_{3} \Delta_{4} b_{4}}{\Delta_{3} \Delta_{4} + \Delta_{4}^{2}} + \frac{\Delta_{4}^{3} d_{5}}{- \Delta_{4}^{2} \Delta_{5} - \Delta_{4} \Delta_{5}^{2}} - \frac{\Delta_{4} \Delta_{5}^{2} c_{5}}{- \Delta_{4}^{2} \Delta_{5} - \Delta_{4} \Delta_{5}^{2}} - 2 & \frac{\Delta_{4}^{2} d_{5}}{\Delta_{4} \Delta_{5} + \Delta_{5}^{2}}\\\frac{2 \Delta_{4}^{2} a_{4}}{\Delta_{3}^{2} + \Delta_{3} \Delta_{4}} & - \frac{2 \Delta_{3}^{2} \Delta_{4} b_{4}}{- \Delta_{3}^{2} \Delta_{4} - \Delta_{3} \Delta_{4}^{2}} + \frac{2 \Delta_{4}^{3} a_{4}}{- \Delta_{3}^{2} \Delta_{4} - \Delta_{3} \Delta_{4}^{2}} + \frac{\Delta_{4} \Delta_{5} c_{5}}{\Delta_{4}^{2} + \Delta_{4} \Delta_{5}} - 3 & - \frac{2 \Delta_{3} \Delta_{4} b_{4}}{\Delta_{3} \Delta_{4} + \Delta_{4}^{2}} - \frac{\Delta_{4}^{3} d_{5}}{- \Delta_{4}^{2} \Delta_{5} - \Delta_{4} \Delta_{5}^{2}} + \frac{\Delta_{4} \Delta_{5}^{2} c_{5}}{- \Delta_{4}^{2} \Delta_{5} - \Delta_{4} \Delta_{5}^{2}} + 3 & - \frac{\Delta_{4}^{2} d_{5}}{\Delta_{4} \Delta_{5} + \Delta_{5}^{2}}\\- \frac{\Delta_{4}^{2} a_{4}}{\Delta_{3}^{2} + \Delta_{3} \Delta_{4}} & \frac{\Delta_{3}^{2} \Delta_{4} b_{4}}{- \Delta_{3}^{2} \Delta_{4} - \Delta_{3} \Delta_{4}^{2}} - \frac{\Delta_{4}^{3} a_{4}}{- \Delta_{3}^{2} \Delta_{4} - \Delta_{3} \Delta_{4}^{2}} & \frac{\Delta_{3} \Delta_{4} b_{4}}{\Delta_{3} \Delta_{4} + \Delta_{4}^{2}} & 0\\0 & 1 & 0 & 0\end{matrix}\right]$

And for completeness’ sake, its inverse:

M_KB.subs(deltas).expand().I

$\displaystyle {M_{\text{KB},4}}^{-1} = \left[\begin{matrix}\frac{\Delta_{3}^{2} b_{4}}{\Delta_{4}^{2} a_{4}} & \frac{\Delta_{3}^{2} b_{4}}{\Delta_{4}^{2} a_{4}} & \frac{\Delta_{3} \left(\Delta_{3} b_{4} - \Delta_{3} - \Delta_{4}\right)}{\Delta_{4}^{2} a_{4}} & 1\\0 & 0 & 0 & 1\\1 & 1 & 1 & 1\\\frac{\Delta_{4}^{2} d_{5} + 3 \Delta_{4} \Delta_{5} - \Delta_{5}^{2} c_{5} + 3 \Delta_{5}^{2}}{\Delta_{4}^{2} d_{5}} & \frac{\Delta_{4}^{2} d_{5} + 2 \Delta_{4} \Delta_{5} - \Delta_{5}^{2} c_{5} + 2 \Delta_{5}^{2}}{\Delta_{4}^{2} d_{5}} & \frac{\Delta_{4}^{2} d_{5} + \Delta_{4} \Delta_{5} - \Delta_{5}^{2} c_{5} + \Delta_{5}^{2}}{\Delta_{4}^{2} d_{5}} & 1\end{matrix}\right]$

TODO: plot some example curves