The Ecere SDK - sdk/blob - deps/libtess/mesh.h

   1 /*
   2 ** License Applicability. Except to the extent portions of this file are
   3 ** made subject to an alternative license as permitted in the SGI Free
   4 ** Software License B, Version 1.1 (the "License"), the contents of this
   5 ** file are subject only to the provisions of the License. You may not use
   6 ** this file except in compliance with the License. You may obtain a copy
   7 ** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600
   8 ** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at:
   9 **
  10 ** http://oss.sgi.com/projects/FreeB
  11 **
  12 ** Note that, as provided in the License, the Software is distributed on an
  13 ** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS
  14 ** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND
  15 ** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A
  16 ** PARTICULAR PURPOSE, AND NON-INFRINGEMENT.
  17 **
  18 ** Original Code. The Original Code is: OpenGL Sample Implementation,
  19 ** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics,
  20 ** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc.
  21 ** Copyright in any portions created by third parties is as indicated
  22 ** elsewhere herein. All Rights Reserved.
  23 **
  24 ** Additional Notice Provisions: The application programming interfaces
  25 ** established by SGI in conjunction with the Original Code are The
  26 ** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released
  27 ** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version
  28 ** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X
  29 ** Window System(R) (Version 1.3), released October 19, 1998. This software
  30 ** was created using the OpenGL(R) version 1.2.1 Sample Implementation
  31 ** published by SGI, but has not been independently verified as being
  32 ** compliant with the OpenGL(R) version 1.2.1 Specification.
  33 **
  34 */
  35 /*
  36 ** Author: Eric Veach, July 1994.
  37 **
  38 ** $Date: 2001/03/17 00:25:41 $ $Revision: 1.1 $
  39 ** $Header: /home/krh/git/sync/mesa-cvs-repo/Mesa/src/glu/sgi/libtess/mesh.h,v 1.1 2001/03/17 00:25:41 brianp Exp $
  40 */
  41
  42 #ifndef __mesh_h_
  43 #define __mesh_h_
  44
  45 #include "glutess.h"
  46
  47 typedef struct GLUmesh GLUmesh;
  48
  49 typedef struct GLUvertex GLUvertex;
  50 typedef struct GLUface GLUface;
  51 typedef struct GLUhalfEdge GLUhalfEdge;
  52
  53 typedef struct ActiveRegion ActiveRegion;       /* Internal data */
  54
  55 /* The mesh structure is similar in spirit, notation, and operations
  56  * to the "quad-edge" structure (see L. Guibas and J. Stolfi, Primitives
  57  * for the manipulation of general subdivisions and the computation of
  58  * Voronoi diagrams, ACM Transactions on Graphics, 4(2):74-123, April 1985).
  59  * For a simplified description, see the course notes for CS348a,
  60  * "Mathematical Foundations of Computer Graphics", available at the
  61  * Stanford bookstore (and taught during the fall quarter).
  62  * The implementation also borrows a tiny subset of the graph-based approach
  63  * use in Mantyla's Geometric Work Bench (see M. Mantyla, An Introduction
  64  * to Sold Modeling, Computer Science Press, Rockville, Maryland, 1988).
  65  *
  66  * The fundamental data structure is the "half-edge".  Two half-edges
  67  * go together to make an edge, but they point in opposite directions.
  68  * Each half-edge has a pointer to its mate (the "symmetric" half-edge Sym),
  69  * its origin vertex (Org), the face on its left side (Lface), and the
  70  * adjacent half-edges in the CCW direction around the origin vertex
  71  * (Onext) and around the left face (Lnext).  There is also a "next"
  72  * pointer for the global edge list (see below).
  73  *
  74  * The notation used for mesh navigation:
  75  *      Sym   = the mate of a half-edge (same edge, but opposite direction)
  76  *      Onext = edge CCW around origin vertex (keep same origin)
  77  *      Dnext = edge CCW around destination vertex (keep same dest)
  78  *      Lnext = edge CCW around left face (dest becomes new origin)
  79  *      Rnext = edge CCW around right face (origin becomes new dest)
  80  *
  81  * "prev" means to substitute CW for CCW in the definitions above.
  82  *
  83  * The mesh keeps global lists of all vertices, faces, and edges,
  84  * stored as doubly-linked circular lists with a dummy header node.
  85  * The mesh stores pointers to these dummy headers (vHead, fHead, eHead).
  86  *
  87  * The circular edge list is special; since half-edges always occur
  88  * in pairs (e and e->Sym), each half-edge stores a pointer in only
  89  * one direction.  Starting at eHead and following the e->next pointers
  90  * will visit each *edge* once (ie. e or e->Sym, but not both).
  91  * e->Sym stores a pointer in the opposite direction, thus it is
  92  * always true that e->Sym->next->Sym->next == e.
  93  *
  94  * Each vertex has a pointer to next and previous vertices in the
  95  * circular list, and a pointer to a half-edge with this vertex as
  96  * the origin (NULL if this is the dummy header).  There is also a
  97  * field "data" for client data.
  98  *
  99  * Each face has a pointer to the next and previous faces in the
 100  * circular list, and a pointer to a half-edge with this face as
 101  * the left face (NULL if this is the dummy header).  There is also
 102  * a field "data" for client data.
 103  *
 104  * Note that what we call a "face" is really a loop; faces may consist
 105  * of more than one loop (ie. not simply connected), but there is no
 106  * record of this in the data structure.  The mesh may consist of
 107  * several disconnected regions, so it may not be possible to visit
 108  * the entire mesh by starting at a half-edge and traversing the edge
 109  * structure.
 110  *
 111  * The mesh does NOT support isolated vertices; a vertex is deleted along
 112  * with its last edge.  Similarly when two faces are merged, one of the
 113  * faces is deleted (see __gl_meshDelete below).  For mesh operations,
 114  * all face (loop) and vertex pointers must not be NULL.  However, once
 115  * mesh manipulation is finished, __gl_MeshZapFace can be used to delete
 116  * faces of the mesh, one at a time.  All external faces can be "zapped"
 117  * before the mesh is returned to the client; then a NULL face indicates
 118  * a region which is not part of the output polygon.
 119  */
 120
 121 struct GLUvertex {
 122   GLUvertex     *next;          /* next vertex (never NULL) */
 123   GLUvertex     *prev;          /* previous vertex (never NULL) */
 124   GLUhalfEdge   *anEdge;        /* a half-edge with this origin */
 125   void          *data;          /* client's data */
 126
 127   /* Internal data (keep hidden) */
 128   GLdouble      coords[3];      /* vertex location in 3D */
 129   GLdouble      s, t;           /* projection onto the sweep plane */
 130   long          pqHandle;       /* to allow deletion from priority queue */
 131 };
 132
 133 struct GLUface {
 134   GLUface       *next;          /* next face (never NULL) */
 135   GLUface       *prev;          /* previous face (never NULL) */
 136   GLUhalfEdge   *anEdge;        /* a half edge with this left face */
 137   void          *data;          /* room for client's data */
 138
 139   /* Internal data (keep hidden) */
 140   GLUface       *trail;         /* "stack" for conversion to strips */
 141   GLboolean     marked;         /* flag for conversion to strips */
 142   GLboolean     inside;         /* this face is in the polygon interior */
 143 };
 144
 145 struct GLUhalfEdge {
 146   GLUhalfEdge   *next;          /* doubly-linked list (prev==Sym->next) */
 147   GLUhalfEdge   *Sym;           /* same edge, opposite direction */
 148   GLUhalfEdge   *Onext;         /* next edge CCW around origin */
 149   GLUhalfEdge   *Lnext;         /* next edge CCW around left face */
 150   GLUvertex     *Org;           /* origin vertex (Overtex too long) */
 151   GLUface       *Lface;         /* left face */
 152
 153   /* Internal data (keep hidden) */
 154   ActiveRegion  *activeRegion;  /* a region with this upper edge (sweep.c) */
 155   int           winding;        /* change in winding number when crossing
 156                                    from the right face to the left face */
 157 };
 158
 159 #define Rface   Sym->Lface
 160 #define Dst     Sym->Org
 161
 162 #define Oprev   Sym->Lnext
 163 #define Lprev   Onext->Sym
 164 #define Dprev   Lnext->Sym
 165 #define Rprev   Sym->Onext
 166 #define Dnext   Rprev->Sym      /* 3 pointers */
 167 #define Rnext   Oprev->Sym      /* 3 pointers */
 168
 169
 170 struct GLUmesh {
 171   GLUvertex     vHead;          /* dummy header for vertex list */
 172   GLUface       fHead;          /* dummy header for face list */
 173   GLUhalfEdge   eHead;          /* dummy header for edge list */
 174   GLUhalfEdge   eHeadSym;       /* and its symmetric counterpart */
 175 };
 176
 177 /* The mesh operations below have three motivations: completeness,
 178  * convenience, and efficiency.  The basic mesh operations are MakeEdge,
 179  * Splice, and Delete.  All the other edge operations can be implemented
 180  * in terms of these.  The other operations are provided for convenience
 181  * and/or efficiency.
 182  *
 183  * When a face is split or a vertex is added, they are inserted into the
 184  * global list *before* the existing vertex or face (ie. e->Org or e->Lface).
 185  * This makes it easier to process all vertices or faces in the global lists
 186  * without worrying about processing the same data twice.  As a convenience,
 187  * when a face is split, the "inside" flag is copied from the old face.
 188  * Other internal data (v->data, v->activeRegion, f->data, f->marked,
 189  * f->trail, e->winding) is set to zero.
 190  *
 191  * ********************** Basic Edge Operations **************************
 192  *
 193  * __gl_meshMakeEdge( mesh ) creates one edge, two vertices, and a loop.
 194  * The loop (face) consists of the two new half-edges.
 195  *
 196  * __gl_meshSplice( eOrg, eDst ) is the basic operation for changing the
 197  * mesh connectivity and topology.  It changes the mesh so that
 198  *      eOrg->Onext <- OLD( eDst->Onext )
 199  *      eDst->Onext <- OLD( eOrg->Onext )
 200  * where OLD(...) means the value before the meshSplice operation.
 201  *
 202  * This can have two effects on the vertex structure:
 203  *  - if eOrg->Org != eDst->Org, the two vertices are merged together
 204  *  - if eOrg->Org == eDst->Org, the origin is split into two vertices
 205  * In both cases, eDst->Org is changed and eOrg->Org is untouched.
 206  *
 207  * Similarly (and independently) for the face structure,
 208  *  - if eOrg->Lface == eDst->Lface, one loop is split into two
 209  *  - if eOrg->Lface != eDst->Lface, two distinct loops are joined into one
 210  * In both cases, eDst->Lface is changed and eOrg->Lface is unaffected.
 211  *
 212  * __gl_meshDelete( eDel ) removes the edge eDel.  There are several cases:
 213  * if (eDel->Lface != eDel->Rface), we join two loops into one; the loop
 214  * eDel->Lface is deleted.  Otherwise, we are splitting one loop into two;
 215  * the newly created loop will contain eDel->Dst.  If the deletion of eDel
 216  * would create isolated vertices, those are deleted as well.
 217  *
 218  * ********************** Other Edge Operations **************************
 219  *
 220  * __gl_meshAddEdgeVertex( eOrg ) creates a new edge eNew such that
 221  * eNew == eOrg->Lnext, and eNew->Dst is a newly created vertex.
 222  * eOrg and eNew will have the same left face.
 223  *
 224  * __gl_meshSplitEdge( eOrg ) splits eOrg into two edges eOrg and eNew,
 225  * such that eNew == eOrg->Lnext.  The new vertex is eOrg->Dst == eNew->Org.
 226  * eOrg and eNew will have the same left face.
 227  *
 228  * __gl_meshConnect( eOrg, eDst ) creates a new edge from eOrg->Dst
 229  * to eDst->Org, and returns the corresponding half-edge eNew.
 230  * If eOrg->Lface == eDst->Lface, this splits one loop into two,
 231  * and the newly created loop is eNew->Lface.  Otherwise, two disjoint
 232  * loops are merged into one, and the loop eDst->Lface is destroyed.
 233  *
 234  * ************************ Other Operations *****************************
 235  *
 236  * __gl_meshNewMesh() creates a new mesh with no edges, no vertices,
 237  * and no loops (what we usually call a "face").
 238  *
 239  * __gl_meshUnion( mesh1, mesh2 ) forms the union of all structures in
 240  * both meshes, and returns the new mesh (the old meshes are destroyed).
 241  *
 242  * __gl_meshDeleteMesh( mesh ) will free all storage for any valid mesh.
 243  *
 244  * __gl_meshZapFace( fZap ) destroys a face and removes it from the
 245  * global face list.  All edges of fZap will have a NULL pointer as their
 246  * left face.  Any edges which also have a NULL pointer as their right face
 247  * are deleted entirely (along with any isolated vertices this produces).
 248  * An entire mesh can be deleted by zapping its faces, one at a time,
 249  * in any order.  Zapped faces cannot be used in further mesh operations!
 250  *
 251  * __gl_meshCheckMesh( mesh ) checks a mesh for self-consistency.
 252  */
 253
 254 GLUhalfEdge     *__gl_meshMakeEdge( GLUmesh *mesh );
 255 int             __gl_meshSplice( GLUhalfEdge *eOrg, GLUhalfEdge *eDst );
 256 int             __gl_meshDelete( GLUhalfEdge *eDel );
 257
 258 GLUhalfEdge     *__gl_meshAddEdgeVertex( GLUhalfEdge *eOrg );
 259 GLUhalfEdge     *__gl_meshSplitEdge( GLUhalfEdge *eOrg );
 260 GLUhalfEdge     *__gl_meshConnect( GLUhalfEdge *eOrg, GLUhalfEdge *eDst );
 261
 262 GLUmesh         *__gl_meshNewMesh( void );
 263 GLUmesh         *__gl_meshUnion( GLUmesh *mesh1, GLUmesh *mesh2 );
 264 void            __gl_meshDeleteMesh( GLUmesh *mesh );
 265 void            __gl_meshZapFace( GLUface *fZap );
 266
 267 #ifdef NDEBUG
 268 #define         __gl_meshCheckMesh( mesh )
 269 #else
 270 void            __gl_meshCheckMesh( GLUmesh *mesh );
 271 #endif
 272
 273 #endif