digplanet beta 1: Athena
Share digplanet:

Agriculture

Applied sciences

Arts

Belief

Chronology

Culture

Education

Environment

Geography

Health

History

Humanities

Language

Law

Life

Mathematics

Nature

People

Politics

Science

Society

Technology

In numerical analysis, a cubic Hermite spline or cubic Hermite interpolator is a spline where each piece is a third-degree polynomial specified in Hermite form: that is, by its values and first derivatives at the end points of the corresponding domain interval.

Cubic Hermite splines are typically used for interpolation of numeric data specified at given argument values $x_1,x_2,\ldots,x_n$, to obtain a smooth continuous function. The data should consist of the desired function value and derivative at each $x_k$. (If only the values are provided, the derivatives must be estimated from them.) The Hermite formula is applied to each interval $(x_k, x_{k+1})$ 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 curves or motion trajectories that pass through specified points of the plane or three-dimensional space. In these applications, each coordinate of the plane or space is separately interpolated by a cubic spline function of a separate parameter t.

Cubic splines can be extended to functions of two or more parameters, in several ways. Bicubic splines 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. 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 $(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 an arbitrary interval

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

$\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 = (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.

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)(x-r)$
$R'(x) = ax(x-1) + ax(x-r) + a(x-1)(x-r)$

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 $h_{00}, h_{10}, h_{01}, h_{11}$ are Hermite basis functions. These can be written in different ways, each way revealing different properties.

expanded factorized Bernstein
$h_{00}(t)$ $2t^3-3t^2+1$ $(1 + 2 t) ( 1 - t)^2$ $B_0(t) + B_1(t)$
$h_{10}(t)$ $t^3-2t^2+t$ $t (1 - t)^2$ $\frac{1}{3}\cdot B_1(t)$
$h_{01}(t)$ $-2t^3+3t^2$ $t^2 (3 - 2 t)$ $B_3(t) + B_2(t)$
$h_{11}(t)$ $t^3-t^2$ $t^2 (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 $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)={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,\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 $(t_1,t_n)$.

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,\ldots,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, sometimes called a canonical spline,[1] is obtained[2] 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 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.[3] Thus the Catmull–Rom spline is

$\mathrm{CINT}_x(p_{-1}, p_0, p_1, p_2) = \frac 12 \begin{pmatrix} -x^3 +2x^2 - x \\ 3x^3 - 5x^2 + 2 \\ -3x^3 + 4x^2 + x \\ x^3 - x^2 \end{pmatrix}\cdot \begin{pmatrix} p_{-1}\\p_{0}\\p_1\\p_2 \end{pmatrix} = \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.

References

• Catmull, Edwin and Rom, Raphael, A class of local interpolating splines, in R. E. Barnhill and R. F. Riesenfeld (eds.) Computer Aided Geometric Design, Academic Press, New York, 1974, 317–326.
 54 videos foundNext >
 Mod-01 Lec-06 L6-Cubic Hermite InterpolationElementary Numerical Analysis by Prof. Rekha P. Kulkarni , Department of Mathematics, IIT Bombay. For more details on NPTEL visit http://nptel.iitm.ac.in. Lecture 12 - Cubic Spline InterpolationNumerical Methods and Programing by P.B.Sunil Kumar, Dept, of physics, IIT Madras. Cubic Hermite SplineDone using C++, OpenGL and Glut. MATLAB tutorial: Curve Fitting (quadratic, cubic, polynomial, etc)This is Matlab tutorial: Curve Fitting. The code can be find in the tutorial section in http://www.eeprogrammer.com More engineering tutorial videos are avai... Spline Interpolation: Linear Spline: TheoryLearn the theory behind linear spline interpolation. For more videos and resources on this topic, please visit http://nm.mathforcollege.com/topics/spline_met... Unity3D Spline based rollercoaster wipUsing Cubic Hermite splines to interpolate the track. Tangent weight is automatic for now. UT Austin Villa 3D Simulation RoboCup 2011 Kick OptimizationOptimization run of a forward kick. The fitness of the agent is determined by how far it can kick the ball forward averaged over ten kick attempts. The agent... UT Austin Villa 3D Simulation RoboCup 2011 KicksDifferent kicks used by UT Austin Villa. Kicks were designed by defining waypoints relative to the ball for the foot to reach along its kicking trajectory. C... Hermite Spline Editor and Spline Based AnimationUni assignment (Animation & Simulation for Computer Games). OpenGL (immediate mode), C++ Development: 1 week. Mod-01 Lec-08 L8-Cubic Spline InterpolationElementary Numerical Analysis by Prof. Rekha P. Kulkarni , Department of Mathematics, IIT Bombay. For more details on NPTEL visit http://nptel.iitm.ac.in.
 54 videos foundNext >

We're sorry, but there's no news about "Cubic Hermite spline" right now.

 Limit to books that you can completely read online Include partial books (book previews) .gsc-branding { display:block; }

Oops, we seem to be having trouble contacting Twitter