If you're already familiar with the Bezier formulation of curves, then you shouldn't feel overwhelmed by the topics presented here. If you're not, read the previous article "The Practical Guide to Bezier Curves".
This article is a primer for the next article in this series. The first 2 parts are intended to set up all of the math and definitions for B-splines, and Part 3 will discuss the algorithms and shortcuts. I believe this article and its companion to be essential to understanding a very common and powerful set of curves and surfaces.
Welcome Adventurers!
If you're reading this, then you've made it past the mathematical swamp and are now ready and willing to make the hike up the B-spline mountain. We may have lost some people along the way, but congratulations to you for understanding the previous article and making it this far. Take a look at the beginning of the previous article if you need a reminder of why this is important. Now that we've gotten the necessary background out of the way in the previous article, let's talk about the B-spline basis functions.
Comparing Bernstein and B-spline Basis Functions
Remember our recursive relationship with Bernstein polynomials?
\[ B_{0,0}(u) = 1 \\ B_{i,n}(u) = 0; \, i < 0 \quad \text{or} \quad i > n \\ B_{-1,n-1}(u) = B_{n,n-1}(u) = 0 \\ B_{i,n}(u) = (1-u)B_{i,n-1}(u)+uB_{i-1,n-1}(u) \]
Let's compare them with our B-spline basis functions and knot vector:
\[ U=\{u_0,\dots,u_m\};\, u_i \le u_{i+1},\, i=0,\dots,m-1 \\ N_{i,0}(u) = \begin{cases} 1, & u_i \le u < u_{i+1} \\ 0, & \text{otherwise} \\ \end{cases} \\ N_{i,p}(u) = \frac{u-u_i}{u_{i+p}-u_i}\,N_{i,p-1}(u)+\frac{u_{i+p+1}-u}{u_{i+p+1}-u_{i+1}}\,N_{i+1,p-1}(u) \]
Before we start our discussion, let me clarify my terminology for this basis function section. I use the word order to specify which level of recursion I'm talking about. The 0th-order for me means that I'm at the "base case", talking about either \( b_{i,0}(u) \) or \( N_{i,0}(u) \). When I use the word "degree", I mean the degree of a polynomial. For a degree-3, p = 3. I will try to stay as consistent as possible with these meanings. This is not the standard terminology for B-splines; it's just the one I'll use here.
First, let's define how many basis functions are needed for a given B-spline. Obviously, we need one for each control point, but how many control points are needed for a given B-spline? Well, remember how I said the number of control points are somewhat independent of the degree of the B-spline? The rule is that if we have m+1 knots in the knot vector and the B-spline is degree p, there must be n=m-p control points. Second, let's look at the number of basis functions per order. For a degree-2 Bezier curve, we need 3 2nd-order Bernstein basis functions. However, those 3 2nd-order functions are interpolations of 4 1st-order functions, which are in turn interpolation of 5 0th-order functions. The dependence tree looks like this:
\[ \begin{matrix} b_{-2,0} \\ b_{-1,0} \\ b_{0,0} \\ b_{1,0} \\ b_{2,0} \\ \end{matrix} \rightarrow \begin{matrix} b_{-1,1} \\ b_{0,1} \\ b_{1,1} \\ b_{2,1} \\ \end{matrix} \rightarrow \begin{matrix} b_{0,2} \\ b_{1,2} \\ b_{2,2} \\ \end{matrix} \quad\quad = \quad\quad \begin{matrix} 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ \end{matrix} \rightarrow \begin{matrix} 0 \\ (1-u) \\ u \\ 0 \\ \end{matrix} \rightarrow \begin{matrix} (1-u)^2 \\ 2u(1-u) \\ u^2 \\ \end{matrix} \]
The B-spline basis functions are analogous in their dependencies. If n pth-order functions are required, then n+p 0th-order basis functions are required:
\[ \begin{matrix} N_{0,0} \\ N_{1,0} \\ N_{2,0} \\ N_{3,0} \\ N_{4,0} \\ \end{matrix} \rightarrow \begin{matrix} N_{0,1} \\ N_{1,1} \\ N_{2,1} \\ N_{3,1} \\ \end{matrix} \rightarrow \begin{matrix} N_{0,2} \\ N_{1,2} \\ N_{2,2} \\ \end{matrix} \]
Notice that in our definitions above, m=n+p. NOTE: In the Bernstein definition, our i values can be negative. In the B-spline definitions, \( i \ge 0 \).
Third, let's look the 0th-order definitions of the Bernstein and B-spline functions. As you can see, the zeroth-order Bernstein functions are held constant (either 1 when i=0, or 0 when i < 0 or i > n) over the entire parameter domain. This is different than the B-spline basis function definition, where all the 0th-order functions are step functions, whose values depend on the parameter value where the functions are evaluated. For the ith 0th-order function, the function is 1 if \( u_i \le u < u_{i+1} \). A couple of interesting things happen because of these peculiarities.
Properties of B-splines
Local Control
In the Bernstein basis definition, we saw that only 0th-order function was nonzero. By looking at the dependence tree, linear interpolation at successive steps produces p+1 nonzero pth-order basis functions (it can be zero somewhere, but it's not zero over the whole parameter domain).
A degree-p Bezier curve requires a basis function for each of the p+1 control points, so that means that every control point influences the shape of the curve everywhere, a property called global control. You notice this when you move a control and the whole curve changes with it to some degree (you can see how much each control point affects the curve in the graph of the basis functions in the previous article). We said that global control was generally an undesirable property in the previous article.
However, in B-spline basis functions things are a bit different. Above, we mentioned that the knot vector consists of m+1 knots, that we needed m 0th-order basis functions, and that m = n + p, where n is the number of control points and p is the degree of the B-spline. That means that m > p because n must be greater than 0. Just like in the Bernstein formulation, the B-spline recursive definition is really a linear interpolation of lower-order B-spline functions. But, since we have m 0th-order basis functions and we can only get p+1 nonzero-everywhere pth-order basis functions, if m > p+1, then at some parameter values we will have control points that have no effect on that point on the curve, a property called local control.
Let's illustrate with a somewhat real example: Let's take the knot vector of a degree-3 B-spline as \( U = \{ 0,0,0,0,1,2,2,2,2 \} \). Here, our m = 8 and p = 3. That means we'll have (5) 3rd-order basis functions. Let's look at the curve point at u = 0.5. Our dependency tree will look like this:
\[ \begin{matrix} b_{0,0}=0 \\ b_{1,0}=0 \\ b_{2,0}=0 \\ b_{3,0}=1 \\ b_{4,0}=0 \\ b_{5,0}=0 \\ b_{6,0}=0 \\ b_{7,0}=0 \\ \end{matrix} \quad \rightarrow \quad \begin{matrix} b_{0,1}=0 \\ b_{1,1}=0 \\ b_{2,1}=\text{nonzero} \\ b_{3,1}=\text{nonzero} \\ b_{4,1}=0 \\ b_{5,1}=0 \\ b_{6,1}=0 \\ \end{matrix} \quad \rightarrow \quad \begin{matrix} b_{0,2}=0 \\ b_{1,2}=\text{nonzero} \\ b_{2,2}=\text{nonzero} \\ b_{3,2}=\text{nonzero} \\ b_{4,2}=0 \\ b_{5,2}=0 \\ \end{matrix}\quad \rightarrow \quad \begin{matrix} b_{0,3}=\text{nonzero} \\ b_{1,3}=\text{nonzero} \\ b_{2,3}=\text{nonzero} \\ b_{3,3}=\text{nonzero} \\ b_{4,3}=0 \\ \end{matrix} \]
As you can see, the 5th control point doesn't affect the curve point at u = 0.5! This allows a designer to change control points while only affecting a portion of the curve.
Bezier End Conditions
Something interesting happens when multiple knots appear in a knot vector. In the previous knot vector example, the first 3 0th-order basis functions that are 1 when \( 0 \le u < 0 \). The next one is 1 when \( 0 \le u < 1 \). For all 4 for these basis functions, when u = 0 these functions are 1:
\[ \begin{matrix} b_{0,0}=1 \\ b_{1,0}=1 \\ b_{2,0}=1 \\ b_{3,0}=1 \\ b_{4,0}=0 \\ b_{5,0}=0 \\ b_{6,0}=0 \\ b_{7,0}=0 \\ \end{matrix} \quad \rightarrow \quad \begin{matrix} b_{0,1}=1 \\ b_{1,1}=1 \\ b_{2,1}=1 \\ b_{3,1}=0 \\ b_{4,1}=0 \\ b_{5,1}=0 \\ b_{6,1}=0 \\ \end{matrix} \quad \rightarrow \quad \begin{matrix} b_{0,2}=1 \\ b_{1,2}=1 \\ b_{2,2}=0 \\ b_{3,2}=0 \\ b_{4,2}=0 \\ b_{5,2}=0 \\ \end{matrix}\quad \rightarrow \quad \begin{matrix} b_{0,3}=1 \\ b_{1,3}=0 \\ b_{2,3}=0 \\ b_{3,3}=0 \\ b_{4,3}=0 \\ \end{matrix} \]
If you're not satisfied with this result, compute it for yourself. This is what happens when the B-spline has Bezier end conditions. In the above example, the B-spline passes through the first control point and the last control point and the curve is tangent to the control polygon. For end conditions, we require the first p+1 and/or last p+1 knots to be repeated. In the above example, the curve has Bezier end conditions. (As an aside, if the knots don't repeat, such as in the knot vector \( U=\{0,1,2,3,4,5,6,7\} \), then the end of the curve isn't coincident with the first control point, and likewise the last point on the curve with the last control point.)
Bezier Curve Equivalence
We can express Bezier curves in B-spline form too. Remember our Bernstein dependency tree? We got the Bernstein basis functions because of 2 factors:
- The middle step function was 1 and the rest were 0 for all parameter values.
- The interpolation for the recursive relationship was \( B_{i,n}(u) = (1-u)B_{i,n-1}(u)+uB_{i-1,n-1}(u) \).
Remember our B-spline recursive relationship is \( N_{i,p}(u) = \frac{u-u_i}{u_{i+p}-u_i}\,N_{i,p-1}(u)+\frac{u_{i+p+1}-u}{u_{i+p+1}-u_{i+1}}\,N_{i+1,p-1}(u) \). If we defined the knot vector to be something to make the fractional multipliers equal to \( 1-u \) and \( u \), then we could get the Bernstein basis functions. If we had a knot vector like \( U=\{0,0,0,0,1,1,1,1\} \), then it would satisfy those conditions.
As well, the only step function in there that isn't degenerate (i.e. the function is 1 only for a single parameter value) is the middle one (the 4th one) and it spans the entire parameter domain, so it will be 1 everywhere. We have p+1 repeated knots at both ends of the knot vector, so we have Bezier end conditions. In general, Bezier curves in B-spline form take the form \( U=\{\underbrace{a,\dots,a}_{p+1},\underbrace{b,\dots,b}_{p+1}\} \), where a and b can be any real numbers. They represent the parameter bounds of the Bezier curve. Remember that Bezier curves can have any parameterization with the modified form, not just between 0 and 1.
Multiple Bezier Curves in a B-spline
Let's just say we had 2 Bezier curves in B-spline form with knot vectors \( U_1=\{0,0,0,0,1,1,1,1\} \) and \( U_2=\{1,1,1,1,2,2,2,2\} \), respectively, and we wanted to join them together.
Continuity and Repeated Knots
We talked about B-splines being a way to achieve high orders of continuity between Bezier curves very easily. You can think of a B-spline as a way to spline together Bezier curves of degree p with a continuity of generally \( C^{p-1} \). There are, however, some special things we have to mention here with regards to continuity. "Real" vs. "Imaginary" Knots: This is really an interesting term. In a knot vector, the first and last p knots don't control the bounds of the parameter domain for the curve. These are called the "imaginary" knots. The rest of the knots in the vector, the "real" knots, control the bounds of the parameter domain. For example, in the knot vector for a standard Bezier curve \( U=\{0,0,0,0,1,1,1,1\} \), only the 4th and 5th knots are "real" and it states that the curve parameter domain bounds are \( [0,1] \).
Conclusion
References
A lot of the information here was taught to me by Dr. Thomas Sederberg (associate dean at Brigham Young University, inventor of the T-splines technology, and recipient of the 2006 ACM SIGGRAPH Computer Graphics Achievement Award). The rest came from my own study of relevant literature.
Article Update Log
09 Aug 2013: Initial release
