The Best Laid Schemes...

"The best laid schemes o' Mice an' Men, Gang aft agley" -- Robert Burns

I've hit on one of those programming conundrums where a quick diversion becomes a huge project. Let me explain what I'm going for; it will probably take three or four blog posts to cover all the details.

My basic idea for a cool Perl 6 twist on knot vectors was evaluating the basis function to create a polynomial rather than a set value. The basis function defines a piecewise polynomial, with a continuous polynomial between each pair of distinct neighboring knots. So if the knot vector is (0, 0, 0, 1, 2, 3, 3, 3), that defines three polynomials: from 0 to 1, from 1 to 2, and from 2 to 3.

For any reasonably complicated knot vector, those polynomials are pretty tricky to calculate by hand. The NURBS Book approach is a change of basis, which works well but is not particularly mathematically enlightening. But the knot vector basis calculation function N we've defined can already do this: if it is passed a reasonably capable polynomial object for the $u parameter. This is the payoff for not forcing $u to be a Num; we can pass a polynomial instead and get a polynomial out.

Well, almost. We have two KnotVector.N functions, one for the $p == 0 case and one for $p > 0. The latter will work perfectly when passed a polynomial for $u. (At least in theory; there may be issues with Rakudo bugs, of course.) The former, however, actually needs to know what the numeric value of $u is. Originally I planned to somehow overload the polynomial class to have a value for this purpose. But as far as I know, to make that work, I'd have to overload prefix:<+> -- and last time I checked, that didn't work in Rakudo.

You could fix that by changing the second N to take an impulse array, instead of calculating it using the value of $u. But once you're thinking about doing that, it's time to face the facts: even the hypothetical "cool" implementation of N we have is grotesquely inefficient for reasonably complicated knot vectors.

	[0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
	[0, 0, 0.5, 0.5, 0, 0, 0, 0, 0]
	[0, 0.25, 0.625, 0.125, 0, 0, 0, 0]
	[0.125, 0.59375, 0.25, 0.03125, 0, 0, 0]

view raw gistfile1.txt hosted with ❤ by GitHub

To calculate the basis efficiently, you should only calculate the values that have a chance of being non-zero. And you should get the impulse value by doing something like a binary search.

So before I can get where I want to go with knot vectors, I need to have a working polynomial class and a working binary search. Plus I think it might be worthwhile to have a short post discussing the .Str and .perl functions for KnotVector and Nubs...