
Cubic Splines 
Hyena_
Member #8,852
July 2007

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
Member #5,432
January 2005

From wikipedia we get the formula for a uniform cubic bspline (which I'm assuming is what you want). The code could look something like this: 1vector<vec3> UniformCubicBspline(vector<vec3> points)
2{
3 vector<vec3> output;
4 for(float t = 0; t < 1.0f; t += 0.01f)
5 {
6 for(int i = 1; i < points.size()2; ++i)
7 {
8 vec3 p;
9 p = (t*t*t) * (1 * points[i1] + 3 * points[i]  3 * points[i+1] + 1 * points[i+2]);
10 p += (t*t) * (3 * points[i1]  6 * points[i] + 3 * points[i+1]);
11 p += (t) * (3 * points[i1] + 3 * points[i+1]);
12 p += (1 * points[i1] + 4 * points[i] + 1 * points[i+1]);
13 p /= 6;
14 output.push_back(p);
15 }
16 }
17 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 bsplines 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_
Member #8,852
July 2007

One other property is that all the input points I provide must be on the trajectory. Will bsplines do that? According to Math World, they don't: http://mathworld.wolfram.com/BSpline.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:

adamk kromm
Member #5,432
January 2005

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
Member #7,827
October 2006

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 CatmullRom 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. "For in much wisdom is much grief: and he that increases knowledge increases sorrow."Ecclesiastes 1:18 
Hyena_
Member #8,852
July 2007

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
Member #7,827
October 2006

Well, yes it is. Quote: A cubic spline is a spline constructed of piecewise thirdorder 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. "For in much wisdom is much grief: and he that increases knowledge increases sorrow."Ecclesiastes 1:18 
Hyena_
Member #8,852
July 2007

oh now I get it, thank you!

