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