2
* SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008)
3
* Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved.
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:
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.
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
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.
31
** Author: Eric Veach, July 1994.
37
#include <setjmp.h> /* longjmp */
38
#include <limits.h> /* LONG_MAX */
44
#include "priorityq.h"
51
#ifdef FOR_TRITE_TEST_PROGRAM
52
extern void DebugEvent(GLUEStesselator* tess);
54
#define DebugEvent(tess)
58
* Invariants for the Edge Dictionary.
59
* - each pair of adjacent edges e2=Succ(e1) satisfies EdgeLeq(e1,e2)
60
* at any valid location of the sweep event
61
* - if EdgeLeq(e2,e1) as well (at any valid sweep event), then e1 and e2
62
* share a common endpoint
63
* - for each e, e->Dst has been processed, but not e->Org
64
* - each edge e satisfies VertLeq(e->Dst,event) && VertLeq(event,e->Org)
65
* where "event" is the current sweep line event.
66
* - no edge e has zero length
68
* Invariants for the Mesh (the processed portion).
69
* - the portion of the mesh left of the sweep line is a planar graph,
70
* ie. there is *some* way to embed it in the plane
71
* - no processed edge has zero length
72
* - no two processed vertices have identical coordinates
73
* - each "inside" region is monotone, ie. can be broken into two chains
74
* of monotonically increasing vertices according to VertLeq(v1,v2)
75
* - a non-invariant: these chains may intersect (very slightly)
77
* Invariants for the Sweep.
78
* - if none of the edges incident to the event vertex have an activeRegion
79
* (ie. none of these edges are in the edge dictionary), then the vertex
80
* has only right-going edges.
81
* - if an edge is marked "fixUpperEdge" (it is a temporary edge introduced
82
* by ConnectRightVertex), then it is the only right-going edge from
83
* its associated vertex. (This says that these edges exist only
84
* when it is necessary.)
89
#define MAX(x, y) ((x)>=(y) ? (x) : (y))
90
#define MIN(x, y) ((x)<=(y) ? (x) : (y))
92
/* When we merge two edges into one, we need to compute the combined
93
* winding of the new edge.
95
#define AddWinding(eDst,eSrc) (eDst->winding+=eSrc->winding, \
96
eDst->Sym->winding += eSrc->Sym->winding)
98
static void SweepEvent(GLUEStesselator* tess, GLUESvertex* vEvent);
99
static void WalkDirtyRegions(GLUEStesselator* tess, ActiveRegion* regUp);
100
static int CheckForRightSplice(GLUEStesselator* tess, ActiveRegion* regUp);
103
* Both edges must be directed from right to left (this is the canonical
104
* direction for the upper edge of each region).
106
* The strategy is to evaluate a "t" value for each edge at the
107
* current sweep line position, given by tess->event. The calculations
108
* are designed to be very stable, but of course they are not perfect.
110
* Special case: if both edge destinations are at the sweep event,
111
* we sort the edges by slope (they would otherwise compare equally).
113
static int EdgeLeq(GLUEStesselator* tess, ActiveRegion* reg1, ActiveRegion* reg2)
115
GLUESvertex* event=tess->event;
127
/* Two edges right of the sweep line which meet at the sweep event.
128
* Sort them by slope.
130
if (VertLeq(e1->Org, e2->Org))
132
return EdgeSign(e2->Dst, e1->Org, e2->Org)<=0;
135
return EdgeSign(e1->Dst, e2->Org, e1->Org)>=0;
137
return EdgeSign( e2->Dst, event, e2->Org ) <= 0;
142
return EdgeSign(e1->Dst, event, e1->Org)>=0;
145
/* General case - compute signed distance *from* e1, e2 to event */
146
t1=EdgeEval(e1->Dst, event, e1->Org);
147
t2=EdgeEval(e2->Dst, event, e2->Org);
152
static void DeleteRegion(GLUEStesselator* tess, ActiveRegion* reg)
154
if (reg->fixUpperEdge)
156
/* It was created with zero winding number, so it better be
157
* deleted with zero winding number (ie. it better not get merged
160
assert(reg->eUp->winding==0);
162
reg->eUp->activeRegion=NULL;
163
dictDelete(tess->dict, reg->nodeUp); /* __gl_dictListDelete */
168
* Replace an upper edge which needs fixing (see ConnectRightVertex).
170
static int FixUpperEdge(ActiveRegion* reg, GLUEShalfEdge* newEdge)
172
assert(reg->fixUpperEdge);
173
if (!__gl_meshDelete(reg->eUp))
177
reg->fixUpperEdge=FALSE;
179
newEdge->activeRegion=reg;
184
static ActiveRegion* TopLeftRegion(ActiveRegion* reg)
186
GLUESvertex* org=reg->eUp->Org;
189
/* Find the region above the uppermost edge with the same origin */
191
reg=RegionAbove(reg);
192
} while(reg->eUp->Org==org);
194
/* If the edge above was a temporary edge introduced by ConnectRightVertex,
195
* now is the time to fix it.
197
if (reg->fixUpperEdge)
199
e=__gl_meshConnect(RegionBelow(reg)->eUp->Sym, reg->eUp->Lnext);
204
if (!FixUpperEdge(reg, e))
208
reg=RegionAbove(reg);
213
static ActiveRegion* TopRightRegion(ActiveRegion* reg)
215
GLUESvertex* dst=reg->eUp->Dst;
217
/* Find the region above the uppermost edge with the same destination */
219
reg=RegionAbove(reg);
220
} while(reg->eUp->Dst==dst);
226
* Add a new active region to the sweep line, *somewhere* below "regAbove"
227
* (according to where the new edge belongs in the sweep-line dictionary).
228
* The upper edge of the new region will be "eNewUp".
229
* Winding number and "inside" flag are not updated.
231
static ActiveRegion* AddRegionBelow(GLUEStesselator* tess, ActiveRegion* regAbove,
232
GLUEShalfEdge* eNewUp)
234
ActiveRegion* regNew=(ActiveRegion*)memAlloc(sizeof(ActiveRegion));
237
longjmp(tess->env, 1);
241
/* __gl_dictListInsertBefore */
242
regNew->nodeUp=dictInsertBefore(tess->dict, regAbove->nodeUp, regNew);
243
if (regNew->nodeUp==NULL)
245
longjmp(tess->env, 1);
247
regNew->fixUpperEdge=FALSE;
248
regNew->sentinel=FALSE;
251
eNewUp->activeRegion=regNew;
256
static GLboolean IsWindingInside(GLUEStesselator* tess, int n)
258
switch (tess->windingRule)
260
case GLUES_TESS_WINDING_ODD:
262
case GLUES_TESS_WINDING_NONZERO:
264
case GLUES_TESS_WINDING_POSITIVE:
266
case GLUES_TESS_WINDING_NEGATIVE:
268
case GLUES_TESS_WINDING_ABS_GEQ_TWO:
269
return (n>=2) || (n<=-2);
276
/* avoid compiler complaints */
280
static void ComputeWinding(GLUEStesselator* tess, ActiveRegion* reg)
282
reg->windingNumber=RegionAbove(reg)->windingNumber+reg->eUp->winding;
283
reg->inside=IsWindingInside(tess, reg->windingNumber);
287
* Delete a region from the sweep line. This happens when the upper
288
* and lower chains of a region meet (at a vertex on the sweep line).
289
* The "inside" flag is copied to the appropriate mesh face (we could
290
* not do this before -- since the structure of the mesh is always
291
* changing, this face may not have even existed until now).
293
static void FinishRegion(GLUEStesselator* tess, ActiveRegion* reg)
295
GLUEShalfEdge* e=reg->eUp;
296
GLUESface* f=e->Lface;
298
f->inside=reg->inside;
299
/* optimization for __gl_meshTessellateMonoRegion() */
301
DeleteRegion(tess, reg);
305
* We are given a vertex with one or more left-going edges. All affected
306
* edges should be in the edge dictionary. Starting at regFirst->eUp,
307
* we walk down deleting all regions where both edges have the same
308
* origin vOrg. At the same time we copy the "inside" flag from the
309
* active region to the face, since at this point each face will belong
310
* to at most one region (this was not necessarily true until this point
311
* in the sweep). The walk stops at the region above regLast; if regLast
312
* is NULL we walk as far as possible. At the same time we relink the
313
* mesh if necessary, so that the ordering of edges around vOrg is the
314
* same as in the dictionary.
316
static GLUEShalfEdge* FinishLeftRegions(GLUEStesselator* tess, ActiveRegion* regFirst,
317
ActiveRegion* regLast)
320
ActiveRegion* regPrev;
322
GLUEShalfEdge* ePrev;
326
while (regPrev!=regLast)
328
/* placement was OK */
329
regPrev->fixUpperEdge=FALSE;
330
reg=RegionBelow(regPrev);
332
if (e->Org!=ePrev->Org)
334
if (!reg->fixUpperEdge)
336
/* Remove the last left-going edge. Even though there are no further
337
* edges in the dictionary with this origin, there may be further
338
* such edges in the mesh (if we are adding left edges to a vertex
339
* that has already been processed). Thus it is important to call
340
* FinishRegion rather than just DeleteRegion.
342
FinishRegion(tess, regPrev);
346
/* If the edge below was a temporary edge introduced by
347
* ConnectRightVertex, now is the time to fix it.
349
e=__gl_meshConnect(ePrev->Lprev, e->Sym);
352
longjmp(tess->env, 1);
354
if (!FixUpperEdge(reg, e))
356
longjmp(tess->env, 1);
360
/* Relink edges so that ePrev->Onext == e */
363
if (!__gl_meshSplice(e->Oprev, e))
365
longjmp(tess->env, 1);
367
if (!__gl_meshSplice(ePrev, e))
369
longjmp(tess->env, 1);
373
/* may change reg->eUp */
374
FinishRegion(tess, regPrev);
383
* Purpose: insert right-going edges into the edge dictionary, and update
384
* winding numbers and mesh connectivity appropriately. All right-going
385
* edges share a common origin vOrg. Edges are inserted CCW starting at
386
* eFirst; the last edge inserted is eLast->Oprev. If vOrg has any
387
* left-going edges already processed, then eTopLeft must be the edge
388
* such that an imaginary upward vertical segment from vOrg would be
389
* contained between eTopLeft->Oprev and eTopLeft; otherwise eTopLeft
392
static void AddRightEdges(GLUEStesselator* tess, ActiveRegion* regUp,
393
GLUEShalfEdge* eFirst, GLUEShalfEdge* eLast, GLUEShalfEdge* eTopLeft,
397
ActiveRegion* regPrev;
399
GLUEShalfEdge* ePrev;
402
/* Insert the new right-going edges in the dictionary */
405
assert(VertLeq(e->Org, e->Dst));
406
AddRegionBelow(tess, regUp, e->Sym);
410
/* Walk *all* right-going edges from e->Org, in the dictionary order,
411
* updating the winding numbers of each region, and re-linking the mesh
412
* edges to match the dictionary ordering (if necessary).
416
eTopLeft=RegionBelow(regUp)->eUp->Rprev;
423
reg=RegionBelow(regPrev);
425
if (e->Org!=ePrev->Org)
432
/* Unlink e from its current position, and relink below ePrev */
433
if (!__gl_meshSplice(e->Oprev, e))
435
longjmp(tess->env, 1);
437
if (!__gl_meshSplice(ePrev->Oprev, e))
439
longjmp(tess->env, 1);
443
/* Compute the winding number and "inside" flag for the new regions */
444
reg->windingNumber=regPrev->windingNumber-e->winding;
445
reg->inside=IsWindingInside(tess,reg->windingNumber);
447
/* Check for two outgoing edges with same slope -- process these
448
* before any intersection tests (see example in __gl_computeInterior).
451
if (!firstTime && CheckForRightSplice(tess, regPrev))
453
AddWinding(e, ePrev);
454
DeleteRegion(tess, regPrev);
455
if (!__gl_meshDelete(ePrev))
457
longjmp(tess->env, 1);
465
assert(regPrev->windingNumber-e->winding==reg->windingNumber);
469
/* Check for intersections between newly adjacent edges. */
470
WalkDirtyRegions(tess, regPrev);
474
static void CallCombine(GLUEStesselator* tess, GLUESvertex* isect,
475
void* data[4], GLfloat weights[4], int needed)
479
/* Copy coord data in case the callback changes it. */
480
coords[0]=isect->coords[0];
481
coords[1]=isect->coords[1];
482
coords[2]=isect->coords[2];
485
CALL_COMBINE_OR_COMBINE_DATA(coords, data, weights, &isect->data);
487
if (isect->data==NULL)
495
if (!tess->fatalError)
497
/* The only way fatal error is when two edges are found to intersect,
498
* but the user has not provided the callback necessary to handle
499
* generated intersection points.
501
CALL_ERROR_OR_ERROR_DATA(GLUES_TESS_NEED_COMBINE_CALLBACK);
502
tess->fatalError=TRUE;
509
* Two vertices with idential coordinates are combined into one.
510
* e1->Org is kept, while e2->Org is discarded.
512
static void SpliceMergeVertices(GLUEStesselator* tess, GLUEShalfEdge *e1, GLUEShalfEdge* e2)
514
void* data[4]={NULL, NULL, NULL, NULL};
515
GLfloat weights[4]={0.5f, 0.5f, 0.0f, 0.0f};
517
data[0]=e1->Org->data;
518
data[1]=e2->Org->data;
519
CallCombine(tess, e1->Org, data, weights, FALSE);
520
if (!__gl_meshSplice(e1, e2))
522
longjmp(tess->env, 1);
527
* Find some weights which describe how the intersection vertex is
528
* a linear combination of "org" and "dest". Each of the two edges
529
* which generated "isect" is allocated 50% of the weight; each edge
530
* splits the weight between its org and dst according to the
531
* relative distance to "isect".
533
static void VertexWeights(GLUESvertex* isect, GLUESvertex* org, GLUESvertex* dst,
536
GLfloat t1=VertL1dist(org, isect);
537
GLfloat t2=VertL1dist(dst, isect);
539
weights[0]=0.5f*t2/(t1+t2);
540
weights[1]=0.5f*t1/(t1+t2);
541
isect->coords[0]+=weights[0]*org->coords[0]+weights[1]*dst->coords[0];
542
isect->coords[1]+=weights[0]*org->coords[1]+weights[1]*dst->coords[1];
543
isect->coords[2]+=weights[0]*org->coords[2]+weights[1]*dst->coords[2];
547
* We've computed a new intersection point, now we need a "data" pointer
548
* from the user so that we can refer to this new vertex in the
549
* rendering callbacks.
551
static void GetIntersectData(GLUEStesselator* tess, GLUESvertex* isect,
552
GLUESvertex* orgUp, GLUESvertex* dstUp,
553
GLUESvertex* orgLo, GLUESvertex* dstLo)
563
isect->coords[0]=isect->coords[1]=isect->coords[2]=0;
564
VertexWeights(isect, orgUp, dstUp, &weights[0]);
565
VertexWeights(isect, orgLo, dstLo, &weights[2]);
567
CallCombine(tess, isect, data, weights, TRUE);
571
* Check the upper and lower edge of "regUp", to make sure that the
572
* eUp->Org is above eLo, or eLo->Org is below eUp (depending on which
573
* origin is leftmost).
575
* The main purpose is to splice right-going edges with the same
576
* dest vertex and nearly identical slopes (ie. we can't distinguish
577
* the slopes numerically). However the splicing can also help us
578
* to recover from numerical errors. For example, suppose at one
579
* point we checked eUp and eLo, and decided that eUp->Org is barely
580
* above eLo. Then later, we split eLo into two edges (eg. from
581
* a splice operation like this one). This can change the result of
582
* our test so that now eUp->Org is incident to eLo, or barely below it.
583
* We must correct this condition to maintain the dictionary invariants.
585
* One possibility is to check these edges for intersection again
586
* (ie. CheckForIntersect). This is what we do if possible. However
587
* CheckForIntersect requires that tess->event lies between eUp and eLo,
588
* so that it has something to fall back on when the intersection
589
* calculation gives us an unusable answer. So, for those cases where
590
* we can't check for intersection, this routine fixes the problem
591
* by just splicing the offending vertex into the other edge.
592
* This is a guaranteed solution, no matter how degenerate things get.
593
* Basically this is a combinatorial solution to a numerical problem.
595
static int CheckForRightSplice(GLUEStesselator* tess, ActiveRegion* regUp)
597
ActiveRegion* regLo=RegionBelow(regUp);
598
GLUEShalfEdge* eUp=regUp->eUp;
599
GLUEShalfEdge* eLo=regLo->eUp;
601
if (VertLeq(eUp->Org, eLo->Org))
603
if (EdgeSign(eLo->Dst, eUp->Org, eLo->Org)>0)
608
/* eUp->Org appears to be below eLo */
609
if (!VertEq(eUp->Org, eLo->Org))
611
/* Splice eUp->Org into eLo */
612
if ( __gl_meshSplitEdge(eLo->Sym)==NULL)
614
longjmp(tess->env, 1);
616
if (!__gl_meshSplice(eUp, eLo->Oprev))
618
longjmp(tess->env, 1);
620
regUp->dirty=regLo->dirty=TRUE;
624
if (eUp->Org!=eLo->Org)
626
/* merge the two vertices, discarding eUp->Org */
627
pqDelete(tess->pq, eUp->Org->pqHandle); /* __gl_pqSortDelete */
628
SpliceMergeVertices(tess, eLo->Oprev, eUp);
634
if (EdgeSign(eUp->Dst, eLo->Org, eUp->Org)<0)
639
/* eLo->Org appears to be above eUp, so splice eLo->Org into eUp */
640
RegionAbove(regUp)->dirty=regUp->dirty=TRUE;
641
if (__gl_meshSplitEdge(eUp->Sym)==NULL)
643
longjmp(tess->env, 1);
645
if (!__gl_meshSplice(eLo->Oprev, eUp))
647
longjmp(tess->env, 1);
655
* Check the upper and lower edge of "regUp", to make sure that the
656
* eUp->Dst is above eLo, or eLo->Dst is below eUp (depending on which
657
* destination is rightmost).
659
* Theoretically, this should always be true. However, splitting an edge
660
* into two pieces can change the results of previous tests. For example,
661
* suppose at one point we checked eUp and eLo, and decided that eUp->Dst
662
* is barely above eLo. Then later, we split eLo into two edges (eg. from
663
* a splice operation like this one). This can change the result of
664
* the test so that now eUp->Dst is incident to eLo, or barely below it.
665
* We must correct this condition to maintain the dictionary invariants
666
* (otherwise new edges might get inserted in the wrong place in the
667
* dictionary, and bad stuff will happen).
669
* We fix the problem by just splicing the offending vertex into the
672
static int CheckForLeftSplice(GLUEStesselator* tess, ActiveRegion* regUp)
674
ActiveRegion* regLo=RegionBelow(regUp);
675
GLUEShalfEdge* eUp=regUp->eUp;
676
GLUEShalfEdge* eLo=regLo->eUp;
679
assert(!VertEq(eUp->Dst, eLo->Dst));
681
if (VertLeq(eUp->Dst, eLo->Dst))
683
if (EdgeSign(eUp->Dst, eLo->Dst, eUp->Org)<0)
688
/* eLo->Dst is above eUp, so splice eLo->Dst into eUp */
689
RegionAbove(regUp)->dirty=regUp->dirty=TRUE;
690
e=__gl_meshSplitEdge(eUp);
693
longjmp(tess->env, 1);
695
if (!__gl_meshSplice(eLo->Sym, e))
697
longjmp(tess->env, 1);
699
e->Lface->inside = regUp->inside;
703
if (EdgeSign(eLo->Dst, eUp->Dst, eLo->Org)>0)
708
/* eUp->Dst is below eLo, so splice eUp->Dst into eLo */
709
regUp->dirty=regLo->dirty=TRUE;
710
e=__gl_meshSplitEdge(eLo);
713
longjmp(tess->env, 1);
715
if (!__gl_meshSplice(eUp->Lnext, eLo->Sym))
717
longjmp(tess->env, 1);
719
e->Rface->inside=regUp->inside;
726
* Check the upper and lower edges of the given region to see if
727
* they intersect. If so, create the intersection and add it
728
* to the data structures.
730
* Returns TRUE if adding the new intersection resulted in a recursive
731
* call to AddRightEdges(); in this case all "dirty" regions have been
732
* checked for intersections, and possibly regUp has been deleted.
734
static int CheckForIntersect(GLUEStesselator* tess, ActiveRegion* regUp)
736
ActiveRegion* regLo=RegionBelow(regUp);
737
GLUEShalfEdge* eUp=regUp->eUp;
738
GLUEShalfEdge* eLo=regLo->eUp;
739
GLUESvertex* orgUp=eUp->Org;
740
GLUESvertex* orgLo=eLo->Org;
741
GLUESvertex* dstUp=eUp->Dst;
742
GLUESvertex* dstLo=eLo->Dst;
743
GLfloat tMinUp, tMaxLo;
748
assert(!VertEq(dstLo, dstUp));
749
assert(EdgeSign(dstUp, tess->event, orgUp)<=0);
750
assert(EdgeSign(dstLo, tess->event, orgLo)>=0);
751
assert(orgUp!=tess->event && orgLo!=tess->event);
752
assert(!regUp->fixUpperEdge && !regLo->fixUpperEdge);
756
/* right endpoints are the same */
760
tMinUp=MIN(orgUp->t, dstUp->t);
761
tMaxLo=MAX(orgLo->t, dstLo->t);
764
/* t ranges do not overlap */
768
if (VertLeq(orgUp, orgLo))
770
if (EdgeSign(dstLo, orgUp, orgLo)>0)
777
if (EdgeSign(dstUp, orgLo, orgUp)<0)
783
/* At this point the edges intersect, at least marginally */
786
__gl_edgeIntersect(dstUp, orgUp, dstLo, orgLo, &isect);
787
/* The following properties are guaranteed: */
788
assert(MIN(orgUp->t, dstUp->t)<=isect.t);
789
assert(isect.t<=MAX(orgLo->t, dstLo->t));
790
assert(MIN(dstLo->s, dstUp->s)<=isect.s);
791
assert(isect.s<=MAX(orgLo->s, orgUp->s));
793
if (VertLeq(&isect, tess->event))
795
/* The intersection point lies slightly to the left of the sweep line,
796
* so move it until it''s slightly to the right of the sweep line.
797
* (If we had perfect numerical precision, this would never happen
798
* in the first place). The easiest and safest thing to do is
799
* replace the intersection by tess->event.
801
isect.s=tess->event->s;
802
isect.t=tess->event->t;
805
/* Similarly, if the computed intersection lies to the right of the
806
* rightmost origin (which should rarely happen), it can cause
807
* unbelievable inefficiency on sufficiently degenerate inputs.
808
* (If you have the test program, try running test54.d with the
809
* "X zoom" option turned on).
811
orgMin=VertLeq(orgUp, orgLo) ? orgUp : orgLo;
812
if (VertLeq(orgMin, &isect))
818
if (VertEq(&isect, orgUp) || VertEq(&isect, orgLo))
820
/* Easy case -- intersection at one of the right endpoints */
821
(void) CheckForRightSplice(tess, regUp);
825
if ((!VertEq( dstUp, tess->event) && EdgeSign(dstUp, tess->event, &isect)>=0)
826
|| (!VertEq(dstLo, tess->event) && EdgeSign(dstLo, tess->event, &isect)<= 0))
828
/* Very unusual -- the new upper or lower edge would pass on the
829
* wrong side of the sweep event, or through it. This can happen
830
* due to very small numerical errors in the intersection calculation.
832
if (dstLo==tess->event)
834
/* Splice dstLo into eUp, and process the new region(s) */
835
if (__gl_meshSplitEdge(eUp->Sym)==NULL)
837
longjmp(tess->env, 1);
839
if (!__gl_meshSplice(eLo->Sym, eUp))
841
longjmp(tess->env, 1);
843
regUp=TopLeftRegion(regUp);
846
longjmp(tess->env, 1);
848
eUp=RegionBelow(regUp)->eUp;
849
FinishLeftRegions(tess, RegionBelow(regUp), regLo);
850
AddRightEdges(tess, regUp, eUp->Oprev, eUp, eUp, TRUE);
854
if (dstUp==tess->event)
856
/* Splice dstUp into eLo, and process the new region(s) */
857
if (__gl_meshSplitEdge(eLo->Sym)==NULL)
859
longjmp(tess->env, 1);
861
if (!__gl_meshSplice(eUp->Lnext, eLo->Oprev))
863
longjmp(tess->env, 1);
866
regUp=TopRightRegion(regUp);
867
e=RegionBelow(regUp)->eUp->Rprev;
868
regLo->eUp=eLo->Oprev;
869
eLo=FinishLeftRegions(tess, regLo, NULL);
870
AddRightEdges(tess, regUp, eLo->Onext, eUp->Rprev, e, TRUE);
875
/* Special case: called from ConnectRightVertex. If either
876
* edge passes on the wrong side of tess->event, split it
877
* (and wait for ConnectRightVertex to splice it appropriately).
879
if (EdgeSign(dstUp, tess->event, &isect)>=0)
881
RegionAbove(regUp)->dirty=regUp->dirty=TRUE;
882
if (__gl_meshSplitEdge(eUp->Sym)==NULL)
884
longjmp(tess->env, 1);
886
eUp->Org->s=tess->event->s;
887
eUp->Org->t=tess->event->t;
890
if (EdgeSign(dstLo, tess->event, &isect)<=0)
892
regUp->dirty=regLo->dirty=TRUE;
893
if (__gl_meshSplitEdge(eLo->Sym)==NULL)
895
longjmp(tess->env, 1);
897
eLo->Org->s=tess->event->s;
898
eLo->Org->t=tess->event->t;
901
/* leave the rest for ConnectRightVertex */
905
/* General case -- split both edges, splice into new vertex.
906
* When we do the splice operation, the order of the arguments is
907
* arbitrary as far as correctness goes. However, when the operation
908
* creates a new face, the work done is proportional to the size of
909
* the new face. We expect the faces in the processed part of
910
* the mesh (ie. eUp->Lface) to be smaller than the faces in the
911
* unprocessed original contours (which will be eLo->Oprev->Lface).
913
if (__gl_meshSplitEdge(eUp->Sym)==NULL)
915
longjmp(tess->env, 1);
917
if (__gl_meshSplitEdge(eLo->Sym)==NULL)
919
longjmp(tess->env, 1);
921
if (!__gl_meshSplice(eLo->Oprev, eUp))
923
longjmp(tess->env, 1);
928
eUp->Org->pqHandle=pqInsert(tess->pq, eUp->Org); /* __gl_pqSortInsert */
929
if (eUp->Org->pqHandle==LONG_MAX)
931
pqDeletePriorityQ(tess->pq); /* __gl_pqSortDeletePriorityQ */
933
longjmp(tess->env, 1);
935
GetIntersectData(tess, eUp->Org, orgUp, dstUp, orgLo, dstLo);
936
RegionAbove(regUp)->dirty=regUp->dirty=regLo->dirty=TRUE;
942
* When the upper or lower edge of any region changes, the region is
943
* marked "dirty". This routine walks through all the dirty regions
944
* and makes sure that the dictionary invariants are satisfied
945
* (see the comments at the beginning of this file). Of course
946
* new dirty regions can be created as we make changes to restore
949
static void WalkDirtyRegions(GLUEStesselator* tess, ActiveRegion* regUp)
951
ActiveRegion* regLo=RegionBelow(regUp);
957
/* Find the lowest dirty region (we walk from the bottom up). */
961
regLo=RegionBelow(regLo);
966
regUp=RegionAbove(regUp);
967
if (regUp==NULL || !regUp->dirty)
969
/* We've walked all the dirty regions */
977
if (eUp->Dst!=eLo->Dst)
979
/* Check that the edge ordering is obeyed at the Dst vertices. */
980
if (CheckForLeftSplice(tess, regUp))
982
/* If the upper or lower edge was marked fixUpperEdge, then
983
* we no longer need it (since these edges are needed only for
984
* vertices which otherwise have no right-going edges).
986
if (regLo->fixUpperEdge)
988
DeleteRegion(tess, regLo);
989
if (!__gl_meshDelete(eLo))
991
longjmp(tess->env, 1);
993
regLo=RegionBelow(regUp);
998
if (regUp->fixUpperEdge)
1000
DeleteRegion(tess, regUp);
1001
if (!__gl_meshDelete(eUp))
1003
longjmp(tess->env, 1);
1005
regUp=RegionAbove(regLo);
1012
if (eUp->Org != eLo->Org)
1014
if (eUp->Dst != eLo->Dst && !regUp->fixUpperEdge &&
1015
!regLo->fixUpperEdge && (eUp->Dst==tess->event ||
1016
eLo->Dst==tess->event))
1018
/* When all else fails in CheckForIntersect(), it uses tess->event
1019
* as the intersection location. To make this possible, it requires
1020
* that tess->event lie between the upper and lower edges, and also
1021
* that neither of these is marked fixUpperEdge (since in the worst
1022
* case it might splice one of these edges into tess->event, and
1023
* violate the invariant that fixable edges are the only right-going
1024
* edge from their associated vertex).
1026
if (CheckForIntersect(tess, regUp))
1028
/* WalkDirtyRegions() was called recursively; we're done */
1034
/* Even though we can't use CheckForIntersect(), the Org vertices
1035
* may violate the dictionary edge ordering. Check and correct this.
1037
(void) CheckForRightSplice(tess, regUp);
1041
if (eUp->Org==eLo->Org && eUp->Dst==eLo->Dst)
1043
/* A degenerate loop consisting of only two edges -- delete it. */
1044
AddWinding(eLo, eUp);
1045
DeleteRegion(tess, regUp);
1046
if (!__gl_meshDelete(eUp))
1048
longjmp(tess->env, 1);
1050
regUp=RegionAbove(regLo);
1056
* Purpose: connect a "right" vertex vEvent (one where all edges go left)
1057
* to the unprocessed portion of the mesh. Since there are no right-going
1058
* edges, two regions (one above vEvent and one below) are being merged
1059
* into one. "regUp" is the upper of these two regions.
1061
* There are two reasons for doing this (adding a right-going edge):
1062
* - if the two regions being merged are "inside", we must add an edge
1063
* to keep them separated (the combined region would not be monotone).
1064
* - in any case, we must leave some record of vEvent in the dictionary,
1065
* so that we can merge vEvent with features that we have not seen yet.
1066
* For example, maybe there is a vertical edge which passes just to
1067
* the right of vEvent; we would like to splice vEvent into this edge.
1069
* However, we don't want to connect vEvent to just any vertex. We don''t
1070
* want the new edge to cross any other edges; otherwise we will create
1071
* intersection vertices even when the input data had no self-intersections.
1072
* (This is a bad thing; if the user's input data has no intersections,
1073
* we don't want to generate any false intersections ourselves.)
1075
* Our eventual goal is to connect vEvent to the leftmost unprocessed
1076
* vertex of the combined region (the union of regUp and regLo).
1077
* But because of unseen vertices with all right-going edges, and also
1078
* new vertices which may be created by edge intersections, we don''t
1079
* know where that leftmost unprocessed vertex is. In the meantime, we
1080
* connect vEvent to the closest vertex of either chain, and mark the region
1081
* as "fixUpperEdge". This flag says to delete and reconnect this edge
1082
* to the next processed vertex on the boundary of the combined region.
1083
* Quite possibly the vertex we connected to will turn out to be the
1084
* closest one, in which case we won''t need to make any changes.
1086
static void ConnectRightVertex(GLUEStesselator* tess, ActiveRegion* regUp,
1087
GLUEShalfEdge* eBottomLeft)
1089
GLUEShalfEdge* eNew;
1090
GLUEShalfEdge* eTopLeft=eBottomLeft->Onext;
1091
ActiveRegion* regLo=RegionBelow(regUp);
1092
GLUEShalfEdge* eUp=regUp->eUp;
1093
GLUEShalfEdge* eLo=regLo->eUp;
1094
int degenerate=FALSE;
1096
if (eUp->Dst!=eLo->Dst)
1098
(void)CheckForIntersect(tess, regUp);
1101
/* Possible new degeneracies: upper or lower edge of regUp may pass
1102
* through vEvent, or may coincide with new intersection vertex
1104
if (VertEq(eUp->Org, tess->event))
1106
if (!__gl_meshSplice(eTopLeft->Oprev, eUp))
1108
longjmp(tess->env, 1);
1110
regUp=TopLeftRegion(regUp);
1113
longjmp(tess->env, 1);
1115
eTopLeft=RegionBelow(regUp)->eUp;
1116
FinishLeftRegions(tess, RegionBelow(regUp), regLo);
1120
if (VertEq(eLo->Org, tess->event))
1122
if (!__gl_meshSplice(eBottomLeft, eLo->Oprev))
1124
longjmp(tess->env, 1);
1126
eBottomLeft=FinishLeftRegions(tess, regLo, NULL);
1132
AddRightEdges(tess, regUp, eBottomLeft->Onext, eTopLeft, eTopLeft, TRUE);
1136
/* Non-degenerate situation -- need to add a temporary, fixable edge.
1137
* Connect to the closer of eLo->Org, eUp->Org.
1139
if (VertLeq(eLo->Org, eUp->Org))
1147
eNew=__gl_meshConnect(eBottomLeft->Lprev, eNew);
1150
longjmp(tess->env, 1);
1153
/* Prevent cleanup, otherwise eNew might disappear before we've even
1154
* had a chance to mark it as a temporary edge.
1156
AddRightEdges(tess, regUp, eNew, eNew->Onext, eNew->Onext, FALSE);
1157
eNew->Sym->activeRegion->fixUpperEdge=TRUE;
1158
WalkDirtyRegions(tess, regUp);
1161
/* Because vertices at exactly the same location are merged together
1162
* before we process the sweep event, some degenerate cases can't occur.
1163
* However if someone eventually makes the modifications required to
1164
* merge features which are close together, the cases below marked
1165
* TOLERANCE_NONZERO will be useful. They were debugged before the
1166
* code to merge identical vertices in the main loop was added.
1168
#define TOLERANCE_NONZERO FALSE
1171
* The event vertex lies exacty on an already-processed edge or vertex.
1172
* Adding the new vertex involves splicing it into the already-processed
1175
static void ConnectLeftDegenerate(GLUEStesselator* tess,
1176
ActiveRegion* regUp, GLUESvertex* vEvent)
1179
GLUEShalfEdge* eTopLeft;
1180
GLUEShalfEdge* eTopRight;
1181
GLUEShalfEdge* eLast;
1185
if (VertEq(e->Org, vEvent))
1187
/* e->Org is an unprocessed vertex - just combine them, and wait
1188
* for e->Org to be pulled from the queue
1190
assert(TOLERANCE_NONZERO);
1191
SpliceMergeVertices(tess, e, vEvent->anEdge);
1195
if (!VertEq(e->Dst, vEvent))
1197
/* General case -- splice vEvent into edge e which passes through it */
1198
if (__gl_meshSplitEdge(e->Sym)==NULL)
1200
longjmp(tess->env, 1);
1202
if (regUp->fixUpperEdge)
1204
/* This edge was fixable -- delete unused portion of original edge */
1205
if (!__gl_meshDelete(e->Onext))
1207
longjmp(tess->env, 1);
1209
regUp->fixUpperEdge=FALSE;
1211
if (!__gl_meshSplice(vEvent->anEdge, e))
1213
longjmp(tess->env, 1);
1215
SweepEvent(tess, vEvent); /* recurse */
1219
/* vEvent coincides with e->Dst, which has already been processed.
1220
* Splice in the additional right-going edges.
1222
assert(TOLERANCE_NONZERO);
1223
regUp=TopRightRegion(regUp);
1224
reg=RegionBelow(regUp);
1225
eTopRight=reg->eUp->Sym;
1226
eTopLeft=eLast=eTopRight->Onext;
1227
if (reg->fixUpperEdge)
1229
/* Here e->Dst has only a single fixable edge going right.
1230
* We can delete it since now we have some real right-going edges.
1232
assert(eTopLeft!=eTopRight); /* there are some left edges too */
1233
DeleteRegion(tess, reg);
1234
if (!__gl_meshDelete(eTopRight))
1236
longjmp(tess->env, 1);
1238
eTopRight=eTopLeft->Oprev;
1240
if (!__gl_meshSplice(vEvent->anEdge, eTopRight))
1242
longjmp(tess->env, 1);
1244
if(!EdgeGoesLeft(eTopLeft))
1246
/* e->Dst had no left-going edges -- indicate this to AddRightEdges() */
1249
AddRightEdges(tess, regUp, eTopRight->Onext, eLast, eTopLeft, TRUE);
1253
* Purpose: connect a "left" vertex (one where both edges go right)
1254
* to the processed portion of the mesh. Let R be the active region
1255
* containing vEvent, and let U and L be the upper and lower edge
1256
* chains of R. There are two possibilities:
1258
* - the normal case: split R into two regions, by connecting vEvent to
1259
* the rightmost vertex of U or L lying to the left of the sweep line
1261
* - the degenerate case: if vEvent is close enough to U or L, we
1262
* merge vEvent into that edge chain. The subcases are:
1263
* - merging with the rightmost vertex of U or L
1264
* - merging with the active edge of U or L
1265
* - merging with an already-processed portion of U or L
1267
static void ConnectLeftVertex(GLUEStesselator* tess, GLUESvertex* vEvent)
1269
ActiveRegion* regUp;
1270
ActiveRegion* regLo;
1274
GLUEShalfEdge* eNew;
1277
/* Get a pointer to the active region containing vEvent */
1278
tmp.eUp=vEvent->anEdge->Sym;
1279
/* __GL_DICTLISTKEY */ /* __gl_dictListSearch */
1280
regUp=(ActiveRegion*)dictKey(dictSearch(tess->dict, &tmp));
1281
regLo=RegionBelow(regUp);
1285
/* Try merging with U or L first */
1286
if (EdgeSign(eUp->Dst, vEvent, eUp->Org)==0)
1288
ConnectLeftDegenerate(tess, regUp, vEvent);
1292
/* Connect vEvent to rightmost processed vertex of either chain.
1293
* e->Dst is the vertex that we will connect to vEvent.
1295
reg=VertLeq(eLo->Dst, eUp->Dst) ? regUp : regLo;
1297
if (regUp->inside || reg->fixUpperEdge)
1301
eNew=__gl_meshConnect(vEvent->anEdge->Sym, eUp->Lnext);
1304
longjmp(tess->env, 1);
1309
GLUEShalfEdge* tempHalfEdge=__gl_meshConnect(eLo->Dnext, vEvent->anEdge);
1310
if (tempHalfEdge==NULL)
1312
longjmp(tess->env, 1);
1315
eNew=tempHalfEdge->Sym;
1317
if (reg->fixUpperEdge)
1319
if (!FixUpperEdge(reg, eNew))
1321
longjmp(tess->env, 1);
1326
ComputeWinding(tess, AddRegionBelow(tess, regUp, eNew));
1328
SweepEvent(tess, vEvent);
1332
/* The new vertex is in a region which does not belong to the polygon.
1333
* We don''t need to connect this vertex to the rest of the mesh.
1335
AddRightEdges(tess, regUp, vEvent->anEdge, vEvent->anEdge, NULL, TRUE);
1340
* Does everything necessary when the sweep line crosses a vertex.
1341
* Updates the mesh and the edge dictionary.
1343
static void SweepEvent(GLUEStesselator* tess, GLUESvertex* vEvent)
1345
ActiveRegion* regUp;
1348
GLUEShalfEdge* eTopLeft;
1349
GLUEShalfEdge* eBottomLeft;
1351
tess->event=vEvent; /* for access in EdgeLeq() */
1354
/* Check if this vertex is the right endpoint of an edge that is
1355
* already in the dictionary. In this case we don't need to waste
1356
* time searching for the location to insert new edges.
1360
while(e->activeRegion==NULL)
1363
if(e==vEvent->anEdge)
1365
/* All edges go right -- not incident to any processed edges */
1366
ConnectLeftVertex(tess, vEvent);
1371
/* Processing consists of two phases: first we "finish" all the
1372
* active regions where both the upper and lower edges terminate
1373
* at vEvent (ie. vEvent is closing off these regions).
1374
* We mark these faces "inside" or "outside" the polygon according
1375
* to their winding number, and delete the edges from the dictionary.
1376
* This takes care of all the left-going edges from vEvent.
1378
regUp=TopLeftRegion(e->activeRegion);
1381
longjmp(tess->env, 1);
1383
reg=RegionBelow(regUp);
1385
eBottomLeft=FinishLeftRegions(tess, reg, NULL);
1387
/* Next we process all the right-going edges from vEvent. This
1388
* involves adding the edges to the dictionary, and creating the
1389
* associated "active regions" which record information about the
1390
* regions between adjacent dictionary edges.
1392
if (eBottomLeft->Onext==eTopLeft)
1394
/* No right-going edges -- add a temporary "fixable" edge */
1395
ConnectRightVertex(tess, regUp, eBottomLeft);
1399
AddRightEdges(tess, regUp, eBottomLeft->Onext, eTopLeft, eTopLeft, TRUE);
1403
/* Make the sentinel coordinates big enough that they will never be
1404
* merged with real input features. (Even with the largest possible
1405
* input contour and the maximum tolerance of 1.0, no merging will be
1406
* done with coordinates larger than 3 * GLUES_TESS_MAX_COORD).
1408
#define SENTINEL_COORD (4.0f*GLUES_TESS_MAX_COORD)
1411
* We add two sentinel edges above and below all other edges,
1412
* to avoid special cases at the top and bottom.
1414
static void AddSentinel(GLUEStesselator* tess, GLfloat t)
1417
ActiveRegion* reg=(ActiveRegion*)memAlloc(sizeof(ActiveRegion));
1420
longjmp(tess->env, 1);
1423
e=__gl_meshMakeEdge(tess->mesh);
1426
longjmp(tess->env, 1);
1429
e->Org->s=SENTINEL_COORD;
1431
e->Dst->s=-SENTINEL_COORD;
1433
tess->event=e->Dst; /* initialize it */
1436
reg->windingNumber=0;
1438
reg->fixUpperEdge=FALSE;
1441
reg->nodeUp=dictInsert(tess->dict, reg); /* __gl_dictListInsertBefore */
1443
if (reg->nodeUp==NULL)
1445
longjmp(tess->env, 1);
1450
* We maintain an ordering of edge intersections with the sweep line.
1451
* This order is maintained in a dynamic dictionary.
1453
static void InitEdgeDict(GLUEStesselator* tess)
1455
/* __gl_dictListNewDict */
1456
tess->dict=dictNewDict(tess, (int (*)(void*, DictKey, DictKey))EdgeLeq);
1457
if (tess->dict==NULL)
1459
longjmp(tess->env, 1);
1462
AddSentinel(tess, -SENTINEL_COORD);
1463
AddSentinel(tess, SENTINEL_COORD);
1466
static void DoneEdgeDict(GLUEStesselator* tess)
1473
/* __GL_DICTLISTKEY */ /* __GL_DICTLISTMIN */
1474
while ((reg=(ActiveRegion*)dictKey(dictMin(tess->dict)))!=NULL)
1477
* At the end of all processing, the dictionary should contain
1478
* only the two sentinel edges, plus at most one "fixable" edge
1479
* created by ConnectRightVertex().
1483
assert(reg->fixUpperEdge);
1484
assert(++fixedEdges==1);
1486
assert(reg->windingNumber==0);
1487
DeleteRegion(tess, reg);
1489
dictDeleteDict(tess->dict); /* __gl_dictListDeleteDict */
1493
* Remove zero-length edges, and contours with fewer than 3 vertices.
1495
static void RemoveDegenerateEdges(GLUEStesselator* tess)
1498
GLUEShalfEdge* eNext;
1499
GLUEShalfEdge* eLnext;
1500
GLUEShalfEdge* eHead=&tess->mesh->eHead;
1503
for(e=eHead->next; e!=eHead; e=eNext)
1508
if (VertEq(e->Org, e->Dst) && e->Lnext->Lnext!=e)
1510
/* Zero-length edge, contour has at least 3 edges */
1511
SpliceMergeVertices(tess, eLnext, e); /* deletes e->Org */
1512
if (!__gl_meshDelete(e))
1514
longjmp(tess->env, 1); /* e is a self-loop */
1520
if (eLnext->Lnext==e)
1522
/* Degenerate contour (one or two edges) */
1525
if (eLnext==eNext || eLnext==eNext->Sym)
1529
if (!__gl_meshDelete(eLnext))
1531
longjmp(tess->env, 1);
1534
if (e==eNext || e==eNext->Sym)
1538
if (!__gl_meshDelete(e))
1540
longjmp(tess->env, 1);
1547
* Insert all vertices into the priority queue which determines the
1548
* order in which vertices cross the sweep line.
1550
static int InitPriorityQ(GLUEStesselator* tess)
1556
/* __gl_pqSortNewPriorityQ */
1557
pq=tess->pq=pqNewPriorityQ((int (*)(PQkey, PQkey))__gl_vertLeq);
1563
vHead=&tess->mesh->vHead;
1564
for(v=vHead->next; v!=vHead; v=v->next)
1566
v->pqHandle=pqInsert(pq, v); /* __gl_pqSortInsert */
1567
if (v->pqHandle==LONG_MAX)
1573
if (v!=vHead || !pqInit(pq))
1574
{ /* __gl_pqSortInit */
1575
pqDeletePriorityQ(tess->pq); /* __gl_pqSortDeletePriorityQ */
1583
static void DonePriorityQ(GLUEStesselator* tess)
1585
pqDeletePriorityQ(tess->pq); /* __gl_pqSortDeletePriorityQ */
1589
* Delete any degenerate faces with only two edges. WalkDirtyRegions()
1590
* will catch almost all of these, but it won't catch degenerate faces
1591
* produced by splice operations on already-processed edges.
1592
* The two places this can happen are in FinishLeftRegions(), when
1593
* we splice in a "temporary" edge produced by ConnectRightVertex(),
1594
* and in CheckForLeftSplice(), where we splice already-processed
1595
* edges to ensure that our dictionary invariants are not violated
1596
* by numerical errors.
1598
* In both these cases it is *very* dangerous to delete the offending
1599
* edge at the time, since one of the routines further up the stack
1600
* will sometimes be keeping a pointer to that edge.
1602
static int RemoveDegenerateFaces(GLUESmesh* mesh)
1609
for(f=mesh->fHead.next; f!=&mesh->fHead; f=fNext)
1613
assert(e->Lnext!=e);
1615
if (e->Lnext->Lnext==e)
1617
/* A face with only two edges */
1618
AddWinding(e->Onext, e);
1619
if (!__gl_meshDelete(e))
1629
int __gl_computeInterior(GLUEStesselator* tess)
1631
* __gl_computeInterior( tess ) computes the planar arrangement specified
1632
* by the given contours, and further subdivides this arrangement
1633
* into regions. Each region is marked "inside" if it belongs
1634
* to the polygon, according to the rule given by tess->windingRule.
1635
* Each interior region is guaranteed be monotone.
1641
tess->fatalError=FALSE;
1643
/* Each vertex defines an event for our sweep line. Start by inserting
1644
* all the vertices in a priority queue. Events are processed in
1645
* lexicographic order, ie.
1647
* e1 < e2 iff e1.x < e2.x || (e1.x == e2.x && e1.y < e2.y)
1649
RemoveDegenerateEdges(tess);
1650
if (!InitPriorityQ(tess))
1652
return 0; /* if error */
1656
/* __gl_pqSortExtractMin */
1657
while((v=(GLUESvertex*)pqExtractMin(tess->pq))!=NULL)
1661
vNext=(GLUESvertex*)pqMinimum(tess->pq); /* __gl_pqSortMinimum */
1662
if (vNext==NULL || !VertEq(vNext, v))
1667
/* Merge together all vertices at exactly the same location.
1668
* This is more efficient than processing them one at a time,
1669
* simplifies the code (see ConnectLeftDegenerate), and is also
1670
* important for correct handling of certain degenerate cases.
1671
* For example, suppose there are two identical edges A and B
1672
* that belong to different contours (so without this code they would
1673
* be processed by separate sweep events). Suppose another edge C
1674
* crosses A and B from above. When A is processed, we split it
1675
* at its intersection point with C. However this also splits C,
1676
* so when we insert B we may compute a slightly different
1677
* intersection point. This might leave two edges with a small
1678
* gap between them. This kind of error is especially obvious
1679
* when using boundary extraction (GLUES_TESS_BOUNDARY_ONLY).
1681
vNext=(GLUESvertex*)pqExtractMin(tess->pq); /* __gl_pqSortExtractMin*/
1682
SpliceMergeVertices(tess, v->anEdge, vNext->anEdge);
1684
SweepEvent(tess, v);
1687
/* Set tess->event for debugging purposes */
1688
/* __GL_DICTLISTKEY */ /* __GL_DICTLISTMIN */
1689
tess->event=((ActiveRegion*)dictKey(dictMin(tess->dict)))->eUp->Org;
1692
DonePriorityQ(tess);
1694
if (!RemoveDegenerateFaces(tess->mesh))
1698
__gl_meshCheckMesh(tess->mesh);
added
removed
src/external/glues_stel/source/libtess/sweep.c
