diff options
| author | Matt Turner <[email protected]> | 2012-08-23 16:39:20 -0700 |
|---|---|---|
| committer | Matt Turner <[email protected]> | 2012-08-31 15:08:40 -0700 |
| commit | d240dcee6de7369a423ed230c67e3be5ff47140a (patch) | |
| tree | cda2a92aaffc2cec4faf1b01ddaac30361b885fc /src/glu/sgi/libtess | |
| parent | 00978098794f723230a33cab1c1152686f1c4fa5 (diff) | |
Remove libGLU
It's been moved to its own repository, found at
http://cgit.freedesktop.org/mesa/glu/
Acked-by: Kenneth Graunke <[email protected]>
Diffstat (limited to 'src/glu/sgi/libtess')
26 files changed, 0 insertions, 6726 deletions
diff --git a/src/glu/sgi/libtess/README b/src/glu/sgi/libtess/README deleted file mode 100644 index 66a6011e25d..00000000000 --- a/src/glu/sgi/libtess/README +++ /dev/null @@ -1,446 +0,0 @@ -/* -*/ - -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 diff --git a/src/glu/sgi/libtess/alg-outline b/src/glu/sgi/libtess/alg-outline deleted file mode 100644 index 33fd69728a4..00000000000 --- a/src/glu/sgi/libtess/alg-outline +++ /dev/null @@ -1,228 +0,0 @@ -/* -*/ - -This is only a very brief overview. There is quite a bit of -additional documentation in the source code itself. - - -Goals of robust tesselation ---------------------------- - -The tesselation algorithm is fundamentally a 2D algorithm. We -initially project all data into a plane; our goal is to robustly -tesselate the projected data. The same topological tesselation is -then applied to the input data. - -Topologically, the output should always be a tesselation. If the -input is even slightly non-planar, then some triangles will -necessarily be back-facing when viewed from some angles, but the goal -is to minimize this effect. - -The algorithm needs some capability of cleaning up the input data as -well as the numerical errors in its own calculations. One way to do -this is to specify a tolerance as defined above, and clean up the -input and output during the line sweep process. At the very least, -the algorithm must handle coincident vertices, vertices incident to an -edge, and coincident edges. - - -Phases of the algorithm ------------------------ - -1. Find the polygon normal N. -2. Project the vertex data onto a plane. It does not need to be - perpendicular to the normal, eg. we can project onto the plane - perpendicular to the coordinate axis whose dot product with N - is largest. -3. Using a line-sweep algorithm, partition the plane into x-monotone - regions. Any vertical line intersects an x-monotone region in - at most one interval. -4. Triangulate the x-monotone regions. -5. Group the triangles into strips and fans. - - -Finding the normal vector -------------------------- - -A common way to find a polygon normal is to compute the signed area -when the polygon is projected along the three coordinate axes. We -can't do this, since contours can have zero area without being -degenerate (eg. a bowtie). - -We fit a plane to the vertex data, ignoring how they are connected -into contours. Ideally this would be a least-squares fit; however for -our purpose the accuracy of the normal is not important. Instead we -find three vertices which are widely separated, and compute the normal -to the triangle they form. The vertices are chosen so that the -triangle has an area at least 1/sqrt(3) times the largest area of any -triangle formed using the input vertices. - -The contours do affect the orientation of the normal; after computing -the normal, we check that the sum of the signed contour areas is -non-negative, and reverse the normal if necessary. - - -Projecting the vertices ------------------------ - -We project the vertices onto a plane perpendicular to one of the three -coordinate axes. This helps numerical accuracy by removing a -transformation step between the original input data and the data -processed by the algorithm. The projection also compresses the input -data; the 2D distance between vertices after projection may be smaller -than the original 2D distance. However by choosing the coordinate -axis whose dot product with the normal is greatest, the compression -factor is at most 1/sqrt(3). - -Even though the *accuracy* of the normal is not that important (since -we are projecting perpendicular to a coordinate axis anyway), the -*robustness* of the computation is important. For example, if there -are many vertices which lie almost along a line, and one vertex V -which is well-separated from the line, then our normal computation -should involve V otherwise the results will be garbage. - -The advantage of projecting perpendicular to the polygon normal is -that computed intersection points will be as close as possible to -their ideal locations. To get this behavior, define TRUE_PROJECT. - - -The Line Sweep --------------- - -There are three data structures: the mesh, the event queue, and the -edge dictionary. - -The mesh is a "quad-edge" data structure which records the topology of -the current decomposition; for details see the include file "mesh.h". - -The event queue simply holds all vertices (both original and computed -ones), organized so that we can quickly extract the vertex with the -minimum x-coord (and among those, the one with the minimum y-coord). - -The edge dictionary describes the current intersection of the sweep -line with the regions of the polygon. This is just an ordering of the -edges which intersect the sweep line, sorted by their current order of -intersection. For each pair of edges, we store some information about -the monotone region between them -- these are call "active regions" -(since they are crossed by the current sweep line). - -The basic algorithm is to sweep from left to right, processing each -vertex. The processed portion of the mesh (left of the sweep line) is -a planar decomposition. As we cross each vertex, we update the mesh -and the edge dictionary, then we check any newly adjacent pairs of -edges to see if they intersect. - -A vertex can have any number of edges. Vertices with many edges can -be created as vertices are merged and intersection points are -computed. For unprocessed vertices (right of the sweep line), these -edges are in no particular order around the vertex; for processed -vertices, the topological ordering should match the geometric ordering. - -The vertex processing happens in two phases: first we process are the -left-going edges (all these edges are currently in the edge -dictionary). This involves: - - - deleting the left-going edges from the dictionary; - - relinking the mesh if necessary, so that the order of these edges around - the event vertex matches the order in the dictionary; - - marking any terminated regions (regions which lie between two left-going - edges) as either "inside" or "outside" according to their winding number. - -When there are no left-going edges, and the event vertex is in an -"interior" region, we need to add an edge (to split the region into -monotone pieces). To do this we simply join the event vertex to the -rightmost left endpoint of the upper or lower edge of the containing -region. - -Then we process the right-going edges. This involves: - - - inserting the edges in the edge dictionary; - - computing the winding number of any newly created active regions. - We can compute this incrementally using the winding of each edge - that we cross as we walk through the dictionary. - - relinking the mesh if necessary, so that the order of these edges around - the event vertex matches the order in the dictionary; - - checking any newly adjacent edges for intersection and/or merging. - -If there are no right-going edges, again we need to add one to split -the containing region into monotone pieces. In our case it is most -convenient to add an edge to the leftmost right endpoint of either -containing edge; however we may need to change this later (see the -code for details). - - -Invariants ----------- - -These are the most important invariants maintained during the sweep. -We define a function VertLeq(v1,v2) which defines the order in which -vertices cross the sweep line, and a function EdgeLeq(e1,e2; loc) -which says whether e1 is below e2 at the sweep event location "loc". -This function is defined only at sweep event locations which lie -between the rightmost left endpoint of {e1,e2}, and the leftmost right -endpoint of {e1,e2}. - -Invariants for the Edge Dictionary. - - - Each pair of adjacent edges e2=Succ(e1) satisfies EdgeLeq(e1,e2) - at any valid location of the sweep event. - - If EdgeLeq(e2,e1) as well (at any valid sweep event), then e1 and e2 - share a common endpoint. - - For each e in the dictionary, e->Dst has been processed but not e->Org. - - Each edge e satisfies VertLeq(e->Dst,event) && VertLeq(event,e->Org) - where "event" is the current sweep line event. - - No edge e has zero length. - - No two edges have identical left and right endpoints. - -Invariants for the Mesh (the processed portion). - - - The portion of the mesh left of the sweep line is a planar graph, - ie. there is *some* way to embed it in the plane. - - No processed edge has zero length. - - No two processed vertices have identical coordinates. - - Each "inside" region is monotone, ie. can be broken into two chains - of monotonically increasing vertices according to VertLeq(v1,v2) - - a non-invariant: these chains may intersect (slightly) due to - numerical errors, but this does not affect the algorithm's operation. - -Invariants for the Sweep. - - - If a vertex has any left-going edges, then these must be in the edge - dictionary at the time the vertex is processed. - - If an edge is marked "fixUpperEdge" (it is a temporary edge introduced - by ConnectRightVertex), then it is the only right-going edge from - its associated vertex. (This says that these edges exist only - when it is necessary.) - - -Robustness ----------- - -The key to the robustness of the algorithm is maintaining the -invariants above, especially the correct ordering of the edge -dictionary. We achieve this by: - - 1. Writing the numerical computations for maximum precision rather - than maximum speed. - - 2. Making no assumptions at all about the results of the edge - intersection calculations -- for sufficiently degenerate inputs, - the computed location is not much better than a random number. - - 3. When numerical errors violate the invariants, restore them - by making *topological* changes when necessary (ie. relinking - the mesh structure). - - -Triangulation and Grouping --------------------------- - -We finish the line sweep before doing any triangulation. This is -because even after a monotone region is complete, there can be further -changes to its vertex data because of further vertex merging. - -After triangulating all monotone regions, we want to group the -triangles into fans and strips. We do this using a greedy approach. -The triangulation itself is not optimized to reduce the number of -primitives; we just try to get a reasonable decomposition of the -computed triangulation. diff --git a/src/glu/sgi/libtess/dict-list.h b/src/glu/sgi/libtess/dict-list.h deleted file mode 100644 index 11331a76edf..00000000000 --- a/src/glu/sgi/libtess/dict-list.h +++ /dev/null @@ -1,100 +0,0 @@ -/* - * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008) - * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved. - * - * Permission is hereby granted, free of charge, to any person obtaining a - * copy of this software and associated documentation files (the "Software"), - * to deal in the Software without restriction, including without limitation - * the rights to use, copy, modify, merge, publish, distribute, sublicense, - * and/or sell copies of the Software, and to permit persons to whom the - * Software is furnished to do so, subject to the following conditions: - * - * The above copyright notice including the dates of first publication and - * either this permission notice or a reference to - * http://oss.sgi.com/projects/FreeB/ - * shall be included in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS - * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL - * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, - * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF - * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - * - * Except as contained in this notice, the name of Silicon Graphics, Inc. - * shall not be used in advertising or otherwise to promote the sale, use or - * other dealings in this Software without prior written authorization from - * Silicon Graphics, Inc. - */ -/* -** Author: Eric Veach, July 1994. -** -*/ - -#ifndef __dict_list_h_ -#define __dict_list_h_ - -/* Use #define's so that another heap implementation can use this one */ - -#define DictKey DictListKey -#define Dict DictList -#define DictNode DictListNode - -#define dictNewDict(frame,leq) __gl_dictListNewDict(frame,leq) -#define dictDeleteDict(dict) __gl_dictListDeleteDict(dict) - -#define dictSearch(dict,key) __gl_dictListSearch(dict,key) -#define dictInsert(dict,key) __gl_dictListInsert(dict,key) -#define dictInsertBefore(dict,node,key) __gl_dictListInsertBefore(dict,node,key) -#define dictDelete(dict,node) __gl_dictListDelete(dict,node) - -#define dictKey(n) __gl_dictListKey(n) -#define dictSucc(n) __gl_dictListSucc(n) -#define dictPred(n) __gl_dictListPred(n) -#define dictMin(d) __gl_dictListMin(d) -#define dictMax(d) __gl_dictListMax(d) - - - -typedef void *DictKey; -typedef struct Dict Dict; -typedef struct DictNode DictNode; - -Dict *dictNewDict( - void *frame, - int (*leq)(void *frame, DictKey key1, DictKey key2) ); - -void dictDeleteDict( Dict *dict ); - -/* Search returns the node with the smallest key greater than or equal - * to the given key. If there is no such key, returns a node whose - * key is NULL. Similarly, Succ(Max(d)) has a NULL key, etc. - */ -DictNode *dictSearch( Dict *dict, DictKey key ); -DictNode *dictInsertBefore( Dict *dict, DictNode *node, DictKey key ); -void dictDelete( Dict *dict, DictNode *node ); - -#define __gl_dictListKey(n) ((n)->key) -#define __gl_dictListSucc(n) ((n)->next) -#define __gl_dictListPred(n) ((n)->prev) -#define __gl_dictListMin(d) ((d)->head.next) -#define __gl_dictListMax(d) ((d)->head.prev) -#define __gl_dictListInsert(d,k) (dictInsertBefore((d),&(d)->head,(k))) - - -/*** Private data structures ***/ - -struct DictNode { - DictKey key; - DictNode *next; - DictNode *prev; -}; - -struct Dict { - DictNode head; - void *frame; - int (*leq)(void *frame, DictKey key1, DictKey key2); -}; - -#endif diff --git a/src/glu/sgi/libtess/dict.c b/src/glu/sgi/libtess/dict.c deleted file mode 100644 index 49d4f759e7e..00000000000 --- a/src/glu/sgi/libtess/dict.c +++ /dev/null @@ -1,111 +0,0 @@ -/* - * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008) - * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved. - * - * Permission is hereby granted, free of charge, to any person obtaining a - * copy of this software and associated documentation files (the "Software"), - * to deal in the Software without restriction, including without limitation - * the rights to use, copy, modify, merge, publish, distribute, sublicense, - * and/or sell copies of the Software, and to permit persons to whom the - * Software is furnished to do so, subject to the following conditions: - * - * The above copyright notice including the dates of first publication and - * either this permission notice or a reference to - * http://oss.sgi.com/projects/FreeB/ - * shall be included in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS - * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL - * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, - * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF - * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - * - * Except as contained in this notice, the name of Silicon Graphics, Inc. - * shall not be used in advertising or otherwise to promote the sale, use or - * other dealings in this Software without prior written authorization from - * Silicon Graphics, Inc. - */ -/* -** Author: Eric Veach, July 1994. -** -*/ - -#include <stddef.h> -#include "dict-list.h" -#include "memalloc.h" - -/* really __gl_dictListNewDict */ -Dict *dictNewDict( void *frame, - int (*leq)(void *frame, DictKey key1, DictKey key2) ) -{ - Dict *dict = (Dict *) memAlloc( sizeof( Dict )); - DictNode *head; - - if (dict == NULL) return NULL; - - head = &dict->head; - - head->key = NULL; - head->next = head; - head->prev = head; - - dict->frame = frame; - dict->leq = leq; - - return dict; -} - -/* really __gl_dictListDeleteDict */ -void dictDeleteDict( Dict *dict ) -{ - DictNode *node, *next; - - for( node = dict->head.next; node != &dict->head; node = next ) { - next = node->next; - memFree( node ); - } - memFree( dict ); -} - -/* really __gl_dictListInsertBefore */ -DictNode *dictInsertBefore( Dict *dict, DictNode *node, DictKey key ) -{ - DictNode *newNode; - - do { - node = node->prev; - } while( node->key != NULL && ! (*dict->leq)(dict->frame, node->key, key)); - - newNode = (DictNode *) memAlloc( sizeof( DictNode )); - if (newNode == NULL) return NULL; - - newNode->key = key; - newNode->next = node->next; - node->next->prev = newNode; - newNode->prev = node; - node->next = newNode; - - return newNode; -} - -/* really __gl_dictListDelete */ -void dictDelete( Dict *dict, DictNode *node ) /*ARGSUSED*/ -{ - node->next->prev = node->prev; - node->prev->next = node->next; - memFree( node ); -} - -/* really __gl_dictListSearch */ -DictNode *dictSearch( Dict *dict, DictKey key ) -{ - DictNode *node = &dict->head; - - do { - node = node->next; - } while( node->key != NULL && ! (*dict->leq)(dict->frame, key, node->key)); - - return node; -} diff --git a/src/glu/sgi/libtess/dict.h b/src/glu/sgi/libtess/dict.h deleted file mode 100644 index 11331a76edf..00000000000 --- a/src/glu/sgi/libtess/dict.h +++ /dev/null @@ -1,100 +0,0 @@ -/* - * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008) - * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved. - * - * Permission is hereby granted, free of charge, to any person obtaining a - * copy of this software and associated documentation files (the "Software"), - * to deal in the Software without restriction, including without limitation - * the rights to use, copy, modify, merge, publish, distribute, sublicense, - * and/or sell copies of the Software, and to permit persons to whom the - * Software is furnished to do so, subject to the following conditions: - * - * The above copyright notice including the dates of first publication and - * either this permission notice or a reference to - * http://oss.sgi.com/projects/FreeB/ - * shall be included in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS - * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL - * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, - * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF - * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - * - * Except as contained in this notice, the name of Silicon Graphics, Inc. - * shall not be used in advertising or otherwise to promote the sale, use or - * other dealings in this Software without prior written authorization from - * Silicon Graphics, Inc. - */ -/* -** Author: Eric Veach, July 1994. -** -*/ - -#ifndef __dict_list_h_ -#define __dict_list_h_ - -/* Use #define's so that another heap implementation can use this one */ - -#define DictKey DictListKey -#define Dict DictList -#define DictNode DictListNode - -#define dictNewDict(frame,leq) __gl_dictListNewDict(frame,leq) -#define dictDeleteDict(dict) __gl_dictListDeleteDict(dict) - -#define dictSearch(dict,key) __gl_dictListSearch(dict,key) -#define dictInsert(dict,key) __gl_dictListInsert(dict,key) -#define dictInsertBefore(dict,node,key) __gl_dictListInsertBefore(dict,node,key) -#define dictDelete(dict,node) __gl_dictListDelete(dict,node) - -#define dictKey(n) __gl_dictListKey(n) -#define dictSucc(n) __gl_dictListSucc(n) -#define dictPred(n) __gl_dictListPred(n) -#define dictMin(d) __gl_dictListMin(d) -#define dictMax(d) __gl_dictListMax(d) - - - -typedef void *DictKey; -typedef struct Dict Dict; -typedef struct DictNode DictNode; - -Dict *dictNewDict( - void *frame, - int (*leq)(void *frame, DictKey key1, DictKey key2) ); - -void dictDeleteDict( Dict *dict ); - -/* Search returns the node with the smallest key greater than or equal - * to the given key. If there is no such key, returns a node whose - * key is NULL. Similarly, Succ(Max(d)) has a NULL key, etc. - */ -DictNode *dictSearch( Dict *dict, DictKey key ); -DictNode *dictInsertBefore( Dict *dict, DictNode *node, DictKey key ); -void dictDelete( Dict *dict, DictNode *node ); - -#define __gl_dictListKey(n) ((n)->key) -#define __gl_dictListSucc(n) ((n)->next) -#define __gl_dictListPred(n) ((n)->prev) -#define __gl_dictListMin(d) ((d)->head.next) -#define __gl_dictListMax(d) ((d)->head.prev) -#define __gl_dictListInsert(d,k) (dictInsertBefore((d),&(d)->head,(k))) - - -/*** Private data structures ***/ - -struct DictNode { - DictKey key; - DictNode *next; - DictNode *prev; -}; - -struct Dict { - DictNode head; - void *frame; - int (*leq)(void *frame, DictKey key1, DictKey key2); -}; - -#endif diff --git a/src/glu/sgi/libtess/geom.c b/src/glu/sgi/libtess/geom.c deleted file mode 100644 index 35b36a394c4..00000000000 --- a/src/glu/sgi/libtess/geom.c +++ /dev/null @@ -1,264 +0,0 @@ -/* - * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008) - * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved. - * - * Permission is hereby granted, free of charge, to any person obtaining a - * copy of this software and associated documentation files (the "Software"), - * to deal in the Software without restriction, including without limitation - * the rights to use, copy, modify, merge, publish, distribute, sublicense, - * and/or sell copies of the Software, and to permit persons to whom the - * Software is furnished to do so, subject to the following conditions: - * - * The above copyright notice including the dates of first publication and - * either this permission notice or a reference to - * http://oss.sgi.com/projects/FreeB/ - * shall be included in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS - * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL - * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, - * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF - * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - * - * Except as contained in this notice, the name of Silicon Graphics, Inc. - * shall not be used in advertising or otherwise to promote the sale, use or - * other dealings in this Software without prior written authorization from - * Silicon Graphics, Inc. - */ -/* -** Author: Eric Veach, July 1994. -** -*/ - -#include "gluos.h" -#include <assert.h> -#include "mesh.h" -#include "geom.h" - -int __gl_vertLeq( GLUvertex *u, GLUvertex *v ) -{ - /* Returns TRUE if u is lexicographically <= v. */ - - return VertLeq( u, v ); -} - -GLdouble __gl_edgeEval( GLUvertex *u, GLUvertex *v, GLUvertex *w ) -{ - /* Given three vertices u,v,w such that VertLeq(u,v) && VertLeq(v,w), - * evaluates the t-coord of the edge uw at the s-coord of the vertex v. - * Returns v->t - (uw)(v->s), ie. the signed distance from uw to v. - * If uw is vertical (and thus passes thru v), the result is zero. - * - * The calculation is extremely accurate and stable, even when v - * is very close to u or w. In particular if we set v->t = 0 and - * let r be the negated result (this evaluates (uw)(v->s)), then - * r is guaranteed to satisfy MIN(u->t,w->t) <= r <= MAX(u->t,w->t). - */ - GLdouble gapL, gapR; - - assert( VertLeq( u, v ) && VertLeq( v, w )); - - gapL = v->s - u->s; - gapR = w->s - v->s; - - if( gapL + gapR > 0 ) { - if( gapL < gapR ) { - return (v->t - u->t) + (u->t - w->t) * (gapL / (gapL + gapR)); - } else { - return (v->t - w->t) + (w->t - u->t) * (gapR / (gapL + gapR)); - } - } - /* vertical line */ - return 0; -} - -GLdouble __gl_edgeSign( GLUvertex *u, GLUvertex *v, GLUvertex *w ) -{ - /* Returns a number whose sign matches EdgeEval(u,v,w) but which - * is cheaper to evaluate. Returns > 0, == 0 , or < 0 - * as v is above, on, or below the edge uw. - */ - GLdouble gapL, gapR; - - assert( VertLeq( u, v ) && VertLeq( v, w )); - - gapL = v->s - u->s; - gapR = w->s - v->s; - - if( gapL + gapR > 0 ) { - return (v->t - w->t) * gapL + (v->t - u->t) * gapR; - } - /* vertical line */ - return 0; -} - - -/*********************************************************************** - * Define versions of EdgeSign, EdgeEval with s and t transposed. - */ - -GLdouble __gl_transEval( GLUvertex *u, GLUvertex *v, GLUvertex *w ) -{ - /* Given three vertices u,v,w such that TransLeq(u,v) && TransLeq(v,w), - * evaluates the t-coord of the edge uw at the s-coord of the vertex v. - * Returns v->s - (uw)(v->t), ie. the signed distance from uw to v. - * If uw is vertical (and thus passes thru v), the result is zero. - * - * The calculation is extremely accurate and stable, even when v - * is very close to u or w. In particular if we set v->s = 0 and - * let r be the negated result (this evaluates (uw)(v->t)), then - * r is guaranteed to satisfy MIN(u->s,w->s) <= r <= MAX(u->s,w->s). - */ - GLdouble gapL, gapR; - - assert( TransLeq( u, v ) && TransLeq( v, w )); - - gapL = v->t - u->t; - gapR = w->t - v->t; - - if( gapL + gapR > 0 ) { - if( gapL < gapR ) { - return (v->s - u->s) + (u->s - w->s) * (gapL / (gapL + gapR)); - } else { - return (v->s - w->s) + (w->s - u->s) * (gapR / (gapL + gapR)); - } - } - /* vertical line */ - return 0; -} - -GLdouble __gl_transSign( GLUvertex *u, GLUvertex *v, GLUvertex *w ) -{ - /* Returns a number whose sign matches TransEval(u,v,w) but which - * is cheaper to evaluate. Returns > 0, == 0 , or < 0 - * as v is above, on, or below the edge uw. - */ - GLdouble gapL, gapR; - - assert( TransLeq( u, v ) && TransLeq( v, w )); - - gapL = v->t - u->t; - gapR = w->t - v->t; - - if( gapL + gapR > 0 ) { - return (v->s - w->s) * gapL + (v->s - u->s) * gapR; - } - /* vertical line */ - return 0; -} - - -int __gl_vertCCW( GLUvertex *u, GLUvertex *v, GLUvertex *w ) -{ - /* For almost-degenerate situations, the results are not reliable. - * Unless the floating-point arithmetic can be performed without - * rounding errors, *any* implementation will give incorrect results - * on some degenerate inputs, so the client must have some way to - * handle this situation. - */ - return (u->s*(v->t - w->t) + v->s*(w->t - u->t) + w->s*(u->t - v->t)) >= 0; -} - -/* Given parameters a,x,b,y returns the value (b*x+a*y)/(a+b), - * or (x+y)/2 if a==b==0. It requires that a,b >= 0, and enforces - * this in the rare case that one argument is slightly negative. - * The implementation is extremely stable numerically. - * In particular it guarantees that the result r satisfies - * MIN(x,y) <= r <= MAX(x,y), and the results are very accurate - * even when a and b differ greatly in magnitude. - */ -#define RealInterpolate(a,x,b,y) \ - (a = (a < 0) ? 0 : a, b = (b < 0) ? 0 : b, \ - ((a <= b) ? ((b == 0) ? ((x+y) / 2) \ - : (x + (y-x) * (a/(a+b)))) \ - : (y + (x-y) * (b/(a+b))))) - -#ifndef FOR_TRITE_TEST_PROGRAM -#define Interpolate(a,x,b,y) RealInterpolate(a,x,b,y) -#else - -/* Claim: the ONLY property the sweep algorithm relies on is that - * MIN(x,y) <= r <= MAX(x,y). This is a nasty way to test that. - */ -#include <stdlib.h> -extern int RandomInterpolate; - -GLdouble Interpolate( GLdouble a, GLdouble x, GLdouble b, GLdouble y) -{ -printf("*********************%d\n",RandomInterpolate); - if( RandomInterpolate ) { - a = 1.2 * drand48() - 0.1; - a = (a < 0) ? 0 : ((a > 1) ? 1 : a); - b = 1.0 - a; - } - return RealInterpolate(a,x,b,y); -} - -#endif - -#define Swap(a,b) do { GLUvertex *t = a; a = b; b = t; } while (0) - -void __gl_edgeIntersect( GLUvertex *o1, GLUvertex *d1, - GLUvertex *o2, GLUvertex *d2, - GLUvertex *v ) -/* Given edges (o1,d1) and (o2,d2), compute their point of intersection. - * The computed point is guaranteed to lie in the intersection of the - * bounding rectangles defined by each edge. - */ -{ - GLdouble z1, z2; - - /* This is certainly not the most efficient way to find the intersection - * of two line segments, but it is very numerically stable. - * - * Strategy: find the two middle vertices in the VertLeq ordering, - * and interpolate the intersection s-value from these. Then repeat - * using the TransLeq ordering to find the intersection t-value. - */ - - if( ! VertLeq( o1, d1 )) { Swap( o1, d1 ); } - if( ! VertLeq( o2, d2 )) { Swap( o2, d2 ); } - if( ! VertLeq( o1, o2 )) { Swap( o1, o2 ); Swap( d1, d2 ); } - - if( ! VertLeq( o2, d1 )) { - /* Technically, no intersection -- do our best */ - v->s = (o2->s + d1->s) / 2; - } else if( VertLeq( d1, d2 )) { - /* Interpolate between o2 and d1 */ - z1 = EdgeEval( o1, o2, d1 ); - z2 = EdgeEval( o2, d1, d2 ); - if( z1+z2 < 0 ) { z1 = -z1; z2 = -z2; } - v->s = Interpolate( z1, o2->s, z2, d1->s ); - } else { - /* Interpolate between o2 and d2 */ - z1 = EdgeSign( o1, o2, d1 ); - z2 = -EdgeSign( o1, d2, d1 ); - if( z1+z2 < 0 ) { z1 = -z1; z2 = -z2; } - v->s = Interpolate( z1, o2->s, z2, d2->s ); - } - - /* Now repeat the process for t */ - - if( ! TransLeq( o1, d1 )) { Swap( o1, d1 ); } - if( ! TransLeq( o2, d2 )) { Swap( o2, d2 ); } - if( ! TransLeq( o1, o2 )) { Swap( o1, o2 ); Swap( d1, d2 ); } - - if( ! TransLeq( o2, d1 )) { - /* Technically, no intersection -- do our best */ - v->t = (o2->t + d1->t) / 2; - } else if( TransLeq( d1, d2 )) { - /* Interpolate between o2 and d1 */ - z1 = TransEval( o1, o2, d1 ); - z2 = TransEval( o2, d1, d2 ); - if( z1+z2 < 0 ) { z1 = -z1; z2 = -z2; } - v->t = Interpolate( z1, o2->t, z2, d1->t ); - } else { - /* Interpolate between o2 and d2 */ - z1 = TransSign( o1, o2, d1 ); - z2 = -TransSign( o1, d2, d1 ); - if( z1+z2 < 0 ) { z1 = -z1; z2 = -z2; } - v->t = Interpolate( z1, o2->t, z2, d2->t ); - } -} diff --git a/src/glu/sgi/libtess/geom.h b/src/glu/sgi/libtess/geom.h deleted file mode 100644 index 5cb76c7d154..00000000000 --- a/src/glu/sgi/libtess/geom.h +++ /dev/null @@ -1,84 +0,0 @@ -/* - * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008) - * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved. - * - * Permission is hereby granted, free of charge, to any person obtaining a - * copy of this software and associated documentation files (the "Software"), - * to deal in the Software without restriction, including without limitation - * the rights to use, copy, modify, merge, publish, distribute, sublicense, - * and/or sell copies of the Software, and to permit persons to whom the - * Software is furnished to do so, subject to the following conditions: - * - * The above copyright notice including the dates of first publication and - * either this permission notice or a reference to - * http://oss.sgi.com/projects/FreeB/ - * shall be included in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS - * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL - * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, - * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF - * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - * - * Except as contained in this notice, the name of Silicon Graphics, Inc. - * shall not be used in advertising or otherwise to promote the sale, use or - * other dealings in this Software without prior written authorization from - * Silicon Graphics, Inc. - */ -/* -** Author: Eric Veach, July 1994. -** -*/ - -#ifndef __geom_h_ -#define __geom_h_ - -#include "mesh.h" - -#ifdef NO_BRANCH_CONDITIONS -/* MIPS architecture has special instructions to evaluate boolean - * conditions -- more efficient than branching, IF you can get the - * compiler to generate the right instructions (SGI compiler doesn't) - */ -#define VertEq(u,v) (((u)->s == (v)->s) & ((u)->t == (v)->t)) -#define VertLeq(u,v) (((u)->s < (v)->s) | \ - ((u)->s == (v)->s & (u)->t <= (v)->t)) -#else -#define VertEq(u,v) ((u)->s == (v)->s && (u)->t == (v)->t) -#define VertLeq(u,v) (((u)->s < (v)->s) || \ - ((u)->s == (v)->s && (u)->t <= (v)->t)) -#endif - -#define EdgeEval(u,v,w) __gl_edgeEval(u,v,w) -#define EdgeSign(u,v,w) __gl_edgeSign(u,v,w) - -/* Versions of VertLeq, EdgeSign, EdgeEval with s and t transposed. */ - -#define TransLeq(u,v) (((u)->t < (v)->t) || \ - ((u)->t == (v)->t && (u)->s <= (v)->s)) -#define TransEval(u,v,w) __gl_transEval(u,v,w) -#define TransSign(u,v,w) __gl_transSign(u,v,w) - - -#define EdgeGoesLeft(e) VertLeq( (e)->Dst, (e)->Org ) -#define EdgeGoesRight(e) VertLeq( (e)->Org, (e)->Dst ) - -#undef ABS -#define ABS(x) ((x) < 0 ? -(x) : (x)) -#define VertL1dist(u,v) (ABS(u->s - v->s) + ABS(u->t - v->t)) - -#define VertCCW(u,v,w) __gl_vertCCW(u,v,w) - -int __gl_vertLeq( GLUvertex *u, GLUvertex *v ); -GLdouble __gl_edgeEval( GLUvertex *u, GLUvertex *v, GLUvertex *w ); -GLdouble __gl_edgeSign( GLUvertex *u, GLUvertex *v, GLUvertex *w ); -GLdouble __gl_transEval( GLUvertex *u, GLUvertex *v, GLUvertex *w ); -GLdouble __gl_transSign( GLUvertex *u, GLUvertex *v, GLUvertex *w ); -int __gl_vertCCW( GLUvertex *u, GLUvertex *v, GLUvertex *w ); -void __gl_edgeIntersect( GLUvertex *o1, GLUvertex *d1, - GLUvertex *o2, GLUvertex *d2, - GLUvertex *v ); - -#endif diff --git a/src/glu/sgi/libtess/memalloc.c b/src/glu/sgi/libtess/memalloc.c deleted file mode 100644 index 81879ef782f..00000000000 --- a/src/glu/sgi/libtess/memalloc.c +++ /dev/null @@ -1,55 +0,0 @@ -/* - * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008) - * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved. - * - * Permission is hereby granted, free of charge, to any person obtaining a - * copy of this software and associated documentation files (the "Software"), - * to deal in the Software without restriction, including without limitation - * the rights to use, copy, modify, merge, publish, distribute, sublicense, - * and/or sell copies of the Software, and to permit persons to whom the - * Software is furnished to do so, subject to the following conditions: - * - * The above copyright notice including the dates of first publication and - * either this permission notice or a reference to - * http://oss.sgi.com/projects/FreeB/ - * shall be included in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS - * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL - * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, - * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF - * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - * - * Except as contained in this notice, the name of Silicon Graphics, Inc. - * shall not be used in advertising or otherwise to promote the sale, use or - * other dealings in this Software without prior written authorization from - * Silicon Graphics, Inc. - */ -/* -** Author: Eric Veach, July 1994. -** -*/ - -#include "memalloc.h" -#include "string.h" - -int __gl_memInit( size_t maxFast ) -{ -#ifndef NO_MALLOPT -/* mallopt( M_MXFAST, maxFast );*/ -#ifdef MEMORY_DEBUG - mallopt( M_DEBUG, 1 ); -#endif -#endif - return 1; -} - -#ifdef MEMORY_DEBUG -void *__gl_memAlloc( size_t n ) -{ - return memset( malloc( n ), 0xa5, n ); -} -#endif - diff --git a/src/glu/sgi/libtess/memalloc.h b/src/glu/sgi/libtess/memalloc.h deleted file mode 100644 index c2f969b8bea..00000000000 --- a/src/glu/sgi/libtess/memalloc.h +++ /dev/null @@ -1,54 +0,0 @@ -/* - * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008) - * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved. - * - * Permission is hereby granted, free of charge, to any person obtaining a - * copy of this software and associated documentation files (the "Software"), - * to deal in the Software without restriction, including without limitation - * the rights to use, copy, modify, merge, publish, distribute, sublicense, - * and/or sell copies of the Software, and to permit persons to whom the - * Software is furnished to do so, subject to the following conditions: - * - * The above copyright notice including the dates of first publication and - * either this permission notice or a reference to - * http://oss.sgi.com/projects/FreeB/ - * shall be included in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS - * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL - * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, - * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF - * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - * - * Except as contained in this notice, the name of Silicon Graphics, Inc. - * shall not be used in advertising or otherwise to promote the sale, use or - * other dealings in this Software without prior written authorization from - * Silicon Graphics, Inc. - */ -/* -** Author: Eric Veach, July 1994. -** -*/ - -#ifndef __memalloc_simple_h_ -#define __memalloc_simple_h_ - -#include <stdlib.h> - -#define memRealloc realloc -#define memFree free - -#define memInit __gl_memInit -/*extern void __gl_memInit( size_t );*/ -extern int __gl_memInit( size_t ); - -#ifndef MEMORY_DEBUG -#define memAlloc malloc -#else -#define memAlloc __gl_memAlloc -extern void * __gl_memAlloc( size_t ); -#endif - -#endif diff --git a/src/glu/sgi/libtess/mesh.c b/src/glu/sgi/libtess/mesh.c deleted file mode 100644 index 36cb3a7be29..00000000000 --- a/src/glu/sgi/libtess/mesh.c +++ /dev/null @@ -1,798 +0,0 @@ -/* - * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008) - * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved. - * - * Permission is hereby granted, free of charge, to any person obtaining a - * copy of this software and associated documentation files (the "Software"), - * to deal in the Software without restriction, including without limitation - * the rights to use, copy, modify, merge, publish, distribute, sublicense, - * and/or sell copies of the Software, and to permit persons to whom the - * Software is furnished to do so, subject to the following conditions: - * - * The above copyright notice including the dates of first publication and - * either this permission notice or a reference to - * http://oss.sgi.com/projects/FreeB/ - * shall be included in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS - * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL - * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, - * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF - * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - * - * Except as contained in this notice, the name of Silicon Graphics, Inc. - * shall not be used in advertising or otherwise to promote the sale, use or - * other dealings in this Software without prior written authorization from - * Silicon Graphics, Inc. - */ -/* -** Author: Eric Veach, July 1994. -** -*/ - -#include "gluos.h" -#include <stddef.h> -#include <assert.h> -#include "mesh.h" -#include "memalloc.h" - -#ifndef TRUE -#define TRUE 1 -#endif -#ifndef FALSE -#define FALSE 0 -#endif - -static GLUvertex *allocVertex() -{ - return (GLUvertex *)memAlloc( sizeof( GLUvertex )); -} - -static GLUface *allocFace() -{ - return (GLUface *)memAlloc( sizeof( GLUface )); -} - -/************************ Utility Routines ************************/ - -/* Allocate and free half-edges in pairs for efficiency. - * The *only* place that should use this fact is allocation/free. - */ -typedef struct { GLUhalfEdge e, eSym; } EdgePair; - -/* MakeEdge creates a new pair of half-edges which form their own loop. - * No vertex or face structures are allocated, but these must be assigned - * before the current edge operation is completed. - */ -static GLUhalfEdge *MakeEdge( GLUhalfEdge *eNext ) -{ - GLUhalfEdge *e; - GLUhalfEdge *eSym; - GLUhalfEdge *ePrev; - EdgePair *pair = (EdgePair *)memAlloc( sizeof( EdgePair )); - if (pair == NULL) return NULL; - - e = &pair->e; - eSym = &pair->eSym; - - /* Make sure eNext points to the first edge of the edge pair */ - if( eNext->Sym < eNext ) { eNext = eNext->Sym; } - - /* Insert in circular doubly-linked list before eNext. - * Note that the prev pointer is stored in Sym->next. - */ - ePrev = eNext->Sym->next; - eSym->next = ePrev; - ePrev->Sym->next = e; - e->next = eNext; - eNext->Sym->next = eSym; - - e->Sym = eSym; - e->Onext = e; - e->Lnext = eSym; - e->Org = NULL; - e->Lface = NULL; - e->winding = 0; - e->activeRegion = NULL; - - eSym->Sym = e; - eSym->Onext = eSym; - eSym->Lnext = e; - eSym->Org = NULL; - eSym->Lface = NULL; - eSym->winding = 0; - eSym->activeRegion = NULL; - - return e; -} - -/* Splice( a, b ) is best described by the Guibas/Stolfi paper or the - * CS348a notes (see mesh.h). Basically it modifies the mesh so that - * a->Onext and b->Onext are exchanged. This can have various effects - * depending on whether a and b belong to different face or vertex rings. - * For more explanation see __gl_meshSplice() below. - */ -static void Splice( GLUhalfEdge *a, GLUhalfEdge *b ) -{ - GLUhalfEdge *aOnext = a->Onext; - GLUhalfEdge *bOnext = b->Onext; - - aOnext->Sym->Lnext = b; - bOnext->Sym->Lnext = a; - a->Onext = bOnext; - b->Onext = aOnext; -} - -/* MakeVertex( newVertex, eOrig, vNext ) attaches a new vertex and makes it the - * origin of all edges in the vertex loop to which eOrig belongs. "vNext" gives - * a place to insert the new vertex in the global vertex list. We insert - * the new vertex *before* vNext so that algorithms which walk the vertex - * list will not see the newly created vertices. - */ -static void MakeVertex( GLUvertex *newVertex, - GLUhalfEdge *eOrig, GLUvertex *vNext ) -{ - GLUhalfEdge *e; - GLUvertex *vPrev; - GLUvertex *vNew = newVertex; - - assert(vNew != NULL); - - /* insert in circular doubly-linked list before vNext */ - vPrev = vNext->prev; - vNew->prev = vPrev; - vPrev->next = vNew; - vNew->next = vNext; - vNext->prev = vNew; - - vNew->anEdge = eOrig; - vNew->data = NULL; - /* leave coords, s, t undefined */ - - /* fix other edges on this vertex loop */ - e = eOrig; - do { - e->Org = vNew; - e = e->Onext; - } while( e != eOrig ); -} - -/* MakeFace( newFace, eOrig, fNext ) attaches a new face and makes it the left - * face of all edges in the face loop to which eOrig belongs. "fNext" gives - * a place to insert the new face in the global face list. We insert - * the new face *before* fNext so that algorithms which walk the face - * list will not see the newly created faces. - */ -static void MakeFace( GLUface *newFace, GLUhalfEdge *eOrig, GLUface *fNext ) -{ - GLUhalfEdge *e; - GLUface *fPrev; - GLUface *fNew = newFace; - - assert(fNew != NULL); - - /* insert in circular doubly-linked list before fNext */ - fPrev = fNext->prev; - fNew->prev = fPrev; - fPrev->next = fNew; - fNew->next = fNext; - fNext->prev = fNew; - - fNew->anEdge = eOrig; - fNew->data = NULL; - fNew->trail = NULL; - fNew->marked = FALSE; - - /* The new face is marked "inside" if the old one was. This is a - * convenience for the common case where a face has been split in two. - */ - fNew->inside = fNext->inside; - - /* fix other edges on this face loop */ - e = eOrig; - do { - e->Lface = fNew; - e = e->Lnext; - } while( e != eOrig ); -} - -/* KillEdge( eDel ) destroys an edge (the half-edges eDel and eDel->Sym), - * and removes from the global edge list. - */ -static void KillEdge( GLUhalfEdge *eDel ) -{ - GLUhalfEdge *ePrev, *eNext; - - /* Half-edges are allocated in pairs, see EdgePair above */ - if( eDel->Sym < eDel ) { eDel = eDel->Sym; } - - /* delete from circular doubly-linked list */ - eNext = eDel->next; - ePrev = eDel->Sym->next; - eNext->Sym->next = ePrev; - ePrev->Sym->next = eNext; - - memFree( eDel ); -} - - -/* KillVertex( vDel ) destroys a vertex and removes it from the global - * vertex list. It updates the vertex loop to point to a given new vertex. - */ -static void KillVertex( GLUvertex *vDel, GLUvertex *newOrg ) -{ - GLUhalfEdge *e, *eStart = vDel->anEdge; - GLUvertex *vPrev, *vNext; - - /* change the origin of all affected edges */ - e = eStart; - do { - e->Org = newOrg; - e = e->Onext; - } while( e != eStart ); - - /* delete from circular doubly-linked list */ - vPrev = vDel->prev; - vNext = vDel->next; - vNext->prev = vPrev; - vPrev->next = vNext; - - memFree( vDel ); -} - -/* KillFace( fDel ) destroys a face and removes it from the global face - * list. It updates the face loop to point to a given new face. - */ -static void KillFace( GLUface *fDel, GLUface *newLface ) -{ - GLUhalfEdge *e, *eStart = fDel->anEdge; - GLUface *fPrev, *fNext; - - /* change the left face of all affected edges */ - e = eStart; - do { - e->Lface = newLface; - e = e->Lnext; - } while( e != eStart ); - - /* delete from circular doubly-linked list */ - fPrev = fDel->prev; - fNext = fDel->next; - fNext->prev = fPrev; - fPrev->next = fNext; - - memFree( fDel ); -} - - -/****************** Basic Edge Operations **********************/ - -/* __gl_meshMakeEdge creates one edge, two vertices, and a loop (face). - * The loop consists of the two new half-edges. - */ -GLUhalfEdge *__gl_meshMakeEdge( GLUmesh *mesh ) -{ - GLUvertex *newVertex1= allocVertex(); - GLUvertex *newVertex2= allocVertex(); - GLUface *newFace= allocFace(); - GLUhalfEdge *e; - - /* if any one is null then all get freed */ - if (newVertex1 == NULL || newVertex2 == NULL || newFace == NULL) { - if (newVertex1 != NULL) memFree(newVertex1); - if (newVertex2 != NULL) memFree(newVertex2); - if (newFace != NULL) memFree(newFace); - return NULL; - } - - e = MakeEdge( &mesh->eHead ); - if (e == NULL) { - memFree(newVertex1); - memFree(newVertex2); - memFree(newFace); - return NULL; - } - - MakeVertex( newVertex1, e, &mesh->vHead ); - MakeVertex( newVertex2, e->Sym, &mesh->vHead ); - MakeFace( newFace, e, &mesh->fHead ); - return e; -} - - -/* __gl_meshSplice( eOrg, eDst ) is the basic operation for changing the - * mesh connectivity and topology. It changes the mesh so that - * eOrg->Onext <- OLD( eDst->Onext ) - * eDst->Onext <- OLD( eOrg->Onext ) - * where OLD(...) means the value before the meshSplice operation. - * - * This can have two effects on the vertex structure: - * - if eOrg->Org != eDst->Org, the two vertices are merged together - * - if eOrg->Org == eDst->Org, the origin is split into two vertices - * In both cases, eDst->Org is changed and eOrg->Org is untouched. - * - * Similarly (and independently) for the face structure, - * - if eOrg->Lface == eDst->Lface, one loop is split into two - * - if eOrg->Lface != eDst->Lface, two distinct loops are joined into one - * In both cases, eDst->Lface is changed and eOrg->Lface is unaffected. - * - * Some special cases: - * If eDst == eOrg, the operation has no effect. - * If eDst == eOrg->Lnext, the new face will have a single edge. - * If eDst == eOrg->Lprev, the old face will have a single edge. - * If eDst == eOrg->Onext, the new vertex will have a single edge. - * If eDst == eOrg->Oprev, the old vertex will have a single edge. - */ -int __gl_meshSplice( GLUhalfEdge *eOrg, GLUhalfEdge *eDst ) -{ - int joiningLoops = FALSE; - int joiningVertices = FALSE; - - if( eOrg == eDst ) return 1; - - if( eDst->Org != eOrg->Org ) { - /* We are merging two disjoint vertices -- destroy eDst->Org */ - joiningVertices = TRUE; - KillVertex( eDst->Org, eOrg->Org ); - } - if( eDst->Lface != eOrg->Lface ) { - /* We are connecting two disjoint loops -- destroy eDst->Lface */ - joiningLoops = TRUE; - KillFace( eDst->Lface, eOrg->Lface ); - } - - /* Change the edge structure */ - Splice( eDst, eOrg ); - - if( ! joiningVertices ) { - GLUvertex *newVertex= allocVertex(); - if (newVertex == NULL) return 0; - - /* We split one vertex into two -- the new vertex is eDst->Org. - * Make sure the old vertex points to a valid half-edge. - */ - MakeVertex( newVertex, eDst, eOrg->Org ); - eOrg->Org->anEdge = eOrg; - } - if( ! joiningLoops ) { - GLUface *newFace= allocFace(); - if (newFace == NULL) return 0; - - /* We split one loop into two -- the new loop is eDst->Lface. - * Make sure the old face points to a valid half-edge. - */ - MakeFace( newFace, eDst, eOrg->Lface ); - eOrg->Lface->anEdge = eOrg; - } - - return 1; -} - - -/* __gl_meshDelete( eDel ) removes the edge eDel. There are several cases: - * if (eDel->Lface != eDel->Rface), we join two loops into one; the loop - * eDel->Lface is deleted. Otherwise, we are splitting one loop into two; - * the newly created loop will contain eDel->Dst. If the deletion of eDel - * would create isolated vertices, those are deleted as well. - * - * This function could be implemented as two calls to __gl_meshSplice - * plus a few calls to memFree, but this would allocate and delete - * unnecessary vertices and faces. - */ -int __gl_meshDelete( GLUhalfEdge *eDel ) -{ - GLUhalfEdge *eDelSym = eDel->Sym; - int joiningLoops = FALSE; - - /* First step: disconnect the origin vertex eDel->Org. We make all - * changes to get a consistent mesh in this "intermediate" state. - */ - if( eDel->Lface != eDel->Rface ) { - /* We are joining two loops into one -- remove the left face */ - joiningLoops = TRUE; - KillFace( eDel->Lface, eDel->Rface ); - } - - if( eDel->Onext == eDel ) { - KillVertex( eDel->Org, NULL ); - } else { - /* Make sure that eDel->Org and eDel->Rface point to valid half-edges */ - eDel->Rface->anEdge = eDel->Oprev; - eDel->Org->anEdge = eDel->Onext; - - Splice( eDel, eDel->Oprev ); - if( ! joiningLoops ) { - GLUface *newFace= allocFace(); - if (newFace == NULL) return 0; - - /* We are splitting one loop into two -- create a new loop for eDel. */ - MakeFace( newFace, eDel, eDel->Lface ); - } - } - - /* Claim: the mesh is now in a consistent state, except that eDel->Org - * may have been deleted. Now we disconnect eDel->Dst. - */ - if( eDelSym->Onext == eDelSym ) { - KillVertex( eDelSym->Org, NULL ); - KillFace( eDelSym->Lface, NULL ); - } else { - /* Make sure that eDel->Dst and eDel->Lface point to valid half-edges */ - eDel->Lface->anEdge = eDelSym->Oprev; - eDelSym->Org->anEdge = eDelSym->Onext; - Splice( eDelSym, eDelSym->Oprev ); - } - - /* Any isolated vertices or faces have already been freed. */ - KillEdge( eDel ); - - return 1; -} - - -/******************** Other Edge Operations **********************/ - -/* All these routines can be implemented with the basic edge - * operations above. They are provided for convenience and efficiency. - */ - - -/* __gl_meshAddEdgeVertex( eOrg ) creates a new edge eNew such that - * eNew == eOrg->Lnext, and eNew->Dst is a newly created vertex. - * eOrg and eNew will have the same left face. - */ -GLUhalfEdge *__gl_meshAddEdgeVertex( GLUhalfEdge *eOrg ) -{ - GLUhalfEdge *eNewSym; - GLUhalfEdge *eNew = MakeEdge( eOrg ); - if (eNew == NULL) return NULL; - - eNewSym = eNew->Sym; - - /* Connect the new edge appropriately */ - Splice( eNew, eOrg->Lnext ); - - /* Set the vertex and face information */ - eNew->Org = eOrg->Dst; - { - GLUvertex *newVertex= allocVertex(); - if (newVertex == NULL) return NULL; - - MakeVertex( newVertex, eNewSym, eNew->Org ); - } - eNew->Lface = eNewSym->Lface = eOrg->Lface; - - return eNew; -} - - -/* __gl_meshSplitEdge( eOrg ) splits eOrg into two edges eOrg and eNew, - * such that eNew == eOrg->Lnext. The new vertex is eOrg->Dst == eNew->Org. - * eOrg and eNew will have the same left face. - */ -GLUhalfEdge *__gl_meshSplitEdge( GLUhalfEdge *eOrg ) -{ - GLUhalfEdge *eNew; - GLUhalfEdge *tempHalfEdge= __gl_meshAddEdgeVertex( eOrg ); - if (tempHalfEdge == NULL) return NULL; - - eNew = tempHalfEdge->Sym; - - /* Disconnect eOrg from eOrg->Dst and connect it to eNew->Org */ - Splice( eOrg->Sym, eOrg->Sym->Oprev ); - Splice( eOrg->Sym, eNew ); - - /* Set the vertex and face information */ - eOrg->Dst = eNew->Org; - eNew->Dst->anEdge = eNew->Sym; /* may have pointed to eOrg->Sym */ - eNew->Rface = eOrg->Rface; - eNew->winding = eOrg->winding; /* copy old winding information */ - eNew->Sym->winding = eOrg->Sym->winding; - - return eNew; -} - - -/* __gl_meshConnect( eOrg, eDst ) creates a new edge from eOrg->Dst - * to eDst->Org, and returns the corresponding half-edge eNew. - * If eOrg->Lface == eDst->Lface, this splits one loop into two, - * and the newly created loop is eNew->Lface. Otherwise, two disjoint - * loops are merged into one, and the loop eDst->Lface is destroyed. - * - * If (eOrg == eDst), the new face will have only two edges. - * If (eOrg->Lnext == eDst), the old face is reduced to a single edge. - * If (eOrg->Lnext->Lnext == eDst), the old face is reduced to two edges. - */ -GLUhalfEdge *__gl_meshConnect( GLUhalfEdge *eOrg, GLUhalfEdge *eDst ) -{ - GLUhalfEdge *eNewSym; - int joiningLoops = FALSE; - GLUhalfEdge *eNew = MakeEdge( eOrg ); - if (eNew == NULL) return NULL; - - eNewSym = eNew->Sym; - - if( eDst->Lface != eOrg->Lface ) { - /* We are connecting two disjoint loops -- destroy eDst->Lface */ - joiningLoops = TRUE; - KillFace( eDst->Lface, eOrg->Lface ); - } - - /* Connect the new edge appropriately */ - Splice( eNew, eOrg->Lnext ); - Splice( eNewSym, eDst ); - - /* Set the vertex and face information */ - eNew->Org = eOrg->Dst; - eNewSym->Org = eDst->Org; - eNew->Lface = eNewSym->Lface = eOrg->Lface; - - /* Make sure the old face points to a valid half-edge */ - eOrg->Lface->anEdge = eNewSym; - - if( ! joiningLoops ) { - GLUface *newFace= allocFace(); - if (newFace == NULL) return NULL; - - /* We split one loop into two -- the new loop is eNew->Lface */ - MakeFace( newFace, eNew, eOrg->Lface ); - } - return eNew; -} - - -/******************** Other Operations **********************/ - -/* __gl_meshZapFace( fZap ) destroys a face and removes it from the - * global face list. All edges of fZap will have a NULL pointer as their - * left face. Any edges which also have a NULL pointer as their right face - * are deleted entirely (along with any isolated vertices this produces). - * An entire mesh can be deleted by zapping its faces, one at a time, - * in any order. Zapped faces cannot be used in further mesh operations! - */ -void __gl_meshZapFace( GLUface *fZap ) -{ - GLUhalfEdge *eStart = fZap->anEdge; - GLUhalfEdge *e, *eNext, *eSym; - GLUface *fPrev, *fNext; - - /* walk around face, deleting edges whose right face is also NULL */ - eNext = eStart->Lnext; - do { - e = eNext; - eNext = e->Lnext; - - e->Lface = NULL; - if( e->Rface == NULL ) { - /* delete the edge -- see __gl_MeshDelete above */ - - if( e->Onext == e ) { - KillVertex( e->Org, NULL ); - } else { - /* Make sure that e->Org points to a valid half-edge */ - e->Org->anEdge = e->Onext; - Splice( e, e->Oprev ); - } - eSym = e->Sym; - if( eSym->Onext == eSym ) { - KillVertex( eSym->Org, NULL ); - } else { - /* Make sure that eSym->Org points to a valid half-edge */ - eSym->Org->anEdge = eSym->Onext; - Splice( eSym, eSym->Oprev ); - } - KillEdge( e ); - } - } while( e != eStart ); - - /* delete from circular doubly-linked list */ - fPrev = fZap->prev; - fNext = fZap->next; - fNext->prev = fPrev; - fPrev->next = fNext; - - memFree( fZap ); -} - - -/* __gl_meshNewMesh() creates a new mesh with no edges, no vertices, - * and no loops (what we usually call a "face"). - */ -GLUmesh *__gl_meshNewMesh( void ) -{ - GLUvertex *v; - GLUface *f; - GLUhalfEdge *e; - GLUhalfEdge *eSym; - GLUmesh *mesh = (GLUmesh *)memAlloc( sizeof( GLUmesh )); - if (mesh == NULL) { - return NULL; - } - - v = &mesh->vHead; - f = &mesh->fHead; - e = &mesh->eHead; - eSym = &mesh->eHeadSym; - - v->next = v->prev = v; - v->anEdge = NULL; - v->data = NULL; - - f->next = f->prev = f; - f->anEdge = NULL; - f->data = NULL; - f->trail = NULL; - f->marked = FALSE; - f->inside = FALSE; - - e->next = e; - e->Sym = eSym; - e->Onext = NULL; - e->Lnext = NULL; - e->Org = NULL; - e->Lface = NULL; - e->winding = 0; - e->activeRegion = NULL; - - eSym->next = eSym; - eSym->Sym = e; - eSym->Onext = NULL; - eSym->Lnext = NULL; - eSym->Org = NULL; - eSym->Lface = NULL; - eSym->winding = 0; - eSym->activeRegion = NULL; - - return mesh; -} - - -/* __gl_meshUnion( mesh1, mesh2 ) forms the union of all structures in - * both meshes, and returns the new mesh (the old meshes are destroyed). - */ -GLUmesh *__gl_meshUnion( GLUmesh *mesh1, GLUmesh *mesh2 ) -{ - GLUface *f1 = &mesh1->fHead; - GLUvertex *v1 = &mesh1->vHead; - GLUhalfEdge *e1 = &mesh1->eHead; - GLUface *f2 = &mesh2->fHead; - GLUvertex *v2 = &mesh2->vHead; - GLUhalfEdge *e2 = &mesh2->eHead; - - /* Add the faces, vertices, and edges of mesh2 to those of mesh1 */ - if( f2->next != f2 ) { - f1->prev->next = f2->next; - f2->next->prev = f1->prev; - f2->prev->next = f1; - f1->prev = f2->prev; - } - - if( v2->next != v2 ) { - v1->prev->next = v2->next; - v2->next->prev = v1->prev; - v2->prev->next = v1; - v1->prev = v2->prev; - } - - if( e2->next != e2 ) { - e1->Sym->next->Sym->next = e2->next; - e2->next->Sym->next = e1->Sym->next; - e2->Sym->next->Sym->next = e1; - e1->Sym->next = e2->Sym->next; - } - - memFree( mesh2 ); - return mesh1; -} - - -#ifdef DELETE_BY_ZAPPING - -/* __gl_meshDeleteMesh( mesh ) will free all storage for any valid mesh. - */ -void __gl_meshDeleteMesh( GLUmesh *mesh ) -{ - GLUface *fHead = &mesh->fHead; - - while( fHead->next != fHead ) { - __gl_meshZapFace( fHead->next ); - } - assert( mesh->vHead.next == &mesh->vHead ); - - memFree( mesh ); -} - -#else - -/* __gl_meshDeleteMesh( mesh ) will free all storage for any valid mesh. - */ -void __gl_meshDeleteMesh( GLUmesh *mesh ) -{ - GLUface *f, *fNext; - GLUvertex *v, *vNext; - GLUhalfEdge *e, *eNext; - - for( f = mesh->fHead.next; f != &mesh->fHead; f = fNext ) { - fNext = f->next; - memFree( f ); - } - - for( v = mesh->vHead.next; v != &mesh->vHead; v = vNext ) { - vNext = v->next; - memFree( v ); - } - - for( e = mesh->eHead.next; e != &mesh->eHead; e = eNext ) { - /* One call frees both e and e->Sym (see EdgePair above) */ - eNext = e->next; - memFree( e ); - } - - memFree( mesh ); -} - -#endif - -#ifndef NDEBUG - -/* __gl_meshCheckMesh( mesh ) checks a mesh for self-consistency. - */ -void __gl_meshCheckMesh( GLUmesh *mesh ) -{ - GLUface *fHead = &mesh->fHead; - GLUvertex *vHead = &mesh->vHead; - GLUhalfEdge *eHead = &mesh->eHead; - GLUface *f, *fPrev; - GLUvertex *v, *vPrev; - GLUhalfEdge *e, *ePrev; - - fPrev = fHead; - for( fPrev = fHead ; (f = fPrev->next) != fHead; fPrev = f) { - assert( f->prev == fPrev ); - e = f->anEdge; - do { - assert( e->Sym != e ); - assert( e->Sym->Sym == e ); - assert( e->Lnext->Onext->Sym == e ); - assert( e->Onext->Sym->Lnext == e ); - assert( e->Lface == f ); - e = e->Lnext; - } while( e != f->anEdge ); - } - assert( f->prev == fPrev && f->anEdge == NULL && f->data == NULL ); - - vPrev = vHead; - for( vPrev = vHead ; (v = vPrev->next) != vHead; vPrev = v) { - assert( v->prev == vPrev ); - e = v->anEdge; - do { - assert( e->Sym != e ); - assert( e->Sym->Sym == e ); - assert( e->Lnext->Onext->Sym == e ); - assert( e->Onext->Sym->Lnext == e ); - assert( e->Org == v ); - e = e->Onext; - } while( e != v->anEdge ); - } - assert( v->prev == vPrev && v->anEdge == NULL && v->data == NULL ); - - ePrev = eHead; - for( ePrev = eHead ; (e = ePrev->next) != eHead; ePrev = e) { - assert( e->Sym->next == ePrev->Sym ); - assert( e->Sym != e ); - assert( e->Sym->Sym == e ); - assert( e->Org != NULL ); - assert( e->Dst != NULL ); - assert( e->Lnext->Onext->Sym == e ); - assert( e->Onext->Sym->Lnext == e ); - } - assert( e->Sym->next == ePrev->Sym - && e->Sym == &mesh->eHeadSym - && e->Sym->Sym == e - && e->Org == NULL && e->Dst == NULL - && e->Lface == NULL && e->Rface == NULL ); -} - -#endif diff --git a/src/glu/sgi/libtess/mesh.h b/src/glu/sgi/libtess/mesh.h deleted file mode 100644 index 690c5f2f696..00000000000 --- a/src/glu/sgi/libtess/mesh.h +++ /dev/null @@ -1,266 +0,0 @@ -/* - * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008) - * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved. - * - * Permission is hereby granted, free of charge, to any person obtaining a - * copy of this software and associated documentation files (the "Software"), - * to deal in the Software without restriction, including without limitation - * the rights to use, copy, modify, merge, publish, distribute, sublicense, - * and/or sell copies of the Software, and to permit persons to whom the - * Software is furnished to do so, subject to the following conditions: - * - * The above copyright notice including the dates of first publication and - * either this permission notice or a reference to - * http://oss.sgi.com/projects/FreeB/ - * shall be included in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS - * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL - * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, - * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF - * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - * - * Except as contained in this notice, the name of Silicon Graphics, Inc. - * shall not be used in advertising or otherwise to promote the sale, use or - * other dealings in this Software without prior written authorization from - * Silicon Graphics, Inc. - */ -/* -** Author: Eric Veach, July 1994. -** -*/ - -#ifndef __mesh_h_ -#define __mesh_h_ - -#include <GL/glu.h> - -typedef struct GLUmesh GLUmesh; - -typedef struct GLUvertex GLUvertex; -typedef struct GLUface GLUface; -typedef struct GLUhalfEdge GLUhalfEdge; - -typedef struct ActiveRegion ActiveRegion; /* Internal data */ - -/* The mesh structure is similar in spirit, notation, and operations - * to the "quad-edge" structure (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 a simplified description, see the course notes for CS348a, - * "Mathematical Foundations of Computer Graphics", available at the - * Stanford bookstore (and taught during the fall quarter). - * The implementation also borrows a tiny subset of the graph-based approach - * use in Mantyla's Geometric Work Bench (see M. Mantyla, An Introduction - * to Sold Modeling, Computer Science Press, Rockville, Maryland, 1988). - * - * The fundamental data structure is the "half-edge". Two half-edges - * go together to make an edge, but they point in opposite directions. - * Each half-edge has a pointer to its mate (the "symmetric" half-edge Sym), - * its origin vertex (Org), the face on its left side (Lface), and the - * adjacent half-edges in the CCW direction around the origin vertex - * (Onext) and around the left face (Lnext). There is also a "next" - * pointer for the global edge list (see below). - * - * The notation used for mesh navigation: - * Sym = the mate of a half-edge (same edge, but opposite direction) - * Onext = edge CCW around origin vertex (keep same origin) - * Dnext = edge CCW around destination vertex (keep same dest) - * Lnext = edge CCW around left face (dest becomes new origin) - * Rnext = edge CCW around right face (origin becomes new dest) - * - * "prev" means to substitute CW for CCW in the definitions above. - * - * The mesh keeps global lists of all vertices, faces, and edges, - * stored as doubly-linked circular lists with a dummy header node. - * The mesh stores pointers to these dummy headers (vHead, fHead, eHead). - * - * The circular edge list is special; since half-edges always occur - * in pairs (e and e->Sym), each half-edge stores a pointer in only - * one direction. Starting at eHead and following the e->next pointers - * will visit each *edge* once (ie. e or e->Sym, but not both). - * e->Sym stores a pointer in the opposite direction, thus it is - * always true that e->Sym->next->Sym->next == e. - * - * Each vertex has a pointer to next and previous vertices in the - * circular list, and a pointer to a half-edge with this vertex as - * the origin (NULL if this is the dummy header). There is also a - * field "data" for client data. - * - * Each face has a pointer to the next and previous faces in the - * circular list, and a pointer to a half-edge with this face as - * the left face (NULL if this is the dummy header). There is also - * a field "data" for client data. - * - * Note that what we call a "face" is really a loop; faces may consist - * of more than one loop (ie. not simply connected), but there is no - * record of this in the data structure. The mesh may consist of - * several disconnected regions, so it may not be possible to visit - * the entire mesh by starting at a half-edge and traversing the edge - * structure. - * - * The mesh does NOT support isolated vertices; a vertex is deleted along - * with its last edge. Similarly when two faces are merged, one of the - * faces is deleted (see __gl_meshDelete below). For mesh operations, - * all face (loop) and vertex pointers must not be NULL. However, once - * mesh manipulation is finished, __gl_MeshZapFace can be used to delete - * faces of the mesh, one at a time. All external faces can be "zapped" - * before the mesh is returned to the client; then a NULL face indicates - * a region which is not part of the output polygon. - */ - -struct GLUvertex { - GLUvertex *next; /* next vertex (never NULL) */ - GLUvertex *prev; /* previous vertex (never NULL) */ - GLUhalfEdge *anEdge; /* a half-edge with this origin */ - void *data; /* client's data */ - - /* Internal data (keep hidden) */ - GLdouble coords[3]; /* vertex location in 3D */ - GLdouble s, t; /* projection onto the sweep plane */ - long pqHandle; /* to allow deletion from priority queue */ -}; - -struct GLUface { - GLUface *next; /* next face (never NULL) */ - GLUface *prev; /* previous face (never NULL) */ - GLUhalfEdge *anEdge; /* a half edge with this left face */ - void *data; /* room for client's data */ - - /* Internal data (keep hidden) */ - GLUface *trail; /* "stack" for conversion to strips */ - GLboolean marked; /* flag for conversion to strips */ - GLboolean inside; /* this face is in the polygon interior */ -}; - -struct GLUhalfEdge { - GLUhalfEdge *next; /* doubly-linked list (prev==Sym->next) */ - GLUhalfEdge *Sym; /* same edge, opposite direction */ - GLUhalfEdge *Onext; /* next edge CCW around origin */ - GLUhalfEdge *Lnext; /* next edge CCW around left face */ - GLUvertex *Org; /* origin vertex (Overtex too long) */ - GLUface *Lface; /* left face */ - - /* Internal data (keep hidden) */ - ActiveRegion *activeRegion; /* a region with this upper edge (sweep.c) */ - int winding; /* change in winding number when crossing - from the right face to the left face */ -}; - -#define Rface Sym->Lface -#define Dst Sym->Org - -#define Oprev Sym->Lnext -#define Lprev Onext->Sym -#define Dprev Lnext->Sym -#define Rprev Sym->Onext -#define Dnext Rprev->Sym /* 3 pointers */ -#define Rnext Oprev->Sym /* 3 pointers */ - - -struct GLUmesh { - GLUvertex vHead; /* dummy header for vertex list */ - GLUface fHead; /* dummy header for face list */ - GLUhalfEdge eHead; /* dummy header for edge list */ - GLUhalfEdge eHeadSym; /* and its symmetric counterpart */ -}; - -/* The mesh operations below have three motivations: completeness, - * convenience, and efficiency. The basic mesh operations are MakeEdge, - * Splice, and Delete. All the other edge operations can be implemented - * in terms of these. The other operations are provided for convenience - * and/or efficiency. - * - * When a face is split or a vertex is added, they are inserted into the - * global list *before* the existing vertex or face (ie. e->Org or e->Lface). - * This makes it easier to process all vertices or faces in the global lists - * without worrying about processing the same data twice. As a convenience, - * when a face is split, the "inside" flag is copied from the old face. - * Other internal data (v->data, v->activeRegion, f->data, f->marked, - * f->trail, e->winding) is set to zero. - * - * ********************** Basic Edge Operations ************************** - * - * __gl_meshMakeEdge( mesh ) creates one edge, two vertices, and a loop. - * The loop (face) consists of the two new half-edges. - * - * __gl_meshSplice( eOrg, eDst ) is the basic operation for changing the - * mesh connectivity and topology. It changes the mesh so that - * eOrg->Onext <- OLD( eDst->Onext ) - * eDst->Onext <- OLD( eOrg->Onext ) - * where OLD(...) means the value before the meshSplice operation. - * - * This can have two effects on the vertex structure: - * - if eOrg->Org != eDst->Org, the two vertices are merged together - * - if eOrg->Org == eDst->Org, the origin is split into two vertices - * In both cases, eDst->Org is changed and eOrg->Org is untouched. - * - * Similarly (and independently) for the face structure, - * - if eOrg->Lface == eDst->Lface, one loop is split into two - * - if eOrg->Lface != eDst->Lface, two distinct loops are joined into one - * In both cases, eDst->Lface is changed and eOrg->Lface is unaffected. - * - * __gl_meshDelete( eDel ) removes the edge eDel. There are several cases: - * if (eDel->Lface != eDel->Rface), we join two loops into one; the loop - * eDel->Lface is deleted. Otherwise, we are splitting one loop into two; - * the newly created loop will contain eDel->Dst. If the deletion of eDel - * would create isolated vertices, those are deleted as well. - * - * ********************** Other Edge Operations ************************** - * - * __gl_meshAddEdgeVertex( eOrg ) creates a new edge eNew such that - * eNew == eOrg->Lnext, and eNew->Dst is a newly created vertex. - * eOrg and eNew will have the same left face. - * - * __gl_meshSplitEdge( eOrg ) splits eOrg into two edges eOrg and eNew, - * such that eNew == eOrg->Lnext. The new vertex is eOrg->Dst == eNew->Org. - * eOrg and eNew will have the same left face. - * - * __gl_meshConnect( eOrg, eDst ) creates a new edge from eOrg->Dst - * to eDst->Org, and returns the corresponding half-edge eNew. - * If eOrg->Lface == eDst->Lface, this splits one loop into two, - * and the newly created loop is eNew->Lface. Otherwise, two disjoint - * loops are merged into one, and the loop eDst->Lface is destroyed. - * - * ************************ Other Operations ***************************** - * - * __gl_meshNewMesh() creates a new mesh with no edges, no vertices, - * and no loops (what we usually call a "face"). - * - * __gl_meshUnion( mesh1, mesh2 ) forms the union of all structures in - * both meshes, and returns the new mesh (the old meshes are destroyed). - * - * __gl_meshDeleteMesh( mesh ) will free all storage for any valid mesh. - * - * __gl_meshZapFace( fZap ) destroys a face and removes it from the - * global face list. All edges of fZap will have a NULL pointer as their - * left face. Any edges which also have a NULL pointer as their right face - * are deleted entirely (along with any isolated vertices this produces). - * An entire mesh can be deleted by zapping its faces, one at a time, - * in any order. Zapped faces cannot be used in further mesh operations! - * - * __gl_meshCheckMesh( mesh ) checks a mesh for self-consistency. - */ - -GLUhalfEdge *__gl_meshMakeEdge( GLUmesh *mesh ); -int __gl_meshSplice( GLUhalfEdge *eOrg, GLUhalfEdge *eDst ); -int __gl_meshDelete( GLUhalfEdge *eDel ); - -GLUhalfEdge *__gl_meshAddEdgeVertex( GLUhalfEdge *eOrg ); -GLUhalfEdge *__gl_meshSplitEdge( GLUhalfEdge *eOrg ); -GLUhalfEdge *__gl_meshConnect( GLUhalfEdge *eOrg, GLUhalfEdge *eDst ); - -GLUmesh *__gl_meshNewMesh( void ); -GLUmesh *__gl_meshUnion( GLUmesh *mesh1, GLUmesh *mesh2 ); -void __gl_meshDeleteMesh( GLUmesh *mesh ); -void __gl_meshZapFace( GLUface *fZap ); - -#ifdef NDEBUG -#define __gl_meshCheckMesh( mesh ) -#else -void __gl_meshCheckMesh( GLUmesh *mesh ); -#endif - -#endif diff --git a/src/glu/sgi/libtess/normal.c b/src/glu/sgi/libtess/normal.c deleted file mode 100644 index 9a3bd43d3c9..00000000000 --- a/src/glu/sgi/libtess/normal.c +++ /dev/null @@ -1,257 +0,0 @@ -/* - * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008) - * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved. - * - * Permission is hereby granted, free of charge, to any person obtaining a - * copy of this software and associated documentation files (the "Software"), - * to deal in the Software without restriction, including without limitation - * the rights to use, copy, modify, merge, publish, distribute, sublicense, - * and/or sell copies of the Software, and to permit persons to whom the - * Software is furnished to do so, subject to the following conditions: - * - * The above copyright notice including the dates of first publication and - * either this permission notice or a reference to - * http://oss.sgi.com/projects/FreeB/ - * shall be included in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS - * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL - * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, - * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF - * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - * - * Except as contained in this notice, the name of Silicon Graphics, Inc. - * shall not be used in advertising or otherwise to promote the sale, use or - * other dealings in this Software without prior written authorization from - * Silicon Graphics, Inc. - */ -/* -** Author: Eric Veach, July 1994. -** -*/ - -#include "gluos.h" -#include "mesh.h" -#include "tess.h" -#include "normal.h" -#include <math.h> -#include <assert.h> - -#ifndef TRUE -#define TRUE 1 -#endif -#ifndef FALSE -#define FALSE 0 -#endif - -#define Dot(u,v) (u[0]*v[0] + u[1]*v[1] + u[2]*v[2]) - -#if 0 -static void Normalize( GLdouble v[3] ) -{ - GLdouble len = v[0]*v[0] + v[1]*v[1] + v[2]*v[2]; - - assert( len > 0 ); - len = sqrt( len ); - v[0] /= len; - v[1] /= len; - v[2] /= len; -} -#endif - -#undef ABS -#define ABS(x) ((x) < 0 ? -(x) : (x)) - -static int LongAxis( GLdouble v[3] ) -{ - int i = 0; - - if( ABS(v[1]) > ABS(v[0]) ) { i = 1; } - if( ABS(v[2]) > ABS(v[i]) ) { i = 2; } - return i; -} - -static void ComputeNormal( GLUtesselator *tess, GLdouble norm[3] ) -{ - GLUvertex *v, *v1, *v2; - GLdouble c, tLen2, maxLen2; - GLdouble maxVal[3], minVal[3], d1[3], d2[3], tNorm[3]; - GLUvertex *maxVert[3], *minVert[3]; - GLUvertex *vHead = &tess->mesh->vHead; - int i; - - maxVal[0] = maxVal[1] = maxVal[2] = -2 * GLU_TESS_MAX_COORD; - minVal[0] = minVal[1] = minVal[2] = 2 * GLU_TESS_MAX_COORD; - - for( v = vHead->next; v != vHead; v = v->next ) { - for( i = 0; i < 3; ++i ) { - c = v->coords[i]; - if( c < minVal[i] ) { minVal[i] = c; minVert[i] = v; } - if( c > maxVal[i] ) { maxVal[i] = c; maxVert[i] = v; } - } - } - - /* Find two vertices separated by at least 1/sqrt(3) of the maximum - * distance between any two vertices - */ - i = 0; - if( maxVal[1] - minVal[1] > maxVal[0] - minVal[0] ) { i = 1; } - if( maxVal[2] - minVal[2] > maxVal[i] - minVal[i] ) { i = 2; } - if( minVal[i] >= maxVal[i] ) { - /* All vertices are the same -- normal doesn't matter */ - norm[0] = 0; norm[1] = 0; norm[2] = 1; - return; - } - - /* Look for a third vertex which forms the triangle with maximum area - * (Length of normal == twice the triangle area) - */ - maxLen2 = 0; - v1 = minVert[i]; - v2 = maxVert[i]; - d1[0] = v1->coords[0] - v2->coords[0]; - d1[1] = v1->coords[1] - v2->coords[1]; - d1[2] = v1->coords[2] - v2->coords[2]; - for( v = vHead->next; v != vHead; v = v->next ) { - d2[0] = v->coords[0] - v2->coords[0]; - d2[1] = v->coords[1] - v2->coords[1]; - d2[2] = v->coords[2] - v2->coords[2]; - tNorm[0] = d1[1]*d2[2] - d1[2]*d2[1]; - tNorm[1] = d1[2]*d2[0] - d1[0]*d2[2]; - tNorm[2] = d1[0]*d2[1] - d1[1]*d2[0]; - tLen2 = tNorm[0]*tNorm[0] + tNorm[1]*tNorm[1] + tNorm[2]*tNorm[2]; - if( tLen2 > maxLen2 ) { - maxLen2 = tLen2; - norm[0] = tNorm[0]; - norm[1] = tNorm[1]; - norm[2] = tNorm[2]; - } - } - - if( maxLen2 <= 0 ) { - /* All points lie on a single line -- any decent normal will do */ - norm[0] = norm[1] = norm[2] = 0; - norm[LongAxis(d1)] = 1; - } -} - - -static void CheckOrientation( GLUtesselator *tess ) -{ - GLdouble area; - GLUface *f, *fHead = &tess->mesh->fHead; - GLUvertex *v, *vHead = &tess->mesh->vHead; - GLUhalfEdge *e; - - /* When we compute the normal automatically, we choose the orientation - * so that the sum of the signed areas of all contours is non-negative. - */ - area = 0; - for( f = fHead->next; f != fHead; f = f->next ) { - e = f->anEdge; - if( e->winding <= 0 ) continue; - do { - area += (e->Org->s - e->Dst->s) * (e->Org->t + e->Dst->t); - e = e->Lnext; - } while( e != f->anEdge ); - } - if( area < 0 ) { - /* Reverse the orientation by flipping all the t-coordinates */ - for( v = vHead->next; v != vHead; v = v->next ) { - v->t = - v->t; - } - tess->tUnit[0] = - tess->tUnit[0]; - tess->tUnit[1] = - tess->tUnit[1]; - tess->tUnit[2] = - tess->tUnit[2]; - } -} - -#ifdef FOR_TRITE_TEST_PROGRAM -#include <stdlib.h> -extern int RandomSweep; -#define S_UNIT_X (RandomSweep ? (2*drand48()-1) : 1.0) -#define S_UNIT_Y (RandomSweep ? (2*drand48()-1) : 0.0) -#else -#if defined(SLANTED_SWEEP) -/* The "feature merging" is not intended to be complete. There are - * special cases where edges are nearly parallel to the sweep line - * which are not implemented. The algorithm should still behave - * robustly (ie. produce a reasonable tesselation) in the presence - * of such edges, however it may miss features which could have been - * merged. We could minimize this effect by choosing the sweep line - * direction to be something unusual (ie. not parallel to one of the - * coordinate axes). - */ -#define S_UNIT_X 0.50941539564955385 /* Pre-normalized */ -#define S_UNIT_Y 0.86052074622010633 -#else -#define S_UNIT_X 1.0 -#define S_UNIT_Y 0.0 -#endif -#endif - -/* Determine the polygon normal and project vertices onto the plane - * of the polygon. - */ -void __gl_projectPolygon( GLUtesselator *tess ) -{ - GLUvertex *v, *vHead = &tess->mesh->vHead; - GLdouble norm[3]; - GLdouble *sUnit, *tUnit; - int i, computedNormal = FALSE; - - norm[0] = tess->normal[0]; - norm[1] = tess->normal[1]; - norm[2] = tess->normal[2]; - if( norm[0] == 0 && norm[1] == 0 && norm[2] == 0 ) { - ComputeNormal( tess, norm ); - computedNormal = TRUE; - } - sUnit = tess->sUnit; - tUnit = tess->tUnit; - i = LongAxis( norm ); - -#if defined(FOR_TRITE_TEST_PROGRAM) || defined(TRUE_PROJECT) - /* Choose the initial sUnit vector to be approximately perpendicular - * to the normal. - */ - Normalize( norm ); - - sUnit[i] = 0; - sUnit[(i+1)%3] = S_UNIT_X; - sUnit[(i+2)%3] = S_UNIT_Y; - - /* Now make it exactly perpendicular */ - w = Dot( sUnit, norm ); - sUnit[0] -= w * norm[0]; - sUnit[1] -= w * norm[1]; - sUnit[2] -= w * norm[2]; - Normalize( sUnit ); - - /* Choose tUnit so that (sUnit,tUnit,norm) form a right-handed frame */ - tUnit[0] = norm[1]*sUnit[2] - norm[2]*sUnit[1]; - tUnit[1] = norm[2]*sUnit[0] - norm[0]*sUnit[2]; - tUnit[2] = norm[0]*sUnit[1] - norm[1]*sUnit[0]; - Normalize( tUnit ); -#else - /* Project perpendicular to a coordinate axis -- better numerically */ - sUnit[i] = 0; - sUnit[(i+1)%3] = S_UNIT_X; - sUnit[(i+2)%3] = S_UNIT_Y; - - tUnit[i] = 0; - tUnit[(i+1)%3] = (norm[i] > 0) ? -S_UNIT_Y : S_UNIT_Y; - tUnit[(i+2)%3] = (norm[i] > 0) ? S_UNIT_X : -S_UNIT_X; -#endif - - /* Project the vertices onto the sweep plane */ - for( v = vHead->next; v != vHead; v = v->next ) { - v->s = Dot( v->coords, sUnit ); - v->t = Dot( v->coords, tUnit ); - } - if( computedNormal ) { - CheckOrientation( tess ); - } -} diff --git a/src/glu/sgi/libtess/normal.h b/src/glu/sgi/libtess/normal.h deleted file mode 100644 index c376ca44523..00000000000 --- a/src/glu/sgi/libtess/normal.h +++ /dev/null @@ -1,45 +0,0 @@ -/* - * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008) - * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved. - * - * Permission is hereby granted, free of charge, to any person obtaining a - * copy of this software and associated documentation files (the "Software"), - * to deal in the Software without restriction, including without limitation - * the rights to use, copy, modify, merge, publish, distribute, sublicense, - * and/or sell copies of the Software, and to permit persons to whom the - * Software is furnished to do so, subject to the following conditions: - * - * The above copyright notice including the dates of first publication and - * either this permission notice or a reference to - * http://oss.sgi.com/projects/FreeB/ - * shall be included in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS - * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL - * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, - * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF - * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - * - * Except as contained in this notice, the name of Silicon Graphics, Inc. - * shall not be used in advertising or otherwise to promote the sale, use or - * other dealings in this Software without prior written authorization from - * Silicon Graphics, Inc. - */ -/* -** Author: Eric Veach, July 1994. -** -*/ - -#ifndef __normal_h_ -#define __normal_h_ - -#include "tess.h" - -/* __gl_projectPolygon( tess ) determines the polygon normal - * and project vertices onto the plane of the polygon. - */ -void __gl_projectPolygon( GLUtesselator *tess ); - -#endif diff --git a/src/glu/sgi/libtess/priorityq-heap.c b/src/glu/sgi/libtess/priorityq-heap.c deleted file mode 100644 index 52698b59cc5..00000000000 --- a/src/glu/sgi/libtess/priorityq-heap.c +++ /dev/null @@ -1,256 +0,0 @@ -/* - * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008) - * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved. - * - * Permission is hereby granted, free of charge, to any person obtaining a - * copy of this software and associated documentation files (the "Software"), - * to deal in the Software without restriction, including without limitation - * the rights to use, copy, modify, merge, publish, distribute, sublicense, - * and/or sell copies of the Software, and to permit persons to whom the - * Software is furnished to do so, subject to the following conditions: - * - * The above copyright notice including the dates of first publication and - * either this permission notice or a reference to - * http://oss.sgi.com/projects/FreeB/ - * shall be included in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS - * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL - * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, - * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF - * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - * - * Except as contained in this notice, the name of Silicon Graphics, Inc. - * shall not be used in advertising or otherwise to promote the sale, use or - * other dealings in this Software without prior written authorization from - * Silicon Graphics, Inc. - */ -/* -** Author: Eric Veach, July 1994. -** -*/ - -#include <stddef.h> -#include <assert.h> -#include "priorityq-heap.h" -#include "memalloc.h" - -#define INIT_SIZE 32 - -#ifndef TRUE -#define TRUE 1 -#endif -#ifndef FALSE -#define FALSE 0 -#endif - -#ifdef FOR_TRITE_TEST_PROGRAM -#define LEQ(x,y) (*pq->leq)(x,y) -#else -/* Violates modularity, but a little faster */ -#include "geom.h" -#define LEQ(x,y) VertLeq((GLUvertex *)x, (GLUvertex *)y) -#endif - -/* really __gl_pqHeapNewPriorityQ */ -PriorityQ *pqNewPriorityQ( int (*leq)(PQkey key1, PQkey key2) ) -{ - PriorityQ *pq = (PriorityQ *)memAlloc( sizeof( PriorityQ )); - if (pq == NULL) return NULL; - - pq->size = 0; - pq->max = INIT_SIZE; - pq->nodes = (PQnode *)memAlloc( (INIT_SIZE + 1) * sizeof(pq->nodes[0]) ); - if (pq->nodes == NULL) { - memFree(pq); - return NULL; - } - - pq->handles = (PQhandleElem *)memAlloc( (INIT_SIZE + 1) * sizeof(pq->handles[0]) ); - if (pq->handles == NULL) { - memFree(pq->nodes); - memFree(pq); - return NULL; - } - - pq->initialized = FALSE; - pq->freeList = 0; - pq->leq = leq; - - pq->nodes[1].handle = 1; /* so that Minimum() returns NULL */ - pq->handles[1].key = NULL; - return pq; -} - -/* really __gl_pqHeapDeletePriorityQ */ -void pqDeletePriorityQ( PriorityQ *pq ) -{ - memFree( pq->handles ); - memFree( pq->nodes ); - memFree( pq ); -} - - -static void FloatDown( PriorityQ *pq, long curr ) -{ - PQnode *n = pq->nodes; - PQhandleElem *h = pq->handles; - PQhandle hCurr, hChild; - long child; - - hCurr = n[curr].handle; - for( ;; ) { - child = curr << 1; - if( child < pq->size && LEQ( h[n[child+1].handle].key, - h[n[child].handle].key )) { - ++child; - } - - assert(child <= pq->max); - - hChild = n[child].handle; - if( child > pq->size || LEQ( h[hCurr].key, h[hChild].key )) { - n[curr].handle = hCurr; - h[hCurr].node = curr; - break; - } - n[curr].handle = hChild; - h[hChild].node = curr; - curr = child; - } -} - - -static void FloatUp( PriorityQ *pq, long curr ) -{ - PQnode *n = pq->nodes; - PQhandleElem *h = pq->handles; - PQhandle hCurr, hParent; - long parent; - - hCurr = n[curr].handle; - for( ;; ) { - parent = curr >> 1; - hParent = n[parent].handle; - if( parent == 0 || LEQ( h[hParent].key, h[hCurr].key )) { - n[curr].handle = hCurr; - h[hCurr].node = curr; - break; - } - n[curr].handle = hParent; - h[hParent].node = curr; - curr = parent; - } -} - -/* really __gl_pqHeapInit */ -void pqInit( PriorityQ *pq ) -{ - long i; - - /* This method of building a heap is O(n), rather than O(n lg n). */ - - for( i = pq->size; i >= 1; --i ) { - FloatDown( pq, i ); - } - pq->initialized = TRUE; -} - -/* really __gl_pqHeapInsert */ -/* returns LONG_MAX iff out of memory */ -PQhandle pqInsert( PriorityQ *pq, PQkey keyNew ) -{ - long curr; - PQhandle free_handle; - - curr = ++ pq->size; - if( (curr*2) > pq->max ) { - PQnode *saveNodes= pq->nodes; - PQhandleElem *saveHandles= pq->handles; - - /* If the heap overflows, double its size. */ - pq->max <<= 1; - pq->nodes = (PQnode *)memRealloc( pq->nodes, - (size_t) - ((pq->max + 1) * sizeof( pq->nodes[0] ))); - if (pq->nodes == NULL) { - pq->nodes = saveNodes; /* restore ptr to free upon return */ - return LONG_MAX; - } - pq->handles = (PQhandleElem *)memRealloc( pq->handles, - (size_t) - ((pq->max + 1) * - sizeof( pq->handles[0] ))); - if (pq->handles == NULL) { - pq->handles = saveHandles; /* restore ptr to free upon return */ - return LONG_MAX; - } - } - - if( pq->freeList == 0 ) { - free_handle = curr; - } else { - free_handle = pq->freeList; - pq->freeList = pq->handles[free_handle].node; - } - - pq->nodes[curr].handle = free_handle; - pq->handles[free_handle].node = curr; - pq->handles[free_handle].key = keyNew; - - if( pq->initialized ) { - FloatUp( pq, curr ); - } - assert(free_handle != LONG_MAX); - return free_handle; -} - -/* really __gl_pqHeapExtractMin */ -PQkey pqExtractMin( PriorityQ *pq ) -{ - PQnode *n = pq->nodes; - PQhandleElem *h = pq->handles; - PQhandle hMin = n[1].handle; - PQkey min = h[hMin].key; - - if( pq->size > 0 ) { - n[1].handle = n[pq->size].handle; - h[n[1].handle].node = 1; - - h[hMin].key = NULL; - h[hMin].node = pq->freeList; - pq->freeList = hMin; - - if( -- pq->size > 0 ) { - FloatDown( pq, 1 ); - } - } - return min; -} - -/* really __gl_pqHeapDelete */ -void pqDelete( PriorityQ *pq, PQhandle hCurr ) -{ - PQnode *n = pq->nodes; - PQhandleElem *h = pq->handles; - long curr; - - assert( hCurr >= 1 && hCurr <= pq->max && h[hCurr].key != NULL ); - - curr = h[hCurr].node; - n[curr].handle = n[pq->size].handle; - h[n[curr].handle].node = curr; - - if( curr <= -- pq->size ) { - if( curr <= 1 || LEQ( h[n[curr>>1].handle].key, h[n[curr].handle].key )) { - FloatDown( pq, curr ); - } else { - FloatUp( pq, curr ); - } - } - h[hCurr].key = NULL; - h[hCurr].node = pq->freeList; - pq->freeList = hCurr; -} diff --git a/src/glu/sgi/libtess/priorityq-heap.h b/src/glu/sgi/libtess/priorityq-heap.h deleted file mode 100644 index dc9aaef87f9..00000000000 --- a/src/glu/sgi/libtess/priorityq-heap.h +++ /dev/null @@ -1,107 +0,0 @@ -/* - * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008) - * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved. - * - * Permission is hereby granted, free of charge, to any person obtaining a - * copy of this software and associated documentation files (the "Software"), - * to deal in the Software without restriction, including without limitation - * the rights to use, copy, modify, merge, publish, distribute, sublicense, - * and/or sell copies of the Software, and to permit persons to whom the - * Software is furnished to do so, subject to the following conditions: - * - * The above copyright notice including the dates of first publication and - * either this permission notice or a reference to - * http://oss.sgi.com/projects/FreeB/ - * shall be included in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS - * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL - * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, - * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF - * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - * - * Except as contained in this notice, the name of Silicon Graphics, Inc. - * shall not be used in advertising or otherwise to promote the sale, use or - * other dealings in this Software without prior written authorization from - * Silicon Graphics, Inc. - */ -/* -** Author: Eric Veach, July 1994. -** -*/ - -#ifndef __priorityq_heap_h_ -#define __priorityq_heap_h_ - -/* Use #define's so that another heap implementation can use this one */ - -#define PQkey PQHeapKey -#define PQhandle PQHeapHandle -#define PriorityQ PriorityQHeap - -#define pqNewPriorityQ(leq) __gl_pqHeapNewPriorityQ(leq) -#define pqDeletePriorityQ(pq) __gl_pqHeapDeletePriorityQ(pq) - -/* The basic operations are insertion of a new key (pqInsert), - * and examination/extraction of a key whose value is minimum - * (pqMinimum/pqExtractMin). Deletion is also allowed (pqDelete); - * for this purpose pqInsert returns a "handle" which is supplied - * as the argument. - * - * An initial heap may be created efficiently by calling pqInsert - * repeatedly, then calling pqInit. In any case pqInit must be called - * before any operations other than pqInsert are used. - * - * If the heap is empty, pqMinimum/pqExtractMin will return a NULL key. - * This may also be tested with pqIsEmpty. - */ -#define pqInit(pq) __gl_pqHeapInit(pq) -#define pqInsert(pq,key) __gl_pqHeapInsert(pq,key) -#define pqMinimum(pq) __gl_pqHeapMinimum(pq) -#define pqExtractMin(pq) __gl_pqHeapExtractMin(pq) -#define pqDelete(pq,handle) __gl_pqHeapDelete(pq,handle) -#define pqIsEmpty(pq) __gl_pqHeapIsEmpty(pq) - - -/* Since we support deletion the data structure is a little more - * complicated than an ordinary heap. "nodes" is the heap itself; - * active nodes are stored in the range 1..pq->size. When the - * heap exceeds its allocated size (pq->max), its size doubles. - * The children of node i are nodes 2i and 2i+1. - * - * Each node stores an index into an array "handles". Each handle - * stores a key, plus a pointer back to the node which currently - * represents that key (ie. nodes[handles[i].node].handle == i). - */ - -typedef void *PQkey; -typedef long PQhandle; -typedef struct PriorityQ PriorityQ; - -typedef struct { PQhandle handle; } PQnode; -typedef struct { PQkey key; PQhandle node; } PQhandleElem; - -struct PriorityQ { - PQnode *nodes; - PQhandleElem *handles; - long size, max; - PQhandle freeList; - int initialized; - int (*leq)(PQkey key1, PQkey key2); -}; - -PriorityQ *pqNewPriorityQ( int (*leq)(PQkey key1, PQkey key2) ); -void pqDeletePriorityQ( PriorityQ *pq ); - -void pqInit( PriorityQ *pq ); -PQhandle pqInsert( PriorityQ *pq, PQkey key ); -PQkey pqExtractMin( PriorityQ *pq ); -void pqDelete( PriorityQ *pq, PQhandle handle ); - - -#define __gl_pqHeapMinimum(pq) ((pq)->handles[(pq)->nodes[1].handle].key) -#define __gl_pqHeapIsEmpty(pq) ((pq)->size == 0) - -#endif diff --git a/src/glu/sgi/libtess/priorityq-sort.h b/src/glu/sgi/libtess/priorityq-sort.h deleted file mode 100644 index 746cf5fa69a..00000000000 --- a/src/glu/sgi/libtess/priorityq-sort.h +++ /dev/null @@ -1,117 +0,0 @@ -/* - * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008) - * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved. - * - * Permission is hereby granted, free of charge, to any person obtaining a - * copy of this software and associated documentation files (the "Software"), - * to deal in the Software without restriction, including without limitation - * the rights to use, copy, modify, merge, publish, distribute, sublicense, - * and/or sell copies of the Software, and to permit persons to whom the - * Software is furnished to do so, subject to the following conditions: - * - * The above copyright notice including the dates of first publication and - * either this permission notice or a reference to - * http://oss.sgi.com/projects/FreeB/ - * shall be included in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS - * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL - * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, - * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF - * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - * - * Except as contained in this notice, the name of Silicon Graphics, Inc. - * shall not be used in advertising or otherwise to promote the sale, use or - * other dealings in this Software without prior written authorization from - * Silicon Graphics, Inc. - */ -/* -** Author: Eric Veach, July 1994. -** -*/ - -#ifndef __priorityq_sort_h_ -#define __priorityq_sort_h_ - -#include "priorityq-heap.h" - -#undef PQkey -#undef PQhandle -#undef PriorityQ -#undef pqNewPriorityQ -#undef pqDeletePriorityQ -#undef pqInit -#undef pqInsert -#undef pqMinimum -#undef pqExtractMin -#undef pqDelete -#undef pqIsEmpty - -/* Use #define's so that another heap implementation can use this one */ - -#define PQkey PQSortKey -#define PQhandle PQSortHandle -#define PriorityQ PriorityQSort - -#define pqNewPriorityQ(leq) __gl_pqSortNewPriorityQ(leq) -#define pqDeletePriorityQ(pq) __gl_pqSortDeletePriorityQ(pq) - -/* The basic operations are insertion of a new key (pqInsert), - * and examination/extraction of a key whose value is minimum - * (pqMinimum/pqExtractMin). Deletion is also allowed (pqDelete); - * for this purpose pqInsert returns a "handle" which is supplied - * as the argument. - * - * An initial heap may be created efficiently by calling pqInsert - * repeatedly, then calling pqInit. In any case pqInit must be called - * before any operations other than pqInsert are used. - * - * If the heap is empty, pqMinimum/pqExtractMin will return a NULL key. - * This may also be tested with pqIsEmpty. - */ -#define pqInit(pq) __gl_pqSortInit(pq) -#define pqInsert(pq,key) __gl_pqSortInsert(pq,key) -#define pqMinimum(pq) __gl_pqSortMinimum(pq) -#define pqExtractMin(pq) __gl_pqSortExtractMin(pq) -#define pqDelete(pq,handle) __gl_pqSortDelete(pq,handle) -#define pqIsEmpty(pq) __gl_pqSortIsEmpty(pq) - - -/* Since we support deletion the data structure is a little more - * complicated than an ordinary heap. "nodes" is the heap itself; - * active nodes are stored in the range 1..pq->size. When the - * heap exceeds its allocated size (pq->max), its size doubles. - * The children of node i are nodes 2i and 2i+1. - * - * Each node stores an index into an array "handles". Each handle - * stores a key, plus a pointer back to the node which currently - * represents that key (ie. nodes[handles[i].node].handle == i). - */ - -typedef PQHeapKey PQkey; -typedef PQHeapHandle PQhandle; -typedef struct PriorityQ PriorityQ; - -struct PriorityQ { - PriorityQHeap *heap; - PQkey *keys; - PQkey **order; - PQhandle size, max; - int initialized; - int (*leq)(PQkey key1, PQkey key2); -}; - -PriorityQ *pqNewPriorityQ( int (*leq)(PQkey key1, PQkey key2) ); -void pqDeletePriorityQ( PriorityQ *pq ); - -int pqInit( PriorityQ *pq ); -PQhandle pqInsert( PriorityQ *pq, PQkey key ); -PQkey pqExtractMin( PriorityQ *pq ); -void pqDelete( PriorityQ *pq, PQhandle handle ); - -PQkey pqMinimum( PriorityQ *pq ); -int pqIsEmpty( PriorityQ *pq ); - -#endif diff --git a/src/glu/sgi/libtess/priorityq.c b/src/glu/sgi/libtess/priorityq.c deleted file mode 100644 index c6b99cce552..00000000000 --- a/src/glu/sgi/libtess/priorityq.c +++ /dev/null @@ -1,260 +0,0 @@ -/* - * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008) - * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved. - * - * Permission is hereby granted, free of charge, to any person obtaining a - * copy of this software and associated documentation files (the "Software"), - * to deal in the Software without restriction, including without limitation - * the rights to use, copy, modify, merge, publish, distribute, sublicense, - * and/or sell copies of the Software, and to permit persons to whom the - * Software is furnished to do so, subject to the following conditions: - * - * The above copyright notice including the dates of first publication and - * either this permission notice or a reference to - * http://oss.sgi.com/projects/FreeB/ - * shall be included in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS - * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL - * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, - * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF - * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - * - * Except as contained in this notice, the name of Silicon Graphics, Inc. - * shall not be used in advertising or otherwise to promote the sale, use or - * other dealings in this Software without prior written authorization from - * Silicon Graphics, Inc. - */ -/* -** Author: Eric Veach, July 1994. -** -*/ - -#include "gluos.h" -#include <stddef.h> -#include <assert.h> -#include <limits.h> /* LONG_MAX */ -#include "memalloc.h" - -/* Include all the code for the regular heap-based queue here. */ - -#include "priorityq-heap.c" - -/* Now redefine all the function names to map to their "Sort" versions. */ - -#include "priorityq-sort.h" - -/* really __gl_pqSortNewPriorityQ */ -PriorityQ *pqNewPriorityQ( int (*leq)(PQkey key1, PQkey key2) ) -{ - PriorityQ *pq = (PriorityQ *)memAlloc( sizeof( PriorityQ )); - if (pq == NULL) return NULL; - - pq->heap = __gl_pqHeapNewPriorityQ( leq ); - if (pq->heap == NULL) { - memFree(pq); - return NULL; - } - - pq->keys = (PQHeapKey *)memAlloc( INIT_SIZE * sizeof(pq->keys[0]) ); - if (pq->keys == NULL) { - __gl_pqHeapDeletePriorityQ(pq->heap); - memFree(pq); - return NULL; - } - - pq->size = 0; - pq->max = INIT_SIZE; - pq->initialized = FALSE; - pq->leq = leq; - return pq; -} - -/* really __gl_pqSortDeletePriorityQ */ -void pqDeletePriorityQ( PriorityQ *pq ) -{ - assert(pq != NULL); - if (pq->heap != NULL) __gl_pqHeapDeletePriorityQ( pq->heap ); - if (pq->order != NULL) memFree( pq->order ); - if (pq->keys != NULL) memFree( pq->keys ); - memFree( pq ); -} - - -#define LT(x,y) (! LEQ(y,x)) -#define GT(x,y) (! LEQ(x,y)) -#define Swap(a,b) do{PQkey *tmp = *a; *a = *b; *b = tmp;}while(0) - -/* really __gl_pqSortInit */ -int pqInit( PriorityQ *pq ) -{ - PQkey **p, **r, **i, **j, *piv; - struct { PQkey **p, **r; } Stack[50], *top = Stack; - unsigned long seed = 2016473283; - - /* Create an array of indirect pointers to the keys, so that we - * the handles we have returned are still valid. - */ -/* - pq->order = (PQHeapKey **)memAlloc( (size_t) - (pq->size * sizeof(pq->order[0])) ); -*/ - pq->order = (PQHeapKey **)memAlloc( (size_t) - ((pq->size+1) * sizeof(pq->order[0])) ); -/* the previous line is a patch to compensate for the fact that IBM */ -/* machines return a null on a malloc of zero bytes (unlike SGI), */ -/* so we have to put in this defense to guard against a memory */ -/* fault four lines down. from [email protected]. */ - if (pq->order == NULL) return 0; - - p = pq->order; - r = p + pq->size - 1; - for( piv = pq->keys, i = p; i <= r; ++piv, ++i ) { - *i = piv; - } - - /* Sort the indirect pointers in descending order, - * using randomized Quicksort - */ - top->p = p; top->r = r; ++top; - while( --top >= Stack ) { - p = top->p; - r = top->r; - while( r > p + 10 ) { - seed = seed * 1539415821 + 1; - i = p + seed % (r - p + 1); - piv = *i; - *i = *p; - *p = piv; - i = p - 1; - j = r + 1; - do { - do { ++i; } while( GT( **i, *piv )); - do { --j; } while( LT( **j, *piv )); - Swap( i, j ); - } while( i < j ); - Swap( i, j ); /* Undo last swap */ - if( i - p < r - j ) { - top->p = j+1; top->r = r; ++top; - r = i-1; - } else { - top->p = p; top->r = i-1; ++top; - p = j+1; - } - } - /* Insertion sort small lists */ - for( i = p+1; i <= r; ++i ) { - piv = *i; - for( j = i; j > p && LT( **(j-1), *piv ); --j ) { - *j = *(j-1); - } - *j = piv; - } - } - pq->max = pq->size; - pq->initialized = TRUE; - __gl_pqHeapInit( pq->heap ); /* always succeeds */ - -#ifndef NDEBUG - p = pq->order; - r = p + pq->size - 1; - for( i = p; i < r; ++i ) { - assert( LEQ( **(i+1), **i )); - } -#endif - - return 1; -} - -/* really __gl_pqSortInsert */ -/* returns LONG_MAX iff out of memory */ -PQhandle pqInsert( PriorityQ *pq, PQkey keyNew ) -{ - long curr; - - if( pq->initialized ) { - return __gl_pqHeapInsert( pq->heap, keyNew ); - } - curr = pq->size; - if( ++ pq->size >= pq->max ) { - PQkey *saveKey= pq->keys; - - /* If the heap overflows, double its size. */ - pq->max <<= 1; - pq->keys = (PQHeapKey *)memRealloc( pq->keys, - (size_t) - (pq->max * sizeof( pq->keys[0] ))); - if (pq->keys == NULL) { - pq->keys = saveKey; /* restore ptr to free upon return */ - return LONG_MAX; - } - } - assert(curr != LONG_MAX); - pq->keys[curr] = keyNew; - - /* Negative handles index the sorted array. */ - return -(curr+1); -} - -/* really __gl_pqSortExtractMin */ -PQkey pqExtractMin( PriorityQ *pq ) -{ - PQkey sortMin, heapMin; - - if( pq->size == 0 ) { - return __gl_pqHeapExtractMin( pq->heap ); - } - sortMin = *(pq->order[pq->size-1]); - if( ! __gl_pqHeapIsEmpty( pq->heap )) { - heapMin = __gl_pqHeapMinimum( pq->heap ); - if( LEQ( heapMin, sortMin )) { - return __gl_pqHeapExtractMin( pq->heap ); - } - } - do { - -- pq->size; - } while( pq->size > 0 && *(pq->order[pq->size-1]) == NULL ); - return sortMin; -} - -/* really __gl_pqSortMinimum */ -PQkey pqMinimum( PriorityQ *pq ) -{ - PQkey sortMin, heapMin; - - if( pq->size == 0 ) { - return __gl_pqHeapMinimum( pq->heap ); - } - sortMin = *(pq->order[pq->size-1]); - if( ! __gl_pqHeapIsEmpty( pq->heap )) { - heapMin = __gl_pqHeapMinimum( pq->heap ); - if( LEQ( heapMin, sortMin )) { - return heapMin; - } - } - return sortMin; -} - -/* really __gl_pqSortIsEmpty */ -int pqIsEmpty( PriorityQ *pq ) -{ - return (pq->size == 0) && __gl_pqHeapIsEmpty( pq->heap ); -} - -/* really __gl_pqSortDelete */ -void pqDelete( PriorityQ *pq, PQhandle curr ) -{ - if( curr >= 0 ) { - __gl_pqHeapDelete( pq->heap, curr ); - return; - } - curr = -(curr+1); - assert( curr < pq->max && pq->keys[curr] != NULL ); - - pq->keys[curr] = NULL; - while( pq->size > 0 && *(pq->order[pq->size-1]) == NULL ) { - -- pq->size; - } -} diff --git a/src/glu/sgi/libtess/priorityq.h b/src/glu/sgi/libtess/priorityq.h deleted file mode 100644 index 746cf5fa69a..00000000000 --- a/src/glu/sgi/libtess/priorityq.h +++ /dev/null @@ -1,117 +0,0 @@ -/* - * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008) - * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved. - * - * Permission is hereby granted, free of charge, to any person obtaining a - * copy of this software and associated documentation files (the "Software"), - * to deal in the Software without restriction, including without limitation - * the rights to use, copy, modify, merge, publish, distribute, sublicense, - * and/or sell copies of the Software, and to permit persons to whom the - * Software is furnished to do so, subject to the following conditions: - * - * The above copyright notice including the dates of first publication and - * either this permission notice or a reference to - * http://oss.sgi.com/projects/FreeB/ - * shall be included in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS - * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL - * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, - * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF - * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - * - * Except as contained in this notice, the name of Silicon Graphics, Inc. - * shall not be used in advertising or otherwise to promote the sale, use or - * other dealings in this Software without prior written authorization from - * Silicon Graphics, Inc. - */ -/* -** Author: Eric Veach, July 1994. -** -*/ - -#ifndef __priorityq_sort_h_ -#define __priorityq_sort_h_ - -#include "priorityq-heap.h" - -#undef PQkey -#undef PQhandle -#undef PriorityQ -#undef pqNewPriorityQ -#undef pqDeletePriorityQ -#undef pqInit -#undef pqInsert -#undef pqMinimum -#undef pqExtractMin -#undef pqDelete -#undef pqIsEmpty - -/* Use #define's so that another heap implementation can use this one */ - -#define PQkey PQSortKey -#define PQhandle PQSortHandle -#define PriorityQ PriorityQSort - -#define pqNewPriorityQ(leq) __gl_pqSortNewPriorityQ(leq) -#define pqDeletePriorityQ(pq) __gl_pqSortDeletePriorityQ(pq) - -/* The basic operations are insertion of a new key (pqInsert), - * and examination/extraction of a key whose value is minimum - * (pqMinimum/pqExtractMin). Deletion is also allowed (pqDelete); - * for this purpose pqInsert returns a "handle" which is supplied - * as the argument. - * - * An initial heap may be created efficiently by calling pqInsert - * repeatedly, then calling pqInit. In any case pqInit must be called - * before any operations other than pqInsert are used. - * - * If the heap is empty, pqMinimum/pqExtractMin will return a NULL key. - * This may also be tested with pqIsEmpty. - */ -#define pqInit(pq) __gl_pqSortInit(pq) -#define pqInsert(pq,key) __gl_pqSortInsert(pq,key) -#define pqMinimum(pq) __gl_pqSortMinimum(pq) -#define pqExtractMin(pq) __gl_pqSortExtractMin(pq) -#define pqDelete(pq,handle) __gl_pqSortDelete(pq,handle) -#define pqIsEmpty(pq) __gl_pqSortIsEmpty(pq) - - -/* Since we support deletion the data structure is a little more - * complicated than an ordinary heap. "nodes" is the heap itself; - * active nodes are stored in the range 1..pq->size. When the - * heap exceeds its allocated size (pq->max), its size doubles. - * The children of node i are nodes 2i and 2i+1. - * - * Each node stores an index into an array "handles". Each handle - * stores a key, plus a pointer back to the node which currently - * represents that key (ie. nodes[handles[i].node].handle == i). - */ - -typedef PQHeapKey PQkey; -typedef PQHeapHandle PQhandle; -typedef struct PriorityQ PriorityQ; - -struct PriorityQ { - PriorityQHeap *heap; - PQkey *keys; - PQkey **order; - PQhandle size, max; - int initialized; - int (*leq)(PQkey key1, PQkey key2); -}; - -PriorityQ *pqNewPriorityQ( int (*leq)(PQkey key1, PQkey key2) ); -void pqDeletePriorityQ( PriorityQ *pq ); - -int pqInit( PriorityQ *pq ); -PQhandle pqInsert( PriorityQ *pq, PQkey key ); -PQkey pqExtractMin( PriorityQ *pq ); -void pqDelete( PriorityQ *pq, PQhandle handle ); - -PQkey pqMinimum( PriorityQ *pq ); -int pqIsEmpty( PriorityQ *pq ); - -#endif diff --git a/src/glu/sgi/libtess/render.c b/src/glu/sgi/libtess/render.c deleted file mode 100644 index bca836f0467..00000000000 --- a/src/glu/sgi/libtess/render.c +++ /dev/null @@ -1,502 +0,0 @@ -/* - * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008) - * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved. - * - * Permission is hereby granted, free of charge, to any person obtaining a - * copy of this software and associated documentation files (the "Software"), - * to deal in the Software without restriction, including without limitation - * the rights to use, copy, modify, merge, publish, distribute, sublicense, - * and/or sell copies of the Software, and to permit persons to whom the - * Software is furnished to do so, subject to the following conditions: - * - * The above copyright notice including the dates of first publication and - * either this permission notice or a reference to - * http://oss.sgi.com/projects/FreeB/ - * shall be included in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS - * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL - * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, - * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF - * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - * - * Except as contained in this notice, the name of Silicon Graphics, Inc. - * shall not be used in advertising or otherwise to promote the sale, use or - * other dealings in this Software without prior written authorization from - * Silicon Graphics, Inc. - */ -/* -** Author: Eric Veach, July 1994. -** -*/ - -#include "gluos.h" -#include <assert.h> -#include <stddef.h> -#include "mesh.h" -#include "tess.h" -#include "render.h" - -#ifndef TRUE -#define TRUE 1 -#endif -#ifndef FALSE -#define FALSE 0 -#endif - -/* This structure remembers the information we need about a primitive - * to be able to render it later, once we have determined which - * primitive is able to use the most triangles. - */ -struct FaceCount { - long size; /* number of triangles used */ - GLUhalfEdge *eStart; /* edge where this primitive starts */ - void (*render)(GLUtesselator *, GLUhalfEdge *, long); - /* routine to render this primitive */ -}; - -static struct FaceCount MaximumFan( GLUhalfEdge *eOrig ); -static struct FaceCount MaximumStrip( GLUhalfEdge *eOrig ); - -static void RenderFan( GLUtesselator *tess, GLUhalfEdge *eStart, long size ); -static void RenderStrip( GLUtesselator *tess, GLUhalfEdge *eStart, long size ); -static void RenderTriangle( GLUtesselator *tess, GLUhalfEdge *eStart, - long size ); - -static void RenderMaximumFaceGroup( GLUtesselator *tess, GLUface *fOrig ); -static void RenderLonelyTriangles( GLUtesselator *tess, GLUface *head ); - - - -/************************ Strips and Fans decomposition ******************/ - -/* __gl_renderMesh( tess, mesh ) takes a mesh and breaks it into triangle - * fans, strips, and separate triangles. A substantial effort is made - * to use as few rendering primitives as possible (ie. to make the fans - * and strips as large as possible). - * - * The rendering output is provided as callbacks (see the api). - */ -void __gl_renderMesh( GLUtesselator *tess, GLUmesh *mesh ) -{ - GLUface *f; - - /* Make a list of separate triangles so we can render them all at once */ - tess->lonelyTriList = NULL; - - for( f = mesh->fHead.next; f != &mesh->fHead; f = f->next ) { - f->marked = FALSE; - } - for( f = mesh->fHead.next; f != &mesh->fHead; f = f->next ) { - - /* We examine all faces in an arbitrary order. Whenever we find - * an unprocessed face F, we output a group of faces including F - * whose size is maximum. - */ - if( f->inside && ! f->marked ) { - RenderMaximumFaceGroup( tess, f ); - assert( f->marked ); - } - } - if( tess->lonelyTriList != NULL ) { - RenderLonelyTriangles( tess, tess->lonelyTriList ); - tess->lonelyTriList = NULL; - } -} - - -static void RenderMaximumFaceGroup( GLUtesselator *tess, GLUface *fOrig ) -{ - /* We want to find the largest triangle fan or strip of unmarked faces - * which includes the given face fOrig. There are 3 possible fans - * passing through fOrig (one centered at each vertex), and 3 possible - * strips (one for each CCW permutation of the vertices). Our strategy - * is to try all of these, and take the primitive which uses the most - * triangles (a greedy approach). - */ - GLUhalfEdge *e = fOrig->anEdge; - struct FaceCount max, newFace; - - max.size = 1; - max.eStart = e; - max.render = &RenderTriangle; - - if( ! tess->flagBoundary ) { - newFace = MaximumFan( e ); if( newFace.size > max.size ) { max = newFace; } - newFace = MaximumFan( e->Lnext ); if( newFace.size > max.size ) { max = newFace; } - newFace = MaximumFan( e->Lprev ); if( newFace.size > max.size ) { max = newFace; } - - newFace = MaximumStrip( e ); if( newFace.size > max.size ) { max = newFace; } - newFace = MaximumStrip( e->Lnext ); if( newFace.size > max.size ) { max = newFace; } - newFace = MaximumStrip( e->Lprev ); if( newFace.size > max.size ) { max = newFace; } - } - (*(max.render))( tess, max.eStart, max.size ); -} - - -/* Macros which keep track of faces we have marked temporarily, and allow - * us to backtrack when necessary. With triangle fans, this is not - * really necessary, since the only awkward case is a loop of triangles - * around a single origin vertex. However with strips the situation is - * more complicated, and we need a general tracking method like the - * one here. - */ -#define Marked(f) (! (f)->inside || (f)->marked) - -#define AddToTrail(f,t) ((f)->trail = (t), (t) = (f), (f)->marked = TRUE) - -#define FreeTrail(t) do { \ - while( (t) != NULL ) { \ - (t)->marked = FALSE; t = (t)->trail; \ - } \ - } while(0) /* absorb trailing semicolon */ - - - -static struct FaceCount MaximumFan( GLUhalfEdge *eOrig ) -{ - /* eOrig->Lface is the face we want to render. We want to find the size - * of a maximal fan around eOrig->Org. To do this we just walk around - * the origin vertex as far as possible in both directions. - */ - struct FaceCount newFace = { 0, NULL, &RenderFan }; - GLUface *trail = NULL; - GLUhalfEdge *e; - - for( e = eOrig; ! Marked( e->Lface ); e = e->Onext ) { - AddToTrail( e->Lface, trail ); - ++newFace.size; - } - for( e = eOrig; ! Marked( e->Rface ); e = e->Oprev ) { - AddToTrail( e->Rface, trail ); - ++newFace.size; - } - newFace.eStart = e; - /*LINTED*/ - FreeTrail( trail ); - return newFace; -} - - -#define IsEven(n) (((n) & 1) == 0) - -static struct FaceCount MaximumStrip( GLUhalfEdge *eOrig ) -{ - /* Here we are looking for a maximal strip that contains the vertices - * eOrig->Org, eOrig->Dst, eOrig->Lnext->Dst (in that order or the - * reverse, such that all triangles are oriented CCW). - * - * Again we walk forward and backward as far as possible. However for - * strips there is a twist: to get CCW orientations, there must be - * an *even* number of triangles in the strip on one side of eOrig. - * We walk the strip starting on a side with an even number of triangles; - * if both side have an odd number, we are forced to shorten one side. - */ - struct FaceCount newFace = { 0, NULL, &RenderStrip }; - long headSize = 0, tailSize = 0; - GLUface *trail = NULL; - GLUhalfEdge *e, *eTail, *eHead; - - for( e = eOrig; ! Marked( e->Lface ); ++tailSize, e = e->Onext ) { - AddToTrail( e->Lface, trail ); - ++tailSize; - e = e->Dprev; - if( Marked( e->Lface )) break; - AddToTrail( e->Lface, trail ); - } - eTail = e; - - for( e = eOrig; ! Marked( e->Rface ); ++headSize, e = e->Dnext ) { - AddToTrail( e->Rface, trail ); - ++headSize; - e = e->Oprev; - if( Marked( e->Rface )) break; - AddToTrail( e->Rface, trail ); - } - eHead = e; - - newFace.size = tailSize + headSize; - if( IsEven( tailSize )) { - newFace.eStart = eTail->Sym; - } else if( IsEven( headSize )) { - newFace.eStart = eHead; - } else { - /* Both sides have odd length, we must shorten one of them. In fact, - * we must start from eHead to guarantee inclusion of eOrig->Lface. - */ - --newFace.size; - newFace.eStart = eHead->Onext; - } - /*LINTED*/ - FreeTrail( trail ); - return newFace; -} - - -static void RenderTriangle( GLUtesselator *tess, GLUhalfEdge *e, long size ) -{ - /* Just add the triangle to a triangle list, so we can render all - * the separate triangles at once. - */ - assert( size == 1 ); - AddToTrail( e->Lface, tess->lonelyTriList ); -} - - -static void RenderLonelyTriangles( GLUtesselator *tess, GLUface *f ) -{ - /* Now we render all the separate triangles which could not be - * grouped into a triangle fan or strip. - */ - GLUhalfEdge *e; - int newState; - int edgeState = -1; /* force edge state output for first vertex */ - - CALL_BEGIN_OR_BEGIN_DATA( GL_TRIANGLES ); - - for( ; f != NULL; f = f->trail ) { - /* Loop once for each edge (there will always be 3 edges) */ - - e = f->anEdge; - do { - if( tess->flagBoundary ) { - /* Set the "edge state" to TRUE just before we output the - * first vertex of each edge on the polygon boundary. - */ - newState = ! e->Rface->inside; - if( edgeState != newState ) { - edgeState = newState; - CALL_EDGE_FLAG_OR_EDGE_FLAG_DATA( edgeState ); - } - } - CALL_VERTEX_OR_VERTEX_DATA( e->Org->data ); - - e = e->Lnext; - } while( e != f->anEdge ); - } - CALL_END_OR_END_DATA(); -} - - -static void RenderFan( GLUtesselator *tess, GLUhalfEdge *e, long size ) -{ - /* Render as many CCW triangles as possible in a fan starting from - * edge "e". The fan *should* contain exactly "size" triangles - * (otherwise we've goofed up somewhere). - */ - CALL_BEGIN_OR_BEGIN_DATA( GL_TRIANGLE_FAN ); - CALL_VERTEX_OR_VERTEX_DATA( e->Org->data ); - CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data ); - - while( ! Marked( e->Lface )) { - e->Lface->marked = TRUE; - --size; - e = e->Onext; - CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data ); - } - - assert( size == 0 ); - CALL_END_OR_END_DATA(); -} - - -static void RenderStrip( GLUtesselator *tess, GLUhalfEdge *e, long size ) -{ - /* Render as many CCW triangles as possible in a strip starting from - * edge "e". The strip *should* contain exactly "size" triangles - * (otherwise we've goofed up somewhere). - */ - CALL_BEGIN_OR_BEGIN_DATA( GL_TRIANGLE_STRIP ); - CALL_VERTEX_OR_VERTEX_DATA( e->Org->data ); - CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data ); - - while( ! Marked( e->Lface )) { - e->Lface->marked = TRUE; - --size; - e = e->Dprev; - CALL_VERTEX_OR_VERTEX_DATA( e->Org->data ); - if( Marked( e->Lface )) break; - - e->Lface->marked = TRUE; - --size; - e = e->Onext; - CALL_VERTEX_OR_VERTEX_DATA( e->Dst->data ); - } - - assert( size == 0 ); - CALL_END_OR_END_DATA(); -} - - -/************************ Boundary contour decomposition ******************/ - -/* __gl_renderBoundary( tess, mesh ) takes a mesh, and outputs one - * contour for each face marked "inside". The rendering output is - * provided as callbacks (see the api). - */ -void __gl_renderBoundary( GLUtesselator *tess, GLUmesh *mesh ) -{ - GLUface *f; - GLUhalfEdge *e; - - for( f = mesh->fHead.next; f != &mesh->fHead; f = f->next ) { - if( f->inside ) { - CALL_BEGIN_OR_BEGIN_DATA( GL_LINE_LOOP ); - e = f->anEdge; - do { - CALL_VERTEX_OR_VERTEX_DATA( e->Org->data ); - e = e->Lnext; - } while( e != f->anEdge ); - CALL_END_OR_END_DATA(); - } - } -} - - -/************************ Quick-and-dirty decomposition ******************/ - -#define SIGN_INCONSISTENT 2 - -static int ComputeNormal( GLUtesselator *tess, GLdouble norm[3], int check ) -/* - * If check==FALSE, we compute the polygon normal and place it in norm[]. - * If check==TRUE, we check that each triangle in the fan from v0 has a - * consistent orientation with respect to norm[]. If triangles are - * consistently oriented CCW, return 1; if CW, return -1; if all triangles - * are degenerate return 0; otherwise (no consistent orientation) return - * SIGN_INCONSISTENT. - */ -{ - CachedVertex *v0 = tess->cache; - CachedVertex *vn = v0 + tess->cacheCount; - CachedVertex *vc; - GLdouble dot, xc, yc, zc, xp, yp, zp, n[3]; - int sign = 0; - - /* Find the polygon normal. It is important to get a reasonable - * normal even when the polygon is self-intersecting (eg. a bowtie). - * Otherwise, the computed normal could be very tiny, but perpendicular - * to the true plane of the polygon due to numerical noise. Then all - * the triangles would appear to be degenerate and we would incorrectly - * decompose the polygon as a fan (or simply not render it at all). - * - * We use a sum-of-triangles normal algorithm rather than the more - * efficient sum-of-trapezoids method (used in CheckOrientation() - * in normal.c). This lets us explicitly reverse the signed area - * of some triangles to get a reasonable normal in the self-intersecting - * case. - */ - if( ! check ) { - norm[0] = norm[1] = norm[2] = 0.0; - } - - vc = v0 + 1; - xc = vc->coords[0] - v0->coords[0]; - yc = vc->coords[1] - v0->coords[1]; - zc = vc->coords[2] - v0->coords[2]; - while( ++vc < vn ) { - xp = xc; yp = yc; zp = zc; - xc = vc->coords[0] - v0->coords[0]; - yc = vc->coords[1] - v0->coords[1]; - zc = vc->coords[2] - v0->coords[2]; - - /* Compute (vp - v0) cross (vc - v0) */ - n[0] = yp*zc - zp*yc; - n[1] = zp*xc - xp*zc; - n[2] = xp*yc - yp*xc; - - dot = n[0]*norm[0] + n[1]*norm[1] + n[2]*norm[2]; - if( ! check ) { - /* Reverse the contribution of back-facing triangles to get - * a reasonable normal for self-intersecting polygons (see above) - */ - if( dot >= 0 ) { - norm[0] += n[0]; norm[1] += n[1]; norm[2] += n[2]; - } else { - norm[0] -= n[0]; norm[1] -= n[1]; norm[2] -= n[2]; - } - } else if( dot != 0 ) { - /* Check the new orientation for consistency with previous triangles */ - if( dot > 0 ) { - if( sign < 0 ) return SIGN_INCONSISTENT; - sign = 1; - } else { - if( sign > 0 ) return SIGN_INCONSISTENT; - sign = -1; - } - } - } - return sign; -} - -/* __gl_renderCache( tess ) takes a single contour and tries to render it - * as a triangle fan. This handles convex polygons, as well as some - * non-convex polygons if we get lucky. - * - * Returns TRUE if the polygon was successfully rendered. The rendering - * output is provided as callbacks (see the api). - */ -GLboolean __gl_renderCache( GLUtesselator *tess ) -{ - CachedVertex *v0 = tess->cache; - CachedVertex *vn = v0 + tess->cacheCount; - CachedVertex *vc; - GLdouble norm[3]; - int sign; - - if( tess->cacheCount < 3 ) { - /* Degenerate contour -- no output */ - return TRUE; - } - - norm[0] = tess->normal[0]; - norm[1] = tess->normal[1]; - norm[2] = tess->normal[2]; - if( norm[0] == 0 && norm[1] == 0 && norm[2] == 0 ) { - ComputeNormal( tess, norm, FALSE ); - } - - sign = ComputeNormal( tess, norm, TRUE ); - if( sign == SIGN_INCONSISTENT ) { - /* Fan triangles did not have a consistent orientation */ - return FALSE; - } - if( sign == 0 ) { - /* All triangles were degenerate */ - return TRUE; - } - - /* Make sure we do the right thing for each winding rule */ - switch( tess->windingRule ) { - case GLU_TESS_WINDING_ODD: - case GLU_TESS_WINDING_NONZERO: - break; - case GLU_TESS_WINDING_POSITIVE: - if( sign < 0 ) return TRUE; - break; - case GLU_TESS_WINDING_NEGATIVE: - if( sign > 0 ) return TRUE; - break; - case GLU_TESS_WINDING_ABS_GEQ_TWO: - return TRUE; - } - - CALL_BEGIN_OR_BEGIN_DATA( tess->boundaryOnly ? GL_LINE_LOOP - : (tess->cacheCount > 3) ? GL_TRIANGLE_FAN - : GL_TRIANGLES ); - - CALL_VERTEX_OR_VERTEX_DATA( v0->data ); - if( sign > 0 ) { - for( vc = v0+1; vc < vn; ++vc ) { - CALL_VERTEX_OR_VERTEX_DATA( vc->data ); - } - } else { - for( vc = vn-1; vc > v0; --vc ) { - CALL_VERTEX_OR_VERTEX_DATA( vc->data ); - } - } - CALL_END_OR_END_DATA(); - return TRUE; -} diff --git a/src/glu/sgi/libtess/render.h b/src/glu/sgi/libtess/render.h deleted file mode 100644 index a298c9a9482..00000000000 --- a/src/glu/sgi/libtess/render.h +++ /dev/null @@ -1,52 +0,0 @@ -/* - * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008) - * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved. - * - * Permission is hereby granted, free of charge, to any person obtaining a - * copy of this software and associated documentation files (the "Software"), - * to deal in the Software without restriction, including without limitation - * the rights to use, copy, modify, merge, publish, distribute, sublicense, - * and/or sell copies of the Software, and to permit persons to whom the - * Software is furnished to do so, subject to the following conditions: - * - * The above copyright notice including the dates of first publication and - * either this permission notice or a reference to - * http://oss.sgi.com/projects/FreeB/ - * shall be included in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS - * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL - * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, - * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF - * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - * - * Except as contained in this notice, the name of Silicon Graphics, Inc. - * shall not be used in advertising or otherwise to promote the sale, use or - * other dealings in this Software without prior written authorization from - * Silicon Graphics, Inc. - */ -/* -** Author: Eric Veach, July 1994. -** -*/ - -#ifndef __render_h_ -#define __render_h_ - -#include "mesh.h" - -/* __gl_renderMesh( tess, mesh ) takes a mesh and breaks it into triangle - * fans, strips, and separate triangles. A substantial effort is made - * to use as few rendering primitives as possible (ie. to make the fans - * and strips as large as possible). - * - * The rendering output is provided as callbacks (see the api). - */ -void __gl_renderMesh( GLUtesselator *tess, GLUmesh *mesh ); -void __gl_renderBoundary( GLUtesselator *tess, GLUmesh *mesh ); - -GLboolean __gl_renderCache( GLUtesselator *tess ); - -#endif diff --git a/src/glu/sgi/libtess/sweep.c b/src/glu/sgi/libtess/sweep.c deleted file mode 100644 index eca828ff67f..00000000000 --- a/src/glu/sgi/libtess/sweep.c +++ /dev/null @@ -1,1361 +0,0 @@ -/* - * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008) - * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved. - * - * Permission is hereby granted, free of charge, to any person obtaining a - * copy of this software and associated documentation files (the "Software"), - * to deal in the Software without restriction, including without limitation - * the rights to use, copy, modify, merge, publish, distribute, sublicense, - * and/or sell copies of the Software, and to permit persons to whom the - * Software is furnished to do so, subject to the following conditions: - * - * The above copyright notice including the dates of first publication and - * either this permission notice or a reference to - * http://oss.sgi.com/projects/FreeB/ - * shall be included in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS - * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL - * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, - * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF - * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - * - * Except as contained in this notice, the name of Silicon Graphics, Inc. - * shall not be used in advertising or otherwise to promote the sale, use or - * other dealings in this Software without prior written authorization from - * Silicon Graphics, Inc. - */ -/* -** Author: Eric Veach, July 1994. -** -*/ - -#include "gluos.h" -#include <assert.h> -#include <stddef.h> -#include <setjmp.h> /* longjmp */ -#include <limits.h> /* LONG_MAX */ - -#include "mesh.h" -#include "geom.h" -#include "tess.h" -#include "dict.h" -#include "priorityq.h" -#include "memalloc.h" -#include "sweep.h" - -#ifndef TRUE -#define TRUE 1 -#endif -#ifndef FALSE -#define FALSE 0 -#endif - -#ifdef FOR_TRITE_TEST_PROGRAM -extern void DebugEvent( GLUtesselator *tess ); -#else -#define DebugEvent( tess ) -#endif - -/* - * Invariants for the Edge Dictionary. - * - each pair of adjacent edges e2=Succ(e1) satisfies EdgeLeq(e1,e2) - * at any valid location of the sweep event - * - if EdgeLeq(e2,e1) as well (at any valid sweep event), then e1 and e2 - * share a common endpoint - * - for each e, e->Dst has been processed, but not e->Org - * - each edge e satisfies VertLeq(e->Dst,event) && VertLeq(event,e->Org) - * where "event" is the current sweep line event. - * - no edge e has zero length - * - * Invariants for the Mesh (the processed portion). - * - the portion of the mesh left of the sweep line is a planar graph, - * ie. there is *some* way to embed it in the plane - * - no processed edge has zero length - * - no two processed vertices have identical coordinates - * - each "inside" region is monotone, ie. can be broken into two chains - * of monotonically increasing vertices according to VertLeq(v1,v2) - * - a non-invariant: these chains may intersect (very slightly) - * - * Invariants for the Sweep. - * - if none of the edges incident to the event vertex have an activeRegion - * (ie. none of these edges are in the edge dictionary), then the vertex - * has only right-going edges. - * - if an edge is marked "fixUpperEdge" (it is a temporary edge introduced - * by ConnectRightVertex), then it is the only right-going edge from - * its associated vertex. (This says that these edges exist only - * when it is necessary.) - */ - -#undef MAX -#undef MIN -#define MAX(x,y) ((x) >= (y) ? (x) : (y)) -#define MIN(x,y) ((x) <= (y) ? (x) : (y)) - -/* When we merge two edges into one, we need to compute the combined - * winding of the new edge. - */ -#define AddWinding(eDst,eSrc) (eDst->winding += eSrc->winding, \ - eDst->Sym->winding += eSrc->Sym->winding) - -static void SweepEvent( GLUtesselator *tess, GLUvertex *vEvent ); -static void WalkDirtyRegions( GLUtesselator *tess, ActiveRegion *regUp ); -static int CheckForRightSplice( GLUtesselator *tess, ActiveRegion *regUp ); - -static int EdgeLeq( GLUtesselator *tess, ActiveRegion *reg1, - ActiveRegion *reg2 ) -/* - * Both edges must be directed from right to left (this is the canonical - * direction for the upper edge of each region). - * - * The strategy is to evaluate a "t" value for each edge at the - * current sweep line position, given by tess->event. The calculations - * are designed to be very stable, but of course they are not perfect. - * - * Special case: if both edge destinations are at the sweep event, - * we sort the edges by slope (they would otherwise compare equally). - */ -{ - GLUvertex *event = tess->event; - GLUhalfEdge *e1, *e2; - GLdouble t1, t2; - - e1 = reg1->eUp; - e2 = reg2->eUp; - - if( e1->Dst == event ) { - if( e2->Dst == event ) { - /* Two edges right of the sweep line which meet at the sweep event. - * Sort them by slope. - */ - if( VertLeq( e1->Org, e2->Org )) { - return EdgeSign( e2->Dst, e1->Org, e2->Org ) <= 0; - } - return EdgeSign( e1->Dst, e2->Org, e1->Org ) >= 0; - } - return EdgeSign( e2->Dst, event, e2->Org ) <= 0; - } - if( e2->Dst == event ) { - return EdgeSign( e1->Dst, event, e1->Org ) >= 0; - } - - /* General case - compute signed distance *from* e1, e2 to event */ - t1 = EdgeEval( e1->Dst, event, e1->Org ); - t2 = EdgeEval( e2->Dst, event, e2->Org ); - return (t1 >= t2); -} - - -static void DeleteRegion( GLUtesselator *tess, ActiveRegion *reg ) -{ - if( reg->fixUpperEdge ) { - /* It was created with zero winding number, so it better be - * deleted with zero winding number (ie. it better not get merged - * with a real edge). - */ - assert( reg->eUp->winding == 0 ); - } - reg->eUp->activeRegion = NULL; - dictDelete( tess->dict, reg->nodeUp ); /* __gl_dictListDelete */ - memFree( reg ); -} - - -static int FixUpperEdge( ActiveRegion *reg, GLUhalfEdge *newEdge ) -/* - * Replace an upper edge which needs fixing (see ConnectRightVertex). - */ -{ - assert( reg->fixUpperEdge ); - if ( !__gl_meshDelete( reg->eUp ) ) return 0; - reg->fixUpperEdge = FALSE; - reg->eUp = newEdge; - newEdge->activeRegion = reg; - - return 1; -} - -static ActiveRegion *TopLeftRegion( ActiveRegion *reg ) -{ - GLUvertex *org = reg->eUp->Org; - GLUhalfEdge *e; - - /* Find the region above the uppermost edge with the same origin */ - do { - reg = RegionAbove( reg ); - } while( reg->eUp->Org == org ); - - /* If the edge above was a temporary edge introduced by ConnectRightVertex, - * now is the time to fix it. - */ - if( reg->fixUpperEdge ) { - e = __gl_meshConnect( RegionBelow(reg)->eUp->Sym, reg->eUp->Lnext ); - if (e == NULL) return NULL; - if ( !FixUpperEdge( reg, e ) ) return NULL; - reg = RegionAbove( reg ); - } - return reg; -} - -static ActiveRegion *TopRightRegion( ActiveRegion *reg ) -{ - GLUvertex *dst = reg->eUp->Dst; - - /* Find the region above the uppermost edge with the same destination */ - do { - reg = RegionAbove( reg ); - } while( reg->eUp->Dst == dst ); - return reg; -} - -static ActiveRegion *AddRegionBelow( GLUtesselator *tess, - ActiveRegion *regAbove, - GLUhalfEdge *eNewUp ) -/* - * Add a new active region to the sweep line, *somewhere* below "regAbove" - * (according to where the new edge belongs in the sweep-line dictionary). - * The upper edge of the new region will be "eNewUp". - * Winding number and "inside" flag are not updated. - */ -{ - ActiveRegion *regNew = (ActiveRegion *)memAlloc( sizeof( ActiveRegion )); - if (regNew == NULL) longjmp(tess->env,1); - - regNew->eUp = eNewUp; - /* __gl_dictListInsertBefore */ - regNew->nodeUp = dictInsertBefore( tess->dict, regAbove->nodeUp, regNew ); - if (regNew->nodeUp == NULL) longjmp(tess->env,1); - regNew->fixUpperEdge = FALSE; - regNew->sentinel = FALSE; - regNew->dirty = FALSE; - - eNewUp->activeRegion = regNew; - return regNew; -} - -static GLboolean IsWindingInside( GLUtesselator *tess, int n ) -{ - switch( tess->windingRule ) { - case GLU_TESS_WINDING_ODD: - return (n & 1); - case GLU_TESS_WINDING_NONZERO: - return (n != 0); - case GLU_TESS_WINDING_POSITIVE: - return (n > 0); - case GLU_TESS_WINDING_NEGATIVE: - return (n < 0); - case GLU_TESS_WINDING_ABS_GEQ_TWO: - return (n >= 2) || (n <= -2); - } - /*LINTED*/ - assert( FALSE ); - /*NOTREACHED*/ - return GL_FALSE; /* avoid compiler complaints */ -} - - -static void ComputeWinding( GLUtesselator *tess, ActiveRegion *reg ) -{ - reg->windingNumber = RegionAbove(reg)->windingNumber + reg->eUp->winding; - reg->inside = IsWindingInside( tess, reg->windingNumber ); -} - - -static void FinishRegion( GLUtesselator *tess, ActiveRegion *reg ) -/* - * Delete a region from the sweep line. This happens when the upper - * and lower chains of a region meet (at a vertex on the sweep line). - * The "inside" flag is copied to the appropriate mesh face (we could - * not do this before -- since the structure of the mesh is always - * changing, this face may not have even existed until now). - */ -{ - GLUhalfEdge *e = reg->eUp; - GLUface *f = e->Lface; - - f->inside = reg->inside; - f->anEdge = e; /* optimization for __gl_meshTessellateMonoRegion() */ - DeleteRegion( tess, reg ); -} - - -static GLUhalfEdge *FinishLeftRegions( GLUtesselator *tess, - ActiveRegion *regFirst, ActiveRegion *regLast ) -/* - * We are given a vertex with one or more left-going edges. All affected - * edges should be in the edge dictionary. Starting at regFirst->eUp, - * we walk down deleting all regions where both edges have the same - * origin vOrg. At the same time we copy the "inside" flag from the - * active region to the face, since at this point each face will belong - * to at most one region (this was not necessarily true until this point - * in the sweep). The walk stops at the region above regLast; if regLast - * is NULL we walk as far as possible. At the same time we relink the - * mesh if necessary, so that the ordering of edges around vOrg is the - * same as in the dictionary. - */ -{ - ActiveRegion *reg, *regPrev; - GLUhalfEdge *e, *ePrev; - - regPrev = regFirst; - ePrev = regFirst->eUp; - while( regPrev != regLast ) { - regPrev->fixUpperEdge = FALSE; /* placement was OK */ - reg = RegionBelow( regPrev ); - e = reg->eUp; - if( e->Org != ePrev->Org ) { - if( ! reg->fixUpperEdge ) { - /* Remove the last left-going edge. Even though there are no further - * edges in the dictionary with this origin, there may be further - * such edges in the mesh (if we are adding left edges to a vertex - * that has already been processed). Thus it is important to call - * FinishRegion rather than just DeleteRegion. - */ - FinishRegion( tess, regPrev ); - break; - } - /* If the edge below was a temporary edge introduced by - * ConnectRightVertex, now is the time to fix it. - */ - e = __gl_meshConnect( ePrev->Lprev, e->Sym ); - if (e == NULL) longjmp(tess->env,1); - if ( !FixUpperEdge( reg, e ) ) longjmp(tess->env,1); - } - - /* Relink edges so that ePrev->Onext == e */ - if( ePrev->Onext != e ) { - if ( !__gl_meshSplice( e->Oprev, e ) ) longjmp(tess->env,1); - if ( !__gl_meshSplice( ePrev, e ) ) longjmp(tess->env,1); - } - FinishRegion( tess, regPrev ); /* may change reg->eUp */ - ePrev = reg->eUp; - regPrev = reg; - } - return ePrev; -} - - -static void AddRightEdges( GLUtesselator *tess, ActiveRegion *regUp, - GLUhalfEdge *eFirst, GLUhalfEdge *eLast, GLUhalfEdge *eTopLeft, - GLboolean cleanUp ) -/* - * Purpose: insert right-going edges into the edge dictionary, and update - * winding numbers and mesh connectivity appropriately. All right-going - * edges share a common origin vOrg. Edges are inserted CCW starting at - * eFirst; the last edge inserted is eLast->Oprev. If vOrg has any - * left-going edges already processed, then eTopLeft must be the edge - * such that an imaginary upward vertical segment from vOrg would be - * contained between eTopLeft->Oprev and eTopLeft; otherwise eTopLeft - * should be NULL. - */ -{ - ActiveRegion *reg, *regPrev; - GLUhalfEdge *e, *ePrev; - int firstTime = TRUE; - - /* Insert the new right-going edges in the dictionary */ - e = eFirst; - do { - assert( VertLeq( e->Org, e->Dst )); - AddRegionBelow( tess, regUp, e->Sym ); - e = e->Onext; - } while ( e != eLast ); - - /* Walk *all* right-going edges from e->Org, in the dictionary order, - * updating the winding numbers of each region, and re-linking the mesh - * edges to match the dictionary ordering (if necessary). - */ - if( eTopLeft == NULL ) { - eTopLeft = RegionBelow( regUp )->eUp->Rprev; - } - regPrev = regUp; - ePrev = eTopLeft; - for( ;; ) { - reg = RegionBelow( regPrev ); - e = reg->eUp->Sym; - if( e->Org != ePrev->Org ) break; - - if( e->Onext != ePrev ) { - /* Unlink e from its current position, and relink below ePrev */ - if ( !__gl_meshSplice( e->Oprev, e ) ) longjmp(tess->env,1); - if ( !__gl_meshSplice( ePrev->Oprev, e ) ) longjmp(tess->env,1); - } - /* Compute the winding number and "inside" flag for the new regions */ - reg->windingNumber = regPrev->windingNumber - e->winding; - reg->inside = IsWindingInside( tess, reg->windingNumber ); - - /* Check for two outgoing edges with same slope -- process these - * before any intersection tests (see example in __gl_computeInterior). - */ - regPrev->dirty = TRUE; - if( ! firstTime && CheckForRightSplice( tess, regPrev )) { - AddWinding( e, ePrev ); - DeleteRegion( tess, regPrev ); - if ( !__gl_meshDelete( ePrev ) ) longjmp(tess->env,1); - } - firstTime = FALSE; - regPrev = reg; - ePrev = e; - } - regPrev->dirty = TRUE; - assert( regPrev->windingNumber - e->winding == reg->windingNumber ); - - if( cleanUp ) { - /* Check for intersections between newly adjacent edges. */ - WalkDirtyRegions( tess, regPrev ); - } -} - - -static void CallCombine( GLUtesselator *tess, GLUvertex *isect, - void *data[4], GLfloat weights[4], int needed ) -{ - GLdouble coords[3]; - - /* Copy coord data in case the callback changes it. */ - coords[0] = isect->coords[0]; - coords[1] = isect->coords[1]; - coords[2] = isect->coords[2]; - - isect->data = NULL; - CALL_COMBINE_OR_COMBINE_DATA( coords, data, weights, &isect->data ); - if( isect->data == NULL ) { - if( ! needed ) { - isect->data = data[0]; - } else if( ! tess->fatalError ) { - /* The only way fatal error is when two edges are found to intersect, - * but the user has not provided the callback necessary to handle - * generated intersection points. - */ - CALL_ERROR_OR_ERROR_DATA( GLU_TESS_NEED_COMBINE_CALLBACK ); - tess->fatalError = TRUE; - } - } -} - -static void SpliceMergeVertices( GLUtesselator *tess, GLUhalfEdge *e1, - GLUhalfEdge *e2 ) -/* - * Two vertices with idential coordinates are combined into one. - * e1->Org is kept, while e2->Org is discarded. - */ -{ - void *data[4] = { NULL, NULL, NULL, NULL }; - GLfloat weights[4] = { 0.5, 0.5, 0.0, 0.0 }; - - data[0] = e1->Org->data; - data[1] = e2->Org->data; - CallCombine( tess, e1->Org, data, weights, FALSE ); - if ( !__gl_meshSplice( e1, e2 ) ) longjmp(tess->env,1); -} - -static void VertexWeights( GLUvertex *isect, GLUvertex *org, GLUvertex *dst, - GLfloat *weights ) -/* - * Find some weights which describe how the intersection vertex is - * a linear combination of "org" and "dest". Each of the two edges - * which generated "isect" is allocated 50% of the weight; each edge - * splits the weight between its org and dst according to the - * relative distance to "isect". - */ -{ - GLdouble t1 = VertL1dist( org, isect ); - GLdouble t2 = VertL1dist( dst, isect ); - - weights[0] = 0.5 * t2 / (t1 + t2); - weights[1] = 0.5 * t1 / (t1 + t2); - isect->coords[0] += weights[0]*org->coords[0] + weights[1]*dst->coords[0]; - isect->coords[1] += weights[0]*org->coords[1] + weights[1]*dst->coords[1]; - isect->coords[2] += weights[0]*org->coords[2] + weights[1]*dst->coords[2]; -} - - -static void GetIntersectData( GLUtesselator *tess, GLUvertex *isect, - GLUvertex *orgUp, GLUvertex *dstUp, - GLUvertex *orgLo, GLUvertex *dstLo ) -/* - * We've computed a new intersection point, now we need a "data" pointer - * from the user so that we can refer to this new vertex in the - * rendering callbacks. - */ -{ - void *data[4]; - GLfloat weights[4]; - - data[0] = orgUp->data; - data[1] = dstUp->data; - data[2] = orgLo->data; - data[3] = dstLo->data; - - isect->coords[0] = isect->coords[1] = isect->coords[2] = 0; - VertexWeights( isect, orgUp, dstUp, &weights[0] ); - VertexWeights( isect, orgLo, dstLo, &weights[2] ); - - CallCombine( tess, isect, data, weights, TRUE ); -} - -static int CheckForRightSplice( GLUtesselator *tess, ActiveRegion *regUp ) -/* - * Check the upper and lower edge of "regUp", to make sure that the - * eUp->Org is above eLo, or eLo->Org is below eUp (depending on which - * origin is leftmost). - * - * The main purpose is to splice right-going edges with the same - * dest vertex and nearly identical slopes (ie. we can't distinguish - * the slopes numerically). However the splicing can also help us - * to recover from numerical errors. For example, suppose at one - * point we checked eUp and eLo, and decided that eUp->Org is barely - * above eLo. Then later, we split eLo into two edges (eg. from - * a splice operation like this one). This can change the result of - * our test so that now eUp->Org is incident to eLo, or barely below it. - * We must correct this condition to maintain the dictionary invariants. - * - * One possibility is to check these edges for intersection again - * (ie. CheckForIntersect). This is what we do if possible. However - * CheckForIntersect requires that tess->event lies between eUp and eLo, - * so that it has something to fall back on when the intersection - * calculation gives us an unusable answer. So, for those cases where - * we can't check for intersection, this routine fixes the problem - * by just splicing the offending vertex into the other edge. - * This is a guaranteed solution, no matter how degenerate things get. - * Basically this is a combinatorial solution to a numerical problem. - */ -{ - ActiveRegion *regLo = RegionBelow(regUp); - GLUhalfEdge *eUp = regUp->eUp; - GLUhalfEdge *eLo = regLo->eUp; - - if( VertLeq( eUp->Org, eLo->Org )) { - if( EdgeSign( eLo->Dst, eUp->Org, eLo->Org ) > 0 ) return FALSE; - - /* eUp->Org appears to be below eLo */ - if( ! VertEq( eUp->Org, eLo->Org )) { - /* Splice eUp->Org into eLo */ - if ( __gl_meshSplitEdge( eLo->Sym ) == NULL) longjmp(tess->env,1); - if ( !__gl_meshSplice( eUp, eLo->Oprev ) ) longjmp(tess->env,1); - regUp->dirty = regLo->dirty = TRUE; - - } else if( eUp->Org != eLo->Org ) { - /* merge the two vertices, discarding eUp->Org */ - pqDelete( tess->pq, eUp->Org->pqHandle ); /* __gl_pqSortDelete */ - SpliceMergeVertices( tess, eLo->Oprev, eUp ); - } - } else { - if( EdgeSign( eUp->Dst, eLo->Org, eUp->Org ) < 0 ) return FALSE; - - /* eLo->Org appears to be above eUp, so splice eLo->Org into eUp */ - RegionAbove(regUp)->dirty = regUp->dirty = TRUE; - if (__gl_meshSplitEdge( eUp->Sym ) == NULL) longjmp(tess->env,1); - if ( !__gl_meshSplice( eLo->Oprev, eUp ) ) longjmp(tess->env,1); - } - return TRUE; -} - -static int CheckForLeftSplice( GLUtesselator *tess, ActiveRegion *regUp ) -/* - * Check the upper and lower edge of "regUp", to make sure that the - * eUp->Dst is above eLo, or eLo->Dst is below eUp (depending on which - * destination is rightmost). - * - * Theoretically, this should always be true. However, splitting an edge - * into two pieces can change the results of previous tests. For example, - * suppose at one point we checked eUp and eLo, and decided that eUp->Dst - * is barely above eLo. Then later, we split eLo into two edges (eg. from - * a splice operation like this one). This can change the result of - * the test so that now eUp->Dst is incident to eLo, or barely below it. - * We must correct this condition to maintain the dictionary invariants - * (otherwise new edges might get inserted in the wrong place in the - * dictionary, and bad stuff will happen). - * - * We fix the problem by just splicing the offending vertex into the - * other edge. - */ -{ - ActiveRegion *regLo = RegionBelow(regUp); - GLUhalfEdge *eUp = regUp->eUp; - GLUhalfEdge *eLo = regLo->eUp; - GLUhalfEdge *e; - - assert( ! VertEq( eUp->Dst, eLo->Dst )); - - if( VertLeq( eUp->Dst, eLo->Dst )) { - if( EdgeSign( eUp->Dst, eLo->Dst, eUp->Org ) < 0 ) return FALSE; - - /* eLo->Dst is above eUp, so splice eLo->Dst into eUp */ - RegionAbove(regUp)->dirty = regUp->dirty = TRUE; - e = __gl_meshSplitEdge( eUp ); - if (e == NULL) longjmp(tess->env,1); - if ( !__gl_meshSplice( eLo->Sym, e ) ) longjmp(tess->env,1); - e->Lface->inside = regUp->inside; - } else { - if( EdgeSign( eLo->Dst, eUp->Dst, eLo->Org ) > 0 ) return FALSE; - - /* eUp->Dst is below eLo, so splice eUp->Dst into eLo */ - regUp->dirty = regLo->dirty = TRUE; - e = __gl_meshSplitEdge( eLo ); - if (e == NULL) longjmp(tess->env,1); - if ( !__gl_meshSplice( eUp->Lnext, eLo->Sym ) ) longjmp(tess->env,1); - e->Rface->inside = regUp->inside; - } - return TRUE; -} - - -static int CheckForIntersect( GLUtesselator *tess, ActiveRegion *regUp ) -/* - * Check the upper and lower edges of the given region to see if - * they intersect. If so, create the intersection and add it - * to the data structures. - * - * Returns TRUE if adding the new intersection resulted in a recursive - * call to AddRightEdges(); in this case all "dirty" regions have been - * checked for intersections, and possibly regUp has been deleted. - */ -{ - ActiveRegion *regLo = RegionBelow(regUp); - GLUhalfEdge *eUp = regUp->eUp; - GLUhalfEdge *eLo = regLo->eUp; - GLUvertex *orgUp = eUp->Org; - GLUvertex *orgLo = eLo->Org; - GLUvertex *dstUp = eUp->Dst; - GLUvertex *dstLo = eLo->Dst; - GLdouble tMinUp, tMaxLo; - GLUvertex isect, *orgMin; - GLUhalfEdge *e; - - assert( ! VertEq( dstLo, dstUp )); - assert( EdgeSign( dstUp, tess->event, orgUp ) <= 0 ); - assert( EdgeSign( dstLo, tess->event, orgLo ) >= 0 ); - assert( orgUp != tess->event && orgLo != tess->event ); - assert( ! regUp->fixUpperEdge && ! regLo->fixUpperEdge ); - - if( orgUp == orgLo ) return FALSE; /* right endpoints are the same */ - - tMinUp = MIN( orgUp->t, dstUp->t ); - tMaxLo = MAX( orgLo->t, dstLo->t ); - if( tMinUp > tMaxLo ) return FALSE; /* t ranges do not overlap */ - - if( VertLeq( orgUp, orgLo )) { - if( EdgeSign( dstLo, orgUp, orgLo ) > 0 ) return FALSE; - } else { - if( EdgeSign( dstUp, orgLo, orgUp ) < 0 ) return FALSE; - } - - /* At this point the edges intersect, at least marginally */ - DebugEvent( tess ); - - __gl_edgeIntersect( dstUp, orgUp, dstLo, orgLo, &isect ); - /* The following properties are guaranteed: */ - assert( MIN( orgUp->t, dstUp->t ) <= isect.t ); - assert( isect.t <= MAX( orgLo->t, dstLo->t )); - assert( MIN( dstLo->s, dstUp->s ) <= isect.s ); - assert( isect.s <= MAX( orgLo->s, orgUp->s )); - - if( VertLeq( &isect, tess->event )) { - /* The intersection point lies slightly to the left of the sweep line, - * so move it until it''s slightly to the right of the sweep line. - * (If we had perfect numerical precision, this would never happen - * in the first place). The easiest and safest thing to do is - * replace the intersection by tess->event. - */ - isect.s = tess->event->s; - isect.t = tess->event->t; - } - /* Similarly, if the computed intersection lies to the right of the - * rightmost origin (which should rarely happen), it can cause - * unbelievable inefficiency on sufficiently degenerate inputs. - * (If you have the test program, try running test54.d with the - * "X zoom" option turned on). - */ - orgMin = VertLeq( orgUp, orgLo ) ? orgUp : orgLo; - if( VertLeq( orgMin, &isect )) { - isect.s = orgMin->s; - isect.t = orgMin->t; - } - - if( VertEq( &isect, orgUp ) || VertEq( &isect, orgLo )) { - /* Easy case -- intersection at one of the right endpoints */ - (void) CheckForRightSplice( tess, regUp ); - return FALSE; - } - - if( (! VertEq( dstUp, tess->event ) - && EdgeSign( dstUp, tess->event, &isect ) >= 0) - || (! VertEq( dstLo, tess->event ) - && EdgeSign( dstLo, tess->event, &isect ) <= 0 )) - { - /* Very unusual -- the new upper or lower edge would pass on the - * wrong side of the sweep event, or through it. This can happen - * due to very small numerical errors in the intersection calculation. - */ - if( dstLo == tess->event ) { - /* Splice dstLo into eUp, and process the new region(s) */ - if (__gl_meshSplitEdge( eUp->Sym ) == NULL) longjmp(tess->env,1); - if ( !__gl_meshSplice( eLo->Sym, eUp ) ) longjmp(tess->env,1); - regUp = TopLeftRegion( regUp ); - if (regUp == NULL) longjmp(tess->env,1); - eUp = RegionBelow(regUp)->eUp; - FinishLeftRegions( tess, RegionBelow(regUp), regLo ); - AddRightEdges( tess, regUp, eUp->Oprev, eUp, eUp, TRUE ); - return TRUE; - } - if( dstUp == tess->event ) { - /* Splice dstUp into eLo, and process the new region(s) */ - if (__gl_meshSplitEdge( eLo->Sym ) == NULL) longjmp(tess->env,1); - if ( !__gl_meshSplice( eUp->Lnext, eLo->Oprev ) ) longjmp(tess->env,1); - regLo = regUp; - regUp = TopRightRegion( regUp ); - e = RegionBelow(regUp)->eUp->Rprev; - regLo->eUp = eLo->Oprev; - eLo = FinishLeftRegions( tess, regLo, NULL ); - AddRightEdges( tess, regUp, eLo->Onext, eUp->Rprev, e, TRUE ); - return TRUE; - } - /* Special case: called from ConnectRightVertex. If either - * edge passes on the wrong side of tess->event, split it - * (and wait for ConnectRightVertex to splice it appropriately). - */ - if( EdgeSign( dstUp, tess->event, &isect ) >= 0 ) { - RegionAbove(regUp)->dirty = regUp->dirty = TRUE; - if (__gl_meshSplitEdge( eUp->Sym ) == NULL) longjmp(tess->env,1); - eUp->Org->s = tess->event->s; - eUp->Org->t = tess->event->t; - } - if( EdgeSign( dstLo, tess->event, &isect ) <= 0 ) { - regUp->dirty = regLo->dirty = TRUE; - if (__gl_meshSplitEdge( eLo->Sym ) == NULL) longjmp(tess->env,1); - eLo->Org->s = tess->event->s; - eLo->Org->t = tess->event->t; - } - /* leave the rest for ConnectRightVertex */ - return FALSE; - } - - /* General case -- split both edges, splice into new vertex. - * When we do the splice operation, the order of the arguments is - * arbitrary as far as correctness goes. However, when the operation - * creates a new face, the work done is proportional to the size of - * the new face. We expect the faces in the processed part of - * the mesh (ie. eUp->Lface) to be smaller than the faces in the - * unprocessed original contours (which will be eLo->Oprev->Lface). - */ - if (__gl_meshSplitEdge( eUp->Sym ) == NULL) longjmp(tess->env,1); - if (__gl_meshSplitEdge( eLo->Sym ) == NULL) longjmp(tess->env,1); - if ( !__gl_meshSplice( eLo->Oprev, eUp ) ) longjmp(tess->env,1); - eUp->Org->s = isect.s; - eUp->Org->t = isect.t; - eUp->Org->pqHandle = pqInsert( tess->pq, eUp->Org ); /* __gl_pqSortInsert */ - if (eUp->Org->pqHandle == LONG_MAX) { - pqDeletePriorityQ(tess->pq); /* __gl_pqSortDeletePriorityQ */ - tess->pq = NULL; - longjmp(tess->env,1); - } - GetIntersectData( tess, eUp->Org, orgUp, dstUp, orgLo, dstLo ); - RegionAbove(regUp)->dirty = regUp->dirty = regLo->dirty = TRUE; - return FALSE; -} - -static void WalkDirtyRegions( GLUtesselator *tess, ActiveRegion *regUp ) -/* - * When the upper or lower edge of any region changes, the region is - * marked "dirty". This routine walks through all the dirty regions - * and makes sure that the dictionary invariants are satisfied - * (see the comments at the beginning of this file). Of course - * new dirty regions can be created as we make changes to restore - * the invariants. - */ -{ - ActiveRegion *regLo = RegionBelow(regUp); - GLUhalfEdge *eUp, *eLo; - - for( ;; ) { - /* Find the lowest dirty region (we walk from the bottom up). */ - while( regLo->dirty ) { - regUp = regLo; - regLo = RegionBelow(regLo); - } - if( ! regUp->dirty ) { - regLo = regUp; - regUp = RegionAbove( regUp ); - if( regUp == NULL || ! regUp->dirty ) { - /* We've walked all the dirty regions */ - return; - } - } - regUp->dirty = FALSE; - eUp = regUp->eUp; - eLo = regLo->eUp; - - if( eUp->Dst != eLo->Dst ) { - /* Check that the edge ordering is obeyed at the Dst vertices. */ - if( CheckForLeftSplice( tess, regUp )) { - - /* If the upper or lower edge was marked fixUpperEdge, then - * we no longer need it (since these edges are needed only for - * vertices which otherwise have no right-going edges). - */ - if( regLo->fixUpperEdge ) { - DeleteRegion( tess, regLo ); - if ( !__gl_meshDelete( eLo ) ) longjmp(tess->env,1); - regLo = RegionBelow( regUp ); - eLo = regLo->eUp; - } else if( regUp->fixUpperEdge ) { - DeleteRegion( tess, regUp ); - if ( !__gl_meshDelete( eUp ) ) longjmp(tess->env,1); - regUp = RegionAbove( regLo ); - eUp = regUp->eUp; - } - } - } - if( eUp->Org != eLo->Org ) { - if( eUp->Dst != eLo->Dst - && ! regUp->fixUpperEdge && ! regLo->fixUpperEdge - && (eUp->Dst == tess->event || eLo->Dst == tess->event) ) - { - /* When all else fails in CheckForIntersect(), it uses tess->event - * as the intersection location. To make this possible, it requires - * that tess->event lie between the upper and lower edges, and also - * that neither of these is marked fixUpperEdge (since in the worst - * case it might splice one of these edges into tess->event, and - * violate the invariant that fixable edges are the only right-going - * edge from their associated vertex). - */ - if( CheckForIntersect( tess, regUp )) { - /* WalkDirtyRegions() was called recursively; we're done */ - return; - } - } else { - /* Even though we can't use CheckForIntersect(), the Org vertices - * may violate the dictionary edge ordering. Check and correct this. - */ - (void) CheckForRightSplice( tess, regUp ); - } - } - if( eUp->Org == eLo->Org && eUp->Dst == eLo->Dst ) { - /* A degenerate loop consisting of only two edges -- delete it. */ - AddWinding( eLo, eUp ); - DeleteRegion( tess, regUp ); - if ( !__gl_meshDelete( eUp ) ) longjmp(tess->env,1); - regUp = RegionAbove( regLo ); - } - } -} - - -static void ConnectRightVertex( GLUtesselator *tess, ActiveRegion *regUp, - GLUhalfEdge *eBottomLeft ) -/* - * Purpose: connect a "right" vertex vEvent (one where all edges go left) - * to the unprocessed portion of the mesh. Since there are no right-going - * edges, two regions (one above vEvent and one below) are being merged - * into one. "regUp" is the upper of these two regions. - * - * There are two reasons for doing this (adding a right-going edge): - * - if the two regions being merged are "inside", we must add an edge - * to keep them separated (the combined region would not be monotone). - * - in any case, we must leave some record of vEvent in the dictionary, - * so that we can merge vEvent with features that we have not seen yet. - * For example, maybe there is a vertical edge which passes just to - * the right of vEvent; we would like to splice vEvent into this edge. - * - * However, we don't want to connect vEvent to just any vertex. We don''t - * want the new edge to cross any other edges; otherwise we will create - * intersection vertices even when the input data had no self-intersections. - * (This is a bad thing; if the user's input data has no intersections, - * we don't want to generate any false intersections ourselves.) - * - * Our eventual goal is to connect vEvent to the leftmost unprocessed - * vertex of the combined region (the union of regUp and regLo). - * But because of unseen vertices with all right-going edges, and also - * new vertices which may be created by edge intersections, we don''t - * know where that leftmost unprocessed vertex is. In the meantime, we - * connect vEvent to the closest vertex of either chain, and mark the region - * as "fixUpperEdge". This flag says to delete and reconnect this edge - * to the next processed vertex on the boundary of the combined region. - * Quite possibly the vertex we connected to will turn out to be the - * closest one, in which case we won''t need to make any changes. - */ -{ - GLUhalfEdge *eNew; - GLUhalfEdge *eTopLeft = eBottomLeft->Onext; - ActiveRegion *regLo = RegionBelow(regUp); - GLUhalfEdge *eUp = regUp->eUp; - GLUhalfEdge *eLo = regLo->eUp; - int degenerate = FALSE; - - if( eUp->Dst != eLo->Dst ) { - (void) CheckForIntersect( tess, regUp ); - } - - /* Possible new degeneracies: upper or lower edge of regUp may pass - * through vEvent, or may coincide with new intersection vertex - */ - if( VertEq( eUp->Org, tess->event )) { - if ( !__gl_meshSplice( eTopLeft->Oprev, eUp ) ) longjmp(tess->env,1); - regUp = TopLeftRegion( regUp ); - if (regUp == NULL) longjmp(tess->env,1); - eTopLeft = RegionBelow( regUp )->eUp; - FinishLeftRegions( tess, RegionBelow(regUp), regLo ); - degenerate = TRUE; - } - if( VertEq( eLo->Org, tess->event )) { - if ( !__gl_meshSplice( eBottomLeft, eLo->Oprev ) ) longjmp(tess->env,1); - eBottomLeft = FinishLeftRegions( tess, regLo, NULL ); - degenerate = TRUE; - } - if( degenerate ) { - AddRightEdges( tess, regUp, eBottomLeft->Onext, eTopLeft, eTopLeft, TRUE ); - return; - } - - /* Non-degenerate situation -- need to add a temporary, fixable edge. - * Connect to the closer of eLo->Org, eUp->Org. - */ - if( VertLeq( eLo->Org, eUp->Org )) { - eNew = eLo->Oprev; - } else { - eNew = eUp; - } - eNew = __gl_meshConnect( eBottomLeft->Lprev, eNew ); - if (eNew == NULL) longjmp(tess->env,1); - - /* Prevent cleanup, otherwise eNew might disappear before we've even - * had a chance to mark it as a temporary edge. - */ - AddRightEdges( tess, regUp, eNew, eNew->Onext, eNew->Onext, FALSE ); - eNew->Sym->activeRegion->fixUpperEdge = TRUE; - WalkDirtyRegions( tess, regUp ); -} - -/* Because vertices at exactly the same location are merged together - * before we process the sweep event, some degenerate cases can't occur. - * However if someone eventually makes the modifications required to - * merge features which are close together, the cases below marked - * TOLERANCE_NONZERO will be useful. They were debugged before the - * code to merge identical vertices in the main loop was added. - */ -#define TOLERANCE_NONZERO FALSE - -static void ConnectLeftDegenerate( GLUtesselator *tess, - ActiveRegion *regUp, GLUvertex *vEvent ) -/* - * The event vertex lies exacty on an already-processed edge or vertex. - * Adding the new vertex involves splicing it into the already-processed - * part of the mesh. - */ -{ - GLUhalfEdge *e, *eTopLeft, *eTopRight, *eLast; - ActiveRegion *reg; - - e = regUp->eUp; - if( VertEq( e->Org, vEvent )) { - /* e->Org is an unprocessed vertex - just combine them, and wait - * for e->Org to be pulled from the queue - */ - assert( TOLERANCE_NONZERO ); - SpliceMergeVertices( tess, e, vEvent->anEdge ); - return; - } - - if( ! VertEq( e->Dst, vEvent )) { - /* General case -- splice vEvent into edge e which passes through it */ - if (__gl_meshSplitEdge( e->Sym ) == NULL) longjmp(tess->env,1); - if( regUp->fixUpperEdge ) { - /* This edge was fixable -- delete unused portion of original edge */ - if ( !__gl_meshDelete( e->Onext ) ) longjmp(tess->env,1); - regUp->fixUpperEdge = FALSE; - } - if ( !__gl_meshSplice( vEvent->anEdge, e ) ) longjmp(tess->env,1); - SweepEvent( tess, vEvent ); /* recurse */ - return; - } - - /* vEvent coincides with e->Dst, which has already been processed. - * Splice in the additional right-going edges. - */ - assert( TOLERANCE_NONZERO ); - regUp = TopRightRegion( regUp ); - reg = RegionBelow( regUp ); - eTopRight = reg->eUp->Sym; - eTopLeft = eLast = eTopRight->Onext; - if( reg->fixUpperEdge ) { - /* Here e->Dst has only a single fixable edge going right. - * We can delete it since now we have some real right-going edges. - */ - assert( eTopLeft != eTopRight ); /* there are some left edges too */ - DeleteRegion( tess, reg ); - if ( !__gl_meshDelete( eTopRight ) ) longjmp(tess->env,1); - eTopRight = eTopLeft->Oprev; - } - if ( !__gl_meshSplice( vEvent->anEdge, eTopRight ) ) longjmp(tess->env,1); - if( ! EdgeGoesLeft( eTopLeft )) { - /* e->Dst had no left-going edges -- indicate this to AddRightEdges() */ - eTopLeft = NULL; - } - AddRightEdges( tess, regUp, eTopRight->Onext, eLast, eTopLeft, TRUE ); -} - - -static void ConnectLeftVertex( GLUtesselator *tess, GLUvertex *vEvent ) -/* - * Purpose: connect a "left" vertex (one where both edges go right) - * to the processed portion of the mesh. Let R be the active region - * containing vEvent, and let U and L be the upper and lower edge - * chains of R. There are two possibilities: - * - * - the normal case: split R into two regions, by connecting vEvent to - * the rightmost vertex of U or L lying to the left of the sweep line - * - * - the degenerate case: if vEvent is close enough to U or L, we - * merge vEvent into that edge chain. The subcases are: - * - merging with the rightmost vertex of U or L - * - merging with the active edge of U or L - * - merging with an already-processed portion of U or L - */ -{ - ActiveRegion *regUp, *regLo, *reg; - GLUhalfEdge *eUp, *eLo, *eNew; - ActiveRegion tmp; - - /* assert( vEvent->anEdge->Onext->Onext == vEvent->anEdge ); */ - - /* Get a pointer to the active region containing vEvent */ - tmp.eUp = vEvent->anEdge->Sym; - /* __GL_DICTLISTKEY */ /* __gl_dictListSearch */ - regUp = (ActiveRegion *)dictKey( dictSearch( tess->dict, &tmp )); - regLo = RegionBelow( regUp ); - eUp = regUp->eUp; - eLo = regLo->eUp; - - /* Try merging with U or L first */ - if( EdgeSign( eUp->Dst, vEvent, eUp->Org ) == 0 ) { - ConnectLeftDegenerate( tess, regUp, vEvent ); - return; - } - - /* Connect vEvent to rightmost processed vertex of either chain. - * e->Dst is the vertex that we will connect to vEvent. - */ - reg = VertLeq( eLo->Dst, eUp->Dst ) ? regUp : regLo; - - if( regUp->inside || reg->fixUpperEdge) { - if( reg == regUp ) { - eNew = __gl_meshConnect( vEvent->anEdge->Sym, eUp->Lnext ); - if (eNew == NULL) longjmp(tess->env,1); - } else { - GLUhalfEdge *tempHalfEdge= __gl_meshConnect( eLo->Dnext, vEvent->anEdge); - if (tempHalfEdge == NULL) longjmp(tess->env,1); - - eNew = tempHalfEdge->Sym; - } - if( reg->fixUpperEdge ) { - if ( !FixUpperEdge( reg, eNew ) ) longjmp(tess->env,1); - } else { - ComputeWinding( tess, AddRegionBelow( tess, regUp, eNew )); - } - SweepEvent( tess, vEvent ); - } else { - /* The new vertex is in a region which does not belong to the polygon. - * We don''t need to connect this vertex to the rest of the mesh. - */ - AddRightEdges( tess, regUp, vEvent->anEdge, vEvent->anEdge, NULL, TRUE ); - } -} - - -static void SweepEvent( GLUtesselator *tess, GLUvertex *vEvent ) -/* - * Does everything necessary when the sweep line crosses a vertex. - * Updates the mesh and the edge dictionary. - */ -{ - ActiveRegion *regUp, *reg; - GLUhalfEdge *e, *eTopLeft, *eBottomLeft; - - tess->event = vEvent; /* for access in EdgeLeq() */ - DebugEvent( tess ); - - /* Check if this vertex is the right endpoint of an edge that is - * already in the dictionary. In this case we don't need to waste - * time searching for the location to insert new edges. - */ - e = vEvent->anEdge; - while( e->activeRegion == NULL ) { - e = e->Onext; - if( e == vEvent->anEdge ) { - /* All edges go right -- not incident to any processed edges */ - ConnectLeftVertex( tess, vEvent ); - return; - } - } - - /* Processing consists of two phases: first we "finish" all the - * active regions where both the upper and lower edges terminate - * at vEvent (ie. vEvent is closing off these regions). - * We mark these faces "inside" or "outside" the polygon according - * to their winding number, and delete the edges from the dictionary. - * This takes care of all the left-going edges from vEvent. - */ - regUp = TopLeftRegion( e->activeRegion ); - if (regUp == NULL) longjmp(tess->env,1); - reg = RegionBelow( regUp ); - eTopLeft = reg->eUp; - eBottomLeft = FinishLeftRegions( tess, reg, NULL ); - - /* Next we process all the right-going edges from vEvent. This - * involves adding the edges to the dictionary, and creating the - * associated "active regions" which record information about the - * regions between adjacent dictionary edges. - */ - if( eBottomLeft->Onext == eTopLeft ) { - /* No right-going edges -- add a temporary "fixable" edge */ - ConnectRightVertex( tess, regUp, eBottomLeft ); - } else { - AddRightEdges( tess, regUp, eBottomLeft->Onext, eTopLeft, eTopLeft, TRUE ); - } -} - - -/* Make the sentinel coordinates big enough that they will never be - * merged with real input features. (Even with the largest possible - * input contour and the maximum tolerance of 1.0, no merging will be - * done with coordinates larger than 3 * GLU_TESS_MAX_COORD). - */ -#define SENTINEL_COORD (4 * GLU_TESS_MAX_COORD) - -static void AddSentinel( GLUtesselator *tess, GLdouble t ) -/* - * We add two sentinel edges above and below all other edges, - * to avoid special cases at the top and bottom. - */ -{ - GLUhalfEdge *e; - ActiveRegion *reg = (ActiveRegion *)memAlloc( sizeof( ActiveRegion )); - if (reg == NULL) longjmp(tess->env,1); - - e = __gl_meshMakeEdge( tess->mesh ); - if (e == NULL) longjmp(tess->env,1); - - e->Org->s = SENTINEL_COORD; - e->Org->t = t; - e->Dst->s = -SENTINEL_COORD; - e->Dst->t = t; - tess->event = e->Dst; /* initialize it */ - - reg->eUp = e; - reg->windingNumber = 0; - reg->inside = FALSE; - reg->fixUpperEdge = FALSE; - reg->sentinel = TRUE; - reg->dirty = FALSE; - reg->nodeUp = dictInsert( tess->dict, reg ); /* __gl_dictListInsertBefore */ - if (reg->nodeUp == NULL) longjmp(tess->env,1); -} - - -static void InitEdgeDict( GLUtesselator *tess ) -/* - * We maintain an ordering of edge intersections with the sweep line. - * This order is maintained in a dynamic dictionary. - */ -{ - /* __gl_dictListNewDict */ - tess->dict = dictNewDict( tess, (int (*)(void *, DictKey, DictKey)) EdgeLeq ); - if (tess->dict == NULL) longjmp(tess->env,1); - - AddSentinel( tess, -SENTINEL_COORD ); - AddSentinel( tess, SENTINEL_COORD ); -} - - -static void DoneEdgeDict( GLUtesselator *tess ) -{ - ActiveRegion *reg; -#ifndef NDEBUG - int fixedEdges = 0; -#endif - - /* __GL_DICTLISTKEY */ /* __GL_DICTLISTMIN */ - while( (reg = (ActiveRegion *)dictKey( dictMin( tess->dict ))) != NULL ) { - /* - * At the end of all processing, the dictionary should contain - * only the two sentinel edges, plus at most one "fixable" edge - * created by ConnectRightVertex(). - */ - if( ! reg->sentinel ) { - assert( reg->fixUpperEdge ); - assert( ++fixedEdges == 1 ); - } - assert( reg->windingNumber == 0 ); - DeleteRegion( tess, reg ); -/* __gl_meshDelete( reg->eUp );*/ - } - dictDeleteDict( tess->dict ); /* __gl_dictListDeleteDict */ -} - - -static void RemoveDegenerateEdges( GLUtesselator *tess ) -/* - * Remove zero-length edges, and contours with fewer than 3 vertices. - */ -{ - GLUhalfEdge *e, *eNext, *eLnext; - GLUhalfEdge *eHead = &tess->mesh->eHead; - - /*LINTED*/ - for( e = eHead->next; e != eHead; e = eNext ) { - eNext = e->next; - eLnext = e->Lnext; - - if( VertEq( e->Org, e->Dst ) && e->Lnext->Lnext != e ) { - /* Zero-length edge, contour has at least 3 edges */ - - SpliceMergeVertices( tess, eLnext, e ); /* deletes e->Org */ - if ( !__gl_meshDelete( e ) ) longjmp(tess->env,1); /* e is a self-loop */ - e = eLnext; - eLnext = e->Lnext; - } - if( eLnext->Lnext == e ) { - /* Degenerate contour (one or two edges) */ - - if( eLnext != e ) { - if( eLnext == eNext || eLnext == eNext->Sym ) { eNext = eNext->next; } - if ( !__gl_meshDelete( eLnext ) ) longjmp(tess->env,1); - } - if( e == eNext || e == eNext->Sym ) { eNext = eNext->next; } - if ( !__gl_meshDelete( e ) ) longjmp(tess->env,1); - } - } -} - -static int InitPriorityQ( GLUtesselator *tess ) -/* - * Insert all vertices into the priority queue which determines the - * order in which vertices cross the sweep line. - */ -{ - PriorityQ *pq; - GLUvertex *v, *vHead; - - /* __gl_pqSortNewPriorityQ */ - pq = tess->pq = pqNewPriorityQ( (int (*)(PQkey, PQkey)) __gl_vertLeq ); - if (pq == NULL) return 0; - - vHead = &tess->mesh->vHead; - for( v = vHead->next; v != vHead; v = v->next ) { - v->pqHandle = pqInsert( pq, v ); /* __gl_pqSortInsert */ - if (v->pqHandle == LONG_MAX) break; - } - if (v != vHead || !pqInit( pq ) ) { /* __gl_pqSortInit */ - pqDeletePriorityQ(tess->pq); /* __gl_pqSortDeletePriorityQ */ - tess->pq = NULL; - return 0; - } - - return 1; -} - - -static void DonePriorityQ( GLUtesselator *tess ) -{ - pqDeletePriorityQ( tess->pq ); /* __gl_pqSortDeletePriorityQ */ -} - - -static int RemoveDegenerateFaces( GLUmesh *mesh ) -/* - * Delete any degenerate faces with only two edges. WalkDirtyRegions() - * will catch almost all of these, but it won't catch degenerate faces - * produced by splice operations on already-processed edges. - * The two places this can happen are in FinishLeftRegions(), when - * we splice in a "temporary" edge produced by ConnectRightVertex(), - * and in CheckForLeftSplice(), where we splice already-processed - * edges to ensure that our dictionary invariants are not violated - * by numerical errors. - * - * In both these cases it is *very* dangerous to delete the offending - * edge at the time, since one of the routines further up the stack - * will sometimes be keeping a pointer to that edge. - */ -{ - GLUface *f, *fNext; - GLUhalfEdge *e; - - /*LINTED*/ - for( f = mesh->fHead.next; f != &mesh->fHead; f = fNext ) { - fNext = f->next; - e = f->anEdge; - assert( e->Lnext != e ); - - if( e->Lnext->Lnext == e ) { - /* A face with only two edges */ - AddWinding( e->Onext, e ); - if ( !__gl_meshDelete( e ) ) return 0; - } - } - return 1; -} - -int __gl_computeInterior( GLUtesselator *tess ) -/* - * __gl_computeInterior( tess ) computes the planar arrangement specified - * by the given contours, and further subdivides this arrangement - * into regions. Each region is marked "inside" if it belongs - * to the polygon, according to the rule given by tess->windingRule. - * Each interior region is guaranteed be monotone. - */ -{ - GLUvertex *v, *vNext; - - tess->fatalError = FALSE; - - /* Each vertex defines an event for our sweep line. Start by inserting - * all the vertices in a priority queue. Events are processed in - * lexicographic order, ie. - * - * e1 < e2 iff e1.x < e2.x || (e1.x == e2.x && e1.y < e2.y) - */ - RemoveDegenerateEdges( tess ); - if ( !InitPriorityQ( tess ) ) return 0; /* if error */ - InitEdgeDict( tess ); - - /* __gl_pqSortExtractMin */ - while( (v = (GLUvertex *)pqExtractMin( tess->pq )) != NULL ) { - for( ;; ) { - vNext = (GLUvertex *)pqMinimum( tess->pq ); /* __gl_pqSortMinimum */ - if( vNext == NULL || ! VertEq( vNext, v )) break; - - /* Merge together all vertices at exactly the same location. - * This is more efficient than processing them one at a time, - * simplifies the code (see ConnectLeftDegenerate), and is also - * important for correct handling of certain degenerate cases. - * For example, suppose there are two identical edges A and B - * that belong to different contours (so without this code they would - * be processed by separate sweep events). Suppose another edge C - * crosses A and B from above. When A is processed, we split it - * at its intersection point with C. However this also splits C, - * so when we insert B we may compute a slightly different - * intersection point. This might leave two edges with a small - * gap between them. This kind of error is especially obvious - * when using boundary extraction (GLU_TESS_BOUNDARY_ONLY). - */ - vNext = (GLUvertex *)pqExtractMin( tess->pq ); /* __gl_pqSortExtractMin*/ - SpliceMergeVertices( tess, v->anEdge, vNext->anEdge ); - } - SweepEvent( tess, v ); - } - - /* Set tess->event for debugging purposes */ - /* __GL_DICTLISTKEY */ /* __GL_DICTLISTMIN */ - tess->event = ((ActiveRegion *) dictKey( dictMin( tess->dict )))->eUp->Org; - DebugEvent( tess ); - DoneEdgeDict( tess ); - DonePriorityQ( tess ); - - if ( !RemoveDegenerateFaces( tess->mesh ) ) return 0; - __gl_meshCheckMesh( tess->mesh ); - - return 1; -} diff --git a/src/glu/sgi/libtess/sweep.h b/src/glu/sgi/libtess/sweep.h deleted file mode 100644 index feb68b0ffe5..00000000000 --- a/src/glu/sgi/libtess/sweep.h +++ /dev/null @@ -1,77 +0,0 @@ -/* - * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008) - * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved. - * - * Permission is hereby granted, free of charge, to any person obtaining a - * copy of this software and associated documentation files (the "Software"), - * to deal in the Software without restriction, including without limitation - * the rights to use, copy, modify, merge, publish, distribute, sublicense, - * and/or sell copies of the Software, and to permit persons to whom the - * Software is furnished to do so, subject to the following conditions: - * - * The above copyright notice including the dates of first publication and - * either this permission notice or a reference to - * http://oss.sgi.com/projects/FreeB/ - * shall be included in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS - * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL - * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, - * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF - * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - * - * Except as contained in this notice, the name of Silicon Graphics, Inc. - * shall not be used in advertising or otherwise to promote the sale, use or - * other dealings in this Software without prior written authorization from - * Silicon Graphics, Inc. - */ -/* -** Author: Eric Veach, July 1994. -** -*/ - -#ifndef __sweep_h_ -#define __sweep_h_ - -#include "mesh.h" - -/* __gl_computeInterior( tess ) computes the planar arrangement specified - * by the given contours, and further subdivides this arrangement - * into regions. Each region is marked "inside" if it belongs - * to the polygon, according to the rule given by tess->windingRule. - * Each interior region is guaranteed be monotone. - */ -int __gl_computeInterior( GLUtesselator *tess ); - - -/* The following is here *only* for access by debugging routines */ - -#include "dict.h" - -/* For each pair of adjacent edges crossing the sweep line, there is - * an ActiveRegion to represent the region between them. The active - * regions are kept in sorted order in a dynamic dictionary. As the - * sweep line crosses each vertex, we update the affected regions. - */ - -struct ActiveRegion { - GLUhalfEdge *eUp; /* upper edge, directed right to left */ - DictNode *nodeUp; /* dictionary node corresponding to eUp */ - int windingNumber; /* used to determine which regions are - * inside the polygon */ - GLboolean inside; /* is this region inside the polygon? */ - GLboolean sentinel; /* marks fake edges at t = +/-infinity */ - GLboolean dirty; /* marks regions where the upper or lower - * edge has changed, but we haven't checked - * whether they intersect yet */ - GLboolean fixUpperEdge; /* marks temporary edges introduced when - * we process a "right vertex" (one without - * any edges leaving to the right) */ -}; - -#define RegionBelow(r) ((ActiveRegion *) dictKey(dictPred((r)->nodeUp))) -#define RegionAbove(r) ((ActiveRegion *) dictKey(dictSucc((r)->nodeUp))) - -#endif diff --git a/src/glu/sgi/libtess/tess.c b/src/glu/sgi/libtess/tess.c deleted file mode 100644 index 4a0e8dea7f7..00000000000 --- a/src/glu/sgi/libtess/tess.c +++ /dev/null @@ -1,632 +0,0 @@ -/* - * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008) - * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved. - * - * Permission is hereby granted, free of charge, to any person obtaining a - * copy of this software and associated documentation files (the "Software"), - * to deal in the Software without restriction, including without limitation - * the rights to use, copy, modify, merge, publish, distribute, sublicense, - * and/or sell copies of the Software, and to permit persons to whom the - * Software is furnished to do so, subject to the following conditions: - * - * The above copyright notice including the dates of first publication and - * either this permission notice or a reference to - * http://oss.sgi.com/projects/FreeB/ - * shall be included in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS - * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL - * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, - * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF - * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - * - * Except as contained in this notice, the name of Silicon Graphics, Inc. - * shall not be used in advertising or otherwise to promote the sale, use or - * other dealings in this Software without prior written authorization from - * Silicon Graphics, Inc. - */ -/* -** Author: Eric Veach, July 1994. -** -*/ - -#include "gluos.h" -#include <stddef.h> -#include <assert.h> -#include <setjmp.h> -#include "memalloc.h" -#include "tess.h" -#include "mesh.h" -#include "normal.h" -#include "sweep.h" -#include "tessmono.h" -#include "render.h" - -#define GLU_TESS_DEFAULT_TOLERANCE 0.0 -#define GLU_TESS_MESH 100112 /* void (*)(GLUmesh *mesh) */ - -#ifndef TRUE -#define TRUE 1 -#endif -#ifndef FALSE -#define FALSE 0 -#endif - -/*ARGSUSED*/ static void GLAPIENTRY noBegin( GLenum type ) {} -/*ARGSUSED*/ static void GLAPIENTRY noEdgeFlag( GLboolean boundaryEdge ) {} -/*ARGSUSED*/ static void GLAPIENTRY noVertex( void *data ) {} -/*ARGSUSED*/ static void GLAPIENTRY noEnd( void ) {} -/*ARGSUSED*/ static void GLAPIENTRY noError( GLenum errnum ) {} -/*ARGSUSED*/ static void GLAPIENTRY noCombine( GLdouble coords[3], void *data[4], - GLfloat weight[4], void **dataOut ) {} -/*ARGSUSED*/ static void GLAPIENTRY noMesh( GLUmesh *mesh ) {} - - -/*ARGSUSED*/ void GLAPIENTRY __gl_noBeginData( GLenum type, - void *polygonData ) {} -/*ARGSUSED*/ void GLAPIENTRY __gl_noEdgeFlagData( GLboolean boundaryEdge, - void *polygonData ) {} -/*ARGSUSED*/ void GLAPIENTRY __gl_noVertexData( void *data, - void *polygonData ) {} -/*ARGSUSED*/ void GLAPIENTRY __gl_noEndData( void *polygonData ) {} -/*ARGSUSED*/ void GLAPIENTRY __gl_noErrorData( GLenum errnum, - void *polygonData ) {} -/*ARGSUSED*/ void GLAPIENTRY __gl_noCombineData( GLdouble coords[3], - void *data[4], - GLfloat weight[4], - void **outData, - void *polygonData ) {} - -/* Half-edges are allocated in pairs (see mesh.c) */ -typedef struct { GLUhalfEdge e, eSym; } EdgePair; - -#undef MAX -#define MAX(a,b) ((a) > (b) ? (a) : (b)) -#define MAX_FAST_ALLOC (MAX(sizeof(EdgePair), \ - MAX(sizeof(GLUvertex),sizeof(GLUface)))) - - -GLUtesselator * GLAPIENTRY -gluNewTess( void ) -{ - GLUtesselator *tess; - - /* Only initialize fields which can be changed by the api. Other fields - * are initialized where they are used. - */ - - if (memInit( MAX_FAST_ALLOC ) == 0) { - return 0; /* out of memory */ - } - tess = (GLUtesselator *)memAlloc( sizeof( GLUtesselator )); - if (tess == NULL) { - return 0; /* out of memory */ - } - - tess->state = T_DORMANT; - - tess->normal[0] = 0; - tess->normal[1] = 0; - tess->normal[2] = 0; - - tess->relTolerance = GLU_TESS_DEFAULT_TOLERANCE; - tess->windingRule = GLU_TESS_WINDING_ODD; - tess->flagBoundary = FALSE; - tess->boundaryOnly = FALSE; - - tess->callBegin = &noBegin; - tess->callEdgeFlag = &noEdgeFlag; - tess->callVertex = &noVertex; - tess->callEnd = &noEnd; - - tess->callError = &noError; - tess->callCombine = &noCombine; - tess->callMesh = &noMesh; - - tess->callBeginData= &__gl_noBeginData; - tess->callEdgeFlagData= &__gl_noEdgeFlagData; - tess->callVertexData= &__gl_noVertexData; - tess->callEndData= &__gl_noEndData; - tess->callErrorData= &__gl_noErrorData; - tess->callCombineData= &__gl_noCombineData; - - tess->polygonData= NULL; - - return tess; -} - -static void MakeDormant( GLUtesselator *tess ) -{ - /* Return the tessellator to its original dormant state. */ - - if( tess->mesh != NULL ) { - __gl_meshDeleteMesh( tess->mesh ); - } - tess->state = T_DORMANT; - tess->lastEdge = NULL; - tess->mesh = NULL; -} - -#define RequireState( tess, s ) if( tess->state != s ) GotoState(tess,s) - -static void GotoState( GLUtesselator *tess, enum TessState newState ) -{ - while( tess->state != newState ) { - /* We change the current state one level at a time, to get to - * the desired state. - */ - if( tess->state < newState ) { - switch( tess->state ) { - case T_DORMANT: - CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_BEGIN_POLYGON ); - gluTessBeginPolygon( tess, NULL ); - break; - case T_IN_POLYGON: - CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_BEGIN_CONTOUR ); - gluTessBeginContour( tess ); - break; - default: - ; - } - } else { - switch( tess->state ) { - case T_IN_CONTOUR: - CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_END_CONTOUR ); - gluTessEndContour( tess ); - break; - case T_IN_POLYGON: - CALL_ERROR_OR_ERROR_DATA( GLU_TESS_MISSING_END_POLYGON ); - /* gluTessEndPolygon( tess ) is too much work! */ - MakeDormant( tess ); - break; - default: - ; - } - } - } -} - - -void GLAPIENTRY -gluDeleteTess( GLUtesselator *tess ) -{ - RequireState( tess, T_DORMANT ); - memFree( tess ); -} - - -void GLAPIENTRY -gluTessProperty( GLUtesselator *tess, GLenum which, GLdouble value ) -{ - GLenum windingRule; - - switch( which ) { - case GLU_TESS_TOLERANCE: - if( value < 0.0 || value > 1.0 ) break; - tess->relTolerance = value; - return; - - case GLU_TESS_WINDING_RULE: - windingRule = (GLenum) value; - if( windingRule != value ) break; /* not an integer */ - - switch( windingRule ) { - case GLU_TESS_WINDING_ODD: - case GLU_TESS_WINDING_NONZERO: - case GLU_TESS_WINDING_POSITIVE: - case GLU_TESS_WINDING_NEGATIVE: - case GLU_TESS_WINDING_ABS_GEQ_TWO: - tess->windingRule = windingRule; - return; - default: - break; - } - - case GLU_TESS_BOUNDARY_ONLY: - tess->boundaryOnly = (value != 0); - return; - - default: - CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_ENUM ); - return; - } - CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_VALUE ); -} - -/* Returns tessellator property */ -void GLAPIENTRY -gluGetTessProperty( GLUtesselator *tess, GLenum which, GLdouble *value ) -{ - switch (which) { - case GLU_TESS_TOLERANCE: - /* tolerance should be in range [0..1] */ - assert(0.0 <= tess->relTolerance && tess->relTolerance <= 1.0); - *value= tess->relTolerance; - break; - case GLU_TESS_WINDING_RULE: - assert(tess->windingRule == GLU_TESS_WINDING_ODD || - tess->windingRule == GLU_TESS_WINDING_NONZERO || - tess->windingRule == GLU_TESS_WINDING_POSITIVE || - tess->windingRule == GLU_TESS_WINDING_NEGATIVE || - tess->windingRule == GLU_TESS_WINDING_ABS_GEQ_TWO); - *value= tess->windingRule; - break; - case GLU_TESS_BOUNDARY_ONLY: - assert(tess->boundaryOnly == TRUE || tess->boundaryOnly == FALSE); - *value= tess->boundaryOnly; - break; - default: - *value= 0.0; - CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_ENUM ); - break; - } -} /* gluGetTessProperty() */ - -void GLAPIENTRY -gluTessNormal( GLUtesselator *tess, GLdouble x, GLdouble y, GLdouble z ) -{ - tess->normal[0] = x; - tess->normal[1] = y; - tess->normal[2] = z; -} - -void GLAPIENTRY -gluTessCallback( GLUtesselator *tess, GLenum which, _GLUfuncptr fn) -{ - switch( which ) { - case GLU_TESS_BEGIN: - tess->callBegin = (fn == NULL) ? &noBegin : (void (GLAPIENTRY *)(GLenum)) fn; - return; - case GLU_TESS_BEGIN_DATA: - tess->callBeginData = (fn == NULL) ? - &__gl_noBeginData : (void (GLAPIENTRY *)(GLenum, void *)) fn; - return; - case GLU_TESS_EDGE_FLAG: - tess->callEdgeFlag = (fn == NULL) ? &noEdgeFlag : - (void (GLAPIENTRY *)(GLboolean)) fn; - /* If the client wants boundary edges to be flagged, - * we render everything as separate triangles (no strips or fans). - */ - tess->flagBoundary = (fn != NULL); - return; - case GLU_TESS_EDGE_FLAG_DATA: - tess->callEdgeFlagData= (fn == NULL) ? - &__gl_noEdgeFlagData : (void (GLAPIENTRY *)(GLboolean, void *)) fn; - /* If the client wants boundary edges to be flagged, - * we render everything as separate triangles (no strips or fans). - */ - tess->flagBoundary = (fn != NULL); - return; - case GLU_TESS_VERTEX: - tess->callVertex = (fn == NULL) ? &noVertex : - (void (GLAPIENTRY *)(void *)) fn; - return; - case GLU_TESS_VERTEX_DATA: - tess->callVertexData = (fn == NULL) ? - &__gl_noVertexData : (void (GLAPIENTRY *)(void *, void *)) fn; - return; - case GLU_TESS_END: - tess->callEnd = (fn == NULL) ? &noEnd : (void (GLAPIENTRY *)(void)) fn; - return; - case GLU_TESS_END_DATA: - tess->callEndData = (fn == NULL) ? &__gl_noEndData : - (void (GLAPIENTRY *)(void *)) fn; - return; - case GLU_TESS_ERROR: - tess->callError = (fn == NULL) ? &noError : (void (GLAPIENTRY *)(GLenum)) fn; - return; - case GLU_TESS_ERROR_DATA: - tess->callErrorData = (fn == NULL) ? - &__gl_noErrorData : (void (GLAPIENTRY *)(GLenum, void *)) fn; - return; - case GLU_TESS_COMBINE: - tess->callCombine = (fn == NULL) ? &noCombine : - (void (GLAPIENTRY *)(GLdouble [3],void *[4], GLfloat [4], void ** )) fn; - return; - case GLU_TESS_COMBINE_DATA: - tess->callCombineData = (fn == NULL) ? &__gl_noCombineData : - (void (GLAPIENTRY *)(GLdouble [3], - void *[4], - GLfloat [4], - void **, - void *)) fn; - return; - case GLU_TESS_MESH: - tess->callMesh = (fn == NULL) ? &noMesh : (void (GLAPIENTRY *)(GLUmesh *)) fn; - return; - default: - CALL_ERROR_OR_ERROR_DATA( GLU_INVALID_ENUM ); - return; - } -} - -static int AddVertex( GLUtesselator *tess, GLdouble coords[3], void *data ) -{ - GLUhalfEdge *e; - - e = tess->lastEdge; - if( e == NULL ) { - /* Make a self-loop (one vertex, one edge). */ - - e = __gl_meshMakeEdge( tess->mesh ); - if (e == NULL) return 0; - if ( !__gl_meshSplice( e, e->Sym ) ) return 0; - } else { - /* Create a new vertex and edge which immediately follow e - * in the ordering around the left face. - */ - if (__gl_meshSplitEdge( e ) == NULL) return 0; - e = e->Lnext; - } - - /* The new vertex is now e->Org. */ - e->Org->data = data; - e->Org->coords[0] = coords[0]; - e->Org->coords[1] = coords[1]; - e->Org->coords[2] = coords[2]; - - /* The winding of an edge says how the winding number changes as we - * cross from the edge''s right face to its left face. We add the - * vertices in such an order that a CCW contour will add +1 to - * the winding number of the region inside the contour. - */ - e->winding = 1; - e->Sym->winding = -1; - - tess->lastEdge = e; - - return 1; -} - - -static void CacheVertex( GLUtesselator *tess, GLdouble coords[3], void *data ) -{ - CachedVertex *v = &tess->cache[tess->cacheCount]; - - v->data = data; - v->coords[0] = coords[0]; - v->coords[1] = coords[1]; - v->coords[2] = coords[2]; - ++tess->cacheCount; -} - - -static int EmptyCache( GLUtesselator *tess ) -{ - CachedVertex *v = tess->cache; - CachedVertex *vLast; - - tess->mesh = __gl_meshNewMesh(); - if (tess->mesh == NULL) return 0; - - for( vLast = v + tess->cacheCount; v < vLast; ++v ) { - if ( !AddVertex( tess, v->coords, v->data ) ) return 0; - } - tess->cacheCount = 0; - tess->emptyCache = FALSE; - - return 1; -} - - -void GLAPIENTRY -gluTessVertex( GLUtesselator *tess, GLdouble coords[3], void *data ) -{ - int i, tooLarge = FALSE; - GLdouble x, clamped[3]; - - RequireState( tess, T_IN_CONTOUR ); - - if( tess->emptyCache ) { - if ( !EmptyCache( tess ) ) { - CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY ); - return; - } - tess->lastEdge = NULL; - } - for( i = 0; i < 3; ++i ) { - x = coords[i]; - if( x < - GLU_TESS_MAX_COORD ) { - x = - GLU_TESS_MAX_COORD; - tooLarge = TRUE; - } - if( x > GLU_TESS_MAX_COORD ) { - x = GLU_TESS_MAX_COORD; - tooLarge = TRUE; - } - clamped[i] = x; - } - if( tooLarge ) { - CALL_ERROR_OR_ERROR_DATA( GLU_TESS_COORD_TOO_LARGE ); - } - - if( tess->mesh == NULL ) { - if( tess->cacheCount < TESS_MAX_CACHE ) { - CacheVertex( tess, clamped, data ); - return; - } - if ( !EmptyCache( tess ) ) { - CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY ); - return; - } - } - if ( !AddVertex( tess, clamped, data ) ) { - CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY ); - } -} - - -void GLAPIENTRY -gluTessBeginPolygon( GLUtesselator *tess, void *data ) -{ - RequireState( tess, T_DORMANT ); - - tess->state = T_IN_POLYGON; - tess->cacheCount = 0; - tess->emptyCache = FALSE; - tess->mesh = NULL; - - tess->polygonData= data; -} - - -void GLAPIENTRY -gluTessBeginContour( GLUtesselator *tess ) -{ - RequireState( tess, T_IN_POLYGON ); - - tess->state = T_IN_CONTOUR; - tess->lastEdge = NULL; - if( tess->cacheCount > 0 ) { - /* Just set a flag so we don't get confused by empty contours - * -- these can be generated accidentally with the obsolete - * NextContour() interface. - */ - tess->emptyCache = TRUE; - } -} - - -void GLAPIENTRY -gluTessEndContour( GLUtesselator *tess ) -{ - RequireState( tess, T_IN_CONTOUR ); - tess->state = T_IN_POLYGON; -} - -void GLAPIENTRY -gluTessEndPolygon( GLUtesselator *tess ) -{ - GLUmesh *mesh; - - if (setjmp(tess->env) != 0) { - /* come back here if out of memory */ - CALL_ERROR_OR_ERROR_DATA( GLU_OUT_OF_MEMORY ); - return; - } - - RequireState( tess, T_IN_POLYGON ); - tess->state = T_DORMANT; - - if( tess->mesh == NULL ) { - if( ! tess->flagBoundary && tess->callMesh == &noMesh ) { - - /* Try some special code to make the easy cases go quickly - * (eg. convex polygons). This code does NOT handle multiple contours, - * intersections, edge flags, and of course it does not generate - * an explicit mesh either. - */ - if( __gl_renderCache( tess )) { - tess->polygonData= NULL; - return; - } - } - if ( !EmptyCache( tess ) ) longjmp(tess->env,1); /* could've used a label*/ - } - - /* Determine the polygon normal and project vertices onto the plane - * of the polygon. - */ - __gl_projectPolygon( tess ); - - /* __gl_computeInterior( tess ) computes the planar arrangement specified - * by the given contours, and further subdivides this arrangement - * into regions. Each region is marked "inside" if it belongs - * to the polygon, according to the rule given by tess->windingRule. - * Each interior region is guaranteed be monotone. - */ - if ( !__gl_computeInterior( tess ) ) { - longjmp(tess->env,1); /* could've used a label */ - } - - mesh = tess->mesh; - if( ! tess->fatalError ) { - int rc = 1; - - /* If the user wants only the boundary contours, we throw away all edges - * except those which separate the interior from the exterior. - * Otherwise we tessellate all the regions marked "inside". - */ - if( tess->boundaryOnly ) { - rc = __gl_meshSetWindingNumber( mesh, 1, TRUE ); - } else { - rc = __gl_meshTessellateInterior( mesh ); - } - if (rc == 0) longjmp(tess->env,1); /* could've used a label */ - - __gl_meshCheckMesh( mesh ); - - if( tess->callBegin != &noBegin || tess->callEnd != &noEnd - || tess->callVertex != &noVertex || tess->callEdgeFlag != &noEdgeFlag - || tess->callBeginData != &__gl_noBeginData - || tess->callEndData != &__gl_noEndData - || tess->callVertexData != &__gl_noVertexData - || tess->callEdgeFlagData != &__gl_noEdgeFlagData ) - { - if( tess->boundaryOnly ) { - __gl_renderBoundary( tess, mesh ); /* output boundary contours */ - } else { - __gl_renderMesh( tess, mesh ); /* output strips and fans */ - } - } - if( tess->callMesh != &noMesh ) { - - /* Throw away the exterior faces, so that all faces are interior. - * This way the user doesn't have to check the "inside" flag, - * and we don't need to even reveal its existence. It also leaves - * the freedom for an implementation to not generate the exterior - * faces in the first place. - */ - __gl_meshDiscardExterior( mesh ); - (*tess->callMesh)( mesh ); /* user wants the mesh itself */ - tess->mesh = NULL; - tess->polygonData= NULL; - return; - } - } - __gl_meshDeleteMesh( mesh ); - tess->polygonData= NULL; - tess->mesh = NULL; -} - - -/*XXXblythe unused function*/ -#if 0 -void GLAPIENTRY -gluDeleteMesh( GLUmesh *mesh ) -{ - __gl_meshDeleteMesh( mesh ); -} -#endif - - - -/*******************************************************/ - -/* Obsolete calls -- for backward compatibility */ - -void GLAPIENTRY -gluBeginPolygon( GLUtesselator *tess ) -{ - gluTessBeginPolygon( tess, NULL ); - gluTessBeginContour( tess ); -} - - -/*ARGSUSED*/ -void GLAPIENTRY -gluNextContour( GLUtesselator *tess, GLenum type ) -{ - gluTessEndContour( tess ); - gluTessBeginContour( tess ); -} - - -void GLAPIENTRY -gluEndPolygon( GLUtesselator *tess ) -{ - gluTessEndContour( tess ); - gluTessEndPolygon( tess ); -} diff --git a/src/glu/sgi/libtess/tess.h b/src/glu/sgi/libtess/tess.h deleted file mode 100644 index 16249608814..00000000000 --- a/src/glu/sgi/libtess/tess.h +++ /dev/null @@ -1,165 +0,0 @@ -/* - * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008) - * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved. - * - * Permission is hereby granted, free of charge, to any person obtaining a - * copy of this software and associated documentation files (the "Software"), - * to deal in the Software without restriction, including without limitation - * the rights to use, copy, modify, merge, publish, distribute, sublicense, - * and/or sell copies of the Software, and to permit persons to whom the - * Software is furnished to do so, subject to the following conditions: - * - * The above copyright notice including the dates of first publication and - * either this permission notice or a reference to - * http://oss.sgi.com/projects/FreeB/ - * shall be included in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS - * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL - * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, - * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF - * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - * - * Except as contained in this notice, the name of Silicon Graphics, Inc. - * shall not be used in advertising or otherwise to promote the sale, use or - * other dealings in this Software without prior written authorization from - * Silicon Graphics, Inc. - */ -/* -** Author: Eric Veach, July 1994. -** -*/ - -#ifndef __tess_h_ -#define __tess_h_ - -#include <GL/glu.h> -#include <setjmp.h> -#include "mesh.h" -#include "dict.h" -#include "priorityq.h" - -/* The begin/end calls must be properly nested. We keep track of - * the current state to enforce the ordering. - */ -enum TessState { T_DORMANT, T_IN_POLYGON, T_IN_CONTOUR }; - -/* We cache vertex data for single-contour polygons so that we can - * try a quick-and-dirty decomposition first. - */ -#define TESS_MAX_CACHE 100 - -typedef struct CachedVertex { - GLdouble coords[3]; - void *data; -} CachedVertex; - -struct GLUtesselator { - - /*** state needed for collecting the input data ***/ - - enum TessState state; /* what begin/end calls have we seen? */ - - GLUhalfEdge *lastEdge; /* lastEdge->Org is the most recent vertex */ - GLUmesh *mesh; /* stores the input contours, and eventually - the tessellation itself */ - - void (GLAPIENTRY *callError)( GLenum errnum ); - - /*** state needed for projecting onto the sweep plane ***/ - - GLdouble normal[3]; /* user-specified normal (if provided) */ - GLdouble sUnit[3]; /* unit vector in s-direction (debugging) */ - GLdouble tUnit[3]; /* unit vector in t-direction (debugging) */ - - /*** state needed for the line sweep ***/ - - GLdouble relTolerance; /* tolerance for merging features */ - GLenum windingRule; /* rule for determining polygon interior */ - GLboolean fatalError; /* fatal error: needed combine callback */ - - Dict *dict; /* edge dictionary for sweep line */ - PriorityQ *pq; /* priority queue of vertex events */ - GLUvertex *event; /* current sweep event being processed */ - - void (GLAPIENTRY *callCombine)( GLdouble coords[3], void *data[4], - GLfloat weight[4], void **outData ); - - /*** state needed for rendering callbacks (see render.c) ***/ - - GLboolean flagBoundary; /* mark boundary edges (use EdgeFlag) */ - GLboolean boundaryOnly; /* Extract contours, not triangles */ - GLUface *lonelyTriList; - /* list of triangles which could not be rendered as strips or fans */ - - void (GLAPIENTRY *callBegin)( GLenum type ); - void (GLAPIENTRY *callEdgeFlag)( GLboolean boundaryEdge ); - void (GLAPIENTRY *callVertex)( void *data ); - void (GLAPIENTRY *callEnd)( void ); - void (GLAPIENTRY *callMesh)( GLUmesh *mesh ); - - - /*** state needed to cache single-contour polygons for renderCache() */ - - GLboolean emptyCache; /* empty cache on next vertex() call */ - int cacheCount; /* number of cached vertices */ - CachedVertex cache[TESS_MAX_CACHE]; /* the vertex data */ - - /*** rendering callbacks that also pass polygon data ***/ - void (GLAPIENTRY *callBeginData)( GLenum type, void *polygonData ); - void (GLAPIENTRY *callEdgeFlagData)( GLboolean boundaryEdge, - void *polygonData ); - void (GLAPIENTRY *callVertexData)( void *data, void *polygonData ); - void (GLAPIENTRY *callEndData)( void *polygonData ); - void (GLAPIENTRY *callErrorData)( GLenum errnum, void *polygonData ); - void (GLAPIENTRY *callCombineData)( GLdouble coords[3], void *data[4], - GLfloat weight[4], void **outData, - void *polygonData ); - - jmp_buf env; /* place to jump to when memAllocs fail */ - - void *polygonData; /* client data for current polygon */ -}; - -void GLAPIENTRY __gl_noBeginData( GLenum type, void *polygonData ); -void GLAPIENTRY __gl_noEdgeFlagData( GLboolean boundaryEdge, void *polygonData ); -void GLAPIENTRY __gl_noVertexData( void *data, void *polygonData ); -void GLAPIENTRY __gl_noEndData( void *polygonData ); -void GLAPIENTRY __gl_noErrorData( GLenum errnum, void *polygonData ); -void GLAPIENTRY __gl_noCombineData( GLdouble coords[3], void *data[4], - GLfloat weight[4], void **outData, - void *polygonData ); - -#define CALL_BEGIN_OR_BEGIN_DATA(a) \ - if (tess->callBeginData != &__gl_noBeginData) \ - (*tess->callBeginData)((a),tess->polygonData); \ - else (*tess->callBegin)((a)); - -#define CALL_VERTEX_OR_VERTEX_DATA(a) \ - if (tess->callVertexData != &__gl_noVertexData) \ - (*tess->callVertexData)((a),tess->polygonData); \ - else (*tess->callVertex)((a)); - -#define CALL_EDGE_FLAG_OR_EDGE_FLAG_DATA(a) \ - if (tess->callEdgeFlagData != &__gl_noEdgeFlagData) \ - (*tess->callEdgeFlagData)((a),tess->polygonData); \ - else (*tess->callEdgeFlag)((a)); - -#define CALL_END_OR_END_DATA() \ - if (tess->callEndData != &__gl_noEndData) \ - (*tess->callEndData)(tess->polygonData); \ - else (*tess->callEnd)(); - -#define CALL_COMBINE_OR_COMBINE_DATA(a,b,c,d) \ - if (tess->callCombineData != &__gl_noCombineData) \ - (*tess->callCombineData)((a),(b),(c),(d),tess->polygonData); \ - else (*tess->callCombine)((a),(b),(c),(d)); - -#define CALL_ERROR_OR_ERROR_DATA(a) \ - if (tess->callErrorData != &__gl_noErrorData) \ - (*tess->callErrorData)((a),tess->polygonData); \ - else (*tess->callError)((a)); - -#endif diff --git a/src/glu/sgi/libtess/tessmono.c b/src/glu/sgi/libtess/tessmono.c deleted file mode 100644 index 4d084400594..00000000000 --- a/src/glu/sgi/libtess/tessmono.c +++ /dev/null @@ -1,201 +0,0 @@ -/* - * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008) - * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved. - * - * Permission is hereby granted, free of charge, to any person obtaining a - * copy of this software and associated documentation files (the "Software"), - * to deal in the Software without restriction, including without limitation - * the rights to use, copy, modify, merge, publish, distribute, sublicense, - * and/or sell copies of the Software, and to permit persons to whom the - * Software is furnished to do so, subject to the following conditions: - * - * The above copyright notice including the dates of first publication and - * either this permission notice or a reference to - * http://oss.sgi.com/projects/FreeB/ - * shall be included in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS - * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL - * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, - * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF - * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - * - * Except as contained in this notice, the name of Silicon Graphics, Inc. - * shall not be used in advertising or otherwise to promote the sale, use or - * other dealings in this Software without prior written authorization from - * Silicon Graphics, Inc. - */ -/* -** Author: Eric Veach, July 1994. -** -*/ - -#include "gluos.h" -#include <stdlib.h> -#include "geom.h" -#include "mesh.h" -#include "tessmono.h" -#include <assert.h> - -#define AddWinding(eDst,eSrc) (eDst->winding += eSrc->winding, \ - eDst->Sym->winding += eSrc->Sym->winding) - -/* __gl_meshTessellateMonoRegion( face ) tessellates a monotone region - * (what else would it do??) The region must consist of a single - * loop of half-edges (see mesh.h) oriented CCW. "Monotone" in this - * case means that any vertical line intersects the interior of the - * region in a single interval. - * - * Tessellation consists of adding interior edges (actually pairs of - * half-edges), to split the region into non-overlapping triangles. - * - * The basic idea is explained in Preparata and Shamos (which I don''t - * have handy right now), although their implementation is more - * complicated than this one. The are two edge chains, an upper chain - * and a lower chain. We process all vertices from both chains in order, - * from right to left. - * - * The algorithm ensures that the following invariant holds after each - * vertex is processed: the untessellated region consists of two - * chains, where one chain (say the upper) is a single edge, and - * the other chain is concave. The left vertex of the single edge - * is always to the left of all vertices in the concave chain. - * - * Each step consists of adding the rightmost unprocessed vertex to one - * of the two chains, and forming a fan of triangles from the rightmost - * of two chain endpoints. Determining whether we can add each triangle - * to the fan is a simple orientation test. By making the fan as large - * as possible, we restore the invariant (check it yourself). - */ -int __gl_meshTessellateMonoRegion( GLUface *face ) -{ - GLUhalfEdge *up, *lo; - - /* All edges are oriented CCW around the boundary of the region. - * First, find the half-edge whose origin vertex is rightmost. - * Since the sweep goes from left to right, face->anEdge should - * be close to the edge we want. - */ - up = face->anEdge; - assert( up->Lnext != up && up->Lnext->Lnext != up ); - - for( ; VertLeq( up->Dst, up->Org ); up = up->Lprev ) - ; - for( ; VertLeq( up->Org, up->Dst ); up = up->Lnext ) - ; - lo = up->Lprev; - - while( up->Lnext != lo ) { - if( VertLeq( up->Dst, lo->Org )) { - /* up->Dst is on the left. It is safe to form triangles from lo->Org. - * The EdgeGoesLeft test guarantees progress even when some triangles - * are CW, given that the upper and lower chains are truly monotone. - */ - while( lo->Lnext != up && (EdgeGoesLeft( lo->Lnext ) - || EdgeSign( lo->Org, lo->Dst, lo->Lnext->Dst ) <= 0 )) { - GLUhalfEdge *tempHalfEdge= __gl_meshConnect( lo->Lnext, lo ); - if (tempHalfEdge == NULL) return 0; - lo = tempHalfEdge->Sym; - } - lo = lo->Lprev; - } else { - /* lo->Org is on the left. We can make CCW triangles from up->Dst. */ - while( lo->Lnext != up && (EdgeGoesRight( up->Lprev ) - || EdgeSign( up->Dst, up->Org, up->Lprev->Org ) >= 0 )) { - GLUhalfEdge *tempHalfEdge= __gl_meshConnect( up, up->Lprev ); - if (tempHalfEdge == NULL) return 0; - up = tempHalfEdge->Sym; - } - up = up->Lnext; - } - } - - /* Now lo->Org == up->Dst == the leftmost vertex. The remaining region - * can be tessellated in a fan from this leftmost vertex. - */ - assert( lo->Lnext != up ); - while( lo->Lnext->Lnext != up ) { - GLUhalfEdge *tempHalfEdge= __gl_meshConnect( lo->Lnext, lo ); - if (tempHalfEdge == NULL) return 0; - lo = tempHalfEdge->Sym; - } - - return 1; -} - - -/* __gl_meshTessellateInterior( mesh ) tessellates each region of - * the mesh which is marked "inside" the polygon. Each such region - * must be monotone. - */ -int __gl_meshTessellateInterior( GLUmesh *mesh ) -{ - GLUface *f, *next; - - /*LINTED*/ - for( f = mesh->fHead.next; f != &mesh->fHead; f = next ) { - /* Make sure we don''t try to tessellate the new triangles. */ - next = f->next; - if( f->inside ) { - if ( !__gl_meshTessellateMonoRegion( f ) ) return 0; - } - } - - return 1; -} - - -/* __gl_meshDiscardExterior( mesh ) zaps (ie. sets to NULL) all faces - * which are not marked "inside" the polygon. Since further mesh operations - * on NULL faces are not allowed, the main purpose is to clean up the - * mesh so that exterior loops are not represented in the data structure. - */ -void __gl_meshDiscardExterior( GLUmesh *mesh ) -{ - GLUface *f, *next; - - /*LINTED*/ - for( f = mesh->fHead.next; f != &mesh->fHead; f = next ) { - /* Since f will be destroyed, save its next pointer. */ - next = f->next; - if( ! f->inside ) { - __gl_meshZapFace( f ); - } - } -} - -#define MARKED_FOR_DELETION 0x7fffffff - -/* __gl_meshSetWindingNumber( mesh, value, keepOnlyBoundary ) resets the - * winding numbers on all edges so that regions marked "inside" the - * polygon have a winding number of "value", and regions outside - * have a winding number of 0. - * - * If keepOnlyBoundary is TRUE, it also deletes all edges which do not - * separate an interior region from an exterior one. - */ -int __gl_meshSetWindingNumber( GLUmesh *mesh, int value, - GLboolean keepOnlyBoundary ) -{ - GLUhalfEdge *e, *eNext; - - for( e = mesh->eHead.next; e != &mesh->eHead; e = eNext ) { - eNext = e->next; - if( e->Rface->inside != e->Lface->inside ) { - - /* This is a boundary edge (one side is interior, one is exterior). */ - e->winding = (e->Lface->inside) ? value : -value; - } else { - - /* Both regions are interior, or both are exterior. */ - if( ! keepOnlyBoundary ) { - e->winding = 0; - } else { - if ( !__gl_meshDelete( e ) ) return 0; - } - } - } - return 1; -} diff --git a/src/glu/sgi/libtess/tessmono.h b/src/glu/sgi/libtess/tessmono.h deleted file mode 100644 index 8ee1b2fe341..00000000000 --- a/src/glu/sgi/libtess/tessmono.h +++ /dev/null @@ -1,71 +0,0 @@ -/* - * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008) - * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved. - * - * Permission is hereby granted, free of charge, to any person obtaining a - * copy of this software and associated documentation files (the "Software"), - * to deal in the Software without restriction, including without limitation - * the rights to use, copy, modify, merge, publish, distribute, sublicense, - * and/or sell copies of the Software, and to permit persons to whom the - * Software is furnished to do so, subject to the following conditions: - * - * The above copyright notice including the dates of first publication and - * either this permission notice or a reference to - * http://oss.sgi.com/projects/FreeB/ - * shall be included in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS - * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL - * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, - * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF - * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - * - * Except as contained in this notice, the name of Silicon Graphics, Inc. - * shall not be used in advertising or otherwise to promote the sale, use or - * other dealings in this Software without prior written authorization from - * Silicon Graphics, Inc. - */ -/* -** Author: Eric Veach, July 1994. -** -*/ - -#ifndef __tessmono_h_ -#define __tessmono_h_ - -/* __gl_meshTessellateMonoRegion( face ) tessellates a monotone region - * (what else would it do??) The region must consist of a single - * loop of half-edges (see mesh.h) oriented CCW. "Monotone" in this - * case means that any vertical line intersects the interior of the - * region in a single interval. - * - * Tessellation consists of adding interior edges (actually pairs of - * half-edges), to split the region into non-overlapping triangles. - * - * __gl_meshTessellateInterior( mesh ) tessellates each region of - * the mesh which is marked "inside" the polygon. Each such region - * must be monotone. - * - * __gl_meshDiscardExterior( mesh ) zaps (ie. sets to NULL) all faces - * which are not marked "inside" the polygon. Since further mesh operations - * on NULL faces are not allowed, the main purpose is to clean up the - * mesh so that exterior loops are not represented in the data structure. - * - * __gl_meshSetWindingNumber( mesh, value, keepOnlyBoundary ) resets the - * winding numbers on all edges so that regions marked "inside" the - * polygon have a winding number of "value", and regions outside - * have a winding number of 0. - * - * If keepOnlyBoundary is TRUE, it also deletes all edges which do not - * separate an interior region from an exterior one. - */ - -int __gl_meshTessellateMonoRegion( GLUface *face ); -int __gl_meshTessellateInterior( GLUmesh *mesh ); -void __gl_meshDiscardExterior( GLUmesh *mesh ); -int __gl_meshSetWindingNumber( GLUmesh *mesh, int value, - GLboolean keepOnlyBoundary ); - -#endif |