deBoor:

http://en.wikipedia.org/wiki/De_Boor's_algorithm

http://www.idav.ucdavis.edu/education/CAGDNotes/Deboor-Cox-Calculation.pdf

^^

The second link is better at explaining, the first gives you a general idea.

Code:

Code:

struct pt {
float x;
float y;
};
typedef struct pt Point;
void generateRegularBSpline(const int n, Point* controlPts, const int d, Point* splinePts, int numSplinePts)
{
float*u = malloc(sizeof(float)*(n+d));
int i;
for(i=0; i<n+d; i++)
{
u[i]=i;
}
float begin = u[d];
float end = u[n];
float x;
for(i=0; i<numSplinePts; i++)
{
x = (begin + i*(end-begin)/numSplinePts);
splinePts[i] = coxDeBoor(u, controlPts, x, n, d);
}
free(u);
}
Point coxDeBoor(float* u, Point* pts, const float x, const int n, int d)
{
// u is the knot vector
// pts contains the control points
// x is the parameter we're calculating for
// n is the number of control points
// d is the degree
int i, l, j = 0;
// find the knot span that x is in
for(i=d-1; i<=n+1; i++)
{
if (x>=u[i] && x<u[i+1]) {
l = i;
break;
}
}
float tau, X, Y;
// initialize our points
Point** P = (Point**)malloc(sizeof(Point*)*(d+1));
for(i=0; i<=d; i++)
{
P[i] = (Point*)malloc(sizeof(Point)*(i+1));
P[i][0] = pts[l-d+i];
for(int k = 1; k < i+1; k++)
{
P[i][k].x = 0;
P[i][k].y = 0;
}
}
// these variables are used to spread out the equations (for debugging purposes)
Point old, new;
float u1, u2;
//int ii;
// loop through the levels
for(i=1; i<=d; i++)
{
// loop through the affected points
for(j=i; j<=d; j++)
{
// the calculations
u1 = u[j+l-d];
u2 = u[j+l-i+1];
tau = (x-u1)/(u2-u1);
old = P[j-1][i-1];
new = P[j][i-1];
X = (1-tau)*old.x + tau*new.x;
Y = (1-tau)*old.y + tau*new.y;
P[j][i].x = X;
P[j][i].y = Y;
}
}
Point returnPoint = P[d][d];
for(i=0; i<=d; i++)
{
free(P[i]);
}
free(P);
// return the last value
return returnPoint;
}

The function you call is generateRegularBSpline. It can be modified it you want to change the knot vector.

(const int n, Point* controlPts, const int d, Point* splinePts, int numSplinePts)

n: number of control points

controlPts: pointer to the first control point

d: degree of the spline

splinePts: pointer to where you want the spline points to be output (its awkward, I know, but you catch the drift)

numSplinePts: number of spline points you want to calculate (and have room for in splinePts)