#include "gluos.h"
#include <assert.h>
#include "geom.h"
#include "tess.h"
#include "memalloc.h"
#include "sweep.h"

Include dependency graph for sweep.c:

Macros
#define	TRUE 1

#define	FALSE 0

#define	DebugEvent(tess)

#define	MAX(x, y) ((x) >= (y) ? (x) : (y))

#define	MIN(x, y) ((x) <= (y) ? (x) : (y))

#define	AddWinding(eDst, eSrc)

#define	TOLERANCE_NONZERO FALSE

#define	SENTINEL_COORD (4 * GLU_TESS_MAX_COORD)

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

static void	DeleteRegion (GLUtesselator tess, ActiveRegion reg)

static int	FixUpperEdge (ActiveRegion reg, GLUhalfEdge newEdge)

static ActiveRegion *	TopLeftRegion (ActiveRegion *reg)

static ActiveRegion *	TopRightRegion (ActiveRegion *reg)

static ActiveRegion *	AddRegionBelow (GLUtesselator tess, ActiveRegion regAbove, GLUhalfEdge *eNewUp)

static GLboolean	IsWindingInside (GLUtesselator *tess, int n)

static void	ComputeWinding (GLUtesselator tess, ActiveRegion reg)

static void	FinishRegion (GLUtesselator tess, ActiveRegion reg)

static GLUhalfEdge *	FinishLeftRegions (GLUtesselator tess, ActiveRegion regFirst, ActiveRegion *regLast)

static void	AddRightEdges (GLUtesselator tess, ActiveRegion regUp, GLUhalfEdge eFirst, GLUhalfEdge eLast, GLUhalfEdge *eTopLeft, GLboolean cleanUp)

static void	CallCombine (GLUtesselator tess, GLUvertex isect, void *data[4], GLfloat weights[4], int needed)

static void	SpliceMergeVertices (GLUtesselator tess, GLUhalfEdge e1, GLUhalfEdge *e2)

static void	VertexWeights (GLUvertex isect, GLUvertex org, GLUvertex dst, GLfloat weights)

static void	GetIntersectData (GLUtesselator tess, GLUvertex isect, GLUvertex orgUp, GLUvertex dstUp, GLUvertex orgLo, GLUvertex dstLo)

static int	CheckForLeftSplice (GLUtesselator tess, ActiveRegion regUp)

static int	CheckForIntersect (GLUtesselator tess, ActiveRegion regUp)

static void	ConnectRightVertex (GLUtesselator tess, ActiveRegion regUp, GLUhalfEdge *eBottomLeft)

static void	ConnectLeftDegenerate (GLUtesselator tess, ActiveRegion regUp, GLUvertex *vEvent)

static void	ConnectLeftVertex (GLUtesselator tess, GLUvertex vEvent)

static void	AddSentinel (GLUtesselator *tess, GLdouble t)

static void	InitEdgeDict (GLUtesselator *tess)

static void	DoneEdgeDict (GLUtesselator *tess)

static void	RemoveDegenerateEdges (GLUtesselator *tess)

static int	InitPriorityQ (GLUtesselator *tess)

static void	DonePriorityQ (GLUtesselator *tess)

static int	RemoveDegenerateFaces (GLUmesh *mesh)

int	__gl_computeInterior (GLUtesselator *tess)

Macro Definition Documentation

◆ AddWinding

#define AddWinding	(	eDst,
		eSrc
	)

Value:

(eDst->winding += eSrc->winding, \

eDst->Sym->winding += eSrc->Sym->winding)

Definition at line 100 of file sweep.c.

◆ DebugEvent

#define DebugEvent ( tess )

Definition at line 59 of file sweep.c.

◆ FALSE

#define FALSE 0

Definition at line 53 of file sweep.c.

◆ MAX

#define MAX	(	x,
		y
	)	((x) >= (y) ? (x) : (y))

Definition at line 94 of file sweep.c.

◆ MIN

#define MIN	(	x,
		y
	)	((x) <= (y) ? (x) : (y))

Definition at line 95 of file sweep.c.

◆ SENTINEL_COORD

#define SENTINEL_COORD (4 * GLU_TESS_MAX_COORD)

Definition at line 1126 of file sweep.c.

◆ TOLERANCE_NONZERO

#define TOLERANCE_NONZERO FALSE

Definition at line 939 of file sweep.c.

◆ TRUE

#define TRUE 1

Definition at line 50 of file sweep.c.

Function Documentation

◆ __gl_computeInterior()

int __gl_computeInterior ( GLUtesselator * tess )

Definition at line 1301 of file sweep.c.

{
  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;
}

Referenced by gluTessEndPolygon().

◆ AddRegionBelow()

static ActiveRegion * AddRegionBelow	(	GLUtesselator *	tess,
		ActiveRegion *	regAbove,
		GLUhalfEdge *	eNewUp
	)

static

Definition at line 213 of file sweep.c.

{
  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;
}

Referenced by AddRightEdges(), and ConnectLeftVertex().

◆ AddRightEdges()

static void AddRightEdges	(	GLUtesselator *	tess,
		ActiveRegion *	regUp,
		GLUhalfEdge *	eFirst,
		GLUhalfEdge *	eLast,
		GLUhalfEdge *	eTopLeft,
		GLboolean	cleanUp
	)

static

Definition at line 340 of file sweep.c.

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

Referenced by CheckForIntersect(), ConnectLeftDegenerate(), ConnectLeftVertex(), ConnectRightVertex(), and SweepEvent().

◆ AddSentinel()

static void AddSentinel	(	GLUtesselator *	tess,
		GLdouble	t
	)

static

Definition at line 1128 of file sweep.c.

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

Referenced by InitEdgeDict().

◆ CallCombine()

static void CallCombine	(	GLUtesselator *	tess,
		GLUvertex *	isect,
		void *	data[4],
		GLfloat	weights[4],
		int	needed
	)

static

Definition at line 412 of file sweep.c.

{
  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;
    }
  }
}

Referenced by GetIntersectData(), and SpliceMergeVertices().

◆ CheckForIntersect()

static int CheckForIntersect	(	GLUtesselator *	tess,
		ActiveRegion *	regUp
	)

static

Definition at line 606 of file sweep.c.

{
  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;
}

Referenced by ConnectRightVertex(), and WalkDirtyRegions().

◆ CheckForLeftSplice()

static int CheckForLeftSplice	(	GLUtesselator *	tess,
		ActiveRegion *	regUp
	)

static

Definition at line 556 of file sweep.c.

{
  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;
}

Referenced by WalkDirtyRegions().

◆ CheckForRightSplice()

static int CheckForRightSplice	(	GLUtesselator *	tess,
		ActiveRegion *	regUp
	)

static

Definition at line 499 of file sweep.c.

{
  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;
}

Referenced by AddRightEdges(), CheckForIntersect(), and WalkDirtyRegions().

◆ ComputeWinding()

static void ComputeWinding	(	GLUtesselator *	tess,
		ActiveRegion *	reg
	)

static

Definition at line 259 of file sweep.c.

{
  reg->windingNumber = RegionAbove(reg)->windingNumber + reg->eUp->winding;
  reg->inside = IsWindingInside( tess, reg->windingNumber );
}

Referenced by ConnectLeftVertex().

◆ ConnectLeftDegenerate()

static void ConnectLeftDegenerate	(	GLUtesselator *	tess,
		ActiveRegion *	regUp,
		GLUvertex *	vEvent
	)

static

Definition at line 941 of file sweep.c.

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

Referenced by ConnectLeftVertex().

◆ ConnectLeftVertex()

static void ConnectLeftVertex	(	GLUtesselator *	tess,
		GLUvertex *	vEvent
	)

static

Definition at line 1001 of file sweep.c.

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

Referenced by SweepEvent().

◆ ConnectRightVertex()

static void ConnectRightVertex	(	GLUtesselator *	tess,
		ActiveRegion *	regUp,
		GLUhalfEdge *	eBottomLeft
	)

static

Definition at line 847 of file sweep.c.

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

Referenced by SweepEvent().

◆ DeleteRegion()

static void DeleteRegion	(	GLUtesselator *	tess,
		ActiveRegion *	reg
	)

static

Definition at line 151 of file sweep.c.

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

Referenced by AddRightEdges(), ConnectLeftDegenerate(), DeleteObject(), DoneEdgeDict(), FinishRegion(), and WalkDirtyRegions().

◆ DoneEdgeDict()

static void DoneEdgeDict ( GLUtesselator * tess )

static

Definition at line 1173 of file sweep.c.

{
  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 */
}

Referenced by __gl_computeInterior().

◆ DonePriorityQ()

static void DonePriorityQ ( GLUtesselator * tess )

static

Definition at line 1261 of file sweep.c.

{
  pqDeletePriorityQ( tess->pq ); /* __gl_pqSortDeletePriorityQ */
}

Referenced by __gl_computeInterior().

◆ EdgeLeq()

static int EdgeLeq	(	GLUtesselator *	tess,
		ActiveRegion *	reg1,
		ActiveRegion *	reg2
	)

static

Definition at line 107 of file sweep.c.

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

Referenced by InitEdgeDict().

◆ FinishLeftRegions()

static GLUhalfEdge * FinishLeftRegions	(	GLUtesselator *	tess,
		ActiveRegion *	regFirst,
		ActiveRegion *	regLast
	)

static

Definition at line 284 of file sweep.c.

{
  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;
}

Referenced by CheckForIntersect(), ConnectRightVertex(), and SweepEvent().

◆ FinishRegion()

static void FinishRegion	(	GLUtesselator *	tess,
		ActiveRegion *	reg
	)

static

Definition at line 266 of file sweep.c.

{
  GLUhalfEdge *e = reg->eUp;
  GLUface *f = e->Lface;
 
  f->inside = reg->inside;
  f->anEdge = e;   /* optimization for __gl_meshTessellateMonoRegion() */
  DeleteRegion( tess, reg );
}

Referenced by FinishLeftRegions().

◆ FixUpperEdge()

static int FixUpperEdge	(	ActiveRegion *	reg,
		GLUhalfEdge *	newEdge
	)

static

Definition at line 166 of file sweep.c.

{
  assert( reg->fixUpperEdge );
  if ( !__gl_meshDelete( reg->eUp ) ) return 0;
  reg->fixUpperEdge = FALSE;
  reg->eUp = newEdge;
  newEdge->activeRegion = reg;
 
  return 1;
}

Referenced by ConnectLeftVertex(), FinishLeftRegions(), and TopLeftRegion().

◆ GetIntersectData()

static void GetIntersectData	(	GLUtesselator *	tess,
		GLUvertex *	isect,
		GLUvertex *	orgUp,
		GLUvertex *	dstUp,
		GLUvertex *	orgLo,
		GLUvertex *	dstLo
	)

static

Definition at line 475 of file sweep.c.

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

Referenced by CheckForIntersect().

◆ InitEdgeDict()

static void InitEdgeDict ( GLUtesselator * tess )

static

Definition at line 1158 of file sweep.c.

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

Referenced by __gl_computeInterior().

◆ InitPriorityQ()

static int InitPriorityQ ( GLUtesselator * tess )

static

Definition at line 1233 of file sweep.c.

{
  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;
}

Referenced by __gl_computeInterior().

◆ IsWindingInside()

static GLboolean IsWindingInside	(	GLUtesselator *	tess,
		int	n
	)

static

Definition at line 238 of file sweep.c.

{
  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 */
}

Referenced by AddRightEdges(), and ComputeWinding().

◆ RemoveDegenerateEdges()

static void RemoveDegenerateEdges ( GLUtesselator * tess )

static

Definition at line 1199 of file sweep.c.

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

Referenced by __gl_computeInterior().

◆ RemoveDegenerateFaces()

static int RemoveDegenerateFaces ( GLUmesh * mesh )

static

Definition at line 1267 of file sweep.c.

{
  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;
}

Referenced by __gl_computeInterior().

◆ SpliceMergeVertices()

static void SpliceMergeVertices	(	GLUtesselator *	tess,
		GLUhalfEdge *	e1,
		GLUhalfEdge *	e2
	)

static

Definition at line 438 of file sweep.c.

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

Referenced by __gl_computeInterior(), CheckForRightSplice(), ConnectLeftDegenerate(), and RemoveDegenerateEdges().

◆ SweepEvent()

static void SweepEvent	(	GLUtesselator *	tess,
		GLUvertex *	vEvent
	)

static

Definition at line 1068 of file sweep.c.

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

Referenced by __gl_computeInterior(), ConnectLeftDegenerate(), and ConnectLeftVertex().

◆ TopLeftRegion()

static ActiveRegion * TopLeftRegion ( ActiveRegion * reg )

static

Definition at line 180 of file sweep.c.

{
  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;
}

Referenced by CheckForIntersect(), ConnectRightVertex(), and SweepEvent().

◆ TopRightRegion()

static ActiveRegion * TopRightRegion ( ActiveRegion * reg )

static

Definition at line 202 of file sweep.c.

{
  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;
}

Referenced by CheckForIntersect(), and ConnectLeftDegenerate().

◆ VertexWeights()

static void VertexWeights	(	GLUvertex *	isect,
		GLUvertex *	org,
		GLUvertex *	dst,
		GLfloat *	weights
	)

static

Definition at line 454 of file sweep.c.

{
  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];
}

Referenced by GetIntersectData().

◆ WalkDirtyRegions()

static void WalkDirtyRegions	(	GLUtesselator *	tess,
		ActiveRegion *	regUp
	)

static

Definition at line 760 of file sweep.c.

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

Referenced by AddRightEdges(), and ConnectRightVertex().

Macros

Functions

Macro Definition Documentation

◆ AddWinding

◆ DebugEvent

◆ FALSE

◆ MAX

◆ MIN

◆ SENTINEL_COORD

◆ TOLERANCE_NONZERO

◆ TRUE

Function Documentation

◆ __gl_computeInterior()

◆ AddRegionBelow()

◆ AddRightEdges()

◆ AddSentinel()

◆ CallCombine()

◆ CheckForIntersect()

◆ CheckForLeftSplice()

◆ CheckForRightSplice()

◆ ComputeWinding()

◆ ConnectLeftDegenerate()

◆ ConnectLeftVertex()

◆ ConnectRightVertex()

◆ DeleteRegion()

◆ DoneEdgeDict()

◆ DonePriorityQ()

◆ EdgeLeq()

◆ FinishLeftRegions()

◆ FinishRegion()

◆ FixUpperEdge()

◆ GetIntersectData()

◆ InitEdgeDict()

◆ InitPriorityQ()

◆ IsWindingInside()

◆ RemoveDegenerateEdges()

◆ RemoveDegenerateFaces()

◆ SpliceMergeVertices()

◆ SweepEvent()

◆ TopLeftRegion()

◆ TopRightRegion()

◆ VertexWeights()

◆ WalkDirtyRegions()