Intro to Cubic Splines

Splines are ubiquitous in computer graphics; they can be found in all but the most limited graphics libraries, masquerading under countless names and taking on an equally vast range of forms.  At the kernel of most implementation is a third order polynomial:

Generally, the name applied to an implementation indicates the way in which the vector coefficients { a, b, c, d } are calculated.  Resources on specific implementations are abundant; rather than dictating the recipes for various types this post is intended provide a fundamental understanding that can be used to derive your own types.

The formulation of v(t) as a third order polynomial necessitates the production of four constraints in order to uniquely define the four coefficients.  There is a great deal of freedom in the way the constraints can be chosen.  A common choice is a set of four control points { v0, v1, v2, v3 } that the spline must pass through at the parametric values of t ∊ { 0,  1/3,  2/3,  1 }.

Plugging t ∊ {0, 1/3, 2/3, 1} into v(t) and expanding produces a set of four linear equations:

The same expansion can be neatly collapsed into a single linear equation:

The 4×4 matrix on the left will be referred to as the parameter matrix as its formulation is a function of the parametric values of t for which the constraints apply.  Note that while the parameter matrix is an array of scalars the elements within the two column vectors are actually vectors themselves; this notation is chosen for the sake of convenience and is meant to imply:

Where i indexes the individual elements of each vector.  Computing the coefficients  { a, b, c, d } is a simple matter of multiplying the inverse of the parameter matrix with the column of control points { v0, v1, v2, v3 } and simplifying the results.  Doing so produces the following:

The result of plotting v(t) with the choice of control points { (1, 4)  (15, 4)  (10, 8)  (6, 1) } is shown in Figure 1.

An equally common scheme is to choose two control points and two tangent vectors, one at each position, that determine the magnitude and direction of the spline’s first order derivative.  The first order derivative of v(t) with respect to t takes the form:

Let the choice of constraints { v0, v1, t0, t1 } be applied to the spline at t ∊ {0, 1} where { v0, v1} are the positional constraints and { t0, t1} are the tangential constraints.

Plugging t ∊ {0, 1} into v(t) and v(t) and expanding produces a set of four linear equations:

Just as before, the same expansion can be neatly collapsed into a single linear equation:

The result of plotting v(t) with the choice of control points { (2, 6)  (14, 5) } and tangent vectors { (25, 25)  (0, 35) } is shown in Figure 2 (the tangent vectors have been scaled down by a factor of 10).

Other spline configurations follow the same pattern of (1) selecting constraints and (2) solving the resulting system of equations such that the spline coefficients can be written as an explicit function of the control data.  Occasionally the interval chosen for the parametric value t is something other than [0, 1] such as: [-1, 1], [-1, 2], [0, 3], etc.  Changing the bounding interval of t alters the parameter matrix and thus invalidates the computation of the coefficients { a, b, c, d } as a static function of the control data.  Flexible implementations cope with variable parameter-intervals by requiring the user to specify where on the spline the control data is applied.  The parameter matrix can then be assembled dynamically and inverted on the fly to compute the spline coefficients.  The overhead incurred by this flexibility can be avoided in most cases by detecting common interval choices and defaulting to a set of previously computed and inverted parameter matrices whenever possible.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s