+++ /dev/null
-/*
- * SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008)
- * Copyright (C) 1991-2000 Silicon Graphics, Inc. All Rights Reserved.
- *
- * Permission is hereby granted, free of charge, to any person obtaining a
- * copy of this software and associated documentation files (the "Software"),
- * to deal in the Software without restriction, including without limitation
- * the rights to use, copy, modify, merge, publish, distribute, sublicense,
- * and/or sell copies of the Software, and to permit persons to whom the
- * Software is furnished to do so, subject to the following conditions:
- *
- * The above copyright notice including the dates of first publication and
- * either this permission notice or a reference to
- * http://oss.sgi.com/projects/FreeB/
- * shall be included in all copies or substantial portions of the Software.
- *
- * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
- * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
- * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
- * SILICON GRAPHICS, INC. BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
- * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
- * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
- * SOFTWARE.
- *
- * Except as contained in this notice, the name of Silicon Graphics, Inc.
- * shall not be used in advertising or otherwise to promote the sale, use or
- * other dealings in this Software without prior written authorization from
- * Silicon Graphics, Inc.
- */
-/*
-** Author: Eric Veach, July 1994.
-**
-*/
-
-#ifndef __mesh_h_
-#define __mesh_h_
-
-#include <GL/glu.h>
-
-typedef struct GLUmesh GLUmesh;
-
-typedef struct GLUvertex GLUvertex;
-typedef struct GLUface GLUface;
-typedef struct GLUhalfEdge GLUhalfEdge;
-
-typedef struct ActiveRegion ActiveRegion; /* Internal data */
-
-/* The mesh structure is similar in spirit, notation, and operations
- * to the "quad-edge" structure (see L. Guibas and J. Stolfi, Primitives
- * for the manipulation of general subdivisions and the computation of
- * Voronoi diagrams, ACM Transactions on Graphics, 4(2):74-123, April 1985).
- * For a simplified description, see the course notes for CS348a,
- * "Mathematical Foundations of Computer Graphics", available at the
- * Stanford bookstore (and taught during the fall quarter).
- * The implementation also borrows a tiny subset of the graph-based approach
- * use in Mantyla's Geometric Work Bench (see M. Mantyla, An Introduction
- * to Sold Modeling, Computer Science Press, Rockville, Maryland, 1988).
- *
- * The fundamental data structure is the "half-edge". Two half-edges
- * go together to make an edge, but they point in opposite directions.
- * Each half-edge has a pointer to its mate (the "symmetric" half-edge Sym),
- * its origin vertex (Org), the face on its left side (Lface), and the
- * adjacent half-edges in the CCW direction around the origin vertex
- * (Onext) and around the left face (Lnext). There is also a "next"
- * pointer for the global edge list (see below).
- *
- * The notation used for mesh navigation:
- * Sym = the mate of a half-edge (same edge, but opposite direction)
- * Onext = edge CCW around origin vertex (keep same origin)
- * Dnext = edge CCW around destination vertex (keep same dest)
- * Lnext = edge CCW around left face (dest becomes new origin)
- * Rnext = edge CCW around right face (origin becomes new dest)
- *
- * "prev" means to substitute CW for CCW in the definitions above.
- *
- * The mesh keeps global lists of all vertices, faces, and edges,
- * stored as doubly-linked circular lists with a dummy header node.
- * The mesh stores pointers to these dummy headers (vHead, fHead, eHead).
- *
- * The circular edge list is special; since half-edges always occur
- * in pairs (e and e->Sym), each half-edge stores a pointer in only
- * one direction. Starting at eHead and following the e->next pointers
- * will visit each *edge* once (ie. e or e->Sym, but not both).
- * e->Sym stores a pointer in the opposite direction, thus it is
- * always true that e->Sym->next->Sym->next == e.
- *
- * Each vertex has a pointer to next and previous vertices in the
- * circular list, and a pointer to a half-edge with this vertex as
- * the origin (NULL if this is the dummy header). There is also a
- * field "data" for client data.
- *
- * Each face has a pointer to the next and previous faces in the
- * circular list, and a pointer to a half-edge with this face as
- * the left face (NULL if this is the dummy header). There is also
- * a field "data" for client data.
- *
- * Note that what we call a "face" is really a loop; faces may consist
- * of more than one loop (ie. not simply connected), but there is no
- * record of this in the data structure. The mesh may consist of
- * several disconnected regions, so it may not be possible to visit
- * the entire mesh by starting at a half-edge and traversing the edge
- * structure.
- *
- * The mesh does NOT support isolated vertices; a vertex is deleted along
- * with its last edge. Similarly when two faces are merged, one of the
- * faces is deleted (see __gl_meshDelete below). For mesh operations,
- * all face (loop) and vertex pointers must not be NULL. However, once
- * mesh manipulation is finished, __gl_MeshZapFace can be used to delete
- * faces of the mesh, one at a time. All external faces can be "zapped"
- * before the mesh is returned to the client; then a NULL face indicates
- * a region which is not part of the output polygon.
- */
-
-struct GLUvertex {
- GLUvertex *next; /* next vertex (never NULL) */
- GLUvertex *prev; /* previous vertex (never NULL) */
- GLUhalfEdge *anEdge; /* a half-edge with this origin */
- void *data; /* client's data */
-
- /* Internal data (keep hidden) */
- GLdouble coords[3]; /* vertex location in 3D */
- GLdouble s, t; /* projection onto the sweep plane */
- long pqHandle; /* to allow deletion from priority queue */
-};
-
-struct GLUface {
- GLUface *next; /* next face (never NULL) */
- GLUface *prev; /* previous face (never NULL) */
- GLUhalfEdge *anEdge; /* a half edge with this left face */
- void *data; /* room for client's data */
-
- /* Internal data (keep hidden) */
- GLUface *trail; /* "stack" for conversion to strips */
- GLboolean marked; /* flag for conversion to strips */
- GLboolean inside; /* this face is in the polygon interior */
-};
-
-struct GLUhalfEdge {
- GLUhalfEdge *next; /* doubly-linked list (prev==Sym->next) */
- GLUhalfEdge *Sym; /* same edge, opposite direction */
- GLUhalfEdge *Onext; /* next edge CCW around origin */
- GLUhalfEdge *Lnext; /* next edge CCW around left face */
- GLUvertex *Org; /* origin vertex (Overtex too long) */
- GLUface *Lface; /* left face */
-
- /* Internal data (keep hidden) */
- ActiveRegion *activeRegion; /* a region with this upper edge (sweep.c) */
- int winding; /* change in winding number when crossing
- from the right face to the left face */
-};
-
-#define Rface Sym->Lface
-#define Dst Sym->Org
-
-#define Oprev Sym->Lnext
-#define Lprev Onext->Sym
-#define Dprev Lnext->Sym
-#define Rprev Sym->Onext
-#define Dnext Rprev->Sym /* 3 pointers */
-#define Rnext Oprev->Sym /* 3 pointers */
-
-
-struct GLUmesh {
- GLUvertex vHead; /* dummy header for vertex list */
- GLUface fHead; /* dummy header for face list */
- GLUhalfEdge eHead; /* dummy header for edge list */
- GLUhalfEdge eHeadSym; /* and its symmetric counterpart */
-};
-
-/* The mesh operations below have three motivations: completeness,
- * convenience, and efficiency. The basic mesh operations are MakeEdge,
- * Splice, and Delete. All the other edge operations can be implemented
- * in terms of these. The other operations are provided for convenience
- * and/or efficiency.
- *
- * When a face is split or a vertex is added, they are inserted into the
- * global list *before* the existing vertex or face (ie. e->Org or e->Lface).
- * This makes it easier to process all vertices or faces in the global lists
- * without worrying about processing the same data twice. As a convenience,
- * when a face is split, the "inside" flag is copied from the old face.
- * Other internal data (v->data, v->activeRegion, f->data, f->marked,
- * f->trail, e->winding) is set to zero.
- *
- * ********************** Basic Edge Operations **************************
- *
- * __gl_meshMakeEdge( mesh ) creates one edge, two vertices, and a loop.
- * The loop (face) consists of the two new half-edges.
- *
- * __gl_meshSplice( eOrg, eDst ) is the basic operation for changing the
- * mesh connectivity and topology. It changes the mesh so that
- * eOrg->Onext <- OLD( eDst->Onext )
- * eDst->Onext <- OLD( eOrg->Onext )
- * where OLD(...) means the value before the meshSplice operation.
- *
- * This can have two effects on the vertex structure:
- * - if eOrg->Org != eDst->Org, the two vertices are merged together
- * - if eOrg->Org == eDst->Org, the origin is split into two vertices
- * In both cases, eDst->Org is changed and eOrg->Org is untouched.
- *
- * Similarly (and independently) for the face structure,
- * - if eOrg->Lface == eDst->Lface, one loop is split into two
- * - if eOrg->Lface != eDst->Lface, two distinct loops are joined into one
- * In both cases, eDst->Lface is changed and eOrg->Lface is unaffected.
- *
- * __gl_meshDelete( eDel ) removes the edge eDel. There are several cases:
- * if (eDel->Lface != eDel->Rface), we join two loops into one; the loop
- * eDel->Lface is deleted. Otherwise, we are splitting one loop into two;
- * the newly created loop will contain eDel->Dst. If the deletion of eDel
- * would create isolated vertices, those are deleted as well.
- *
- * ********************** Other Edge Operations **************************
- *
- * __gl_meshAddEdgeVertex( eOrg ) creates a new edge eNew such that
- * eNew == eOrg->Lnext, and eNew->Dst is a newly created vertex.
- * eOrg and eNew will have the same left face.
- *
- * __gl_meshSplitEdge( eOrg ) splits eOrg into two edges eOrg and eNew,
- * such that eNew == eOrg->Lnext. The new vertex is eOrg->Dst == eNew->Org.
- * eOrg and eNew will have the same left face.
- *
- * __gl_meshConnect( eOrg, eDst ) creates a new edge from eOrg->Dst
- * to eDst->Org, and returns the corresponding half-edge eNew.
- * If eOrg->Lface == eDst->Lface, this splits one loop into two,
- * and the newly created loop is eNew->Lface. Otherwise, two disjoint
- * loops are merged into one, and the loop eDst->Lface is destroyed.
- *
- * ************************ Other Operations *****************************
- *
- * __gl_meshNewMesh() creates a new mesh with no edges, no vertices,
- * and no loops (what we usually call a "face").
- *
- * __gl_meshUnion( mesh1, mesh2 ) forms the union of all structures in
- * both meshes, and returns the new mesh (the old meshes are destroyed).
- *
- * __gl_meshDeleteMesh( mesh ) will free all storage for any valid mesh.
- *
- * __gl_meshZapFace( fZap ) destroys a face and removes it from the
- * global face list. All edges of fZap will have a NULL pointer as their
- * left face. Any edges which also have a NULL pointer as their right face
- * are deleted entirely (along with any isolated vertices this produces).
- * An entire mesh can be deleted by zapping its faces, one at a time,
- * in any order. Zapped faces cannot be used in further mesh operations!
- *
- * __gl_meshCheckMesh( mesh ) checks a mesh for self-consistency.
- */
-
-GLUhalfEdge *__gl_meshMakeEdge( GLUmesh *mesh );
-int __gl_meshSplice( GLUhalfEdge *eOrg, GLUhalfEdge *eDst );
-int __gl_meshDelete( GLUhalfEdge *eDel );
-
-GLUhalfEdge *__gl_meshAddEdgeVertex( GLUhalfEdge *eOrg );
-GLUhalfEdge *__gl_meshSplitEdge( GLUhalfEdge *eOrg );
-GLUhalfEdge *__gl_meshConnect( GLUhalfEdge *eOrg, GLUhalfEdge *eDst );
-
-GLUmesh *__gl_meshNewMesh( void );
-GLUmesh *__gl_meshUnion( GLUmesh *mesh1, GLUmesh *mesh2 );
-void __gl_meshDeleteMesh( GLUmesh *mesh );
-void __gl_meshZapFace( GLUface *fZap );
-
-#ifdef NDEBUG
-#define __gl_meshCheckMesh( mesh )
-#else
-void __gl_meshCheckMesh( GLUmesh *mesh );
-#endif
-
-#endif
projects / reactos.git / blobdiff