In my article in the November 1999 issue of Game Developer ("Putting Curved Surfaces to Work on the Nintendo64"), I talked a lot about bicubic Bézier surfaces. But I didn't go into the mathematics behind them, or why I picked the tessellation algorithm I used. This article is an extended version in which I will go into the gory details behind three tessellation algorithms. Whereas the goal of the magazine article was to implement one of these algorithms in microcode for the Nintendo64, this article details the background work it took to determine which tessellation algorithm to implement.
If you're not familiar with drawing curves using parametric equations, please refer to the references at the end of this article. Bézier surfaces are biparametric, and you'll need to understand the use of parametric equations before this discussion will make any sense. A Bézier curve is defined by a set of parametric equations that use one parameter. Bézier surfaces use two independent parameters, and three parameters will generate a Bézier solid. These are all fun and interesting things to play with, but we'll concentrate on Bézier surfaces in this article.
Why Bicubic Bézier Surfaces?
Using bicubic Bézier surfaces instead of other surface types makes a lot of sense. They are a nice balance between simplicity and complexity, providing freedom for the artist with a minimal amount of complexity for the programmer and renderer.
Bézier surfaces are just about as simple as you can get for curved surfaces. They are defined by a square grid of control points. The bounding curves of the surface are Bézier curves dictated purely by the control points at the edge. The surface between the edges is controlled by a simple proportion of nearby control points. The limitations placed on control point position to ensure continuity between neighboring surfaces is well-known and easy to enforce.
While biquadric (power-of-two) Bézier surfaces are simpler to implement, the bounding curves of biquadric Bézier surfaces are also quadric so each Bézier curve lies completely within a plane. Quadric Bézier curves are defined by three points, and these three points define the plane which contains the curve. This is an unnecessary limitation to place on the artist. Bicubic Bézier surfaces are bounded by cubic Bézier curves. These curves are defined by four points, the simplest form of curve which is not constrained within a plane.
Cubic Bézier Curves
Let's start with a discussion of cubic Bézier curves. The cubic Bézier curve is a parametric curve (u = [0, 1]) defined by its four control points pi. The common way of representing this curve is with the function:
The Bi(u) are the Bézier basis functions, which are cubic Bernstein polynomials. The Bernstein polynomials used for a cubic Bézier curve take this form:
Here are the same equations expanded out:
These basis functions indicate the proportion that each control point influences the curve. As you can see, each basis function is a cubic. They are also symmetrical (shown in Figure 1), and add up to one.
The basis functions are cubic, symmetrical, and add up to one.
Bézier curves travel through their beginning and ending control points, but the middle control points only influence the curve, and aren't directly on the curve.