summaryrefslogtreecommitdiff
path: root/src/libtess2/mesh.h
diff options
context:
space:
mode:
authorKonstantin Käfer <mail@kkaefer.com>2014-02-17 12:45:57 +0100
committerKonstantin Käfer <mail@kkaefer.com>2014-02-17 12:45:57 +0100
commitb087c35c98ba31cd0e27d15a6c61d18664bc981a (patch)
tree0466a2ad436efcd6c641f0cbd64472a630129067 /src/libtess2/mesh.h
parentd1910f0e040e97b36f0f8b12035a63f628279595 (diff)
downloadqtlocation-mapboxgl-b087c35c98ba31cd0e27d15a6c61d18664bc981a.tar.gz
add tessellation library
Diffstat (limited to 'src/libtess2/mesh.h')
-rwxr-xr-xsrc/libtess2/mesh.h267
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