src/glu/sgi/libtess/README

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