File indexing completed on 2024-03-24 15:17:33

0001 /*
0002 ** Author: Eric Veach, July 1994.
0003 **
0004 */
0005 
0006 #ifndef __mesh_h_
0007 #define __mesh_h_
0008 
0009 #include "glu.h"
0010 
0011 typedef struct GLUmesh GLUmesh;
0012 
0013 typedef struct GLUvertex GLUvertex;
0014 typedef struct GLUface GLUface;
0015 typedef struct GLUhalfEdge GLUhalfEdge;
0016 
0017 typedef struct ActiveRegion ActiveRegion; /* Internal data */
0018 
0019 /* The mesh structure is similar in spirit, notation, and operations
0020  * to the "quad-edge" structure (see L. Guibas and J. Stolfi, Primitives
0021  * for the manipulation of general subdivisions and the computation of
0022  * Voronoi diagrams, ACM Transactions on Graphics, 4(2):74-123, April 1985).
0023  * For a simplified description, see the course notes for CS348a,
0024  * "Mathematical Foundations of Computer Graphics", available at the
0025  * Stanford bookstore (and taught during the fall quarter).
0026  * The implementation also borrows a tiny subset of the graph-based approach
0027  * use in Mantyla's Geometric Work Bench (see M. Mantyla, An Introduction
0028  * to Sold Modeling, Computer Science Press, Rockville, Maryland, 1988).
0029  *
0030  * The fundamental data structure is the "half-edge".  Two half-edges
0031  * go together to make an edge, but they point in opposite directions.
0032  * Each half-edge has a pointer to its mate (the "symmetric" half-edge Sym),
0033  * its origin vertex (Org), the face on its left side (Lface), and the
0034  * adjacent half-edges in the CCW direction around the origin vertex
0035  * (Onext) and around the left face (Lnext).  There is also a "next"
0036  * pointer for the global edge list (see below).
0037  *
0038  * The notation used for mesh navigation:
0039  *  Sym   = the mate of a half-edge (same edge, but opposite direction)
0040  *  Onext = edge CCW around origin vertex (keep same origin)
0041  *  Dnext = edge CCW around destination vertex (keep same dest)
0042  *  Lnext = edge CCW around left face (dest becomes new origin)
0043  *  Rnext = edge CCW around right face (origin becomes new dest)
0044  *
0045  * "prev" means to substitute CW for CCW in the definitions above.
0046  *
0047  * The mesh keeps global lists of all vertices, faces, and edges,
0048  * stored as doubly-linked circular lists with a dummy header node.
0049  * The mesh stores pointers to these dummy headers (vHead, fHead, eHead).
0050  *
0051  * The circular edge list is special; since half-edges always occur
0052  * in pairs (e and e->Sym), each half-edge stores a pointer in only
0053  * one direction.  Starting at eHead and following the e->next pointers
0054  * will visit each *edge* once (ie. e or e->Sym, but not both).
0055  * e->Sym stores a pointer in the opposite direction, thus it is
0056  * always true that e->Sym->next->Sym->next == e.
0057  *
0058  * Each vertex has a pointer to next and previous vertices in the
0059  * circular list, and a pointer to a half-edge with this vertex as
0060  * the origin (NULL if this is the dummy header).  There is also a
0061  * field "data" for client data.
0062  *
0063  * Each face has a pointer to the next and previous faces in the
0064  * circular list, and a pointer to a half-edge with this face as
0065  * the left face (NULL if this is the dummy header).  There is also
0066  * a field "data" for client data.
0067  *
0068  * Note that what we call a "face" is really a loop; faces may consist
0069  * of more than one loop (ie. not simply connected), but there is no
0070  * record of this in the data structure.  The mesh may consist of
0071  * several disconnected regions, so it may not be possible to visit
0072  * the entire mesh by starting at a half-edge and traversing the edge
0073  * structure.
0074  *
0075  * The mesh does NOT support isolated vertices; a vertex is deleted along
0076  * with its last edge.  Similarly when two faces are merged, one of the
0077  * faces is deleted (see __gl_meshDelete below).  For mesh operations,
0078  * all face (loop) and vertex pointers must not be NULL.  However, once
0079  * mesh manipulation is finished, __gl_MeshZapFace can be used to delete
0080  * faces of the mesh, one at a time.  All external faces can be "zapped"
0081  * before the mesh is returned to the client; then a NULL face indicates
0082  * a region which is not part of the output polygon.
0083  */
0084 
0085 struct GLUvertex
0086 {
0087     GLUvertex *next;     /* next vertex (never NULL) */
0088     GLUvertex *prev;     /* previous vertex (never NULL) */
0089     GLUhalfEdge *anEdge; /* a half-edge with this origin */
0090     void *data;          /* client's data */
0091 
0092     /* Internal data (keep hidden) */
0093     GLdouble coords[3]; /* vertex location in 3D */
0094     GLdouble s, t;      /* projection onto the sweep plane */
0095     long pqHandle;      /* to allow deletion from priority queue */
0096 };
0097 
0098 struct GLUface
0099 {
0100     GLUface *next;       /* next face (never NULL) */
0101     GLUface *prev;       /* previous face (never NULL) */
0102     GLUhalfEdge *anEdge; /* a half edge with this left face */
0103     void *data;          /* room for client's data */
0104 
0105     /* Internal data (keep hidden) */
0106     GLUface *trail;   /* "stack" for conversion to strips */
0107     GLboolean marked; /* flag for conversion to strips */
0108     GLboolean inside; /* this face is in the polygon interior */
0109 };
0110 
0111 struct GLUhalfEdge
0112 {
0113     GLUhalfEdge *next;  /* doubly-linked list (prev==Sym->next) */
0114     GLUhalfEdge *Sym;   /* same edge, opposite direction */
0115     GLUhalfEdge *Onext; /* next edge CCW around origin */
0116     GLUhalfEdge *Lnext; /* next edge CCW around left face */
0117     GLUvertex *Org;     /* origin vertex (Overtex too long) */
0118     GLUface *Lface;     /* left face */
0119 
0120     /* Internal data (keep hidden) */
0121     ActiveRegion *activeRegion; /* a region with this upper edge (sweep.c) */
0122     int winding;                /* change in winding number when crossing
0123                                    from the right face to the left face */
0124 };
0125 
0126 #define Rface Sym->Lface
0127 #define Dst   Sym->Org
0128 
0129 #define Oprev Sym->Lnext
0130 #define Lprev Onext->Sym
0131 #define Dprev Lnext->Sym
0132 #define Rprev Sym->Onext
0133 #define Dnext Rprev->Sym /* 3 pointers */
0134 #define Rnext Oprev->Sym /* 3 pointers */
0135 
0136 struct GLUmesh
0137 {
0138     GLUvertex vHead;      /* dummy header for vertex list */
0139     GLUface fHead;        /* dummy header for face list */
0140     GLUhalfEdge eHead;    /* dummy header for edge list */
0141     GLUhalfEdge eHeadSym; /* and its symmetric counterpart */
0142 };
0143 
0144 /* The mesh operations below have three motivations: completeness,
0145  * convenience, and efficiency.  The basic mesh operations are MakeEdge,
0146  * Splice, and Delete.  All the other edge operations can be implemented
0147  * in terms of these.  The other operations are provided for convenience
0148  * and/or efficiency.
0149  *
0150  * When a face is split or a vertex is added, they are inserted into the
0151  * global list *before* the existing vertex or face (ie. e->Org or e->Lface).
0152  * This makes it easier to process all vertices or faces in the global lists
0153  * without worrying about processing the same data twice.  As a convenience,
0154  * when a face is split, the "inside" flag is copied from the old face.
0155  * Other internal data (v->data, v->activeRegion, f->data, f->marked,
0156  * f->trail, e->winding) is set to zero.
0157  *
0158  * ********************** Basic Edge Operations **************************
0159  *
0160  * __gl_meshMakeEdge( mesh ) creates one edge, two vertices, and a loop.
0161  * The loop (face) consists of the two new half-edges.
0162  *
0163  * __gl_meshSplice( eOrg, eDst ) is the basic operation for changing the
0164  * mesh connectivity and topology.  It changes the mesh so that
0165  *  eOrg->Onext <- OLD( eDst->Onext )
0166  *  eDst->Onext <- OLD( eOrg->Onext )
0167  * where OLD(...) means the value before the meshSplice operation.
0168  *
0169  * This can have two effects on the vertex structure:
0170  *  - if eOrg->Org != eDst->Org, the two vertices are merged together
0171  *  - if eOrg->Org == eDst->Org, the origin is split into two vertices
0172  * In both cases, eDst->Org is changed and eOrg->Org is untouched.
0173  *
0174  * Similarly (and independently) for the face structure,
0175  *  - if eOrg->Lface == eDst->Lface, one loop is split into two
0176  *  - if eOrg->Lface != eDst->Lface, two distinct loops are joined into one
0177  * In both cases, eDst->Lface is changed and eOrg->Lface is unaffected.
0178  *
0179  * __gl_meshDelete( eDel ) removes the edge eDel.  There are several cases:
0180  * if (eDel->Lface != eDel->Rface), we join two loops into one; the loop
0181  * eDel->Lface is deleted.  Otherwise, we are splitting one loop into two;
0182  * the newly created loop will contain eDel->Dst.  If the deletion of eDel
0183  * would create isolated vertices, those are deleted as well.
0184  *
0185  * ********************** Other Edge Operations **************************
0186  *
0187  * __gl_meshAddEdgeVertex( eOrg ) creates a new edge eNew such that
0188  * eNew == eOrg->Lnext, and eNew->Dst is a newly created vertex.
0189  * eOrg and eNew will have the same left face.
0190  *
0191  * __gl_meshSplitEdge( eOrg ) splits eOrg into two edges eOrg and eNew,
0192  * such that eNew == eOrg->Lnext.  The new vertex is eOrg->Dst == eNew->Org.
0193  * eOrg and eNew will have the same left face.
0194  *
0195  * __gl_meshConnect( eOrg, eDst ) creates a new edge from eOrg->Dst
0196  * to eDst->Org, and returns the corresponding half-edge eNew.
0197  * If eOrg->Lface == eDst->Lface, this splits one loop into two,
0198  * and the newly created loop is eNew->Lface.  Otherwise, two disjoint
0199  * loops are merged into one, and the loop eDst->Lface is destroyed.
0200  *
0201  * ************************ Other Operations *****************************
0202  *
0203  * __gl_meshNewMesh() creates a new mesh with no edges, no vertices,
0204  * and no loops (what we usually call a "face").
0205  *
0206  * __gl_meshUnion( mesh1, mesh2 ) forms the union of all structures in
0207  * both meshes, and returns the new mesh (the old meshes are destroyed).
0208  *
0209  * __gl_meshDeleteMesh( mesh ) will free all storage for any valid mesh.
0210  *
0211  * __gl_meshZapFace( fZap ) destroys a face and removes it from the
0212  * global face list.  All edges of fZap will have a NULL pointer as their
0213  * left face.  Any edges which also have a NULL pointer as their right face
0214  * are deleted entirely (along with any isolated vertices this produces).
0215  * An entire mesh can be deleted by zapping its faces, one at a time,
0216  * in any order.  Zapped faces cannot be used in further mesh operations!
0217  *
0218  * __gl_meshCheckMesh( mesh ) checks a mesh for self-consistency.
0219  */
0220 
0221 GLUhalfEdge *__gl_meshMakeEdge(GLUmesh *mesh);
0222 int __gl_meshSplice(GLUhalfEdge *eOrg, GLUhalfEdge *eDst);
0223 int __gl_meshDelete(GLUhalfEdge *eDel);
0224 
0225 GLUhalfEdge *__gl_meshAddEdgeVertex(GLUhalfEdge *eOrg);
0226 GLUhalfEdge *__gl_meshSplitEdge(GLUhalfEdge *eOrg);
0227 GLUhalfEdge *__gl_meshConnect(GLUhalfEdge *eOrg, GLUhalfEdge *eDst);
0228 
0229 GLUmesh *__gl_meshNewMesh(void);
0230 GLUmesh *__gl_meshUnion(GLUmesh *mesh1, GLUmesh *mesh2);
0231 void __gl_meshDeleteMesh(GLUmesh *mesh);
0232 void __gl_meshZapFace(GLUface *fZap);
0233 
0234 #ifdef NDEBUG
0235 #define __gl_meshCheckMesh(mesh)
0236 #else
0237 void __gl_meshCheckMesh(GLUmesh *mesh);
0238 #endif
0239 
0240 #endif