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