Contents |
|
Bicubic Bézier Surfaces
A bicubic Bézier surface is a parametric surface (u,v =) defined by its sixteen control points which lie in a four-by-four grid, pij. The common form for representing this surface is:
The functions Bi(u) and Bj(v) are the same Bernstein polynomials which were shown for the Bézier curve.
The edges of Bézier surfaces are each Bézier curves defined by the control points along that edge. The only control points that lie on the surface are the corner control points. In order to generate the surface, we need to compute points from the surface representation given above, defined by the sixteen control points. This tessellation can be done in a variety of ways. Let's look at three of them and examine the cost of creating a 9x9 grid of vertices on the surface.
Tessellation by Direct Evaluation
The most obvious way to slice a Bézier surface into polygons is by directly calculating the double-sum equation on a regular grid. Directly calculating a point on the surface costs 51 adds and 116 multiplies when done in a fairly efficient manner. Since we can calculate all 81 points iteratively, some of these computations can be amortized across the rows or down the columns of the grid. Without doing too much extra programming it is possible to compute all 81 vertices using direct evaluation at a cost of 3978 adds and 8586 multiplies.
Tessellation by De Casteljau's Algorithm
Another way to tessellate a Bézier surface is through the use of De Casteljau's algorithm. De Casteljau's algorithm shows how a Bézier curve can be calculated by using simple linear interpolation between control points. Calculating points on a Bézier curve via De Casteljau's algorithm is similar to direct evaluation of points on the curve. But we can construct an algorithm to generate surface points by splitting surfaces from De Casteljau's algorithm, and that should increase the speed of surface tessellation.
Take a look at Figure 2 for an illustration of how De Casteljau's algorithm works. Start with lines connecting each pair of the Bézier curve's adjacent control points (P0 to P1, P1 to P2, P2 to P3). The parameter t () represents a distance along each of these lines, where 0 is the beginning of the line, and 1 is the end. At t along each line put a mark. Connect adjacent marks (call them P01, P12, P23) with lines, and again make a mark at t on each of those lines. Connect these two marks (P02, P13) and drop a point at t (P03) on this line. That point lies on the Bézier curve. If you step the parameter t from 0 to 1, you will produce the entire curve.
![]() |
A graphical
depiction of De Casteljau's algorithm. |
This is a pretty simple algorithm and it can easily be used to split curves in half if you set t=0.5. This will generate two smaller Bézier curves with their own sets of control points. The control points of the subcurves are actually the intermediate marks we made during the split process.
And we can use this curve-splitting technique to split our Bézier surface into subsurfaces! At each stage we start with a bicubic Bézier surface that has four rows of four control points each. Split all four rows of control points in half using De Casteljau's algorithm at each row, and we then have two separate Bézier surfaces, each with their own sets of control points. Since these are subsurfaces of the original surface, the corner control points of the subsurfaces are points that lie on the original Bézier surface.
To compute the control points of the subcurves we can generate equations directly from the description above. Here are the equations that will generate the new sets of control points qi and ri:
The point q3 (also known as r0) is the curve splitting point. This set of equations will generate two subcurves with their control points, at a cost of 18 adds and 18 multiplies. (6 adds and 6 multiplies for each of x, y, and z.)
A surface split takes four curve splits so it costs four times that, or 72 adds and 72 multiplies. We need to do 51 surface splits (optimized from 63) to tessellate our entire surface, so the total comes to 3672 adds and 3672 multiplies.
Although this algorithm is indeed cheaper than direct evaluation, a drawback is how much extra data we have to keep around. Keeping track of all the control points necessary for each subsurface is a lot of data. For computation of Bézier surfaces in a limited memory space (the Nintendo64 RSP DMEM is only 4KB) this may be too much stuff to keep around. Let's see if we can find something better.