Contents

Scalable Geometry

Representations

Implementing Bezier Patches

Implementing Bézier Curves

Our approach to rendering a Bézier curve is similar to that for rendering Hermite curves. We find a series of points along the curve, and render that series as a line strip. We'll do it, once again, by evaluating the curve at even intervals of u. Listing 3 shows this clearly: UniformCurveTessellator::tessellate takes a vector of four control points and a vector of four associated basis functions, and renders the curve in 100 steps.

To generate each point, it calculates Equation 2 for the input - it adds up the sum of each point times that point's basis function. For our cubic curve, this is certainly not the most optimized way to calculate the curve. However, because it's only 100 points, it's not noticeable and the demo still runs quite fast.

Surfaces: The Bézier Patch

It might seem more consistent to cover not only Bézier patches but also Hermite patches, as well. The reason we're skipping straight to Bézier patches is that we're trying to cover the curves and curved surfaces in the most intuitive order possible. Whereas it makes sense to cover Hermite curves and then Bézier curves, Hermite patches are somewhat more difficult to learn than Bézier patches.

Figure 4. A bicubic Bézier patch. The green grid
connects the control points.

Since a Bézier curve was a function of one variable, f(u), it's logical that a surface would be a function of two variables, f(u,v). Following that logic, since a Bézier curve had a one-dimensional array of control points, it makes sense that a patch would have a two-dimensional array of control points. We'll now discuss bicubic Bézier patches. The phrase "bicubic" simply means that the surface is a cubic function in two variables - it is cubic along u and also along v. Then, since our cubic Bézier curve had a 1¥4 array of control points, our bicubic Bézier patch has a 4¥4 array of control points. Figure 4 shows an example of a surface.

Now, with that, we need to take our equation for evaluating a Bézier curve at some u and extend it to allow us to evaluate our patch at some (u,v). The extension is fairly straightforward. We just evaluate the influence of each of the 16 control points, yielding:


Eq. 3

We can see by inspection that our properties from the Bézier curve extend to the patches. Why? For the following reasons.

  1. The patch interpolates p00, p03, p30, and p33 as endpoints.
  2. Control points have local control, that is, moving a point over the center of the patch will most strongly affect the surface near that point.
  3. The patch remains within the convex hull of its control points.

Implementing Bézier Patches

Rendering a Bézier patch is more complicated than rendering a Bézier curve, even when doing it in the simplest possible way. With a Bézier curve, we could just evaluate a number of points and render a line strip. With a patch, we need to evaluate strips of points and render triangle strips. Also, with a patch we have to worry about lighting. After all, an unlit patch will just look like an oddly-shaped splotch of red on the screen. To see the contours, we need lighting. For our naïve implementation, that means we'll need to light each vertex. To light a vertex, we need its normal. So, for every (u,v) pair, we need to solve for the point on the surface, and then solve for its normal.

Equation 3 tells us how to find the point on the surface, but how do we find the normal? Well, we know we can take the derivative of the surface with respect to either u or v, which would yield the tangent vectors to the surface in the direction of either u or v, respectively. If we find both of those tangents, we know that they both lie in the plane tangent to the surface. Then, taking their cross product will yield a mutually perpendicular vector, the surface normal. Finally, we'll have to normalize it since it most likely won't be unit length.

So, how do we find df(u,v)/du and df(u,v)/dv? As it turns out, we can just take the derivatives of the basis functions. That is,


Eq. 4

The same holds for the derivative with respect to v. Therefore, before rendering, we calculate the derivatives of the basis functions and store them. We use Equation 4 and its v analogue to find the tangents, and then proceed to find the surface normal. The code for the loop is shown in Listing 4.

Now, while the curves didn't slow down from our naive implementations, this patch demo shows quite painfully why optimization is very necessary. It runs at a steady 30 or so frames per second (again, on my Voodoo2), but that's just one patch. If you tried to base a terrain system on this implementation, it would be painfully slow. After all, consider the work we're doing. By default, the tessellator breaks the surface into 100 points. At each point, we're evaluating 32 cubic functions and 32 quadratic functions, then doing a vector cross-product and a vector normalization (ouch!). Then, for each point, we're asking OpenGL to light it, which is not cheap either. Plus, we're not caching any of this between frames, and we're actually allocating and then deallocating the space every frame. So we're doing a lot of work, much of it entirely unnecessary.

Nonetheless, it works. We're rendering a lit Bézier patch, and even if it is a bit sluggish, it looks pretty good. Now, if only we could do something with it...

Moving from Theory to Application

There are certainly a number of loose ends. We've covered Bézier and Hermite curves and Bézier patches, but the implementations so far are entirely unoptimized and the patch demo is rather sluggish even for what little it is supposed to do.

Furthermore, we haven't seen an example of using these things in a real application. The demo code is just that - a demo of a curve or surface floating in black space. There is still a fair amount of material to cover before we can turn these into something real.

Next month, I'll cover some optimization techniques for Bézier curves and surfaces. We'll also see how to form other surfaces and objects by joining Bézier patches together, and look at some of the properties of such objects, as well as some of the problems that can arise from the new techniques. Finally, having covered all of this, I'll finish off the article with a far more interesting demo.

References

When he's not sitting around radiating potential, Brian's probably busy furthering the secret OpenGL agenda. Either that, or he's likely doing the same thing he does every night, Pinky - trying to take over the world. Send preemptive bribes and/or tribute to brian@maniacal.org.

Discuss this article in Gamasutra's discussion forums

________________________________________________________

[Back to] Scalable Geometry