2 ** License Applicability. Except to the extent portions of this file are
3 ** made subject to an alternative license as permitted in the SGI Free
4 ** Software License B, Version 1.1 (the "License"), the contents of this
5 ** file are subject only to the provisions of the License. You may not use
6 ** this file except in compliance with the License. You may obtain a copy
7 ** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600
8 ** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at:
10 ** http://oss.sgi.com/projects/FreeB
12 ** Note that, as provided in the License, the Software is distributed on an
13 ** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS
14 ** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND
15 ** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A
16 ** PARTICULAR PURPOSE, AND NON-INFRINGEMENT.
18 ** Original Code. The Original Code is: OpenGL Sample Implementation,
19 ** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics,
20 ** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc.
21 ** Copyright in any portions created by third parties is as indicated
22 ** elsewhere herein. All Rights Reserved.
24 ** Additional Notice Provisions: The application programming interfaces
25 ** established by SGI in conjunction with the Original Code are The
26 ** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released
27 ** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version
28 ** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X
29 ** Window System(R) (Version 1.3), released October 19, 1998. This software
30 ** was created using the OpenGL(R) version 1.2.1 Sample Implementation
31 ** published by SGI, but has not been independently verified as being
32 ** compliant with the OpenGL(R) version 1.2.1 Specification.
36 ** Author: Eric Veach, July 1994.
43 #include <setjmp.h> /* longjmp */
44 #include <limits.h> /* LONG_MAX */
50 #include "priorityq.h"
57 #ifdef FOR_TRITE_TEST_PROGRAM
58 extern void DebugEvent( GLUtesselator
*tess
);
60 #define DebugEvent( tess )
64 * Invariants for the Edge Dictionary.
65 * - each pair of adjacent edges e2=Succ(e1) satisfies EdgeLeq(e1,e2)
66 * at any valid location of the sweep event
67 * - if EdgeLeq(e2,e1) as well (at any valid sweep event), then e1 and e2
68 * share a common endpoint
69 * - for each e, e->Dst has been processed, but not e->Org
70 * - each edge e satisfies VertLeq(e->Dst,event) && VertLeq(event,e->Org)
71 * where "event" is the current sweep line event.
72 * - no edge e has zero length
74 * Invariants for the Mesh (the processed portion).
75 * - the portion of the mesh left of the sweep line is a planar graph,
76 * ie. there is *some* way to embed it in the plane
77 * - no processed edge has zero length
78 * - no two processed vertices have identical coordinates
79 * - each "inside" region is monotone, ie. can be broken into two chains
80 * of monotonically increasing vertices according to VertLeq(v1,v2)
81 * - a non-invariant: these chains may intersect (very slightly)
83 * Invariants for the Sweep.
84 * - if none of the edges incident to the event vertex have an activeRegion
85 * (ie. none of these edges are in the edge dictionary), then the vertex
86 * has only right-going edges.
87 * - if an edge is marked "fixUpperEdge" (it is a temporary edge introduced
88 * by ConnectRightVertex), then it is the only right-going edge from
89 * its associated vertex. (This says that these edges exist only
90 * when it is necessary.)
95 #define MAX(x,y) ((x) >= (y) ? (x) : (y))
96 #define MIN(x,y) ((x) <= (y) ? (x) : (y))
98 /* When we merge two edges into one, we need to compute the combined
99 * winding of the new edge.
101 #define AddWinding(eDst,eSrc) (eDst->winding += eSrc->winding, \
102 eDst->Sym->winding += eSrc->Sym->winding)
104 static void SweepEvent( GLUtesselator
*tess
, GLUvertex
*vEvent
);
105 static void WalkDirtyRegions( GLUtesselator
*tess
, ActiveRegion
*regUp
);
106 static int CheckForRightSplice( GLUtesselator
*tess
, ActiveRegion
*regUp
);
108 static int EdgeLeq( GLUtesselator
*tess
, ActiveRegion
*reg1
,
111 * Both edges must be directed from right to left (this is the canonical
112 * direction for the upper edge of each region).
114 * The strategy is to evaluate a "t" value for each edge at the
115 * current sweep line position, given by tess->event. The calculations
116 * are designed to be very stable, but of course they are not perfect.
118 * Special case: if both edge destinations are at the sweep event,
119 * we sort the edges by slope (they would otherwise compare equally).
122 GLUvertex
*event
= tess
->event
;
123 GLUhalfEdge
*e1
, *e2
;
129 if( e1
->Dst
== event
) {
130 if( e2
->Dst
== event
) {
131 /* Two edges right of the sweep line which meet at the sweep event.
132 * Sort them by slope.
134 if( VertLeq( e1
->Org
, e2
->Org
)) {
135 return EdgeSign( e2
->Dst
, e1
->Org
, e2
->Org
) <= 0;
137 return EdgeSign( e1
->Dst
, e2
->Org
, e1
->Org
) >= 0;
139 return EdgeSign( e2
->Dst
, event
, e2
->Org
) <= 0;
141 if( e2
->Dst
== event
) {
142 return EdgeSign( e1
->Dst
, event
, e1
->Org
) >= 0;
145 /* General case - compute signed distance *from* e1, e2 to event */
146 t1
= EdgeEval( e1
->Dst
, event
, e1
->Org
);
147 t2
= EdgeEval( e2
->Dst
, event
, e2
->Org
);
152 static void DeleteRegion( GLUtesselator
*tess
, ActiveRegion
*reg
)
154 if( reg
->fixUpperEdge
) {
155 /* It was created with zero winding number, so it better be
156 * deleted with zero winding number (ie. it better not get merged
159 assert( reg
->eUp
->winding
== 0 );
161 reg
->eUp
->activeRegion
= NULL
;
162 dictDelete( tess
->dict
, reg
->nodeUp
); /* __gl_dictListDelete */
167 static int FixUpperEdge( ActiveRegion
*reg
, GLUhalfEdge
*newEdge
)
169 * Replace an upper edge which needs fixing (see ConnectRightVertex).
172 assert( reg
->fixUpperEdge
);
173 if ( !__gl_meshDelete( reg
->eUp
) ) return 0;
174 reg
->fixUpperEdge
= FALSE
;
176 newEdge
->activeRegion
= reg
;
181 static ActiveRegion
*TopLeftRegion( ActiveRegion
*reg
)
183 GLUvertex
*org
= reg
->eUp
->Org
;
186 /* Find the region above the uppermost edge with the same origin */
188 reg
= RegionAbove( reg
);
189 } while( reg
->eUp
->Org
== org
);
191 /* If the edge above was a temporary edge introduced by ConnectRightVertex,
192 * now is the time to fix it.
194 if( reg
->fixUpperEdge
) {
195 e
= __gl_meshConnect( RegionBelow(reg
)->eUp
->Sym
, reg
->eUp
->Lnext
);
196 if (e
== NULL
) return NULL
;
197 if ( !FixUpperEdge( reg
, e
) ) return NULL
;
198 reg
= RegionAbove( reg
);
203 static ActiveRegion
*TopRightRegion( ActiveRegion
*reg
)
205 GLUvertex
*dst
= reg
->eUp
->Dst
;
207 /* Find the region above the uppermost edge with the same destination */
209 reg
= RegionAbove( reg
);
210 } while( reg
->eUp
->Dst
== dst
);
214 static ActiveRegion
*AddRegionBelow( GLUtesselator
*tess
,
215 ActiveRegion
*regAbove
,
216 GLUhalfEdge
*eNewUp
)
218 * Add a new active region to the sweep line, *somewhere* below "regAbove"
219 * (according to where the new edge belongs in the sweep-line dictionary).
220 * The upper edge of the new region will be "eNewUp".
221 * Winding number and "inside" flag are not updated.
224 ActiveRegion
*regNew
= (ActiveRegion
*)memAlloc( sizeof( ActiveRegion
));
225 if (regNew
== NULL
) longjmp(tess
->env
,1);
227 regNew
->eUp
= eNewUp
;
228 /* __gl_dictListInsertBefore */
229 regNew
->nodeUp
= dictInsertBefore( tess
->dict
, regAbove
->nodeUp
, regNew
);
230 if (regNew
->nodeUp
== NULL
) longjmp(tess
->env
,1);
231 regNew
->fixUpperEdge
= FALSE
;
232 regNew
->sentinel
= FALSE
;
233 regNew
->dirty
= FALSE
;
235 eNewUp
->activeRegion
= regNew
;
239 static GLboolean
IsWindingInside( GLUtesselator
*tess
, int n
)
241 switch( tess
->windingRule
) {
242 case GLU_TESS_WINDING_ODD
:
244 case GLU_TESS_WINDING_NONZERO
:
246 case GLU_TESS_WINDING_POSITIVE
:
248 case GLU_TESS_WINDING_NEGATIVE
:
250 case GLU_TESS_WINDING_ABS_GEQ_TWO
:
251 return (n
>= 2) || (n
<= -2);
256 return GL_FALSE
; /* avoid compiler complaints */
260 static void ComputeWinding( GLUtesselator
*tess
, ActiveRegion
*reg
)
262 reg
->windingNumber
= RegionAbove(reg
)->windingNumber
+ reg
->eUp
->winding
;
263 reg
->inside
= IsWindingInside( tess
, reg
->windingNumber
);
267 static void FinishRegion( GLUtesselator
*tess
, ActiveRegion
*reg
)
269 * Delete a region from the sweep line. This happens when the upper
270 * and lower chains of a region meet (at a vertex on the sweep line).
271 * The "inside" flag is copied to the appropriate mesh face (we could
272 * not do this before -- since the structure of the mesh is always
273 * changing, this face may not have even existed until now).
276 GLUhalfEdge
*e
= reg
->eUp
;
277 GLUface
*f
= e
->Lface
;
279 f
->inside
= reg
->inside
;
280 f
->anEdge
= e
; /* optimization for __gl_meshTessellateMonoRegion() */
281 DeleteRegion( tess
, reg
);
285 static GLUhalfEdge
*FinishLeftRegions( GLUtesselator
*tess
,
286 ActiveRegion
*regFirst
, ActiveRegion
*regLast
)
288 * We are given a vertex with one or more left-going edges. All affected
289 * edges should be in the edge dictionary. Starting at regFirst->eUp,
290 * we walk down deleting all regions where both edges have the same
291 * origin vOrg. At the same time we copy the "inside" flag from the
292 * active region to the face, since at this point each face will belong
293 * to at most one region (this was not necessarily true until this point
294 * in the sweep). The walk stops at the region above regLast; if regLast
295 * is NULL we walk as far as possible. At the same time we relink the
296 * mesh if necessary, so that the ordering of edges around vOrg is the
297 * same as in the dictionary.
300 ActiveRegion
*reg
, *regPrev
;
301 GLUhalfEdge
*e
, *ePrev
;
304 ePrev
= regFirst
->eUp
;
305 while( regPrev
!= regLast
) {
306 regPrev
->fixUpperEdge
= FALSE
; /* placement was OK */
307 reg
= RegionBelow( regPrev
);
309 if( e
->Org
!= ePrev
->Org
) {
310 if( ! reg
->fixUpperEdge
) {
311 /* Remove the last left-going edge. Even though there are no further
312 * edges in the dictionary with this origin, there may be further
313 * such edges in the mesh (if we are adding left edges to a vertex
314 * that has already been processed). Thus it is important to call
315 * FinishRegion rather than just DeleteRegion.
317 FinishRegion( tess
, regPrev
);
320 /* If the edge below was a temporary edge introduced by
321 * ConnectRightVertex, now is the time to fix it.
323 e
= __gl_meshConnect( ePrev
->Lprev
, e
->Sym
);
324 if (e
== NULL
) longjmp(tess
->env
,1);
325 if ( !FixUpperEdge( reg
, e
) ) longjmp(tess
->env
,1);
328 /* Relink edges so that ePrev->Onext == e */
329 if( ePrev
->Onext
!= e
) {
330 if ( !__gl_meshSplice( e
->Oprev
, e
) ) longjmp(tess
->env
,1);
331 if ( !__gl_meshSplice( ePrev
, e
) ) longjmp(tess
->env
,1);
333 FinishRegion( tess
, regPrev
); /* may change reg->eUp */
341 static void AddRightEdges( GLUtesselator
*tess
, ActiveRegion
*regUp
,
342 GLUhalfEdge
*eFirst
, GLUhalfEdge
*eLast
, GLUhalfEdge
*eTopLeft
,
345 * Purpose: insert right-going edges into the edge dictionary, and update
346 * winding numbers and mesh connectivity appropriately. All right-going
347 * edges share a common origin vOrg. Edges are inserted CCW starting at
348 * eFirst; the last edge inserted is eLast->Oprev. If vOrg has any
349 * left-going edges already processed, then eTopLeft must be the edge
350 * such that an imaginary upward vertical segment from vOrg would be
351 * contained between eTopLeft->Oprev and eTopLeft; otherwise eTopLeft
355 ActiveRegion
*reg
, *regPrev
;
356 GLUhalfEdge
*e
, *ePrev
;
357 int firstTime
= TRUE
;
359 /* Insert the new right-going edges in the dictionary */
362 assert( VertLeq( e
->Org
, e
->Dst
));
363 AddRegionBelow( tess
, regUp
, e
->Sym
);
365 } while ( e
!= eLast
);
367 /* Walk *all* right-going edges from e->Org, in the dictionary order,
368 * updating the winding numbers of each region, and re-linking the mesh
369 * edges to match the dictionary ordering (if necessary).
371 if( eTopLeft
== NULL
) {
372 eTopLeft
= RegionBelow( regUp
)->eUp
->Rprev
;
377 reg
= RegionBelow( regPrev
);
379 if( e
->Org
!= ePrev
->Org
) break;
381 if( e
->Onext
!= ePrev
) {
382 /* Unlink e from its current position, and relink below ePrev */
383 if ( !__gl_meshSplice( e
->Oprev
, e
) ) longjmp(tess
->env
,1);
384 if ( !__gl_meshSplice( ePrev
->Oprev
, e
) ) longjmp(tess
->env
,1);
386 /* Compute the winding number and "inside" flag for the new regions */
387 reg
->windingNumber
= regPrev
->windingNumber
- e
->winding
;
388 reg
->inside
= IsWindingInside( tess
, reg
->windingNumber
);
390 /* Check for two outgoing edges with same slope -- process these
391 * before any intersection tests (see example in __gl_computeInterior).
393 regPrev
->dirty
= TRUE
;
394 if( ! firstTime
&& CheckForRightSplice( tess
, regPrev
)) {
395 AddWinding( e
, ePrev
);
396 DeleteRegion( tess
, regPrev
);
397 if ( !__gl_meshDelete( ePrev
) ) longjmp(tess
->env
,1);
403 regPrev
->dirty
= TRUE
;
404 assert( regPrev
->windingNumber
- e
->winding
== reg
->windingNumber
);
407 /* Check for intersections between newly adjacent edges. */
408 WalkDirtyRegions( tess
, regPrev
);
413 static void CallCombine( GLUtesselator
*tess
, GLUvertex
*isect
,
414 void *data
[4], GLfloat weights
[4], int needed
)
418 /* Copy coord data in case the callback changes it. */
419 coords
[0] = isect
->coords
[0];
420 coords
[1] = isect
->coords
[1];
421 coords
[2] = isect
->coords
[2];
424 CALL_COMBINE_OR_COMBINE_DATA( coords
, data
, weights
, &isect
->data
);
425 if( isect
->data
== NULL
) {
427 isect
->data
= data
[0];
428 } else if( ! tess
->fatalError
) {
429 /* The only way fatal error is when two edges are found to intersect,
430 * but the user has not provided the callback necessary to handle
431 * generated intersection points.
433 CALL_ERROR_OR_ERROR_DATA( GLU_TESS_NEED_COMBINE_CALLBACK
);
434 tess
->fatalError
= TRUE
;
439 static void SpliceMergeVertices( GLUtesselator
*tess
, GLUhalfEdge
*e1
,
442 * Two vertices with idential coordinates are combined into one.
443 * e1->Org is kept, while e2->Org is discarded.
446 void *data
[4] = { NULL
, NULL
, NULL
, NULL
};
447 GLfloat weights
[4] = { 0.5, 0.5, 0.0, 0.0 };
449 data
[0] = e1
->Org
->data
;
450 data
[1] = e2
->Org
->data
;
451 CallCombine( tess
, e1
->Org
, data
, weights
, FALSE
);
452 if ( !__gl_meshSplice( e1
, e2
) ) longjmp(tess
->env
,1);
455 static void VertexWeights( GLUvertex
*isect
, GLUvertex
*org
, GLUvertex
*dst
,
458 * Find some weights which describe how the intersection vertex is
459 * a linear combination of "org" and "dest". Each of the two edges
460 * which generated "isect" is allocated 50% of the weight; each edge
461 * splits the weight between its org and dst according to the
462 * relative distance to "isect".
465 GLdouble t1
= VertL1dist( org
, isect
);
466 GLdouble t2
= VertL1dist( dst
, isect
);
468 weights
[0] = 0.5 * t2
/ (t1
+ t2
);
469 weights
[1] = 0.5 * t1
/ (t1
+ t2
);
470 isect
->coords
[0] += weights
[0]*org
->coords
[0] + weights
[1]*dst
->coords
[0];
471 isect
->coords
[1] += weights
[0]*org
->coords
[1] + weights
[1]*dst
->coords
[1];
472 isect
->coords
[2] += weights
[0]*org
->coords
[2] + weights
[1]*dst
->coords
[2];
476 static void GetIntersectData( GLUtesselator
*tess
, GLUvertex
*isect
,
477 GLUvertex
*orgUp
, GLUvertex
*dstUp
,
478 GLUvertex
*orgLo
, GLUvertex
*dstLo
)
480 * We've computed a new intersection point, now we need a "data" pointer
481 * from the user so that we can refer to this new vertex in the
482 * rendering callbacks.
488 data
[0] = orgUp
->data
;
489 data
[1] = dstUp
->data
;
490 data
[2] = orgLo
->data
;
491 data
[3] = dstLo
->data
;
493 isect
->coords
[0] = isect
->coords
[1] = isect
->coords
[2] = 0;
494 VertexWeights( isect
, orgUp
, dstUp
, &weights
[0] );
495 VertexWeights( isect
, orgLo
, dstLo
, &weights
[2] );
497 CallCombine( tess
, isect
, data
, weights
, TRUE
);
500 static int CheckForRightSplice( GLUtesselator
*tess
, ActiveRegion
*regUp
)
502 * Check the upper and lower edge of "regUp", to make sure that the
503 * eUp->Org is above eLo, or eLo->Org is below eUp (depending on which
504 * origin is leftmost).
506 * The main purpose is to splice right-going edges with the same
507 * dest vertex and nearly identical slopes (ie. we can't distinguish
508 * the slopes numerically). However the splicing can also help us
509 * to recover from numerical errors. For example, suppose at one
510 * point we checked eUp and eLo, and decided that eUp->Org is barely
511 * above eLo. Then later, we split eLo into two edges (eg. from
512 * a splice operation like this one). This can change the result of
513 * our test so that now eUp->Org is incident to eLo, or barely below it.
514 * We must correct this condition to maintain the dictionary invariants.
516 * One possibility is to check these edges for intersection again
517 * (ie. CheckForIntersect). This is what we do if possible. However
518 * CheckForIntersect requires that tess->event lies between eUp and eLo,
519 * so that it has something to fall back on when the intersection
520 * calculation gives us an unusable answer. So, for those cases where
521 * we can't check for intersection, this routine fixes the problem
522 * by just splicing the offending vertex into the other edge.
523 * This is a guaranteed solution, no matter how degenerate things get.
524 * Basically this is a combinatorial solution to a numerical problem.
527 ActiveRegion
*regLo
= RegionBelow(regUp
);
528 GLUhalfEdge
*eUp
= regUp
->eUp
;
529 GLUhalfEdge
*eLo
= regLo
->eUp
;
531 if( VertLeq( eUp
->Org
, eLo
->Org
)) {
532 if( EdgeSign( eLo
->Dst
, eUp
->Org
, eLo
->Org
) > 0 ) return FALSE
;
534 /* eUp->Org appears to be below eLo */
535 if( ! VertEq( eUp
->Org
, eLo
->Org
)) {
536 /* Splice eUp->Org into eLo */
537 if ( __gl_meshSplitEdge( eLo
->Sym
) == NULL
) longjmp(tess
->env
,1);
538 if ( !__gl_meshSplice( eUp
, eLo
->Oprev
) ) longjmp(tess
->env
,1);
539 regUp
->dirty
= regLo
->dirty
= TRUE
;
541 } else if( eUp
->Org
!= eLo
->Org
) {
542 /* merge the two vertices, discarding eUp->Org */
543 pqDelete( tess
->pq
, eUp
->Org
->pqHandle
); /* __gl_pqSortDelete */
544 SpliceMergeVertices( tess
, eLo
->Oprev
, eUp
);
547 if( EdgeSign( eUp
->Dst
, eLo
->Org
, eUp
->Org
) < 0 ) return FALSE
;
549 /* eLo->Org appears to be above eUp, so splice eLo->Org into eUp */
550 RegionAbove(regUp
)->dirty
= regUp
->dirty
= TRUE
;
551 if (__gl_meshSplitEdge( eUp
->Sym
) == NULL
) longjmp(tess
->env
,1);
552 if ( !__gl_meshSplice( eLo
->Oprev
, eUp
) ) longjmp(tess
->env
,1);
557 static int CheckForLeftSplice( GLUtesselator
*tess
, ActiveRegion
*regUp
)
559 * Check the upper and lower edge of "regUp", to make sure that the
560 * eUp->Dst is above eLo, or eLo->Dst is below eUp (depending on which
561 * destination is rightmost).
563 * Theoretically, this should always be true. However, splitting an edge
564 * into two pieces can change the results of previous tests. For example,
565 * suppose at one point we checked eUp and eLo, and decided that eUp->Dst
566 * is barely above eLo. Then later, we split eLo into two edges (eg. from
567 * a splice operation like this one). This can change the result of
568 * the test so that now eUp->Dst is incident to eLo, or barely below it.
569 * We must correct this condition to maintain the dictionary invariants
570 * (otherwise new edges might get inserted in the wrong place in the
571 * dictionary, and bad stuff will happen).
573 * We fix the problem by just splicing the offending vertex into the
577 ActiveRegion
*regLo
= RegionBelow(regUp
);
578 GLUhalfEdge
*eUp
= regUp
->eUp
;
579 GLUhalfEdge
*eLo
= regLo
->eUp
;
582 assert( ! VertEq( eUp
->Dst
, eLo
->Dst
));
584 if( VertLeq( eUp
->Dst
, eLo
->Dst
)) {
585 if( EdgeSign( eUp
->Dst
, eLo
->Dst
, eUp
->Org
) < 0 ) return FALSE
;
587 /* eLo->Dst is above eUp, so splice eLo->Dst into eUp */
588 RegionAbove(regUp
)->dirty
= regUp
->dirty
= TRUE
;
589 e
= __gl_meshSplitEdge( eUp
);
590 if (e
== NULL
) longjmp(tess
->env
,1);
591 if ( !__gl_meshSplice( eLo
->Sym
, e
) ) longjmp(tess
->env
,1);
592 e
->Lface
->inside
= regUp
->inside
;
594 if( EdgeSign( eLo
->Dst
, eUp
->Dst
, eLo
->Org
) > 0 ) return FALSE
;
596 /* eUp->Dst is below eLo, so splice eUp->Dst into eLo */
597 regUp
->dirty
= regLo
->dirty
= TRUE
;
598 e
= __gl_meshSplitEdge( eLo
);
599 if (e
== NULL
) longjmp(tess
->env
,1);
600 if ( !__gl_meshSplice( eUp
->Lnext
, eLo
->Sym
) ) longjmp(tess
->env
,1);
601 e
->Rface
->inside
= regUp
->inside
;
607 static int CheckForIntersect( GLUtesselator
*tess
, ActiveRegion
*regUp
)
609 * Check the upper and lower edges of the given region to see if
610 * they intersect. If so, create the intersection and add it
611 * to the data structures.
613 * Returns TRUE if adding the new intersection resulted in a recursive
614 * call to AddRightEdges(); in this case all "dirty" regions have been
615 * checked for intersections, and possibly regUp has been deleted.
618 ActiveRegion
*regLo
= RegionBelow(regUp
);
619 GLUhalfEdge
*eUp
= regUp
->eUp
;
620 GLUhalfEdge
*eLo
= regLo
->eUp
;
621 GLUvertex
*orgUp
= eUp
->Org
;
622 GLUvertex
*orgLo
= eLo
->Org
;
623 GLUvertex
*dstUp
= eUp
->Dst
;
624 GLUvertex
*dstLo
= eLo
->Dst
;
625 GLdouble tMinUp
, tMaxLo
;
626 GLUvertex isect
, *orgMin
;
629 assert( ! VertEq( dstLo
, dstUp
));
630 assert( EdgeSign( dstUp
, tess
->event
, orgUp
) <= 0 );
631 assert( EdgeSign( dstLo
, tess
->event
, orgLo
) >= 0 );
632 assert( orgUp
!= tess
->event
&& orgLo
!= tess
->event
);
633 assert( ! regUp
->fixUpperEdge
&& ! regLo
->fixUpperEdge
);
635 if( orgUp
== orgLo
) return FALSE
; /* right endpoints are the same */
637 tMinUp
= MIN( orgUp
->t
, dstUp
->t
);
638 tMaxLo
= MAX( orgLo
->t
, dstLo
->t
);
639 if( tMinUp
> tMaxLo
) return FALSE
; /* t ranges do not overlap */
641 if( VertLeq( orgUp
, orgLo
)) {
642 if( EdgeSign( dstLo
, orgUp
, orgLo
) > 0 ) return FALSE
;
644 if( EdgeSign( dstUp
, orgLo
, orgUp
) < 0 ) return FALSE
;
647 /* At this point the edges intersect, at least marginally */
650 __gl_edgeIntersect( dstUp
, orgUp
, dstLo
, orgLo
, &isect
);
651 /* The following properties are guaranteed: */
652 assert( MIN( orgUp
->t
, dstUp
->t
) <= isect
.t
);
653 assert( isect
.t
<= MAX( orgLo
->t
, dstLo
->t
));
654 assert( MIN( dstLo
->s
, dstUp
->s
) <= isect
.s
);
655 assert( isect
.s
<= MAX( orgLo
->s
, orgUp
->s
));
657 if( VertLeq( &isect
, tess
->event
)) {
658 /* The intersection point lies slightly to the left of the sweep line,
659 * so move it until it''s slightly to the right of the sweep line.
660 * (If we had perfect numerical precision, this would never happen
661 * in the first place). The easiest and safest thing to do is
662 * replace the intersection by tess->event.
664 isect
.s
= tess
->event
->s
;
665 isect
.t
= tess
->event
->t
;
667 /* Similarly, if the computed intersection lies to the right of the
668 * rightmost origin (which should rarely happen), it can cause
669 * unbelievable inefficiency on sufficiently degenerate inputs.
670 * (If you have the test program, try running test54.d with the
671 * "X zoom" option turned on).
673 orgMin
= VertLeq( orgUp
, orgLo
) ? orgUp
: orgLo
;
674 if( VertLeq( orgMin
, &isect
)) {
679 if( VertEq( &isect
, orgUp
) || VertEq( &isect
, orgLo
)) {
680 /* Easy case -- intersection at one of the right endpoints */
681 (void) CheckForRightSplice( tess
, regUp
);
685 if( (! VertEq( dstUp
, tess
->event
)
686 && EdgeSign( dstUp
, tess
->event
, &isect
) >= 0)
687 || (! VertEq( dstLo
, tess
->event
)
688 && EdgeSign( dstLo
, tess
->event
, &isect
) <= 0 ))
690 /* Very unusual -- the new upper or lower edge would pass on the
691 * wrong side of the sweep event, or through it. This can happen
692 * due to very small numerical errors in the intersection calculation.
694 if( dstLo
== tess
->event
) {
695 /* Splice dstLo into eUp, and process the new region(s) */
696 if (__gl_meshSplitEdge( eUp
->Sym
) == NULL
) longjmp(tess
->env
,1);
697 if ( !__gl_meshSplice( eLo
->Sym
, eUp
) ) longjmp(tess
->env
,1);
698 regUp
= TopLeftRegion( regUp
);
699 if (regUp
== NULL
) longjmp(tess
->env
,1);
700 eUp
= RegionBelow(regUp
)->eUp
;
701 FinishLeftRegions( tess
, RegionBelow(regUp
), regLo
);
702 AddRightEdges( tess
, regUp
, eUp
->Oprev
, eUp
, eUp
, TRUE
);
705 if( dstUp
== tess
->event
) {
706 /* Splice dstUp into eLo, and process the new region(s) */
707 if (__gl_meshSplitEdge( eLo
->Sym
) == NULL
) longjmp(tess
->env
,1);
708 if ( !__gl_meshSplice( eUp
->Lnext
, eLo
->Oprev
) ) longjmp(tess
->env
,1);
710 regUp
= TopRightRegion( regUp
);
711 e
= RegionBelow(regUp
)->eUp
->Rprev
;
712 regLo
->eUp
= eLo
->Oprev
;
713 eLo
= FinishLeftRegions( tess
, regLo
, NULL
);
714 AddRightEdges( tess
, regUp
, eLo
->Onext
, eUp
->Rprev
, e
, TRUE
);
717 /* Special case: called from ConnectRightVertex. If either
718 * edge passes on the wrong side of tess->event, split it
719 * (and wait for ConnectRightVertex to splice it appropriately).
721 if( EdgeSign( dstUp
, tess
->event
, &isect
) >= 0 ) {
722 RegionAbove(regUp
)->dirty
= regUp
->dirty
= TRUE
;
723 if (__gl_meshSplitEdge( eUp
->Sym
) == NULL
) longjmp(tess
->env
,1);
724 eUp
->Org
->s
= tess
->event
->s
;
725 eUp
->Org
->t
= tess
->event
->t
;
727 if( EdgeSign( dstLo
, tess
->event
, &isect
) <= 0 ) {
728 regUp
->dirty
= regLo
->dirty
= TRUE
;
729 if (__gl_meshSplitEdge( eLo
->Sym
) == NULL
) longjmp(tess
->env
,1);
730 eLo
->Org
->s
= tess
->event
->s
;
731 eLo
->Org
->t
= tess
->event
->t
;
733 /* leave the rest for ConnectRightVertex */
737 /* General case -- split both edges, splice into new vertex.
738 * When we do the splice operation, the order of the arguments is
739 * arbitrary as far as correctness goes. However, when the operation
740 * creates a new face, the work done is proportional to the size of
741 * the new face. We expect the faces in the processed part of
742 * the mesh (ie. eUp->Lface) to be smaller than the faces in the
743 * unprocessed original contours (which will be eLo->Oprev->Lface).
745 if (__gl_meshSplitEdge( eUp
->Sym
) == NULL
) longjmp(tess
->env
,1);
746 if (__gl_meshSplitEdge( eLo
->Sym
) == NULL
) longjmp(tess
->env
,1);
747 if ( !__gl_meshSplice( eLo
->Oprev
, eUp
) ) longjmp(tess
->env
,1);
748 eUp
->Org
->s
= isect
.s
;
749 eUp
->Org
->t
= isect
.t
;
750 eUp
->Org
->pqHandle
= pqInsert( tess
->pq
, eUp
->Org
); /* __gl_pqSortInsert */
751 if (eUp
->Org
->pqHandle
== LONG_MAX
) {
752 pqDeletePriorityQ(tess
->pq
); /* __gl_pqSortDeletePriorityQ */
754 longjmp(tess
->env
,1);
756 GetIntersectData( tess
, eUp
->Org
, orgUp
, dstUp
, orgLo
, dstLo
);
757 RegionAbove(regUp
)->dirty
= regUp
->dirty
= regLo
->dirty
= TRUE
;
761 static void WalkDirtyRegions( GLUtesselator
*tess
, ActiveRegion
*regUp
)
763 * When the upper or lower edge of any region changes, the region is
764 * marked "dirty". This routine walks through all the dirty regions
765 * and makes sure that the dictionary invariants are satisfied
766 * (see the comments at the beginning of this file). Of course
767 * new dirty regions can be created as we make changes to restore
771 ActiveRegion
*regLo
= RegionBelow(regUp
);
772 GLUhalfEdge
*eUp
, *eLo
;
775 /* Find the lowest dirty region (we walk from the bottom up). */
776 while( regLo
->dirty
) {
778 regLo
= RegionBelow(regLo
);
780 if( ! regUp
->dirty
) {
782 regUp
= RegionAbove( regUp
);
783 if( regUp
== NULL
|| ! regUp
->dirty
) {
784 /* We've walked all the dirty regions */
788 regUp
->dirty
= FALSE
;
792 if( eUp
->Dst
!= eLo
->Dst
) {
793 /* Check that the edge ordering is obeyed at the Dst vertices. */
794 if( CheckForLeftSplice( tess
, regUp
)) {
796 /* If the upper or lower edge was marked fixUpperEdge, then
797 * we no longer need it (since these edges are needed only for
798 * vertices which otherwise have no right-going edges).
800 if( regLo
->fixUpperEdge
) {
801 DeleteRegion( tess
, regLo
);
802 if ( !__gl_meshDelete( eLo
) ) longjmp(tess
->env
,1);
803 regLo
= RegionBelow( regUp
);
805 } else if( regUp
->fixUpperEdge
) {
806 DeleteRegion( tess
, regUp
);
807 if ( !__gl_meshDelete( eUp
) ) longjmp(tess
->env
,1);
808 regUp
= RegionAbove( regLo
);
813 if( eUp
->Org
!= eLo
->Org
) {
814 if( eUp
->Dst
!= eLo
->Dst
815 && ! regUp
->fixUpperEdge
&& ! regLo
->fixUpperEdge
816 && (eUp
->Dst
== tess
->event
|| eLo
->Dst
== tess
->event
) )
818 /* When all else fails in CheckForIntersect(), it uses tess->event
819 * as the intersection location. To make this possible, it requires
820 * that tess->event lie between the upper and lower edges, and also
821 * that neither of these is marked fixUpperEdge (since in the worst
822 * case it might splice one of these edges into tess->event, and
823 * violate the invariant that fixable edges are the only right-going
824 * edge from their associated vertex).
826 if( CheckForIntersect( tess
, regUp
)) {
827 /* WalkDirtyRegions() was called recursively; we're done */
831 /* Even though we can't use CheckForIntersect(), the Org vertices
832 * may violate the dictionary edge ordering. Check and correct this.
834 (void) CheckForRightSplice( tess
, regUp
);
837 if( eUp
->Org
== eLo
->Org
&& eUp
->Dst
== eLo
->Dst
) {
838 /* A degenerate loop consisting of only two edges -- delete it. */
839 AddWinding( eLo
, eUp
);
840 DeleteRegion( tess
, regUp
);
841 if ( !__gl_meshDelete( eUp
) ) longjmp(tess
->env
,1);
842 regUp
= RegionAbove( regLo
);
848 static void ConnectRightVertex( GLUtesselator
*tess
, ActiveRegion
*regUp
,
849 GLUhalfEdge
*eBottomLeft
)
851 * Purpose: connect a "right" vertex vEvent (one where all edges go left)
852 * to the unprocessed portion of the mesh. Since there are no right-going
853 * edges, two regions (one above vEvent and one below) are being merged
854 * into one. "regUp" is the upper of these two regions.
856 * There are two reasons for doing this (adding a right-going edge):
857 * - if the two regions being merged are "inside", we must add an edge
858 * to keep them separated (the combined region would not be monotone).
859 * - in any case, we must leave some record of vEvent in the dictionary,
860 * so that we can merge vEvent with features that we have not seen yet.
861 * For example, maybe there is a vertical edge which passes just to
862 * the right of vEvent; we would like to splice vEvent into this edge.
864 * However, we don't want to connect vEvent to just any vertex. We don''t
865 * want the new edge to cross any other edges; otherwise we will create
866 * intersection vertices even when the input data had no self-intersections.
867 * (This is a bad thing; if the user's input data has no intersections,
868 * we don't want to generate any false intersections ourselves.)
870 * Our eventual goal is to connect vEvent to the leftmost unprocessed
871 * vertex of the combined region (the union of regUp and regLo).
872 * But because of unseen vertices with all right-going edges, and also
873 * new vertices which may be created by edge intersections, we don''t
874 * know where that leftmost unprocessed vertex is. In the meantime, we
875 * connect vEvent to the closest vertex of either chain, and mark the region
876 * as "fixUpperEdge". This flag says to delete and reconnect this edge
877 * to the next processed vertex on the boundary of the combined region.
878 * Quite possibly the vertex we connected to will turn out to be the
879 * closest one, in which case we won''t need to make any changes.
883 GLUhalfEdge
*eTopLeft
= eBottomLeft
->Onext
;
884 ActiveRegion
*regLo
= RegionBelow(regUp
);
885 GLUhalfEdge
*eUp
= regUp
->eUp
;
886 GLUhalfEdge
*eLo
= regLo
->eUp
;
887 int degenerate
= FALSE
;
889 if( eUp
->Dst
!= eLo
->Dst
) {
890 (void) CheckForIntersect( tess
, regUp
);
893 /* Possible new degeneracies: upper or lower edge of regUp may pass
894 * through vEvent, or may coincide with new intersection vertex
896 if( VertEq( eUp
->Org
, tess
->event
)) {
897 if ( !__gl_meshSplice( eTopLeft
->Oprev
, eUp
) ) longjmp(tess
->env
,1);
898 regUp
= TopLeftRegion( regUp
);
899 if (regUp
== NULL
) longjmp(tess
->env
,1);
900 eTopLeft
= RegionBelow( regUp
)->eUp
;
901 FinishLeftRegions( tess
, RegionBelow(regUp
), regLo
);
904 if( VertEq( eLo
->Org
, tess
->event
)) {
905 if ( !__gl_meshSplice( eBottomLeft
, eLo
->Oprev
) ) longjmp(tess
->env
,1);
906 eBottomLeft
= FinishLeftRegions( tess
, regLo
, NULL
);
910 AddRightEdges( tess
, regUp
, eBottomLeft
->Onext
, eTopLeft
, eTopLeft
, TRUE
);
914 /* Non-degenerate situation -- need to add a temporary, fixable edge.
915 * Connect to the closer of eLo->Org, eUp->Org.
917 if( VertLeq( eLo
->Org
, eUp
->Org
)) {
922 eNew
= __gl_meshConnect( eBottomLeft
->Lprev
, eNew
);
923 if (eNew
== NULL
) longjmp(tess
->env
,1);
925 /* Prevent cleanup, otherwise eNew might disappear before we've even
926 * had a chance to mark it as a temporary edge.
928 AddRightEdges( tess
, regUp
, eNew
, eNew
->Onext
, eNew
->Onext
, FALSE
);
929 eNew
->Sym
->activeRegion
->fixUpperEdge
= TRUE
;
930 WalkDirtyRegions( tess
, regUp
);
933 /* Because vertices at exactly the same location are merged together
934 * before we process the sweep event, some degenerate cases can't occur.
935 * However if someone eventually makes the modifications required to
936 * merge features which are close together, the cases below marked
937 * TOLERANCE_NONZERO will be useful. They were debugged before the
938 * code to merge identical vertices in the main loop was added.
940 #define TOLERANCE_NONZERO FALSE
942 static void ConnectLeftDegenerate( GLUtesselator
*tess
,
943 ActiveRegion
*regUp
, GLUvertex
*vEvent
)
945 * The event vertex lies exacty on an already-processed edge or vertex.
946 * Adding the new vertex involves splicing it into the already-processed
950 GLUhalfEdge
*e
, *eTopLeft
, *eTopRight
, *eLast
;
954 if( VertEq( e
->Org
, vEvent
)) {
955 /* e->Org is an unprocessed vertex - just combine them, and wait
956 * for e->Org to be pulled from the queue
958 assert( TOLERANCE_NONZERO
);
959 SpliceMergeVertices( tess
, e
, vEvent
->anEdge
);
963 if( ! VertEq( e
->Dst
, vEvent
)) {
964 /* General case -- splice vEvent into edge e which passes through it */
965 if (__gl_meshSplitEdge( e
->Sym
) == NULL
) longjmp(tess
->env
,1);
966 if( regUp
->fixUpperEdge
) {
967 /* This edge was fixable -- delete unused portion of original edge */
968 if ( !__gl_meshDelete( e
->Onext
) ) longjmp(tess
->env
,1);
969 regUp
->fixUpperEdge
= FALSE
;
971 if ( !__gl_meshSplice( vEvent
->anEdge
, e
) ) longjmp(tess
->env
,1);
972 SweepEvent( tess
, vEvent
); /* recurse */
976 /* vEvent coincides with e->Dst, which has already been processed.
977 * Splice in the additional right-going edges.
979 assert( TOLERANCE_NONZERO
);
980 regUp
= TopRightRegion( regUp
);
981 reg
= RegionBelow( regUp
);
982 eTopRight
= reg
->eUp
->Sym
;
983 eTopLeft
= eLast
= eTopRight
->Onext
;
984 if( reg
->fixUpperEdge
) {
985 /* Here e->Dst has only a single fixable edge going right.
986 * We can delete it since now we have some real right-going edges.
988 assert( eTopLeft
!= eTopRight
); /* there are some left edges too */
989 DeleteRegion( tess
, reg
);
990 if ( !__gl_meshDelete( eTopRight
) ) longjmp(tess
->env
,1);
991 eTopRight
= eTopLeft
->Oprev
;
993 if ( !__gl_meshSplice( vEvent
->anEdge
, eTopRight
) ) longjmp(tess
->env
,1);
994 if( ! EdgeGoesLeft( eTopLeft
)) {
995 /* e->Dst had no left-going edges -- indicate this to AddRightEdges() */
998 AddRightEdges( tess
, regUp
, eTopRight
->Onext
, eLast
, eTopLeft
, TRUE
);
1002 static void ConnectLeftVertex( GLUtesselator
*tess
, GLUvertex
*vEvent
)
1004 * Purpose: connect a "left" vertex (one where both edges go right)
1005 * to the processed portion of the mesh. Let R be the active region
1006 * containing vEvent, and let U and L be the upper and lower edge
1007 * chains of R. There are two possibilities:
1009 * - the normal case: split R into two regions, by connecting vEvent to
1010 * the rightmost vertex of U or L lying to the left of the sweep line
1012 * - the degenerate case: if vEvent is close enough to U or L, we
1013 * merge vEvent into that edge chain. The subcases are:
1014 * - merging with the rightmost vertex of U or L
1015 * - merging with the active edge of U or L
1016 * - merging with an already-processed portion of U or L
1019 ActiveRegion
*regUp
, *regLo
, *reg
;
1020 GLUhalfEdge
*eUp
, *eLo
, *eNew
;
1023 /* assert( vEvent->anEdge->Onext->Onext == vEvent->anEdge ); */
1025 /* Get a pointer to the active region containing vEvent */
1026 tmp
.eUp
= vEvent
->anEdge
->Sym
;
1027 /* __GL_DICTLISTKEY */ /* __gl_dictListSearch */
1028 regUp
= (ActiveRegion
*)dictKey( dictSearch( tess
->dict
, &tmp
));
1029 regLo
= RegionBelow( regUp
);
1033 /* Try merging with U or L first */
1034 if( EdgeSign( eUp
->Dst
, vEvent
, eUp
->Org
) == 0 ) {
1035 ConnectLeftDegenerate( tess
, regUp
, vEvent
);
1039 /* Connect vEvent to rightmost processed vertex of either chain.
1040 * e->Dst is the vertex that we will connect to vEvent.
1042 reg
= VertLeq( eLo
->Dst
, eUp
->Dst
) ? regUp
: regLo
;
1044 if( regUp
->inside
|| reg
->fixUpperEdge
) {
1045 if( reg
== regUp
) {
1046 eNew
= __gl_meshConnect( vEvent
->anEdge
->Sym
, eUp
->Lnext
);
1047 if (eNew
== NULL
) longjmp(tess
->env
,1);
1049 GLUhalfEdge
*tempHalfEdge
= __gl_meshConnect( eLo
->Dnext
, vEvent
->anEdge
);
1050 if (tempHalfEdge
== NULL
) longjmp(tess
->env
,1);
1052 eNew
= tempHalfEdge
->Sym
;
1054 if( reg
->fixUpperEdge
) {
1055 if ( !FixUpperEdge( reg
, eNew
) ) longjmp(tess
->env
,1);
1057 ComputeWinding( tess
, AddRegionBelow( tess
, regUp
, eNew
));
1059 SweepEvent( tess
, vEvent
);
1061 /* The new vertex is in a region which does not belong to the polygon.
1062 * We don''t need to connect this vertex to the rest of the mesh.
1064 AddRightEdges( tess
, regUp
, vEvent
->anEdge
, vEvent
->anEdge
, NULL
, TRUE
);
1069 static void SweepEvent( GLUtesselator
*tess
, GLUvertex
*vEvent
)
1071 * Does everything necessary when the sweep line crosses a vertex.
1072 * Updates the mesh and the edge dictionary.
1075 ActiveRegion
*regUp
, *reg
;
1076 GLUhalfEdge
*e
, *eTopLeft
, *eBottomLeft
;
1078 tess
->event
= vEvent
; /* for access in EdgeLeq() */
1081 /* Check if this vertex is the right endpoint of an edge that is
1082 * already in the dictionary. In this case we don't need to waste
1083 * time searching for the location to insert new edges.
1086 while( e
->activeRegion
== NULL
) {
1088 if( e
== vEvent
->anEdge
) {
1089 /* All edges go right -- not incident to any processed edges */
1090 ConnectLeftVertex( tess
, vEvent
);
1095 /* Processing consists of two phases: first we "finish" all the
1096 * active regions where both the upper and lower edges terminate
1097 * at vEvent (ie. vEvent is closing off these regions).
1098 * We mark these faces "inside" or "outside" the polygon according
1099 * to their winding number, and delete the edges from the dictionary.
1100 * This takes care of all the left-going edges from vEvent.
1102 regUp
= TopLeftRegion( e
->activeRegion
);
1103 if (regUp
== NULL
) longjmp(tess
->env
,1);
1104 reg
= RegionBelow( regUp
);
1105 eTopLeft
= reg
->eUp
;
1106 eBottomLeft
= FinishLeftRegions( tess
, reg
, NULL
);
1108 /* Next we process all the right-going edges from vEvent. This
1109 * involves adding the edges to the dictionary, and creating the
1110 * associated "active regions" which record information about the
1111 * regions between adjacent dictionary edges.
1113 if( eBottomLeft
->Onext
== eTopLeft
) {
1114 /* No right-going edges -- add a temporary "fixable" edge */
1115 ConnectRightVertex( tess
, regUp
, eBottomLeft
);
1117 AddRightEdges( tess
, regUp
, eBottomLeft
->Onext
, eTopLeft
, eTopLeft
, TRUE
);
1122 /* Make the sentinel coordinates big enough that they will never be
1123 * merged with real input features. (Even with the largest possible
1124 * input contour and the maximum tolerance of 1.0, no merging will be
1125 * done with coordinates larger than 3 * GLU_TESS_MAX_COORD).
1127 #define SENTINEL_COORD (4 * GLU_TESS_MAX_COORD)
1129 static void AddSentinel( GLUtesselator
*tess
, GLdouble t
)
1131 * We add two sentinel edges above and below all other edges,
1132 * to avoid special cases at the top and bottom.
1136 ActiveRegion
*reg
= (ActiveRegion
*)memAlloc( sizeof( ActiveRegion
));
1137 if (reg
== NULL
) longjmp(tess
->env
,1);
1139 e
= __gl_meshMakeEdge( tess
->mesh
);
1140 if (e
== NULL
) longjmp(tess
->env
,1);
1142 e
->Org
->s
= SENTINEL_COORD
;
1144 e
->Dst
->s
= -SENTINEL_COORD
;
1146 tess
->event
= e
->Dst
; /* initialize it */
1149 reg
->windingNumber
= 0;
1150 reg
->inside
= FALSE
;
1151 reg
->fixUpperEdge
= FALSE
;
1152 reg
->sentinel
= TRUE
;
1154 reg
->nodeUp
= dictInsert( tess
->dict
, reg
); /* __gl_dictListInsertBefore */
1155 if (reg
->nodeUp
== NULL
) longjmp(tess
->env
,1);
1159 static void InitEdgeDict( GLUtesselator
*tess
)
1161 * We maintain an ordering of edge intersections with the sweep line.
1162 * This order is maintained in a dynamic dictionary.
1165 /* __gl_dictListNewDict */
1166 tess
->dict
= dictNewDict( tess
, (int (*)(void *, DictKey
, DictKey
)) EdgeLeq
);
1167 if (tess
->dict
== NULL
) longjmp(tess
->env
,1);
1169 AddSentinel( tess
, -SENTINEL_COORD
);
1170 AddSentinel( tess
, SENTINEL_COORD
);
1174 static void DoneEdgeDict( GLUtesselator
*tess
)
1181 /* __GL_DICTLISTKEY */ /* __GL_DICTLISTMIN */
1182 while( (reg
= (ActiveRegion
*)dictKey( dictMin( tess
->dict
))) != NULL
) {
1184 * At the end of all processing, the dictionary should contain
1185 * only the two sentinel edges, plus at most one "fixable" edge
1186 * created by ConnectRightVertex().
1188 if( ! reg
->sentinel
) {
1189 assert( reg
->fixUpperEdge
);
1190 assert( ++fixedEdges
== 1 );
1192 assert( reg
->windingNumber
== 0 );
1193 DeleteRegion( tess
, reg
);
1194 /* __gl_meshDelete( reg->eUp );*/
1196 dictDeleteDict( tess
->dict
); /* __gl_dictListDeleteDict */
1200 static void RemoveDegenerateEdges( GLUtesselator
*tess
)
1202 * Remove zero-length edges, and contours with fewer than 3 vertices.
1205 GLUhalfEdge
*e
, *eNext
, *eLnext
;
1206 GLUhalfEdge
*eHead
= &tess
->mesh
->eHead
;
1209 for( e
= eHead
->next
; e
!= eHead
; e
= eNext
) {
1213 if( VertEq( e
->Org
, e
->Dst
) && e
->Lnext
->Lnext
!= e
) {
1214 /* Zero-length edge, contour has at least 3 edges */
1216 SpliceMergeVertices( tess
, eLnext
, e
); /* deletes e->Org */
1217 if ( !__gl_meshDelete( e
) ) longjmp(tess
->env
,1); /* e is a self-loop */
1221 if( eLnext
->Lnext
== e
) {
1222 /* Degenerate contour (one or two edges) */
1225 if( eLnext
== eNext
|| eLnext
== eNext
->Sym
) { eNext
= eNext
->next
; }
1226 if ( !__gl_meshDelete( eLnext
) ) longjmp(tess
->env
,1);
1228 if( e
== eNext
|| e
== eNext
->Sym
) { eNext
= eNext
->next
; }
1229 if ( !__gl_meshDelete( e
) ) longjmp(tess
->env
,1);
1234 static int InitPriorityQ( GLUtesselator
*tess
)
1236 * Insert all vertices into the priority queue which determines the
1237 * order in which vertices cross the sweep line.
1241 GLUvertex
*v
, *vHead
;
1243 /* __gl_pqSortNewPriorityQ */
1244 pq
= tess
->pq
= pqNewPriorityQ( (int (*)(PQkey
, PQkey
)) __gl_vertLeq
);
1245 if (pq
== NULL
) return 0;
1247 vHead
= &tess
->mesh
->vHead
;
1248 for( v
= vHead
->next
; v
!= vHead
; v
= v
->next
) {
1249 v
->pqHandle
= pqInsert( pq
, v
); /* __gl_pqSortInsert */
1250 if (v
->pqHandle
== LONG_MAX
) break;
1252 if (v
!= vHead
|| !pqInit( pq
) ) { /* __gl_pqSortInit */
1253 pqDeletePriorityQ(tess
->pq
); /* __gl_pqSortDeletePriorityQ */
1262 static void DonePriorityQ( GLUtesselator
*tess
)
1264 pqDeletePriorityQ( tess
->pq
); /* __gl_pqSortDeletePriorityQ */
1268 static int RemoveDegenerateFaces( GLUmesh
*mesh
)
1270 * Delete any degenerate faces with only two edges. WalkDirtyRegions()
1271 * will catch almost all of these, but it won't catch degenerate faces
1272 * produced by splice operations on already-processed edges.
1273 * The two places this can happen are in FinishLeftRegions(), when
1274 * we splice in a "temporary" edge produced by ConnectRightVertex(),
1275 * and in CheckForLeftSplice(), where we splice already-processed
1276 * edges to ensure that our dictionary invariants are not violated
1277 * by numerical errors.
1279 * In both these cases it is *very* dangerous to delete the offending
1280 * edge at the time, since one of the routines further up the stack
1281 * will sometimes be keeping a pointer to that edge.
1288 for( f
= mesh
->fHead
.next
; f
!= &mesh
->fHead
; f
= fNext
) {
1291 assert( e
->Lnext
!= e
);
1293 if( e
->Lnext
->Lnext
== e
) {
1294 /* A face with only two edges */
1295 AddWinding( e
->Onext
, e
);
1296 if ( !__gl_meshDelete( e
) ) return 0;
1302 int __gl_computeInterior( GLUtesselator
*tess
)
1304 * __gl_computeInterior( tess ) computes the planar arrangement specified
1305 * by the given contours, and further subdivides this arrangement
1306 * into regions. Each region is marked "inside" if it belongs
1307 * to the polygon, according to the rule given by tess->windingRule.
1308 * Each interior region is guaranteed be monotone.
1311 GLUvertex
*v
, *vNext
;
1313 tess
->fatalError
= FALSE
;
1315 /* Each vertex defines an event for our sweep line. Start by inserting
1316 * all the vertices in a priority queue. Events are processed in
1317 * lexicographic order, ie.
1319 * e1 < e2 iff e1.x < e2.x || (e1.x == e2.x && e1.y < e2.y)
1321 RemoveDegenerateEdges( tess
);
1322 if ( !InitPriorityQ( tess
) ) return 0; /* if error */
1323 InitEdgeDict( tess
);
1325 /* __gl_pqSortExtractMin */
1326 while( (v
= (GLUvertex
*)pqExtractMin( tess
->pq
)) != NULL
) {
1328 vNext
= (GLUvertex
*)pqMinimum( tess
->pq
); /* __gl_pqSortMinimum */
1329 if( vNext
== NULL
|| ! VertEq( vNext
, v
)) break;
1331 /* Merge together all vertices at exactly the same location.
1332 * This is more efficient than processing them one at a time,
1333 * simplifies the code (see ConnectLeftDegenerate), and is also
1334 * important for correct handling of certain degenerate cases.
1335 * For example, suppose there are two identical edges A and B
1336 * that belong to different contours (so without this code they would
1337 * be processed by separate sweep events). Suppose another edge C
1338 * crosses A and B from above. When A is processed, we split it
1339 * at its intersection point with C. However this also splits C,
1340 * so when we insert B we may compute a slightly different
1341 * intersection point. This might leave two edges with a small
1342 * gap between them. This kind of error is especially obvious
1343 * when using boundary extraction (GLU_TESS_BOUNDARY_ONLY).
1345 vNext
= (GLUvertex
*)pqExtractMin( tess
->pq
); /* __gl_pqSortExtractMin*/
1346 SpliceMergeVertices( tess
, v
->anEdge
, vNext
->anEdge
);
1348 SweepEvent( tess
, v
);
1351 /* Set tess->event for debugging purposes */
1352 /* __GL_DICTLISTKEY */ /* __GL_DICTLISTMIN */
1353 tess
->event
= ((ActiveRegion
*) dictKey( dictMin( tess
->dict
)))->eUp
->Org
;
1355 DoneEdgeDict( tess
);
1356 DonePriorityQ( tess
);
1358 if ( !RemoveDegenerateFaces( tess
->mesh
) ) return 0;
1359 __gl_meshCheckMesh( tess
->mesh
);