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, bite-size 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:


void gluTessCallback(GLUtesselator *tessobj, Glenum type, void (*fn)( ));


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 user-defined 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:


void gluTessProperty(GLUtesselator *tessobj, Glenum property, Gldouble value);


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:


void gluTessBeginPolygon(GLUtesselator *tessobj, void *user_data);
void gluTessEndPolygon(GLUtesselator *tessobj);


These two routines begin and end a single contour, and go inside a polygon's definition:


void gluTessBeginContour(GLUtesselator *tessobj);
void gluTessEndContour(GLUtesselator *tessobj);


Within a contour's definition, this routine is called to specify and store a vertex for the current contour:


void gluTessVertex(GLUtesselator *tessobj, Gldouble coords[3], void *vertex_data);


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:


void gluDeleteTess(GLUtesselator *tessobj);


That's it! To sum it all up, we:

1. Create the tessellation object
2. Specify callback functions
3. Specify tessellation properties-winding 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().


//first polygon: a star-5 vertices and color information
GLdouble star[5][6] = { 0.6f,  -0.1f, -2.0f, 1.0f, 1.0f, 1.0f,
                        1.35f, 1.4f, -2.0f, 1.0f, 1.0f, 1.0f,
                        2.1f,  -0.1f, -2.0f, 1.0f, 1.0f, 1.0f,
                        0.6f, 0.9f, -2.0f, 1.0f, 1.0f, 1.0f,
                        2.1f, 0.9f, -2.0f, 1.0f, 1.0f, 1.0f };

//second polygon: a quad-4 vertices; first contour
GLdouble quad[4][6] = { 0.0f, 0.0f, 0.0f, 1.0f, 1.0f, 0.0f,
                        1.0f, 0.0f, 0.0f, 0.0f, 1.0f, 0.0f,
                        1.0f, 0.0f, 0.0f, 0.0f, 1.0f, 0.0f,
                        0.0f, 1.0f, 0.0f, 0.0f, 0.0f, 1.0f, };

//second polygon: a triangle-3 vertices; second contour
GLdouble tri[3][6] = { 0.3f, 0.3f, 0.0f, 0.0f, 0.0f, 0.0f,
                       0.7f, 0.3f, 0.0f, 0.0f, 0.0f, 0.0f,
                       0.5f, 0.7f, 0.0f, 0.0f, 0.0f, 0.0f, };


This is a class we'll be using. All of the GLU tessellation routines we need are encapsulated in this very simple class:


class Tess_Poly {

private:

GLUtesselator *tobj; // the tessellation object

public:

int Init(GLvoid);
int Set_Winding_Rule(GLenum winding_rule);
int Render_Contour(GLdouble obj_data[][6], int num_vertices);
int Begin_Polygon(GLvoid);
int End_Polygon(GLvoid);
int Begin_Contour(GLvoid);
int End_Contour(GLvoid);
int End(GLvoid);

};

Tess_Poly Poly;


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 user-defined function, combineCallback( ), which will be defined later. GLU_TESS_VERTEX is also associated with a user-defined function, vertexCallback, which will also be defined and explained later.


Tess_Poly::Init(GLvoid)
{
// Create a new tessellation object 
tobj = gluNewTess(); 

// Set callback functions
gluTessCallback(tobj, GLU_TESS_VERTEX, (GLvoid (*) ( )) &vertexCallback);
gluTessCallback(tobj, GLU_TESS_BEGIN, (GLvoid (*) ( )) &glBegin);
gluTessCallback(tobj, GLU_TESS_END, (GLvoid (*) ( )) &glEnd);
gluTessCallback(tobj, GLU_TESS_COMBINE, (GLvoid (*) ( ))&combineCallback);

return(1);
}


Tess_Poly::Set_Winding_Rule( ) simply sets the winding rule to the value of winding_rule for the current polygon.


Tess_Poly::Set_Winding_Rule(GLenum winding_rule)
{
// Set the winding rule
gluTessProperty(tobj, GLU_TESS_WINDING_RULE, winding_rule); 

return(1);
}


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::Render_Contour(GLdouble obj_data[][6], int num_vertices)
{
for (int x = 0; x < num_vertices; x++) //loop through the vertices
{
gluTessVertex(tobj, obj_data[x], obj_data[x]); //store the vertex
}

return(1);
}


Tess_Poly::Begin_Polygon( ) initializes a new polygon.


Tess_Poly::Begin_Polygon(GLvoid)
{
gluTessBeginPolygon(tobj, NULL);

return(1);
}


Tess_Poly::End_Polygon( ) ends a polygon.


Tess_Poly::End_Polygon(GLvoid)
{
gluTessEndPolygon(tobj);

return(1);
}


Tess_Poly::Begin_Contour( ) initializes a new contour of the current polygon.


Tess_Poly::Begin_Contour(GLvoid)
{
gluTessBeginContour(tobj);

return(1);
}


Tess_Poly::End_Contour( ) ends the current contour.


Tess_Poly::End_Contour(GLvoid)
{
gluTessEndContour(tobj);

return(1);
}


Tess_Poly::End( ) deletes the tessellation object.


Tess_Poly::End(GLvoid)
{
gluDeleteTess(tobj);

return(1);
}


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.


void CALLBACK combineCallback(GLdouble coords[3], Gldouble *vertex_data[4],
GLfloat weight[4], GLdouble **dataOut)
{
GLdouble *vertex;

vertex = (GLdouble *) malloc(6 * sizeof(GLdouble));
vertex[0] = coords[0];
vertex[1] = coords[1];
vertex[2] = coords[2];

for (int i = 3; i < 6; i++)
{
vertex[i] = weight[0] * vertex_data[0][i] +
indent indweight[1] * vertex_data[1][i] +
indent indweight[2] * vertex_data[2][i] +
indent indweight[3] * vertex_data[3][i];
}

*dataOut = vertex;
}


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.


void CALLBACK vertexCallback(GLvoid *vertex)
{
GLdouble *ptr;

ptr = (GLdouble *) vertex;
glVertex3dv((GLdouble *) ptr);
glColor3dv((GLdouble *) ptr + 3);
}


The Final Product 





//render the first polygon: the textured star

//create tess object; create callback functions
Poly.Init(); 
//set winding rule to positive
Poly.Set_Winding_Rule(GLU_TESS_WINDING_POSITIVE); 
Poly.Begin_Polygon(); 
Poly.Begin_Contour();
Poly.Render_Contour(star, 5); 
Poly.End_Contour();
Poly.End_Polygon();

//render the second polygon: triangle cut out of a quad

//set winding rule to odd
Poly.Set_Winding_Rule(GLU_TESS_WINDING_ODD); 
//begin the new polygon
Poly.Begin_Polygon(); 
Poly.Begin_Contour();
Poly.Render_Contour(quad, 4); 
Poly.End_Contour();
Poly.Begin_Contour();
Poly.Render_Contour(tri, 3); 
Poly.End_Contour();
Poly.End_Polygon();
//delete the tess object
Poly.End();


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 re-printed without the author's consent.
 

Copyright 1999-2008 (C) FLIPCODE.COM and/or the original content author(s). All rights reserved.
Please read our Terms, Conditions, and Privacy information.