B-Splines

B-Spline Curves

 


B-Splines

B-splines were introduced around 1940's in the context of Approximation Theory. They have been applied for geometric modeling since 1970's. According to Schoenberg, B-spline means spline basis and the letter B in B-spline stands for basis. For instance, each polynomial F(t) in the polynomial space of degree three can be written as a linear combination of powers of t. The power basis that most of us are familiar with is on the unit interval where we have basis functions: 1, t, t2, and t3. There are four basis functions. And we say that its order is four since we have four coefficients for polynomials of degree three.

There are many other bases. The same polynomial F(t) can be expressed as a linear combination of a different set of the basis functions, B-splines, the spline basis. Let us look at one special case. On the same unit interval, we have another set of basis functions thatt can be thought of as part of a bell shaped function. This bell shaped function is part of a basis for a different space, a space of piecewise polynomial functions which we will discuss later. One convention is to call the bell shaped function "basis function" and to call the restricted portion "basis segment". As we said earlier, we may think of the other baisises as part of the basis functions, except, truncated in this particular case. These end points where basis functions start, end and coalesce with each other, are called knots.

A fully extended basis function has a finite number of intervals upon which it is positive, and it is zero everywhere else. The closure of the non-zero set is called its support. There is no way to describe this basis function with one single polynomial. For instance, the basis segment is part of the polynomial, -t3 + 3t2 - 3t + 1, properly scaled, translated and truncated. Another two segment is part of this polynomial. A third is related to this polynomial. And the final basis segment is part of t3. When we write the spline basis functions in terms of power basis, a B-spline is a composition of pieces cut from different polynomials.

Scaling the knots uniformly will not change the definition of the basis function. But changing the relative positioning of the knots will change the shape and therefore change the definition of the basis functions. When we move one of the end knots, it has the effect over only the immediately adjacent intervals, not the furthermost interval. If the knots are evenly spaced, the bases are called uniform B-splines, otherwise, they are non-uniform B-splines. One particular example of non-uniform B-spline is to have multiple knots at one end with multiplicity equal to the order.

Changing the degree would also change the shape of the basis functions. In the linear case the number of intervals in the support is two. And there are only two basis segments. In the quadratic, its support extends to three intervals;t hree basis segments; order three. Cubic: there are four intervals in its support and four basis segments; order four. This continues for quartic and quintic.

B-Spline Curves

For a planar B-spline curve, C(t), it is a vector- valued function of X(t) and Y(t). Both X and Y are piecewise polynomial functions of t, expressed in terms of the same spline basis. The constant coefficients, Vi's, are called the control vertices because they control the shape of the curve. For instance, if we have four basis segments in the domain space or parameter space, in the range space or object space we have a B-spline curve and we have four points that form a polyline structure usually called the control polygon.

The color coding shows the specific pairing between the basis and the control vertices. In other words, at any parameter on this interval there is a point on the curve that is calculated as follows. We pair up the control vertices with their corresponding basis functions evaluated at this parameter, take the product, and add them up. At any parameter on this interval, if we add up all the basis functions evaluated at this parameter, the sum is one. This demonstrate this property of basis functions called the partition of unity. When we traverse along the curve, we can see that the variation of the contribution from each control vertex is in fact dictated by the corresponding basis function, and that the contributions always add up to one everywhere.

Moving the knots will change the shape of the curve. This action has more subtle and less intuitive impact on the shape of the curve. The knots have direct influence on the basis functions defined over the intervals they reside. If we force the knots to collapse into a special case like this, it is called a Bézier curve. The basis segments are also called Bernstein polynomials, or, binomial expansions of (1-t) and t, of degree (k-l). For instance, for k = 4, one basis is (1-t)3 and another is t3, and so on. As a special case of B-spline curves, a Bézier curve will always have multiple knots at both ends with multiplicity equals to the order, and there are no interior knots. What is so peculiar about a Bézier curve? A Bézier curve always passes through both end points of the control polygon. It interpolates both ends, and the interpolation is tangential. In other words, at both ends, it interpolates both the positions and the tangents.