aas_gsubdiv.c

quakeIII源码这个不用我多说吧

	int foundsplitter, facesplits, groundsplits, epsilonfaces, bestepsilonfaces;
	float bestvalue, value;
	tmp_face_t *face1, *face2;
	vec3_t tmpnormal, invgravity;
	float tmpdist;

	//get inverse of gravity direction
	VectorCopy(cfg.phys_gravitydirection, invgravity);
	VectorInverse(invgravity);

	foundsplitter = false;
	bestvalue = -999999;
	bestepsilonfaces = 0;
	//
#ifdef AW_DEBUG
	Log_Print("finding split plane for area %d\n", tmparea->areanum);
#endif //AW_DEBUG
	for (face1 = tmparea->tmpfaces; face1; face1 = face1->next[side1])
	{
		//side of the face the area is on
		side1 = face1->frontarea != tmparea;
		//
		if (WindingIsTiny(face1->winding))
		{
			Log_Write("gsubdiv: area %d has a tiny winding\r\n", tmparea->areanum);
			continue;
		} //end if
		//if the face isn't a gap or ground there's no split edge
		if (!(face1->faceflags & FACE_GROUND) && !AAS_GapFace(face1, side1)) continue;
		//
		for (face2 = face1->next[side1]; face2; face2 = face2->next[side2])
		{
			//side of the face the area is on
			side2 = face2->frontarea != tmparea;
			//
			if (WindingIsTiny(face1->winding))
			{
				Log_Write("gsubdiv: area %d has a tiny winding\r\n", tmparea->areanum);
				continue;
			} //end if
			//if the face isn't a gap or ground there's no split edge
			if (!(face2->faceflags & FACE_GROUND) && !AAS_GapFace(face2, side2)) continue;
			//only split between gaps and ground
			if (!(((face1->faceflags & FACE_GROUND) && AAS_GapFace(face2, side2)) ||
					((face2->faceflags & FACE_GROUND) && AAS_GapFace(face1, side1)))) continue;
			//find a plane seperating the windings of the faces
			if (!FindPlaneSeperatingWindings(face1->winding, face2->winding, invgravity,
														tmpnormal, &tmpdist)) continue;
#ifdef AW_DEBUG
			Log_Print("normal = \'%f %f %f\', dist = %f\n",
							tmpnormal[0], tmpnormal[1], tmpnormal[2], tmpdist);
#endif //AW_DEBUG
			//get metrics for this vertical plane
			if (!AAS_TestSplitPlane(tmparea, tmpnormal, tmpdist,
										&facesplits, &groundsplits, &epsilonfaces))
			{
				continue;
			} //end if
#ifdef AW_DEBUG
			Log_Print("face splits = %d\nground splits = %d\n",
							facesplits, groundsplits);
#endif //AW_DEBUG
			value = 100 - facesplits - 2 * groundsplits;
			//avoid epsilon faces
			value += epsilonfaces * -1000;
			if (value > bestvalue)
			{
				VectorCopy(tmpnormal, normal);
				*dist = tmpdist;
				bestvalue = value;
				bestepsilonfaces = epsilonfaces;
				foundsplitter = true;
			} //end if
		} //end for
	} //end for
	if (bestepsilonfaces)
	{
		Log_Write("found %d epsilon faces trying to split area %d\r\n",
									epsilonfaces, tmparea->areanum);
	} //end else
	return foundsplitter;
} //end of the function AAS_FindBestAreaSplitPlane
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
tmp_node_t *AAS_SubdivideArea_r(tmp_node_t *tmpnode)
{
	int planenum;
	tmp_area_t *frontarea, *backarea;
	tmp_node_t *tmpnode1, *tmpnode2;
	vec3_t normal;
	float dist;

	if (AAS_FindBestAreaSplitPlane(tmpnode->tmparea, normal, &dist))
	{
		qprintf("\r%6d", ++numgravitationalsubdivisions);
		//
		planenum = FindFloatPlane(normal, dist);
		//split the area
		AAS_SplitArea(tmpnode->tmparea, planenum, &frontarea, &backarea);
		//
		tmpnode->tmparea = NULL;
		tmpnode->planenum = FindFloatPlane(normal, dist);
		//
		tmpnode1 = AAS_AllocTmpNode();
		tmpnode1->planenum = 0;
		tmpnode1->tmparea = frontarea;
		//
		tmpnode2 = AAS_AllocTmpNode();
		tmpnode2->planenum = 0;
		tmpnode2->tmparea = backarea;
		//subdivide the areas created by splitting recursively
		tmpnode->children[0] = AAS_SubdivideArea_r(tmpnode1);
		tmpnode->children[1] = AAS_SubdivideArea_r(tmpnode2);
	} //end if
	return tmpnode;
} //end of the function AAS_SubdivideArea_r
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
tmp_node_t *AAS_GravitationalSubdivision_r(tmp_node_t *tmpnode)
{
	//if this is a solid leaf
	if (!tmpnode) return NULL;
	//negative so it's an area
	if (tmpnode->tmparea) return AAS_SubdivideArea_r(tmpnode);
	//do the children recursively
	tmpnode->children[0] = AAS_GravitationalSubdivision_r(tmpnode->children[0]);
	tmpnode->children[1] = AAS_GravitationalSubdivision_r(tmpnode->children[1]);
	return tmpnode;
} //end of the function AAS_GravitationalSubdivision_r
//===========================================================================
// NOTE: merge faces and melt edges first
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_GravitationalSubdivision(void)
{
	Log_Write("AAS_GravitationalSubdivision\r\n");
	numgravitationalsubdivisions = 0;
	qprintf("%6i gravitational subdivisions", numgravitationalsubdivisions);
	//start with the head node
	AAS_GravitationalSubdivision_r(tmpaasworld.nodes);
	qprintf("\n");
	Log_Write("%6i gravitational subdivisions\r\n", numgravitationalsubdivisions);
} //end of the function AAS_GravitationalSubdivision
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
tmp_node_t *AAS_RefreshLadderSubdividedTree_r(tmp_node_t *tmpnode, tmp_area_t *tmparea,
												  tmp_node_t *tmpnode1, tmp_node_t *tmpnode2, int planenum)
{
	//if this is a solid leaf
	if (!tmpnode) return NULL;
	//negative so it's an area
	if (tmpnode->tmparea)
	{
		if (tmpnode->tmparea == tmparea)
		{
			tmpnode->tmparea = NULL;
			tmpnode->planenum = planenum;
			tmpnode->children[0] = tmpnode1;
			tmpnode->children[1] = tmpnode2;
		} //end if
		return tmpnode;
	} //end if
	//do the children recursively
	tmpnode->children[0] = AAS_RefreshLadderSubdividedTree_r(tmpnode->children[0],
									tmparea, tmpnode1, tmpnode2, planenum);
	tmpnode->children[1] = AAS_RefreshLadderSubdividedTree_r(tmpnode->children[1],
									tmparea, tmpnode1, tmpnode2, planenum);
	return tmpnode;
} //end of the function AAS_RefreshLadderSubdividedTree_r
//===========================================================================
// find an area with ladder faces and ground faces that are not connected
// split the area with a horizontal plane at the lowest vertex of all
// ladder faces in the area
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
tmp_node_t *AAS_LadderSubdivideArea_r(tmp_node_t *tmpnode)
{
	int side1, i, planenum;
	int foundladderface, foundgroundface;
	float dist;
	tmp_area_t *tmparea, *frontarea, *backarea;
	tmp_face_t *face1;
	tmp_node_t *tmpnode1, *tmpnode2;
	vec3_t lowestpoint, normal = {0, 0, 1};
	plane_t *plane;
	winding_t *w;

	tmparea = tmpnode->tmparea;
	//skip areas with a liquid
	if (tmparea->contents & (AREACONTENTS_WATER
									| AREACONTENTS_LAVA
									| AREACONTENTS_SLIME)) return tmpnode;
	//must be possible to stand in the area
	if (!(tmparea->presencetype & PRESENCE_NORMAL)) return tmpnode;
	//
	foundladderface = false;
	foundgroundface = false;
	lowestpoint[2] = 99999;
	//
	for (face1 = tmparea->tmpfaces; face1; face1 = face1->next[side1])
	{
		//side of the face the area is on
		side1 = face1->frontarea != tmparea;
		//if the face is a ladder face
		if (face1->faceflags & FACE_LADDER)
		{
			plane = &mapplanes[face1->planenum];
			//the ladder face plane should be pretty much vertical
			if (DotProduct(plane->normal, normal) > -0.1)
			{
				foundladderface = true;
				//find lowest point
				for (i = 0; i < face1->winding->numpoints; i++)
				{
					if (face1->winding->p[i][2] < lowestpoint[2])
					{
						VectorCopy(face1->winding->p[i], lowestpoint);
					} //end if
				} //end for
			} //end if
		} //end if
		else if (face1->faceflags & FACE_GROUND)
		{
			foundgroundface = true;
		} //end else if
	} //end for
	//
	if ((!foundladderface) || (!foundgroundface)) return tmpnode;
	//
	for (face1 = tmparea->tmpfaces; face1; face1 = face1->next[side1])
	{
		//side of the face the area is on
		side1 = face1->frontarea != tmparea;
		//if the face isn't a ground face
		if (!(face1->faceflags & FACE_GROUND)) continue;
		//the ground plane
		plane = &mapplanes[face1->planenum];
		//get the difference between the ground plane and the lowest point
		dist = DotProduct(plane->normal, lowestpoint) - plane->dist;
		//if the lowest point is very near one of the ground planes
		if (dist > -1 && dist < 1)
		{
			return tmpnode;
		} //end if
	} //end for
	//
	dist = DotProduct(normal, lowestpoint);
	planenum = FindFloatPlane(normal, dist);
	//
	w = AAS_SplitWinding(tmparea, planenum);
	if (!w) return tmpnode;
	FreeWinding(w);
	//split the area with a horizontal plane through the lowest point
	qprintf("\r%6d", ++numladdersubdivisions);
	//
	AAS_SplitArea(tmparea, planenum, &frontarea, &backarea);
	//
	tmpnode->tmparea = NULL;
	tmpnode->planenum = planenum;
	//
	tmpnode1 = AAS_AllocTmpNode();
	tmpnode1->planenum = 0;
	tmpnode1->tmparea = frontarea;
	//
	tmpnode2 = AAS_AllocTmpNode();
	tmpnode2->planenum = 0;
	tmpnode2->tmparea = backarea;
	//subdivide the areas created by splitting recursively
	tmpnode->children[0] = AAS_LadderSubdivideArea_r(tmpnode1);
	tmpnode->children[1] = AAS_LadderSubdivideArea_r(tmpnode2);
	//refresh the tree
	AAS_RefreshLadderSubdividedTree_r(tmpaasworld.nodes, tmparea, tmpnode1, tmpnode2, planenum);
	//
	return tmpnode;
} //end of the function AAS_LadderSubdivideArea_r
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
tmp_node_t *AAS_LadderSubdivision_r(tmp_node_t *tmpnode)
{
	//if this is a solid leaf
	if (!tmpnode) return 0;
	//negative so it's an area
	if (tmpnode->tmparea) return AAS_LadderSubdivideArea_r(tmpnode);
	//do the children recursively
	tmpnode->children[0] = AAS_LadderSubdivision_r(tmpnode->children[0]);
	tmpnode->children[1] = AAS_LadderSubdivision_r(tmpnode->children[1]);
	return tmpnode;
} //end of the function AAS_LadderSubdivision_r
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_LadderSubdivision(void)
{
	Log_Write("AAS_LadderSubdivision\r\n");
	numladdersubdivisions = 0;
	qprintf("%6i ladder subdivisions", numladdersubdivisions);
	//start with the head node
	AAS_LadderSubdivision_r(tmpaasworld.nodes);
	//
	qprintf("\n");
	Log_Write("%6i ladder subdivisions\r\n", numladdersubdivisions);
} //end of the function AAS_LadderSubdivision