FreeWRL / FreeX3D
4.3.0
mesh.h
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 "libtess2.h"
39
40
typedef
struct
GLUmesh
GLUmesh
;
41
42
typedef
struct
GLUvertex
GLUvertex
;
43
typedef
struct
GLUface
GLUface
;
44
typedef
struct
GLUhalfEdge
GLUhalfEdge
;
45
46
typedef
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
114
struct
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
126
struct
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
138
struct
GLUhalfEdge
{
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
#define Rface Sym->Lface
153
#define Dst Sym->Org
154
155
#define Oprev Sym->Lnext
156
#define Lprev Onext->Sym
157
#define Dprev Lnext->Sym
158
#define Rprev Sym->Onext
159
#define Dnext Rprev->Sym
/* 3 pointers */
160
#define Rnext Oprev->Sym
/* 3 pointers */
161
162
163
struct
GLUmesh
{
164
GLUvertex
vHead;
/* dummy header for vertex list */
165
GLUface
fHead;
/* dummy header for face list */
166
GLUhalfEdge
eHead;
/* dummy header for edge list */
167
GLUhalfEdge
eHeadSym;
/* and its symmetric counterpart */
168
};
169
170
/* The mesh operations below have three motivations: completeness,
171
* convenience, and efficiency. The basic mesh operations are MakeEdge,
172
* Splice, and Delete. All the other edge operations can be implemented
173
* in terms of these. The other operations are provided for convenience
174
* and/or efficiency.
175
*
176
* When a face is split or a vertex is added, they are inserted into the
177
* global list *before* the existing vertex or face (ie. e->Org or e->Lface).
178
* This makes it easier to process all vertices or faces in the global lists
179
* without worrying about processing the same data twice. As a convenience,
180
* when a face is split, the "inside" flag is copied from the old face.
181
* Other internal data (v->data, v->activeRegion, f->data, f->marked,
182
* f->trail, e->winding) is set to zero.
183
*
184
* ********************** Basic Edge Operations **************************
185
*
186
* __gl_meshMakeEdge( mesh ) creates one edge, two vertices, and a loop.
187
* The loop (face) consists of the two new half-edges.
188
*
189
* __gl_meshSplice( eOrg, eDst ) is the basic operation for changing the
190
* mesh connectivity and topology. It changes the mesh so that
191
* eOrg->Onext <- OLD( eDst->Onext )
192
* eDst->Onext <- OLD( eOrg->Onext )
193
* where OLD(...) means the value before the meshSplice operation.
194
*
195
* This can have two effects on the vertex structure:
196
* - if eOrg->Org != eDst->Org, the two vertices are merged together
197
* - if eOrg->Org == eDst->Org, the origin is split into two vertices
198
* In both cases, eDst->Org is changed and eOrg->Org is untouched.
199
*
200
* Similarly (and independently) for the face structure,
201
* - if eOrg->Lface == eDst->Lface, one loop is split into two
202
* - if eOrg->Lface != eDst->Lface, two distinct loops are joined into one
203
* In both cases, eDst->Lface is changed and eOrg->Lface is unaffected.
204
*
205
* __gl_meshDelete( eDel ) removes the edge eDel. There are several cases:
206
* if (eDel->Lface != eDel->Rface), we join two loops into one; the loop
207
* eDel->Lface is deleted. Otherwise, we are splitting one loop into two;
208
* the newly created loop will contain eDel->Dst. If the deletion of eDel
209
* would create isolated vertices, those are deleted as well.
210
*
211
* ********************** Other Edge Operations **************************
212
*
213
* __gl_meshAddEdgeVertex( eOrg ) creates a new edge eNew such that
214
* eNew == eOrg->Lnext, and eNew->Dst is a newly created vertex.
215
* eOrg and eNew will have the same left face.
216
*
217
* __gl_meshSplitEdge( eOrg ) splits eOrg into two edges eOrg and eNew,
218
* such that eNew == eOrg->Lnext. The new vertex is eOrg->Dst == eNew->Org.
219
* eOrg and eNew will have the same left face.
220
*
221
* __gl_meshConnect( eOrg, eDst ) creates a new edge from eOrg->Dst
222
* to eDst->Org, and returns the corresponding half-edge eNew.
223
* If eOrg->Lface == eDst->Lface, this splits one loop into two,
224
* and the newly created loop is eNew->Lface. Otherwise, two disjoint
225
* loops are merged into one, and the loop eDst->Lface is destroyed.
226
*
227
* ************************ Other Operations *****************************
228
*
229
* __gl_meshNewMesh() creates a new mesh with no edges, no vertices,
230
* and no loops (what we usually call a "face").
231
*
232
* __gl_meshUnion( mesh1, mesh2 ) forms the union of all structures in
233
* both meshes, and returns the new mesh (the old meshes are destroyed).
234
*
235
* __gl_meshDeleteMesh( mesh ) will free all storage for any valid mesh.
236
*
237
* __gl_meshZapFace( fZap ) destroys a face and removes it from the
238
* global face list. All edges of fZap will have a NULL pointer as their
239
* left face. Any edges which also have a NULL pointer as their right face
240
* are deleted entirely (along with any isolated vertices this produces).
241
* An entire mesh can be deleted by zapping its faces, one at a time,
242
* in any order. Zapped faces cannot be used in further mesh operations!
243
*
244
* __gl_meshCheckMesh( mesh ) checks a mesh for self-consistency.
245
*/
246
247
GLUhalfEdge
*__gl_meshMakeEdge(
GLUmesh
*mesh );
248
int
__gl_meshSplice(
GLUhalfEdge
*eOrg,
GLUhalfEdge
*eDst );
249
int
__gl_meshDelete(
GLUhalfEdge
*eDel );
250
251
GLUhalfEdge
*__gl_meshAddEdgeVertex(
GLUhalfEdge
*eOrg );
252
GLUhalfEdge
*__gl_meshSplitEdge(
GLUhalfEdge
*eOrg );
253
GLUhalfEdge
*__gl_meshConnect(
GLUhalfEdge
*eOrg,
GLUhalfEdge
*eDst );
254
255
GLUmesh
*__gl_meshNewMesh(
void
);
256
GLUmesh
*__gl_meshUnion(
GLUmesh
*mesh1,
GLUmesh
*mesh2 );
257
void
__gl_meshDeleteMesh(
GLUmesh
*mesh );
258
void
__gl_meshZapFace(
GLUface
*fZap );
259
260
#ifdef NDEBUG
261
#define __gl_meshCheckMesh( mesh )
262
#else
263
void
__gl_meshCheckMesh(
GLUmesh
*mesh );
264
#endif
265
266
#endif
ActiveRegion
Definition
sweep.h:59
GLUface
Definition
mesh.h:126
GLUhalfEdge
Definition
mesh.h:138
GLUmesh
Definition
mesh.h:163
GLUvertex
Definition
mesh.h:114
src
libtess
mesh.h
Generated by
1.13.1