🔒 Locked

Bezier curve and constant speeds

Started by Rajveer Aug 19, 2009 at 1:15 PM 2 replies 10.4k views

Original Post

Aug 19, 2009 at 1:15 PM

I'm using a cubic Bezier curve for my AI routines within my racing game. Currently I estimate the nearest position of the player along a spline by calculating the closest position along the line segment of the spline's 2 knots, getting time t, and plugging it into the cubic Bezier curve equation. The problem is that speed isn't constant along the Bezier curve, so for curvy parts I've got the correct closest point on the line segment but not on the actual curve. I've read that Catmull-Rom splines have constant speed if you parameterise for arc length, however the whole reason I'm using Bezier curves is because I'm using 3ds Max splines to create levels (therefore the spline maps perfectly to the level), and since curved splines in 3ds Max are Bezier splines I export them in that format. If I have to somehow use Catmull-Rom, are there any algorithms for converting between these 2 splines? Any advice you guys can give me for constant speed?

Arikwex

Aug 19, 2009 at 2:53 PM

Let's examine a 2D racetrack
You said the racetrack is with a bezier curve.
Imagine (sorry about this terrible drawing (haha):

......*...............................
....**.**.............****[3]***......
[0]*.....**[1]*..*[2]*..........***[4]
...............**.....................

Where the values inside the nodes represent the "t" parameter values.
I'm assuming that your Bezier function, S(t), can be expanded as X(t)*i + Y(t)*j.

The distance between those nodes is clearly non-constant and thus you have a problem.
The arclength between any two node n and n+1 is given as:

dS = sqrt( (dX/dt)^2 + (dY/dt)^2 ) * dt

Arclength = AL(n) = Integral( sqrt((dX/dt)^2 + (dY/dt)^2 )) * dt, from t = t(n)...t(n+1) )

Note that t(0) = 0, t(1) = 1, t(2) = 2, etc... (based on my drawing above).
Now that you can calculate the arclength in between any two nodes of the bezier curve,
you can force it to have a "normalized velocity" by parameterizing the originial track with the nodal (t) values:

[0],[AL(0)],[AL(0)+AL(1)],[AL(0)+AL(1)+AL(2)], etc...

By doing this, there is a specific amount of path traveled per parameter (t) increment.
This of course means that your "velocity" vector along the curve will remain constant.
Does this help? :D

Maze Master

Aug 19, 2009 at 11:33 PM

Perhaps this pdf will be of use?
http://www.geometrictools.com/Documentation/MovingAlongCurveSpecifiedSpeed.pdf

Rajveer

Aug 23, 2009 at 4:25 PM

Thanks for the info guys. I like the ASCII art Arikwex :D Although I'm not worried about the spline segments having the same length as I'm not moving an object along the spline and don't need it to be at a constant speed between segments, rather I'm finding the closest position on the spline to the player, so I'm more concerned with the increase and decrease of acceleration within a spline segment itself.

So from what I understand the analytical approach will not always work and a numerical approach is favorable (that integral doesn't look nice, maybe because I haven't integrated for 5 years!) One method I've read is to precalculate a look-up table for each segment and map the time variable t to the distance along a spline segment, approximating length by using tiny increments of t and summing the length of the segments. Any other methods you guys use?

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.