No replies to this topic

[philcyb]

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

N[0,3](t[0]=0.0)=0.0 N[1,3](t[0]=0.0)=0.0 N[2,3](t[0]=0.0)=0.0 N[3,3](t[0]=0.0)=0.0 N[4,3](t[0]=0.0)=0.0
N[0,3](t[1]=1.0)=0.5 N[1,3](t[1]=1.0)=0.0 N[2,3](t[1]=1.0)=0.0 N[3,3](t[1]=1.0)=0.0 N[4,3](t[1]=1.0)=0.0
N[0,3](t[2]=2.0)=0.5 N[1,3](t[2]=2.0)=0.5 N[2,3](t[2]=2.0)=0.0 N[3,3](t[2]=2.0)=0.0 N[4,3](t[2]=2.0)=0.0
N[0,3](t[3]=3.0)=0.0 N[1,3](t[3]=3.0)=0.5 N[2,3](t[3]=3.0)=0.5 N[3,3](t[3]=3.0)=0.0 N[4,3](t[3]=3.0)=0.0
N[0,3](t[4]=4.0)=0.0 N[1,3](t[4]=4.0)=0.0 N[2,3](t[4]=4.0)=0.5 N[3,3](t[4]=4.0)=0.5 N[4,3](t[4]=4.0)=0.0

or with the second knot vector:

N[0,3](t[0]=0.0)=1.0 N[1,3](t[0]=0.0)=0.0 N[2,3](t[0]=0.0)=0.0 N[3,3](t[0]=0.0)=0.0 N[4,3](t[0]=0.0)=0.0
N[0,3](t[1]=0.0)=1.0 N[1,3](t[1]=0.0)=0.0 N[2,3](t[1]=0.0)=0.0 N[3,3](t[1]=0.0)=0.0 N[4,3](t[1]=0.0)=0.0
N[0,3](t[2]=0.0)=1.0 N[1,3](t[2]=0.0)=0.0 N[2,3](t[2]=0.0)=0.0 N[3,3](t[2]=0.0)=0.0 N[4,3](t[2]=0.0)=0.0
N[0,3](t[3]=3.0)=0.0 N[1,3](t[3]=3.0)=0.25 N[2,3](t[3]=3.0)=0.75 N[3,3](t[3]=3.0)=0.0 N[4,3](t[3]=3.0)=0.0
N[0,3](t[4]=4.0)=0.0 N[1,3](t[4]=4.0)=0.0 N[2,3](t[4]=4.0)=0.5 N[3,3](t[4]=4.0)=0.5 N[4,3](t[4]=4.0)=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!?).