Introduction to Splines

This is the second post in a multiple part series. The first post was on interpolation between two values. Here we will look at interpolation between multiple values.

Splines are mathematical functions to interpolate between several values. They are defined as piecewise polynomials, meaning that each interval is handled separately.

So, let’s get started. For example, we will interpolate with 10 control points. The interpolation function will loop, so we also copy the first point to the end. Also note that these control points are uniformly spaced (at 0, .1, .2, .3, etc) on the X axis. In general we will try to avoid having uniform spacing as an absolute requirement because it’s not always practical.
splines_1d_points

Our goal with a spline is to take in a list of inputs, Xs, and outputs, Ys, and produce a reasonable output for any given input. Each XY pair is called a control point, knot, or duck. The input into a spline function is usually labeled splines_t, for time.

Remember that splines are defined piecewise; a separate function can be written for each interval. The simplest spline uses the Step function for each interval. That is, it just jumps to the nearest control point. This is rarely useful, and mostly makes its way into programs by accident.
splines_1d_step

Next, we can use linear interpolation for each interval. Note that linear interpolation only considers the two surrounding control points for each interval. Because of this, it is very local. Any one control point only affects the interval immediately before and after it. We will also look at this spline’s derivative. You can easily see that it’s not continuous. If you prefer to think of the spline function as defining an object’s position, then the derivative can be thought of as the object’s speed. It not hard to imagine that linear interpolation gives a jerky appearance in animations, because of it’s non-continuous speed and infinite acceleration.
splines_1d_linearsplines_1d_linear_d

Cosine interpolation fixes the non-continuous derivative, but introduces other problems. It forces the derivative at each control point to be 0. So, if cosine interpolation is used in animation, an object will slow down and stop at each control point. This is usually undesirable, but it can nevertheless sometimes be useful. Cosine interpolation is still local, it only every considers the immediately adjacent control points for each interval.
splines_1d_cosinesplines_1d_cosine_dsplines_1d_cosine_dd

Cubic Hermite Splines

To get smoother interpolation it is desirable to consider more than just two control points for each interval. Natural cubic splines have global control, and the function always considers each control point. Catmull-Rom, Cardinal, and Kochanek-Bartels splines use four control points for each interval (that is the two immediately surrounding control points, and an extra control point on each side, for each interval). These last three splines are all types of cubic Hermite splines.

A cubic Hermite spline is a spline with each polynomial in Hermite form. Basically, each interval will use two control points and two tangents. These tangent values can be defined by the user, or defined automatically by more surrounding control points. First off, we need to define the four Hermite basis functions.

splines_h1_function

splines_h2_function

splines_h3_function

splines_h4_function

splines_hermite_basis

Each interval uses the four basis functions like so:
splines_hermite_function where splines_m1 and splines_m2 are the tangent values.

You can see that splines_h1 and splines_h2 scale the control points, while splines_h3 and splines_h4 scale the specified tangents. You can also quickly see that the spline will pass through each control point by considering the scaling factors from the graph above.

The tangents can be specified individually by an artist, or generated automatically. They are usually generated automatically, but to get a feel for the cubic Hermite spline I’ll show an example where every tangent has been specified as 1. You can see that the function always has a slope of 1 at each control point. In other words, it passes through each control point at 45 degrees because that was the tangent specified.
splines_1d_hermite

Cardinal Splines

Given the control points splines_y0, splines_y1, splines_y2, and splines_y3 we can use a Cardinal spline to interpolate between splines_y1 and splines_y2.

Assuming uniformly spaced control points, a Cardinal spline defines the tangents as:
splines_m1_function splines_m2_function
Where splines_c is a tension parameter. The tension parameter can intuitively be thought of as the length of the tangents. splines_s is a scaling factor for non-uniform control point spacing. If the control points are uniformly space, it can be omitted or set to 1. We’ll cover non-uniform control point spacing below.

Here are some examples of Cardinal splines with various splines_c (tension) values:

splines_1d_cardinal_lsplines_1d_cardinal_h

It’s straight forward to adapt the Cardinal spline for non-uniform control. However, it seems to be little known. A search online doesn’t turn up much help and indeed a few sources even say it’s non-trivial or even impossible (due to the curvature of the curves, uh-huh). That’s not true. Using non-uniformly spaced control points is actually quite straightforward.

For non-uniform control points, each tangent simply needs scaled. First we’ll define a few variables useful for the control point spacing.

splines_dx_function splines_dx1_function splines_dx2_function

Then the scaling factors are:
splines_s1_function splines_s2_function

Non-uniform control point spacing is incredibly useful for animation key-framing. With uniform control points an artist would have to specify the models’ positions every fixed amount of time (e.g. every half second). With non-uniform control point spacing, an animation artist can specify models’ positions whenever convenient.

Catmull-Rom Splines

A Cardinal spline with a tension of .5 is a special case. It’s then called a Catmull-Rom spline. Catmull-Rom splines are thought to be esthetically pleasing and are quite common.
splines_1d_catmullromsplines_1d_catmullrom_dsplines_1d_catmullrom_dd

Two Dimensional Splines

Wrapping up, we’ll take a quick look at two dimensional splines. It should first be noted that the X and Y axis can be interpolated completely separate. This makes sense since the axises are orthogonal, and a movement on one axis does not affect the other axis at all. Good spline code should be written generically and work equally well with a single number or a vector. In C++ this is easily accomplished with templates, which allows the same code to be used for one or more dimensions.

splines_2d_linear
splines_2d_cardinal
splines_2d_catmullrom

Next up we’ll look at arc-length parametrization.

10 Responses to “Introduction to Splines”

  1. Jeffom Says:

    Very good article.
    Hope you continue writing more about this.

  2. Peter Says:

    > ascetically pleasing

    I think you mean “esthetically pleasing”. Ascetic is usually a bad quality (and reserved for opinionated articles) and your article is actually quite good. I hope I’ll get the non-uniform Catmull-Rom in by tonight. Yours is one of the few that says it can be done.

  3. Lewis Says:

    Yes, thanks for the correction.

    I’ve used non-uniformly spaced control points extensively, and I’m sure you’ll get it without much trouble. I really have no idea why some others sources say it’s impossible.

  4. Steve Says:

    That’s a great article; it really helped me to understand (although I still haven’t fully got my head around it).

    I think it may be missing something though. According to Wikipedia, if the interval is not 1, then the calculation of the tangents included a scale factor: m1h3(t)/(y2-y1) and m2h4(t)/(y2-y1) – it wasn’t until I put this in that my results started looking as I expected them to.

  5. samaursa Says:

    Great article. It has been a long time since I worked with splines and this refresher was exactly what I needed. Looking forward to your next arc-length parametrization article!

  6. Philippe Simons Says:

    Greate article, did you published the article on arc-length parametrization?

  7. Lewis Says:

    No, I haven’t gotten around to it yet (almost 2 years later).

  8. Jay Omega Says:

    Now 3+ years later ….
    Any closer to publishing Arc-Length parametrization (I hope, I hope, I hope….)

    Looking forward to it and the promised C++ code …. which I’d like to transpose into a C# version.

    Kind regards,

  9. Non-Linear Trends | Advanced Epidemiology Says:

    [...] http://codeplea.com/introduction-to-splines This website shows examples of splines that extend beyond the cubic and smoothing versions discussed in class in order to capture more complex shapes [...]

  10. Niels Says:

    Fantastic article! I, also, would love to see that arc-length article. It’s the other component for regulating velocity along a spline, which is so useful in animation and the like.

    also, If you want an in-depth treatment of splines,check out Barsky’s “an introduction to splines for use in computer graphics”.

Leave a Reply