approximating a curve through several points

[svero]

So say i have 3 points... its easy to draw lines through those points and make a V. How to approximate the 3 points with a curve without specifying a derivitive at each point? Ie.. draw an elbow. And specifically generalize that to several points. Ie.. draw a smooth curve through a set of points with ONLY the points themselves as data. (and no direction arrows)

Any standard way to do that?

- S

[ManuelFLara]

Look at the first function shown here (http://www.phelios.com/ptk/kspline.html). I guess that's what you want. Maybe Patrice could share his code with you, but at least you now know it's possible :)

[MadSage]

Look up quadratic b-splines on google:

px = (1-t)*(1-t)*Ax + 2*t*(1-t)*Bx + t*t*Cx
py = (1-t)*(1-t)*Ay + 2*t*(1-t)*By + t*t*Cy

Where t is between 0 and 1, and A, B and C are the three points defining your curve.

[Fabio]

So say i have 3 points... its easy to draw lines through those points and make a V. How to approximate the 3 points with a curve without specifying a derivitive at each point? Ie.. draw an elbow. And specifically generalize that to several points. Ie.. draw a smooth curve through a set of points with ONLY the points themselves as data. (and no direction arrows)

Any standard way to do that?

- SIMHO your best friend is Catmull-Rom interpolation.

[mr n00b]

The answer is cubic interpolation, given four points on a curve: v0, v1, v2 and v3 the code to interpolate between v1 and v2 looks like this:

Point cubic_interpolation(const Point& v0, const Point& v1, const Point& v2, const Point& v3, float t)
{
Point p = (v3 - v2) - (v0 - v1);
Point q = (v0 - v1) - p;
Point r = v2 - v0;
Point s = v1;

return ((p * t + q) * t + r) * t + s;
}

The t value is a parametric value in the range [0, 1] that interpolates between v1 and v2. For the start and end interval of your line segments you'll have to insert two "virtual" control points. The position of these "virtual" control points will determine the curvature of the start and end of your curve. If you're uncertain on how to position the two virtual control points you can just duplicate the first and last control point.

/mr n00b

[ggambett]

A spline if you want global control, piecewise curves if you want local control. In general, pick a series of weighting functions that add up to 1.0 at all points in the curve (and are nonnegative), if you want the curve to pass through the points make sure that at one of the point only the weighting function associated to that point is 1.0 and the rest are 0.0.

Easiest example of this is your "V". If you parameterize the curve with a value t in [0,1], then [0,0.5] is the first "arm" of the V (P0 to P1) and (0.5,1] is the second arm (P1 to P2). The blending functions in this case are F0 = 2*(0.5-t) if t < 0.5, 0.0 otherwise; F1 = 2*t if t < 0.5, 2*(t-0.5) - 1 otherwise; and F2 = 0.0 if t < 0.5, or 2*(t - 0.5) otherwise. Because weights are nonzero only in the curve points between two points, you get straight lines. If you get creative and assign other weights to the other points, these will "pull" the curve in their direction (because you're doing a weighted average of coordinates, after all) and you get a curve curve.

There are many pre-made curves too, such as splines, but these are all generalizations of the above concept.

[Jim Buck]

+1 for Catmull-Rom. It calculates derivatives from the existing points.

[svero]

Catmull-Rom seems exactly right. Thanks.

- S

[gosub]

One of the problems you might encounter with Catmull-Rom is that the speed of your object along the path can change non-linearly along the line. One way to fix this is to split each segment in several pieces and measure the distance/velocity.

-Jeremy

[svero]

Yeah I had the same problem with beziers making Beetle Bomp.

[Fabio]

One of the problems you might encounter with Catmull-Rom is that the speed of your object along the path can change non-linearly along the line. One way to fix this is to split each segment in several pieces and measure the distance/velocity.

-JeremyThis is not a Catmull-Rom specific problem, but a problem of all the interpolators of this (vast) class. The way you suggested to fix it is a very valid workaround to this problem.

[Jim Buck]

Splitting it up is exactly what I did when using catmull-rom for Twisted Metal 4.