svn merge ^/branches/released . --username marha

1 files changed, 446 insertions, 0 deletions

diff --git a/mesalib/src/glu/sgi/libtess/README b/mesalib/src/glu/sgi/libtess/README
new file mode 100644
index 000000000..66a6011e2
--- /dev/null
+++ b/mesalib/src/glu/sgi/libtess/README
@@ -0,0 +1,446 @@
+/*
+*/
+
+General Polygon Tesselation
+---------------------------
+
+  This note describes a tesselator for polygons consisting of one or
+  more closed contours.  It is backward-compatible with the current
+  OpenGL Utilities tesselator, and is intended to replace it.  Here is
+  a summary of the major differences:
+
+   - input contours can be intersecting, self-intersecting, or degenerate.
+  
+   - supports a choice of several winding rules for determining which parts
+     of the polygon are on the "interior".  This makes it possible to do
+     CSG operations on polygons.
+  
+   - boundary extraction: instead of tesselating the polygon, returns a
+     set of closed contours which separate the interior from the exterior.
+  
+   - returns the output as a small number of triangle fans and strips,
+     rather than a list of independent triangles (when possible).
+  
+   - output is available as an explicit mesh (a quad-edge structure),
+     in addition to the normal callback interface.
+  
+   - the algorithm used is extremely robust.
+
+
+The interface
+-------------
+
+  The tesselator state is maintained in a "tesselator object".
+  These are allocated and destroyed using
+
+     GLUtesselator *gluNewTess( void );
+     void gluDeleteTess( GLUtesselator *tess );
+
+  Several tesselator objects may be used simultaneously.
+
+  Inputs
+  ------
+  
+  The input contours are specified with the following routines:
+
+     void gluTessBeginPolygon( GLUtesselator *tess );
+     void gluTessBeginContour( GLUtesselator *tess );
+     void gluTessVertex( GLUtesselator *tess, GLUcoord coords[3], void *data );
+     void gluTessEndContour( GLUtesselator *tess );
+     void gluTessEndPolygon( GLUtesselator *tess );
+
+  Within each BeginPolygon/EndPolygon pair, there can be zero or more
+  calls to BeginContour/EndContour.  Within each contour, there are zero
+  or more calls to gluTessVertex().  The vertices specify a closed
+  contour (the last vertex of each contour is automatically linked to
+  the first).
+
+  "coords" give the coordinates of the vertex in 3-space.  For useful
+  results, all vertices should lie in some plane, since the vertices
+  are projected onto a plane before tesselation.  "data" is a pointer
+  to a user-defined vertex structure, which typically contains other
+  information such as color, texture coordinates, normal, etc.  It is
+  used to refer to the vertex during rendering.
+
+  The library can be compiled in single- or double-precision; the type
+  GLUcoord represents either "float" or "double" accordingly.  The GLU
+  version will be available in double-precision only.  Compile with
+  GLU_TESS_API_FLOAT defined to get the single-precision version.
+
+  When EndPolygon is called, the tesselation algorithm determines
+  which regions are interior to the given contours, according to one
+  of several "winding rules" described below.  The interior regions
+  are then tesselated, and the output is provided as callbacks.
+
+
+  Rendering Callbacks
+  -------------------
+
+  Callbacks are specified by the client using
+
+     void gluTessCallback( GLUtesselator *tess, GLenum which, void (*fn)());
+
+  If "fn" is NULL, any previously defined callback is discarded.
+  
+  The callbacks used to provide output are:	/* which == */
+
+     void begin( GLenum type );			/* GLU_TESS_BEGIN */
+     void edgeFlag( GLboolean flag );		/* GLU_TESS_EDGE_FLAG */
+     void vertex( void *data );			/* GLU_TESS_VERTEX */
+     void end( void );				/* GLU_TESS_END */
+
+  Any of the callbacks may be left undefined; if so, the corresponding
+  information will not be supplied during rendering.
+
+  The "begin" callback indicates the start of a primitive; type is one
+  of GL_TRIANGLE_STRIP, GL_TRIANGLE_FAN, or GL_TRIANGLES (but see the
+  notes on "boundary extraction" below).
+  
+  It is followed by any number of "vertex" callbacks, which supply the
+  vertices in the same order as expected by the corresponding glBegin()
+  call.  After the last vertex of a given primitive, there is a callback
+  to "end".
+
+  If the "edgeFlag" callback is provided, no triangle fans or strips
+  will be used.  When edgeFlag is called, if "flag" is GL_TRUE then each
+  vertex which follows begins an edge which lies on the polygon boundary
+  (ie. an edge which separates an interior region from an exterior one).
+  If "flag" is GL_FALSE, each vertex which follows begins an edge which lies
+  in the polygon interior.  "edgeFlag" will be called before the first
+  call to "vertex".
+
+  Other Callbacks
+  ---------------
+
+   void mesh( GLUmesh *mesh );			/* GLU_TESS_MESH */
+
+   - Returns an explicit mesh, represented using the quad-edge structure
+     (Guibas/Stolfi '85).  Other implementations of this interface might
+     use a different mesh structure, so this is available only only as an
+     SGI extension.  When the mesh is no longer needed, it should be freed
+     using
+
+	void gluDeleteMesh( GLUmesh *mesh );
+
+     There is a brief description of this data structure in the include
+     file "mesh.h".  For the full details, see L. Guibas and J. Stolfi,
+     Primitives for the manipulation of general subdivisions and the
+     computation of Voronoi diagrams, ACM Transactions on Graphics,
+     4(2):74-123, April 1985.  For an introduction, see the course notes
+     for CS348a, "Mathematical Foundations of Computer Graphics",
+     available at the Stanford bookstore (and taught during the fall
+     quarter).
+
+   void error( GLenum errno );			/* GLU_TESS_ERROR */
+
+   - errno is one of	GLU_TESS_MISSING_BEGIN_POLYGON,
+			GLU_TESS_MISSING_END_POLYGON,
+			GLU_TESS_MISSING_BEGIN_CONTOUR,
+			GLU_TESS_MISSING_END_CONTOUR,
+			GLU_TESS_COORD_TOO_LARGE,
+			GLU_TESS_NEED_COMBINE_CALLBACK
+
+     The first four are obvious.  The interface recovers from these
+     errors by inserting the missing call(s).
+  
+     GLU_TESS_COORD_TOO_LARGE says that some vertex coordinate exceeded
+     the predefined constant GLU_TESS_MAX_COORD in absolute value, and
+     that the value has been clamped.  (Coordinate values must be small
+     enough so that two can be multiplied together without overflow.)
+
+     GLU_TESS_NEED_COMBINE_CALLBACK says that the algorithm detected an
+     intersection between two edges in the input data, and the "combine"
+     callback (below) was not provided.  No output will be generated.
+
+
+   void combine( GLUcoord coords[3], void *data[4],	/* GLU_TESS_COMBINE */
+		 GLUcoord weight[4], void **outData );
+
+   - When the algorithm detects an intersection, or wishes to merge
+     features, it needs to create a new vertex.  The vertex is defined
+     as a linear combination of up to 4 existing vertices, referenced
+     by data[0..3].  The coefficients of the linear combination are
+     given by weight[0..3]; these weights always sum to 1.0.  All vertex
+     pointers are valid even when some of the weights are zero.
+     "coords" gives the location of the new vertex.
+
+     The user must allocate another vertex, interpolate parameters
+     using "data" and "weights", and return the new vertex pointer in
+     "outData".  This handle is supplied during rendering callbacks.
+     For example, if the polygon lies in an arbitrary plane in 3-space,
+     and we associate a color with each vertex, the combine callback might
+     look like this:
+    
+     void myCombine( GLUcoord coords[3], VERTEX *d[4],
+                     GLUcoord w[4], VERTEX **dataOut )
+     {
+        VERTEX *new = new_vertex();
+       
+        new->x = coords[0];
+        new->y = coords[1];
+        new->z = coords[2];
+        new->r = w[0]*d[0]->r + w[1]*d[1]->r + w[2]*d[2]->r + w[3]*d[3]->r;
+        new->g = w[0]*d[0]->g + w[1]*d[1]->g + w[2]*d[2]->g + w[3]*d[3]->g;
+        new->b = w[0]*d[0]->b + w[1]*d[1]->b + w[2]*d[2]->b + w[3]*d[3]->b;
+        new->a = w[0]*d[0]->a + w[1]*d[1]->a + w[2]*d[2]->a + w[3]*d[3]->a;
+        *dataOut = new;
+     }
+
+     If the algorithm detects an intersection, then the "combine" callback
+     must be defined, and must write a non-NULL pointer into "dataOut".
+     Otherwise the GLU_TESS_NEED_COMBINE_CALLBACK error occurs, and no
+     output is generated.  This is the only error that can occur during
+     tesselation and rendering.
+
+
+  Control over Tesselation
+  ------------------------
+  
+   void gluTessProperty( GLUtesselator *tess, GLenum which, GLUcoord value );
+
+   Properties defined:
+
+    - GLU_TESS_WINDING_RULE.  Possible values:
+
+	  GLU_TESS_WINDING_ODD
+	  GLU_TESS_WINDING_NONZERO
+	  GLU_TESS_WINDING_POSITIVE
+	  GLU_TESS_WINDING_NEGATIVE
+	  GLU_TESS_WINDING_ABS_GEQ_TWO
+
+      The input contours parition the plane into regions.  A winding
+      rule determines which of these regions are inside the polygon.
+      
+      For a single contour C, the winding number of a point x is simply
+      the signed number of revolutions we make around x as we travel
+      once around C (where CCW is positive).  When there are several
+      contours, the individual winding numbers are summed.  This
+      procedure associates a signed integer value with each point x in
+      the plane.  Note that the winding number is the same for all
+      points in a single region.
+
+      The winding rule classifies a region as "inside" if its winding
+      number belongs to the chosen category (odd, nonzero, positive,
+      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