Logo ROOT  
Reference Guide
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
54{
55 return (GLUface *)memAlloc( sizeof( GLUface ));
56}
57
58/************************ Utility Routines ************************/
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 */
65{
67 GLUhalfEdge *eSym;
68 GLUhalfEdge *ePrev;
69 EdgePair *pair = (EdgePair *)memAlloc( 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 */
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 */
129static 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 */
163static 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 */
199static 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 memFree( 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 */
219static 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 memFree( 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 */
243static 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 memFree( 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 */
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 if (newVertex1 != NULL) memFree(newVertex1);
280 if (newVertex2 != NULL) memFree(newVertex2);
281 if (newFace != NULL) memFree(newFace);
282 return NULL;
283 }
284
285 e = MakeEdge( &mesh->eHead );
286 if (e == NULL) {
287 memFree(newVertex1);
288 memFree(newVertex2);
289 memFree(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 */
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 */
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 */
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 */
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 */
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 */
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 memFree( 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 */
599{
600 GLUvertex *v;
601 GLUface *f;
602 GLUhalfEdge *e;
603 GLUhalfEdge *eSym;
604 GLUmesh *mesh = (GLUmesh *)memAlloc( 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 */
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 memFree( 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 */
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 */
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 memFree( f );
715 }
716
717 for( v = mesh->vHead.next; v != &mesh->vHead; v = vNext ) {
718 vNext = v->next;
719 memFree( 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 memFree( e );
726 }
727
728 memFree( mesh );
729}
730
731#endif
732
733#ifndef NDEBUG
734
735/* __gl_meshCheckMesh( mesh ) checks a mesh for self-consistency.
736 */
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
#define b(i)
Definition: RSha256.hxx:100
#define f(i)
Definition: RSha256.hxx:104
#define e(i)
Definition: RSha256.hxx:103
TF1 * f1
Definition: legend1.C:11
#define memAlloc
Definition: memalloc.h:48
#define memFree
Definition: memalloc.h:41
GLUhalfEdge * __gl_meshMakeEdge(GLUmesh *mesh)
Definition: mesh.c:270
GLUhalfEdge * __gl_meshSplitEdge(GLUhalfEdge *eOrg)
Definition: mesh.c:470
static void MakeVertex(GLUvertex *newVertex, GLUhalfEdge *eOrig, GLUvertex *vNext)
Definition: mesh.c:129
static void KillVertex(GLUvertex *vDel, GLUvertex *newOrg)
Definition: mesh.c:219
static void Splice(GLUhalfEdge *a, GLUhalfEdge *b)
Definition: mesh.c:112
void __gl_meshCheckMesh(GLUmesh *mesh)
Definition: mesh.c:737
void __gl_meshZapFace(GLUface *fZap)
Definition: mesh.c:550
static void MakeFace(GLUface *newFace, GLUhalfEdge *eOrig, GLUface *fNext)
Definition: mesh.c:163
void __gl_meshDeleteMesh(GLUmesh *mesh)
Definition: mesh.c:706
GLUmesh * __gl_meshNewMesh(void)
Definition: mesh.c:598
GLUhalfEdge * __gl_meshConnect(GLUhalfEdge *eOrg, GLUhalfEdge *eDst)
Definition: mesh.c:503
int __gl_meshDelete(GLUhalfEdge *eDel)
Definition: mesh.c:379
#define TRUE
Definition: mesh.c:42
#define FALSE
Definition: mesh.c:45
GLUmesh * __gl_meshUnion(GLUmesh *mesh1, GLUmesh *mesh2)
Definition: mesh.c:650
int __gl_meshSplice(GLUhalfEdge *eOrg, GLUhalfEdge *eDst)
Definition: mesh.c:323
static GLUface * allocFace()
Definition: mesh.c:53
static void KillEdge(GLUhalfEdge *eDel)
Definition: mesh.c:199
static void KillFace(GLUface *fDel, GLUface *newLface)
Definition: mesh.c:243
static GLUhalfEdge * MakeEdge(GLUhalfEdge *eNext)
Definition: mesh.c:64
GLUhalfEdge * __gl_meshAddEdgeVertex(GLUhalfEdge *eOrg)
Definition: mesh.c:441
static GLUvertex * allocVertex()
Definition: mesh.c:48
Definition: mesh.h:155
GLUhalfEdge eSym
Definition: mesh.h:155
GLUhalfEdge e
Definition: mesh.h:155
Definition: mesh.h:126
GLboolean marked
Definition: mesh.h:134
GLUface * trail
Definition: mesh.h:133
GLUhalfEdge * anEdge
Definition: mesh.h:129
GLUface * prev
Definition: mesh.h:128
void * data
Definition: mesh.h:130
GLboolean inside
Definition: mesh.h:135
GLUface * next
Definition: mesh.h:127
GLUhalfEdge * Lnext
Definition: mesh.h:142
GLUvertex * Org
Definition: mesh.h:143
GLUhalfEdge * Onext
Definition: mesh.h:141
ActiveRegion * activeRegion
Definition: mesh.h:147
GLUhalfEdge * Sym
Definition: mesh.h:140
GLUface * Lface
Definition: mesh.h:144
GLUhalfEdge * next
Definition: mesh.h:139
int winding
Definition: mesh.h:148
Definition: mesh.h:168
GLUvertex vHead
Definition: mesh.h:169
GLUhalfEdge eHead
Definition: mesh.h:171
GLUface fHead
Definition: mesh.h:170
GLUhalfEdge * anEdge
Definition: mesh.h:117
GLUvertex * next
Definition: mesh.h:115
void * data
Definition: mesh.h:118
GLUvertex * prev
Definition: mesh.h:116
Definition: triangle.c:632
auto * a
Definition: textangle.C:12