This is the third part of the interpolation tutorial series. Here I will finally cover the so called spline interpolation. Part one and part two covered linear interpolation and tweening. Spline interpolation is close to linear interpolation as it works great on arrays of points. So you might want to check out the first part, if you missed it. Again, I will cover most of the mathematical foundation needed to implement the algorithm yourself, as well as provide ready to use code that you may use in your project.

What is spline interpolation?

Let's start from linear interpolation between a set of points. All that is needed for linear interpolation, are the positions (x,y) of the points. Spline interpolation takes this idea one step further. Each point now includes a slope k in addition to the x and y values. This allows not only to fit a linear function (aka a straight line) between the points, but a polynomial of order two. The most simple form of such a polynomial is a parabola. This will make the function smooth (and not zigzag like in linear interpolation) by including higher order terms. In other words, the additional information k will be used to smooth the interpolation function in a smart way.

k is a real valued number. It describes the slope of the tangent of the smooth function at that point. For k = 0, the tangent is horizontal. For larger values of k the tangent will get steeper counter clockwise. For smaller values, the tangent will rotate clockwise. For k equals +/- infinity, the tangent will be vertical (pointing up or down respectively). There are different ways to calculate k values for all points. Three ways will be described later in this tutorial. The smooth interpolation function will go through all points for any k values, but it can occur, that the interpolation function will overshoot.

The Algorithm

The interpolation algorithm is based on the equations introduced in the fist part of the tutorial. At first, the two neighboring points are searched. Then a value t (range 0 to 1) is calculated which describes where in between the two neighboring points the interpolation should be evaluated.

The major change in the algorithm is the calculation of the interpolated value, as the derivatives of the points are taken into account. The idea is to use a second order polynomial and to bring that to the symmetrical form. This means some lines of calculation, but luckily, the equation has been solved by countless maths students for you. And that's it: spline interpolation!

The haxe code is listed below.

private function interpolate (p : Array<SplinePoint>, x : Float ) : Float
{
  // this is all the same as in the first tutorial
  var pMin : SplinePoint =  new SplinePoint(Math.POSITIVE_INFINITY,0);
  var pMax : SplinePoint =  new SplinePoint(Math.NEGATIVE_INFINITY, 0);
  var pleft : SplinePoint = new SplinePoint(Math.POSITIVE_INFINITY, 0);
  var pright : SplinePoint = new SplinePoint(Math.NEGATIVE_INFINITY, 0);

  for (j in 0... p.length)
  {
    var pt:SplinePoint = p[j];

    if (pt.x < pMin.x) 
    {
      pMin.x = pt.x;
      pMin.y = pt.y;
      pMin.k = pt.k;
    }
    if (pt.x > pMax.x)
    {
      pMax.x = pt.x;
      pMax.y = pt.y;
      pMax.k = pt.k;
    }

    if (pt.x < pleft.x && x < pt.x)
    {
      pleft.x = pt.x;
      pleft.y = pt.y;
      pleft.k = pt.k;
    }

    if (pt.x > pright.x && x > pt.x)
    {
      pright.x = pt.x;
      pright.y = pt.y;
      pright.k = pt.k;
    }

  }
  if (x <= pMin.x) return pMin.y;
  if (x >= pMax.x) return pMax.y;

  // t is the local coordinate between i and i-1. 
  // t must be in the range of [0,1] and can be used for interpolation
  // if t == 0, the point [i-1] is chosen, for t == 1, the point [i] is returned.
  var t : Float  = (x - pleft.x) / (pright.x - pleft.x);

  var a : Float =  pleft.k  * (pright.x - pleft.x) - (pright.y - pleft.y);
  var b : Float = -pright.k * (pright.x - pleft.x) + (pright.y - pleft.y);

  // this would be linear interpolation
  var q : Float = (1.0 - t) * pleft.y + t * pright.y;
  // this is the addition from polynomial of order two
  q += a * t +(b - 2 * a) * t * t + (a - b) * t * t * t;

  return q;
}

How to set the k values (slope)

There is still one piece of information missing: How to get the derivatives (k). There is, as usual, no one fits it all way to do it. The simplest way to handle this, is to set all k values to 0. This means, that all points given are extremal values (or saddle points). This means there are no overshoots. For some points at the values (20, 200), (200, 400), (300, 110) and (500, 230, 0) the interpolation would look like this.

You can also do a type of three point interpolation. This means, k for a point i is calculated as the mean value of the slopes between the points i-1 and i as well as i and i+1. Or you use some sort of forward integration. This is depicted in the following imagenine interpolation with mean k](httenter image title hereine interpolation with mean k")

One Last way to calculate the k values is to do this by solving a linear system of equations. This corresponds to the midpoint interpolation formula. Note that this is the way most spline interpolation libraries handle it and the results look "the smoothest". But since the math is cumbersome, most ready to use libs use some sort of linear algebra framework. There are many very good tutorials on this, and I could not explain better. (remember, this is purely optional)

Interpolation is easy (Summary)

This tutorial series started from linear interpolation, covered tweening and touched spline interpolation in this part. It was meant to give you a broad overview about interpolation and to give you the needed mathematical tools and the understanding of the meaning of the equations. You are free to use or adapt the presented code.