Logo ROOT  
Reference Guide
sweep.c
Go to the documentation of this file.
1/*
2 * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008)
3 * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved.
4 *
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:
11 *
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.
16 *
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
23 * SOFTWARE.
24 *
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.
29 */
30/*
31** Author: Eric Veach, July 1994.
32**
33*/
34
35#include "gluos.h"
36#include <assert.h>
37#include <stddef.h>
38#include <setjmp.h> /* longjmp */
39#include <limits.h> /* LONG_MAX */
40
41#include "mesh.h"
42#include "geom.h"
43#include "tess.h"
44#include "dict.h"
45#include "priorityq.h"
46#include "memalloc.h"
47#include "sweep.h"
48
49#ifndef TRUE
50#define TRUE 1
51#endif
52#ifndef FALSE
53#define FALSE 0
54#endif
55
56#ifdef FOR_TRITE_TEST_PROGRAM
57extern void DebugEvent( GLUtesselator *tess );
58#else
59#define DebugEvent( tess )
60#endif
61
62/*
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
72 *
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)
81 *
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.)
90 */
91
92#undef MAX
93#undef MIN
94#define MAX(x,y) ((x) >= (y) ? (x) : (y))
95#define MIN(x,y) ((x) <= (y) ? (x) : (y))
96
97/* When we merge two edges into one, we need to compute the combined
98 * winding of the new edge.
99 */
100#define AddWinding(eDst,eSrc) (eDst->winding += eSrc->winding, \
101 eDst->Sym->winding += eSrc->Sym->winding)
102
103static void SweepEvent( GLUtesselator *tess, GLUvertex *vEvent );
104static void WalkDirtyRegions( GLUtesselator *tess, ActiveRegion *regUp );
105static int CheckForRightSplice( GLUtesselator *tess, ActiveRegion *regUp );
106
107static int EdgeLeq( GLUtesselator *tess, ActiveRegion *reg1,
108 ActiveRegion *reg2 )
109/*
110 * Both edges must be directed from right to left (this is the canonical
111 * direction for the upper edge of each region).
112 *
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.
116 *
117 * Special case: if both edge destinations are at the sweep event,
118 * we sort the edges by slope (they would otherwise compare equally).
119 */
120{
121 GLUvertex *event = tess->event;
122 GLUhalfEdge *e1, *e2;
123 GLdouble t1, t2;
124
125 e1 = reg1->eUp;
126 e2 = reg2->eUp;
127
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.
132 */
133 if( VertLeq( e1->Org, e2->Org )) {
134 return EdgeSign( e2->Dst, e1->Org, e2->Org ) <= 0;
135 }
136 return EdgeSign( e1->Dst, e2->Org, e1->Org ) >= 0;
137 }
138 return EdgeSign( e2->Dst, event, e2->Org ) <= 0;
139 }
140 if( e2->Dst == event ) {
141 return EdgeSign( e1->Dst, event, e1->Org ) >= 0;
142 }
143
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 );
147 return (t1 >= t2);
148}
149
150
152{
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
156 * with a real edge).
157 */
158 assert( reg->eUp->winding == 0 );
159 }
160 reg->eUp->activeRegion = NULL;
161 dictDelete( tess->dict, reg->nodeUp ); /* __gl_dictListDelete */
162 memFree( reg );
163}
164
165
166static int FixUpperEdge( ActiveRegion *reg, GLUhalfEdge *newEdge )
167/*
168 * Replace an upper edge which needs fixing (see ConnectRightVertex).
169 */
170{
171 assert( reg->fixUpperEdge );
172 if ( !__gl_meshDelete( reg->eUp ) ) return 0;
173 reg->fixUpperEdge = FALSE;
174 reg->eUp = newEdge;
175 newEdge->activeRegion = reg;
176
177 return 1;
178}
179
181{
182 GLUvertex *org = reg->eUp->Org;
183 GLUhalfEdge *e;
184
185 /* Find the region above the uppermost edge with the same origin */
186 do {
187 reg = RegionAbove( reg );
188 } while( reg->eUp->Org == org );
189
190 /* If the edge above was a temporary edge introduced by ConnectRightVertex,
191 * now is the time to fix it.
192 */
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 );
198 }
199 return reg;
200}
201
203{
204 GLUvertex *dst = reg->eUp->Dst;
205
206 /* Find the region above the uppermost edge with the same destination */
207 do {
208 reg = RegionAbove( reg );
209 } while( reg->eUp->Dst == dst );
210 return reg;
211}
212
214 ActiveRegion *regAbove,
215 GLUhalfEdge *eNewUp )
216/*
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.
221 */
222{
223 ActiveRegion *regNew = (ActiveRegion *)memAlloc( sizeof( ActiveRegion ));
224 if (regNew == NULL) longjmp(tess->env,1);
225
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;
233
234 eNewUp->activeRegion = regNew;
235 return regNew;
236}
237
239{
240 switch( tess->windingRule ) {
242 return (n & 1);
244 return (n != 0);
246 return (n > 0);
248 return (n < 0);
250 return (n >= 2) || (n <= -2);
251 }
252 /*LINTED*/
253 assert( FALSE );
254 /*NOTREACHED*/
255 return GL_FALSE; /* avoid compiler complaints */
256}
257
258
260{
261 reg->windingNumber = RegionAbove(reg)->windingNumber + reg->eUp->winding;
262 reg->inside = IsWindingInside( tess, reg->windingNumber );
263}
264
265
267/*
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).
273 */
274{
275 GLUhalfEdge *e = reg->eUp;
276 GLUface *f = e->Lface;
277
278 f->inside = reg->inside;
279 f->anEdge = e; /* optimization for __gl_meshTessellateMonoRegion() */
280 DeleteRegion( tess, reg );
281}
282
283
285 ActiveRegion *regFirst, ActiveRegion *regLast )
286/*
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.
297 */
298{
299 ActiveRegion *reg, *regPrev;
300 GLUhalfEdge *e, *ePrev;
301
302 regPrev = regFirst;
303 ePrev = regFirst->eUp;
304 while( regPrev != regLast ) {
305 regPrev->fixUpperEdge = FALSE; /* placement was OK */
306 reg = RegionBelow( regPrev );
307 e = reg->eUp;
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.
315 */
316 FinishRegion( tess, regPrev );
317 break;
318 }
319 /* If the edge below was a temporary edge introduced by
320 * ConnectRightVertex, now is the time to fix it.
321 */
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);
325 }
326
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);
331 }
332 FinishRegion( tess, regPrev ); /* may change reg->eUp */
333 ePrev = reg->eUp;
334 regPrev = reg;
335 }
336 return ePrev;
337}
338
339
340static void AddRightEdges( GLUtesselator *tess, ActiveRegion *regUp,
341 GLUhalfEdge *eFirst, GLUhalfEdge *eLast, GLUhalfEdge *eTopLeft,
342 GLboolean cleanUp )
343/*
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
351 * should be NULL.
352 */
353{
354 ActiveRegion *reg, *regPrev;
355 GLUhalfEdge *e, *ePrev;
356 int firstTime = TRUE;
357
358 /* Insert the new right-going edges in the dictionary */
359 e = eFirst;
360 do {
361 assert( VertLeq( e->Org, e->Dst ));
362 AddRegionBelow( tess, regUp, e->Sym );
363 e = e->Onext;
364 } while ( e != eLast );
365
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).
369 */
370 if( eTopLeft == NULL ) {
371 eTopLeft = RegionBelow( regUp )->eUp->Rprev;
372 }
373 regPrev = regUp;
374 ePrev = eTopLeft;
375 for( ;; ) {
376 reg = RegionBelow( regPrev );
377 e = reg->eUp->Sym;
378 if( e->Org != ePrev->Org ) break;
379
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);
384 }
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 );
388
389 /* Check for two outgoing edges with same slope -- process these
390 * before any intersection tests (see example in __gl_computeInterior).
391 */
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);
397 }
398 firstTime = FALSE;
399 regPrev = reg;
400 ePrev = e;
401 }
402 regPrev->dirty = TRUE;
403 assert( regPrev->windingNumber - e->winding == reg->windingNumber );
404
405 if( cleanUp ) {
406 /* Check for intersections between newly adjacent edges. */
407 WalkDirtyRegions( tess, regPrev );
408 }
409}
410
411
412static void CallCombine( GLUtesselator *tess, GLUvertex *isect,
413 void *data[4], GLfloat weights[4], int needed )
414{
415 GLdouble coords[3];
416
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];
421
422 isect->data = NULL;
423 CALL_COMBINE_OR_COMBINE_DATA( coords, data, weights, &isect->data );
424 if( isect->data == NULL ) {
425 if( ! needed ) {
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.
431 */
433 tess->fatalError = TRUE;
434 }
435 }
436}
437
439 GLUhalfEdge *e2 )
440/*
441 * Two vertices with idential coordinates are combined into one.
442 * e1->Org is kept, while e2->Org is discarded.
443 */
444{
445 void *data[4] = { NULL, NULL, NULL, NULL };
446 GLfloat weights[4] = { 0.5, 0.5, 0.0, 0.0 };
447
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);
452}
453
454static void VertexWeights( GLUvertex *isect, GLUvertex *org, GLUvertex *dst,
455 GLfloat *weights )
456/*
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".
462 */
463{
464 GLdouble t1 = VertL1dist( org, isect );
465 GLdouble t2 = VertL1dist( dst, isect );
466
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];
472}
473
474
475static void GetIntersectData( GLUtesselator *tess, GLUvertex *isect,
476 GLUvertex *orgUp, GLUvertex *dstUp,
477 GLUvertex *orgLo, GLUvertex *dstLo )
478/*
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.
482 */
483{
484 void *data[4];
485 GLfloat weights[4];
486
487 data[0] = orgUp->data;
488 data[1] = dstUp->data;
489 data[2] = orgLo->data;
490 data[3] = dstLo->data;
491
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] );
495
496 CallCombine( tess, isect, data, weights, TRUE );
497}
498
500/*
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).
504 *
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.
514 *
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.
524 */
525{
526 ActiveRegion *regLo = RegionBelow(regUp);
527 GLUhalfEdge *eUp = regUp->eUp;
528 GLUhalfEdge *eLo = regLo->eUp;
529
530 if( VertLeq( eUp->Org, eLo->Org )) {
531 if( EdgeSign( eLo->Dst, eUp->Org, eLo->Org ) > 0 ) return FALSE;
532
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;
539
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 );
544 }
545 } else {
546 if( EdgeSign( eUp->Dst, eLo->Org, eUp->Org ) < 0 ) return FALSE;
547
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);
552 }
553 return TRUE;
554}
555
557/*
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).
561 *
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).
571 *
572 * We fix the problem by just splicing the offending vertex into the
573 * other edge.
574 */
575{
576 ActiveRegion *regLo = RegionBelow(regUp);
577 GLUhalfEdge *eUp = regUp->eUp;
578 GLUhalfEdge *eLo = regLo->eUp;
579 GLUhalfEdge *e;
580
581 assert( ! VertEq( eUp->Dst, eLo->Dst ));
582
583 if( VertLeq( eUp->Dst, eLo->Dst )) {
584 if( EdgeSign( eUp->Dst, eLo->Dst, eUp->Org ) < 0 ) return FALSE;
585
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;
592 } else {
593 if( EdgeSign( eLo->Dst, eUp->Dst, eLo->Org ) > 0 ) return FALSE;
594
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;
601 }
602 return TRUE;
603}
604
605
607/*
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.
611 *
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.
615 */
616{
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;
626 GLUhalfEdge *e;
627
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 );
633
634 if( orgUp == orgLo ) return FALSE; /* right endpoints are the same */
635
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 */
639
640 if( VertLeq( orgUp, orgLo )) {
641 if( EdgeSign( dstLo, orgUp, orgLo ) > 0 ) return FALSE;
642 } else {
643 if( EdgeSign( dstUp, orgLo, orgUp ) < 0 ) return FALSE;
644 }
645
646 /* At this point the edges intersect, at least marginally */
647 DebugEvent( tess );
648
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 ));
655
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.
662 */
663 isect.s = tess->event->s;
664 isect.t = tess->event->t;
665 }
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).
671 */
672 orgMin = VertLeq( orgUp, orgLo ) ? orgUp : orgLo;
673 if( VertLeq( orgMin, &isect )) {
674 isect.s = orgMin->s;
675 isect.t = orgMin->t;
676 }
677
678 if( VertEq( &isect, orgUp ) || VertEq( &isect, orgLo )) {
679 /* Easy case -- intersection at one of the right endpoints */
680 (void) CheckForRightSplice( tess, regUp );
681 return FALSE;
682 }
683
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 ))
688 {
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.
692 */
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 );
702 return TRUE;
703 }
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);
708 regLo = regUp;
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 );
714 return TRUE;
715 }
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).
719 */
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;
725 }
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;
731 }
732 /* leave the rest for ConnectRightVertex */
733 return FALSE;
734 }
735
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).
743 */
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 */
752 tess->pq = NULL;
753 longjmp(tess->env,1);
754 }
755 GetIntersectData( tess, eUp->Org, orgUp, dstUp, orgLo, dstLo );
756 RegionAbove(regUp)->dirty = regUp->dirty = regLo->dirty = TRUE;
757 return FALSE;
758}
759
760static void WalkDirtyRegions( GLUtesselator *tess, ActiveRegion *regUp )
761/*
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
767 * the invariants.
768 */
769{
770 ActiveRegion *regLo = RegionBelow(regUp);
771 GLUhalfEdge *eUp, *eLo;
772
773 for( ;; ) {
774 /* Find the lowest dirty region (we walk from the bottom up). */
775 while( regLo->dirty ) {
776 regUp = regLo;
777 regLo = RegionBelow(regLo);
778 }
779 if( ! regUp->dirty ) {
780 regLo = regUp;
781 regUp = RegionAbove( regUp );
782 if( regUp == NULL || ! regUp->dirty ) {
783 /* We've walked all the dirty regions */
784 return;
785 }
786 }
787 regUp->dirty = FALSE;
788 eUp = regUp->eUp;
789 eLo = regLo->eUp;
790
791 if( eUp->Dst != eLo->Dst ) {
792 /* Check that the edge ordering is obeyed at the Dst vertices. */
793 if( CheckForLeftSplice( tess, regUp )) {
794
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).
798 */
799 if( regLo->fixUpperEdge ) {
800 DeleteRegion( tess, regLo );
801 if ( !__gl_meshDelete( eLo ) ) longjmp(tess->env,1);
802 regLo = RegionBelow( regUp );
803 eLo = regLo->eUp;
804 } else if( regUp->fixUpperEdge ) {
805 DeleteRegion( tess, regUp );
806 if ( !__gl_meshDelete( eUp ) ) longjmp(tess->env,1);
807 regUp = RegionAbove( regLo );
808 eUp = regUp->eUp;
809 }
810 }
811 }
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) )
816 {
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).
824 */
825 if( CheckForIntersect( tess, regUp )) {
826 /* WalkDirtyRegions() was called recursively; we're done */
827 return;
828 }
829 } else {
830 /* Even though we can't use CheckForIntersect(), the Org vertices
831 * may violate the dictionary edge ordering. Check and correct this.
832 */
833 (void) CheckForRightSplice( tess, regUp );
834 }
835 }
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 );
842 }
843 }
844}
845
846
848 GLUhalfEdge *eBottomLeft )
849/*
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.
854 *
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.
862 *
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.)
868 *
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.
879 */
880{
881 GLUhalfEdge *eNew;
882 GLUhalfEdge *eTopLeft = eBottomLeft->Onext;
883 ActiveRegion *regLo = RegionBelow(regUp);
884 GLUhalfEdge *eUp = regUp->eUp;
885 GLUhalfEdge *eLo = regLo->eUp;
886 int degenerate = FALSE;
887
888 if( eUp->Dst != eLo->Dst ) {
889 (void) CheckForIntersect( tess, regUp );
890 }
891
892 /* Possible new degeneracies: upper or lower edge of regUp may pass
893 * through vEvent, or may coincide with new intersection vertex
894 */
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 );
901 degenerate = TRUE;
902 }
903 if( VertEq( eLo->Org, tess->event )) {
904 if ( !__gl_meshSplice( eBottomLeft, eLo->Oprev ) ) longjmp(tess->env,1);
905 eBottomLeft = FinishLeftRegions( tess, regLo, NULL );
906 degenerate = TRUE;
907 }
908 if( degenerate ) {
909 AddRightEdges( tess, regUp, eBottomLeft->Onext, eTopLeft, eTopLeft, TRUE );
910 return;
911 }
912
913 /* Non-degenerate situation -- need to add a temporary, fixable edge.
914 * Connect to the closer of eLo->Org, eUp->Org.
915 */
916 if( VertLeq( eLo->Org, eUp->Org )) {
917 eNew = eLo->Oprev;
918 } else {
919 eNew = eUp;
920 }
921 eNew = __gl_meshConnect( eBottomLeft->Lprev, eNew );
922 if (eNew == NULL) longjmp(tess->env,1);
923
924 /* Prevent cleanup, otherwise eNew might disappear before we've even
925 * had a chance to mark it as a temporary edge.
926 */
927 AddRightEdges( tess, regUp, eNew, eNew->Onext, eNew->Onext, FALSE );
929 WalkDirtyRegions( tess, regUp );
930}
931
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.
938 */
939#define TOLERANCE_NONZERO FALSE
940
942 ActiveRegion *regUp, GLUvertex *vEvent )
943/*
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
946 * part of the mesh.
947 */
948{
949 GLUhalfEdge *e, *eTopLeft, *eTopRight, *eLast;
951
952 e = regUp->eUp;
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
956 */
957 assert( TOLERANCE_NONZERO );
958 SpliceMergeVertices( tess, e, vEvent->anEdge );
959 return;
960 }
961
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;
969 }
970 if ( !__gl_meshSplice( vEvent->anEdge, e ) ) longjmp(tess->env,1);
971 SweepEvent( tess, vEvent ); /* recurse */
972 return;
973 }
974
975 /* vEvent coincides with e->Dst, which has already been processed.
976 * Splice in the additional right-going edges.
977 */
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.
986 */
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;
991 }
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() */
995 eTopLeft = NULL;
996 }
997 AddRightEdges( tess, regUp, eTopRight->Onext, eLast, eTopLeft, TRUE );
998}
999
1000
1001static void ConnectLeftVertex( GLUtesselator *tess, GLUvertex *vEvent )
1002/*
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:
1007 *
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
1010 *
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
1016 */
1017{
1018 ActiveRegion *regUp, *regLo, *reg;
1019 GLUhalfEdge *eUp, *eLo, *eNew;
1020 ActiveRegion tmp;
1021
1022 /* assert( vEvent->anEdge->Onext->Onext == vEvent->anEdge ); */
1023
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 );
1029 eUp = regUp->eUp;
1030 eLo = regLo->eUp;
1031
1032 /* Try merging with U or L first */
1033 if( EdgeSign( eUp->Dst, vEvent, eUp->Org ) == 0 ) {
1034 ConnectLeftDegenerate( tess, regUp, vEvent );
1035 return;
1036 }
1037
1038 /* Connect vEvent to rightmost processed vertex of either chain.
1039 * e->Dst is the vertex that we will connect to vEvent.
1040 */
1041 reg = VertLeq( eLo->Dst, eUp->Dst ) ? regUp : regLo;
1042
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);
1047 } else {
1048 GLUhalfEdge *tempHalfEdge= __gl_meshConnect( eLo->Dnext, vEvent->anEdge);
1049 if (tempHalfEdge == NULL) longjmp(tess->env,1);
1050
1051 eNew = tempHalfEdge->Sym;
1052 }
1053 if( reg->fixUpperEdge ) {
1054 if ( !FixUpperEdge( reg, eNew ) ) longjmp(tess->env,1);
1055 } else {
1056 ComputeWinding( tess, AddRegionBelow( tess, regUp, eNew ));
1057 }
1058 SweepEvent( tess, vEvent );
1059 } else {
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.
1062 */
1063 AddRightEdges( tess, regUp, vEvent->anEdge, vEvent->anEdge, NULL, TRUE );
1064 }
1065}
1066
1067
1068static void SweepEvent( GLUtesselator *tess, GLUvertex *vEvent )
1069/*
1070 * Does everything necessary when the sweep line crosses a vertex.
1071 * Updates the mesh and the edge dictionary.
1072 */
1073{
1074 ActiveRegion *regUp, *reg;
1075 GLUhalfEdge *e, *eTopLeft, *eBottomLeft;
1076
1077 tess->event = vEvent; /* for access in EdgeLeq() */
1078 DebugEvent( tess );
1079
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.
1083 */
1084 e = vEvent->anEdge;
1085 while( e->activeRegion == NULL ) {
1086 e = e->Onext;
1087 if( e == vEvent->anEdge ) {
1088 /* All edges go right -- not incident to any processed edges */
1089 ConnectLeftVertex( tess, vEvent );
1090 return;
1091 }
1092 }
1093
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.
1100 */
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 );
1106
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.
1111 */
1112 if( eBottomLeft->Onext == eTopLeft ) {
1113 /* No right-going edges -- add a temporary "fixable" edge */
1114 ConnectRightVertex( tess, regUp, eBottomLeft );
1115 } else {
1116 AddRightEdges( tess, regUp, eBottomLeft->Onext, eTopLeft, eTopLeft, TRUE );
1117 }
1118}
1119
1120
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).
1125 */
1126#define SENTINEL_COORD (4 * GLU_TESS_MAX_COORD)
1127
1128static void AddSentinel( GLUtesselator *tess, GLdouble t )
1129/*
1130 * We add two sentinel edges above and below all other edges,
1131 * to avoid special cases at the top and bottom.
1132 */
1133{
1134 GLUhalfEdge *e;
1136 if (reg == NULL) longjmp(tess->env,1);
1137
1138 e = __gl_meshMakeEdge( tess->mesh );
1139 if (e == NULL) longjmp(tess->env,1);
1140
1141 e->Org->s = SENTINEL_COORD;
1142 e->Org->t = t;
1143 e->Dst->s = -SENTINEL_COORD;
1144 e->Dst->t = t;
1145 tess->event = e->Dst; /* initialize it */
1146
1147 reg->eUp = e;
1148 reg->windingNumber = 0;
1149 reg->inside = FALSE;
1150 reg->fixUpperEdge = FALSE;
1151 reg->sentinel = TRUE;
1152 reg->dirty = FALSE;
1153 reg->nodeUp = dictInsert( tess->dict, reg ); /* __gl_dictListInsertBefore */
1154 if (reg->nodeUp == NULL) longjmp(tess->env,1);
1155}
1156
1157
1158static void InitEdgeDict( GLUtesselator *tess )
1159/*
1160 * We maintain an ordering of edge intersections with the sweep line.
1161 * This order is maintained in a dynamic dictionary.
1162 */
1163{
1164 /* __gl_dictListNewDict */
1165 tess->dict = dictNewDict( tess, (int (*)(void *, DictKey, DictKey)) EdgeLeq );
1166 if (tess->dict == NULL) longjmp(tess->env,1);
1167
1168 AddSentinel( tess, -SENTINEL_COORD );
1169 AddSentinel( tess, SENTINEL_COORD );
1170}
1171
1172
1173static void DoneEdgeDict( GLUtesselator *tess )
1174{
1176#ifndef NDEBUG
1177 int fixedEdges = 0;
1178#endif
1179
1180 /* __GL_DICTLISTKEY */ /* __GL_DICTLISTMIN */
1181 while( (reg = (ActiveRegion *)dictKey( dictMin( tess->dict ))) != NULL ) {
1182 /*
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().
1186 */
1187 if( ! reg->sentinel ) {
1188 assert( reg->fixUpperEdge );
1189 assert( ++fixedEdges == 1 );
1190 }
1191 assert( reg->windingNumber == 0 );
1192 DeleteRegion( tess, reg );
1193/* __gl_meshDelete( reg->eUp );*/
1194 }
1195 dictDeleteDict( tess->dict ); /* __gl_dictListDeleteDict */
1196}
1197
1198
1200/*
1201 * Remove zero-length edges, and contours with fewer than 3 vertices.
1202 */
1203{
1204 GLUhalfEdge *e, *eNext, *eLnext;
1205 GLUhalfEdge *eHead = &tess->mesh->eHead;
1206
1207 /*LINTED*/
1208 for( e = eHead->next; e != eHead; e = eNext ) {
1209 eNext = e->next;
1210 eLnext = e->Lnext;
1211
1212 if( VertEq( e->Org, e->Dst ) && e->Lnext->Lnext != e ) {
1213 /* Zero-length edge, contour has at least 3 edges */
1214
1215 SpliceMergeVertices( tess, eLnext, e ); /* deletes e->Org */
1216 if ( !__gl_meshDelete( e ) ) longjmp(tess->env,1); /* e is a self-loop */
1217 e = eLnext;
1218 eLnext = e->Lnext;
1219 }
1220 if( eLnext->Lnext == e ) {
1221 /* Degenerate contour (one or two edges) */
1222
1223 if( eLnext != e ) {
1224 if( eLnext == eNext || eLnext == eNext->Sym ) { eNext = eNext->next; }
1225 if ( !__gl_meshDelete( eLnext ) ) longjmp(tess->env,1);
1226 }
1227 if( e == eNext || e == eNext->Sym ) { eNext = eNext->next; }
1228 if ( !__gl_meshDelete( e ) ) longjmp(tess->env,1);
1229 }
1230 }
1231}
1232
1233static int InitPriorityQ( GLUtesselator *tess )
1234/*
1235 * Insert all vertices into the priority queue which determines the
1236 * order in which vertices cross the sweep line.
1237 */
1238{
1239 PriorityQ *pq;
1240 GLUvertex *v, *vHead;
1241
1242 /* __gl_pqSortNewPriorityQ */
1243 pq = tess->pq = pqNewPriorityQ( (int (*)(PQkey, PQkey)) __gl_vertLeq );
1244 if (pq == NULL) return 0;
1245
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;
1250 }
1251 if (v != vHead || !pqInit( pq ) ) { /* __gl_pqSortInit */
1252 pqDeletePriorityQ(tess->pq); /* __gl_pqSortDeletePriorityQ */
1253 tess->pq = NULL;
1254 return 0;
1255 }
1256
1257 return 1;
1258}
1259
1260
1261static void DonePriorityQ( GLUtesselator *tess )
1262{
1263 pqDeletePriorityQ( tess->pq ); /* __gl_pqSortDeletePriorityQ */
1264}
1265
1266
1268/*
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.
1277 *
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.
1281 */
1282{
1283 GLUface *f, *fNext;
1284 GLUhalfEdge *e;
1285
1286 /*LINTED*/
1287 for( f = mesh->fHead.next; f != &mesh->fHead; f = fNext ) {
1288 fNext = f->next;
1289 e = f->anEdge;
1290 assert( e->Lnext != e );
1291
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;
1296 }
1297 }
1298 return 1;
1299}
1300
1302/*
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.
1308 */
1309{
1310 GLUvertex *v, *vNext;
1311
1312 tess->fatalError = FALSE;
1313
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.
1317 *
1318 * e1 < e2 iff e1.x < e2.x || (e1.x == e2.x && e1.y < e2.y)
1319 */
1320 RemoveDegenerateEdges( tess );
1321 if ( !InitPriorityQ( tess ) ) return 0; /* if error */
1322 InitEdgeDict( tess );
1323
1324 /* __gl_pqSortExtractMin */
1325 while( (v = (GLUvertex *)pqExtractMin( tess->pq )) != NULL ) {
1326 for( ;; ) {
1327 vNext = (GLUvertex *)pqMinimum( tess->pq ); /* __gl_pqSortMinimum */
1328 if( vNext == NULL || ! VertEq( vNext, v )) break;
1329
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).
1343 */
1344 vNext = (GLUvertex *)pqExtractMin( tess->pq ); /* __gl_pqSortExtractMin*/
1345 SpliceMergeVertices( tess, v->anEdge, vNext->anEdge );
1346 }
1347 SweepEvent( tess, v );
1348 }
1349
1350 /* Set tess->event for debugging purposes */
1351 /* __GL_DICTLISTKEY */ /* __GL_DICTLISTMIN */
1352 tess->event = ((ActiveRegion *) dictKey( dictMin( tess->dict )))->eUp->Org;
1353 DebugEvent( tess );
1354 DoneEdgeDict( tess );
1355 DonePriorityQ( tess );
1356
1357 if ( !RemoveDegenerateFaces( tess->mesh ) ) return 0;
1358 __gl_meshCheckMesh( tess->mesh );
1359
1360 return 1;
1361}
#define GLU_TESS_WINDING_NONZERO
Definition: GL_glu.h:254
#define GLU_TESS_WINDING_POSITIVE
Definition: GL_glu.h:255
float GLfloat
Definition: GL_glu.h:277
#define GLU_TESS_WINDING_NEGATIVE
Definition: GL_glu.h:256
double GLdouble
Definition: GL_glu.h:279
unsigned char GLboolean
Definition: GL_glu.h:267
#define GLU_TESS_WINDING_ODD
Definition: GL_glu.h:253
#define GLU_TESS_NEED_COMBINE_CALLBACK
Definition: GL_glu.h:250
#define GL_FALSE
Definition: GL_glu.h:261
#define GLU_TESS_WINDING_ABS_GEQ_TWO
Definition: GL_glu.h:257
#define f(i)
Definition: RSha256.hxx:104
#define e(i)
Definition: RSha256.hxx:103
Option_t Option_t TPoint TPoint const char GetTextMagnitude GetFillStyle GetLineColor GetLineWidth GetMarkerStyle GetTextAlign GetTextColor GetTextSize void data
Option_t Option_t TPoint TPoint const char GetTextMagnitude GetFillStyle GetLineColor GetLineWidth GetMarkerStyle GetTextAlign GetTextColor GetTextSize void char Point_t Rectangle_t WindowAttributes_t Float_t Float_t Float_t Int_t Int_t UInt_t UInt_t Rectangle_t org
Option_t Option_t TPoint TPoint const char GetTextMagnitude GetFillStyle GetLineColor GetLineWidth GetMarkerStyle GetTextAlign GetTextColor GetTextSize void reg
#define dictInsert(dict, key)
Definition: dict-list.h:48
#define dictDeleteDict(dict)
Definition: dict-list.h:45
#define dictSearch(dict, key)
Definition: dict-list.h:47
#define dictMin(d)
Definition: dict-list.h:55
#define dictDelete(dict, node)
Definition: dict-list.h:50
#define dictInsertBefore(dict, node, key)
Definition: dict-list.h:49
#define DictKey
Definition: dict-list.h:40
#define dictNewDict(frame, leq)
Definition: dict-list.h:44
#define dictKey(n)
Definition: dict-list.h:52
void __gl_edgeIntersect(GLUvertex *o1, GLUvertex *d1, GLUvertex *o2, GLUvertex *d2, GLUvertex *v)
Definition: geom.c:203
int __gl_vertLeq(GLUvertex *u, GLUvertex *v)
Definition: geom.c:40
#define VertLeq(u, v)
Definition: geom.h:50
#define VertEq(u, v)
Definition: geom.h:49
#define EdgeGoesLeft(e)
Definition: geom.h:65
#define EdgeSign(u, v, w)
Definition: geom.h:55
#define EdgeEval(u, v, w)
Definition: geom.h:54
#define VertL1dist(u, v)
Definition: geom.h:70
const Int_t n
Definition: legend1.C:16
#define memAlloc
Definition: memalloc.h:48
#define memFree
Definition: memalloc.h:41
GLUhalfEdge * __gl_meshMakeEdge(GLUmesh *mesh)
Definition: mesh.c:270
GLUhalfEdge * __gl_meshSplitEdge(GLUhalfEdge *eOrg)
Definition: mesh.c:470
void __gl_meshCheckMesh(GLUmesh *mesh)
Definition: mesh.c:737
GLUhalfEdge * __gl_meshConnect(GLUhalfEdge *eOrg, GLUhalfEdge *eDst)
Definition: mesh.c:503
int __gl_meshDelete(GLUhalfEdge *eDel)
Definition: mesh.c:379
int __gl_meshSplice(GLUhalfEdge *eOrg, GLUhalfEdge *eDst)
Definition: mesh.c:323
void(off) SmallVectorTemplateBase< T
#define pqNewPriorityQ(leq)
#define pqDeletePriorityQ(pq)
#define PriorityQ
#define pqInit(pq)
#define pqDelete(pq, handle)
#define pqExtractMin(pq)
#define pqMinimum(pq)
#define PQkey
#define pqInsert(pq, key)
GLboolean fixUpperEdge
Definition: sweep.h:69
GLboolean dirty
Definition: sweep.h:66
GLUhalfEdge * eUp
Definition: sweep.h:60
int windingNumber
Definition: sweep.h:62
GLboolean inside
Definition: sweep.h:64
DictListNode * nodeUp
Definition: sweep.h:61
GLboolean sentinel
Definition: sweep.h:65
Definition: mesh.h:126
GLUhalfEdge * Lnext
Definition: mesh.h:142
GLUvertex * Org
Definition: mesh.h:143
GLUhalfEdge * Onext
Definition: mesh.h:141
ActiveRegion * activeRegion
Definition: mesh.h:147
GLUhalfEdge * Sym
Definition: mesh.h:140
GLUhalfEdge * next
Definition: mesh.h:139
Definition: mesh.h:168
GLUvertex vHead
Definition: mesh.h:169
GLUhalfEdge eHead
Definition: mesh.h:171
GLUvertex * event
Definition: tess.h:85
GLenum windingRule
Definition: tess.h:80
PriorityQHeap * pq
Definition: tess.h:84
GLboolean fatalError
Definition: tess.h:81
DictList * dict
Definition: tess.h:83
GLUmesh * mesh
Definition: tess.h:66
jmp_buf env
Definition: tess.h:121
GLUhalfEdge * anEdge
Definition: mesh.h:117
GLdouble t
Definition: mesh.h:122
GLdouble coords[3]
Definition: mesh.h:121
GLdouble s
Definition: mesh.h:122
GLUvertex * next
Definition: mesh.h:115
long pqHandle
Definition: mesh.h:123
void * data
Definition: mesh.h:118
Definition: triangle.c:632
static void InitEdgeDict(GLUtesselator *tess)
Definition: sweep.c:1158
static int FixUpperEdge(ActiveRegion *reg, GLUhalfEdge *newEdge)
Definition: sweep.c:166
#define AddWinding(eDst, eSrc)
Definition: sweep.c:100
static GLboolean IsWindingInside(GLUtesselator *tess, int n)
Definition: sweep.c:238
static void RemoveDegenerateEdges(GLUtesselator *tess)
Definition: sweep.c:1199
static int CheckForRightSplice(GLUtesselator *tess, ActiveRegion *regUp)
Definition: sweep.c:499
static void CallCombine(GLUtesselator *tess, GLUvertex *isect, void *data[4], GLfloat weights[4], int needed)
Definition: sweep.c:412
static int RemoveDegenerateFaces(GLUmesh *mesh)
Definition: sweep.c:1267
int __gl_computeInterior(GLUtesselator *tess)
Definition: sweep.c:1301
static GLUhalfEdge * FinishLeftRegions(GLUtesselator *tess, ActiveRegion *regFirst, ActiveRegion *regLast)
Definition: sweep.c:284
static void FinishRegion(GLUtesselator *tess, ActiveRegion *reg)
Definition: sweep.c:266
static void SweepEvent(GLUtesselator *tess, GLUvertex *vEvent)
Definition: sweep.c:1068
static ActiveRegion * TopLeftRegion(ActiveRegion *reg)
Definition: sweep.c:180
#define DebugEvent(tess)
Definition: sweep.c:59
static ActiveRegion * AddRegionBelow(GLUtesselator *tess, ActiveRegion *regAbove, GLUhalfEdge *eNewUp)
Definition: sweep.c:213
#define SENTINEL_COORD
Definition: sweep.c:1126
static int InitPriorityQ(GLUtesselator *tess)
Definition: sweep.c:1233
#define MIN(x, y)
Definition: sweep.c:95
static void AddRightEdges(GLUtesselator *tess, ActiveRegion *regUp, GLUhalfEdge *eFirst, GLUhalfEdge *eLast, GLUhalfEdge *eTopLeft, GLboolean cleanUp)
Definition: sweep.c:340
static void GetIntersectData(GLUtesselator *tess, GLUvertex *isect, GLUvertex *orgUp, GLUvertex *dstUp, GLUvertex *orgLo, GLUvertex *dstLo)
Definition: sweep.c:475
static void DeleteRegion(GLUtesselator *tess, ActiveRegion *reg)
Definition: sweep.c:151
static void VertexWeights(GLUvertex *isect, GLUvertex *org, GLUvertex *dst, GLfloat *weights)
Definition: sweep.c:454
static ActiveRegion * TopRightRegion(ActiveRegion *reg)
Definition: sweep.c:202
static void WalkDirtyRegions(GLUtesselator *tess, ActiveRegion *regUp)
Definition: sweep.c:760
static void ConnectLeftVertex(GLUtesselator *tess, GLUvertex *vEvent)
Definition: sweep.c:1001
static int CheckForIntersect(GLUtesselator *tess, ActiveRegion *regUp)
Definition: sweep.c:606
#define TRUE
Definition: sweep.c:50
#define FALSE
Definition: sweep.c:53
#define MAX(x, y)
Definition: sweep.c:94
static int EdgeLeq(GLUtesselator *tess, ActiveRegion *reg1, ActiveRegion *reg2)
Definition: sweep.c:107
static void ConnectRightVertex(GLUtesselator *tess, ActiveRegion *regUp, GLUhalfEdge *eBottomLeft)
Definition: sweep.c:847
static void DoneEdgeDict(GLUtesselator *tess)
Definition: sweep.c:1173
static void ComputeWinding(GLUtesselator *tess, ActiveRegion *reg)
Definition: sweep.c:259
static void ConnectLeftDegenerate(GLUtesselator *tess, ActiveRegion *regUp, GLUvertex *vEvent)
Definition: sweep.c:941
static int CheckForLeftSplice(GLUtesselator *tess, ActiveRegion *regUp)
Definition: sweep.c:556
static void DonePriorityQ(GLUtesselator *tess)
Definition: sweep.c:1261
#define TOLERANCE_NONZERO
Definition: sweep.c:939
static void SpliceMergeVertices(GLUtesselator *tess, GLUhalfEdge *e1, GLUhalfEdge *e2)
Definition: sweep.c:438
static void AddSentinel(GLUtesselator *tess, GLdouble t)
Definition: sweep.c:1128
#define RegionAbove(r)
Definition: sweep.h:75
#define RegionBelow(r)
Definition: sweep.h:74
#define CALL_ERROR_OR_ERROR_DATA(a)
Definition: tess.h:160
#define CALL_COMBINE_OR_COMBINE_DATA(a, b, c, d)
Definition: tess.h:155
auto * t1
Definition: textangle.C:20