aas_create.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 "../botlib/aasfile.h"
#include "aas_create.h"
#include "aas_store.h"
#include "aas_gsubdiv.h"
#include "aas_facemerging.h"
#include "aas_areamerging.h"
#include "aas_edgemelting.h"
#include "aas_prunenodes.h"
#include "aas_cfg.h"
#include "../game/surfaceflags.h"

//#define AW_DEBUG
//#define L_DEBUG

#define AREAONFACESIDE(face, area)		(face->frontarea != area)

tmp_aas_t tmpaasworld;

//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_InitTmpAAS(void)
{
	//tmp faces
	tmpaasworld.numfaces = 0;
	tmpaasworld.facenum = 0;
	tmpaasworld.faces = NULL;
	//tmp convex areas
	tmpaasworld.numareas = 0;
	tmpaasworld.areanum = 0;
	tmpaasworld.areas = NULL;
	//tmp nodes
	tmpaasworld.numnodes = 0;
	tmpaasworld.nodes = NULL;
	//
	tmpaasworld.nodebuffer = NULL;
} //end of the function AAS_InitTmpAAS
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_FreeTmpAAS(void)
{
	tmp_face_t *f, *nextf;
	tmp_area_t *a, *nexta;
	tmp_nodebuf_t *nb, *nextnb;

	//free all the faces
	for (f = tmpaasworld.faces; f; f = nextf)
	{
		nextf = f->l_next;
		if (f->winding) FreeWinding(f->winding);
		FreeMemory(f);
	} //end if
	//free all tmp areas
	for (a = tmpaasworld.areas; a; a = nexta)
	{
		nexta = a->l_next;
		if (a->settings) FreeMemory(a->settings);
		FreeMemory(a);
	} //end for
	//free all the tmp nodes
	for (nb = tmpaasworld.nodebuffer; nb; nb = nextnb)
	{
		nextnb = nb->next;
		FreeMemory(nb);
	} //end for
} //end of the function AAS_FreeTmpAAS
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
tmp_face_t *AAS_AllocTmpFace(void)
{
	tmp_face_t *tmpface;

	tmpface = (tmp_face_t *) GetClearedMemory(sizeof(tmp_face_t));
	tmpface->num = tmpaasworld.facenum++;
	tmpface->l_prev = NULL;
	tmpface->l_next = tmpaasworld.faces;
	if (tmpaasworld.faces) tmpaasworld.faces->l_prev = tmpface;
	tmpaasworld.faces = tmpface;
	tmpaasworld.numfaces++;
	return tmpface;
} //end of the function AAS_AllocTmpFace
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_FreeTmpFace(tmp_face_t *tmpface)
{
	if (tmpface->l_next) tmpface->l_next->l_prev = tmpface->l_prev;
	if (tmpface->l_prev) tmpface->l_prev->l_next = tmpface->l_next;
	else tmpaasworld.faces = tmpface->l_next;
	//free the winding
	if (tmpface->winding) FreeWinding(tmpface->winding);
	//free the face
	FreeMemory(tmpface);
	tmpaasworld.numfaces--;
} //end of the function AAS_FreeTmpFace
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
tmp_area_t *AAS_AllocTmpArea(void)
{
	tmp_area_t *tmparea;

	tmparea = (tmp_area_t *) GetClearedMemory(sizeof(tmp_area_t));
	tmparea->areanum = tmpaasworld.areanum++;
	tmparea->l_prev = NULL;
	tmparea->l_next = tmpaasworld.areas;
	if (tmpaasworld.areas) tmpaasworld.areas->l_prev = tmparea;
	tmpaasworld.areas = tmparea;
	tmpaasworld.numareas++;
	return tmparea;
} //end of the function AAS_AllocTmpArea
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_FreeTmpArea(tmp_area_t *tmparea)
{
	if (tmparea->l_next) tmparea->l_next->l_prev = tmparea->l_prev;
	if (tmparea->l_prev) tmparea->l_prev->l_next = tmparea->l_next;
	else tmpaasworld.areas = tmparea->l_next;
	if (tmparea->settings) FreeMemory(tmparea->settings);
	FreeMemory(tmparea);
	tmpaasworld.numareas--;
} //end of the function AAS_FreeTmpArea
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
tmp_node_t *AAS_AllocTmpNode(void)
{
	tmp_nodebuf_t *nodebuf;

	if (!tmpaasworld.nodebuffer ||
			tmpaasworld.nodebuffer->numnodes >= NODEBUF_SIZE)
	{
		nodebuf = (tmp_nodebuf_t *) GetClearedMemory(sizeof(tmp_nodebuf_t));
		nodebuf->next = tmpaasworld.nodebuffer;
		nodebuf->numnodes = 0;
		tmpaasworld.nodebuffer = nodebuf;
	} //end if
	tmpaasworld.numnodes++;
	return &tmpaasworld.nodebuffer->nodes[tmpaasworld.nodebuffer->numnodes++];
} //end of the function AAS_AllocTmpNode
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_FreeTmpNode(tmp_node_t *tmpnode)
{
	tmpaasworld.numnodes--;
} //end of the function AAS_FreeTmpNode
//===========================================================================
// returns true if the face is a gap from the given side
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
int AAS_GapFace(tmp_face_t *tmpface, int side)
{
	vec3_t invgravity;

	//if the face is a solid or ground face it can't be a gap
	if (tmpface->faceflags & (FACE_GROUND | FACE_SOLID)) return 0;

	VectorCopy(cfg.phys_gravitydirection, invgravity);
	VectorInverse(invgravity);

	return (DotProduct(invgravity, mapplanes[tmpface->planenum ^ side].normal) > cfg.phys_maxsteepness);
} //end of the function AAS_GapFace
//===========================================================================
// returns true if the face is a ground face
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
int AAS_GroundFace(tmp_face_t *tmpface)
{
	vec3_t invgravity;

	//must be a solid face
	if (!(tmpface->faceflags & FACE_SOLID)) return 0;

	VectorCopy(cfg.phys_gravitydirection, invgravity);
	VectorInverse(invgravity);

	return (DotProduct(invgravity, mapplanes[tmpface->planenum].normal) > cfg.phys_maxsteepness);
} //end of the function AAS_GroundFace
//===========================================================================
// adds the side of a face to an area
//
// side :	0 = front side
//				1 = back side
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_AddFaceSideToArea(tmp_face_t *tmpface, int side, tmp_area_t *tmparea)
{
	int tmpfaceside;

	if (side)
	{
		if (tmpface->backarea) Error("AAS_AddFaceSideToArea: already a back area\n");
	} //end if
	else
	{
		if (tmpface->frontarea) Error("AAS_AddFaceSideToArea: already a front area\n");
	} //end else

	if (side) tmpface->backarea = tmparea;
	else tmpface->frontarea = tmparea;

	if (tmparea->tmpfaces)
	{
		tmpfaceside = tmparea->tmpfaces->frontarea != tmparea;
		tmparea->tmpfaces->prev[tmpfaceside] = tmpface;
	} //end if
	tmpface->next[side] = tmparea->tmpfaces;
	tmpface->prev[side] = NULL;
	tmparea->tmpfaces = tmpface;
} //end of the function AAS_AddFaceSideToArea
//===========================================================================
// remove (a side of) a face from an area
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_RemoveFaceFromArea(tmp_face_t *tmpface, tmp_area_t *tmparea)
{
	int side, prevside, nextside;

	if (tmpface->frontarea != tmparea &&
			tmpface->backarea != tmparea)
	{
		Error("AAS_RemoveFaceFromArea: face not part of the area");
	} //end if
	side = tmpface->frontarea != tmparea;
	if (tmpface->prev[side])
	{
		prevside = tmpface->prev[side]->frontarea != tmparea;
		tmpface->prev[side]->next[prevside] = tmpface->next[side];
	} //end if
	else
	{
		tmparea->tmpfaces = tmpface->next[side];
	} //end else
	if (tmpface->next[side])
	{
		nextside = tmpface->next[side]->frontarea != tmparea;
		tmpface->next[side]->prev[nextside] = tmpface->prev[side];
	} //end if
	//remove the area number from the face depending on the side
	if (side) tmpface->backarea = NULL;
	else tmpface->frontarea = NULL;
	tmpface->prev[side] = NULL;
	tmpface->next[side] = NULL;
} //end of the function AAS_RemoveFaceFromArea
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_CheckArea(tmp_area_t *tmparea)
{
	int side;
	tmp_face_t *face;
	plane_t *plane;
	vec3_t wcenter, acenter = {0, 0, 0};
	vec3_t normal;
	float n, dist;

	if (tmparea->invalid) Log_Print("AAS_CheckArea: invalid area\n");
	for (n = 0, face = tmparea->tmpfaces; face; face = face->next[side])
	{
		//side of the face the area is on
		side = face->frontarea != tmparea;
		WindingCenter(face->winding, wcenter);
		VectorAdd(acenter, wcenter, acenter);
		n++;
	} //end for
	n = 1 / n;
	VectorScale(acenter, n, acenter);
	for (face = tmparea->tmpfaces; face; face = face->next[side])
	{
		//side of the face the area is on
		side = face->frontarea != tmparea;

#ifdef L_DEBUG
		if (WindingError(face->winding))
		{
			Log_Write("AAS_CheckArea: area %d face %d: %s\r\n", tmparea->areanum,
						face->num, WindingErrorString());
		} //end if
#endif L_DEBUG

		plane = &mapplanes[face->planenum ^ side];

		if (DotProduct(plane->normal, acenter) - plane->dist < 0)
		{
			Log_Print("AAS_CheckArea: area %d face %d is flipped\n", tmparea->areanum, face->num);
			Log_Print("AAS_CheckArea: area %d center is %f %f %f\n", tmparea->areanum, acenter[0], acenter[1], acenter[2]);
		} //end if
		//check if the winding plane is the same as the face plane
		WindingPlane(face->winding, normal, &dist);
		plane = &mapplanes[face->planenum];
#ifdef L_DEBUG
		if (fabs(dist - plane->dist) > 0.4 ||
				fabs(normal[0] - plane->normal[0]) > 0.0001 ||
				fabs(normal[1] - plane->normal[1]) > 0.0001 ||
				fabs(normal[2] - plane->normal[2]) > 0.0001)
		{
			Log_Write("AAS_CheckArea: area %d face %d winding plane unequal to face plane\r\n",
										tmparea->areanum, face->num);
		} //end if
#endif L_DEBUG
	} //end for
} //end of the function AAS_CheckArea
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_CheckFaceWindingPlane(tmp_face_t *face)
{
	float dist, sign1, sign2;
	vec3_t normal;
	plane_t *plane;
	winding_t *w;