See what's going on with flipcode! 
Polygon Tessellation In OpenGL by (04 April 2001) 
Return to The Archives 
Introduction

Prerequisites: A basic knowledge of OpenGL; GLU 1.2. OpenGL itself is only capable of directly rendering convex polygons such as triangles, triangle fans, etc. More complex objects, through tessellation, must be subdivided into these simple convex polygons before they can be displayed. Luckily for us, the GLU (OpenGL Utility Library) contains an easy solution for polygon tessellation of concave polygons, polygons with holes, or polygons whose sides intersect. Basically, the GLU routines are fed a bunch of complicated vertex data that make up the contours of a complex polygon, which are then calculated and spit out as neat, bitesize convex polygons that OpenGL will have no problem displaying. 
How It Works

Here's a synopsis of how the tessellation works. The first thing we need to do is to use the gluNewTess(void) routine to create a new tessellation object, the basis for all the work we'll do, and return a GLUtesselator* pointer to it. It's possible to create more than one tessellation object, perhaps to have different objects with different sets of properties or callback functions, but most applications reuse the same one for different polygons and change properties for the single tessellation object when needed. Once the tessellation object is created, callback functions for that object have to be specified by using the gluTessCallback( ) routine. These callback functions will be called by GLU in certain instances during the tessellation of our polygons. Such instances may include when a vertex has to be drawn, or when two sides of a polygon intersect and a new vertex has to be calculated. The definition of gluTessCallback( ) is:
What this routine does is attach the fn function to the tessellation object tessobj. The function fn can either be an OpenGL function or a userdefined function. The type of the callback function is determined by type. We'll only be working with the types GLU_TESS_VERTEX (invokes the drawing of a vertex of the polygon), GLU_TESS_BEGIN (starts a new polygon), GLU_TESS_END (ends the current polygon), and GLU_TESS_COMBINE (calculates a new vertex if sides intersect). For a complete listing of the possible tessellation callback function types, see The OpenGL Programming Guide. After we specify the callback functions, we have to specify tessellation properties with the gluTessProperty( ) routine. The definition of gluTessProperty( ) is:
For the tessellation object tessobj, value is assigned to property. property can be GLU_TESS_BOUNDARY_ONLY, GLU_TESS_TOLERANCE, or GLU_TESS_WINDING_RULE. We'll be working solely with the property GLU_TESS_WINDING_RULE, which deals with the winding numbers and winding rule of the tessellation. The winding rule defines which contours of a polygon are "interior," or "filled," and which are "exterior," or "cut out," and are especially important when tessellating polygons with holes. A winding number is assigned to every contour of a polygon. In one of the polygons we'll use in an example, a quad with a triangle cut out of it, the quad itself will have a winding number of 1 while the triangle will have a winding number of 2. Because we'll be using the GLU_TESS_WINDING_ODD winding rule value for value, only contours with an odd winding number will be filled and it will seem like the triangle contour with the even winding number is actually cut out of the polygon. Click here for a diagram from The OpenGL Programming Guide that is great for showing how the winding rule can significantly affect the tessellation of polygons. Finally, we can now begin polygon definition. These two routines begin and end a polygon, and surround the definition of one or more contours:
These two routines begin and end a single contour, and go inside a polygon's definition:
Within a contour's definition, this routine is called to specify and store a vertex for the current contour:
coords is the data for a single vertex coordinate, and vertex_data is the pointer containing the vertex information (coordinates, color, texture coords, etc.) that's later passed to the function associated with GLU_TESS_VERTEX. It is essential to understand the differences between these two parameters: coords is used for the tessellation and contains only coordinate data. vertex_data is a pointer that is used for rendering (and later passed to the GLU_TESS_VERTEX callback function), and contains not only the coordinate data, but also color, texture, and normals data. After we're done with all the polygon tessellations we need, we can destroy the tessellation object by making a call to:
That's it! To sum it all up, we: 1. Create the tessellation object 2. Specify callback functions 3. Specify tessellation propertieswinding rule, etc. 4. Initialize the polygons and the contours of the polygons; call gluTessVertex() 5. Delete the tessellation object 
The Code

First we define the data for our polygons. In our example there are going to be
two polygons: a star (one contour) and a quad with a triangle "cut out" of it
(two contours). You can simply declare them in the code like this, but if you
want to be neat, inputting the data from a file might be best. You probably
noticed that in the arrays, there is extra information (xyz + rgb)a color
value for each vertex. As we'll see later, both the coordinate data and color
data will be stored in the vertex_data parameter of gluTessVertex().
This is a class we'll be using. All of the GLU tessellation routines we need are encapsulated in this very simple class:
Tess_Poly::Init() sets up everything for basic tessellation. It creates the tessellation objects and specifies the callback functions. GLU_TESS_BEGIN and GLU_TESS_END are pointed to the OpenGL functions glBegin( ) and glEnd( ), respectively. GLU_TESS_COMBINE is associated with a userdefined function, combineCallback( ), which will be defined later. GLU_TESS_VERTEX is also associated with a userdefined function, vertexCallback, which will also be defined and explained later.
Tess_Poly::Set_Winding_Rule( ) simply sets the winding rule to the value of winding_rule for the current polygon.
Tess_Poly::Render_Contour( ) renders a full contour of a polygon. obj_data refers to the array that contains all the vertex data for the contour. For what we need, the vertex data will include the vertex coordinate and color value. num_vertices is the number of vertices for the contour.
Tess_Poly::Begin_Polygon( ) initializes a new polygon.
Tess_Poly::End_Polygon( ) ends a polygon.
Tess_Poly::Begin_Contour( ) initializes a new contour of the current polygon.
Tess_Poly::End_Contour( ) ends the current contour.
Tess_Poly::End( ) deletes the tessellation object.
Before we put this code together, we have to define the combineCallback( ) and vertexCallback( ) functions. combineCallback( ) returns new vertex coordinates and color data if the GLU_TESS_COMBINE is invoked. The new vertex is created by referencing the contents of vertex_data. coords is the location of the new vertex. weight[4] is used to interpolate the average RGB value for newly created vertices.
Now we have to define our vertex callback function, vertexCallback( ). This function creates a pointer to the vertex's data (the vertex_data pointer) that is passed to it and references the coordinate and color data.

The Final Product


Conclusion

I hope the basics of tessellation are now easy to understand. Here are a few
suggestions for extending the code: 1. Add the ability to texture your tessellated polygons. For an example, see my tessellation demo (tessellation demo/src) which dynamically updates the texture coordinates for a polygon 2. Add the ability to specify a normal for your tessellated polygons. Search for gluTessNormal( ). 3. Use display lists if your polygon data is always static. For much more information on polygon tessellation and tessellation properties, please refer to The OpenGL Programming Guide, sometimes known as "The Red Book." Have any questions, comments, or complaints? Please email me at lpSoftware@gdnmail.net. Visit my website at http://lpsoftware.cfxweb.net. This article is © 2001 Martin Estevao. This article may not be reprinted without the author's consent. 
