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.
44 static GLUvertex
*allocVertex()
46 return (GLUvertex
*)memAlloc( sizeof( GLUvertex
));
49 static GLUface
*allocFace()
51 return (GLUface
*)memAlloc( sizeof( GLUface
));
54 /************************ Utility Routines ************************/
56 /* Allocate and free half-edges in pairs for efficiency.
57 * The *only* place that should use this fact is allocation/free.
59 typedef struct { GLUhalfEdge e
, eSym
; } EdgePair
;
61 /* MakeEdge creates a new pair of half-edges which form their own loop.
62 * No vertex or face structures are allocated, but these must be assigned
63 * before the current edge operation is completed.
65 static GLUhalfEdge
*MakeEdge( GLUhalfEdge
*eNext
)
70 EdgePair
*pair
= (EdgePair
*)memAlloc( sizeof( EdgePair
));
71 if (pair
== NULL
) return NULL
;
76 /* Make sure eNext points to the first edge of the edge pair */
77 if( eNext
->Sym
< eNext
) { eNext
= eNext
->Sym
; }
79 /* Insert in circular doubly-linked list before eNext.
80 * Note that the prev pointer is stored in Sym->next.
82 ePrev
= eNext
->Sym
->next
;
86 eNext
->Sym
->next
= eSym
;
94 e
->activeRegion
= NULL
;
102 eSym
->activeRegion
= NULL
;
107 /* Splice( a, b ) is best described by the Guibas/Stolfi paper or the
108 * CS348a notes (see mesh.h). Basically it modifies the mesh so that
109 * a->Onext and b->Onext are exchanged. This can have various effects
110 * depending on whether a and b belong to different face or vertex rings.
111 * For more explanation see __gl_meshSplice() below.
113 static void Splice( GLUhalfEdge
*a
, GLUhalfEdge
*b
)
115 GLUhalfEdge
*aOnext
= a
->Onext
;
116 GLUhalfEdge
*bOnext
= b
->Onext
;
118 aOnext
->Sym
->Lnext
= b
;
119 bOnext
->Sym
->Lnext
= a
;
124 /* MakeVertex( newVertex, eOrig, vNext ) attaches a new vertex and makes it the
125 * origin of all edges in the vertex loop to which eOrig belongs. "vNext" gives
126 * a place to insert the new vertex in the global vertex list. We insert
127 * the new vertex *before* vNext so that algorithms which walk the vertex
128 * list will not see the newly created vertices.
130 static void MakeVertex( GLUvertex
*newVertex
,
131 GLUhalfEdge
*eOrig
, GLUvertex
*vNext
)
135 GLUvertex
*vNew
= newVertex
;
137 assert(vNew
!= NULL
);
139 /* insert in circular doubly-linked list before vNext */
146 vNew
->anEdge
= eOrig
;
148 /* leave coords, s, t undefined */
150 /* fix other edges on this vertex loop */
155 } while( e
!= eOrig
);
158 /* MakeFace( newFace, eOrig, fNext ) attaches a new face and makes it the left
159 * face of all edges in the face loop to which eOrig belongs. "fNext" gives
160 * a place to insert the new face in the global face list. We insert
161 * the new face *before* fNext so that algorithms which walk the face
162 * list will not see the newly created faces.
164 static void MakeFace( GLUface
*newFace
, GLUhalfEdge
*eOrig
, GLUface
*fNext
)
168 GLUface
*fNew
= newFace
;
170 assert(fNew
!= NULL
);
172 /* insert in circular doubly-linked list before fNext */
179 fNew
->anEdge
= eOrig
;
182 fNew
->marked
= FALSE
;
184 /* The new face is marked "inside" if the old one was. This is a
185 * convenience for the common case where a face has been split in two.
187 fNew
->inside
= fNext
->inside
;
189 /* fix other edges on this face loop */
194 } while( e
!= eOrig
);
197 /* KillEdge( eDel ) destroys an edge (the half-edges eDel and eDel->Sym),
198 * and removes from the global edge list.
200 static void KillEdge( GLUhalfEdge
*eDel
)
202 GLUhalfEdge
*ePrev
, *eNext
;
204 /* Half-edges are allocated in pairs, see EdgePair above */
205 if( eDel
->Sym
< eDel
) { eDel
= eDel
->Sym
; }
207 /* delete from circular doubly-linked list */
209 ePrev
= eDel
->Sym
->next
;
210 eNext
->Sym
->next
= ePrev
;
211 ePrev
->Sym
->next
= eNext
;
217 /* KillVertex( vDel ) destroys a vertex and removes it from the global
218 * vertex list. It updates the vertex loop to point to a given new vertex.
220 static void KillVertex( GLUvertex
*vDel
, GLUvertex
*newOrg
)
222 GLUhalfEdge
*e
, *eStart
= vDel
->anEdge
;
223 GLUvertex
*vPrev
, *vNext
;
225 /* change the origin of all affected edges */
230 } while( e
!= eStart
);
232 /* delete from circular doubly-linked list */
241 /* KillFace( fDel ) destroys a face and removes it from the global face
242 * list. It updates the face loop to point to a given new face.
244 static void KillFace( GLUface
*fDel
, GLUface
*newLface
)
246 GLUhalfEdge
*e
, *eStart
= fDel
->anEdge
;
247 GLUface
*fPrev
, *fNext
;
249 /* change the left face of all affected edges */
254 } while( e
!= eStart
);
256 /* delete from circular doubly-linked list */
266 /****************** Basic Edge Operations **********************/
268 /* __gl_meshMakeEdge creates one edge, two vertices, and a loop (face).
269 * The loop consists of the two new half-edges.
271 GLUhalfEdge
*__gl_meshMakeEdge( GLUmesh
*mesh
)
273 GLUvertex
*newVertex1
= allocVertex();
274 GLUvertex
*newVertex2
= allocVertex();
275 GLUface
*newFace
= allocFace();
278 /* if any one is null then all get freed */
279 if (newVertex1
== NULL
|| newVertex2
== NULL
|| newFace
== NULL
) {
280 if (newVertex1
!= NULL
) memFree(newVertex1
);
281 if (newVertex2
!= NULL
) memFree(newVertex2
);
282 if (newFace
!= NULL
) memFree(newFace
);
286 e
= MakeEdge( &mesh
->eHead
);
294 MakeVertex( newVertex1
, e
, &mesh
->vHead
);
295 MakeVertex( newVertex2
, e
->Sym
, &mesh
->vHead
);
296 MakeFace( newFace
, e
, &mesh
->fHead
);
301 /* __gl_meshSplice( eOrg, eDst ) is the basic operation for changing the
302 * mesh connectivity and topology. It changes the mesh so that
303 * eOrg->Onext <- OLD( eDst->Onext )
304 * eDst->Onext <- OLD( eOrg->Onext )
305 * where OLD(...) means the value before the meshSplice operation.
307 * This can have two effects on the vertex structure:
308 * - if eOrg->Org != eDst->Org, the two vertices are merged together
309 * - if eOrg->Org == eDst->Org, the origin is split into two vertices
310 * In both cases, eDst->Org is changed and eOrg->Org is untouched.
312 * Similarly (and independently) for the face structure,
313 * - if eOrg->Lface == eDst->Lface, one loop is split into two
314 * - if eOrg->Lface != eDst->Lface, two distinct loops are joined into one
315 * In both cases, eDst->Lface is changed and eOrg->Lface is unaffected.
317 * Some special cases:
318 * If eDst == eOrg, the operation has no effect.
319 * If eDst == eOrg->Lnext, the new face will have a single edge.
320 * If eDst == eOrg->Lprev, the old face will have a single edge.
321 * If eDst == eOrg->Onext, the new vertex will have a single edge.
322 * If eDst == eOrg->Oprev, the old vertex will have a single edge.
324 int __gl_meshSplice( GLUhalfEdge
*eOrg
, GLUhalfEdge
*eDst
)
326 int joiningLoops
= FALSE
;
327 int joiningVertices
= FALSE
;
329 if( eOrg
== eDst
) return 1;
331 if( eDst
->Org
!= eOrg
->Org
) {
332 /* We are merging two disjoint vertices -- destroy eDst->Org */
333 joiningVertices
= TRUE
;
334 KillVertex( eDst
->Org
, eOrg
->Org
);
336 if( eDst
->Lface
!= eOrg
->Lface
) {
337 /* We are connecting two disjoint loops -- destroy eDst->Lface */
339 KillFace( eDst
->Lface
, eOrg
->Lface
);
342 /* Change the edge structure */
343 Splice( eDst
, eOrg
);
345 if( ! joiningVertices
) {
346 GLUvertex
*newVertex
= allocVertex();
347 if (newVertex
== NULL
) return 0;
349 /* We split one vertex into two -- the new vertex is eDst->Org.
350 * Make sure the old vertex points to a valid half-edge.
352 MakeVertex( newVertex
, eDst
, eOrg
->Org
);
353 eOrg
->Org
->anEdge
= eOrg
;
355 if( ! joiningLoops
) {
356 GLUface
*newFace
= allocFace();
357 if (newFace
== NULL
) return 0;
359 /* We split one loop into two -- the new loop is eDst->Lface.
360 * Make sure the old face points to a valid half-edge.
362 MakeFace( newFace
, eDst
, eOrg
->Lface
);
363 eOrg
->Lface
->anEdge
= eOrg
;
370 /* __gl_meshDelete( eDel ) removes the edge eDel. There are several cases:
371 * if (eDel->Lface != eDel->Rface), we join two loops into one; the loop
372 * eDel->Lface is deleted. Otherwise, we are splitting one loop into two;
373 * the newly created loop will contain eDel->Dst. If the deletion of eDel
374 * would create isolated vertices, those are deleted as well.
376 * This function could be implemented as two calls to __gl_meshSplice
377 * plus a few calls to memFree, but this would allocate and delete
378 * unnecessary vertices and faces.
380 int __gl_meshDelete( GLUhalfEdge
*eDel
)
382 GLUhalfEdge
*eDelSym
= eDel
->Sym
;
383 int joiningLoops
= FALSE
;
385 /* First step: disconnect the origin vertex eDel->Org. We make all
386 * changes to get a consistent mesh in this "intermediate" state.
388 if( eDel
->Lface
!= eDel
->Rface
) {
389 /* We are joining two loops into one -- remove the left face */
391 KillFace( eDel
->Lface
, eDel
->Rface
);
394 if( eDel
->Onext
== eDel
) {
395 KillVertex( eDel
->Org
, NULL
);
397 /* Make sure that eDel->Org and eDel->Rface point to valid half-edges */
398 eDel
->Rface
->anEdge
= eDel
->Oprev
;
399 eDel
->Org
->anEdge
= eDel
->Onext
;
401 Splice( eDel
, eDel
->Oprev
);
402 if( ! joiningLoops
) {
403 GLUface
*newFace
= allocFace();
404 if (newFace
== NULL
) return 0;
406 /* We are splitting one loop into two -- create a new loop for eDel. */
407 MakeFace( newFace
, eDel
, eDel
->Lface
);
411 /* Claim: the mesh is now in a consistent state, except that eDel->Org
412 * may have been deleted. Now we disconnect eDel->Dst.
414 if( eDelSym
->Onext
== eDelSym
) {
415 KillVertex( eDelSym
->Org
, NULL
);
416 KillFace( eDelSym
->Lface
, NULL
);
418 /* Make sure that eDel->Dst and eDel->Lface point to valid half-edges */
419 eDel
->Lface
->anEdge
= eDelSym
->Oprev
;
420 eDelSym
->Org
->anEdge
= eDelSym
->Onext
;
421 Splice( eDelSym
, eDelSym
->Oprev
);
424 /* Any isolated vertices or faces have already been freed. */
431 /******************** Other Edge Operations **********************/
433 /* All these routines can be implemented with the basic edge
434 * operations above. They are provided for convenience and efficiency.
438 /* __gl_meshAddEdgeVertex( eOrg ) creates a new edge eNew such that
439 * eNew == eOrg->Lnext, and eNew->Dst is a newly created vertex.
440 * eOrg and eNew will have the same left face.
442 GLUhalfEdge
*__gl_meshAddEdgeVertex( GLUhalfEdge
*eOrg
)
444 GLUhalfEdge
*eNewSym
;
445 GLUhalfEdge
*eNew
= MakeEdge( eOrg
);
446 if (eNew
== NULL
) return NULL
;
450 /* Connect the new edge appropriately */
451 Splice( eNew
, eOrg
->Lnext
);
453 /* Set the vertex and face information */
454 eNew
->Org
= eOrg
->Dst
;
456 GLUvertex
*newVertex
= allocVertex();
457 if (newVertex
== NULL
) return NULL
;
459 MakeVertex( newVertex
, eNewSym
, eNew
->Org
);
461 eNew
->Lface
= eNewSym
->Lface
= eOrg
->Lface
;
467 /* __gl_meshSplitEdge( eOrg ) splits eOrg into two edges eOrg and eNew,
468 * such that eNew == eOrg->Lnext. The new vertex is eOrg->Dst == eNew->Org.
469 * eOrg and eNew will have the same left face.
471 GLUhalfEdge
*__gl_meshSplitEdge( GLUhalfEdge
*eOrg
)
474 GLUhalfEdge
*tempHalfEdge
= __gl_meshAddEdgeVertex( eOrg
);
475 if (tempHalfEdge
== NULL
) return NULL
;
477 eNew
= tempHalfEdge
->Sym
;
479 /* Disconnect eOrg from eOrg->Dst and connect it to eNew->Org */
480 Splice( eOrg
->Sym
, eOrg
->Sym
->Oprev
);
481 Splice( eOrg
->Sym
, eNew
);
483 /* Set the vertex and face information */
484 eOrg
->Dst
= eNew
->Org
;
485 eNew
->Dst
->anEdge
= eNew
->Sym
; /* may have pointed to eOrg->Sym */
486 eNew
->Rface
= eOrg
->Rface
;
487 eNew
->winding
= eOrg
->winding
; /* copy old winding information */
488 eNew
->Sym
->winding
= eOrg
->Sym
->winding
;
494 /* __gl_meshConnect( eOrg, eDst ) creates a new edge from eOrg->Dst
495 * to eDst->Org, and returns the corresponding half-edge eNew.
496 * If eOrg->Lface == eDst->Lface, this splits one loop into two,
497 * and the newly created loop is eNew->Lface. Otherwise, two disjoint
498 * loops are merged into one, and the loop eDst->Lface is destroyed.
500 * If (eOrg == eDst), the new face will have only two edges.
501 * If (eOrg->Lnext == eDst), the old face is reduced to a single edge.
502 * If (eOrg->Lnext->Lnext == eDst), the old face is reduced to two edges.
504 GLUhalfEdge
*__gl_meshConnect( GLUhalfEdge
*eOrg
, GLUhalfEdge
*eDst
)
506 GLUhalfEdge
*eNewSym
;
507 int joiningLoops
= FALSE
;
508 GLUhalfEdge
*eNew
= MakeEdge( eOrg
);
509 if (eNew
== NULL
) return NULL
;
513 if( eDst
->Lface
!= eOrg
->Lface
) {
514 /* We are connecting two disjoint loops -- destroy eDst->Lface */
516 KillFace( eDst
->Lface
, eOrg
->Lface
);
519 /* Connect the new edge appropriately */
520 Splice( eNew
, eOrg
->Lnext
);
521 Splice( eNewSym
, eDst
);
523 /* Set the vertex and face information */
524 eNew
->Org
= eOrg
->Dst
;
525 eNewSym
->Org
= eDst
->Org
;
526 eNew
->Lface
= eNewSym
->Lface
= eOrg
->Lface
;
528 /* Make sure the old face points to a valid half-edge */
529 eOrg
->Lface
->anEdge
= eNewSym
;
531 if( ! joiningLoops
) {
532 GLUface
*newFace
= allocFace();
533 if (newFace
== NULL
) return NULL
;
535 /* We split one loop into two -- the new loop is eNew->Lface */
536 MakeFace( newFace
, eNew
, eOrg
->Lface
);
542 /******************** Other Operations **********************/
544 /* __gl_meshZapFace( fZap ) destroys a face and removes it from the
545 * global face list. All edges of fZap will have a NULL pointer as their
546 * left face. Any edges which also have a NULL pointer as their right face
547 * are deleted entirely (along with any isolated vertices this produces).
548 * An entire mesh can be deleted by zapping its faces, one at a time,
549 * in any order. Zapped faces cannot be used in further mesh operations!
551 void __gl_meshZapFace( GLUface
*fZap
)
553 GLUhalfEdge
*eStart
= fZap
->anEdge
;
554 GLUhalfEdge
*e
, *eNext
, *eSym
;
555 GLUface
*fPrev
, *fNext
;
557 /* walk around face, deleting edges whose right face is also NULL */
558 eNext
= eStart
->Lnext
;
564 if( e
->Rface
== NULL
) {
565 /* delete the edge -- see __gl_MeshDelete above */
567 if( e
->Onext
== e
) {
568 KillVertex( e
->Org
, NULL
);
570 /* Make sure that e->Org points to a valid half-edge */
571 e
->Org
->anEdge
= e
->Onext
;
572 Splice( e
, e
->Oprev
);
575 if( eSym
->Onext
== eSym
) {
576 KillVertex( eSym
->Org
, NULL
);
578 /* Make sure that eSym->Org points to a valid half-edge */
579 eSym
->Org
->anEdge
= eSym
->Onext
;
580 Splice( eSym
, eSym
->Oprev
);
584 } while( e
!= eStart
);
586 /* delete from circular doubly-linked list */
596 /* __gl_meshNewMesh() creates a new mesh with no edges, no vertices,
597 * and no loops (what we usually call a "face").
599 GLUmesh
*__gl_meshNewMesh( void )
605 GLUmesh
*mesh
= (GLUmesh
*)memAlloc( sizeof( GLUmesh
));
613 eSym
= &mesh
->eHeadSym
;
615 v
->next
= v
->prev
= v
;
619 f
->next
= f
->prev
= f
;
633 e
->activeRegion
= NULL
;
642 eSym
->activeRegion
= NULL
;
648 /* __gl_meshUnion( mesh1, mesh2 ) forms the union of all structures in
649 * both meshes, and returns the new mesh (the old meshes are destroyed).
651 GLUmesh
*__gl_meshUnion( GLUmesh
*mesh1
, GLUmesh
*mesh2
)
653 GLUface
*f1
= &mesh1
->fHead
;
654 GLUvertex
*v1
= &mesh1
->vHead
;
655 GLUhalfEdge
*e1
= &mesh1
->eHead
;
656 GLUface
*f2
= &mesh2
->fHead
;
657 GLUvertex
*v2
= &mesh2
->vHead
;
658 GLUhalfEdge
*e2
= &mesh2
->eHead
;
660 /* Add the faces, vertices, and edges of mesh2 to those of mesh1 */
661 if( f2
->next
!= f2
) {
662 f1
->prev
->next
= f2
->next
;
663 f2
->next
->prev
= f1
->prev
;
668 if( v2
->next
!= v2
) {
669 v1
->prev
->next
= v2
->next
;
670 v2
->next
->prev
= v1
->prev
;
675 if( e2
->next
!= e2
) {
676 e1
->Sym
->next
->Sym
->next
= e2
->next
;
677 e2
->next
->Sym
->next
= e1
->Sym
->next
;
678 e2
->Sym
->next
->Sym
->next
= e1
;
679 e1
->Sym
->next
= e2
->Sym
->next
;
687 #ifdef DELETE_BY_ZAPPING
689 /* __gl_meshDeleteMesh( mesh ) will free all storage for any valid mesh.
691 void __gl_meshDeleteMesh( GLUmesh
*mesh
)
693 GLUface
*fHead
= &mesh
->fHead
;
695 while( fHead
->next
!= fHead
) {
696 __gl_meshZapFace( fHead
->next
);
698 assert( mesh
->vHead
.next
== &mesh
->vHead
);
705 /* __gl_meshDeleteMesh( mesh ) will free all storage for any valid mesh.
707 void __gl_meshDeleteMesh( GLUmesh
*mesh
)
710 GLUvertex
*v
, *vNext
;
711 GLUhalfEdge
*e
, *eNext
;
713 for( f
= mesh
->fHead
.next
; f
!= &mesh
->fHead
; f
= fNext
) {
718 for( v
= mesh
->vHead
.next
; v
!= &mesh
->vHead
; v
= vNext
) {
723 for( e
= mesh
->eHead
.next
; e
!= &mesh
->eHead
; e
= eNext
) {
724 /* One call frees both e and e->Sym (see EdgePair above) */
736 /* __gl_meshCheckMesh( mesh ) checks a mesh for self-consistency.
738 void __gl_meshCheckMesh( GLUmesh
*mesh
)
740 GLUface
*fHead
= &mesh
->fHead
;
741 GLUvertex
*vHead
= &mesh
->vHead
;
742 GLUhalfEdge
*eHead
= &mesh
->eHead
;
744 GLUvertex
*v
, *vPrev
;
745 GLUhalfEdge
*e
, *ePrev
;
748 for( fPrev
= fHead
; (f
= fPrev
->next
) != fHead
; fPrev
= f
) {
749 assert( f
->prev
== fPrev
);
752 assert( e
->Sym
!= e
);
753 assert( e
->Sym
->Sym
== e
);
754 assert( e
->Lnext
->Onext
->Sym
== e
);
755 assert( e
->Onext
->Sym
->Lnext
== e
);
756 assert( e
->Lface
== f
);
758 } while( e
!= f
->anEdge
);
760 assert( f
->prev
== fPrev
&& f
->anEdge
== NULL
&& f
->data
== NULL
);
763 for( vPrev
= vHead
; (v
= vPrev
->next
) != vHead
; vPrev
= v
) {
764 assert( v
->prev
== vPrev
);
767 assert( e
->Sym
!= e
);
768 assert( e
->Sym
->Sym
== e
);
769 assert( e
->Lnext
->Onext
->Sym
== e
);
770 assert( e
->Onext
->Sym
->Lnext
== e
);
771 assert( e
->Org
== v
);
773 } while( e
!= v
->anEdge
);
775 assert( v
->prev
== vPrev
&& v
->anEdge
== NULL
&& v
->data
== NULL
);
778 for( ePrev
= eHead
; (e
= ePrev
->next
) != eHead
; ePrev
= e
) {
779 assert( e
->Sym
->next
== ePrev
->Sym
);
780 assert( e
->Sym
!= e
);
781 assert( e
->Sym
->Sym
== e
);
782 assert( e
->Org
!= NULL
);
783 assert( e
->Dst
!= NULL
);
784 assert( e
->Lnext
->Onext
->Sym
== e
);
785 assert( e
->Onext
->Sym
->Lnext
== e
);
787 assert( e
->Sym
->next
== ePrev
->Sym
788 && e
->Sym
== &mesh
->eHeadSym
790 && e
->Org
== NULL
&& e
->Dst
== NULL
791 && e
->Lface
== NULL
&& e
->Rface
== NULL
);