Cinder

  • Main Page
  • Related Pages
  • Namespaces
  • Classes
  • Files
  • Examples
  • File List
  • File Members

src/libtess2/mesh.h

Go to the documentation of this file.
00001 /*
00002 ** SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008) 
00003 ** Copyright (C) [dates of first publication] Silicon Graphics, Inc.
00004 ** All Rights Reserved.
00005 **
00006 ** Permission is hereby granted, free of charge, to any person obtaining a copy
00007 ** of this software and associated documentation files (the "Software"), to deal
00008 ** in the Software without restriction, including without limitation the rights
00009 ** to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
00010 ** of the Software, and to permit persons to whom the Software is furnished to do so,
00011 ** subject to the following conditions:
00012 ** 
00013 ** The above copyright notice including the dates of first publication and either this
00014 ** permission notice or a reference to http://oss.sgi.com/projects/FreeB/ shall be
00015 ** included in all copies or substantial portions of the Software. 
00016 **
00017 ** THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
00018 ** INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
00019 ** PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL SILICON GRAPHICS, INC.
00020 ** BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
00021 ** TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE
00022 ** OR OTHER DEALINGS IN THE SOFTWARE.
00023 ** 
00024 ** Except as contained in this notice, the name of Silicon Graphics, Inc. shall not
00025 ** be used in advertising or otherwise to promote the sale, use or other dealings in
00026 ** this Software without prior written authorization from Silicon Graphics, Inc.
00027 */
00028 /*
00029 ** Author: Eric Veach, July 1994.
00030 */
00031 
00032 #ifndef MESH_H
00033 #define MESH_H
00034 
00035 #include "tesselator.h"
00036 
00037 typedef struct TESSmesh TESSmesh; 
00038 typedef struct TESSvertex TESSvertex;
00039 typedef struct TESSface TESSface;
00040 typedef struct TESShalfEdge TESShalfEdge;
00041 typedef struct ActiveRegion ActiveRegion;
00042 
00043 /* The mesh structure is similar in spirit, notation, and operations
00044 * to the "quad-edge" structure (see L. Guibas and J. Stolfi, Primitives
00045 * for the manipulation of general subdivisions and the computation of
00046 * Voronoi diagrams, ACM Transactions on Graphics, 4(2):74-123, April 1985).
00047 * For a simplified description, see the course notes for CS348a,
00048 * "Mathematical Foundations of Computer Graphics", available at the
00049 * Stanford bookstore (and taught during the fall quarter).
00050 * The implementation also borrows a tiny subset of the graph-based approach
00051 * use in Mantyla's Geometric Work Bench (see M. Mantyla, An Introduction
00052 * to Sold Modeling, Computer Science Press, Rockville, Maryland, 1988).
00053 *
00054 * The fundamental data structure is the "half-edge".  Two half-edges
00055 * go together to make an edge, but they point in opposite directions.
00056 * Each half-edge has a pointer to its mate (the "symmetric" half-edge Sym),
00057 * its origin vertex (Org), the face on its left side (Lface), and the
00058 * adjacent half-edges in the CCW direction around the origin vertex
00059 * (Onext) and around the left face (Lnext).  There is also a "next"
00060 * pointer for the global edge list (see below).
00061 *
00062 * The notation used for mesh navigation:
00063 *  Sym   = the mate of a half-edge (same edge, but opposite direction)
00064 *  Onext = edge CCW around origin vertex (keep same origin)
00065 *  Dnext = edge CCW around destination vertex (keep same dest)
00066 *  Lnext = edge CCW around left face (dest becomes new origin)
00067 *  Rnext = edge CCW around right face (origin becomes new dest)
00068 *
00069 * "prev" means to substitute CW for CCW in the definitions above.
00070 *
00071 * The mesh keeps global lists of all vertices, faces, and edges,
00072 * stored as doubly-linked circular lists with a dummy header node.
00073 * The mesh stores pointers to these dummy headers (vHead, fHead, eHead).
00074 *
00075 * The circular edge list is special; since half-edges always occur
00076 * in pairs (e and e->Sym), each half-edge stores a pointer in only
00077 * one direction.  Starting at eHead and following the e->next pointers
00078 * will visit each *edge* once (ie. e or e->Sym, but not both).
00079 * e->Sym stores a pointer in the opposite direction, thus it is
00080 * always true that e->Sym->next->Sym->next == e.
00081 *
00082 * Each vertex has a pointer to next and previous vertices in the
00083 * circular list, and a pointer to a half-edge with this vertex as
00084 * the origin (NULL if this is the dummy header).  There is also a
00085 * field "data" for client data.
00086 *
00087 * Each face has a pointer to the next and previous faces in the
00088 * circular list, and a pointer to a half-edge with this face as
00089 * the left face (NULL if this is the dummy header).  There is also
00090 * a field "data" for client data.
00091 *
00092 * Note that what we call a "face" is really a loop; faces may consist
00093 * of more than one loop (ie. not simply connected), but there is no
00094 * record of this in the data structure.  The mesh may consist of
00095 * several disconnected regions, so it may not be possible to visit
00096 * the entire mesh by starting at a half-edge and traversing the edge
00097 * structure.
00098 *
00099 * The mesh does NOT support isolated vertices; a vertex is deleted along
00100 * with its last edge.  Similarly when two faces are merged, one of the
00101 * faces is deleted (see tessMeshDelete below).  For mesh operations,
00102 * all face (loop) and vertex pointers must not be NULL.  However, once
00103 * mesh manipulation is finished, TESSmeshZapFace can be used to delete
00104 * faces of the mesh, one at a time.  All external faces can be "zapped"
00105 * before the mesh is returned to the client; then a NULL face indicates
00106 * a region which is not part of the output polygon.
00107 */
00108 
00109 struct TESSvertex {
00110     TESSvertex *next;      /* next vertex (never NULL) */
00111     TESSvertex *prev;      /* previous vertex (never NULL) */
00112     TESShalfEdge *anEdge;    /* a half-edge with this origin */
00113 
00114     /* Internal data (keep hidden) */
00115     TESSreal coords[3];  /* vertex location in 3D */
00116     TESSreal s, t;       /* projection onto the sweep plane */
00117     int pqHandle;   /* to allow deletion from priority queue */
00118     TESSindex n;            /* to allow identiy unique vertices */
00119 };
00120 
00121 struct TESSface {
00122     TESSface *next;      /* next face (never NULL) */
00123     TESSface *prev;      /* previous face (never NULL) */
00124     TESShalfEdge *anEdge;    /* a half edge with this left face */
00125 
00126     /* Internal data (keep hidden) */
00127     TESSface *trail;     /* "stack" for conversion to strips */
00128     TESSindex n;        /* to allow identiy unique faces */
00129     char marked;     /* flag for conversion to strips */
00130     char inside;     /* this face is in the polygon interior */
00131 };
00132 
00133 struct TESShalfEdge {
00134     TESShalfEdge *next;      /* doubly-linked list (prev==Sym->next) */
00135     TESShalfEdge *Sym;       /* same edge, opposite direction */
00136     TESShalfEdge *Onext;     /* next edge CCW around origin */
00137     TESShalfEdge *Lnext;     /* next edge CCW around left face */
00138     TESSvertex *Org;       /* origin vertex (Overtex too long) */
00139     TESSface *Lface;     /* left face */
00140 
00141     /* Internal data (keep hidden) */
00142     ActiveRegion *activeRegion;  /* a region with this upper edge (sweep.c) */
00143     int winding;    /* change in winding number when crossing
00144                           from the right face to the left face */
00145 };
00146 
00147 #define Rface   Sym->Lface
00148 #define Dst Sym->Org
00149 
00150 #define Oprev   Sym->Lnext
00151 #define Lprev   Onext->Sym
00152 #define Dprev   Lnext->Sym
00153 #define Rprev   Sym->Onext
00154 #define Dnext   Rprev->Sym  /* 3 pointers */
00155 #define Rnext   Oprev->Sym  /* 3 pointers */
00156 
00157 
00158 struct TESSmesh {
00159     TESSvertex vHead;      /* dummy header for vertex list */
00160     TESSface fHead;      /* dummy header for face list */
00161     TESShalfEdge eHead;      /* dummy header for edge list */
00162     TESShalfEdge eHeadSym;   /* and its symmetric counterpart */
00163 
00164     struct BucketAlloc* edgeBucket;
00165     struct BucketAlloc* vertexBucket;
00166     struct BucketAlloc* faceBucket;
00167 };
00168 
00169 /* The mesh operations below have three motivations: completeness,
00170 * convenience, and efficiency.  The basic mesh operations are MakeEdge,
00171 * Splice, and Delete.  All the other edge operations can be implemented
00172 * in terms of these.  The other operations are provided for convenience
00173 * and/or efficiency.
00174 *
00175 * When a face is split or a vertex is added, they are inserted into the
00176 * global list *before* the existing vertex or face (ie. e->Org or e->Lface).
00177 * This makes it easier to process all vertices or faces in the global lists
00178 * without worrying about processing the same data twice.  As a convenience,
00179 * when a face is split, the "inside" flag is copied from the old face.
00180 * Other internal data (v->data, v->activeRegion, f->data, f->marked,
00181 * f->trail, e->winding) is set to zero.
00182 *
00183 * ********************** Basic Edge Operations **************************
00184 *
00185 * tessMeshMakeEdge( mesh ) creates one edge, two vertices, and a loop.
00186 * The loop (face) consists of the two new half-edges.
00187 *
00188 * tessMeshSplice( eOrg, eDst ) is the basic operation for changing the
00189 * mesh connectivity and topology.  It changes the mesh so that
00190 *  eOrg->Onext <- OLD( eDst->Onext )
00191 *  eDst->Onext <- OLD( eOrg->Onext )
00192 * where OLD(...) means the value before the meshSplice operation.
00193 *
00194 * This can have two effects on the vertex structure:
00195 *  - if eOrg->Org != eDst->Org, the two vertices are merged together
00196 *  - if eOrg->Org == eDst->Org, the origin is split into two vertices
00197 * In both cases, eDst->Org is changed and eOrg->Org is untouched.
00198 *
00199 * Similarly (and independently) for the face structure,
00200 *  - if eOrg->Lface == eDst->Lface, one loop is split into two
00201 *  - if eOrg->Lface != eDst->Lface, two distinct loops are joined into one
00202 * In both cases, eDst->Lface is changed and eOrg->Lface is unaffected.
00203 *
00204 * tessMeshDelete( eDel ) removes the edge eDel.  There are several cases:
00205 * if (eDel->Lface != eDel->Rface), we join two loops into one; the loop
00206 * eDel->Lface is deleted.  Otherwise, we are splitting one loop into two;
00207 * the newly created loop will contain eDel->Dst.  If the deletion of eDel
00208 * would create isolated vertices, those are deleted as well.
00209 *
00210 * ********************** Other Edge Operations **************************
00211 *
00212 * tessMeshAddEdgeVertex( eOrg ) creates a new edge eNew such that
00213 * eNew == eOrg->Lnext, and eNew->Dst is a newly created vertex.
00214 * eOrg and eNew will have the same left face.
00215 *
00216 * tessMeshSplitEdge( eOrg ) splits eOrg into two edges eOrg and eNew,
00217 * such that eNew == eOrg->Lnext.  The new vertex is eOrg->Dst == eNew->Org.
00218 * eOrg and eNew will have the same left face.
00219 *
00220 * tessMeshConnect( eOrg, eDst ) creates a new edge from eOrg->Dst
00221 * to eDst->Org, and returns the corresponding half-edge eNew.
00222 * If eOrg->Lface == eDst->Lface, this splits one loop into two,
00223 * and the newly created loop is eNew->Lface.  Otherwise, two disjoint
00224 * loops are merged into one, and the loop eDst->Lface is destroyed.
00225 *
00226 * ************************ Other Operations *****************************
00227 *
00228 * tessMeshNewMesh() creates a new mesh with no edges, no vertices,
00229 * and no loops (what we usually call a "face").
00230 *
00231 * tessMeshUnion( mesh1, mesh2 ) forms the union of all structures in
00232 * both meshes, and returns the new mesh (the old meshes are destroyed).
00233 *
00234 * tessMeshDeleteMesh( mesh ) will free all storage for any valid mesh.
00235 *
00236 * tessMeshZapFace( fZap ) destroys a face and removes it from the
00237 * global face list.  All edges of fZap will have a NULL pointer as their
00238 * left face.  Any edges which also have a NULL pointer as their right face
00239 * are deleted entirely (along with any isolated vertices this produces).
00240 * An entire mesh can be deleted by zapping its faces, one at a time,
00241 * in any order.  Zapped faces cannot be used in further mesh operations!
00242 *
00243 * tessMeshCheckMesh( mesh ) checks a mesh for self-consistency.
00244 */
00245 
00246 TESShalfEdge *tessMeshMakeEdge( TESSmesh *mesh );
00247 int tessMeshSplice( TESSmesh *mesh, TESShalfEdge *eOrg, TESShalfEdge *eDst );
00248 int tessMeshDelete( TESSmesh *mesh, TESShalfEdge *eDel );
00249 
00250 TESShalfEdge *tessMeshAddEdgeVertex( TESSmesh *mesh, TESShalfEdge *eOrg );
00251 TESShalfEdge *tessMeshSplitEdge( TESSmesh *mesh, TESShalfEdge *eOrg );
00252 TESShalfEdge *tessMeshConnect( TESSmesh *mesh, TESShalfEdge *eOrg, TESShalfEdge *eDst );
00253 
00254 TESSmesh *tessMeshNewMesh( TESSalloc* alloc );
00255 TESSmesh *tessMeshUnion( TESSalloc* alloc, TESSmesh *mesh1, TESSmesh *mesh2 );
00256 int tessMeshMergeConvexFaces( TESSmesh *mesh, int maxVertsPerFace );
00257 void tessMeshDeleteMesh( TESSalloc* alloc, TESSmesh *mesh );
00258 void tessMeshZapFace( TESSmesh *mesh, TESSface *fZap );
00259 
00260 #ifdef NDEBUG
00261 #define tessMeshCheckMesh( mesh )
00262 #else
00263 void tessMeshCheckMesh( TESSmesh *mesh );
00264 #endif
00265 
00266 #endif