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
);
287 if (e
== NULL
) return NULL
;
289 MakeVertex( newVertex1
, e
, &mesh
->vHead
);
290 MakeVertex( newVertex2
, e
->Sym
, &mesh
->vHead
);
291 MakeFace( newFace
, e
, &mesh
->fHead
);
296 /* __gl_meshSplice( eOrg, eDst ) is the basic operation for changing the
297 * mesh connectivity and topology. It changes the mesh so that
298 * eOrg->Onext <- OLD( eDst->Onext )
299 * eDst->Onext <- OLD( eOrg->Onext )
300 * where OLD(...) means the value before the meshSplice operation.
302 * This can have two effects on the vertex structure:
303 * - if eOrg->Org != eDst->Org, the two vertices are merged together
304 * - if eOrg->Org == eDst->Org, the origin is split into two vertices
305 * In both cases, eDst->Org is changed and eOrg->Org is untouched.
307 * Similarly (and independently) for the face structure,
308 * - if eOrg->Lface == eDst->Lface, one loop is split into two
309 * - if eOrg->Lface != eDst->Lface, two distinct loops are joined into one
310 * In both cases, eDst->Lface is changed and eOrg->Lface is unaffected.
312 * Some special cases:
313 * If eDst == eOrg, the operation has no effect.
314 * If eDst == eOrg->Lnext, the new face will have a single edge.
315 * If eDst == eOrg->Lprev, the old face will have a single edge.
316 * If eDst == eOrg->Onext, the new vertex will have a single edge.
317 * If eDst == eOrg->Oprev, the old vertex will have a single edge.
319 int __gl_meshSplice( GLUhalfEdge
*eOrg
, GLUhalfEdge
*eDst
)
321 int joiningLoops
= FALSE
;
322 int joiningVertices
= FALSE
;
324 if( eOrg
== eDst
) return 1;
326 if( eDst
->Org
!= eOrg
->Org
) {
327 /* We are merging two disjoint vertices -- destroy eDst->Org */
328 joiningVertices
= TRUE
;
329 KillVertex( eDst
->Org
, eOrg
->Org
);
331 if( eDst
->Lface
!= eOrg
->Lface
) {
332 /* We are connecting two disjoint loops -- destroy eDst->Lface */
334 KillFace( eDst
->Lface
, eOrg
->Lface
);
337 /* Change the edge structure */
338 Splice( eDst
, eOrg
);
340 if( ! joiningVertices
) {
341 GLUvertex
*newVertex
= allocVertex();
342 if (newVertex
== NULL
) return 0;
344 /* We split one vertex into two -- the new vertex is eDst->Org.
345 * Make sure the old vertex points to a valid half-edge.
347 MakeVertex( newVertex
, eDst
, eOrg
->Org
);
348 eOrg
->Org
->anEdge
= eOrg
;
350 if( ! joiningLoops
) {
351 GLUface
*newFace
= allocFace();
352 if (newFace
== NULL
) return 0;
354 /* We split one loop into two -- the new loop is eDst->Lface.
355 * Make sure the old face points to a valid half-edge.
357 MakeFace( newFace
, eDst
, eOrg
->Lface
);
358 eOrg
->Lface
->anEdge
= eOrg
;
365 /* __gl_meshDelete( eDel ) removes the edge eDel. There are several cases:
366 * if (eDel->Lface != eDel->Rface), we join two loops into one; the loop
367 * eDel->Lface is deleted. Otherwise, we are splitting one loop into two;
368 * the newly created loop will contain eDel->Dst. If the deletion of eDel
369 * would create isolated vertices, those are deleted as well.
371 * This function could be implemented as two calls to __gl_meshSplice
372 * plus a few calls to memFree, but this would allocate and delete
373 * unnecessary vertices and faces.
375 int __gl_meshDelete( GLUhalfEdge
*eDel
)
377 GLUhalfEdge
*eDelSym
= eDel
->Sym
;
378 int joiningLoops
= FALSE
;
380 /* First step: disconnect the origin vertex eDel->Org. We make all
381 * changes to get a consistent mesh in this "intermediate" state.
383 if( eDel
->Lface
!= eDel
->Rface
) {
384 /* We are joining two loops into one -- remove the left face */
386 KillFace( eDel
->Lface
, eDel
->Rface
);
389 if( eDel
->Onext
== eDel
) {
390 KillVertex( eDel
->Org
, NULL
);
392 /* Make sure that eDel->Org and eDel->Rface point to valid half-edges */
393 eDel
->Rface
->anEdge
= eDel
->Oprev
;
394 eDel
->Org
->anEdge
= eDel
->Onext
;
396 Splice( eDel
, eDel
->Oprev
);
397 if( ! joiningLoops
) {
398 GLUface
*newFace
= allocFace();
399 if (newFace
== NULL
) return 0;
401 /* We are splitting one loop into two -- create a new loop for eDel. */
402 MakeFace( newFace
, eDel
, eDel
->Lface
);
406 /* Claim: the mesh is now in a consistent state, except that eDel->Org
407 * may have been deleted. Now we disconnect eDel->Dst.
409 if( eDelSym
->Onext
== eDelSym
) {
410 KillVertex( eDelSym
->Org
, NULL
);
411 KillFace( eDelSym
->Lface
, NULL
);
413 /* Make sure that eDel->Dst and eDel->Lface point to valid half-edges */
414 eDel
->Lface
->anEdge
= eDelSym
->Oprev
;
415 eDelSym
->Org
->anEdge
= eDelSym
->Onext
;
416 Splice( eDelSym
, eDelSym
->Oprev
);
419 /* Any isolated vertices or faces have already been freed. */
426 /******************** Other Edge Operations **********************/
428 /* All these routines can be implemented with the basic edge
429 * operations above. They are provided for convenience and efficiency.
433 /* __gl_meshAddEdgeVertex( eOrg ) creates a new edge eNew such that
434 * eNew == eOrg->Lnext, and eNew->Dst is a newly created vertex.
435 * eOrg and eNew will have the same left face.
437 GLUhalfEdge
*__gl_meshAddEdgeVertex( GLUhalfEdge
*eOrg
)
439 GLUhalfEdge
*eNewSym
;
440 GLUhalfEdge
*eNew
= MakeEdge( eOrg
);
441 if (eNew
== NULL
) return NULL
;
445 /* Connect the new edge appropriately */
446 Splice( eNew
, eOrg
->Lnext
);
448 /* Set the vertex and face information */
449 eNew
->Org
= eOrg
->Dst
;
451 GLUvertex
*newVertex
= allocVertex();
452 if (newVertex
== NULL
) return NULL
;
454 MakeVertex( newVertex
, eNewSym
, eNew
->Org
);
456 eNew
->Lface
= eNewSym
->Lface
= eOrg
->Lface
;
462 /* __gl_meshSplitEdge( eOrg ) splits eOrg into two edges eOrg and eNew,
463 * such that eNew == eOrg->Lnext. The new vertex is eOrg->Dst == eNew->Org.
464 * eOrg and eNew will have the same left face.
466 GLUhalfEdge
*__gl_meshSplitEdge( GLUhalfEdge
*eOrg
)
469 GLUhalfEdge
*tempHalfEdge
= __gl_meshAddEdgeVertex( eOrg
);
470 if (tempHalfEdge
== NULL
) return NULL
;
472 eNew
= tempHalfEdge
->Sym
;
474 /* Disconnect eOrg from eOrg->Dst and connect it to eNew->Org */
475 Splice( eOrg
->Sym
, eOrg
->Sym
->Oprev
);
476 Splice( eOrg
->Sym
, eNew
);
478 /* Set the vertex and face information */
479 eOrg
->Dst
= eNew
->Org
;
480 eNew
->Dst
->anEdge
= eNew
->Sym
; /* may have pointed to eOrg->Sym */
481 eNew
->Rface
= eOrg
->Rface
;
482 eNew
->winding
= eOrg
->winding
; /* copy old winding information */
483 eNew
->Sym
->winding
= eOrg
->Sym
->winding
;
489 /* __gl_meshConnect( eOrg, eDst ) creates a new edge from eOrg->Dst
490 * to eDst->Org, and returns the corresponding half-edge eNew.
491 * If eOrg->Lface == eDst->Lface, this splits one loop into two,
492 * and the newly created loop is eNew->Lface. Otherwise, two disjoint
493 * loops are merged into one, and the loop eDst->Lface is destroyed.
495 * If (eOrg == eDst), the new face will have only two edges.
496 * If (eOrg->Lnext == eDst), the old face is reduced to a single edge.
497 * If (eOrg->Lnext->Lnext == eDst), the old face is reduced to two edges.
499 GLUhalfEdge
*__gl_meshConnect( GLUhalfEdge
*eOrg
, GLUhalfEdge
*eDst
)
501 GLUhalfEdge
*eNewSym
;
502 int joiningLoops
= FALSE
;
503 GLUhalfEdge
*eNew
= MakeEdge( eOrg
);
504 if (eNew
== NULL
) return NULL
;
508 if( eDst
->Lface
!= eOrg
->Lface
) {
509 /* We are connecting two disjoint loops -- destroy eDst->Lface */
511 KillFace( eDst
->Lface
, eOrg
->Lface
);
514 /* Connect the new edge appropriately */
515 Splice( eNew
, eOrg
->Lnext
);
516 Splice( eNewSym
, eDst
);
518 /* Set the vertex and face information */
519 eNew
->Org
= eOrg
->Dst
;
520 eNewSym
->Org
= eDst
->Org
;
521 eNew
->Lface
= eNewSym
->Lface
= eOrg
->Lface
;
523 /* Make sure the old face points to a valid half-edge */
524 eOrg
->Lface
->anEdge
= eNewSym
;
526 if( ! joiningLoops
) {
527 GLUface
*newFace
= allocFace();
528 if (newFace
== NULL
) return NULL
;
530 /* We split one loop into two -- the new loop is eNew->Lface */
531 MakeFace( newFace
, eNew
, eOrg
->Lface
);
537 /******************** Other Operations **********************/
539 /* __gl_meshZapFace( fZap ) destroys a face and removes it from the
540 * global face list. All edges of fZap will have a NULL pointer as their
541 * left face. Any edges which also have a NULL pointer as their right face
542 * are deleted entirely (along with any isolated vertices this produces).
543 * An entire mesh can be deleted by zapping its faces, one at a time,
544 * in any order. Zapped faces cannot be used in further mesh operations!
546 void __gl_meshZapFace( GLUface
*fZap
)
548 GLUhalfEdge
*eStart
= fZap
->anEdge
;
549 GLUhalfEdge
*e
, *eNext
, *eSym
;
550 GLUface
*fPrev
, *fNext
;
552 /* walk around face, deleting edges whose right face is also NULL */
553 eNext
= eStart
->Lnext
;
559 if( e
->Rface
== NULL
) {
560 /* delete the edge -- see __gl_MeshDelete above */
562 if( e
->Onext
== e
) {
563 KillVertex( e
->Org
, NULL
);
565 /* Make sure that e->Org points to a valid half-edge */
566 e
->Org
->anEdge
= e
->Onext
;
567 Splice( e
, e
->Oprev
);
570 if( eSym
->Onext
== eSym
) {
571 KillVertex( eSym
->Org
, NULL
);
573 /* Make sure that eSym->Org points to a valid half-edge */
574 eSym
->Org
->anEdge
= eSym
->Onext
;
575 Splice( eSym
, eSym
->Oprev
);
579 } while( e
!= eStart
);
581 /* delete from circular doubly-linked list */
591 /* __gl_meshNewMesh() creates a new mesh with no edges, no vertices,
592 * and no loops (what we usually call a "face").
594 GLUmesh
*__gl_meshNewMesh( void )
600 GLUmesh
*mesh
= (GLUmesh
*)memAlloc( sizeof( GLUmesh
));
608 eSym
= &mesh
->eHeadSym
;
610 v
->next
= v
->prev
= v
;
614 f
->next
= f
->prev
= f
;
628 e
->activeRegion
= NULL
;
637 eSym
->activeRegion
= NULL
;
643 /* __gl_meshUnion( mesh1, mesh2 ) forms the union of all structures in
644 * both meshes, and returns the new mesh (the old meshes are destroyed).
646 GLUmesh
*__gl_meshUnion( GLUmesh
*mesh1
, GLUmesh
*mesh2
)
648 GLUface
*f1
= &mesh1
->fHead
;
649 GLUvertex
*v1
= &mesh1
->vHead
;
650 GLUhalfEdge
*e1
= &mesh1
->eHead
;
651 GLUface
*f2
= &mesh2
->fHead
;
652 GLUvertex
*v2
= &mesh2
->vHead
;
653 GLUhalfEdge
*e2
= &mesh2
->eHead
;
655 /* Add the faces, vertices, and edges of mesh2 to those of mesh1 */
656 if( f2
->next
!= f2
) {
657 f1
->prev
->next
= f2
->next
;
658 f2
->next
->prev
= f1
->prev
;
663 if( v2
->next
!= v2
) {
664 v1
->prev
->next
= v2
->next
;
665 v2
->next
->prev
= v1
->prev
;
670 if( e2
->next
!= e2
) {
671 e1
->Sym
->next
->Sym
->next
= e2
->next
;
672 e2
->next
->Sym
->next
= e1
->Sym
->next
;
673 e2
->Sym
->next
->Sym
->next
= e1
;
674 e1
->Sym
->next
= e2
->Sym
->next
;
682 #ifdef DELETE_BY_ZAPPING
684 /* __gl_meshDeleteMesh( mesh ) will free all storage for any valid mesh.
686 void __gl_meshDeleteMesh( GLUmesh
*mesh
)
688 GLUface
*fHead
= &mesh
->fHead
;
690 while( fHead
->next
!= fHead
) {
691 __gl_meshZapFace( fHead
->next
);
693 assert( mesh
->vHead
.next
== &mesh
->vHead
);
700 /* __gl_meshDeleteMesh( mesh ) will free all storage for any valid mesh.
702 void __gl_meshDeleteMesh( GLUmesh
*mesh
)
705 GLUvertex
*v
, *vNext
;
706 GLUhalfEdge
*e
, *eNext
;
708 for( f
= mesh
->fHead
.next
; f
!= &mesh
->fHead
; f
= fNext
) {
713 for( v
= mesh
->vHead
.next
; v
!= &mesh
->vHead
; v
= vNext
) {
718 for( e
= mesh
->eHead
.next
; e
!= &mesh
->eHead
; e
= eNext
) {
719 /* One call frees both e and e->Sym (see EdgePair above) */
731 /* __gl_meshCheckMesh( mesh ) checks a mesh for self-consistency.
733 void __gl_meshCheckMesh( GLUmesh
*mesh
)
735 GLUface
*fHead
= &mesh
->fHead
;
736 GLUvertex
*vHead
= &mesh
->vHead
;
737 GLUhalfEdge
*eHead
= &mesh
->eHead
;
739 GLUvertex
*v
, *vPrev
;
740 GLUhalfEdge
*e
, *ePrev
;
743 for( fPrev
= fHead
; (f
= fPrev
->next
) != fHead
; fPrev
= f
) {
744 assert( f
->prev
== fPrev
);
747 assert( e
->Sym
!= e
);
748 assert( e
->Sym
->Sym
== e
);
749 assert( e
->Lnext
->Onext
->Sym
== e
);
750 assert( e
->Onext
->Sym
->Lnext
== e
);
751 assert( e
->Lface
== f
);
753 } while( e
!= f
->anEdge
);
755 assert( f
->prev
== fPrev
&& f
->anEdge
== NULL
&& f
->data
== NULL
);
758 for( vPrev
= vHead
; (v
= vPrev
->next
) != vHead
; vPrev
= v
) {
759 assert( v
->prev
== vPrev
);
762 assert( e
->Sym
!= e
);
763 assert( e
->Sym
->Sym
== e
);
764 assert( e
->Lnext
->Onext
->Sym
== e
);
765 assert( e
->Onext
->Sym
->Lnext
== e
);
766 assert( e
->Org
== v
);
768 } while( e
!= v
->anEdge
);
770 assert( v
->prev
== vPrev
&& v
->anEdge
== NULL
&& v
->data
== NULL
);
773 for( ePrev
= eHead
; (e
= ePrev
->next
) != eHead
; ePrev
= e
) {
774 assert( e
->Sym
->next
== ePrev
->Sym
);
775 assert( e
->Sym
!= e
);
776 assert( e
->Sym
->Sym
== e
);
777 assert( e
->Org
!= NULL
);
778 assert( e
->Dst
!= NULL
);
779 assert( e
->Lnext
->Onext
->Sym
== e
);
780 assert( e
->Onext
->Sym
->Lnext
== e
);
782 assert( e
->Sym
->next
== ePrev
->Sym
783 && e
->Sym
== &mesh
->eHeadSym
785 && e
->Org
== NULL
&& e
->Dst
== NULL
786 && e
->Lface
== NULL
&& e
->Rface
== NULL
);