tetrahedron.c

quakeIII源码这个不用我多说吧

/*
===========================================================================
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:		-
//===========================================================================