PDA

View Full Version : Trouble with NURBS...



PixelDuck
04-04-2005, 06:16 AM
Hi,

I might sound stupid here, but could someone please explain evaluation of a b-spline for me? First off, when doing interpolation through corner points you have to duplicate 'k' of the first and final knot vector elements (k being the degree + 1). If we now evaluate using the vector elements as duplicates we get a division by zero, which is clearly not mathematically correct...

The division comes from this:

vec = { 0, 0, 1, 2, 3, 3 };
B1(u) = ( (u - vec[0])/(vec[i+1] - vec[i]) );

...because vec[i+1] and vec[i] are equal when i == 0.

This example is only for linear b-splines (but the same applies for any degree).

Is there something I'm doing wrong? Please explain to me the whole process of evaluation... How to avoid the situation where there would be a division by zero?

- PD

plasmonster
04-04-2005, 09:37 PM
0/0 is taken to be 0, so that multiple knot values will work.

Here's a bunch of working code on the subject:
http://www.nar-associates.com/nurbs/c_code.html#chapter2

A quick overview:
http://www.cs.wpi.edu/~matt/courses/cs563/talks/nurbs.html

Another fun site:
http://www.ibiblio.org/e-notes/Splines/Intro.htm

bChambers
04-05-2005, 10:24 AM
Originally posted by graham:
0/0 is taken to be 0, so that multiple knot values will work.

I was under the impression that shaders were aware of NANs. 0/0 is not defined, under any sane math implementation, as anything except NAN as the value does not exist.


Originally posted by PixelDuck:
Hi,

The division comes from this:

vec = { 0, 0, 1, 2, 3, 3 };
B1(u) = ( (u - vec[0])/(vec[i+1] - vec[i]) );

- PDI wouldn't recommend this. Better would be:
vec = { -1, 0, 1, 2, 3, 4 };

This will result in the spline being interpolated as a straight line. If you want me to go into the reasons I will, but for now you should know that your spline will approach a singularity (in practice it causes one, which is the problem you're complaining of).

plasmonster
04-05-2005, 11:52 AM
Hey bChambers, I don't think that PixelDuck is implementing this thing in a shader of some kind. It's quite common to repeat knot values in NURBS, and there's nothing wrong with doing so. The link above domonstrates the conic sections, for example, tricky to produce without repeating knot elements. The indeterminate form 0/0 is simply taken to be 0 so that algorithms that produce curve points will work as expected (e.g., Cox de Boor). One would simply test values before the division.

PixelDuck
04-05-2005, 08:54 PM
Hi,

Really, the idea of the whole duplication process is to decrease the degree of interpolation locally. It's just odd that this is not mentioned in any introduction to the b-spline (basis) function. It is however required for some kinds of objects as graham wrote. The other way is to partition the curve into smaller curves which is tricky and easily results in cracks when surfaces are concerned.

- PD