I am writing a F-Zero/Wipeout clone. Generating my track from Bezier patches seems to be working really well; it's nice and easy to edit allowing for easy adjustment and the physics so far for travelling along the patches work perfectly.



With one minor detail; unless the distance between the start and control point and the end point and the control point are identical, the patches are no longer linear. The generated polygons that represent them tend to bunch up at one end and whilst travelling along the patch, the vehicle visible slows down and speeds up regardless of the true speed it should be going at.



I don't know much about 3D math; I never took A-level and I'm largely self-taught. Is there any way to get a equally spaced sample regardless of the difference in distance between start/end and control points or am I going to have to throw ease of use and flexibility out of the window and force the distance to be the same by normalising the difference and then multiplying by the mean average distance to place the point equidistant but not where the track designer put it?

It's been a little bit since the last time i worked w/ bezier curves but the last time i did anything with them i remember i was getting evenly spaced samples and i had to make code that only kept the ones that mattered (ie throw points away if they don't significantly change the line at that point).

How are you generating your curve points? Can you show some code or outline your algorithm?

(:

It's a fairly nasty big block of code because it also deals with the barriers and lighting normals, but what I can tell you is that I am generating the curves by linear interpolating between A and B, B and C and then between those two results, which as far as I can tell is what a quadratic Bezier should be (looking on Wikipedia).

The discard idea is nice but it wouldn't be applicable when transforming the 2D positions of the racers (left-right and progress) onto the patch. I do have the side lengths of the patch (use them for dividing the speed of the ship each frame so on an equal patch it keeps a consistent global speed) but that doesn't help much. I guess I could perform a little heuristic if I could find the length of each half of the patch.

Arc-length reparameterization might be what you're looking for.

I'll take a closer look at that tomorrow when I get up. Thanks!

There's some good stuff there. I've had an idea though; would it be possible to determine the length of the first and second halves of the quadratic Bezier separately? This is the function I'm using at the moment to determine the length of the whole Bezier:

//Courtesy of Dave Eberly (http://www.gamedev.net/community/forums/profile.asp?mode=display&id=65726).//Finds the length of a bezier line, used heavily in track code.//--------------------------------------------------------float LengthQuadraticBezier( float fXX, float fXY, float fXZ, float fYX, float fYY, float fYZ, float fZX, float fZY, float fZZ ){    // ASSERT:  C[0], C[1], and C[2] are distinct points.    // The position is the following vector-valued function for 0 <= t <= 1.    //   P(t) = (1-t)^2*C[0] + 2*(1-t)*t*C[1] + t^2*C[2].    // The derivative is    //   P'(t) = -2*(1-t)*C[0] + 2*(1-2*t)*C[1] + 2*t*C[2]    //         = 2*(C[0] - 2*C[1] + C[2])*t + 2*(C[1] - C[0])    //         = 2*A[1]*t + 2*A[0]    // The squared length of the derivative is    //   f(t) = 4*Dot(A[1],A[1])*t^2 + 8*Dot(A[0],A[1])*t + 4*Dot(A[0],A[0])    // The length of the curve is    //   integral[0,1] sqrt(f(t)) dt    float fAX = fYX - fXX;    float fAY = fYY - fXY;    float fAZ = fYZ - fXZ;    float fBX = fXX - 2.0f * fYX + fZX;    float fBY = fXY - 2.0f * fYY + fZY;    float fBZ = fXZ - 2.0f * fYZ + fZZ;    float length;    if( ( fBX != 0.0f ) || ( fBY != 0.0f ) || ( fBZ != 0.0f ) )    {        // Coefficients of f(t) = c*t^2 + b*t + a.        float c = 4.0f*((fBX*fBX)+(fBY*fBY)+(fBZ*fBZ));  // c > 0 to be in this block of code        float b = 8.0f*((fAX*fBX)+(fAY*fBY)+(fAZ*fBZ));        float a = 4.0f*((fAX*fAX)+(fAY*fAY)+(fAZ*fAZ));  // a > 0 by assumption        float q = 4.0f*a*c - b*b;  // = 16*|Cross(A0,A1)| >= 0        // Antiderivative of sqrt(c*t^2 + b*t + a) is        // F(t) = (2*c*t + b)*sqrt(c*t^2 + b*t + a)/(4*c)        //   + (q/(8*c^{3/2}))*log(2*sqrt(c*(c*t^2 + b*t + a)) + 2*c*t + b)        // Integral is F(1) - F(0).        float twoCpB = 2.0f*c + b;        float sumCBA = c + b + a;        float mult0 = 0.25f/c;        float mult1 = q/(8.0f*powf(c, 1.5f));        length =            mult0*(twoCpB*sqrtf(sumCBA)-b*sqrtf(a)) +            mult1*(logf(2.0f*sqrtf(c*sumCBA)+twoCpB)-logf(2.0f*sqrtf(c*a)+b));    }    else    {        length = 2.0f*sqrt((fAX*fAX)+(fAY*fAY)+(fAZ*fAZ));    }    return length;}//--------------------------------------------------------

I'm looking at having a lot of objects on the track and as I'm using only quadratic Beziers, I think it would be more sensible to use a solution that would be faster as I don't need it to work for any kind of curve like the PDF you linked (I think) describes.

The idea is that if I can get at least one half of the Bezier's length (Start->control point or control point->end) I can subtract it from the total length as calculated above to get the length of the other half and add a bias to the Bezier offset to counteract the imbalance.

Wait! Would a straight line distance be sufficient to bias it in this manner?

Just to wrap up, I have solved the problem. I got the distance between (A, B) and (B, C) and used them to produce a bias which is multiplied by the speed of the car or the movement along the Bezier when dropping points and the global speed is now more or less constant.

Thanks for all your prompt and insightful replies.