mesh.h

/*
 * 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 "glues.h"

typedef struct GLUESmesh GLUESmesh;

typedef struct GLUESvertex GLUESvertex;
typedef struct GLUESface GLUESface;
typedef struct GLUEShalfEdge GLUEShalfEdge;

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 GLUESvertex
{
   GLUESvertex*    next;          /* next vertex (never NULL) */
   GLUESvertex*    prev;          /* previous vertex (never NULL) */
   GLUEShalfEdge*  anEdge;        /* a half-edge with this origin */
   void*         data;          /* client's data */

   /* Internal data (keep hidden) */
   double coords[3];           /* vertex location in 3D */
   GLfloat s, t;                /* projection onto the sweep plane */
   long    pqHandle;            /* to allow deletion from priority queue */
};

struct GLUESface
{
   GLUESface*     next;           /* next face (never NULL) */
   GLUESface*     prev;           /* previous face (never NULL) */
   GLUEShalfEdge* anEdge;         /* a half edge with this left face */
   void*        data;           /* room for client's data */

   /* Internal data (keep hidden) */
   GLUESface*     trail;          /* "stack" for conversion to strips */
   GLboolean    marked;         /* flag for conversion to strips */
   GLboolean    inside;         /* this face is in the polygon interior */
};

struct GLUEShalfEdge
{
   GLUEShalfEdge* next;           /* doubly-linked list (prev==Sym->next) */
   GLUEShalfEdge* Sym;            /* same edge, opposite direction */
   GLUEShalfEdge* Onext;          /* next edge CCW around origin */
   GLUEShalfEdge* Lnext;          /* next edge CCW around left face */
   GLUESvertex*   Org;            /* origin vertex (Overtex too long) */
   GLUESface*     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 GLUESmesh
{
   GLUESvertex   vHead;           /* dummy header for vertex list */
   GLUESface     fHead;           /* dummy header for face list */
   GLUEShalfEdge eHead;           /* dummy header for edge list */
   GLUEShalfEdge 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.
 */

GLUEShalfEdge* __gl_meshMakeEdge(GLUESmesh* mesh);
int          __gl_meshSplice(GLUEShalfEdge* eOrg, GLUEShalfEdge* eDst);
int          __gl_meshDelete(GLUEShalfEdge* eDel);

GLUEShalfEdge* __gl_meshAddEdgeVertex(GLUEShalfEdge* eOrg);
GLUEShalfEdge* __gl_meshSplitEdge(GLUEShalfEdge* eOrg);
GLUEShalfEdge* __gl_meshConnect(GLUEShalfEdge* eOrg, GLUEShalfEdge* eDst);

GLUESmesh*     __gl_meshNewMesh(void);
GLUESmesh*     __gl_meshUnion(GLUESmesh* mesh1, GLUESmesh* mesh2);
void         __gl_meshDeleteMesh(GLUESmesh* mesh);
void         __gl_meshZapFace(GLUESface* fZap);

#ifdef NDEBUG
   #define __gl_meshCheckMesh(mesh)
#else
   void __gl_meshCheckMesh(GLUESmesh* mesh);
#endif

#endif /* __mesh_h_ */