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