src/glu/sgi/libtess/mesh.c

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