|Interpolation using cubic splines|
|Fast cubic splines|
A spline is a contiguous curve defined by a set of discrete values.
The set of discrete values is typically referred to as "control points". For some spline types the curve touches the control points, for other spline types it doesn't.
Control points are specified by position, optionally further information is attached to the points (i.e. the s parameter on X-splines).
Bezier segments are used in graphics languages like PS/EPS, PDF and SVG to draw curve segements.
A Bezier segment is specified by 4 points:
For t in the range 0≤t≤1 we can calculate curve points using the formula:
An alternate specification of a Bezier segment consists of start point, endpoint and the first derivative of the curve in start and end point. The control points can be calculated using the formulas:
Cubic splines are used for curve interpolation if a curve is
given as set of x/y pairs.
Optionally dy/dx may be given for some or all of the points.
For n points the curve is splitted into n-1 intervals.
Each interval i (1≤i≤n-1) is described by a 3rd degree polynomial:
xi is the x value at the beginning of interval i.
A structure containing the original points (interval borders) and the coefficients for the polynomials is referred to as "piecewise polynomial" (PP).
On the left interval border x=xi
the polynomial value must match the given y value.
So we can rewrite our polynomial to:
For n-1 polynomials we need 3 coefficients ai, bi, and ci for each polynomial. 3(n-1) equations are necessary.
|i interval||Equation number||Equation|
|At the right border of each interval i the polynomial value must match the y value of point i+1.|
|On inner points k
(2≤k≤n-1) the first derivative of the polynomials
must be contiguous.
At the right endpoint of interval i (i=k-1) the first derivative of polynomial pi must be equal to the first derivative of pi+1.
|On inner points the second derivative must be contiguous too.|
|The remaining two equations depend on the spline type (sometimes referred to as condition):|
|For not-a-knot splines the third polynomial derivative is contiguous on the second and penultimate point.|
|For variational (natural) splines the second derivative is 0 at start and end point.|
|For periodic splines the first and second derivative of the first polynomial in the first point and the last polynomial in the last point must be equal.|
|If the value of the first derivative yi'=dy/dx is given for some points, we have to replace some of the equations above:|
|If the value of the first derivative is given for an inner point i (2≤i≤n-1) we have to replace the equations for continuity of first and second derivative by equations for the first derivative.|
|If the value of the first derivative is given for the start point we have to replace one equation:|
|If the value of the first derivative is given for the end point we have to replace one equation:|
To build a fast cubic spline, the first derivative
dy/dx in each of the given points is calculated by
placing a quadratic polynomial in the points left neighbour, the
current point and the right neighbour. We find dy/dx
by deriving the the quadratic polynomial in the current point.
Unless the cubic spline is periodic, the dy/dx for start and end point is calculated from the first and last quadratic polynomial.
Instead of solving a system of linear equations we have a linear dependency between computation time and number of points here.
X-splines were introduced by Carole Blanc and Christophe Schlick
on the SIGGRAPH 1995 conference.
Their article "X-Splines: A Spline Model Designed for the End-User" (proceedings of the SIGGRAPH 1995) describes X-splines in detail.
Here is a very short summary: