Topic: Calculating points along a curve

Objective: Get a lot of coordinates along a curve, ideally, at a customizable interval (ie every 3px, 5px, 10px, etc along the line).

I'm not quite sure how the best way is to do this, but here's my progression of thought:
- Establish a sequence of points that the line passes through (no square corners, so the line isn't directly from point to point).
- C# allows this via: Graphics.DrawCurve(Pen pen, Point[] points, int tension).
- This will give me the control over the shape of the line (as much as I need anyways).

The problem I have now is getting the coordinates at a much finer detail than the points I put down. I can define the line I want in as few as 5-6 points in some cases, however, I'd like to have 20-30 times that many points available (the output will go into another app that "follows" the detailed path).

Anybody have any ideas? Whatever solution I end up using doesn't need to be tied to any particular language, I just used C# above because that's what I have in front of me right now and that seemed like a fairly straightforward way of stating the problem...

Many many thanks to anyone who can enlighten me a little,
LF

--

Any sufficiently advanced bug is indistinguishable from a feature.

A curve described by a list of points is called a Spline. There are a lot of ways to create a spline from a list of points, the simplest being a straight line from each point to the next. More complicated spline representations can be smooth.

My personal favorite is the "natural cubic spline." As with most splines, you represent the curve as a function on a variable t. As t goes from 0 to 1, the function f(t) goes from the first point to the second point. As t goes higher, it goes to each successive point. To make this work in 2 or 3 dimensions, we actually have a separate function for each dimension.

In reality, we use a separate function for each segment. To enforce smoothness at each point, we require that the first and second derivatives of these functions match at their endpoints.

The details are described here: http://mathworld.wolfram.com/CubicSpline.html

Actually implementing this is pretty difficult, because once you create the matrix from the points you need to solve it. (Not impossible to implement, just time consuming.) It's best if you can find an external library that does all this for you. Once you have the function, you can get as many points from it as you want by plugging in different values of t.

The POV-Ray scripting language can do what you want, and it's capable of outputting CSV files, if that's useful to you.

All the splines/bezier/catmull-rom/Hermite/youNameIt curves I've seen and implemented usually ended up with a single cubic equation i.e:

f(t) = a*t^3+b*t^2+c*t+d

which is straight forward to implement and evaluate for each coordinate ( x, y, z ... )



(Edited by poi on 12-05-2006 10:32)

If I understand what your asking, I would say that you will find it easiest to implement a parabolic blending curve.

The advantage of a parabolic blending curve over a spline is that the math is a lot simpler and you are guaranteed to get a smooth curve whereas some situations with Cubic Spline/B-Spline/Beta-Spline/Catmull-Rom/Hermite/... can end up with discontinuities and non-linear third derivatives. The disadvantage is that the parabolic blending may not track your original points as closely as you would like.

You might also look at implementing a Bezier curve. It's a little harder (mathematically) than parabolic blending, but more commonly used so it might be easier to find a good implementation.

.



-- not necessarily stoned... just beautiful.

Thank you three.

I ended up taking an algorithm for a Bezier curve and modifying it some. I don't have quite the control over the precise shape of my curve that I'd like right now, but that has more to do with me, not the curve or the algorithm. And what I'm able to get is plenty sufficient for testing right now.

Muchas gracias again.

--

Any sufficiently advanced bug is indistinguishable from a feature.

If you haven't already, make sure to check Paul Bourke : Interpolation methods.



(Edited by poi on 12-05-2006 23:49)

poi: if you don't have a separate equation for each dimension, then you'll get the same values for x, y, and z.

I mean, yes, each function has the same *form* (the form you mentioned), but the coefficients are different.

Yep of course the actual f(t) is different for each dimension. Sorry the term 'single', in my first post, was probably confusing.