math & physics
mark at September 8th, 2005 11:20 — #1
I'm writing a path system that objects (and cameras) follow through a scene, using DeCasteljou's algorithm to find points (for 0 \< t \< 1) along a bezier curve. I would like the objects to follow the curve at a constant speed. However, the algorithm doesn't allow me to do this easily or accurately.
The 't' parameter takes no account of distance travelled along the curve. So that 0.5 may not be half way along the curve and the distance between 0.4 and 0.5, may not equal the distance between 0.5 and 0.6. If I interpolate object positions this way, those objects would not have a constant speed.
I could get (roughly) constant speeds by dividing the curve into lines and tallying their lengths until the total distance travelled is approximately bezier.length * t. But this is slow, ugly and less robust.
Is there a better way to get constant speed, or a better compromise I've overlooked? Any thoughts much appreciated. Thanks.
geon at September 8th, 2005 18:19 — #2
There is no way to calculate the length of a bezier segment in a simple formula.
The algorithm you chosed should work fine, though. Are you subdividing the spline enough?
einheri at September 9th, 2005 07:45 — #3
Well, I've not done a lot of work with bezier curves before, but I've worked with many kinds of curves as part of my maths.
As such, my first suggestion would be, like you say, to approximate the curve as a series of lines. This shouldn't really be all too slow or ugly, though, as I assume your path system is treating the curve as a series of points and lines, anyway. Providing your t values are close together, you should be able to get the effect you desire; if I were you I'd simply keep track of the 'distance so far' for each point as it is generated; just add on the distance from the last point to the first. If you know the approximate distance at each point (node, you might say?), then you'll be able to get your constant speed.... but I'm sure that's what you had in mind, anyway.
The other way I'd think about doing it is purely out of mathematical curiosity. Surely if you have three or four points sequential near points (I forget the required number), then you could approximate that section of the curve with a parabola. I assume that the problem of finding the length of a stretch of bezier curve is problematic, but this is not the case for the parabola, so for near points on the curve it might be a useful approximation. But, like I say, that is just for curiosity, and is likely to be highly inefficient.
geon at September 9th, 2005 11:43 — #4
you could approximate that section of the curve with a parabola.
Shure, but there is no advantage. If the section is small enough, a line will aproximate it just as fine.
einheri at September 9th, 2005 11:48 — #5
Like I say, I'd look at it purely out of curiosity. Either way, it'll most likely get a more accurate approximation per calculated point than you'd get from using a line; it just depends whether you need that extra accuracy or not. Most people won't.
mark at September 9th, 2005 12:08 — #6
Yeah, looks like I'll be taking the incremental approximation with lines. I was kind of hoping there would be some tidy algorithm I could plug in and have this work, but it looks as though I'll have to bite the bullet. Many thanks for all the input.
bignobody at September 9th, 2005 14:07 — #7
This may not be helpful for you (and I may not even be understanding the problem correctly) as I get the impression you're writing all this yourself, but I achieve this in my game using Catmull Rom splines through the D3DX library:
m_fMoveFrame += m_fMoveSpeed * delta;
Simple enough, and my objects/camera follow the spline at a constant speed.
Sorry if this isn't helpful, but if I was better at math I wouldn't be relying on someone else's math libraries
(edit: constant speed, assuming the delta is always constant )
mark at September 9th, 2005 17:02 — #8
The poster here is having the same problem, only he's explained it more eloquently than I did. I'm beginning to think that I need to use Catmull Rom splines too. Most of the path interpolation examples I've found use them.
nils_pipenbrinck at October 8th, 2005 07:17 — #9
I had to solve the same problem two days ago, and my solution - also it's just an approximation - works pretty good.
For each bezier curve I build a function that maps length to t (interplant).
First I sample the curve in 1000 steps to get the entire length and keep the sampled data. Then I normalize the data by dividing by the segment length. The data gets inverted in a way that I have a lookup table that maps length to t.
Then I fit a bezier to the data. I do least sqare error fitting (pretty easy) and I can throw away two of the 4 control points since the curve starts always at 0 and ends at 1. So in the end I have to store 3 additional floats per bezier: The segment length and the two control points of the length-to-t speed compensation bezier.
For a lookup I just have to normalize the "position" along the segment, do a bezier interpolation to get the interpolant and then pass this value to the 3d bezier.
The results are stunning! I tested it with all kinds of worst case bezier curves by moving an object along the path at constant speed, and I can't see *any* acceleration effects anymore, also I measured the error and it's still far from perfect. there are speed differences here and there, but there aren't any velocity leaps and the acceleration effects are so weak you won't notice them ever.
I do all the calculations during a data conversion step, so the time it takes to sample and approximate the bezier does not matter for the game. It just costs 3 floats per key (segment length + two tangents for speed compensation). The computational costs are neglible.. Just a hand full of muls and adds.
reedbeta at October 8th, 2005 14:03 — #10
That's a very good idea. Nice work Nils.
polar_sleuth at October 18th, 2005 14:11 — #11
The difference between Catmull-Rom and Beizer are in how the approximations are calculated. It is also why you see speed differences in your Beizer approximations.
Beizer splines are calculated by using a point that is measured from the end points on a straight line. The effect of the anchor points are then determined on that point and adjust it accordingly. But the point is always on the straight line distance. Nils "solution" is to flood the line with points and try to get their distances to equal, but it is still an equality based on the distance between the end points along the straight line, which is why he still gets the effects he still does. However this inequality has been used for CGI cameras and CGI animation for years to great effect!
Catmull-Rom is instead a surface subdivision algorithm. So it is concerned with the half-way point on the curve - regardless of its distance from an end point. This creates a very different camera and animation effect which is "undesirable" for TV and film. However, the Catmull-Rom spline surfaces are used as a polygon reduction strategy.
Having only used quaternion math for in game cameras, I will offer no advice on which one to use - except to say, "do what looks best."
corey at October 18th, 2005 15:08 — #12
In other words, Catmull-Rom splines always go through the control points.
nils_pipenbrinck at October 19th, 2005 06:17 — #13
Catmull-Rom is instead a surface subdivision algorithm.
Hate to correct you, but Catmull-Rom have only recently (couple of years) been used as a basis for patch/surface subdivision. The "Catmull-Rom"-curve itself is just one polynomial curve, not unlike bezier, hermites or whatnot other curves.
I've written something up about these curves some years ago: