Cubic Splines

Hyena_

Can anyone suggest me some small and simple C or C++ implementation for calculating cubic splines? It would be best if it could handle circles (end point and start point being the same).

adamk kromm

From wikipedia we get the formula for a uniform cubic b-spline (which I'm assuming is what you want).

The code could look something like this:

#SelectExpand
  1vector<vec3> UniformCubicBspline(vector<vec3> points)
  2{
  vector<vec3> output;
  for(float t = 0; t < 1.0f; t += 0.01f)
  {    
      for(int i = 1; i < points.size()-2; ++i)
      {
          vec3 p;
          p = (t*t*t) * (-1 * points[i-1] + 3 * points[i] - 3 * points[i+1] + 1 * points[i+2]);
          p += (t*t) * (3 * points[i-1] - 6 * points[i] + 3 * points[i+1]);
          p += (t) * (-3 * points[i-1] + 3 * points[i+1]);
          p += (1 * points[i-1] + 4 * points[i] + 1 * points[i+1]);
          p /= 6;
          output.push_back(p);
      }
  }
  return output;
 18}

This is untested code. It may or may not work. It does however give a general idea on how to do it. I'm not sure if you know this or not, but uniform cubic b-splines can't really make a perfect circle. You would need NURBS for that. If you don't mind it not being a perfect circle you can just add the first couple points to the end of the list after the last point and that will connect the curve.

Hyena_

One other property is that all the input points I provide must be on the trajectory. Will b-splines do that?

According to Math World, they don't: http://mathworld.wolfram.com/B-Spline.html

While this is cubic spline: http://mathworld.wolfram.com/CubicSpline.html

Any ideas how to implement the latter one?

This is what I mean by drawing a circle:
"If the curve is instead closed, the system becomes ..."

adamk kromm

If you want the curve to pass through the points then you probably want to use a spline that uses interpolation rather than approximation (bspline).

A quick google on interpolation helped me find this

it has a bunch of different interpolation schemes: one of which is cubic.

SiegeLord

Err... A cubic spline interpolates between two points. If you want more than two points, you stick a bunch of cubic splines together. Something like Catmull-Rom Spline. Just because every second point is a control point doesn't mean that it doesn't go through all your datapoints... it means you have to come up with additional points for algorithm to work.

Hyena_

thanks siegeLord, it gets me closer to what I seek. Although, based on mathWorld (http://mathworld.wolfram.com/CubicSpline.html) I really thought that cubic splines were what I needed.

SiegeLord

Well, yes it is.

Quote:

A cubic spline is a spline constructed of piecewise third-order polynomials which pass through a set of m control points.

Which means that you have a set of individual cubic splines put together end to end. You make sure it looks nice by picking control points like in the article I showed you.

Basically your function may sort of look like this:

// Interpolates between p1 and p2, such that the line is
// parallel to vectors m1 and m2 at p1 and p2 respectively
vector interpolate(vector p1, vector p2, vector m1, vector m2)
{
    return TheUsualBezierInterpolation(p1, p1 + m1 / 3, p2 - m1 / 3, p2);
}

You compute m1 and m2 using whatever method from the article I linked to you choose (but ultimately they depend on the 3 points that define each angle). TheUsualBezierInterpolation is just what it says. There's a version of it on the internet for sure. Allegro5 has it in the al_calculate_spline function.

Hyena_

oh now I get it, thank you!

Thread #612242. Printed from Allegro.cc