2 * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008)
3 * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved.
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:
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.
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
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.
31 ** Author: Eric Veach, July 1994.
48 static GLUvertex
*allocVertex()
50 return (GLUvertex
*)memAlloc( sizeof( GLUvertex
));
53 static GLUface
*allocFace()
55 return (GLUface
*)memAlloc( sizeof( GLUface
));
58 /************************ Utility Routines ************************/
60 /* Allocate and free half-edges in pairs for efficiency.
61 * The *only* place that should use this fact is allocation/free.
63 typedef struct { GLUhalfEdge e
, eSym
; } EdgePair
;
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.
69 static GLUhalfEdge
*MakeEdge( GLUhalfEdge
*eNext
)
74 EdgePair
*pair
= (EdgePair
*)memAlloc( sizeof( EdgePair
));
75 if (pair
== NULL
) return NULL
;
80 /* Make sure eNext points to the first edge of the edge pair */
81 if( eNext
->Sym
< eNext
) { eNext
= eNext
->Sym
; }
83 /* Insert in circular doubly-linked list before eNext.
84 * Note that the prev pointer is stored in Sym->next.
86 ePrev
= eNext
->Sym
->next
;
90 eNext
->Sym
->next
= eSym
;
98 e
->activeRegion
= NULL
;
106 eSym
->activeRegion
= NULL
;
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.
117 static void Splice( GLUhalfEdge
*a
, GLUhalfEdge
*b
)
119 GLUhalfEdge
*aOnext
= a
->Onext
;
120 GLUhalfEdge
*bOnext
= b
->Onext
;
122 aOnext
->Sym
->Lnext
= b
;
123 bOnext
->Sym
->Lnext
= a
;
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.
134 static void MakeVertex( GLUvertex
*newVertex
,
135 GLUhalfEdge
*eOrig
, GLUvertex
*vNext
)
139 GLUvertex
*vNew
= newVertex
;
141 assert(vNew
!= NULL
);
143 /* insert in circular doubly-linked list before vNext */
150 vNew
->anEdge
= eOrig
;
152 /* leave coords, s, t undefined */
154 /* fix other edges on this vertex loop */
159 } while( e
!= eOrig
);
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.
168 static void MakeFace( GLUface
*newFace
, GLUhalfEdge
*eOrig
, GLUface
*fNext
)
172 GLUface
*fNew
= newFace
;
174 assert(fNew
!= NULL
);
176 /* insert in circular doubly-linked list before fNext */
183 fNew
->anEdge
= eOrig
;
186 fNew
->marked
= FALSE
;
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.
191 fNew
->inside
= fNext
->inside
;
193 /* fix other edges on this face loop */
198 } while( e
!= eOrig
);
201 /* KillEdge( eDel ) destroys an edge (the half-edges eDel and eDel->Sym),
202 * and removes from the global edge list.
204 static void KillEdge( GLUhalfEdge
*eDel
)
206 GLUhalfEdge
*ePrev
, *eNext
;
208 /* Half-edges are allocated in pairs, see EdgePair above */
209 if( eDel
->Sym
< eDel
) { eDel
= eDel
->Sym
; }
211 /* delete from circular doubly-linked list */
213 ePrev
= eDel
->Sym
->next
;
214 eNext
->Sym
->next
= ePrev
;
215 ePrev
->Sym
->next
= eNext
;
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.
224 static void KillVertex( GLUvertex
*vDel
, GLUvertex
*newOrg
)
226 GLUhalfEdge
*e
, *eStart
= vDel
->anEdge
;
227 GLUvertex
*vPrev
, *vNext
;
229 /* change the origin of all affected edges */
234 } while( e
!= eStart
);
236 /* delete from circular doubly-linked list */
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.
248 static void KillFace( GLUface
*fDel
, GLUface
*newLface
)
250 GLUhalfEdge
*e
, *eStart
= fDel
->anEdge
;
251 GLUface
*fPrev
, *fNext
;
253 /* change the left face of all affected edges */
258 } while( e
!= eStart
);
260 /* delete from circular doubly-linked list */
270 /****************** Basic Edge Operations **********************/
272 /* __gl_meshMakeEdge creates one edge, two vertices, and a loop (face).
273 * The loop consists of the two new half-edges.
275 GLUhalfEdge
*__gl_meshMakeEdge( GLUmesh
*mesh
)
277 GLUvertex
*newVertex1
= allocVertex();
278 GLUvertex
*newVertex2
= allocVertex();
279 GLUface
*newFace
= allocFace();
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
);
290 e
= MakeEdge( &mesh
->eHead
);
298 MakeVertex( newVertex1
, e
, &mesh
->vHead
);
299 MakeVertex( newVertex2
, e
->Sym
, &mesh
->vHead
);
300 MakeFace( newFace
, e
, &mesh
->fHead
);
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.
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.
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.
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.
328 int __gl_meshSplice( GLUhalfEdge
*eOrg
, GLUhalfEdge
*eDst
)
330 int joiningLoops
= FALSE
;
331 int joiningVertices
= FALSE
;
333 if( eOrg
== eDst
) return 1;
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
);
340 if( eDst
->Lface
!= eOrg
->Lface
) {
341 /* We are connecting two disjoint loops -- destroy eDst->Lface */
343 KillFace( eDst
->Lface
, eOrg
->Lface
);
346 /* Change the edge structure */
347 Splice( eDst
, eOrg
);
349 if( ! joiningVertices
) {
350 GLUvertex
*newVertex
= allocVertex();
351 if (newVertex
== NULL
) return 0;
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.
356 MakeVertex( newVertex
, eDst
, eOrg
->Org
);
357 eOrg
->Org
->anEdge
= eOrg
;
359 if( ! joiningLoops
) {
360 GLUface
*newFace
= allocFace();
361 if (newFace
== NULL
) return 0;
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.
366 MakeFace( newFace
, eDst
, eOrg
->Lface
);
367 eOrg
->Lface
->anEdge
= eOrg
;
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.
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.
384 int __gl_meshDelete( GLUhalfEdge
*eDel
)
386 GLUhalfEdge
*eDelSym
= eDel
->Sym
;
387 int joiningLoops
= FALSE
;
389 /* First step: disconnect the origin vertex eDel->Org. We make all
390 * changes to get a consistent mesh in this "intermediate" state.
392 if( eDel
->Lface
!= eDel
->Rface
) {
393 /* We are joining two loops into one -- remove the left face */
395 KillFace( eDel
->Lface
, eDel
->Rface
);
398 if( eDel
->Onext
== eDel
) {
399 KillVertex( eDel
->Org
, NULL
);
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
;
405 Splice( eDel
, eDel
->Oprev
);
406 if( ! joiningLoops
) {
407 GLUface
*newFace
= allocFace();
408 if (newFace
== NULL
) return 0;
410 /* We are splitting one loop into two -- create a new loop for eDel. */
411 MakeFace( newFace
, eDel
, eDel
->Lface
);
415 /* Claim: the mesh is now in a consistent state, except that eDel->Org
416 * may have been deleted. Now we disconnect eDel->Dst.
418 if( eDelSym
->Onext
== eDelSym
) {
419 KillVertex( eDelSym
->Org
, NULL
);
420 KillFace( eDelSym
->Lface
, NULL
);
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
);
428 /* Any isolated vertices or faces have already been freed. */
435 /******************** Other Edge Operations **********************/
437 /* All these routines can be implemented with the basic edge
438 * operations above. They are provided for convenience and efficiency.
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.
446 GLUhalfEdge
*__gl_meshAddEdgeVertex( GLUhalfEdge
*eOrg
)
448 GLUhalfEdge
*eNewSym
;
449 GLUhalfEdge
*eNew
= MakeEdge( eOrg
);
450 if (eNew
== NULL
) return NULL
;
454 /* Connect the new edge appropriately */
455 Splice( eNew
, eOrg
->Lnext
);
457 /* Set the vertex and face information */
458 eNew
->Org
= eOrg
->Dst
;
460 GLUvertex
*newVertex
= allocVertex();
461 if (newVertex
== NULL
) return NULL
;
463 MakeVertex( newVertex
, eNewSym
, eNew
->Org
);
465 eNew
->Lface
= eNewSym
->Lface
= eOrg
->Lface
;
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.
475 GLUhalfEdge
*__gl_meshSplitEdge( GLUhalfEdge
*eOrg
)
478 GLUhalfEdge
*tempHalfEdge
= __gl_meshAddEdgeVertex( eOrg
);
479 if (tempHalfEdge
== NULL
) return NULL
;
481 eNew
= tempHalfEdge
->Sym
;
483 /* Disconnect eOrg from eOrg->Dst and connect it to eNew->Org */
484 Splice( eOrg
->Sym
, eOrg
->Sym
->Oprev
);
485 Splice( eOrg
->Sym
, eNew
);
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
;
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.
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.
508 GLUhalfEdge
*__gl_meshConnect( GLUhalfEdge
*eOrg
, GLUhalfEdge
*eDst
)
510 GLUhalfEdge
*eNewSym
;
511 int joiningLoops
= FALSE
;
512 GLUhalfEdge
*eNew
= MakeEdge( eOrg
);
513 if (eNew
== NULL
) return NULL
;
517 if( eDst
->Lface
!= eOrg
->Lface
) {
518 /* We are connecting two disjoint loops -- destroy eDst->Lface */
520 KillFace( eDst
->Lface
, eOrg
->Lface
);
523 /* Connect the new edge appropriately */
524 Splice( eNew
, eOrg
->Lnext
);
525 Splice( eNewSym
, eDst
);
527 /* Set the vertex and face information */
528 eNew
->Org
= eOrg
->Dst
;
529 eNewSym
->Org
= eDst
->Org
;
530 eNew
->Lface
= eNewSym
->Lface
= eOrg
->Lface
;
532 /* Make sure the old face points to a valid half-edge */
533 eOrg
->Lface
->anEdge
= eNewSym
;
535 if( ! joiningLoops
) {
536 GLUface
*newFace
= allocFace();
537 if (newFace
== NULL
) return NULL
;
539 /* We split one loop into two -- the new loop is eNew->Lface */
540 MakeFace( newFace
, eNew
, eOrg
->Lface
);
546 /******************** Other Operations **********************/
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!
555 void __gl_meshZapFace( GLUface
*fZap
)
557 GLUhalfEdge
*eStart
= fZap
->anEdge
;
558 GLUhalfEdge
*e
, *eNext
, *eSym
;
559 GLUface
*fPrev
, *fNext
;
561 /* walk around face, deleting edges whose right face is also NULL */
562 eNext
= eStart
->Lnext
;
568 if( e
->Rface
== NULL
) {
569 /* delete the edge -- see __gl_MeshDelete above */
571 if( e
->Onext
== e
) {
572 KillVertex( e
->Org
, NULL
);
574 /* Make sure that e->Org points to a valid half-edge */
575 e
->Org
->anEdge
= e
->Onext
;
576 Splice( e
, e
->Oprev
);
579 if( eSym
->Onext
== eSym
) {
580 KillVertex( eSym
->Org
, NULL
);
582 /* Make sure that eSym->Org points to a valid half-edge */
583 eSym
->Org
->anEdge
= eSym
->Onext
;
584 Splice( eSym
, eSym
->Oprev
);
588 } while( e
!= eStart
);
590 /* delete from circular doubly-linked list */
600 /* __gl_meshNewMesh() creates a new mesh with no edges, no vertices,
601 * and no loops (what we usually call a "face").
603 GLUmesh
*__gl_meshNewMesh( void )
609 GLUmesh
*mesh
= (GLUmesh
*)memAlloc( sizeof( GLUmesh
));
617 eSym
= &mesh
->eHeadSym
;
619 v
->next
= v
->prev
= v
;
623 f
->next
= f
->prev
= f
;
637 e
->activeRegion
= NULL
;
646 eSym
->activeRegion
= NULL
;
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).
655 GLUmesh
*__gl_meshUnion( GLUmesh
*mesh1
, GLUmesh
*mesh2
)
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
;
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
;
672 if( v2
->next
!= v2
) {
673 v1
->prev
->next
= v2
->next
;
674 v2
->next
->prev
= v1
->prev
;
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
;
691 #ifdef DELETE_BY_ZAPPING
693 /* __gl_meshDeleteMesh( mesh ) will free all storage for any valid mesh.
695 void __gl_meshDeleteMesh( GLUmesh
*mesh
)
697 GLUface
*fHead
= &mesh
->fHead
;
699 while( fHead
->next
!= fHead
) {
700 __gl_meshZapFace( fHead
->next
);
702 assert( mesh
->vHead
.next
== &mesh
->vHead
);
709 /* __gl_meshDeleteMesh( mesh ) will free all storage for any valid mesh.
711 void __gl_meshDeleteMesh( GLUmesh
*mesh
)
714 GLUvertex
*v
, *vNext
;
715 GLUhalfEdge
*e
, *eNext
;
717 for( f
= mesh
->fHead
.next
; f
!= &mesh
->fHead
; f
= fNext
) {
722 for( v
= mesh
->vHead
.next
; v
!= &mesh
->vHead
; v
= vNext
) {
727 for( e
= mesh
->eHead
.next
; e
!= &mesh
->eHead
; e
= eNext
) {
728 /* One call frees both e and e->Sym (see EdgePair above) */
740 /* __gl_meshCheckMesh( mesh ) checks a mesh for self-consistency.
742 void __gl_meshCheckMesh( GLUmesh
*mesh
)
744 GLUface
*fHead
= &mesh
->fHead
;
745 GLUvertex
*vHead
= &mesh
->vHead
;
746 GLUhalfEdge
*eHead
= &mesh
->eHead
;
748 GLUvertex
*v
, *vPrev
;
749 GLUhalfEdge
*e
, *ePrev
;
752 for( fPrev
= fHead
; (f
= fPrev
->next
) != fHead
; fPrev
= f
) {
753 assert( f
->prev
== fPrev
);
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
);
762 } while( e
!= f
->anEdge
);
764 assert( f
->prev
== fPrev
&& f
->anEdge
== NULL
&& f
->data
== NULL
);
767 for( vPrev
= vHead
; (v
= vPrev
->next
) != vHead
; vPrev
= v
) {
768 assert( v
->prev
== vPrev
);
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
);
777 } while( e
!= v
->anEdge
);
779 assert( v
->prev
== vPrev
&& v
->anEdge
== NULL
&& v
->data
== NULL
);
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
);
791 assert( e
->Sym
->next
== ePrev
->Sym
792 && e
->Sym
== &mesh
->eHeadSym
794 && e
->Org
== NULL
&& e
->Dst
== NULL
795 && e
->Lface
== NULL
&& e
->Rface
== NULL
);