cubic Hermite spline

File:HermiteBasis.svg

On the unit interval $[0,1]$, given a starting point $\backslash boldsymbol\{p\}\_0$ at $t\; =\; 0$ and an ending point $\backslash boldsymbol\{p\}\_1$ at $t\; =\; 1$ with starting tangent $\backslash boldsymbol\{m\}\_0$ at $t\; =\; 0$ and ending tangent $\backslash boldsymbol\{m\}\_1$ at $t\; =\; 1$, the polynomial can be defined by

$$\backslash boldsymbol\{p\}(t)\; =\; \backslash left(2t^3\; -\; 3t^2\; +\; 1\backslash right)\; \backslash boldsymbol\{p\}\_0\; +\; \backslash left(t^3\; -\; 2t^2\; +\; t\backslash right)\; \backslash boldsymbol\{m\}\_0\; +\; \backslash left(-2t^3\; +\; 3t^2\backslash right)\; \backslash boldsymbol\{p\}\_1\; +\; \backslash left(t^3\; -\; t^2\backslash right)\; \backslash boldsymbol\{m\}\_1,$$

where t ∈ [0, 1].

Interpolating $x$ in an arbitrary interval $(x\_k,\; x\_\{k+1\})$ is done by mapping the latter to $[0,\; 1]$ through an affine (degree-1) change of variable. The formula is

$$\backslash boldsymbol\{p\}(x)\; =\; h\_\{00\}(t)\; \backslash boldsymbol\{p\}\_k\; +\; h\_\{10\}(t)\; (x\_\{k+1\}\; -\; x\_k)\backslash boldsymbol\{m\}\_k\; +\; h\_\{01\}(t)\; \backslash boldsymbol\{p\}\_\{k+1\}\; +\; h\_\{11\}(t)(x\_\{k+1\}\; -\; x\_k)\backslash boldsymbol\{m\}\_\{k+1\},$$

where $t\; =\; (x\; -\; x\_k)/(x\_\{k+1\}\; -\; x\_k)$, and $h$ refers to the basis functions, defined below. Note that the tangent values have been scaled by $x\_\{k+1\}\; -\; x\_k$ compared to the equation on the unit interval.

The formula specified above provides the unique third-degree polynomial path between the two points with the given tangents.

Proof. Let $P,\; Q$ be two third-degree polynomials satisfying the given boundary conditions. Define $R\; =\; Q\; -\; P,$ then:

: $R(0)\; =\; Q(0)-P(0)\; =\; 0,$

: $R(1)\; =\; Q(1)\; -\; P(1)\; =\; 0.$

Since both $Q$ and $P$ are third-degree polynomials, $R$ is at most a third-degree polynomial. So $R$ must be of the form

$$R(x)\; =\; ax(x\; -\; 1)(x\; -\; r).$$

Calculating the derivative gives

$$R\text{'}(x)\; =\; ax(x\; -\; 1)\; +\; ax(x\; -\; r)\; +\; a(x\; -\; 1)(x\; -\; r).$$

We know furthermore that

: $R\text{'}(0)\; =\; Q\text{'}(0)\; -\; P\text{'}(0)\; =\; 0,$

{{NumBlk|:|$R\text{'}(0)\; =\; 0\; =\; ar,$|{{EquationRef|1}}}}

: $R\text{'}(1)\; =\; Q\text{'}(1)\; -\; P\text{'}(1)\; =\; 0,$

{{NumBlk|:|$R\text{'}(1)\; =\; 0\; =\; a(1\; -\; r).$|{{EquationRef|2}}}}

Putting ({{EquationNote|1}}) and ({{EquationNote|2}}) together, we deduce that $a\; =\; 0$, and therefore $R\; =\; 0,$ thus $P\; =\; Q.$

We can write the interpolation polynomial on the unit interval (for an arbitrary interval see the rescaled version above) as

$$\backslash boldsymbol\{p\}(t)\; =\; h\_\{00\}(t)\backslash boldsymbol\{p\}\_0\; +\; h\_\{10\}(t)\backslash boldsymbol\{m\}\_0\; +\; h\_\{01\}(t)\backslash boldsymbol\{p\}\_1\; +\; h\_\{11\}(t)\backslash boldsymbol\{m\}\_1$$

where $h\_\{00\}$, $h\_\{10\}$, $h\_\{01\}$, $h\_\{11\}$ are Hermite basis functions.

These can be written in different ways, each way revealing different properties:

The "expanded" column shows the representation used in the definition above.

The "factorized" column shows immediately that $h\_\{10\}$ and $h\_\{11\}$ are zero at the boundaries.

You can further conclude that $h\_\{01\}$ and $h\_\{11\}$ have a zero of multiplicity 2 at 0, and $h\_\{00\}$ and $h\_\{10\}$ have such a zero at 1, thus they have slope 0 at those boundaries.

The "Bernstein" column shows the decomposition of the Hermite basis functions into Bernstein polynomials of order 3:

$$B\_k(t)\; =\; \backslash binom\{3\}\{k\}\; \backslash cdot\; t^k\; \backslash cdot\; (1\; -\; t)^\{3-k\}.$$

Using this connection you can express cubic Hermite interpolation in terms of cubic Bézier curves with respect to the four values $\backslash boldsymbol\{p\}\_0,\; \backslash boldsymbol\{p\}\_0\; +\; \backslash frac\{1\}\{3\}\; \backslash boldsymbol\{m\}\_0,\; \backslash boldsymbol\{p\}\_1\; -\; \backslash frac\{1\}\{3\}\; \backslash boldsymbol\{m\}\_1,\; \backslash boldsymbol\{p\}\_1$ and do Hermite interpolation using the de Casteljau algorithm.

It shows that in a cubic Bézier patch the two control points in the middle determine the tangents of the interpolation curve at the respective outer points.

We can also write the polynomial in standard form as

$$\backslash boldsymbol\{p\}(t)\; =\; \backslash left(2\backslash boldsymbol\{p\}\_0\; +\; \backslash boldsymbol\{m\}\_0\; -\; 2\backslash boldsymbol\{p\}\_1\; +\; \backslash boldsymbol\{m\}\_1\backslash right)\; t^3\; +\; \backslash left(-3\backslash boldsymbol\{p\}\_0\; +\; 3\backslash boldsymbol\{p\}\_1\; -\; 2\backslash boldsymbol\{m\}\_0\; -\; \backslash boldsymbol\{m\}\_1\backslash right)\; t^2\; +\; \backslash boldsymbol\{m\}\_0\; t\; +\; \backslash boldsymbol\{p\}\_0$$

where the control points and tangents are coefficients. This permits efficient evaluation of the polynomial at various values of t since the constant coefficients can be computed once and reused.

A data set, $(x\_k,\backslash boldsymbol\{p\}\_k)$ for $k=1,\backslash ldots,n$, can be interpolated by applying the above procedure on each interval, where the tangents are chosen in a sensible manner, meaning that the tangents for intervals sharing endpoints are equal. The interpolated curve then consists of piecewise cubic Hermite splines and is globally continuously differentiable in $(x\_1,\; x\_n)$.

The choice of tangents is not unique, and there are several options available.

File:Finite difference spline example.png

The simplest choice is the three-point difference, not requiring constant interval lengths:

: $\backslash boldsymbol\{m\}\_k\; =\; \backslash frac\{1\}\{2\}\; \backslash left(\backslash frac\{\backslash boldsymbol\{p\}\_\{k+1\}\; -\; \backslash boldsymbol\{p\}\_k\}\{x\_\{k+1\}\; -\; x\_k\}\; +\; \backslash frac\{\backslash boldsymbol\{p\}\_k\; -\; \backslash boldsymbol\{p\}\_\{k-1\}\}\{x\_k\; -\; x\_\{k-1\}\}\backslash right)$

for internal points $k\; =\; 2,\; \backslash dots,\; n\; -\; 1$, and one-sided difference at the endpoints of the data set.

=== Cardinal spline ===

File:Cardinal Spline Example.png

A cardinal spline, sometimes called a canonical spline,{{cite web |last=Petzold |first=Charles |author-link=Charles Petzold |url=http://www.charlespetzold.com/blog/2009/01/Canonical-Splines-in-WPF-and-Silverlight.html |title=Canonical Splines in WPF and Silverlight |date=2009}} is obtained{{cite web |url=http://msdn2.microsoft.com/en-us/library/ms536358.aspx |title=Cardinal Splines |website=Microsoft Developer Network |access-date=2018-05-27}} if

: $\backslash boldsymbol\{m\}\_k\; =\; (1\; -\; c)\; \backslash frac\{\backslash boldsymbol\{p\}\_\{k+1\}\; -\; \backslash boldsymbol\{p\}\_\{k-1\}\}\{x\_\{k+1\}\; -\; x\_\{k-1\}\}$

is used to calculate the tangents. The parameter {{mvar|c}} is a tension parameter that must be in the interval {{math|[0, 1]}}. In some sense, this can be interpreted as the "length" of the tangent. Choosing {{math|1=c = 1}} yields all zero tangents, and choosing {{math|1=c = 0}} yields a Catmull–Rom spline in the uniform parameterization case.

=== Catmull–Rom spline ===

{{cubic_interpolation_visualisation.svg}}

{{seealso|Centripetal Catmull–Rom spline}}

For tangents chosen to be

: $\backslash boldsymbol\{m\}\_k\; =\; \backslash frac\{\backslash boldsymbol\{p\}\_\{k+1\}\; -\; \backslash boldsymbol\{p\}\_\{k-1\}\}\{2\}$

a Catmull–Rom spline is obtained, being a special case of a cardinal spline. This assumes uniform parameter spacing.

The curve is named after Edwin Catmull and Raphael Rom. The principal advantage of this technique is that the points along the original set of points also make up the control points for the spline curve.{{citation|last1=Catmull|first1=Edwin|author1-link=Edwin Catmull|last2=Rom|first2=Raphael|author2-link=Raphael Rom|chapter=A class of local interpolating splines|editor1-first=R. E.|editor1-last=Barnhill|editor2-first=R. F.|editor2-last=Riesenfeld|title=Computer Aided Geometric Design|publisher=Academic Press|location=New York|year=1974|pages=317–326}} Two additional points are required on either end of the curve. The uniform Catmull–Rom implementation can produce loops and self-intersections. The chordal and centripetal Catmull–Rom implementationsN. Dyn, M. S. Floater, and K. Hormann. Four-point curve subdivision based on iterated chordal and centripetal parameterizations. Computer Aided Geometric Design, 26(3):279–286, 2009. solve this problem, but use a slightly different calculation.P. J. Barry and R. N. Goldman. A recursive evaluation algorithm for a class of Catmull-Rom splines. SIGGRAPH Computer Graphics, 22(4):199–204, 1988. In computer graphics, Catmull–Rom splines are frequently used to get smooth interpolated motion between key frames. For example, most camera path animations generated from discrete key-frames are handled using Catmull–Rom splines. They are popular mainly for being relatively easy to compute, guaranteeing that each key frame position will be hit exactly, and also guaranteeing that the tangents of the generated curve are continuous over multiple segments.

{{main|Kochanek–Bartels spline}}

A Kochanek–Bartels spline is a further generalization on how to choose the tangents given the data points $\backslash boldsymbol\{p\}\_\{k-1\}$, $\backslash boldsymbol\{p\}\_k$ and $\backslash boldsymbol\{p\}\_\{k+1\}$, with three parameters possible: tension, bias and a continuity parameter.

{{main|Monotone cubic interpolation}}

If a cubic Hermite spline of any of the above listed types is used for interpolation of a monotonic data set, the interpolated function will not necessarily be monotonic, but monotonicity can be preserved by adjusting the tangents.

Consider a single coordinate of the points $\backslash boldsymbol\{p\}\_\{n-1\},\; \backslash boldsymbol\{p\}\_n,\; \backslash boldsymbol\{p\}\_\{n+1\}$ and $\backslash boldsymbol\{p\}\_\{n+2\}$ as the values that a function f(x) takes at integer ordinates x = n − 1, n, n + 1 and n + 2,

: $p\_n\; =\; f(n)\; \backslash quad\; \backslash forall\; n\; \backslash in\; \backslash mathbb\{Z\}.$

In addition, assume that the tangents at the endpoints are defined as the centered differences of the adjacent points:

$$m\_n\; =\; \backslash frac\{f(n\; +\; 1)\; -\; f(n\; -\; 1)\}\{2\}\; =\; \backslash frac\{p\_\{n+1\}\; -\; p\_\{n-1\}\}\{2\}\; \backslash quad\; \backslash forall\; n\; \backslash in\; \backslash mathbb\{Z\}.$$

To evaluate the interpolated f(x) for a real x, first separate x into the integer portion n and fractional portion u:

: $x\; =\; n\; +\; u,$

: $n\; =\; \backslash lfloor\; x\; \backslash rfloor\; =\; \backslash operatorname\{floor\}(x),$

: $u\; =\; x\; -\; n\; =\; x\; -\; \backslash lfloor\; x\; \backslash rfloor,$

:

where $\backslash lfloor\; x\; \backslash rfloor$ denotes the floor function, which returns the largest integer no larger than x.

Then the Catmull–Rom spline is[https://arxiv.org/abs/0905.3564 Two hierarchies of spline interpolations. Practical algorithms for multivariate higher order splines].

$$\backslash begin\{align\}$$

f(x) = f(n + u) &= \text{CINT}_u(p_{n-1}, p_n, p_{n+1}, p_{n+2}) \\

&=

\begin{bmatrix}

1 & u & u^2 & u^3

\end{bmatrix}

\begin{bmatrix}

0 & 1 & 0 & 0 \\

-\tfrac12 & 0 & \tfrac12 & 0 \\

1 & -\tfrac52 & 2 & -\tfrac12 \\

-\tfrac12 & \tfrac32 & -\tfrac32 & \tfrac12

\end{bmatrix}

\begin{bmatrix}

p_{n-1} \\

p_n \\

p_{n+1} \\

p_{n+2}

\end{bmatrix} \\

&= \frac 12

\begin{bmatrix}

-u^3 +2u^2 - u \\

3u^3 - 5u^2 + 2 \\

-3u^3 + 4u^2 + u \\

u^3 - u^2

\end{bmatrix}^\mathrm{T}

\begin{bmatrix}

p_{n-1} \\

p_n \\

p_{n+1} \\

p_{n+2}

\end{bmatrix} \\

&= \frac 12

\begin{bmatrix}

u\big((2 - u)u - 1\big) \\

u^2(3u - 5) + 2 \\

u\big((4 - 3u)u + 1\big) \\

u^2(u - 1)

\end{bmatrix}^\mathrm{T}

\begin{bmatrix}

p_{n-1} \\

p_n \\

p_{n+1} \\

p_{n+2}

\end{bmatrix} \\

&= \tfrac12 \Big(\big(u^2(2 - u) - u\big) p_{n-1} + \big(u^2(3u - 5) + 2\big) p_n + \big(u^2(4 - 3u) + u\big) p_{n+1} + u^2(u - 1) p_{n+2}\Big) \\

&= \tfrac12 \big((-u^3 + 2u^2 - u) p_{n-1} + (3u^3 - 5u^2 + 2) p_n + (-3u^3 + 4u^2 + u) p_{n+1} + (u^3 - u^2) p_{n+2}\big) \\

&= \tfrac12 \big((-p_{n-1} + 3p_n - 3p_{n+1} + p_{n+2}) u^3 + (2p_{n-1} - 5p_n + 4p_{n+1} - p_{n+2})u^2 + (-p_{n-1} + p_{n+1}) u + 2p_n\big) \\

&= \tfrac12 \Big(\big((-p_{n-1} + 3p_n - 3p_{n+1} + p_{n+2}) u + (2p_{n-1} - 5p_n + 4p_{n+1} - p_{n+2})\big)u + (-p_{n-1} + p_{n+1})\Big)u + p_n,

\end{align}

where $\backslash mathrm\{T\}$ denotes the matrix transpose. The bottom equality is depicting the application of Horner's method.

This writing is relevant for tricubic interpolation, where one optimization requires computing CINT_u sixteen times with the same u and different p.

• Bicubic interpolation, a generalization to two dimensions
• Tricubic interpolation, a generalization to three dimensions
• Hermite interpolation
• Multivariate interpolation
• Spline interpolation
• Discrete spline interpolation

{{reflist}}

• [http://www.cs.clemson.edu/~dhouse/courses/405/notes/splines.pdf Spline Curves], Prof. Donald H. House Clemson University
• [http://cvcweb.ices.utexas.edu/ccv/papers/1993/conference/multidim.pdf Multi-dimensional Hermite Interpolation and Approximation], Prof. Chandrajit Bajaj, Purdue University
• [http://www.mvps.org/directx/articles/catmull/ Introduction to Catmull–Rom Splines], MVPs.org
• [http://www.ibiblio.org/e-notes/Splines/Cardinal.htm Interpolating Cardinal and Catmull–Rom splines]
• [http://paulbourke.net/miscellaneous/interpolation/ Interpolation methods: linear, cosine, cubic and hermite (with C sources)]
• [http://www.blackpawn.com/texts/splines/ Common Spline Equations ]

{{DEFAULTSORT:Cubic Hermite Spline}}

Category:Splines (mathematics)

Category:Interpolation