diff options
Diffstat (limited to 'libtess/README')
| -rw-r--r-- | libtess/README | 447 |
1 files changed, 0 insertions, 447 deletions
diff --git a/libtess/README b/libtess/README deleted file mode 100644 index 6396f5b..0000000 --- a/libtess/README +++ /dev/null @@ -1,447 +0,0 @@ -/* -** $Header$ -*/ - -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 |