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

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.

• It's a good question, IMO. Aug 5, 2010 at 16:02
• I vote for this question to be changed to apply to interpolation rather than specifically spline interpolation. This is what I thought the question was about, thus my out-of-place answer below. Aug 5, 2010 at 19:25
• Although your bilinear interpolation is a good answer, I think these kind of calculations could go in a related question, for example, a spline fit or approximations. Or maybe I'm wrong and these could also go here. Aug 6, 2010 at 2:59

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)


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)

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).

• The question is about interpolation along a spline Aug 5, 2010 at 18:25
• Sorry; message added to top of answer. Aug 5, 2010 at 19:22