The DeCasteljau Method for Computing Bezier Splines

Anthony K. Yan

Independent Study for Bruce Land

Spring 98

0. Abstract

We present a simple Java applet which demonstrates the DeCasteljau method for computing spline surfaces of arbitrary order. Although slow, the DeCastlejau method has great intuitive appeal as it is highly geometric in nature.

1. Intro

Bezier splines are widely used in surface modeling for computer graphics. They have a variety of nice features, such as numerical stability, simple computation, smoothness, and are fairly intuitive. (Currently the graphics industry is interested in NURBS, which are essentially perspective transformed splines which are projected down from a higher dimension.)

When first learning about Bezier splines, students may feel slighly ungrounded, in that the splines are based on Bernstein polynomials which can appear mysterious. Of course, once graphs of the Berstein polynomials are explained, students feel more at ease.

However, there is a purely geometric construction for Bezier splines which does not rely on any polynomial formulation, and is extremely easy to understand. The DeCastlejau method is an algorithm which performs repeated bi-linear interpolation to compute splines of any order.

In Section 2, we dicuss the DeCastlejau method. In Section 3, we give instructions on how to run the Java applets, and in Section 4 we conclude with minor remarks on implementation issues.

2. The DeCastlejau Method

We start with a quick review of bilinear interpolation. For bilinear interpolation, we start with 4 points in space, P00, P01, P10, and P11. We parameterize the two dimensional surface with variables u and v, which are in the range [0,1]. The parameterization is as follows:

Let L(u) = (1-u)*P00 + (u)*P10

Let R(u) = (1-u)*P01 + (u)*P11

Then a point P is in the bilinear patch if:

P(u,v) = (1-v)*L(u) + v*R(u)

Intuitively, we are doing interpolation down the left and right edges of the quadrilateral, and then interpolating across. A complete description of the bilinear patch can be easily found in a book on curves and surfaces, the web, or a graphics text.

Notice the DeCastlejau Method reduces grid cell down to a single point. That is, it takes 2x2 nodes (one cell), and produces a single point. The DeCasteljau takes advantage of this simple fact.

Consider C[0], a N x N grid of control points. Suppose u and v are fixed. We can now perform bilinear interpolation on each individual grid cell of C[0]. The result is (N-) x N1) new points, which form a grid of new control points. We can repeat this process N-1 times until we have a 1x1 grid of control points. That is, we are left with a single point. This point is on the Nth order Bezier spline defined by the control points C[0].

More formally:

For now, fix u and v (u,v in the range [0,1])

C[0][i,j] = an N x N grid of control points (i,j in the range 1..N)

C[1][i,j] = an (N-1) x (N-1) grid of control points (i,j in the range 1..N-2)

C[2][i,j] = an (N-2) x (N-2) grid of control points (i,j in the range 1..N-2)

etc.

C[N-1][i,j] = a single point

So we have

C[k][i,j] = a (N-k) x (N-k) grid

where C[k][i,j] = The bilinear interpolation of the grid cell at C[k-1][i,j] using parameters u and v. Specificaly, C[k][i,j] is the bilinear interpolation is over the following four points:

C[k-1][i,j]

C[k-1][i+1,j]

C[k-1][i,j+1]

C[k-1][i+1,j+1]

Now, if we let u and v vary, the final point C[N-1][i,j] will move over the entire Bezier patch.

The DeCasteljau method also generalizes to M x N control points. In this case, the repeat bilinear interpolation will eventually collapse the grid down to a row (or column) of points. The interpoltation then continues as linear interpolation in one dimension. Repeated one-dimensional interpolation then reduces the row (or column) of points down to a single point on the surface.

In the M x N case, the resulting surfaces is an (M-1) by (N-1) degree Bezier surface. That is, in one direction, the surface has (M-1) order Bezier curves, and in the other direction it has (N-1) order Bezier curves.

The connection between the DeCastleJau method and Bernstein polynomals can be found in most books on curves and surfaces. We happen to like the book Curves and Surfaces for CAGD by DeFarin. Another books (more encyclopedic) is The NURBS Book by Les Piegl and Wayne Tiller.

3. The DeCastlejau Applet

To run the Java applet, you first must type in M and N which determine the size of the initial grid of control points. We suggest values between 1 and 5. Larger values are acceptable, but 6th order splines are extremely smooth so it's hard to get surfaces with interesting features unless you move the control points very far. You can then type in the size of the main window. Typically values around 400x400 to 500x500 are good. You'll need a monitor at 800x600 to view all the windows comfortably.

Clink on the "Make the Grid" button, and wait a few seconds.. A main window and a series of control windows will appear. A default grid is created. It is completely flat, and initially lies in the x-y plane. The z axis is directly into the screen.

The Global Rotation window contains 6 buttons to rotate the grid along any of the primary 3 axes. These axes are global, and are therefore fixed with respect to the view-screen.

The Global Translation window also contains 6 buttons which can translate the grid along any of the xyz axes. Once again, the translations are in global coordinates, so their effect is always the same with respect to the viewer.

In the upper right, is the Node Editing window. Clicking on one of the buttons will select a node of the control grid. That grid can then be translated by the 6-button cluster. The node translations are in local coordinates. So if you do a global rotation, the translation directions rotate with the grid itself. For example, z in local coordinates is always "up and down" with repect to the grid.

Finally, in the lower right is the Mode window. The top three buttons of the mode window determine what is drawn in the main window. In Surface Mode, the main window draws the Bezier surface as a wireframe. In Base Grid mode, only the original control points are shown. In Base+Surface mode, both the control points and the Bezier surface are drawn.

In Trace mode, you can actually see the DeCasteljau method in action. Drag the mouse in the square below the mode buttons. This square represents the unit square for parameters u and v. In the main window, you will see each grid which results from repeated bilinear interpolation. Finally, you'll see a single point marked by a small "+" symbol. That is a point on the Bezier surface. By dragging the mouse around, you can see how a point in (u,v) space is mapped onto the Bezier surface. You can also see all of the intermediate bilinear interpolations.

The remaining two buttons simple expand or contract the view of the main window.

You can run the Applet here. Browsable source is also available.

A slower, but less flickery version of the same Applet is here, with source code.

4. Implementation

The DeCastlejau method is extremely simple, but very slow. Notice that for an NxN grid, finding a single point on the surface requires

O( N^2 + (N-1)^2 + (N-2)^2 + .... +1) runs of the bilinear interpolater.

This reduces down to O(N^3) operations just to compute a single point on the surface. Since we need O(N^2) points to draw the surface, we end up with a run time of O(N^5). So, typically, running the Java applet in Surface mode is extremely slow. Therefore, the DeCasteljau method is not useful in practice, and one should return to the Berstein polynomial formulation. Fortunately, though, the other modes, such as Trace are very fast.

We implemented two versions of the DeCastlejau method. The first method has a very fast Trace mode, but is rather flickery. To reduce flicker, we attempted to use off-screen buffering. Unfortunately, Java is fairly slow in blitting, so the second version of the applet has a slow trace mode.

5. Future Enhancements

In the future it would be nice to add a few extra features. First of all it would be nice to reduce flicker in Trace mode, but keep execution fast. Currently, it is unclear how to do this in Java. Another feature which would be nice, would be to allow the user to sketch on the surface in trace mode. The user could then gain a feel for the surface by drawing a mesh him or herself.

Perhaps a solution to the problems would be to re-implement everything in OpenGL. Then speed would not be an issue, and there would be additional advantages such as the possibility of hidden surface removal or transparency. For example, drawing each intermediate grid as a semi-transparent surface would be quite interesting.