add tessellation library

1 files changed, 968 insertions, 0 deletions

diff --git a/src/libtess2/tess.c b/src/libtess2/tess.c
new file mode 100755
index 0000000000..ad71478375
--- /dev/null
+++ b/src/libtess2/tess.c
@@ -0,0 +1,968 @@
+/*
+** 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 <stddef.h>
+#include <assert.h>
+#include <setjmp.h>
+#include "bucketalloc.h"
+#include "tess.h"
+#include "mesh.h"
+#include "sweep.h"
+#include "geom.h"
+#include <math.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#define TRUE 1
+#define FALSE 0
+
+#define Dot(u,v)	(u[0]*v[0] + u[1]*v[1] + u[2]*v[2])
+
+static void Normalize( TESSreal v[3] )
+{
+	TESSreal len = v[0]*v[0] + v[1]*v[1] + v[2]*v[2];
+
+	assert( len > 0 );
+	len = sqrtf( len );
+	v[0] /= len;
+	v[1] /= len;
+	v[2] /= len;
+}
+
+#define ABS(x)	((x) < 0 ? -(x) : (x))
+
+static int LongAxis( TESSreal v[3] )
+{
+	int i = 0;
+
+	if( ABS(v[1]) > ABS(v[0]) ) { i = 1; }
+	if( ABS(v[2]) > ABS(v[i]) ) { i = 2; }
+	return i;
+}
+
+static void ComputeNormal( TESStesselator *tess, TESSreal norm[3] )
+{
+	TESSvertex *v, *v1, *v2;
+	TESSreal c, tLen2, maxLen2;
+	TESSreal maxVal[3], minVal[3], d1[3], d2[3], tNorm[3];
+	TESSvertex *maxVert[3], *minVert[3];
+	TESSvertex *vHead = &tess->mesh->vHead;
+	int i;
+
+	v = vHead->next;
+	for( i = 0; i < 3; ++i ) {
+		c = v->coords[i];
+		minVal[i] = c;
+		minVert[i] = v;
+		maxVal[i] = c;
+		maxVert[i] = v;
+	}
+
+	for( v = vHead->next; v != vHead; v = v->next ) {
+		for( i = 0; i < 3; ++i ) {
+			c = v->coords[i];
+			if( c < minVal[i] ) { minVal[i] = c; minVert[i] = v; }
+			if( c > maxVal[i] ) { maxVal[i] = c; maxVert[i] = v; }
+		}
+	}
+
+	/* Find two vertices separated by at least 1/sqrt(3) of the maximum
+	* distance between any two vertices
+	*/
+	i = 0;
+	if( maxVal[1] - minVal[1] > maxVal[0] - minVal[0] ) { i = 1; }
+	if( maxVal[2] - minVal[2] > maxVal[i] - minVal[i] ) { i = 2; }
+	if( minVal[i] >= maxVal[i] ) {
+		/* All vertices are the same -- normal doesn't matter */
+		norm[0] = 0; norm[1] = 0; norm[2] = 1;
+		return;
+	}
+
+	/* Look for a third vertex which forms the triangle with maximum area
+	* (Length of normal == twice the triangle area)
+	*/
+	maxLen2 = 0;
+	v1 = minVert[i];
+	v2 = maxVert[i];
+	d1[0] = v1->coords[0] - v2->coords[0];
+	d1[1] = v1->coords[1] - v2->coords[1];
+	d1[2] = v1->coords[2] - v2->coords[2];
+	for( v = vHead->next; v != vHead; v = v->next ) {
+		d2[0] = v->coords[0] - v2->coords[0];
+		d2[1] = v->coords[1] - v2->coords[1];
+		d2[2] = v->coords[2] - v2->coords[2];
+		tNorm[0] = d1[1]*d2[2] - d1[2]*d2[1];
+		tNorm[1] = d1[2]*d2[0] - d1[0]*d2[2];
+		tNorm[2] = d1[0]*d2[1] - d1[1]*d2[0];
+		tLen2 = tNorm[0]*tNorm[0] + tNorm[1]*tNorm[1] + tNorm[2]*tNorm[2];
+		if( tLen2 > maxLen2 ) {
+			maxLen2 = tLen2;
+			norm[0] = tNorm[0];
+			norm[1] = tNorm[1];
+			norm[2] = tNorm[2];
+		}
+	}
+
+	if( maxLen2 <= 0 ) {
+		/* All points lie on a single line -- any decent normal will do */
+		norm[0] = norm[1] = norm[2] = 0;
+		norm[LongAxis(d1)] = 1;
+	}
+}
+
+
+static void CheckOrientation( TESStesselator *tess )
+{
+	TESSreal area;
+	TESSface *f, *fHead = &tess->mesh->fHead;
+	TESSvertex *v, *vHead = &tess->mesh->vHead;
+	TESShalfEdge *e;
+
+	/* When we compute the normal automatically, we choose the orientation
+	* so that the the sum of the signed areas of all contours is non-negative.
+	*/
+	area = 0;
+	for( f = fHead->next; f != fHead; f = f->next ) {
+		e = f->anEdge;
+		if( e->winding <= 0 ) continue;
+		do {
+			area += (e->Org->s - e->Dst->s) * (e->Org->t + e->Dst->t);
+			e = e->Lnext;
+		} while( e != f->anEdge );
+	}
+	if( area < 0 ) {
+		/* Reverse the orientation by flipping all the t-coordinates */
+		for( v = vHead->next; v != vHead; v = v->next ) {
+			v->t = - v->t;
+		}
+		tess->tUnit[0] = - tess->tUnit[0];
+		tess->tUnit[1] = - tess->tUnit[1];
+		tess->tUnit[2] = - tess->tUnit[2];
+	}
+}
+
+#ifdef FOR_TRITE_TEST_PROGRAM
+#include <stdlib.h>
+extern int RandomSweep;
+#define S_UNIT_X	(RandomSweep ? (2*drand48()-1) : 1.0)
+#define S_UNIT_Y	(RandomSweep ? (2*drand48()-1) : 0.0)
+#else
+#if defined(SLANTED_SWEEP)
+/* The "feature merging" is not intended to be complete.  There are
+* special cases where edges are nearly parallel to the sweep line
+* which are not implemented.  The algorithm should still behave
+* robustly (ie. produce a reasonable tesselation) in the presence
+* of such edges, however it may miss features which could have been
+* merged.  We could minimize this effect by choosing the sweep line
+* direction to be something unusual (ie. not parallel to one of the
+* coordinate axes).
+*/
+#define S_UNIT_X	(TESSreal)0.50941539564955385	/* Pre-normalized */
+#define S_UNIT_Y	(TESSreal)0.86052074622010633
+#else
+#define S_UNIT_X	(TESSreal)1.0
+#define S_UNIT_Y	(TESSreal)0.0
+#endif
+#endif
+
+/* Determine the polygon normal and project vertices onto the plane
+* of the polygon.
+*/
+void tessProjectPolygon( TESStesselator *tess )
+{
+	TESSvertex *v, *vHead = &tess->mesh->vHead;
+	TESSreal norm[3];
+	TESSreal *sUnit, *tUnit;
+	int i, first, computedNormal = FALSE;
+
+	norm[0] = tess->normal[0];
+	norm[1] = tess->normal[1];
+	norm[2] = tess->normal[2];
+	if( norm[0] == 0 && norm[1] == 0 && norm[2] == 0 ) {
+		ComputeNormal( tess, norm );
+		computedNormal = TRUE;
+	}
+	sUnit = tess->sUnit;
+	tUnit = tess->tUnit;
+	i = LongAxis( norm );
+
+#if defined(FOR_TRITE_TEST_PROGRAM) || defined(TRUE_PROJECT)
+	/* Choose the initial sUnit vector to be approximately perpendicular
+	* to the normal.
+	*/
+	Normalize( norm );
+
+	sUnit[i] = 0;
+	sUnit[(i+1)%3] = S_UNIT_X;
+	sUnit[(i+2)%3] = S_UNIT_Y;
+
+	/* Now make it exactly perpendicular */
+	w = Dot( sUnit, norm );
+	sUnit[0] -= w * norm[0];
+	sUnit[1] -= w * norm[1];
+	sUnit[2] -= w * norm[2];
+	Normalize( sUnit );
+
+	/* Choose tUnit so that (sUnit,tUnit,norm) form a right-handed frame */
+	tUnit[0] = norm[1]*sUnit[2] - norm[2]*sUnit[1];
+	tUnit[1] = norm[2]*sUnit[0] - norm[0]*sUnit[2];
+	tUnit[2] = norm[0]*sUnit[1] - norm[1]*sUnit[0];
+	Normalize( tUnit );
+#else
+	/* Project perpendicular to a coordinate axis -- better numerically */
+	sUnit[i] = 0;
+	sUnit[(i+1)%3] = S_UNIT_X;
+	sUnit[(i+2)%3] = S_UNIT_Y;
+
+	tUnit[i] = 0;
+	tUnit[(i+1)%3] = (norm[i] > 0) ? -S_UNIT_Y : S_UNIT_Y;
+	tUnit[(i+2)%3] = (norm[i] > 0) ? S_UNIT_X : -S_UNIT_X;
+#endif
+
+	/* Project the vertices onto the sweep plane */
+	for( v = vHead->next; v != vHead; v = v->next )
+	{
+		v->s = Dot( v->coords, sUnit );
+		v->t = Dot( v->coords, tUnit );
+	}
+	if( computedNormal ) {
+		CheckOrientation( tess );
+	}
+
+	/* Compute ST bounds. */
+	first = 1;
+	for( v = vHead->next; v != vHead; v = v->next )
+	{
+		if (first)
+		{
+			tess->bmin[0] = tess->bmax[0] = v->s;
+			tess->bmin[1] = tess->bmax[1] = v->t;
+			first = 0;
+		}
+		else
+		{
+			if (v->s < tess->bmin[0]) tess->bmin[0] = v->s;
+			if (v->s > tess->bmax[0]) tess->bmax[0] = v->s;
+			if (v->t < tess->bmin[1]) tess->bmin[1] = v->t;
+			if (v->t > tess->bmax[1]) tess->bmax[1] = v->t;
+		}
+	}
+}
+
+#define AddWinding(eDst,eSrc)	(eDst->winding += eSrc->winding, \
+	eDst->Sym->winding += eSrc->Sym->winding)
+
+/* tessMeshTessellateMonoRegion( face ) tessellates a monotone region
+* (what else would it do??)  The region must consist of a single
+* loop of half-edges (see mesh.h) oriented CCW.  "Monotone" in this
+* case means that any vertical line intersects the interior of the
+* region in a single interval.
+*
+* Tessellation consists of adding interior edges (actually pairs of
+* half-edges), to split the region into non-overlapping triangles.
+*
+* The basic idea is explained in Preparata and Shamos (which I don''t
+* have handy right now), although their implementation is more
+* complicated than this one.  The are two edge chains, an upper chain
+* and a lower chain.  We process all vertices from both chains in order,
+* from right to left.
+*
+* The algorithm ensures that the following invariant holds after each
+* vertex is processed: the untessellated region consists of two
+* chains, where one chain (say the upper) is a single edge, and
+* the other chain is concave.  The left vertex of the single edge
+* is always to the left of all vertices in the concave chain.
+*
+* Each step consists of adding the rightmost unprocessed vertex to one
+* of the two chains, and forming a fan of triangles from the rightmost
+* of two chain endpoints.  Determining whether we can add each triangle
+* to the fan is a simple orientation test.  By making the fan as large
+* as possible, we restore the invariant (check it yourself).
+*/
+int tessMeshTessellateMonoRegion( TESSmesh *mesh, TESSface *face )
+{
+	TESShalfEdge *up, *lo;
+
+	/* All edges are oriented CCW around the boundary of the region.
+	* First, find the half-edge whose origin vertex is rightmost.
+	* Since the sweep goes from left to right, face->anEdge should
+	* be close to the edge we want.
+	*/
+	up = face->anEdge;
+	assert( up->Lnext != up && up->Lnext->Lnext != up );
+
+	for( ; VertLeq( up->Dst, up->Org ); up = up->Lprev )
+		;
+	for( ; VertLeq( up->Org, up->Dst ); up = up->Lnext )
+		;
+	lo = up->Lprev;
+
+	while( up->Lnext != lo ) {
+		if( VertLeq( up->Dst, lo->Org )) {
+			/* up->Dst is on the left.  It is safe to form triangles from lo->Org.
+			* The EdgeGoesLeft test guarantees progress even when some triangles
+			* are CW, given that the upper and lower chains are truly monotone.
+			*/
+			while( lo->Lnext != up && (EdgeGoesLeft( lo->Lnext )
+				|| EdgeSign( lo->Org, lo->Dst, lo->Lnext->Dst ) <= 0 )) {
+					TESShalfEdge *tempHalfEdge= tessMeshConnect( mesh, lo->Lnext, lo );
+					if (tempHalfEdge == NULL) return 0;
+					lo = tempHalfEdge->Sym;
+			}
+			lo = lo->Lprev;
+		} else {
+			/* lo->Org is on the left.  We can make CCW triangles from up->Dst. */
+			while( lo->Lnext != up && (EdgeGoesRight( up->Lprev )
+				|| EdgeSign( up->Dst, up->Org, up->Lprev->Org ) >= 0 )) {
+					TESShalfEdge *tempHalfEdge= tessMeshConnect( mesh, up, up->Lprev );
+					if (tempHalfEdge == NULL) return 0;
+					up = tempHalfEdge->Sym;
+			}
+			up = up->Lnext;
+		}
+	}
+
+	/* Now lo->Org == up->Dst == the leftmost vertex.  The remaining region
+	* can be tessellated in a fan from this leftmost vertex.
+	*/
+	assert( lo->Lnext != up );
+	while( lo->Lnext->Lnext != up ) {
+		TESShalfEdge *tempHalfEdge= tessMeshConnect( mesh, lo->Lnext, lo );
+		if (tempHalfEdge == NULL) return 0;
+		lo = tempHalfEdge->Sym;
+	}
+
+	return 1;
+}
+
+
+/* tessMeshTessellateInterior( mesh ) tessellates each region of
+* the mesh which is marked "inside" the polygon.  Each such region
+* must be monotone.
+*/
+int tessMeshTessellateInterior( TESSmesh *mesh )
+{
+	TESSface *f, *next;
+
+	/*LINTED*/
+	for( f = mesh->fHead.next; f != &mesh->fHead; f = next ) {
+		/* Make sure we don''t try to tessellate the new triangles. */
+		next = f->next;
+		if( f->inside ) {
+			if ( !tessMeshTessellateMonoRegion( mesh, f ) ) return 0;
+		}
+	}
+
+	return 1;
+}
+
+
+/* tessMeshDiscardExterior( mesh ) zaps (ie. sets to NULL) all faces
+* which are not marked "inside" the polygon.  Since further mesh operations
+* on NULL faces are not allowed, the main purpose is to clean up the
+* mesh so that exterior loops are not represented in the data structure.
+*/
+void tessMeshDiscardExterior( TESSmesh *mesh )
+{
+	TESSface *f, *next;
+
+	/*LINTED*/
+	for( f = mesh->fHead.next; f != &mesh->fHead; f = next ) {
+		/* Since f will be destroyed, save its next pointer. */
+		next = f->next;
+		if( ! f->inside ) {
+			tessMeshZapFace( mesh, f );
+		}
+	}
+}
+
+/* tessMeshSetWindingNumber( mesh, value, keepOnlyBoundary ) resets the
+* winding numbers on all edges so that regions marked "inside" the
+* polygon have a winding number of "value", and regions outside
+* have a winding number of 0.
+*
+* If keepOnlyBoundary is TRUE, it also deletes all edges which do not
+* separate an interior region from an exterior one.
+*/
+int tessMeshSetWindingNumber( TESSmesh *mesh, int value,
+							 int keepOnlyBoundary )
+{
+	TESShalfEdge *e, *eNext;
+
+	for( e = mesh->eHead.next; e != &mesh->eHead; e = eNext ) {
+		eNext = e->next;
+		if( e->Rface->inside != e->Lface->inside ) {
+
+			/* This is a boundary edge (one side is interior, one is exterior). */
+			e->winding = (e->Lface->inside) ? value : -value;
+		} else {
+
+			/* Both regions are interior, or both are exterior. */
+			if( ! keepOnlyBoundary ) {
+				e->winding = 0;
+			} else {
+				if ( !tessMeshDelete( mesh, e ) ) return 0;
+			}
+		}
+	}
+	return 1;
+}
+
+void* heapAlloc( void* userData, unsigned int size )
+{
+	return malloc( size );
+}
+
+void* heapRealloc( void *userData, void* ptr, unsigned int size )
+{
+	return realloc( ptr, size );
+}
+
+void heapFree( void* userData, void* ptr )
+{
+	free( ptr );
+}
+
+static TESSalloc defaulAlloc =
+{
+	heapAlloc,
+	heapRealloc,
+	heapFree,
+	0,
+	0,
+	0,
+	0,
+	0,
+	0,
+	0,
+};
+
+TESStesselator* tessNewTess( TESSalloc* alloc )
+{
+	TESStesselator* tess;
+
+	if (alloc == NULL)
+		alloc = &defaulAlloc;
+
+	/* Only initialize fields which can be changed by the api.  Other fields
+	* are initialized where they are used.
+	*/
+
+	tess = (TESStesselator *)alloc->memalloc( alloc->userData, sizeof( TESStesselator ));
+	if ( tess == NULL ) {
+		return 0;          /* out of memory */
+	}
+	tess->alloc = *alloc;
+	/* Check and set defaults. */
+	if (tess->alloc.meshEdgeBucketSize == 0)
+		tess->alloc.meshEdgeBucketSize = 512;
+	if (tess->alloc.meshVertexBucketSize == 0)
+		tess->alloc.meshVertexBucketSize = 512;
+	if (tess->alloc.meshFaceBucketSize == 0)
+		tess->alloc.meshFaceBucketSize = 256;
+	if (tess->alloc.dictNodeBucketSize == 0)
+		tess->alloc.dictNodeBucketSize = 512;
+	if (tess->alloc.regionBucketSize == 0)
+		tess->alloc.regionBucketSize = 256;
+
+	tess->normal[0] = 0;
+	tess->normal[1] = 0;
+	tess->normal[2] = 0;
+
+	tess->bmin[0] = 0;
+	tess->bmin[1] = 0;
+	tess->bmax[0] = 0;
+	tess->bmax[1] = 0;
+
+	tess->windingRule = TESS_WINDING_ODD;
+
+	if (tess->alloc.regionBucketSize < 16)
+		tess->alloc.regionBucketSize = 16;
+	if (tess->alloc.regionBucketSize > 4096)
+		tess->alloc.regionBucketSize = 4096;
+	tess->regionPool = createBucketAlloc( &tess->alloc, "Regions",
+										 sizeof(ActiveRegion), tess->alloc.regionBucketSize );
+
+	// Initialize to begin polygon.
+	tess->mesh = NULL;
+
+	tess->outOfMemory = 0;
+	tess->vertexIndexCounter = 0;
+
+	tess->vertices = 0;
+	tess->vertexIndices = 0;
+	tess->vertexCount = 0;
+	tess->elements = 0;
+	tess->elementCount = 0;
+
+	return tess;
+}
+
+void tessDeleteTess( TESStesselator *tess )
+{
+
+	struct TESSalloc alloc = tess->alloc;
+
+	deleteBucketAlloc( tess->regionPool );
+
+	if( tess->mesh != NULL ) {
+		tessMeshDeleteMesh( &alloc, tess->mesh );
+		tess->mesh = NULL;
+	}
+	if (tess->vertices != NULL) {
+		alloc.memfree( alloc.userData, tess->vertices );
+		tess->vertices = 0;
+	}
+	if (tess->vertexIndices != NULL) {
+		alloc.memfree( alloc.userData, tess->vertexIndices );
+		tess->vertexIndices = 0;
+	}
+	if (tess->elements != NULL) {
+		alloc.memfree( alloc.userData, tess->elements );
+		tess->elements = 0;
+	}
+
+	alloc.memfree( alloc.userData, tess );
+}
+
+
+static TESSindex GetNeighbourFace(TESShalfEdge* edge)
+{
+	if (!edge->Rface)
+		return TESS_UNDEF;
+	if (!edge->Rface->inside)
+		return TESS_UNDEF;
+	return edge->Rface->n;
+}
+
+void OutputPolymesh( TESStesselator *tess, TESSmesh *mesh, int elementType, int polySize, int vertexSize )
+{
+	TESSvertex* v = 0;
+	TESSface* f = 0;
+	TESShalfEdge* edge = 0;
+	int maxFaceCount = 0;
+	int maxVertexCount = 0;
+	int faceVerts, i;
+	TESSindex *elements = 0;
+	TESSreal *vert;
+
+	// Assume that the input data is triangles now.
+	// Try to merge as many polygons as possible
+	if (polySize > 3)
+	{
+		if (!tessMeshMergeConvexFaces( mesh, polySize ))
+		{
+			tess->outOfMemory = 1;
+			return;
+		}
+	}
+
+	// Mark unused
+	for ( v = mesh->vHead.next; v != &mesh->vHead; v = v->next )
+		v->n = TESS_UNDEF;
+
+	// Create unique IDs for all vertices and faces.
+	for ( f = mesh->fHead.next; f != &mesh->fHead; f = f->next )
+	{
+		f->n = TESS_UNDEF;
+		if( !f->inside ) continue;
+
+		edge = f->anEdge;
+		faceVerts = 0;
+		do
+		{
+			v = edge->Org;
+			if ( v->n == TESS_UNDEF )
+			{
+				v->n = maxVertexCount;
+				maxVertexCount++;
+			}
+			faceVerts++;
+			edge = edge->Lnext;
+		}
+		while (edge != f->anEdge);
+
+		assert( faceVerts <= polySize );
+
+		f->n = maxFaceCount;
+		++maxFaceCount;
+	}
+
+	tess->elementCount = maxFaceCount;
+	if (elementType == TESS_CONNECTED_POLYGONS)
+		maxFaceCount *= 2;
+	tess->elements = (TESSindex*)tess->alloc.memalloc( tess->alloc.userData,
+													  sizeof(TESSindex) * maxFaceCount * polySize );
+	if (!tess->elements)
+	{
+		tess->outOfMemory = 1;
+		return;
+	}
+
+	tess->vertexCount = maxVertexCount;
+	tess->vertices = (TESSreal*)tess->alloc.memalloc( tess->alloc.userData,
+													 sizeof(TESSreal) * tess->vertexCount * vertexSize );
+	if (!tess->vertices)
+	{
+		tess->outOfMemory = 1;
+		return;
+	}
+
+	tess->vertexIndices = (TESSindex*)tess->alloc.memalloc( tess->alloc.userData,
+														    sizeof(TESSindex) * tess->vertexCount );
+	if (!tess->vertexIndices)
+	{
+		tess->outOfMemory = 1;
+		return;
+	}
+
+	// Output vertices.
+	for ( v = mesh->vHead.next; v != &mesh->vHead; v = v->next )
+	{
+		if ( v->n != TESS_UNDEF )
+		{
+			// Store coordinate
+			vert = &tess->vertices[v->n*vertexSize];
+			vert[0] = v->coords[0];
+			vert[1] = v->coords[1];
+			if ( vertexSize > 2 )
+				vert[2] = v->coords[2];
+			// Store vertex index.
+			tess->vertexIndices[v->n] = v->idx;
+		}
+	}
+
+	// Output indices.
+	elements = tess->elements;
+	for ( f = mesh->fHead.next; f != &mesh->fHead; f = f->next )
+	{
+		if ( !f->inside ) continue;
+
+		// Store polygon
+		edge = f->anEdge;
+		faceVerts = 0;
+		do
+		{
+			v = edge->Org;
+			*elements++ = v->n;
+			faceVerts++;
+			edge = edge->Lnext;
+		}
+		while (edge != f->anEdge);
+		// Fill unused.
+		for (i = faceVerts; i < polySize; ++i)
+			*elements++ = TESS_UNDEF;
+
+		// Store polygon connectivity
+		if ( elementType == TESS_CONNECTED_POLYGONS )
+		{
+			edge = f->anEdge;
+			do
+			{
+				*elements++ = GetNeighbourFace( edge );
+				edge = edge->Lnext;
+			}
+			while (edge != f->anEdge);
+			// Fill unused.
+			for (i = faceVerts; i < polySize; ++i)
+				*elements++ = TESS_UNDEF;
+		}
+	}
+}
+
+void OutputContours( TESStesselator *tess, TESSmesh *mesh, int vertexSize )
+{
+	TESSface *f = 0;
+	TESShalfEdge *edge = 0;
+	TESShalfEdge *start = 0;
+	TESSreal *verts = 0;
+	TESSindex *elements = 0;
+	TESSindex *vertInds = 0;
+	int startVert = 0;
+	int vertCount = 0;
+
+	tess->vertexCount = 0;
+	tess->elementCount = 0;
+
+	for ( f = mesh->fHead.next; f != &mesh->fHead; f = f->next )
+	{
+		if ( !f->inside ) continue;
+
+		start = edge = f->anEdge;
+		do
+		{
+			++tess->vertexCount;
+			edge = edge->Lnext;
+		}
+		while ( edge != start );
+
+		++tess->elementCount;
+	}
+
+	tess->elements = (TESSindex*)tess->alloc.memalloc( tess->alloc.userData,
+													  sizeof(TESSindex) * tess->elementCount * 2 );
+	if (!tess->elements)
+	{
+		tess->outOfMemory = 1;
+		return;
+	}
+
+	tess->vertices = (TESSreal*)tess->alloc.memalloc( tess->alloc.userData,
+													  sizeof(TESSreal) * tess->vertexCount * vertexSize );
+	if (!tess->vertices)
+	{
+		tess->outOfMemory = 1;
+		return;
+	}
+
+	tess->vertexIndices = (TESSindex*)tess->alloc.memalloc( tess->alloc.userData,
+														    sizeof(TESSindex) * tess->vertexCount );
+	if (!tess->vertexIndices)
+	{
+		tess->outOfMemory = 1;
+		return;
+	}
+
+	verts = tess->vertices;
+	elements = tess->elements;
+	vertInds = tess->vertexIndices;
+
+	startVert = 0;
+
+	for ( f = mesh->fHead.next; f != &mesh->fHead; f = f->next )
+	{
+		if ( !f->inside ) continue;
+
+		vertCount = 0;
+		start = edge = f->anEdge;
+		do
+		{
+			*verts++ = edge->Org->coords[0];
+			*verts++ = edge->Org->coords[1];
+			if ( vertexSize > 2 )
+				*verts++ = edge->Org->coords[2];
+			*vertInds++ = edge->Org->idx;
+			++vertCount;
+			edge = edge->Lnext;
+		}
+		while ( edge != start );
+
+		elements[0] = startVert;
+		elements[1] = vertCount;
+		elements += 2;
+
+		startVert += vertCount;
+	}
+}
+
+void tessAddContour( TESStesselator *tess, int size, const void* vertices,
+					int stride, int numVertices )
+{
+	const unsigned char *src = (const unsigned char*)vertices;
+	TESShalfEdge *e;
+	int i;
+
+	if ( tess->mesh == NULL )
+	  	tess->mesh = tessMeshNewMesh( &tess->alloc );
+ 	if ( tess->mesh == NULL ) {
+		tess->outOfMemory = 1;
+		return;
+	}
+
+	if ( size < 2 )
+		size = 2;
+	if ( size > 3 )
+		size = 3;
+
+	e = NULL;
+
+	for( i = 0; i < numVertices; ++i )
+	{
+		const TESSreal* coords = (const TESSreal*)src;
+		src += stride;
+
+		if( e == NULL ) {
+			/* Make a self-loop (one vertex, one edge). */
+			e = tessMeshMakeEdge( tess->mesh );
+			if ( e == NULL ) {
+				tess->outOfMemory = 1;
+				return;
+			}
+			if ( !tessMeshSplice( tess->mesh, e, e->Sym ) ) {
+				tess->outOfMemory = 1;
+				return;
+			}
+		} else {
+			/* Create a new vertex and edge which immediately follow e
+			* in the ordering around the left face.
+			*/
+			if ( tessMeshSplitEdge( tess->mesh, e ) == NULL ) {
+				tess->outOfMemory = 1;
+				return;
+			}
+			e = e->Lnext;
+		}
+
+		/* The new vertex is now e->Org. */
+		e->Org->coords[0] = coords[0];
+		e->Org->coords[1] = coords[1];
+		if ( size > 2 )
+			e->Org->coords[2] = coords[2];
+		else
+			e->Org->coords[2] = 0;
+		/* Store the insertion number so that the vertex can be later recognized. */
+		e->Org->idx = tess->vertexIndexCounter++;
+
+		/* The winding of an edge says how the winding number changes as we
+		* cross from the edge''s right face to its left face.  We add the
+		* vertices in such an order that a CCW contour will add +1 to
+		* the winding number of the region inside the contour.
+		*/
+		e->winding = 1;
+		e->Sym->winding = -1;
+	}
+}
+
+int tessTesselate( TESStesselator *tess, int windingRule, int elementType,
+				  int polySize, int vertexSize, const TESSreal* normal )
+{
+	TESSmesh *mesh;
+	int rc = 1;
+
+	if (tess->vertices != NULL) {
+		tess->alloc.memfree( tess->alloc.userData, tess->vertices );
+		tess->vertices = 0;
+	}
+	if (tess->elements != NULL) {
+		tess->alloc.memfree( tess->alloc.userData, tess->elements );
+		tess->elements = 0;
+	}
+	if (tess->vertexIndices != NULL) {
+		tess->alloc.memfree( tess->alloc.userData, tess->vertexIndices );
+		tess->vertexIndices = 0;
+	}
+
+	tess->vertexIndexCounter = 0;
+
+	if (normal)
+	{
+		tess->normal[0] = normal[0];
+		tess->normal[1] = normal[1];
+		tess->normal[2] = normal[2];
+	}
+
+	tess->windingRule = windingRule;
+
+	if (vertexSize < 2)
+		vertexSize = 2;
+	if (vertexSize > 3)
+		vertexSize = 3;
+
+	if (setjmp(tess->env) != 0) {
+		/* come back here if out of memory */
+		return 0;
+	}
+
+	if (!tess->mesh)
+	{
+		return 0;
+	}
+
+	/* Determine the polygon normal and project vertices onto the plane
+	* of the polygon.
+	*/
+	tessProjectPolygon( tess );
+
+	/* tessComputeInterior( tess ) computes the planar arrangement specified
+	* by the given contours, and further subdivides this arrangement
+	* into regions.  Each region is marked "inside" if it belongs
+	* to the polygon, according to the rule given by tess->windingRule.
+	* Each interior region is guaranteed be monotone.
+	*/
+	if ( !tessComputeInterior( tess ) ) {
+		longjmp(tess->env,1);  /* could've used a label */
+	}
+
+	mesh = tess->mesh;
+
+	/* If the user wants only the boundary contours, we throw away all edges
+	* except those which separate the interior from the exterior.
+	* Otherwise we tessellate all the regions marked "inside".
+	*/
+	if (elementType == TESS_BOUNDARY_CONTOURS) {
+		rc = tessMeshSetWindingNumber( mesh, 1, TRUE );
+	} else {
+		rc = tessMeshTessellateInterior( mesh );
+	}
+	if (rc == 0) longjmp(tess->env,1);  /* could've used a label */
+
+	tessMeshCheckMesh( mesh );
+
+	if (elementType == TESS_BOUNDARY_CONTOURS) {
+		OutputContours( tess, mesh, vertexSize );     /* output contours */
+	}
+	else
+	{
+		OutputPolymesh( tess, mesh, elementType, polySize, vertexSize );     /* output polygons */
+	}
+
+	tessMeshDeleteMesh( &tess->alloc, mesh );
+	tess->mesh = NULL;
+
+	if (tess->outOfMemory)
+		return 0;
+	return 1;
+}
+
+int tessGetVertexCount( TESStesselator *tess )
+{
+	return tess->vertexCount;
+}
+
+const TESSreal* tessGetVertices( TESStesselator *tess )
+{
+	return tess->vertices;
+}
+
+const TESSindex* tessGetVertexIndices( TESStesselator *tess )
+{
+	return tess->vertexIndices;
+}
+
+int tessGetElementCount( TESStesselator *tess )
+{
+	return tess->elementCount;
+}
+
+const int* tessGetElements( TESStesselator *tess )
+{
+	return tess->elements;
+}