mesh.h File Reference

#include "glu-libtess.h"

Include dependency graph for mesh.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	GLUvertex
struct	GLUface
struct	GLUhalfEdge
struct	GLUmesh

Macros
#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 */

Typedefs
typedef struct GLUmesh	GLUmesh
typedef struct GLUvertex	GLUvertex
typedef struct GLUface	GLUface
typedef struct GLUhalfEdge	GLUhalfEdge
typedef struct ActiveRegion	ActiveRegion

Functions
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)
void	__gl_meshCheckMesh (GLUmesh *mesh)

---

Class Documentation

GLUvertex

struct GLUvertex

Collaboration diagram for GLUvertex:

Class Members
GLUhalfEdge *	anEdge
GLdouble	coords[3]
void *	data
GLUvertex *	next
long	pqHandle
GLUvertex *	prev
GLdouble	s
GLdouble	t

GLUface

struct GLUface

Collaboration diagram for GLUface:

Class Members
GLUhalfEdge *	anEdge
void *	data
GLboolean	inside
GLboolean	marked
GLUface *	next
GLUface *	prev
GLUface *	trail

GLUhalfEdge

struct GLUhalfEdge

Collaboration diagram for GLUhalfEdge:

Class Members
ActiveRegion *	activeRegion
GLUface *	Lface
GLUhalfEdge *	Lnext
GLUhalfEdge *	next
GLUhalfEdge *	Onext
GLUvertex *	Org
GLUhalfEdge *	Sym
int	winding

GLUmesh

struct GLUmesh

Collaboration diagram for GLUmesh:

Class Members
GLUhalfEdge	eHead
GLUhalfEdge	eHeadSym
GLUface	fHead
GLUvertex	vHead

Macro Definition Documentation

Dnext

#define Dnext   Rprev->Sym /* 3 pointers */

Dprev

#define Dprev   Lnext->Sym

Dst

#define Dst   Sym->Org

Lprev

#define Lprev   Onext->Sym

Oprev

#define Oprev   Sym->Lnext

Rface

#define Rface   Sym->Lface

Rnext

#define Rnext   Oprev->Sym /* 3 pointers */

Rprev

#define Rprev   Sym->Onext

Typedef Documentation

ActiveRegion

typedef struct ActiveRegion ActiveRegion

GLUface

typedef struct GLUface GLUface

GLUhalfEdge

typedef struct GLUhalfEdge GLUhalfEdge

GLUmesh

typedef struct GLUmesh GLUmesh

GLUvertex

typedef struct GLUvertex GLUvertex

Function Documentation

__gl_meshAddEdgeVertex()

GLUhalfEdge * __gl_meshAddEdgeVertex

(

GLUhalfEdge *

eOrg

)

{
  GLUhalfEdge *eNewSym;
  GLUhalfEdge *eNew = MakeEdge( eOrg );
  if (eNew == NULL) return NULL;
 
  eNewSym = eNew->Sym;
 
  /* Connect the new edge appropriately */
  Splice( eNew, eOrg->Lnext );
 
  /* Set the vertex and face information */
  eNew->Org = eOrg->Dst;
  {
    GLUvertex *newVertex= allocVertex();
    if (newVertex == NULL) return NULL;
 
    MakeVertex( newVertex, eNewSym, eNew->Org );
  }
  eNew->Lface = eNewSym->Lface = eOrg->Lface;
 
  return eNew;
}

References allocVertex(), GLUhalfEdge::Lface, GLUhalfEdge::Lnext, MakeEdge(), MakeVertex(), GLUhalfEdge::Org, Splice(), and GLUhalfEdge::Sym.

Referenced by __gl_meshSplitEdge().

Here is the call graph for this function:

Here is the caller graph for this function:

__gl_meshCheckMesh()

void __gl_meshCheckMesh

(

GLUmesh *

mesh

)

{
  GLUface *fHead = &mesh->fHead;
  GLUvertex *vHead = &mesh->vHead;
  GLUhalfEdge *eHead = &mesh->eHead;
  GLUface *f, *fPrev;
  GLUvertex *v, *vPrev;
  GLUhalfEdge *e, *ePrev;
 
  fPrev = fHead;
  for( fPrev = fHead ; (f = fPrev->next) != fHead; fPrev = f) {
    assert( f->prev == fPrev );
    e = f->anEdge;
    do {
      assert( e->Sym != e );
      assert( e->Sym->Sym == e );
      assert( e->Lnext->Onext->Sym == e );
      assert( e->Onext->Sym->Lnext == e );
      assert( e->Lface == f );
      e = e->Lnext;
    } while( e != f->anEdge );
  }
  assert( f->prev == fPrev && f->anEdge == NULL && f->data == NULL );
 
  vPrev = vHead;
  for( vPrev = vHead ; (v = vPrev->next) != vHead; vPrev = v) {
    assert( v->prev == vPrev );
    e = v->anEdge;
    do {
      assert( e->Sym != e );
      assert( e->Sym->Sym == e );
      assert( e->Lnext->Onext->Sym == e );
      assert( e->Onext->Sym->Lnext == e );
      assert( e->Org == v );
      e = e->Onext;
    } while( e != v->anEdge );
  }
  assert( v->prev == vPrev && v->anEdge == NULL && v->data == NULL );
 
  ePrev = eHead;
  for( ePrev = eHead ; (e = ePrev->next) != eHead; ePrev = e) {
    assert( e->Sym->next == ePrev->Sym );
    assert( e->Sym != e );
    assert( e->Sym->Sym == e );
    assert( e->Org != NULL );
    assert( e->Dst != NULL );
    assert( e->Lnext->Onext->Sym == e );
    assert( e->Onext->Sym->Lnext == e );
  }
  assert( e->Sym->next == ePrev->Sym
       && e->Sym == &mesh->eHeadSym
       && e->Sym->Sym == e
       && e->Org == NULL && e->Dst == NULL
       && e->Lface == NULL && e->Rface == NULL );
}

References GLUvertex::anEdge, GLUface::anEdge, GLUvertex::data, GLUface::data, GLUmesh::eHead, GLUmesh::eHeadSym, GLUmesh::fHead, GLUhalfEdge::Lface, GLUhalfEdge::Lnext, GLUvertex::next, GLUface::next, GLUhalfEdge::next, GLUhalfEdge::Onext, GLUhalfEdge::Org, GLUvertex::prev, GLUface::prev, GLUhalfEdge::Sym, and GLUmesh::vHead.

Referenced by __gl_computeInterior(), and gluTessEndPolygon().

Here is the caller graph for this function:

__gl_meshConnect()

GLUhalfEdge * __gl_meshConnect	(	GLUhalfEdge *	eOrg,
		GLUhalfEdge *	eDst
	)

{
  GLUhalfEdge *eNewSym;
  int joiningLoops = FALSE;  
  GLUhalfEdge *eNew = MakeEdge( eOrg );
  if (eNew == NULL) return NULL;
 
  eNewSym = eNew->Sym;
 
  if( eDst->Lface != eOrg->Lface ) {
    /* We are connecting two disjoint loops -- destroy eDst->Lface */
    joiningLoops = TRUE;
    KillFace( eDst->Lface, eOrg->Lface );
  }
 
  /* Connect the new edge appropriately */
  Splice( eNew, eOrg->Lnext );
  Splice( eNewSym, eDst );
 
  /* Set the vertex and face information */
  eNew->Org = eOrg->Dst;
  eNewSym->Org = eDst->Org;
  eNew->Lface = eNewSym->Lface = eOrg->Lface;
 
  /* Make sure the old face points to a valid half-edge */
  eOrg->Lface->anEdge = eNewSym;
 
  if( ! joiningLoops ) {
    GLUface *newFace= allocFace();
    if (newFace == NULL) return NULL;
 
    /* We split one loop into two -- the new loop is eNew->Lface */
    MakeFace( newFace, eNew, eOrg->Lface );
  }
  return eNew;
}

References allocFace(), GLUface::anEdge, FALSE, KillFace(), GLUhalfEdge::Lface, GLUhalfEdge::Lnext, MakeEdge(), MakeFace(), GLUhalfEdge::Org, Splice(), GLUhalfEdge::Sym, and TRUE.

Referenced by __gl_meshTessellateMonoRegion(), ConnectLeftVertex(), ConnectRightVertex(), FinishLeftRegions(), and TopLeftRegion().

Here is the call graph for this function:

Here is the caller graph for this function:

__gl_meshDelete()

int __gl_meshDelete

(

GLUhalfEdge *

eDel

)

{
  GLUhalfEdge *eDelSym = eDel->Sym;
  int joiningLoops = FALSE;
 
  /* First step: disconnect the origin vertex eDel->Org.  We make all
   * changes to get a consistent mesh in this "intermediate" state.
   */
  if( eDel->Lface != eDel->Rface ) {
    /* We are joining two loops into one -- remove the left face */
    joiningLoops = TRUE;
    KillFace( eDel->Lface, eDel->Rface );
  }
 
  if( eDel->Onext == eDel ) {
    KillVertex( eDel->Org, NULL );
  } else {
    /* Make sure that eDel->Org and eDel->Rface point to valid half-edges */
    eDel->Rface->anEdge = eDel->Oprev;
    eDel->Org->anEdge = eDel->Onext;
 
    Splice( eDel, eDel->Oprev );
    if( ! joiningLoops ) {
      GLUface *newFace= allocFace();
      if (newFace == NULL) return 0; 
 
      /* We are splitting one loop into two -- create a new loop for eDel. */
      MakeFace( newFace, eDel, eDel->Lface );
    }
  }
 
  /* Claim: the mesh is now in a consistent state, except that eDel->Org
   * may have been deleted.  Now we disconnect eDel->Dst.
   */
  if( eDelSym->Onext == eDelSym ) {
    KillVertex( eDelSym->Org, NULL );
    KillFace( eDelSym->Lface, NULL );
  } else {
    /* Make sure that eDel->Dst and eDel->Lface point to valid half-edges */
    eDel->Lface->anEdge = eDelSym->Oprev;
    eDelSym->Org->anEdge = eDelSym->Onext;
    Splice( eDelSym, eDelSym->Oprev );
  }
 
  /* Any isolated vertices or faces have already been freed. */
  KillEdge( eDel );
 
  return 1;
}

References allocFace(), GLUvertex::anEdge, GLUface::anEdge, FALSE, KillEdge(), KillFace(), KillVertex(), GLUhalfEdge::Lface, MakeFace(), GLUhalfEdge::Onext, GLUhalfEdge::Org, Splice(), GLUhalfEdge::Sym, and TRUE.

Referenced by __gl_meshSetWindingNumber(), AddRightEdges(), ConnectLeftDegenerate(), FixUpperEdge(), RemoveDegenerateEdges(), RemoveDegenerateFaces(), and WalkDirtyRegions().

Here is the call graph for this function:

Here is the caller graph for this function:

__gl_meshDeleteMesh()

void __gl_meshDeleteMesh

(

GLUmesh *

mesh

)

{
  GLUface *f, *fNext;
  GLUvertex *v, *vNext;
  GLUhalfEdge *e, *eNext;
 
  for( f = mesh->fHead.next; f != &mesh->fHead; f = fNext ) {
    fNext = f->next;
    memFree( f );
  }
 
  for( v = mesh->vHead.next; v != &mesh->vHead; v = vNext ) {
    vNext = v->next;
    memFree( v );
  }
 
  for( e = mesh->eHead.next; e != &mesh->eHead; e = eNext ) {
    /* One call frees both e and e->Sym (see EdgePair above) */
    eNext = e->next;
    memFree( e );
  }
 
  memFree( mesh );
}

References GLUmesh::eHead, GLUmesh::fHead, memFree, GLUvertex::next, GLUface::next, GLUhalfEdge::next, and GLUmesh::vHead.

Referenced by gluTessEndPolygon(), and MakeDormant().

Here is the caller graph for this function:

__gl_meshMakeEdge()

GLUhalfEdge * __gl_meshMakeEdge

(

GLUmesh *

mesh

)

{
  GLUvertex *newVertex1= allocVertex();
  GLUvertex *newVertex2= allocVertex();
  GLUface *newFace= allocFace();
  GLUhalfEdge *e;
 
  /* if any one is null then all get freed */
  if (newVertex1 == NULL || newVertex2 == NULL || newFace == NULL) {
     if (newVertex1 != NULL) memFree(newVertex1);
     if (newVertex2 != NULL) memFree(newVertex2);
     if (newFace != NULL) memFree(newFace);     
     return NULL;
  } 
 
  e = MakeEdge( &mesh->eHead );
  if (e == NULL) {
     memFree(newVertex1);
     memFree(newVertex2);
     memFree(newFace);
     return NULL;
  }
 
  MakeVertex( newVertex1, e, &mesh->vHead );
  MakeVertex( newVertex2, e->Sym, &mesh->vHead );
  MakeFace( newFace, e, &mesh->fHead );
  return e;
}

References allocFace(), allocVertex(), GLUmesh::eHead, GLUmesh::fHead, MakeEdge(), MakeFace(), MakeVertex(), memFree, GLUhalfEdge::Sym, and GLUmesh::vHead.

Referenced by AddSentinel(), and AddVertex().

Here is the call graph for this function:

Here is the caller graph for this function:

__gl_meshNewMesh()

GLUmesh * __gl_meshNewMesh

(

void

)

{
  GLUvertex *v;
  GLUface *f;
  GLUhalfEdge *e;
  GLUhalfEdge *eSym;
  GLUmesh *mesh = (GLUmesh *)memAlloc( sizeof( GLUmesh ));
  if (mesh == NULL) {
     return NULL;
  }
  
  v = &mesh->vHead;
  f = &mesh->fHead;
  e = &mesh->eHead;
  eSym = &mesh->eHeadSym;
 
  v->next = v->prev = v;
  v->anEdge = NULL;
  v->data = NULL;
 
  f->next = f->prev = f;
  f->anEdge = NULL;
  f->data = NULL;
  f->trail = NULL;
  f->marked = FALSE;
  f->inside = FALSE;
 
  e->next = e;
  e->Sym = eSym;
  e->Onext = NULL;
  e->Lnext = NULL;
  e->Org = NULL;
  e->Lface = NULL;
  e->winding = 0;
  e->activeRegion = NULL;
 
  eSym->next = eSym;
  eSym->Sym = e;
  eSym->Onext = NULL;
  eSym->Lnext = NULL;
  eSym->Org = NULL;
  eSym->Lface = NULL;
  eSym->winding = 0;
  eSym->activeRegion = NULL;
 
  return mesh;
}

References GLUhalfEdge::activeRegion, GLUvertex::anEdge, GLUface::anEdge, GLUvertex::data, GLUface::data, GLUmesh::eHead, GLUmesh::eHeadSym, FALSE, GLUmesh::fHead, GLUface::inside, GLUhalfEdge::Lface, GLUhalfEdge::Lnext, GLUface::marked, memAlloc, GLUvertex::next, GLUface::next, GLUhalfEdge::next, GLUhalfEdge::Onext, GLUhalfEdge::Org, GLUvertex::prev, GLUface::prev, GLUhalfEdge::Sym, GLUface::trail, GLUmesh::vHead, and GLUhalfEdge::winding.

Referenced by EmptyCache().

Here is the caller graph for this function:

__gl_meshSplice()

int __gl_meshSplice	(	GLUhalfEdge *	eOrg,
		GLUhalfEdge *	eDst
	)

{
  int joiningLoops = FALSE;
  int joiningVertices = FALSE;
 
  if( eOrg == eDst ) return 1;
 
  if( eDst->Org != eOrg->Org ) {
    /* We are merging two disjoint vertices -- destroy eDst->Org */
    joiningVertices = TRUE;
    KillVertex( eDst->Org, eOrg->Org );
  }
  if( eDst->Lface != eOrg->Lface ) {
    /* We are connecting two disjoint loops -- destroy eDst->Lface */
    joiningLoops = TRUE;
    KillFace( eDst->Lface, eOrg->Lface );
  }
 
  /* Change the edge structure */
  Splice( eDst, eOrg );
 
  if( ! joiningVertices ) {
    GLUvertex *newVertex= allocVertex();
    if (newVertex == NULL) return 0;
 
    /* We split one vertex into two -- the new vertex is eDst->Org.
     * Make sure the old vertex points to a valid half-edge.
     */
    MakeVertex( newVertex, eDst, eOrg->Org );
    eOrg->Org->anEdge = eOrg;
  }
  if( ! joiningLoops ) {
    GLUface *newFace= allocFace();  
    if (newFace == NULL) return 0;
 
    /* We split one loop into two -- the new loop is eDst->Lface.
     * Make sure the old face points to a valid half-edge.
     */
    MakeFace( newFace, eDst, eOrg->Lface );
    eOrg->Lface->anEdge = eOrg;
  }
 
  return 1;
}

References allocFace(), allocVertex(), GLUvertex::anEdge, GLUface::anEdge, FALSE, KillFace(), KillVertex(), GLUhalfEdge::Lface, MakeFace(), MakeVertex(), GLUhalfEdge::Org, Splice(), and TRUE.

Referenced by AddRightEdges(), AddVertex(), CheckForIntersect(), CheckForLeftSplice(), CheckForRightSplice(), ConnectLeftDegenerate(), ConnectRightVertex(), FinishLeftRegions(), and SpliceMergeVertices().

Here is the call graph for this function:

Here is the caller graph for this function:

__gl_meshSplitEdge()

GLUhalfEdge * __gl_meshSplitEdge

(

GLUhalfEdge *

eOrg

)

{
  GLUhalfEdge *eNew;
  GLUhalfEdge *tempHalfEdge= __gl_meshAddEdgeVertex( eOrg );
  if (tempHalfEdge == NULL) return NULL;
 
  eNew = tempHalfEdge->Sym;
 
  /* Disconnect eOrg from eOrg->Dst and connect it to eNew->Org */
  Splice( eOrg->Sym, eOrg->Sym->Oprev );
  Splice( eOrg->Sym, eNew );
 
  /* Set the vertex and face information */
  eOrg->Dst = eNew->Org;
  eNew->Dst->anEdge = eNew->Sym;  /* may have pointed to eOrg->Sym */
  eNew->Rface = eOrg->Rface;
  eNew->winding = eOrg->winding;  /* copy old winding information */
  eNew->Sym->winding = eOrg->Sym->winding;
 
  return eNew;
}

References __gl_meshAddEdgeVertex(), GLUhalfEdge::Org, Splice(), GLUhalfEdge::Sym, and GLUhalfEdge::winding.

Referenced by AddVertex(), CheckForIntersect(), CheckForLeftSplice(), CheckForRightSplice(), and ConnectLeftDegenerate().

Here is the call graph for this function:

Here is the caller graph for this function:

__gl_meshUnion()

GLUmesh * __gl_meshUnion	(	GLUmesh *	mesh1,
		GLUmesh *	mesh2
	)

{
  GLUface *f1 = &mesh1->fHead;
  GLUvertex *v1 = &mesh1->vHead;
  GLUhalfEdge *e1 = &mesh1->eHead;
  GLUface *f2 = &mesh2->fHead;
  GLUvertex *v2 = &mesh2->vHead;
  GLUhalfEdge *e2 = &mesh2->eHead;
 
  /* Add the faces, vertices, and edges of mesh2 to those of mesh1 */
  if( f2->next != f2 ) {
    f1->prev->next = f2->next;
    f2->next->prev = f1->prev;
    f2->prev->next = f1;
    f1->prev = f2->prev;
  }
 
  if( v2->next != v2 ) {
    v1->prev->next = v2->next;
    v2->next->prev = v1->prev;
    v2->prev->next = v1;
    v1->prev = v2->prev;
  }
 
  if( e2->next != e2 ) {
    e1->Sym->next->Sym->next = e2->next;
    e2->next->Sym->next = e1->Sym->next;
    e2->Sym->next->Sym->next = e1;
    e1->Sym->next = e2->Sym->next;
  }
 
  memFree( mesh2 );
  return mesh1;
}

References GLUmesh::eHead, GLUmesh::fHead, memFree, GLUvertex::next, GLUface::next, GLUhalfEdge::next, GLUvertex::prev, GLUface::prev, GLUhalfEdge::Sym, and GLUmesh::vHead.

__gl_meshZapFace()

void __gl_meshZapFace

(

GLUface *

fZap

)

{
  GLUhalfEdge *eStart = fZap->anEdge;
  GLUhalfEdge *e, *eNext, *eSym;
  GLUface *fPrev, *fNext;
 
  /* walk around face, deleting edges whose right face is also NULL */
  eNext = eStart->Lnext;
  do {
    e = eNext;
    eNext = e->Lnext;
 
    e->Lface = NULL;
    if( e->Rface == NULL ) {
      /* delete the edge -- see __gl_MeshDelete above */
 
      if( e->Onext == e ) {
  KillVertex( e->Org, NULL );
      } else {
  /* Make sure that e->Org points to a valid half-edge */
  e->Org->anEdge = e->Onext;
  Splice( e, e->Oprev );
      }
      eSym = e->Sym;
      if( eSym->Onext == eSym ) {
  KillVertex( eSym->Org, NULL );
      } else {
  /* Make sure that eSym->Org points to a valid half-edge */
  eSym->Org->anEdge = eSym->Onext;
  Splice( eSym, eSym->Oprev );
      }
      KillEdge( e );
    }
  } while( e != eStart );
 
  /* delete from circular doubly-linked list */
  fPrev = fZap->prev;
  fNext = fZap->next;
  fNext->prev = fPrev;
  fPrev->next = fNext;
 
  memFree( fZap );
}

References GLUvertex::anEdge, GLUface::anEdge, KillEdge(), KillVertex(), GLUhalfEdge::Lface, GLUhalfEdge::Lnext, memFree, GLUface::next, GLUhalfEdge::Onext, GLUhalfEdge::Org, GLUface::prev, Splice(), and GLUhalfEdge::Sym.

Referenced by __gl_meshDiscardExterior().

Here is the call graph for this function:

Here is the caller graph for this function: