diff options
Diffstat (limited to 'cogl/cogl-path/tesselator/mesh.h')
| -rw-r--r-- | cogl/cogl-path/tesselator/mesh.h | 266 |
1 files changed, 266 insertions, 0 deletions
diff --git a/cogl/cogl-path/tesselator/mesh.h b/cogl/cogl-path/tesselator/mesh.h new file mode 100644 index 000000000..690c5f2f6 --- /dev/null +++ b/cogl/cogl-path/tesselator/mesh.h @@ -0,0 +1,266 @@ +/* + * 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 |