readme

Mesa is an open-source implementation of the OpenGL specification - a system for rendering interacti

      negative, or absolute value of at least two).  The current GLU
      tesselator implements the "odd" rule.  The "nonzero" rule is another
      common way to define the interior.  The other three rules are
      useful for polygon CSG operations (see below).

    - GLU_TESS_BOUNDARY_ONLY.  Values: TRUE (non-zero) or FALSE (zero).

      If TRUE, returns a set of closed contours which separate the
      polygon interior and exterior (rather than a tesselation).
      Exterior contours are oriented CCW with respect to the normal,
      interior contours are oriented CW.  The GLU_TESS_BEGIN callback
      uses the type GL_LINE_LOOP for each contour.
      
    - GLU_TESS_TOLERANCE.  Value: a real number between 0.0 and 1.0.

      This specifies a tolerance for merging features to reduce the size
      of the output.  For example, two vertices which are very close to
      each other might be replaced by a single vertex.  The tolerance
      is multiplied by the largest coordinate magnitude of any input vertex;
      this specifies the maximum distance that any feature can move as the
      result of a single merge operation.  If a single feature takes part
      in several merge operations, the total distance moved could be larger.

      Feature merging is completely optional; the tolerance is only a hint.
      The implementation is free to merge in some cases and not in others,
      or to never merge features at all.  The default tolerance is zero.
      
      The current implementation merges vertices only if they are exactly
      coincident, regardless of the current tolerance.  A vertex is
      spliced into an edge only if the implementation is unable to
      distinguish which side of the edge the vertex lies on.
      Two edges are merged only when both endpoints are identical.


   void gluTessNormal( GLUtesselator *tess,
		      GLUcoord x, GLUcoord y, GLUcoord z )

    - Lets the user supply the polygon normal, if known.  All input data
      is projected into a plane perpendicular to the normal before
      tesselation.  All output triangles are oriented CCW with
      respect to the normal (CW orientation can be obtained by
      reversing the sign of the supplied normal).  For example, if
      you know that all polygons lie in the x-y plane, call
      "gluTessNormal(tess, 0.0, 0.0, 1.0)" before rendering any polygons.
      
    - If the supplied normal is (0,0,0) (the default value), the
      normal is determined as follows.  The direction of the normal,
      up to its sign, is found by fitting a plane to the vertices,
      without regard to how the vertices are connected.  It is
      expected that the input data lies approximately in plane;
      otherwise projection perpendicular to the computed normal may
      substantially change the geometry.  The sign of the normal is
      chosen so that the sum of the signed areas of all input contours
      is non-negative (where a CCW contour has positive area).
    
    - The supplied normal persists until it is changed by another
      call to gluTessNormal.


  Backward compatibility with the GLU tesselator
  ----------------------------------------------

  The preferred interface is the one described above.  The following
  routines are obsolete, and are provided only for backward compatibility:

    typedef GLUtesselator GLUtriangulatorObj;	/* obsolete name */

    void gluBeginPolygon( GLUtesselator *tess );
    void gluNextContour( GLUtesselator *tess, GLenum type );
    void gluEndPolygon( GLUtesselator *tess );
  
  "type" is one of GLU_EXTERIOR, GLU_INTERIOR, GLU_CCW, GLU_CW, or
  GLU_UNKNOWN.  It is ignored by the current GLU tesselator.
  
  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.


Polygon CSG operations
----------------------

  The features of the tesselator make it easy to find the union, difference,
  or intersection of several polygons.

  First, assume that each polygon is defined so that the winding number
  is 0 for each exterior region, and 1 for each interior region.  Under
  this model, CCW contours define the outer boundary of the polygon, and
  CW 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 tesselator with the
  GLU_TESS_BOUNDARY_ONLY property turned on.  This returns a list of
  contours satisfying the restriction above.  By allocating two
  tesselator objects, the callbacks from one tesselator can be fed
  directly to the input of another.

  Given two or more polygons of the form above, CSG operations can be
  implemented as follows:

  Union
     Draw all the input contours as a single polygon.  The winding number
     of each resulting region is the number of original polygons
     which cover it.  The union can be extracted using the
     GLU_TESS_WINDING_NONZERO or GLU_TESS_WINDING_POSITIVE winding rules.
     Note that with the nonzero rule, we would get the same result if
     all contour orientations were reversed.

  Intersection (two polygons at a time only)
     Draw a single polygon using the contours from both input polygons.
     Extract the result using GLU_TESS_WINDING_ABS_GEQ_TWO.  (Since this
     winding rule looks at the absolute value, reversing all contour
     orientations does not change the result.)

  Difference
  
     Suppose we want to compute A \ (B union C union D).  Draw a single
     polygon consisting of the unmodified contours from A, followed by
     the contours of B,C,D with the vertex order reversed (this changes
     the winding number of the interior regions to -1).  To extract the
     result, use the GLU_TESS_WINDING_POSITIVE rule.
   
     If B,C,D are the result of a GLU_TESS_BOUNDARY_ONLY call, an
     alternative to reversing the vertex order is to reverse the sign of
     the supplied normal.  For example in the x-y plane, call
     gluTessNormal( tess, 0.0, 0.0, -1.0 ).
 

Performance
-----------

  The tesselator is not intended for immediate-mode rendering; when
  possible the output should be cached in a user structure or display
  list.  General polygon tesselation is an inherently difficult problem,
  especially given the goal of extreme robustness.

  The implementation makes an effort to output a small number of fans
  and strips; this should improve the rendering performance when the
  output is used in a display list.

  Single-contour input polygons are first tested to see whether they can
  be rendered as a triangle fan with respect to the first vertex (to
  avoid running the full decomposition algorithm on convex polygons).
  Non-convex polygons may be rendered by this "fast path" as well, if
  the algorithm gets lucky in its choice of a starting vertex.

  For best performance follow these guidelines:

   - supply the polygon normal, if available, using gluTessNormal().
     This represents about 10% of the computation time.  For example,
     if all polygons lie in the x-y plane, use gluTessNormal(tess,0,0,1).

   - render many polygons using the same tesselator object, rather than
     allocating a new tesselator for each one.  (In a multi-threaded,
     multi-processor environment you may get better performance using
     several tesselators.)


Comparison with the GLU tesselator
----------------------------------

  On polygons which make it through the "fast path", the tesselator is
  3 to 5 times faster than the GLU tesselator.

  On polygons which don't make it through the fast path (but which don't
  have self-intersections or degeneracies), it is about 2 times slower.

  On polygons with self-intersections or degeneraces, there is nothing
  to compare against.

  The new tesselator generates many more fans and strips, reducing the
  number of vertices that need to be sent to the hardware.

  Key to the statistics:

	vert		number of input vertices on all contours
	cntr		number of input contours
	tri		number of triangles in all output primitives
	strip		number of triangle strips
	fan		number of triangle fans
	ind		number of independent triangles
	ms		number of milliseconds for tesselation
			(on a 150MHz R4400 Indy)

  Convex polygon examples:

New:     3 vert,   1 cntr,     1 tri,   0 strip,   0 fan,     1 ind,  0.0459 ms
Old:     3 vert,   1 cntr,     1 tri,   0 strip,   0 fan,     1 ind,   0.149 ms
New:     4 vert,   1 cntr,     2 tri,   0 strip,   1 fan,     0 ind,  0.0459 ms
Old:     4 vert,   1 cntr,     2 tri,   0 strip,   0 fan,     2 ind,   0.161 ms
New:    36 vert,   1 cntr,    34 tri,   0 strip,   1 fan,     0 ind,   0.153 ms
Old:    36 vert,   1 cntr,    34 tri,   0 strip,   0 fan,    34 ind,   0.621 ms

  Concave single-contour polygons:

New:     5 vert,   1 cntr,     3 tri,   0 strip,   1 fan,     0 ind,   0.052 ms
Old:     5 vert,   1 cntr,     3 tri,   0 strip,   0 fan,     3 ind,   0.252 ms
New:    19 vert,   1 cntr,    17 tri,   2 strip,   2 fan,     1 ind,   0.911 ms
Old:    19 vert,   1 cntr,    17 tri,   0 strip,   0 fan,    17 ind,   0.529 ms
New:   151 vert,   1 cntr,   149 tri,  13 strip,  18 fan,     3 ind,    6.82 ms
Old:   151 vert,   1 cntr,   149 tri,   0 strip,   3 fan,   143 ind,     2.7 ms
New:   574 vert,   1 cntr,   572 tri,  59 strip,  54 fan,    11 ind,    26.6 ms
Old:   574 vert,   1 cntr,   572 tri,   0 strip,  31 fan,   499 ind,    12.4 ms

  Multiple contours, but no intersections:

New:     7 vert,   2 cntr,     7 tri,   1 strip,   0 fan,     0 ind,   0.527 ms
Old:     7 vert,   2 cntr,     7 tri,   0 strip,   0 fan,     7 ind,   0.274 ms
New:    81 vert,   6 cntr,    89 tri,   9 strip,   7 fan,     6 ind,    3.88 ms
Old:    81 vert,   6 cntr,    89 tri,   0 strip,  13 fan,    61 ind,     2.2 ms
New:   391 vert,  19 cntr,   413 tri,  37 strip,  32 fan,    26 ind,    20.2 ms
Old:   391 vert,  19 cntr,   413 tri,   0 strip,  25 fan,   363 ind,    8.68 ms

  Self-intersecting and degenerate examples:

Bowtie:  4 vert,   1 cntr,     2 tri,   0 strip,   0 fan,     2 ind,   0.483 ms
Star:    5 vert,   1 cntr,     5 tri,   0 strip,   0 fan,     5 ind,    0.91 ms
Random: 24 vert,   7 cntr,    46 tri,   2 strip,  12 fan,     7 ind,    5.32 ms
Font:  333 vert,   2 cntr,   331 tri,  32 strip,  16 fan,     3 ind,    14.1 ms
:      167 vert,  35 cntr,   254 tri,   8 strip,  56 fan,    52 ind,    46.3 ms
:       78 vert,   1 cntr,  2675 tri, 148 strip, 207 fan,   180 ind,     243 ms
:    12480 vert,   2 cntr, 12478 tri, 736 strip,1275 fan,     5 ind,    1010 ms