## Monday, January 26, 2015

### B-Splines

B-splines are similar to Bezier curves in some ways and different than Bezier curves in different ways. Both are calculated using a coefficient vector and a basis function vector. The benefit of B-splines over Bezier curves, however,  is that B-splines’ basis functions are more local than Bezier curves’ basis functions.

Recall that the Bernstein polynomials were useful because each of them had a hump in a particular place along the (0, 1) range. However, the Bernstein polynomials are nonzero everywhere inside that same range. It would be beneficial if a particular basis function was 0-valued everywhere except in some small range, and if this range consisted entirely of the hump.

Such a function, however, is not a polynomial. There are no polynomials that are zero-valued everywhere except for some finite range, and nonzero within that range. This means that if we want to adopt such basis functions, our resulting curve won’t be a polynomial. Which is fine.

This also means that our resultant curve will be zero-valued outside of union of all the ranges of all the basis functions.

So where do we put each of these nonzero ranges? Well, we want the ranges of the different basis functions to overlap (If they didn’t, then our resultant curve would be forced to 0 at all of the non overlapping parts). The most logical way to do this is to cut up your range into k segments, and give each curve a sliding window into each of these segments. For example, you could give the first basis function segments 1 and 2, and give the second basis function segments 2 and 3, and give the third basis function segments 3 and 4, etc.

If we want to keep this general, we should also provide a way to change the width of that sliding window. We probably also want a way to give each basis function more than two consecutive segments (instead of 2 in the previous example). If we want to give each basis function 4 segments, then the first basis function gets segments 1, 2, 3, and 4, while the second basis function gets segments 2, 3, 4, and 5. We probably want this to be a tunable parameter in our system. In the picture above those basis functions are of order 4.

So how do we decide where on the number line the boundaries between our segments lie? Well, we could make them regularly spaced; however, that would limit the kinds of curves that we could create with this system. Instead, we should probably make these locations a tunable parameter to the system.

We now have the structure that we need to describe B-splines. A B-spline is characterized by three things:
1. How many basis functions (and coefficient values) we want
2. How many sequential segments each basis function is nonzero over. This is called the order of the spline, and is also equivalent to the order of the resulting polynomials and the basis polynomials.
3. A vector of positions on the X axis which denote the locations of the segment boundaries. This is called the knot vector. Note that the number of elements in the knot vector is equal to the number of basis functions plus the order of the spline. Also note that the elements in this vector, called knots, must be increasing.
With these pieces of information, we can generate each of our basis functions. The function that generates these basis functions was created so that they form a basis over the vector space of splines. This is important because it means that any polynomial spline can be written as a linear combination of B-splines.

Also note that discontinuities can be created if multiple knots are placed on top of each other (have the same value). The kind of discontinuity can be controlled with how many knots are all on top of each other.

Another interesting phenomenon is that, if the order of the B-spline is equal to the number of basis functions, as well as the first half of all the knots are on top of each other and the second half of all the knots are on top of each other, then you actually get a single effective interval (between the two piles of knots). The bases that traverse the entire range have the same behavior as the Bernstein polynomials (albeit limited to a particular domain). This means that every Bezier curve is representable as a B-spline.

So there you have it - the logical conclusion to the idea that the basis functions should be nonzero only in a particular range and zero everywhere else, generalized to a system which can represent any spline.