What are the most common splines you will find in game development?

Question

List here the most common splines found in game development, how many points the method needs to interpolate a curve, and how can you build a data type that allows you to get an interpolation of the curve points. Examples: Bezier curves, B-Splines, Cubic Splines, etc.

P.S.: I'm putting this as a community wiki so we can list all kinds of spline interpolation.

Answer 1

The most simple case is a linear interpolation for a straight line:

(x0, y0) * ------------------------ * (x1, y1)

Say t is between [0, 1]:

function lerp((x0, y0), (x1, y1), t):
    return (x0+(x1-x0)*t, y0+(y1-y0)*t)

Answer 2

Catmull-Rom splines (a type of cubic hermite spline) can be quite useful, if you've got a set of points that you want to create a smooth path between (without defining any additional control points), such as camera paths

For all the maths, see:

http://en.wikipedia.org/wiki/Cubic_Hermite_spline

If you're using D3DX, there's some handy functions for dealing with them (D3DXVec3CatmullRom)

Answer 3

Edit: Sorry, as Jason points out in the comment, the following answer is not about splines but about two-dimensional linear (or bilinear) interpolation. I am choosing not to delete it in case someone might find it informative.

---

I've created a simple 3D terrain and then wanted my character to walk across the terrain. So, to find the character's height at any point on the terrain, I used bilinear interpolation.

Here is the Java code I use for the bilinear interpolation:

/**
 * Interpolates the value of a point in a two dimensional surface using bilinear spline interpolation.
 * The value is calculated using the position of the point and the values of the 4 surrounding points.
 * Note that the returned value can be more or less than any of the values of the surrounding points. 
 * 
 * @param p A 2x2 array containing the heights of the 4 surrounding points
 * @param x The horizontal position, between 0 and 1
 * @param y The vertical position, between 0 and 1
 * @return the interpolated height
 */
private static float bilinearInterpolate (float[][] p, float x, float y) {
    return p[0][0]*(1.0f-x)*(1.0f-y) + p[1][0]*x*(1.0f-y) + p[0][1]*(1.0f-x)*y + p[1][1]*x*y;
}

/**
 * Finds a 2-dimensional array of the heights of the four points that 
 * surround (x,y).
 *
 * Uses the member variable "verts", an 2D array of Vertex objects which have
 * a member "height" that is the specific vertex's height.
 */
private float[][] nearestFour(float x, float y) {
    int xf = (int) Math.floor(x);
    int yf = (int) Math.floor(y);

    if(xf < 0 || yf < 0 || xf > verts[0].length-2 || yf > verts.length-2) {
        // TODO do something better than just return 0s
        return new float[][]{
                {0.0f, 0.0f},
                {0.0f, 0.0f}
            };
    } else {
        return new float[][]{
                {verts[yf][xf].height, verts[yf][xf+1].height},
                {verts[yf+1][xf].height, verts[yf+1][xf+1].height},
            };
    }
}

Note that bicubic interpolation might present smoother or more realistic interpolation across distant points; but I choose to go with bilinear because I have a dense grid, in an attempt to optimize (perhaps prematurely).