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