Tuesday, September 8, 2009

NURBS Knot Vectors In Perl 6 (part 1)

I'm not going to provide a lot of background for the wheres and whys of Non-Uniform Rational B-Spline (NURBS) knot vectors yet. Basically, a NURBS object is one or more knot vectors which define the parametrization and polynomials of the object, along with a bunch of Vectors to define the frame of the shape. I'm planning on spending a couple of posts working on getting a good knot vector class built up.

Confusingly enough, knot vectors have nothing directly to do with the sort of Vector we have been working with so far. From, say, a Perl 6 perspective, it would probably be more correct to call them knot arrays or knot lists. But knot vector is the traditional term, so that is what we will use.

The knot vector is a series of numbers in non-descending order, some of them repeated, that define the parameter range of the NURBS object we are looking at, and where it does interesting things. That is to say, adding a knot to the middle of the knot vector essentially splits one polynomial span the NURBS object is defined over into two joined polynomials. It's a fairly simple basis for a lot of powerful geometry.

Instead of starting by defining a knot vector class which can be the basis for NURBS objects, we're going to start by implementing the definition of the B-spline basis functions directly. (Note that the Wikipedia version there specifies it using different variable names -- our notation comes from The NURBS Book.) This would be horribly inefficient for real-world calculations, but we're just going to use it to establish good tests for our real class when that is ready.

Here's a straight forward implementation of the basis function formulas.

There are two tricky bits here. The first is that the standard definition can result in dividing zero by zero, which is defined to result in zero in this case. To keep the function implementation clean and simple, we define a "O/" operator which implements this exception to the standard rules of division.

The second wrinkle is that the standard definition has one curious blind spot. The equation does not work out when you reach the very last point! That is to say, the B-spline basis defined the standard way on a knot vector whose first value is A and last value is B covers the range [A, B). (Actually, I'm using first and last rather loosely there -- that's only true with the most common kind of knot vectors.) We define a KnotBasisDirection argument to N allows you to switch to the symmetrical definition, which is defined over (A, B]. The two definitions are identical over the interior range (A, B). The KnotBasisDirection enum has two values, Left and Right, corresponding to these choices. That's the first time I've defined an enum in Perl 6, but it seems straightforward enough.

No comments:

Post a Comment