Tessellation of 4x4 Bezier Patches for
the Intel Pentium III Processor

Contents

Introduction to Bezier Curves and Surfaces Data Structures and Classes Surface Normal Calculation

This month, we take a look at optimizing content based upon parametric surfaces. To do this we concentrate on a specific case, 4x4 Bezier patches. By creating an optimized engine that incorporates tessellated surfaces, we can exploit features such as continuous LOD and non-rigid body deformation. This article features the work of Ronen Zohar, a member of Intel Israel's Media Team, who has experience with a wide range of 3D engine optimizations under his belt, including Intel's Processor Specific Graphics Pipeline for Direct3D since release 6.

With increased processor power, previous offline 3D tasks, such as dealing with high-order surfaces, can now be performed at run-time. A big advantage of high-order surfaces is that their relatively small data set makes them perfect for bandwidth-limited Internet applications. Since current 3D HW can render triangles only, we must generate triangles from the high-order surface using a process called “tessellation.” In this article, we show how to perform uniform tessellation of 4x4 Bezier surfaces (or patches), using the SIMD power of the Pentium III processor’s Streaming SIMD Extensions. Our implementation is written in C++ using the Streaming SIMD Extensions support classes and the Intel C/C++ compiler.

Introduction to Bezier Curves and Surfaces

Bezier curves are parametric curves defined by a set of n+1 control points (P₀-P_n), which define the “basic shape” of the curve, and a parameter (t), in the range of [0..1]. The mathematical representation of a Bezier curve is:

where the polynomials, B_i,n, (called Bezier basis functions) are defined as:

Bezier curves are polynomials of n-th degree that interpolate between the control points, where C(0) = P₀ and C(1) = P_n. 

Bezier surfaces are two-parameter expansions to the Bezier curve concept. Bezier surfaces are defined by an (n+1) x (m+1) matrix of control points (P), which define the “basic shape” of the surface, and two parameters (s and t), both in the range [0..1]. The mathematical representation of a Bezier surface is:

Lighting and reflection mapping calculations require the normal vector for each surface point (s, t). To calculate this vector, we first differentiate the surface equation with respect to s and t. The resultant partial derivatives define two vectors in the plane tangent to the surface at (s, t). The normal vector for the surface at this point is the cross product of these two tangent vectors:

In this paper, we deal with 4x4 Bezier curves, which are bi-cubic polynomials. The basis functions and their derivatives for the n=3 case are:

                    

The Tessellation Process

There are three basic steps in the tessellation process: taking samples of the parametric surface, connecting these samples into triangles, and generating the tessellated surface vertices.

Many techniques and algorithms deal with the problem of sampling the parametric surface. Some are based on the surface curvature (the smaller the surface curvature, the fewer triangles you need to approximate the surface shape). We use the simplest algorithm, which uniformly divides the [0…1]² (s, t) plane into some tessellation level , and then samples the surface at these points. Note that we designed our data structures so that any other tessellation-sampling algorithm can be used instead of our simple algorithm.

After determining the sample points, we precalculate the basis function values at these sample points and generate an indices list that accompanies the tessellation data. This indices list describes the triangle connectivity of the surface sample points that will be generated by the tessellation process. The indices list will be submitted to the rasterizer, along with the surface sample points, in order to render the tessellated surface.

We can use two methods to generate the tessellated surface vertices. The simplest method is to compute the surface position and normal in object space (the space where the control points are defined), and then feed these vertices to the triangle transform and lighting routines. A more complex, but faster, method is to transform the control points to screen space and tessellate using the transformed control points. In our case, we will need 16 transformations, regardless of the number of vertices generated by the tessellation process.  The two drawbacks of the second method are:

1. For small vertex counts, it is cheaper to transform only an already tessellated surface.
2. Lighting calculations sometimes require object or world space position. In this case, we will have to tessellate once for screen space and once for object/world space.

We’ve implemented only the second method, but the implementation of the first method can be done easily by commenting the transformation and lighting calculations from the routines.

________________________________________________________________

Data Structures and Classes