2 ** License Applicability. Except to the extent portions of this file are
3 ** made subject to an alternative license as permitted in the SGI Free
4 ** Software License B, Version 1.1 (the "License"), the contents of this
5 ** file are subject only to the provisions of the License. You may not use
6 ** this file except in compliance with the License. You may obtain a copy
7 ** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600
8 ** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at:
10 ** http://oss.sgi.com/projects/FreeB
12 ** Note that, as provided in the License, the Software is distributed on an
13 ** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS
14 ** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND
15 ** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A
16 ** PARTICULAR PURPOSE, AND NON-INFRINGEMENT.
18 ** Original Code. The Original Code is: OpenGL Sample Implementation,
19 ** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics,
20 ** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc.
21 ** Copyright in any portions created by third parties is as indicated
22 ** elsewhere herein. All Rights Reserved.
24 ** Additional Notice Provisions: The application programming interfaces
25 ** established by SGI in conjunction with the Original Code are The
26 ** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released
27 ** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version
28 ** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X
29 ** Window System(R) (Version 1.3), released October 19, 1998. This software
30 ** was created using the OpenGL(R) version 1.2.1 Sample Implementation
31 ** published by SGI, but has not been independently verified as being
32 ** compliant with the OpenGL(R) version 1.2.1 Specification.
36 ** Author: Eric Veach, July 1994.
38 ** $Date$ $Revision: 1.1 $
39 ** $Header: /cygdrive/c/RCVS/CVS/ReactOS/reactos/lib/glu32/libtess/mesh.h,v 1.1 2004/02/02 16:39:15 navaraf Exp $
47 typedef struct GLUmesh GLUmesh
;
49 typedef struct GLUvertex GLUvertex
;
50 typedef struct GLUface GLUface
;
51 typedef struct GLUhalfEdge GLUhalfEdge
;
53 typedef struct ActiveRegion ActiveRegion
; /* Internal data */
55 /* The mesh structure is similar in spirit, notation, and operations
56 * to the "quad-edge" structure (see L. Guibas and J. Stolfi, Primitives
57 * for the manipulation of general subdivisions and the computation of
58 * Voronoi diagrams, ACM Transactions on Graphics, 4(2):74-123, April 1985).
59 * For a simplified description, see the course notes for CS348a,
60 * "Mathematical Foundations of Computer Graphics", available at the
61 * Stanford bookstore (and taught during the fall quarter).
62 * The implementation also borrows a tiny subset of the graph-based approach
63 * use in Mantyla's Geometric Work Bench (see M. Mantyla, An Introduction
64 * to Sold Modeling, Computer Science Press, Rockville, Maryland, 1988).
66 * The fundamental data structure is the "half-edge". Two half-edges
67 * go together to make an edge, but they point in opposite directions.
68 * Each half-edge has a pointer to its mate (the "symmetric" half-edge Sym),
69 * its origin vertex (Org), the face on its left side (Lface), and the
70 * adjacent half-edges in the CCW direction around the origin vertex
71 * (Onext) and around the left face (Lnext). There is also a "next"
72 * pointer for the global edge list (see below).
74 * The notation used for mesh navigation:
75 * Sym = the mate of a half-edge (same edge, but opposite direction)
76 * Onext = edge CCW around origin vertex (keep same origin)
77 * Dnext = edge CCW around destination vertex (keep same dest)
78 * Lnext = edge CCW around left face (dest becomes new origin)
79 * Rnext = edge CCW around right face (origin becomes new dest)
81 * "prev" means to substitute CW for CCW in the definitions above.
83 * The mesh keeps global lists of all vertices, faces, and edges,
84 * stored as doubly-linked circular lists with a dummy header node.
85 * The mesh stores pointers to these dummy headers (vHead, fHead, eHead).
87 * The circular edge list is special; since half-edges always occur
88 * in pairs (e and e->Sym), each half-edge stores a pointer in only
89 * one direction. Starting at eHead and following the e->next pointers
90 * will visit each *edge* once (ie. e or e->Sym, but not both).
91 * e->Sym stores a pointer in the opposite direction, thus it is
92 * always true that e->Sym->next->Sym->next == e.
94 * Each vertex has a pointer to next and previous vertices in the
95 * circular list, and a pointer to a half-edge with this vertex as
96 * the origin (NULL if this is the dummy header). There is also a
97 * field "data" for client data.
99 * Each face has a pointer to the next and previous faces in the
100 * circular list, and a pointer to a half-edge with this face as
101 * the left face (NULL if this is the dummy header). There is also
102 * a field "data" for client data.
104 * Note that what we call a "face" is really a loop; faces may consist
105 * of more than one loop (ie. not simply connected), but there is no
106 * record of this in the data structure. The mesh may consist of
107 * several disconnected regions, so it may not be possible to visit
108 * the entire mesh by starting at a half-edge and traversing the edge
111 * The mesh does NOT support isolated vertices; a vertex is deleted along
112 * with its last edge. Similarly when two faces are merged, one of the
113 * faces is deleted (see __gl_meshDelete below). For mesh operations,
114 * all face (loop) and vertex pointers must not be NULL. However, once
115 * mesh manipulation is finished, __gl_MeshZapFace can be used to delete
116 * faces of the mesh, one at a time. All external faces can be "zapped"
117 * before the mesh is returned to the client; then a NULL face indicates
118 * a region which is not part of the output polygon.
122 GLUvertex
*next
; /* next vertex (never NULL) */
123 GLUvertex
*prev
; /* previous vertex (never NULL) */
124 GLUhalfEdge
*anEdge
; /* a half-edge with this origin */
125 void *data
; /* client's data */
127 /* Internal data (keep hidden) */
128 GLdouble coords
[3]; /* vertex location in 3D */
129 GLdouble s
, t
; /* projection onto the sweep plane */
130 long pqHandle
; /* to allow deletion from priority queue */
134 GLUface
*next
; /* next face (never NULL) */
135 GLUface
*prev
; /* previous face (never NULL) */
136 GLUhalfEdge
*anEdge
; /* a half edge with this left face */
137 void *data
; /* room for client's data */
139 /* Internal data (keep hidden) */
140 GLUface
*trail
; /* "stack" for conversion to strips */
141 GLboolean marked
; /* flag for conversion to strips */
142 GLboolean inside
; /* this face is in the polygon interior */
146 GLUhalfEdge
*next
; /* doubly-linked list (prev==Sym->next) */
147 GLUhalfEdge
*Sym
; /* same edge, opposite direction */
148 GLUhalfEdge
*Onext
; /* next edge CCW around origin */
149 GLUhalfEdge
*Lnext
; /* next edge CCW around left face */
150 GLUvertex
*Org
; /* origin vertex (Overtex too long) */
151 GLUface
*Lface
; /* left face */
153 /* Internal data (keep hidden) */
154 ActiveRegion
*activeRegion
; /* a region with this upper edge (sweep.c) */
155 int winding
; /* change in winding number when crossing
156 from the right face to the left face */
159 #define Rface Sym->Lface
162 #define Oprev Sym->Lnext
163 #define Lprev Onext->Sym
164 #define Dprev Lnext->Sym
165 #define Rprev Sym->Onext
166 #define Dnext Rprev->Sym /* 3 pointers */
167 #define Rnext Oprev->Sym /* 3 pointers */
171 GLUvertex vHead
; /* dummy header for vertex list */
172 GLUface fHead
; /* dummy header for face list */
173 GLUhalfEdge eHead
; /* dummy header for edge list */
174 GLUhalfEdge eHeadSym
; /* and its symmetric counterpart */
177 /* The mesh operations below have three motivations: completeness,
178 * convenience, and efficiency. The basic mesh operations are MakeEdge,
179 * Splice, and Delete. All the other edge operations can be implemented
180 * in terms of these. The other operations are provided for convenience
183 * When a face is split or a vertex is added, they are inserted into the
184 * global list *before* the existing vertex or face (ie. e->Org or e->Lface).
185 * This makes it easier to process all vertices or faces in the global lists
186 * without worrying about processing the same data twice. As a convenience,
187 * when a face is split, the "inside" flag is copied from the old face.
188 * Other internal data (v->data, v->activeRegion, f->data, f->marked,
189 * f->trail, e->winding) is set to zero.
191 * ********************** Basic Edge Operations **************************
193 * __gl_meshMakeEdge( mesh ) creates one edge, two vertices, and a loop.
194 * The loop (face) consists of the two new half-edges.
196 * __gl_meshSplice( eOrg, eDst ) is the basic operation for changing the
197 * mesh connectivity and topology. It changes the mesh so that
198 * eOrg->Onext <- OLD( eDst->Onext )
199 * eDst->Onext <- OLD( eOrg->Onext )
200 * where OLD(...) means the value before the meshSplice operation.
202 * This can have two effects on the vertex structure:
203 * - if eOrg->Org != eDst->Org, the two vertices are merged together
204 * - if eOrg->Org == eDst->Org, the origin is split into two vertices
205 * In both cases, eDst->Org is changed and eOrg->Org is untouched.
207 * Similarly (and independently) for the face structure,
208 * - if eOrg->Lface == eDst->Lface, one loop is split into two
209 * - if eOrg->Lface != eDst->Lface, two distinct loops are joined into one
210 * In both cases, eDst->Lface is changed and eOrg->Lface is unaffected.
212 * __gl_meshDelete( eDel ) removes the edge eDel. There are several cases:
213 * if (eDel->Lface != eDel->Rface), we join two loops into one; the loop
214 * eDel->Lface is deleted. Otherwise, we are splitting one loop into two;
215 * the newly created loop will contain eDel->Dst. If the deletion of eDel
216 * would create isolated vertices, those are deleted as well.
218 * ********************** Other Edge Operations **************************
220 * __gl_meshAddEdgeVertex( eOrg ) creates a new edge eNew such that
221 * eNew == eOrg->Lnext, and eNew->Dst is a newly created vertex.
222 * eOrg and eNew will have the same left face.
224 * __gl_meshSplitEdge( eOrg ) splits eOrg into two edges eOrg and eNew,
225 * such that eNew == eOrg->Lnext. The new vertex is eOrg->Dst == eNew->Org.
226 * eOrg and eNew will have the same left face.
228 * __gl_meshConnect( eOrg, eDst ) creates a new edge from eOrg->Dst
229 * to eDst->Org, and returns the corresponding half-edge eNew.
230 * If eOrg->Lface == eDst->Lface, this splits one loop into two,
231 * and the newly created loop is eNew->Lface. Otherwise, two disjoint
232 * loops are merged into one, and the loop eDst->Lface is destroyed.
234 * ************************ Other Operations *****************************
236 * __gl_meshNewMesh() creates a new mesh with no edges, no vertices,
237 * and no loops (what we usually call a "face").
239 * __gl_meshUnion( mesh1, mesh2 ) forms the union of all structures in
240 * both meshes, and returns the new mesh (the old meshes are destroyed).
242 * __gl_meshDeleteMesh( mesh ) will free all storage for any valid mesh.
244 * __gl_meshZapFace( fZap ) destroys a face and removes it from the
245 * global face list. All edges of fZap will have a NULL pointer as their
246 * left face. Any edges which also have a NULL pointer as their right face
247 * are deleted entirely (along with any isolated vertices this produces).
248 * An entire mesh can be deleted by zapping its faces, one at a time,
249 * in any order. Zapped faces cannot be used in further mesh operations!
251 * __gl_meshCheckMesh( mesh ) checks a mesh for self-consistency.
254 GLUhalfEdge
*__gl_meshMakeEdge( GLUmesh
*mesh
);
255 int __gl_meshSplice( GLUhalfEdge
*eOrg
, GLUhalfEdge
*eDst
);
256 int __gl_meshDelete( GLUhalfEdge
*eDel
);
258 GLUhalfEdge
*__gl_meshAddEdgeVertex( GLUhalfEdge
*eOrg
);
259 GLUhalfEdge
*__gl_meshSplitEdge( GLUhalfEdge
*eOrg
);
260 GLUhalfEdge
*__gl_meshConnect( GLUhalfEdge
*eOrg
, GLUhalfEdge
*eDst
);
262 GLUmesh
*__gl_meshNewMesh( void );
263 GLUmesh
*__gl_meshUnion( GLUmesh
*mesh1
, GLUmesh
*mesh2
);
264 void __gl_meshDeleteMesh( GLUmesh
*mesh
);
265 void __gl_meshZapFace( GLUface
*fZap
);
268 #define __gl_meshCheckMesh( mesh )
270 void __gl_meshCheckMesh( GLUmesh
*mesh
);