| 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