In Conclusion

text only
 
progress indicator progress indicator progress indicator progress indicator

The Building Blocks of a B-Spline

As I said, B-splines are quite a bit more flexible than Bezier curves. This flexibility comes from the fact that you have much more control over the basis functions. Instead of being limited to the Bernstein basis functions, you can develop your own basis functions by controlling a handful of basic building blocks. Therefore, I will begin the explanation by deconstructing what you learned about polynomial and Bezier curves and add the new material needed for B-splines. Then, I show you how everything comes together to form the basis functions needed to draw these splines. I will begin with the control points.

Control Points

In this chapter, the way you manipulate the control points is largely the same as in Chapter 3. This is a set of points that controls the overall shape of the curve. The role of the basis functions will be to describe how points are interpolated between these control points. So, you can manipulate control points just like you did in Chapter 3. You can move them in two or three (or more) dimensions and rely on the basis functions to help change the resulting curve.

Note 

All of the examples in this chapter deal with 2D curves. I do this because 2D is easier to visualize in figures. The concepts work exactly the same in three dimensions. The equations in this chapter apply to each component of the control point position, regardless of how many dimensions are used.

Having said that, there is a difference in the way that control points affect the curve. In Chapter 3, you saw that each control point had an effect on each point on the curve; likewise, the number of control points affected the degree of the curve. For the sake of flexibility, you would like to be able to arbitrarily set the degree of the curve and to also determine the range of effect each control point has. B-splines allow this level of control, but before I tell you how, I have to talk about what the degree of the curve really means.

Degree and Order

In Chapter 1, you learned that the highest exponent in the equation determined the degree of the polynomial curve. In Chapter 3, you saw that N control points yielded Bernstein basis functions of degree (N-1). So, N control points affected spans of curves with degree (N-1). In the case of Bezier curves, there was only one span, which was affected by all the control points.

At this point, I'd like to introduce some new nomenclature and talk about curves where the order is designated by k and the degree of the curve is (k-1). For example, each Bezier curve in Chapter 3 was fourth order with third-degree basis functions. The Bernstein polynomials are always (k-1) degree where k is always equal to N. B-splines and their basis functions are much more flexible.

B-splines decouple the number of control points (N) from the degree of the curve (k - 1) and the range of effect for the control points (k). In purely abstract terms, you can begin to think about curves in which each curve point is only affected by a subset of the control points instead of every control point (likewise, each control point only affects a subset of curve points). This is interesting because you now have more local control over the shape of the curve. You can talk about a curve of order k=4 with 16 control points. Moving one control point only affects a subset of the curve points as shown in Figure 4.1. The only way to do this with Bezier curves is to join several separate curves.


Figure 4.1: The advantages of local control.

You can also think about curves of arbitrary degrees that are not fixed by the number of control points. Curves of higher degrees have spans that are influenced by more control points and are therefore smoother approximations of the control polygon. Curves of lower degrees have spans that are influenced by fewer control points and are therefore not as smooth. First degree curves degenerate into the control polygon, as show in Figure 4.2. The points on first degree curves are affected by two control points. Interpolating between two points is just a line, as shown in Chapter 3, "Parametric Equations and Bezier Curves."


Figure 4.2: Curves of various degrees.

So, you now have more control over the degree, but you don't have complete control. The order k determines the number of control points that affect subsets of curve points. Therefore, the maximum order of a curve is k=N, and the maximum degree of a curve is N-1. The minimum order is 2, which creates a first degree (linear) curve.

I have talked about order and degree in terms of how control points affect subsets or spans of curve points, but I have not yet told you how those spans are determined. With Bezier curves, you didn't have any mechanism to determine the subsets because the control points always affect every curve point. B-splines give you more control thanks to such a mechanism. This extra building block is called the knot vector.

Knot Vectors

The purpose of the knot vector is to describe the range of influence for each of the control points. Imagine you wanted to draw a third-order curve with five control points. Each control point affects some subset of curve points along the parametric range. You might describe the ranges of each control point as [t , t 3 ], [t 1 , t 4 ], [t 2 , t 5 ], [t 3 , t 6 ], [t 4 , t 7 ]. You could also compact this to a single sequence in the form of [t t 1 t 2 t 3 t 4 t 5 t 6 t 7 ].

This is a knot vector. In this specific case, this knot vector could be used to describe how the control points influence a third-order curve with a parametric range of t < t t 7 . Figure 4.3 shows this more formally and shows how the ranges are encoded into the knot vector.


Figure 4.3: A knot vector.

There are a couple of generalizations you can pull from this example. First, a knot vector must have N + k elements. This is the number of elements needed to describe all of the ranges for each control point.

Also, the elements of the knot vector must be monotonically increasing. This means that each subsequent element must be greater than or equal to the one before it. The actual values of the elements can either be monotonically increasing values on some arbitrary range, or they can be normalized to the range of [0,1]. These are three examples of knot vectors. Note that the second and third knot vectors are functionally equivalent. They would produce the same curve.

  • [X] = [3 4 5 6 7 8]

  • [X] = [1 2 3 4 5 6 7 8]

  • [X] = [0.125 0.25 0.375 0.5 0.625 0.75 0.875 1.0]

For most of the text explanations , I will use integer knot values as shown in the second knot vector above because it is a little bit easier to explain different knot vector types in those terms. In the code examples, I use normalized knot vectors because it makes it a little easier to think about different ranges where the parametric range is from 0 to 1. In either case, remember that there is no difference in the resulting curve.

There are two defined flavors of knot vectors labeled as uniform and nonuniform. The elements of a uniform knot vector are evenly spaced . In a nonuniform knot vector, they are not. The following are some examples of each flavor.

  • [X] = [1 2 3 4 5 6] (uniform)

  • [X] = [1 3 5 7 9 11] (uniform)

  • [X] = [1 2 2 3 3 4] (nonuniform)

  • [X] = [1 2 3 3 4 5] (nonuniform)

There are also two different types of knot vectors, open and periodic. I will describe the attributes and advantages of each type after I describe all of the building blocks. The full discussion of the knot vector is far from complete, but the specifics of different types of knot vectors will make more sense after you see how all the pieces come together.

At this point, you have all but one of the "building blocks". You know that a set of control points can be used to define a curve. You know that you can describe the properties of the curve in terms of the order and associated degree. You also have a mechanism (the knot vector) that allows you to talk about how the control points and the properties of the curve interact. You need one more basic building block-the piece that binds everything together and allows you to actually draw something-the basis function.

B-Spline Basis Functions

In Chapter 3, life was easier. Equation 3.7 gave you the Bernstein basis function solely as a function of the number of control points. Now, you have a lot more flexibility, but you also have a lot more to worry about. In addition to control points, the B-spline basis function must account for the degree of the curve, as well as the ranges defined by the knot vector. The resulting basis functions are defined not by Bernstein polynomials, but by the Cox-de Boor recursion formulas shown in Equation 4.1.

(4.1) Recursion formulas used to derive basis functions. 

The resulting basis functions are subject to the constraint that the sum of the basis functions must be equal to 1.0. In other words, see Equation 4.2.

(4.2) Constraint on the range of the basis functions. 

This constraint was always true for Bezier curves, but the flexibility of B-splines sometimes leaves cases where you must specifically account for this constraint. You will see why when I talk about periodic curves.

At first glance, these formulas can seem quite intimidating, but they aren't once you understand what they are doing. With Bezier curves, you used Equation 3.7 to derive a basis function. Now you must recursively find the basis functions for a given order, starting at the first-order basis functions. This is best described graphically, and by example.

Imagine I want to draw a fourth-order (k=4) cubic curve with 4 control points and I choose a knot vector of [X] = [0, 0, 0, 0, 1, 1, 1, 1]. Before I go any further, think about this knot vector in terms of Figure 4.3. I have created a knot vector that forces each control point to affect the entire curve. Sound familiar?

First, using the first part of Equation 4.1, I come up with the following first-order basis functions shown in Equation 4.3, which are shown graphically in Figure 4.4.


Figure 4.4: First-order basis functions for k=4 [X] = [0 0 0 0 1 1 1 1].
(4.3) First-order basis functions for k=4 [X] = [0 0 0 0 1 1 1 1]. 

Those basis functions will now provide the input I need to define the second-order basis functions. This yields Equation 4.4, shown graphically in Figure 4.5.


Figure 4.5: Second-order basis functions for k=4, [X] = [0 0 0 0 1 1 1 1].
(4.4) Second-order basis functions for k=4, [X] = [0 0 0 0 1 1 1 1]. 

Repeating this for the third-and fourth-order basis functions, I get the following equations and graphs (Equations 4.5 and 4.6 and Figures 4.6 and 4.7).


Figure 4.6: Third-order basis functions for k=4, [X] = [0 0 0 0 1 1 1 1].

Figure 4.7: Fourth-order basis functions for k=4, [X] = [0 0 0 0 1 1 1 1].
(4.5) Third-order basis functions for k=4, [X] = [0 0 0 0 1 1 1 1]. 
(4.6) Fourth-order basis functions for k=4, [X] = [0 0 0 0 1 1 1 1]. 

The fourth-order basis functions are what you need for a fourth-order, third-degree curve. The graphs of these basis functions are shown in Figure 4.7. Look familiar?

As you can see, these basis functions are the Bernstein polynomials last seen in Chapter 3, when I mentioned that Bezier curves could be considered a special case of B-splines. Here is the proof. With the proper knot vector and degree, you can represent Bezier curves as a special case of the more general B-spline. The knot vector was chosen so that each control point affected the entire curve and the degree was chosen to match that of a Bezier curve with four points. I will talk about this in more depth when I talk about the different types of knot vectors.

These steps have walked you through all the components needed to draw your curve except for one very small and extremely important piece.

The B-Spline Curve Equation

You have a set of basis functions and you know the degree you want your curve to be. Equation 4.7 shows the equation of the B-spline curve.

This equation is extremely similar to the one given for Bezier curves. In this case, the set of basis functions to be used is determined by the desired degree of the curve. The basis functions define the influence of each control point as a function of t. Once you have derived the necessary basis functions, the location of a point on the curve is simply a weighted sum of all the control points at a given value of t. Only now, the weight of some of the control points might be 0.

(4.7) B-spline curve equation. 

You now have the basic information about the building blocks you need to draw B-splines. So far, I have left out many of the details, most notably on the subject of the knot vector. Now that you have all the basic pieces, I will backtrack and fill in the details.

progress indicator progress indicator progress indicator progress indicator


Focus on Curves and Surfaces
Focus On Curves and Surfaces (Focus on Game Development)
ISBN: 159200007X
EAN: 2147483647
Year: 2003
Pages: 104
Authors: Kelly Dempski

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net