Getting the point of a catmull rom spline after a certain distance?

Question

If I have a Catmull-Rom spline of a certain length how can I calculate its position at a certain distance? Typically to calculate the point in a catmull rom spline you input a value between 0 and 1 to get its position via proportions, how can I do this for distances? For example if my spline is 30 units long how can I get its position at distance 8?

The reason I ask is because it seems with catmull rom splines giving points in the [0,1] domain does not guarantee that it will give you the point at that distance into the spline, for example if I input 0.5 into a catmull romspline of length 30 it does not mean I'll get the position at the distance of 15 of the spline unless the spline itself is in effect a straight line..

Answer 1

The usual way is to store length of each segment and then to find out the partial length of a segment you increment t by an epsilon value and calculate the linear distance between the 2 points until you hit your answer. Obviously the smaller your epsilon the better the result you get but it gives surprisingly good results. I used this method for moving at a constant speed along a catmul-rom and you cannot see it speed up and slow down ... it DOES move at a constant speed. Obviously depending on how tight your segments are your epsilon value will need to change but, in general, you can pick a "good enough" epsilon and everything will be fine.

Findinf the answer non-iteratively is INCREDIBLY expensive (I have seen the derivation a while back and it was not pretty ;)). You will have to have a tiny epsilon value to get worse performance ...

Answer 2

Another link: Adaptive Subdivision of Bezier Curves in the Anti-Grain Geometry library
is mainly on the different problem of drawing Bezier curves on a grid of pixels with a wide brush, but see the very end.
(Added:) Antigrain also has a lovely examples/bspline.cpp in which you can move knots and vary the number of intermediate points.

Answer 3

Goz's answer is accurate - here's a related discussion about length of Bezier curves. The summary of the posters was that it's less computation (and much simpler) to do an approximation than compute the exact answer. This is applicable because you can change the basis of parametric splines, so you could convert the Catmull-Rom curve to Bezier segments.

For approximation, you're basically breaking it into primitives with simple analytical length, then summing all of the simple lengths. While most people use line segments, you do tend to have shrinkage. You can minimize the error by using small segments, but your approximation will always be less than the true length for non-linear curves.

If you need more accuracy there's a paper from jgt that discusses how to use circles as your approximation primitives, which is apparently faster/more accurate but not much harder to implement. They include a sample C implementation.