Cubic Spline Basics

By Dendrite

DISCLAIMER: I don't assume any responsibility should anything undesirable happen due to this file ... but if anything cool happens, it's definitely down to me!

Cubic splines are a means of interpolating a curve between two points in space, given their respective co-ordinates as well as the gradients that the curve is supposed to have at either of the points.

This comes in handy if, say, you want to move an object around in a demo but do not want to store the exact co-ordinates of the object for each and every frame. Using cubic interpolation, a few co-ordinates will do because the intermediate values can be calculated in real time. Apart from saving you RAM for cooler stuff than paths, this has the advantage than you can vary the number of intermediate values according to the speed of the machine - otherwise the framerate would be fixed, which would be - well, you name it.

Back to theory.

At this point you might ask why we actually use cubics and not just another function, say quadratics or a linear one. If you use a linear function, you'll get a straight line. Which is guaranteed not give smooth curves unless you use so many little sections that you nearly make up for the co-ordinate space you wanted to save in the first place. Try a quadratic. This time, it will actually be a bit smoother. However, the general quadratic equation (y=ax^2+bx+c) has just three parameters, so you can only specify three "characteristics" in the first place. This means that you can only specify one gradient, which can be at one of the points or somewhere in between. Of course, you could try specifying only one point - but hey!, that would be pretty darn useless. Finally, by using a cubic (y=ax^3+bx^2+cx+d), you can specify four parameters and thus four "characteristics", namely both points and two gradients. When there are two adjacent splines, you just use the same point and gradient , and the resulting path will be perfectly smooth. (NB You can nicely check out the differences between linear, quadratic and cubic interpolation on a lathe in POVRAY.)

You waffled enough buddy. I want splines, right now ... OK!

The overall process consists of two steps:
a) finding the right cubic function.
b) doing the actual interpolation in a loop which calculates the value of cubic for the present situation.

I'll leave b) to you, cos there is no general way of doing this =)

And since this is supposed to be an easy tutorial, I'll constrain a) to 2D splines in which both points have different x-coordinates. If they don't, the cubic won't be a function any more (cos a function can't assume more than one y-value per x-value, for the first years ...), and you'll have to swap axes. But well, you sort that out.

The parameters of the cubic can be derived from four simultaneous equations:

y1 = a*(x1)^3 + b*(x1)^2 + c*(x1) + d
y2 = a*(x2)^3 + b*(x2)^2 + c*(x2) + d

g1 = a*(x1)^2 + b*(x1) + c
g2 = a*(x2)^2 + b*(x2) + c

... where:

(x1,y1) are the co-ordinates of point 1,
(x2,y2) are the co-ordinates of point 2,
g1 is the gradient at point 1, and
g2 is the gradient at point 2.

After a sheet of A4 full of mental scribblin' you'd arrive at the following:

  a=( 2*(y1-y3)*(x1-x3) - (g1-g2)*(x1^2-x3^2-2*x1*(x1-x3))
      -2*g1*(x1-x3)*(x1-x3) ) / ( 2*(x1^3-x3^3
      -3*(x1^2)*(x1-x3))*(x1-x3)
      -3*(x1^2-x3^2)*(x1^2-x3^2-2*x1*(x1-x3)))
  b=( g1-g2-3*a*(x1^2-x3^2) ) / ( 2*(x1-x3) )
  c=g1-3*a*(x1^2)-2*b*x1
  d=y1-a*(x1^3)-b*(x1^2)-c*x1

(These are the straight results, I made no attempt at optimisations.)

Now use a, b, c and d in the general cubic y=a*x^3 + b*x^2 + c*x + d. Loop through the cubic with different values of x, get a smooth path ... and enjoy.

See you soon (or not: I got exams guys ... !)

Dendrite

P.S. In many commercial 3D programs one can specify even more characteristics like elasticity of the spline etc. Also they work whatever the orientation of the spline. Anyone knows how to do that mail me please. Or, for any questions: thunderchopper@hotmail.com

For tracking stuff check out http://ban.joh.cam.ac.uk/~srj22/