1/* 2*/ 3 4General Polygon Tesselation 5--------------------------- 6 7 This note describes a tesselator for polygons consisting of one or 8 more closed contours. It is backward-compatible with the current 9 OpenGL Utilities tesselator, and is intended to replace it. Here is 10 a summary of the major differences: 11 12 - input contours can be intersecting, self-intersecting, or degenerate. 13 14 - supports a choice of several winding rules for determining which parts 15 of the polygon are on the "interior". This makes it possible to do 16 CSG operations on polygons. 17 18 - boundary extraction: instead of tesselating the polygon, returns a 19 set of closed contours which separate the interior from the exterior. 20 21 - returns the output as a small number of triangle fans and strips, 22 rather than a list of independent triangles (when possible). 23 24 - output is available as an explicit mesh (a quad-edge structure), 25 in addition to the normal callback interface. 26 27 - the algorithm used is extremely robust. 28 29 30The interface 31------------- 32 33 The tesselator state is maintained in a "tesselator object". 34 These are allocated and destroyed using 35 36 GLUtesselator *gluNewTess( void ); 37 void gluDeleteTess( GLUtesselator *tess ); 38 39 Several tesselator objects may be used simultaneously. 40 41 Inputs 42 ------ 43 44 The input contours are specified with the following routines: 45 46 void gluTessBeginPolygon( GLUtesselator *tess ); 47 void gluTessBeginContour( GLUtesselator *tess ); 48 void gluTessVertex( GLUtesselator *tess, GLUcoord coords[3], void *data ); 49 void gluTessEndContour( GLUtesselator *tess ); 50 void gluTessEndPolygon( GLUtesselator *tess ); 51 52 Within each BeginPolygon/EndPolygon pair, there can be zero or more 53 calls to BeginContour/EndContour. Within each contour, there are zero 54 or more calls to gluTessVertex(). The vertices specify a closed 55 contour (the last vertex of each contour is automatically linked to 56 the first). 57 58 "coords" give the coordinates of the vertex in 3-space. For useful 59 results, all vertices should lie in some plane, since the vertices 60 are projected onto a plane before tesselation. "data" is a pointer 61 to a user-defined vertex structure, which typically contains other 62 information such as color, texture coordinates, normal, etc. It is 63 used to refer to the vertex during rendering. 64 65 The library can be compiled in single- or double-precision; the type 66 GLUcoord represents either "float" or "double" accordingly. The GLU 67 version will be available in double-precision only. Compile with 68 GLU_TESS_API_FLOAT defined to get the single-precision version. 69 70 When EndPolygon is called, the tesselation algorithm determines 71 which regions are interior to the given contours, according to one 72 of several "winding rules" described below. The interior regions 73 are then tesselated, and the output is provided as callbacks. 74 75 76 Rendering Callbacks 77 ------------------- 78 79 Callbacks are specified by the client using 80 81 void gluTessCallback( GLUtesselator *tess, GLenum which, void (*fn)()); 82 83 If "fn" is NULL, any previously defined callback is discarded. 84 85 The callbacks used to provide output are: /* which == */ 86 87 void begin( GLenum type ); /* GLU_TESS_BEGIN */ 88 void edgeFlag( GLboolean flag ); /* GLU_TESS_EDGE_FLAG */ 89 void vertex( void *data ); /* GLU_TESS_VERTEX */ 90 void end( void ); /* GLU_TESS_END */ 91 92 Any of the callbacks may be left undefined; if so, the corresponding 93 information will not be supplied during rendering. 94 95 The "begin" callback indicates the start of a primitive; type is one 96 of GL_TRIANGLE_STRIP, GL_TRIANGLE_FAN, or GL_TRIANGLES (but see the 97 notes on "boundary extraction" below). 98 99 It is followed by any number of "vertex" callbacks, which supply the 100 vertices in the same order as expected by the corresponding glBegin() 101 call. After the last vertex of a given primitive, there is a callback 102 to "end". 103 104 If the "edgeFlag" callback is provided, no triangle fans or strips 105 will be used. When edgeFlag is called, if "flag" is GL_TRUE then each 106 vertex which follows begins an edge which lies on the polygon boundary 107 (ie. an edge which separates an interior region from an exterior one). 108 If "flag" is GL_FALSE, each vertex which follows begins an edge which lies 109 in the polygon interior. "edgeFlag" will be called before the first 110 call to "vertex". 111 112 Other Callbacks 113 --------------- 114 115 void mesh( GLUmesh *mesh ); /* GLU_TESS_MESH */ 116 117 - Returns an explicit mesh, represented using the quad-edge structure 118 (Guibas/Stolfi '85). Other implementations of this interface might 119 use a different mesh structure, so this is available only only as an 120 SGI extension. When the mesh is no longer needed, it should be freed 121 using 122 123 void gluDeleteMesh( GLUmesh *mesh ); 124 125 There is a brief description of this data structure in the include 126 file "mesh.h". For the full details, see L. Guibas and J. Stolfi, 127 Primitives for the manipulation of general subdivisions and the 128 computation of Voronoi diagrams, ACM Transactions on Graphics, 129 4(2):74-123, April 1985. For an introduction, see the course notes 130 for CS348a, "Mathematical Foundations of Computer Graphics", 131 available at the Stanford bookstore (and taught during the fall 132 quarter). 133 134 void error( GLenum errno ); /* GLU_TESS_ERROR */ 135 136 - errno is one of GLU_TESS_MISSING_BEGIN_POLYGON, 137 GLU_TESS_MISSING_END_POLYGON, 138 GLU_TESS_MISSING_BEGIN_CONTOUR, 139 GLU_TESS_MISSING_END_CONTOUR, 140 GLU_TESS_COORD_TOO_LARGE, 141 GLU_TESS_NEED_COMBINE_CALLBACK 142 143 The first four are obvious. The interface recovers from these 144 errors by inserting the missing call(s). 145 146 GLU_TESS_COORD_TOO_LARGE says that some vertex coordinate exceeded 147 the predefined constant GLU_TESS_MAX_COORD in absolute value, and 148 that the value has been clamped. (Coordinate values must be small 149 enough so that two can be multiplied together without overflow.) 150 151 GLU_TESS_NEED_COMBINE_CALLBACK says that the algorithm detected an 152 intersection between two edges in the input data, and the "combine" 153 callback (below) was not provided. No output will be generated. 154 155 156 void combine( GLUcoord coords[3], void *data[4], /* GLU_TESS_COMBINE */ 157 GLUcoord weight[4], void **outData ); 158 159 - When the algorithm detects an intersection, or wishes to merge 160 features, it needs to create a new vertex. The vertex is defined 161 as a linear combination of up to 4 existing vertices, referenced 162 by data[0..3]. The coefficients of the linear combination are 163 given by weight[0..3]; these weights always sum to 1.0. All vertex 164 pointers are valid even when some of the weights are zero. 165 "coords" gives the location of the new vertex. 166 167 The user must allocate another vertex, interpolate parameters 168 using "data" and "weights", and return the new vertex pointer in 169 "outData". This handle is supplied during rendering callbacks. 170 For example, if the polygon lies in an arbitrary plane in 3-space, 171 and we associate a color with each vertex, the combine callback might 172 look like this: 173 174 void myCombine( GLUcoord coords[3], VERTEX *d[4], 175 GLUcoord w[4], VERTEX **dataOut ) 176 { 177 VERTEX *new = new_vertex(); 178 179 new->x = coords[0]; 180 new->y = coords[1]; 181 new->z = coords[2]; 182 new->r = w[0]*d[0]->r + w[1]*d[1]->r + w[2]*d[2]->r + w[3]*d[3]->r; 183 new->g = w[0]*d[0]->g + w[1]*d[1]->g + w[2]*d[2]->g + w[3]*d[3]->g; 184 new->b = w[0]*d[0]->b + w[1]*d[1]->b + w[2]*d[2]->b + w[3]*d[3]->b; 185 new->a = w[0]*d[0]->a + w[1]*d[1]->a + w[2]*d[2]->a + w[3]*d[3]->a; 186 *dataOut = new; 187 } 188 189 If the algorithm detects an intersection, then the "combine" callback 190 must be defined, and must write a non-NULL pointer into "dataOut". 191 Otherwise the GLU_TESS_NEED_COMBINE_CALLBACK error occurs, and no 192 output is generated. This is the only error that can occur during 193 tesselation and rendering. 194 195 196 Control over Tesselation 197 ------------------------ 198 199 void gluTessProperty( GLUtesselator *tess, GLenum which, GLUcoord value ); 200 201 Properties defined: 202 203 - GLU_TESS_WINDING_RULE. Possible values: 204 205 GLU_TESS_WINDING_ODD 206 GLU_TESS_WINDING_NONZERO 207 GLU_TESS_WINDING_POSITIVE 208 GLU_TESS_WINDING_NEGATIVE 209 GLU_TESS_WINDING_ABS_GEQ_TWO 210 211 The input contours parition the plane into regions. A winding 212 rule determines which of these regions are inside the polygon. 213 214 For a single contour C, the winding number of a point x is simply 215 the signed number of revolutions we make around x as we travel 216 once around C (where CCW is positive). When there are several 217 contours, the individual winding numbers are summed. This 218 procedure associates a signed integer value with each point x in 219 the plane. Note that the winding number is the same for all 220 points in a single region. 221 222 The winding rule classifies a region as "inside" if its winding 223 number belongs to the chosen category (odd, nonzero, positive, 224 negative, or absolute value of at least two). The current GLU 225 tesselator implements the "odd" rule. The "nonzero" rule is another 226 common way to define the interior. The other three rules are 227 useful for polygon CSG operations (see below). 228 229 - GLU_TESS_BOUNDARY_ONLY. Values: TRUE (non-zero) or FALSE (zero). 230 231 If TRUE, returns a set of closed contours which separate the 232 polygon interior and exterior (rather than a tesselation). 233 Exterior contours are oriented CCW with respect to the normal, 234 interior contours are oriented CW. The GLU_TESS_BEGIN callback 235 uses the type GL_LINE_LOOP for each contour. 236 237 - GLU_TESS_TOLERANCE. Value: a real number between 0.0 and 1.0. 238 239 This specifies a tolerance for merging features to reduce the size 240 of the output. For example, two vertices which are very close to 241 each other might be replaced by a single vertex. The tolerance 242 is multiplied by the largest coordinate magnitude of any input vertex; 243 this specifies the maximum distance that any feature can move as the 244 result of a single merge operation. If a single feature takes part 245 in several merge operations, the total distance moved could be larger. 246 247 Feature merging is completely optional; the tolerance is only a hint. 248 The implementation is free to merge in some cases and not in others, 249 or to never merge features at all. The default tolerance is zero. 250 251 The current implementation merges vertices only if they are exactly 252 coincident, regardless of the current tolerance. A vertex is 253 spliced into an edge only if the implementation is unable to 254 distinguish which side of the edge the vertex lies on. 255 Two edges are merged only when both endpoints are identical. 256 257 258 void gluTessNormal( GLUtesselator *tess, 259 GLUcoord x, GLUcoord y, GLUcoord z ) 260 261 - Lets the user supply the polygon normal, if known. All input data 262 is projected into a plane perpendicular to the normal before 263 tesselation. All output triangles are oriented CCW with 264 respect to the normal (CW orientation can be obtained by 265 reversing the sign of the supplied normal). For example, if 266 you know that all polygons lie in the x-y plane, call 267 "gluTessNormal(tess, 0.0, 0.0, 1.0)" before rendering any polygons. 268 269 - If the supplied normal is (0,0,0) (the default value), the 270 normal is determined as follows. The direction of the normal, 271 up to its sign, is found by fitting a plane to the vertices, 272 without regard to how the vertices are connected. It is 273 expected that the input data lies approximately in plane; 274 otherwise projection perpendicular to the computed normal may 275 substantially change the geometry. The sign of the normal is 276 chosen so that the sum of the signed areas of all input contours 277 is non-negative (where a CCW contour has positive area). 278 279 - The supplied normal persists until it is changed by another 280 call to gluTessNormal. 281 282 283 Backward compatibility with the GLU tesselator 284 ---------------------------------------------- 285 286 The preferred interface is the one described above. The following 287 routines are obsolete, and are provided only for backward compatibility: 288 289 typedef GLUtesselator GLUtriangulatorObj; /* obsolete name */ 290 291 void gluBeginPolygon( GLUtesselator *tess ); 292 void gluNextContour( GLUtesselator *tess, GLenum type ); 293 void gluEndPolygon( GLUtesselator *tess ); 294 295 "type" is one of GLU_EXTERIOR, GLU_INTERIOR, GLU_CCW, GLU_CW, or 296 GLU_UNKNOWN. It is ignored by the current GLU tesselator. 297 298 GLU_BEGIN, GLU_VERTEX, GLU_END, GLU_ERROR, and GLU_EDGE_FLAG are defined 299 as synonyms for GLU_TESS_BEGIN, GLU_TESS_VERTEX, GLU_TESS_END, 300 GLU_TESS_ERROR, and GLU_TESS_EDGE_FLAG. 301 302 303Polygon CSG operations 304---------------------- 305 306 The features of the tesselator make it easy to find the union, difference, 307 or intersection of several polygons. 308 309 First, assume that each polygon is defined so that the winding number 310 is 0 for each exterior region, and 1 for each interior region. Under 311 this model, CCW contours define the outer boundary of the polygon, and 312 CW contours define holes. Contours may be nested, but a nested 313 contour must be oriented oppositely from the contour that contains it. 314 315 If the original polygons do not satisfy this description, they can be 316 converted to this form by first running the tesselator with the 317 GLU_TESS_BOUNDARY_ONLY property turned on. This returns a list of 318 contours satisfying the restriction above. By allocating two 319 tesselator objects, the callbacks from one tesselator can be fed 320 directly to the input of another. 321 322 Given two or more polygons of the form above, CSG operations can be 323 implemented as follows: 324 325 Union 326 Draw all the input contours as a single polygon. The winding number 327 of each resulting region is the number of original polygons 328 which cover it. The union can be extracted using the 329 GLU_TESS_WINDING_NONZERO or GLU_TESS_WINDING_POSITIVE winding rules. 330 Note that with the nonzero rule, we would get the same result if 331 all contour orientations were reversed. 332 333 Intersection (two polygons at a time only) 334 Draw a single polygon using the contours from both input polygons. 335 Extract the result using GLU_TESS_WINDING_ABS_GEQ_TWO. (Since this 336 winding rule looks at the absolute value, reversing all contour 337 orientations does not change the result.) 338 339 Difference 340 341 Suppose we want to compute A \ (B union C union D). Draw a single 342 polygon consisting of the unmodified contours from A, followed by 343 the contours of B,C,D with the vertex order reversed (this changes 344 the winding number of the interior regions to -1). To extract the 345 result, use the GLU_TESS_WINDING_POSITIVE rule. 346 347 If B,C,D are the result of a GLU_TESS_BOUNDARY_ONLY call, an 348 alternative to reversing the vertex order is to reverse the sign of 349 the supplied normal. For example in the x-y plane, call 350 gluTessNormal( tess, 0.0, 0.0, -1.0 ). 351 352 353Performance 354----------- 355 356 The tesselator is not intended for immediate-mode rendering; when 357 possible the output should be cached in a user structure or display 358 list. General polygon tesselation is an inherently difficult problem, 359 especially given the goal of extreme robustness. 360 361 The implementation makes an effort to output a small number of fans 362 and strips; this should improve the rendering performance when the 363 output is used in a display list. 364 365 Single-contour input polygons are first tested to see whether they can 366 be rendered as a triangle fan with respect to the first vertex (to 367 avoid running the full decomposition algorithm on convex polygons). 368 Non-convex polygons may be rendered by this "fast path" as well, if 369 the algorithm gets lucky in its choice of a starting vertex. 370 371 For best performance follow these guidelines: 372 373 - supply the polygon normal, if available, using gluTessNormal(). 374 This represents about 10% of the computation time. For example, 375 if all polygons lie in the x-y plane, use gluTessNormal(tess,0,0,1). 376 377 - render many polygons using the same tesselator object, rather than 378 allocating a new tesselator for each one. (In a multi-threaded, 379 multi-processor environment you may get better performance using 380 several tesselators.) 381 382 383Comparison with the GLU tesselator 384---------------------------------- 385 386 On polygons which make it through the "fast path", the tesselator is 387 3 to 5 times faster than the GLU tesselator. 388 389 On polygons which don't make it through the fast path (but which don't 390 have self-intersections or degeneracies), it is about 2 times slower. 391 392 On polygons with self-intersections or degeneraces, there is nothing 393 to compare against. 394 395 The new tesselator generates many more fans and strips, reducing the 396 number of vertices that need to be sent to the hardware. 397 398 Key to the statistics: 399 400 vert number of input vertices on all contours 401 cntr number of input contours 402 tri number of triangles in all output primitives 403 strip number of triangle strips 404 fan number of triangle fans 405 ind number of independent triangles 406 ms number of milliseconds for tesselation 407 (on a 150MHz R4400 Indy) 408 409 Convex polygon examples: 410 411New: 3 vert, 1 cntr, 1 tri, 0 strip, 0 fan, 1 ind, 0.0459 ms 412Old: 3 vert, 1 cntr, 1 tri, 0 strip, 0 fan, 1 ind, 0.149 ms 413New: 4 vert, 1 cntr, 2 tri, 0 strip, 1 fan, 0 ind, 0.0459 ms 414Old: 4 vert, 1 cntr, 2 tri, 0 strip, 0 fan, 2 ind, 0.161 ms 415New: 36 vert, 1 cntr, 34 tri, 0 strip, 1 fan, 0 ind, 0.153 ms 416Old: 36 vert, 1 cntr, 34 tri, 0 strip, 0 fan, 34 ind, 0.621 ms 417 418 Concave single-contour polygons: 419 420New: 5 vert, 1 cntr, 3 tri, 0 strip, 1 fan, 0 ind, 0.052 ms 421Old: 5 vert, 1 cntr, 3 tri, 0 strip, 0 fan, 3 ind, 0.252 ms 422New: 19 vert, 1 cntr, 17 tri, 2 strip, 2 fan, 1 ind, 0.911 ms 423Old: 19 vert, 1 cntr, 17 tri, 0 strip, 0 fan, 17 ind, 0.529 ms 424New: 151 vert, 1 cntr, 149 tri, 13 strip, 18 fan, 3 ind, 6.82 ms 425Old: 151 vert, 1 cntr, 149 tri, 0 strip, 3 fan, 143 ind, 2.7 ms 426New: 574 vert, 1 cntr, 572 tri, 59 strip, 54 fan, 11 ind, 26.6 ms 427Old: 574 vert, 1 cntr, 572 tri, 0 strip, 31 fan, 499 ind, 12.4 ms 428 429 Multiple contours, but no intersections: 430 431New: 7 vert, 2 cntr, 7 tri, 1 strip, 0 fan, 0 ind, 0.527 ms 432Old: 7 vert, 2 cntr, 7 tri, 0 strip, 0 fan, 7 ind, 0.274 ms 433New: 81 vert, 6 cntr, 89 tri, 9 strip, 7 fan, 6 ind, 3.88 ms 434Old: 81 vert, 6 cntr, 89 tri, 0 strip, 13 fan, 61 ind, 2.2 ms 435New: 391 vert, 19 cntr, 413 tri, 37 strip, 32 fan, 26 ind, 20.2 ms 436Old: 391 vert, 19 cntr, 413 tri, 0 strip, 25 fan, 363 ind, 8.68 ms 437 438 Self-intersecting and degenerate examples: 439 440Bowtie: 4 vert, 1 cntr, 2 tri, 0 strip, 0 fan, 2 ind, 0.483 ms 441Star: 5 vert, 1 cntr, 5 tri, 0 strip, 0 fan, 5 ind, 0.91 ms 442Random: 24 vert, 7 cntr, 46 tri, 2 strip, 12 fan, 7 ind, 5.32 ms 443Font: 333 vert, 2 cntr, 331 tri, 32 strip, 16 fan, 3 ind, 14.1 ms 444: 167 vert, 35 cntr, 254 tri, 8 strip, 56 fan, 52 ind, 46.3 ms 445: 78 vert, 1 cntr, 2675 tri, 148 strip, 207 fan, 180 ind, 243 ms 446: 12480 vert, 2 cntr, 12478 tri, 736 strip,1275 fan, 5 ind, 1010 ms 447