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
5General 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
31The 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
304Polygon 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
354Performance
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
384Comparison 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
412New: 3 vert, 1 cntr, 1 tri, 0 strip, 0 fan, 1 ind, 0.0459 ms
413Old: 3 vert, 1 cntr, 1 tri, 0 strip, 0 fan, 1 ind, 0.149 ms
414New: 4 vert, 1 cntr, 2 tri, 0 strip, 1 fan, 0 ind, 0.0459 ms
415Old: 4 vert, 1 cntr, 2 tri, 0 strip, 0 fan, 2 ind, 0.161 ms
416New: 36 vert, 1 cntr, 34 tri, 0 strip, 1 fan, 0 ind, 0.153 ms
417Old: 36 vert, 1 cntr, 34 tri, 0 strip, 0 fan, 34 ind, 0.621 ms
418
419 Concave single-contour polygons:
420
421New: 5 vert, 1 cntr, 3 tri, 0 strip, 1 fan, 0 ind, 0.052 ms
422Old: 5 vert, 1 cntr, 3 tri, 0 strip, 0 fan, 3 ind, 0.252 ms
423New: 19 vert, 1 cntr, 17 tri, 2 strip, 2 fan, 1 ind, 0.911 ms
424Old: 19 vert, 1 cntr, 17 tri, 0 strip, 0 fan, 17 ind, 0.529 ms
425New: 151 vert, 1 cntr, 149 tri, 13 strip, 18 fan, 3 ind, 6.82 ms
426Old: 151 vert, 1 cntr, 149 tri, 0 strip, 3 fan, 143 ind, 2.7 ms
427New: 574 vert, 1 cntr, 572 tri, 59 strip, 54 fan, 11 ind, 26.6 ms
428Old: 574 vert, 1 cntr, 572 tri, 0 strip, 31 fan, 499 ind, 12.4 ms
429
430 Multiple contours, but no intersections:
431
432New: 7 vert, 2 cntr, 7 tri, 1 strip, 0 fan, 0 ind, 0.527 ms
433Old: 7 vert, 2 cntr, 7 tri, 0 strip, 0 fan, 7 ind, 0.274 ms
434New: 81 vert, 6 cntr, 89 tri, 9 strip, 7 fan, 6 ind, 3.88 ms
435Old: 81 vert, 6 cntr, 89 tri, 0 strip, 13 fan, 61 ind, 2.2 ms
436New: 391 vert, 19 cntr, 413 tri, 37 strip, 32 fan, 26 ind, 20.2 ms
437Old: 391 vert, 19 cntr, 413 tri, 0 strip, 25 fan, 363 ind, 8.68 ms
438
439 Self-intersecting and degenerate examples:
440
441Bowtie: 4 vert, 1 cntr, 2 tri, 0 strip, 0 fan, 2 ind, 0.483 ms
442Star: 5 vert, 1 cntr, 5 tri, 0 strip, 0 fan, 5 ind, 0.91 ms
443Random: 24 vert, 7 cntr, 46 tri, 2 strip, 12 fan, 7 ind, 5.32 ms
444Font: 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