Quake-III-Arena

tetrahedron.c (42552B)

---

 /*
 ===========================================================================
 Copyright (C) 1999-2005 Id Software, Inc.
 
 This file is part of Quake III Arena source code.
 
 Quake III Arena source code is free software; you can redistribute it
 and/or modify it under the terms of the GNU General Public License as
 published by the Free Software Foundation; either version 2 of the License,
 or (at your option) any later version.
 
 Quake III Arena source code is distributed in the hope that it will be
 useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.
 
 You should have received a copy of the GNU General Public License
 along with Foobar; if not, write to the Free Software
 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 ===========================================================================
 */
 
 #include "qbsp.h"
 #include "l_mem.h"
 #include "../botlib/aasfile.h"
 #include "aas_store.h"
 #include "aas_cfg.h"
 #include "aas_file.h"
 
 //
 // creating tetrahedrons from a arbitrary world bounded by triangles
 //
 // a triangle has 3 corners and 3 edges
 // a tetrahedron is build out of 4 triangles
 // a tetrahedron has 6 edges
 // we start with a world bounded by triangles, a side of a triangle facing
 // towards the oudside of the world is marked as part of tetrahedron -1
 //
 // a tetrahedron is defined by two non-coplanar triangles with a shared edge
 //
 // a tetrahedron is defined by one triangle and a vertex not in the triangle plane
 //
 // if all triangles using a specific vertex have tetrahedrons
 // at both sides then this vertex will never be part of a new tetrahedron
 //
 // if all triangles using a specific edge have tetrahedrons
 // at both sides then this vertex will never be part of a new tetrahedron
 //
 // each triangle can only be shared by two tetrahedrons
 // when all triangles have tetrahedrons at both sides then we're done
 //
 // if we cannot create any new tetrahedrons and there is at least one triangle
 // which has a tetrahedron only at one side then the world leaks
 //
 
 #define Sign(x)		(x < 0 ? 1 : 0)
 
 #define MAX_TH_VERTEXES			128000
 #define MAX_TH_PLANES			128000
 #define MAX_TH_EDGES			512000
 #define MAX_TH_TRIANGLES		51200
 #define MAX_TH_TETRAHEDRONS		12800
 
 #define PLANEHASH_SIZE			1024
 #define EDGEHASH_SIZE			1024
 #define TRIANGLEHASH_SIZE		1024
 #define VERTEXHASH_SHIFT		7
 #define VERTEXHASH_SIZE			((MAX_MAP_BOUNDS>>(VERTEXHASH_SHIFT-1))+1)	//was 64
 
 #define	NORMAL_EPSILON			0.0001
 #define DIST_EPSILON			0.1
 #define VERTEX_EPSILON			0.01
 #define INTEGRAL_EPSILON		0.01
 
 
 //plane
 typedef struct th_plane_s
 {
 	vec3_t normal;
 	float dist;
 	int type;
 	int signbits;
 	struct th_plane_s *hashnext;		//next plane in hash
 } th_plane_t;
 
 //vertex
 typedef struct th_vertex_s
 {
 	vec3_t v;
 	int usercount;						//2x the number of to be processed
 										//triangles using this vertex
 	struct th_vertex_s *hashnext;		//next vertex in hash
 } th_vertex_t;
 
 //edge
 typedef struct th_edge_s
 {
 	int v[2];							//vertex indexes
 	int usercount;						//number of to be processed
 										//triangles using this edge
 	struct th_edge_s *hashnext;			//next edge in hash
 } th_edge_t;
 
 //triangle
 typedef struct th_triangle_s
 {
 	int edges[3];						//negative if edge is flipped
 	th_plane_t planes[3];				//triangle bounding planes
 	int planenum;						//plane the triangle is in
 	int front;							//tetrahedron at the front
 	int back;							//tetrahedron at the back
 	vec3_t mins, maxs;					//triangle bounding box
 	struct th_triangle_s *prev, *next;	//links in linked triangle lists
 	struct th_triangle_s *hashnext;		//next triangle in hash
 } th_triangle_t;
 
 //tetrahedron
 typedef struct th_tetrahedron_s
 {
 	int triangles[4];					//negative if at backside of triangle
 	float volume;						//tetrahedron volume
 } th_tetrahedron_t;
 
 typedef struct th_s
 {
 	//vertexes
 	int numvertexes;
 	th_vertex_t *vertexes;
 	th_vertex_t *vertexhash[VERTEXHASH_SIZE * VERTEXHASH_SIZE];
 	//planes
 	int numplanes;
 	th_plane_t *planes;
 	th_plane_t *planehash[PLANEHASH_SIZE];
 	//edges
 	int numedges;
 	th_edge_t *edges;
 	th_edge_t *edgehash[EDGEHASH_SIZE];
 	//triangles
 	int numtriangles;
 	th_triangle_t *triangles;
 	th_triangle_t *trianglehash[TRIANGLEHASH_SIZE];
 	//tetrahedrons
 	int numtetrahedrons;
 	th_tetrahedron_t *tetrahedrons;
 } th_t;
 
 th_t thworld;
 
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 void TH_InitMaxTH(void)
 {
 	//get memory for the tetrahedron data
 	thworld.vertexes = (th_vertex_t *) GetClearedMemory(MAX_TH_VERTEXES * sizeof(th_vertex_t));
 	thworld.planes = (th_plane_t *) GetClearedMemory(MAX_TH_PLANES * sizeof(th_plane_t));
 	thworld.edges = (th_edge_t *) GetClearedMemory(MAX_TH_EDGES * sizeof(th_edge_t));
 	thworld.triangles = (th_triangle_t *) GetClearedMemory(MAX_TH_TRIANGLES * sizeof(th_triangle_t));
 	thworld.tetrahedrons = (th_tetrahedron_t *) GetClearedMemory(MAX_TH_TETRAHEDRONS * sizeof(th_tetrahedron_t));
 	//reset the hash tables
 	memset(thworld.vertexhash, 0, VERTEXHASH_SIZE * sizeof(th_vertex_t *));
 	memset(thworld.planehash, 0, PLANEHASH_SIZE * sizeof(th_plane_t *));
 	memset(thworld.edgehash, 0, EDGEHASH_SIZE * sizeof(th_edge_t *));
 	memset(thworld.trianglehash, 0, TRIANGLEHASH_SIZE * sizeof(th_triangle_t *));
 } //end of the function TH_InitMaxTH
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 void TH_FreeMaxTH(void)
 {
 	if (thworld.vertexes) FreeMemory(thworld.vertexes);
 	thworld.vertexes = NULL;
 	thworld.numvertexes = 0;
 	if (thworld.planes) FreeMemory(thworld.planes);
 	thworld.planes = NULL;
 	thworld.numplanes = 0;
 	if (thworld.edges) FreeMemory(thworld.edges);
 	thworld.edges = NULL;
 	thworld.numedges = 0;
 	if (thworld.triangles) FreeMemory(thworld.triangles);
 	thworld.triangles = NULL;
 	thworld.numtriangles = 0;
 	if (thworld.tetrahedrons) FreeMemory(thworld.tetrahedrons);
 	thworld.tetrahedrons = NULL;
 	thworld.numtetrahedrons = 0;
 } //end of the function TH_FreeMaxTH
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 float TH_TriangleArea(th_triangle_t *tri)
 {
 	return 0;
 } //end of the function TH_TriangleArea
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 float TH_TetrahedronVolume(th_tetrahedron_t *tetrahedron)
 {
 	int edgenum, verts[3], i, j, v2;
 	float volume, d;
 	th_triangle_t *tri, *tri2;
 	th_plane_t *plane;
 
 	tri = &thworld.triangles[abs(tetrahedron->triangles[0])];
 	for (i = 0; i < 3; i++)
 	{
 		edgenum = tri->edges[i];
 		if (edgenum < 0) verts[i] = thworld.edges[abs(edgenum)].v[1];
 		else verts[i] = thworld.edges[edgenum].v[0];
 	} //end for
 	//
 	tri2 = &thworld.triangles[abs(tetrahedron->triangles[1])];
 	for (j = 0; j < 3; j++)
 	{
 		edgenum = tri2->edges[i];
 		if (edgenum < 0) v2 = thworld.edges[abs(edgenum)].v[1];
 		else v2 = thworld.edges[edgenum].v[0];
 		if (v2 != verts[0] &&
 			v2 != verts[1] &&
 			v2 != verts[2]) break;
 	} //end for
 
 	plane = &thworld.planes[tri->planenum];
 	d = -(DotProduct (thworld.vertexes[v2].v, plane->normal) - plane->dist);
 	volume = TH_TriangleArea(tri) * d / 3;
 	return volume;
 } //end of the function TH_TetrahedronVolume
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 int TH_PlaneSignBits(vec3_t normal)
 {
 	int i, signbits;
 
 	signbits = 0;
 	for (i = 2; i >= 0; i--)
 	{
 		signbits = (signbits << 1) + Sign(normal[i]);
 	} //end for
 	return signbits;
 } //end of the function TH_PlaneSignBits
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 int TH_PlaneTypeForNormal(vec3_t normal)
 {
 	vec_t	ax, ay, az;
 	
 // NOTE: should these have an epsilon around 1.0?		
 	if (normal[0] == 1.0 || normal[0] == -1.0)
 		return PLANE_X;
 	if (normal[1] == 1.0 || normal[1] == -1.0)
 		return PLANE_Y;
 	if (normal[2] == 1.0 || normal[2] == -1.0)
 		return PLANE_Z;
 		
 	ax = fabs(normal[0]);
 	ay = fabs(normal[1]);
 	az = fabs(normal[2]);
 	
 	if (ax >= ay && ax >= az)
 		return PLANE_ANYX;
 	if (ay >= ax && ay >= az)
 		return PLANE_ANYY;
 	return PLANE_ANYZ;
 } //end of the function TH_PlaneTypeForNormal
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 qboolean TH_PlaneEqual(th_plane_t *p, vec3_t normal, vec_t dist)
 {
 	if (
 	   fabs(p->normal[0] - normal[0]) < NORMAL_EPSILON
 	&& fabs(p->normal[1] - normal[1]) < NORMAL_EPSILON
 	&& fabs(p->normal[2] - normal[2]) < NORMAL_EPSILON
 	&& fabs(p->dist - dist) < DIST_EPSILON )
 		return true;
 	return false;
 } //end of the function TH_PlaneEqual
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 void TH_AddPlaneToHash(th_plane_t *p)
 {
 	int hash;
 
 	hash = (int)fabs(p->dist) / 8;
 	hash &= (PLANEHASH_SIZE-1);
 
 	p->hashnext = thworld.planehash[hash];
 	thworld.planehash[hash] = p;
 } //end of the function TH_AddPlaneToHash
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 int TH_CreateFloatPlane(vec3_t normal, vec_t dist)
 {
 	th_plane_t *p, temp;
 
 	if (VectorLength(normal) < 0.5)
 		Error ("FloatPlane: bad normal");
 	// create a new plane
 	if (thworld.numplanes+2 > MAX_TH_PLANES)
 		Error ("MAX_TH_PLANES");
 
 	p = &thworld.planes[thworld.numplanes];
 	VectorCopy (normal, p->normal);
 	p->dist = dist;
 	p->type = (p+1)->type = TH_PlaneTypeForNormal (p->normal);
 	p->signbits = TH_PlaneSignBits(p->normal);
 
 	VectorSubtract (vec3_origin, normal, (p+1)->normal);
 	(p+1)->dist = -dist;
 	(p+1)->signbits = TH_PlaneSignBits((p+1)->normal);
 
 	thworld.numplanes += 2;
 
 	// allways put axial planes facing positive first
 	if (p->type < 3)
 	{
 		if (p->normal[0] < 0 || p->normal[1] < 0 || p->normal[2] < 0)
 		{
 			// flip order
 			temp = *p;
 			*p = *(p+1);
 			*(p+1) = temp;
 
 			TH_AddPlaneToHash(p);
 			TH_AddPlaneToHash(p+1);
 			return thworld.numplanes - 1;
 		} //end if
 	} //end if
 
 	TH_AddPlaneToHash(p);
 	TH_AddPlaneToHash(p+1);
 	return thworld.numplanes - 2;
 } //end of the function TH_CreateFloatPlane
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 void TH_SnapVector(vec3_t normal)
 {
 	int		i;
 
 	for (i = 0; i < 3; i++)
 	{
 		if ( fabs(normal[i] - 1) < NORMAL_EPSILON )
 		{
 			VectorClear (normal);
 			normal[i] = 1;
 			break;
 		} //end if
 		if ( fabs(normal[i] - -1) < NORMAL_EPSILON )
 		{
 			VectorClear (normal);
 			normal[i] = -1;
 			break;
 		} //end if
 	} //end for
 } //end of the function TH_SnapVector
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 void TH_SnapPlane(vec3_t normal, vec_t *dist)
 {
 	TH_SnapVector(normal);
 
 	if (fabs(*dist-Q_rint(*dist)) < DIST_EPSILON)
 		*dist = Q_rint(*dist);
 } //end of the function TH_SnapPlane
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 int TH_FindFloatPlane(vec3_t normal, vec_t dist)
 {
 	int i;
 	th_plane_t *p;
 	int hash, h;
 
 	TH_SnapPlane (normal, &dist);
 	hash = (int)fabs(dist) / 8;
 	hash &= (PLANEHASH_SIZE-1);
 
 	// search the border bins as well
 	for (i = -1; i <= 1; i++)
 	{
 		h = (hash+i)&(PLANEHASH_SIZE-1);
 		for (p = thworld.planehash[h]; p; p = p->hashnext)
 		{
 			if (TH_PlaneEqual(p, normal, dist))
 			{
 				return p - thworld.planes;
 			} //end if
 		} //end for
 	} //end for
 	return TH_CreateFloatPlane(normal, dist);
 } //end of the function TH_FindFloatPlane
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 int TH_PlaneFromPoints(int v1, int v2, int v3)
 {
 	vec3_t t1, t2, normal;
 	vec_t dist;
 	float *p0, *p1, *p2;
 
 	p0 = thworld.vertexes[v1].v;
 	p1 = thworld.vertexes[v2].v;
 	p2 = thworld.vertexes[v3].v;
 
 	VectorSubtract(p0, p1, t1);
 	VectorSubtract(p2, p1, t2);
 	CrossProduct(t1, t2, normal);
 	VectorNormalize(normal);
 
 	dist = DotProduct(p0, normal);
 
 	return TH_FindFloatPlane(normal, dist);
 } //end of the function TH_PlaneFromPoints
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 void TH_AddEdgeUser(int edgenum)
 {
 	th_edge_t *edge;
 
 	edge = &thworld.edges[abs(edgenum)];
 	//increase edge user count
 	edge->usercount++;
 	//increase vertex user count as well
 	thworld.vertexes[edge->v[0]].usercount++;
 	thworld.vertexes[edge->v[1]].usercount++;
 } //end of the function TH_AddEdgeUser
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 void TH_RemoveEdgeUser(int edgenum)
 {
 	th_edge_t *edge;
 
 	edge = &thworld.edges[abs(edgenum)];
 	//decrease edge user count
 	edge->usercount--;
 	//decrease vertex user count as well
 	thworld.vertexes[edge->v[0]].usercount--;
 	thworld.vertexes[edge->v[1]].usercount--;
 } //end of the function TH_RemoveEdgeUser
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 void TH_FreeTriangleEdges(th_triangle_t *tri)
 {
 	int i;
 
 	for (i = 0; i < 3; i++)
 	{
 		TH_RemoveEdgeUser(abs(tri->edges[i]));
 	} //end for
 } //end of the function TH_FreeTriangleEdges
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 unsigned TH_HashVec(vec3_t vec)
 {
 	int x, y;
 
 	x = (MAX_MAP_BOUNDS + (int)(vec[0]+0.5)) >> VERTEXHASH_SHIFT;
 	y = (MAX_MAP_BOUNDS + (int)(vec[1]+0.5)) >> VERTEXHASH_SHIFT;
 
 	if (x < 0 || x >= VERTEXHASH_SIZE || y < 0 || y >= VERTEXHASH_SIZE)
 		Error("HashVec: point %f %f %f outside valid range", vec[0], vec[1], vec[2]);
 	
 	return y*VERTEXHASH_SIZE + x;
 } //end of the function TH_HashVec
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 int TH_FindVertex(vec3_t v)
 {
 	int i, h;
 	th_vertex_t *vertex;
 	vec3_t vert;
 	
 	for (i = 0; i < 3; i++)
 	{
 		if ( fabs(v[i] - Q_rint(v[i])) < INTEGRAL_EPSILON)
 			vert[i] = Q_rint(v[i]);
 		else
 			vert[i] = v[i];
 	} //end for
 
 	h = TH_HashVec(vert);
 
 	for (vertex = thworld.vertexhash[h]; vertex; vertex = vertex->hashnext)
 	{
 		if (fabs(vertex->v[0] - vert[0]) < VERTEX_EPSILON &&
 			fabs(vertex->v[1] - vert[1]) < VERTEX_EPSILON &&
 			fabs(vertex->v[2] - vert[2]) < VERTEX_EPSILON)
 		{
 			return vertex - thworld.vertexes;
 		} //end if
 	} //end for
 	return 0;
 } //end of the function TH_FindVertex
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 void TH_AddVertexToHash(th_vertex_t *vertex)
 {
 	int hashvalue;
 
 	hashvalue = TH_HashVec(vertex->v);
 	vertex->hashnext = thworld.vertexhash[hashvalue];
 	thworld.vertexhash[hashvalue] = vertex;
 } //end of the function TH_AddVertexToHash
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 int TH_CreateVertex(vec3_t v)
 {
 	if (thworld.numvertexes == 0) thworld.numvertexes = 1;
 	if (thworld.numvertexes >= MAX_TH_VERTEXES)
 		Error("MAX_TH_VERTEXES");
 	VectorCopy(v, thworld.vertexes[thworld.numvertexes].v);
 	thworld.vertexes[thworld.numvertexes].usercount = 0;
 	TH_AddVertexToHash(&thworld.vertexes[thworld.numvertexes]);
 	thworld.numvertexes++;
 	return thworld.numvertexes-1;
 } //end of the function TH_CreateVertex
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 int TH_FindOrCreateVertex(vec3_t v)
 {
 	int vertexnum;
 
 	vertexnum = TH_FindVertex(v);
 	if (!vertexnum) vertexnum = TH_CreateVertex(v);
 	return vertexnum;
 } //end of the function TH_FindOrCreateVertex
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 int TH_FindEdge(int v1, int v2)
 {
 	int hashvalue;
 	th_edge_t *edge;
 
 	hashvalue = (v1 + v2) & (EDGEHASH_SIZE-1);
 
 	for (edge = thworld.edgehash[hashvalue]; edge; edge = edge->hashnext)
 	{
 		if (edge->v[0] == v1 && edge->v[1] == v2) return edge - thworld.edges;
 		if (edge->v[1] == v1 && edge->v[0] == v2) return -(edge - thworld.edges);
 	} //end for
 	return 0;
 } //end of the function TH_FindEdge
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 void TH_AddEdgeToHash(th_edge_t *edge)
 {
 	int hashvalue;
 
 	hashvalue = (edge->v[0] + edge->v[1]) & (EDGEHASH_SIZE-1);
 	edge->hashnext = thworld.edgehash[hashvalue];
 	thworld.edgehash[hashvalue] = edge;
 } //end of the function TH_AddEdgeToHash
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 int TH_CreateEdge(int v1, int v2)
 {
 	th_edge_t *edge;
 
 	if (thworld.numedges == 0) thworld.numedges = 1;
 	if (thworld.numedges >= MAX_TH_EDGES)
 		Error("MAX_TH_EDGES");
 	edge = &thworld.edges[thworld.numedges++];
 	edge->v[0] = v1;
 	edge->v[1] = v2;
 	TH_AddEdgeToHash(edge);
 	return thworld.numedges-1;
 } //end of the function TH_CreateEdge
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 int TH_FindOrCreateEdge(int v1, int v2)
 {
 	int edgenum;
 
 	edgenum = TH_FindEdge(v1, v2);
 	if (!edgenum) edgenum = TH_CreateEdge(v1, v2);
 	return edgenum;
 } //end of the function TH_FindOrCreateEdge
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 int TH_FindTriangle(int verts[3])
 {
 	int i, hashvalue, edges[3];
 	th_triangle_t *tri;
 
 	for (i = 0; i < 3; i++)
 	{
 		edges[i] = TH_FindEdge(verts[i], verts[(i+1)%3]);
 		if (!edges[i]) return false;
 	} //end for
 	hashvalue = (abs(edges[0]) + abs(edges[1]) + abs(edges[2])) & (TRIANGLEHASH_SIZE-1);
 	for (tri = thworld.trianglehash[hashvalue]; tri; tri = tri->next)
 	{
 		for (i = 0; i < 3; i++)
 		{
 			if (abs(tri->edges[i]) != abs(edges[0]) &&
 				abs(tri->edges[i]) != abs(edges[1]) &&
 				abs(tri->edges[i]) != abs(edges[2])) break;
 		} //end for
 		if (i >= 3) return tri - thworld.triangles;
 	} //end for
 	return 0;
 } //end of the function TH_FindTriangle
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 void TH_AddTriangleToHash(th_triangle_t *tri)
 {
 	int hashvalue;
 
 	hashvalue = (abs(tri->edges[0]) + abs(tri->edges[1]) + abs(tri->edges[2])) & (TRIANGLEHASH_SIZE-1);
 	tri->hashnext = thworld.trianglehash[hashvalue];
 	thworld.trianglehash[hashvalue] = tri;
 } //end of the function TH_AddTriangleToHash
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 void TH_CreateTrianglePlanes(int verts[3], th_plane_t *triplane, th_plane_t *planes)
 {
 	int i;
 	vec3_t dir;
 
 	for (i = 0; i < 3; i++)
 	{
 		VectorSubtract(thworld.vertexes[verts[(i+1)%3]].v, thworld.vertexes[verts[i]].v, dir);
 		CrossProduct(dir, triplane->normal, planes[i].normal);
 		VectorNormalize(planes[i].normal);
 		planes[i].dist = DotProduct(thworld.vertexes[verts[i]].v, planes[i].normal);
 	} //end for
 } //end of the function TH_CreateTrianglePlanes
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 int TH_CreateTriangle(int verts[3])
 {
 	th_triangle_t *tri;
 	int i;
 
 	if (thworld.numtriangles == 0) thworld.numtriangles = 1;
 	if (thworld.numtriangles >= MAX_TH_TRIANGLES)
 		Error("MAX_TH_TRIANGLES");
 	tri = &thworld.triangles[thworld.numtriangles++];
 	for (i = 0; i < 3; i++)
 	{
 		tri->edges[i] = TH_FindOrCreateEdge(verts[i], verts[(i+1)%3]);
 		TH_AddEdgeUser(abs(tri->edges[i]));
 	} //end for
 	tri->front = 0;
 	tri->back = 0;
 	tri->planenum = TH_PlaneFromPoints(verts[0], verts[1], verts[2]);
 	tri->prev = NULL;
 	tri->next = NULL;
 	tri->hashnext = NULL;
 	TH_CreateTrianglePlanes(verts, &thworld.planes[tri->planenum], tri->planes);
 	TH_AddTriangleToHash(tri);
 	ClearBounds(tri->mins, tri->maxs);
 	for (i = 0; i < 3; i++)
 	{
 		AddPointToBounds(thworld.vertexes[verts[i]].v, tri->mins, tri->maxs);
 	} //end for
 	return thworld.numtriangles-1;
 } //end of the function TH_CreateTriangle
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 int TH_CreateTetrahedron(int triangles[4])
 {
 	th_tetrahedron_t *tetrahedron;
 	int i;
 
 	if (thworld.numtetrahedrons == 0) thworld.numtetrahedrons = 1;
 	if (thworld.numtetrahedrons >= MAX_TH_TETRAHEDRONS)
 		Error("MAX_TH_TETRAHEDRONS");
 	tetrahedron = &thworld.tetrahedrons[thworld.numtetrahedrons++];
 	for (i = 0; i < 4; i++)
 	{
 		tetrahedron->triangles[i] = triangles[i];
 		if (thworld.triangles[abs(triangles[i])].front)
 		{
 			thworld.triangles[abs(triangles[i])].back = thworld.numtetrahedrons-1;
 		} //end if
 		else
 		{
 			thworld.triangles[abs(triangles[i])].front = thworld.numtetrahedrons-1;
 		} //end else
 	} //end for
 	tetrahedron->volume = 0;
 	return thworld.numtetrahedrons-1;
 } //end of the function TH_CreateTetrahedron
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 int TH_IntersectTrianglePlanes(int v1, int v2, th_plane_t *triplane, th_plane_t *planes)
 {
 	float *p1, *p2, front, back, frac, d;
 	int i, side, lastside;
 	vec3_t mid;
 
 	p1 = thworld.vertexes[v1].v;
 	p2 = thworld.vertexes[v2].v;
 
 	front = DotProduct(p1, triplane->normal) - triplane->dist;
 	back = DotProduct(p2, triplane->normal) - triplane->dist;
 	//if both points at the same side of the plane
 	if (front < 0.1 && back < 0.1) return false;
 	if (front > -0.1 && back > -0.1) return false;
 	//
 	frac = front/(front-back);
 	mid[0] = p1[0] + (p2[0] - p1[0]) * frac;
 	mid[1] = p1[1] + (p2[1] - p1[1]) * frac;
 	mid[2] = p1[2] + (p2[2] - p1[2]) * frac;
 	//if the mid point is at the same side of all the tri bounding planes
 	lastside = 0;
 	for (i = 0; i < 3; i++)
 	{
 		d = DotProduct(mid, planes[i].normal) - planes[i].dist;
 		side = d < 0;
 		if (i && side != lastside) return false;
 		lastside = side;
 	} //end for
 	return true;
 } //end of the function TH_IntersectTrianglePlanes
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 int TH_OutsideBoundingBox(int v1, int v2, vec3_t mins, vec3_t maxs)
 {
 	float *p1, *p2;
 	int i;
 
 	p1 = thworld.vertexes[v1].v;
 	p2 = thworld.vertexes[v2].v;
 	//if both points are at the outer side of one of the bounding box planes
 	for (i = 0; i < 3; i++)
 	{
 		if (p1[i] < mins[i] && p2[i] < mins[i]) return true;
 		if (p1[i] > maxs[i] && p2[i] > maxs[i]) return true;
 	} //end for
 	return false;
 } //end of the function TH_OutsideBoundingBox
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 int TH_TryEdge(int v1, int v2)
 {
 	int i, j, v;
 	th_plane_t *plane;
 	th_triangle_t *tri;
 
 	//if the edge already exists it must be valid
 	if (TH_FindEdge(v1, v2)) return true;
 	//test the edge with all existing triangles
 	for (i = 1; i < thworld.numtriangles; i++)
 	{
 		tri = &thworld.triangles[i];
 		//if triangle is enclosed by two tetrahedrons we don't have to test it
 		//because the edge always has to go through another triangle of those
 		//tetrahedrons first to reach the enclosed triangle
 		if (tri->front && tri->back) continue;
 		//if the edges is totally outside the triangle bounding box
 		if (TH_OutsideBoundingBox(v1, v2, tri->mins, tri->maxs)) continue;
 		//if one of the edge vertexes is used by this triangle
 		for (j = 0; j < 3; j++)
 		{
 			v = thworld.edges[abs(tri->edges[j])].v[tri->edges[j] < 0];
 			if (v == v1 || v == v2) break;
 		} //end for
 		if (j < 3) continue;
 		//get the triangle plane
 		plane = &thworld.planes[tri->planenum];
 		//if the edge intersects with a triangle then it's not valid
 		if (TH_IntersectTrianglePlanes(v1, v2, plane, tri->planes)) return false;
 	} //end for
 	return true;
 } //end of the function TH_TryEdge
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 int TH_TryTriangle(int verts[3])
 {
 	th_plane_t planes[3], triplane;
 	vec3_t t1, t2;
 	float *p0, *p1, *p2;
 	int i, j;
 
 	p0 = thworld.vertexes[verts[0]].v;
 	p1 = thworld.vertexes[verts[1]].v;
 	p2 = thworld.vertexes[verts[2]].v;
 
 	VectorSubtract(p0, p1, t1);
 	VectorSubtract(p2, p1, t2);
 	CrossProduct(t1, t2, triplane.normal);
 	VectorNormalize(triplane.normal);
 	triplane.dist = DotProduct(p0, triplane.normal);
 	//
 	TH_CreateTrianglePlanes(verts, &triplane, planes);
 	//test if any existing edge intersects with this triangle
 	for (i = 1; i < thworld.numedges; i++)
 	{
 		//if the edge is only used by triangles with tetrahedrons at both sides
 		if (!thworld.edges[i].usercount) continue;
 		//if one of the triangle vertexes is used by this edge
 		for (j = 0; j < 3; j++)
 		{
 			if (verts[j] == thworld.edges[j].v[0] ||
 				verts[j] == thworld.edges[j].v[1]) break;
 		} //end for
 		if (j < 3) continue;
 		//if this edge intersects with the triangle
 		if (TH_IntersectTrianglePlanes(thworld.edges[i].v[0], thworld.edges[i].v[1], &triplane, planes)) return false;
 	} //end for
 	return true;
 } //end of the function TH_TryTriangle
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 void TH_AddTriangleToList(th_triangle_t **trianglelist, th_triangle_t *tri)
 {
 	tri->prev = NULL;
 	tri->next = *trianglelist;
 	if (*trianglelist) (*trianglelist)->prev = tri;
 	*trianglelist = tri;
 } //end of the function TH_AddTriangleToList
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 void TH_RemoveTriangleFromList(th_triangle_t **trianglelist, th_triangle_t *tri)
 {
 	if (tri->next) tri->next->prev = tri->prev;
 	if (tri->prev) tri->prev->next = tri->next;
 	else *trianglelist = tri->next;
 } //end of the function TH_RemoveTriangleFromList
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 int TH_FindTetrahedron1(th_triangle_t *tri, int *triangles)
 {
 	int i, j, edgenum, side, v1, v2, v3, v4;
 	int verts1[3], verts2[3];
 	th_triangle_t *tri2;
 
 	//find another triangle with a shared edge
 	for (tri2 = tri->next; tri2; tri2 = tri2->next)
 	{
 		//if the triangles are in the same plane
 		if ((tri->planenum & ~1) == (tri2->planenum & ~1)) continue;
 		//try to find a shared edge
 		for (i = 0; i < 3; i++)
 		{
 			edgenum = abs(tri->edges[i]);
 			for (j = 0; j < 3; j++)
 			{
 				if (edgenum == abs(tri2->edges[j])) break;
 			} //end for
 			if (j < 3) break;
 		} //end for
 		//if the triangles have a shared edge
 		if (i < 3)
 		{
 			edgenum = tri->edges[(i+1)%3];
 			if (edgenum < 0) v1 = thworld.edges[abs(edgenum)].v[0];
 			else v1 = thworld.edges[edgenum].v[1];
 			edgenum = tri2->edges[(j+1)%3];
 			if (edgenum < 0) v2 = thworld.edges[abs(edgenum)].v[0];
 			else v2 = thworld.edges[edgenum].v[1];
 			//try the new edge
 			if (TH_TryEdge(v1, v2))
 			{
 				edgenum = tri->edges[i];
 				side = edgenum < 0;
 				//get the vertexes of the shared edge
 				v3 = thworld.edges[abs(edgenum)].v[side];
 				v4 = thworld.edges[abs(edgenum)].v[!side];
 				//try the two new triangles
 				verts1[0] = v1;
 				verts1[1] = v2;
 				verts1[2] = v3;
 				triangles[2] = TH_FindTriangle(verts1);
 				if (triangles[2] || TH_TryTriangle(verts1))
 				{
 					verts2[0] = v2;
 					verts2[1] = v1;
 					verts2[2] = v4;
 					triangles[3] = TH_FindTriangle(verts2);
 					if (triangles[3] || TH_TryTriangle(verts2))
 					{
 						triangles[0] = tri - thworld.triangles;
 						triangles[1] = tri2 - thworld.triangles;
 						if (!triangles[2]) triangles[2] = TH_CreateTriangle(verts1);
 						if (!triangles[3]) triangles[3] = TH_CreateTriangle(verts2);
 						return true;
 					} //end if
 				} //end if
 			} //end if
 		} //end if
 	} //end for
 	return false;
 } //end of the function TH_FindTetrahedron
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 int TH_FindTetrahedron2(th_triangle_t *tri, int *triangles)
 {
 	int i, edgenum, v1, verts[3], triverts[3];
 	float d;
 	th_plane_t *plane;
 
 	//get the verts of this triangle
 	for (i = 0; i < 3; i++)
 	{
 		edgenum = tri->edges[i];
 		if (edgenum < 0) verts[i] = thworld.edges[abs(edgenum)].v[1];
 		else verts[i] = thworld.edges[edgenum].v[0];
 	} //end for
 	//
 	plane = &thworld.planes[tri->planenum];
 	for (v1 = 0; v1 < thworld.numvertexes; v1++)
 	{
 		//if the vertex is only used by triangles with tetrahedrons at both sides
 		if (!thworld.vertexes[v1].usercount) continue;
 		//check if the vertex is not coplanar with the triangle
 		d = DotProduct(thworld.vertexes[v1].v, plane->normal) - plane->dist;
 		if (fabs(d) < 1) continue;
 		//check if we can create edges from the triangle towards this new vertex
 		for (i = 0; i < 3; i++)
 		{
 			if (v1 == verts[i]) break;
 			if (!TH_TryEdge(v1, verts[i])) break;
 		} //end for
 		if (i < 3) continue;
 		//check if the triangles are valid
 		for (i = 0; i < 3; i++)
 		{
 			triverts[0] = v1;
 			triverts[1] = verts[i];
 			triverts[2] = verts[(i+1)%3];
 			//if the triangle already exists then it is valid
 			triangles[i] = TH_FindTriangle(triverts);
 			if (!triangles[i])
 			{
 				if (!TH_TryTriangle(triverts)) break;
 			} //end if
 		} //end for
 		if (i < 3) continue;
 		//create the tetrahedron triangles using the new vertex
 		for (i = 0; i < 3; i++)
 		{
 			if (!triangles[i])
 			{
 				triverts[0] = v1;
 				triverts[1] = verts[i];
 				triverts[2] = verts[(i+1)%3];
 				triangles[i] = TH_CreateTriangle(triverts);
 			} //end if
 		} //end for
 		//add the existing triangle
 		triangles[3] = tri - thworld.triangles;
 		//
 		return true;
 	} //end for
 	return false;
 } //end of the function TH_FindTetrahedron2
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 void TH_TetrahedralDecomposition(th_triangle_t *triangles)
 {
 	int i, thtriangles[4], numtriangles;
 	th_triangle_t *donetriangles, *tri;
 
 	donetriangles = NULL;
 
 	/*
 	numtriangles = 0;
 	qprintf("%6d triangles", numtriangles);
 	for (tri = triangles; tri; tri = triangles)
 	{
 		qprintf("\r%6d", numtriangles++);
 		if (!TH_FindTetrahedron1(tri, thtriangles))
 		{
 //			if (!TH_FindTetrahedron2(tri, thtriangles))
 			{
 //				Error("triangle without tetrahedron");
 				TH_RemoveTriangleFromList(&triangles, tri);
 				continue;
 			} //end if
 		} //end if
 		//create a tetrahedron from the triangles
 		TH_CreateTetrahedron(thtriangles);
 		//
 		for (i = 0; i < 4; i++)
 		{
 			if (thworld.triangles[abs(thtriangles[i])].front &&
 				thworld.triangles[abs(thtriangles[i])].back)
 			{
 				TH_RemoveTriangleFromList(&triangles, &thworld.triangles[abs(thtriangles[i])]);
 				TH_AddTriangleToList(&donetriangles, &thworld.triangles[abs(thtriangles[i])]);
 				TH_FreeTriangleEdges(&thworld.triangles[abs(thtriangles[i])]);
 			} //end if
 			else
 			{
 				TH_AddTriangleToList(&triangles, &thworld.triangles[abs(thtriangles[i])]);
 			} //end else
 		} //end for
 	} //end for*/
 	qprintf("%6d tetrahedrons", thworld.numtetrahedrons);
 	do
 	{
 		do
 		{
 			numtriangles = 0;
 			for (i = 1; i < thworld.numtriangles; i++)
 			{
 				tri = &thworld.triangles[i];
 				if (tri->front && tri->back) continue;
 				//qprintf("\r%6d", numtriangles++);
 				if (!TH_FindTetrahedron1(tri, thtriangles))
 				{
 //					if (!TH_FindTetrahedron2(tri, thtriangles))
 					{
 						continue;
 					} //end if
 				} //end if
 				numtriangles++;
 				//create a tetrahedron from the triangles
 				TH_CreateTetrahedron(thtriangles);
 				qprintf("\r%6d", thworld.numtetrahedrons);
 			} //end for
 		} while(numtriangles);
  		for (i = 1; i < thworld.numtriangles; i++)
 		{
 			tri = &thworld.triangles[i];
 			if (tri->front && tri->back) continue;
 			//qprintf("\r%6d", numtriangles++);
 //			if (!TH_FindTetrahedron1(tri, thtriangles))
 			{
 				if (!TH_FindTetrahedron2(tri, thtriangles))
 				{
 					continue;
 				} //end if
 			} //end if
 			numtriangles++;
 			//create a tetrahedron from the triangles
 			TH_CreateTetrahedron(thtriangles);
 			qprintf("\r%6d", thworld.numtetrahedrons);
 		} //end for
 	} while(numtriangles);
 	//
 	numtriangles = 0;
 	for (i = 1; i < thworld.numtriangles; i++)
 	{
 		tri = &thworld.triangles[i];
 		if (!tri->front && !tri->back) numtriangles++;
 	} //end for
 	Log_Print("\r%6d triangles with front only\n", numtriangles);
 	Log_Print("\r%6d tetrahedrons\n", thworld.numtetrahedrons-1);
 } //end of the function TH_TetrahedralDecomposition
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 void TH_AASFaceVertex(aas_face_t *face, int index, vec3_t vertex)
 {
 	int edgenum, side;
 
 	edgenum = aasworld.edgeindex[face->firstedge + index];
 	side = edgenum < 0;
 	VectorCopy(aasworld.vertexes[aasworld.edges[abs(edgenum)].v[side]], vertex);
 } //end of the function TH_AASFaceVertex
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 int TH_Colinear(float *v0, float *v1, float *v2)
 {
 	vec3_t t1, t2, vcross;
 	float d;
 	
 	VectorSubtract(v1, v0, t1);
 	VectorSubtract(v2, v0, t2);
 	CrossProduct (t1, t2, vcross);
 	d = VectorLength( vcross );
 
 	// if cross product is zero point is colinear
 	if (d < 10)
 	{
 		return true;
 	} //end if
 	return false;
 } //end of the function TH_Colinear
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 void TH_FaceCenter(aas_face_t *face, vec3_t center)
 {
 	int i, edgenum, side;
 	aas_edge_t *edge;
 
 	VectorClear(center);
 	for (i = 0; i < face->numedges; i++)
 	{
 		edgenum = abs(aasworld.edgeindex[face->firstedge + i]);
 		side = edgenum < 0;
 		edge = &aasworld.edges[abs(edgenum)];
 		VectorAdd(aasworld.vertexes[edge->v[side]], center, center);
 	} //end for
 	VectorScale(center, 1.0 / face->numedges, center);
 } //end of the function TH_FaceCenter
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 th_triangle_t *TH_CreateAASFaceTriangles(aas_face_t *face)
 {
 	int i, first, verts[3], trinum;
 	vec3_t p0, p1, p2, p3, p4, center;
 	th_triangle_t *tri, *triangles;
 
 	triangles = NULL;
 	//find three points that are not colinear
 	for (i = 0; i < face->numedges; i++)
 	{
 		TH_AASFaceVertex(face, (face->numedges + i-2)%face->numedges, p0);
 		TH_AASFaceVertex(face, (face->numedges + i-1)%face->numedges, p1);
 		TH_AASFaceVertex(face, (i  )%face->numedges, p2);
 		if (TH_Colinear(p2, p0, p1)) continue;
 		TH_AASFaceVertex(face, (i+1)%face->numedges, p3);
 		TH_AASFaceVertex(face, (i+2)%face->numedges, p4);
 		if (TH_Colinear(p2, p3, p4)) continue;
 		break;
 	} //end for
 	//if there are three points that are not colinear
 	if (i < face->numedges)
 	{
 		//normal triangulation
 		first = i; //left and right most point of three non-colinear points
 		TH_AASFaceVertex(face, first, p0);
 		verts[0] = TH_FindOrCreateVertex(p0);
 		for (i = 1; i < face->numedges-1; i++)
 		{
 			TH_AASFaceVertex(face, (first+i  )%face->numedges, p1);
 			TH_AASFaceVertex(face, (first+i+1)%face->numedges, p2);
 			verts[1] = TH_FindOrCreateVertex(p1);
 			verts[2] = TH_FindOrCreateVertex(p2);
 			trinum = TH_CreateTriangle(verts);
 			tri = &thworld.triangles[trinum];
 			tri->front = -1;
 			TH_AddTriangleToList(&triangles, tri);
 		} //end for
 	} //end if
 	else
 	{
 		//fan triangulation
 		TH_FaceCenter(face, center);
 		//
 		verts[0] = TH_FindOrCreateVertex(center);
 		for (i = 0; i < face->numedges; i++)
 		{
 			TH_AASFaceVertex(face, (i  )%face->numedges, p1);
 			TH_AASFaceVertex(face, (i+1)%face->numedges, p2);
 			if (TH_Colinear(center, p1, p2)) continue;
 			verts[1] = TH_FindOrCreateVertex(p1);
 			verts[2] = TH_FindOrCreateVertex(p2);
 			trinum = TH_CreateTriangle(verts);
 			tri = &thworld.triangles[trinum];
 			tri->front = -1;
 			TH_AddTriangleToList(&triangles, tri);
 		} //end for
 	} //end else
 	return triangles;
 } //end of the function TH_CreateAASFaceTriangles
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 th_triangle_t *TH_AASToTriangleMesh(void)
 {
 	int i, j, facenum, otherareanum;
 	aas_face_t *face;
 	th_triangle_t *tri, *nexttri, *triangles;
 
 	triangles = NULL;
 	for (i = 1; i < aasworld.numareas; i++)
 	{
 		//if (!(aasworld.areasettings[i].presencetype & PRESENCE_NORMAL)) continue;
 		for (j = 0; j < aasworld.areas[i].numfaces; j++)
 		{
 			facenum = abs(aasworld.faceindex[aasworld.areas[i].firstface + j]);
 			face = &aasworld.faces[facenum];
 			//only convert solid faces into triangles
 			if (!(face->faceflags & FACE_SOLID))
 			{
 				/*
 				if (face->frontarea == i) otherareanum = face->backarea;
 				else otherareanum = face->frontarea;
 				if (aasworld.areasettings[otherareanum].presencetype & PRESENCE_NORMAL) continue;
 				*/
 				continue;
 			} //end if
 			//
 			tri = TH_CreateAASFaceTriangles(face);
 			for (; tri; tri = nexttri)
 			{
 				nexttri = tri->next;
 				TH_AddTriangleToList(&triangles, tri);
 			} //end for
 		} //end if
 	} //end for
 	return triangles;
 } //end of the function TH_AASToTriangleMesh
 //===========================================================================
 //
 // Parameter:			-
 // Returns:				-
 // Changes Globals:		-
 //===========================================================================
 void TH_AASToTetrahedrons(char *filename)
 {
 	th_triangle_t *triangles, *tri, *lasttri;
 	int cnt;
 
 	if (!AAS_LoadAASFile(filename, 0, 0))
 		Error("couldn't load %s\n", filename);
 
 	//
 	TH_InitMaxTH();
 	//create a triangle mesh from the solid faces in the AAS file
 	triangles = TH_AASToTriangleMesh();
 	//
 	cnt = 0;
 	lasttri = NULL;
 	for (tri = triangles; tri; tri = tri->next)
 	{
 		cnt++;
 		if (tri->prev != lasttri) Log_Print("BAH\n");
 		lasttri = tri;
 	} //end for
 	Log_Print("%6d triangles\n", cnt);
 	//create a tetrahedral decomposition of the world bounded by triangles
 	TH_TetrahedralDecomposition(triangles);
 	//
 	TH_FreeMaxTH();
 } //end of the function TH_AASToTetrahedrons