Source/mesh.c

/*
** SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008) 
** Copyright (C) [dates of first publication] 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.
*/

//#include "tesos.h"
#include <stddef.h>
#include <assert.h>
#include "mesh.h"
#include "geom.h"
#include "bucketalloc.h"

#define TRUE 1
#define FALSE 0

/************************ Utility Routines ************************/

/* Allocate and free half-edges in pairs for efficiency.
* The *only* place that should use this fact is allocation/free.
*/
typedef struct { TESShalfEdge e, eSym; } EdgePair;

/* MakeEdge creates a new pair of half-edges which form their own loop.
* No vertex or face structures are allocated, but these must be assigned
* before the current edge operation is completed.
*/
static TESShalfEdge *MakeEdge( TESSmesh* mesh, TESShalfEdge *eNext )
{
	TESShalfEdge *e;
	TESShalfEdge *eSym;
	TESShalfEdge *ePrev;
	EdgePair *pair = (EdgePair *)bucketAlloc( mesh->edgeBucket );
	if (pair == NULL) return NULL;

	e = &pair->e;
	eSym = &pair->eSym;

	/* Make sure eNext points to the first edge of the edge pair */
	if( eNext->Sym < eNext ) { eNext = eNext->Sym; }

	/* Insert in circular doubly-linked list before eNext.
	* Note that the prev pointer is stored in Sym->next.
	*/
	ePrev = eNext->Sym->next;
	eSym->next = ePrev;
	ePrev->Sym->next = e;
	e->next = eNext;
	eNext->Sym->next = eSym;

	e->Sym = eSym;
	e->Onext = e;
	e->Lnext = eSym;
	e->Org = NULL;
	e->Lface = NULL;
	e->winding = 0;
	e->activeRegion = NULL;
	e->mark = 0;

	eSym->Sym = e;
	eSym->Onext = eSym;
	eSym->Lnext = e;
	eSym->Org = NULL;
	eSym->Lface = NULL;
	eSym->winding = 0;
	eSym->activeRegion = NULL;
	eSym->mark = 0;

	return e;
}

/* Splice( a, b ) is best described by the Guibas/Stolfi paper or the
* CS348a notes (see mesh.h).  Basically it modifies the mesh so that
* a->Onext and b->Onext are exchanged.  This can have various effects
* depending on whether a and b belong to different face or vertex rings.
* For more explanation see tessMeshSplice() below.
*/
static void Splice( TESShalfEdge *a, TESShalfEdge *b )
{
	TESShalfEdge *aOnext = a->Onext;
	TESShalfEdge *bOnext = b->Onext;

	aOnext->Sym->Lnext = b;
	bOnext->Sym->Lnext = a;
	a->Onext = bOnext;
	b->Onext = aOnext;
}

/* MakeVertex( newVertex, eOrig, vNext ) attaches a new vertex and makes it the
* origin of all edges in the vertex loop to which eOrig belongs. "vNext" gives
* a place to insert the new vertex in the global vertex list.  We insert
* the new vertex *before* vNext so that algorithms which walk the vertex
* list will not see the newly created vertices.
*/
static void MakeVertex( TESSvertex *newVertex, 
					   TESShalfEdge *eOrig, TESSvertex *vNext )
{
	TESShalfEdge *e;
	TESSvertex *vPrev;
	TESSvertex *vNew = newVertex;

	assert(vNew != NULL);

	/* insert in circular doubly-linked list before vNext */
	vPrev = vNext->prev;
	vNew->prev = vPrev;
	vPrev->next = vNew;
	vNew->next = vNext;
	vNext->prev = vNew;

	vNew->anEdge = eOrig;
	/* leave coords, s, t undefined */

	/* fix other edges on this vertex loop */
	e = eOrig;
	do {
		e->Org = vNew;
		e = e->Onext;
	} while( e != eOrig );
}

/* MakeFace( newFace, eOrig, fNext ) attaches a new face and makes it the left
* face of all edges in the face loop to which eOrig belongs.  "fNext" gives
* a place to insert the new face in the global face list.  We insert
* the new face *before* fNext so that algorithms which walk the face
* list will not see the newly created faces.
*/
static void MakeFace( TESSface *newFace, TESShalfEdge *eOrig, TESSface *fNext )
{
	TESShalfEdge *e;
	TESSface *fPrev;
	TESSface *fNew = newFace;

	assert(fNew != NULL); 

	/* insert in circular doubly-linked list before fNext */
	fPrev = fNext->prev;
	fNew->prev = fPrev;
	fPrev->next = fNew;
	fNew->next = fNext;
	fNext->prev = fNew;

	fNew->anEdge = eOrig;
	fNew->trail = NULL;
	fNew->marked = FALSE;

	/* The new face is marked "inside" if the old one was.  This is a
	* convenience for the common case where a face has been split in two.
	*/
	fNew->inside = fNext->inside;

	/* fix other edges on this face loop */
	e = eOrig;
	do {
		e->Lface = fNew;
		e = e->Lnext;
	} while( e != eOrig );
}

/* KillEdge( eDel ) destroys an edge (the half-edges eDel and eDel->Sym),
* and removes from the global edge list.
*/
static void KillEdge( TESSmesh *mesh, TESShalfEdge *eDel )
{
	TESShalfEdge *ePrev, *eNext;

	/* Half-edges are allocated in pairs, see EdgePair above */
	if( eDel->Sym < eDel ) { eDel = eDel->Sym; }

	/* delete from circular doubly-linked list */
	eNext = eDel->next;
	ePrev = eDel->Sym->next;
	eNext->Sym->next = ePrev;
	ePrev->Sym->next = eNext;

	bucketFree( mesh->edgeBucket, eDel );
}


/* KillVertex( vDel ) destroys a vertex and removes it from the global
* vertex list.  It updates the vertex loop to point to a given new vertex.
*/
static void KillVertex( TESSmesh *mesh, TESSvertex *vDel, TESSvertex *newOrg )
{
	TESShalfEdge *e, *eStart = vDel->anEdge;
	TESSvertex *vPrev, *vNext;

	/* change the origin of all affected edges */
	e = eStart;
	do {
		e->Org = newOrg;
		e = e->Onext;
	} while( e != eStart );

	/* delete from circular doubly-linked list */
	vPrev = vDel->prev;
	vNext = vDel->next;
	vNext->prev = vPrev;
	vPrev->next = vNext;

	bucketFree( mesh->vertexBucket, vDel );
}

/* KillFace( fDel ) destroys a face and removes it from the global face
* list.  It updates the face loop to point to a given new face.
*/
static void KillFace( TESSmesh *mesh, TESSface *fDel, TESSface *newLface )
{
	TESShalfEdge *e, *eStart = fDel->anEdge;
	TESSface *fPrev, *fNext;

	/* change the left face of all affected edges */
	e = eStart;
	do {
		e->Lface = newLface;
		e = e->Lnext;
	} while( e != eStart );

	/* delete from circular doubly-linked list */
	fPrev = fDel->prev;
	fNext = fDel->next;
	fNext->prev = fPrev;
	fPrev->next = fNext;

	bucketFree( mesh->faceBucket, fDel );
}


/****************** Basic Edge Operations **********************/

/* tessMeshMakeEdge creates one edge, two vertices, and a loop (face).
* The loop consists of the two new half-edges.
*/
TESShalfEdge *tessMeshMakeEdge( TESSmesh *mesh )
{
	TESSvertex *newVertex1 = (TESSvertex*)bucketAlloc(mesh->vertexBucket);
	TESSvertex *newVertex2 = (TESSvertex*)bucketAlloc(mesh->vertexBucket);
	TESSface *newFace = (TESSface*)bucketAlloc(mesh->faceBucket);
	TESShalfEdge *e;

	/* if any one is null then all get freed */
	if (newVertex1 == NULL || newVertex2 == NULL || newFace == NULL) {
		if (newVertex1 != NULL) bucketFree( mesh->vertexBucket, newVertex1 );
		if (newVertex2 != NULL) bucketFree( mesh->vertexBucket, newVertex2 );
		if (newFace != NULL) bucketFree( mesh->faceBucket, newFace );     
		return NULL;
	} 

	e = MakeEdge( mesh, &mesh->eHead );
	if (e == NULL) return NULL;

	MakeVertex( newVertex1, e, &mesh->vHead );
	MakeVertex( newVertex2, e->Sym, &mesh->vHead );
	MakeFace( newFace, e, &mesh->fHead );
	return e;
}


/* tessMeshSplice( 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.
*
* Some special cases:
* If eDst == eOrg, the operation has no effect.
* If eDst == eOrg->Lnext, the new face will have a single edge.
* If eDst == eOrg->Lprev, the old face will have a single edge.
* If eDst == eOrg->Onext, the new vertex will have a single edge.
* If eDst == eOrg->Oprev, the old vertex will have a single edge.
*/
int tessMeshSplice( TESSmesh* mesh, TESShalfEdge *eOrg, TESShalfEdge *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( mesh, eDst->Org, eOrg->Org );
	}
	if( eDst->Lface != eOrg->Lface ) {
		/* We are connecting two disjoint loops -- destroy eDst->Lface */
		joiningLoops = TRUE;
		KillFace( mesh, eDst->Lface, eOrg->Lface );
	}

	/* Change the edge structure */
	Splice( eDst, eOrg );

	if( ! joiningVertices ) {
		TESSvertex *newVertex = (TESSvertex*)bucketAlloc( mesh->vertexBucket );
		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 ) {
		TESSface *newFace = (TESSface*)bucketAlloc( mesh->faceBucket );  
		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;
}


/* tessMeshDelete( 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.
*
* This function could be implemented as two calls to tessMeshSplice
* plus a few calls to memFree, but this would allocate and delete
* unnecessary vertices and faces.
*/
int tessMeshDelete( TESSmesh *mesh, TESShalfEdge *eDel )
{
	TESShalfEdge *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( mesh, eDel->Lface, eDel->Rface );
	}

	if( eDel->Onext == eDel ) {
		KillVertex( mesh, 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 ) {
			TESSface *newFace= (TESSface*)bucketAlloc( mesh->faceBucket );
			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( mesh, eDelSym->Org, NULL );
		KillFace( mesh, 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( mesh, eDel );

	return 1;
}


/******************** Other Edge Operations **********************/

/* All these routines can be implemented with the basic edge
* operations above.  They are provided for convenience and efficiency.
*/


/* tessMeshAddEdgeVertex( 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.
*/
TESShalfEdge *tessMeshAddEdgeVertex( TESSmesh *mesh, TESShalfEdge *eOrg )
{
	TESShalfEdge *eNewSym;
	TESShalfEdge *eNew = MakeEdge( mesh, 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;
	{
		TESSvertex *newVertex= (TESSvertex*)bucketAlloc( mesh->vertexBucket );
		if (newVertex == NULL) return NULL;

		MakeVertex( newVertex, eNewSym, eNew->Org );
	}
	eNew->Lface = eNewSym->Lface = eOrg->Lface;

	return eNew;
}


/* tessMeshSplitEdge( 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.
*/
TESShalfEdge *tessMeshSplitEdge( TESSmesh *mesh, TESShalfEdge *eOrg )
{
	TESShalfEdge *eNew;
	TESShalfEdge *tempHalfEdge= tessMeshAddEdgeVertex( mesh, 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;
}


/* tessMeshConnect( 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.
*
* If (eOrg == eDst), the new face will have only two edges.
* If (eOrg->Lnext == eDst), the old face is reduced to a single edge.
* If (eOrg->Lnext->Lnext == eDst), the old face is reduced to two edges.
*/
TESShalfEdge *tessMeshConnect( TESSmesh *mesh, TESShalfEdge *eOrg, TESShalfEdge *eDst )
{
	TESShalfEdge *eNewSym;
	int joiningLoops = FALSE;  
	TESShalfEdge *eNew = MakeEdge( mesh, 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( mesh, 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 ) {
		TESSface *newFace= (TESSface*)bucketAlloc( mesh->faceBucket );
		if (newFace == NULL) return NULL;

		/* We split one loop into two -- the new loop is eNew->Lface */
		MakeFace( newFace, eNew, eOrg->Lface );
	}
	return eNew;
}


/******************** Other Operations **********************/

/* tessMeshZapFace( 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!
*/
void tessMeshZapFace( TESSmesh *mesh, TESSface *fZap )
{
	TESShalfEdge *eStart = fZap->anEdge;
	TESShalfEdge *e, *eNext, *eSym;
	TESSface *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 TESSmeshDelete above */

			if( e->Onext == e ) {
				KillVertex( mesh, 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( mesh, 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( mesh, e );
		}
	} while( e != eStart );

	/* delete from circular doubly-linked list */
	fPrev = fZap->prev;
	fNext = fZap->next;
	fNext->prev = fPrev;
	fPrev->next = fNext;

	bucketFree( mesh->faceBucket, fZap );
}


/* tessMeshNewMesh() creates a new mesh with no edges, no vertices,
* and no loops (what we usually call a "face").
*/
TESSmesh *tessMeshNewMesh( TESSalloc* alloc )
{
	TESSvertex *v;
	TESSface *f;
	TESShalfEdge *e;
	TESShalfEdge *eSym;
	TESSmesh *mesh = (TESSmesh *)alloc->memalloc( alloc->userData, sizeof( TESSmesh ));
	if (mesh == NULL) {
		return NULL;
	}
	
	if (alloc->meshEdgeBucketSize < 16)
		alloc->meshEdgeBucketSize = 16;
	if (alloc->meshEdgeBucketSize > 4096)
		alloc->meshEdgeBucketSize = 4096;
	
	if (alloc->meshVertexBucketSize < 16)
		alloc->meshVertexBucketSize = 16;
	if (alloc->meshVertexBucketSize > 4096)
		alloc->meshVertexBucketSize = 4096;
	
	if (alloc->meshFaceBucketSize < 16)
		alloc->meshFaceBucketSize = 16;
	if (alloc->meshFaceBucketSize > 4096)
		alloc->meshFaceBucketSize = 4096;

	mesh->edgeBucket = createBucketAlloc( alloc, "Mesh Edges", sizeof(EdgePair), alloc->meshEdgeBucketSize );
	mesh->vertexBucket = createBucketAlloc( alloc, "Mesh Vertices", sizeof(TESSvertex), alloc->meshVertexBucketSize );
	mesh->faceBucket = createBucketAlloc( alloc, "Mesh Faces", sizeof(TESSface), alloc->meshFaceBucketSize );

	v = &mesh->vHead;
	f = &mesh->fHead;
	e = &mesh->eHead;
	eSym = &mesh->eHeadSym;

	v->next = v->prev = v;
	v->anEdge = NULL;

	f->next = f->prev = f;
	f->anEdge = 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;
}


/* tessMeshUnion( mesh1, mesh2 ) forms the union of all structures in
* both meshes, and returns the new mesh (the old meshes are destroyed).
*/
TESSmesh *tessMeshUnion( TESSalloc* alloc, TESSmesh *mesh1, TESSmesh *mesh2 )
{
	TESSface *f1 = &mesh1->fHead;
	TESSvertex *v1 = &mesh1->vHead;
	TESShalfEdge *e1 = &mesh1->eHead;
	TESSface *f2 = &mesh2->fHead;
	TESSvertex *v2 = &mesh2->vHead;
	TESShalfEdge *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;
	}

	alloc->memfree( alloc->userData, mesh2 );
	return mesh1;
}


static int CountFaceVerts( TESSface *f )
{
	TESShalfEdge *eCur = f->anEdge;
	int n = 0;
	do
	{
		n++;
		eCur = eCur->Lnext;
	}
	while (eCur != f->anEdge);
	return n;
}

int tessMeshMergeConvexFaces( TESSmesh *mesh, int maxVertsPerFace )
{
	TESSface *f;
	TESShalfEdge *eCur, *eNext, *eSym;
	TESSvertex *vStart;
	int curNv, symNv;
	
	for( f = mesh->fHead.next; f != &mesh->fHead; f = f->next )
	{
		// Skip faces which are outside the result.
		if( !f->inside )
			continue;

		eCur = f->anEdge;
		vStart = eCur->Org;
			
		while (1)
		{
			eNext = eCur->Lnext;
			eSym = eCur->Sym;

			// Try to merge if the neighbour face is valid.
			if( eSym && eSym->Lface && eSym->Lface->inside )
			{
				// Try to merge the neighbour faces if the resulting polygons
				// does not exceed maximum number of vertices.
				curNv = CountFaceVerts( f );
				symNv = CountFaceVerts( eSym->Lface );
				if( (curNv+symNv-2) <= maxVertsPerFace )
				{
					// Merge if the resulting poly is convex.
					if( VertCCW( eCur->Lprev->Org, eCur->Org, eSym->Lnext->Lnext->Org ) &&
						VertCCW( eSym->Lprev->Org, eSym->Org, eCur->Lnext->Lnext->Org ) )
					{
						eNext = eSym->Lnext;
						if( !tessMeshDelete( mesh, eSym ) )
							return 0;
						eCur = 0;
					}
				}
			}
			
			if( eCur && eCur->Lnext->Org == vStart )
				break;
				
			// Continue to next edge.
			eCur = eNext;
		}
	}
	
	return 1;
}

void tessMeshFlipEdge( TESSmesh *mesh, TESShalfEdge *edge )
{
	TESShalfEdge *a0 = edge;
	TESShalfEdge *a1 = a0->Lnext;
	TESShalfEdge *a2 = a1->Lnext;
	TESShalfEdge *b0 = edge->Sym;
	TESShalfEdge *b1 = b0->Lnext;
	TESShalfEdge *b2 = b1->Lnext;

	TESSvertex *aOrg = a0->Org;
	TESSvertex *aOpp = a2->Org;
	TESSvertex *bOrg = b0->Org;
	TESSvertex *bOpp = b2->Org;

	TESSface *fa = a0->Lface;
	TESSface *fb = b0->Lface;

	assert(EdgeIsInternal(edge));
	assert(a2->Lnext == a0);
	assert(b2->Lnext == b0);

	a0->Org = bOpp;
	a0->Onext = b1->Sym;
	b0->Org = aOpp;
	b0->Onext = a1->Sym;
	a2->Onext = b0;
	b2->Onext = a0;
	b1->Onext = a2->Sym;
	a1->Onext = b2->Sym;

	a0->Lnext = a2;
	a2->Lnext = b1;
	b1->Lnext = a0;

	b0->Lnext = b2;
	b2->Lnext = a1;
	a1->Lnext = b0;

	a1->Lface = fb;
	b1->Lface = fa;

	fa->anEdge = a0;
	fb->anEdge = b0;

	if (aOrg->anEdge == a0) aOrg->anEdge = b1;
	if (bOrg->anEdge == b0) bOrg->anEdge = a1;

	assert( a0->Lnext->Onext->Sym == a0 );
	assert( a0->Onext->Sym->Lnext == a0 );
	assert( a0->Org->anEdge->Org == a0->Org );


	assert( a1->Lnext->Onext->Sym == a1 );
	assert( a1->Onext->Sym->Lnext == a1 );
	assert( a1->Org->anEdge->Org == a1->Org );

	assert( a2->Lnext->Onext->Sym == a2 );
	assert( a2->Onext->Sym->Lnext == a2 );
	assert( a2->Org->anEdge->Org == a2->Org );

	assert( b0->Lnext->Onext->Sym == b0 );
	assert( b0->Onext->Sym->Lnext == b0 );
	assert( b0->Org->anEdge->Org == b0->Org );

	assert( b1->Lnext->Onext->Sym == b1 );
	assert( b1->Onext->Sym->Lnext == b1 );
	assert( b1->Org->anEdge->Org == b1->Org );

	assert( b2->Lnext->Onext->Sym == b2 );
	assert( b2->Onext->Sym->Lnext == b2 );
	assert( b2->Org->anEdge->Org == b2->Org );

	assert(aOrg->anEdge->Org == aOrg);
	assert(bOrg->anEdge->Org == bOrg);

	assert(a0->Oprev->Onext->Org == a0->Org);
}

#ifdef DELETE_BY_ZAPPING

/* tessMeshDeleteMesh( mesh ) will free all storage for any valid mesh.
*/
void tessMeshDeleteMesh( TESSalloc* alloc, TESSmesh *mesh )
{
	TESSface *fHead = &mesh->fHead;

	while( fHead->next != fHead ) {
		tessMeshZapFace( fHead->next );
	}
	assert( mesh->vHead.next == &mesh->vHead );

	alloc->memfree( alloc->userData, mesh );
}

#else

/* tessMeshDeleteMesh( mesh ) will free all storage for any valid mesh.
*/
void tessMeshDeleteMesh( TESSalloc* alloc, TESSmesh *mesh )
{
	deleteBucketAlloc(mesh->edgeBucket);
	deleteBucketAlloc(mesh->vertexBucket);
	deleteBucketAlloc(mesh->faceBucket);

	alloc->memfree( alloc->userData, mesh );
}

#endif

#ifndef NDEBUG

/* tessMeshCheckMesh( mesh ) checks a mesh for self-consistency.
*/
void tessMeshCheckMesh( TESSmesh *mesh )
{
	TESSface *fHead = &mesh->fHead;
	TESSvertex *vHead = &mesh->vHead;
	TESShalfEdge *eHead = &mesh->eHead;
	TESSface *f, *fPrev;
	TESSvertex *v, *vPrev;
	TESShalfEdge *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 );

	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 );

	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 );
}

#endif