|
|
|
This thread is locked; no one can reply to it.
|
| 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 b-spline (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[i-1] + 3 * points[i] - 3 * points[i+1] + 1 * points[i+2]);
10 p += (t*t) * (3 * points[i-1] - 6 * points[i] + 3 * points[i+1]);
11 p += (t) * (-3 * points[i-1] + 3 * points[i+1]);
12 p += (1 * points[i-1] + 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 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_
Member #8,852
July 2007
|
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:
|
|
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 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. "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 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. "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!
|
|
|
