## Thursday, January 29, 2015

### NURBS

Previously, I had described the logic behind B-splines. NURBS are not much different, but still require a little more thought.

The acronym NURBS stands for Non-Uniform Rational B-Spline. First off, the “non-uniform” part just means that the knots are not equally spaced. It seems silly to explicitly call this out in the name, as this is the natural state of B-splines.

That leaves us with the “Rational” part. Rational B-splines are B-splines where each basis function has a “weight” associated with it. However, this doesn’t simply mean that each of the basis functions gets naively multiplied by its weight. Instead, it’s a little more subtle than that.

First of all, recall that the original formulation of a B-spline is of the form Σ basis * value. If you naively multiply a particular basis function by a weight, that is mathematically equivalent to multiplying the value instead, which would effectively be moving your input point. This might make the resultant curve not resemble our input values at all, which is the whole point of B-splines and NURBS.

Instead, we want to augment the contribution that a particular basis function makes, relative to the other basis functions. Let’s unpack that statement:
1. We are interested in the “contribution” of a basis function. That means that we are interested in the value of a basis function compared to the sum of all the basis functions.
2. We are augmenting a basis function in order to create a different basis function. Once we have our augmented basis functions, the formulation of a NURBS is still Σ newbasis * value.
3. We want the weights to be relative. For example, if all the weights are 2, that should have the same resulting curve as if all the weights are 1.
With this goal in mind, it becomes clear that, as you increase the weight of a basis function, the curve gets drawn to the associated value, rather than simply just “upwards.”

Let’s take an an example which will help us show how these weights get applied. Here is a chart that depicts 10 basis functions of order 4. The knot vector is [0, 1, 2, 3, 4, 100, 200, 300, 400, 500, 600, 601, 602, 603, 604].

Now, let’s show the same data in a stacked graph, in order to show each basis function’s contributions.

As you can see, the sum of all the basis functions is a constant 1. This isn’t an accident - it’s a fundamental requirement of B-splines. This is why the curves grow and shrink as you move knots around.

If we pick a particular input, we can see that there is more than one basis function that contributes to the resulting sum. We can see the different contributions of that particular value easily.

Going back to our goal, we want to augment the contributions of the constituent basis functions in proportion to their weights. This means that we don’t want to affect the sum total of the basis functions, but we do want to grow and shrink the contribution of each individual basis. The way we do that is pretty straightforward - multiply each of the basis functions by their weight, and then normalize by the new total. This looks like newbasis[i] = oldbasis[i] * weight[i] / (Σ oldbasis[k] * weight[k])

Here’s what the example data above looks like if you give one of the basis functions a weight of 5 and all the other ones a weight of 1. As you can see, the sum of all the basis functions is still 1; however, the contribution that the heavily-weighted basis function makes has grown proportionately.