View source for Cubic Hermite spline

{{short description|Cubic function used for interpolation}}
{{not to be confused|Hermite polynomial}}

In [[numerical analysis]], a '''cubic Hermite spline''' or '''cubic Hermite interpolator''' is a [[spline (mathematics)|spline]] where each piece is a third-degree [[polynomial]] specified in [[Hermite interpolation|Hermite form]]:<ref name=kreyszig>
{{cite book
 | title = Advanced Engineering Mathematics
 | author = Erwin Kreyszig
 | publisher = Wiley
 | year = 2005
 | isbn =  9780471488859
 | pages = 816
 | edition = 9
 }}</ref> i.e., by its values and first [[derivative (mathematics)|derivatives]] at the end points of the corresponding [[domain (mathematics)|domain]] interval.

Cubic Hermite splines are typically used for [[interpolation]] of numeric data specified at given argument values <math>x_1,x_2,\ldots,x_n</math>, to obtain a smooth [[continuous function]].  The data should consist of the desired function value and derivative at each <math>x_k</math>. (If only the values are provided, the derivatives must be estimated from them.)  The Hermite formula is applied to each interval <math>(x_k, x_{k+1})</math> separately. The resulting spline will be continuous and will have continuous first derivative.

Cubic polynomial splines can be specified in other ways, the [[Bézier form]] being the most common.  However, these two methods provide the same set of splines, and data can be easily converted between the Bézier and Hermite forms; so the names are often used as if they were synonymous.  

Cubic polynomial splines are extensively used in [[computer graphics]] and [[geometric modeling]] to obtain [[curve]]s or motion [[trajectory|trajectories]] that pass through specified points of the [[plane (geometry)|plane]] or three-dimensional [[space (geometry)|space]].  In these applications, each coordinate of the plane or space is separately interpolated by a cubic spline function of a separate parameter&nbsp;''t''. 
Cubic polynomial splines are also used extensively in structural analysis applications, such as [[Euler–Bernoulli beam theory]].

Cubic splines can be extended to functions of two or more parameters, in several ways.  Bicubic splines ([[Bicubic interpolation]]) are often used to interpolate data on a regular rectangular grid, such as [[pixel]] values in a [[digital image]] or [[altitude]] data on a terrain.  [[Bézier patch|Bicubic surface patches]], defined by three bicubic splines, are an essential tool in computer graphics.

Cubic splines are often called '''csplines''', especially in computer graphics. Hermite splines are named after [[Charles Hermite]].

==Interpolation on a single interval==
===Unit interval (0, 1)===
On the unit interval <math>(0,1)</math>, given a starting point <math>\boldsymbol{p}_0</math> at <math>t=0</math> and an ending point <math>\boldsymbol{p}_1</math> at <math>t=1</math> with starting tangent <math>\boldsymbol{m}_0</math> at <math>t=0</math> and ending tangent <math>\boldsymbol{m}_1</math> at <math>t=1</math>, the polynomial can be defined by
:<math>\boldsymbol{p}(t) = (2t^3-3t^2+1)\boldsymbol{p}_0 + (t^3-2t^2+t)\boldsymbol{m}_0 + (-2t^3+3t^2)\boldsymbol{p}_1 +(t^3-t^2)\boldsymbol{m}_1</math>
[[File:HermiteBasis.svg|thumb|300px|right|The four Hermite basis functions. The interpolant in each subinterval is a linear combination of these four functions.]]
where ''t'' ∈ [0, 1].

===Interpolation on an arbitrary interval===
Interpolating <math>x</math> in an arbitrary interval <math>(x_k, x_{k+1})</math> is done by mapping the latter to <math>[0,1]</math> through an [[affine function|affine]] (degree 1) change of variable.  The formula is
:<math>\boldsymbol{p}(x) = h_{00}(t)\boldsymbol{p}_{k} + h_{10}(t)(x_{k+1}-x_k)\boldsymbol{m}_{k} + h_{01}(t)\boldsymbol{p}_{k+1} + h_{11}(t)(x_{k+1}-x_k)\boldsymbol{m}_{k+1}.</math>
with <math>t = (x-x_k)/(x_{k+1}-x_k)</math> and <math>h</math> refers to the basis functions, defined below. Note that the tangent values have been scaled by <math>x_{k+1}-x_k</math> compared to the equation on the unit interval.

===Uniqueness===
The formulae specified above provide the unique third-degree polynomial path between the two points with the given tangents. <br />

'''Proof.''' Let <math>P, Q</math> be two third degree polynomials satisfying the given boundary conditions. Define <math>R = Q-P,</math> then:
:<math>R(0) = Q(0)-P(0) = 0,</math>
:<math>R(1) = Q(1) - P(1) = 0.</math>
Since both <math>Q</math> and <math>P</math> are third degree polynomials, <math>R</math> is at most a third degree polynomial. So <math>R</math> must be of the form:
:<math>R(x) = ax(x-1)(x-r),</math>
calculating the derivative gives:
:<math>R'(x) = ax(x-1) + ax(x-r) + a(x-1)(x-r).</math>

We know furthermore that:

:<math>R'(0) = Q'(0) - P'(0) = 0</math>
{{NumBlk|:|<math>R'(0) = 0 = ar</math>|{{EquationRef|1}}}}

:<math>R'(1) = Q'(1) - P'(1) = 0</math>
{{NumBlk|:|<math>R'(1) = 0 = a(1-r)</math>|{{EquationRef|2}}}}

Putting ({{EquationNote|1}}) and ({{EquationNote|2}}) together, we deduce that <math>a = 0</math> and therefore <math>R = 0,</math> thus <math>P = Q.</math>

===Representations===

We can write the interpolation polynomial as
:<math>\boldsymbol{p}(t) = h_{00}(t)\boldsymbol{p}_0 + h_{10}(t)\boldsymbol{m}_0 + h_{01}(t)\boldsymbol{p}_1 + h_{11}(t)\boldsymbol{m}_1</math>
where <math>h_{00}</math>, <math>h_{10}</math>, <math>h_{01}</math>, <math>h_{11}</math> are Hermite basis functions.
These can be written in different ways, each way revealing different properties.

{| class="wikitable" border="1"
 |-
 !
 !  expanded
 !  factorized
 !  Bernstein
 |-
 |  <math>h_{00}(t)</math>
 |  <math>2t^3-3t^2+1</math>
 |  <math>(1 + 2 t) ( 1 - t)^2</math>
 |  <math>B_0(t) + B_1(t)</math>
 |-
 |  <math>h_{10}(t)</math>
 |  <math>t^3-2t^2+t</math>
 |  <math>t (1 - t)^2</math>
 |  <math>\frac{1}{3}\cdot B_1(t)</math>
 |-
 |  <math>h_{01}(t)</math>
 |  <math>-2t^3+3t^2</math>
 |  <math>t^2 (3 - 2 t)</math>
 |  <math>B_3(t) + B_2(t)</math>
 |-
 |  <math>h_{11}(t)</math>
 |  <math>t^3-t^2</math>
 |  <math>t^2 (t - 1)</math>
 |  <math>-\frac{1}{3}\cdot B_2(t)</math>
 |}

The "expanded" column shows the representation used in the definition above.
The "factorized" column shows immediately, that <math>h_{10}</math> and <math>h_{11}</math> are zero at the boundaries.
You can further conclude
that <math>h_{01}</math> and <math>h_{11}</math> have a [[Multiplicity_(mathematics)#Multiplicity_of_a_zero_of_a_function|zero of multiplicity 2]] at 0
and <math>h_{00}</math> and <math>h_{10}</math> 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 polynomial]]s of order 3:

:<math>B_k(t)={3 \choose k} \cdot t^k \cdot (1-t)^{3-k}</math>

Using this connection you can express cubic Hermite interpolation in terms of cubic [[Bézier curve]]s
with respect to the four values <math>\boldsymbol{p}_0, \boldsymbol{p}_0 + \frac{\boldsymbol{m}_0}{3}, \boldsymbol{p}_1 - \frac{\boldsymbol{m}_1}{3}, \boldsymbol{p}_1</math>
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.

==Interpolating a data set==
A data set, <math>(t_k,\boldsymbol{p}_k)</math> for <math>k=1,\ldots,n</math>, 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 <math>(t_1,t_n)</math>.

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

===Finite difference===
[[File:Finite difference spline example.png|thumb|Example with finite difference tangents]]
The simplest choice is the three-point difference, not requiring constant interval lengths,<!-- See talk page -->
:<math>\boldsymbol{m}_k = \frac{1}{2}\left(\frac{\boldsymbol{p}_{k+1}-\boldsymbol{p}_{k}}{t_{k+1}-t_{k}} + \frac{\boldsymbol{p}_{k}-\boldsymbol{p}_{k-1}}{t_{k}-t_{k-1}}\right)</math>
for internal points <math>k=2,\ldots,n-1</math>, and one-sided difference at the endpoints of the data set.

=== Cardinal spline === <!-- Redirect "Cardinal spline" points directly to this section -->

[[File:Cardinal Spline Example.png|thumb|right|Cardinal spline example in 2D. The line represents the curve, and the squares represent the control points <math>\boldsymbol{p}_k</math>. Notice that the curve does not reach the first and last points; these points do however affect the shape of the curve. The tension parameter used is 0.1]]
A '''cardinal spline''', sometimes called a '''canonical spline''',<ref>{{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}}</ref> is obtained<ref>{{cite web |url=http://msdn2.microsoft.com/en-us/library/ms536358.aspx |title=Cardinal Splines |website=Microsoft Developer Network |access-date=2018-05-27}}</ref> if
:<math> \boldsymbol{m}_k = (1-c)\frac{\boldsymbol{p}_{k+1}-\boldsymbol{p}_{k-1}}{t_{k+1}-t_{k-1}}</math>
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.

=== Catmull–Rom spline === <!-- Redirect "Catmull-Rom spline" points directly to this section -->

{{seealso|Centripetal Catmull–Rom spline}}

For tangents chosen to be
:<math>\boldsymbol{m}_k = \frac{\boldsymbol{p}_{k+1} - \boldsymbol{p}_{k-1}}{t_{k+1} - t_{k-1}}</math>
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.<ref>{{citation |last1=Catmull |first1=Edwin |author1link=Edwin Catmull  |last2=Rom |first2=Raphael |author2link=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}}</ref>  Two additional points are required on either end of the curve.  The default implementation of the Catmull–Rom algorithm can produce loops and self intersections.  The chordal and [[centripetal Catmull–Rom spline|centripetal Catmull–Rom]] implementations <ref>N. 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</ref> solve this problem, but use a slightly different calculation.<ref> 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.</ref> In [[computer graphics]], Catmull–Rom splines are frequently used to get smooth interpolated motion between [[key frame]]s. 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.

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

===Monotone cubic interpolation===
{{main|Monotone cubic interpolation}}
If a cubic Hermite spline of any of the above listed types is used for [[interpolation]] of a [[Monotonic function|monotonic]] data set, the interpolated function will not necessarily be monotonic, but monotonicity can be preserved by adjusting the tangents.

==Interpolation on the unit interval with matched derivatives at endpoints==
Considering a single coordinate of the points <math>\boldsymbol{p}_{n-1}, \boldsymbol{p}_{n}, \boldsymbol{p}_{n+1}</math> and <math>\boldsymbol{p}_{n+2}</math> as the values that a function, ''f''(''x''), takes at integer ordinates ''x''=''n''−1, ''n'', ''n''+1 and ''n''+2,

:<math> p_n = f(n) \quad \forall n \in \mathbb{Z} </math>

If, in addition, the tangents at the endpoints are defined as the centered differences of the adjacent points,

:<math> m_n = \frac{f(n+1)-f(n-1)}{2} = \frac{p_{n+1}-p_{n-1}}{2} \quad \forall n \in \mathbb{Z} </math>

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

:<math> x = n + u </math>
:<math> n = \lfloor x \rfloor  =  \operatorname{floor}(x) </math>
:<math> u = x - n = x - \lfloor x \rfloor </math>
:<math> 0 \le u < 1 </math>

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

:<math>\begin{align}
f(x) = f(n+u) &= \mathrm{CINT}_u \left (p_{n-1}, p_n, p_{n+1}, p_{n+2} \right ) \\[8pt]
& = \begin{bmatrix} 1 & u & u^2 & u^3 \\ \end{bmatrix}
\cdot
\begin{bmatrix}
0 & 1 & 0 & 0 \\
-\tfrac12 & 0 & \tfrac12 & 0 \\
1 & -\tfrac52 & 2 & -\tfrac12 \\
-\tfrac12 & \tfrac32 & -\tfrac32 & \tfrac12 \\
\end{bmatrix}
\cdot
\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} \cdot \begin{bmatrix} p_{n-1}\\p_n\\p_{n+1}\\p_{n+2} \end{bmatrix} \\
\\
& = \frac 12 \begin{bmatrix} u((2-u)u - 1) \\ u^2(3u-5) + 2 \\ u((4-3u)u + 1) \\ u^2(u-1) \end{bmatrix}^\mathrm{T} \cdot \begin{bmatrix}  p_{n-1}\\p_n\\p_{n+1}\\p_{n+2} \end{bmatrix} \\
\\ 
& = \tfrac12 \bigg( \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} \bigg) \\
\\ 
& = \tfrac12 \bigg( (-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} \bigg) \\
\\ 
& = \tfrac12 \bigg( (-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 \bigg) \\
\\ 
& = \tfrac12 \bigg( \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}) \bigg)u \ + \ p_n  \\
\end{align}</math>

<math>\lfloor x \rfloor</math> denotes the [[floor function]] which returns the largest integer no larger than ''x'' and <math>\mathrm{T}</math> 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 you to compute CINT<sub>''u''</sub> sixteen times with the same ''u'' and different ''p''.

==See also==
* [[Bicubic interpolation]], a generalization to two dimensions
* [[Tricubic interpolation]], a generalization to three dimensions
* [[Hermite interpolation]]
* [[Multivariate interpolation]]
* [[Spline interpolation]]
* [[Discrete spline interpolation]]

==References==
{{reflist}}

==External links==
* [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]]