src/glu/sgi/libtess/mesh.c

   1 /*
   2  * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008)
   3  * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved.
   4  *
   5  * Permission is hereby granted, free of charge, to any person obtaining a
   6  * copy of this software and associated documentation files (the "Software"),
   7  * to deal in the Software without restriction, including without limitation
   8  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   9  * and/or sell copies of the Software, and to permit persons to whom the
  10  * Software is furnished to do so, subject to the following conditions:
  11  *
  12  * The above copyright notice including the dates of first publication and
  13  * either this permission notice or a reference to
  14  * http://oss.sgi.com/projects/FreeB/
  15  * shall be included in all copies or substantial portions of the Software.
  16  *
  17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  18  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
  20  * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
  21  * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
  22  * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  23  * SOFTWARE.
  24  *
  25  * Except as contained in this notice, the name of Silicon Graphics, Inc.
  26  * shall not be used in advertising or otherwise to promote the sale, use or
  27  * other dealings in this Software without prior written authorization from
  28  * Silicon Graphics, Inc.
  29  */
  30 /*
  31 ** Author: Eric Veach, July 1994.
  32 **
  33 */
  34
  35 #include "gluos.h"
  36 #include <stddef.h>
  37 #include <assert.h>
  38 #include "mesh.h"
  39 #include "memalloc.h"
  40
  41 #ifndef TRUE
  42 #define TRUE 1
  43 #endif
  44 #ifndef FALSE
  45 #define FALSE 0
  46 #endif
  47
  48 static GLUvertex *allocVertex()
  49 {
  50    return (GLUvertex *)memAlloc( sizeof( GLUvertex ));
  51 }
  52
  53 static GLUface *allocFace()
  54 {
  55    return (GLUface *)memAlloc( sizeof( GLUface ));
  56 }
  57
  58 /************************ Utility Routines ************************/
  59
  60 /* Allocate and free half-edges in pairs for efficiency.
  61  * The *only* place that should use this fact is allocation/free.
  62  */
  63 typedef struct { GLUhalfEdge e, eSym; } EdgePair;
  64
  65 /* MakeEdge creates a new pair of half-edges which form their own loop.
  66  * No vertex or face structures are allocated, but these must be assigned
  67  * before the current edge operation is completed.
  68  */
  69 static GLUhalfEdge *MakeEdge( GLUhalfEdge *eNext )
  70 {
  71   GLUhalfEdge *e;
  72   GLUhalfEdge *eSym;
  73   GLUhalfEdge *ePrev;
  74   EdgePair *pair = (EdgePair *)memAlloc( sizeof( EdgePair ));
  75   if (pair == NULL) return NULL;
  76
  77   e = &pair->e;
  78   eSym = &pair->eSym;
  79
  80   /* Make sure eNext points to the first edge of the edge pair */
  81   if( eNext->Sym < eNext ) { eNext = eNext->Sym; }
  82
  83   /* Insert in circular doubly-linked list before eNext.
  84    * Note that the prev pointer is stored in Sym->next.
  85    */
  86   ePrev = eNext->Sym->next;
  87   eSym->next = ePrev;
  88   ePrev->Sym->next = e;
  89   e->next = eNext;
  90   eNext->Sym->next = eSym;
  91
  92   e->Sym = eSym;
  93   e->Onext = e;
  94   e->Lnext = eSym;
  95   e->Org = NULL;
  96   e->Lface = NULL;
  97   e->winding = 0;
  98   e->activeRegion = NULL;
  99
 100   eSym->Sym = e;
 101   eSym->Onext = eSym;
 102   eSym->Lnext = e;
 103   eSym->Org = NULL;
 104   eSym->Lface = NULL;
 105   eSym->winding = 0;
 106   eSym->activeRegion = NULL;
 107
 108   return e;
 109 }
 110
 111 /* Splice( a, b ) is best described by the Guibas/Stolfi paper or the
 112  * CS348a notes (see mesh.h).  Basically it modifies the mesh so that
 113  * a->Onext and b->Onext are exchanged.  This can have various effects
 114  * depending on whether a and b belong to different face or vertex rings.
 115  * For more explanation see __gl_meshSplice() below.
 116  */
 117 static void Splice( GLUhalfEdge *a, GLUhalfEdge *b )
 118 {
 119   GLUhalfEdge *aOnext = a->Onext;
 120   GLUhalfEdge *bOnext = b->Onext;
 121
 122   aOnext->Sym->Lnext = b;
 123   bOnext->Sym->Lnext = a;
 124   a->Onext = bOnext;
 125   b->Onext = aOnext;
 126 }
 127
 128 /* MakeVertex( newVertex, eOrig, vNext ) attaches a new vertex and makes it the
 129  * origin of all edges in the vertex loop to which eOrig belongs. "vNext" gives
 130  * a place to insert the new vertex in the global vertex list.  We insert
 131  * the new vertex *before* vNext so that algorithms which walk the vertex
 132  * list will not see the newly created vertices.
 133  */
 134 static void MakeVertex( GLUvertex *newVertex,
 135                         GLUhalfEdge *eOrig, GLUvertex *vNext )
 136 {
 137   GLUhalfEdge *e;
 138   GLUvertex *vPrev;
 139   GLUvertex *vNew = newVertex;
 140
 141   assert(vNew != NULL);
 142
 143   /* insert in circular doubly-linked list before vNext */
 144   vPrev = vNext->prev;
 145   vNew->prev = vPrev;
 146   vPrev->next = vNew;
 147   vNew->next = vNext;
 148   vNext->prev = vNew;
 149
 150   vNew->anEdge = eOrig;
 151   vNew->data = NULL;
 152   /* leave coords, s, t undefined */
 153
 154   /* fix other edges on this vertex loop */
 155   e = eOrig;
 156   do {
 157     e->Org = vNew;
 158     e = e->Onext;
 159   } while( e != eOrig );
 160 }
 161
 162 /* MakeFace( newFace, eOrig, fNext ) attaches a new face and makes it the left
 163  * face of all edges in the face loop to which eOrig belongs.  "fNext" gives
 164  * a place to insert the new face in the global face list.  We insert
 165  * the new face *before* fNext so that algorithms which walk the face
 166  * list will not see the newly created faces.
 167  */
 168 static void MakeFace( GLUface *newFace, GLUhalfEdge *eOrig, GLUface *fNext )
 169 {
 170   GLUhalfEdge *e;
 171   GLUface *fPrev;
 172   GLUface *fNew = newFace;
 173
 174   assert(fNew != NULL);
 175
 176   /* insert in circular doubly-linked list before fNext */
 177   fPrev = fNext->prev;
 178   fNew->prev = fPrev;
 179   fPrev->next = fNew;
 180   fNew->next = fNext;
 181   fNext->prev = fNew;
 182
 183   fNew->anEdge = eOrig;
 184   fNew->data = NULL;
 185   fNew->trail = NULL;
 186   fNew->marked = FALSE;
 187
 188   /* The new face is marked "inside" if the old one was.  This is a
 189    * convenience for the common case where a face has been split in two.
 190    */
 191   fNew->inside = fNext->inside;
 192
 193   /* fix other edges on this face loop */
 194   e = eOrig;
 195   do {
 196     e->Lface = fNew;
 197     e = e->Lnext;
 198   } while( e != eOrig );
 199 }
 200
 201 /* KillEdge( eDel ) destroys an edge (the half-edges eDel and eDel->Sym),
 202  * and removes from the global edge list.
 203  */
 204 static void KillEdge( GLUhalfEdge *eDel )
 205 {
 206   GLUhalfEdge *ePrev, *eNext;
 207
 208   /* Half-edges are allocated in pairs, see EdgePair above */
 209   if( eDel->Sym < eDel ) { eDel = eDel->Sym; }
 210
 211   /* delete from circular doubly-linked list */
 212   eNext = eDel->next;
 213   ePrev = eDel->Sym->next;
 214   eNext->Sym->next = ePrev;
 215   ePrev->Sym->next = eNext;
 216
 217   memFree( eDel );
 218 }
 219
 220
 221 /* KillVertex( vDel ) destroys a vertex and removes it from the global
 222  * vertex list.  It updates the vertex loop to point to a given new vertex.
 223  */
 224 static void KillVertex( GLUvertex *vDel, GLUvertex *newOrg )
 225 {
 226   GLUhalfEdge *e, *eStart = vDel->anEdge;
 227   GLUvertex *vPrev, *vNext;
 228
 229   /* change the origin of all affected edges */
 230   e = eStart;
 231   do {
 232     e->Org = newOrg;
 233     e = e->Onext;
 234   } while( e != eStart );
 235
 236   /* delete from circular doubly-linked list */
 237   vPrev = vDel->prev;
 238   vNext = vDel->next;
 239   vNext->prev = vPrev;
 240   vPrev->next = vNext;
 241
 242   memFree( vDel );
 243 }
 244
 245 /* KillFace( fDel ) destroys a face and removes it from the global face
 246  * list.  It updates the face loop to point to a given new face.
 247  */
 248 static void KillFace( GLUface *fDel, GLUface *newLface )
 249 {
 250   GLUhalfEdge *e, *eStart = fDel->anEdge;
 251   GLUface *fPrev, *fNext;
 252
 253   /* change the left face of all affected edges */
 254   e = eStart;
 255   do {
 256     e->Lface = newLface;
 257     e = e->Lnext;
 258   } while( e != eStart );
 259
 260   /* delete from circular doubly-linked list */
 261   fPrev = fDel->prev;
 262   fNext = fDel->next;
 263   fNext->prev = fPrev;
 264   fPrev->next = fNext;
 265
 266   memFree( fDel );
 267 }
 268
 269
 270 /****************** Basic Edge Operations **********************/
 271
 272 /* __gl_meshMakeEdge creates one edge, two vertices, and a loop (face).
 273  * The loop consists of the two new half-edges.
 274  */
 275 GLUhalfEdge *__gl_meshMakeEdge( GLUmesh *mesh )
 276 {
 277   GLUvertex *newVertex1= allocVertex();
 278   GLUvertex *newVertex2= allocVertex();
 279   GLUface *newFace= allocFace();
 280   GLUhalfEdge *e;
 281
 282   /* if any one is null then all get freed */
 283   if (newVertex1 == NULL || newVertex2 == NULL || newFace == NULL) {
 284      if (newVertex1 != NULL) memFree(newVertex1);
 285      if (newVertex2 != NULL) memFree(newVertex2);
 286      if (newFace != NULL) memFree(newFace);
 287      return NULL;
 288   }
 289
 290   e = MakeEdge( &mesh->eHead );
 291   if (e == NULL) {
 292      memFree(newVertex1);
 293      memFree(newVertex2);
 294      memFree(newFace);
 295      return NULL;
 296   }
 297
 298   MakeVertex( newVertex1, e, &mesh->vHead );
 299   MakeVertex( newVertex2, e->Sym, &mesh->vHead );
 300   MakeFace( newFace, e, &mesh->fHead );
 301   return e;
 302 }
 303
 304
 305 /* __gl_meshSplice( eOrg, eDst ) is the basic operation for changing the
 306  * mesh connectivity and topology.  It changes the mesh so that
 307  *      eOrg->Onext <- OLD( eDst->Onext )
 308  *      eDst->Onext <- OLD( eOrg->Onext )
 309  * where OLD(...) means the value before the meshSplice operation.
 310  *
 311  * This can have two effects on the vertex structure:
 312  *  - if eOrg->Org != eDst->Org, the two vertices are merged together
 313  *  - if eOrg->Org == eDst->Org, the origin is split into two vertices
 314  * In both cases, eDst->Org is changed and eOrg->Org is untouched.
 315  *
 316  * Similarly (and independently) for the face structure,
 317  *  - if eOrg->Lface == eDst->Lface, one loop is split into two
 318  *  - if eOrg->Lface != eDst->Lface, two distinct loops are joined into one
 319  * In both cases, eDst->Lface is changed and eOrg->Lface is unaffected.
 320  *
 321  * Some special cases:
 322  * If eDst == eOrg, the operation has no effect.
 323  * If eDst == eOrg->Lnext, the new face will have a single edge.
 324  * If eDst == eOrg->Lprev, the old face will have a single edge.
 325  * If eDst == eOrg->Onext, the new vertex will have a single edge.
 326  * If eDst == eOrg->Oprev, the old vertex will have a single edge.
 327  */
 328 int __gl_meshSplice( GLUhalfEdge *eOrg, GLUhalfEdge *eDst )
 329 {
 330   int joiningLoops = FALSE;
 331   int joiningVertices = FALSE;
 332
 333   if( eOrg == eDst ) return 1;
 334
 335   if( eDst->Org != eOrg->Org ) {
 336     /* We are merging two disjoint vertices -- destroy eDst->Org */
 337     joiningVertices = TRUE;
 338     KillVertex( eDst->Org, eOrg->Org );
 339   }
 340   if( eDst->Lface != eOrg->Lface ) {
 341     /* We are connecting two disjoint loops -- destroy eDst->Lface */
 342     joiningLoops = TRUE;
 343     KillFace( eDst->Lface, eOrg->Lface );
 344   }
 345
 346   /* Change the edge structure */
 347   Splice( eDst, eOrg );
 348
 349   if( ! joiningVertices ) {
 350     GLUvertex *newVertex= allocVertex();
 351     if (newVertex == NULL) return 0;
 352
 353     /* We split one vertex into two -- the new vertex is eDst->Org.
 354      * Make sure the old vertex points to a valid half-edge.
 355      */
 356     MakeVertex( newVertex, eDst, eOrg->Org );
 357     eOrg->Org->anEdge = eOrg;
 358   }
 359   if( ! joiningLoops ) {
 360     GLUface *newFace= allocFace();
 361     if (newFace == NULL) return 0;
 362
 363     /* We split one loop into two -- the new loop is eDst->Lface.
 364      * Make sure the old face points to a valid half-edge.
 365      */
 366     MakeFace( newFace, eDst, eOrg->Lface );
 367     eOrg->Lface->anEdge = eOrg;
 368   }
 369
 370   return 1;
 371 }
 372
 373
 374 /* __gl_meshDelete( eDel ) removes the edge eDel.  There are several cases:
 375  * if (eDel->Lface != eDel->Rface), we join two loops into one; the loop
 376  * eDel->Lface is deleted.  Otherwise, we are splitting one loop into two;
 377  * the newly created loop will contain eDel->Dst.  If the deletion of eDel
 378  * would create isolated vertices, those are deleted as well.
 379  *
 380  * This function could be implemented as two calls to __gl_meshSplice
 381  * plus a few calls to memFree, but this would allocate and delete
 382  * unnecessary vertices and faces.
 383  */
 384 int __gl_meshDelete( GLUhalfEdge *eDel )
 385 {
 386   GLUhalfEdge *eDelSym = eDel->Sym;
 387   int joiningLoops = FALSE;
 388
 389   /* First step: disconnect the origin vertex eDel->Org.  We make all
 390    * changes to get a consistent mesh in this "intermediate" state.
 391    */
 392   if( eDel->Lface != eDel->Rface ) {
 393     /* We are joining two loops into one -- remove the left face */
 394     joiningLoops = TRUE;
 395     KillFace( eDel->Lface, eDel->Rface );
 396   }
 397
 398   if( eDel->Onext == eDel ) {
 399     KillVertex( eDel->Org, NULL );
 400   } else {
 401     /* Make sure that eDel->Org and eDel->Rface point to valid half-edges */
 402     eDel->Rface->anEdge = eDel->Oprev;
 403     eDel->Org->anEdge = eDel->Onext;
 404
 405     Splice( eDel, eDel->Oprev );
 406     if( ! joiningLoops ) {
 407       GLUface *newFace= allocFace();
 408       if (newFace == NULL) return 0;
 409
 410       /* We are splitting one loop into two -- create a new loop for eDel. */
 411       MakeFace( newFace, eDel, eDel->Lface );
 412     }
 413   }
 414
 415   /* Claim: the mesh is now in a consistent state, except that eDel->Org
 416    * may have been deleted.  Now we disconnect eDel->Dst.
 417    */
 418   if( eDelSym->Onext == eDelSym ) {
 419     KillVertex( eDelSym->Org, NULL );
 420     KillFace( eDelSym->Lface, NULL );
 421   } else {
 422     /* Make sure that eDel->Dst and eDel->Lface point to valid half-edges */
 423     eDel->Lface->anEdge = eDelSym->Oprev;
 424     eDelSym->Org->anEdge = eDelSym->Onext;
 425     Splice( eDelSym, eDelSym->Oprev );
 426   }
 427
 428   /* Any isolated vertices or faces have already been freed. */
 429   KillEdge( eDel );
 430
 431   return 1;
 432 }
 433
 434
 435 /******************** Other Edge Operations **********************/
 436
 437 /* All these routines can be implemented with the basic edge
 438  * operations above.  They are provided for convenience and efficiency.
 439  */
 440
 441
 442 /* __gl_meshAddEdgeVertex( eOrg ) creates a new edge eNew such that
 443  * eNew == eOrg->Lnext, and eNew->Dst is a newly created vertex.
 444  * eOrg and eNew will have the same left face.
 445  */
 446 GLUhalfEdge *__gl_meshAddEdgeVertex( GLUhalfEdge *eOrg )
 447 {
 448   GLUhalfEdge *eNewSym;
 449   GLUhalfEdge *eNew = MakeEdge( eOrg );
 450   if (eNew == NULL) return NULL;
 451
 452   eNewSym = eNew->Sym;
 453
 454   /* Connect the new edge appropriately */
 455   Splice( eNew, eOrg->Lnext );
 456
 457   /* Set the vertex and face information */
 458   eNew->Org = eOrg->Dst;
 459   {
 460     GLUvertex *newVertex= allocVertex();
 461     if (newVertex == NULL) return NULL;
 462
 463     MakeVertex( newVertex, eNewSym, eNew->Org );
 464   }
 465   eNew->Lface = eNewSym->Lface = eOrg->Lface;
 466
 467   return eNew;
 468 }
 469
 470
 471 /* __gl_meshSplitEdge( eOrg ) splits eOrg into two edges eOrg and eNew,
 472  * such that eNew == eOrg->Lnext.  The new vertex is eOrg->Dst == eNew->Org.
 473  * eOrg and eNew will have the same left face.
 474  */
 475 GLUhalfEdge *__gl_meshSplitEdge( GLUhalfEdge *eOrg )
 476 {
 477   GLUhalfEdge *eNew;
 478   GLUhalfEdge *tempHalfEdge= __gl_meshAddEdgeVertex( eOrg );
 479   if (tempHalfEdge == NULL) return NULL;
 480
 481   eNew = tempHalfEdge->Sym;
 482
 483   /* Disconnect eOrg from eOrg->Dst and connect it to eNew->Org */
 484   Splice( eOrg->Sym, eOrg->Sym->Oprev );
 485   Splice( eOrg->Sym, eNew );
 486
 487   /* Set the vertex and face information */
 488   eOrg->Dst = eNew->Org;
 489   eNew->Dst->anEdge = eNew->Sym;        /* may have pointed to eOrg->Sym */
 490   eNew->Rface = eOrg->Rface;
 491   eNew->winding = eOrg->winding;        /* copy old winding information */
 492   eNew->Sym->winding = eOrg->Sym->winding;
 493
 494   return eNew;
 495 }
 496
 497
 498 /* __gl_meshConnect( eOrg, eDst ) creates a new edge from eOrg->Dst
 499  * to eDst->Org, and returns the corresponding half-edge eNew.
 500  * If eOrg->Lface == eDst->Lface, this splits one loop into two,
 501  * and the newly created loop is eNew->Lface.  Otherwise, two disjoint
 502  * loops are merged into one, and the loop eDst->Lface is destroyed.
 503  *
 504  * If (eOrg == eDst), the new face will have only two edges.
 505  * If (eOrg->Lnext == eDst), the old face is reduced to a single edge.
 506  * If (eOrg->Lnext->Lnext == eDst), the old face is reduced to two edges.
 507  */
 508 GLUhalfEdge *__gl_meshConnect( GLUhalfEdge *eOrg, GLUhalfEdge *eDst )
 509 {
 510   GLUhalfEdge *eNewSym;
 511   int joiningLoops = FALSE;
 512   GLUhalfEdge *eNew = MakeEdge( eOrg );
 513   if (eNew == NULL) return NULL;
 514
 515   eNewSym = eNew->Sym;
 516
 517   if( eDst->Lface != eOrg->Lface ) {
 518     /* We are connecting two disjoint loops -- destroy eDst->Lface */
 519     joiningLoops = TRUE;
 520     KillFace( eDst->Lface, eOrg->Lface );
 521   }
 522
 523   /* Connect the new edge appropriately */
 524   Splice( eNew, eOrg->Lnext );
 525   Splice( eNewSym, eDst );
 526
 527   /* Set the vertex and face information */
 528   eNew->Org = eOrg->Dst;
 529   eNewSym->Org = eDst->Org;
 530   eNew->Lface = eNewSym->Lface = eOrg->Lface;
 531
 532   /* Make sure the old face points to a valid half-edge */
 533   eOrg->Lface->anEdge = eNewSym;
 534
 535   if( ! joiningLoops ) {
 536     GLUface *newFace= allocFace();
 537     if (newFace == NULL) return NULL;
 538
 539     /* We split one loop into two -- the new loop is eNew->Lface */
 540     MakeFace( newFace, eNew, eOrg->Lface );
 541   }
 542   return eNew;
 543 }
 544
 545
 546 /******************** Other Operations **********************/
 547
 548 /* __gl_meshZapFace( fZap ) destroys a face and removes it from the
 549  * global face list.  All edges of fZap will have a NULL pointer as their
 550  * left face.  Any edges which also have a NULL pointer as their right face
 551  * are deleted entirely (along with any isolated vertices this produces).
 552  * An entire mesh can be deleted by zapping its faces, one at a time,
 553  * in any order.  Zapped faces cannot be used in further mesh operations!
 554  */
 555 void __gl_meshZapFace( GLUface *fZap )
 556 {
 557   GLUhalfEdge *eStart = fZap->anEdge;
 558   GLUhalfEdge *e, *eNext, *eSym;
 559   GLUface *fPrev, *fNext;
 560
 561   /* walk around face, deleting edges whose right face is also NULL */
 562   eNext = eStart->Lnext;
 563   do {
 564     e = eNext;
 565     eNext = e->Lnext;
 566
 567     e->Lface = NULL;
 568     if( e->Rface == NULL ) {
 569       /* delete the edge -- see __gl_MeshDelete above */
 570
 571       if( e->Onext == e ) {
 572         KillVertex( e->Org, NULL );
 573       } else {
 574         /* Make sure that e->Org points to a valid half-edge */
 575         e->Org->anEdge = e->Onext;
 576         Splice( e, e->Oprev );
 577       }
 578       eSym = e->Sym;
 579       if( eSym->Onext == eSym ) {
 580         KillVertex( eSym->Org, NULL );
 581       } else {
 582         /* Make sure that eSym->Org points to a valid half-edge */
 583         eSym->Org->anEdge = eSym->Onext;
 584         Splice( eSym, eSym->Oprev );
 585       }
 586       KillEdge( e );
 587     }
 588   } while( e != eStart );
 589
 590   /* delete from circular doubly-linked list */
 591   fPrev = fZap->prev;
 592   fNext = fZap->next;
 593   fNext->prev = fPrev;
 594   fPrev->next = fNext;
 595
 596   memFree( fZap );
 597 }
 598
 599
 600 /* __gl_meshNewMesh() creates a new mesh with no edges, no vertices,
 601  * and no loops (what we usually call a "face").
 602  */
 603 GLUmesh *__gl_meshNewMesh( void )
 604 {
 605   GLUvertex *v;
 606   GLUface *f;
 607   GLUhalfEdge *e;
 608   GLUhalfEdge *eSym;
 609   GLUmesh *mesh = (GLUmesh *)memAlloc( sizeof( GLUmesh ));
 610   if (mesh == NULL) {
 611      return NULL;
 612   }
 613
 614   v = &mesh->vHead;
 615   f = &mesh->fHead;
 616   e = &mesh->eHead;
 617   eSym = &mesh->eHeadSym;
 618
 619   v->next = v->prev = v;
 620   v->anEdge = NULL;
 621   v->data = NULL;
 622
 623   f->next = f->prev = f;
 624   f->anEdge = NULL;
 625   f->data = NULL;
 626   f->trail = NULL;
 627   f->marked = FALSE;
 628   f->inside = FALSE;
 629
 630   e->next = e;
 631   e->Sym = eSym;
 632   e->Onext = NULL;
 633   e->Lnext = NULL;
 634   e->Org = NULL;
 635   e->Lface = NULL;
 636   e->winding = 0;
 637   e->activeRegion = NULL;
 638
 639   eSym->next = eSym;
 640   eSym->Sym = e;
 641   eSym->Onext = NULL;
 642   eSym->Lnext = NULL;
 643   eSym->Org = NULL;
 644   eSym->Lface = NULL;
 645   eSym->winding = 0;
 646   eSym->activeRegion = NULL;
 647
 648   return mesh;
 649 }
 650
 651
 652 /* __gl_meshUnion( mesh1, mesh2 ) forms the union of all structures in
 653  * both meshes, and returns the new mesh (the old meshes are destroyed).
 654  */
 655 GLUmesh *__gl_meshUnion( GLUmesh *mesh1, GLUmesh *mesh2 )
 656 {
 657   GLUface *f1 = &mesh1->fHead;
 658   GLUvertex *v1 = &mesh1->vHead;
 659   GLUhalfEdge *e1 = &mesh1->eHead;
 660   GLUface *f2 = &mesh2->fHead;
 661   GLUvertex *v2 = &mesh2->vHead;
 662   GLUhalfEdge *e2 = &mesh2->eHead;
 663
 664   /* Add the faces, vertices, and edges of mesh2 to those of mesh1 */
 665   if( f2->next != f2 ) {
 666     f1->prev->next = f2->next;
 667     f2->next->prev = f1->prev;
 668     f2->prev->next = f1;
 669     f1->prev = f2->prev;
 670   }
 671
 672   if( v2->next != v2 ) {
 673     v1->prev->next = v2->next;
 674     v2->next->prev = v1->prev;
 675     v2->prev->next = v1;
 676     v1->prev = v2->prev;
 677   }
 678
 679   if( e2->next != e2 ) {
 680     e1->Sym->next->Sym->next = e2->next;
 681     e2->next->Sym->next = e1->Sym->next;
 682     e2->Sym->next->Sym->next = e1;
 683     e1->Sym->next = e2->Sym->next;
 684   }
 685
 686   memFree( mesh2 );
 687   return mesh1;
 688 }
 689
 690
 691 #ifdef DELETE_BY_ZAPPING
 692
 693 /* __gl_meshDeleteMesh( mesh ) will free all storage for any valid mesh.
 694  */
 695 void __gl_meshDeleteMesh( GLUmesh *mesh )
 696 {
 697   GLUface *fHead = &mesh->fHead;
 698
 699   while( fHead->next != fHead ) {
 700     __gl_meshZapFace( fHead->next );
 701   }
 702   assert( mesh->vHead.next == &mesh->vHead );
 703
 704   memFree( mesh );
 705 }
 706
 707 #else
 708
 709 /* __gl_meshDeleteMesh( mesh ) will free all storage for any valid mesh.
 710  */
 711 void __gl_meshDeleteMesh( GLUmesh *mesh )
 712 {
 713   GLUface *f, *fNext;
 714   GLUvertex *v, *vNext;
 715   GLUhalfEdge *e, *eNext;
 716
 717   for( f = mesh->fHead.next; f != &mesh->fHead; f = fNext ) {
 718     fNext = f->next;
 719     memFree( f );
 720   }
 721
 722   for( v = mesh->vHead.next; v != &mesh->vHead; v = vNext ) {
 723     vNext = v->next;
 724     memFree( v );
 725   }
 726
 727   for( e = mesh->eHead.next; e != &mesh->eHead; e = eNext ) {
 728     /* One call frees both e and e->Sym (see EdgePair above) */
 729     eNext = e->next;
 730     memFree( e );
 731   }
 732
 733   memFree( mesh );
 734 }
 735
 736 #endif
 737
 738 #ifndef NDEBUG
 739
 740 /* __gl_meshCheckMesh( mesh ) checks a mesh for self-consistency.
 741  */
 742 void __gl_meshCheckMesh( GLUmesh *mesh )
 743 {
 744   GLUface *fHead = &mesh->fHead;
 745   GLUvertex *vHead = &mesh->vHead;
 746   GLUhalfEdge *eHead = &mesh->eHead;
 747   GLUface *f, *fPrev;
 748   GLUvertex *v, *vPrev;
 749   GLUhalfEdge *e, *ePrev;
 750
 751   fPrev = fHead;
 752   for( fPrev = fHead ; (f = fPrev->next) != fHead; fPrev = f) {
 753     assert( f->prev == fPrev );
 754     e = f->anEdge;
 755     do {
 756       assert( e->Sym != e );
 757       assert( e->Sym->Sym == e );
 758       assert( e->Lnext->Onext->Sym == e );
 759       assert( e->Onext->Sym->Lnext == e );
 760       assert( e->Lface == f );
 761       e = e->Lnext;
 762     } while( e != f->anEdge );
 763   }
 764   assert( f->prev == fPrev && f->anEdge == NULL && f->data == NULL );
 765
 766   vPrev = vHead;
 767   for( vPrev = vHead ; (v = vPrev->next) != vHead; vPrev = v) {
 768     assert( v->prev == vPrev );
 769     e = v->anEdge;
 770     do {
 771       assert( e->Sym != e );
 772       assert( e->Sym->Sym == e );
 773       assert( e->Lnext->Onext->Sym == e );
 774       assert( e->Onext->Sym->Lnext == e );
 775       assert( e->Org == v );
 776       e = e->Onext;
 777     } while( e != v->anEdge );
 778   }
 779   assert( v->prev == vPrev && v->anEdge == NULL && v->data == NULL );
 780
 781   ePrev = eHead;
 782   for( ePrev = eHead ; (e = ePrev->next) != eHead; ePrev = e) {
 783     assert( e->Sym->next == ePrev->Sym );
 784     assert( e->Sym != e );
 785     assert( e->Sym->Sym == e );
 786     assert( e->Org != NULL );
 787     assert( e->Dst != NULL );
 788     assert( e->Lnext->Onext->Sym == e );
 789     assert( e->Onext->Sym->Lnext == e );
 790   }
 791   assert( e->Sym->next == ePrev->Sym
 792        && e->Sym == &mesh->eHeadSym
 793        && e->Sym->Sym == e
 794        && e->Org == NULL && e->Dst == NULL
 795        && e->Lface == NULL && e->Rface == NULL );
 796 }
 797
 798 #endif