Cubic Hermitian spline

In the mathematical sub-field of numerics , a cubic Hermitian spline (also called cSpline ) is understood to be a spline that interpolates between control points. The control points are connected by segments, which consist of cubic polynomials, which are continuously differentiable . This means that one part of the curve ends exactly where the next one begins, and, moreover, that the two tangents coincide in their direction at the segment boundary, which results in a smooth transition (without kink) from segment to segment. The individual sub-curves are clearly defined by the start and end point as well as the incoming and outgoing tangent vector. ${\displaystyle n}$ ${\displaystyle n-1}$

This spline definition is particularly widespread in computer animation programs in order to interpolate between individual keyframes , which can also have different time intervals from one another. In addition to the cubic splines, there are also splines with a higher or lower order. However, lower orders are classified as too inflexible and higher orders as too costly to implement. In particular, higher-order splines tend to "overshoot", which could disturb the animator in his work through undesired processes. In addition, there is the effective possibility of being able to calculate and influence the tangents, as is the case, for example, with the Kochanek-Bartels spline discussed later. The definition of a segment of this spline is also closely related to the cubic Bézier curve , so that both can be converted into one another. This makes it possible to use the algorithms for Bézier curves (e.g. the De Casteljau algorithm ) also to calculate and display cubic Hermitian splines.

Cubic Hermitian spline consisting of two segments between the control points , and . It can be seen that two segments each share a common control point and that their tangent vectors have the same direction. ${\displaystyle p_{0}}$ ${\displaystyle p_{1}}$ ${\displaystyle p_{2}}$

Definition of a segment

In the unit interval

In the unit interval , a segment of the cubic Hermitian spline is defined by the following cubic Hermitian curve : ${\displaystyle [0,1]}$

${\displaystyle {\begin{aligned}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{aligned}}}$

It is the starting point at and the endpoint . The points can be multi-dimensional and are linearly independent of one another. and are the associated tangents at the start and end point. It should be noted that the tangent of the end point points in the direction of escape. It is not to be equated with the second middle control point of the Bézier curve , since the definition is fundamentally different. ${\displaystyle p_{0}}$ ${\displaystyle t=0}$ ${\displaystyle p_{1}}$ ${\displaystyle t=1}$ ${\displaystyle m_{0}}$ ${\displaystyle m_{1}}$

The function can be represented more clearly in matrix notation :

${\displaystyle 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]}$

${\displaystyle M_{h}}$is referred to as the Hermitian matrix .

In the value interval

In the general interval , the function is stretched accordingly, which results from the equation and the tangents must be scaled in the same ratio. As a result, the distance of the interval is added as an additional parameter that results from if the tangents are not already normalized for the value interval. In the case of a normalization . ${\displaystyle [x_{k},x_{k+1}]}$ ${\displaystyle t}$ ${\displaystyle t=(x-x_{k})/(x_{k+1}-x_{k})}$ ${\displaystyle d}$ ${\displaystyle d=x_{k+1}-x_{k}}$ ${\displaystyle d=1}$

${\displaystyle {\begin{aligned}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{aligned}}}$

Derivation

Let the points and and their associated tangents and be given. Likewise, the function sought should be a third degree polynomial, which can generally be represented as . ${\displaystyle p_{0}}$ ${\displaystyle p_{1}}$ ${\displaystyle m_{0}}$ ${\displaystyle m_{1}}$ ${\displaystyle x(t)=at^{3}+bt^{2}+ct+d}$

At the same time, it is assumed that two adjacent segments share the start and end point and that there is a smooth transition, i.e. they have the same start and end point and have the same derivative at these points. This creates four conditions that can be described as follows:

${\displaystyle {\begin{aligned}x(0)\ &=\ p_{0}\\x(1)\ &=\ p_{1}\\x'(0)\ &=\ m_{0}\\x'(1)\ &=\ m_{1}\\\end{aligned}}}$

The polynomial mentioned at the beginning can be clearly described in matrix form:

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

It follows for and : ${\displaystyle t=0}$ ${\displaystyle t=1}$

${\displaystyle {\begin{aligned}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{aligned}}}$

For the tangents, the function must be derived once , so that the following equations result: ${\displaystyle t}$

${\displaystyle {\begin{aligned}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{aligned}}}$

The four relationships gained can be summarized as follows:

${\displaystyle {\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}$

The equation can now by multiplication with the inverse to be resolved. ${\displaystyle A^{-1}}$ ${\displaystyle C}$

${\displaystyle 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}}}$

Inserted into the general cubic equation results in the definition of the segment of the cubic Hermitian spline mentioned at the beginning. ${\displaystyle x(t)}$

Representations and Relationships

Plot of the Hermitian basis functions.

The Hermitian basic functions can be represented in different ways, whereby different properties of the curve segments can be read off directly. ${\displaystyle h_{00},h_{01},h_{10},h_{11}}$

presentation	${\displaystyle {\boldsymbol {h_{00}(t)}}}$	${\displaystyle {\boldsymbol {h_{01}(t)}}}$	${\displaystyle {\boldsymbol {h_{10}(t)}}}$	${\displaystyle {\boldsymbol {h_{11}(t)}}}$
expands	${\displaystyle 2t^{3}-3t^{2}+1}$	${\displaystyle t^{3}-2t^{2}+t}$	${\displaystyle -2t^{3}+3t^{2}}$	${\displaystyle t^{3}-t^{2}}$
factored	${\displaystyle (1+2t)(1-t)^{2}}$	${\displaystyle t(1-t)^{2}}$	${\displaystyle t^{2}(3-2t)}$	${\displaystyle t^{2}(t-1)}$
Amber	${\displaystyle B_{0}(t)+B_{1}(t)}$	${\displaystyle {\frac {1}{3}}B_{1}(t)}$	${\displaystyle B_{2}(t)+B_{3}(t)}$	${\displaystyle -{\frac {1}{3}}B_{2}(t)}$

The expanded form can be obtained directly from the derivation and is usually used for definition, as is the case here.

It can be seen directly from the factorization that at has a zero and the increase is the same . The same applies to for . and , on the other hand, have a multiplicity of 2 and each have a zero at the end and the beginning of the definition range . ${\displaystyle h_{00}}$ ${\displaystyle t=1}$ ${\displaystyle 0}$ ${\displaystyle h_{10}}$ ${\displaystyle t=0}$ ${\displaystyle h_{01}}$ ${\displaystyle h_{11}}$ ${\displaystyle t}$

When considering the Bernstein polynomial of 3rd order which is analogous to the cubic Bezier curve can be seen, the Bernstein polynomial , , and are. Accordingly, there is a direct connection between the two equations, from which the following relationships result, ${\displaystyle B_{k}(t)={3 \choose k}t^{k}(1-t)^{3-k}}$ ${\displaystyle B_{0}(t)}$ ${\displaystyle B_{1}(t)}$ ${\displaystyle B_{2}(t)}$ ${\displaystyle B_{3}(t)}$

${\displaystyle {\begin{aligned}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{aligned}}}$

if the Bézier curve is defined as follows:

${\displaystyle {\begin{aligned}C(t)\ &=\ (1-t)^{3}P_{0}+3t(1-t)^{2}P_{1}+3t^{2}(1-t)P_{2}+t^{3}P_{3}\ \end{aligned}}}$.

Because of this connection, the De Casteljau algorithm can be used to calculate interpolations using cubic Hermitian splines. It can also be seen that in a cubic Bézier curve, the central control points define the direction of the tangent at the end points.

Uniqueness

The definition of the segment guarantees that the path between two points is unique. This means that no second polynomial different from that can be found that has the same course. ${\displaystyle c(t)}$ ${\displaystyle q(x)}$

Illustrative behavior

While the direction of each tangent vector indicates in which direction the curve leaves or reaches the associated point , the amount (the "length") of each tangent vector describes how strong its influence on the curve is: From the direction of a short vector, the curve can move quickly it can only slowly detach from the direction of a long vector. ${\displaystyle {\vec {m}}_{i}}$ ${\displaystyle p_{i}}$

If it is irrelevant in which direction the spline leaves a point, the associated tangent vector can be set to. ${\displaystyle {\vec {0}}}$

interpolation

The scheme of the segment-wise cubic Hermitian spline can be used to define for a data set with the control points for a curve which runs through the control point and whose tangents are selected in such a way that a smooth transition between the segments results. This means that the tangents of adjacent segments are the same in their common point. The curve interpolated in this way then consists of piece-wise differentiable segments and is even continuously differentiable in the area . ${\displaystyle (x_{k},p_{k})}$ ${\displaystyle k=1,\ldots ,n}$ ${\displaystyle (x_{1},x_{n})}$

The choice of tangents, on the other hand, is not clear, so that different determination methods with different results have become established.

Finite difference

The simplest method for choosing the tangents ( increase in the one-dimensional case) is to use the finite difference . It can be used to calculate the tangents for a segment in the unit interval and as follows: ${\displaystyle k=2,\ldots ,n-1}$

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

For end points ( and ) either the one-sided difference is used, which effectively corresponds to a doubling of the start and end points. Alternatively, a predecessor and successor are estimated, for which there are different approaches. ${\displaystyle k=0}$ ${\displaystyle k=n}$ ${\displaystyle p_{-1}}$ ${\displaystyle p_{n+1}}$

Catmull Rom Spline

Tangent from the Catmull-Rom spline for different factors ${\displaystyle T_{1}}$

If you summarize the above equation, multiply it by and define a factor , you get the Catmull-Rom spline. ${\displaystyle 2}$ ${\displaystyle T_{k}}$

${\displaystyle {\begin{aligned}{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{aligned}}}$

From the part of the equation it can be seen that the tangent is based on the direction of the vector from to . In the meantime, the parameter scales this vector so that the curve segment becomes wider or sharper. This parameter is often set to a fixed value , which again results in the initial equation. ${\displaystyle p_{k+1}-p_{k-1}}$ ${\displaystyle p_{k-1}}$ ${\displaystyle p_{k+1}}$ ${\displaystyle T_{k}}$ ${\displaystyle 0{,}5}$

This curve is named after Edwin Catmull and Raphael Rom . In computer graphics , this form is often used to distinguish between keyframes display (keyframes) to interpolate or graphic objects. They are widely used mainly because of their simple calculation and meet the condition that each key frame is reached exactly while the movement continues smoothly and without jumps from segment to segment. It should be noted that changing a control point changes a total of four curve segments by determining the neighboring tangents.

Cardinal spline

A cardinal spline is obtained when the tangents are determined as follows:

${\displaystyle {\begin{aligned}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{aligned}}}$

The parameter is understood as the voltage of the curve and must be in the interval of . Considered clearly, the parameter determines the "length of the tangents", which means that they have no length, leads to tangents that are twice as long, which results in a very smooth passage through the control point. ${\displaystyle c}$ ${\displaystyle [-1,1]}$ ${\displaystyle c=1}$ ${\displaystyle c=-1}$

Kochanek-Bartels spline

Influence of tension , continuity and bias on the choice of tangents and the course of the curve

The Kochanek-Bartels spline (also called TCB spline) is a further generalization for the choice of tangents, which can be influenced by the parameters tension , continuity and bias . They were introduced in 1984 by Doris HU Kochanek and Richard H. Bartels to give users greater control over the course of the interpolation in keyframe animation. They became known through applications such as 3ds Max from Discreet or LightWave 3D from NewTek.

The basis for the Kochanek-Bartels splines is the -continuous Hermitian spline, which allows left and right-hand tangents ( and ) at a control point . ${\displaystyle C^{0}}$ ${\displaystyle m_{k}^{-}}$ ${\displaystyle m_{k}^{+}}$ ${\displaystyle p_{k}}$

Tension

The tension parameter is comparable to the parameter of the cardinal spline and also influences the length of the tangents at the control point. In analogy to the tangent direction of the Catmull-Rom spline: ${\displaystyle T_{k}}$ ${\displaystyle c}$

${\displaystyle 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]}$

For negative values, the curve goes through the control point in a wide arc, while for positive values ​​it contracts strongly. In the case of , the tangents have a length of , which creates a sharp but still continuous kink. At the tangent is twice as long as at which results in a wide arc through the control point. ${\displaystyle T_{k}=1}$ ${\displaystyle 0}$ ${\displaystyle C^{1}}$ ${\displaystyle T_{k}=-1}$ ${\displaystyle T_{k}=0}$

Continuity

The continuity parameter lets the tangents diverge in their direction. Accordingly, the parameter acts differently on the left and right-hand tangent: ${\displaystyle C_{k}}$

${\displaystyle {\begin{aligned}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{aligned}}}$

The spline is no longer -continuous for values ​​of . The curve shows corners that become sharper with increasing . The sign defines meanwhile whether the corner to the "outside" or "inside" shows. ${\displaystyle C_{k}\neq 0}$ ${\displaystyle C^{1}}$ ${\displaystyle |c_{k}|}$

Bias

The bias parameter determines which segment has a stronger influence on the tangent. The common tangent rotates accordingly in the direction of the weight. ${\displaystyle B_{k}}$

${\displaystyle 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]}$

Summary of TCB

If one summarizes the obtained properties for the tangents, one obtains the following equations for the incoming and outgoing tangent of : ${\displaystyle p_{k}}$

Unit interval

${\displaystyle {\begin{aligned}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{aligned}}}$

Value interval

${\displaystyle {\begin{aligned}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{aligned}}}$

literature

• IJ Schoenberg: Cardinal Spline Interpolation . No. 12 . SIAM (Society for Industrial and Applied Mathematics), 1987, ISBN 0-89871-009-X .
• Michael Bender, Manfred Brill: Computer graphics: An application-oriented textbook . No. 2 . Hanser Verlag, 2005, ISBN 3-446-40434-1 .
• David Salomon: Curves and surfaces for computer graphics . Springer, 2006, ISBN 0-387-24196-5 .

Web links

• Donald H. House: Spline Curves (PDF; 5.4 MB). Clemson University (English).
• Chandrajit Bajaj: Multi-dimensional Hermite Interpolation and Approximation (PDF; 207 kB). Purdue University (English).

Individual evidence

1. ^ G. Scott Owen: Hermite Splines. Sisgraph, September 2, 1999, accessed November 1, 2010 .  
2. ↑ ^{a b c} Michael Bender, Manfred Brill: Computer graphics: An application-oriented textbook . No. 2 . Hanser Verlag, 2005, ISBN 3-446-40434-1 , p. 139 ff .
3. ^ IJ Schoenberg: Cardinal Spline Interpolation . No. 12 . SIAM (Society for Industrial and Applied Mathematics), 1987, ISBN 0-89871-009-X , p. 33 ff .
4. ↑ David Salomon: Curves and surfaces for computer graphics . Springer, 2006, ISBN 0-387-24196-5 , pp. 161 ff .
5. ↑ David Salomon: Curves and surfaces for computer graphics . Springer, 2006, ISBN 0-387-24196-5 , pp. 167 ff .
6. ^ David Eberly: Kochanek-Bartels Cubic Splines (TCB Splines). (No longer available online.) Geometric Tools, LLC, February 14, 2008, archived from the original on April 13, 2014 ; accessed on November 1, 2010 (English). Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice.