00001 /* 00002 ** SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008) 00003 ** Copyright (C) [dates of first publication] Silicon Graphics, Inc. 00004 ** All Rights Reserved. 00005 ** 00006 ** Permission is hereby granted, free of charge, to any person obtaining a copy 00007 ** of this software and associated documentation files (the "Software"), to deal 00008 ** in the Software without restriction, including without limitation the rights 00009 ** to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies 00010 ** of the Software, and to permit persons to whom the Software is furnished to do so, 00011 ** subject to the following conditions: 00012 ** 00013 ** The above copyright notice including the dates of first publication and either this 00014 ** permission notice or a reference to http://oss.sgi.com/projects/FreeB/ shall be 00015 ** included in all copies or substantial portions of the Software. 00016 ** 00017 ** THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, 00018 ** INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A 00019 ** PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL SILICON GRAPHICS, INC. 00020 ** BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, 00021 ** TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE 00022 ** OR OTHER DEALINGS IN THE SOFTWARE. 00023 ** 00024 ** Except as contained in this notice, the name of Silicon Graphics, Inc. shall not 00025 ** be used in advertising or otherwise to promote the sale, use or other dealings in 00026 ** this Software without prior written authorization from Silicon Graphics, Inc. 00027 */ 00028 /* 00029 ** Author: Eric Veach, July 1994. 00030 */ 00031 00032 #ifndef MESH_H 00033 #define MESH_H 00034 00035 #include "tesselator.h" 00036 00037 typedef struct TESSmesh TESSmesh; 00038 typedef struct TESSvertex TESSvertex; 00039 typedef struct TESSface TESSface; 00040 typedef struct TESShalfEdge TESShalfEdge; 00041 typedef struct ActiveRegion ActiveRegion; 00042 00043 /* The mesh structure is similar in spirit, notation, and operations 00044 * to the "quad-edge" structure (see L. Guibas and J. Stolfi, Primitives 00045 * for the manipulation of general subdivisions and the computation of 00046 * Voronoi diagrams, ACM Transactions on Graphics, 4(2):74-123, April 1985). 00047 * For a simplified description, see the course notes for CS348a, 00048 * "Mathematical Foundations of Computer Graphics", available at the 00049 * Stanford bookstore (and taught during the fall quarter). 00050 * The implementation also borrows a tiny subset of the graph-based approach 00051 * use in Mantyla's Geometric Work Bench (see M. Mantyla, An Introduction 00052 * to Sold Modeling, Computer Science Press, Rockville, Maryland, 1988). 00053 * 00054 * The fundamental data structure is the "half-edge". Two half-edges 00055 * go together to make an edge, but they point in opposite directions. 00056 * Each half-edge has a pointer to its mate (the "symmetric" half-edge Sym), 00057 * its origin vertex (Org), the face on its left side (Lface), and the 00058 * adjacent half-edges in the CCW direction around the origin vertex 00059 * (Onext) and around the left face (Lnext). There is also a "next" 00060 * pointer for the global edge list (see below). 00061 * 00062 * The notation used for mesh navigation: 00063 * Sym = the mate of a half-edge (same edge, but opposite direction) 00064 * Onext = edge CCW around origin vertex (keep same origin) 00065 * Dnext = edge CCW around destination vertex (keep same dest) 00066 * Lnext = edge CCW around left face (dest becomes new origin) 00067 * Rnext = edge CCW around right face (origin becomes new dest) 00068 * 00069 * "prev" means to substitute CW for CCW in the definitions above. 00070 * 00071 * The mesh keeps global lists of all vertices, faces, and edges, 00072 * stored as doubly-linked circular lists with a dummy header node. 00073 * The mesh stores pointers to these dummy headers (vHead, fHead, eHead). 00074 * 00075 * The circular edge list is special; since half-edges always occur 00076 * in pairs (e and e->Sym), each half-edge stores a pointer in only 00077 * one direction. Starting at eHead and following the e->next pointers 00078 * will visit each *edge* once (ie. e or e->Sym, but not both). 00079 * e->Sym stores a pointer in the opposite direction, thus it is 00080 * always true that e->Sym->next->Sym->next == e. 00081 * 00082 * Each vertex has a pointer to next and previous vertices in the 00083 * circular list, and a pointer to a half-edge with this vertex as 00084 * the origin (NULL if this is the dummy header). There is also a 00085 * field "data" for client data. 00086 * 00087 * Each face has a pointer to the next and previous faces in the 00088 * circular list, and a pointer to a half-edge with this face as 00089 * the left face (NULL if this is the dummy header). There is also 00090 * a field "data" for client data. 00091 * 00092 * Note that what we call a "face" is really a loop; faces may consist 00093 * of more than one loop (ie. not simply connected), but there is no 00094 * record of this in the data structure. The mesh may consist of 00095 * several disconnected regions, so it may not be possible to visit 00096 * the entire mesh by starting at a half-edge and traversing the edge 00097 * structure. 00098 * 00099 * The mesh does NOT support isolated vertices; a vertex is deleted along 00100 * with its last edge. Similarly when two faces are merged, one of the 00101 * faces is deleted (see tessMeshDelete below). For mesh operations, 00102 * all face (loop) and vertex pointers must not be NULL. However, once 00103 * mesh manipulation is finished, TESSmeshZapFace can be used to delete 00104 * faces of the mesh, one at a time. All external faces can be "zapped" 00105 * before the mesh is returned to the client; then a NULL face indicates 00106 * a region which is not part of the output polygon. 00107 */ 00108 00109 struct TESSvertex { 00110 TESSvertex *next; /* next vertex (never NULL) */ 00111 TESSvertex *prev; /* previous vertex (never NULL) */ 00112 TESShalfEdge *anEdge; /* a half-edge with this origin */ 00113 00114 /* Internal data (keep hidden) */ 00115 TESSreal coords[3]; /* vertex location in 3D */ 00116 TESSreal s, t; /* projection onto the sweep plane */ 00117 int pqHandle; /* to allow deletion from priority queue */ 00118 TESSindex n; /* to allow identiy unique vertices */ 00119 }; 00120 00121 struct TESSface { 00122 TESSface *next; /* next face (never NULL) */ 00123 TESSface *prev; /* previous face (never NULL) */ 00124 TESShalfEdge *anEdge; /* a half edge with this left face */ 00125 00126 /* Internal data (keep hidden) */ 00127 TESSface *trail; /* "stack" for conversion to strips */ 00128 TESSindex n; /* to allow identiy unique faces */ 00129 char marked; /* flag for conversion to strips */ 00130 char inside; /* this face is in the polygon interior */ 00131 }; 00132 00133 struct TESShalfEdge { 00134 TESShalfEdge *next; /* doubly-linked list (prev==Sym->next) */ 00135 TESShalfEdge *Sym; /* same edge, opposite direction */ 00136 TESShalfEdge *Onext; /* next edge CCW around origin */ 00137 TESShalfEdge *Lnext; /* next edge CCW around left face */ 00138 TESSvertex *Org; /* origin vertex (Overtex too long) */ 00139 TESSface *Lface; /* left face */ 00140 00141 /* Internal data (keep hidden) */ 00142 ActiveRegion *activeRegion; /* a region with this upper edge (sweep.c) */ 00143 int winding; /* change in winding number when crossing 00144 from the right face to the left face */ 00145 }; 00146 00147 #define Rface Sym->Lface 00148 #define Dst Sym->Org 00149 00150 #define Oprev Sym->Lnext 00151 #define Lprev Onext->Sym 00152 #define Dprev Lnext->Sym 00153 #define Rprev Sym->Onext 00154 #define Dnext Rprev->Sym /* 3 pointers */ 00155 #define Rnext Oprev->Sym /* 3 pointers */ 00156 00157 00158 struct TESSmesh { 00159 TESSvertex vHead; /* dummy header for vertex list */ 00160 TESSface fHead; /* dummy header for face list */ 00161 TESShalfEdge eHead; /* dummy header for edge list */ 00162 TESShalfEdge eHeadSym; /* and its symmetric counterpart */ 00163 00164 struct BucketAlloc* edgeBucket; 00165 struct BucketAlloc* vertexBucket; 00166 struct BucketAlloc* faceBucket; 00167 }; 00168 00169 /* The mesh operations below have three motivations: completeness, 00170 * convenience, and efficiency. The basic mesh operations are MakeEdge, 00171 * Splice, and Delete. All the other edge operations can be implemented 00172 * in terms of these. The other operations are provided for convenience 00173 * and/or efficiency. 00174 * 00175 * When a face is split or a vertex is added, they are inserted into the 00176 * global list *before* the existing vertex or face (ie. e->Org or e->Lface). 00177 * This makes it easier to process all vertices or faces in the global lists 00178 * without worrying about processing the same data twice. As a convenience, 00179 * when a face is split, the "inside" flag is copied from the old face. 00180 * Other internal data (v->data, v->activeRegion, f->data, f->marked, 00181 * f->trail, e->winding) is set to zero. 00182 * 00183 * ********************** Basic Edge Operations ************************** 00184 * 00185 * tessMeshMakeEdge( mesh ) creates one edge, two vertices, and a loop. 00186 * The loop (face) consists of the two new half-edges. 00187 * 00188 * tessMeshSplice( eOrg, eDst ) is the basic operation for changing the 00189 * mesh connectivity and topology. It changes the mesh so that 00190 * eOrg->Onext <- OLD( eDst->Onext ) 00191 * eDst->Onext <- OLD( eOrg->Onext ) 00192 * where OLD(...) means the value before the meshSplice operation. 00193 * 00194 * This can have two effects on the vertex structure: 00195 * - if eOrg->Org != eDst->Org, the two vertices are merged together 00196 * - if eOrg->Org == eDst->Org, the origin is split into two vertices 00197 * In both cases, eDst->Org is changed and eOrg->Org is untouched. 00198 * 00199 * Similarly (and independently) for the face structure, 00200 * - if eOrg->Lface == eDst->Lface, one loop is split into two 00201 * - if eOrg->Lface != eDst->Lface, two distinct loops are joined into one 00202 * In both cases, eDst->Lface is changed and eOrg->Lface is unaffected. 00203 * 00204 * tessMeshDelete( eDel ) removes the edge eDel. There are several cases: 00205 * if (eDel->Lface != eDel->Rface), we join two loops into one; the loop 00206 * eDel->Lface is deleted. Otherwise, we are splitting one loop into two; 00207 * the newly created loop will contain eDel->Dst. If the deletion of eDel 00208 * would create isolated vertices, those are deleted as well. 00209 * 00210 * ********************** Other Edge Operations ************************** 00211 * 00212 * tessMeshAddEdgeVertex( eOrg ) creates a new edge eNew such that 00213 * eNew == eOrg->Lnext, and eNew->Dst is a newly created vertex. 00214 * eOrg and eNew will have the same left face. 00215 * 00216 * tessMeshSplitEdge( eOrg ) splits eOrg into two edges eOrg and eNew, 00217 * such that eNew == eOrg->Lnext. The new vertex is eOrg->Dst == eNew->Org. 00218 * eOrg and eNew will have the same left face. 00219 * 00220 * tessMeshConnect( eOrg, eDst ) creates a new edge from eOrg->Dst 00221 * to eDst->Org, and returns the corresponding half-edge eNew. 00222 * If eOrg->Lface == eDst->Lface, this splits one loop into two, 00223 * and the newly created loop is eNew->Lface. Otherwise, two disjoint 00224 * loops are merged into one, and the loop eDst->Lface is destroyed. 00225 * 00226 * ************************ Other Operations ***************************** 00227 * 00228 * tessMeshNewMesh() creates a new mesh with no edges, no vertices, 00229 * and no loops (what we usually call a "face"). 00230 * 00231 * tessMeshUnion( mesh1, mesh2 ) forms the union of all structures in 00232 * both meshes, and returns the new mesh (the old meshes are destroyed). 00233 * 00234 * tessMeshDeleteMesh( mesh ) will free all storage for any valid mesh. 00235 * 00236 * tessMeshZapFace( fZap ) destroys a face and removes it from the 00237 * global face list. All edges of fZap will have a NULL pointer as their 00238 * left face. Any edges which also have a NULL pointer as their right face 00239 * are deleted entirely (along with any isolated vertices this produces). 00240 * An entire mesh can be deleted by zapping its faces, one at a time, 00241 * in any order. Zapped faces cannot be used in further mesh operations! 00242 * 00243 * tessMeshCheckMesh( mesh ) checks a mesh for self-consistency. 00244 */ 00245 00246 TESShalfEdge *tessMeshMakeEdge( TESSmesh *mesh ); 00247 int tessMeshSplice( TESSmesh *mesh, TESShalfEdge *eOrg, TESShalfEdge *eDst ); 00248 int tessMeshDelete( TESSmesh *mesh, TESShalfEdge *eDel ); 00249 00250 TESShalfEdge *tessMeshAddEdgeVertex( TESSmesh *mesh, TESShalfEdge *eOrg ); 00251 TESShalfEdge *tessMeshSplitEdge( TESSmesh *mesh, TESShalfEdge *eOrg ); 00252 TESShalfEdge *tessMeshConnect( TESSmesh *mesh, TESShalfEdge *eOrg, TESShalfEdge *eDst ); 00253 00254 TESSmesh *tessMeshNewMesh( TESSalloc* alloc ); 00255 TESSmesh *tessMeshUnion( TESSalloc* alloc, TESSmesh *mesh1, TESSmesh *mesh2 ); 00256 int tessMeshMergeConvexFaces( TESSmesh *mesh, int maxVertsPerFace ); 00257 void tessMeshDeleteMesh( TESSalloc* alloc, TESSmesh *mesh ); 00258 void tessMeshZapFace( TESSmesh *mesh, TESSface *fZap ); 00259 00260 #ifdef NDEBUG 00261 #define tessMeshCheckMesh( mesh ) 00262 #else 00263 void tessMeshCheckMesh( TESSmesh *mesh ); 00264 #endif 00265 00266 #endif