File indexing completed on 2024-03-24 15:17:33
0001 /* 0002 ** Author: Eric Veach, July 1994. 0003 ** 0004 */ 0005 0006 #include "gluos.h" 0007 #include <stddef.h> 0008 #include <assert.h> 0009 #include "mesh.h" 0010 #include "memalloc.h" 0011 0012 #ifndef TRUE 0013 #define TRUE 1 0014 #endif 0015 #ifndef FALSE 0016 #define FALSE 0 0017 #endif 0018 0019 static GLUvertex *allocVertex() 0020 { 0021 return (GLUvertex *)memAlloc(sizeof(GLUvertex)); 0022 } 0023 0024 static GLUface *allocFace() 0025 { 0026 return (GLUface *)memAlloc(sizeof(GLUface)); 0027 } 0028 0029 /************************ Utility Routines ************************/ 0030 0031 /* Allocate and free half-edges in pairs for efficiency. 0032 * The *only* place that should use this fact is allocation/free. 0033 */ 0034 typedef struct 0035 { 0036 GLUhalfEdge e, eSym; 0037 } EdgePair; 0038 0039 /* MakeEdge creates a new pair of half-edges which form their own loop. 0040 * No vertex or face structures are allocated, but these must be assigned 0041 * before the current edge operation is completed. 0042 */ 0043 static GLUhalfEdge *MakeEdge(GLUhalfEdge *eNext) 0044 { 0045 GLUhalfEdge *e; 0046 GLUhalfEdge *eSym; 0047 GLUhalfEdge *ePrev; 0048 EdgePair *pair = (EdgePair *)memAlloc(sizeof(EdgePair)); 0049 if (pair == NULL) 0050 return NULL; 0051 0052 e = &pair->e; 0053 eSym = &pair->eSym; 0054 0055 /* Make sure eNext points to the first edge of the edge pair */ 0056 if (eNext->Sym < eNext) 0057 { 0058 eNext = eNext->Sym; 0059 } 0060 0061 /* Insert in circular doubly-linked list before eNext. 0062 * Note that the prev pointer is stored in Sym->next. 0063 */ 0064 ePrev = eNext->Sym->next; 0065 eSym->next = ePrev; 0066 ePrev->Sym->next = e; 0067 e->next = eNext; 0068 eNext->Sym->next = eSym; 0069 0070 e->Sym = eSym; 0071 e->Onext = e; 0072 e->Lnext = eSym; 0073 e->Org = NULL; 0074 e->Lface = NULL; 0075 e->winding = 0; 0076 e->activeRegion = NULL; 0077 0078 eSym->Sym = e; 0079 eSym->Onext = eSym; 0080 eSym->Lnext = e; 0081 eSym->Org = NULL; 0082 eSym->Lface = NULL; 0083 eSym->winding = 0; 0084 eSym->activeRegion = NULL; 0085 0086 return e; 0087 } 0088 0089 /* Splice( a, b ) is best described by the Guibas/Stolfi paper or the 0090 * CS348a notes (see mesh.h). Basically it modifies the mesh so that 0091 * a->Onext and b->Onext are exchanged. This can have various effects 0092 * depending on whether a and b belong to different face or vertex rings. 0093 * For more explanation see __gl_meshSplice() below. 0094 */ 0095 static void Splice(GLUhalfEdge *a, GLUhalfEdge *b) 0096 { 0097 GLUhalfEdge *aOnext = a->Onext; 0098 GLUhalfEdge *bOnext = b->Onext; 0099 0100 aOnext->Sym->Lnext = b; 0101 bOnext->Sym->Lnext = a; 0102 a->Onext = bOnext; 0103 b->Onext = aOnext; 0104 } 0105 0106 /* MakeVertex( newVertex, eOrig, vNext ) attaches a new vertex and makes it the 0107 * origin of all edges in the vertex loop to which eOrig belongs. "vNext" gives 0108 * a place to insert the new vertex in the global vertex list. We insert 0109 * the new vertex *before* vNext so that algorithms which walk the vertex 0110 * list will not see the newly created vertices. 0111 */ 0112 static void MakeVertex(GLUvertex *newVertex, GLUhalfEdge *eOrig, GLUvertex *vNext) 0113 { 0114 GLUhalfEdge *e; 0115 GLUvertex *vPrev; 0116 GLUvertex *vNew = newVertex; 0117 0118 assert(vNew != NULL); 0119 0120 /* insert in circular doubly-linked list before vNext */ 0121 vPrev = vNext->prev; 0122 vNew->prev = vPrev; 0123 vPrev->next = vNew; 0124 vNew->next = vNext; 0125 vNext->prev = vNew; 0126 0127 vNew->anEdge = eOrig; 0128 vNew->data = NULL; 0129 /* leave coords, s, t undefined */ 0130 0131 /* fix other edges on this vertex loop */ 0132 e = eOrig; 0133 do 0134 { 0135 e->Org = vNew; 0136 e = e->Onext; 0137 } while (e != eOrig); 0138 } 0139 0140 /* MakeFace( newFace, eOrig, fNext ) attaches a new face and makes it the left 0141 * face of all edges in the face loop to which eOrig belongs. "fNext" gives 0142 * a place to insert the new face in the global face list. We insert 0143 * the new face *before* fNext so that algorithms which walk the face 0144 * list will not see the newly created faces. 0145 */ 0146 static void MakeFace(GLUface *newFace, GLUhalfEdge *eOrig, GLUface *fNext) 0147 { 0148 GLUhalfEdge *e; 0149 GLUface *fPrev; 0150 GLUface *fNew = newFace; 0151 0152 assert(fNew != NULL); 0153 0154 /* insert in circular doubly-linked list before fNext */ 0155 fPrev = fNext->prev; 0156 fNew->prev = fPrev; 0157 fPrev->next = fNew; 0158 fNew->next = fNext; 0159 fNext->prev = fNew; 0160 0161 fNew->anEdge = eOrig; 0162 fNew->data = NULL; 0163 fNew->trail = NULL; 0164 fNew->marked = FALSE; 0165 0166 /* The new face is marked "inside" if the old one was. This is a 0167 * convenience for the common case where a face has been split in two. 0168 */ 0169 fNew->inside = fNext->inside; 0170 0171 /* fix other edges on this face loop */ 0172 e = eOrig; 0173 do 0174 { 0175 e->Lface = fNew; 0176 e = e->Lnext; 0177 } while (e != eOrig); 0178 } 0179 0180 /* KillEdge( eDel ) destroys an edge (the half-edges eDel and eDel->Sym), 0181 * and removes from the global edge list. 0182 */ 0183 static void KillEdge(GLUhalfEdge *eDel) 0184 { 0185 GLUhalfEdge *ePrev, *eNext; 0186 0187 /* Half-edges are allocated in pairs, see EdgePair above */ 0188 if (eDel->Sym < eDel) 0189 { 0190 eDel = eDel->Sym; 0191 } 0192 0193 /* delete from circular doubly-linked list */ 0194 eNext = eDel->next; 0195 ePrev = eDel->Sym->next; 0196 eNext->Sym->next = ePrev; 0197 ePrev->Sym->next = eNext; 0198 0199 memFree(eDel); 0200 } 0201 0202 /* KillVertex( vDel ) destroys a vertex and removes it from the global 0203 * vertex list. It updates the vertex loop to point to a given new vertex. 0204 */ 0205 static void KillVertex(GLUvertex *vDel, GLUvertex *newOrg) 0206 { 0207 GLUhalfEdge *e, *eStart = vDel->anEdge; 0208 GLUvertex *vPrev, *vNext; 0209 0210 /* change the origin of all affected edges */ 0211 e = eStart; 0212 do 0213 { 0214 e->Org = newOrg; 0215 e = e->Onext; 0216 } while (e != eStart); 0217 0218 /* delete from circular doubly-linked list */ 0219 vPrev = vDel->prev; 0220 vNext = vDel->next; 0221 vNext->prev = vPrev; 0222 vPrev->next = vNext; 0223 0224 memFree(vDel); 0225 } 0226 0227 /* KillFace( fDel ) destroys a face and removes it from the global face 0228 * list. It updates the face loop to point to a given new face. 0229 */ 0230 static void KillFace(GLUface *fDel, GLUface *newLface) 0231 { 0232 GLUhalfEdge *e, *eStart = fDel->anEdge; 0233 GLUface *fPrev, *fNext; 0234 0235 /* change the left face of all affected edges */ 0236 e = eStart; 0237 do 0238 { 0239 e->Lface = newLface; 0240 e = e->Lnext; 0241 } while (e != eStart); 0242 0243 /* delete from circular doubly-linked list */ 0244 fPrev = fDel->prev; 0245 fNext = fDel->next; 0246 fNext->prev = fPrev; 0247 fPrev->next = fNext; 0248 0249 memFree(fDel); 0250 } 0251 0252 /****************** Basic Edge Operations **********************/ 0253 0254 /* __gl_meshMakeEdge creates one edge, two vertices, and a loop (face). 0255 * The loop consists of the two new half-edges. 0256 */ 0257 GLUhalfEdge *__gl_meshMakeEdge(GLUmesh *mesh) 0258 { 0259 GLUvertex *newVertex1 = allocVertex(); 0260 GLUvertex *newVertex2 = allocVertex(); 0261 GLUface *newFace = allocFace(); 0262 GLUhalfEdge *e; 0263 0264 /* if any one is null then all get freed */ 0265 if (newVertex1 == NULL || newVertex2 == NULL || newFace == NULL) 0266 { 0267 if (newVertex1 != NULL) 0268 memFree(newVertex1); 0269 if (newVertex2 != NULL) 0270 memFree(newVertex2); 0271 if (newFace != NULL) 0272 memFree(newFace); 0273 return NULL; 0274 } 0275 0276 e = MakeEdge(&mesh->eHead); 0277 if (e == NULL) 0278 { 0279 memFree(newVertex1); 0280 memFree(newVertex2); 0281 memFree(newFace); 0282 return NULL; 0283 } 0284 0285 MakeVertex(newVertex1, e, &mesh->vHead); 0286 MakeVertex(newVertex2, e->Sym, &mesh->vHead); 0287 MakeFace(newFace, e, &mesh->fHead); 0288 return e; 0289 } 0290 0291 /* __gl_meshSplice( eOrg, eDst ) is the basic operation for changing the 0292 * mesh connectivity and topology. It changes the mesh so that 0293 * eOrg->Onext <- OLD( eDst->Onext ) 0294 * eDst->Onext <- OLD( eOrg->Onext ) 0295 * where OLD(...) means the value before the meshSplice operation. 0296 * 0297 * This can have two effects on the vertex structure: 0298 * - if eOrg->Org != eDst->Org, the two vertices are merged together 0299 * - if eOrg->Org == eDst->Org, the origin is split into two vertices 0300 * In both cases, eDst->Org is changed and eOrg->Org is untouched. 0301 * 0302 * Similarly (and independently) for the face structure, 0303 * - if eOrg->Lface == eDst->Lface, one loop is split into two 0304 * - if eOrg->Lface != eDst->Lface, two distinct loops are joined into one 0305 * In both cases, eDst->Lface is changed and eOrg->Lface is unaffected. 0306 * 0307 * Some special cases: 0308 * If eDst == eOrg, the operation has no effect. 0309 * If eDst == eOrg->Lnext, the new face will have a single edge. 0310 * If eDst == eOrg->Lprev, the old face will have a single edge. 0311 * If eDst == eOrg->Onext, the new vertex will have a single edge. 0312 * If eDst == eOrg->Oprev, the old vertex will have a single edge. 0313 */ 0314 int __gl_meshSplice(GLUhalfEdge *eOrg, GLUhalfEdge *eDst) 0315 { 0316 int joiningLoops = FALSE; 0317 int joiningVertices = FALSE; 0318 0319 if (eOrg == eDst) 0320 return 1; 0321 0322 if (eDst->Org != eOrg->Org) 0323 { 0324 /* We are merging two disjoint vertices -- destroy eDst->Org */ 0325 joiningVertices = TRUE; 0326 KillVertex(eDst->Org, eOrg->Org); 0327 } 0328 if (eDst->Lface != eOrg->Lface) 0329 { 0330 /* We are connecting two disjoint loops -- destroy eDst->Lface */ 0331 joiningLoops = TRUE; 0332 KillFace(eDst->Lface, eOrg->Lface); 0333 } 0334 0335 /* Change the edge structure */ 0336 Splice(eDst, eOrg); 0337 0338 if (!joiningVertices) 0339 { 0340 GLUvertex *newVertex = allocVertex(); 0341 if (newVertex == NULL) 0342 return 0; 0343 0344 /* We split one vertex into two -- the new vertex is eDst->Org. 0345 * Make sure the old vertex points to a valid half-edge. 0346 */ 0347 MakeVertex(newVertex, eDst, eOrg->Org); 0348 eOrg->Org->anEdge = eOrg; 0349 } 0350 if (!joiningLoops) 0351 { 0352 GLUface *newFace = allocFace(); 0353 if (newFace == NULL) 0354 return 0; 0355 0356 /* We split one loop into two -- the new loop is eDst->Lface. 0357 * Make sure the old face points to a valid half-edge. 0358 */ 0359 MakeFace(newFace, eDst, eOrg->Lface); 0360 eOrg->Lface->anEdge = eOrg; 0361 } 0362 0363 return 1; 0364 } 0365 0366 /* __gl_meshDelete( eDel ) removes the edge eDel. There are several cases: 0367 * if (eDel->Lface != eDel->Rface), we join two loops into one; the loop 0368 * eDel->Lface is deleted. Otherwise, we are splitting one loop into two; 0369 * the newly created loop will contain eDel->Dst. If the deletion of eDel 0370 * would create isolated vertices, those are deleted as well. 0371 * 0372 * This function could be implemented as two calls to __gl_meshSplice 0373 * plus a few calls to memFree, but this would allocate and delete 0374 * unnecessary vertices and faces. 0375 */ 0376 int __gl_meshDelete(GLUhalfEdge *eDel) 0377 { 0378 GLUhalfEdge *eDelSym = eDel->Sym; 0379 int joiningLoops = FALSE; 0380 0381 /* First step: disconnect the origin vertex eDel->Org. We make all 0382 * changes to get a consistent mesh in this "intermediate" state. 0383 */ 0384 if (eDel->Lface != eDel->Rface) 0385 { 0386 /* We are joining two loops into one -- remove the left face */ 0387 joiningLoops = TRUE; 0388 KillFace(eDel->Lface, eDel->Rface); 0389 } 0390 0391 if (eDel->Onext == eDel) 0392 { 0393 KillVertex(eDel->Org, NULL); 0394 } 0395 else 0396 { 0397 /* Make sure that eDel->Org and eDel->Rface point to valid half-edges */ 0398 eDel->Rface->anEdge = eDel->Oprev; 0399 eDel->Org->anEdge = eDel->Onext; 0400 0401 Splice(eDel, eDel->Oprev); 0402 if (!joiningLoops) 0403 { 0404 GLUface *newFace = allocFace(); 0405 if (newFace == NULL) 0406 return 0; 0407 0408 /* We are splitting one loop into two -- create a new loop for eDel. */ 0409 MakeFace(newFace, eDel, eDel->Lface); 0410 } 0411 } 0412 0413 /* Claim: the mesh is now in a consistent state, except that eDel->Org 0414 * may have been deleted. Now we disconnect eDel->Dst. 0415 */ 0416 if (eDelSym->Onext == eDelSym) 0417 { 0418 KillVertex(eDelSym->Org, NULL); 0419 KillFace(eDelSym->Lface, NULL); 0420 } 0421 else 0422 { 0423 /* Make sure that eDel->Dst and eDel->Lface point to valid half-edges */ 0424 eDel->Lface->anEdge = eDelSym->Oprev; 0425 eDelSym->Org->anEdge = eDelSym->Onext; 0426 Splice(eDelSym, eDelSym->Oprev); 0427 } 0428 0429 /* Any isolated vertices or faces have already been freed. */ 0430 KillEdge(eDel); 0431 0432 return 1; 0433 } 0434 0435 /******************** Other Edge Operations **********************/ 0436 0437 /* All these routines can be implemented with the basic edge 0438 * operations above. They are provided for convenience and efficiency. 0439 */ 0440 0441 /* __gl_meshAddEdgeVertex( eOrg ) creates a new edge eNew such that 0442 * eNew == eOrg->Lnext, and eNew->Dst is a newly created vertex. 0443 * eOrg and eNew will have the same left face. 0444 */ 0445 GLUhalfEdge *__gl_meshAddEdgeVertex(GLUhalfEdge *eOrg) 0446 { 0447 GLUhalfEdge *eNewSym; 0448 GLUhalfEdge *eNew = MakeEdge(eOrg); 0449 if (eNew == NULL) 0450 return NULL; 0451 0452 eNewSym = eNew->Sym; 0453 0454 /* Connect the new edge appropriately */ 0455 Splice(eNew, eOrg->Lnext); 0456 0457 /* Set the vertex and face information */ 0458 eNew->Org = eOrg->Dst; 0459 { 0460 GLUvertex *newVertex = allocVertex(); 0461 if (newVertex == NULL) 0462 return NULL; 0463 0464 MakeVertex(newVertex, eNewSym, eNew->Org); 0465 } 0466 eNew->Lface = eNewSym->Lface = eOrg->Lface; 0467 0468 return eNew; 0469 } 0470 0471 /* __gl_meshSplitEdge( eOrg ) splits eOrg into two edges eOrg and eNew, 0472 * such that eNew == eOrg->Lnext. The new vertex is eOrg->Dst == eNew->Org. 0473 * eOrg and eNew will have the same left face. 0474 */ 0475 GLUhalfEdge *__gl_meshSplitEdge(GLUhalfEdge *eOrg) 0476 { 0477 GLUhalfEdge *eNew; 0478 GLUhalfEdge *tempHalfEdge = __gl_meshAddEdgeVertex(eOrg); 0479 if (tempHalfEdge == NULL) 0480 return NULL; 0481 0482 eNew = tempHalfEdge->Sym; 0483 0484 /* Disconnect eOrg from eOrg->Dst and connect it to eNew->Org */ 0485 Splice(eOrg->Sym, eOrg->Sym->Oprev); 0486 Splice(eOrg->Sym, eNew); 0487 0488 /* Set the vertex and face information */ 0489 eOrg->Dst = eNew->Org; 0490 eNew->Dst->anEdge = eNew->Sym; /* may have pointed to eOrg->Sym */ 0491 eNew->Rface = eOrg->Rface; 0492 eNew->winding = eOrg->winding; /* copy old winding information */ 0493 eNew->Sym->winding = eOrg->Sym->winding; 0494 0495 return eNew; 0496 } 0497 0498 /* __gl_meshConnect( eOrg, eDst ) creates a new edge from eOrg->Dst 0499 * to eDst->Org, and returns the corresponding half-edge eNew. 0500 * If eOrg->Lface == eDst->Lface, this splits one loop into two, 0501 * and the newly created loop is eNew->Lface. Otherwise, two disjoint 0502 * loops are merged into one, and the loop eDst->Lface is destroyed. 0503 * 0504 * If (eOrg == eDst), the new face will have only two edges. 0505 * If (eOrg->Lnext == eDst), the old face is reduced to a single edge. 0506 * If (eOrg->Lnext->Lnext == eDst), the old face is reduced to two edges. 0507 */ 0508 GLUhalfEdge *__gl_meshConnect(GLUhalfEdge *eOrg, GLUhalfEdge *eDst) 0509 { 0510 GLUhalfEdge *eNewSym; 0511 int joiningLoops = FALSE; 0512 GLUhalfEdge *eNew = MakeEdge(eOrg); 0513 if (eNew == NULL) 0514 return NULL; 0515 0516 eNewSym = eNew->Sym; 0517 0518 if (eDst->Lface != eOrg->Lface) 0519 { 0520 /* We are connecting two disjoint loops -- destroy eDst->Lface */ 0521 joiningLoops = TRUE; 0522 KillFace(eDst->Lface, eOrg->Lface); 0523 } 0524 0525 /* Connect the new edge appropriately */ 0526 Splice(eNew, eOrg->Lnext); 0527 Splice(eNewSym, eDst); 0528 0529 /* Set the vertex and face information */ 0530 eNew->Org = eOrg->Dst; 0531 eNewSym->Org = eDst->Org; 0532 eNew->Lface = eNewSym->Lface = eOrg->Lface; 0533 0534 /* Make sure the old face points to a valid half-edge */ 0535 eOrg->Lface->anEdge = eNewSym; 0536 0537 if (!joiningLoops) 0538 { 0539 GLUface *newFace = allocFace(); 0540 if (newFace == NULL) 0541 return NULL; 0542 0543 /* We split one loop into two -- the new loop is eNew->Lface */ 0544 MakeFace(newFace, eNew, eOrg->Lface); 0545 } 0546 return eNew; 0547 } 0548 0549 /******************** Other Operations **********************/ 0550 0551 /* __gl_meshZapFace( fZap ) destroys a face and removes it from the 0552 * global face list. All edges of fZap will have a NULL pointer as their 0553 * left face. Any edges which also have a NULL pointer as their right face 0554 * are deleted entirely (along with any isolated vertices this produces). 0555 * An entire mesh can be deleted by zapping its faces, one at a time, 0556 * in any order. Zapped faces cannot be used in further mesh operations! 0557 */ 0558 void __gl_meshZapFace(GLUface *fZap) 0559 { 0560 GLUhalfEdge *eStart = fZap->anEdge; 0561 GLUhalfEdge *e, *eNext, *eSym; 0562 GLUface *fPrev, *fNext; 0563 0564 /* walk around face, deleting edges whose right face is also NULL */ 0565 eNext = eStart->Lnext; 0566 do 0567 { 0568 e = eNext; 0569 eNext = e->Lnext; 0570 0571 e->Lface = NULL; 0572 if (e->Rface == NULL) 0573 { 0574 /* delete the edge -- see __gl_MeshDelete above */ 0575 0576 if (e->Onext == e) 0577 { 0578 KillVertex(e->Org, NULL); 0579 } 0580 else 0581 { 0582 /* Make sure that e->Org points to a valid half-edge */ 0583 e->Org->anEdge = e->Onext; 0584 Splice(e, e->Oprev); 0585 } 0586 eSym = e->Sym; 0587 if (eSym->Onext == eSym) 0588 { 0589 KillVertex(eSym->Org, NULL); 0590 } 0591 else 0592 { 0593 /* Make sure that eSym->Org points to a valid half-edge */ 0594 eSym->Org->anEdge = eSym->Onext; 0595 Splice(eSym, eSym->Oprev); 0596 } 0597 KillEdge(e); 0598 } 0599 } while (e != eStart); 0600 0601 /* delete from circular doubly-linked list */ 0602 fPrev = fZap->prev; 0603 fNext = fZap->next; 0604 fNext->prev = fPrev; 0605 fPrev->next = fNext; 0606 0607 memFree(fZap); 0608 } 0609 0610 /* __gl_meshNewMesh() creates a new mesh with no edges, no vertices, 0611 * and no loops (what we usually call a "face"). 0612 */ 0613 GLUmesh *__gl_meshNewMesh(void) 0614 { 0615 GLUvertex *v; 0616 GLUface *f; 0617 GLUhalfEdge *e; 0618 GLUhalfEdge *eSym; 0619 GLUmesh *mesh = (GLUmesh *)memAlloc(sizeof(GLUmesh)); 0620 if (mesh == NULL) 0621 { 0622 return NULL; 0623 } 0624 0625 v = &mesh->vHead; 0626 f = &mesh->fHead; 0627 e = &mesh->eHead; 0628 eSym = &mesh->eHeadSym; 0629 0630 v->next = v->prev = v; 0631 v->anEdge = NULL; 0632 v->data = NULL; 0633 0634 f->next = f->prev = f; 0635 f->anEdge = NULL; 0636 f->data = NULL; 0637 f->trail = NULL; 0638 f->marked = FALSE; 0639 f->inside = FALSE; 0640 0641 e->next = e; 0642 e->Sym = eSym; 0643 e->Onext = NULL; 0644 e->Lnext = NULL; 0645 e->Org = NULL; 0646 e->Lface = NULL; 0647 e->winding = 0; 0648 e->activeRegion = NULL; 0649 0650 eSym->next = eSym; 0651 eSym->Sym = e; 0652 eSym->Onext = NULL; 0653 eSym->Lnext = NULL; 0654 eSym->Org = NULL; 0655 eSym->Lface = NULL; 0656 eSym->winding = 0; 0657 eSym->activeRegion = NULL; 0658 0659 return mesh; 0660 } 0661 0662 /* __gl_meshUnion( mesh1, mesh2 ) forms the union of all structures in 0663 * both meshes, and returns the new mesh (the old meshes are destroyed). 0664 */ 0665 GLUmesh *__gl_meshUnion(GLUmesh *mesh1, GLUmesh *mesh2) 0666 { 0667 GLUface *f1 = &mesh1->fHead; 0668 GLUvertex *v1 = &mesh1->vHead; 0669 GLUhalfEdge *e1 = &mesh1->eHead; 0670 GLUface *f2 = &mesh2->fHead; 0671 GLUvertex *v2 = &mesh2->vHead; 0672 GLUhalfEdge *e2 = &mesh2->eHead; 0673 0674 /* Add the faces, vertices, and edges of mesh2 to those of mesh1 */ 0675 if (f2->next != f2) 0676 { 0677 f1->prev->next = f2->next; 0678 f2->next->prev = f1->prev; 0679 f2->prev->next = f1; 0680 f1->prev = f2->prev; 0681 } 0682 0683 if (v2->next != v2) 0684 { 0685 v1->prev->next = v2->next; 0686 v2->next->prev = v1->prev; 0687 v2->prev->next = v1; 0688 v1->prev = v2->prev; 0689 } 0690 0691 if (e2->next != e2) 0692 { 0693 e1->Sym->next->Sym->next = e2->next; 0694 e2->next->Sym->next = e1->Sym->next; 0695 e2->Sym->next->Sym->next = e1; 0696 e1->Sym->next = e2->Sym->next; 0697 } 0698 0699 memFree(mesh2); 0700 return mesh1; 0701 } 0702 0703 #ifdef DELETE_BY_ZAPPING 0704 0705 /* __gl_meshDeleteMesh( mesh ) will free all storage for any valid mesh. 0706 */ 0707 void __gl_meshDeleteMesh(GLUmesh *mesh) 0708 { 0709 GLUface *fHead = &mesh->fHead; 0710 0711 while (fHead->next != fHead) 0712 { 0713 __gl_meshZapFace(fHead->next); 0714 } 0715 assert(mesh->vHead.next == &mesh->vHead); 0716 0717 memFree(mesh); 0718 } 0719 0720 #else 0721 0722 /* __gl_meshDeleteMesh( mesh ) will free all storage for any valid mesh. 0723 */ 0724 void __gl_meshDeleteMesh(GLUmesh *mesh) 0725 { 0726 GLUface *f, *fNext; 0727 GLUvertex *v, *vNext; 0728 GLUhalfEdge *e, *eNext; 0729 0730 for (f = mesh->fHead.next; f != &mesh->fHead; f = fNext) 0731 { 0732 fNext = f->next; 0733 memFree(f); 0734 } 0735 0736 for (v = mesh->vHead.next; v != &mesh->vHead; v = vNext) 0737 { 0738 vNext = v->next; 0739 memFree(v); 0740 } 0741 0742 for (e = mesh->eHead.next; e != &mesh->eHead; e = eNext) 0743 { 0744 /* One call frees both e and e->Sym (see EdgePair above) */ 0745 eNext = e->next; 0746 memFree(e); 0747 } 0748 0749 memFree(mesh); 0750 } 0751 0752 #endif 0753 0754 #ifndef NDEBUG 0755 0756 /* __gl_meshCheckMesh( mesh ) checks a mesh for self-consistency. 0757 */ 0758 void __gl_meshCheckMesh(GLUmesh *mesh) 0759 { 0760 GLUface *fHead = &mesh->fHead; 0761 GLUvertex *vHead = &mesh->vHead; 0762 GLUhalfEdge *eHead = &mesh->eHead; 0763 GLUface *f, *fPrev; 0764 GLUvertex *v, *vPrev; 0765 GLUhalfEdge *e, *ePrev; 0766 0767 fPrev = fHead; 0768 for (fPrev = fHead; (f = fPrev->next) != fHead; fPrev = f) 0769 { 0770 assert(f->prev == fPrev); 0771 e = f->anEdge; 0772 do 0773 { 0774 assert(e->Sym != e); 0775 assert(e->Sym->Sym == e); 0776 assert(e->Lnext->Onext->Sym == e); 0777 assert(e->Onext->Sym->Lnext == e); 0778 assert(e->Lface == f); 0779 e = e->Lnext; 0780 } while (e != f->anEdge); 0781 } 0782 assert(f->prev == fPrev && f->anEdge == NULL && f->data == NULL); 0783 0784 vPrev = vHead; 0785 for (vPrev = vHead; (v = vPrev->next) != vHead; vPrev = v) 0786 { 0787 assert(v->prev == vPrev); 0788 e = v->anEdge; 0789 do 0790 { 0791 assert(e->Sym != e); 0792 assert(e->Sym->Sym == e); 0793 assert(e->Lnext->Onext->Sym == e); 0794 assert(e->Onext->Sym->Lnext == e); 0795 assert(e->Org == v); 0796 e = e->Onext; 0797 } while (e != v->anEdge); 0798 } 0799 assert(v->prev == vPrev && v->anEdge == NULL && v->data == NULL); 0800 0801 ePrev = eHead; 0802 for (ePrev = eHead; (e = ePrev->next) != eHead; ePrev = e) 0803 { 0804 assert(e->Sym->next == ePrev->Sym); 0805 assert(e->Sym != e); 0806 assert(e->Sym->Sym == e); 0807 assert(e->Org != NULL); 0808 assert(e->Dst != NULL); 0809 assert(e->Lnext->Onext->Sym == e); 0810 assert(e->Onext->Sym->Lnext == e); 0811 } 0812 assert(e->Sym->next == ePrev->Sym && e->Sym == &mesh->eHeadSym && e->Sym->Sym == e && e->Org == NULL && 0813 e->Dst == NULL && e->Lface == NULL && e->Rface == NULL); 0814 } 0815 0816 #endif