Interpolation is a very common technique used all over the place, especially in computer graphics. Pretty much every game programmer can code a simple linear interpolation in his sleep. Interpolation is everywhere, especially in the realm of animation.
Linear interpolation is simple and easy. Unfortunately, it is also very limited, and produces ugly results when used for moving objects around. For a given set of control points, linear interpolation will produce very rigid, jerky movement, with abrupt changes in direction and speed. This obviously doesn't make for a very good result.
Typically, we will use more complicated interpolation techniques, such as cubic spline interpolation, to overcome this problem. A good spline interpolation is smooth and graceful, and can be controlled very precisely given suitable control points. Unfortunately, it can also become fairly expensive to compute, and setting up lots of control points by hand can be tedious.
Sometimes, we want just a simple interpolator that creates a nice smooth path between two given control points - and it'd be nice if it was fast, too. In the remainder of this post, I'll describe just such a technique.
Background
Let's start with a basic linear interpolation. The basic formula should be very familiar: y = (x - x1)((y2 - y1) / (x2 - x1)) + y1. This will give us a run-of-the mill linear interpolation of y between the points (x1, y1) and (x2, y2), given an input value of x.
Now, here's the important point: that function is just the result of a simple function that has been scaled and translated with a couple of simple transformations. The process of applying those transformations to a function is beyond the scope of this post, but it should be familiar from most high-school level algebra courses. Mathematically-inclined readers should already recognize that the linear interpolation formula is just a transformation of a simple base function, namely y = x.
The interesting thing about y = x is what it looks like inside the square (0,0)-(1,1):
This is the heart of interpolation: you first "squish" the inputs so that they fit into the square (0,0)-(1,1); then, apply the interpolation function; then "unsquish" the result to get a value in the original required range. A convenient way to think about this is as a percentage function. You put in some percentage of x, and out comes a corresponding percentage of y. If you know the percentage "distance" that x has travelled from the beginning of its range towards the end, you can convert that into a percentage "distance" that y should move as well.
For example, let's set up the control points (10, 50) and (25, 106). If we substitute those into our original linear interpolation equation and graph the function, this is the result:
So, in theory, if we have any function that passes through the points (0,0) and (1,1), we can apply the squishing/unsquishing (transformation) technique, and then use that function for interpolation.
Logistic Functions
If you've taken a statistics course, you're probably acquainted with logistic functions. A logistic function produces a really nice, smooth S-shaped curve. In fact, it's a curve that looks like it would be just about perfect for doing interpolation...
Here's what the logistic function y = 1 / (1 + e-5x) looks like:
Looks nice, eh? Only problem is, it doesn't quite fit inside our (0,0)-(1,1) box: it hangs over into the negative x axis a bit. Let's translate it by 0.5 to the right, using the equation y = 1 / (1 + e-5(x - 0.5)):
This is getting better, but it still doesn't quite fit: at x = 0 it's a bit above the y axis, and it doesn't quite hit the y = 1 line by the time x hits 1, either. (In fact, strictly speaking, it never reaches y = 1 at all.) This means it isn't quite ready for use as an interpolation function yet. So let's apply another little transformation or two to get it where we want it. Our final equation looks like this: y = ((1 / (1 + e-5(x - 0.5))) / 0.8483) - 0.0894
Perfect! But how did I come up with those two extra numbers? It's pretty simple, but it's an important trick, so remember it for later! Essentially we're doing a little bit of interpolation by hand. First, start by finding the value of y when x is 1. In our case, that value is roughly 0.92414. This is about 0.07586 away from 1, which is what we want the function to equal. So, multiply that difference by 2, to get 0.1517, and subtract that back from 1, which yields 0.8483. Divide the entire function by this value. Now, if you graph the function again at this point, you'll see that it's too high - it doesn't equal 0 at x=0, and it actually passes above y=1 when x=1. So, find the value of this new equation at x=0 - it is roughly 0.0894. Subtract that from the equation, and voila - now the function fits into our (0,0)-(1,1) square.
Smooth Interpolation
Well, this is a plenty nice little graph, but it isn't quite an interpolator just yet. For that, we need to re-apply the squishing transformations that let us get a nice interpolation between any control points we want.
I'll spare you the tedious algebra, but you should be able to do this on your own - if you know the underlying mathematics, you can create your own interesting interpolation functions easily.
The resulting equation looks like this:
y = ((1 / (1 + e(-5)((x - x1) / (x2 - x1) - 0.5)))(1 / 0.8483) - 0.0894)(y2 - y1) + y1
And here's what it looks like when we provide the control points (2, 3) and (17, 11):
Beautiful!
Extra Exercises
There's a few things you might play with here to get different effects. This interpolator will accelerate smoothly and then decelerate, but it's still only a subtle change over a linear interpolation. You can change the exponent part of the equation a bit to get a more or less "extreme" acceleration profile; the current exponent coefficient is -5; a value of -2 will be much closer to a linear interpolation, whereas a value of -15 will produce a very slow initial and final change, with an extreme rapid spike in the middle.
So far, all I've done is show an example of translating the function along the x axis. You can also experiment with multiplying various values by the x coordinate to scale the interpolation. This can be used (in combination with a suitable translation) to "bias" the acceleration/deceleration, so that the interpolation curves more rapidly at the beginning than at the end, for example.
Finally, you can get some truly interesting results by combining more than one function. For instance, adding a suitably transformed sine wave can cause the interpolation to "overshoot" slightly (it will actually go below 0 and above 1) which results in a sort of "imperfection." When used to control a camera, for instance, this has the result of slightly passing a point and then recentering on it, giving a very realistic and "human" touch to the result. You can also experiment with adding (or subtracting!) other functions like polynomials to get more complex curves.
The most advanced method of combination is composing two functions. For this, you first process the interpolation using one function, then re-interpolate with a second. (This can cause the squishing/unsquishing bit to be a little complicated, though.) I personally haven't found any practical use for such things yet, but you can get some very interesting behavior by doing this. Experiment, have fun, and see what you can discover!
One last tip
I highly recommend a couple of tools for this - a calculator and some kind of grapher. Graphing calculators are obviously the most convenient solution. However, a cheap pocket calculator (or even Windows Calculator) will suffice; combine this with a graphing package such as Graphmatica, and you're all set to play with creating interpolators of your own.
Now go forth and interpolate things... smoothly.
