Cubic Hermite spline

Cubic Hermite spline

In the mathematical subfield of numerical analysis a cubic Hermite spline (also called cspline), named in honor of Charles Hermite, is a third-degree spline with each polynomial of the spline in Hermite form. The Hermite form consists of two control points and two control tangents for each polynomial.

For interpolation on a grid with points xk for k = 1,...,n, interpolation is performed on one subinterval (xk,xk + 1) at a time (given that tangent values are predetermined). The subinterval (xk,xk + 1) is normalized to (0,1) via t = (xxk) / (xk + 1xk).

Contents

Interpolation on a single interval

Unit interval (0, 1)

On the unit interval (0,1), given a starting point p0 at t = 0 and an ending point p1 at t = 1 with starting tangent m0 at t = 0 and ending tangent m1 at t = 1, the polynomial can be defined by

\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
The four Hermite basis functions. The interpolant in each subinterval is a linear combination of these four functions.

where t ∈ [0, 1].

Interpolation on (xk, xk+1)

Interpolating x in the interval (xk,xk + 1) can now be done with the formula

\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}.

with t = (xxk) / (xk + 1xk) and h refers to the basis functions, defined below. Note that the tangent values have been scaled by xk + 1xk compared to the equation on the unit interval.

Uniqueness

The formulae specified above are guaranteed to produce a unique path between the two points.
Proof:
Let Q(x) be another third degree polynomial satisfying the given boundary conditions. Define R(x) = Q(x) − P(x). Since both Q and P are third degree polynomials, R is at most a third degree polynomial. Furthermore:

R(0) = Q(0) − P(0) = 0 (We assume both P and Q satisfy the boundary conditions)
R(1) = 0

So R must be of the form:

R(x) = ax(x − 1)(xr)
R'(x) = ax(x − 1) + ax(xr) + a(x − 1)(xr)

We know furthermore that:

R'(0) = Q'(0) − P'(0) = 0
R'(0) = 0 = ar.......................(1)
R'(1) = Q'(1) − P'(1) = 0
R'(1) = 0 = a(1 − r)...............(2)

Putting (1) and (2) together, we deduce that a = 0 and R = 0, thus P(x) = Q(x)

Representations

We can write the interpolation polynomial as

\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

where h00,h10,h01,h11 are Hermite basis functions. These can be written in different ways, each way revealing different properties.

expanded factorized Bernstein
h00(t) 2t3 − 3t2 + 1 (1 + 2t)(1 − t)2 B0(t) + B1(t)
h10(t) t3 − 2t2 + t t(1 − t)2 \frac{1}{3}\cdot B_1(t)
h01(t) − 2t3 + 3t2 t2(3 − 2t) B3(t) + B2(t)
h11(t) t3t2 t2(t − 1) -\frac{1}{3}\cdot B_2(t)

The "expanded" column shows the representation used in the definition above. The "factorized" column shows immediately, that h10 and h11 are zero at the boundaries. You can further conclude that h01 and h11 have a zero of multiplicity 2 at 0 and h00 and h10 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)={3 \choose k} \cdot t^k \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 \boldsymbol{p}_0, \boldsymbol{p}_0 + \frac{\boldsymbol{m}_0}{3}, \boldsymbol{p}_1 - \frac{\boldsymbol{m}_1}{3}, \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.

Interpolating a data set

A data set, (t_k,\boldsymbol{p}_k) for k = 1,...,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 (t1,tn).

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

Finite difference

Example with finite difference tangents

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

\boldsymbol{m}_k = \frac{\boldsymbol{p}_{k+1}-\boldsymbol{p}_{k}}{2(t_{k+1}-t_{k})} + \frac{\boldsymbol{p}_{k}-\boldsymbol{p}_{k-1}}{2(t_{k}-t_{k-1})}

for internal points k = 2,...,n − 1, and one-sided difference at the endpoints of the data set.

Cardinal spline

Cardinal spline example in 2D. The line represents the curve, and the squares represent the control points \boldsymbol{p}_k. 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 is obtained[1] if

 \boldsymbol{m}_k = (1-c)\frac{\boldsymbol{p}_{k+1}-\boldsymbol{p}_{k-1}}{t_{k+1}-t_{k-1}}

is used to calculate the tangents. The parameter c is a tension parameter that must be in the interval (0,1). In some sense, this can be interpreted as the "length" of the tangent. c = 1 will yield all zero tangents, and c = 0 yields a Catmull–Rom spline.

Catmull–Rom spline

For tangents chosen to be

\boldsymbol{m}_k = \frac{\boldsymbol{p}_{k+1} - \boldsymbol{p}_{k-1}}{t_{k+1} - t_{k-1}}

a Catmull–Rom spline is obtained, being a special case of a cardinal spline.

The curve is named after Edwin Catmull and Raphael (Raphie) Rom. 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.

Kochanek–Bartels spline

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

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.

Interpolation on the unit interval without exact derivatives

Given p-1, p0, p1 and p2 as the values that the function should take on at -1, 0, 1 and 2, we can use centered differences instead of exact derivatives.[2] Thus the Catmull–Rom spline is

\mathrm{CINT}_x(p_{-1}, p_0, p_1, p_2) = \frac 12 \begin{pmatrix} x ((2-x) x-1) \\ x^2 (3 x-5)+2 \\ x ((4-3 x) x+1) \\ (x-1) x^2 \end{pmatrix} \cdot \begin{pmatrix} p_{-1}\\p_{0}\\p_1\\p_2 \end{pmatrix}

for x \in [0,1], where the left-hand vector is independent of the p.

This writing is relevant for tricubic interpolation, where one optimization requires you to compute CINTx sixteen times with the same x and different p.

See also

References

  • Catmull, Edwin and Rom, Raphael, A class of local interpolating splines, in R.E. Barnhill and R.F. Riesenfe}d (eds.) Computer Aided Geometric Design, Academic Press, New York, 1974, 317-326.

External links


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Hermite spline — In the mathematical subfield of numerical analysis, a Hermite spline is a spline curve where each polynomial of the spline is in Hermite form.ee also*Cubic Hermite spline *Hermite polynomials *Hermite interpolation …   Wikipedia

  • Hermite interpolation — is a method closely related to the Newton divided difference method of interpolation in numerical analysis, that allows us to consider given derivatives at data points, as well as the data points themselves. The interpolation will give a… …   Wikipedia

  • Spline interpolation — See also: Spline (mathematics) In the mathematical field of numerical analysis, spline interpolation is a form of interpolation where the interpolant is a special type of piecewise polynomial called a spline. Spline interpolation is preferred… …   Wikipedia

  • Monotone cubic interpolation — In the mathematical subfield of numerical analysis, monotone cubic interpolation is a variant of cubic interpolation that preserves monotonicity of the data set being interpolated. Monotonicity is preserved by linear interpolation but not… …   Wikipedia

  • Kochanek–Bartels spline — In mathematics, a Kochanek Bartels spline or Kochanek Bartels curve is a cubic Hermite spline with tension, bias, and continuity parameters defined to change the behavior of the tangents.Given n + 1 knots, :p0, ..., p n , to be interpolated with… …   Wikipedia

  • 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… …   Deutsch Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • Bicubic interpolation — In mathematics, bicubic interpolation is an extension of cubic interpolation for interpolating data points on a two dimensional regular grid. The interpolated surface is smoother than corresponding surfaces obtained by bilinear interpolation or… …   Wikipedia

  • Multivariate interpolation — In numerical analysis, multivariate interpolation or spatial interpolation is interpolation on functions of more than one variable. The function to be interpolated is known at given points and the interpolation problem consist of yielding values… …   Wikipedia

  • List of mathematics articles (C) — NOTOC C C closed subgroup C minimal theory C normal subgroup C number C semiring C space C symmetry C* algebra C0 semigroup CA group Cabal (set theory) Cabibbo Kobayashi Maskawa matrix Cabinet projection Cable knot Cabri Geometry Cabtaxi number… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”