Logo ROOT  
Reference Guide
mesh.h
Go to the documentation of this file.
1/*
2 * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008)
3 * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved.
4 *
5 * Permission is hereby granted, free of charge, to any person obtaining a
6 * copy of this software and associated documentation files (the "Software"),
7 * to deal in the Software without restriction, including without limitation
8 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
9 * and/or sell copies of the Software, and to permit persons to whom the
10 * Software is furnished to do so, subject to the following conditions:
11 *
12 * The above copyright notice including the dates of first publication and
13 * either this permission notice or a reference to
14 * http://oss.sgi.com/projects/FreeB/
15 * shall be included in all copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
18 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
20 * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
21 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
22 * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
23 * SOFTWARE.
24 *
25 * Except as contained in this notice, the name of Silicon Graphics, Inc.
26 * shall not be used in advertising or otherwise to promote the sale, use or
27 * other dealings in this Software without prior written authorization from
28 * Silicon Graphics, Inc.
29 */
30/*
31** Author: Eric Veach, July 1994.
32**
33*/
34
35#ifndef __mesh_h_
36#define __mesh_h_
37
38#include "GL_glu.h"
39
40typedef struct GLUmesh GLUmesh;
41
42typedef struct GLUvertex GLUvertex;
43typedef struct GLUface GLUface;
44typedef struct GLUhalfEdge GLUhalfEdge;
45
46typedef struct ActiveRegion ActiveRegion; /* Internal data */
47
48/* The mesh structure is similar in spirit, notation, and operations
49 * to the "quad-edge" structure (see L. Guibas and J. Stolfi, Primitives
50 * for the manipulation of general subdivisions and the computation of
51 * Voronoi diagrams, ACM Transactions on Graphics, 4(2):74-123, April 1985).
52 * For a simplified description, see the course notes for CS348a,
53 * "Mathematical Foundations of Computer Graphics", available at the
54 * Stanford bookstore (and taught during the fall quarter).
55 * The implementation also borrows a tiny subset of the graph-based approach
56 * use in Mantyla's Geometric Work Bench (see M. Mantyla, An Introduction
57 * to Sold Modeling, Computer Science Press, Rockville, Maryland, 1988).
58 *
59 * The fundamental data structure is the "half-edge". Two half-edges
60 * go together to make an edge, but they point in opposite directions.
61 * Each half-edge has a pointer to its mate (the "symmetric" half-edge Sym),
62 * its origin vertex (Org), the face on its left side (Lface), and the
63 * adjacent half-edges in the CCW direction around the origin vertex
64 * (Onext) and around the left face (Lnext). There is also a "next"
65 * pointer for the global edge list (see below).
66 *
67 * The notation used for mesh navigation:
68 * Sym = the mate of a half-edge (same edge, but opposite direction)
69 * Onext = edge CCW around origin vertex (keep same origin)
70 * Dnext = edge CCW around destination vertex (keep same dest)
71 * Lnext = edge CCW around left face (dest becomes new origin)
72 * Rnext = edge CCW around right face (origin becomes new dest)
73 *
74 * "prev" means to substitute CW for CCW in the definitions above.
75 *
76 * The mesh keeps global lists of all vertices, faces, and edges,
77 * stored as doubly-linked circular lists with a dummy header node.
78 * The mesh stores pointers to these dummy headers (vHead, fHead, eHead).
79 *
80 * The circular edge list is special; since half-edges always occur
81 * in pairs (e and e->Sym), each half-edge stores a pointer in only
82 * one direction. Starting at eHead and following the e->next pointers
83 * will visit each *edge* once (ie. e or e->Sym, but not both).
84 * e->Sym stores a pointer in the opposite direction, thus it is
85 * always true that e->Sym->next->Sym->next == e.
86 *
87 * Each vertex has a pointer to next and previous vertices in the
88 * circular list, and a pointer to a half-edge with this vertex as
89 * the origin (NULL if this is the dummy header). There is also a
90 * field "data" for client data.
91 *
92 * Each face has a pointer to the next and previous faces in the
93 * circular list, and a pointer to a half-edge with this face as
94 * the left face (NULL if this is the dummy header). There is also
95 * a field "data" for client data.
96 *
97 * Note that what we call a "face" is really a loop; faces may consist
98 * of more than one loop (ie. not simply connected), but there is no
99 * record of this in the data structure. The mesh may consist of
100 * several disconnected regions, so it may not be possible to visit
101 * the entire mesh by starting at a half-edge and traversing the edge
102 * structure.
103 *
104 * The mesh does NOT support isolated vertices; a vertex is deleted along
105 * with its last edge. Similarly when two faces are merged, one of the
106 * faces is deleted (see __gl_meshDelete below). For mesh operations,
107 * all face (loop) and vertex pointers must not be NULL. However, once
108 * mesh manipulation is finished, __gl_MeshZapFace can be used to delete
109 * faces of the mesh, one at a time. All external faces can be "zapped"
110 * before the mesh is returned to the client; then a NULL face indicates
111 * a region which is not part of the output polygon.
112 */
113
114struct GLUvertex {
115 GLUvertex *next; /* next vertex (never NULL) */
116 GLUvertex *prev; /* previous vertex (never NULL) */
117 GLUhalfEdge *anEdge; /* a half-edge with this origin */
118 void *data; /* client's data */
119
120 /* Internal data (keep hidden) */
121 GLdouble coords[3]; /* vertex location in 3D */
122 GLdouble s, t; /* projection onto the sweep plane */
123 long pqHandle; /* to allow deletion from priority queue */
124};
125
126struct GLUface {
127 GLUface *next; /* next face (never NULL) */
128 GLUface *prev; /* previous face (never NULL) */
129 GLUhalfEdge *anEdge; /* a half edge with this left face */
130 void *data; /* room for client's data */
131
132 /* Internal data (keep hidden) */
133 GLUface *trail; /* "stack" for conversion to strips */
134 GLboolean marked; /* flag for conversion to strips */
135 GLboolean inside; /* this face is in the polygon interior */
136};
137
139 GLUhalfEdge *next; /* doubly-linked list (prev==Sym->next) */
140 GLUhalfEdge *Sym; /* same edge, opposite direction */
141 GLUhalfEdge *Onext; /* next edge CCW around origin */
142 GLUhalfEdge *Lnext; /* next edge CCW around left face */
143 GLUvertex *Org; /* origin vertex (Overtex too long) */
144 GLUface *Lface; /* left face */
145
146 /* Internal data (keep hidden) */
147 ActiveRegion *activeRegion; /* a region with this upper edge (sweep.c) */
148 int winding; /* change in winding number when crossing
149 from the right face to the left face */
150};
151
152/* Allocate and free half-edges in pairs for efficiency.
153 * The *only* place that should use this fact is allocation/free.
154 */
155typedef struct { GLUhalfEdge e, eSym; } EdgePair;
156
157#define Rface Sym->Lface
158#define Dst Sym->Org
159
160#define Oprev Sym->Lnext
161#define Lprev Onext->Sym
162#define Dprev Lnext->Sym
163#define Rprev Sym->Onext
164#define Dnext Rprev->Sym /* 3 pointers */
165#define Rnext Oprev->Sym /* 3 pointers */
166
167
168struct GLUmesh {
169 GLUvertex vHead; /* dummy header for vertex list */
170 GLUface fHead; /* dummy header for face list */
171 GLUhalfEdge eHead; /* dummy header for edge list */
172 GLUhalfEdge eHeadSym; /* and its symmetric counterpart */
173};
174
175/* The mesh operations below have three motivations: completeness,
176 * convenience, and efficiency. The basic mesh operations are MakeEdge,
177 * Splice, and Delete. All the other edge operations can be implemented
178 * in terms of these. The other operations are provided for convenience
179 * and/or efficiency.
180 *
181 * When a face is split or a vertex is added, they are inserted into the
182 * global list *before* the existing vertex or face (ie. e->Org or e->Lface).
183 * This makes it easier to process all vertices or faces in the global lists
184 * without worrying about processing the same data twice. As a convenience,
185 * when a face is split, the "inside" flag is copied from the old face.
186 * Other internal data (v->data, v->activeRegion, f->data, f->marked,
187 * f->trail, e->winding) is set to zero.
188 *
189 * ********************** Basic Edge Operations **************************
190 *
191 * __gl_meshMakeEdge( mesh ) creates one edge, two vertices, and a loop.
192 * The loop (face) consists of the two new half-edges.
193 *
194 * __gl_meshSplice( eOrg, eDst ) is the basic operation for changing the
195 * mesh connectivity and topology. It changes the mesh so that
196 * eOrg->Onext <- OLD( eDst->Onext )
197 * eDst->Onext <- OLD( eOrg->Onext )
198 * where OLD(...) means the value before the meshSplice operation.
199 *
200 * This can have two effects on the vertex structure:
201 * - if eOrg->Org != eDst->Org, the two vertices are merged together
202 * - if eOrg->Org == eDst->Org, the origin is split into two vertices
203 * In both cases, eDst->Org is changed and eOrg->Org is untouched.
204 *
205 * Similarly (and independently) for the face structure,
206 * - if eOrg->Lface == eDst->Lface, one loop is split into two
207 * - if eOrg->Lface != eDst->Lface, two distinct loops are joined into one
208 * In both cases, eDst->Lface is changed and eOrg->Lface is unaffected.
209 *
210 * __gl_meshDelete( eDel ) removes the edge eDel. There are several cases:
211 * if (eDel->Lface != eDel->Rface), we join two loops into one; the loop
212 * eDel->Lface is deleted. Otherwise, we are splitting one loop into two;
213 * the newly created loop will contain eDel->Dst. If the deletion of eDel
214 * would create isolated vertices, those are deleted as well.
215 *
216 * ********************** Other Edge Operations **************************
217 *
218 * __gl_meshAddEdgeVertex( eOrg ) creates a new edge eNew such that
219 * eNew == eOrg->Lnext, and eNew->Dst is a newly created vertex.
220 * eOrg and eNew will have the same left face.
221 *
222 * __gl_meshSplitEdge( eOrg ) splits eOrg into two edges eOrg and eNew,
223 * such that eNew == eOrg->Lnext. The new vertex is eOrg->Dst == eNew->Org.
224 * eOrg and eNew will have the same left face.
225 *
226 * __gl_meshConnect( eOrg, eDst ) creates a new edge from eOrg->Dst
227 * to eDst->Org, and returns the corresponding half-edge eNew.
228 * If eOrg->Lface == eDst->Lface, this splits one loop into two,
229 * and the newly created loop is eNew->Lface. Otherwise, two disjoint
230 * loops are merged into one, and the loop eDst->Lface is destroyed.
231 *
232 * ************************ Other Operations *****************************
233 *
234 * __gl_meshNewMesh() creates a new mesh with no edges, no vertices,
235 * and no loops (what we usually call a "face").
236 *
237 * __gl_meshUnion( mesh1, mesh2 ) forms the union of all structures in
238 * both meshes, and returns the new mesh (the old meshes are destroyed).
239 *
240 * __gl_meshDeleteMesh( mesh ) will free all storage for any valid mesh.
241 *
242 * __gl_meshZapFace( fZap ) destroys a face and removes it from the
243 * global face list. All edges of fZap will have a NULL pointer as their
244 * left face. Any edges which also have a NULL pointer as their right face
245 * are deleted entirely (along with any isolated vertices this produces).
246 * An entire mesh can be deleted by zapping its faces, one at a time,
247 * in any order. Zapped faces cannot be used in further mesh operations!
248 *
249 * __gl_meshCheckMesh( mesh ) checks a mesh for self-consistency.
250 */
251
253int __gl_meshSplice( GLUhalfEdge *eOrg, GLUhalfEdge *eDst );
254int __gl_meshDelete( GLUhalfEdge *eDel );
255
259
261GLUmesh *__gl_meshUnion( GLUmesh *mesh1, GLUmesh *mesh2 );
263void __gl_meshZapFace( GLUface *fZap );
264
265#ifdef NDEBUG
266#define __gl_meshCheckMesh( mesh )
267#else
269#endif
270
271#endif
double GLdouble
Definition: GL_glu.h:279
unsigned char GLboolean
Definition: GL_glu.h:267
GLUhalfEdge * __gl_meshMakeEdge(GLUmesh *mesh)
Definition: mesh.c:270
GLUhalfEdge * __gl_meshSplitEdge(GLUhalfEdge *eOrg)
Definition: mesh.c:470
void __gl_meshCheckMesh(GLUmesh *mesh)
Definition: mesh.c:737
void __gl_meshZapFace(GLUface *fZap)
Definition: mesh.c:550
void __gl_meshDeleteMesh(GLUmesh *mesh)
Definition: mesh.c:706
GLUmesh * __gl_meshNewMesh(void)
Definition: mesh.c:598
GLUhalfEdge * __gl_meshConnect(GLUhalfEdge *eOrg, GLUhalfEdge *eDst)
Definition: mesh.c:503
int __gl_meshDelete(GLUhalfEdge *eDel)
Definition: mesh.c:379
GLUmesh * __gl_meshUnion(GLUmesh *mesh1, GLUmesh *mesh2)
Definition: mesh.c:650
int __gl_meshSplice(GLUhalfEdge *eOrg, GLUhalfEdge *eDst)
Definition: mesh.c:323
GLUhalfEdge * __gl_meshAddEdgeVertex(GLUhalfEdge *eOrg)
Definition: mesh.c:441
Definition: mesh.h:155
GLUhalfEdge e
Definition: mesh.h:155
Definition: mesh.h:126
GLboolean marked
Definition: mesh.h:134
GLUface * trail
Definition: mesh.h:133
GLUhalfEdge * anEdge
Definition: mesh.h:129
GLUface * prev
Definition: mesh.h:128
void * data
Definition: mesh.h:130
GLboolean inside
Definition: mesh.h:135
GLUface * next
Definition: mesh.h:127
GLUhalfEdge * Lnext
Definition: mesh.h:142
GLUvertex * Org
Definition: mesh.h:143
GLUhalfEdge * Onext
Definition: mesh.h:141
ActiveRegion * activeRegion
Definition: mesh.h:147
GLUhalfEdge * Sym
Definition: mesh.h:140
GLUface * Lface
Definition: mesh.h:144
GLUhalfEdge * next
Definition: mesh.h:139
int winding
Definition: mesh.h:148
Definition: mesh.h:168
GLUvertex vHead
Definition: mesh.h:169
GLUhalfEdge eHead
Definition: mesh.h:171
GLUface fHead
Definition: mesh.h:170
GLUhalfEdge eHeadSym
Definition: mesh.h:172
GLUhalfEdge * anEdge
Definition: mesh.h:117
GLdouble t
Definition: mesh.h:122
GLdouble coords[3]
Definition: mesh.h:121
GLdouble s
Definition: mesh.h:122
GLUvertex * next
Definition: mesh.h:115
long pqHandle
Definition: mesh.h:123
void * data
Definition: mesh.h:118
GLUvertex * prev
Definition: mesh.h:116
Definition: triangle.c:632