ReactOS  0.4.14-dev-115-g4576127
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
57 extern 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 
103 static void SweepEvent( GLUtesselator *tess, GLUvertex *vEvent );
104 static void WalkDirtyRegions( GLUtesselator *tess, ActiveRegion *regUp );
105 static int CheckForRightSplice( GLUtesselator *tess, ActiveRegion *regUp );
106 
107 static 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 
166 static 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 
340 static void AddRightEdges( GLUtesselator *tess, ActiveRegion *regUp,
341  GLUhalfEdge *eFirst, GLUhalfEdge *eLast, GLUhalfEdge *eTopLeft,
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 
412 static 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;
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 
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 
475 static 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 
499 static int CheckForRightSplice( GLUtesselator *tess, ActiveRegion *regUp )
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 
556 static int CheckForLeftSplice( GLUtesselator *tess, ActiveRegion *regUp )
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 
606 static int CheckForIntersect( GLUtesselator *tess, ActiveRegion *regUp )
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 
760 static 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 
847 static void ConnectRightVertex( GLUtesselator *tess, ActiveRegion *regUp,
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 );
928  eNew->Sym->activeRegion->fixUpperEdge = TRUE;
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;
950  ActiveRegion *reg;
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  */
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  */
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 
1001 static 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 
1068 static 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 
1128 static 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 
1158 static 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 
1173 static void DoneEdgeDict( GLUtesselator *tess )
1174 {
1175  ActiveRegion *reg;
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 
1233 static 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 
1261 static void DonePriorityQ( GLUtesselator *tess )
1262 {
1263  pqDeletePriorityQ( tess->pq ); /* __gl_pqSortDeletePriorityQ */
1264 }
1265 
1266 
1267 static int RemoveDegenerateFaces( GLUmesh *mesh )
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 }
static int CheckForIntersect(GLUtesselator *tess, ActiveRegion *regUp)
Definition: sweep.c:606
double GLdouble
Definition: gl.h:163
#define CALL_COMBINE_OR_COMBINE_DATA(a, b, c, d)
Definition: tess.h:155
#define dictInsertBefore(dict, node, key)
Definition: dict-list.h:49
#define MIN(x, y)
Definition: sweep.c:95
#define AddWinding(eDst, eSrc)
Definition: sweep.c:100
#define pqMinimum(pq)
ActiveRegion * activeRegion
Definition: mesh.h:147
#define VertL1dist(u, v)
Definition: geom.h:70
Definition: mesh.h:163
struct png_info_def **typedef void(__cdecl typeof(png_destroy_read_struct))(struct png_struct_def **
Definition: typeof.h:49
GLUhalfEdge * Lnext
Definition: mesh.h:142
static void DeleteRegion(GLUtesselator *tess, ActiveRegion *reg)
Definition: sweep.c:151
static int FixUpperEdge(ActiveRegion *reg, GLUhalfEdge *newEdge)
Definition: sweep.c:166
void __gl_edgeIntersect(GLUvertex *o1, GLUvertex *d1, GLUvertex *o2, GLUvertex *d2, GLUvertex *v)
Definition: geom.c:203
long pqHandle
Definition: mesh.h:123
int __gl_computeInterior(GLUtesselator *tess)
Definition: sweep.c:1301
GLUvertex * Org
Definition: mesh.h:143
#define GL_FALSE
Definition: gl.h:173
#define dictSearch(dict, key)
Definition: dict-list.h:47
GLdouble n
Definition: glext.h:7729
#define RegionBelow(r)
Definition: sweep.h:74
GLdouble GLdouble t
Definition: gl.h:2047
GLboolean sentinel
Definition: sweep.h:65
#define dictDeleteDict(dict)
Definition: dict-list.h:45
#define assert(x)
Definition: debug.h:53
#define DebugEvent(tess)
Definition: sweep.c:59
GLUface * next
Definition: mesh.h:127
#define CALL_ERROR_OR_ERROR_DATA(a)
Definition: tess.h:160
static void DoneEdgeDict(GLUtesselator *tess)
Definition: sweep.c:1173
static int CheckForLeftSplice(GLUtesselator *tess, ActiveRegion *regUp)
Definition: sweep.c:556
int __gl_meshDelete(GLUhalfEdge *eDel)
Definition: mesh.c:384
int windingNumber
Definition: sweep.h:62
GLUvertex vHead
Definition: mesh.h:164
void * data
Definition: mesh.h:118
GLuint coords
Definition: glext.h:7368
static void ComputeWinding(GLUtesselator *tess, ActiveRegion *reg)
Definition: sweep.c:259
static void SpliceMergeVertices(GLUtesselator *tess, GLUhalfEdge *e1, GLUhalfEdge *e2)
Definition: sweep.c:438
GLUhalfEdge * __gl_meshSplitEdge(GLUhalfEdge *eOrg)
Definition: mesh.c:475
Definition: mesh.h:126
#define dictInsert(dict, key)
Definition: dict-list.h:48
#define dictNewDict(frame, leq)
Definition: dict-list.h:44
static ActiveRegion * TopLeftRegion(ActiveRegion *reg)
Definition: sweep.c:180
DictNode * nodeUp
Definition: sweep.h:61
GLUhalfEdge * __gl_meshConnect(GLUhalfEdge *eOrg, GLUhalfEdge *eDst)
Definition: mesh.c:508
GLdouble coords[3]
Definition: mesh.h:121
#define EdgeEval(u, v, w)
Definition: geom.h:54
static char org[]
Definition: encode.c:7456
#define TRUE
Definition: sweep.c:50
#define GLU_TESS_NEED_COMBINE_CALLBACK
Definition: glu.h:257
#define e
Definition: ke_i.h:82
unsigned char GLboolean
Definition: gl.h:151
static void VertexWeights(GLUvertex *isect, GLUvertex *org, GLUvertex *dst, GLfloat *weights)
Definition: sweep.c:454
static void ConnectRightVertex(GLUtesselator *tess, ActiveRegion *regUp, GLUhalfEdge *eBottomLeft)
Definition: sweep.c:847
GLUface fHead
Definition: mesh.h:165
int __gl_meshSplice(GLUhalfEdge *eOrg, GLUhalfEdge *eDst)
Definition: mesh.c:328
#define pqNewPriorityQ(leq)
smooth NULL
Definition: ftsmooth.c:416
GLUhalfEdge eHead
Definition: mesh.h:166
static int EdgeLeq(GLUtesselator *tess, ActiveRegion *reg1, ActiveRegion *reg2)
Definition: sweep.c:107
static void ConnectLeftDegenerate(GLUtesselator *tess, ActiveRegion *regUp, GLUvertex *vEvent)
Definition: sweep.c:941
GLboolean fixUpperEdge
Definition: sweep.h:69
jmp_buf env
Definition: tess.h:121
static void DonePriorityQ(GLUtesselator *tess)
Definition: sweep.c:1261
int longjmp(jmp_buf buf, int retval)
GLdouble t
Definition: mesh.h:122
GLboolean fatalError
Definition: tess.h:81
GLUhalfEdge * Onext
Definition: mesh.h:141
GLfloat f
Definition: glext.h:7540
#define dictDelete(dict, node)
Definition: dict-list.h:50
GLUhalfEdge * __gl_meshMakeEdge(GLUmesh *mesh)
Definition: mesh.c:275
static void CallCombine(GLUtesselator *tess, GLUvertex *isect, void *data[4], GLfloat weights[4], int needed)
Definition: sweep.c:412
#define pqExtractMin(pq)
#define GLU_TESS_WINDING_POSITIVE
Definition: glu.h:262
GLboolean inside
Definition: sweep.h:64
static int InitPriorityQ(GLUtesselator *tess)
Definition: sweep.c:1233
static ActiveRegion * TopRightRegion(ActiveRegion *reg)
Definition: sweep.c:202
GLUvertex * event
Definition: tess.h:85
#define pqInit(pq)
void __gl_meshCheckMesh(GLUmesh *mesh)
Definition: mesh.c:742
GLint GLenum GLsizei GLsizei GLsizei GLint GLsizei const GLvoid * data
Definition: gl.h:1950
#define LONG_MAX
Definition: limits.h:43
static int CheckForRightSplice(GLUtesselator *tess, ActiveRegion *regUp)
Definition: sweep.c:499
Dict * dict
Definition: tess.h:83
#define pqDeletePriorityQ(pq)
GLUmesh * mesh
Definition: tess.h:66
static int RemoveDegenerateFaces(GLUmesh *mesh)
Definition: sweep.c:1267
#define FALSE
Definition: sweep.c:53
#define EdgeGoesLeft(e)
Definition: geom.h:65
GLenum windingRule
Definition: tess.h:80
struct _cl_event * event
Definition: glext.h:7739
GLdouble s
Definition: mesh.h:122
static void GetIntersectData(GLUtesselator *tess, GLUvertex *isect, GLUvertex *orgUp, GLUvertex *dstUp, GLUvertex *orgLo, GLUvertex *dstLo)
Definition: sweep.c:475
GLUhalfEdge * Sym
Definition: mesh.h:140
#define memFree
Definition: memalloc.h:41
#define EdgeSign(u, v, w)
Definition: geom.h:55
#define GLU_TESS_WINDING_ODD
Definition: glu.h:260
static void WalkDirtyRegions(GLUtesselator *tess, ActiveRegion *regUp)
Definition: sweep.c:760
static void AddRightEdges(GLUtesselator *tess, ActiveRegion *regUp, GLUhalfEdge *eFirst, GLUhalfEdge *eLast, GLUhalfEdge *eTopLeft, GLboolean cleanUp)
Definition: sweep.c:340
#define RegionAbove(r)
Definition: sweep.h:75
GLUhalfEdge * next
Definition: mesh.h:139
#define pqDelete(pq, handle)
GLUhalfEdge * eUp
Definition: sweep.h:60
#define TOLERANCE_NONZERO
Definition: sweep.c:939
const GLdouble * v
Definition: gl.h:2040
GLUvertex * next
Definition: mesh.h:115
int __gl_vertLeq(GLUvertex *u, GLUvertex *v)
Definition: geom.c:40
#define f
Definition: ke_i.h:83
#define VertLeq(u, v)
Definition: geom.h:50
GLenum GLenum dst
Definition: glext.h:6340
static ActiveRegion * AddRegionBelow(GLUtesselator *tess, ActiveRegion *regAbove, GLUhalfEdge *eNewUp)
Definition: sweep.c:213
#define MAX(x, y)
Definition: sweep.c:94
static int reg
Definition: i386-dis.c:1275
struct define * next
Definition: wpp.c:35
static void SweepEvent(GLUtesselator *tess, GLUvertex *vEvent)
Definition: sweep.c:1068
static GLUhalfEdge * FinishLeftRegions(GLUtesselator *tess, ActiveRegion *regFirst, ActiveRegion *regLast)
Definition: sweep.c:284
#define pqInsert(pq, key)
float GLfloat
Definition: gl.h:161
#define VertEq(u, v)
Definition: geom.h:49
#define GLU_TESS_WINDING_NEGATIVE
Definition: glu.h:263
PriorityQ * pq
Definition: tess.h:84
static void FinishRegion(GLUtesselator *tess, ActiveRegion *reg)
Definition: sweep.c:266
const GLbyte * weights
Definition: glext.h:6523
#define dictMin(d)
Definition: dict-list.h:55
#define GLU_TESS_WINDING_ABS_GEQ_TWO
Definition: glu.h:264
static void ConnectLeftVertex(GLUtesselator *tess, GLUvertex *vEvent)
Definition: sweep.c:1001
void cleanUp()
Definition: main.cpp:472
#define dictKey(n)
Definition: dict-list.h:52
static GLboolean IsWindingInside(GLUtesselator *tess, int n)
Definition: sweep.c:238
GLUhalfEdge * anEdge
Definition: mesh.h:117
#define GLU_TESS_WINDING_NONZERO
Definition: glu.h:261
static void InitEdgeDict(GLUtesselator *tess)
Definition: sweep.c:1158
#define SENTINEL_COORD
Definition: sweep.c:1126
#define memAlloc
Definition: memalloc.h:48
static void RemoveDegenerateEdges(GLUtesselator *tess)
Definition: sweep.c:1199
GLboolean dirty
Definition: sweep.h:66
static void AddSentinel(GLUtesselator *tess, GLdouble t)
Definition: sweep.c:1128