Lines Matching defs:tess
43 #include "tess.h"
57 extern void DebugEvent( GLUtesselator *tess );
59 #define DebugEvent( tess )
103 static void SweepEvent( GLUtesselator *tess, GLUvertex *vEvent );
104 static void WalkDirtyRegions( GLUtesselator *tess, ActiveRegion *regUp );
105 static int CheckForRightSplice( GLUtesselator *tess, ActiveRegion *regUp );
107 static int EdgeLeq( GLUtesselator *tess, ActiveRegion *reg1,
114 * current sweep line position, given by tess->event. The calculations
121 GLUvertex *event = tess->event;
151 static void DeleteRegion( GLUtesselator *tess, ActiveRegion *reg )
161 dictDelete( tess->dict, reg->nodeUp ); /* __gl_dictListDelete */
213 static ActiveRegion *AddRegionBelow( GLUtesselator *tess,
224 if (regNew == NULL) longjmp(tess->env,1);
228 regNew->nodeUp = dictInsertBefore( tess->dict, regAbove->nodeUp, regNew );
229 if (regNew->nodeUp == NULL) longjmp(tess->env,1);
238 static GLboolean IsWindingInside( GLUtesselator *tess, int n )
240 switch( tess->windingRule ) {
259 static void ComputeWinding( GLUtesselator *tess, ActiveRegion *reg )
262 reg->inside = IsWindingInside( tess, reg->windingNumber );
266 static void FinishRegion( GLUtesselator *tess, ActiveRegion *reg )
280 DeleteRegion( tess, reg );
284 static GLUhalfEdge *FinishLeftRegions( GLUtesselator *tess,
316 FinishRegion( tess, regPrev );
323 if (e == NULL) longjmp(tess->env,1);
324 if ( !FixUpperEdge( reg, e ) ) longjmp(tess->env,1);
329 if ( !__gl_meshSplice( e->Oprev, e ) ) longjmp(tess->env,1);
330 if ( !__gl_meshSplice( ePrev, e ) ) longjmp(tess->env,1);
332 FinishRegion( tess, regPrev ); /* may change reg->eUp */
340 static void AddRightEdges( GLUtesselator *tess, ActiveRegion *regUp,
362 AddRegionBelow( tess, regUp, e->Sym );
382 if ( !__gl_meshSplice( e->Oprev, e ) ) longjmp(tess->env,1);
383 if ( !__gl_meshSplice( ePrev->Oprev, e ) ) longjmp(tess->env,1);
387 reg->inside = IsWindingInside( tess, reg->windingNumber );
393 if( ! firstTime && CheckForRightSplice( tess, regPrev )) {
395 DeleteRegion( tess, regPrev );
396 if ( !__gl_meshDelete( ePrev ) ) longjmp(tess->env,1);
407 WalkDirtyRegions( tess, regPrev );
412 static void CallCombine( GLUtesselator *tess, GLUvertex *isect,
427 } else if( ! tess->fatalError ) {
433 tess->fatalError = TRUE;
438 static void SpliceMergeVertices( GLUtesselator *tess, GLUhalfEdge *e1,
450 CallCombine( tess, e1->Org, data, weights, FALSE );
451 if ( !__gl_meshSplice( e1, e2 ) ) longjmp(tess->env,1);
475 static void GetIntersectData( GLUtesselator *tess, GLUvertex *isect,
496 CallCombine( tess, isect, data, weights, TRUE );
499 static int CheckForRightSplice( GLUtesselator *tess, ActiveRegion *regUp )
517 * CheckForIntersect requires that tess->event lies between eUp and eLo,
536 if ( __gl_meshSplitEdge( eLo->Sym ) == NULL) longjmp(tess->env,1);
537 if ( !__gl_meshSplice( eUp, eLo->Oprev ) ) longjmp(tess->env,1);
542 pqDelete( tess->pq, eUp->Org->pqHandle ); /* __gl_pqSortDelete */
543 SpliceMergeVertices( tess, eLo->Oprev, eUp );
552 if (__gl_meshSplitEdge( eUp->Sym ) == NULL) longjmp(tess->env,1);
553 if ( !__gl_meshSplice( eLo->Oprev, eUp ) ) longjmp(tess->env,1);
558 static int CheckForLeftSplice( GLUtesselator *tess, ActiveRegion *regUp )
593 if (e == NULL) longjmp(tess->env,1);
594 if ( !__gl_meshSplice( eLo->Sym, e ) ) longjmp(tess->env,1);
602 if (e == NULL) longjmp(tess->env,1);
603 if ( !__gl_meshSplice( eUp->Lnext, eLo->Sym ) ) longjmp(tess->env,1);
610 static int CheckForIntersect( GLUtesselator *tess, ActiveRegion *regUp )
633 assert( EdgeSign( dstUp, tess->event, orgUp ) <= 0 );
634 assert( EdgeSign( dstLo, tess->event, orgLo ) >= 0 );
635 assert( orgUp != tess->event && orgLo != tess->event );
651 DebugEvent( tess );
660 if( VertLeq( &isect, tess->event )) {
665 * replace the intersection by tess->event.
667 isect.s = tess->event->s;
668 isect.t = tess->event->t;
684 (void) CheckForRightSplice( tess, regUp );
688 if( (! VertEq( dstUp, tess->event )
689 && EdgeSign( dstUp, tess->event, &isect ) >= 0)
690 || (! VertEq( dstLo, tess->event )
691 && EdgeSign( dstLo, tess->event, &isect ) <= 0 ))
697 if( dstLo == tess->event ) {
699 if (__gl_meshSplitEdge( eUp->Sym ) == NULL) longjmp(tess->env,1);
700 if ( !__gl_meshSplice( eLo->Sym, eUp ) ) longjmp(tess->env,1);
702 if (regUp == NULL) longjmp(tess->env,1);
704 FinishLeftRegions( tess, RegionBelow(regUp), regLo );
705 AddRightEdges( tess, regUp, eUp->Oprev, eUp, eUp, TRUE );
708 if( dstUp == tess->event ) {
710 if (__gl_meshSplitEdge( eLo->Sym ) == NULL) longjmp(tess->env,1);
711 if ( !__gl_meshSplice( eUp->Lnext, eLo->Oprev ) ) longjmp(tess->env,1);
716 eLo = FinishLeftRegions( tess, regLo, NULL );
717 AddRightEdges( tess, regUp, eLo->Onext, eUp->Rprev, e, TRUE );
721 * edge passes on the wrong side of tess->event, split it
724 if( EdgeSign( dstUp, tess->event, &isect ) >= 0 ) {
728 if (__gl_meshSplitEdge( eUp->Sym ) == NULL) longjmp(tess->env,1);
729 eUp->Org->s = tess->event->s;
730 eUp->Org->t = tess->event->t;
732 if( EdgeSign( dstLo, tess->event, &isect ) <= 0 ) {
734 if (__gl_meshSplitEdge( eLo->Sym ) == NULL) longjmp(tess->env,1);
735 eLo->Org->s = tess->event->s;
736 eLo->Org->t = tess->event->t;
750 if (__gl_meshSplitEdge( eUp->Sym ) == NULL) longjmp(tess->env,1);
751 if (__gl_meshSplitEdge( eLo->Sym ) == NULL) longjmp(tess->env,1);
752 if ( !__gl_meshSplice( eLo->Oprev, eUp ) ) longjmp(tess->env,1);
755 eUp->Org->pqHandle = pqInsert( tess->pq, eUp->Org ); /* __gl_pqSortInsert */
757 pqDeletePriorityQ(tess->pq); /* __gl_pqSortDeletePriorityQ */
758 tess->pq = NULL;
759 longjmp(tess->env,1);
761 GetIntersectData( tess, eUp->Org, orgUp, dstUp, orgLo, dstLo );
768 static void WalkDirtyRegions( GLUtesselator *tess, ActiveRegion *regUp )
801 if( CheckForLeftSplice( tess, regUp )) {
808 DeleteRegion( tess, regLo );
809 if ( !__gl_meshDelete( eLo ) ) longjmp(tess->env,1);
813 DeleteRegion( tess, regUp );
814 if ( !__gl_meshDelete( eUp ) ) longjmp(tess->env,1);
823 && (eUp->Dst == tess->event || eLo->Dst == tess->event) )
825 /* When all else fails in CheckForIntersect(), it uses tess->event
827 * that tess->event lie between the upper and lower edges, and also
829 * case it might splice one of these edges into tess->event, and
833 if( CheckForIntersect( tess, regUp )) {
841 (void) CheckForRightSplice( tess, regUp );
847 DeleteRegion( tess, regUp );
848 if ( !__gl_meshDelete( eUp ) ) longjmp(tess->env,1);
855 static void ConnectRightVertex( GLUtesselator *tess, ActiveRegion *regUp,
897 (void) CheckForIntersect( tess, regUp );
903 if( VertEq( eUp->Org, tess->event )) {
904 if ( !__gl_meshSplice( eTopLeft->Oprev, eUp ) ) longjmp(tess->env,1);
906 if (regUp == NULL) longjmp(tess->env,1);
908 FinishLeftRegions( tess, RegionBelow(regUp), regLo );
911 if( VertEq( eLo->Org, tess->event )) {
912 if ( !__gl_meshSplice( eBottomLeft, eLo->Oprev ) ) longjmp(tess->env,1);
913 eBottomLeft = FinishLeftRegions( tess, regLo, NULL );
917 AddRightEdges( tess, regUp, eBottomLeft->Onext, eTopLeft, eTopLeft, TRUE );
930 if (eNew == NULL) longjmp(tess->env,1);
935 AddRightEdges( tess, regUp, eNew, eNew->Onext, eNew->Onext, FALSE );
937 WalkDirtyRegions( tess, regUp );
949 static void ConnectLeftDegenerate( GLUtesselator *tess,
966 SpliceMergeVertices( tess, e, vEvent->anEdge );
972 if (__gl_meshSplitEdge( e->Sym ) == NULL) longjmp(tess->env,1);
975 if ( !__gl_meshDelete( e->Onext ) ) longjmp(tess->env,1);
978 if ( !__gl_meshSplice( vEvent->anEdge, e ) ) longjmp(tess->env,1);
979 SweepEvent( tess, vEvent ); /* recurse */
996 DeleteRegion( tess, reg );
997 if ( !__gl_meshDelete( eTopRight ) ) longjmp(tess->env,1);
1000 if ( !__gl_meshSplice( vEvent->anEdge, eTopRight ) ) longjmp(tess->env,1);
1005 AddRightEdges( tess, regUp, eTopRight->Onext, eLast, eTopLeft, TRUE );
1009 static void ConnectLeftVertex( GLUtesselator *tess, GLUvertex *vEvent )
1035 regUp = (ActiveRegion *)dictKey( dictSearch( tess->dict, &tmp ));
1042 ConnectLeftDegenerate( tess, regUp, vEvent );
1054 if (eNew == NULL) longjmp(tess->env,1);
1057 if (tempHalfEdge == NULL) longjmp(tess->env,1);
1062 if ( !FixUpperEdge( reg, eNew ) ) longjmp(tess->env,1);
1064 ComputeWinding( tess, AddRegionBelow( tess, regUp, eNew ));
1066 SweepEvent( tess, vEvent );
1071 AddRightEdges( tess, regUp, vEvent->anEdge, vEvent->anEdge, NULL, TRUE );
1076 static void SweepEvent( GLUtesselator *tess, GLUvertex *vEvent )
1085 tess->event = vEvent; /* for access in EdgeLeq() */
1086 DebugEvent( tess );
1097 ConnectLeftVertex( tess, vEvent );
1110 if (regUp == NULL) longjmp(tess->env,1);
1113 eBottomLeft = FinishLeftRegions( tess, reg, NULL );
1122 ConnectRightVertex( tess, regUp, eBottomLeft );
1124 AddRightEdges( tess, regUp, eBottomLeft->Onext, eTopLeft, eTopLeft, TRUE );
1136 static void AddSentinel( GLUtesselator *tess, GLdouble t )
1144 if (reg == NULL) longjmp(tess->env,1);
1146 e = __gl_meshMakeEdge( tess->mesh );
1147 if (e == NULL) longjmp(tess->env,1);
1153 tess->event = e->Dst; /* initialize it */
1161 reg->nodeUp = dictInsert( tess->dict, reg ); /* __gl_dictListInsertBefore */
1162 if (reg->nodeUp == NULL) longjmp(tess->env,1);
1166 static void InitEdgeDict( GLUtesselator *tess )
1173 tess->dict = dictNewDict( tess, (int (*)(void *, DictKey, DictKey)) EdgeLeq );
1174 if (tess->dict == NULL) longjmp(tess->env,1);
1176 AddSentinel( tess, -SENTINEL_COORD );
1177 AddSentinel( tess, SENTINEL_COORD );
1181 static void DoneEdgeDict( GLUtesselator *tess )
1189 while( (reg = (ActiveRegion *)dictKey( dictMin( tess->dict ))) != NULL ) {
1200 DeleteRegion( tess, reg );
1203 dictDeleteDict( tess->dict ); /* __gl_dictListDeleteDict */
1207 static void RemoveDegenerateEdges( GLUtesselator *tess )
1213 GLUhalfEdge *eHead = &tess->mesh->eHead;
1223 SpliceMergeVertices( tess, eLnext, e ); /* deletes e->Org */
1224 if ( !__gl_meshDelete( e ) ) longjmp(tess->env,1); /* e is a self-loop */
1233 if ( !__gl_meshDelete( eLnext ) ) longjmp(tess->env,1);
1236 if ( !__gl_meshDelete( e ) ) longjmp(tess->env,1);
1241 static int InitPriorityQ( GLUtesselator *tess )
1251 pq = tess->pq = pqNewPriorityQ( (int (*)(PQkey, PQkey)) __gl_vertLeq );
1254 vHead = &tess->mesh->vHead;
1260 pqDeletePriorityQ(tess->pq); /* __gl_pqSortDeletePriorityQ */
1261 tess->pq = NULL;
1269 static void DonePriorityQ( GLUtesselator *tess )
1271 pqDeletePriorityQ( tess->pq ); /* __gl_pqSortDeletePriorityQ */
1309 int __gl_computeInterior( GLUtesselator *tess )
1311 * __gl_computeInterior( tess ) computes the planar arrangement specified
1314 * to the polygon, according to the rule given by tess->windingRule.
1320 tess->fatalError = FALSE;
1328 RemoveDegenerateEdges( tess );
1329 if ( !InitPriorityQ( tess ) ) return 0; /* if error */
1330 InitEdgeDict( tess );
1333 while( (v = (GLUvertex *)pqExtractMin( tess->pq )) != NULL ) {
1335 vNext = (GLUvertex *)pqMinimum( tess->pq ); /* __gl_pqSortMinimum */
1352 vNext = (GLUvertex *)pqExtractMin( tess->pq ); /* __gl_pqSortExtractMin*/
1353 SpliceMergeVertices( tess, v->anEdge, vNext->anEdge );
1355 SweepEvent( tess, v );
1358 /* Set tess->event for debugging purposes */
1360 tess->event = ((ActiveRegion *) dictKey( dictMin( tess->dict )))->eUp->Org;
1361 DebugEvent( tess );
1362 DoneEdgeDict( tess );
1363 DonePriorityQ( tess );
1365 if ( !RemoveDegenerateFaces( tess->mesh ) ) return 0;
1366 __gl_meshCheckMesh( tess->mesh );