Kstars

mesh.h
1 /*
2 ** Author: Eric Veach, July 1994.
3 **
4 */
5 
6 #ifndef __mesh_h_
7 #define __mesh_h_
8 
9 #include "glu.h"
10 
11 typedef struct GLUmesh GLUmesh;
12 
13 typedef struct GLUvertex GLUvertex;
14 typedef struct GLUface GLUface;
15 typedef struct GLUhalfEdge GLUhalfEdge;
16 
17 typedef struct ActiveRegion ActiveRegion; /* Internal data */
18 
19 /* The mesh structure is similar in spirit, notation, and operations
20  * to the "quad-edge" structure (see L. Guibas and J. Stolfi, Primitives
21  * for the manipulation of general subdivisions and the computation of
22  * Voronoi diagrams, ACM Transactions on Graphics, 4(2):74-123, April 1985).
23  * For a simplified description, see the course notes for CS348a,
24  * "Mathematical Foundations of Computer Graphics", available at the
25  * Stanford bookstore (and taught during the fall quarter).
26  * The implementation also borrows a tiny subset of the graph-based approach
27  * use in Mantyla's Geometric Work Bench (see M. Mantyla, An Introduction
28  * to Sold Modeling, Computer Science Press, Rockville, Maryland, 1988).
29  *
30  * The fundamental data structure is the "half-edge". Two half-edges
31  * go together to make an edge, but they point in opposite directions.
32  * Each half-edge has a pointer to its mate (the "symmetric" half-edge Sym),
33  * its origin vertex (Org), the face on its left side (Lface), and the
34  * adjacent half-edges in the CCW direction around the origin vertex
35  * (Onext) and around the left face (Lnext). There is also a "next"
36  * pointer for the global edge list (see below).
37  *
38  * The notation used for mesh navigation:
39  * Sym = the mate of a half-edge (same edge, but opposite direction)
40  * Onext = edge CCW around origin vertex (keep same origin)
41  * Dnext = edge CCW around destination vertex (keep same dest)
42  * Lnext = edge CCW around left face (dest becomes new origin)
43  * Rnext = edge CCW around right face (origin becomes new dest)
44  *
45  * "prev" means to substitute CW for CCW in the definitions above.
46  *
47  * The mesh keeps global lists of all vertices, faces, and edges,
48  * stored as doubly-linked circular lists with a dummy header node.
49  * The mesh stores pointers to these dummy headers (vHead, fHead, eHead).
50  *
51  * The circular edge list is special; since half-edges always occur
52  * in pairs (e and e->Sym), each half-edge stores a pointer in only
53  * one direction. Starting at eHead and following the e->next pointers
54  * will visit each *edge* once (ie. e or e->Sym, but not both).
55  * e->Sym stores a pointer in the opposite direction, thus it is
56  * always true that e->Sym->next->Sym->next == e.
57  *
58  * Each vertex has a pointer to next and previous vertices in the
59  * circular list, and a pointer to a half-edge with this vertex as
60  * the origin (NULL if this is the dummy header). There is also a
61  * field "data" for client data.
62  *
63  * Each face has a pointer to the next and previous faces in the
64  * circular list, and a pointer to a half-edge with this face as
65  * the left face (NULL if this is the dummy header). There is also
66  * a field "data" for client data.
67  *
68  * Note that what we call a "face" is really a loop; faces may consist
69  * of more than one loop (ie. not simply connected), but there is no
70  * record of this in the data structure. The mesh may consist of
71  * several disconnected regions, so it may not be possible to visit
72  * the entire mesh by starting at a half-edge and traversing the edge
73  * structure.
74  *
75  * The mesh does NOT support isolated vertices; a vertex is deleted along
76  * with its last edge. Similarly when two faces are merged, one of the
77  * faces is deleted (see __gl_meshDelete below). For mesh operations,
78  * all face (loop) and vertex pointers must not be NULL. However, once
79  * mesh manipulation is finished, __gl_MeshZapFace can be used to delete
80  * faces of the mesh, one at a time. All external faces can be "zapped"
81  * before the mesh is returned to the client; then a NULL face indicates
82  * a region which is not part of the output polygon.
83  */
84 
85 struct GLUvertex
86 {
87  GLUvertex *next; /* next vertex (never NULL) */
88  GLUvertex *prev; /* previous vertex (never NULL) */
89  GLUhalfEdge *anEdge; /* a half-edge with this origin */
90  void *data; /* client's data */
91 
92  /* Internal data (keep hidden) */
93  GLdouble coords[3]; /* vertex location in 3D */
94  GLdouble s, t; /* projection onto the sweep plane */
95  long pqHandle; /* to allow deletion from priority queue */
96 };
97 
98 struct GLUface
99 {
100  GLUface *next; /* next face (never NULL) */
101  GLUface *prev; /* previous face (never NULL) */
102  GLUhalfEdge *anEdge; /* a half edge with this left face */
103  void *data; /* room for client's data */
104 
105  /* Internal data (keep hidden) */
106  GLUface *trail; /* "stack" for conversion to strips */
107  GLboolean marked; /* flag for conversion to strips */
108  GLboolean inside; /* this face is in the polygon interior */
109 };
110 
111 struct GLUhalfEdge
112 {
113  GLUhalfEdge *next; /* doubly-linked list (prev==Sym->next) */
114  GLUhalfEdge *Sym; /* same edge, opposite direction */
115  GLUhalfEdge *Onext; /* next edge CCW around origin */
116  GLUhalfEdge *Lnext; /* next edge CCW around left face */
117  GLUvertex *Org; /* origin vertex (Overtex too long) */
118  GLUface *Lface; /* left face */
119 
120  /* Internal data (keep hidden) */
121  ActiveRegion *activeRegion; /* a region with this upper edge (sweep.c) */
122  int winding; /* change in winding number when crossing
123  from the right face to the left face */
124 };
125 
126 #define Rface Sym->Lface
127 #define Dst Sym->Org
128 
129 #define Oprev Sym->Lnext
130 #define Lprev Onext->Sym
131 #define Dprev Lnext->Sym
132 #define Rprev Sym->Onext
133 #define Dnext Rprev->Sym /* 3 pointers */
134 #define Rnext Oprev->Sym /* 3 pointers */
135 
136 struct GLUmesh
137 {
138  GLUvertex vHead; /* dummy header for vertex list */
139  GLUface fHead; /* dummy header for face list */
140  GLUhalfEdge eHead; /* dummy header for edge list */
141  GLUhalfEdge eHeadSym; /* and its symmetric counterpart */
142 };
143 
144 /* The mesh operations below have three motivations: completeness,
145  * convenience, and efficiency. The basic mesh operations are MakeEdge,
146  * Splice, and Delete. All the other edge operations can be implemented
147  * in terms of these. The other operations are provided for convenience
148  * and/or efficiency.
149  *
150  * When a face is split or a vertex is added, they are inserted into the
151  * global list *before* the existing vertex or face (ie. e->Org or e->Lface).
152  * This makes it easier to process all vertices or faces in the global lists
153  * without worrying about processing the same data twice. As a convenience,
154  * when a face is split, the "inside" flag is copied from the old face.
155  * Other internal data (v->data, v->activeRegion, f->data, f->marked,
156  * f->trail, e->winding) is set to zero.
157  *
158  * ********************** Basic Edge Operations **************************
159  *
160  * __gl_meshMakeEdge( mesh ) creates one edge, two vertices, and a loop.
161  * The loop (face) consists of the two new half-edges.
162  *
163  * __gl_meshSplice( eOrg, eDst ) is the basic operation for changing the
164  * mesh connectivity and topology. It changes the mesh so that
165  * eOrg->Onext <- OLD( eDst->Onext )
166  * eDst->Onext <- OLD( eOrg->Onext )
167  * where OLD(...) means the value before the meshSplice operation.
168  *
169  * This can have two effects on the vertex structure:
170  * - if eOrg->Org != eDst->Org, the two vertices are merged together
171  * - if eOrg->Org == eDst->Org, the origin is split into two vertices
172  * In both cases, eDst->Org is changed and eOrg->Org is untouched.
173  *
174  * Similarly (and independently) for the face structure,
175  * - if eOrg->Lface == eDst->Lface, one loop is split into two
176  * - if eOrg->Lface != eDst->Lface, two distinct loops are joined into one
177  * In both cases, eDst->Lface is changed and eOrg->Lface is unaffected.
178  *
179  * __gl_meshDelete( eDel ) removes the edge eDel. There are several cases:
180  * if (eDel->Lface != eDel->Rface), we join two loops into one; the loop
181  * eDel->Lface is deleted. Otherwise, we are splitting one loop into two;
182  * the newly created loop will contain eDel->Dst. If the deletion of eDel
183  * would create isolated vertices, those are deleted as well.
184  *
185  * ********************** Other Edge Operations **************************
186  *
187  * __gl_meshAddEdgeVertex( eOrg ) creates a new edge eNew such that
188  * eNew == eOrg->Lnext, and eNew->Dst is a newly created vertex.
189  * eOrg and eNew will have the same left face.
190  *
191  * __gl_meshSplitEdge( eOrg ) splits eOrg into two edges eOrg and eNew,
192  * such that eNew == eOrg->Lnext. The new vertex is eOrg->Dst == eNew->Org.
193  * eOrg and eNew will have the same left face.
194  *
195  * __gl_meshConnect( eOrg, eDst ) creates a new edge from eOrg->Dst
196  * to eDst->Org, and returns the corresponding half-edge eNew.
197  * If eOrg->Lface == eDst->Lface, this splits one loop into two,
198  * and the newly created loop is eNew->Lface. Otherwise, two disjoint
199  * loops are merged into one, and the loop eDst->Lface is destroyed.
200  *
201  * ************************ Other Operations *****************************
202  *
203  * __gl_meshNewMesh() creates a new mesh with no edges, no vertices,
204  * and no loops (what we usually call a "face").
205  *
206  * __gl_meshUnion( mesh1, mesh2 ) forms the union of all structures in
207  * both meshes, and returns the new mesh (the old meshes are destroyed).
208  *
209  * __gl_meshDeleteMesh( mesh ) will free all storage for any valid mesh.
210  *
211  * __gl_meshZapFace( fZap ) destroys a face and removes it from the
212  * global face list. All edges of fZap will have a NULL pointer as their
213  * left face. Any edges which also have a NULL pointer as their right face
214  * are deleted entirely (along with any isolated vertices this produces).
215  * An entire mesh can be deleted by zapping its faces, one at a time,
216  * in any order. Zapped faces cannot be used in further mesh operations!
217  *
218  * __gl_meshCheckMesh( mesh ) checks a mesh for self-consistency.
219  */
220 
221 GLUhalfEdge *__gl_meshMakeEdge(GLUmesh *mesh);
222 int __gl_meshSplice(GLUhalfEdge *eOrg, GLUhalfEdge *eDst);
223 int __gl_meshDelete(GLUhalfEdge *eDel);
224 
225 GLUhalfEdge *__gl_meshAddEdgeVertex(GLUhalfEdge *eOrg);
226 GLUhalfEdge *__gl_meshSplitEdge(GLUhalfEdge *eOrg);
227 GLUhalfEdge *__gl_meshConnect(GLUhalfEdge *eOrg, GLUhalfEdge *eDst);
228 
229 GLUmesh *__gl_meshNewMesh(void);
230 GLUmesh *__gl_meshUnion(GLUmesh *mesh1, GLUmesh *mesh2);
231 void __gl_meshDeleteMesh(GLUmesh *mesh);
232 void __gl_meshZapFace(GLUface *fZap);
233 
234 #ifdef NDEBUG
235 #define __gl_meshCheckMesh(mesh)
236 #else
237 void __gl_meshCheckMesh(GLUmesh *mesh);
238 #endif
239 
240 #endif
const QList< QKeySequence > & next()
This file is part of the KDE documentation.
Documentation copyright © 1996-2022 The KDE developers.
Generated on Thu Aug 11 2022 04:00:01 by doxygen 1.8.17 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.