Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
1  
It's a good question, IMO. –  jacmoe Aug 5 '10 at 16:02
2  
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. –  Ricket Aug 5 '10 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. –  chiguire Aug 6 '10 at 2:59
add comment

3 Answers

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)
share|improve this answer
add comment

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)

share|improve this answer
add comment

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

share|improve this answer
    
The question is about interpolation along a spline –  Jason Kozak Aug 5 '10 at 18:25
    
Sorry; message added to top of answer. –  Ricket Aug 5 '10 at 19:22
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.