]> git.jsancho.org Git - lugaru.git/blob - Dependencies/GLU/mesh.h
Introduce pause_sound
[lugaru.git] / Dependencies / GLU / 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 <GL/glu.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