Winding Numbers and Winding Rules
For a single contour, the winding number of a point is the signed number of revolutions we make around that point while traveling once around the contour (where a counterclockwise revolution is positive and a clockwise revolution is negative). When there are several contours, the individual winding numbers are summed. This procedure associates a signed integer value with each point in the plane. Note that the winding number is the same for all points in a single region.
Figure 11-2 shows three sets of contours and winding numbers for points inside those contours. In the set at the left, all three contours are counterclockwise, so each nested interior region adds 1 to the winding number. In the middle set, the two interior contours are drawn clockwise, so tne winding number decreases and actually becomes negative.
Figure 11-2 Winding Numbers for Sample Contours
The winding rule classifies a region as inside if its winding number belongs to the chosen category (odd, nonzero, positive, negative, or "absolute value greater than or equal to 2"). The odd and nonzero rules are common ways to define the interior. The positive, negative, and "absolute value > 2" winding rules have some limited use for polygon CSG (computational solid geometry) operations.
The program tesswind.c demonstrates the effects of winding rules. The four sets of contours shown in Figure 11-3 are rendered. The user can then cycle through the different winding rule properties to see their effects. For each winding rule, the dark areas represent interiors. Note the effects of clockwise and counterclockwise winding.
CSG Uses for Winding Rules
GLU_TESS_WINDING_ODD and GLU_TESS_WINDING_NONZERO are the most commonly used winding rules. They work for the most typical cases of shading.
The winding rules are also designed for CSG operations, making it easy to find the union, difference, or intersection (Boolean operations) of several contours.
Figure 11-3 How Winding Rules Define Interiors
First, assume that each contour is defined so that the winding number is 0 for each exterior region and 1 for each interior region. (Each contour must not intersect itself.) Under this model, counterclockwise contours define the outer boundary of the polygon, and clockwise contours define holes. Contours may be nested, but a nested contour must be oriented oppositely from the contour that contains it.
If the original polygons do not satisfy this description, they can be converted to this form by first running the tessellator with the GLU_TESS_ BOUNDARY_ONLY property turned on. This returns a list of contours satisfying the restriction just described. By creating two tessellator objects, the callbacks from one tessellator can be fed directly as input to the other.
Given two or more polygons of the preceding form, CSG operations can be implemented as follows:
• UNION—To calculate the union of several contours, draw all input contours as a single polygon. The winding number of each resulting region is the number of original polygons that cover it. The union can be extracted by using the GLU_TESS_WINDING_NONZERO or GLU_TESS_WINDING_POSITIVE winding rule. Note that with the nonzero winding rule, we would get the same result if all contour orientations were reversed.
• INTERSECTION—This works only for two contours at a time. Draw a single polygon using two contours. Extract the result using GLU_TESS_ WINDING_ABS_GEQ_TWO.
• DIFFERENCE—Suppose you want to compute A diff (B union C union D). Draw a single polygon consisting of the unmodified contours from A, followed by the contours of B, C, and D, with their vertex order reversed. To extract the result, use the GLU_TESS_WINDING_POSITIVE winding rule. (If B, C, and D are the result of a GLU_TESS_BOUNDARY_ ONLY operation, an alternative to reversing the vertex order is to use gluTessNormal() to reverse the sign of the supplied normal.)
Other Tessellation Property Routines
There are also complementary routines, which work alongside gluTessPropertyO. gluGetTessPropertyO retrieves the current values of tessellator properties. If the tessellator is being used to generate wireframe outlines instead of filled polygons, gluTessNormal() can be used to determine the winding direction of the tessellated polygons.
void gluGetTessProperty(GLUtesselator *tessobj, GLenum property,GLdouble * value);
For the tessellation object lessobj, the current value of property is returned to value. Values for property and value are the same as for gluTessPropertyO.
void gluTessNormal(GLUtesselator *tessobj, GLdouble x, GLdouble y, GLdouble z);
For the tessellation object tessobj, gluTessNormal() defines a normal vector, which controls the winding direction of generated polygons. Before tessellation, all input data is projected into a plane perpendicular to the normal. Then, all output triangles are oriented counterclockwise, with respect to the normal. (Clockwise orientation can be obtained by reversing the sign of the supplied normal.) The default normal is (0, 0, 0).
If you have some knowledge about the location and orientation of the input data, then using gluTessNormal() can increase the speed of the tessellation. For example, if you know that all polygons lie on the .xy-plane, call gluTessNormal(iessofr/, 0, 0, 1).
As stated above, the default normal is (0, 0, 0), and its effect is not immediately obvious. In tnis case, it is expected that the input data lies approximately in a plane, and a plane is fitted to the vertices, no matter how they are truly connected. The sign of the normal is chosen so that the sum of the signed areas of all input contours is non-negative (where a counterclockwise contour has a positive area). Note that if the input data does not lie approximately in a plane, then projection perpendicular to the computed normal may substantially change the geometry.
Polygon Definition
After all the tessellation properties have been set and the callback actions have been registered, it is finally time to describe the vertices that comprise input contours and tessellate the polygons.
void gluTessBeginPolygon(GLUtesselator *tessobj, void *user_data); void gluTessEndPolygon(GLUtesselator *tessobj);
Begins and ends the specification of a polygon to be tessellated and associates a tessellation object, tessobj, with it. user_data points to a user-defined data structure, which is passed along all the GLU_TESS__*_DATA callback functions that have been bound.
Calls to gluTessBeginPolygon() and g!uTessEndPolygon() surround the definition of one or more contours. When gluTessEndPolygonQ is called,the tessellation algorithm is implemented, and the tessellated polygons are generated and rendered. The callback functions and tessellation properties that were bound and set to the tessellation object using gluTessCallback() and eluTessProperty() are used.
void glulessBeginContour(GLUtesselator ktessobj); void gluTessEndContour(GLUtesselator *tessobj);
Begins and ends the specification of a closed contour, which is a portion of a polygon. A closed contour consists of zero or more calls to gluTessYertex(), which defines the vertices. The last vertex of each contour is automatically linked to the first.
Specifies a vertex in the current contour for the tessellation object, coords contains the three-dimensional vertex coordinates, and vertex_data is a pointer that’s sent to the callback associated with GLU_TESS_VERTEX or GLU_rESS_VERTEX_DATA. Typically, vertex_data contains vertex coordinates, surface normals, texture coordinates, color information, or whatever else the application may find useful.
In the program tess.c, a portion of which is shown in Example 11-3, two polygons are defined. One polygon is a rectangular contour with a triangular hole inside, and the other is a smooth-shaded, self-intersecting, five-pointed star. For efficiency, both polygons are stored in display lists. The first polygon consists of two contours; the outer one is wound counterclockwise, and the "hole" is wound clockwise. For the second polygon, the star array contains both the coordinate and color data, and its tessellation callback, vertexCallback(), uses both.
It is important that each vertex is in a different memory location because the vertex data is not copied by gluTessVertex(); only the pointer (vertex_ data) is saved. A program that reuses the same memory for several vertices may not get the desired result.
Note: In gluTessVertex(), it may seem redundant to specify the vertex coordinate data twice, for both the coords and vertex_data parameters; however, both are necessary, coords refers only to the vertex coordinates. vertexjdata uses the coordinate data, but may also use other information for each vertex.
Example 11-3 Polygon Definition: tess.c
Deleting a Tessellation Object
If you no longer need a tessellation object, you can delete it and free all associated memory with gluDeleteTess().
void gluDeleteTess(GLUtesselator *tessobj);
Deletes the specified tessellation object, tessobj, and frees all associated memory.
Tessellation Performance Tips
For best performance, remember these rules:
• Cache the output of the tessellator in a display list or other user structure. To obtain the post-tessellation vertex coordinates, tessellate the polygons while in feedback mode.
• Use gluTessNormalQ to supply the polygon normal.
• Use the same tessellator object to render many polygons, rather than allocate a new tessellator for each one. (In a multithreaded, multiprocessor environment, you may get better performance using several tessellators.)
Describing GLU Errors
The GLU provides a routine for obtaining a descriptive string for an error code. This routine is not limited to tessellation but is also used for NURBS and quadrics errors, as well as for errors in the base GL.
Backward Compatibility
If you are using the 1.0 or 1.1 version of GLU, you have a much less powerful tessellator. The 1.0/1.1 tessellator handles only simple nonconvex polygons or simple polygons containing holes. It does not properly tessellate intersecting contours (no COMBINE callback) or process per-polygon data. The 1.0/1.1 tessellator still works in either GLU 1.2 or 1.3, but its use is no longer recommended.
The 1.0/1.1 tessellator has some similarities to the current tessellator. gluNewTess() and gluDeleteTess() are used for both tessellators. The main vertex specification routine remains gluTessVertex(). The callback mechanism is controlled by gluTessCallback(), although only five callback functions can be registered, a subset of the current 12.
Here are the prototypes for the 1.0/1.1 tessellator:
void gluBeginPolygon(GLUtriangulatorOb) *tessobj)f-’r.
void gluNextContour(GLUtriangulatorObj *tessohj, GLenum type);
void gluEndPolygon(GLUtriangulatorObj * tessobj);
The outermost contour must be specified first, and it does not require an initial call to gluNextContour(). For polygons without holes, only one contour is defined, and gluNextContour() is not used. If a polygon has multiple contours (that is, holes or holes within holes), the contours are specified one after the other, each preceded by gluNextContour(). gluTessVertexO is called for each vertex of a contour.
For gluNextContour(), type can be GLU_EXTERIOR, GLUJNTERIOR, GLtJ_CCW, GLU_CVV, or GLU_UNKNOWN. These serve only as hints to the tessellation. If you get them right, the.tessellation might go faster. If you get them wrong, they’re ignored, and the tessellation still works. For polygons with holes, one contour is the exterior contour and the other is the interior. The first contour is assumed to be of type GLU_EXTERIOR. Choosing clockwise or counterclockwise orientation is arbitrary in three dimensions; however;· there are two different orientations in any plane, and the GLU_CCW and GLU_CW types should be used consistently. Use GLUJJNKNOWN if you don’t have a clue.
It is highly recommended that you convert GLU 1.0/1.1 code to the new tessellation interface for GLU 1.2 by following these steps:
1. Change references to the major data structure type from GLUtriangulatorObj to GLUtesselator. In GLU 1.2, GLUtriangulatorObj and GLUtesselator are defined to be the same type.
2. Convert gluBeginPolygon() to two commands: gluTessBeginPolygon() and gluTessBeginContour(). All contours must be explicitly started, including the first one.
3. Convert gluNextContour() to both gluTessEndContour() and gluTessBeginContour(). You have to end the previous contour before starting the next one.
4. Convert gluEndPolygon() to both gluTessEndContour() and gluTessEndPolygon(). The final contour must be closed.
5. Change references to constants to gluTessCallback(). In GLU 1.2, GLU_BEGIN, GLU_VERTEX, GLU_END, GLU_ERROR, and GLU_EDGE_FLAG are defined as synonyms for GLU_TESS_BEGIN, GLU_TESS_VERTEX, GLU_TESS_END, GLU_TESS_ERROR, and GLU_TESS_EDGE_FLAG.
