ReactOS 0.4.15-dev-8145-ga541a46
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/* Allocate and free half-edges in pairs for efficiency.
61 * The *only* place that should use this fact is allocation/free.
62 */
63typedef 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 */
70{
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 */
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 */
134static 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 */
168static 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 */
204static 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 */
224static 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 */
248static 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 */
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
#define NULL
Definition: types.h:112
#define TRUE
Definition: types.h:120
#define FALSE
Definition: types.h:117
GLUhalfEdge * __gl_meshMakeEdge(GLUmesh *mesh)
Definition: mesh.c:275
GLUhalfEdge * __gl_meshSplitEdge(GLUhalfEdge *eOrg)
Definition: mesh.c:475
static void MakeVertex(GLUvertex *newVertex, GLUhalfEdge *eOrig, GLUvertex *vNext)
Definition: mesh.c:134
static void KillVertex(GLUvertex *vDel, GLUvertex *newOrg)
Definition: mesh.c:224
static void Splice(GLUhalfEdge *a, GLUhalfEdge *b)
Definition: mesh.c:117
void __gl_meshCheckMesh(GLUmesh *mesh)
Definition: mesh.c:742
void __gl_meshZapFace(GLUface *fZap)
Definition: mesh.c:555
static void MakeFace(GLUface *newFace, GLUhalfEdge *eOrig, GLUface *fNext)
Definition: mesh.c:168
void __gl_meshDeleteMesh(GLUmesh *mesh)
Definition: mesh.c:711
GLUmesh * __gl_meshNewMesh(void)
Definition: mesh.c:603
GLUhalfEdge * __gl_meshConnect(GLUhalfEdge *eOrg, GLUhalfEdge *eDst)
Definition: mesh.c:508
int __gl_meshDelete(GLUhalfEdge *eDel)
Definition: mesh.c:384
GLUmesh * __gl_meshUnion(GLUmesh *mesh1, GLUmesh *mesh2)
Definition: mesh.c:655
int __gl_meshSplice(GLUhalfEdge *eOrg, GLUhalfEdge *eDst)
Definition: mesh.c:328
static GLUface * allocFace()
Definition: mesh.c:53
static void KillEdge(GLUhalfEdge *eDel)
Definition: mesh.c:204
static void KillFace(GLUface *fDel, GLUface *newLface)
Definition: mesh.c:248
static GLUhalfEdge * MakeEdge(GLUhalfEdge *eNext)
Definition: mesh.c:69
GLUhalfEdge * __gl_meshAddEdgeVertex(GLUhalfEdge *eOrg)
Definition: mesh.c:446
static GLUvertex * allocVertex()
Definition: mesh.c:48
#define assert(x)
Definition: debug.h:53
const GLdouble * v
Definition: gl.h:2040
GLfloat f
Definition: glext.h:7540
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
GLfloat GLfloat v1
Definition: glext.h:6062
GLfloat GLfloat GLfloat v2
Definition: glext.h:6063
#define e
Definition: ke_i.h:82
#define f
Definition: ke_i.h:83
#define a
Definition: ke_i.h:78
#define b
Definition: ke_i.h:79
#define memAlloc
Definition: memalloc.h:48
#define memFree
Definition: memalloc.h:41
#define f2(x, y, z)
Definition: sha1.c:31
#define f1(x, y, z)
Definition: sha1.c:30
Definition: mesh.c:63
GLUhalfEdge e
Definition: mesh.c:63
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:163
GLUvertex vHead
Definition: mesh.h:164
GLUhalfEdge eHead
Definition: mesh.h:166
GLUface fHead
Definition: mesh.h:165
GLUhalfEdge * anEdge
Definition: mesh.h:117
GLUvertex * next
Definition: mesh.h:115
void * data
Definition: mesh.h:118
GLUvertex * prev
Definition: mesh.h:116
struct define * next
Definition: compiler.c:65
Definition: mesh.c:198
Definition: _pair.h:47