aboutsummaryrefslogtreecommitdiff
path: root/mesalib/src/glu/sgi/libtess/README
diff options
context:
space:
mode:
Diffstat (limited to 'mesalib/src/glu/sgi/libtess/README')
-rw-r--r--mesalib/src/glu/sgi/libtess/README446
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