Linear Curved Trajectories

OpenGL OpenGL: Advanced Coding
1

Hi,

I need to be able to move many objects from point a to b avoiding fixed objects on route.

Initially I used routines that determined the objects proximity to those of the fixed objects … it worked but the result looked odd. What I needed was a predetermined curved trajectory specified by a start point, end point and one or two control points … bezier sounded like the solution and the trajectories now look much more acceptable … but incrementing the object’s position is non-linear with respect to the bezier curve. Does anyone have any suggestions of another formula that I could use or any idea how to retrieve linearly spaced segments of a bezier curve ?

Thanks

Andrew

2

If I get you right you want to move your object along a Bezier curve with constant linear velocity?

I’ve done this, it’s fairly straightforward, and doesn’t take too much maths. It goes something like this:

Your Bezier curve is represented by a parametric equation (I’ll call the parameter ‘t’).

The problem is, as you’ve found out, that the integrated path length (call is S(t)) along the curve as a function of t is not a straight-line, so your object appears to change speed. To solve this you need to invent a new parametric variable, call it ‘q’, and map this q on to t in such a way that the integrated path length S(q) is a straight-line.

To do this you first need to calculate S(t). Just calculate points along your Bezier curve at small intervals in the parametric variable (t=0.0, 0.01, 0.02, …), and work out the linear (straight-line) distance between adjacent points. Keeping a running total of these will give you a list of t, and S(t). (Incidentally this will also give you the total length of the Bezier curve, which can be useful if you have a trajectory represented piece-wise by Bezier curves).

To achieve constant linear velocity motion along the curve, you use this pre-calculated relation between t and S(t) to perform your mapping of q onto t.

If you are moving at constant velocity, V, and you’ve been moving for a time, q, then you’ve moved a distance q * V. Simply search along your pre-calculated list of (t, S(t)) to work out the value of t you need to use to plug in to your Bezier equations. You can interpolate between your adjacent samples of (t, S(t)) to get better accuracy.

Typically when I’ve done this I’ve used about 100 samples along the curve. It’s pretty quick, though my applications have never been real-time so I wouldn’t like to claim that.

There may be an analytical way to calculate S(t) directly from the parametric representation of the Bezier curve. I spent a few days trying to work it out when I was a kid (computers were slow back then), but never found a solution due to my dodgy grasp on maths. The numerical scheme I’ve outlined above works, and it’s quite simple, so I use that…

I think that in principle this technique should work for any parametric curve, not just Bezier curves.

Sorry this has been so long-winded, I hope I’ve explained myself clearly and correctly!

3

Hi nutball?

Many thanks for your clear and detailed response … yes, I’d concluded that your solution is probably the only way to actually achieve this linearity from a bezier curve … by definition, I understand that there is no direct solution to provide linear velocity nor a direct way to determine the actual length of the bezier …

Actually, by choosing the two control points carefully, I’ve found that the motion looks fairly good … due to the proximity of the control points to the start and end points, I get an intial period of what looks like acceleration followed by linear velocity and then deceleration … and it looks OK …

Again many thanks for your help …

Andrew

4

I like this problem. I haven’t finished it yet, but I am working on it.

I am in the 2-d case.

You have parametric expressions:

x=f(t)
y=g(t)

That describe your path.

What you want is a constant speed, say C; in other words, you want:

dot (derivative with respect to t)

sqrt(xdot^2 + ydot^2) (the speed) = C.

Well,
xdot = f’(t), ydot = g’(t)

Suppose you can introduce a function s(t) that does this for you and that you follow the path by:

x=f[s(t)]
y=g[s(t)]

Now by the chain rule:

xdot = f’[s(t)]*s’(t)
ydot = g’[s(t)]*s’(t)

(s’(t) == sdot)

So you want

xdot^2+ydot^2 = (f’[s(t)]*sdot)^2 + (g’[s(t)]*sdot)^2 to be equal to C^2

This gives a differential equation for the function s(t):

s’(t)^2 = sdot^2 = C^2/(f’(s)^2 + g’(s)^2)

This is as far as I have gotten. What are your f and g? If you give me your f and g I can solve this by separation of variables rather quickly, I believe. I will try to look for the bezier parameterization too…

This result is the same as saying:

Integral(sqrt(f’(s)^2 + g’(s)^2))dt = line length from 0 to (f(s(t)), g(s(t)))= Speed*time

In other words, the line integral for 0 to now (i.e. the distance travelled) is your speed*time, which means you have been going a constant speed.

[This message has been edited by nickels (edited 06-19-2002).]

5

Ok, at last, here is the algorithm:

You have x = f(t), y = g(t) as above.

For each section of your bezier curve (each f,g are different, and you must calculate f’,g’–of course, each f and g are so similar you can calc them by the same function with parameters):

ticks = number of points per bezier curve to draw
for (j = 0; j < num beziers;j++)
{
s = 0
L = Length of curve j(Use nutball’s algorithm)
t= 0
tstep = L / (Velocity * ticks)
for (i = 0; i < ticks; i++)
{
sdot = Velocity /(f_j’(s)^2 + g_j’(s)^2)
s += sdot*tstep
t += tstep (does nothing but shows t; 0->L/V)
draw_ship_at(f_j(s), g_j(s))

}
}

This relies on the fact s goes from 0 to 1 as t goes from 0 to L/V (We choose s[0] = 0). This is true since V*time = Distance; replacing Distance with the whole lenght (when we are done), time = Distance/Velocity.

This eliminates the loop in nutball’s algorithm, but you have to get the derivatives of your parameterization.
Unfortunately you still have to calculate the length since your step in t depends on it.

You could avoid calculating the lenght and choose choose an arbitrary time step. Then exit the inner loop when s == 1. After some tuning this might be acceptable.

[This message has been edited by nickels (edited 06-19-2002).]

6

Originally posted by nickels:
[b]

Integral(sqrt(f’(s)^2 + g’(s)^2))dt = line length from 0 to (f(s(t)), g(s(t)))= Speed*time

[/b]

Yes, this is the conclusion I reached when trying to obtain the analytical solution. My maths isn’t that hot, but I think that’s quite a challenging integral to perform analytically.

7

Well, it is pretty good to get that far. It may be hard to solve analytically, because s(t) may not, in general, be an analytic function since the diff-eq is non-linear. However, the diff-eq for s(t) gives a pretty good numerica way to proceed.

Cheers

8

Thanks for your kind support - I seemed to have initiated lots of thought and your maths abilities are outstripping mine …

Anyway, it’s helped a lot and I now have an workable solution to what I required … whilst maybe not a ‘true’ solution !

Kind regards

Andrew

9

Another solution to find the length is the one I use. Rather than breaking the spline into segments (0, 0.1, 0.2, …), I repeatedly divide the spline in half. For each half, I calculate the straight line distance from end to end. If this distance is greater than a set threshold, I recursively process that half. When I have calculated distances for both halves, add them together and you have the total spline length.

This method has the advantage that it always has the same level of precision for any size spline. The downside is that the performance varies depending on the size of the spline and what you pick as your threshhold.