Duke Leto

Aug 2, 2010, 12:29 PM

I'm trying to implement de Boor's algorithm for B splines, but I'm having some issues.

The rest of the code contains the control points, and it creates a uniform integer knot vector {0, 1, 2, 3, .... } It goes through the knots and calculates the point on the spline for that point. After that, it creates a .png file using the results from the de Boor algorithm.

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);

Point testPt;

for(i=0; i<d; i++)

{

P[i] = malloc(sizeof(Point)*i);

P[i][0] = testPt;

}

// these variables are used to spread out the equations (for debugging purposes)

Point old, new;

float u1, u2;

// 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];

u2 = u[j+d-i];

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;

}

}

// return the last value

return P[d-1][d-1];

}

After a couple of days of debugging, I'm pretty sure the problem is in here. Here are some .png files of the output.

The control points:

http://thebluekoala.com/images/ctrlpoints.png

The output:

http://thebluekoala.com/images/splinetest.png

As you can see, there are skips in the spline for some reason, and it goes past the control points, instead of staying well inside. I've also determined that the jumps happen when the x value passes knot values. This leads me to believe that the problem is in the calculation of tau, but I'm not sure. Any help is appreciated!!

The rest of the code contains the control points, and it creates a uniform integer knot vector {0, 1, 2, 3, .... } It goes through the knots and calculates the point on the spline for that point. After that, it creates a .png file using the results from the de Boor algorithm.

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);

Point testPt;

for(i=0; i<d; i++)

{

P[i] = malloc(sizeof(Point)*i);

P[i][0] = testPt;

}

// these variables are used to spread out the equations (for debugging purposes)

Point old, new;

float u1, u2;

// 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];

u2 = u[j+d-i];

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;

}

}

// return the last value

return P[d-1][d-1];

}

After a couple of days of debugging, I'm pretty sure the problem is in here. Here are some .png files of the output.

The control points:

http://thebluekoala.com/images/ctrlpoints.png

The output:

http://thebluekoala.com/images/splinetest.png

As you can see, there are skips in the spline for some reason, and it goes past the control points, instead of staying well inside. I've also determined that the jumps happen when the x value passes knot values. This leads me to believe that the problem is in the calculation of tau, but I'm not sure. Any help is appreciated!!