Geant4 Cross Reference |
1 // see license file for original license. 2 3 #ifndef tools_glutess_sweep 4 #define tools_glutess_sweep 5 6 #include "mesh" 7 #include "dict" 8 9 /* For each pair of adjacent edges crossing th 10 * an ActiveRegion to represent the region bet 11 * regions are kept in sorted order in a dynam 12 * sweep line crosses each vertex, we update t 13 */ 14 15 struct ActiveRegion { 16 GLUhalfEdge *eUp; /* upper edge, directed 17 DictNode *nodeUp; /* dictionary node corre 18 int windingNumber; /* used to determine w 19 * inside the 20 GLUboolean inside; /* is this region insi 21 GLUboolean sentinel; /* marks fake edges at 22 GLUboolean dirty; /* marks regions where 23 * edge has ch 24 * whether the 25 GLUboolean fixUpperEdge; /* marks temporary 26 * we process 27 * any edges l 28 }; 29 30 #define RegionBelow(r) ((ActiveRegion *) dict 31 #define RegionAbove(r) ((ActiveRegion *) dict 32 33 ////////////////////////////////////////////// 34 /// inlined C code : ///////////////////////// 35 ////////////////////////////////////////////// 36 37 #include "geom" 38 #include "_tess" 39 #include "priorityq" 40 41 #define DebugEvent( tess ) 42 43 /* 44 * Invariants for the Edge Dictionary. 45 * - each pair of adjacent edges e2=Succ(e1) s 46 * at any valid location of the sweep event 47 * - if EdgeLeq(e2,e1) as well (at any valid s 48 * share a common endpoint 49 * - for each e, e->Dst has been processed, bu 50 * - each edge e satisfies VertLeq(e->Dst,even 51 * where "event" is the current sweep line e 52 * - no edge e has zero length 53 * 54 * Invariants for the Mesh (the processed port 55 * - the portion of the mesh left of the sweep 56 * ie. there is *some* way to embed it in th 57 * - no processed edge has zero length 58 * - no two processed vertices have identical 59 * - each "inside" region is monotone, ie. can 60 * of monotonically increasing vertices acco 61 * - a non-invariant: these chains may inter 62 * 63 * Invariants for the Sweep. 64 * - if none of the edges incident to the even 65 * (ie. none of these edges are in the edge 66 * has only right-going edges. 67 * - if an edge is marked "fixUpperEdge" (it i 68 * by ConnectRightVertex), then it is the on 69 * its associated vertex. (This says that t 70 * when it is necessary.) 71 */ 72 73 /* When we merge two edges into one, we need t 74 * winding of the new edge. 75 */ 76 #define AddWinding(eDst,eSrc) (eDst->winding + 77 eDst->Sym->wi 78 79 inline/*static*/ void static_SweepEvent( GLUte 80 inline/*static*/ void static_WalkDirtyRegions( 81 inline/*static*/ int static_CheckForRightSplic 82 83 inline/*static*/ int static_EdgeLeq( GLUtessel 84 ActiveRegion *reg2 ) 85 /* 86 * Both edges must be directed from right to l 87 * direction for the upper edge of each region 88 * 89 * The strategy is to evaluate a "t" value for 90 * current sweep line position, given by tess- 91 * are designed to be very stable, but of cour 92 * 93 * Special case: if both edge destinations are 94 * we sort the edges by slope (they would othe 95 */ 96 { 97 GLUvertex *event = tess->event; 98 GLUhalfEdge *e1, *e2; 99 GLUdouble t1, t2; 100 101 e1 = reg1->eUp; 102 e2 = reg2->eUp; 103 104 if( e1->Dst == event ) { 105 if( e2->Dst == event ) { 106 /* Two edges right of the sweep line whi 107 * Sort them by slope. 108 */ 109 if( VertLeq( e1->Org, e2->Org )) { 110 return EdgeSign( e2->Dst, e1->Org, e2->Org ) 111 } 112 return EdgeSign( e1->Dst, e2->Org, e1->O 113 } 114 return EdgeSign( e2->Dst, event, e2->Org ) 115 } 116 if( e2->Dst == event ) { 117 return EdgeSign( e1->Dst, event, e1->Org ) 118 } 119 120 /* General case - compute signed distance *f 121 t1 = EdgeEval( e1->Dst, event, e1->Org ); 122 t2 = EdgeEval( e2->Dst, event, e2->Org ); 123 return (t1 >= t2); 124 } 125 126 127 inline/*static*/ void static_DeleteRegion( GLU 128 { 129 if( reg->fixUpperEdge ) { 130 /* It was created with zero winding number 131 * deleted with zero winding number (ie. i 132 * with a real edge). 133 */ 134 assert( reg->eUp->winding == 0 ); 135 } 136 reg->eUp->activeRegion = NULL; 137 dictDelete( tess->dict, reg->nodeUp ); /* __ 138 memFree( reg ); 139 } 140 141 142 inline/*static*/ int static_FixUpperEdge( Acti 143 /* 144 * Replace an upper edge which needs fixing (s 145 */ 146 { 147 assert( reg->fixUpperEdge ); 148 if ( !__gl_meshDelete( reg->eUp ) ) return 0 149 reg->fixUpperEdge = TOOLS_GLU_FALSE; 150 reg->eUp = newEdge; 151 newEdge->activeRegion = reg; 152 153 return 1; 154 } 155 156 inline/*static*/ ActiveRegion *static_TopLeftR 157 { 158 GLUvertex *org = reg->eUp->Org; 159 GLUhalfEdge *e; 160 161 /* Find the region above the uppermost edge 162 do { 163 reg = RegionAbove( reg ); 164 } while( reg->eUp->Org == org ); 165 166 /* If the edge above was a temporary edge in 167 * now is the time to fix it. 168 */ 169 if( reg->fixUpperEdge ) { 170 e = __gl_meshConnect( RegionBelow(reg)->eU 171 if (e == NULL) return NULL; 172 if ( !static_FixUpperEdge( reg, e ) ) retu 173 reg = RegionAbove( reg ); 174 } 175 return reg; 176 } 177 178 inline/*static*/ ActiveRegion *static_TopRight 179 { 180 GLUvertex *dst = reg->eUp->Dst; 181 182 /* Find the region above the uppermost edge 183 do { 184 reg = RegionAbove( reg ); 185 } while( reg->eUp->Dst == dst ); 186 return reg; 187 } 188 189 inline/*static*/ ActiveRegion *static_AddRegio 190 ActiveRegion *regAbove, 191 GLUhalfEdge *eNewUp ) 192 /* 193 * Add a new active region to the sweep line, 194 * (according to where the new edge belongs in 195 * The upper edge of the new region will be "e 196 * Winding number and "inside" flag are not up 197 */ 198 { 199 ActiveRegion *regNew = (ActiveRegion *)memAl 200 if (regNew == NULL) longjmp(tess->env,1); 201 202 regNew->eUp = eNewUp; 203 /* __gl_dictListInsertBefore */ 204 regNew->nodeUp = dictInsertBefore( tess->dic 205 if (regNew->nodeUp == NULL) longjmp(tess->en 206 regNew->fixUpperEdge = TOOLS_GLU_FALSE; 207 regNew->sentinel = TOOLS_GLU_FALSE; 208 regNew->dirty = TOOLS_GLU_FALSE; 209 210 eNewUp->activeRegion = regNew; 211 return regNew; 212 } 213 214 inline/*static*/ GLUboolean static_IsWindingIn 215 { 216 switch( tess->windingRule ) { 217 case GLU_TESS_WINDING_ODD: 218 return (n & 1); 219 case GLU_TESS_WINDING_NONZERO: 220 return (n != 0); 221 case GLU_TESS_WINDING_POSITIVE: 222 return (n > 0); 223 case GLU_TESS_WINDING_NEGATIVE: 224 return (n < 0); 225 case GLU_TESS_WINDING_ABS_GEQ_TWO: 226 return (n >= 2) || (n <= -2); 227 } 228 /*LINTED*/ 229 assert( TOOLS_GLU_FALSE ); 230 /*NOTREACHED*/ 231 return TOOLS_GLU_FALSE; /* avoid compiler c 232 } 233 234 235 inline/*static*/ void static_ComputeWinding( G 236 { 237 reg->windingNumber = RegionAbove(reg)->windi 238 reg->inside = static_IsWindingInside( tess, 239 } 240 241 242 inline/*static*/ void static_FinishRegion( GLU 243 /* 244 * Delete a region from the sweep line. This 245 * and lower chains of a region meet (at a ver 246 * The "inside" flag is copied to the appropri 247 * not do this before -- since the structure o 248 * changing, this face may not have even exist 249 */ 250 { 251 GLUhalfEdge *e = reg->eUp; 252 GLUface *f = e->Lface; 253 254 f->inside = reg->inside; 255 f->anEdge = e; /* optimization for __gl_me 256 static_DeleteRegion( tess, reg ); 257 } 258 259 260 inline/*static*/ GLUhalfEdge *static_FinishLef 261 ActiveRegion *regFirst, ActiveRegion 262 /* 263 * We are given a vertex with one or more left 264 * edges should be in the edge dictionary. St 265 * we walk down deleting all regions where bot 266 * origin vOrg. At the same time we copy the 267 * active region to the face, since at this po 268 * to at most one region (this was not necessa 269 * in the sweep). The walk stops at the regio 270 * is NULL we walk as far as possible. At the 271 * mesh if necessary, so that the ordering of 272 * same as in the dictionary. 273 */ 274 { 275 ActiveRegion *reg, *regPrev; 276 GLUhalfEdge *e, *ePrev; 277 278 regPrev = regFirst; 279 ePrev = regFirst->eUp; 280 while( regPrev != regLast ) { 281 regPrev->fixUpperEdge = TOOLS_GLU_FALSE; 282 reg = RegionBelow( regPrev ); 283 e = reg->eUp; 284 if( e->Org != ePrev->Org ) { 285 if( ! reg->fixUpperEdge ) { 286 /* Remove the last left-going edge. Even th 287 * edges in the dictionary with this origin, 288 * such edges in the mesh (if we are adding 289 * that has already been processed). Thus i 290 * FinishRegion rather than just DeleteRegio 291 */ 292 static_FinishRegion( tess, regPrev ); 293 break; 294 } 295 /* If the edge below was a temporary edg 296 * ConnectRightVertex, now is the time t 297 */ 298 e = __gl_meshConnect( ePrev->Lprev, e->S 299 if (e == NULL) longjmp(tess->env,1); 300 if ( !static_FixUpperEdge( reg, e ) ) lo 301 } 302 303 /* Relink edges so that ePrev->Onext == e 304 if( ePrev->Onext != e ) { 305 if ( !__gl_meshSplice( e->Oprev, e ) ) l 306 if ( !__gl_meshSplice( ePrev, e ) ) long 307 } 308 static_FinishRegion( tess, regPrev ); /* m 309 ePrev = reg->eUp; 310 regPrev = reg; 311 } 312 return ePrev; 313 } 314 315 316 inline/*static*/ void static_AddRightEdges( GL 317 GLUhalfEdge *eFirst, GLUhalfEdge *eLast 318 GLUboolean cleanUp ) 319 /* 320 * Purpose: insert right-going edges into the 321 * winding numbers and mesh connectivity appro 322 * edges share a common origin vOrg. Edges ar 323 * eFirst; the last edge inserted is eLast->Op 324 * left-going edges already processed, then eT 325 * such that an imaginary upward vertical segm 326 * contained between eTopLeft->Oprev and eTopL 327 * should be NULL. 328 */ 329 { 330 ActiveRegion *reg, *regPrev; 331 GLUhalfEdge *e, *ePrev; 332 int firstTime = TOOLS_GLU_TRUE; 333 334 /* Insert the new right-going edges in the d 335 e = eFirst; 336 do { 337 assert( VertLeq( e->Org, e->Dst )); 338 static_AddRegionBelow( tess, regUp, e->Sym 339 e = e->Onext; 340 } while ( e != eLast ); 341 342 /* Walk *all* right-going edges from e->Org, 343 * updating the winding numbers of each regi 344 * edges to match the dictionary ordering (i 345 */ 346 if( eTopLeft == NULL ) { 347 eTopLeft = RegionBelow( regUp )->eUp->Rpre 348 } 349 regPrev = regUp; 350 ePrev = eTopLeft; 351 for( ;; ) { 352 reg = RegionBelow( regPrev ); 353 e = reg->eUp->Sym; 354 if( e->Org != ePrev->Org ) break; 355 356 if( e->Onext != ePrev ) { 357 /* Unlink e from its current position, a 358 if ( !__gl_meshSplice( e->Oprev, e ) ) l 359 if ( !__gl_meshSplice( ePrev->Oprev, e ) 360 } 361 /* Compute the winding number and "inside" 362 reg->windingNumber = regPrev->windingNumbe 363 reg->inside = static_IsWindingInside( tess 364 365 /* Check for two outgoing edges with same 366 * before any intersection tests (see exam 367 */ 368 regPrev->dirty = TOOLS_GLU_TRUE; 369 if( ! firstTime && static_CheckForRightSpl 370 AddWinding( e, ePrev ); 371 static_DeleteRegion( tess, regPrev ); 372 if ( !__gl_meshDelete( ePrev ) ) longjmp 373 } 374 firstTime = TOOLS_GLU_FALSE; 375 regPrev = reg; 376 ePrev = e; 377 } 378 regPrev->dirty = TOOLS_GLU_TRUE; 379 assert( regPrev->windingNumber - e->winding 380 381 if( cleanUp ) { 382 /* Check for intersections between newly a 383 static_WalkDirtyRegions( tess, regPrev ); 384 } 385 } 386 387 388 inline/*static*/ void static_CallCombine( GLUt 389 void *data[4], GLUfloat weights[4], int 390 { 391 GLUdouble coords[3]; 392 393 /* Copy coord data in case the callback chan 394 coords[0] = isect->coords[0]; 395 coords[1] = isect->coords[1]; 396 coords[2] = isect->coords[2]; 397 398 isect->data = NULL; 399 CALL_COMBINE_OR_COMBINE_DATA( coords, data, 400 if( isect->data == NULL ) { 401 if( ! needed ) { 402 isect->data = data[0]; 403 } else if( ! tess->fatalError ) { 404 /* The only way fatal error is when two 405 * but the user has not provided the cal 406 * generated intersection points. 407 */ 408 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_NEED_ 409 tess->fatalError = TOOLS_GLU_TRUE; 410 } 411 } 412 } 413 414 inline/*static*/ void static_SpliceMergeVertic 415 GLUhalfEdge *e2 ) 416 /* 417 * Two vertices with idential coordinates are 418 * e1->Org is kept, while e2->Org is discarded 419 */ 420 { 421 void *data[4] = { NULL, NULL, NULL, NULL }; 422 GLUfloat weights[4] = { 0.5, 0.5, 0.0, 0.0 } 423 424 data[0] = e1->Org->data; 425 data[1] = e2->Org->data; 426 static_CallCombine( tess, e1->Org, data, wei 427 if ( !__gl_meshSplice( e1, e2 ) ) longjmp(te 428 } 429 430 inline/*static*/ void static_VertexWeights( GL 431 GLUfloat *weights ) 432 /* 433 * Find some weights which describe how the in 434 * a linear combination of "org" and "dest". 435 * which generated "isect" is allocated 50% of 436 * splits the weight between its org and dst a 437 * relative distance to "isect". 438 */ 439 { 440 GLUdouble t1 = VertL1dist( org, isect ); 441 GLUdouble t2 = VertL1dist( dst, isect ); 442 443 weights[0] = float(0.5 * t2 / (t1 + t2)); 444 weights[1] = float(0.5 * t1 / (t1 + t2)); 445 isect->coords[0] += weights[0]*org->coords[0 446 isect->coords[1] += weights[0]*org->coords[1 447 isect->coords[2] += weights[0]*org->coords[2 448 } 449 450 451 inline/*static*/ void static_GetIntersectData( 452 GLUvertex *orgUp, GLUvertex *dstUp, 453 GLUvertex *orgLo, GLUvertex *dstLo ) 454 /* 455 * We've computed a new intersection point, no 456 * from the user so that we can refer to this 457 * rendering callbacks. 458 */ 459 { 460 void *data[4]; 461 GLUfloat weights[4]; 462 463 data[0] = orgUp->data; 464 data[1] = dstUp->data; 465 data[2] = orgLo->data; 466 data[3] = dstLo->data; 467 468 isect->coords[0] = isect->coords[1] = isect- 469 static_VertexWeights( isect, orgUp, dstUp, & 470 static_VertexWeights( isect, orgLo, dstLo, & 471 472 static_CallCombine( tess, isect, data, weigh 473 } 474 475 inline/*static*/ int static_CheckForRightSplic 476 /* 477 * Check the upper and lower edge of "regUp", 478 * eUp->Org is above eLo, or eLo->Org is below 479 * origin is leftmost). 480 * 481 * The main purpose is to splice right-going e 482 * dest vertex and nearly identical slopes (ie 483 * the slopes numerically). However the splic 484 * to recover from numerical errors. For exam 485 * point we checked eUp and eLo, and decided t 486 * above eLo. Then later, we split eLo into t 487 * a splice operation like this one). This ca 488 * our test so that now eUp->Org is incident t 489 * We must correct this condition to maintain 490 * 491 * One possibility is to check these edges for 492 * (ie. CheckForIntersect). This is what we d 493 * CheckForIntersect requires that tess->event 494 * so that it has something to fall back on wh 495 * calculation gives us an unusable answer. S 496 * we can't check for intersection, this routi 497 * by just splicing the offending vertex into 498 * This is a guaranteed solution, no matter ho 499 * Basically this is a combinatorial solution 500 */ 501 { 502 ActiveRegion *regLo = RegionBelow(regUp); 503 GLUhalfEdge *eUp = regUp->eUp; 504 GLUhalfEdge *eLo = regLo->eUp; 505 506 if( VertLeq( eUp->Org, eLo->Org )) { 507 if( EdgeSign( eLo->Dst, eUp->Org, eLo->Org 508 509 /* eUp->Org appears to be below eLo */ 510 if( ! VertEq( eUp->Org, eLo->Org )) { 511 /* Splice eUp->Org into eLo */ 512 if ( __gl_meshSplitEdge( eLo->Sym ) == N 513 if ( !__gl_meshSplice( eUp, eLo->Oprev ) 514 regUp->dirty = regLo->dirty = TOOLS_GLU_ 515 516 } else if( eUp->Org != eLo->Org ) { 517 /* merge the two vertices, discarding eU 518 pqDelete( tess->pq, eUp->Org->pqHandle ) 519 static_SpliceMergeVertices( tess, eLo->O 520 } 521 } else { 522 if( EdgeSign( eUp->Dst, eLo->Org, eUp->Org 523 524 /* eLo->Org appears to be above eUp, so sp 525 RegionAbove(regUp)->dirty = regUp->dirty = 526 if (__gl_meshSplitEdge( eUp->Sym ) == NULL 527 if ( !__gl_meshSplice( eLo->Oprev, eUp ) ) 528 } 529 return TOOLS_GLU_TRUE; 530 } 531 532 inline/*static*/ int static_CheckForLeftSplice 533 /* 534 * Check the upper and lower edge of "regUp", 535 * eUp->Dst is above eLo, or eLo->Dst is below 536 * destination is rightmost). 537 * 538 * Theoretically, this should always be true. 539 * into two pieces can change the results of p 540 * suppose at one point we checked eUp and eLo 541 * is barely above eLo. Then later, we split 542 * a splice operation like this one). This ca 543 * the test so that now eUp->Dst is incident t 544 * We must correct this condition to maintain 545 * (otherwise new edges might get inserted in 546 * dictionary, and bad stuff will happen). 547 * 548 * We fix the problem by just splicing the off 549 * other edge. 550 */ 551 { 552 ActiveRegion *regLo = RegionBelow(regUp); 553 GLUhalfEdge *eUp = regUp->eUp; 554 GLUhalfEdge *eLo = regLo->eUp; 555 GLUhalfEdge *e; 556 557 assert( ! VertEq( eUp->Dst, eLo->Dst )); 558 559 if( VertLeq( eUp->Dst, eLo->Dst )) { 560 if( EdgeSign( eUp->Dst, eLo->Dst, eUp->Org 561 562 /* eLo->Dst is above eUp, so splice eLo->D 563 RegionAbove(regUp)->dirty = regUp->dirty = 564 e = __gl_meshSplitEdge( eUp ); 565 if (e == NULL) longjmp(tess->env,1); 566 if ( !__gl_meshSplice( eLo->Sym, e ) ) lon 567 e->Lface->inside = regUp->inside; 568 } else { 569 if( EdgeSign( eLo->Dst, eUp->Dst, eLo->Org 570 571 /* eUp->Dst is below eLo, so splice eUp->D 572 regUp->dirty = regLo->dirty = TOOLS_GLU_TR 573 e = __gl_meshSplitEdge( eLo ); 574 if (e == NULL) longjmp(tess->env,1); 575 if ( !__gl_meshSplice( eUp->Lnext, eLo->Sy 576 e->Rface->inside = regUp->inside; 577 } 578 return TOOLS_GLU_TRUE; 579 } 580 581 582 inline/*static*/ int static_CheckForIntersect( 583 /* 584 * Check the upper and lower edges of the give 585 * they intersect. If so, create the intersec 586 * to the data structures. 587 * 588 * Returns TOOLS_GLU_TRUE if adding the new in 589 * call to AddRightEdges(); in this case all " 590 * checked for intersections, and possibly reg 591 */ 592 { 593 ActiveRegion *regLo = RegionBelow(regUp); 594 GLUhalfEdge *eUp = regUp->eUp; 595 GLUhalfEdge *eLo = regLo->eUp; 596 GLUvertex *orgUp = eUp->Org; 597 GLUvertex *orgLo = eLo->Org; 598 GLUvertex *dstUp = eUp->Dst; 599 GLUvertex *dstLo = eLo->Dst; 600 GLUdouble tMinUp, tMaxLo; 601 GLUvertex isect, *orgMin; 602 GLUhalfEdge *e; 603 604 assert( ! VertEq( dstLo, dstUp )); 605 assert( EdgeSign( dstUp, tess->event, orgUp 606 assert( EdgeSign( dstLo, tess->event, orgLo 607 assert( orgUp != tess->event && orgLo != tes 608 assert( ! regUp->fixUpperEdge && ! regLo->fi 609 610 if( orgUp == orgLo ) return TOOLS_GLU_FALSE; 611 612 tMinUp = GLU_MIN( orgUp->t, dstUp->t ); 613 tMaxLo = GLU_MAX( orgLo->t, dstLo->t ); 614 if( tMinUp > tMaxLo ) return TOOLS_GLU_FALSE 615 616 if( VertLeq( orgUp, orgLo )) { 617 if( EdgeSign( dstLo, orgUp, orgLo ) > 0 ) 618 } else { 619 if( EdgeSign( dstUp, orgLo, orgUp ) < 0 ) 620 } 621 622 /* At this point the edges intersect, at lea 623 DebugEvent( tess ); 624 625 __gl_edgeIntersect( dstUp, orgUp, dstLo, org 626 /* The following properties are guaranteed: 627 assert( GLU_MIN( orgUp->t, dstUp->t ) <= ise 628 assert( isect.t <= GLU_MAX( orgLo->t, dstLo- 629 assert( GLU_MIN( dstLo->s, dstUp->s ) <= ise 630 assert( isect.s <= GLU_MAX( orgLo->s, orgUp- 631 632 if( VertLeq( &isect, tess->event )) { 633 /* The intersection point lies slightly to 634 * so move it until it''s slightly to the 635 * (If we had perfect numerical precision, 636 * in the first place). The easiest and s 637 * replace the intersection by tess->event 638 */ 639 isect.s = tess->event->s; 640 isect.t = tess->event->t; 641 } 642 /* Similarly, if the computed intersection l 643 * rightmost origin (which should rarely hap 644 * unbelievable inefficiency on sufficiently 645 * (If you have the test program, try runnin 646 * "X zoom" option turned on). 647 */ 648 orgMin = VertLeq( orgUp, orgLo ) ? orgUp : o 649 if( VertLeq( orgMin, &isect )) { 650 isect.s = orgMin->s; 651 isect.t = orgMin->t; 652 } 653 654 if( VertEq( &isect, orgUp ) || VertEq( &isec 655 /* Easy case -- intersection at one of the 656 (void) static_CheckForRightSplice( tess, r 657 return TOOLS_GLU_FALSE; 658 } 659 660 if( (! VertEq( dstUp, tess->event ) 661 && EdgeSign( dstUp, tess->event, &isect ) 662 || (! VertEq( dstLo, tess->event ) 663 && EdgeSign( dstLo, tess->event, &isect ) 664 { 665 /* Very unusual -- the new upper or lower 666 * wrong side of the sweep event, or throu 667 * due to very small numerical errors in t 668 */ 669 if( dstLo == tess->event ) { 670 /* Splice dstLo into eUp, and process th 671 if (__gl_meshSplitEdge( eUp->Sym ) == NU 672 if ( !__gl_meshSplice( eLo->Sym, eUp ) ) 673 regUp = static_TopLeftRegion( regUp ); 674 if (regUp == NULL) longjmp(tess->env,1); 675 eUp = RegionBelow(regUp)->eUp; 676 static_FinishLeftRegions( tess, RegionBe 677 static_AddRightEdges( tess, regUp, eUp-> 678 return TOOLS_GLU_TRUE; 679 } 680 if( dstUp == tess->event ) { 681 /* Splice dstUp into eLo, and process th 682 if (__gl_meshSplitEdge( eLo->Sym ) == NU 683 if ( !__gl_meshSplice( eUp->Lnext, eLo-> 684 regLo = regUp; 685 regUp = static_TopRightRegion( regUp ); 686 e = RegionBelow(regUp)->eUp->Rprev; 687 regLo->eUp = eLo->Oprev; 688 eLo = static_FinishLeftRegions( tess, re 689 static_AddRightEdges( tess, regUp, eLo-> 690 return TOOLS_GLU_TRUE; 691 } 692 /* Special case: called from ConnectRightV 693 * edge passes on the wrong side of tess-> 694 * (and wait for ConnectRightVertex to spl 695 */ 696 if( EdgeSign( dstUp, tess->event, &isect ) 697 RegionAbove(regUp)->dirty = regUp->dirty 698 if (__gl_meshSplitEdge( eUp->Sym ) == NU 699 eUp->Org->s = tess->event->s; 700 eUp->Org->t = tess->event->t; 701 } 702 if( EdgeSign( dstLo, tess->event, &isect ) 703 regUp->dirty = regLo->dirty = TOOLS_GLU_ 704 if (__gl_meshSplitEdge( eLo->Sym ) == NU 705 eLo->Org->s = tess->event->s; 706 eLo->Org->t = tess->event->t; 707 } 708 /* leave the rest for ConnectRightVertex * 709 return TOOLS_GLU_FALSE; 710 } 711 712 /* General case -- split both edges, splice 713 * When we do the splice operation, the orde 714 * arbitrary as far as correctness goes. Ho 715 * creates a new face, the work done is prop 716 * the new face. We expect the faces in the 717 * the mesh (ie. eUp->Lface) to be smaller t 718 * unprocessed original contours (which will 719 */ 720 if (__gl_meshSplitEdge( eUp->Sym ) == NULL) 721 if (__gl_meshSplitEdge( eLo->Sym ) == NULL) 722 if ( !__gl_meshSplice( eLo->Oprev, eUp ) ) l 723 eUp->Org->s = isect.s; 724 eUp->Org->t = isect.t; 725 eUp->Org->pqHandle = pqInsert( tess->pq, eUp 726 if (eUp->Org->pqHandle == LONG_MAX) { 727 pqDeletePriorityQ(tess->pq); /* __gl_pqSo 728 tess->pq = NULL; 729 longjmp(tess->env,1); 730 } 731 static_GetIntersectData( tess, eUp->Org, org 732 RegionAbove(regUp)->dirty = regUp->dirty = r 733 return TOOLS_GLU_FALSE; 734 } 735 736 inline/*static*/ void static_WalkDirtyRegions( 737 /* 738 * When the upper or lower edge of any region 739 * marked "dirty". This routine walks through 740 * and makes sure that the dictionary invarian 741 * (see the comments at the beginning of this 742 * new dirty regions can be created as we make 743 * the invariants. 744 */ 745 { 746 ActiveRegion *regLo = RegionBelow(regUp); 747 GLUhalfEdge *eUp, *eLo; 748 749 for( ;; ) { 750 /* Find the lowest dirty region (we walk f 751 while( regLo->dirty ) { 752 regUp = regLo; 753 regLo = RegionBelow(regLo); 754 } 755 if( ! regUp->dirty ) { 756 regLo = regUp; 757 regUp = RegionAbove( regUp ); 758 if( regUp == NULL || ! regUp->dirty ) { 759 /* We've walked all the dirty regions */ 760 return; 761 } 762 } 763 regUp->dirty = TOOLS_GLU_FALSE; 764 eUp = regUp->eUp; 765 eLo = regLo->eUp; 766 767 if( eUp->Dst != eLo->Dst ) { 768 /* Check that the edge ordering is obeye 769 if( static_CheckForLeftSplice( tess, reg 770 771 /* If the upper or lower edge was marked fix 772 * we no longer need it (since these edges a 773 * vertices which otherwise have no right-go 774 */ 775 if( regLo->fixUpperEdge ) { 776 static_DeleteRegion( tess, regLo ); 777 if ( !__gl_meshDelete( eLo ) ) longjmp(tes 778 regLo = RegionBelow( regUp ); 779 eLo = regLo->eUp; 780 } else if( regUp->fixUpperEdge ) { 781 static_DeleteRegion( tess, regUp ); 782 if ( !__gl_meshDelete( eUp ) ) longjmp(tes 783 regUp = RegionAbove( regLo ); 784 eUp = regUp->eUp; 785 } 786 } 787 } 788 if( eUp->Org != eLo->Org ) { 789 if( eUp->Dst != eLo->Dst 790 && ! regUp->fixUpperEdge && ! regLo->fixUp 791 && (eUp->Dst == tess->event || eLo->Dst == 792 { 793 /* When all else fails in CheckForIntersect( 794 * as the intersection location. To make th 795 * that tess->event lie between the upper an 796 * that neither of these is marked fixUpperE 797 * case it might splice one of these edges i 798 * violate the invariant that fixable edges 799 * edge from their associated vertex). 800 */ 801 if( static_CheckForIntersect( tess, regUp )) 802 /* WalkDirtyRegions() was called recursive 803 return; 804 } 805 } else { 806 /* Even though we can't use CheckForIntersec 807 * may violate the dictionary edge ordering. 808 */ 809 (void) static_CheckForRightSplice( tess, reg 810 } 811 } 812 if( eUp->Org == eLo->Org && eUp->Dst == eL 813 /* A degenerate loop consisting of only 814 AddWinding( eLo, eUp ); 815 static_DeleteRegion( tess, regUp ); 816 if ( !__gl_meshDelete( eUp ) ) longjmp(t 817 regUp = RegionAbove( regLo ); 818 } 819 } 820 } 821 822 823 inline/*static*/ void static_ConnectRightVerte 824 GLUhalfEdge *eBottomLeft ) 825 /* 826 * Purpose: connect a "right" vertex vEvent (o 827 * to the unprocessed portion of the mesh. Si 828 * edges, two regions (one above vEvent and on 829 * into one. "regUp" is the upper of these tw 830 * 831 * There are two reasons for doing this (addin 832 * - if the two regions being merged are "ins 833 * to keep them separated (the combined reg 834 * - in any case, we must leave some record o 835 * so that we can merge vEvent with feature 836 * For example, maybe there is a vertical e 837 * the right of vEvent; we would like to sp 838 * 839 * However, we don't want to connect vEvent to 840 * want the new edge to cross any other edges; 841 * intersection vertices even when the input d 842 * (This is a bad thing; if the user's input d 843 * we don't want to generate any false interse 844 * 845 * Our eventual goal is to connect vEvent to t 846 * vertex of the combined region (the union of 847 * But because of unseen vertices with all rig 848 * new vertices which may be created by edge i 849 * know where that leftmost unprocessed vertex 850 * connect vEvent to the closest vertex of eit 851 * as "fixUpperEdge". This flag says to delet 852 * to the next processed vertex on the boundar 853 * Quite possibly the vertex we connected to w 854 * closest one, in which case we won''t need t 855 */ 856 { 857 GLUhalfEdge *eNew; 858 GLUhalfEdge *eTopLeft = eBottomLeft->Onext; 859 ActiveRegion *regLo = RegionBelow(regUp); 860 GLUhalfEdge *eUp = regUp->eUp; 861 GLUhalfEdge *eLo = regLo->eUp; 862 int degenerate = TOOLS_GLU_FALSE; 863 864 if( eUp->Dst != eLo->Dst ) { 865 (void) static_CheckForIntersect( tess, reg 866 } 867 868 /* Possible new degeneracies: upper or lower 869 * through vEvent, or may coincide with new 870 */ 871 if( VertEq( eUp->Org, tess->event )) { 872 if ( !__gl_meshSplice( eTopLeft->Oprev, eU 873 regUp = static_TopLeftRegion( regUp ); 874 if (regUp == NULL) longjmp(tess->env,1); 875 eTopLeft = RegionBelow( regUp )->eUp; 876 static_FinishLeftRegions( tess, RegionBelo 877 degenerate = TOOLS_GLU_TRUE; 878 } 879 if( VertEq( eLo->Org, tess->event )) { 880 if ( !__gl_meshSplice( eBottomLeft, eLo->O 881 eBottomLeft = static_FinishLeftRegions( te 882 degenerate = TOOLS_GLU_TRUE; 883 } 884 if( degenerate ) { 885 static_AddRightEdges( tess, regUp, eBottom 886 return; 887 } 888 889 /* Non-degenerate situation -- need to add a 890 * Connect to the closer of eLo->Org, eUp->O 891 */ 892 if( VertLeq( eLo->Org, eUp->Org )) { 893 eNew = eLo->Oprev; 894 } else { 895 eNew = eUp; 896 } 897 eNew = __gl_meshConnect( eBottomLeft->Lprev, 898 if (eNew == NULL) longjmp(tess->env,1); 899 900 /* Prevent cleanup, otherwise eNew might dis 901 * had a chance to mark it as a temporary ed 902 */ 903 static_AddRightEdges( tess, regUp, eNew, eNe 904 eNew->Sym->activeRegion->fixUpperEdge = TOOL 905 static_WalkDirtyRegions( tess, regUp ); 906 } 907 908 /* Because vertices at exactly the same locati 909 * before we process the sweep event, some deg 910 * However if someone eventually makes the mod 911 * merge features which are close together, th 912 * TOLERANCE_NONZERO will be useful. They wer 913 * code to merge identical vertices in the mai 914 */ 915 //#define TOLERANCE_NONZERO TOOLS_GLU_FALSE 916 917 inline/*static*/ void static_ConnectLeftDegene 918 ActiveRegion *regUp, GLUvertex *vEv 919 /* 920 * The event vertex lies exacty on an already- 921 * Adding the new vertex involves splicing it 922 * part of the mesh. 923 */ 924 { 925 GLUhalfEdge *e, *eTopLeft, *eTopRight, *eLas 926 ActiveRegion *reg; 927 928 e = regUp->eUp; 929 if( VertEq( e->Org, vEvent )) { 930 /* e->Org is an unprocessed vertex - just 931 * for e->Org to be pulled from the queue 932 */ 933 assert( /*TOLERANCE_NONZERO*/ TOOLS_GLU_FA 934 static_SpliceMergeVertices( tess, e, vEven 935 return; 936 } 937 938 if( ! VertEq( e->Dst, vEvent )) { 939 /* General case -- splice vEvent into edge 940 if (__gl_meshSplitEdge( e->Sym ) == NULL) 941 if( regUp->fixUpperEdge ) { 942 /* This edge was fixable -- delete unuse 943 if ( !__gl_meshDelete( e->Onext ) ) long 944 regUp->fixUpperEdge = TOOLS_GLU_FALSE; 945 } 946 if ( !__gl_meshSplice( vEvent->anEdge, e ) 947 static_SweepEvent( tess, vEvent ); /* recu 948 return; 949 } 950 951 /* vEvent coincides with e->Dst, which has a 952 * Splice in the additional right-going edge 953 */ 954 assert( /*TOLERANCE_NONZERO*/ TOOLS_GLU_FALS 955 regUp = static_TopRightRegion( regUp ); 956 reg = RegionBelow( regUp ); 957 eTopRight = reg->eUp->Sym; 958 eTopLeft = eLast = eTopRight->Onext; 959 if( reg->fixUpperEdge ) { 960 /* Here e->Dst has only a single fixable e 961 * We can delete it since now we have some 962 */ 963 assert( eTopLeft != eTopRight ); /* ther 964 static_DeleteRegion( tess, reg ); 965 if ( !__gl_meshDelete( eTopRight ) ) longj 966 eTopRight = eTopLeft->Oprev; 967 } 968 if ( !__gl_meshSplice( vEvent->anEdge, eTopR 969 if( ! EdgeGoesLeft( eTopLeft )) { 970 /* e->Dst had no left-going edges -- indic 971 eTopLeft = NULL; 972 } 973 static_AddRightEdges( tess, regUp, eTopRight 974 } 975 976 977 inline/*static*/ void static_ConnectLeftVertex 978 /* 979 * Purpose: connect a "left" vertex (one where 980 * to the processed portion of the mesh. Let 981 * containing vEvent, and let U and L be the u 982 * chains of R. There are two possibilities: 983 * 984 * - the normal case: split R into two regions 985 * the rightmost vertex of U or L lying to t 986 * 987 * - the degenerate case: if vEvent is close e 988 * merge vEvent into that edge chain. The s 989 * - merging with the rightmost vertex of U o 990 * - merging with the active edge of U or L 991 * - merging with an already-processed portio 992 */ 993 { 994 ActiveRegion *regUp, *regLo, *reg; 995 GLUhalfEdge *eUp, *eLo, *eNew; 996 ActiveRegion tmp; 997 998 /* assert( vEvent->anEdge->Onext->Onext == v 999 1000 /* Get a pointer to the active region conta 1001 tmp.eUp = vEvent->anEdge->Sym; 1002 /* __GL_DICTLISTKEY */ /* __gl_dictListSear 1003 regUp = (ActiveRegion *)dictKey( dictSearch 1004 regLo = RegionBelow( regUp ); 1005 eUp = regUp->eUp; 1006 eLo = regLo->eUp; 1007 1008 /* Try merging with U or L first */ 1009 if( EdgeSign( eUp->Dst, vEvent, eUp->Org ) 1010 static_ConnectLeftDegenerate( tess, regUp 1011 return; 1012 } 1013 1014 /* Connect vEvent to rightmost processed ve 1015 * e->Dst is the vertex that we will connec 1016 */ 1017 reg = VertLeq( eLo->Dst, eUp->Dst ) ? regUp 1018 1019 if( regUp->inside || reg->fixUpperEdge) { 1020 if( reg == regUp ) { 1021 eNew = __gl_meshConnect( vEvent->anEdge 1022 if (eNew == NULL) longjmp(tess->env,1); 1023 } else { 1024 GLUhalfEdge *tempHalfEdge= __gl_meshCon 1025 if (tempHalfEdge == NULL) longjmp(tess- 1026 1027 eNew = tempHalfEdge->Sym; 1028 } 1029 if( reg->fixUpperEdge ) { 1030 if ( !static_FixUpperEdge( reg, eNew ) 1031 } else { 1032 static_ComputeWinding( tess, static_Add 1033 } 1034 static_SweepEvent( tess, vEvent ); 1035 } else { 1036 /* The new vertex is in a region which do 1037 * We don''t need to connect this vertex 1038 */ 1039 static_AddRightEdges( tess, regUp, vEvent 1040 } 1041 } 1042 1043 1044 inline/*static*/ void static_SweepEvent( GLUt 1045 /* 1046 * Does everything necessary when the sweep l 1047 * Updates the mesh and the edge dictionary. 1048 */ 1049 { 1050 ActiveRegion *regUp, *reg; 1051 GLUhalfEdge *e, *eTopLeft, *eBottomLeft; 1052 1053 tess->event = vEvent; /* for access in Ed 1054 DebugEvent( tess ); 1055 1056 /* Check if this vertex is the right endpoi 1057 * already in the dictionary. In this case 1058 * time searching for the location to inser 1059 */ 1060 e = vEvent->anEdge; 1061 while( e->activeRegion == NULL ) { 1062 e = e->Onext; 1063 if( e == vEvent->anEdge ) { 1064 /* All edges go right -- not incident t 1065 static_ConnectLeftVertex( tess, vEvent 1066 return; 1067 } 1068 } 1069 1070 /* Processing consists of two phases: first 1071 * active regions where both the upper and 1072 * at vEvent (ie. vEvent is closing off the 1073 * We mark these faces "inside" or "outside 1074 * to their winding number, and delete the 1075 * This takes care of all the left-going ed 1076 */ 1077 regUp = static_TopLeftRegion( e->activeRegi 1078 if (regUp == NULL) longjmp(tess->env,1); 1079 reg = RegionBelow( regUp ); 1080 eTopLeft = reg->eUp; 1081 eBottomLeft = static_FinishLeftRegions( tes 1082 1083 /* Next we process all the right-going edge 1084 * involves adding the edges to the diction 1085 * associated "active regions" which record 1086 * regions between adjacent dictionary edge 1087 */ 1088 if( eBottomLeft->Onext == eTopLeft ) { 1089 /* No right-going edges -- add a temporar 1090 static_ConnectRightVertex( tess, regUp, e 1091 } else { 1092 static_AddRightEdges( tess, regUp, eBotto 1093 } 1094 } 1095 1096 1097 /* Make the sentinel coordinates big enough t 1098 * merged with real input features. (Even wi 1099 * input contour and the maximum tolerance of 1100 * done with coordinates larger than 3 * GLU_ 1101 */ 1102 //#define SENTINEL_COORD (4 * GLU_TESS_MAX_CO 1103 inline GLUdouble SENTINEL_COORD() { 1104 static const GLUdouble s_value = 4 * GLU_TE 1105 return s_value; 1106 } 1107 1108 inline/*static*/ void static_AddSentinel( GLU 1109 /* 1110 * We add two sentinel edges above and below 1111 * to avoid special cases at the top and bott 1112 */ 1113 { 1114 GLUhalfEdge *e; 1115 ActiveRegion *reg = (ActiveRegion *)memAllo 1116 if (reg == NULL) longjmp(tess->env,1); 1117 1118 e = __gl_meshMakeEdge( tess->mesh ); 1119 if (e == NULL) longjmp(tess->env,1); 1120 1121 e->Org->s = SENTINEL_COORD(); 1122 e->Org->t = t; 1123 e->Dst->s = -SENTINEL_COORD(); 1124 e->Dst->t = t; 1125 tess->event = e->Dst; /* initialize it */ 1126 1127 reg->eUp = e; 1128 reg->windingNumber = 0; 1129 reg->inside = TOOLS_GLU_FALSE; 1130 reg->fixUpperEdge = TOOLS_GLU_FALSE; 1131 reg->sentinel = TOOLS_GLU_TRUE; 1132 reg->dirty = TOOLS_GLU_FALSE; 1133 reg->nodeUp = dictInsert( tess->dict, reg ) 1134 if (reg->nodeUp == NULL) longjmp(tess->env, 1135 } 1136 1137 1138 inline/*static*/ void static_InitEdgeDict( GL 1139 /* 1140 * We maintain an ordering of edge intersecti 1141 * This order is maintained in a dynamic dict 1142 */ 1143 { 1144 /* __gl_dictListNewDict */ 1145 tess->dict = dictNewDict( tess, (int (*)(vo 1146 if (tess->dict == NULL) longjmp(tess->env,1 1147 1148 static_AddSentinel( tess, -SENTINEL_COORD() 1149 static_AddSentinel( tess, SENTINEL_COORD() 1150 } 1151 1152 1153 inline/*static*/ void static_DoneEdgeDict( GL 1154 { 1155 ActiveRegion *reg; 1156 #ifndef NDEBUG 1157 int fixedEdges = 0; 1158 #endif 1159 1160 /* __GL_DICTLISTKEY */ /* __GL_DICTLISTMIN 1161 while( (reg = (ActiveRegion *)dictKey( dict 1162 /* 1163 * At the end of all processing, the dict 1164 * only the two sentinel edges, plus at m 1165 * created by ConnectRightVertex(). 1166 */ 1167 if( ! reg->sentinel ) { 1168 assert( reg->fixUpperEdge ); 1169 //G.Barrand : fix a Coverity diagnostic : 1170 //assert( ++fixedEdges == 1 ); 1171 #ifndef NDEBUG 1172 fixedEdges++; 1173 #endif 1174 assert( fixedEdges == 1 ); 1175 //G.Barrand : end. 1176 } 1177 assert( reg->windingNumber == 0 ); 1178 static_DeleteRegion( tess, reg ); 1179 /* __gl_meshDelete( reg->eUp );*/ 1180 } 1181 dictDeleteDict( tess->dict ); /* __gl_dictL 1182 } 1183 1184 1185 inline/*static*/ void static_RemoveDegenerate 1186 /* 1187 * Remove zero-length edges, and contours wit 1188 */ 1189 { 1190 GLUhalfEdge *e, *eNext, *eLnext; 1191 GLUhalfEdge *eHead = &tess->mesh->eHead; 1192 1193 /*LINTED*/ 1194 for( e = eHead->next; e != eHead; e = eNext 1195 eNext = e->next; 1196 eLnext = e->Lnext; 1197 1198 if( VertEq( e->Org, e->Dst ) && e->Lnext- 1199 /* Zero-length edge, contour has at lea 1200 1201 static_SpliceMergeVertices( tess, eLnex 1202 if ( !__gl_meshDelete( e ) ) longjmp(te 1203 e = eLnext; 1204 eLnext = e->Lnext; 1205 } 1206 if( eLnext->Lnext == e ) { 1207 /* Degenerate contour (one or two edges 1208 1209 if( eLnext != e ) { 1210 if( eLnext == eNext || eLnext == eNext->Sym 1211 if ( !__gl_meshDelete( eLnext ) ) longjmp(t 1212 } 1213 if( e == eNext || e == eNext->Sym ) { e 1214 if ( !__gl_meshDelete( e ) ) longjmp(te 1215 } 1216 } 1217 } 1218 1219 inline/*static*/ int static_InitPriorityQ( GL 1220 /* 1221 * Insert all vertices into the priority queu 1222 * order in which vertices cross the sweep li 1223 */ 1224 { 1225 PriorityQ *pq; 1226 GLUvertex *v, *vHead; 1227 1228 /* __gl_pqSortNewPriorityQ */ 1229 pq = tess->pq = pqNewPriorityQ( (int (*)(PQ 1230 if (pq == NULL) return 0; 1231 1232 vHead = &tess->mesh->vHead; 1233 for( v = vHead->next; v != vHead; v = v->ne 1234 v->pqHandle = pqInsert( pq, v ); /* __gl_ 1235 if (v->pqHandle == LONG_MAX) break; 1236 } 1237 if (v != vHead || !pqInit( pq ) ) { /* __gl 1238 pqDeletePriorityQ(tess->pq); /* __gl_pqS 1239 tess->pq = NULL; 1240 return 0; 1241 } 1242 1243 return 1; 1244 } 1245 1246 1247 inline/*static*/ void static_DonePriorityQ( G 1248 { 1249 pqDeletePriorityQ( tess->pq ); /* __gl_pqSo 1250 } 1251 1252 1253 inline/*static*/ int static_RemoveDegenerateF 1254 /* 1255 * Delete any degenerate faces with only two 1256 * will catch almost all of these, but it won 1257 * produced by splice operations on already-p 1258 * The two places this can happen are in Fini 1259 * we splice in a "temporary" edge produced b 1260 * and in CheckForLeftSplice(), where we spli 1261 * edges to ensure that our dictionary invari 1262 * by numerical errors. 1263 * 1264 * In both these cases it is *very* dangerous 1265 * edge at the time, since one of the routine 1266 * will sometimes be keeping a pointer to tha 1267 */ 1268 { 1269 GLUface *f, *fNext; 1270 GLUhalfEdge *e; 1271 1272 /*LINTED*/ 1273 for( f = mesh->fHead.next; f != &mesh->fHea 1274 fNext = f->next; 1275 e = f->anEdge; 1276 assert( e->Lnext != e ); 1277 1278 if( e->Lnext->Lnext == e ) { 1279 /* A face with only two edges */ 1280 AddWinding( e->Onext, e ); 1281 if ( !__gl_meshDelete( e ) ) return 0; 1282 } 1283 } 1284 return 1; 1285 } 1286 1287 inline int __gl_computeInterior( GLUtesselato 1288 /* 1289 * __gl_computeInterior( tess ) computes the 1290 * by the given contours, and further subdivi 1291 * into regions. Each region is marked "insi 1292 * to the polygon, according to the rule give 1293 * Each interior region is guaranteed be mono 1294 */ 1295 { 1296 GLUvertex *v, *vNext; 1297 1298 tess->fatalError = TOOLS_GLU_FALSE; 1299 1300 /* Each vertex defines an event for our swe 1301 * all the vertices in a priority queue. E 1302 * lexicographic order, ie. 1303 * 1304 * e1 < e2 iff e1.x < e2.x || (e1.x == e 1305 */ 1306 static_RemoveDegenerateEdges( tess ); 1307 if ( !static_InitPriorityQ( tess ) ) return 1308 static_InitEdgeDict( tess ); 1309 1310 /* __gl_pqSortExtractMin */ 1311 while( (v = (GLUvertex *)pqExtractMin( tess 1312 for( ;; ) { 1313 vNext = (GLUvertex *)pqMinimum( tess->p 1314 if( vNext == NULL || ! VertEq( vNext, v 1315 1316 /* Merge together all vertices at exact 1317 * This is more efficient than processi 1318 * simplifies the code (see ConnectLeft 1319 * important for correct handling of ce 1320 * For example, suppose there are two i 1321 * that belong to different contours (s 1322 * be processed by separate sweep event 1323 * crosses A and B from above. When A 1324 * at its intersection point with C. H 1325 * so when we insert B we may compute a 1326 * intersection point. This might leav 1327 * gap between them. This kind of erro 1328 * when using boundary extraction (GLU_ 1329 */ 1330 vNext = (GLUvertex *)pqExtractMin( tess 1331 static_SpliceMergeVertices( tess, v->an 1332 } 1333 static_SweepEvent( tess, v ); 1334 } 1335 1336 /* Set tess->event for debugging purposes * 1337 /* __GL_DICTLISTKEY */ /* __GL_DICTLISTMIN 1338 tess->event = ((ActiveRegion *) dictKey( di 1339 DebugEvent( tess ); 1340 static_DoneEdgeDict( tess ); 1341 static_DonePriorityQ( tess ); 1342 1343 if ( !static_RemoveDegenerateFaces( tess->m 1344 __gl_meshCheckMesh( tess->mesh ); 1345 1346 return 1; 1347 } 1348 1349 #endif