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