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