| 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; /* I
15
16 /* The mesh structure is similar in spirit, no
17 * to the "quad-edge" structure (see L. Guibas
18 * for the manipulation of general subdivision
19 * Voronoi diagrams, ACM Transactions on Graph
20 * For a simplified description, see the cours
21 * "Mathematical Foundations of Computer Graph
22 * Stanford bookstore (and taught during the f
23 * The implementation also borrows a tiny subs
24 * use in Mantyla's Geometric Work Bench (see
25 * to Sold Modeling, Computer Science Press, R
26 *
27 * The fundamental data structure is the "half
28 * go together to make an edge, but they point
29 * Each half-edge has a pointer to its mate (t
30 * its origin vertex (Org), the face on its le
31 * adjacent half-edges in the CCW direction ar
32 * (Onext) and around the left face (Lnext).
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
37 * Onext = edge CCW around origin vertex (kee
38 * Dnext = edge CCW around destination vertex
39 * Lnext = edge CCW around left face (dest be
40 * Rnext = edge CCW around right face (origin
41 *
42 * "prev" means to substitute CW for CCW in th
43 *
44 * The mesh keeps global lists of all vertices
45 * stored as doubly-linked circular lists with
46 * The mesh stores pointers to these dummy hea
47 *
48 * The circular edge list is special; since ha
49 * in pairs (e and e->Sym), each half-edge sto
50 * one direction. Starting at eHead and follo
51 * will visit each *edge* once (ie. e or e->Sy
52 * e->Sym stores a pointer in the opposite dir
53 * always true that e->Sym->next->Sym->next ==
54 *
55 * Each vertex has a pointer to next and previ
56 * circular list, and a pointer to a half-edge
57 * the origin (NULL if this is the dummy heade
58 * field "data" for client data.
59 *
60 * Each face has a pointer to the next and pre
61 * circular list, and a pointer to a half-edge
62 * the left face (NULL if this is the dummy he
63 * a field "data" for client data.
64 *
65 * Note that what we call a "face" is really a
66 * of more than one loop (ie. not simply conne
67 * record of this in the data structure. The
68 * several disconnected regions, so it may not
69 * the entire mesh by starting at a half-edge
70 * structure.
71 *
72 * The mesh does NOT support isolated vertices
73 * with its last edge. Similarly when two fac
74 * faces is deleted (see __gl_meshDelete below
75 * all face (loop) and vertex pointers must no
76 * mesh manipulation is finished, __gl_MeshZap
77 * faces of the mesh, one at a time. All exte
78 * before the mesh is returned to the client;
79 * a region which is not part of the output po
80 */
81
82 struct GLUvertex {
83 GLUvertex *next; /* next vertex (never NU
84 GLUvertex *prev; /* previous vertex (neve
85 GLUhalfEdge *anEdge; /* a half-edge with th
86 void *data; /* client's data */
87
88 /* Internal data (keep hidden) */
89 GLUdouble coords[3]; /* vertex location in
90 GLUdouble s, t; /* projection onto the swe
91 long pqHandle; /* to allow deletion from
92 };
93
94 struct GLUface {
95 GLUface *next; /* next face (never NULL)
96 GLUface *prev; /* previous face (never NU
97 GLUhalfEdge *anEdge; /* a half edge with th
98 void *data; /* room for client's data
99
100 /* Internal data (keep hidden) */
101 GLUface *trail; /* "stack" for conversion
102 GLUboolean marked; /* flag for conversion
103 GLUboolean inside; /* this face is in the
104 };
105
106 struct GLUhalfEdge {
107 GLUhalfEdge *next; /* doubly-linked list
108 GLUhalfEdge *Sym; /* same edge, opposite d
109 GLUhalfEdge *Onext; /* next edge CCW aroun
110 GLUhalfEdge *Lnext; /* next edge CCW aroun
111 GLUvertex *Org; /* origin vertex (Overtex
112 GLUface *Lface; /* left face */
113
114 /* Internal data (keep hidden) */
115 ActiveRegion *activeRegion; /* a region wi
116 int winding; /* change in winding number
117 from the ri
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 vert
133 GLUface fHead; /* dummy header for face l
134 GLUhalfEdge eHead; /* dummy header for ed
135 GLUhalfEdge eHeadSym; /* and its symmetric c
136 };
137
138 /* The mesh operations below have three motiva
139 * convenience, and efficiency. The basic mes
140 * Splice, and Delete. All the other edge ope
141 * in terms of these. The other operations ar
142 * and/or efficiency.
143 *
144 * When a face is split or a vertex is added,
145 * global list *before* the existing vertex or
146 * This makes it easier to process all vertice
147 * without worrying about processing the same
148 * when a face is split, the "inside" flag is
149 * Other internal data (v->data, v->activeRegi
150 * f->trail, e->winding) is set to zero.
151 *
152 * ********************** Basic Edge Operation
153 *
154 * __gl_meshMakeEdge( mesh ) creates one edge,
155 * The loop (face) consists of the two new hal
156 *
157 * __gl_meshSplice( eOrg, eDst ) is the basic
158 * mesh connectivity and topology. It changes
159 * eOrg->Onext <- OLD( eDst->Onext )
160 * eDst->Onext <- OLD( eOrg->Onext )
161 * where OLD(...) means the value before the m
162 *
163 * This can have two effects on the vertex str
164 * - if eOrg->Org != eDst->Org, the two verti
165 * - if eOrg->Org == eDst->Org, the origin is
166 * In both cases, eDst->Org is changed and eOr
167 *
168 * Similarly (and independently) for the face
169 * - if eOrg->Lface == eDst->Lface, one loop
170 * - if eOrg->Lface != eDst->Lface, two disti
171 * In both cases, eDst->Lface is changed and e
172 *
173 * __gl_meshDelete( eDel ) removes the edge eD
174 * if (eDel->Lface != eDel->Rface), we join tw
175 * eDel->Lface is deleted. Otherwise, we are
176 * the newly created loop will contain eDel->D
177 * would create isolated vertices, those are d
178 *
179 * ********************** Other Edge Operation
180 *
181 * __gl_meshAddEdgeVertex( eOrg ) creates a ne
182 * eNew == eOrg->Lnext, and eNew->Dst is a new
183 * eOrg and eNew will have the same left face.
184 *
185 * __gl_meshSplitEdge( eOrg ) splits eOrg into
186 * such that eNew == eOrg->Lnext. The new ver
187 * eOrg and eNew will have the same left face.
188 *
189 * __gl_meshConnect( eOrg, eDst ) creates a ne
190 * to eDst->Org, and returns the corresponding
191 * If eOrg->Lface == eDst->Lface, this splits
192 * and the newly created loop is eNew->Lface.
193 * loops are merged into one, and the loop eDs
194 *
195 * ************************ Other Operations *
196 *
197 * __gl_meshNewMesh() creates a new mesh with
198 * and no loops (what we usually call a "face"
199 *
200 * __gl_meshUnion( mesh1, mesh2 ) forms the un
201 * both meshes, and returns the new mesh (the
202 *
203 * __gl_meshDeleteMesh( mesh ) will free all s
204 *
205 * __gl_meshZapFace( fZap ) destroys a face an
206 * global face list. All edges of fZap will h
207 * left face. Any edges which also have a NUL
208 * are deleted entirely (along with any isolat
209 * An entire mesh can be deleted by zapping it
210 * in any order. Zapped faces cannot be used
211 *
212 * __gl_meshCheckMesh( mesh ) checks a mesh fo
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( GLUve
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 e
237 * The *only* place that should use this fact
238 */
239 typedef struct { GLUhalfEdge e, eSym; } EdgePa
240
241 /* MakeEdge creates a new pair of half-edges w
242 * No vertex or face structures are allocated,
243 * before the current edge operation is comple
244 */
245 inline/*static*/ GLUhalfEdge *static_MakeEdge(
246 {
247 GLUhalfEdge *e;
248 GLUhalfEdge *eSym;
249 GLUhalfEdge *ePrev;
250 EdgePair *pair = (EdgePair *)memAlloc( sizeo
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
257 if( eNext->Sym < eNext ) { eNext = eNext->Sy
258
259 /* Insert in circular doubly-linked list bef
260 * Note that the prev pointer is stored in S
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 Gui
288 * CS348a notes (see mesh.h). Basically it mo
289 * a->Onext and b->Onext are exchanged. This
290 * depending on whether a and b belong to diff
291 * For more explanation see __gl_meshSplice()
292 */
293 inline/*static*/ void static_Splice( GLUhalfEd
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 ) attac
305 * origin of all edges in the vertex loop to w
306 * a place to insert the new vertex in the glo
307 * the new vertex *before* vNext so that algor
308 * list will not see the newly created vertice
309 */
310 inline/*static*/ void static_MakeVertex( GLUve
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 bef
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
339 * face of all edges in the face loop to which
340 * a place to insert the new face in the globa
341 * the new face *before* fNext so that algorit
342 * list will not see the newly created faces.
343 */
344 inline/*static*/ void static_MakeFace( GLUface
345 {
346 GLUhalfEdge *e;
347 GLUface *fPrev;
348 GLUface *fNew = newFace;
349
350 assert(fNew != NULL);
351
352 /* insert in circular doubly-linked list bef
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 ol
365 * convenience for the common case where a f
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
378 * and removes from the global edge list.
379 */
380 inline/*static*/ void static_KillEdge( GLUhalf
381 {
382 GLUhalfEdge *ePrev, *eNext;
383
384 /* Half-edges are allocated in pairs, see Ed
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 re
398 * vertex list. It updates the vertex loop to
399 */
400 inline/*static*/ void static_KillVertex( GLUve
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 remove
422 * list. It updates the face loop to point to
423 */
424 inline/*static*/ void static_KillFace( GLUface
425 {
426 GLUhalfEdge *e, *eStart = fDel->anEdge;
427 GLUface *fPrev, *fNext;
428
429 /* change the left face of all affected edge
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 ver
449 * The loop consists of the two new half-edges
450 */
451 inline GLUhalfEdge *__gl_meshMakeEdge( GLUmesh
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
460 if (newVertex1 != NULL) memFree(newVertex
461 if (newVertex2 != NULL) memFree(newVertex
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->vHe
475 static_MakeVertex( newVertex2, e->Sym, &mesh
476 static_MakeFace( newFace, e, &mesh->fHead );
477 return e;
478 }
479
480
481 /* __gl_meshSplice( eOrg, eDst ) is the basic
482 * mesh connectivity and topology. It changes
483 * eOrg->Onext <- OLD( eDst->Onext )
484 * eDst->Onext <- OLD( eOrg->Onext )
485 * where OLD(...) means the value before the m
486 *
487 * This can have two effects on the vertex str
488 * - if eOrg->Org != eDst->Org, the two verti
489 * - if eOrg->Org == eDst->Org, the origin is
490 * In both cases, eDst->Org is changed and eOr
491 *
492 * Similarly (and independently) for the face
493 * - if eOrg->Lface == eDst->Lface, one loop
494 * - if eOrg->Lface != eDst->Lface, two disti
495 * In both cases, eDst->Lface is changed and e
496 *
497 * Some special cases:
498 * If eDst == eOrg, the operation has no effec
499 * If eDst == eOrg->Lnext, the new face will h
500 * If eDst == eOrg->Lprev, the old face will h
501 * If eDst == eOrg->Onext, the new vertex will
502 * If eDst == eOrg->Oprev, the old vertex will
503 */
504 inline int __gl_meshSplice( GLUhalfEdge *eOrg,
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 --
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 --
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
530 * Make sure the old vertex points to a va
531 */
532 static_MakeVertex( newVertex, eDst, eOrg->
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 l
540 * Make sure the old face points to a vali
541 */
542 static_MakeFace( newFace, eDst, eOrg->Lfac
543 eOrg->Lface->anEdge = eOrg;
544 }
545
546 return 1;
547 }
548
549
550 /* __gl_meshDelete( eDel ) removes the edge eD
551 * if (eDel->Lface != eDel->Rface), we join tw
552 * eDel->Lface is deleted. Otherwise, we are
553 * the newly created loop will contain eDel->D
554 * would create isolated vertices, those are d
555 *
556 * This function could be implemented as two c
557 * plus a few calls to memFree, but this would
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
566 * changes to get a consistent mesh in this
567 */
568 if( eDel->Lface != eDel->Rface ) {
569 /* We are joining two loops into one -- re
570 joiningLoops = TOOLS_GLU_TRUE;
571 static_KillFace( eDel->Lface, eDel->Rface
572 /* G.Barrand : note : Coverity says that t
573 but it appears that at the out of the u
574 (the pointer freeed) is not the same th
575 }
576
577 if( eDel->Onext == eDel ) {
578 static_KillVertex( eDel->Org, NULL );
579 } else {
580 /* Make sure that eDel->Org and eDel->Rfac
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 --
590 static_MakeFace( newFace, eDel, eDel->Lf
591 }
592 }
593
594 /* Claim: the mesh is now in a consistent st
595 * may have been deleted. Now we disconnect
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->Lfac
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 alrea
608 static_KillEdge( eDel );
609
610 return 1;
611 }
612
613
614 /******************** Other Edge Operations **
615
616 /* All these routines can be implemented with
617 * operations above. They are provided for co
618 */
619
620
621 /* __gl_meshAddEdgeVertex( eOrg ) creates a ne
622 * eNew == eOrg->Lnext, and eNew->Dst is a new
623 * eOrg and eNew will have the same left face.
624 */
625 inline GLUhalfEdge *__gl_meshAddEdgeVertex( GL
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, eNe
643 }
644 eNew->Lface = eNewSym->Lface = eOrg->Lface;
645
646 return eNew;
647 }
648
649
650 /* __gl_meshSplitEdge( eOrg ) splits eOrg into
651 * such that eNew == eOrg->Lnext. The new ver
652 * eOrg and eNew will have the same left face.
653 */
654 inline GLUhalfEdge *__gl_meshSplitEdge( GLUhal
655 {
656 GLUhalfEdge *eNew;
657 GLUhalfEdge *tempHalfEdge= __gl_meshAddEdgeV
658 if (tempHalfEdge == NULL) return NULL;
659
660 eNew = tempHalfEdge->Sym;
661
662 /* Disconnect eOrg from eOrg->Dst and connec
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
669 eNew->Rface = eOrg->Rface;
670 eNew->winding = eOrg->winding; /* copy old
671 eNew->Sym->winding = eOrg->Sym->winding;
672
673 return eNew;
674 }
675
676
677 /* __gl_meshConnect( eOrg, eDst ) creates a ne
678 * to eDst->Org, and returns the corresponding
679 * If eOrg->Lface == eDst->Lface, this splits
680 * and the newly created loop is eNew->Lface.
681 * loops are merged into one, and the loop eDs
682 *
683 * If (eOrg == eDst), the new face will have o
684 * If (eOrg->Lnext == eDst), the old face is r
685 * If (eOrg->Lnext->Lnext == eDst), the old fa
686 */
687 inline GLUhalfEdge *__gl_meshConnect( GLUhalfE
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 --
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
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 l
719 static_MakeFace( newFace, eNew, eOrg->Lfac
720 }
721 return eNew;
722 }
723
724
725 /******************** Other Operations *******
726
727 /* __gl_meshZapFace( fZap ) destroys a face an
728 * global face list. All edges of fZap will h
729 * left face. Any edges which also have a NUL
730 * are deleted entirely (along with any isolat
731 * An entire mesh can be deleted by zapping it
732 * in any order. Zapped faces cannot be used
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 ri
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_MeshDelet
749
750 if( e->Onext == e ) {
751 static_KillVertex( e->Org, NULL );
752 } else {
753 /* Make sure that e->Org points to a valid h
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 vali
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
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(
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 un
832 * both meshes, and returns the new mesh (the
833 */
834 inline GLUmesh *__gl_meshUnion( GLUmesh *mesh1
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 mes
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 s
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 s
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
897 fNext = f->next;
898 memFree( f );
899 }
900
901 for( v = mesh->vHead.next; v != &mesh->vHead
902 vNext = v->next;
903 memFree( v );
904 }
905
906 for( e = mesh->eHead.next; e != &mesh->eHead
907 /* One call frees both e and e->Sym (see E
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) != fH
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 == NUL
940
941 vPrev = vHead;
942 for( vPrev = vHead ; (v = vPrev->next) != vH
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 == NUL
955
956 ePrev = eHead;
957 for( ePrev = eHead ; (e = ePrev->next) != eH
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