2 * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008)
3 * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved.
5 * Permission is hereby granted, free of charge, to any person obtaining a
6 * copy of this software and associated documentation files (the "Software"),
7 * to deal in the Software without restriction, including without limitation
8 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
9 * and/or sell copies of the Software, and to permit persons to whom the
10 * Software is furnished to do so, subject to the following conditions:
12 * The above copyright notice including the dates of first publication and
13 * either this permission notice or a reference to
14 * http://oss.sgi.com/projects/FreeB/
15 * shall be included in all copies or substantial portions of the Software.
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
18 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
20 * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
21 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
22 * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
25 * Except as contained in this notice, the name of Silicon Graphics, Inc.
26 * shall not be used in advertising or otherwise to promote the sale, use or
27 * other dealings in this Software without prior written authorization from
28 * Silicon Graphics, Inc.
31 ** Author: Eric Veach, July 1994.
38 //#include <setjmp.h> /* longjmp */
39 //#include <limits.h> /* LONG_MAX */
45 //#include "priorityq.h"
56 #ifdef FOR_TRITE_TEST_PROGRAM
57 extern void DebugEvent( GLUtesselator
*tess
);
59 #define DebugEvent( tess )
63 * Invariants for the Edge Dictionary.
64 * - each pair of adjacent edges e2=Succ(e1) satisfies EdgeLeq(e1,e2)
65 * at any valid location of the sweep event
66 * - if EdgeLeq(e2,e1) as well (at any valid sweep event), then e1 and e2
67 * share a common endpoint
68 * - for each e, e->Dst has been processed, but not e->Org
69 * - each edge e satisfies VertLeq(e->Dst,event) && VertLeq(event,e->Org)
70 * where "event" is the current sweep line event.
71 * - no edge e has zero length
73 * Invariants for the Mesh (the processed portion).
74 * - the portion of the mesh left of the sweep line is a planar graph,
75 * ie. there is *some* way to embed it in the plane
76 * - no processed edge has zero length
77 * - no two processed vertices have identical coordinates
78 * - each "inside" region is monotone, ie. can be broken into two chains
79 * of monotonically increasing vertices according to VertLeq(v1,v2)
80 * - a non-invariant: these chains may intersect (very slightly)
82 * Invariants for the Sweep.
83 * - if none of the edges incident to the event vertex have an activeRegion
84 * (ie. none of these edges are in the edge dictionary), then the vertex
85 * has only right-going edges.
86 * - if an edge is marked "fixUpperEdge" (it is a temporary edge introduced
87 * by ConnectRightVertex), then it is the only right-going edge from
88 * its associated vertex. (This says that these edges exist only
89 * when it is necessary.)
94 #define MAX(x,y) ((x) >= (y) ? (x) : (y))
95 #define MIN(x,y) ((x) <= (y) ? (x) : (y))
97 /* When we merge two edges into one, we need to compute the combined
98 * winding of the new edge.
100 #define AddWinding(eDst,eSrc) (eDst->winding += eSrc->winding, \
101 eDst->Sym->winding += eSrc->Sym->winding)
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
,
110 * Both edges must be directed from right to left (this is the canonical
111 * direction for the upper edge of each region).
113 * The strategy is to evaluate a "t" value for each edge at the
114 * current sweep line position, given by tess->event. The calculations
115 * are designed to be very stable, but of course they are not perfect.
117 * Special case: if both edge destinations are at the sweep event,
118 * we sort the edges by slope (they would otherwise compare equally).
121 GLUvertex
*event
= tess
->event
;
122 GLUhalfEdge
*e1
, *e2
;
128 if( e1
->Dst
== event
) {
129 if( e2
->Dst
== event
) {
130 /* Two edges right of the sweep line which meet at the sweep event.
131 * Sort them by slope.
133 if( VertLeq( e1
->Org
, e2
->Org
)) {
134 return EdgeSign( e2
->Dst
, e1
->Org
, e2
->Org
) <= 0;
136 return EdgeSign( e1
->Dst
, e2
->Org
, e1
->Org
) >= 0;
138 return EdgeSign( e2
->Dst
, event
, e2
->Org
) <= 0;
140 if( e2
->Dst
== event
) {
141 return EdgeSign( e1
->Dst
, event
, e1
->Org
) >= 0;
144 /* General case - compute signed distance *from* e1, e2 to event */
145 t1
= EdgeEval( e1
->Dst
, event
, e1
->Org
);
146 t2
= EdgeEval( e2
->Dst
, event
, e2
->Org
);
151 static void DeleteRegion( GLUtesselator
*tess
, ActiveRegion
*reg
)
153 if( reg
->fixUpperEdge
) {
154 /* It was created with zero winding number, so it better be
155 * deleted with zero winding number (ie. it better not get merged
158 assert( reg
->eUp
->winding
== 0 );
160 reg
->eUp
->activeRegion
= NULL
;
161 dictDelete( tess
->dict
, reg
->nodeUp
); /* __gl_dictListDelete */
166 static int FixUpperEdge( ActiveRegion
*reg
, GLUhalfEdge
*newEdge
)
168 * Replace an upper edge which needs fixing (see ConnectRightVertex).
171 assert( reg
->fixUpperEdge
);
172 if ( !__gl_meshDelete( reg
->eUp
) ) return 0;
173 reg
->fixUpperEdge
= FALSE
;
175 newEdge
->activeRegion
= reg
;
180 static ActiveRegion
*TopLeftRegion( ActiveRegion
*reg
)
182 GLUvertex
*org
= reg
->eUp
->Org
;
185 /* Find the region above the uppermost edge with the same origin */
187 reg
= RegionAbove( reg
);
188 } while( reg
->eUp
->Org
== org
);
190 /* If the edge above was a temporary edge introduced by ConnectRightVertex,
191 * now is the time to fix it.
193 if( reg
->fixUpperEdge
) {
194 e
= __gl_meshConnect( RegionBelow(reg
)->eUp
->Sym
, reg
->eUp
->Lnext
);
195 if (e
== NULL
) return NULL
;
196 if ( !FixUpperEdge( reg
, e
) ) return NULL
;
197 reg
= RegionAbove( reg
);
202 static ActiveRegion
*TopRightRegion( ActiveRegion
*reg
)
204 GLUvertex
*dst
= reg
->eUp
->Dst
;
206 /* Find the region above the uppermost edge with the same destination */
208 reg
= RegionAbove( reg
);
209 } while( reg
->eUp
->Dst
== dst
);
213 static ActiveRegion
*AddRegionBelow( GLUtesselator
*tess
,
214 ActiveRegion
*regAbove
,
215 GLUhalfEdge
*eNewUp
)
217 * Add a new active region to the sweep line, *somewhere* below "regAbove"
218 * (according to where the new edge belongs in the sweep-line dictionary).
219 * The upper edge of the new region will be "eNewUp".
220 * Winding number and "inside" flag are not updated.
223 ActiveRegion
*regNew
= (ActiveRegion
*)memAlloc( sizeof( ActiveRegion
));
224 if (regNew
== NULL
) longjmp(tess
->env
,1);
226 regNew
->eUp
= eNewUp
;
227 /* __gl_dictListInsertBefore */
228 regNew
->nodeUp
= dictInsertBefore( tess
->dict
, regAbove
->nodeUp
, regNew
);
229 if (regNew
->nodeUp
== NULL
) longjmp(tess
->env
,1);
230 regNew
->fixUpperEdge
= FALSE
;
231 regNew
->sentinel
= FALSE
;
232 regNew
->dirty
= FALSE
;
234 eNewUp
->activeRegion
= regNew
;
238 static GLboolean
IsWindingInside( GLUtesselator
*tess
, int n
)
240 switch( tess
->windingRule
) {
241 case GLU_TESS_WINDING_ODD
:
243 case GLU_TESS_WINDING_NONZERO
:
245 case GLU_TESS_WINDING_POSITIVE
:
247 case GLU_TESS_WINDING_NEGATIVE
:
249 case GLU_TESS_WINDING_ABS_GEQ_TWO
:
250 return (n
>= 2) || (n
<= -2);
255 return GL_FALSE
; /* avoid compiler complaints */
259 static void ComputeWinding( GLUtesselator
*tess
, ActiveRegion
*reg
)
261 reg
->windingNumber
= RegionAbove(reg
)->windingNumber
+ reg
->eUp
->winding
;
262 reg
->inside
= IsWindingInside( tess
, reg
->windingNumber
);
266 static void FinishRegion( GLUtesselator
*tess
, ActiveRegion
*reg
)
268 * Delete a region from the sweep line. This happens when the upper
269 * and lower chains of a region meet (at a vertex on the sweep line).
270 * The "inside" flag is copied to the appropriate mesh face (we could
271 * not do this before -- since the structure of the mesh is always
272 * changing, this face may not have even existed until now).
275 GLUhalfEdge
*e
= reg
->eUp
;
276 GLUface
*f
= e
->Lface
;
278 f
->inside
= reg
->inside
;
279 f
->anEdge
= e
; /* optimization for __gl_meshTessellateMonoRegion() */
280 DeleteRegion( tess
, reg
);
284 static GLUhalfEdge
*FinishLeftRegions( GLUtesselator
*tess
,
285 ActiveRegion
*regFirst
, ActiveRegion
*regLast
)
287 * We are given a vertex with one or more left-going edges. All affected
288 * edges should be in the edge dictionary. Starting at regFirst->eUp,
289 * we walk down deleting all regions where both edges have the same
290 * origin vOrg. At the same time we copy the "inside" flag from the
291 * active region to the face, since at this point each face will belong
292 * to at most one region (this was not necessarily true until this point
293 * in the sweep). The walk stops at the region above regLast; if regLast
294 * is NULL we walk as far as possible. At the same time we relink the
295 * mesh if necessary, so that the ordering of edges around vOrg is the
296 * same as in the dictionary.
299 ActiveRegion
*reg
, *regPrev
;
300 GLUhalfEdge
*e
, *ePrev
;
303 ePrev
= regFirst
->eUp
;
304 while( regPrev
!= regLast
) {
305 regPrev
->fixUpperEdge
= FALSE
; /* placement was OK */
306 reg
= RegionBelow( regPrev
);
308 if( e
->Org
!= ePrev
->Org
) {
309 if( ! reg
->fixUpperEdge
) {
310 /* Remove the last left-going edge. Even though there are no further
311 * edges in the dictionary with this origin, there may be further
312 * such edges in the mesh (if we are adding left edges to a vertex
313 * that has already been processed). Thus it is important to call
314 * FinishRegion rather than just DeleteRegion.
316 FinishRegion( tess
, regPrev
);
319 /* If the edge below was a temporary edge introduced by
320 * ConnectRightVertex, now is the time to fix it.
322 e
= __gl_meshConnect( ePrev
->Lprev
, e
->Sym
);
323 if (e
== NULL
) longjmp(tess
->env
,1);
324 if ( !FixUpperEdge( reg
, e
) ) longjmp(tess
->env
,1);
327 /* Relink edges so that ePrev->Onext == e */
328 if( ePrev
->Onext
!= e
) {
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
,
341 GLUhalfEdge
*eFirst
, GLUhalfEdge
*eLast
, GLUhalfEdge
*eTopLeft
,
344 * Purpose: insert right-going edges into the edge dictionary, and update
345 * winding numbers and mesh connectivity appropriately. All right-going
346 * edges share a common origin vOrg. Edges are inserted CCW starting at
347 * eFirst; the last edge inserted is eLast->Oprev. If vOrg has any
348 * left-going edges already processed, then eTopLeft must be the edge
349 * such that an imaginary upward vertical segment from vOrg would be
350 * contained between eTopLeft->Oprev and eTopLeft; otherwise eTopLeft
354 ActiveRegion
*reg
, *regPrev
;
355 GLUhalfEdge
*e
, *ePrev
;
356 int firstTime
= TRUE
;
358 /* Insert the new right-going edges in the dictionary */
361 assert( VertLeq( e
->Org
, e
->Dst
));
362 AddRegionBelow( tess
, regUp
, e
->Sym
);
364 } while ( e
!= eLast
);
366 /* Walk *all* right-going edges from e->Org, in the dictionary order,
367 * updating the winding numbers of each region, and re-linking the mesh
368 * edges to match the dictionary ordering (if necessary).
370 if( eTopLeft
== NULL
) {
371 eTopLeft
= RegionBelow( regUp
)->eUp
->Rprev
;
376 reg
= RegionBelow( regPrev
);
378 if( e
->Org
!= ePrev
->Org
) break;
380 if( e
->Onext
!= ePrev
) {
381 /* Unlink e from its current position, and relink below ePrev */
382 if ( !__gl_meshSplice( e
->Oprev
, e
) ) longjmp(tess
->env
,1);
383 if ( !__gl_meshSplice( ePrev
->Oprev
, e
) ) longjmp(tess
->env
,1);
385 /* Compute the winding number and "inside" flag for the new regions */
386 reg
->windingNumber
= regPrev
->windingNumber
- e
->winding
;
387 reg
->inside
= IsWindingInside( tess
, reg
->windingNumber
);
389 /* Check for two outgoing edges with same slope -- process these
390 * before any intersection tests (see example in __gl_computeInterior).
392 regPrev
->dirty
= TRUE
;
393 if( ! firstTime
&& CheckForRightSplice( tess
, regPrev
)) {
394 AddWinding( e
, ePrev
);
395 DeleteRegion( tess
, regPrev
);
396 if ( !__gl_meshDelete( ePrev
) ) longjmp(tess
->env
,1);
402 regPrev
->dirty
= TRUE
;
403 assert( regPrev
->windingNumber
- e
->winding
== reg
->windingNumber
);
406 /* Check for intersections between newly adjacent edges. */
407 WalkDirtyRegions( tess
, regPrev
);
412 static void CallCombine( GLUtesselator
*tess
, GLUvertex
*isect
,
413 void *data
[4], GLfloat weights
[4], int needed
)
417 /* Copy coord data in case the callback changes it. */
418 coords
[0] = isect
->coords
[0];
419 coords
[1] = isect
->coords
[1];
420 coords
[2] = isect
->coords
[2];
423 CALL_COMBINE_OR_COMBINE_DATA( coords
, data
, weights
, &isect
->data
);
424 if( isect
->data
== NULL
) {
426 isect
->data
= data
[0];
427 } else if( ! tess
->fatalError
) {
428 /* The only way fatal error is when two edges are found to intersect,
429 * but the user has not provided the callback necessary to handle
430 * generated intersection points.
432 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_NEED_COMBINE_CALLBACK
);
433 tess
->fatalError
= TRUE
;
438 static void SpliceMergeVertices( GLUtesselator
*tess
, GLUhalfEdge
*e1
,
441 * Two vertices with idential coordinates are combined into one.
442 * e1->Org is kept, while e2->Org is discarded.
445 void *data
[4] = { NULL
, NULL
, NULL
, NULL
};
446 GLfloat weights
[4] = { 0.5, 0.5, 0.0, 0.0 };
448 data
[0] = e1
->Org
->data
;
449 data
[1] = e2
->Org
->data
;
450 CallCombine( tess
, e1
->Org
, data
, weights
, FALSE
);
451 if ( !__gl_meshSplice( e1
, e2
) ) longjmp(tess
->env
,1);
454 static void VertexWeights( GLUvertex
*isect
, GLUvertex
*org
, GLUvertex
*dst
,
457 * Find some weights which describe how the intersection vertex is
458 * a linear combination of "org" and "dest". Each of the two edges
459 * which generated "isect" is allocated 50% of the weight; each edge
460 * splits the weight between its org and dst according to the
461 * relative distance to "isect".
464 GLdouble t1
= VertL1dist( org
, isect
);
465 GLdouble t2
= VertL1dist( dst
, isect
);
467 weights
[0] = 0.5 * t2
/ (t1
+ t2
);
468 weights
[1] = 0.5 * t1
/ (t1
+ t2
);
469 isect
->coords
[0] += weights
[0]*org
->coords
[0] + weights
[1]*dst
->coords
[0];
470 isect
->coords
[1] += weights
[0]*org
->coords
[1] + weights
[1]*dst
->coords
[1];
471 isect
->coords
[2] += weights
[0]*org
->coords
[2] + weights
[1]*dst
->coords
[2];
475 static void GetIntersectData( GLUtesselator
*tess
, GLUvertex
*isect
,
476 GLUvertex
*orgUp
, GLUvertex
*dstUp
,
477 GLUvertex
*orgLo
, GLUvertex
*dstLo
)
479 * We've computed a new intersection point, now we need a "data" pointer
480 * from the user so that we can refer to this new vertex in the
481 * rendering callbacks.
487 data
[0] = orgUp
->data
;
488 data
[1] = dstUp
->data
;
489 data
[2] = orgLo
->data
;
490 data
[3] = dstLo
->data
;
492 isect
->coords
[0] = isect
->coords
[1] = isect
->coords
[2] = 0;
493 VertexWeights( isect
, orgUp
, dstUp
, &weights
[0] );
494 VertexWeights( isect
, orgLo
, dstLo
, &weights
[2] );
496 CallCombine( tess
, isect
, data
, weights
, TRUE
);
499 static int CheckForRightSplice( GLUtesselator
*tess
, ActiveRegion
*regUp
)
501 * Check the upper and lower edge of "regUp", to make sure that the
502 * eUp->Org is above eLo, or eLo->Org is below eUp (depending on which
503 * origin is leftmost).
505 * The main purpose is to splice right-going edges with the same
506 * dest vertex and nearly identical slopes (ie. we can't distinguish
507 * the slopes numerically). However the splicing can also help us
508 * to recover from numerical errors. For example, suppose at one
509 * point we checked eUp and eLo, and decided that eUp->Org is barely
510 * above eLo. Then later, we split eLo into two edges (eg. from
511 * a splice operation like this one). This can change the result of
512 * our test so that now eUp->Org is incident to eLo, or barely below it.
513 * We must correct this condition to maintain the dictionary invariants.
515 * One possibility is to check these edges for intersection again
516 * (ie. CheckForIntersect). This is what we do if possible. However
517 * CheckForIntersect requires that tess->event lies between eUp and eLo,
518 * so that it has something to fall back on when the intersection
519 * calculation gives us an unusable answer. So, for those cases where
520 * we can't check for intersection, this routine fixes the problem
521 * by just splicing the offending vertex into the other edge.
522 * This is a guaranteed solution, no matter how degenerate things get.
523 * Basically this is a combinatorial solution to a numerical problem.
526 ActiveRegion
*regLo
= RegionBelow(regUp
);
527 GLUhalfEdge
*eUp
= regUp
->eUp
;
528 GLUhalfEdge
*eLo
= regLo
->eUp
;
530 if( VertLeq( eUp
->Org
, eLo
->Org
)) {
531 if( EdgeSign( eLo
->Dst
, eUp
->Org
, eLo
->Org
) > 0 ) return FALSE
;
533 /* eUp->Org appears to be below eLo */
534 if( ! VertEq( eUp
->Org
, eLo
->Org
)) {
535 /* Splice eUp->Org into eLo */
536 if ( __gl_meshSplitEdge( eLo
->Sym
) == NULL
) longjmp(tess
->env
,1);
537 if ( !__gl_meshSplice( eUp
, eLo
->Oprev
) ) longjmp(tess
->env
,1);
538 regUp
->dirty
= regLo
->dirty
= TRUE
;
540 } else if( eUp
->Org
!= eLo
->Org
) {
541 /* merge the two vertices, discarding eUp->Org */
542 pqDelete( tess
->pq
, eUp
->Org
->pqHandle
); /* __gl_pqSortDelete */
543 SpliceMergeVertices( tess
, eLo
->Oprev
, eUp
);
546 if( EdgeSign( eUp
->Dst
, eLo
->Org
, eUp
->Org
) < 0 ) return FALSE
;
548 /* eLo->Org appears to be above eUp, so splice eLo->Org into eUp */
549 RegionAbove(regUp
)->dirty
= regUp
->dirty
= TRUE
;
550 if (__gl_meshSplitEdge( eUp
->Sym
) == NULL
) longjmp(tess
->env
,1);
551 if ( !__gl_meshSplice( eLo
->Oprev
, eUp
) ) longjmp(tess
->env
,1);
556 static int CheckForLeftSplice( GLUtesselator
*tess
, ActiveRegion
*regUp
)
558 * Check the upper and lower edge of "regUp", to make sure that the
559 * eUp->Dst is above eLo, or eLo->Dst is below eUp (depending on which
560 * destination is rightmost).
562 * Theoretically, this should always be true. However, splitting an edge
563 * into two pieces can change the results of previous tests. For example,
564 * suppose at one point we checked eUp and eLo, and decided that eUp->Dst
565 * is barely above eLo. Then later, we split eLo into two edges (eg. from
566 * a splice operation like this one). This can change the result of
567 * the test so that now eUp->Dst is incident to eLo, or barely below it.
568 * We must correct this condition to maintain the dictionary invariants
569 * (otherwise new edges might get inserted in the wrong place in the
570 * dictionary, and bad stuff will happen).
572 * We fix the problem by just splicing the offending vertex into the
576 ActiveRegion
*regLo
= RegionBelow(regUp
);
577 GLUhalfEdge
*eUp
= regUp
->eUp
;
578 GLUhalfEdge
*eLo
= regLo
->eUp
;
581 assert( ! VertEq( eUp
->Dst
, eLo
->Dst
));
583 if( VertLeq( eUp
->Dst
, eLo
->Dst
)) {
584 if( EdgeSign( eUp
->Dst
, eLo
->Dst
, eUp
->Org
) < 0 ) return FALSE
;
586 /* eLo->Dst is above eUp, so splice eLo->Dst into eUp */
587 RegionAbove(regUp
)->dirty
= regUp
->dirty
= TRUE
;
588 e
= __gl_meshSplitEdge( eUp
);
589 if (e
== NULL
) longjmp(tess
->env
,1);
590 if ( !__gl_meshSplice( eLo
->Sym
, e
) ) longjmp(tess
->env
,1);
591 e
->Lface
->inside
= regUp
->inside
;
593 if( EdgeSign( eLo
->Dst
, eUp
->Dst
, eLo
->Org
) > 0 ) return FALSE
;
595 /* eUp->Dst is below eLo, so splice eUp->Dst into eLo */
596 regUp
->dirty
= regLo
->dirty
= TRUE
;
597 e
= __gl_meshSplitEdge( eLo
);
598 if (e
== NULL
) longjmp(tess
->env
,1);
599 if ( !__gl_meshSplice( eUp
->Lnext
, eLo
->Sym
) ) longjmp(tess
->env
,1);
600 e
->Rface
->inside
= regUp
->inside
;
606 static int CheckForIntersect( GLUtesselator
*tess
, ActiveRegion
*regUp
)
608 * Check the upper and lower edges of the given region to see if
609 * they intersect. If so, create the intersection and add it
610 * to the data structures.
612 * Returns TRUE if adding the new intersection resulted in a recursive
613 * call to AddRightEdges(); in this case all "dirty" regions have been
614 * checked for intersections, and possibly regUp has been deleted.
617 ActiveRegion
*regLo
= RegionBelow(regUp
);
618 GLUhalfEdge
*eUp
= regUp
->eUp
;
619 GLUhalfEdge
*eLo
= regLo
->eUp
;
620 GLUvertex
*orgUp
= eUp
->Org
;
621 GLUvertex
*orgLo
= eLo
->Org
;
622 GLUvertex
*dstUp
= eUp
->Dst
;
623 GLUvertex
*dstLo
= eLo
->Dst
;
624 GLdouble tMinUp
, tMaxLo
;
625 GLUvertex isect
, *orgMin
;
628 assert( ! VertEq( dstLo
, dstUp
));
629 assert( EdgeSign( dstUp
, tess
->event
, orgUp
) <= 0 );
630 assert( EdgeSign( dstLo
, tess
->event
, orgLo
) >= 0 );
631 assert( orgUp
!= tess
->event
&& orgLo
!= tess
->event
);
632 assert( ! regUp
->fixUpperEdge
&& ! regLo
->fixUpperEdge
);
634 if( orgUp
== orgLo
) return FALSE
; /* right endpoints are the same */
636 tMinUp
= MIN( orgUp
->t
, dstUp
->t
);
637 tMaxLo
= MAX( orgLo
->t
, dstLo
->t
);
638 if( tMinUp
> tMaxLo
) return FALSE
; /* t ranges do not overlap */
640 if( VertLeq( orgUp
, orgLo
)) {
641 if( EdgeSign( dstLo
, orgUp
, orgLo
) > 0 ) return FALSE
;
643 if( EdgeSign( dstUp
, orgLo
, orgUp
) < 0 ) return FALSE
;
646 /* At this point the edges intersect, at least marginally */
649 __gl_edgeIntersect( dstUp
, orgUp
, dstLo
, orgLo
, &isect
);
650 /* The following properties are guaranteed: */
651 assert( MIN( orgUp
->t
, dstUp
->t
) <= isect
.t
);
652 assert( isect
.t
<= MAX( orgLo
->t
, dstLo
->t
));
653 assert( MIN( dstLo
->s
, dstUp
->s
) <= isect
.s
);
654 assert( isect
.s
<= MAX( orgLo
->s
, orgUp
->s
));
656 if( VertLeq( &isect
, tess
->event
)) {
657 /* The intersection point lies slightly to the left of the sweep line,
658 * so move it until it''s slightly to the right of the sweep line.
659 * (If we had perfect numerical precision, this would never happen
660 * in the first place). The easiest and safest thing to do is
661 * replace the intersection by tess->event.
663 isect
.s
= tess
->event
->s
;
664 isect
.t
= tess
->event
->t
;
666 /* Similarly, if the computed intersection lies to the right of the
667 * rightmost origin (which should rarely happen), it can cause
668 * unbelievable inefficiency on sufficiently degenerate inputs.
669 * (If you have the test program, try running test54.d with the
670 * "X zoom" option turned on).
672 orgMin
= VertLeq( orgUp
, orgLo
) ? orgUp
: orgLo
;
673 if( VertLeq( orgMin
, &isect
)) {
678 if( VertEq( &isect
, orgUp
) || VertEq( &isect
, orgLo
)) {
679 /* Easy case -- intersection at one of the right endpoints */
680 (void) CheckForRightSplice( tess
, regUp
);
684 if( (! VertEq( dstUp
, tess
->event
)
685 && EdgeSign( dstUp
, tess
->event
, &isect
) >= 0)
686 || (! VertEq( dstLo
, tess
->event
)
687 && EdgeSign( dstLo
, tess
->event
, &isect
) <= 0 ))
689 /* Very unusual -- the new upper or lower edge would pass on the
690 * wrong side of the sweep event, or through it. This can happen
691 * due to very small numerical errors in the intersection calculation.
693 if( dstLo
== tess
->event
) {
694 /* Splice dstLo into eUp, and process the new region(s) */
695 if (__gl_meshSplitEdge( eUp
->Sym
) == NULL
) longjmp(tess
->env
,1);
696 if ( !__gl_meshSplice( eLo
->Sym
, eUp
) ) longjmp(tess
->env
,1);
697 regUp
= TopLeftRegion( regUp
);
698 if (regUp
== NULL
) longjmp(tess
->env
,1);
699 eUp
= RegionBelow(regUp
)->eUp
;
700 FinishLeftRegions( tess
, RegionBelow(regUp
), regLo
);
701 AddRightEdges( tess
, regUp
, eUp
->Oprev
, eUp
, eUp
, TRUE
);
704 if( dstUp
== tess
->event
) {
705 /* Splice dstUp into eLo, and process the new region(s) */
706 if (__gl_meshSplitEdge( eLo
->Sym
) == NULL
) longjmp(tess
->env
,1);
707 if ( !__gl_meshSplice( eUp
->Lnext
, eLo
->Oprev
) ) longjmp(tess
->env
,1);
709 regUp
= TopRightRegion( regUp
);
710 e
= RegionBelow(regUp
)->eUp
->Rprev
;
711 regLo
->eUp
= eLo
->Oprev
;
712 eLo
= FinishLeftRegions( tess
, regLo
, NULL
);
713 AddRightEdges( tess
, regUp
, eLo
->Onext
, eUp
->Rprev
, e
, TRUE
);
716 /* Special case: called from ConnectRightVertex. If either
717 * edge passes on the wrong side of tess->event, split it
718 * (and wait for ConnectRightVertex to splice it appropriately).
720 if( EdgeSign( dstUp
, tess
->event
, &isect
) >= 0 ) {
721 RegionAbove(regUp
)->dirty
= regUp
->dirty
= TRUE
;
722 if (__gl_meshSplitEdge( eUp
->Sym
) == NULL
) longjmp(tess
->env
,1);
723 eUp
->Org
->s
= tess
->event
->s
;
724 eUp
->Org
->t
= tess
->event
->t
;
726 if( EdgeSign( dstLo
, tess
->event
, &isect
) <= 0 ) {
727 regUp
->dirty
= regLo
->dirty
= TRUE
;
728 if (__gl_meshSplitEdge( eLo
->Sym
) == NULL
) longjmp(tess
->env
,1);
729 eLo
->Org
->s
= tess
->event
->s
;
730 eLo
->Org
->t
= tess
->event
->t
;
732 /* leave the rest for ConnectRightVertex */
736 /* General case -- split both edges, splice into new vertex.
737 * When we do the splice operation, the order of the arguments is
738 * arbitrary as far as correctness goes. However, when the operation
739 * creates a new face, the work done is proportional to the size of
740 * the new face. We expect the faces in the processed part of
741 * the mesh (ie. eUp->Lface) to be smaller than the faces in the
742 * unprocessed original contours (which will be eLo->Oprev->Lface).
744 if (__gl_meshSplitEdge( eUp
->Sym
) == NULL
) longjmp(tess
->env
,1);
745 if (__gl_meshSplitEdge( eLo
->Sym
) == NULL
) longjmp(tess
->env
,1);
746 if ( !__gl_meshSplice( eLo
->Oprev
, eUp
) ) longjmp(tess
->env
,1);
747 eUp
->Org
->s
= isect
.s
;
748 eUp
->Org
->t
= isect
.t
;
749 eUp
->Org
->pqHandle
= pqInsert( tess
->pq
, eUp
->Org
); /* __gl_pqSortInsert */
750 if (eUp
->Org
->pqHandle
== LONG_MAX
) {
751 pqDeletePriorityQ(tess
->pq
); /* __gl_pqSortDeletePriorityQ */
753 longjmp(tess
->env
,1);
755 GetIntersectData( tess
, eUp
->Org
, orgUp
, dstUp
, orgLo
, dstLo
);
756 RegionAbove(regUp
)->dirty
= regUp
->dirty
= regLo
->dirty
= TRUE
;
760 static void WalkDirtyRegions( GLUtesselator
*tess
, ActiveRegion
*regUp
)
762 * When the upper or lower edge of any region changes, the region is
763 * marked "dirty". This routine walks through all the dirty regions
764 * and makes sure that the dictionary invariants are satisfied
765 * (see the comments at the beginning of this file). Of course
766 * new dirty regions can be created as we make changes to restore
770 ActiveRegion
*regLo
= RegionBelow(regUp
);
771 GLUhalfEdge
*eUp
, *eLo
;
774 /* Find the lowest dirty region (we walk from the bottom up). */
775 while( regLo
->dirty
) {
777 regLo
= RegionBelow(regLo
);
779 if( ! regUp
->dirty
) {
781 regUp
= RegionAbove( regUp
);
782 if( regUp
== NULL
|| ! regUp
->dirty
) {
783 /* We've walked all the dirty regions */
787 regUp
->dirty
= FALSE
;
791 if( eUp
->Dst
!= eLo
->Dst
) {
792 /* Check that the edge ordering is obeyed at the Dst vertices. */
793 if( CheckForLeftSplice( tess
, regUp
)) {
795 /* If the upper or lower edge was marked fixUpperEdge, then
796 * we no longer need it (since these edges are needed only for
797 * vertices which otherwise have no right-going edges).
799 if( regLo
->fixUpperEdge
) {
800 DeleteRegion( tess
, regLo
);
801 if ( !__gl_meshDelete( eLo
) ) longjmp(tess
->env
,1);
802 regLo
= RegionBelow( regUp
);
804 } else if( regUp
->fixUpperEdge
) {
805 DeleteRegion( tess
, regUp
);
806 if ( !__gl_meshDelete( eUp
) ) longjmp(tess
->env
,1);
807 regUp
= RegionAbove( regLo
);
812 if( eUp
->Org
!= eLo
->Org
) {
813 if( eUp
->Dst
!= eLo
->Dst
814 && ! regUp
->fixUpperEdge
&& ! regLo
->fixUpperEdge
815 && (eUp
->Dst
== tess
->event
|| eLo
->Dst
== tess
->event
) )
817 /* When all else fails in CheckForIntersect(), it uses tess->event
818 * as the intersection location. To make this possible, it requires
819 * that tess->event lie between the upper and lower edges, and also
820 * that neither of these is marked fixUpperEdge (since in the worst
821 * case it might splice one of these edges into tess->event, and
822 * violate the invariant that fixable edges are the only right-going
823 * edge from their associated vertex).
825 if( CheckForIntersect( tess
, regUp
)) {
826 /* WalkDirtyRegions() was called recursively; we're done */
830 /* Even though we can't use CheckForIntersect(), the Org vertices
831 * may violate the dictionary edge ordering. Check and correct this.
833 (void) CheckForRightSplice( tess
, regUp
);
836 if( eUp
->Org
== eLo
->Org
&& eUp
->Dst
== eLo
->Dst
) {
837 /* A degenerate loop consisting of only two edges -- delete it. */
838 AddWinding( eLo
, eUp
);
839 DeleteRegion( tess
, regUp
);
840 if ( !__gl_meshDelete( eUp
) ) longjmp(tess
->env
,1);
841 regUp
= RegionAbove( regLo
);
847 static void ConnectRightVertex( GLUtesselator
*tess
, ActiveRegion
*regUp
,
848 GLUhalfEdge
*eBottomLeft
)
850 * Purpose: connect a "right" vertex vEvent (one where all edges go left)
851 * to the unprocessed portion of the mesh. Since there are no right-going
852 * edges, two regions (one above vEvent and one below) are being merged
853 * into one. "regUp" is the upper of these two regions.
855 * There are two reasons for doing this (adding a right-going edge):
856 * - if the two regions being merged are "inside", we must add an edge
857 * to keep them separated (the combined region would not be monotone).
858 * - in any case, we must leave some record of vEvent in the dictionary,
859 * so that we can merge vEvent with features that we have not seen yet.
860 * For example, maybe there is a vertical edge which passes just to
861 * the right of vEvent; we would like to splice vEvent into this edge.
863 * However, we don't want to connect vEvent to just any vertex. We don''t
864 * want the new edge to cross any other edges; otherwise we will create
865 * intersection vertices even when the input data had no self-intersections.
866 * (This is a bad thing; if the user's input data has no intersections,
867 * we don't want to generate any false intersections ourselves.)
869 * Our eventual goal is to connect vEvent to the leftmost unprocessed
870 * vertex of the combined region (the union of regUp and regLo).
871 * But because of unseen vertices with all right-going edges, and also
872 * new vertices which may be created by edge intersections, we don''t
873 * know where that leftmost unprocessed vertex is. In the meantime, we
874 * connect vEvent to the closest vertex of either chain, and mark the region
875 * as "fixUpperEdge". This flag says to delete and reconnect this edge
876 * to the next processed vertex on the boundary of the combined region.
877 * Quite possibly the vertex we connected to will turn out to be the
878 * closest one, in which case we won''t need to make any changes.
882 GLUhalfEdge
*eTopLeft
= eBottomLeft
->Onext
;
883 ActiveRegion
*regLo
= RegionBelow(regUp
);
884 GLUhalfEdge
*eUp
= regUp
->eUp
;
885 GLUhalfEdge
*eLo
= regLo
->eUp
;
886 int degenerate
= FALSE
;
888 if( eUp
->Dst
!= eLo
->Dst
) {
889 (void) CheckForIntersect( tess
, regUp
);
892 /* Possible new degeneracies: upper or lower edge of regUp may pass
893 * through vEvent, or may coincide with new intersection vertex
895 if( VertEq( eUp
->Org
, tess
->event
)) {
896 if ( !__gl_meshSplice( eTopLeft
->Oprev
, eUp
) ) longjmp(tess
->env
,1);
897 regUp
= TopLeftRegion( regUp
);
898 if (regUp
== NULL
) longjmp(tess
->env
,1);
899 eTopLeft
= RegionBelow( regUp
)->eUp
;
900 FinishLeftRegions( tess
, RegionBelow(regUp
), regLo
);
903 if( VertEq( eLo
->Org
, tess
->event
)) {
904 if ( !__gl_meshSplice( eBottomLeft
, eLo
->Oprev
) ) longjmp(tess
->env
,1);
905 eBottomLeft
= FinishLeftRegions( tess
, regLo
, NULL
);
909 AddRightEdges( tess
, regUp
, eBottomLeft
->Onext
, eTopLeft
, eTopLeft
, TRUE
);
913 /* Non-degenerate situation -- need to add a temporary, fixable edge.
914 * Connect to the closer of eLo->Org, eUp->Org.
916 if( VertLeq( eLo
->Org
, eUp
->Org
)) {
921 eNew
= __gl_meshConnect( eBottomLeft
->Lprev
, eNew
);
922 if (eNew
== NULL
) longjmp(tess
->env
,1);
924 /* Prevent cleanup, otherwise eNew might disappear before we've even
925 * had a chance to mark it as a temporary edge.
927 AddRightEdges( tess
, regUp
, eNew
, eNew
->Onext
, eNew
->Onext
, FALSE
);
928 eNew
->Sym
->activeRegion
->fixUpperEdge
= TRUE
;
929 WalkDirtyRegions( tess
, regUp
);
932 /* Because vertices at exactly the same location are merged together
933 * before we process the sweep event, some degenerate cases can't occur.
934 * However if someone eventually makes the modifications required to
935 * merge features which are close together, the cases below marked
936 * TOLERANCE_NONZERO will be useful. They were debugged before the
937 * code to merge identical vertices in the main loop was added.
939 #define TOLERANCE_NONZERO FALSE
941 static void ConnectLeftDegenerate( GLUtesselator
*tess
,
942 ActiveRegion
*regUp
, GLUvertex
*vEvent
)
944 * The event vertex lies exacty on an already-processed edge or vertex.
945 * Adding the new vertex involves splicing it into the already-processed
949 GLUhalfEdge
*e
, *eTopLeft
, *eTopRight
, *eLast
;
953 if( VertEq( e
->Org
, vEvent
)) {
954 /* e->Org is an unprocessed vertex - just combine them, and wait
955 * for e->Org to be pulled from the queue
957 assert( TOLERANCE_NONZERO
);
958 SpliceMergeVertices( tess
, e
, vEvent
->anEdge
);
962 if( ! VertEq( e
->Dst
, vEvent
)) {
963 /* General case -- splice vEvent into edge e which passes through it */
964 if (__gl_meshSplitEdge( e
->Sym
) == NULL
) longjmp(tess
->env
,1);
965 if( regUp
->fixUpperEdge
) {
966 /* This edge was fixable -- delete unused portion of original edge */
967 if ( !__gl_meshDelete( e
->Onext
) ) longjmp(tess
->env
,1);
968 regUp
->fixUpperEdge
= FALSE
;
970 if ( !__gl_meshSplice( vEvent
->anEdge
, e
) ) longjmp(tess
->env
,1);
971 SweepEvent( tess
, vEvent
); /* recurse */
975 /* vEvent coincides with e->Dst, which has already been processed.
976 * Splice in the additional right-going edges.
978 assert( TOLERANCE_NONZERO
);
979 regUp
= TopRightRegion( regUp
);
980 reg
= RegionBelow( regUp
);
981 eTopRight
= reg
->eUp
->Sym
;
982 eTopLeft
= eLast
= eTopRight
->Onext
;
983 if( reg
->fixUpperEdge
) {
984 /* Here e->Dst has only a single fixable edge going right.
985 * We can delete it since now we have some real right-going edges.
987 assert( eTopLeft
!= eTopRight
); /* there are some left edges too */
988 DeleteRegion( tess
, reg
);
989 if ( !__gl_meshDelete( eTopRight
) ) longjmp(tess
->env
,1);
990 eTopRight
= eTopLeft
->Oprev
;
992 if ( !__gl_meshSplice( vEvent
->anEdge
, eTopRight
) ) longjmp(tess
->env
,1);
993 if( ! EdgeGoesLeft( eTopLeft
)) {
994 /* e->Dst had no left-going edges -- indicate this to AddRightEdges() */
997 AddRightEdges( tess
, regUp
, eTopRight
->Onext
, eLast
, eTopLeft
, TRUE
);
1001 static void ConnectLeftVertex( GLUtesselator
*tess
, GLUvertex
*vEvent
)
1003 * Purpose: connect a "left" vertex (one where both edges go right)
1004 * to the processed portion of the mesh. Let R be the active region
1005 * containing vEvent, and let U and L be the upper and lower edge
1006 * chains of R. There are two possibilities:
1008 * - the normal case: split R into two regions, by connecting vEvent to
1009 * the rightmost vertex of U or L lying to the left of the sweep line
1011 * - the degenerate case: if vEvent is close enough to U or L, we
1012 * merge vEvent into that edge chain. The subcases are:
1013 * - merging with the rightmost vertex of U or L
1014 * - merging with the active edge of U or L
1015 * - merging with an already-processed portion of U or L
1018 ActiveRegion
*regUp
, *regLo
, *reg
;
1019 GLUhalfEdge
*eUp
, *eLo
, *eNew
;
1022 /* assert( vEvent->anEdge->Onext->Onext == vEvent->anEdge ); */
1024 /* Get a pointer to the active region containing vEvent */
1025 tmp
.eUp
= vEvent
->anEdge
->Sym
;
1026 /* __GL_DICTLISTKEY */ /* __gl_dictListSearch */
1027 regUp
= (ActiveRegion
*)dictKey( dictSearch( tess
->dict
, &tmp
));
1028 regLo
= RegionBelow( regUp
);
1032 /* Try merging with U or L first */
1033 if( EdgeSign( eUp
->Dst
, vEvent
, eUp
->Org
) == 0 ) {
1034 ConnectLeftDegenerate( tess
, regUp
, vEvent
);
1038 /* Connect vEvent to rightmost processed vertex of either chain.
1039 * e->Dst is the vertex that we will connect to vEvent.
1041 reg
= VertLeq( eLo
->Dst
, eUp
->Dst
) ? regUp
: regLo
;
1043 if( regUp
->inside
|| reg
->fixUpperEdge
) {
1044 if( reg
== regUp
) {
1045 eNew
= __gl_meshConnect( vEvent
->anEdge
->Sym
, eUp
->Lnext
);
1046 if (eNew
== NULL
) longjmp(tess
->env
,1);
1048 GLUhalfEdge
*tempHalfEdge
= __gl_meshConnect( eLo
->Dnext
, vEvent
->anEdge
);
1049 if (tempHalfEdge
== NULL
) longjmp(tess
->env
,1);
1051 eNew
= tempHalfEdge
->Sym
;
1053 if( reg
->fixUpperEdge
) {
1054 if ( !FixUpperEdge( reg
, eNew
) ) longjmp(tess
->env
,1);
1056 ComputeWinding( tess
, AddRegionBelow( tess
, regUp
, eNew
));
1058 SweepEvent( tess
, vEvent
);
1060 /* The new vertex is in a region which does not belong to the polygon.
1061 * We don''t need to connect this vertex to the rest of the mesh.
1063 AddRightEdges( tess
, regUp
, vEvent
->anEdge
, vEvent
->anEdge
, NULL
, TRUE
);
1068 static void SweepEvent( GLUtesselator
*tess
, GLUvertex
*vEvent
)
1070 * Does everything necessary when the sweep line crosses a vertex.
1071 * Updates the mesh and the edge dictionary.
1074 ActiveRegion
*regUp
, *reg
;
1075 GLUhalfEdge
*e
, *eTopLeft
, *eBottomLeft
;
1077 tess
->event
= vEvent
; /* for access in EdgeLeq() */
1080 /* Check if this vertex is the right endpoint of an edge that is
1081 * already in the dictionary. In this case we don't need to waste
1082 * time searching for the location to insert new edges.
1085 while( e
->activeRegion
== NULL
) {
1087 if( e
== vEvent
->anEdge
) {
1088 /* All edges go right -- not incident to any processed edges */
1089 ConnectLeftVertex( tess
, vEvent
);
1094 /* Processing consists of two phases: first we "finish" all the
1095 * active regions where both the upper and lower edges terminate
1096 * at vEvent (ie. vEvent is closing off these regions).
1097 * We mark these faces "inside" or "outside" the polygon according
1098 * to their winding number, and delete the edges from the dictionary.
1099 * This takes care of all the left-going edges from vEvent.
1101 regUp
= TopLeftRegion( e
->activeRegion
);
1102 if (regUp
== NULL
) longjmp(tess
->env
,1);
1103 reg
= RegionBelow( regUp
);
1104 eTopLeft
= reg
->eUp
;
1105 eBottomLeft
= FinishLeftRegions( tess
, reg
, NULL
);
1107 /* Next we process all the right-going edges from vEvent. This
1108 * involves adding the edges to the dictionary, and creating the
1109 * associated "active regions" which record information about the
1110 * regions between adjacent dictionary edges.
1112 if( eBottomLeft
->Onext
== eTopLeft
) {
1113 /* No right-going edges -- add a temporary "fixable" edge */
1114 ConnectRightVertex( tess
, regUp
, eBottomLeft
);
1116 AddRightEdges( tess
, regUp
, eBottomLeft
->Onext
, eTopLeft
, eTopLeft
, TRUE
);
1121 /* Make the sentinel coordinates big enough that they will never be
1122 * merged with real input features. (Even with the largest possible
1123 * input contour and the maximum tolerance of 1.0, no merging will be
1124 * done with coordinates larger than 3 * GLU_TESS_MAX_COORD).
1126 #define SENTINEL_COORD (4 * GLU_TESS_MAX_COORD)
1128 static void AddSentinel( GLUtesselator
*tess
, GLdouble t
)
1130 * We add two sentinel edges above and below all other edges,
1131 * to avoid special cases at the top and bottom.
1135 ActiveRegion
*reg
= (ActiveRegion
*)memAlloc( sizeof( ActiveRegion
));
1136 if (reg
== NULL
) longjmp(tess
->env
,1);
1138 e
= __gl_meshMakeEdge( tess
->mesh
);
1139 if (e
== NULL
) longjmp(tess
->env
,1);
1141 e
->Org
->s
= SENTINEL_COORD
;
1143 e
->Dst
->s
= -SENTINEL_COORD
;
1145 tess
->event
= e
->Dst
; /* initialize it */
1148 reg
->windingNumber
= 0;
1149 reg
->inside
= FALSE
;
1150 reg
->fixUpperEdge
= FALSE
;
1151 reg
->sentinel
= TRUE
;
1153 reg
->nodeUp
= dictInsert( tess
->dict
, reg
); /* __gl_dictListInsertBefore */
1154 if (reg
->nodeUp
== NULL
) longjmp(tess
->env
,1);
1158 static void InitEdgeDict( GLUtesselator
*tess
)
1160 * We maintain an ordering of edge intersections with the sweep line.
1161 * This order is maintained in a dynamic dictionary.
1164 /* __gl_dictListNewDict */
1165 tess
->dict
= dictNewDict( tess
, (int (*)(void *, DictKey
, DictKey
)) EdgeLeq
);
1166 if (tess
->dict
== NULL
) longjmp(tess
->env
,1);
1168 AddSentinel( tess
, -SENTINEL_COORD
);
1169 AddSentinel( tess
, SENTINEL_COORD
);
1173 static void DoneEdgeDict( GLUtesselator
*tess
)
1180 /* __GL_DICTLISTKEY */ /* __GL_DICTLISTMIN */
1181 while( (reg
= (ActiveRegion
*)dictKey( dictMin( tess
->dict
))) != NULL
) {
1183 * At the end of all processing, the dictionary should contain
1184 * only the two sentinel edges, plus at most one "fixable" edge
1185 * created by ConnectRightVertex().
1187 if( ! reg
->sentinel
) {
1188 assert( reg
->fixUpperEdge
);
1189 assert( ++fixedEdges
== 1 );
1191 assert( reg
->windingNumber
== 0 );
1192 DeleteRegion( tess
, reg
);
1193 /* __gl_meshDelete( reg->eUp );*/
1195 dictDeleteDict( tess
->dict
); /* __gl_dictListDeleteDict */
1199 static void RemoveDegenerateEdges( GLUtesselator
*tess
)
1201 * Remove zero-length edges, and contours with fewer than 3 vertices.
1204 GLUhalfEdge
*e
, *eNext
, *eLnext
;
1205 GLUhalfEdge
*eHead
= &tess
->mesh
->eHead
;
1208 for( e
= eHead
->next
; e
!= eHead
; e
= eNext
) {
1212 if( VertEq( e
->Org
, e
->Dst
) && e
->Lnext
->Lnext
!= e
) {
1213 /* Zero-length edge, contour has at least 3 edges */
1215 SpliceMergeVertices( tess
, eLnext
, e
); /* deletes e->Org */
1216 if ( !__gl_meshDelete( e
) ) longjmp(tess
->env
,1); /* e is a self-loop */
1220 if( eLnext
->Lnext
== e
) {
1221 /* Degenerate contour (one or two edges) */
1224 if( eLnext
== eNext
|| eLnext
== eNext
->Sym
) { eNext
= eNext
->next
; }
1225 if ( !__gl_meshDelete( eLnext
) ) longjmp(tess
->env
,1);
1227 if( e
== eNext
|| e
== eNext
->Sym
) { eNext
= eNext
->next
; }
1228 if ( !__gl_meshDelete( e
) ) longjmp(tess
->env
,1);
1233 static int InitPriorityQ( GLUtesselator
*tess
)
1235 * Insert all vertices into the priority queue which determines the
1236 * order in which vertices cross the sweep line.
1240 GLUvertex
*v
, *vHead
;
1242 /* __gl_pqSortNewPriorityQ */
1243 pq
= tess
->pq
= pqNewPriorityQ( (int (*)(PQkey
, PQkey
)) __gl_vertLeq
);
1244 if (pq
== NULL
) return 0;
1246 vHead
= &tess
->mesh
->vHead
;
1247 for( v
= vHead
->next
; v
!= vHead
; v
= v
->next
) {
1248 v
->pqHandle
= pqInsert( pq
, v
); /* __gl_pqSortInsert */
1249 if (v
->pqHandle
== LONG_MAX
) break;
1251 if (v
!= vHead
|| !pqInit( pq
) ) { /* __gl_pqSortInit */
1252 pqDeletePriorityQ(tess
->pq
); /* __gl_pqSortDeletePriorityQ */
1261 static void DonePriorityQ( GLUtesselator
*tess
)
1263 pqDeletePriorityQ( tess
->pq
); /* __gl_pqSortDeletePriorityQ */
1267 static int RemoveDegenerateFaces( GLUmesh
*mesh
)
1269 * Delete any degenerate faces with only two edges. WalkDirtyRegions()
1270 * will catch almost all of these, but it won't catch degenerate faces
1271 * produced by splice operations on already-processed edges.
1272 * The two places this can happen are in FinishLeftRegions(), when
1273 * we splice in a "temporary" edge produced by ConnectRightVertex(),
1274 * and in CheckForLeftSplice(), where we splice already-processed
1275 * edges to ensure that our dictionary invariants are not violated
1276 * by numerical errors.
1278 * In both these cases it is *very* dangerous to delete the offending
1279 * edge at the time, since one of the routines further up the stack
1280 * will sometimes be keeping a pointer to that edge.
1287 for( f
= mesh
->fHead
.next
; f
!= &mesh
->fHead
; f
= fNext
) {
1290 assert( e
->Lnext
!= e
);
1292 if( e
->Lnext
->Lnext
== e
) {
1293 /* A face with only two edges */
1294 AddWinding( e
->Onext
, e
);
1295 if ( !__gl_meshDelete( e
) ) return 0;
1301 int __gl_computeInterior( GLUtesselator
*tess
)
1303 * __gl_computeInterior( tess ) computes the planar arrangement specified
1304 * by the given contours, and further subdivides this arrangement
1305 * into regions. Each region is marked "inside" if it belongs
1306 * to the polygon, according to the rule given by tess->windingRule.
1307 * Each interior region is guaranteed be monotone.
1310 GLUvertex
*v
, *vNext
;
1312 tess
->fatalError
= FALSE
;
1314 /* Each vertex defines an event for our sweep line. Start by inserting
1315 * all the vertices in a priority queue. Events are processed in
1316 * lexicographic order, ie.
1318 * e1 < e2 iff e1.x < e2.x || (e1.x == e2.x && e1.y < e2.y)
1320 RemoveDegenerateEdges( tess
);
1321 if ( !InitPriorityQ( tess
) ) return 0; /* if error */
1322 InitEdgeDict( tess
);
1324 /* __gl_pqSortExtractMin */
1325 while( (v
= (GLUvertex
*)pqExtractMin( tess
->pq
)) != NULL
) {
1327 vNext
= (GLUvertex
*)pqMinimum( tess
->pq
); /* __gl_pqSortMinimum */
1328 if( vNext
== NULL
|| ! VertEq( vNext
, v
)) break;
1330 /* Merge together all vertices at exactly the same location.
1331 * This is more efficient than processing them one at a time,
1332 * simplifies the code (see ConnectLeftDegenerate), and is also
1333 * important for correct handling of certain degenerate cases.
1334 * For example, suppose there are two identical edges A and B
1335 * that belong to different contours (so without this code they would
1336 * be processed by separate sweep events). Suppose another edge C
1337 * crosses A and B from above. When A is processed, we split it
1338 * at its intersection point with C. However this also splits C,
1339 * so when we insert B we may compute a slightly different
1340 * intersection point. This might leave two edges with a small
1341 * gap between them. This kind of error is especially obvious
1342 * when using boundary extraction (GLU_TESS_BOUNDARY_ONLY).
1344 vNext
= (GLUvertex
*)pqExtractMin( tess
->pq
); /* __gl_pqSortExtractMin*/
1345 SpliceMergeVertices( tess
, v
->anEdge
, vNext
->anEdge
);
1347 SweepEvent( tess
, v
);
1350 /* Set tess->event for debugging purposes */
1351 /* __GL_DICTLISTKEY */ /* __GL_DICTLISTMIN */
1352 tess
->event
= ((ActiveRegion
*) dictKey( dictMin( tess
->dict
)))->eUp
->Org
;
1354 DoneEdgeDict( tess
);
1355 DonePriorityQ( tess
);
1357 if ( !RemoveDegenerateFaces( tess
->mesh
) ) return 0;
1358 __gl_meshCheckMesh( tess
->mesh
);