diff options
Diffstat (limited to 'mesalib/src/glu/sgi/libtess/sweep.c')
| -rw-r--r-- | mesalib/src/glu/sgi/libtess/sweep.c | 1357 |
1 files changed, 1357 insertions, 0 deletions
diff --git a/mesalib/src/glu/sgi/libtess/sweep.c b/mesalib/src/glu/sgi/libtess/sweep.c new file mode 100644 index 000000000..744be6b47 --- /dev/null +++ b/mesalib/src/glu/sgi/libtess/sweep.c @@ -0,0 +1,1357 @@ +/* + * 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" + +#define TRUE 1 +#define FALSE 0 + +#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; +} |