text: /*
   * 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.
  **
  ** $Date: 2012/03/29 17:22:17 $ $Revision: 1.1.1.1 $
  ** $Header: /cvs/bao-parsec/pkgs/libs/mesa/src/src/glu/sgi/libtess/mesh.h,v 1.1.1.1 2012/03/29 17:22:17 uid42307 Exp $
  */
  
  #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
  