Gegeben sind $n$ Punkte $p_0$ bis $p_{n-1}$, durch welche eine geschlossene Kurve gelegt werden soll. Diese Kurve soll möglichst “angenehm” zu fahren sein, d.h. die Beschleunigungen sind klein und vor allem soll die Beschleunigung stetig sein.

Die Kurve soll stückweise kubisch sein, d.h. durch Bezierkurven darstellbar.

Wir beschränken uns erst einmal auf den eindimensionalen Fall auf dem Intervall $t \in [0,1]$. Gesucht ist eine kubische Funktion $f(x)$ so, dass $$ f(0)=x_0,\quad f(1)=x_1, \quad f'(0) = m_0 \text{ und} \quad f'(1)=m_1. $$

Bestimmen Sie die kubischen Funktionen für folgende Parameter:

Zeigen Sie, dass $f(t) = x_0 h_{0,0}(t) + x_1 h_{1,0}(t)+ m_0 h{0,1}(t) + m_1 h_{1,1}(t)$ eine Lösung für das oben gestellte Problem ist.

Bestimmen Sie die zweiten Ableitungen der obigen Funktionen.

Für allgemeine Funktionen ergibt sich die zweite Ableitung für $t=0$ und $t=1$:

$f''(0) = -6x_0+6x_1-4m_0-2 m_1$ und $f''(1) = 6x_0-6x_1+2m_0+4m_1$.

Siehe auch: https://de.wikipedia.org/wiki/Kubisch_Hermitescher_Spline

Sind $n$ Werte $x_0$ bis $x_{n-1}$ gegeben sind die Steigungen $m_0$ bis $m_{n-1}$ so zu bestimmen, dass $$ f''_{i}(1) = f''_{i+1}(0) $$ (Die Indizies sind modulo $n$ aufzufassen, da die Kurve geschlossen werden soll, d.h. $f_{n}=f_{0}$ etc.)

Damit haben wir $n$ Unbekannte und $n$ Gleichungen der Form: $$ \begin{align*} f''_{i}(1) & = & f''_{i+1}(0) \\ 6x_i-6x_{i+1}+2m_i+4m_{i+1} & = & -6x_{i+1}+6x_{i+2}-4m_{i+1}-2m_{i+2}\\ 2m_i+4m_{i+1} & = & -6x_i+6x_{i+2}-4m_{i+1}-2m_{i+2}\\ 2m_i+8m_{i+1}+2m_{i+2} & = & -6x_i+6x_{i+2}\\ m_i+4m_{i+1}+m_{i+2} & = & -3x_i+3x_{i+2}\\ \end{align*} $$ In matrizieller Form geschrieben: \[ \begin{pmatrix} 1 & 4 & 1 & 0 & 0 & \cdots & 0 \\\\ 0 & 1 & 4 & 1 & 0 & \cdots & 0 \\\\ 0 & 0 & 1 & 4 & 1 & \cdots & 0 \\\\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\\\ 4 & 1 & 0 & 0 & 0 & \cdots & 1 \\\\ \end{pmatrix} \cdot \begin{pmatrix} m_0 \\\\ m_1 \\\\ m_2 \\\\ \vdots \\\\ m_{n-1} \end{pmatrix} = \begin{pmatrix} -3 & 0 & 3 & 0 & 0 & \cdots & 0 \\\\ 0 & -3 & 0 & 3 & 0 & \cdots & 0 \\\\ 0 & 0 & -3 & 0 & 3 & \cdots & 0 \\\\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\\\ 0 & 3 & 0 & 0 & 0 & \cdots & -3 \\\\ \end{pmatrix} \cdot \begin{pmatrix} x_0 \\\\ x_1 \\\\ x_2 \\\\ \vdots \\\\ x_{n-1} \\\\ \end{pmatrix} \]

In Python (hier Blender Code) sieht das dann z.B. wie folgt aus:

import bpy
import numpy as np
 
 
n=5
M = np.zeros((n,n))
X = np.zeros((n,n))
x = np.array([0,4,1,3,1])
for i in range(n):
    M[i][i] = 1
    M[i][(i+1)%n] = 4
    M[i][(i+2)%n] = 1
    X[i][i] = -3
    X[i][(i+2)%n] = 3
 
print(M) 
print(X)
print(x)
x = np.dot(X,x)
print(x)
m = np.linalg.solve(M,x)
print(m)

Da wir wissen, dass für eine Bezierkurve $p(t)$ folgendes gilt: $p'(0) = 3(P_1-P_0)$. Und im eindimensionalen Fall gilt $p(0) = x_0$ und $p'(0)=m_0$, also

\begin{align*} p'(0) & = & m_0 \\ 3(P_1- x_0) & = & m_0 \\ P_1 & = & \frac{1}{3}m_0+x_0 \end{align*}

Analog für $P_2$:

\begin{align*} p'(1) & = & m_1 \\ 3(x_1- P_2) & = & m_1 \\ P_2 & = & -\frac{1}{3}m_1+x_1 \end{align*}

Die komplette Berechnung kann für alle Dimensionen unabhängig durchgeführt werden. Damit erhalten wir die Kontrollpunkte der Bezierkurven für eine ruckelfreie Bahn durch $n$ Punkte.

Wie man es noch viel viel besser machen könnte: https://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/CSD-93-732.pdf Siehe z.B. S. 96 (was hier vorgeschlagen ist) und S. 97 (was möglich wäre, aber nicht wirklich in unserem Rahmen hier)…

I.A. sind die Punkte $p_i$ nicht äquidistant, daher macht es Sinn die kubischen Funktionen auf den Intervallen $[0,a_i]$ zu bestimmen, wobei $a_i$ z.B. die Distanz der Punkte (oder die Länge einer vorhergehenden Bezierkurve ist).

Gegeben: $a$, $x_0$, $x_1$, $m_0$, $m_1$. Gesucht: Kubische Funktion $g(t)$ so, dass $g(0)=x_0$, $g'(0)=m_0$, $g(a)=x_1$, $g'(a)=m_1$.

Ansatz: $g(t) = f\left(\frac{t}{a}\right)$ wobei $f$ auf dem Intervall $[0,1]$ definiert ist. Damit gilt $g'(t) = f'\left(\frac{t}{a}\right) \cdot \frac{1}{a}$ d.h. $a \cdot g'(t) = f'\left(\frac{t}{a}\right)$.

Wir suchen also $f$ kubisch mit $f'(0)=am_0$ und $f'(1)=am_1$.

Für die zweite Ableitung gilt:

$g'(t) = f''\left(\frac{t}{a}\right) \cdot \frac{1}{a^2}$, d.h. $a^2 \cdot g'(t) = f''\left(\frac{t}{a}\right)$.

Wir suchen also $g_i$ mit $g_i(0)=x_i$, $g_i(a_i) = x_{i+1}$, $g'_i(a_i) = g'_{i+1}(0)$ und $g''_i(a_i) = g''_{i+1}(0)$.

Seien $m_i$ die unbekannten Steigungen von $g_i$ bei $t=0$ (und damit von $g_{i-1}$ bei $t=a_{i-1}$.)

Damit ist $$ g_i(t) = x_i \cdot h_{0,0}\left(\frac{t}{a_i}\right) + x_{i+1} \cdot h_{1,0}\left(\frac{t}{a_i}\right) + a_i \cdot m_i \cdot h_{0,1}\left(\frac{t}{a_i}\right) + a_i \cdot m_{i+1} \cdot h_{1,1}\left(\frac{t}{a_i}\right) $$ und $$ g''_i(t) = \frac{1}{a_i^2} x_i \cdot h''_{0,0}\left(\frac{t}{a_i}\right) + \frac{1}{a_i^2} x_{i+1} \cdot h''_{1,0}\left(\frac{t}{a_i}\right) + \frac{1}{a_i} \cdot m_i \cdot h_{0,1}\left(\frac{t}{a}\right) + \frac{1}{a_i} \cdot m_{i+1} \cdot h_{1,1}\left(\frac{t}{a}\right) $$

Zur Erinnerung: $f''(0) = -6x_0+6x_1-4m_0-2 m_1$ und $f''(1) = 6x_0-6x_1+2m_0+4m_1$, wobei hier $m_0$ und $m_1$ durch $a_i\cdot m_i$ und $a_i\cdot m_{i+1}$ zu ersetzen sind und es gilt $g''_i(t) = \frac{1}{a_i^2} f''(t)$.

Bei $t=0$ und $t=a_i$ ausgewertet: $$ g''_i(0) = \frac{1}{a_i^2}(-6x_i+6x_{i+1}) + \frac{1}{a_i}(-4m_i-2m_{i+1}) $$ und $$ g''_i(a_i) = \frac{1}{a_i^2}(6x_i-6x_{i+1}) + \frac{1}{a_i}(2m_i+4m_{i+1}) $$

Schliesslich die $n$ Gleichungen für $m_i$: $$ g''_i(a_i) = g''_{i+1}(0) $$ Ausgeschrieben: $$ \frac{1}{a_i^2}(6x_i-6x_{i+1}) + \frac{1}{a_i}(2m_i+4m_{i+1}) = g''_{i+1}(0) = \frac{1}{a_{i+1}^2}(-6x_{i+1}+6x_{i+2}) + \frac{1}{a_{i+1}}(-4m_{i+1}-2m_{i+2}) $$ Variablen nach links, Konstanten nach rechts: $$ \frac{1}{a_i}(2m_i+4m_{i+1}) - \frac{1}{a_{i+1}}(-4m_{i+1}-2m_{i+2}) = \frac{1}{a_{i+1}^2}(-6x_{i+1}+6x_{i+2}) - \frac{1}{a_i^2}(6x_i-6x_{i+1}) $$ Zusammenfassen: $$ \frac{2}{a_i}m_i +m_{i+1} \cdot \left(\frac{4}{a_i}+\frac{4}{a_{i+1}}\right) +\frac{2}{a_{i+1}}\cdot m_{i+2} = \frac{1}{a_{i+1}^2}(-6x_{i+1}+6x_{i+2}) - \frac{1}{a_i^2}(6x_i-6x_{i+1}) $$