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