dlls/glu32/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 <stdarg.h>
  36 #include <assert.h>
  37
  38 #include "windef.h"
  39 #include "winbase.h"
  40
  41 #include "tess.h"
  42
  43 static GLUvertex *allocVertex(void)
  44 {
  45     return HeapAlloc( GetProcessHeap(), 0, sizeof( GLUvertex ));
  46 }
  47
  48 static GLUface *allocFace(void)
  49 {
  50     return HeapAlloc( GetProcessHeap(), 0, sizeof( GLUface ));
  51 }
  52
  53 /************************ Utility Routines ************************/
  54
  55 /* Allocate and free half-edges in pairs for efficiency.
  56  * The *only* place that should use this fact is allocation/free.
  57  */
  58 typedef struct { GLUhalfEdge e, eSym; } EdgePair;
  59
  60 /* MakeEdge creates a new pair of half-edges which form their own loop.
  61  * No vertex or face structures are allocated, but these must be assigned
  62  * before the current edge operation is completed.
  63  */
  64 static GLUhalfEdge *MakeEdge( GLUhalfEdge *eNext )
  65 {
  66   GLUhalfEdge *e;
  67   GLUhalfEdge *eSym;
  68   GLUhalfEdge *ePrev;
  69   EdgePair *pair = HeapAlloc( GetProcessHeap(), 0, sizeof( EdgePair ));
  70   if (pair == NULL) return NULL;
  71
  72   e = &pair->e;
  73   eSym = &pair->eSym;
  74
  75   /* Make sure eNext points to the first edge of the edge pair */
  76   if( eNext->Sym < eNext ) { eNext = eNext->Sym; }
  77
  78   /* Insert in circular doubly-linked list before eNext.
  79    * Note that the prev pointer is stored in Sym->next.
  80    */
  81   ePrev = eNext->Sym->next;
  82   eSym->next = ePrev;
  83   ePrev->Sym->next = e;
  84   e->next = eNext;
  85   eNext->Sym->next = eSym;
  86
  87   e->Sym = eSym;
  88   e->Onext = e;
  89   e->Lnext = eSym;
  90   e->Org = NULL;
  91   e->Lface = NULL;
  92   e->winding = 0;
  93   e->activeRegion = NULL;
  94
  95   eSym->Sym = e;
  96   eSym->Onext = eSym;
  97   eSym->Lnext = e;
  98   eSym->Org = NULL;
  99   eSym->Lface = NULL;
 100   eSym->winding = 0;
 101   eSym->activeRegion = NULL;
 102
 103   return e;
 104 }
 105
 106 /* Splice( a, b ) is best described by the Guibas/Stolfi paper or the
 107  * CS348a notes (see mesh.h).  Basically it modifies the mesh so that
 108  * a->Onext and b->Onext are exchanged.  This can have various effects
 109  * depending on whether a and b belong to different face or vertex rings.
 110  * For more explanation see __gl_meshSplice() below.
 111  */
 112 static void Splice( GLUhalfEdge *a, GLUhalfEdge *b )
 113 {
 114   GLUhalfEdge *aOnext = a->Onext;
 115   GLUhalfEdge *bOnext = b->Onext;
 116
 117   aOnext->Sym->Lnext = b;
 118   bOnext->Sym->Lnext = a;
 119   a->Onext = bOnext;
 120   b->Onext = aOnext;
 121 }
 122
 123 /* MakeVertex( newVertex, eOrig, vNext ) attaches a new vertex and makes it the
 124  * origin of all edges in the vertex loop to which eOrig belongs. "vNext" gives
 125  * a place to insert the new vertex in the global vertex list.  We insert
 126  * the new vertex *before* vNext so that algorithms which walk the vertex
 127  * list will not see the newly created vertices.
 128  */
 129 static void MakeVertex( GLUvertex *newVertex,
 130                         GLUhalfEdge *eOrig, GLUvertex *vNext )
 131 {
 132   GLUhalfEdge *e;
 133   GLUvertex *vPrev;
 134   GLUvertex *vNew = newVertex;
 135
 136   assert(vNew != NULL);
 137
 138   /* insert in circular doubly-linked list before vNext */
 139   vPrev = vNext->prev;
 140   vNew->prev = vPrev;
 141   vPrev->next = vNew;
 142   vNew->next = vNext;
 143   vNext->prev = vNew;
 144
 145   vNew->anEdge = eOrig;
 146   vNew->data = NULL;
 147   /* leave coords, s, t undefined */
 148
 149   /* fix other edges on this vertex loop */
 150   e = eOrig;
 151   do {
 152     e->Org = vNew;
 153     e = e->Onext;
 154   } while( e != eOrig );
 155 }
 156
 157 /* MakeFace( newFace, eOrig, fNext ) attaches a new face and makes it the left
 158  * face of all edges in the face loop to which eOrig belongs.  "fNext" gives
 159  * a place to insert the new face in the global face list.  We insert
 160  * the new face *before* fNext so that algorithms which walk the face
 161  * list will not see the newly created faces.
 162  */
 163 static void MakeFace( GLUface *newFace, GLUhalfEdge *eOrig, GLUface *fNext )
 164 {
 165   GLUhalfEdge *e;
 166   GLUface *fPrev;
 167   GLUface *fNew = newFace;
 168
 169   assert(fNew != NULL);
 170
 171   /* insert in circular doubly-linked list before fNext */
 172   fPrev = fNext->prev;
 173   fNew->prev = fPrev;
 174   fPrev->next = fNew;
 175   fNew->next = fNext;
 176   fNext->prev = fNew;
 177
 178   fNew->anEdge = eOrig;
 179   fNew->data = NULL;
 180   fNew->trail = NULL;
 181   fNew->marked = FALSE;
 182
 183   /* The new face is marked "inside" if the old one was.  This is a
 184    * convenience for the common case where a face has been split in two.
 185    */
 186   fNew->inside = fNext->inside;
 187
 188   /* fix other edges on this face loop */
 189   e = eOrig;
 190   do {
 191     e->Lface = fNew;
 192     e = e->Lnext;
 193   } while( e != eOrig );
 194 }
 195
 196 /* KillEdge( eDel ) destroys an edge (the half-edges eDel and eDel->Sym),
 197  * and removes from the global edge list.
 198  */
 199 static void KillEdge( GLUhalfEdge *eDel )
 200 {
 201   GLUhalfEdge *ePrev, *eNext;
 202
 203   /* Half-edges are allocated in pairs, see EdgePair above */
 204   if( eDel->Sym < eDel ) { eDel = eDel->Sym; }
 205
 206   /* delete from circular doubly-linked list */
 207   eNext = eDel->next;
 208   ePrev = eDel->Sym->next;
 209   eNext->Sym->next = ePrev;
 210   ePrev->Sym->next = eNext;
 211
 212   HeapFree( GetProcessHeap(), 0, eDel );
 213 }
 214
 215
 216 /* KillVertex( vDel ) destroys a vertex and removes it from the global
 217  * vertex list.  It updates the vertex loop to point to a given new vertex.
 218  */
 219 static void KillVertex( GLUvertex *vDel, GLUvertex *newOrg )
 220 {
 221   GLUhalfEdge *e, *eStart = vDel->anEdge;
 222   GLUvertex *vPrev, *vNext;
 223
 224   /* change the origin of all affected edges */
 225   e = eStart;
 226   do {
 227     e->Org = newOrg;
 228     e = e->Onext;
 229   } while( e != eStart );
 230
 231   /* delete from circular doubly-linked list */
 232   vPrev = vDel->prev;
 233   vNext = vDel->next;
 234   vNext->prev = vPrev;
 235   vPrev->next = vNext;
 236
 237   HeapFree( GetProcessHeap(), 0, vDel );
 238 }
 239
 240 /* KillFace( fDel ) destroys a face and removes it from the global face
 241  * list.  It updates the face loop to point to a given new face.
 242  */
 243 static void KillFace( GLUface *fDel, GLUface *newLface )
 244 {
 245   GLUhalfEdge *e, *eStart = fDel->anEdge;
 246   GLUface *fPrev, *fNext;
 247
 248   /* change the left face of all affected edges */
 249   e = eStart;
 250   do {
 251     e->Lface = newLface;
 252     e = e->Lnext;
 253   } while( e != eStart );
 254
 255   /* delete from circular doubly-linked list */
 256   fPrev = fDel->prev;
 257   fNext = fDel->next;
 258   fNext->prev = fPrev;
 259   fPrev->next = fNext;
 260
 261   HeapFree( GetProcessHeap(), 0, fDel );
 262 }
 263
 264
 265 /****************** Basic Edge Operations **********************/
 266
 267 /* __gl_meshMakeEdge creates one edge, two vertices, and a loop (face).
 268  * The loop consists of the two new half-edges.
 269  */
 270 GLUhalfEdge *__gl_meshMakeEdge( GLUmesh *mesh )
 271 {
 272   GLUvertex *newVertex1= allocVertex();
 273   GLUvertex *newVertex2= allocVertex();
 274   GLUface *newFace= allocFace();
 275   GLUhalfEdge *e;
 276
 277   /* if any one is null then all get freed */
 278   if (newVertex1 == NULL || newVertex2 == NULL || newFace == NULL) {
 279      HeapFree( GetProcessHeap(), 0, newVertex1 );
 280      HeapFree( GetProcessHeap(), 0, newVertex2 );
 281      HeapFree( GetProcessHeap(), 0, newFace );
 282      return NULL;
 283   }
 284
 285   e = MakeEdge( &mesh->eHead );
 286   if (e == NULL) {
 287      HeapFree( GetProcessHeap(), 0, newVertex1 );
 288      HeapFree( GetProcessHeap(), 0, newVertex2 );
 289      HeapFree( GetProcessHeap(), 0, newFace );
 290      return NULL;
 291   }
 292
 293   MakeVertex( newVertex1, e, &mesh->vHead );
 294   MakeVertex( newVertex2, e->Sym, &mesh->vHead );
 295   MakeFace( newFace, e, &mesh->fHead );
 296   return e;
 297 }
 298
 299
 300 /* __gl_meshSplice( eOrg, eDst ) is the basic operation for changing the
 301  * mesh connectivity and topology.  It changes the mesh so that
 302  *      eOrg->Onext <- OLD( eDst->Onext )
 303  *      eDst->Onext <- OLD( eOrg->Onext )
 304  * where OLD(...) means the value before the meshSplice operation.
 305  *
 306  * This can have two effects on the vertex structure:
 307  *  - if eOrg->Org != eDst->Org, the two vertices are merged together
 308  *  - if eOrg->Org == eDst->Org, the origin is split into two vertices
 309  * In both cases, eDst->Org is changed and eOrg->Org is untouched.
 310  *
 311  * Similarly (and independently) for the face structure,
 312  *  - if eOrg->Lface == eDst->Lface, one loop is split into two
 313  *  - if eOrg->Lface != eDst->Lface, two distinct loops are joined into one
 314  * In both cases, eDst->Lface is changed and eOrg->Lface is unaffected.
 315  *
 316  * Some special cases:
 317  * If eDst == eOrg, the operation has no effect.
 318  * If eDst == eOrg->Lnext, the new face will have a single edge.
 319  * If eDst == eOrg->Lprev, the old face will have a single edge.
 320  * If eDst == eOrg->Onext, the new vertex will have a single edge.
 321  * If eDst == eOrg->Oprev, the old vertex will have a single edge.
 322  */
 323 int __gl_meshSplice( GLUhalfEdge *eOrg, GLUhalfEdge *eDst )
 324 {
 325   int joiningLoops = FALSE;
 326   int joiningVertices = FALSE;
 327
 328   if( eOrg == eDst ) return 1;
 329
 330   if( eDst->Org != eOrg->Org ) {
 331     /* We are merging two disjoint vertices -- destroy eDst->Org */
 332     joiningVertices = TRUE;
 333     KillVertex( eDst->Org, eOrg->Org );
 334   }
 335   if( eDst->Lface != eOrg->Lface ) {
 336     /* We are connecting two disjoint loops -- destroy eDst->Lface */
 337     joiningLoops = TRUE;
 338     KillFace( eDst->Lface, eOrg->Lface );
 339   }
 340
 341   /* Change the edge structure */
 342   Splice( eDst, eOrg );
 343
 344   if( ! joiningVertices ) {
 345     GLUvertex *newVertex= allocVertex();
 346     if (newVertex == NULL) return 0;
 347
 348     /* We split one vertex into two -- the new vertex is eDst->Org.
 349      * Make sure the old vertex points to a valid half-edge.
 350      */
 351     MakeVertex( newVertex, eDst, eOrg->Org );
 352     eOrg->Org->anEdge = eOrg;
 353   }
 354   if( ! joiningLoops ) {
 355     GLUface *newFace= allocFace();
 356     if (newFace == NULL) return 0;
 357
 358     /* We split one loop into two -- the new loop is eDst->Lface.
 359      * Make sure the old face points to a valid half-edge.
 360      */
 361     MakeFace( newFace, eDst, eOrg->Lface );
 362     eOrg->Lface->anEdge = eOrg;
 363   }
 364
 365   return 1;
 366 }
 367
 368
 369 /* __gl_meshDelete( eDel ) removes the edge eDel.  There are several cases:
 370  * if (eDel->Lface != eDel->Rface), we join two loops into one; the loop
 371  * eDel->Lface is deleted.  Otherwise, we are splitting one loop into two;
 372  * the newly created loop will contain eDel->Dst.  If the deletion of eDel
 373  * would create isolated vertices, those are deleted as well.
 374  *
 375  * This function could be implemented as two calls to __gl_meshSplice
 376  * plus a few calls to memFree, but this would allocate and delete
 377  * unnecessary vertices and faces.
 378  */
 379 int __gl_meshDelete( GLUhalfEdge *eDel )
 380 {
 381   GLUhalfEdge *eDelSym = eDel->Sym;
 382   int joiningLoops = FALSE;
 383
 384   /* First step: disconnect the origin vertex eDel->Org.  We make all
 385    * changes to get a consistent mesh in this "intermediate" state.
 386    */
 387   if( eDel->Lface != eDel->Rface ) {
 388     /* We are joining two loops into one -- remove the left face */
 389     joiningLoops = TRUE;
 390     KillFace( eDel->Lface, eDel->Rface );
 391   }
 392
 393   if( eDel->Onext == eDel ) {
 394     KillVertex( eDel->Org, NULL );
 395   } else {
 396     /* Make sure that eDel->Org and eDel->Rface point to valid half-edges */
 397     eDel->Rface->anEdge = eDel->Oprev;
 398     eDel->Org->anEdge = eDel->Onext;
 399
 400     Splice( eDel, eDel->Oprev );
 401     if( ! joiningLoops ) {
 402       GLUface *newFace= allocFace();
 403       if (newFace == NULL) return 0;
 404
 405       /* We are splitting one loop into two -- create a new loop for eDel. */
 406       MakeFace( newFace, eDel, eDel->Lface );
 407     }
 408   }
 409
 410   /* Claim: the mesh is now in a consistent state, except that eDel->Org
 411    * may have been deleted.  Now we disconnect eDel->Dst.
 412    */
 413   if( eDelSym->Onext == eDelSym ) {
 414     KillVertex( eDelSym->Org, NULL );
 415     KillFace( eDelSym->Lface, NULL );
 416   } else {
 417     /* Make sure that eDel->Dst and eDel->Lface point to valid half-edges */
 418     eDel->Lface->anEdge = eDelSym->Oprev;
 419     eDelSym->Org->anEdge = eDelSym->Onext;
 420     Splice( eDelSym, eDelSym->Oprev );
 421   }
 422
 423   /* Any isolated vertices or faces have already been freed. */
 424   KillEdge( eDel );
 425
 426   return 1;
 427 }
 428
 429
 430 /******************** Other Edge Operations **********************/
 431
 432 /* All these routines can be implemented with the basic edge
 433  * operations above.  They are provided for convenience and efficiency.
 434  */
 435
 436
 437 /* __gl_meshAddEdgeVertex( eOrg ) creates a new edge eNew such that
 438  * eNew == eOrg->Lnext, and eNew->Dst is a newly created vertex.
 439  * eOrg and eNew will have the same left face.
 440  */
 441 GLUhalfEdge *__gl_meshAddEdgeVertex( GLUhalfEdge *eOrg )
 442 {
 443   GLUhalfEdge *eNewSym;
 444   GLUhalfEdge *eNew = MakeEdge( eOrg );
 445   if (eNew == NULL) return NULL;
 446
 447   eNewSym = eNew->Sym;
 448
 449   /* Connect the new edge appropriately */
 450   Splice( eNew, eOrg->Lnext );
 451
 452   /* Set the vertex and face information */
 453   eNew->Org = eOrg->Dst;
 454   {
 455     GLUvertex *newVertex= allocVertex();
 456     if (newVertex == NULL) return NULL;
 457
 458     MakeVertex( newVertex, eNewSym, eNew->Org );
 459   }
 460   eNew->Lface = eNewSym->Lface = eOrg->Lface;
 461
 462   return eNew;
 463 }
 464
 465
 466 /* __gl_meshSplitEdge( eOrg ) splits eOrg into two edges eOrg and eNew,
 467  * such that eNew == eOrg->Lnext.  The new vertex is eOrg->Dst == eNew->Org.
 468  * eOrg and eNew will have the same left face.
 469  */
 470 GLUhalfEdge *__gl_meshSplitEdge( GLUhalfEdge *eOrg )
 471 {
 472   GLUhalfEdge *eNew;
 473   GLUhalfEdge *tempHalfEdge= __gl_meshAddEdgeVertex( eOrg );
 474   if (tempHalfEdge == NULL) return NULL;
 475
 476   eNew = tempHalfEdge->Sym;
 477
 478   /* Disconnect eOrg from eOrg->Dst and connect it to eNew->Org */
 479   Splice( eOrg->Sym, eOrg->Sym->Oprev );
 480   Splice( eOrg->Sym, eNew );
 481
 482   /* Set the vertex and face information */
 483   eOrg->Dst = eNew->Org;
 484   eNew->Dst->anEdge = eNew->Sym;        /* may have pointed to eOrg->Sym */
 485   eNew->Rface = eOrg->Rface;
 486   eNew->winding = eOrg->winding;        /* copy old winding information */
 487   eNew->Sym->winding = eOrg->Sym->winding;
 488
 489   return eNew;
 490 }
 491
 492
 493 /* __gl_meshConnect( eOrg, eDst ) creates a new edge from eOrg->Dst
 494  * to eDst->Org, and returns the corresponding half-edge eNew.
 495  * If eOrg->Lface == eDst->Lface, this splits one loop into two,
 496  * and the newly created loop is eNew->Lface.  Otherwise, two disjoint
 497  * loops are merged into one, and the loop eDst->Lface is destroyed.
 498  *
 499  * If (eOrg == eDst), the new face will have only two edges.
 500  * If (eOrg->Lnext == eDst), the old face is reduced to a single edge.
 501  * If (eOrg->Lnext->Lnext == eDst), the old face is reduced to two edges.
 502  */
 503 GLUhalfEdge *__gl_meshConnect( GLUhalfEdge *eOrg, GLUhalfEdge *eDst )
 504 {
 505   GLUhalfEdge *eNewSym;
 506   int joiningLoops = FALSE;
 507   GLUhalfEdge *eNew = MakeEdge( eOrg );
 508   if (eNew == NULL) return NULL;
 509
 510   eNewSym = eNew->Sym;
 511
 512   if( eDst->Lface != eOrg->Lface ) {
 513     /* We are connecting two disjoint loops -- destroy eDst->Lface */
 514     joiningLoops = TRUE;
 515     KillFace( eDst->Lface, eOrg->Lface );
 516   }
 517
 518   /* Connect the new edge appropriately */
 519   Splice( eNew, eOrg->Lnext );
 520   Splice( eNewSym, eDst );
 521
 522   /* Set the vertex and face information */
 523   eNew->Org = eOrg->Dst;
 524   eNewSym->Org = eDst->Org;
 525   eNew->Lface = eNewSym->Lface = eOrg->Lface;
 526
 527   /* Make sure the old face points to a valid half-edge */
 528   eOrg->Lface->anEdge = eNewSym;
 529
 530   if( ! joiningLoops ) {
 531     GLUface *newFace= allocFace();
 532     if (newFace == NULL) return NULL;
 533
 534     /* We split one loop into two -- the new loop is eNew->Lface */
 535     MakeFace( newFace, eNew, eOrg->Lface );
 536   }
 537   return eNew;
 538 }
 539
 540
 541 /******************** Other Operations **********************/
 542
 543 /* __gl_meshZapFace( fZap ) destroys a face and removes it from the
 544  * global face list.  All edges of fZap will have a NULL pointer as their
 545  * left face.  Any edges which also have a NULL pointer as their right face
 546  * are deleted entirely (along with any isolated vertices this produces).
 547  * An entire mesh can be deleted by zapping its faces, one at a time,
 548  * in any order.  Zapped faces cannot be used in further mesh operations!
 549  */
 550 void __gl_meshZapFace( GLUface *fZap )
 551 {
 552   GLUhalfEdge *eStart = fZap->anEdge;
 553   GLUhalfEdge *e, *eNext, *eSym;
 554   GLUface *fPrev, *fNext;
 555
 556   /* walk around face, deleting edges whose right face is also NULL */
 557   eNext = eStart->Lnext;
 558   do {
 559     e = eNext;
 560     eNext = e->Lnext;
 561
 562     e->Lface = NULL;
 563     if( e->Rface == NULL ) {
 564       /* delete the edge -- see __gl_MeshDelete above */
 565
 566       if( e->Onext == e ) {
 567         KillVertex( e->Org, NULL );
 568       } else {
 569         /* Make sure that e->Org points to a valid half-edge */
 570         e->Org->anEdge = e->Onext;
 571         Splice( e, e->Oprev );
 572       }
 573       eSym = e->Sym;
 574       if( eSym->Onext == eSym ) {
 575         KillVertex( eSym->Org, NULL );
 576       } else {
 577         /* Make sure that eSym->Org points to a valid half-edge */
 578         eSym->Org->anEdge = eSym->Onext;
 579         Splice( eSym, eSym->Oprev );
 580       }
 581       KillEdge( e );
 582     }
 583   } while( e != eStart );
 584
 585   /* delete from circular doubly-linked list */
 586   fPrev = fZap->prev;
 587   fNext = fZap->next;
 588   fNext->prev = fPrev;
 589   fPrev->next = fNext;
 590
 591   HeapFree( GetProcessHeap(), 0, fZap );
 592 }
 593
 594
 595 /* __gl_meshNewMesh() creates a new mesh with no edges, no vertices,
 596  * and no loops (what we usually call a "face").
 597  */
 598 GLUmesh *__gl_meshNewMesh( void )
 599 {
 600   GLUvertex *v;
 601   GLUface *f;
 602   GLUhalfEdge *e;
 603   GLUhalfEdge *eSym;
 604   GLUmesh *mesh = HeapAlloc( GetProcessHeap(), 0, sizeof( GLUmesh ));
 605   if (mesh == NULL) {
 606      return NULL;
 607   }
 608
 609   v = &mesh->vHead;
 610   f = &mesh->fHead;
 611   e = &mesh->eHead;
 612   eSym = &mesh->eHeadSym;
 613
 614   v->next = v->prev = v;
 615   v->anEdge = NULL;
 616   v->data = NULL;
 617
 618   f->next = f->prev = f;
 619   f->anEdge = NULL;
 620   f->data = NULL;
 621   f->trail = NULL;
 622   f->marked = FALSE;
 623   f->inside = FALSE;
 624
 625   e->next = e;
 626   e->Sym = eSym;
 627   e->Onext = NULL;
 628   e->Lnext = NULL;
 629   e->Org = NULL;
 630   e->Lface = NULL;
 631   e->winding = 0;
 632   e->activeRegion = NULL;
 633
 634   eSym->next = eSym;
 635   eSym->Sym = e;
 636   eSym->Onext = NULL;
 637   eSym->Lnext = NULL;
 638   eSym->Org = NULL;
 639   eSym->Lface = NULL;
 640   eSym->winding = 0;
 641   eSym->activeRegion = NULL;
 642
 643   return mesh;
 644 }
 645
 646
 647 /* __gl_meshUnion( mesh1, mesh2 ) forms the union of all structures in
 648  * both meshes, and returns the new mesh (the old meshes are destroyed).
 649  */
 650 GLUmesh *__gl_meshUnion( GLUmesh *mesh1, GLUmesh *mesh2 )
 651 {
 652   GLUface *f1 = &mesh1->fHead;
 653   GLUvertex *v1 = &mesh1->vHead;
 654   GLUhalfEdge *e1 = &mesh1->eHead;
 655   GLUface *f2 = &mesh2->fHead;
 656   GLUvertex *v2 = &mesh2->vHead;
 657   GLUhalfEdge *e2 = &mesh2->eHead;
 658
 659   /* Add the faces, vertices, and edges of mesh2 to those of mesh1 */
 660   if( f2->next != f2 ) {
 661     f1->prev->next = f2->next;
 662     f2->next->prev = f1->prev;
 663     f2->prev->next = f1;
 664     f1->prev = f2->prev;
 665   }
 666
 667   if( v2->next != v2 ) {
 668     v1->prev->next = v2->next;
 669     v2->next->prev = v1->prev;
 670     v2->prev->next = v1;
 671     v1->prev = v2->prev;
 672   }
 673
 674   if( e2->next != e2 ) {
 675     e1->Sym->next->Sym->next = e2->next;
 676     e2->next->Sym->next = e1->Sym->next;
 677     e2->Sym->next->Sym->next = e1;
 678     e1->Sym->next = e2->Sym->next;
 679   }
 680
 681   HeapFree( GetProcessHeap(), 0, mesh2 );
 682   return mesh1;
 683 }
 684
 685
 686 #ifdef DELETE_BY_ZAPPING
 687
 688 /* __gl_meshDeleteMesh( mesh ) will free all storage for any valid mesh.
 689  */
 690 void __gl_meshDeleteMesh( GLUmesh *mesh )
 691 {
 692   GLUface *fHead = &mesh->fHead;
 693
 694   while( fHead->next != fHead ) {
 695     __gl_meshZapFace( fHead->next );
 696   }
 697   assert( mesh->vHead.next == &mesh->vHead );
 698
 699   memFree( mesh );
 700 }
 701
 702 #else
 703
 704 /* __gl_meshDeleteMesh( mesh ) will free all storage for any valid mesh.
 705  */
 706 void __gl_meshDeleteMesh( GLUmesh *mesh )
 707 {
 708   GLUface *f, *fNext;
 709   GLUvertex *v, *vNext;
 710   GLUhalfEdge *e, *eNext;
 711
 712   for( f = mesh->fHead.next; f != &mesh->fHead; f = fNext ) {
 713     fNext = f->next;
 714     HeapFree( GetProcessHeap(), 0, f );
 715   }
 716
 717   for( v = mesh->vHead.next; v != &mesh->vHead; v = vNext ) {
 718     vNext = v->next;
 719     HeapFree( GetProcessHeap(), 0, v );
 720   }
 721
 722   for( e = mesh->eHead.next; e != &mesh->eHead; e = eNext ) {
 723     /* One call frees both e and e->Sym (see EdgePair above) */
 724     eNext = e->next;
 725     HeapFree( GetProcessHeap(), 0, e );
 726   }
 727
 728   HeapFree( GetProcessHeap(), 0, mesh );
 729 }
 730
 731 #endif
 732
 733 #ifndef NDEBUG
 734
 735 /* __gl_meshCheckMesh( mesh ) checks a mesh for self-consistency.
 736  */
 737 void __gl_meshCheckMesh( GLUmesh *mesh )
 738 {
 739   GLUface *fHead = &mesh->fHead;
 740   GLUvertex *vHead = &mesh->vHead;
 741   GLUhalfEdge *eHead = &mesh->eHead;
 742   GLUface *f, *fPrev;
 743   GLUvertex *v, *vPrev;
 744   GLUhalfEdge *e, *ePrev;
 745
 746   fPrev = fHead;
 747   for( fPrev = fHead ; (f = fPrev->next) != fHead; fPrev = f) {
 748     assert( f->prev == fPrev );
 749     e = f->anEdge;
 750     do {
 751       assert( e->Sym != e );
 752       assert( e->Sym->Sym == e );
 753       assert( e->Lnext->Onext->Sym == e );
 754       assert( e->Onext->Sym->Lnext == e );
 755       assert( e->Lface == f );
 756       e = e->Lnext;
 757     } while( e != f->anEdge );
 758   }
 759   assert( f->prev == fPrev && f->anEdge == NULL && f->data == NULL );
 760
 761   vPrev = vHead;
 762   for( vPrev = vHead ; (v = vPrev->next) != vHead; vPrev = v) {
 763     assert( v->prev == vPrev );
 764     e = v->anEdge;
 765     do {
 766       assert( e->Sym != e );
 767       assert( e->Sym->Sym == e );
 768       assert( e->Lnext->Onext->Sym == e );
 769       assert( e->Onext->Sym->Lnext == e );
 770       assert( e->Org == v );
 771       e = e->Onext;
 772     } while( e != v->anEdge );
 773   }
 774   assert( v->prev == vPrev && v->anEdge == NULL && v->data == NULL );
 775
 776   ePrev = eHead;
 777   for( ePrev = eHead ; (e = ePrev->next) != eHead; ePrev = e) {
 778     assert( e->Sym->next == ePrev->Sym );
 779     assert( e->Sym != e );
 780     assert( e->Sym->Sym == e );
 781     assert( e->Org != NULL );
 782     assert( e->Dst != NULL );
 783     assert( e->Lnext->Onext->Sym == e );
 784     assert( e->Onext->Sym->Lnext == e );
 785   }
 786   assert( e->Sym->next == ePrev->Sym
 787        && e->Sym == &mesh->eHeadSym
 788        && e->Sym->Sym == e
 789        && e->Org == NULL && e->Dst == NULL
 790        && e->Lface == NULL && e->Rface == NULL );
 791 }
 792
 793 #endif
 794
 795 /* monotone region support (used to be in tessmono.c) */
 796
 797 /* __gl_meshTessellateMonoRegion( face ) tessellates a monotone region
 798  * (what else would it do??)  The region must consist of a single
 799  * loop of half-edges (see mesh.h) oriented CCW.  "Monotone" in this
 800  * case means that any vertical line intersects the interior of the
 801  * region in a single interval.
 802  *
 803  * Tessellation consists of adding interior edges (actually pairs of
 804  * half-edges), to split the region into non-overlapping triangles.
 805  *
 806  * The basic idea is explained in Preparata and Shamos (which I don''t
 807  * have handy right now), although their implementation is more
 808  * complicated than this one.  The are two edge chains, an upper chain
 809  * and a lower chain.  We process all vertices from both chains in order,
 810  * from right to left.
 811  *
 812  * The algorithm ensures that the following invariant holds after each
 813  * vertex is processed: the untessellated region consists of two
 814  * chains, where one chain (say the upper) is a single edge, and
 815  * the other chain is concave.  The left vertex of the single edge
 816  * is always to the left of all vertices in the concave chain.
 817  *
 818  * Each step consists of adding the rightmost unprocessed vertex to one
 819  * of the two chains, and forming a fan of triangles from the rightmost
 820  * of two chain endpoints.  Determining whether we can add each triangle
 821  * to the fan is a simple orientation test.  By making the fan as large
 822  * as possible, we restore the invariant (check it yourself).
 823  */
 824 static int __gl_meshTessellateMonoRegion( GLUface *face )
 825 {
 826   GLUhalfEdge *up, *lo;
 827
 828   /* All edges are oriented CCW around the boundary of the region.
 829    * First, find the half-edge whose origin vertex is rightmost.
 830    * Since the sweep goes from left to right, face->anEdge should
 831    * be close to the edge we want.
 832    */
 833   up = face->anEdge;
 834   assert( up->Lnext != up && up->Lnext->Lnext != up );
 835
 836   for( ; VertLeq( up->Dst, up->Org ); up = up->Lprev )
 837     ;
 838   for( ; VertLeq( up->Org, up->Dst ); up = up->Lnext )
 839     ;
 840   lo = up->Lprev;
 841
 842   while( up->Lnext != lo ) {
 843     if( VertLeq( up->Dst, lo->Org )) {
 844       /* up->Dst is on the left.  It is safe to form triangles from lo->Org.
 845        * The EdgeGoesLeft test guarantees progress even when some triangles
 846        * are CW, given that the upper and lower chains are truly monotone.
 847        */
 848       while( lo->Lnext != up && (EdgeGoesLeft( lo->Lnext )
 849              || EdgeSign( lo->Org, lo->Dst, lo->Lnext->Dst ) <= 0 )) {
 850         GLUhalfEdge *tempHalfEdge= __gl_meshConnect( lo->Lnext, lo );
 851         if (tempHalfEdge == NULL) return 0;
 852         lo = tempHalfEdge->Sym;
 853       }
 854       lo = lo->Lprev;
 855     } else {
 856       /* lo->Org is on the left.  We can make CCW triangles from up->Dst. */
 857       while( lo->Lnext != up && (EdgeGoesRight( up->Lprev )
 858              || EdgeSign( up->Dst, up->Org, up->Lprev->Org ) >= 0 )) {
 859         GLUhalfEdge *tempHalfEdge= __gl_meshConnect( up, up->Lprev );
 860         if (tempHalfEdge == NULL) return 0;
 861         up = tempHalfEdge->Sym;
 862       }
 863       up = up->Lnext;
 864     }
 865   }
 866
 867   /* Now lo->Org == up->Dst == the leftmost vertex.  The remaining region
 868    * can be tessellated in a fan from this leftmost vertex.
 869    */
 870   assert( lo->Lnext != up );
 871   while( lo->Lnext->Lnext != up ) {
 872     GLUhalfEdge *tempHalfEdge= __gl_meshConnect( lo->Lnext, lo );
 873     if (tempHalfEdge == NULL) return 0;
 874     lo = tempHalfEdge->Sym;
 875   }
 876
 877   return 1;
 878 }
 879
 880
 881 /* __gl_meshTessellateInterior( mesh ) tessellates each region of
 882  * the mesh which is marked "inside" the polygon.  Each such region
 883  * must be monotone.
 884  */
 885 int __gl_meshTessellateInterior( GLUmesh *mesh )
 886 {
 887   GLUface *f, *next;
 888
 889   /*LINTED*/
 890   for( f = mesh->fHead.next; f != &mesh->fHead; f = next ) {
 891     /* Make sure we don''t try to tessellate the new triangles. */
 892     next = f->next;
 893     if( f->inside ) {
 894       if ( !__gl_meshTessellateMonoRegion( f ) ) return 0;
 895     }
 896   }
 897
 898   return 1;
 899 }
 900
 901
 902 /* __gl_meshDiscardExterior( mesh ) zaps (ie. sets to NULL) all faces
 903  * which are not marked "inside" the polygon.  Since further mesh operations
 904  * on NULL faces are not allowed, the main purpose is to clean up the
 905  * mesh so that exterior loops are not represented in the data structure.
 906  */
 907 void __gl_meshDiscardExterior( GLUmesh *mesh )
 908 {
 909   GLUface *f, *next;
 910
 911   /*LINTED*/
 912   for( f = mesh->fHead.next; f != &mesh->fHead; f = next ) {
 913     /* Since f will be destroyed, save its next pointer. */
 914     next = f->next;
 915     if( ! f->inside ) {
 916       __gl_meshZapFace( f );
 917     }
 918   }
 919 }
 920
 921 /* __gl_meshSetWindingNumber( mesh, value, keepOnlyBoundary ) resets the
 922  * winding numbers on all edges so that regions marked "inside" the
 923  * polygon have a winding number of "value", and regions outside
 924  * have a winding number of 0.
 925  *
 926  * If keepOnlyBoundary is TRUE, it also deletes all edges which do not
 927  * separate an interior region from an exterior one.
 928  */
 929 int __gl_meshSetWindingNumber( GLUmesh *mesh, int value,
 930                                 GLboolean keepOnlyBoundary )
 931 {
 932   GLUhalfEdge *e, *eNext;
 933
 934   for( e = mesh->eHead.next; e != &mesh->eHead; e = eNext ) {
 935     eNext = e->next;
 936     if( e->Rface->inside != e->Lface->inside ) {
 937
 938       /* This is a boundary edge (one side is interior, one is exterior). */
 939       e->winding = (e->Lface->inside) ? value : -value;
 940     } else {
 941
 942       /* Both regions are interior, or both are exterior. */
 943       if( ! keepOnlyBoundary ) {
 944         e->winding = 0;
 945       } else {
 946         if ( !__gl_meshDelete( e ) ) return 0;
 947       }
 948     }
 949   }
 950   return 1;
 951 }