Everybody who works in the graphic industry knows about Bresenham’s line drawing algorithm. And we all apply, every time it's possible, his simple and power full principle: compute a step and use it to climb, and climb, and climb…

Let’s try one more time. Let’s find out how much this elegant solution can help us in the fashionable problem of tessellating Bézier patches.

Recently, a handful of articles have been published dealing with Bézier patches :

> Tessellation of 4x4 Bezier Patches for the Intel Pentium III Processor, Haim Barad, Gamasutra

> Putting Curved Surfaces to Work on the Nintendo 64, DeLoura, Game Developer Magazine, November 1999

> Curved Surfaces Using Bézier Patches, Gabe Kruger, Gamasutra.

> Implementing Curved Surface Geometry, Brian Sharp, Game Developer Magazine, June 1999

> Optimizing Curved Surface Geometry, Brian Sharp, Game Developer Magazine, July 1999

Note: My goal is not to repeat what you’ve probably already read in those papers. Rather, I simply want to add a stone to the building by sharing with you my desire to build a fast tesselator adapted to a certain use. For this reason, and if you are not familiar with curved surfaces, I advise you to take a look at the references at the end of this article.

The ambition of this article is to provide a fully functional solution for tessellating Béziers patches. This means computing vertices, normals and UV coordinates.

If you are looking for algorithms to tessellate a patch, you will find two families with their variants: direct evaluation and recursive subdivision. Both have pros and cons and, as always, there is not a good and a bad solution. But there is one that best matches your needs. I’ve chosen to work on the first family, as I thought that it has a reasonable potential over optimization.

We will start with some math consideration. (I won’t give here the demonstrations of the mathematical tools we will use. Those tools are quite simple and you won’t have any problems finding in your favorite literature a demonstration of those tools).

Vertex generation

Our starting point to define a vertex (shortened Vtx) generated from a patch is the following equation:

Where:

For more details have a look at pages 186-189 of 3D Computer Graphics by Alan Watt. A quick implementation is shown in listing 1.

 Here we are. I think it’s quite simple, don’t you? Now, how could one improve this? This is a fully incremental operation. So, we expect to be able to use a result (a vertex) to compute the next one:

And:


Our goal is simple: find f and g.

Let’s have a little break here. We must care about two things concerning optimization: the first one is to reduce the number of calculation. The second one is to reduce the complexity of theses operations. Thinking in terms of scalar operation has no more sense today. All of today’s popular platforms do have some floating point SIMD piece of hardware. Both PC/MAC and consoles handle 4D vector operations. Some of theses operations such as dot product and cross product are not always well supported by the vector floating points ALUs. As you’ve noticed, the inner loop is composed of 4 scalar dot products or one vector dot product. And as we will see later, normal calculation needs a cross product. Keep in mind that the tessellator will be optimized in order to get maximum performance for SIMD architectures.

>>>Continued