Tuesday, October 29, 2013

So, you want to travel along a Bezier curve

So today was a bunch more playing around with Bezier curves.

I got the curve editor basically working well, but how to actually travel along the curve?  The thing about Bezier curves is that, as you evaluate them over a specific t∈[0,1], the change in distance travelled is not directly proportional to the change in t.

Even worse, if you are joining multiple curves together, using time elapsed as the t value could give wild discontinuities in velocity as you cross the boundary between a long curve and a short curve.  It's also very difficult to control acceleration at the beginning and end of travel along the curve.

So, today has been about evaluating a Bezier curve in terms of distance travelled, rather than elapsed time.
It appears that evaluating the length of a Bezier curve is fairly expensive as there is no closed form for computing it.  You basically have to recursively divide it up into a bunch of line segments and sum up their lengths, with improved accuracy the smaller you make the segments.  The error is just the difference between the sum of the lengths between the control points vs. the length between the first and last points - that is, keep subdividing until the segment is close enough to a straight line.

This is fairly straightforward, so my current approach is:
  • The BezierPathComponent takes an associated BezierCurveComponent and breaks it down into a bunch of segments (storing length, t0 and t1 for each segment)
  • Store the sum of the length all of the segments for a total curve length
  • Set a constant target distance along curve, target (maximum) speed and acceleration value
  • Keep track of the total distance travelled and the current speed
Then, we can update the speed each frame, update the total distance travelled, and figure out which segment we are in based on the total distance travelled so far.  After figuring out which segment we are in, we can either linearly interpolate along the segment, or figure out a t value based on the stored range of the segment to compute the position directly from the Bezier curve.

That should let us move at a controlled speed along a set of curves of varying shapes and lengths.

No comments:

Post a Comment