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