tetrahedron.c

quakeIII源码这个不用我多说吧

		//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