1 /* 2 * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008) 3 * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved. 4 * 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: 11 * 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. 16 * 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 23 * SOFTWARE. 24 * 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. 29 */ 30 /* 31 ** Author: Eric Veach, July 1994. 32 ** 33 */ 34 35 #ifndef __mesh_h_ 36 #define __mesh_h_ 37 38 #include <GL/glu.h> 39 40 typedef struct GLUmesh GLUmesh; 41 42 typedef struct GLUvertex GLUvertex; 43 typedef struct GLUface GLUface; 44 typedef struct GLUhalfEdge GLUhalfEdge; 45 46 typedef struct ActiveRegion ActiveRegion; /* Internal data */ 47 48 /* The mesh structure is similar in spirit, notation, and operations 49 * to the "quad-edge" structure (see L. Guibas and J. Stolfi, Primitives 50 * for the manipulation of general subdivisions and the computation of 51 * Voronoi diagrams, ACM Transactions on Graphics, 4(2):74-123, April 1985). 52 * For a simplified description, see the course notes for CS348a, 53 * "Mathematical Foundations of Computer Graphics", available at the 54 * Stanford bookstore (and taught during the fall quarter). 55 * The implementation also borrows a tiny subset of the graph-based approach 56 * use in Mantyla's Geometric Work Bench (see M. Mantyla, An Introduction 57 * to Sold Modeling, Computer Science Press, Rockville, Maryland, 1988). 58 * 59 * The fundamental data structure is the "half-edge". Two half-edges 60 * go together to make an edge, but they point in opposite directions. 61 * Each half-edge has a pointer to its mate (the "symmetric" half-edge Sym), 62 * its origin vertex (Org), the face on its left side (Lface), and the 63 * adjacent half-edges in the CCW direction around the origin vertex 64 * (Onext) and around the left face (Lnext). There is also a "next" 65 * pointer for the global edge list (see below). 66 * 67 * The notation used for mesh navigation: 68 * Sym = the mate of a half-edge (same edge, but opposite direction) 69 * Onext = edge CCW around origin vertex (keep same origin) 70 * Dnext = edge CCW around destination vertex (keep same dest) 71 * Lnext = edge CCW around left face (dest becomes new origin) 72 * Rnext = edge CCW around right face (origin becomes new dest) 73 * 74 * "prev" means to substitute CW for CCW in the definitions above. 75 * 76 * The mesh keeps global lists of all vertices, faces, and edges, 77 * stored as doubly-linked circular lists with a dummy header node. 78 * The mesh stores pointers to these dummy headers (vHead, fHead, eHead). 79 * 80 * The circular edge list is special; since half-edges always occur 81 * in pairs (e and e->Sym), each half-edge stores a pointer in only 82 * one direction. Starting at eHead and following the e->next pointers 83 * will visit each *edge* once (ie. e or e->Sym, but not both). 84 * e->Sym stores a pointer in the opposite direction, thus it is 85 * always true that e->Sym->next->Sym->next == e. 86 * 87 * Each vertex has a pointer to next and previous vertices in the 88 * circular list, and a pointer to a half-edge with this vertex as 89 * the origin (NULL if this is the dummy header). There is also a 90 * field "data" for client data. 91 * 92 * Each face has a pointer to the next and previous faces in the 93 * circular list, and a pointer to a half-edge with this face as 94 * the left face (NULL if this is the dummy header). There is also 95 * a field "data" for client data. 96 * 97 * Note that what we call a "face" is really a loop; faces may consist 98 * of more than one loop (ie. not simply connected), but there is no 99 * record of this in the data structure. The mesh may consist of 100 * several disconnected regions, so it may not be possible to visit 101 * the entire mesh by starting at a half-edge and traversing the edge 102 * structure. 103 * 104 * The mesh does NOT support isolated vertices; a vertex is deleted along 105 * with its last edge. Similarly when two faces are merged, one of the 106 * faces is deleted (see __gl_meshDelete below). For mesh operations, 107 * all face (loop) and vertex pointers must not be NULL. However, once 108 * mesh manipulation is finished, __gl_MeshZapFace can be used to delete 109 * faces of the mesh, one at a time. All external faces can be "zapped" 110 * before the mesh is returned to the client; then a NULL face indicates 111 * a region which is not part of the output polygon. 112 */ 113 114 struct GLUvertex { 115 GLUvertex *next; /* next vertex (never NULL) */ 116 GLUvertex *prev; /* previous vertex (never NULL) */ 117 GLUhalfEdge *anEdge; /* a half-edge with this origin */ 118 void *data; /* client's data */ 119 120 /* Internal data (keep hidden) */ 121 GLdouble coords[3]; /* vertex location in 3D */ 122 GLdouble s, t; /* projection onto the sweep plane */ 123 long pqHandle; /* to allow deletion from priority queue */ 124 }; 125 126 struct GLUface { 127 GLUface *next; /* next face (never NULL) */ 128 GLUface *prev; /* previous face (never NULL) */ 129 GLUhalfEdge *anEdge; /* a half edge with this left face */ 130 void *data; /* room for client's data */ 131 132 /* Internal data (keep hidden) */ 133 GLUface *trail; /* "stack" for conversion to strips */ 134 GLboolean marked; /* flag for conversion to strips */ 135 GLboolean inside; /* this face is in the polygon interior */ 136 }; 137 138 struct GLUhalfEdge { 139 GLUhalfEdge *next; /* doubly-linked list (prev==Sym->next) */ 140 GLUhalfEdge *Sym; /* same edge, opposite direction */ 141 GLUhalfEdge *Onext; /* next edge CCW around origin */ 142 GLUhalfEdge *Lnext; /* next edge CCW around left face */ 143 GLUvertex *Org; /* origin vertex (Overtex too long) */ 144 GLUface *Lface; /* left face */ 145 146 /* Internal data (keep hidden) */ 147 ActiveRegion *activeRegion; /* a region with this upper edge (sweep.c) */ 148 int winding; /* change in winding number when crossing 149 from the right face to the left face */ 150 }; 151 152 #define Rface Sym->Lface 153 #define Dst Sym->Org 154 155 #define Oprev Sym->Lnext 156 #define Lprev Onext->Sym 157 #define Dprev Lnext->Sym 158 #define Rprev Sym->Onext 159 #define Dnext Rprev->Sym /* 3 pointers */ 160 #define Rnext Oprev->Sym /* 3 pointers */ 161 162 163 struct GLUmesh { 164 GLUvertex vHead; /* dummy header for vertex list */ 165 GLUface fHead; /* dummy header for face list */ 166 GLUhalfEdge eHead; /* dummy header for edge list */ 167 GLUhalfEdge eHeadSym; /* and its symmetric counterpart */ 168 }; 169 170 /* The mesh operations below have three motivations: completeness, 171 * convenience, and efficiency. The basic mesh operations are MakeEdge, 172 * Splice, and Delete. All the other edge operations can be implemented 173 * in terms of these. The other operations are provided for convenience 174 * and/or efficiency. 175 * 176 * When a face is split or a vertex is added, they are inserted into the 177 * global list *before* the existing vertex or face (ie. e->Org or e->Lface). 178 * This makes it easier to process all vertices or faces in the global lists 179 * without worrying about processing the same data twice. As a convenience, 180 * when a face is split, the "inside" flag is copied from the old face. 181 * Other internal data (v->data, v->activeRegion, f->data, f->marked, 182 * f->trail, e->winding) is set to zero. 183 * 184 * ********************** Basic Edge Operations ************************** 185 * 186 * __gl_meshMakeEdge( mesh ) creates one edge, two vertices, and a loop. 187 * The loop (face) consists of the two new half-edges. 188 * 189 * __gl_meshSplice( eOrg, eDst ) is the basic operation for changing the 190 * mesh connectivity and topology. It changes the mesh so that 191 * eOrg->Onext <- OLD( eDst->Onext ) 192 * eDst->Onext <- OLD( eOrg->Onext ) 193 * where OLD(...) means the value before the meshSplice operation. 194 * 195 * This can have two effects on the vertex structure: 196 * - if eOrg->Org != eDst->Org, the two vertices are merged together 197 * - if eOrg->Org == eDst->Org, the origin is split into two vertices 198 * In both cases, eDst->Org is changed and eOrg->Org is untouched. 199 * 200 * Similarly (and independently) for the face structure, 201 * - if eOrg->Lface == eDst->Lface, one loop is split into two 202 * - if eOrg->Lface != eDst->Lface, two distinct loops are joined into one 203 * In both cases, eDst->Lface is changed and eOrg->Lface is unaffected. 204 * 205 * __gl_meshDelete( eDel ) removes the edge eDel. There are several cases: 206 * if (eDel->Lface != eDel->Rface), we join two loops into one; the loop 207 * eDel->Lface is deleted. Otherwise, we are splitting one loop into two; 208 * the newly created loop will contain eDel->Dst. If the deletion of eDel 209 * would create isolated vertices, those are deleted as well. 210 * 211 * ********************** Other Edge Operations ************************** 212 * 213 * __gl_meshAddEdgeVertex( eOrg ) creates a new edge eNew such that 214 * eNew == eOrg->Lnext, and eNew->Dst is a newly created vertex. 215 * eOrg and eNew will have the same left face. 216 * 217 * __gl_meshSplitEdge( eOrg ) splits eOrg into two edges eOrg and eNew, 218 * such that eNew == eOrg->Lnext. The new vertex is eOrg->Dst == eNew->Org. 219 * eOrg and eNew will have the same left face. 220 * 221 * __gl_meshConnect( eOrg, eDst ) creates a new edge from eOrg->Dst 222 * to eDst->Org, and returns the corresponding half-edge eNew. 223 * If eOrg->Lface == eDst->Lface, this splits one loop into two, 224 * and the newly created loop is eNew->Lface. Otherwise, two disjoint 225 * loops are merged into one, and the loop eDst->Lface is destroyed. 226 * 227 * ************************ Other Operations ***************************** 228 * 229 * __gl_meshNewMesh() creates a new mesh with no edges, no vertices, 230 * and no loops (what we usually call a "face"). 231 * 232 * __gl_meshUnion( mesh1, mesh2 ) forms the union of all structures in 233 * both meshes, and returns the new mesh (the old meshes are destroyed). 234 * 235 * __gl_meshDeleteMesh( mesh ) will free all storage for any valid mesh. 236 * 237 * __gl_meshZapFace( fZap ) destroys a face and removes it from the 238 * global face list. All edges of fZap will have a NULL pointer as their 239 * left face. Any edges which also have a NULL pointer as their right face 240 * are deleted entirely (along with any isolated vertices this produces). 241 * An entire mesh can be deleted by zapping its faces, one at a time, 242 * in any order. Zapped faces cannot be used in further mesh operations! 243 * 244 * __gl_meshCheckMesh( mesh ) checks a mesh for self-consistency. 245 */ 246 247 GLUhalfEdge *__gl_meshMakeEdge( GLUmesh *mesh ); 248 int __gl_meshSplice( GLUhalfEdge *eOrg, GLUhalfEdge *eDst ); 249 int __gl_meshDelete( GLUhalfEdge *eDel ); 250 251 GLUhalfEdge *__gl_meshAddEdgeVertex( GLUhalfEdge *eOrg ); 252 GLUhalfEdge *__gl_meshSplitEdge( GLUhalfEdge *eOrg ); 253 GLUhalfEdge *__gl_meshConnect( GLUhalfEdge *eOrg, GLUhalfEdge *eDst ); 254 255 GLUmesh *__gl_meshNewMesh( void ); 256 GLUmesh *__gl_meshUnion( GLUmesh *mesh1, GLUmesh *mesh2 ); 257 void __gl_meshDeleteMesh( GLUmesh *mesh ); 258 void __gl_meshZapFace( GLUface *fZap ); 259 260 #ifdef NDEBUG 261 #define __gl_meshCheckMesh( mesh ) 262 #else 263 void __gl_meshCheckMesh( GLUmesh *mesh ); 264 #endif 265 266 #endif 267