Interpolation pt.1: Linear Interpolation

Whenever something in a game should vary smoothly between two values this can be done by interpolating. Examples are changing an object's position to make it move from A to B or changing the alpha value of a sprite to fade it in or out of the scene. I tried to learn more about the idea and theory of interpolating, but there is not that much information available that is explained well and captures the math up to a point at which the reader can use it by himself confidently.

About this tutorial

This tutorial is part of a series, which will cover interpolation. At first I want to show you linear interpolation. A second part will cover tweening (often called easing). And the third part will cover the dreaded spline interpolation. The tutorial will empower you to implement interpolation on your own by explaining the math step by step. The code given is in haxe, but is easily applicable to the language of your choice as no advanced libraries or language features are used.

Linear interpolation

Ok, what is this interpolating thing about? At first I want to talk only about linear interpolation. Let's stick with the example of the moving object. A game object should move from A to B in a smooth way, e.g. in a cutscene. You (or your designer) provides the positions A and B (y0 and y1) as well as the time the movement starts (x0) and the time you want to reach position B (x1). Note that the y values do not have to be numbers, but can also be vectors, or if you want to interpolate a rotation, they can even be rotation matrices or quaternions. The x values will always be a number.

If you imagine a coordinate system with the time on the x axis and the position on the y axis, calculating a linear interpolation means drawing a straight line between the two points created by (x0, y0), (x1,y1).

To interpolate between those position you can use the following code. It will calculate a variable q which is the interpolation at the point x.

// first get a value t in the range [0,1].
var t : Float  = (x - x0) / (x1 - x0);
var q : Float = (1.0 - t) * y0 + t * y1;
return q;

The value t is in the range between 0 and 1. If x is equal to x0, t is 0. If x is equal to x1, t is 1. The variable t is then used to calculate the value q, which is in the range y0, y1. This represents an linear interpolation between two points.

Interpolation between multiple points

You can extend the same behavior to an array of points. This is shown in the following code example. SplinePoint is a class that has a x and y value. The function linterp takes an array of those SplinePoints and an x value which indicates where to evaluate the interpolation. The array does not have to ordered.

private function linterp (p:Array<SplinePoint>, x : Float) : Float
    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;
        if (pt.x > pMax.x)
            pMax.x = pt.x;
    	    pMax.y = pt.y;

        if (pt.x < pleft.x && x < pt.x)
            pleft.x = pt.x;
    	    pleft.y = pt.y;
        if (pt.x > pright.x && x > pt.x)
    	    pright.x = pt.x;
    	    pright.y = pt.y;
    if (x <= pMin.x) return pMin.y;
    if (x >= pMax.x) return pMax.y;

    var t : Float  = (x - pleft.x) / (pright.x - pleft.x);
    var q : Float = (1.0 - t) * pleft.y + t * pright.y;
    return q;

At first, the points with minimal and maximal x in the array p are searched. If the value x (this is where you want to evaluate the interpolation) lies outside of the values specified in the array, then the value of the most left or right Splinepoint will be returned. Furthermore the closest points to x from the left and right (pleft, pright) are searched. Then the interpolation formulae from above is used to calculate the value between the two points pleft and pright.

linear interpolation The result will look something like this. I added four points (indicated by the red squares) to the array p and called the function to calculate the values in between (white squares).

Ok, that's it for this part. The next part will cover tweening, which will cover mainly interpolating between two points, but with some fancy functions.