Uniform Bezier Interpolation

[svero]

I'm currently using the DeCasteljau algorithm to get back the points in a Bezier curve. The problem is that the algorithm returns non-uniform points along the curve. You'll get more points in the curved section than you will in the straight line areas etc...

I've tried measuring the returned values and capping them at uniform distances but sometimes the algorithm will return very far off points. (I'm looking for subpixel distances and the algorithm will return a point 5 pixels away) - I want to move a game object along the curve at a uniform speed though.

So I'm wondering if anyone has an alternate algorithm that's able to return uniform values (per distance) along the curve.

[luggage]

Hi

Don't know if this helps but I always use Catmull Rom interpolation. It's quick and it goes through all the control points. I'd need to check but if I remember correctly there's a D3DX function (D3DXVec3CatmullRom - there's also a Vec2 and Vec4). I think it was quite uniform, it's been a while since I've had to use it.

[svero]

Bezier's pass through the control points. What I need is not a curve that passes through it's control points. What I need is a way to interpolate the curve uniformly so that GetCurvePoint(.25) returns a curve point that is 25% of the way through the path. Using the DeCasteljau algorithm will return a point on the curve somewhere, but there's no guarantee where.

[world_creator]

honestly, this all sounds way over my head but doesnt a cubic spline or something else of that nature not go thru its control points and interpolates with a percentage value (0.0 at start and 1.0 at end)?

[FlySim]

I have done this two different ways:
- pregenerate the curve and map dist to u - good if you are going to reuse
the curve.
- iterate u by computing del dist/ del u - usually converges in a couple
of iterations.

If you get stuck, I may be able to find some old code.

-J.R.

[Jim Buck]

If you are using OpenGL, the gluNurbs stuff allows you specify different parameters for the tessellation. (You are using uniform, but I believe it's a special case of nurbs, so it should still work.)

[svero]

honestly, this all sounds way over my head but doesnt a cubic spline or something else of that nature not go thru its control points and interpolates with a percentage value (0.0 at start and 1.0 at end)?

Yes it does, but using Decasteljau there's only 2 points on a bezier that you can be sure of. And that's Bezier(1.0) and Bezier(0.0) which will give you your start and end point. The points you get in between will be somewhere on the curve but there's no guarantee where. That means that if you draw all of the curve by connecting lines fom 0.0->1.0 at some reasonably small percentage interval you'll get a nice drawing of the curve. The problem is if you want a car to drive the path of the curve at 50 pixels per minute or something like that. You cant use the curve parameter to control the speed because the points you get along the path could be 10 pixels apart or a 10th of a pixel apart.

[svero]

I have done this two different ways:
- pregenerate the curve and map dist to u - good if you are going to reuse
the curve.
- iterate u by computing del dist/ del u - usually converges in a couple
of iterations.

If you get stuck, I may be able to find some old code.

-J.R.

I am pregenerating the curve. I guess I'll just have to do a linear interpolation between points too far aprart. I'll try that next. I was hoping there was a better curve generator.

[FlySim]

I am pregenerating the curve. I guess I'll just have to do a linear interpolation between points too far aprart. I'll try that next. I was hoping there was a better curve generator.

If you generate a smooth curve of dist fract to u, then in my experience
its pretty accurate and reasonably fast - dist fract -> u -> point. I havent
seen a closed form solution for this problem.

-J.R.

[Jim Buck]

Mentioning that you're using it for a vehicle to follow a path just jarred my memory. I had to do the same thing for Twisted Metal 4. There are a couple levels where there's a vehicle going around a path around the level (a train, a helicopter, and I can't remember what else). I had the same problem as you in that the vehicle had to go at a certain speed regardless of the tessellation of the curve. I ended up using 3d Catmull-Rom splines (also mentioned earlier) to achieve what I wanted.

[Wayward]

A simple way for moving an object along a path at a constant speed:

Calculate a point (a waypoint) on the bezier curve a little ahead of your current position.
Point your vehicle at the waypoint and 'drive' it towards the way point at a constant speed.
When the vehicle gets close to the waypoint calculate another waypoint a bit further ahead.

It won't matter that bezier interpolation might give you non-equidistant waypoints - the vehicle goes at a constant speed (though this method makes it easier to add vehicle acceleration too).

[svero]

Waypoints aren't really useful because my game actually uses a distance parameter and I can't easily substitute that for something else. (or at least I dont want to because in many respects it's very elegant) It's not really a moving vehicle. I only used that to illustrate the non-uniformity problem.

Anyway.. it doesnt matter.. I've written an algorithm to cut the spline up into linearly interpolated equidistant lines which will serve just as well.

[jaggu]

Cubic spline with end points A, D and tangent points B and C is given by:

(1-t)^3 * A + 3*t^2 * (1 - t)^2 * B + 3*t^2 (1 -t) * C + t^3 * D

First generate the points on the curve with t going 0 to 1 with a step of say 0.1. A polyline running thru these points is your curve. The problem is these points are not equidistant. To make them equidistant you can do this:

Lets take two consecutive points on the curve P, Q. Find midpoint M of PQ. If PM or QM is greater than some threshold distance T subdivide recursively until its not. Insert the final midpoint M. If you do that for all points on the curve, the resulting list of points will be practically equidistant (not absolutely accurate) all separated by the threshold distance T.

You then run the train or whatever thru these points at constant rate for constant speed.

I used the precalculation method in a2b : http://www.poojyum.com/a2b/ Trains run at constant/arbitrary speed on catmull rom splines. Acceleration also supported. Take a look if u like.

This is similar to Wayward's method - he is calculating in realtime - I precalculate - his acceleration support is interesting though.

[Greenwire]

Anyway.. it doesnt matter.. I've written an algorithm to cut the spline up into linearly interpolated equidistant lines which will serve just as well.

Hi, I'm having exactly the same problem. Could you mail me this algorithm please?
Thanks.
Greenwire

[svero]

Hi, I'm having exactly the same problem. Could you mail me this algorithm please?
Thanks.
Greenwire

Well.. the thing is all completely changed now. I'm not using the spline anymore. Should be easy though.. Assuming GetSplinePoint takes a probability (0->1) In pseudocode it will be something like...

point lastpoint = (0,0);
float dist = 0;
while(dist<1)
{
dist+=(1/resolution);
dist = max(dist, 1);
currpoint = GetSplinePoint(dist);
float distance_between_points = distance(lastpoint, currpoint)
if(dist>1/num_desired_points)
{
lstSegmentpoints += currpoint;
lastpoint = currpoint;
}
}

Probably made a few mistakes writing that out, but I think the idea of what needs to be done should be clear from it.

[Chaster]

Steve, have you tried using forward differencing instead of decasteljau? I think that might do what you want...

[TwoD]

I've been searching the web for info about Bézier curves when I stumbled upun this forum.
I know it's been a while since this thread was active but I think I might be able to help.

svero: I have an algorithm which draws a continuos Bézier curve which is always 1 pixel wide, is that what you are looking for?