tetrahedron.c

quakeIII源码这个不用我多说吧

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;