Geant4 Cross Reference |
1 // see license file for original license. 1 // see license file for original license. 2 2 3 #ifndef tools_glutess_mesh 3 #ifndef tools_glutess_mesh 4 #define tools_glutess_mesh 4 #define tools_glutess_mesh 5 5 6 #include "_glu" 6 #include "_glu" 7 7 8 typedef struct GLUmesh GLUmesh; 8 typedef struct GLUmesh GLUmesh; 9 9 10 typedef struct GLUvertex GLUvertex; 10 typedef struct GLUvertex GLUvertex; 11 typedef struct GLUface GLUface; 11 typedef struct GLUface GLUface; 12 typedef struct GLUhalfEdge GLUhalfEdge; 12 typedef struct GLUhalfEdge GLUhalfEdge; 13 13 14 typedef struct ActiveRegion ActiveRegion; /* I 14 typedef struct ActiveRegion ActiveRegion; /* Internal data */ 15 15 16 /* The mesh structure is similar in spirit, no 16 /* The mesh structure is similar in spirit, notation, and operations 17 * to the "quad-edge" structure (see L. Guibas 17 * to the "quad-edge" structure (see L. Guibas and J. Stolfi, Primitives 18 * for the manipulation of general subdivision 18 * for the manipulation of general subdivisions and the computation of 19 * Voronoi diagrams, ACM Transactions on Graph 19 * Voronoi diagrams, ACM Transactions on Graphics, 4(2):74-123, April 1985). 20 * For a simplified description, see the cours 20 * For a simplified description, see the course notes for CS348a, 21 * "Mathematical Foundations of Computer Graph 21 * "Mathematical Foundations of Computer Graphics", available at the 22 * Stanford bookstore (and taught during the f 22 * Stanford bookstore (and taught during the fall quarter). 23 * The implementation also borrows a tiny subs 23 * The implementation also borrows a tiny subset of the graph-based approach 24 * use in Mantyla's Geometric Work Bench (see 24 * use in Mantyla's Geometric Work Bench (see M. Mantyla, An Introduction 25 * to Sold Modeling, Computer Science Press, R 25 * to Sold Modeling, Computer Science Press, Rockville, Maryland, 1988). 26 * 26 * 27 * The fundamental data structure is the "half 27 * The fundamental data structure is the "half-edge". Two half-edges 28 * go together to make an edge, but they point 28 * go together to make an edge, but they point in opposite directions. 29 * Each half-edge has a pointer to its mate (t 29 * Each half-edge has a pointer to its mate (the "symmetric" half-edge Sym), 30 * its origin vertex (Org), the face on its le 30 * its origin vertex (Org), the face on its left side (Lface), and the 31 * adjacent half-edges in the CCW direction ar 31 * adjacent half-edges in the CCW direction around the origin vertex 32 * (Onext) and around the left face (Lnext). 32 * (Onext) and around the left face (Lnext). There is also a "next" 33 * pointer for the global edge list (see below 33 * pointer for the global edge list (see below). 34 * 34 * 35 * The notation used for mesh navigation: 35 * The notation used for mesh navigation: 36 * Sym = the mate of a half-edge (same edge 36 * Sym = the mate of a half-edge (same edge, but opposite direction) 37 * Onext = edge CCW around origin vertex (kee 37 * Onext = edge CCW around origin vertex (keep same origin) 38 * Dnext = edge CCW around destination vertex 38 * Dnext = edge CCW around destination vertex (keep same dest) 39 * Lnext = edge CCW around left face (dest be 39 * Lnext = edge CCW around left face (dest becomes new origin) 40 * Rnext = edge CCW around right face (origin 40 * Rnext = edge CCW around right face (origin becomes new dest) 41 * 41 * 42 * "prev" means to substitute CW for CCW in th 42 * "prev" means to substitute CW for CCW in the definitions above. 43 * 43 * 44 * The mesh keeps global lists of all vertices 44 * The mesh keeps global lists of all vertices, faces, and edges, 45 * stored as doubly-linked circular lists with 45 * stored as doubly-linked circular lists with a dummy header node. 46 * The mesh stores pointers to these dummy hea 46 * The mesh stores pointers to these dummy headers (vHead, fHead, eHead). 47 * 47 * 48 * The circular edge list is special; since ha 48 * The circular edge list is special; since half-edges always occur 49 * in pairs (e and e->Sym), each half-edge sto 49 * in pairs (e and e->Sym), each half-edge stores a pointer in only 50 * one direction. Starting at eHead and follo 50 * one direction. Starting at eHead and following the e->next pointers 51 * will visit each *edge* once (ie. e or e->Sy 51 * will visit each *edge* once (ie. e or e->Sym, but not both). 52 * e->Sym stores a pointer in the opposite dir 52 * e->Sym stores a pointer in the opposite direction, thus it is 53 * always true that e->Sym->next->Sym->next == 53 * always true that e->Sym->next->Sym->next == e. 54 * 54 * 55 * Each vertex has a pointer to next and previ 55 * Each vertex has a pointer to next and previous vertices in the 56 * circular list, and a pointer to a half-edge 56 * circular list, and a pointer to a half-edge with this vertex as 57 * the origin (NULL if this is the dummy heade 57 * the origin (NULL if this is the dummy header). There is also a 58 * field "data" for client data. 58 * field "data" for client data. 59 * 59 * 60 * Each face has a pointer to the next and pre 60 * Each face has a pointer to the next and previous faces in the 61 * circular list, and a pointer to a half-edge 61 * circular list, and a pointer to a half-edge with this face as 62 * the left face (NULL if this is the dummy he 62 * the left face (NULL if this is the dummy header). There is also 63 * a field "data" for client data. 63 * a field "data" for client data. 64 * 64 * 65 * Note that what we call a "face" is really a 65 * Note that what we call a "face" is really a loop; faces may consist 66 * of more than one loop (ie. not simply conne 66 * of more than one loop (ie. not simply connected), but there is no 67 * record of this in the data structure. The 67 * record of this in the data structure. The mesh may consist of 68 * several disconnected regions, so it may not 68 * several disconnected regions, so it may not be possible to visit 69 * the entire mesh by starting at a half-edge 69 * the entire mesh by starting at a half-edge and traversing the edge 70 * structure. 70 * structure. 71 * 71 * 72 * The mesh does NOT support isolated vertices 72 * The mesh does NOT support isolated vertices; a vertex is deleted along 73 * with its last edge. Similarly when two fac 73 * with its last edge. Similarly when two faces are merged, one of the 74 * faces is deleted (see __gl_meshDelete below 74 * faces is deleted (see __gl_meshDelete below). For mesh operations, 75 * all face (loop) and vertex pointers must no 75 * all face (loop) and vertex pointers must not be NULL. However, once 76 * mesh manipulation is finished, __gl_MeshZap 76 * mesh manipulation is finished, __gl_MeshZapFace can be used to delete 77 * faces of the mesh, one at a time. All exte 77 * faces of the mesh, one at a time. All external faces can be "zapped" 78 * before the mesh is returned to the client; 78 * before the mesh is returned to the client; then a NULL face indicates 79 * a region which is not part of the output po 79 * a region which is not part of the output polygon. 80 */ 80 */ 81 81 82 struct GLUvertex { 82 struct GLUvertex { 83 GLUvertex *next; /* next vertex (never NU 83 GLUvertex *next; /* next vertex (never NULL) */ 84 GLUvertex *prev; /* previous vertex (neve 84 GLUvertex *prev; /* previous vertex (never NULL) */ 85 GLUhalfEdge *anEdge; /* a half-edge with th 85 GLUhalfEdge *anEdge; /* a half-edge with this origin */ 86 void *data; /* client's data */ 86 void *data; /* client's data */ 87 87 88 /* Internal data (keep hidden) */ 88 /* Internal data (keep hidden) */ 89 GLUdouble coords[3]; /* vertex location in 89 GLUdouble coords[3]; /* vertex location in 3D */ 90 GLUdouble s, t; /* projection onto the swe 90 GLUdouble s, t; /* projection onto the sweep plane */ 91 long pqHandle; /* to allow deletion from 91 long pqHandle; /* to allow deletion from priority queue */ 92 }; 92 }; 93 93 94 struct GLUface { 94 struct GLUface { 95 GLUface *next; /* next face (never NULL) 95 GLUface *next; /* next face (never NULL) */ 96 GLUface *prev; /* previous face (never NU 96 GLUface *prev; /* previous face (never NULL) */ 97 GLUhalfEdge *anEdge; /* a half edge with th 97 GLUhalfEdge *anEdge; /* a half edge with this left face */ 98 void *data; /* room for client's data 98 void *data; /* room for client's data */ 99 99 100 /* Internal data (keep hidden) */ 100 /* Internal data (keep hidden) */ 101 GLUface *trail; /* "stack" for conversion 101 GLUface *trail; /* "stack" for conversion to strips */ 102 GLUboolean marked; /* flag for conversion 102 GLUboolean marked; /* flag for conversion to strips */ 103 GLUboolean inside; /* this face is in the 103 GLUboolean inside; /* this face is in the polygon interior */ 104 }; 104 }; 105 105 106 struct GLUhalfEdge { 106 struct GLUhalfEdge { 107 GLUhalfEdge *next; /* doubly-linked list 107 GLUhalfEdge *next; /* doubly-linked list (prev==Sym->next) */ 108 GLUhalfEdge *Sym; /* same edge, opposite d 108 GLUhalfEdge *Sym; /* same edge, opposite direction */ 109 GLUhalfEdge *Onext; /* next edge CCW aroun 109 GLUhalfEdge *Onext; /* next edge CCW around origin */ 110 GLUhalfEdge *Lnext; /* next edge CCW aroun 110 GLUhalfEdge *Lnext; /* next edge CCW around left face */ 111 GLUvertex *Org; /* origin vertex (Overtex 111 GLUvertex *Org; /* origin vertex (Overtex too long) */ 112 GLUface *Lface; /* left face */ 112 GLUface *Lface; /* left face */ 113 113 114 /* Internal data (keep hidden) */ 114 /* Internal data (keep hidden) */ 115 ActiveRegion *activeRegion; /* a region wi 115 ActiveRegion *activeRegion; /* a region with this upper edge (sweep.c) */ 116 int winding; /* change in winding number 116 int winding; /* change in winding number when crossing 117 from the ri 117 from the right face to the left face */ 118 }; 118 }; 119 119 120 #define Rface Sym->Lface 120 #define Rface Sym->Lface 121 #define Dst Sym->Org 121 #define Dst Sym->Org 122 122 123 #define Oprev Sym->Lnext 123 #define Oprev Sym->Lnext 124 #define Lprev Onext->Sym 124 #define Lprev Onext->Sym 125 #define Dprev Lnext->Sym 125 #define Dprev Lnext->Sym 126 #define Rprev Sym->Onext 126 #define Rprev Sym->Onext 127 #define Dnext Rprev->Sym /* 3 pointers */ 127 #define Dnext Rprev->Sym /* 3 pointers */ 128 #define Rnext Oprev->Sym /* 3 pointers */ 128 #define Rnext Oprev->Sym /* 3 pointers */ 129 129 130 130 131 struct GLUmesh { 131 struct GLUmesh { 132 GLUvertex vHead; /* dummy header for vert 132 GLUvertex vHead; /* dummy header for vertex list */ 133 GLUface fHead; /* dummy header for face l 133 GLUface fHead; /* dummy header for face list */ 134 GLUhalfEdge eHead; /* dummy header for ed 134 GLUhalfEdge eHead; /* dummy header for edge list */ 135 GLUhalfEdge eHeadSym; /* and its symmetric c 135 GLUhalfEdge eHeadSym; /* and its symmetric counterpart */ 136 }; 136 }; 137 137 138 /* The mesh operations below have three motiva 138 /* The mesh operations below have three motivations: completeness, 139 * convenience, and efficiency. The basic mes 139 * convenience, and efficiency. The basic mesh operations are MakeEdge, 140 * Splice, and Delete. All the other edge ope 140 * Splice, and Delete. All the other edge operations can be implemented 141 * in terms of these. The other operations ar 141 * in terms of these. The other operations are provided for convenience 142 * and/or efficiency. 142 * and/or efficiency. 143 * 143 * 144 * When a face is split or a vertex is added, 144 * When a face is split or a vertex is added, they are inserted into the 145 * global list *before* the existing vertex or 145 * global list *before* the existing vertex or face (ie. e->Org or e->Lface). 146 * This makes it easier to process all vertice 146 * This makes it easier to process all vertices or faces in the global lists 147 * without worrying about processing the same 147 * without worrying about processing the same data twice. As a convenience, 148 * when a face is split, the "inside" flag is 148 * when a face is split, the "inside" flag is copied from the old face. 149 * Other internal data (v->data, v->activeRegi 149 * Other internal data (v->data, v->activeRegion, f->data, f->marked, 150 * f->trail, e->winding) is set to zero. 150 * f->trail, e->winding) is set to zero. 151 * 151 * 152 * ********************** Basic Edge Operation 152 * ********************** Basic Edge Operations ************************** 153 * 153 * 154 * __gl_meshMakeEdge( mesh ) creates one edge, 154 * __gl_meshMakeEdge( mesh ) creates one edge, two vertices, and a loop. 155 * The loop (face) consists of the two new hal 155 * The loop (face) consists of the two new half-edges. 156 * 156 * 157 * __gl_meshSplice( eOrg, eDst ) is the basic 157 * __gl_meshSplice( eOrg, eDst ) is the basic operation for changing the 158 * mesh connectivity and topology. It changes 158 * mesh connectivity and topology. It changes the mesh so that 159 * eOrg->Onext <- OLD( eDst->Onext ) 159 * eOrg->Onext <- OLD( eDst->Onext ) 160 * eDst->Onext <- OLD( eOrg->Onext ) 160 * eDst->Onext <- OLD( eOrg->Onext ) 161 * where OLD(...) means the value before the m 161 * where OLD(...) means the value before the meshSplice operation. 162 * 162 * 163 * This can have two effects on the vertex str 163 * This can have two effects on the vertex structure: 164 * - if eOrg->Org != eDst->Org, the two verti 164 * - if eOrg->Org != eDst->Org, the two vertices are merged together 165 * - if eOrg->Org == eDst->Org, the origin is 165 * - if eOrg->Org == eDst->Org, the origin is split into two vertices 166 * In both cases, eDst->Org is changed and eOr 166 * In both cases, eDst->Org is changed and eOrg->Org is untouched. 167 * 167 * 168 * Similarly (and independently) for the face 168 * Similarly (and independently) for the face structure, 169 * - if eOrg->Lface == eDst->Lface, one loop 169 * - if eOrg->Lface == eDst->Lface, one loop is split into two 170 * - if eOrg->Lface != eDst->Lface, two disti 170 * - if eOrg->Lface != eDst->Lface, two distinct loops are joined into one 171 * In both cases, eDst->Lface is changed and e 171 * In both cases, eDst->Lface is changed and eOrg->Lface is unaffected. 172 * 172 * 173 * __gl_meshDelete( eDel ) removes the edge eD 173 * __gl_meshDelete( eDel ) removes the edge eDel. There are several cases: 174 * if (eDel->Lface != eDel->Rface), we join tw 174 * if (eDel->Lface != eDel->Rface), we join two loops into one; the loop 175 * eDel->Lface is deleted. Otherwise, we are 175 * eDel->Lface is deleted. Otherwise, we are splitting one loop into two; 176 * the newly created loop will contain eDel->D 176 * the newly created loop will contain eDel->Dst. If the deletion of eDel 177 * would create isolated vertices, those are d 177 * would create isolated vertices, those are deleted as well. 178 * 178 * 179 * ********************** Other Edge Operation 179 * ********************** Other Edge Operations ************************** 180 * 180 * 181 * __gl_meshAddEdgeVertex( eOrg ) creates a ne 181 * __gl_meshAddEdgeVertex( eOrg ) creates a new edge eNew such that 182 * eNew == eOrg->Lnext, and eNew->Dst is a new 182 * eNew == eOrg->Lnext, and eNew->Dst is a newly created vertex. 183 * eOrg and eNew will have the same left face. 183 * eOrg and eNew will have the same left face. 184 * 184 * 185 * __gl_meshSplitEdge( eOrg ) splits eOrg into 185 * __gl_meshSplitEdge( eOrg ) splits eOrg into two edges eOrg and eNew, 186 * such that eNew == eOrg->Lnext. The new ver 186 * such that eNew == eOrg->Lnext. The new vertex is eOrg->Dst == eNew->Org. 187 * eOrg and eNew will have the same left face. 187 * eOrg and eNew will have the same left face. 188 * 188 * 189 * __gl_meshConnect( eOrg, eDst ) creates a ne 189 * __gl_meshConnect( eOrg, eDst ) creates a new edge from eOrg->Dst 190 * to eDst->Org, and returns the corresponding 190 * to eDst->Org, and returns the corresponding half-edge eNew. 191 * If eOrg->Lface == eDst->Lface, this splits 191 * If eOrg->Lface == eDst->Lface, this splits one loop into two, 192 * and the newly created loop is eNew->Lface. 192 * and the newly created loop is eNew->Lface. Otherwise, two disjoint 193 * loops are merged into one, and the loop eDs 193 * loops are merged into one, and the loop eDst->Lface is destroyed. 194 * 194 * 195 * ************************ Other Operations * 195 * ************************ Other Operations ***************************** 196 * 196 * 197 * __gl_meshNewMesh() creates a new mesh with 197 * __gl_meshNewMesh() creates a new mesh with no edges, no vertices, 198 * and no loops (what we usually call a "face" 198 * and no loops (what we usually call a "face"). 199 * 199 * 200 * __gl_meshUnion( mesh1, mesh2 ) forms the un 200 * __gl_meshUnion( mesh1, mesh2 ) forms the union of all structures in 201 * both meshes, and returns the new mesh (the 201 * both meshes, and returns the new mesh (the old meshes are destroyed). 202 * 202 * 203 * __gl_meshDeleteMesh( mesh ) will free all s 203 * __gl_meshDeleteMesh( mesh ) will free all storage for any valid mesh. 204 * 204 * 205 * __gl_meshZapFace( fZap ) destroys a face an 205 * __gl_meshZapFace( fZap ) destroys a face and removes it from the 206 * global face list. All edges of fZap will h 206 * global face list. All edges of fZap will have a NULL pointer as their 207 * left face. Any edges which also have a NUL 207 * left face. Any edges which also have a NULL pointer as their right face 208 * are deleted entirely (along with any isolat 208 * are deleted entirely (along with any isolated vertices this produces). 209 * An entire mesh can be deleted by zapping it 209 * An entire mesh can be deleted by zapping its faces, one at a time, 210 * in any order. Zapped faces cannot be used 210 * in any order. Zapped faces cannot be used in further mesh operations! 211 * 211 * 212 * __gl_meshCheckMesh( mesh ) checks a mesh fo 212 * __gl_meshCheckMesh( mesh ) checks a mesh for self-consistency. 213 */ 213 */ 214 214 215 ////////////////////////////////////////////// 215 //////////////////////////////////////////////////////// 216 /// inlined C code : ///////////////////////// 216 /// inlined C code : /////////////////////////////////// 217 ////////////////////////////////////////////// 217 //////////////////////////////////////////////////////// 218 218 219 //#include "gluos" 219 //#include "gluos" 220 #include <cstddef> 220 #include <cstddef> 221 #include <cassert> 221 #include <cassert> 222 #include "memalloc" 222 #include "memalloc" 223 223 224 inline/*static*/ GLUvertex *static_allocVertex 224 inline/*static*/ GLUvertex *static_allocVertex() 225 { 225 { 226 return (GLUvertex *)memAlloc( sizeof( GLUve 226 return (GLUvertex *)memAlloc( sizeof( GLUvertex )); 227 } 227 } 228 228 229 inline/*static*/ GLUface *static_allocFace() 229 inline/*static*/ GLUface *static_allocFace() 230 { 230 { 231 return (GLUface *)memAlloc( sizeof( GLUface 231 return (GLUface *)memAlloc( sizeof( GLUface )); 232 } 232 } 233 233 234 /************************ Utility Routines *** 234 /************************ Utility Routines ************************/ 235 235 236 /* Allocate and free half-edges in pairs for e 236 /* Allocate and free half-edges in pairs for efficiency. 237 * The *only* place that should use this fact 237 * The *only* place that should use this fact is allocation/free. 238 */ 238 */ 239 typedef struct { GLUhalfEdge e, eSym; } EdgePa 239 typedef struct { GLUhalfEdge e, eSym; } EdgePair; 240 240 241 /* MakeEdge creates a new pair of half-edges w 241 /* MakeEdge creates a new pair of half-edges which form their own loop. 242 * No vertex or face structures are allocated, 242 * No vertex or face structures are allocated, but these must be assigned 243 * before the current edge operation is comple 243 * before the current edge operation is completed. 244 */ 244 */ 245 inline/*static*/ GLUhalfEdge *static_MakeEdge( 245 inline/*static*/ GLUhalfEdge *static_MakeEdge( GLUhalfEdge *eNext ) 246 { 246 { 247 GLUhalfEdge *e; 247 GLUhalfEdge *e; 248 GLUhalfEdge *eSym; 248 GLUhalfEdge *eSym; 249 GLUhalfEdge *ePrev; 249 GLUhalfEdge *ePrev; 250 EdgePair *pair = (EdgePair *)memAlloc( sizeo 250 EdgePair *pair = (EdgePair *)memAlloc( sizeof( EdgePair )); 251 if (pair == NULL) return NULL; 251 if (pair == NULL) return NULL; 252 252 253 e = &pair->e; 253 e = &pair->e; 254 eSym = &pair->eSym; 254 eSym = &pair->eSym; 255 255 256 /* Make sure eNext points to the first edge 256 /* Make sure eNext points to the first edge of the edge pair */ 257 if( eNext->Sym < eNext ) { eNext = eNext->Sy 257 if( eNext->Sym < eNext ) { eNext = eNext->Sym; } 258 258 259 /* Insert in circular doubly-linked list bef 259 /* Insert in circular doubly-linked list before eNext. 260 * Note that the prev pointer is stored in S 260 * Note that the prev pointer is stored in Sym->next. 261 */ 261 */ 262 ePrev = eNext->Sym->next; 262 ePrev = eNext->Sym->next; 263 eSym->next = ePrev; 263 eSym->next = ePrev; 264 ePrev->Sym->next = e; 264 ePrev->Sym->next = e; 265 e->next = eNext; 265 e->next = eNext; 266 eNext->Sym->next = eSym; 266 eNext->Sym->next = eSym; 267 267 268 e->Sym = eSym; 268 e->Sym = eSym; 269 e->Onext = e; 269 e->Onext = e; 270 e->Lnext = eSym; 270 e->Lnext = eSym; 271 e->Org = NULL; 271 e->Org = NULL; 272 e->Lface = NULL; 272 e->Lface = NULL; 273 e->winding = 0; 273 e->winding = 0; 274 e->activeRegion = NULL; 274 e->activeRegion = NULL; 275 275 276 eSym->Sym = e; 276 eSym->Sym = e; 277 eSym->Onext = eSym; 277 eSym->Onext = eSym; 278 eSym->Lnext = e; 278 eSym->Lnext = e; 279 eSym->Org = NULL; 279 eSym->Org = NULL; 280 eSym->Lface = NULL; 280 eSym->Lface = NULL; 281 eSym->winding = 0; 281 eSym->winding = 0; 282 eSym->activeRegion = NULL; 282 eSym->activeRegion = NULL; 283 283 284 return e; 284 return e; 285 } 285 } 286 286 287 /* Splice( a, b ) is best described by the Gui 287 /* Splice( a, b ) is best described by the Guibas/Stolfi paper or the 288 * CS348a notes (see mesh.h). Basically it mo 288 * CS348a notes (see mesh.h). Basically it modifies the mesh so that 289 * a->Onext and b->Onext are exchanged. This 289 * a->Onext and b->Onext are exchanged. This can have various effects 290 * depending on whether a and b belong to diff 290 * depending on whether a and b belong to different face or vertex rings. 291 * For more explanation see __gl_meshSplice() 291 * For more explanation see __gl_meshSplice() below. 292 */ 292 */ 293 inline/*static*/ void static_Splice( GLUhalfEd 293 inline/*static*/ void static_Splice( GLUhalfEdge *a, GLUhalfEdge *b ) 294 { 294 { 295 GLUhalfEdge *aOnext = a->Onext; 295 GLUhalfEdge *aOnext = a->Onext; 296 GLUhalfEdge *bOnext = b->Onext; 296 GLUhalfEdge *bOnext = b->Onext; 297 297 298 aOnext->Sym->Lnext = b; 298 aOnext->Sym->Lnext = b; 299 bOnext->Sym->Lnext = a; 299 bOnext->Sym->Lnext = a; 300 a->Onext = bOnext; 300 a->Onext = bOnext; 301 b->Onext = aOnext; 301 b->Onext = aOnext; 302 } 302 } 303 303 304 /* MakeVertex( newVertex, eOrig, vNext ) attac 304 /* MakeVertex( newVertex, eOrig, vNext ) attaches a new vertex and makes it the 305 * origin of all edges in the vertex loop to w 305 * origin of all edges in the vertex loop to which eOrig belongs. "vNext" gives 306 * a place to insert the new vertex in the glo 306 * a place to insert the new vertex in the global vertex list. We insert 307 * the new vertex *before* vNext so that algor 307 * the new vertex *before* vNext so that algorithms which walk the vertex 308 * list will not see the newly created vertice 308 * list will not see the newly created vertices. 309 */ 309 */ 310 inline/*static*/ void static_MakeVertex( GLUve 310 inline/*static*/ void static_MakeVertex( GLUvertex *newVertex, 311 GLUhalfEdge *eOrig, GLUvertex *vNext ) 311 GLUhalfEdge *eOrig, GLUvertex *vNext ) 312 { 312 { 313 GLUhalfEdge *e; 313 GLUhalfEdge *e; 314 GLUvertex *vPrev; 314 GLUvertex *vPrev; 315 GLUvertex *vNew = newVertex; 315 GLUvertex *vNew = newVertex; 316 316 317 assert(vNew != NULL); 317 assert(vNew != NULL); 318 318 319 /* insert in circular doubly-linked list bef 319 /* insert in circular doubly-linked list before vNext */ 320 vPrev = vNext->prev; 320 vPrev = vNext->prev; 321 vNew->prev = vPrev; 321 vNew->prev = vPrev; 322 vPrev->next = vNew; 322 vPrev->next = vNew; 323 vNew->next = vNext; 323 vNew->next = vNext; 324 vNext->prev = vNew; 324 vNext->prev = vNew; 325 325 326 vNew->anEdge = eOrig; 326 vNew->anEdge = eOrig; 327 vNew->data = NULL; 327 vNew->data = NULL; 328 /* leave coords, s, t undefined */ 328 /* leave coords, s, t undefined */ 329 329 330 /* fix other edges on this vertex loop */ 330 /* fix other edges on this vertex loop */ 331 e = eOrig; 331 e = eOrig; 332 do { 332 do { 333 e->Org = vNew; 333 e->Org = vNew; 334 e = e->Onext; 334 e = e->Onext; 335 } while( e != eOrig ); 335 } while( e != eOrig ); 336 } 336 } 337 337 338 /* MakeFace( newFace, eOrig, fNext ) attaches 338 /* MakeFace( newFace, eOrig, fNext ) attaches a new face and makes it the left 339 * face of all edges in the face loop to which 339 * face of all edges in the face loop to which eOrig belongs. "fNext" gives 340 * a place to insert the new face in the globa 340 * a place to insert the new face in the global face list. We insert 341 * the new face *before* fNext so that algorit 341 * the new face *before* fNext so that algorithms which walk the face 342 * list will not see the newly created faces. 342 * list will not see the newly created faces. 343 */ 343 */ 344 inline/*static*/ void static_MakeFace( GLUface 344 inline/*static*/ void static_MakeFace( GLUface *newFace, GLUhalfEdge *eOrig, GLUface *fNext ) 345 { 345 { 346 GLUhalfEdge *e; 346 GLUhalfEdge *e; 347 GLUface *fPrev; 347 GLUface *fPrev; 348 GLUface *fNew = newFace; 348 GLUface *fNew = newFace; 349 349 350 assert(fNew != NULL); 350 assert(fNew != NULL); 351 351 352 /* insert in circular doubly-linked list bef 352 /* insert in circular doubly-linked list before fNext */ 353 fPrev = fNext->prev; 353 fPrev = fNext->prev; 354 fNew->prev = fPrev; 354 fNew->prev = fPrev; 355 fPrev->next = fNew; 355 fPrev->next = fNew; 356 fNew->next = fNext; 356 fNew->next = fNext; 357 fNext->prev = fNew; 357 fNext->prev = fNew; 358 358 359 fNew->anEdge = eOrig; 359 fNew->anEdge = eOrig; 360 fNew->data = NULL; 360 fNew->data = NULL; 361 fNew->trail = NULL; 361 fNew->trail = NULL; 362 fNew->marked = TOOLS_GLU_FALSE; 362 fNew->marked = TOOLS_GLU_FALSE; 363 363 364 /* The new face is marked "inside" if the ol 364 /* The new face is marked "inside" if the old one was. This is a 365 * convenience for the common case where a f 365 * convenience for the common case where a face has been split in two. 366 */ 366 */ 367 fNew->inside = fNext->inside; 367 fNew->inside = fNext->inside; 368 368 369 /* fix other edges on this face loop */ 369 /* fix other edges on this face loop */ 370 e = eOrig; 370 e = eOrig; 371 do { 371 do { 372 e->Lface = fNew; 372 e->Lface = fNew; 373 e = e->Lnext; 373 e = e->Lnext; 374 } while( e != eOrig ); 374 } while( e != eOrig ); 375 } 375 } 376 376 377 /* KillEdge( eDel ) destroys an edge (the half 377 /* KillEdge( eDel ) destroys an edge (the half-edges eDel and eDel->Sym), 378 * and removes from the global edge list. 378 * and removes from the global edge list. 379 */ 379 */ 380 inline/*static*/ void static_KillEdge( GLUhalf 380 inline/*static*/ void static_KillEdge( GLUhalfEdge *eDel ) 381 { 381 { 382 GLUhalfEdge *ePrev, *eNext; 382 GLUhalfEdge *ePrev, *eNext; 383 383 384 /* Half-edges are allocated in pairs, see Ed 384 /* Half-edges are allocated in pairs, see EdgePair above */ 385 if( eDel->Sym < eDel ) { eDel = eDel->Sym; } 385 if( eDel->Sym < eDel ) { eDel = eDel->Sym; } 386 386 387 /* delete from circular doubly-linked list * 387 /* delete from circular doubly-linked list */ 388 eNext = eDel->next; 388 eNext = eDel->next; 389 ePrev = eDel->Sym->next; 389 ePrev = eDel->Sym->next; 390 eNext->Sym->next = ePrev; 390 eNext->Sym->next = ePrev; 391 ePrev->Sym->next = eNext; 391 ePrev->Sym->next = eNext; 392 392 393 memFree( eDel ); 393 memFree( eDel ); 394 } 394 } 395 395 396 396 397 /* KillVertex( vDel ) destroys a vertex and re 397 /* KillVertex( vDel ) destroys a vertex and removes it from the global 398 * vertex list. It updates the vertex loop to 398 * vertex list. It updates the vertex loop to point to a given new vertex. 399 */ 399 */ 400 inline/*static*/ void static_KillVertex( GLUve 400 inline/*static*/ void static_KillVertex( GLUvertex *vDel, GLUvertex *newOrg ) 401 { 401 { 402 GLUhalfEdge *e, *eStart = vDel->anEdge; 402 GLUhalfEdge *e, *eStart = vDel->anEdge; 403 GLUvertex *vPrev, *vNext; 403 GLUvertex *vPrev, *vNext; 404 404 405 /* change the origin of all affected edges * 405 /* change the origin of all affected edges */ 406 e = eStart; 406 e = eStart; 407 do { 407 do { 408 e->Org = newOrg; 408 e->Org = newOrg; 409 e = e->Onext; 409 e = e->Onext; 410 } while( e != eStart ); 410 } while( e != eStart ); 411 411 412 /* delete from circular doubly-linked list * 412 /* delete from circular doubly-linked list */ 413 vPrev = vDel->prev; 413 vPrev = vDel->prev; 414 vNext = vDel->next; 414 vNext = vDel->next; 415 vNext->prev = vPrev; 415 vNext->prev = vPrev; 416 vPrev->next = vNext; 416 vPrev->next = vNext; 417 417 418 memFree( vDel ); 418 memFree( vDel ); 419 } 419 } 420 420 421 /* KillFace( fDel ) destroys a face and remove 421 /* KillFace( fDel ) destroys a face and removes it from the global face 422 * list. It updates the face loop to point to 422 * list. It updates the face loop to point to a given new face. 423 */ 423 */ 424 inline/*static*/ void static_KillFace( GLUface 424 inline/*static*/ void static_KillFace( GLUface *fDel, GLUface *newLface ) 425 { 425 { 426 GLUhalfEdge *e, *eStart = fDel->anEdge; 426 GLUhalfEdge *e, *eStart = fDel->anEdge; 427 GLUface *fPrev, *fNext; 427 GLUface *fPrev, *fNext; 428 428 429 /* change the left face of all affected edge 429 /* change the left face of all affected edges */ 430 e = eStart; 430 e = eStart; 431 do { 431 do { 432 e->Lface = newLface; 432 e->Lface = newLface; 433 e = e->Lnext; 433 e = e->Lnext; 434 } while( e != eStart ); 434 } while( e != eStart ); 435 435 436 /* delete from circular doubly-linked list * 436 /* delete from circular doubly-linked list */ 437 fPrev = fDel->prev; 437 fPrev = fDel->prev; 438 fNext = fDel->next; 438 fNext = fDel->next; 439 fNext->prev = fPrev; 439 fNext->prev = fPrev; 440 fPrev->next = fNext; 440 fPrev->next = fNext; 441 441 442 memFree( fDel ); 442 memFree( fDel ); 443 } 443 } 444 444 445 445 446 /****************** Basic Edge Operations **** 446 /****************** Basic Edge Operations **********************/ 447 447 448 /* __gl_meshMakeEdge creates one edge, two ver 448 /* __gl_meshMakeEdge creates one edge, two vertices, and a loop (face). 449 * The loop consists of the two new half-edges 449 * The loop consists of the two new half-edges. 450 */ 450 */ 451 inline GLUhalfEdge *__gl_meshMakeEdge( GLUmesh 451 inline GLUhalfEdge *__gl_meshMakeEdge( GLUmesh *mesh ) 452 { 452 { 453 GLUvertex *newVertex1= static_allocVertex(); 453 GLUvertex *newVertex1= static_allocVertex(); 454 GLUvertex *newVertex2= static_allocVertex(); 454 GLUvertex *newVertex2= static_allocVertex(); 455 GLUface *newFace= static_allocFace(); 455 GLUface *newFace= static_allocFace(); 456 GLUhalfEdge *e; 456 GLUhalfEdge *e; 457 457 458 /* if any one is null then all get freed */ 458 /* if any one is null then all get freed */ 459 if (newVertex1 == NULL || newVertex2 == NULL 459 if (newVertex1 == NULL || newVertex2 == NULL || newFace == NULL) { 460 if (newVertex1 != NULL) memFree(newVertex 460 if (newVertex1 != NULL) memFree(newVertex1); 461 if (newVertex2 != NULL) memFree(newVertex 461 if (newVertex2 != NULL) memFree(newVertex2); 462 if (newFace != NULL) memFree(newFace); 462 if (newFace != NULL) memFree(newFace); 463 return NULL; 463 return NULL; 464 } 464 } 465 465 466 e = static_MakeEdge( &mesh->eHead ); 466 e = static_MakeEdge( &mesh->eHead ); 467 if (e == NULL) { 467 if (e == NULL) { 468 memFree(newVertex1); 468 memFree(newVertex1); 469 memFree(newVertex2); 469 memFree(newVertex2); 470 memFree(newFace); 470 memFree(newFace); 471 return NULL; 471 return NULL; 472 } 472 } 473 473 474 static_MakeVertex( newVertex1, e, &mesh->vHe 474 static_MakeVertex( newVertex1, e, &mesh->vHead ); 475 static_MakeVertex( newVertex2, e->Sym, &mesh 475 static_MakeVertex( newVertex2, e->Sym, &mesh->vHead ); 476 static_MakeFace( newFace, e, &mesh->fHead ); 476 static_MakeFace( newFace, e, &mesh->fHead ); 477 return e; 477 return e; 478 } 478 } 479 479 480 480 481 /* __gl_meshSplice( eOrg, eDst ) is the basic 481 /* __gl_meshSplice( eOrg, eDst ) is the basic operation for changing the 482 * mesh connectivity and topology. It changes 482 * mesh connectivity and topology. It changes the mesh so that 483 * eOrg->Onext <- OLD( eDst->Onext ) 483 * eOrg->Onext <- OLD( eDst->Onext ) 484 * eDst->Onext <- OLD( eOrg->Onext ) 484 * eDst->Onext <- OLD( eOrg->Onext ) 485 * where OLD(...) means the value before the m 485 * where OLD(...) means the value before the meshSplice operation. 486 * 486 * 487 * This can have two effects on the vertex str 487 * This can have two effects on the vertex structure: 488 * - if eOrg->Org != eDst->Org, the two verti 488 * - if eOrg->Org != eDst->Org, the two vertices are merged together 489 * - if eOrg->Org == eDst->Org, the origin is 489 * - if eOrg->Org == eDst->Org, the origin is split into two vertices 490 * In both cases, eDst->Org is changed and eOr 490 * In both cases, eDst->Org is changed and eOrg->Org is untouched. 491 * 491 * 492 * Similarly (and independently) for the face 492 * Similarly (and independently) for the face structure, 493 * - if eOrg->Lface == eDst->Lface, one loop 493 * - if eOrg->Lface == eDst->Lface, one loop is split into two 494 * - if eOrg->Lface != eDst->Lface, two disti 494 * - if eOrg->Lface != eDst->Lface, two distinct loops are joined into one 495 * In both cases, eDst->Lface is changed and e 495 * In both cases, eDst->Lface is changed and eOrg->Lface is unaffected. 496 * 496 * 497 * Some special cases: 497 * Some special cases: 498 * If eDst == eOrg, the operation has no effec 498 * If eDst == eOrg, the operation has no effect. 499 * If eDst == eOrg->Lnext, the new face will h 499 * If eDst == eOrg->Lnext, the new face will have a single edge. 500 * If eDst == eOrg->Lprev, the old face will h 500 * If eDst == eOrg->Lprev, the old face will have a single edge. 501 * If eDst == eOrg->Onext, the new vertex will 501 * If eDst == eOrg->Onext, the new vertex will have a single edge. 502 * If eDst == eOrg->Oprev, the old vertex will 502 * If eDst == eOrg->Oprev, the old vertex will have a single edge. 503 */ 503 */ 504 inline int __gl_meshSplice( GLUhalfEdge *eOrg, 504 inline int __gl_meshSplice( GLUhalfEdge *eOrg, GLUhalfEdge *eDst ) 505 { 505 { 506 int joiningLoops = TOOLS_GLU_FALSE; 506 int joiningLoops = TOOLS_GLU_FALSE; 507 int joiningVertices = TOOLS_GLU_FALSE; 507 int joiningVertices = TOOLS_GLU_FALSE; 508 508 509 if( eOrg == eDst ) return 1; 509 if( eOrg == eDst ) return 1; 510 510 511 if( eDst->Org != eOrg->Org ) { 511 if( eDst->Org != eOrg->Org ) { 512 /* We are merging two disjoint vertices -- 512 /* We are merging two disjoint vertices -- destroy eDst->Org */ 513 joiningVertices = TOOLS_GLU_TRUE; 513 joiningVertices = TOOLS_GLU_TRUE; 514 static_KillVertex( eDst->Org, eOrg->Org ); 514 static_KillVertex( eDst->Org, eOrg->Org ); 515 } 515 } 516 if( eDst->Lface != eOrg->Lface ) { 516 if( eDst->Lface != eOrg->Lface ) { 517 /* We are connecting two disjoint loops -- 517 /* We are connecting two disjoint loops -- destroy eDst->Lface */ 518 joiningLoops = TOOLS_GLU_TRUE; 518 joiningLoops = TOOLS_GLU_TRUE; 519 static_KillFace( eDst->Lface, eOrg->Lface 519 static_KillFace( eDst->Lface, eOrg->Lface ); 520 } 520 } 521 521 522 /* Change the edge structure */ 522 /* Change the edge structure */ 523 static_Splice( eDst, eOrg ); 523 static_Splice( eDst, eOrg ); 524 524 525 if( ! joiningVertices ) { 525 if( ! joiningVertices ) { 526 GLUvertex *newVertex= static_allocVertex() 526 GLUvertex *newVertex= static_allocVertex(); 527 if (newVertex == NULL) return 0; 527 if (newVertex == NULL) return 0; 528 528 529 /* We split one vertex into two -- the new 529 /* We split one vertex into two -- the new vertex is eDst->Org. 530 * Make sure the old vertex points to a va 530 * Make sure the old vertex points to a valid half-edge. 531 */ 531 */ 532 static_MakeVertex( newVertex, eDst, eOrg-> 532 static_MakeVertex( newVertex, eDst, eOrg->Org ); 533 eOrg->Org->anEdge = eOrg; 533 eOrg->Org->anEdge = eOrg; 534 } 534 } 535 if( ! joiningLoops ) { 535 if( ! joiningLoops ) { 536 GLUface *newFace= static_allocFace(); 536 GLUface *newFace= static_allocFace(); 537 if (newFace == NULL) return 0; 537 if (newFace == NULL) return 0; 538 538 539 /* We split one loop into two -- the new l 539 /* We split one loop into two -- the new loop is eDst->Lface. 540 * Make sure the old face points to a vali 540 * Make sure the old face points to a valid half-edge. 541 */ 541 */ 542 static_MakeFace( newFace, eDst, eOrg->Lfac 542 static_MakeFace( newFace, eDst, eOrg->Lface ); 543 eOrg->Lface->anEdge = eOrg; 543 eOrg->Lface->anEdge = eOrg; 544 } 544 } 545 545 546 return 1; 546 return 1; 547 } 547 } 548 548 549 549 550 /* __gl_meshDelete( eDel ) removes the edge eD 550 /* __gl_meshDelete( eDel ) removes the edge eDel. There are several cases: 551 * if (eDel->Lface != eDel->Rface), we join tw 551 * if (eDel->Lface != eDel->Rface), we join two loops into one; the loop 552 * eDel->Lface is deleted. Otherwise, we are 552 * eDel->Lface is deleted. Otherwise, we are splitting one loop into two; 553 * the newly created loop will contain eDel->D 553 * the newly created loop will contain eDel->Dst. If the deletion of eDel 554 * would create isolated vertices, those are d 554 * would create isolated vertices, those are deleted as well. 555 * 555 * 556 * This function could be implemented as two c 556 * This function could be implemented as two calls to __gl_meshSplice 557 * plus a few calls to memFree, but this would 557 * plus a few calls to memFree, but this would allocate and delete 558 * unnecessary vertices and faces. 558 * unnecessary vertices and faces. 559 */ 559 */ 560 inline int __gl_meshDelete( GLUhalfEdge *eDel 560 inline int __gl_meshDelete( GLUhalfEdge *eDel ) 561 { 561 { 562 GLUhalfEdge *eDelSym = eDel->Sym; 562 GLUhalfEdge *eDelSym = eDel->Sym; 563 int joiningLoops = TOOLS_GLU_FALSE; 563 int joiningLoops = TOOLS_GLU_FALSE; 564 564 565 /* First step: disconnect the origin vertex 565 /* First step: disconnect the origin vertex eDel->Org. We make all 566 * changes to get a consistent mesh in this 566 * changes to get a consistent mesh in this "intermediate" state. 567 */ 567 */ 568 if( eDel->Lface != eDel->Rface ) { 568 if( eDel->Lface != eDel->Rface ) { 569 /* We are joining two loops into one -- re 569 /* We are joining two loops into one -- remove the left face */ 570 joiningLoops = TOOLS_GLU_TRUE; 570 joiningLoops = TOOLS_GLU_TRUE; 571 static_KillFace( eDel->Lface, eDel->Rface 571 static_KillFace( eDel->Lface, eDel->Rface ); 572 /* G.Barrand : note : Coverity says that t 572 /* G.Barrand : note : Coverity says that there is a problem using eDel->Lface->anEdge in the below, 573 but it appears that at the out of the u 573 but it appears that at the out of the upper static_KillFace() call (then here), eDel->Lface before 574 (the pointer freeed) is not the same th 574 (the pointer freeed) is not the same than after (then here). */ 575 } 575 } 576 576 577 if( eDel->Onext == eDel ) { 577 if( eDel->Onext == eDel ) { 578 static_KillVertex( eDel->Org, NULL ); 578 static_KillVertex( eDel->Org, NULL ); 579 } else { 579 } else { 580 /* Make sure that eDel->Org and eDel->Rfac 580 /* Make sure that eDel->Org and eDel->Rface point to valid half-edges */ 581 eDel->Rface->anEdge = eDel->Oprev; 581 eDel->Rface->anEdge = eDel->Oprev; 582 eDel->Org->anEdge = eDel->Onext; 582 eDel->Org->anEdge = eDel->Onext; 583 583 584 static_Splice( eDel, eDel->Oprev ); 584 static_Splice( eDel, eDel->Oprev ); 585 if( ! joiningLoops ) { 585 if( ! joiningLoops ) { 586 GLUface *newFace= static_allocFace(); 586 GLUface *newFace= static_allocFace(); 587 if (newFace == NULL) return 0; 587 if (newFace == NULL) return 0; 588 588 589 /* We are splitting one loop into two -- 589 /* We are splitting one loop into two -- create a new loop for eDel. */ 590 static_MakeFace( newFace, eDel, eDel->Lf 590 static_MakeFace( newFace, eDel, eDel->Lface ); 591 } 591 } 592 } 592 } 593 593 594 /* Claim: the mesh is now in a consistent st 594 /* Claim: the mesh is now in a consistent state, except that eDel->Org 595 * may have been deleted. Now we disconnect 595 * may have been deleted. Now we disconnect eDel->Dst. 596 */ 596 */ 597 if( eDelSym->Onext == eDelSym ) { 597 if( eDelSym->Onext == eDelSym ) { 598 static_KillVertex( eDelSym->Org, NULL ); 598 static_KillVertex( eDelSym->Org, NULL ); 599 static_KillFace( eDelSym->Lface, NULL ); 599 static_KillFace( eDelSym->Lface, NULL ); 600 } else { 600 } else { 601 /* Make sure that eDel->Dst and eDel->Lfac 601 /* Make sure that eDel->Dst and eDel->Lface point to valid half-edges */ 602 eDel->Lface->anEdge = eDelSym->Oprev; 602 eDel->Lface->anEdge = eDelSym->Oprev; 603 eDelSym->Org->anEdge = eDelSym->Onext; 603 eDelSym->Org->anEdge = eDelSym->Onext; 604 static_Splice( eDelSym, eDelSym->Oprev ); 604 static_Splice( eDelSym, eDelSym->Oprev ); 605 } 605 } 606 606 607 /* Any isolated vertices or faces have alrea 607 /* Any isolated vertices or faces have already been freed. */ 608 static_KillEdge( eDel ); 608 static_KillEdge( eDel ); 609 609 610 return 1; 610 return 1; 611 } 611 } 612 612 613 613 614 /******************** Other Edge Operations ** 614 /******************** Other Edge Operations **********************/ 615 615 616 /* All these routines can be implemented with 616 /* All these routines can be implemented with the basic edge 617 * operations above. They are provided for co 617 * operations above. They are provided for convenience and efficiency. 618 */ 618 */ 619 619 620 620 621 /* __gl_meshAddEdgeVertex( eOrg ) creates a ne 621 /* __gl_meshAddEdgeVertex( eOrg ) creates a new edge eNew such that 622 * eNew == eOrg->Lnext, and eNew->Dst is a new 622 * eNew == eOrg->Lnext, and eNew->Dst is a newly created vertex. 623 * eOrg and eNew will have the same left face. 623 * eOrg and eNew will have the same left face. 624 */ 624 */ 625 inline GLUhalfEdge *__gl_meshAddEdgeVertex( GL 625 inline GLUhalfEdge *__gl_meshAddEdgeVertex( GLUhalfEdge *eOrg ) 626 { 626 { 627 GLUhalfEdge *eNewSym; 627 GLUhalfEdge *eNewSym; 628 GLUhalfEdge *eNew = static_MakeEdge( eOrg ); 628 GLUhalfEdge *eNew = static_MakeEdge( eOrg ); 629 if (eNew == NULL) return NULL; 629 if (eNew == NULL) return NULL; 630 630 631 eNewSym = eNew->Sym; 631 eNewSym = eNew->Sym; 632 632 633 /* Connect the new edge appropriately */ 633 /* Connect the new edge appropriately */ 634 static_Splice( eNew, eOrg->Lnext ); 634 static_Splice( eNew, eOrg->Lnext ); 635 635 636 /* Set the vertex and face information */ 636 /* Set the vertex and face information */ 637 eNew->Org = eOrg->Dst; 637 eNew->Org = eOrg->Dst; 638 { 638 { 639 GLUvertex *newVertex= static_allocVertex() 639 GLUvertex *newVertex= static_allocVertex(); 640 if (newVertex == NULL) return NULL; 640 if (newVertex == NULL) return NULL; 641 641 642 static_MakeVertex( newVertex, eNewSym, eNe 642 static_MakeVertex( newVertex, eNewSym, eNew->Org ); 643 } 643 } 644 eNew->Lface = eNewSym->Lface = eOrg->Lface; 644 eNew->Lface = eNewSym->Lface = eOrg->Lface; 645 645 646 return eNew; 646 return eNew; 647 } 647 } 648 648 649 649 650 /* __gl_meshSplitEdge( eOrg ) splits eOrg into 650 /* __gl_meshSplitEdge( eOrg ) splits eOrg into two edges eOrg and eNew, 651 * such that eNew == eOrg->Lnext. The new ver 651 * such that eNew == eOrg->Lnext. The new vertex is eOrg->Dst == eNew->Org. 652 * eOrg and eNew will have the same left face. 652 * eOrg and eNew will have the same left face. 653 */ 653 */ 654 inline GLUhalfEdge *__gl_meshSplitEdge( GLUhal 654 inline GLUhalfEdge *__gl_meshSplitEdge( GLUhalfEdge *eOrg ) 655 { 655 { 656 GLUhalfEdge *eNew; 656 GLUhalfEdge *eNew; 657 GLUhalfEdge *tempHalfEdge= __gl_meshAddEdgeV 657 GLUhalfEdge *tempHalfEdge= __gl_meshAddEdgeVertex( eOrg ); 658 if (tempHalfEdge == NULL) return NULL; 658 if (tempHalfEdge == NULL) return NULL; 659 659 660 eNew = tempHalfEdge->Sym; 660 eNew = tempHalfEdge->Sym; 661 661 662 /* Disconnect eOrg from eOrg->Dst and connec 662 /* Disconnect eOrg from eOrg->Dst and connect it to eNew->Org */ 663 static_Splice( eOrg->Sym, eOrg->Sym->Oprev ) 663 static_Splice( eOrg->Sym, eOrg->Sym->Oprev ); 664 static_Splice( eOrg->Sym, eNew ); 664 static_Splice( eOrg->Sym, eNew ); 665 665 666 /* Set the vertex and face information */ 666 /* Set the vertex and face information */ 667 eOrg->Dst = eNew->Org; 667 eOrg->Dst = eNew->Org; 668 eNew->Dst->anEdge = eNew->Sym; /* may have 668 eNew->Dst->anEdge = eNew->Sym; /* may have pointed to eOrg->Sym */ 669 eNew->Rface = eOrg->Rface; 669 eNew->Rface = eOrg->Rface; 670 eNew->winding = eOrg->winding; /* copy old 670 eNew->winding = eOrg->winding; /* copy old winding information */ 671 eNew->Sym->winding = eOrg->Sym->winding; 671 eNew->Sym->winding = eOrg->Sym->winding; 672 672 673 return eNew; 673 return eNew; 674 } 674 } 675 675 676 676 677 /* __gl_meshConnect( eOrg, eDst ) creates a ne 677 /* __gl_meshConnect( eOrg, eDst ) creates a new edge from eOrg->Dst 678 * to eDst->Org, and returns the corresponding 678 * to eDst->Org, and returns the corresponding half-edge eNew. 679 * If eOrg->Lface == eDst->Lface, this splits 679 * If eOrg->Lface == eDst->Lface, this splits one loop into two, 680 * and the newly created loop is eNew->Lface. 680 * and the newly created loop is eNew->Lface. Otherwise, two disjoint 681 * loops are merged into one, and the loop eDs 681 * loops are merged into one, and the loop eDst->Lface is destroyed. 682 * 682 * 683 * If (eOrg == eDst), the new face will have o 683 * If (eOrg == eDst), the new face will have only two edges. 684 * If (eOrg->Lnext == eDst), the old face is r 684 * If (eOrg->Lnext == eDst), the old face is reduced to a single edge. 685 * If (eOrg->Lnext->Lnext == eDst), the old fa 685 * If (eOrg->Lnext->Lnext == eDst), the old face is reduced to two edges. 686 */ 686 */ 687 inline GLUhalfEdge *__gl_meshConnect( GLUhalfE 687 inline GLUhalfEdge *__gl_meshConnect( GLUhalfEdge *eOrg, GLUhalfEdge *eDst ) 688 { 688 { 689 GLUhalfEdge *eNewSym; 689 GLUhalfEdge *eNewSym; 690 int joiningLoops = TOOLS_GLU_FALSE; 690 int joiningLoops = TOOLS_GLU_FALSE; 691 GLUhalfEdge *eNew = static_MakeEdge( eOrg ); 691 GLUhalfEdge *eNew = static_MakeEdge( eOrg ); 692 if (eNew == NULL) return NULL; 692 if (eNew == NULL) return NULL; 693 693 694 eNewSym = eNew->Sym; 694 eNewSym = eNew->Sym; 695 695 696 if( eDst->Lface != eOrg->Lface ) { 696 if( eDst->Lface != eOrg->Lface ) { 697 /* We are connecting two disjoint loops -- 697 /* We are connecting two disjoint loops -- destroy eDst->Lface */ 698 joiningLoops = TOOLS_GLU_TRUE; 698 joiningLoops = TOOLS_GLU_TRUE; 699 static_KillFace( eDst->Lface, eOrg->Lface 699 static_KillFace( eDst->Lface, eOrg->Lface ); 700 } 700 } 701 701 702 /* Connect the new edge appropriately */ 702 /* Connect the new edge appropriately */ 703 static_Splice( eNew, eOrg->Lnext ); 703 static_Splice( eNew, eOrg->Lnext ); 704 static_Splice( eNewSym, eDst ); 704 static_Splice( eNewSym, eDst ); 705 705 706 /* Set the vertex and face information */ 706 /* Set the vertex and face information */ 707 eNew->Org = eOrg->Dst; 707 eNew->Org = eOrg->Dst; 708 eNewSym->Org = eDst->Org; 708 eNewSym->Org = eDst->Org; 709 eNew->Lface = eNewSym->Lface = eOrg->Lface; 709 eNew->Lface = eNewSym->Lface = eOrg->Lface; 710 710 711 /* Make sure the old face points to a valid 711 /* Make sure the old face points to a valid half-edge */ 712 eOrg->Lface->anEdge = eNewSym; 712 eOrg->Lface->anEdge = eNewSym; 713 713 714 if( ! joiningLoops ) { 714 if( ! joiningLoops ) { 715 GLUface *newFace= static_allocFace(); 715 GLUface *newFace= static_allocFace(); 716 if (newFace == NULL) return NULL; 716 if (newFace == NULL) return NULL; 717 717 718 /* We split one loop into two -- the new l 718 /* We split one loop into two -- the new loop is eNew->Lface */ 719 static_MakeFace( newFace, eNew, eOrg->Lfac 719 static_MakeFace( newFace, eNew, eOrg->Lface ); 720 } 720 } 721 return eNew; 721 return eNew; 722 } 722 } 723 723 724 724 725 /******************** Other Operations ******* 725 /******************** Other Operations **********************/ 726 726 727 /* __gl_meshZapFace( fZap ) destroys a face an 727 /* __gl_meshZapFace( fZap ) destroys a face and removes it from the 728 * global face list. All edges of fZap will h 728 * global face list. All edges of fZap will have a NULL pointer as their 729 * left face. Any edges which also have a NUL 729 * left face. Any edges which also have a NULL pointer as their right face 730 * are deleted entirely (along with any isolat 730 * are deleted entirely (along with any isolated vertices this produces). 731 * An entire mesh can be deleted by zapping it 731 * An entire mesh can be deleted by zapping its faces, one at a time, 732 * in any order. Zapped faces cannot be used 732 * in any order. Zapped faces cannot be used in further mesh operations! 733 */ 733 */ 734 inline void __gl_meshZapFace( GLUface *fZap ) 734 inline void __gl_meshZapFace( GLUface *fZap ) 735 { 735 { 736 GLUhalfEdge *eStart = fZap->anEdge; 736 GLUhalfEdge *eStart = fZap->anEdge; 737 GLUhalfEdge *e, *eNext, *eSym; 737 GLUhalfEdge *e, *eNext, *eSym; 738 GLUface *fPrev, *fNext; 738 GLUface *fPrev, *fNext; 739 739 740 /* walk around face, deleting edges whose ri 740 /* walk around face, deleting edges whose right face is also NULL */ 741 eNext = eStart->Lnext; 741 eNext = eStart->Lnext; 742 do { 742 do { 743 e = eNext; 743 e = eNext; 744 eNext = e->Lnext; 744 eNext = e->Lnext; 745 745 746 e->Lface = NULL; 746 e->Lface = NULL; 747 if( e->Rface == NULL ) { 747 if( e->Rface == NULL ) { 748 /* delete the edge -- see __gl_MeshDelet 748 /* delete the edge -- see __gl_MeshDelete above */ 749 749 750 if( e->Onext == e ) { 750 if( e->Onext == e ) { 751 static_KillVertex( e->Org, NULL ); 751 static_KillVertex( e->Org, NULL ); 752 } else { 752 } else { 753 /* Make sure that e->Org points to a valid h 753 /* Make sure that e->Org points to a valid half-edge */ 754 e->Org->anEdge = e->Onext; 754 e->Org->anEdge = e->Onext; 755 static_Splice( e, e->Oprev ); 755 static_Splice( e, e->Oprev ); 756 } 756 } 757 eSym = e->Sym; 757 eSym = e->Sym; 758 if( eSym->Onext == eSym ) { 758 if( eSym->Onext == eSym ) { 759 static_KillVertex( eSym->Org, NULL ); 759 static_KillVertex( eSym->Org, NULL ); 760 } else { 760 } else { 761 /* Make sure that eSym->Org points to a vali 761 /* Make sure that eSym->Org points to a valid half-edge */ 762 eSym->Org->anEdge = eSym->Onext; 762 eSym->Org->anEdge = eSym->Onext; 763 static_Splice( eSym, eSym->Oprev ); 763 static_Splice( eSym, eSym->Oprev ); 764 } 764 } 765 static_KillEdge( e ); 765 static_KillEdge( e ); 766 } 766 } 767 } while( e != eStart ); 767 } while( e != eStart ); 768 768 769 /* delete from circular doubly-linked list * 769 /* delete from circular doubly-linked list */ 770 fPrev = fZap->prev; 770 fPrev = fZap->prev; 771 fNext = fZap->next; 771 fNext = fZap->next; 772 fNext->prev = fPrev; 772 fNext->prev = fPrev; 773 fPrev->next = fNext; 773 fPrev->next = fNext; 774 774 775 memFree( fZap ); 775 memFree( fZap ); 776 } 776 } 777 777 778 778 779 /* __gl_meshNewMesh() creates a new mesh with 779 /* __gl_meshNewMesh() creates a new mesh with no edges, no vertices, 780 * and no loops (what we usually call a "face" 780 * and no loops (what we usually call a "face"). 781 */ 781 */ 782 inline GLUmesh *__gl_meshNewMesh( void ) 782 inline GLUmesh *__gl_meshNewMesh( void ) 783 { 783 { 784 GLUvertex *v; 784 GLUvertex *v; 785 GLUface *f; 785 GLUface *f; 786 GLUhalfEdge *e; 786 GLUhalfEdge *e; 787 GLUhalfEdge *eSym; 787 GLUhalfEdge *eSym; 788 GLUmesh *mesh = (GLUmesh *)memAlloc( sizeof( 788 GLUmesh *mesh = (GLUmesh *)memAlloc( sizeof( GLUmesh )); 789 if (mesh == NULL) { 789 if (mesh == NULL) { 790 return NULL; 790 return NULL; 791 } 791 } 792 792 793 v = &mesh->vHead; 793 v = &mesh->vHead; 794 f = &mesh->fHead; 794 f = &mesh->fHead; 795 e = &mesh->eHead; 795 e = &mesh->eHead; 796 eSym = &mesh->eHeadSym; 796 eSym = &mesh->eHeadSym; 797 797 798 v->next = v->prev = v; 798 v->next = v->prev = v; 799 v->anEdge = NULL; 799 v->anEdge = NULL; 800 v->data = NULL; 800 v->data = NULL; 801 801 802 f->next = f->prev = f; 802 f->next = f->prev = f; 803 f->anEdge = NULL; 803 f->anEdge = NULL; 804 f->data = NULL; 804 f->data = NULL; 805 f->trail = NULL; 805 f->trail = NULL; 806 f->marked = TOOLS_GLU_FALSE; 806 f->marked = TOOLS_GLU_FALSE; 807 f->inside = TOOLS_GLU_FALSE; 807 f->inside = TOOLS_GLU_FALSE; 808 808 809 e->next = e; 809 e->next = e; 810 e->Sym = eSym; 810 e->Sym = eSym; 811 e->Onext = NULL; 811 e->Onext = NULL; 812 e->Lnext = NULL; 812 e->Lnext = NULL; 813 e->Org = NULL; 813 e->Org = NULL; 814 e->Lface = NULL; 814 e->Lface = NULL; 815 e->winding = 0; 815 e->winding = 0; 816 e->activeRegion = NULL; 816 e->activeRegion = NULL; 817 817 818 eSym->next = eSym; 818 eSym->next = eSym; 819 eSym->Sym = e; 819 eSym->Sym = e; 820 eSym->Onext = NULL; 820 eSym->Onext = NULL; 821 eSym->Lnext = NULL; 821 eSym->Lnext = NULL; 822 eSym->Org = NULL; 822 eSym->Org = NULL; 823 eSym->Lface = NULL; 823 eSym->Lface = NULL; 824 eSym->winding = 0; 824 eSym->winding = 0; 825 eSym->activeRegion = NULL; 825 eSym->activeRegion = NULL; 826 826 827 return mesh; 827 return mesh; 828 } 828 } 829 829 830 830 831 /* __gl_meshUnion( mesh1, mesh2 ) forms the un 831 /* __gl_meshUnion( mesh1, mesh2 ) forms the union of all structures in 832 * both meshes, and returns the new mesh (the 832 * both meshes, and returns the new mesh (the old meshes are destroyed). 833 */ 833 */ 834 inline GLUmesh *__gl_meshUnion( GLUmesh *mesh1 834 inline GLUmesh *__gl_meshUnion( GLUmesh *mesh1, GLUmesh *mesh2 ) 835 { 835 { 836 GLUface *f1 = &mesh1->fHead; 836 GLUface *f1 = &mesh1->fHead; 837 GLUvertex *v1 = &mesh1->vHead; 837 GLUvertex *v1 = &mesh1->vHead; 838 GLUhalfEdge *e1 = &mesh1->eHead; 838 GLUhalfEdge *e1 = &mesh1->eHead; 839 GLUface *f2 = &mesh2->fHead; 839 GLUface *f2 = &mesh2->fHead; 840 GLUvertex *v2 = &mesh2->vHead; 840 GLUvertex *v2 = &mesh2->vHead; 841 GLUhalfEdge *e2 = &mesh2->eHead; 841 GLUhalfEdge *e2 = &mesh2->eHead; 842 842 843 /* Add the faces, vertices, and edges of mes 843 /* Add the faces, vertices, and edges of mesh2 to those of mesh1 */ 844 if( f2->next != f2 ) { 844 if( f2->next != f2 ) { 845 f1->prev->next = f2->next; 845 f1->prev->next = f2->next; 846 f2->next->prev = f1->prev; 846 f2->next->prev = f1->prev; 847 f2->prev->next = f1; 847 f2->prev->next = f1; 848 f1->prev = f2->prev; 848 f1->prev = f2->prev; 849 } 849 } 850 850 851 if( v2->next != v2 ) { 851 if( v2->next != v2 ) { 852 v1->prev->next = v2->next; 852 v1->prev->next = v2->next; 853 v2->next->prev = v1->prev; 853 v2->next->prev = v1->prev; 854 v2->prev->next = v1; 854 v2->prev->next = v1; 855 v1->prev = v2->prev; 855 v1->prev = v2->prev; 856 } 856 } 857 857 858 if( e2->next != e2 ) { 858 if( e2->next != e2 ) { 859 e1->Sym->next->Sym->next = e2->next; 859 e1->Sym->next->Sym->next = e2->next; 860 e2->next->Sym->next = e1->Sym->next; 860 e2->next->Sym->next = e1->Sym->next; 861 e2->Sym->next->Sym->next = e1; 861 e2->Sym->next->Sym->next = e1; 862 e1->Sym->next = e2->Sym->next; 862 e1->Sym->next = e2->Sym->next; 863 } 863 } 864 864 865 memFree( mesh2 ); 865 memFree( mesh2 ); 866 return mesh1; 866 return mesh1; 867 } 867 } 868 868 869 869 870 #ifdef DELETE_BY_ZAPPING 870 #ifdef DELETE_BY_ZAPPING 871 871 872 /* __gl_meshDeleteMesh( mesh ) will free all s 872 /* __gl_meshDeleteMesh( mesh ) will free all storage for any valid mesh. 873 */ 873 */ 874 inline void __gl_meshDeleteMesh( GLUmesh *mesh 874 inline void __gl_meshDeleteMesh( GLUmesh *mesh ) 875 { 875 { 876 GLUface *fHead = &mesh->fHead; 876 GLUface *fHead = &mesh->fHead; 877 877 878 while( fHead->next != fHead ) { 878 while( fHead->next != fHead ) { 879 __gl_meshZapFace( fHead->next ); 879 __gl_meshZapFace( fHead->next ); 880 } 880 } 881 assert( mesh->vHead.next == &mesh->vHead ); 881 assert( mesh->vHead.next == &mesh->vHead ); 882 882 883 memFree( mesh ); 883 memFree( mesh ); 884 } 884 } 885 885 886 #else 886 #else 887 887 888 /* __gl_meshDeleteMesh( mesh ) will free all s 888 /* __gl_meshDeleteMesh( mesh ) will free all storage for any valid mesh. 889 */ 889 */ 890 inline void __gl_meshDeleteMesh( GLUmesh *mesh 890 inline void __gl_meshDeleteMesh( GLUmesh *mesh ) 891 { 891 { 892 GLUface *f, *fNext; 892 GLUface *f, *fNext; 893 GLUvertex *v, *vNext; 893 GLUvertex *v, *vNext; 894 GLUhalfEdge *e, *eNext; 894 GLUhalfEdge *e, *eNext; 895 895 896 for( f = mesh->fHead.next; f != &mesh->fHead 896 for( f = mesh->fHead.next; f != &mesh->fHead; f = fNext ) { 897 fNext = f->next; 897 fNext = f->next; 898 memFree( f ); 898 memFree( f ); 899 } 899 } 900 900 901 for( v = mesh->vHead.next; v != &mesh->vHead 901 for( v = mesh->vHead.next; v != &mesh->vHead; v = vNext ) { 902 vNext = v->next; 902 vNext = v->next; 903 memFree( v ); 903 memFree( v ); 904 } 904 } 905 905 906 for( e = mesh->eHead.next; e != &mesh->eHead 906 for( e = mesh->eHead.next; e != &mesh->eHead; e = eNext ) { 907 /* One call frees both e and e->Sym (see E 907 /* One call frees both e and e->Sym (see EdgePair above) */ 908 eNext = e->next; 908 eNext = e->next; 909 memFree( e ); 909 memFree( e ); 910 } 910 } 911 911 912 memFree( mesh ); 912 memFree( mesh ); 913 } 913 } 914 914 915 #endif 915 #endif 916 916 917 inline void __gl_meshCheckMesh( GLUmesh *mesh 917 inline void __gl_meshCheckMesh( GLUmesh *mesh ) 918 { 918 { 919 GLUface *fHead = &mesh->fHead; 919 GLUface *fHead = &mesh->fHead; 920 GLUvertex *vHead = &mesh->vHead; 920 GLUvertex *vHead = &mesh->vHead; 921 GLUhalfEdge *eHead = &mesh->eHead; 921 GLUhalfEdge *eHead = &mesh->eHead; 922 GLUface *f, *fPrev; 922 GLUface *f, *fPrev; 923 GLUvertex *v, *vPrev; 923 GLUvertex *v, *vPrev; 924 GLUhalfEdge *e, *ePrev; 924 GLUhalfEdge *e, *ePrev; 925 925 926 fPrev = fHead; 926 fPrev = fHead; 927 for( fPrev = fHead ; (f = fPrev->next) != fH 927 for( fPrev = fHead ; (f = fPrev->next) != fHead; fPrev = f) { 928 assert( f->prev == fPrev ); 928 assert( f->prev == fPrev ); 929 e = f->anEdge; 929 e = f->anEdge; 930 do { 930 do { 931 assert( e->Sym != e ); 931 assert( e->Sym != e ); 932 assert( e->Sym->Sym == e ); 932 assert( e->Sym->Sym == e ); 933 assert( e->Lnext->Onext->Sym == e ); 933 assert( e->Lnext->Onext->Sym == e ); 934 assert( e->Onext->Sym->Lnext == e ); 934 assert( e->Onext->Sym->Lnext == e ); 935 assert( e->Lface == f ); 935 assert( e->Lface == f ); 936 e = e->Lnext; 936 e = e->Lnext; 937 } while( e != f->anEdge ); 937 } while( e != f->anEdge ); 938 } 938 } 939 assert( f->prev == fPrev && f->anEdge == NUL 939 assert( f->prev == fPrev && f->anEdge == NULL && f->data == NULL ); 940 940 941 vPrev = vHead; 941 vPrev = vHead; 942 for( vPrev = vHead ; (v = vPrev->next) != vH 942 for( vPrev = vHead ; (v = vPrev->next) != vHead; vPrev = v) { 943 assert( v->prev == vPrev ); 943 assert( v->prev == vPrev ); 944 e = v->anEdge; 944 e = v->anEdge; 945 do { 945 do { 946 assert( e->Sym != e ); 946 assert( e->Sym != e ); 947 assert( e->Sym->Sym == e ); 947 assert( e->Sym->Sym == e ); 948 assert( e->Lnext->Onext->Sym == e ); 948 assert( e->Lnext->Onext->Sym == e ); 949 assert( e->Onext->Sym->Lnext == e ); 949 assert( e->Onext->Sym->Lnext == e ); 950 assert( e->Org == v ); 950 assert( e->Org == v ); 951 e = e->Onext; 951 e = e->Onext; 952 } while( e != v->anEdge ); 952 } while( e != v->anEdge ); 953 } 953 } 954 assert( v->prev == vPrev && v->anEdge == NUL 954 assert( v->prev == vPrev && v->anEdge == NULL && v->data == NULL ); 955 955 956 ePrev = eHead; 956 ePrev = eHead; 957 for( ePrev = eHead ; (e = ePrev->next) != eH 957 for( ePrev = eHead ; (e = ePrev->next) != eHead; ePrev = e) { 958 assert( e->Sym->next == ePrev->Sym ); 958 assert( e->Sym->next == ePrev->Sym ); 959 assert( e->Sym != e ); 959 assert( e->Sym != e ); 960 assert( e->Sym->Sym == e ); 960 assert( e->Sym->Sym == e ); 961 assert( e->Org != NULL ); 961 assert( e->Org != NULL ); 962 assert( e->Dst != NULL ); 962 assert( e->Dst != NULL ); 963 assert( e->Lnext->Onext->Sym == e ); 963 assert( e->Lnext->Onext->Sym == e ); 964 assert( e->Onext->Sym->Lnext == e ); 964 assert( e->Onext->Sym->Lnext == e ); 965 } 965 } 966 assert( e->Sym->next == ePrev->Sym 966 assert( e->Sym->next == ePrev->Sym 967 && e->Sym == &mesh->eHeadSym 967 && e->Sym == &mesh->eHeadSym 968 && e->Sym->Sym == e 968 && e->Sym->Sym == e 969 && e->Org == NULL && e->Dst == NULL 969 && e->Org == NULL && e->Dst == NULL 970 && e->Lface == NULL && e->Rface == NULL 970 && e->Lface == NULL && e->Rface == NULL ); 971 } 971 } 972 972 973 #endif 973 #endif