File indexing completed on 2024-05-05 12:00:43
0001 /* 0002 ** Author: Eric Veach, July 1994. 0003 ** 0004 */ 0005 0006 #include "gluos.h" 0007 #include <assert.h> 0008 #include <stddef.h> 0009 #include <setjmp.h> /* longjmp */ 0010 #include <limits.h> /* LONG_MAX */ 0011 0012 #include "mesh.h" 0013 #include "geom.h" 0014 #include "tess.h" 0015 #include "dict.h" 0016 #include "priorityq.h" 0017 #include "memalloc.h" 0018 #include "sweep.h" 0019 0020 #ifndef TRUE 0021 #define TRUE 1 0022 #endif 0023 #ifndef FALSE 0024 #define FALSE 0 0025 #endif 0026 0027 #ifdef FOR_TRITE_TEST_PROGRAM 0028 extern void DebugEvent(GLUtesselator *tess); 0029 #else 0030 #define DebugEvent(tess) 0031 #endif 0032 0033 /* 0034 * Invariants for the Edge Dictionary. 0035 * - each pair of adjacent edges e2=Succ(e1) satisfies EdgeLeq(e1,e2) 0036 * at any valid location of the sweep event 0037 * - if EdgeLeq(e2,e1) as well (at any valid sweep event), then e1 and e2 0038 * share a common endpoint 0039 * - for each e, e->Dst has been processed, but not e->Org 0040 * - each edge e satisfies VertLeq(e->Dst,event) && VertLeq(event,e->Org) 0041 * where "event" is the current sweep line event. 0042 * - no edge e has zero length 0043 * 0044 * Invariants for the Mesh (the processed portion). 0045 * - the portion of the mesh left of the sweep line is a planar graph, 0046 * ie. there is *some* way to embed it in the plane 0047 * - no processed edge has zero length 0048 * - no two processed vertices have identical coordinates 0049 * - each "inside" region is monotone, ie. can be broken into two chains 0050 * of monotonically increasing vertices according to VertLeq(v1,v2) 0051 * - a non-invariant: these chains may intersect (very slightly) 0052 * 0053 * Invariants for the Sweep. 0054 * - if none of the edges incident to the event vertex have an activeRegion 0055 * (ie. none of these edges are in the edge dictionary), then the vertex 0056 * has only right-going edges. 0057 * - if an edge is marked "fixUpperEdge" (it is a temporary edge introduced 0058 * by ConnectRightVertex), then it is the only right-going edge from 0059 * its associated vertex. (This says that these edges exist only 0060 * when it is necessary.) 0061 */ 0062 0063 #undef MAX 0064 #undef MIN 0065 #define MAX(x, y) ((x) >= (y) ? (x) : (y)) 0066 #define MIN(x, y) ((x) <= (y) ? (x) : (y)) 0067 0068 /* When we merge two edges into one, we need to compute the combined 0069 * winding of the new edge. 0070 */ 0071 #define AddWinding(eDst, eSrc) (eDst->winding += eSrc->winding, eDst->Sym->winding += eSrc->Sym->winding) 0072 0073 static void SweepEvent(GLUtesselator *tess, GLUvertex *vEvent); 0074 static void WalkDirtyRegions(GLUtesselator *tess, ActiveRegion *regUp); 0075 static int CheckForRightSplice(GLUtesselator *tess, ActiveRegion *regUp); 0076 0077 static int EdgeLeq(GLUtesselator *tess, ActiveRegion *reg1, ActiveRegion *reg2) 0078 /* 0079 * Both edges must be directed from right to left (this is the canonical 0080 * direction for the upper edge of each region). 0081 * 0082 * The strategy is to evaluate a "t" value for each edge at the 0083 * current sweep line position, given by tess->event. The calculations 0084 * are designed to be very stable, but of course they are not perfect. 0085 * 0086 * Special case: if both edge destinations are at the sweep event, 0087 * we sort the edges by slope (they would otherwise compare equally). 0088 */ 0089 { 0090 GLUvertex *event = tess->event; 0091 GLUhalfEdge *e1, *e2; 0092 GLdouble t1, t2; 0093 0094 e1 = reg1->eUp; 0095 e2 = reg2->eUp; 0096 0097 if (e1->Dst == event) 0098 { 0099 if (e2->Dst == event) 0100 { 0101 /* Two edges right of the sweep line which meet at the sweep event. 0102 * Sort them by slope. 0103 */ 0104 if (VertLeq(e1->Org, e2->Org)) 0105 { 0106 return EdgeSign(e2->Dst, e1->Org, e2->Org) <= 0; 0107 } 0108 return EdgeSign(e1->Dst, e2->Org, e1->Org) >= 0; 0109 } 0110 return EdgeSign(e2->Dst, event, e2->Org) <= 0; 0111 } 0112 if (e2->Dst == event) 0113 { 0114 return EdgeSign(e1->Dst, event, e1->Org) >= 0; 0115 } 0116 0117 /* General case - compute signed distance *from* e1, e2 to event */ 0118 t1 = EdgeEval(e1->Dst, event, e1->Org); 0119 t2 = EdgeEval(e2->Dst, event, e2->Org); 0120 return (t1 >= t2); 0121 } 0122 0123 static void DeleteRegion(GLUtesselator *tess, ActiveRegion *reg) 0124 { 0125 if (reg->fixUpperEdge) 0126 { 0127 /* It was created with zero winding number, so it better be 0128 * deleted with zero winding number (ie. it better not get merged 0129 * with a real edge). 0130 */ 0131 assert(reg->eUp->winding == 0); 0132 } 0133 reg->eUp->activeRegion = NULL; 0134 dictDelete(tess->dict, reg->nodeUp); /* __gl_dictListDelete */ 0135 memFree(reg); 0136 } 0137 0138 static int FixUpperEdge(ActiveRegion *reg, GLUhalfEdge *newEdge) 0139 /* 0140 * Replace an upper edge which needs fixing (see ConnectRightVertex). 0141 */ 0142 { 0143 assert(reg->fixUpperEdge); 0144 if (!__gl_meshDelete(reg->eUp)) 0145 return 0; 0146 reg->fixUpperEdge = FALSE; 0147 reg->eUp = newEdge; 0148 newEdge->activeRegion = reg; 0149 0150 return 1; 0151 } 0152 0153 static ActiveRegion *TopLeftRegion(ActiveRegion *reg) 0154 { 0155 GLUvertex *org = reg->eUp->Org; 0156 GLUhalfEdge *e; 0157 0158 /* Find the region above the uppermost edge with the same origin */ 0159 do 0160 { 0161 reg = RegionAbove(reg); 0162 } while (reg->eUp->Org == org); 0163 0164 /* If the edge above was a temporary edge introduced by ConnectRightVertex, 0165 * now is the time to fix it. 0166 */ 0167 if (reg->fixUpperEdge) 0168 { 0169 e = __gl_meshConnect(RegionBelow(reg)->eUp->Sym, reg->eUp->Lnext); 0170 if (e == NULL) 0171 return NULL; 0172 if (!FixUpperEdge(reg, e)) 0173 return NULL; 0174 reg = RegionAbove(reg); 0175 } 0176 return reg; 0177 } 0178 0179 static ActiveRegion *TopRightRegion(ActiveRegion *reg) 0180 { 0181 GLUvertex *dst = reg->eUp->Dst; 0182 0183 /* Find the region above the uppermost edge with the same destination */ 0184 do 0185 { 0186 reg = RegionAbove(reg); 0187 } while (reg->eUp->Dst == dst); 0188 return reg; 0189 } 0190 0191 static ActiveRegion *AddRegionBelow(GLUtesselator *tess, ActiveRegion *regAbove, GLUhalfEdge *eNewUp) 0192 /* 0193 * Add a new active region to the sweep line, *somewhere* below "regAbove" 0194 * (according to where the new edge belongs in the sweep-line dictionary). 0195 * The upper edge of the new region will be "eNewUp". 0196 * Winding number and "inside" flag are not updated. 0197 */ 0198 { 0199 ActiveRegion *regNew = (ActiveRegion *)memAlloc(sizeof(ActiveRegion)); 0200 if (regNew == NULL) 0201 longjmp(tess->env, 1); 0202 0203 regNew->eUp = eNewUp; 0204 /* __gl_dictListInsertBefore */ 0205 regNew->nodeUp = dictInsertBefore(tess->dict, regAbove->nodeUp, regNew); 0206 if (regNew->nodeUp == NULL) 0207 longjmp(tess->env, 1); 0208 regNew->fixUpperEdge = FALSE; 0209 regNew->sentinel = FALSE; 0210 regNew->dirty = FALSE; 0211 0212 eNewUp->activeRegion = regNew; 0213 return regNew; 0214 } 0215 0216 static GLboolean IsWindingInside(GLUtesselator *tess, int n) 0217 { 0218 switch (tess->windingRule) 0219 { 0220 case GLU_TESS_WINDING_ODD: 0221 return (n & 1); 0222 case GLU_TESS_WINDING_NONZERO: 0223 return (n != 0); 0224 case GLU_TESS_WINDING_POSITIVE: 0225 return (n > 0); 0226 case GLU_TESS_WINDING_NEGATIVE: 0227 return (n < 0); 0228 case GLU_TESS_WINDING_ABS_GEQ_TWO: 0229 return (n >= 2) || (n <= -2); 0230 } 0231 /*LINTED*/ 0232 assert(FALSE); 0233 /*NOTREACHED*/ 0234 return GL_FALSE; /* avoid compiler complaints */ 0235 } 0236 0237 static void ComputeWinding(GLUtesselator *tess, ActiveRegion *reg) 0238 { 0239 reg->windingNumber = RegionAbove(reg)->windingNumber + reg->eUp->winding; 0240 reg->inside = IsWindingInside(tess, reg->windingNumber); 0241 } 0242 0243 static void FinishRegion(GLUtesselator *tess, ActiveRegion *reg) 0244 /* 0245 * Delete a region from the sweep line. This happens when the upper 0246 * and lower chains of a region meet (at a vertex on the sweep line). 0247 * The "inside" flag is copied to the appropriate mesh face (we could 0248 * not do this before -- since the structure of the mesh is always 0249 * changing, this face may not have even existed until now). 0250 */ 0251 { 0252 GLUhalfEdge *e = reg->eUp; 0253 GLUface *f = e->Lface; 0254 0255 f->inside = reg->inside; 0256 f->anEdge = e; /* optimization for __gl_meshTessellateMonoRegion() */ 0257 DeleteRegion(tess, reg); 0258 } 0259 0260 static GLUhalfEdge *FinishLeftRegions(GLUtesselator *tess, ActiveRegion *regFirst, ActiveRegion *regLast) 0261 /* 0262 * We are given a vertex with one or more left-going edges. All affected 0263 * edges should be in the edge dictionary. Starting at regFirst->eUp, 0264 * we walk down deleting all regions where both edges have the same 0265 * origin vOrg. At the same time we copy the "inside" flag from the 0266 * active region to the face, since at this point each face will belong 0267 * to at most one region (this was not necessarily true until this point 0268 * in the sweep). The walk stops at the region above regLast; if regLast 0269 * is NULL we walk as far as possible. At the same time we relink the 0270 * mesh if necessary, so that the ordering of edges around vOrg is the 0271 * same as in the dictionary. 0272 */ 0273 { 0274 ActiveRegion *reg, *regPrev; 0275 GLUhalfEdge *e, *ePrev; 0276 0277 regPrev = regFirst; 0278 ePrev = regFirst->eUp; 0279 while (regPrev != regLast) 0280 { 0281 regPrev->fixUpperEdge = FALSE; /* placement was OK */ 0282 reg = RegionBelow(regPrev); 0283 e = reg->eUp; 0284 if (e->Org != ePrev->Org) 0285 { 0286 if (!reg->fixUpperEdge) 0287 { 0288 /* Remove the last left-going edge. Even though there are no further 0289 * edges in the dictionary with this origin, there may be further 0290 * such edges in the mesh (if we are adding left edges to a vertex 0291 * that has already been processed). Thus it is important to call 0292 * FinishRegion rather than just DeleteRegion. 0293 */ 0294 FinishRegion(tess, regPrev); 0295 break; 0296 } 0297 /* If the edge below was a temporary edge introduced by 0298 * ConnectRightVertex, now is the time to fix it. 0299 */ 0300 e = __gl_meshConnect(ePrev->Lprev, e->Sym); 0301 if (e == NULL) 0302 longjmp(tess->env, 1); 0303 if (!FixUpperEdge(reg, e)) 0304 longjmp(tess->env, 1); 0305 } 0306 0307 /* Relink edges so that ePrev->Onext == e */ 0308 if (ePrev->Onext != e) 0309 { 0310 if (!__gl_meshSplice(e->Oprev, e)) 0311 longjmp(tess->env, 1); 0312 if (!__gl_meshSplice(ePrev, e)) 0313 longjmp(tess->env, 1); 0314 } 0315 FinishRegion(tess, regPrev); /* may change reg->eUp */ 0316 ePrev = reg->eUp; 0317 regPrev = reg; 0318 } 0319 return ePrev; 0320 } 0321 0322 static void AddRightEdges(GLUtesselator *tess, ActiveRegion *regUp, GLUhalfEdge *eFirst, GLUhalfEdge *eLast, 0323 GLUhalfEdge *eTopLeft, GLboolean cleanUp) 0324 /* 0325 * Purpose: insert right-going edges into the edge dictionary, and update 0326 * winding numbers and mesh connectivity appropriately. All right-going 0327 * edges share a common origin vOrg. Edges are inserted CCW starting at 0328 * eFirst; the last edge inserted is eLast->Oprev. If vOrg has any 0329 * left-going edges already processed, then eTopLeft must be the edge 0330 * such that an imaginary upward vertical segment from vOrg would be 0331 * contained between eTopLeft->Oprev and eTopLeft; otherwise eTopLeft 0332 * should be NULL. 0333 */ 0334 { 0335 ActiveRegion *reg, *regPrev; 0336 GLUhalfEdge *e, *ePrev; 0337 int firstTime = TRUE; 0338 0339 /* Insert the new right-going edges in the dictionary */ 0340 e = eFirst; 0341 do 0342 { 0343 assert(VertLeq(e->Org, e->Dst)); 0344 AddRegionBelow(tess, regUp, e->Sym); 0345 e = e->Onext; 0346 } while (e != eLast); 0347 0348 /* Walk *all* right-going edges from e->Org, in the dictionary order, 0349 * updating the winding numbers of each region, and re-linking the mesh 0350 * edges to match the dictionary ordering (if necessary). 0351 */ 0352 if (eTopLeft == NULL) 0353 { 0354 eTopLeft = RegionBelow(regUp)->eUp->Rprev; 0355 } 0356 regPrev = regUp; 0357 ePrev = eTopLeft; 0358 for (;;) 0359 { 0360 reg = RegionBelow(regPrev); 0361 e = reg->eUp->Sym; 0362 if (e->Org != ePrev->Org) 0363 break; 0364 0365 if (e->Onext != ePrev) 0366 { 0367 /* Unlink e from its current position, and relink below ePrev */ 0368 if (!__gl_meshSplice(e->Oprev, e)) 0369 longjmp(tess->env, 1); 0370 if (!__gl_meshSplice(ePrev->Oprev, e)) 0371 longjmp(tess->env, 1); 0372 } 0373 /* Compute the winding number and "inside" flag for the new regions */ 0374 reg->windingNumber = regPrev->windingNumber - e->winding; 0375 reg->inside = IsWindingInside(tess, reg->windingNumber); 0376 0377 /* Check for two outgoing edges with same slope -- process these 0378 * before any intersection tests (see example in __gl_computeInterior). 0379 */ 0380 regPrev->dirty = TRUE; 0381 if (!firstTime && CheckForRightSplice(tess, regPrev)) 0382 { 0383 AddWinding(e, ePrev); 0384 DeleteRegion(tess, regPrev); 0385 if (!__gl_meshDelete(ePrev)) 0386 longjmp(tess->env, 1); 0387 } 0388 firstTime = FALSE; 0389 regPrev = reg; 0390 ePrev = e; 0391 } 0392 regPrev->dirty = TRUE; 0393 assert(regPrev->windingNumber - e->winding == reg->windingNumber); 0394 0395 if (cleanUp) 0396 { 0397 /* Check for intersections between newly adjacent edges. */ 0398 WalkDirtyRegions(tess, regPrev); 0399 } 0400 } 0401 0402 static void CallCombine(GLUtesselator *tess, GLUvertex *isect, void *data[4], GLfloat weights[4], int needed) 0403 { 0404 GLdouble coords[3]; 0405 0406 /* Copy coord data in case the callback changes it. */ 0407 coords[0] = isect->coords[0]; 0408 coords[1] = isect->coords[1]; 0409 coords[2] = isect->coords[2]; 0410 0411 isect->data = NULL; 0412 CALL_COMBINE_OR_COMBINE_DATA(coords, data, weights, &isect->data); 0413 if (isect->data == NULL) 0414 { 0415 if (!needed) 0416 { 0417 isect->data = data[0]; 0418 } 0419 else if (!tess->fatalError) 0420 { 0421 /* The only way fatal error is when two edges are found to intersect, 0422 * but the user has not provided the callback necessary to handle 0423 * generated intersection points. 0424 */ 0425 CALL_ERROR_OR_ERROR_DATA(GLU_TESS_NEED_COMBINE_CALLBACK); 0426 tess->fatalError = TRUE; 0427 } 0428 } 0429 } 0430 0431 static void SpliceMergeVertices(GLUtesselator *tess, GLUhalfEdge *e1, GLUhalfEdge *e2) 0432 /* 0433 * Two vertices with identical coordinates are combined into one. 0434 * e1->Org is kept, while e2->Org is discarded. 0435 */ 0436 { 0437 void *data[4] = { NULL, NULL, NULL, NULL }; 0438 GLfloat weights[4] = { 0.5, 0.5, 0.0, 0.0 }; 0439 0440 data[0] = e1->Org->data; 0441 data[1] = e2->Org->data; 0442 CallCombine(tess, e1->Org, data, weights, FALSE); 0443 if (!__gl_meshSplice(e1, e2)) 0444 longjmp(tess->env, 1); 0445 } 0446 0447 static void VertexWeights(GLUvertex *isect, GLUvertex *org, GLUvertex *dst, GLfloat *weights) 0448 /* 0449 * Find some weights which describe how the intersection vertex is 0450 * a linear combination of "org" and "dest". Each of the two edges 0451 * which generated "isect" is allocated 50% of the weight; each edge 0452 * splits the weight between its org and dst according to the 0453 * relative distance to "isect". 0454 */ 0455 { 0456 GLdouble t1 = VertL1dist(org, isect); 0457 GLdouble t2 = VertL1dist(dst, isect); 0458 0459 weights[0] = 0.5 * t2 / (t1 + t2); 0460 weights[1] = 0.5 * t1 / (t1 + t2); 0461 isect->coords[0] += weights[0] * org->coords[0] + weights[1] * dst->coords[0]; 0462 isect->coords[1] += weights[0] * org->coords[1] + weights[1] * dst->coords[1]; 0463 isect->coords[2] += weights[0] * org->coords[2] + weights[1] * dst->coords[2]; 0464 } 0465 0466 static void GetIntersectData(GLUtesselator *tess, GLUvertex *isect, GLUvertex *orgUp, GLUvertex *dstUp, 0467 GLUvertex *orgLo, GLUvertex *dstLo) 0468 /* 0469 * We've computed a new intersection point, now we need a "data" pointer 0470 * from the user so that we can refer to this new vertex in the 0471 * rendering callbacks. 0472 */ 0473 { 0474 void *data[4]; 0475 GLfloat weights[4]; 0476 0477 data[0] = orgUp->data; 0478 data[1] = dstUp->data; 0479 data[2] = orgLo->data; 0480 data[3] = dstLo->data; 0481 0482 isect->coords[0] = isect->coords[1] = isect->coords[2] = 0; 0483 VertexWeights(isect, orgUp, dstUp, &weights[0]); 0484 VertexWeights(isect, orgLo, dstLo, &weights[2]); 0485 0486 CallCombine(tess, isect, data, weights, TRUE); 0487 } 0488 0489 static int CheckForRightSplice(GLUtesselator *tess, ActiveRegion *regUp) 0490 /* 0491 * Check the upper and lower edge of "regUp", to make sure that the 0492 * eUp->Org is above eLo, or eLo->Org is below eUp (depending on which 0493 * origin is leftmost). 0494 * 0495 * The main purpose is to splice right-going edges with the same 0496 * dest vertex and nearly identical slopes (ie. we can't distinguish 0497 * the slopes numerically). However the splicing can also help us 0498 * to recover from numerical errors. For example, suppose at one 0499 * point we checked eUp and eLo, and decided that eUp->Org is barely 0500 * above eLo. Then later, we split eLo into two edges (eg. from 0501 * a splice operation like this one). This can change the result of 0502 * our test so that now eUp->Org is incident to eLo, or barely below it. 0503 * We must correct this condition to maintain the dictionary invariants. 0504 * 0505 * One possibility is to check these edges for intersection again 0506 * (ie. CheckForIntersect). This is what we do if possible. However 0507 * CheckForIntersect requires that tess->event lies between eUp and eLo, 0508 * so that it has something to fall back on when the intersection 0509 * calculation gives us an unusable answer. So, for those cases where 0510 * we can't check for intersection, this routine fixes the problem 0511 * by just splicing the offending vertex into the other edge. 0512 * This is a guaranteed solution, no matter how degenerate things get. 0513 * Basically this is a combinatorial solution to a numerical problem. 0514 */ 0515 { 0516 ActiveRegion *regLo = RegionBelow(regUp); 0517 GLUhalfEdge *eUp = regUp->eUp; 0518 GLUhalfEdge *eLo = regLo->eUp; 0519 0520 if (VertLeq(eUp->Org, eLo->Org)) 0521 { 0522 if (EdgeSign(eLo->Dst, eUp->Org, eLo->Org) > 0) 0523 return FALSE; 0524 0525 /* eUp->Org appears to be below eLo */ 0526 if (!VertEq(eUp->Org, eLo->Org)) 0527 { 0528 /* Splice eUp->Org into eLo */ 0529 if (__gl_meshSplitEdge(eLo->Sym) == NULL) 0530 longjmp(tess->env, 1); 0531 if (!__gl_meshSplice(eUp, eLo->Oprev)) 0532 longjmp(tess->env, 1); 0533 regUp->dirty = regLo->dirty = TRUE; 0534 } 0535 else if (eUp->Org != eLo->Org) 0536 { 0537 /* merge the two vertices, discarding eUp->Org */ 0538 pqDelete(tess->pq, eUp->Org->pqHandle); /* __gl_pqSortDelete */ 0539 SpliceMergeVertices(tess, eLo->Oprev, eUp); 0540 } 0541 } 0542 else 0543 { 0544 if (EdgeSign(eUp->Dst, eLo->Org, eUp->Org) < 0) 0545 return FALSE; 0546 0547 /* eLo->Org appears to be above eUp, so splice eLo->Org into eUp */ 0548 RegionAbove(regUp)->dirty = regUp->dirty = TRUE; 0549 if (__gl_meshSplitEdge(eUp->Sym) == NULL) 0550 longjmp(tess->env, 1); 0551 if (!__gl_meshSplice(eLo->Oprev, eUp)) 0552 longjmp(tess->env, 1); 0553 } 0554 return TRUE; 0555 } 0556 0557 static int CheckForLeftSplice(GLUtesselator *tess, ActiveRegion *regUp) 0558 /* 0559 * Check the upper and lower edge of "regUp", to make sure that the 0560 * eUp->Dst is above eLo, or eLo->Dst is below eUp (depending on which 0561 * destination is rightmost). 0562 * 0563 * Theoretically, this should always be true. However, splitting an edge 0564 * into two pieces can change the results of previous tests. For example, 0565 * suppose at one point we checked eUp and eLo, and decided that eUp->Dst 0566 * is barely above eLo. Then later, we split eLo into two edges (eg. from 0567 * a splice operation like this one). This can change the result of 0568 * the test so that now eUp->Dst is incident to eLo, or barely below it. 0569 * We must correct this condition to maintain the dictionary invariants 0570 * (otherwise new edges might get inserted in the wrong place in the 0571 * dictionary, and bad stuff will happen). 0572 * 0573 * We fix the problem by just splicing the offending vertex into the 0574 * other edge. 0575 */ 0576 { 0577 ActiveRegion *regLo = RegionBelow(regUp); 0578 GLUhalfEdge *eUp = regUp->eUp; 0579 GLUhalfEdge *eLo = regLo->eUp; 0580 GLUhalfEdge *e; 0581 0582 assert(!VertEq(eUp->Dst, eLo->Dst)); 0583 0584 if (VertLeq(eUp->Dst, eLo->Dst)) 0585 { 0586 if (EdgeSign(eUp->Dst, eLo->Dst, eUp->Org) < 0) 0587 return FALSE; 0588 0589 /* eLo->Dst is above eUp, so splice eLo->Dst into eUp */ 0590 RegionAbove(regUp)->dirty = regUp->dirty = TRUE; 0591 e = __gl_meshSplitEdge(eUp); 0592 if (e == NULL) 0593 longjmp(tess->env, 1); 0594 if (!__gl_meshSplice(eLo->Sym, e)) 0595 longjmp(tess->env, 1); 0596 e->Lface->inside = regUp->inside; 0597 } 0598 else 0599 { 0600 if (EdgeSign(eLo->Dst, eUp->Dst, eLo->Org) > 0) 0601 return FALSE; 0602 0603 /* eUp->Dst is below eLo, so splice eUp->Dst into eLo */ 0604 regUp->dirty = regLo->dirty = TRUE; 0605 e = __gl_meshSplitEdge(eLo); 0606 if (e == NULL) 0607 longjmp(tess->env, 1); 0608 if (!__gl_meshSplice(eUp->Lnext, eLo->Sym)) 0609 longjmp(tess->env, 1); 0610 e->Rface->inside = regUp->inside; 0611 } 0612 return TRUE; 0613 } 0614 0615 static int CheckForIntersect(GLUtesselator *tess, ActiveRegion *regUp) 0616 /* 0617 * Check the upper and lower edges of the given region to see if 0618 * they intersect. If so, create the intersection and add it 0619 * to the data structures. 0620 * 0621 * Returns TRUE if adding the new intersection resulted in a recursive 0622 * call to AddRightEdges(); in this case all "dirty" regions have been 0623 * checked for intersections, and possibly regUp has been deleted. 0624 */ 0625 { 0626 ActiveRegion *regLo = RegionBelow(regUp); 0627 GLUhalfEdge *eUp = regUp->eUp; 0628 GLUhalfEdge *eLo = regLo->eUp; 0629 GLUvertex *orgUp = eUp->Org; 0630 GLUvertex *orgLo = eLo->Org; 0631 GLUvertex *dstUp = eUp->Dst; 0632 GLUvertex *dstLo = eLo->Dst; 0633 GLdouble tMinUp, tMaxLo; 0634 GLUvertex isect, *orgMin; 0635 GLUhalfEdge *e; 0636 0637 assert(!VertEq(dstLo, dstUp)); 0638 assert(EdgeSign(dstUp, tess->event, orgUp) <= 0); 0639 assert(EdgeSign(dstLo, tess->event, orgLo) >= 0); 0640 assert(orgUp != tess->event && orgLo != tess->event); 0641 assert(!regUp->fixUpperEdge && !regLo->fixUpperEdge); 0642 0643 if (orgUp == orgLo) 0644 return FALSE; /* right endpoints are the same */ 0645 0646 tMinUp = MIN(orgUp->t, dstUp->t); 0647 tMaxLo = MAX(orgLo->t, dstLo->t); 0648 if (tMinUp > tMaxLo) 0649 return FALSE; /* t ranges do not overlap */ 0650 0651 if (VertLeq(orgUp, orgLo)) 0652 { 0653 if (EdgeSign(dstLo, orgUp, orgLo) > 0) 0654 return FALSE; 0655 } 0656 else 0657 { 0658 if (EdgeSign(dstUp, orgLo, orgUp) < 0) 0659 return FALSE; 0660 } 0661 0662 /* At this point the edges intersect, at least marginally */ 0663 DebugEvent(tess); 0664 0665 __gl_edgeIntersect(dstUp, orgUp, dstLo, orgLo, &isect); 0666 /* The following properties are guaranteed: */ 0667 assert(MIN(orgUp->t, dstUp->t) <= isect.t); 0668 assert(isect.t <= MAX(orgLo->t, dstLo->t)); 0669 assert(MIN(dstLo->s, dstUp->s) <= isect.s); 0670 assert(isect.s <= MAX(orgLo->s, orgUp->s)); 0671 0672 if (VertLeq(&isect, tess->event)) 0673 { 0674 /* The intersection point lies slightly to the left of the sweep line, 0675 * so move it until it''s slightly to the right of the sweep line. 0676 * (If we had perfect numerical precision, this would never happen 0677 * in the first place). The easiest and safest thing to do is 0678 * replace the intersection by tess->event. 0679 */ 0680 isect.s = tess->event->s; 0681 isect.t = tess->event->t; 0682 } 0683 /* Similarly, if the computed intersection lies to the right of the 0684 * rightmost origin (which should rarely happen), it can cause 0685 * unbelievable inefficiency on sufficiently degenerate inputs. 0686 * (If you have the test program, try running test54.d with the 0687 * "X zoom" option turned on). 0688 */ 0689 orgMin = VertLeq(orgUp, orgLo) ? orgUp : orgLo; 0690 if (VertLeq(orgMin, &isect)) 0691 { 0692 isect.s = orgMin->s; 0693 isect.t = orgMin->t; 0694 } 0695 0696 if (VertEq(&isect, orgUp) || VertEq(&isect, orgLo)) 0697 { 0698 /* Easy case -- intersection at one of the right endpoints */ 0699 (void)CheckForRightSplice(tess, regUp); 0700 return FALSE; 0701 } 0702 0703 if ((!VertEq(dstUp, tess->event) && EdgeSign(dstUp, tess->event, &isect) >= 0) || 0704 (!VertEq(dstLo, tess->event) && EdgeSign(dstLo, tess->event, &isect) <= 0)) 0705 { 0706 /* Very unusual -- the new upper or lower edge would pass on the 0707 * wrong side of the sweep event, or through it. This can happen 0708 * due to very small numerical errors in the intersection calculation. 0709 */ 0710 if (dstLo == tess->event) 0711 { 0712 /* Splice dstLo into eUp, and process the new region(s) */ 0713 if (__gl_meshSplitEdge(eUp->Sym) == NULL) 0714 longjmp(tess->env, 1); 0715 if (!__gl_meshSplice(eLo->Sym, eUp)) 0716 longjmp(tess->env, 1); 0717 regUp = TopLeftRegion(regUp); 0718 if (regUp == NULL) 0719 longjmp(tess->env, 1); 0720 eUp = RegionBelow(regUp)->eUp; 0721 FinishLeftRegions(tess, RegionBelow(regUp), regLo); 0722 AddRightEdges(tess, regUp, eUp->Oprev, eUp, eUp, TRUE); 0723 return TRUE; 0724 } 0725 if (dstUp == tess->event) 0726 { 0727 /* Splice dstUp into eLo, and process the new region(s) */ 0728 if (__gl_meshSplitEdge(eLo->Sym) == NULL) 0729 longjmp(tess->env, 1); 0730 if (!__gl_meshSplice(eUp->Lnext, eLo->Oprev)) 0731 longjmp(tess->env, 1); 0732 regLo = regUp; 0733 regUp = TopRightRegion(regUp); 0734 e = RegionBelow(regUp)->eUp->Rprev; 0735 regLo->eUp = eLo->Oprev; 0736 eLo = FinishLeftRegions(tess, regLo, NULL); 0737 AddRightEdges(tess, regUp, eLo->Onext, eUp->Rprev, e, TRUE); 0738 return TRUE; 0739 } 0740 /* Special case: called from ConnectRightVertex. If either 0741 * edge passes on the wrong side of tess->event, split it 0742 * (and wait for ConnectRightVertex to splice it appropriately). 0743 */ 0744 if (EdgeSign(dstUp, tess->event, &isect) >= 0) 0745 { 0746 RegionAbove(regUp)->dirty = regUp->dirty = TRUE; 0747 if (__gl_meshSplitEdge(eUp->Sym) == NULL) 0748 longjmp(tess->env, 1); 0749 eUp->Org->s = tess->event->s; 0750 eUp->Org->t = tess->event->t; 0751 } 0752 if (EdgeSign(dstLo, tess->event, &isect) <= 0) 0753 { 0754 regUp->dirty = regLo->dirty = TRUE; 0755 if (__gl_meshSplitEdge(eLo->Sym) == NULL) 0756 longjmp(tess->env, 1); 0757 eLo->Org->s = tess->event->s; 0758 eLo->Org->t = tess->event->t; 0759 } 0760 /* leave the rest for ConnectRightVertex */ 0761 return FALSE; 0762 } 0763 0764 /* General case -- split both edges, splice into new vertex. 0765 * When we do the splice operation, the order of the arguments is 0766 * arbitrary as far as correctness goes. However, when the operation 0767 * creates a new face, the work done is proportional to the size of 0768 * the new face. We expect the faces in the processed part of 0769 * the mesh (ie. eUp->Lface) to be smaller than the faces in the 0770 * unprocessed original contours (which will be eLo->Oprev->Lface). 0771 */ 0772 if (__gl_meshSplitEdge(eUp->Sym) == NULL) 0773 longjmp(tess->env, 1); 0774 if (__gl_meshSplitEdge(eLo->Sym) == NULL) 0775 longjmp(tess->env, 1); 0776 if (!__gl_meshSplice(eLo->Oprev, eUp)) 0777 longjmp(tess->env, 1); 0778 eUp->Org->s = isect.s; 0779 eUp->Org->t = isect.t; 0780 eUp->Org->pqHandle = pqInsert(tess->pq, eUp->Org); /* __gl_pqSortInsert */ 0781 if (eUp->Org->pqHandle == LONG_MAX) 0782 { 0783 pqDeletePriorityQ(tess->pq); /* __gl_pqSortDeletePriorityQ */ 0784 tess->pq = NULL; 0785 longjmp(tess->env, 1); 0786 } 0787 GetIntersectData(tess, eUp->Org, orgUp, dstUp, orgLo, dstLo); 0788 RegionAbove(regUp)->dirty = regUp->dirty = regLo->dirty = TRUE; 0789 return FALSE; 0790 } 0791 0792 static void WalkDirtyRegions(GLUtesselator *tess, ActiveRegion *regUp) 0793 /* 0794 * When the upper or lower edge of any region changes, the region is 0795 * marked "dirty". This routine walks through all the dirty regions 0796 * and makes sure that the dictionary invariants are satisfied 0797 * (see the comments at the beginning of this file). Of course 0798 * new dirty regions can be created as we make changes to restore 0799 * the invariants. 0800 */ 0801 { 0802 ActiveRegion *regLo = RegionBelow(regUp); 0803 GLUhalfEdge *eUp, *eLo; 0804 0805 for (;;) 0806 { 0807 /* Find the lowest dirty region (we walk from the bottom up). */ 0808 while (regLo->dirty) 0809 { 0810 regUp = regLo; 0811 regLo = RegionBelow(regLo); 0812 } 0813 if (!regUp->dirty) 0814 { 0815 regLo = regUp; 0816 regUp = RegionAbove(regUp); 0817 if (regUp == NULL || !regUp->dirty) 0818 { 0819 /* We've walked all the dirty regions */ 0820 return; 0821 } 0822 } 0823 regUp->dirty = FALSE; 0824 eUp = regUp->eUp; 0825 eLo = regLo->eUp; 0826 0827 if (eUp->Dst != eLo->Dst) 0828 { 0829 /* Check that the edge ordering is obeyed at the Dst vertices. */ 0830 if (CheckForLeftSplice(tess, regUp)) 0831 { 0832 /* If the upper or lower edge was marked fixUpperEdge, then 0833 * we no longer need it (since these edges are needed only for 0834 * vertices which otherwise have no right-going edges). 0835 */ 0836 if (regLo->fixUpperEdge) 0837 { 0838 DeleteRegion(tess, regLo); 0839 if (!__gl_meshDelete(eLo)) 0840 longjmp(tess->env, 1); 0841 regLo = RegionBelow(regUp); 0842 eLo = regLo->eUp; 0843 } 0844 else if (regUp->fixUpperEdge) 0845 { 0846 DeleteRegion(tess, regUp); 0847 if (!__gl_meshDelete(eUp)) 0848 longjmp(tess->env, 1); 0849 regUp = RegionAbove(regLo); 0850 eUp = regUp->eUp; 0851 } 0852 } 0853 } 0854 if (eUp->Org != eLo->Org) 0855 { 0856 if (eUp->Dst != eLo->Dst && !regUp->fixUpperEdge && !regLo->fixUpperEdge && 0857 (eUp->Dst == tess->event || eLo->Dst == tess->event)) 0858 { 0859 /* When all else fails in CheckForIntersect(), it uses tess->event 0860 * as the intersection location. To make this possible, it requires 0861 * that tess->event lie between the upper and lower edges, and also 0862 * that neither of these is marked fixUpperEdge (since in the worst 0863 * case it might splice one of these edges into tess->event, and 0864 * violate the invariant that fixable edges are the only right-going 0865 * edge from their associated vertex). 0866 */ 0867 if (CheckForIntersect(tess, regUp)) 0868 { 0869 /* WalkDirtyRegions() was called recursively; we're done */ 0870 return; 0871 } 0872 } 0873 else 0874 { 0875 /* Even though we can't use CheckForIntersect(), the Org vertices 0876 * may violate the dictionary edge ordering. Check and correct this. 0877 */ 0878 (void)CheckForRightSplice(tess, regUp); 0879 } 0880 } 0881 if (eUp->Org == eLo->Org && eUp->Dst == eLo->Dst) 0882 { 0883 /* A degenerate loop consisting of only two edges -- delete it. */ 0884 AddWinding(eLo, eUp); 0885 DeleteRegion(tess, regUp); 0886 if (!__gl_meshDelete(eUp)) 0887 longjmp(tess->env, 1); 0888 regUp = RegionAbove(regLo); 0889 } 0890 } 0891 } 0892 0893 static void ConnectRightVertex(GLUtesselator *tess, ActiveRegion *regUp, GLUhalfEdge *eBottomLeft) 0894 /* 0895 * Purpose: connect a "right" vertex vEvent (one where all edges go left) 0896 * to the unprocessed portion of the mesh. Since there are no right-going 0897 * edges, two regions (one above vEvent and one below) are being merged 0898 * into one. "regUp" is the upper of these two regions. 0899 * 0900 * There are two reasons for doing this (adding a right-going edge): 0901 * - if the two regions being merged are "inside", we must add an edge 0902 * to keep them separated (the combined region would not be monotone). 0903 * - in any case, we must leave some record of vEvent in the dictionary, 0904 * so that we can merge vEvent with features that we have not seen yet. 0905 * For example, maybe there is a vertical edge which passes just to 0906 * the right of vEvent; we would like to splice vEvent into this edge. 0907 * 0908 * However, we don't want to connect vEvent to just any vertex. We don''t 0909 * want the new edge to cross any other edges; otherwise we will create 0910 * intersection vertices even when the input data had no self-intersections. 0911 * (This is a bad thing; if the user's input data has no intersections, 0912 * we don't want to generate any false intersections ourselves.) 0913 * 0914 * Our eventual goal is to connect vEvent to the leftmost unprocessed 0915 * vertex of the combined region (the union of regUp and regLo). 0916 * But because of unseen vertices with all right-going edges, and also 0917 * new vertices which may be created by edge intersections, we don''t 0918 * know where that leftmost unprocessed vertex is. In the meantime, we 0919 * connect vEvent to the closest vertex of either chain, and mark the region 0920 * as "fixUpperEdge". This flag says to delete and reconnect this edge 0921 * to the next processed vertex on the boundary of the combined region. 0922 * Quite possibly the vertex we connected to will turn out to be the 0923 * closest one, in which case we won''t need to make any changes. 0924 */ 0925 { 0926 GLUhalfEdge *eNew; 0927 GLUhalfEdge *eTopLeft = eBottomLeft->Onext; 0928 ActiveRegion *regLo = RegionBelow(regUp); 0929 GLUhalfEdge *eUp = regUp->eUp; 0930 GLUhalfEdge *eLo = regLo->eUp; 0931 int degenerate = FALSE; 0932 0933 if (eUp->Dst != eLo->Dst) 0934 { 0935 (void)CheckForIntersect(tess, regUp); 0936 } 0937 0938 /* Possible new degeneracies: upper or lower edge of regUp may pass 0939 * through vEvent, or may coincide with new intersection vertex 0940 */ 0941 if (VertEq(eUp->Org, tess->event)) 0942 { 0943 if (!__gl_meshSplice(eTopLeft->Oprev, eUp)) 0944 longjmp(tess->env, 1); 0945 regUp = TopLeftRegion(regUp); 0946 if (regUp == NULL) 0947 longjmp(tess->env, 1); 0948 eTopLeft = RegionBelow(regUp)->eUp; 0949 FinishLeftRegions(tess, RegionBelow(regUp), regLo); 0950 degenerate = TRUE; 0951 } 0952 if (VertEq(eLo->Org, tess->event)) 0953 { 0954 if (!__gl_meshSplice(eBottomLeft, eLo->Oprev)) 0955 longjmp(tess->env, 1); 0956 eBottomLeft = FinishLeftRegions(tess, regLo, NULL); 0957 degenerate = TRUE; 0958 } 0959 if (degenerate) 0960 { 0961 AddRightEdges(tess, regUp, eBottomLeft->Onext, eTopLeft, eTopLeft, TRUE); 0962 return; 0963 } 0964 0965 /* Non-degenerate situation -- need to add a temporary, fixable edge. 0966 * Connect to the closer of eLo->Org, eUp->Org. 0967 */ 0968 if (VertLeq(eLo->Org, eUp->Org)) 0969 { 0970 eNew = eLo->Oprev; 0971 } 0972 else 0973 { 0974 eNew = eUp; 0975 } 0976 eNew = __gl_meshConnect(eBottomLeft->Lprev, eNew); 0977 if (eNew == NULL) 0978 longjmp(tess->env, 1); 0979 0980 /* Prevent cleanup, otherwise eNew might disappear before we've even 0981 * had a chance to mark it as a temporary edge. 0982 */ 0983 AddRightEdges(tess, regUp, eNew, eNew->Onext, eNew->Onext, FALSE); 0984 eNew->Sym->activeRegion->fixUpperEdge = TRUE; 0985 WalkDirtyRegions(tess, regUp); 0986 } 0987 0988 /* Because vertices at exactly the same location are merged together 0989 * before we process the sweep event, some degenerate cases can't occur. 0990 * However if someone eventually makes the modifications required to 0991 * merge features which are close together, the cases below marked 0992 * TOLERANCE_NONZERO will be useful. They were debugged before the 0993 * code to merge identical vertices in the main loop was added. 0994 */ 0995 #define TOLERANCE_NONZERO FALSE 0996 0997 static void ConnectLeftDegenerate(GLUtesselator *tess, ActiveRegion *regUp, GLUvertex *vEvent) 0998 /* 0999 * The event vertex lies exacty on an already-processed edge or vertex. 1000 * Adding the new vertex involves splicing it into the already-processed 1001 * part of the mesh. 1002 */ 1003 { 1004 GLUhalfEdge *e, *eTopLeft, *eTopRight, *eLast; 1005 ActiveRegion *reg; 1006 1007 e = regUp->eUp; 1008 if (VertEq(e->Org, vEvent)) 1009 { 1010 /* e->Org is an unprocessed vertex - just combine them, and wait 1011 * for e->Org to be pulled from the queue 1012 */ 1013 assert(TOLERANCE_NONZERO); 1014 SpliceMergeVertices(tess, e, vEvent->anEdge); 1015 return; 1016 } 1017 1018 if (!VertEq(e->Dst, vEvent)) 1019 { 1020 /* General case -- splice vEvent into edge e which passes through it */ 1021 if (__gl_meshSplitEdge(e->Sym) == NULL) 1022 longjmp(tess->env, 1); 1023 if (regUp->fixUpperEdge) 1024 { 1025 /* This edge was fixable -- delete unused portion of original edge */ 1026 if (!__gl_meshDelete(e->Onext)) 1027 longjmp(tess->env, 1); 1028 regUp->fixUpperEdge = FALSE; 1029 } 1030 if (!__gl_meshSplice(vEvent->anEdge, e)) 1031 longjmp(tess->env, 1); 1032 SweepEvent(tess, vEvent); /* recurse */ 1033 return; 1034 } 1035 1036 /* vEvent coincides with e->Dst, which has already been processed. 1037 * Splice in the additional right-going edges. 1038 */ 1039 assert(TOLERANCE_NONZERO); 1040 regUp = TopRightRegion(regUp); 1041 reg = RegionBelow(regUp); 1042 eTopRight = reg->eUp->Sym; 1043 eTopLeft = eLast = eTopRight->Onext; 1044 if (reg->fixUpperEdge) 1045 { 1046 /* Here e->Dst has only a single fixable edge going right. 1047 * We can delete it since now we have some real right-going edges. 1048 */ 1049 assert(eTopLeft != eTopRight); /* there are some left edges too */ 1050 DeleteRegion(tess, reg); 1051 if (!__gl_meshDelete(eTopRight)) 1052 longjmp(tess->env, 1); 1053 eTopRight = eTopLeft->Oprev; 1054 } 1055 if (!__gl_meshSplice(vEvent->anEdge, eTopRight)) 1056 longjmp(tess->env, 1); 1057 if (!EdgeGoesLeft(eTopLeft)) 1058 { 1059 /* e->Dst had no left-going edges -- indicate this to AddRightEdges() */ 1060 eTopLeft = NULL; 1061 } 1062 AddRightEdges(tess, regUp, eTopRight->Onext, eLast, eTopLeft, TRUE); 1063 } 1064 1065 static void ConnectLeftVertex(GLUtesselator *tess, GLUvertex *vEvent) 1066 /* 1067 * Purpose: connect a "left" vertex (one where both edges go right) 1068 * to the processed portion of the mesh. Let R be the active region 1069 * containing vEvent, and let U and L be the upper and lower edge 1070 * chains of R. There are two possibilities: 1071 * 1072 * - the normal case: split R into two regions, by connecting vEvent to 1073 * the rightmost vertex of U or L lying to the left of the sweep line 1074 * 1075 * - the degenerate case: if vEvent is close enough to U or L, we 1076 * merge vEvent into that edge chain. The subcases are: 1077 * - merging with the rightmost vertex of U or L 1078 * - merging with the active edge of U or L 1079 * - merging with an already-processed portion of U or L 1080 */ 1081 { 1082 ActiveRegion *regUp, *regLo, *reg; 1083 GLUhalfEdge *eUp, *eLo, *eNew; 1084 ActiveRegion tmp; 1085 1086 /* assert( vEvent->anEdge->Onext->Onext == vEvent->anEdge ); */ 1087 1088 /* Get a pointer to the active region containing vEvent */ 1089 tmp.eUp = vEvent->anEdge->Sym; 1090 /* __GL_DICTLISTKEY */ /* __gl_dictListSearch */ 1091 regUp = (ActiveRegion *)dictKey(dictSearch(tess->dict, &tmp)); 1092 regLo = RegionBelow(regUp); 1093 eUp = regUp->eUp; 1094 eLo = regLo->eUp; 1095 1096 /* Try merging with U or L first */ 1097 if (EdgeSign(eUp->Dst, vEvent, eUp->Org) == 0) 1098 { 1099 ConnectLeftDegenerate(tess, regUp, vEvent); 1100 return; 1101 } 1102 1103 /* Connect vEvent to rightmost processed vertex of either chain. 1104 * e->Dst is the vertex that we will connect to vEvent. 1105 */ 1106 reg = VertLeq(eLo->Dst, eUp->Dst) ? regUp : regLo; 1107 1108 if (regUp->inside || reg->fixUpperEdge) 1109 { 1110 if (reg == regUp) 1111 { 1112 eNew = __gl_meshConnect(vEvent->anEdge->Sym, eUp->Lnext); 1113 if (eNew == NULL) 1114 longjmp(tess->env, 1); 1115 } 1116 else 1117 { 1118 GLUhalfEdge *tempHalfEdge = __gl_meshConnect(eLo->Dnext, vEvent->anEdge); 1119 if (tempHalfEdge == NULL) 1120 longjmp(tess->env, 1); 1121 1122 eNew = tempHalfEdge->Sym; 1123 } 1124 if (reg->fixUpperEdge) 1125 { 1126 if (!FixUpperEdge(reg, eNew)) 1127 longjmp(tess->env, 1); 1128 } 1129 else 1130 { 1131 ComputeWinding(tess, AddRegionBelow(tess, regUp, eNew)); 1132 } 1133 SweepEvent(tess, vEvent); 1134 } 1135 else 1136 { 1137 /* The new vertex is in a region which does not belong to the polygon. 1138 * We don''t need to connect this vertex to the rest of the mesh. 1139 */ 1140 AddRightEdges(tess, regUp, vEvent->anEdge, vEvent->anEdge, NULL, TRUE); 1141 } 1142 } 1143 1144 static void SweepEvent(GLUtesselator *tess, GLUvertex *vEvent) 1145 /* 1146 * Does everything necessary when the sweep line crosses a vertex. 1147 * Updates the mesh and the edge dictionary. 1148 */ 1149 { 1150 ActiveRegion *regUp, *reg; 1151 GLUhalfEdge *e, *eTopLeft, *eBottomLeft; 1152 1153 tess->event = vEvent; /* for access in EdgeLeq() */ 1154 DebugEvent(tess); 1155 1156 /* Check if this vertex is the right endpoint of an edge that is 1157 * already in the dictionary. In this case we don't need to waste 1158 * time searching for the location to insert new edges. 1159 */ 1160 e = vEvent->anEdge; 1161 while (e->activeRegion == NULL) 1162 { 1163 e = e->Onext; 1164 if (e == vEvent->anEdge) 1165 { 1166 /* All edges go right -- not incident to any processed edges */ 1167 ConnectLeftVertex(tess, vEvent); 1168 return; 1169 } 1170 } 1171 1172 /* Processing consists of two phases: first we "finish" all the 1173 * active regions where both the upper and lower edges terminate 1174 * at vEvent (ie. vEvent is closing off these regions). 1175 * We mark these faces "inside" or "outside" the polygon according 1176 * to their winding number, and delete the edges from the dictionary. 1177 * This takes care of all the left-going edges from vEvent. 1178 */ 1179 regUp = TopLeftRegion(e->activeRegion); 1180 if (regUp == NULL) 1181 longjmp(tess->env, 1); 1182 reg = RegionBelow(regUp); 1183 eTopLeft = reg->eUp; 1184 eBottomLeft = FinishLeftRegions(tess, reg, NULL); 1185 1186 /* Next we process all the right-going edges from vEvent. This 1187 * involves adding the edges to the dictionary, and creating the 1188 * associated "active regions" which record information about the 1189 * regions between adjacent dictionary edges. 1190 */ 1191 if (eBottomLeft->Onext == eTopLeft) 1192 { 1193 /* No right-going edges -- add a temporary "fixable" edge */ 1194 ConnectRightVertex(tess, regUp, eBottomLeft); 1195 } 1196 else 1197 { 1198 AddRightEdges(tess, regUp, eBottomLeft->Onext, eTopLeft, eTopLeft, TRUE); 1199 } 1200 } 1201 1202 /* Make the sentinel coordinates big enough that they will never be 1203 * merged with real input features. (Even with the largest possible 1204 * input contour and the maximum tolerance of 1.0, no merging will be 1205 * done with coordinates larger than 3 * GLU_TESS_MAX_COORD). 1206 */ 1207 #define SENTINEL_COORD (4 * GLU_TESS_MAX_COORD) 1208 1209 static void AddSentinel(GLUtesselator *tess, GLdouble t) 1210 /* 1211 * We add two sentinel edges above and below all other edges, 1212 * to avoid special cases at the top and bottom. 1213 */ 1214 { 1215 GLUhalfEdge *e; 1216 ActiveRegion *reg = (ActiveRegion *)memAlloc(sizeof(ActiveRegion)); 1217 if (reg == NULL) 1218 longjmp(tess->env, 1); 1219 1220 e = __gl_meshMakeEdge(tess->mesh); 1221 if (e == NULL) 1222 longjmp(tess->env, 1); 1223 1224 e->Org->s = SENTINEL_COORD; 1225 e->Org->t = t; 1226 e->Dst->s = -SENTINEL_COORD; 1227 e->Dst->t = t; 1228 tess->event = e->Dst; /* initialize it */ 1229 1230 reg->eUp = e; 1231 reg->windingNumber = 0; 1232 reg->inside = FALSE; 1233 reg->fixUpperEdge = FALSE; 1234 reg->sentinel = TRUE; 1235 reg->dirty = FALSE; 1236 reg->nodeUp = dictInsert(tess->dict, reg); /* __gl_dictListInsertBefore */ 1237 if (reg->nodeUp == NULL) 1238 longjmp(tess->env, 1); 1239 } 1240 1241 static void InitEdgeDict(GLUtesselator *tess) 1242 /* 1243 * We maintain an ordering of edge intersections with the sweep line. 1244 * This order is maintained in a dynamic dictionary. 1245 */ 1246 { 1247 /* __gl_dictListNewDict */ 1248 tess->dict = dictNewDict(tess, (int (*)(void *, DictKey, DictKey))EdgeLeq); 1249 if (tess->dict == NULL) 1250 longjmp(tess->env, 1); 1251 1252 AddSentinel(tess, -SENTINEL_COORD); 1253 AddSentinel(tess, SENTINEL_COORD); 1254 } 1255 1256 static void DoneEdgeDict(GLUtesselator *tess) 1257 { 1258 ActiveRegion *reg; 1259 #ifndef NDEBUG 1260 int fixedEdges = 0; 1261 #endif 1262 1263 /* __GL_DICTLISTKEY */ /* __GL_DICTLISTMIN */ 1264 while ((reg = (ActiveRegion *)dictKey(dictMin(tess->dict))) != NULL) 1265 { 1266 /* 1267 * At the end of all processing, the dictionary should contain 1268 * only the two sentinel edges, plus at most one "fixable" edge 1269 * created by ConnectRightVertex(). 1270 */ 1271 if (!reg->sentinel) 1272 { 1273 assert(reg->fixUpperEdge); 1274 assert(++fixedEdges == 1); 1275 } 1276 assert(reg->windingNumber == 0); 1277 DeleteRegion(tess, reg); 1278 /* __gl_meshDelete( reg->eUp );*/ 1279 } 1280 dictDeleteDict(tess->dict); /* __gl_dictListDeleteDict */ 1281 } 1282 1283 static void RemoveDegenerateEdges(GLUtesselator *tess) 1284 /* 1285 * Remove zero-length edges, and contours with fewer than 3 vertices. 1286 */ 1287 { 1288 GLUhalfEdge *e, *eNext, *eLnext; 1289 GLUhalfEdge *eHead = &tess->mesh->eHead; 1290 1291 /*LINTED*/ 1292 for (e = eHead->next; e != eHead; e = eNext) 1293 { 1294 eNext = e->next; 1295 eLnext = e->Lnext; 1296 1297 if (VertEq(e->Org, e->Dst) && e->Lnext->Lnext != e) 1298 { 1299 /* Zero-length edge, contour has at least 3 edges */ 1300 1301 SpliceMergeVertices(tess, eLnext, e); /* deletes e->Org */ 1302 if (!__gl_meshDelete(e)) 1303 longjmp(tess->env, 1); /* e is a self-loop */ 1304 e = eLnext; 1305 eLnext = e->Lnext; 1306 } 1307 if (eLnext->Lnext == e) 1308 { 1309 /* Degenerate contour (one or two edges) */ 1310 1311 if (eLnext != e) 1312 { 1313 if (eLnext == eNext || eLnext == eNext->Sym) 1314 { 1315 eNext = eNext->next; 1316 } 1317 if (!__gl_meshDelete(eLnext)) 1318 longjmp(tess->env, 1); 1319 } 1320 if (e == eNext || e == eNext->Sym) 1321 { 1322 eNext = eNext->next; 1323 } 1324 if (!__gl_meshDelete(e)) 1325 longjmp(tess->env, 1); 1326 } 1327 } 1328 } 1329 1330 static int InitPriorityQ(GLUtesselator *tess) 1331 /* 1332 * Insert all vertices into the priority queue which determines the 1333 * order in which vertices cross the sweep line. 1334 */ 1335 { 1336 PriorityQ *pq; 1337 GLUvertex *v, *vHead; 1338 1339 /* __gl_pqSortNewPriorityQ */ 1340 pq = tess->pq = pqNewPriorityQ((int (*)(PQkey, PQkey))__gl_vertLeq); 1341 if (pq == NULL) 1342 return 0; 1343 1344 vHead = &tess->mesh->vHead; 1345 for (v = vHead->next; v != vHead; v = v->next) 1346 { 1347 v->pqHandle = pqInsert(pq, v); /* __gl_pqSortInsert */ 1348 if (v->pqHandle == LONG_MAX) 1349 break; 1350 } 1351 if (v != vHead || !pqInit(pq)) 1352 { /* __gl_pqSortInit */ 1353 pqDeletePriorityQ(tess->pq); /* __gl_pqSortDeletePriorityQ */ 1354 tess->pq = NULL; 1355 return 0; 1356 } 1357 1358 return 1; 1359 } 1360 1361 static void DonePriorityQ(GLUtesselator *tess) 1362 { 1363 pqDeletePriorityQ(tess->pq); /* __gl_pqSortDeletePriorityQ */ 1364 } 1365 1366 static int RemoveDegenerateFaces(GLUmesh *mesh) 1367 /* 1368 * Delete any degenerate faces with only two edges. WalkDirtyRegions() 1369 * will catch almost all of these, but it won't catch degenerate faces 1370 * produced by splice operations on already-processed edges. 1371 * The two places this can happen are in FinishLeftRegions(), when 1372 * we splice in a "temporary" edge produced by ConnectRightVertex(), 1373 * and in CheckForLeftSplice(), where we splice already-processed 1374 * edges to ensure that our dictionary invariants are not violated 1375 * by numerical errors. 1376 * 1377 * In both these cases it is *very* dangerous to delete the offending 1378 * edge at the time, since one of the routines further up the stack 1379 * will sometimes be keeping a pointer to that edge. 1380 */ 1381 { 1382 GLUface *f, *fNext; 1383 GLUhalfEdge *e; 1384 1385 /*LINTED*/ 1386 for (f = mesh->fHead.next; f != &mesh->fHead; f = fNext) 1387 { 1388 fNext = f->next; 1389 e = f->anEdge; 1390 assert(e->Lnext != e); 1391 1392 if (e->Lnext->Lnext == e) 1393 { 1394 /* A face with only two edges */ 1395 AddWinding(e->Onext, e); 1396 if (!__gl_meshDelete(e)) 1397 return 0; 1398 } 1399 } 1400 return 1; 1401 } 1402 1403 int __gl_computeInterior(GLUtesselator *tess) 1404 /* 1405 * __gl_computeInterior( tess ) computes the planar arrangement specified 1406 * by the given contours, and further subdivides this arrangement 1407 * into regions. Each region is marked "inside" if it belongs 1408 * to the polygon, according to the rule given by tess->windingRule. 1409 * Each interior region is guaranteed be monotone. 1410 */ 1411 { 1412 GLUvertex *v, *vNext; 1413 1414 tess->fatalError = FALSE; 1415 1416 /* Each vertex defines an event for our sweep line. Start by inserting 1417 * all the vertices in a priority queue. Events are processed in 1418 * lexicographic order, ie. 1419 * 1420 * e1 < e2 iff e1.x < e2.x || (e1.x == e2.x && e1.y < e2.y) 1421 */ 1422 RemoveDegenerateEdges(tess); 1423 if (!InitPriorityQ(tess)) 1424 return 0; /* if error */ 1425 InitEdgeDict(tess); 1426 1427 /* __gl_pqSortExtractMin */ 1428 while ((v = (GLUvertex *)pqExtractMin(tess->pq)) != NULL) 1429 { 1430 for (;;) 1431 { 1432 vNext = (GLUvertex *)pqMinimum(tess->pq); /* __gl_pqSortMinimum */ 1433 if (vNext == NULL || !VertEq(vNext, v)) 1434 break; 1435 1436 /* Merge together all vertices at exactly the same location. 1437 * This is more efficient than processing them one at a time, 1438 * simplifies the code (see ConnectLeftDegenerate), and is also 1439 * important for correct handling of certain degenerate cases. 1440 * For example, suppose there are two identical edges A and B 1441 * that belong to different contours (so without this code they would 1442 * be processed by separate sweep events). Suppose another edge C 1443 * crosses A and B from above. When A is processed, we split it 1444 * at its intersection point with C. However this also splits C, 1445 * so when we insert B we may compute a slightly different 1446 * intersection point. This might leave two edges with a small 1447 * gap between them. This kind of error is especially obvious 1448 * when using boundary extraction (GLU_TESS_BOUNDARY_ONLY). 1449 */ 1450 vNext = (GLUvertex *)pqExtractMin(tess->pq); /* __gl_pqSortExtractMin*/ 1451 SpliceMergeVertices(tess, v->anEdge, vNext->anEdge); 1452 } 1453 SweepEvent(tess, v); 1454 } 1455 1456 /* Set tess->event for debugging purposes */ 1457 /* __GL_DICTLISTKEY */ /* __GL_DICTLISTMIN */ 1458 tess->event = ((ActiveRegion *)dictKey(dictMin(tess->dict)))->eUp->Org; 1459 DebugEvent(tess); 1460 DoneEdgeDict(tess); 1461 DonePriorityQ(tess); 1462 1463 if (!RemoveDegenerateFaces(tess->mesh)) 1464 return 0; 1465 __gl_meshCheckMesh(tess->mesh); 1466 1467 return 1; 1468 }