     |
 |
 |
 | | | | |
 |
|||
 |
||||||
          |
 |
 |
||||
|
Representations
So all a programmer needs to do is code up a quick tool for the artists consisting of a view window and four text entry boxes for them to type in the coefficients of curves, right? Of course not - artists demand flexibile, intuitive tools, and it's clear that creating curves by typing in coefficients lacks that certain ease-of-use factor for most of us. Therefore, we need another representation for the curve that makes creation and manipulation more intuitive. We'll touch on two such representations, the Hermite curve and Bézier curve. The Hermite curve we cover both because it's fairly common, but also because it doesn't require any specialized formulae to understand it. Then, as Bézier curves are somewhat more versatile, we'll move on to them. While we won't discuss it here, converting from Bézier curves to Hermite curves and vice versa is very straightforward and is explained in the references at the end of the article. There are plenty of other curve representations that we aren't going to touch upon. Notably, we are not going to cover B-Splines or that family (including the pervasive NURBS), of which Bézier curves are simply a special case. I chose the Hermite and Bézier curve models as a good starting point, because they can be represented and understood with a fair degree of ease. Once you have a firm grasp on Bézier curves, picking up one of the references at the end of this article and learning more about other curve models is much easier. Hermite Curves
A Hermite curve is a cubic curve described by its endpoints p0 and p1 and the tangent vectors at the endpoints, v0 and v1. You can see in Figure 1 what an example curve looks like. The question, then, is how we get the cubic equation from the points and vectors. Hermite curves are nice this way, as the derivation of the cubic is possible with just a little calculus. Let's say our cubic equation is
Note that f(u), a, b, c, and d are vectors. Then, we have that:
Then, we can express the endpoints as f(0) and f(1), and the tangents as f'(0) and f'(1).
Solving now for a, b, c, and d, we get:
Then we'll solve for what are called the "basis functions." The basis functions are simply functions of u that determine the contribution of the endpoints and tangents along the curve. So, for instance, the basis function that corresponds to p0 determines how much p0 contributes to points along the curve. Just by rearranging terms once again, we have the basis functions.
Then, we can express the curve as the sum of the basis functions times the components:
This provides us a handy way of expressing the curve. Furthermore, basis functions become far more important when we discuss Bézier curves, and so the Hermite curve provides a good introduction to the idea of a basis function. So, as we see here, a basis function is nothing more than a function associated with a component of the curve that determines the contribution of that component to points along the curve. Implementing Hermite Curves As handy as the basis functions are for expressing the curve, it's easier for our naïve implementation just to calculate the cubic equation of the curve by finding the coefficients using Equation 1. The code that does this is shown in Listing 1. Then, we just run along the curve by starting u at 0 and incrementing it by some fixed amount until we reach 1. We evaluate the curve at each value of u, save each result as a point on the curve, and then render the curve as a line strip. The code to evaluate the curve at a given value of u is quite simple and is shown in Listing 2. It's worth noting that even though the curve is recalculated fairly slowly every frame, the frame rate is still in the high hundreds (well, on my Voodoo2 graphics card, at least). Since we're doing nothing but calculating a hundred or so points along a curve every frame, the speed hit as a result of this inefficiency is not yet apparent. Bézier Curves
Now that we understand the cubic Hermite curve and its implementation, we can move on to Bézier curves. Whereas a Hermite curve is defined by endpoints and tangents, a cubic Bézier curve is simply described by four ordered control points, p0, p1, p2, and p3. Figure 2 shows an example curve. Our problem now is that it's not immediately clear how we define the curve based on these four points. With Hermite curves, we could use some basic calculus to get a cubic parametric equation. But even if we say that p0 and p3 are the endpoints, the points p1 and p2 seem to have little bearing, analytically, on the curve. It's easy enough to say that the curve should "bend towards" the points, but what does that give us in terms of our cubic equation? Here's where the importance of our basis functions comes in. We need to find a set of functions that blend the control points together in ways that give us the curve that we want. To do that, of course, we need to define the properties we'd like the curve to have. We can summarize these with three qualities:
Luckily for us, there exists just such a set of functions. These functions are called the Bernstein basis functions, and are defined as follows:
The parenthesized block with the n and the i is the mathematical phrasing of the binomial coefficient normally phrased "n choose i" or "n nCr i". The formula for n choose i is:
If we were considering general Bézier curves, we'd have to calculate that. Since we're only considering cubic curves, though, n = 3, and i is in the range [0,3]. Then, we further note that n choose i is the ith element of the nth row of Pascal's triangle, and so we have our values, {1,3,3,1}. So we can just hard-code that, no computation necessary.
While the Bernstein basis functions are a little odd looking at first, they're not that bad. To show that they really do satisfy our three conditions, we refer to Figure 3. This is a graph of the cubic basis functions. The red curve corresponds to p0, the green to p1, the blue to p2, and the magenta to p3. They're pretty looking, but what do they mean? Recall that the basis functions determine the contribution of each point over the curve. Also, the horizontal axis on that graph is u. So, when u is zero, the value of the basis function for p0 is 1, and all the others are 0. Therefore, the starting point of the curve is:
Therefore, we have that the curve starts at p0. Looking at the basis functions, it's obvious that the curve ends on p3. Our first condition is satisfied. As for the local control, we can convince ourselves that this holds by staring at the basis functions for long enough. It's obvious that p0 and p3 have local control, because as we move them, the curve moves, and they have very little influence over the rest of the curve. We can also see, then, that p1 and p2 have local control, since they have the most influence over the curve 1/3 of the way and 2/3 of the way along the curve, respectively. That means that if we moved p1, it would pull the section 1/3 of the way along the curve with it, and affect the rest of the curve much less. Then, we have our final condition: the curve must remain within the convex hull of the control points. With the Bernstein basis functions, this is true. The proof, however, is fairly complicated, and ends up dragging a bevy of new concepts into the fray. For the interested, Farin does a reasonable job of explaining this. It has to do with the fact that the Bernstein basis functions are nonnegative for u in the range [0,1], and also that if you sum up the values of all the basis functions for any value of u, the result is always 1. Then, the formula for calculating a point on our Bézier curve is:
________________________________________________________ |
||||||||||||||||||||||||||||||||||||||||||||||||||
Features
|
|
|