| 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