Kubisch Hermitescher Spline

In dem mathematischen Teilgebiet der Numerik wird unter einem kubisch hermiteschen Spline (auch cSpline genannt) ein Spline verstanden der zwischen n Kontrollpunkten interpoliert. Die Kontrollpunkte sind durch n − 1 Segmente verbunden, die aus kubischen Hermiteschen Polynomen bestehen, die stetig differenzierbar ineinander übergehen. Dies bedeutet, dass eine Teilkurve genau da aufhört, wo die nächste beginnt und darüber hinaus die Tangenten der Segmente an ihren Grenzen übereinstimmen, wodurch sich ein weicher Übergang (ohne Knick) von Segment zu Segment ergibt. Die einzelnen Teilkurven sind durch Anfangs- und Endpunkt, sowie die eingehende und ausgehenden Tangente eindeutig bestimmt.

Besonders verbreitet ist diese Splinedefinition in Programmen der Computeranimation um zwischen einzelnen Keyframes, die auch unterschiedliche zeitliche Abstände voneinander haben können, zu interpolieren. Neben den kubischen Splines existieren auch noch Splines mit höherer oder niedrigerer Ordnung. Allerdings werden niedrigere Ordnungen als zu unflexibel eingestuft und höhere Ordnungen als zu aufwändig zu implementieren. Insbesondere tendieren Splines höherer Ordnung zu „Überschwingern“, was den Animator durch ungewollte Abläufe bei seiner Arbeit stören könnte. Hinzu kommt die effektive Möglichkeit die Tangenten berechnen und beeinflussen zu können, wie es zum Beispiel beim später behandelten Kochanek-Bartels-Spline der Fall ist. Ebenso steht die Definition eines Segments dieses Splines in enger Verwandtschaft zur kubischen Bézierkurve, sodass beide ineinander überführt werden können. Dadurch ist es möglich die Algorithmen für Bézierkurven (z. B. den De-Casteljau-Algorithmus) auch zur Berechnung und Darstellung von kubisch hermiteschen Splines zu verwenden.

Kubisch hermitescher Spline bestehend aus zwei Segmenten zwischen den Kontrollpunkten p₀, p₁ und p₂. Es ist ersichtlich, dass sich zwei Segmente jeweils einen gemeinsamen Kontrollpunkt und eine gemeinsame Tangente teilen.

Definition eines Segments

Im Einheitsintervall

Im Einheitsintervall [0,1] ist ein Segment des kubisch hermiteschen Splines durch folgende kubisch hermitesche Kurve definiert:

$\begin{align} c(t) \ & = \ (2p_0 - 2p_1 + m_0 + m_1) t^3 + (-3p_0 + 3p_1 - 2m_0 - m_1) t^2 + m_0 t + p_0 \\ \ & = \ \underbrace {(2t^3 - 3t^2 + 1)}_{h_{00}} p_0 + \underbrace{(-2t^3 + 3t^2)}_{h_{10}} p_1 + \underbrace{(t^3 - 2t^2 + t)}_{h_{01}} m_0 + \underbrace{(t^3 - t^2)}_{h_{11}} m_1 \qquad \text{mit} \ t \in [0,1] \end{align}$

Dabei ist p₀ der Startpunkt bei t = 0 und p₁ der Endpunkt bei t = 1. Die Punkte können dabei mehrdimensional sein und sind linear unabhängig voneinander. m₀ und m₁ sind die zugehörigen Tangenten am Start- und Endpunkt. Dabei ist anzumerken, dass die Tangente des Endpunktes in Fluchtrichtung zeigt. Sie ist nicht mit dem zweiten mittleren Kontrollpunkt der Bézierkurve gleichzusetzen, da die Definition sich grundsätzlich unterscheidet.

Anschaulicher lässt sich die Funktion in Matrixschreibweise darstellen:

$c(t) \ = \ T \, M_h \, C \ = \ \begin{bmatrix}t^3 & t^2 & t & 1\end{bmatrix} \begin{bmatrix}2 & -2 & 1 & 1 \\ -3 & 3 & -2 & -1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0\end{bmatrix} \begin{bmatrix}p_0 \\ p_1 \\ m_0 \\ m_1\end{bmatrix} \qquad \text{mit} \ t \in [0,1]$

M_h wird dabei als hermitesche Matrix bezeichnet.

Im Werteintervall

Im allgemeinen Intervall [x_k,x_{k + 1}] wird die Funktion entsprechend gestreckt, wodurch sich t aus der Gleichung t = (x − x_k) / (x_{k + 1} − x_k) ergibt und die Tangenten im gleichen Verhältnis skaliert werden müssen. Dadurch kommt der Abstand des Intervalls als zusätzlicher Parameter d hinzu, der sich aus d = x_{k + 1} − x_k ergibt, falls die Tangenten nicht bereits für das Werteintervall normiert sind. Im Falle einer Normierung ist d = 1.

$\begin{align} c(x) \ & = \ h_{00}(t) p_k + h_{10}(t) p_{k+1} + h_{01}(t) m_k d + h_{11}(t) m_{k+1} d \text{, mit } t = (x - x_k) / (x_{k+1} - x_k) \text{ und } d = x_{k+1} - x_k. \end{align}$

Herleitung

Es seien die Punkte p₀ und p₁ und ihre zugehörigen Tangenten m₀ und m₁ gegeben. Ebenso soll die gesuchte Funktion ein Polynom dritten Grades sein, das sich allgemein als x(t) = at³ + bt² + ct + d darstellen lässt.

Zugleich wird vorausgesetzt, dass zwei aneinandergesetzte Segmente sich den Anfangs- und Endpunkt teilen und ein weicher Übergang besteht, sie also dieselben Anfangs- und Endpunkt haben, sowie an diesen Stellen dieselbe Ableitung besitzen. Dadurch entstehen vier Bedingungen, die sich wie folgt beschreiben lassen:

$\begin{align} x(0) \ & = \ p_0 \\ x(1) \ & = \ p_1 \\ x'(0) \ & = \ m_0 \\ x'(1) \ & = \ m_1 \\ \end{align}$

Das eingangs erwähnte Polynom lässt sich anschaulich in Matrixform beschreiben:

$x(t) = \begin{bmatrix}t^3 & t^2 & t & 1 \end{bmatrix} \begin{bmatrix}a \\ b \\ c \\ d \end{bmatrix} = T C$

Daraus folgt für t = 0 und t = 1:

$\begin{align} x(0) \ & = \ p_0 \ = \ \begin{bmatrix}0 & 0 & 0 & 1\end{bmatrix} C \\ x(1) \ & = \ p_1 \ = \ \begin{bmatrix}1 & 1 & 1 & 1\end{bmatrix} C \end{align}$

Für die Tangenten muss die Funktion einmal nach t abgeleitet werden, sodass sich folgende Gleichungen ergeben:

$\begin{align} x'(t) \ & = \ \begin{bmatrix}3t^2 & 2t & 1 & 0\end{bmatrix} C \\ x'(0) \ & = \ m_0 \ = \ \begin{bmatrix} 0 & 0 & 1 & 0\end{bmatrix} C \\ x'(1) \ & = \ m_1 \ = \ \begin{bmatrix} 3 & 2 & 1 & 0\end{bmatrix} C \end{align}$

Die vier gewonnenen Beziehungen können wie folgt zusammengefasst werden:

$\begin{bmatrix}p_0 \\ p_1 \\ m_0 \\ m_1 \end{bmatrix} = \underbrace{\begin{bmatrix}0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 \\ 3 & 2 & 1 & 0\end{bmatrix}}_{A} C$

Nun kann die Gleichung durch Multiplikation mit der Inversen A ^{− 1} nach C aufgelöst werden.

$C \ = \ A^{-1} \begin{bmatrix}p_0 \\ p_1 \\ m_0 \\ m_1 \end{bmatrix} \ = \ \begin{bmatrix}2 & -2 & 1 & 1 \\ -3 & 3 & -2 & -1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0\end{bmatrix} \begin{bmatrix}p_0 \\ p_1 \\ m_0 \\ m_1 \end{bmatrix}$

Eingesetzt in die allgemeine kubische Gleichung x(t) ergibt sich die anfangs genannte Definition des Segments des kubisch hermiteschen Splines.^[1]

Darstellungen und Verwandtschaft

Plot der hermiteschen Basisfunktionen.

Die hermiteschen Basisfunktionen h₀₀,h₀₁,h₁₀,h₁₁ lassen sich auf unterschiedliche Weise darstellen, wodurch sich jeweils direkt verschiedene Eigenschaften der Kurvensegmente ablesen lassen.

Darstellung	$\boldsymbol{h_{00}(t)}$	$\boldsymbol{h_{01}(t)}$	$\boldsymbol{h_{10}(t)}$	$\boldsymbol{h_{11}(t)}$
expandiert	2t3 − 3t2 + 1	t3 − 2t2 + t	− 2t3 + 3t2	t3 − t2
faktorisiert	(1 + 2t)(1 − t)2	t(1 − t)2	t2(3 − 2t)	t2(t − 1)
Bernstein	B0(t) + B1(t)	$\frac 1 3 B_1(t)$	B2(t) + B3(t)	$-\frac 1 3 B_2(t)$

Die expandierte Form lässt sich direkt aus der Herleitung gewinnen und wird üblicherweise, wie auch hier, zur Definition benutzt.

Es ist direkt an der Faktorisierung ersichtlich, dass h₀₀ bei t = 1 eine Nullstelle besitzt und der Anstieg gleich 0 ist. Selbiges gilt für h₁₀ für t = 0. h₀₁ und h₁₁ besitzen hingegen eine Multiplizität von 2 und besitzen jeweils am Ende und Anfang des Definitionsbereichs von t eine Nullstelle.

Bei der Betrachtung der Bernsteinpolynome der 3. Ordnung $B_k(t)={3 \choose k} t^k (1-t)^{3-k}$ wird die Analogie zur kubischen Bézierkurve ersichtlich, deren Bernsteinpolynome B₀(t), B₁(t), B₂(t) und B₃(t) sind. Entsprechend existiert eine direkte Verbindung zwischen beiden Gleichungen, aus der sich die folgenden Zusammenhänge ergeben,

$\begin{align} P_0 \ & = \ p_0, \\ P_1 \ & = \ p_0 + \frac{m_0}{3}, \\ P_2 \ & = \ p_1 - \frac{m_1}{3}, \\ P_3 \ & = \ p_1, \end{align}$

wenn die Bézierkurve wie folgt definiert ist:

$\begin{align} C(t) \ & = \ (1-t)^3P_0+3t(1-t)^2P_1+3t^2(1-t)P_2+t^3P_3 \\ \end{align}$.

Durch diesen Zusammenhang kann der De-Casteljau-Algorithmus zu Berechnung von Interpolationen mittels kubisch hermitescher Splines benutzt werden. Ebenso ist ersichtlich, dass bei einer kubischen Bézierkurve die mittleren Kontrollpunkte die Richtung der Tangente an den Endpunkten definieren.

Eindeutigkeit

Die Definition des Segments garantiert, dass der Pfad zwischen zwei Punkten eindeutig ist. Damit ist gemeint, dass es kein zweites von c(t) verschiedenes Polynom q(x) gefunden werden kann, das den gleichen Verlauf besitzt.

Interpolation

Das Schema des segmentweise aufgebauten kubisch hermiteschen Splines kann benutzt werden, um für einen Datensatz mit den Kontrollpunkten (x_k,p_k) für $k = 1,\ldots,n$ eine Kurve zu definieren, die durch die Kontrollpunkt verläuft und deren Tangenten derart gewählt werden, dass sich ein weicher Übergang zwischen den Segmenten ergibt. Dies bedeutet, dass die Tangenten aneinandergrenzender Segmente in ihrem gemeinsamen Punkt gleich sind. Die so interpolierte Kurve besteht dann aus stückweise differenzierbaren Segmenten und ist selbst im Bereich (x₁,x_n) stetig differenzierbar.

Die Wahl der Tangenten ist hingegen nicht eindeutig, sodass sich verschiedene Bestimmungsverfahren mit unterschiedlichen Ergebnissen etabliert haben.

Finite Differenz

Die einfachste Methode zur Wahl der Tangenten (Anstieg im eindimensionalen Fall) ist die Verwendung der finiten Differenz. Mit ihr lassen sich die Tangenten für ein Segment im Einheitsintervall und $k = 2,\ldots,n-1$ wie folgt berechnen:

$m_k \ = \ \frac{p_{k}-p_{k-1}}{2} + \frac{p_{k+1}-p_{k}}{2}$

Für Endpunkte (k = 0 und k = n) wird entweder die einseitige Differenz verwendet, was effektiv einer Verdoppelung des Anfangs- und Endpunktes entspricht. Alternativ wird ein Vorgänger p _{− 1} und Nachfolger p_{n + 1} geschätzt, wofür es verschiedene Ansätze gibt.

Catmull-Rom-Spline

Tangente vom Catmull-Rom-Spline bei unterschiedlichem Faktor T₁

Fasst man obige Gleichung zusammen, multipliziert sie mit 2 und definiert einen Faktor T_k erhält man das Catmull-Rom-Spline.

$\begin{align} {m}_k \ & = \ T_k (p_{k+1} - p_{k-1}) \ \text{mit} \ T_k \in [0,\infty) \qquad & \text{(Einheitsintervall)} \\ {m}_k \ & = \ T_k \frac{p_{k+1} - p_{k-1}}{x_{k+1} - x_{k-1}} \ \text{mit} \ T_k \in [0,\infty) \qquad & \text{(Werteintervall)} \end{align}$

Aus dem Teilstück p_{k + 1} − p_{k − 1} der Gleichung ist ersichtlich, dass die Tangente sich an der Richtung des Vektors von p_{k − 1} nach p_{k + 1} orientiert. Der Parameter T_k skaliert unterdessen diesen Vektor, sodass das Kurvensegment weiter oder schärfer wird. Häufig wird dieser Parameter fest auf 0,5 gesetzt, womit sich wieder die Ausgangsgleichung ergibt.

Benannt ist diese Kurve nach Edwin Catmull und Raphael Rom. In der Computergrafik wird diese Form häufig genutzt um zwischen Schlüsselbildern (Keyframes) zu interpolieren oder grafische Objekte darzustellen. Sie sind hauptsächlich wegen ihrer einfachen Berechnung verbreitet und erfüllen die Bedingung, dass jedes Schlüsselbild exakt erreicht wird, während die Bewegung sich weich und ohne Sprünge von Segment zu Segment fortsetzt. Dabei ist zu beachten, dass sich durch die Änderung eines Kontrollpunktes sich über die Bestimmung der benachbarten Tangenten insgesamt vier Kurvensegmente verändern.^[2]

Cardinal Spline

Ein Cardinal Spline ergibt sich, wenn die Tangenten wie folgt bestimmt werden:^[3][4]

$\begin{align} m_k \ & = \ \frac{1-c_k}{2} (p_{k+1}-p_{k-1}) \ \text{mit} \ c_k \in [-1,1] \qquad & \text{(Einheitsintervall)} \\ m_k \ & = \ \frac{1-c_k}{2} \frac{p_{k+1}-p_{k-1}}{x_{k+1}-x_{k-1}} \ \text{mit} \ c_k \in [-1,1] \qquad & \text{(Werteintervall)} \end{align}$

Der Parameter c wird dabei als Spannung der Kurve verstanden und muss im Interval von [ − 1,1] liegen. Anschaulich betrachtet, bestimmt der Parameter die „Länge der Tangenten“, wobei c = 1 bedeutet, dass sie keine Länge besitzen, c = − 1 führt zu doppelt so langen Tangenten, was einen sehr weichen Durchlauf durch den Kontrollpunkt nach sich zieht.

Kochanek-Bartels-Spline

Einfluss von Tension, Continuity und Bias auf die Wahl der Tangenten und den Kurvenverlauf

Das Kochanek-Bartels-Spline (auch TCB-Spline genannt) ist eine weitere Generalisierung für die Wahl der Tangenten, die sich durch die Parameter Tension, Continuity und Bias beeinflussen lässt. Sie wurden 1984 von Doris H. U. Kochanek und Richard H. Bartels eingeführt um Anwendern bei der Keyframe-Animation eine größere Kontrolle über den Verlauf der Interpolation zu geben. Bekannt wurden sie durch Anwendungen wie 3ds Max von Discreet oder LightWave 3D von NewTek.^[2]

Als Grundlage für die Kochanek-Bartels-Splines dient der C⁰-stetige hermitesche Spline, der links- und rechtsseitige Tangenten ($m_k^-$ und $m_k^+$) an einem Kontrollpunkt p_k erlaubt.^[2][5][6]

Tension

Der Tension-Parameter T_k ist mit dem c-Parameter vom Cardinal Spline vergleichbar und beeinflusst gleichermaßen die Länge der Tangenten am Kontrollpunkt. In Analogie zur Tangentenrichtung des Catmull-Rom-Spline ergibt sich:

$m_k^- \ = \ m_k^+ \ = \ \frac{1-T_k}{2} (p_k - p_{k-1}) + \frac{1-T_k}{2} (p_{k+1} - p_k) \ \text{mit} \ T_k \in [-1,1]$

Für negative Werte durchläuft die Kurve in weitem Bogen den Kontrollpunkt, während sie sich für positive stark zusammenzieht. Im Falle von T_k = 1 besitzen die Tangenten eine Länge von 0, wodurch ein scharfer aber dennoch C¹-stetiger Knick entsteht. Bei T_k = 1 ist die Tangente doppelt so lang wie bei T_k = 0 was einen weit verlaufenden Bogen durch den Kontrollpunkt ergibt.

Continuity

Der Continuity-Parameter C_k lässt die Tangenten in ihrer Richtung auseinandergehen. Entsprechend wirkt der Parameter unterschiedlich auf die links- und rechtsseitige Tangente:

$\begin{align} m_k^- \ & = \ \frac{1-C_k}{2} (p_k - p_{k-1}) + \frac{1+C_k}{2} (p_{k+1} - p_k) \ , \\ m_k^+ \ & = \ \frac{1+C_k}{2} (p_k - p_{k-1}) + \frac{1-C_k}{2} (p_{k+1} - p_k) \ \text{mit} \ C_k \in [-1,1] \end{align}$

Für Werte von $C_k \neq 0$ ist der Spline nicht mehr C¹-stetig. Die Kurve zeigt Ecken die mit zunehmenden | c_k | schärfer werden. Das Vorzeichen definiert unterdessen ob die Ecke nach „außen“ oder „innen“ zeigt.

Bias

Der Bias-Parameter B_k bestimmt welches Segment einen stärkeren Einfluss auf die Tangente besitzt. Entsprechend rotiert die gemeinsame Tangente in Richtung des Gewichts.

$m_k^- \ = \ m_k^+ \ = \ \frac{1+B_k}{2} (p_k - p_{k-1}) + \frac{1-B_k}{2} (p_{k+1} - p_k) \ \text{mit} \ B_k \in [-1,1]$

Zusammenfassung zu TCB

Fasst man die gewonnenen Eigenschaften für die Tangenten zusammen, erhält man folgende Gleichungen für die eingehende und ausgehende Tangente von p_k:

Einheitsintervall

$\begin{align} m_k^- \ & = \ \frac{(1-T_k)(1-C_k)(1+B_k)}{2} (p_k - p_{k-1}) + \frac{(1-T_k)(1+C_k)(1-B_k)}{2} (p_{k+1} - p_k) \ , \\ m_k^+ \ & = \ \frac{(1-T_k)(1+C_k)(1+B_k)}{2} (p_k - p_{k-1}) + \frac{(1-T_k)(1-C_k)(1-B_k)}{2} (p_{k+1} - p_k)\ \text{mit} \ T_k, C_k, B_k \in [-1,1] \end{align}$

Werteintervall

$\begin{align} m_k^- \ & = \ \frac{(1-T_k)(1-C_k)(1+B_k)}{2} \frac{p_k - p_{k-1}}{x_k - x_{k-1}} + \frac{(1-T_k)(1+C_k)(1-B_k)}{2} \frac{p_{k+1} - p_k}{x_{k+1} - x_k} \ , \\ m_k^+ \ & = \ \frac{(1-T_k)(1+C_k)(1+B_k)}{2} \frac{p_k - p_{k-1}}{x_k - x_{k-1}} + \frac{(1-T_k)(1-C_k)(1-B_k)}{2} \frac{p_{k+1} - p_k}{x_{k+1} - x_k} \ \text{mit} \ T_k, C_k, B_k \in [-1,1] \end{align}$

Literatur

• I. J. Schoenberg: Cardinal Spline Interpolation. SIAM (Society for Industrial and Applied Mathematics), 1987, ISBN 0-89871-009-X.
• Michael Bender, Manfred Brill: Computergrafik: Ein anwendungsorientiertes Lehrbuch. Hanser Verlag, 2005, ISBN 3-446-40434-1.
• David Salomon: Curves and surfaces for computer graphics. Springer, 2006, ISBN 0-387-24196-5.

Einzelnachweise

1. ↑ G. Scott Owen: Hermite Splines. Sisgraph, 2. September 1999, abgerufen am 1. November 2010 (englisch). 
2. ↑ ^{a b c} Michael Bender, Manfred Brill: Computergrafik: Ein anwendungsorientiertes Lehrbuch. Hanser Verlag, 2005, ISBN 3-446-40434-1, S. 139ff..
3. ↑ I. J. Schoenberg: Cardinal Spline Interpolation. SIAM (Society for Industrial and Applied Mathematics), 1987, ISBN 0-89871-009-X, S. 33ff..
4. ↑ David Salomon: Curves and surfaces for computer graphics. Springer, 2006, ISBN 0-387-24196-5, S. 161ff..
5. ↑ David Salomon: Curves and surfaces for computer graphics. Springer, 2006, ISBN 0-387-24196-5, S. 167ff..
6. ↑ David Eberly: Kochanek-Bartels Cubic Splines (TCB Splines). Geometric Tools, LLC, 14. Februar 2008, abgerufen am 1. November 2010 (englisch). 

Weblinks

• Donald H. House: Spline Curves. Clemson University (Englisch).
• Chandrajit Bajaja: Multi-dimensional Hermite Interpolation and Approximation. Purdue University (Englisch).