Constant speed following bezier curve
Posted 08 September 2005 - 03:20 PM
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.
Posted 08 September 2005 - 10:19 PM
The algorithm you chosed should work fine, though. Are you subdividing the spline enough?
Posted 09 September 2005 - 11:45 AM
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.
Posted 09 September 2005 - 03:43 PM
Shure, but there is no advantage. If the section is small enough, a line will aproximate it just as fine.
Posted 09 September 2005 - 03:48 PM
Posted 09 September 2005 - 04:08 PM
Posted 09 September 2005 - 06:07 PM
m_fMoveFrame += m_fMoveSpeed * delta; D3DXVec3CatmullRom(&m_Position, &m_VSplineControl, &m_VSplineControl, &m_VSplineControl, &m_VSplineControl, m_fMoveFrame);
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 ;) )
Posted 09 September 2005 - 09:02 PM
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.
Posted 08 October 2005 - 11:17 AM
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.
Posted 18 October 2005 - 06:11 PM
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."
Posted 19 October 2005 - 10:17 AM
Polar Sleuth said:
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:
1 user(s) are reading this topic
0 members, 1 guests, 0 anonymous users