]> git.jsancho.org Git - lugaru.git/blob - Dependencies/GLU/mesh.c
Drop commented-out remains of MinMaxDistance
[lugaru.git] / Dependencies / GLU / 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) return NULL;
288
289   MakeVertex( newVertex1, e, &mesh->vHead );
290   MakeVertex( newVertex2, e->Sym, &mesh->vHead );
291   MakeFace( newFace, e, &mesh->fHead );
292   return e;
293 }
294   
295
296 /* __gl_meshSplice( eOrg, eDst ) is the basic operation for changing the
297  * mesh connectivity and topology.  It changes the mesh so that
298  *      eOrg->Onext <- OLD( eDst->Onext )
299  *      eDst->Onext <- OLD( eOrg->Onext )
300  * where OLD(...) means the value before the meshSplice operation.
301  *
302  * This can have two effects on the vertex structure:
303  *  - if eOrg->Org != eDst->Org, the two vertices are merged together
304  *  - if eOrg->Org == eDst->Org, the origin is split into two vertices
305  * In both cases, eDst->Org is changed and eOrg->Org is untouched.
306  *
307  * Similarly (and independently) for the face structure,
308  *  - if eOrg->Lface == eDst->Lface, one loop is split into two
309  *  - if eOrg->Lface != eDst->Lface, two distinct loops are joined into one
310  * In both cases, eDst->Lface is changed and eOrg->Lface is unaffected.
311  *
312  * Some special cases:
313  * If eDst == eOrg, the operation has no effect.
314  * If eDst == eOrg->Lnext, the new face will have a single edge.
315  * If eDst == eOrg->Lprev, the old face will have a single edge.
316  * If eDst == eOrg->Onext, the new vertex will have a single edge.
317  * If eDst == eOrg->Oprev, the old vertex will have a single edge.
318  */
319 int __gl_meshSplice( GLUhalfEdge *eOrg, GLUhalfEdge *eDst )
320 {
321   int joiningLoops = FALSE;
322   int joiningVertices = FALSE;
323
324   if( eOrg == eDst ) return 1;
325
326   if( eDst->Org != eOrg->Org ) {
327     /* We are merging two disjoint vertices -- destroy eDst->Org */
328     joiningVertices = TRUE;
329     KillVertex( eDst->Org, eOrg->Org );
330   }
331   if( eDst->Lface != eOrg->Lface ) {
332     /* We are connecting two disjoint loops -- destroy eDst->Lface */
333     joiningLoops = TRUE;
334     KillFace( eDst->Lface, eOrg->Lface );
335   }
336
337   /* Change the edge structure */
338   Splice( eDst, eOrg );
339
340   if( ! joiningVertices ) {
341     GLUvertex *newVertex= allocVertex();
342     if (newVertex == NULL) return 0;
343
344     /* We split one vertex into two -- the new vertex is eDst->Org.
345      * Make sure the old vertex points to a valid half-edge.
346      */
347     MakeVertex( newVertex, eDst, eOrg->Org );
348     eOrg->Org->anEdge = eOrg;
349   }
350   if( ! joiningLoops ) {
351     GLUface *newFace= allocFace();  
352     if (newFace == NULL) return 0;
353
354     /* We split one loop into two -- the new loop is eDst->Lface.
355      * Make sure the old face points to a valid half-edge.
356      */
357     MakeFace( newFace, eDst, eOrg->Lface );
358     eOrg->Lface->anEdge = eOrg;
359   }
360
361   return 1;
362 }
363
364
365 /* __gl_meshDelete( eDel ) removes the edge eDel.  There are several cases:
366  * if (eDel->Lface != eDel->Rface), we join two loops into one; the loop
367  * eDel->Lface is deleted.  Otherwise, we are splitting one loop into two;
368  * the newly created loop will contain eDel->Dst.  If the deletion of eDel
369  * would create isolated vertices, those are deleted as well.
370  *
371  * This function could be implemented as two calls to __gl_meshSplice
372  * plus a few calls to memFree, but this would allocate and delete
373  * unnecessary vertices and faces.
374  */
375 int __gl_meshDelete( GLUhalfEdge *eDel )
376 {
377   GLUhalfEdge *eDelSym = eDel->Sym;
378   int joiningLoops = FALSE;
379
380   /* First step: disconnect the origin vertex eDel->Org.  We make all
381    * changes to get a consistent mesh in this "intermediate" state.
382    */
383   if( eDel->Lface != eDel->Rface ) {
384     /* We are joining two loops into one -- remove the left face */
385     joiningLoops = TRUE;
386     KillFace( eDel->Lface, eDel->Rface );
387   }
388
389   if( eDel->Onext == eDel ) {
390     KillVertex( eDel->Org, NULL );
391   } else {
392     /* Make sure that eDel->Org and eDel->Rface point to valid half-edges */
393     eDel->Rface->anEdge = eDel->Oprev;
394     eDel->Org->anEdge = eDel->Onext;
395
396     Splice( eDel, eDel->Oprev );
397     if( ! joiningLoops ) {
398       GLUface *newFace= allocFace();
399       if (newFace == NULL) return 0; 
400
401       /* We are splitting one loop into two -- create a new loop for eDel. */
402       MakeFace( newFace, eDel, eDel->Lface );
403     }
404   }
405
406   /* Claim: the mesh is now in a consistent state, except that eDel->Org
407    * may have been deleted.  Now we disconnect eDel->Dst.
408    */
409   if( eDelSym->Onext == eDelSym ) {
410     KillVertex( eDelSym->Org, NULL );
411     KillFace( eDelSym->Lface, NULL );
412   } else {
413     /* Make sure that eDel->Dst and eDel->Lface point to valid half-edges */
414     eDel->Lface->anEdge = eDelSym->Oprev;
415     eDelSym->Org->anEdge = eDelSym->Onext;
416     Splice( eDelSym, eDelSym->Oprev );
417   }
418
419   /* Any isolated vertices or faces have already been freed. */
420   KillEdge( eDel );
421
422   return 1;
423 }
424
425
426 /******************** Other Edge Operations **********************/
427
428 /* All these routines can be implemented with the basic edge
429  * operations above.  They are provided for convenience and efficiency.
430  */
431
432
433 /* __gl_meshAddEdgeVertex( eOrg ) creates a new edge eNew such that
434  * eNew == eOrg->Lnext, and eNew->Dst is a newly created vertex.
435  * eOrg and eNew will have the same left face.
436  */
437 GLUhalfEdge *__gl_meshAddEdgeVertex( GLUhalfEdge *eOrg )
438 {
439   GLUhalfEdge *eNewSym;
440   GLUhalfEdge *eNew = MakeEdge( eOrg );
441   if (eNew == NULL) return NULL;
442
443   eNewSym = eNew->Sym;
444
445   /* Connect the new edge appropriately */
446   Splice( eNew, eOrg->Lnext );
447
448   /* Set the vertex and face information */
449   eNew->Org = eOrg->Dst;
450   {
451     GLUvertex *newVertex= allocVertex();
452     if (newVertex == NULL) return NULL;
453
454     MakeVertex( newVertex, eNewSym, eNew->Org );
455   }
456   eNew->Lface = eNewSym->Lface = eOrg->Lface;
457
458   return eNew;
459 }
460
461
462 /* __gl_meshSplitEdge( eOrg ) splits eOrg into two edges eOrg and eNew,
463  * such that eNew == eOrg->Lnext.  The new vertex is eOrg->Dst == eNew->Org.
464  * eOrg and eNew will have the same left face.
465  */
466 GLUhalfEdge *__gl_meshSplitEdge( GLUhalfEdge *eOrg )
467 {
468   GLUhalfEdge *eNew;
469   GLUhalfEdge *tempHalfEdge= __gl_meshAddEdgeVertex( eOrg );
470   if (tempHalfEdge == NULL) return NULL;
471
472   eNew = tempHalfEdge->Sym;
473
474   /* Disconnect eOrg from eOrg->Dst and connect it to eNew->Org */
475   Splice( eOrg->Sym, eOrg->Sym->Oprev );
476   Splice( eOrg->Sym, eNew );
477
478   /* Set the vertex and face information */
479   eOrg->Dst = eNew->Org;
480   eNew->Dst->anEdge = eNew->Sym;        /* may have pointed to eOrg->Sym */
481   eNew->Rface = eOrg->Rface;
482   eNew->winding = eOrg->winding;        /* copy old winding information */
483   eNew->Sym->winding = eOrg->Sym->winding;
484
485   return eNew;
486 }
487
488
489 /* __gl_meshConnect( eOrg, eDst ) creates a new edge from eOrg->Dst
490  * to eDst->Org, and returns the corresponding half-edge eNew.
491  * If eOrg->Lface == eDst->Lface, this splits one loop into two,
492  * and the newly created loop is eNew->Lface.  Otherwise, two disjoint
493  * loops are merged into one, and the loop eDst->Lface is destroyed.
494  *
495  * If (eOrg == eDst), the new face will have only two edges.
496  * If (eOrg->Lnext == eDst), the old face is reduced to a single edge.
497  * If (eOrg->Lnext->Lnext == eDst), the old face is reduced to two edges.
498  */
499 GLUhalfEdge *__gl_meshConnect( GLUhalfEdge *eOrg, GLUhalfEdge *eDst )
500 {
501   GLUhalfEdge *eNewSym;
502   int joiningLoops = FALSE;  
503   GLUhalfEdge *eNew = MakeEdge( eOrg );
504   if (eNew == NULL) return NULL;
505
506   eNewSym = eNew->Sym;
507
508   if( eDst->Lface != eOrg->Lface ) {
509     /* We are connecting two disjoint loops -- destroy eDst->Lface */
510     joiningLoops = TRUE;
511     KillFace( eDst->Lface, eOrg->Lface );
512   }
513
514   /* Connect the new edge appropriately */
515   Splice( eNew, eOrg->Lnext );
516   Splice( eNewSym, eDst );
517
518   /* Set the vertex and face information */
519   eNew->Org = eOrg->Dst;
520   eNewSym->Org = eDst->Org;
521   eNew->Lface = eNewSym->Lface = eOrg->Lface;
522
523   /* Make sure the old face points to a valid half-edge */
524   eOrg->Lface->anEdge = eNewSym;
525
526   if( ! joiningLoops ) {
527     GLUface *newFace= allocFace();
528     if (newFace == NULL) return NULL;
529
530     /* We split one loop into two -- the new loop is eNew->Lface */
531     MakeFace( newFace, eNew, eOrg->Lface );
532   }
533   return eNew;
534 }
535
536
537 /******************** Other Operations **********************/
538
539 /* __gl_meshZapFace( fZap ) destroys a face and removes it from the
540  * global face list.  All edges of fZap will have a NULL pointer as their
541  * left face.  Any edges which also have a NULL pointer as their right face
542  * are deleted entirely (along with any isolated vertices this produces).
543  * An entire mesh can be deleted by zapping its faces, one at a time,
544  * in any order.  Zapped faces cannot be used in further mesh operations!
545  */
546 void __gl_meshZapFace( GLUface *fZap )
547 {
548   GLUhalfEdge *eStart = fZap->anEdge;
549   GLUhalfEdge *e, *eNext, *eSym;
550   GLUface *fPrev, *fNext;
551
552   /* walk around face, deleting edges whose right face is also NULL */
553   eNext = eStart->Lnext;
554   do {
555     e = eNext;
556     eNext = e->Lnext;
557
558     e->Lface = NULL;
559     if( e->Rface == NULL ) {
560       /* delete the edge -- see __gl_MeshDelete above */
561
562       if( e->Onext == e ) {
563         KillVertex( e->Org, NULL );
564       } else {
565         /* Make sure that e->Org points to a valid half-edge */
566         e->Org->anEdge = e->Onext;
567         Splice( e, e->Oprev );
568       }
569       eSym = e->Sym;
570       if( eSym->Onext == eSym ) {
571         KillVertex( eSym->Org, NULL );
572       } else {
573         /* Make sure that eSym->Org points to a valid half-edge */
574         eSym->Org->anEdge = eSym->Onext;
575         Splice( eSym, eSym->Oprev );
576       }
577       KillEdge( e );
578     }
579   } while( e != eStart );
580
581   /* delete from circular doubly-linked list */
582   fPrev = fZap->prev;
583   fNext = fZap->next;
584   fNext->prev = fPrev;
585   fPrev->next = fNext;
586
587   memFree( fZap );
588 }
589
590
591 /* __gl_meshNewMesh() creates a new mesh with no edges, no vertices,
592  * and no loops (what we usually call a "face").
593  */
594 GLUmesh *__gl_meshNewMesh( void )
595 {
596   GLUvertex *v;
597   GLUface *f;
598   GLUhalfEdge *e;
599   GLUhalfEdge *eSym;
600   GLUmesh *mesh = (GLUmesh *)memAlloc( sizeof( GLUmesh ));
601   if (mesh == NULL) {
602      return NULL;
603   }
604   
605   v = &mesh->vHead;
606   f = &mesh->fHead;
607   e = &mesh->eHead;
608   eSym = &mesh->eHeadSym;
609
610   v->next = v->prev = v;
611   v->anEdge = NULL;
612   v->data = NULL;
613
614   f->next = f->prev = f;
615   f->anEdge = NULL;
616   f->data = NULL;
617   f->trail = NULL;
618   f->marked = FALSE;
619   f->inside = FALSE;
620
621   e->next = e;
622   e->Sym = eSym;
623   e->Onext = NULL;
624   e->Lnext = NULL;
625   e->Org = NULL;
626   e->Lface = NULL;
627   e->winding = 0;
628   e->activeRegion = NULL;
629
630   eSym->next = eSym;
631   eSym->Sym = e;
632   eSym->Onext = NULL;
633   eSym->Lnext = NULL;
634   eSym->Org = NULL;
635   eSym->Lface = NULL;
636   eSym->winding = 0;
637   eSym->activeRegion = NULL;
638
639   return mesh;
640 }
641
642
643 /* __gl_meshUnion( mesh1, mesh2 ) forms the union of all structures in
644  * both meshes, and returns the new mesh (the old meshes are destroyed).
645  */
646 GLUmesh *__gl_meshUnion( GLUmesh *mesh1, GLUmesh *mesh2 )
647 {
648   GLUface *f1 = &mesh1->fHead;
649   GLUvertex *v1 = &mesh1->vHead;
650   GLUhalfEdge *e1 = &mesh1->eHead;
651   GLUface *f2 = &mesh2->fHead;
652   GLUvertex *v2 = &mesh2->vHead;
653   GLUhalfEdge *e2 = &mesh2->eHead;
654
655   /* Add the faces, vertices, and edges of mesh2 to those of mesh1 */
656   if( f2->next != f2 ) {
657     f1->prev->next = f2->next;
658     f2->next->prev = f1->prev;
659     f2->prev->next = f1;
660     f1->prev = f2->prev;
661   }
662
663   if( v2->next != v2 ) {
664     v1->prev->next = v2->next;
665     v2->next->prev = v1->prev;
666     v2->prev->next = v1;
667     v1->prev = v2->prev;
668   }
669
670   if( e2->next != e2 ) {
671     e1->Sym->next->Sym->next = e2->next;
672     e2->next->Sym->next = e1->Sym->next;
673     e2->Sym->next->Sym->next = e1;
674     e1->Sym->next = e2->Sym->next;
675   }
676
677   memFree( mesh2 );
678   return mesh1;
679 }
680
681
682 #ifdef DELETE_BY_ZAPPING
683
684 /* __gl_meshDeleteMesh( mesh ) will free all storage for any valid mesh.
685  */
686 void __gl_meshDeleteMesh( GLUmesh *mesh )
687 {
688   GLUface *fHead = &mesh->fHead;
689
690   while( fHead->next != fHead ) {
691     __gl_meshZapFace( fHead->next );
692   }
693   assert( mesh->vHead.next == &mesh->vHead );
694
695   memFree( mesh );
696 }
697
698 #else
699
700 /* __gl_meshDeleteMesh( mesh ) will free all storage for any valid mesh.
701  */
702 void __gl_meshDeleteMesh( GLUmesh *mesh )
703 {
704   GLUface *f, *fNext;
705   GLUvertex *v, *vNext;
706   GLUhalfEdge *e, *eNext;
707
708   for( f = mesh->fHead.next; f != &mesh->fHead; f = fNext ) {
709     fNext = f->next;
710     memFree( f );
711   }
712
713   for( v = mesh->vHead.next; v != &mesh->vHead; v = vNext ) {
714     vNext = v->next;
715     memFree( v );
716   }
717
718   for( e = mesh->eHead.next; e != &mesh->eHead; e = eNext ) {
719     /* One call frees both e and e->Sym (see EdgePair above) */
720     eNext = e->next;
721     memFree( e );
722   }
723
724   memFree( mesh );
725 }
726
727 #endif
728
729 #ifndef NDEBUG
730
731 /* __gl_meshCheckMesh( mesh ) checks a mesh for self-consistency.
732  */
733 void __gl_meshCheckMesh( GLUmesh *mesh )
734 {
735   GLUface *fHead = &mesh->fHead;
736   GLUvertex *vHead = &mesh->vHead;
737   GLUhalfEdge *eHead = &mesh->eHead;
738   GLUface *f, *fPrev;
739   GLUvertex *v, *vPrev;
740   GLUhalfEdge *e, *ePrev;
741
742   fPrev = fHead;
743   for( fPrev = fHead ; (f = fPrev->next) != fHead; fPrev = f) {
744     assert( f->prev == fPrev );
745     e = f->anEdge;
746     do {
747       assert( e->Sym != e );
748       assert( e->Sym->Sym == e );
749       assert( e->Lnext->Onext->Sym == e );
750       assert( e->Onext->Sym->Lnext == e );
751       assert( e->Lface == f );
752       e = e->Lnext;
753     } while( e != f->anEdge );
754   }
755   assert( f->prev == fPrev && f->anEdge == NULL && f->data == NULL );
756
757   vPrev = vHead;
758   for( vPrev = vHead ; (v = vPrev->next) != vHead; vPrev = v) {
759     assert( v->prev == vPrev );
760     e = v->anEdge;
761     do {
762       assert( e->Sym != e );
763       assert( e->Sym->Sym == e );
764       assert( e->Lnext->Onext->Sym == e );
765       assert( e->Onext->Sym->Lnext == e );
766       assert( e->Org == v );
767       e = e->Onext;
768     } while( e != v->anEdge );
769   }
770   assert( v->prev == vPrev && v->anEdge == NULL && v->data == NULL );
771
772   ePrev = eHead;
773   for( ePrev = eHead ; (e = ePrev->next) != eHead; ePrev = e) {
774     assert( e->Sym->next == ePrev->Sym );
775     assert( e->Sym != e );
776     assert( e->Sym->Sym == e );
777     assert( e->Org != NULL );
778     assert( e->Dst != NULL );
779     assert( e->Lnext->Onext->Sym == e );
780     assert( e->Onext->Sym->Lnext == e );
781   }
782   assert( e->Sym->next == ePrev->Sym
783        && e->Sym == &mesh->eHeadSym
784        && e->Sym->Sym == e
785        && e->Org == NULL && e->Dst == NULL
786        && e->Lface == NULL && e->Rface == NULL );
787 }
788
789 #endif