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