Welcome to mapoid.com on July 11 2009.
This is an internet experiment running to monitor browsing habbits of individuals through wikipedia contents.

Cubic Hermite spline

From Wikipedia, the free encyclopedia

  (Redirected from Catmull-Rom spline)
Jump to: navigation, search

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 = (x − xk) / (xk + 1 − xk).

Contents

[edit] Interpolation on a single interval

[edit] 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].

The four Hermite basis functions can be defined as

h_{00}(t) = 2t^3-3t^2+1 = (1 + 2 t) ( 1 - t)^2\,\!
h_{10}(t) = t^3-2t^2+t = t ( 1 - t)^2\,\!
h_{01}(t) = -2t^3+3t^2 = t^2 (3 - 2 t) \,\!
h_{11}(t) = t^3-t^2 = t^2 (t - 1)\,\!

to give the 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.

[edit] 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}_0 + h_{10}(t)h\boldsymbol{m}_0 + h_{01}(t)\boldsymbol{p}_1 + h_{11}(t)h\boldsymbol{m}_1.

with h = xk + 1 − xk and t = (x − xk) / h. Note that the tangent values have been scaled by h compared to the equation on the unit interval.

[edit] Uniqueness

Using the procedure outlined above, two control points and two tangents specify a third-degree polynomial. Two distinct third-degree polynomials satisfying the given boundary conditions would differ only by a third-degree polynomial which is zero with zero derivative at two distinct points. The only such third-degree polynomial is zero.

[edit] Interpolating a data set

A data set, (x_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 (x1,xn).

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

[edit] Finite difference

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(x_{k+1}-x_{k})} + \frac{\boldsymbol{p}_{k}-\boldsymbol{p}_{k-1}}{2(x_{k}-x_{k-1})}

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

[edit] 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}}{2}

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.

[edit] Catmull–Rom spline

For tangents chosen to be

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

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

The curve is named after Edwin Catmull and 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.

[edit] Kochanek–Bartels spline

Main article: 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.

[edit] Monotone cubic interpolation

Main article: 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.

[edit] 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], and the result 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}

where the left-hand vector is independent of the p.

This is in fact the Catmull–Rom spline as described above. Note that this approximation is only valid for x \in [0,1].

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

[edit] See also

[edit] References

  1. ^ Cardinal Splines at Microsoft Developer Network
  2. ^ Two hierarchies of spline interpolations. Practical algorithms for multivariate higher order splines

[edit] External links

Retrieved from "http://en.wikipedia.org/wiki/Cubic_Hermite_spline#Catmull.E2.80.93Rom_spline"
Personal tools
Visit joltnews for the latest headlines
Visit bloit.com for company information
Geed Media does computer consulting on long island.
This page viewed times. See Logs