Contents

Introduction

Bicubic Bezier Surfaces

Tessellation by Central Differencing

Conclusion

Tessellation by Central Differencing

A third way of generating points on a Bézier surface is through the use of central differencing. In this approach we look at taking advantage of the Bézier curves on the edges of the surface, by splitting the edge curves and then splitting across the surface repeatedly to subdivide the surface. Using central differencing we can very quickly compute the midpoint of a Bézier curve, so this should speed up our tessellation even further. Let's derive the algorithm for surface splitting.

We start with the Taylor series expansion, which represents the value of a function Q near a point u.

In this equation, Qi(u) is the i-th derivative of Q(u).

The functions that describe a Bézier curve are cubic. So we know right away that the derivatives will be of the form:

Since the fourth and higher derivatives of the cubic equation are zero, the Taylor expansion only needs to go out to the third derivative. The new form of the above equation looks like this:

If we wanted to look at points just behind u, in the negative du direction, we could work with this expression:

Let's add these two equations together to see what we can derive using points in front of and behind Q(u). Adding the equations together we receive this:

This equation is beginning to look useful. Let's simplify it to solve for Q(u):

Now imagine that we're trying to split a Bézier curve in half. If u ranges from 0 to 1, we want to find the value of the curve at u=0.5. We can also use du=0.5, to represent the entire curve. Note that these values are only valid at the first curve subdivision step for the surface. This equation simplifies even further, down to:

This shows us that the value at the midpoint of the curve, Q(0.5), is simply the average of the endpoints of the curve, minus a fraction of the second derivative at the midpoint! That's 6 adds and 6 multiplies to compute the midpoint assuming that we have the values Q(0), Q(1), and Q''(0.5).

How do we get Q''(0.5)? Let's start with the grid of 16 control points that represents the surface. Earlier I stated that the corner control points are on the Bézier surface, and that each edge is a Bézier curve. So the first step to take is splitting each edge of the surface to generate midpoints for the edge curves. We have the Q(0) and Q(1) values for each edge (the above equation works equally well in either parameter direction, u or v), but no second derivatives.

If we go through the derivation above with Q(u) replaced by Q''(u), we get a formula that helps:

Since the fourth derivative of the cubic equation is zero, the equation has reduced nicely to the form above. At the first subdivision step, this equation reduces to:

It doesn't get much easier than that. Just the average of the second derivative at the curve's endpoints! That makes sense, since Q''(u) is a linear function. But wait, we still don't have Q''(0) or Q''(1). Let's derive those.

Deriving the Second Partial Derivatives. We're working in a biparametric space. Both u and v vary across the Bézier surface. All the curve splitting we'll be doing will be along curves where one of these parameters is held constant. So the equation we need to derive is for the second derivative in the direction of the varied parameter. For curves that vary in u, what we need is the second partial derivative of u for the surface along this curve. Likewise for v-curves.

Starting with the parametric equation for the Bézier curve expanded from the sum form, we can easily compute the second derivative for the curve.

Now we have equations that we can use at the corner points of the surface to generate the second partial derivatives for both u and v. The points in the equations will correspond to the points along each edge of the surface, in the appropriate parameter direction. As we split the curves, we can average the second partials at the endpoints (as shown above) so that successive subcurves will have appropriate values for future curve splits.

This leaves one last issue. As we split the surface, we will frequently split a u-curve, take the midpoint, and use it as an endpoint for a curve to be split in v. The second partial in v is cubic across a u-curve, so we need a way to generate both second partials at each split. A previous equation that we derived can be adapted for this purpose:

This shows that we can compute the second partial derivative in v on a u-curve if we know the value of Quuvv. A similar equation shows that we can use Quuvv for v-curves as well.

Quuvv is guaranteed to be linear across the curve, so we can average the endpoints again to receive the value at the midpoint:

So now we just need the value of Quuvv at the surface corner points to start things off. This time we have to do the derivation from the original double-sum equation.

We can take the second derivative of each of the Bernstein polynomials, to plug into the above equation:

To compute Quuvv at any corner point, just plug u and v into these equations and perform the double summation.

Central Differencing Performance Analysis. We've done a lot of work here so let's review. At the initialization stage we need to compute the values Quu(u,v), Qvv(u,v) and Quuvv(u,v) at each corner point. Here are examples of what these equations look like at the corner point (u,v)=(0,0).

Performing these computations on each corner point results in a total cost of 120 adds and 180 multiplies. A pretty hefty initialization cost, to be sure!

However, each curve subdivision after initialization generates one surface point and costs fairly little. These computations need to be performed at each curve split (these equations are for u-curves, but the v-curve equations are similar):

These curve splits cost 18 adds and 30 multiplies each.

We need to perform 77 curve splits in order to produce a total of 81 surface points. The total cost to do this, including initialization, is 1506 adds and 2490 multiplies. As you might guess, a lot of the computations are redundant and it is quite easy to optimize the algorithm further, to 1506 adds and 1488 multiplies.

Conclusion