/*
** SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008)
** Copyright (C) [dates of first publication] 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 <assert.h>
#include <stddef.h>
#include <setjmp.h>        /* longjmp */

#include "mesh.h"
#include "geom.h"
#include "tess.h"
#include "dict.h"
#include "priorityq.h"
#include "bucketalloc.h"
#include "sweep.h"

#define TRUE 1
#define FALSE 0

#ifdef FOR_TRITE_TEST_PROGRAM
extern void DebugEvent( TESStesselator *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.)
*/

#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( TESStesselator *tess, TESSvertex *vEvent );
static void WalkDirtyRegions( TESStesselator *tess, ActiveRegion *regUp );
static int CheckForRightSplice( TESStesselator *tess, ActiveRegion *regUp );

static int EdgeLeq( TESStesselator *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).
*/
{
    TESSvertex *event = tess->event;
    TESShalfEdge *e1, *e2;
    TESSreal 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( TESStesselator *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).
        */
        if( reg->eUp->winding != 0 ) return;
    }
    reg->eUp->activeRegion = NULL;
    dictDelete( tess->dict, reg->nodeUp );
    bucketFree( tess->regionPool, reg );
}


static int FixUpperEdge( TESStesselator *tess, ActiveRegion *reg, TESShalfEdge *newEdge )
/*
* Replace an upper edge which needs fixing (see ConnectRightVertex).
*/
{
    if(! reg->fixUpperEdge ) return 0;
    if ( !tessMeshDelete( tess->mesh, reg->eUp ) ) return 0;
    reg->fixUpperEdge = FALSE;
    reg->eUp = newEdge;
    newEdge->activeRegion = reg;

    return 1;
}

static ActiveRegion *TopLeftRegion( TESStesselator *tess, ActiveRegion *reg )
{
    TESSvertex *org = reg->eUp->Org;
    TESShalfEdge *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 = tessMeshConnect( tess->mesh, RegionBelow(reg)->eUp->Sym, reg->eUp->Lnext );
        if (e == NULL) return NULL;
        if ( !FixUpperEdge( tess, reg, e ) ) return NULL;
        reg = RegionAbove( reg );
    }
    return reg;
}

static ActiveRegion *TopRightRegion( ActiveRegion *reg )
{
    TESSvertex *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( TESStesselator *tess,
                                    ActiveRegion *regAbove,
                                    TESShalfEdge *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 *)bucketAlloc( tess->regionPool );
    if (regNew == NULL) longjmp(tess->env,1);

    regNew->eUp = eNewUp;
    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 int IsWindingInside( TESStesselator *tess, int n )
{
    switch( tess->windingRule ) {
        case TESS_WINDING_ODD:
            return (n & 1);
        case TESS_WINDING_NONZERO:
            return (n != 0);
        case TESS_WINDING_POSITIVE:
            return (n > 0);
        case TESS_WINDING_NEGATIVE:
            return (n < 0);
        case TESS_WINDING_ABS_GEQ_TWO:
            return (n >= 2) || (n <= -2);
    }
    /*LINTED*/
    //assert( FALSE );
    /*NOTREACHED*/

    return( FALSE );
}


static void ComputeWinding( TESStesselator *tess, ActiveRegion *reg )
{
    reg->windingNumber = RegionAbove(reg)->windingNumber + reg->eUp->winding;
    reg->inside = IsWindingInside( tess, reg->windingNumber );
}


static void FinishRegion( TESStesselator *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).
*/
{
    TESShalfEdge *e = reg->eUp;
    TESSface *f = e->Lface;

    f->inside = reg->inside;
    f->anEdge = e;   /* optimization for tessMeshTessellateMonoRegion() */
    DeleteRegion( tess, reg );
}


static TESShalfEdge *FinishLeftRegions( TESStesselator *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;
    TESShalfEdge *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 = tessMeshConnect( tess->mesh, ePrev->Lprev, e->Sym );
            if (e == NULL) longjmp(tess->env,1);
            if ( !FixUpperEdge( tess, reg, e ) ) longjmp(tess->env,1);
        }

        /* Relink edges so that ePrev->Onext == e */
        if( ePrev->Onext != e ) {
            if ( !tessMeshSplice( tess->mesh, e->Oprev, e ) ) longjmp(tess->env,1);
            if ( !tessMeshSplice( tess->mesh, ePrev, e ) ) longjmp(tess->env,1);
        }
        FinishRegion( tess, regPrev );    /* may change reg->eUp */
        ePrev = reg->eUp;
        regPrev = reg;
    }
    return ePrev;
}


static void AddRightEdges( TESStesselator *tess, ActiveRegion *regUp,
                          TESShalfEdge *eFirst, TESShalfEdge *eLast, TESShalfEdge *eTopLeft,
                          int 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;
    TESShalfEdge *e, *ePrev;
    int firstTime = TRUE;

    /* Insert the new right-going edges in the dictionary */
    e = eFirst;
    do {
        if(! VertLeq( e->Org, e->Dst )) return;
        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 ( !tessMeshSplice( tess->mesh, e->Oprev, e ) ) longjmp(tess->env,1);
            if ( !tessMeshSplice( tess->mesh, 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 tessComputeInterior).
        */
        regPrev->dirty = TRUE;
        if( ! firstTime && CheckForRightSplice( tess, regPrev )) {
            AddWinding( e, ePrev );
            DeleteRegion( tess, regPrev );
            if ( !tessMeshDelete( tess->mesh, ePrev ) ) longjmp(tess->env,1);
        }
        firstTime = FALSE;
        regPrev = reg;
        ePrev = e;
    }
    regPrev->dirty = TRUE;
    if(!( regPrev->windingNumber - e->winding == reg->windingNumber )) return;

    if( cleanUp ) {
        /* Check for intersections between newly adjacent edges. */
        WalkDirtyRegions( tess, regPrev );
    }
}


static void SpliceMergeVertices( TESStesselator *tess, TESShalfEdge *e1,
                                TESShalfEdge *e2 )
/*
* Two vertices with idential coordinates are combined into one.
* e1->Org is kept, while e2->Org is discarded.
*/
{
    if ( !tessMeshSplice( tess->mesh, e1, e2 ) ) longjmp(tess->env,1);
}

static void VertexWeights( TESSvertex *isect, TESSvertex *org, TESSvertex *dst,
                          TESSreal *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".
*/
{
    TESSreal t1 = VertL1dist( org, isect );
    TESSreal t2 = VertL1dist( dst, isect );

    weights[0] = (TESSreal)0.5 * t2 / (t1 + t2);
    weights[1] = (TESSreal)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( TESStesselator *tess, TESSvertex *isect,
                             TESSvertex *orgUp, TESSvertex *dstUp,
                             TESSvertex *orgLo, TESSvertex *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.
 */
{
    TESSreal weights[4];

    isect->coords[0] = isect->coords[1] = isect->coords[2] = 0;
    isect->idx = TESS_UNDEF;
    VertexWeights( isect, orgUp, dstUp, &weights[0] );
    VertexWeights( isect, orgLo, dstLo, &weights[2] );
}

static int CheckForRightSplice( TESStesselator *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);
    TESShalfEdge *eUp = regUp->eUp;
    TESShalfEdge *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 ( tessMeshSplitEdge( tess->mesh, eLo->Sym ) == NULL) longjmp(tess->env,1);
            if ( !tessMeshSplice( tess->mesh, 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 );
            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 (tessMeshSplitEdge( tess->mesh, eUp->Sym ) == NULL) longjmp(tess->env,1);
        if ( !tessMeshSplice( tess->mesh, eLo->Oprev, eUp ) ) longjmp(tess->env,1);
    }
    return TRUE;
}

static int CheckForLeftSplice( TESStesselator *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);
    TESShalfEdge *eUp = regUp->eUp;
    TESShalfEdge *eLo = regLo->eUp;
    TESShalfEdge *e;

    if( VertEq( eUp->Dst, eLo->Dst )) return FALSE;

    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 = tessMeshSplitEdge( tess->mesh, eUp );
        if (e == NULL) longjmp(tess->env,1);
        if ( !tessMeshSplice( tess->mesh, 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 = tessMeshSplitEdge( tess->mesh, eLo );
        if (e == NULL) longjmp(tess->env,1);
        if ( !tessMeshSplice( tess->mesh, eUp->Lnext, eLo->Sym ) ) longjmp(tess->env,1);
        e->Rface->inside = regUp->inside;
    }
    return TRUE;
}


static int CheckForIntersect( TESStesselator *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);
    TESShalfEdge *eUp = regUp->eUp;
    TESShalfEdge *eLo = regLo->eUp;
    TESSvertex *orgUp = eUp->Org;
    TESSvertex *orgLo = eLo->Org;
    TESSvertex *dstUp = eUp->Dst;
    TESSvertex *dstLo = eLo->Dst;
    TESSreal tMinUp, tMaxLo;
    TESSvertex isect, *orgMin;
    TESShalfEdge *e;

    if( VertEq( dstLo, dstUp )) return FALSE;
    if( EdgeSign( dstUp, tess->event, orgUp ) > 0 ) return FALSE;
    if( EdgeSign( dstLo, tess->event, orgLo ) < 0 ) return FALSE;
    if(!( orgUp != tess->event && orgLo != tess->event )) return FALSE;
    if(!( ! regUp->fixUpperEdge && ! regLo->fixUpperEdge )) return FALSE;

    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 );

    tesedgeIntersect( dstUp, orgUp, dstLo, orgLo, &isect );
    /* The following properties are guaranteed: */
    if(!( MIN( orgUp->t, dstUp->t ) <= isect.t )) return FALSE;
    if(!( isect.t <= MAX( orgLo->t, dstLo->t ))) return FALSE;
    if(!( MIN( dstLo->s, dstUp->s ) <= isect.s )) return FALSE;
    if(!( isect.s <= MAX( orgLo->s, orgUp->s ))) return FALSE;

    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 (tessMeshSplitEdge( tess->mesh, eUp->Sym ) == NULL) longjmp(tess->env,1);
            if ( !tessMeshSplice( tess->mesh, eLo->Sym, eUp ) ) longjmp(tess->env,1);
            regUp = TopLeftRegion( tess, 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 (tessMeshSplitEdge( tess->mesh, eLo->Sym ) == NULL) longjmp(tess->env,1);
            if ( !tessMeshSplice( tess->mesh, 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 (tessMeshSplitEdge( tess->mesh, 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 (tessMeshSplitEdge( tess->mesh, 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 (tessMeshSplitEdge( tess->mesh, eUp->Sym ) == NULL) longjmp(tess->env,1);
    if (tessMeshSplitEdge( tess->mesh, eLo->Sym ) == NULL) longjmp(tess->env,1);
    if ( !tessMeshSplice( tess->mesh, eLo->Oprev, eUp ) ) longjmp(tess->env,1);
    eUp->Org->s = isect.s;
    eUp->Org->t = isect.t;
    eUp->Org->pqHandle = pqInsert( &tess->alloc, tess->pq, eUp->Org );
    if (eUp->Org->pqHandle == INV_HANDLE) {
        pqDeletePriorityQ( &tess->alloc, tess->pq );
        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( TESStesselator *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);
    TESShalfEdge *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 ( !tessMeshDelete( tess->mesh, eLo ) ) longjmp(tess->env,1);
                    regLo = RegionBelow( regUp );
                    eLo = regLo->eUp;
                } else if( regUp->fixUpperEdge ) {
                    DeleteRegion( tess, regUp );
                    if ( !tessMeshDelete( tess->mesh, 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 ( !tessMeshDelete( tess->mesh, eUp ) ) longjmp(tess->env,1);
            regUp = RegionAbove( regLo );
        }
    }
}


static void ConnectRightVertex( TESStesselator *tess, ActiveRegion *regUp,
                               TESShalfEdge *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.
*/
{
    TESShalfEdge *eNew;
    TESShalfEdge *eTopLeft = eBottomLeft->Onext;
    ActiveRegion *regLo = RegionBelow(regUp);
    TESShalfEdge *eUp = regUp->eUp;
    TESShalfEdge *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 ( !tessMeshSplice( tess->mesh, eTopLeft->Oprev, eUp ) ) longjmp(tess->env,1);
        regUp = TopLeftRegion( tess, 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 ( !tessMeshSplice( tess->mesh, 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 = tessMeshConnect( tess->mesh, 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( TESStesselator *tess,
                                  ActiveRegion *regUp, TESSvertex *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.
*/
{
    TESShalfEdge *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
        */
        if(! TOLERANCE_NONZERO ) return;
        SpliceMergeVertices( tess, e, vEvent->anEdge );
        return;
    }

    if( ! VertEq( e->Dst, vEvent )) {
        /* General case -- splice vEvent into edge e which passes through it */
        if (tessMeshSplitEdge( tess->mesh, e->Sym ) == NULL) longjmp(tess->env,1);
        if( regUp->fixUpperEdge ) {
            /* This edge was fixable -- delete unused portion of original edge */
            if ( !tessMeshDelete( tess->mesh, e->Onext ) ) longjmp(tess->env,1);
            regUp->fixUpperEdge = FALSE;
        }
        if ( !tessMeshSplice( tess->mesh, 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.
    */
    if(! TOLERANCE_NONZERO ) return;
    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.
        */
        if( eTopLeft == eTopRight ) return;   /* there are some left edges too */
        DeleteRegion( tess, reg );
        if ( !tessMeshDelete( tess->mesh, eTopRight ) ) longjmp(tess->env,1);
        eTopRight = eTopLeft->Oprev;
    }
    if ( !tessMeshSplice( tess->mesh, 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( TESStesselator *tess, TESSvertex *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;
    TESShalfEdge *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 */ /* tessDictListSearch */
    regUp = (ActiveRegion *)dictKey( dictSearch( tess->dict, &tmp ));
    regLo = RegionBelow( regUp );
    if(!regUp) return;
    if(!regLo) return;

    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 = tessMeshConnect( tess->mesh, vEvent->anEdge->Sym, eUp->Lnext );
            if (eNew == NULL) longjmp(tess->env,1);
        } else {
            TESShalfEdge *tempHalfEdge= tessMeshConnect( tess->mesh, eLo->Dnext, vEvent->anEdge);
            if (tempHalfEdge == NULL) longjmp(tess->env,1);

            eNew = tempHalfEdge->Sym;
        }
        if( reg->fixUpperEdge ) {
            if ( !FixUpperEdge( tess, 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( TESStesselator *tess, TESSvertex *vEvent )
/*
* Does everything necessary when the sweep line crosses a vertex.
* Updates the mesh and the edge dictionary.
*/
{
    ActiveRegion *regUp, *reg;
    TESShalfEdge *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( tess, 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.
*/

static void AddSentinel( TESStesselator *tess, TESSreal smin, TESSreal smax, TESSreal t )
/*
* We add two sentinel edges above and below all other edges,
* to avoid special cases at the top and bottom.
*/
{
    TESShalfEdge *e;
    ActiveRegion *reg = (ActiveRegion *)bucketAlloc( tess->regionPool );
    if (reg == NULL) longjmp(tess->env,1);

    e = tessMeshMakeEdge( tess->mesh );
    if (e == NULL) longjmp(tess->env,1);

    e->Org->s = smax;
    e->Org->t = t;
    e->Dst->s = smin;
    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 );
    if (reg->nodeUp == NULL) longjmp(tess->env,1);
}


static void InitEdgeDict( TESStesselator *tess )
/*
* We maintain an ordering of edge intersections with the sweep line.
* This order is maintained in a dynamic dictionary.
*/
{
    TESSreal w, h;
    TESSreal smin, smax, tmin, tmax;

    tess->dict = dictNewDict( &tess->alloc, tess, (int (*)(void *, DictKey, DictKey)) EdgeLeq );
    if (tess->dict == NULL) longjmp(tess->env,1);

    w = (tess->bmax[0] - tess->bmin[0]);
    h = (tess->bmax[1] - tess->bmin[1]);

    smin = tess->bmin[0] - w;
    smax = tess->bmax[0] + w;
    tmin = tess->bmin[1] - h;
    tmax = tess->bmax[1] + h;

    AddSentinel( tess, smin, smax, tmin );
    AddSentinel( tess, smin, smax, tmax );
}


static void DoneEdgeDict( TESStesselator *tess )
{
    ActiveRegion *reg;
    int fixedEdges = 0;

    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 ) {
            if(! reg->fixUpperEdge ) continue;
            if( ++fixedEdges != 1 ) continue;
        }
        if( reg->windingNumber != 0 ) continue;
        DeleteRegion( tess, reg );
        /*    tessMeshDelete( reg->eUp );*/
    }
    dictDeleteDict( &tess->alloc, tess->dict );
}


static void RemoveDegenerateEdges( TESStesselator *tess )
/*
* Remove zero-length edges, and contours with fewer than 3 vertices.
*/
{
    TESShalfEdge *e, *eNext, *eLnext;
    TESShalfEdge *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 ( !tessMeshDelete( tess->mesh, 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 ( !tessMeshDelete( tess->mesh, eLnext ) ) longjmp(tess->env,1);
            }
            if( e == eNext || e == eNext->Sym ) { eNext = eNext->next; }
            if ( !tessMeshDelete( tess->mesh, e ) ) longjmp(tess->env,1);
        }
    }
}

static int InitPriorityQ( TESStesselator *tess )
/*
* Insert all vertices into the priority queue which determines the
* order in which vertices cross the sweep line.
*/
{
    PriorityQ *pq;
    TESSvertex *v, *vHead;
    int vertexCount = 0;

    vHead = &tess->mesh->vHead;
    for( v = vHead->next; v != vHead; v = v->next ) {
        vertexCount++;
    }
    /* Make sure there is enough space for sentinels. */
    vertexCount += MAX( 8, tess->alloc.extraVertices );

    pq = tess->pq = pqNewPriorityQ( &tess->alloc, vertexCount, (int (*)(PQkey, PQkey)) tesvertLeq );
    if (pq == NULL) return 0;

    vHead = &tess->mesh->vHead;
    for( v = vHead->next; v != vHead; v = v->next ) {
        v->pqHandle = pqInsert( &tess->alloc, pq, v );
        if (v->pqHandle == INV_HANDLE)
            break;
    }
    if (v != vHead || !pqInit( &tess->alloc, pq ) ) {
        pqDeletePriorityQ( &tess->alloc, tess->pq );
        tess->pq = NULL;
        return 0;
    }

    return 1;
}


static void DonePriorityQ( TESStesselator *tess )
{
    pqDeletePriorityQ( &tess->alloc, tess->pq );
}


static int RemoveDegenerateFaces( TESStesselator *tess, TESSmesh *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.
*/
{
    TESSface *f, *fNext;
    TESShalfEdge *e;

    /*LINTED*/
    for( f = mesh->fHead.next; f != &mesh->fHead; f = fNext ) {
        fNext = f->next;
        e = f->anEdge;
        if( e->Lnext == e ) continue;

        if( e->Lnext->Lnext == e ) {
            /* A face with only two edges */
            AddWinding( e->Onext, e );
            if ( !tessMeshDelete( tess->mesh, e ) ) return 0;
        }
    }
    return 1;
}

int tessComputeInterior( TESStesselator *tess )
/*
* tessComputeInterior( 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.
*/
{
    TESSvertex *v, *vNext;

    /* 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 );

    while( (v = (TESSvertex *)pqExtractMin( tess->pq )) != NULL ) {
        for( ;; ) {
            vNext = (TESSvertex *)pqMinimum( tess->pq );
            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 (TESS_BOUNDARY_ONLY).
            */
            vNext = (TESSvertex *)pqExtractMin( tess->pq );
            SpliceMergeVertices( tess, v->anEdge, vNext->anEdge );
        }
        SweepEvent( tess, v );
    }

    /* Set tess->event for debugging purposes */
    tess->event = ((ActiveRegion *) dictKey( dictMin( tess->dict )))->eUp->Org;
    DebugEvent( tess );
    DoneEdgeDict( tess );
    DonePriorityQ( tess );

    if ( !RemoveDegenerateFaces( tess, tess->mesh ) ) return 0;
    //tessMeshCheckMesh( tess->mesh );

    return 1;
}
