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