diff options
Diffstat (limited to 'src/libtess2/mesh.h')
| -rwxr-xr-x | src/libtess2/mesh.h | 267 |
1 files changed, 267 insertions, 0 deletions
diff --git a/src/libtess2/mesh.h b/src/libtess2/mesh.h new file mode 100755 index 0000000000..d6142716a9 --- /dev/null +++ b/src/libtess2/mesh.h @@ -0,0 +1,267 @@ +/* +** SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008) +** Copyright (C) [dates of first publication] 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 <libtess2/tesselator.h> + +typedef struct TESSmesh TESSmesh; +typedef struct TESSvertex TESSvertex; +typedef struct TESSface TESSface; +typedef struct TESShalfEdge TESShalfEdge; +typedef struct ActiveRegion ActiveRegion; + +/* 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 tessMeshDelete below). For mesh operations, +* all face (loop) and vertex pointers must not be NULL. However, once +* mesh manipulation is finished, TESSmeshZapFace 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 TESSvertex { + TESSvertex *next; /* next vertex (never NULL) */ + TESSvertex *prev; /* previous vertex (never NULL) */ + TESShalfEdge *anEdge; /* a half-edge with this origin */ + + /* Internal data (keep hidden) */ + TESSreal coords[3]; /* vertex location in 3D */ + TESSreal s, t; /* projection onto the sweep plane */ + int pqHandle; /* to allow deletion from priority queue */ + TESSindex n; /* to allow identify unique vertices */ + TESSindex idx; /* to allow map result to original verts */ +}; + +struct TESSface { + TESSface *next; /* next face (never NULL) */ + TESSface *prev; /* previous face (never NULL) */ + TESShalfEdge *anEdge; /* a half edge with this left face */ + + /* Internal data (keep hidden) */ + TESSface *trail; /* "stack" for conversion to strips */ + TESSindex n; /* to allow identiy unique faces */ + char marked; /* flag for conversion to strips */ + char inside; /* this face is in the polygon interior */ +}; + +struct TESShalfEdge { + TESShalfEdge *next; /* doubly-linked list (prev==Sym->next) */ + TESShalfEdge *Sym; /* same edge, opposite direction */ + TESShalfEdge *Onext; /* next edge CCW around origin */ + TESShalfEdge *Lnext; /* next edge CCW around left face */ + TESSvertex *Org; /* origin vertex (Overtex too long) */ + TESSface *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 TESSmesh { + TESSvertex vHead; /* dummy header for vertex list */ + TESSface fHead; /* dummy header for face list */ + TESShalfEdge eHead; /* dummy header for edge list */ + TESShalfEdge eHeadSym; /* and its symmetric counterpart */ + + struct BucketAlloc* edgeBucket; + struct BucketAlloc* vertexBucket; + struct BucketAlloc* faceBucket; +}; + +/* 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 ************************** +* +* tessMeshMakeEdge( mesh ) creates one edge, two vertices, and a loop. +* The loop (face) consists of the two new half-edges. +* +* tessMeshSplice( 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. +* +* tessMeshDelete( 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 ************************** +* +* tessMeshAddEdgeVertex( 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. +* +* tessMeshSplitEdge( 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. +* +* tessMeshConnect( 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 ***************************** +* +* tessMeshNewMesh() creates a new mesh with no edges, no vertices, +* and no loops (what we usually call a "face"). +* +* tessMeshUnion( mesh1, mesh2 ) forms the union of all structures in +* both meshes, and returns the new mesh (the old meshes are destroyed). +* +* tessMeshDeleteMesh( mesh ) will free all storage for any valid mesh. +* +* tessMeshZapFace( 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! +* +* tessMeshCheckMesh( mesh ) checks a mesh for self-consistency. +*/ + +TESShalfEdge *tessMeshMakeEdge( TESSmesh *mesh ); +int tessMeshSplice( TESSmesh *mesh, TESShalfEdge *eOrg, TESShalfEdge *eDst ); +int tessMeshDelete( TESSmesh *mesh, TESShalfEdge *eDel ); + +TESShalfEdge *tessMeshAddEdgeVertex( TESSmesh *mesh, TESShalfEdge *eOrg ); +TESShalfEdge *tessMeshSplitEdge( TESSmesh *mesh, TESShalfEdge *eOrg ); +TESShalfEdge *tessMeshConnect( TESSmesh *mesh, TESShalfEdge *eOrg, TESShalfEdge *eDst ); + +TESSmesh *tessMeshNewMesh( TESSalloc* alloc ); +TESSmesh *tessMeshUnion( TESSalloc* alloc, TESSmesh *mesh1, TESSmesh *mesh2 ); +int tessMeshMergeConvexFaces( TESSmesh *mesh, int maxVertsPerFace ); +void tessMeshDeleteMesh( TESSalloc* alloc, TESSmesh *mesh ); +void tessMeshZapFace( TESSmesh *mesh, TESSface *fZap ); + +#ifdef NDEBUG +#define tessMeshCheckMesh( mesh ) +#else +void tessMeshCheckMesh( TESSmesh *mesh ); +#endif + +#endif |