11cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger/* 21cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger** $Header: /cvs/projects/ogl-sample/main/gfx/lib/glu/libtess/alg-outline,v 1.1 2000/04/26 05:53:59 ljp Exp $ 31cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger*/ 41cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 51cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerThis is only a very brief overview. There is quite a bit of 61cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergeradditional documentation in the source code itself. 71cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 81cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 91cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerGoals of robust tesselation 101cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger--------------------------- 111cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 121cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerThe tesselation algorithm is fundamentally a 2D algorithm. We 131cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerinitially project all data into a plane; our goal is to robustly 141cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergertesselate the projected data. The same topological tesselation is 151cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerthen applied to the input data. 161cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 171cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerTopologically, the output should always be a tesselation. If the 181cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerinput is even slightly non-planar, then some triangles will 191cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergernecessarily be back-facing when viewed from some angles, but the goal 201cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergeris to minimize this effect. 211cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 221cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerThe algorithm needs some capability of cleaning up the input data as 231cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerwell as the numerical errors in its own calculations. One way to do 241cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerthis is to specify a tolerance as defined above, and clean up the 251cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerinput and output during the line sweep process. At the very least, 261cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerthe algorithm must handle coincident vertices, vertices incident to an 271cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergeredge, and coincident edges. 281cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 291cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 301cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerPhases of the algorithm 311cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger----------------------- 321cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 331cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger1. Find the polygon normal N. 341cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger2. Project the vertex data onto a plane. It does not need to be 351cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger perpendicular to the normal, eg. we can project onto the plane 361cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger perpendicular to the coordinate axis whose dot product with N 371cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger is largest. 381cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger3. Using a line-sweep algorithm, partition the plane into x-monotone 391cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger regions. Any vertical line intersects an x-monotone region in 401cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger at most one interval. 411cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger4. Triangulate the x-monotone regions. 421cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger5. Group the triangles into strips and fans. 431cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 441cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 451cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerFinding the normal vector 461cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger------------------------- 471cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 481cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerA common way to find a polygon normal is to compute the signed area 491cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerwhen the polygon is projected along the three coordinate axes. We 501cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergercan't do this, since contours can have zero area without being 511cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerdegenerate (eg. a bowtie). 521cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 531cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerWe fit a plane to the vertex data, ignoring how they are connected 541cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerinto contours. Ideally this would be a least-squares fit; however for 551cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerour purpose the accuracy of the normal is not important. Instead we 561cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerfind three vertices which are widely separated, and compute the normal 571cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerto the triangle they form. The vertices are chosen so that the 581cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergertriangle has an area at least 1/sqrt(3) times the largest area of any 591cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergertriangle formed using the input vertices. 601cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 611cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerThe contours do affect the orientation of the normal; after computing 621cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerthe normal, we check that the sum of the signed contour areas is 631cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergernon-negative, and reverse the normal if necessary. 641cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 651cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 661cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerProjecting the vertices 671cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger----------------------- 681cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 691cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerWe project the vertices onto a plane perpendicular to one of the three 701cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergercoordinate axes. This helps numerical accuracy by removing a 711cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergertransformation step between the original input data and the data 721cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerprocessed by the algorithm. The projection also compresses the input 731cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerdata; the 2D distance between vertices after projection may be smaller 741cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerthan the original 2D distance. However by choosing the coordinate 751cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergeraxis whose dot product with the normal is greatest, the compression 761cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerfactor is at most 1/sqrt(3). 771cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 781cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerEven though the *accuracy* of the normal is not that important (since 791cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerwe are projecting perpendicular to a coordinate axis anyway), the 801cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger*robustness* of the computation is important. For example, if there 811cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerare many vertices which lie almost along a line, and one vertex V 821cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerwhich is well-separated from the line, then our normal computation 831cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergershould involve V otherwise the results will be garbage. 841cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 851cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerThe advantage of projecting perpendicular to the polygon normal is 861cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerthat computed intersection points will be as close as possible to 871cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergertheir ideal locations. To get this behavior, define TRUE_PROJECT. 881cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 891cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 901cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerThe Line Sweep 911cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger-------------- 921cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 931cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerThere are three data structures: the mesh, the event queue, and the 941cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergeredge dictionary. 951cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 961cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerThe mesh is a "quad-edge" data structure which records the topology of 971cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerthe current decomposition; for details see the include file "mesh.h". 981cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 991cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerThe event queue simply holds all vertices (both original and computed 1001cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerones), organized so that we can quickly extract the vertex with the 1011cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerminimum x-coord (and among those, the one with the minimum y-coord). 1021cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1031cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerThe edge dictionary describes the current intersection of the sweep 1041cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerline with the regions of the polygon. This is just an ordering of the 1051cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergeredges which intersect the sweep line, sorted by their current order of 1061cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerintersection. For each pair of edges, we store some information about 1071cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerthe monotone region between them -- these are call "active regions" 1081cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger(since they are crossed by the current sweep line). 1091cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1101cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerThe basic algorithm is to sweep from left to right, processing each 1111cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergervertex. The processed portion of the mesh (left of the sweep line) is 1121cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergera planar decomposition. As we cross each vertex, we update the mesh 1131cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerand the edge dictionary, then we check any newly adjacent pairs of 1141cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergeredges to see if they intersect. 1151cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1161cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerA vertex can have any number of edges. Vertices with many edges can 1171cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerbe created as vertices are merged and intersection points are 1181cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergercomputed. For unprocessed vertices (right of the sweep line), these 1191cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergeredges are in no particular order around the vertex; for processed 1201cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergervertices, the topological ordering should match the geometric ordering. 1211cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1221cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerThe vertex processing happens in two phases: first we process are the 1231cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerleft-going edges (all these edges are currently in the edge 1241cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerdictionary). This involves: 1251cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1261cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger - deleting the left-going edges from the dictionary; 1271cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger - relinking the mesh if necessary, so that the order of these edges around 1281cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger the event vertex matches the order in the dictionary; 1291cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger - marking any terminated regions (regions which lie between two left-going 1301cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger edges) as either "inside" or "outside" according to their winding number. 1311cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1321cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerWhen there are no left-going edges, and the event vertex is in an 1331cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger"interior" region, we need to add an edge (to split the region into 1341cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergermonotone pieces). To do this we simply join the event vertex to the 1351cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerrightmost left endpoint of the upper or lower edge of the containing 1361cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerregion. 1371cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1381cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerThen we process the right-going edges. This involves: 1391cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1401cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger - inserting the edges in the edge dictionary; 1411cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger - computing the winding number of any newly created active regions. 1421cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger We can compute this incrementally using the winding of each edge 1431cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger that we cross as we walk through the dictionary. 1441cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger - relinking the mesh if necessary, so that the order of these edges around 1451cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger the event vertex matches the order in the dictionary; 1461cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger - checking any newly adjacent edges for intersection and/or merging. 1471cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1481cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerIf there are no right-going edges, again we need to add one to split 1491cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerthe containing region into monotone pieces. In our case it is most 1501cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerconvenient to add an edge to the leftmost right endpoint of either 1511cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergercontaining edge; however we may need to change this later (see the 1521cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergercode for details). 1531cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1541cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1551cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerInvariants 1561cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger---------- 1571cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1581cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerThese are the most important invariants maintained during the sweep. 1591cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerWe define a function VertLeq(v1,v2) which defines the order in which 1601cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergervertices cross the sweep line, and a function EdgeLeq(e1,e2; loc) 1611cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerwhich says whether e1 is below e2 at the sweep event location "loc". 1621cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerThis function is defined only at sweep event locations which lie 1631cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerbetween the rightmost left endpoint of {e1,e2}, and the leftmost right 1641cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerendpoint of {e1,e2}. 1651cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1661cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerInvariants for the Edge Dictionary. 1671cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1681cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger - Each pair of adjacent edges e2=Succ(e1) satisfies EdgeLeq(e1,e2) 1691cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger at any valid location of the sweep event. 1701cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger - If EdgeLeq(e2,e1) as well (at any valid sweep event), then e1 and e2 1711cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger share a common endpoint. 1721cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger - For each e in the dictionary, e->Dst has been processed but not e->Org. 1731cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger - Each edge e satisfies VertLeq(e->Dst,event) && VertLeq(event,e->Org) 1741cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger where "event" is the current sweep line event. 1751cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger - No edge e has zero length. 1761cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger - No two edges have identical left and right endpoints. 1771cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1781cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerInvariants for the Mesh (the processed portion). 1791cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1801cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger - The portion of the mesh left of the sweep line is a planar graph, 1811cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger ie. there is *some* way to embed it in the plane. 1821cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger - No processed edge has zero length. 1831cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger - No two processed vertices have identical coordinates. 1841cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger - Each "inside" region is monotone, ie. can be broken into two chains 1851cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger of monotonically increasing vertices according to VertLeq(v1,v2) 1861cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger - a non-invariant: these chains may intersect (slightly) due to 1871cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger numerical errors, but this does not affect the algorithm's operation. 1881cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1891cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerInvariants for the Sweep. 1901cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1911cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger - If a vertex has any left-going edges, then these must be in the edge 1921cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger dictionary at the time the vertex is processed. 1931cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger - If an edge is marked "fixUpperEdge" (it is a temporary edge introduced 1941cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger by ConnectRightVertex), then it is the only right-going edge from 1951cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger its associated vertex. (This says that these edges exist only 1961cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger when it is necessary.) 1971cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1981cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1991cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerRobustness 2001cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger---------- 2011cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 2021cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerThe key to the robustness of the algorithm is maintaining the 2031cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerinvariants above, especially the correct ordering of the edge 2041cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerdictionary. We achieve this by: 2051cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 2061cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 1. Writing the numerical computations for maximum precision rather 2071cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger than maximum speed. 2081cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 2091cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 2. Making no assumptions at all about the results of the edge 2101cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger intersection calculations -- for sufficiently degenerate inputs, 2111cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger the computed location is not much better than a random number. 2121cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 2131cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 3. When numerical errors violate the invariants, restore them 2141cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger by making *topological* changes when necessary (ie. relinking 2151cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger the mesh structure). 2161cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 2171cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 2181cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerTriangulation and Grouping 2191cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger-------------------------- 2201cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 2211cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerWe finish the line sweep before doing any triangulation. This is 2221cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerbecause even after a monotone region is complete, there can be further 2231cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerchanges to its vertex data because of further vertex merging. 2241cab2921ab279367f8206cdadc9259d12e603548Derek Sollenberger 2251cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerAfter triangulating all monotone regions, we want to group the 2261cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergertriangles into fans and strips. We do this using a greedy approach. 2271cab2921ab279367f8206cdadc9259d12e603548Derek SollenbergerThe triangulation itself is not optimized to reduce the number of 2281cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergerprimitives; we just try to get a reasonable decomposition of the 2291cab2921ab279367f8206cdadc9259d12e603548Derek Sollenbergercomputed triangulation. 230