File indexing completed on 2024-05-19 03:46:49
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