0
101 Sep 30, 2005 at 14:53

Hello,

I’ve a big problem with my BSpline implementation that I couln’t solve for days or weeks! Perhaps you can help me with some hints.

The problem is:

given:

• BSpline with degree = n = 3.

• M data points element of R³, c_0, c_1, …, c_M-1, with parameter values x_0, x_1, …, x_M-1

I look for:

• m spline controling break points, d_0, d_1, …, d_m-1, with a node vector t_0, t_1, …, t_m+n, (n is the degree of the BSpline). Due to the degree is 3 there must be at least 4 break points.

with M >> m that means I want to approximate the data points with a BSpline. I want to use a least square approach:

 Ad - c ² should be minimized.

A is a Mxm matrix row i and column j consists of

N(i, 3, x_i)

with the common BSpline base function definition:

N(i, k, u) = (u-t_i)/(t_i+k - t_i) * N(i, k-1, u) + (t_i+k+1-u)/(t_i+k+1 - t_i+1) * N(i+1, k-1, u)

N(i, 0, u) = { 1 if t_i <= u < t_i+1,
{ 0 otherwise

My problem is how to find the break points d?

It’s no problem to solve || Ad - c ||². But I think that my problem is how to find the correct x_i and t_j!

Is it necessary that x_M-1 < t_m+n and ? How to achieve this condition?

I tried to define x_i = t_i = i for i=0..M-1, but that doesn’t work.

Then I tried to extend the t_is and define t_0 = t_1 = t_2 = 0 and t_M = t_M+1 = t_M+2 = M, but that doesn’t work, too.

Then I tried to to define x_i = i and t_i = 1/3 ( x_i-3 + x_i-2 + x_i-1). For an example what I’ve done:

Assume we’ve

5 data points P_i = (1.0; i; 1.0) i=0..4

Is this a possible knot vector (this is a uniform knots vector)?

T=[0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0]

What about the multiplicity? Is this “more” correct:

T=[0.0, 0.0, 0.0, 3.0, 4.0, 5.0, 6.0, 6.0, 6.0]

(Both didn’t work in my case)

and A (with the first knot vector) =

N0,3=0.0 N1,3=0.0 N2,3=0.0 N3,3=0.0 N4,3=0.0
N0,3=0.5 N1,3=0.0 N2,3=0.0 N3,3=0.0 N4,3=0.0
N0,3=0.5 N1,3=0.5 N2,3=0.0 N3,3=0.0 N4,3=0.0
N0,3=0.0 N1,3=0.5 N2,3=0.5 N3,3=0.0 N4,3=0.0
N0,3=0.0 N1,3=0.0 N2,3=0.5 N3,3=0.5 N4,3=0.0

or with the second knot vector:

N0,3=1.0 N1,3=0.0 N2,3=0.0 N3,3=0.0 N4,3=0.0
N0,3=1.0 N1,3=0.0 N2,3=0.0 N3,3=0.0 N4,3=0.0
N0,3=1.0 N1,3=0.0 N2,3=0.0 N3,3=0.0 N4,3=0.0
N0,3=0.0 N1,3=0.25 N2,3=0.75 N3,3=0.0 N4,3=0.0
N0,3=0.0 N1,3=0.0 N2,3=0.5 N3,3=0.5 N4,3=0.0

(Although the Schoenberg-Whitney (t_i <= x_i < t_i+n+1) condition is fulfilled it isn’t possible to invert both A matrices!?).