aas_store.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_file.h"
#include "aas_store.h"
#include "aas_create.h"
#include "aas_cfg.h"


//#define NOTHREEVERTEXFACES

#define STOREPLANESDOUBLE

#define VERTEX_EPSILON			0.1			//NOTE: changed from 0.5
#define DIST_EPSILON			0.05		//NOTE: changed from 0.9
#define NORMAL_EPSILON			0.0001		//NOTE: changed from 0.005
#define INTEGRAL_EPSILON		0.01

#define VERTEX_HASHING
#define VERTEX_HASH_SHIFT		7
#define VERTEX_HASH_SIZE		((MAX_MAP_BOUNDS>>(VERTEX_HASH_SHIFT-1))+1)	//was 64
//
#define PLANE_HASHING
#define PLANE_HASH_SIZE			1024		//must be power of 2
//
#define EDGE_HASHING
#define EDGE_HASH_SIZE			1024		//must be power of 2

aas_t aasworld;

//vertex hash
int *aas_vertexchain;						// the next vertex in a hash chain
int aas_hashverts[VERTEX_HASH_SIZE*VERTEX_HASH_SIZE];	// a vertex number, or 0 for no verts
//plane hash
int *aas_planechain;
int aas_hashplanes[PLANE_HASH_SIZE];
//edge hash
int *aas_edgechain;
int aas_hashedges[EDGE_HASH_SIZE];

int allocatedaasmem = 0;

int groundfacesonly = false;//true;
//
typedef struct max_aas_s
{
	int max_bboxes;
	int max_vertexes;
	int max_planes;
	int max_edges;
	int max_edgeindexsize;
	int max_faces;
	int max_faceindexsize;
	int max_areas;
	int max_areasettings;
	int max_reachabilitysize;
	int max_nodes;
	int max_portals;
	int max_portalindexsize;
	int max_clusters;
} max_aas_t;
//maximums of everything
max_aas_t max_aas;

//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
int AAS_CountTmpNodes(tmp_node_t *tmpnode)
{
	if (!tmpnode) return 0;
	return AAS_CountTmpNodes(tmpnode->children[0]) +
				AAS_CountTmpNodes(tmpnode->children[1]) + 1;
} //end of the function AAS_CountTmpNodes
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_InitMaxAAS(void)
{
	int numfaces, numpoints, numareas;
	tmp_face_t *f;
	tmp_area_t *a;

	numpoints = 0;
	numfaces = 0;
	for (f = tmpaasworld.faces; f; f = f->l_next)
	{
		numfaces++;
		if (f->winding) numpoints += f->winding->numpoints;
	} //end for
	//
	numareas = 0;
	for (a = tmpaasworld.areas; a; a = a->l_next)
	{
		numareas++;
	} //end for
	max_aas.max_bboxes = AAS_MAX_BBOXES;
	max_aas.max_vertexes = numpoints + 1;
	max_aas.max_planes = nummapplanes;
	max_aas.max_edges = numpoints + 1;
	max_aas.max_edgeindexsize = (numpoints + 1) * 3;
	max_aas.max_faces = numfaces + 10;
	max_aas.max_faceindexsize = (numfaces + 10) * 2;
	max_aas.max_areas = numareas + 10;
	max_aas.max_areasettings = numareas + 10;
	max_aas.max_reachabilitysize = 0;
	max_aas.max_nodes = AAS_CountTmpNodes(tmpaasworld.nodes) + 10;
	max_aas.max_portals = 0;
	max_aas.max_portalindexsize = 0;
	max_aas.max_clusters = 0;
} //end of the function AAS_InitMaxAAS
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_AllocMaxAAS(void)
{
	int i;

	AAS_InitMaxAAS();
	//bounding boxes
	aasworld.numbboxes = 0;
	aasworld.bboxes = (aas_bbox_t *) GetClearedMemory(max_aas.max_bboxes * sizeof(aas_bbox_t));
	allocatedaasmem += max_aas.max_bboxes * sizeof(aas_bbox_t);
	//vertexes
	aasworld.numvertexes = 0;
	aasworld.vertexes = (aas_vertex_t *) GetClearedMemory(max_aas.max_vertexes * sizeof(aas_vertex_t));
	allocatedaasmem += max_aas.max_vertexes * sizeof(aas_vertex_t);
	//planes
	aasworld.numplanes = 0;
	aasworld.planes = (aas_plane_t *) GetClearedMemory(max_aas.max_planes * sizeof(aas_plane_t));
	allocatedaasmem += max_aas.max_planes * sizeof(aas_plane_t);
	//edges
	aasworld.numedges = 0;
	aasworld.edges = (aas_edge_t *) GetClearedMemory(max_aas.max_edges * sizeof(aas_edge_t));
	allocatedaasmem += max_aas.max_edges * sizeof(aas_edge_t);
	//edge index
	aasworld.edgeindexsize = 0;
	aasworld.edgeindex = (aas_edgeindex_t *) GetClearedMemory(max_aas.max_edgeindexsize * sizeof(aas_edgeindex_t));
	allocatedaasmem += max_aas.max_edgeindexsize * sizeof(aas_edgeindex_t);
	//faces
	aasworld.numfaces = 0;
	aasworld.faces = (aas_face_t *) GetClearedMemory(max_aas.max_faces * sizeof(aas_face_t));
	allocatedaasmem += max_aas.max_faces * sizeof(aas_face_t);
	//face index
	aasworld.faceindexsize = 0;
	aasworld.faceindex = (aas_faceindex_t *) GetClearedMemory(max_aas.max_faceindexsize * sizeof(aas_faceindex_t));
	allocatedaasmem += max_aas.max_faceindexsize * sizeof(aas_faceindex_t);
	//convex areas
	aasworld.numareas = 0;
	aasworld.areas = (aas_area_t *) GetClearedMemory(max_aas.max_areas * sizeof(aas_area_t));
	allocatedaasmem += max_aas.max_areas * sizeof(aas_area_t);
	//convex area settings
	aasworld.numareasettings = 0;
	aasworld.areasettings = (aas_areasettings_t *) GetClearedMemory(max_aas.max_areasettings * sizeof(aas_areasettings_t));
	allocatedaasmem += max_aas.max_areasettings * sizeof(aas_areasettings_t);
	//reachablity list
	aasworld.reachabilitysize = 0;
	aasworld.reachability = (aas_reachability_t *) GetClearedMemory(max_aas.max_reachabilitysize * sizeof(aas_reachability_t));
	allocatedaasmem += max_aas.max_reachabilitysize * sizeof(aas_reachability_t);
	//nodes of the bsp tree
	aasworld.numnodes = 0;
	aasworld.nodes = (aas_node_t *) GetClearedMemory(max_aas.max_nodes * sizeof(aas_node_t));
	allocatedaasmem += max_aas.max_nodes * sizeof(aas_node_t);
	//cluster portals
	aasworld.numportals = 0;
	aasworld.portals = (aas_portal_t *) GetClearedMemory(max_aas.max_portals * sizeof(aas_portal_t));
	allocatedaasmem += max_aas.max_portals * sizeof(aas_portal_t);
	//cluster portal index
	aasworld.portalindexsize = 0;
	aasworld.portalindex = (aas_portalindex_t *) GetClearedMemory(max_aas.max_portalindexsize * sizeof(aas_portalindex_t));
	allocatedaasmem += max_aas.max_portalindexsize * sizeof(aas_portalindex_t);
	//cluster
	aasworld.numclusters = 0;
	aasworld.clusters = (aas_cluster_t *) GetClearedMemory(max_aas.max_clusters * sizeof(aas_cluster_t));
	allocatedaasmem += max_aas.max_clusters * sizeof(aas_cluster_t);
	//
	Log_Print("allocated ");
	PrintMemorySize(allocatedaasmem);
	Log_Print(" of AAS memory\n");
	//reset the has stuff
	aas_vertexchain = (int *) GetClearedMemory(max_aas.max_vertexes * sizeof(int));
	aas_planechain = (int *) GetClearedMemory(max_aas.max_planes * sizeof(int));
	aas_edgechain = (int *) GetClearedMemory(max_aas.max_edges * sizeof(int));
	//
	for (i = 0; i < max_aas.max_vertexes; i++) aas_vertexchain[i] = -1;
	for (i = 0; i < VERTEX_HASH_SIZE * VERTEX_HASH_SIZE; i++) aas_hashverts[i] = -1;
	//
	for (i = 0; i < max_aas.max_planes; i++) aas_planechain[i] = -1;
	for (i = 0; i < PLANE_HASH_SIZE; i++) aas_hashplanes[i] = -1;
	//
	for (i = 0; i < max_aas.max_edges; i++) aas_edgechain[i] = -1;
	for (i = 0; i < EDGE_HASH_SIZE; i++) aas_hashedges[i] = -1;
} //end of the function AAS_AllocMaxAAS
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_FreeMaxAAS(void)
{
	//bounding boxes
	if (aasworld.bboxes) FreeMemory(aasworld.bboxes);
	aasworld.bboxes = NULL;
	aasworld.numbboxes = 0;
	//vertexes
	if (aasworld.vertexes) FreeMemory(aasworld.vertexes);
	aasworld.vertexes = NULL;
	aasworld.numvertexes = 0;
	//planes
	if (aasworld.planes) FreeMemory(aasworld.planes);
	aasworld.planes = NULL;
	aasworld.numplanes = 0;
	//edges
	if (aasworld.edges) FreeMemory(aasworld.edges);
	aasworld.edges = NULL;
	aasworld.numedges = 0;
	//edge index
	if (aasworld.edgeindex) FreeMemory(aasworld.edgeindex);
	aasworld.edgeindex = NULL;
	aasworld.edgeindexsize = 0;
	//faces
	if (aasworld.faces) FreeMemory(aasworld.faces);
	aasworld.faces = NULL;
	aasworld.numfaces = 0;
	//face index
	if (aasworld.faceindex) FreeMemory(aasworld.faceindex);
	aasworld.faceindex = NULL;
	aasworld.faceindexsize = 0;
	//convex areas
	if (aasworld.areas) FreeMemory(aasworld.areas);
	aasworld.areas = NULL;
	aasworld.numareas = 0;
	//convex area settings
	if (aasworld.areasettings) FreeMemory(aasworld.areasettings);
	aasworld.areasettings = NULL;
	aasworld.numareasettings = 0;
	//reachablity list
	if (aasworld.reachability) FreeMemory(aasworld.reachability);
	aasworld.reachability = NULL;
	aasworld.reachabilitysize = 0;
	//nodes of the bsp tree
	if (aasworld.nodes) FreeMemory(aasworld.nodes);
	aasworld.nodes = NULL;
	aasworld.numnodes = 0;
	//cluster portals
	if (aasworld.portals) FreeMemory(aasworld.portals);
	aasworld.portals = NULL;
	aasworld.numportals = 0;
	//cluster portal index
	if (aasworld.portalindex) FreeMemory(aasworld.portalindex);
	aasworld.portalindex = NULL;
	aasworld.portalindexsize = 0;
	//clusters
	if (aasworld.clusters) FreeMemory(aasworld.clusters);
	aasworld.clusters = NULL;
	aasworld.numclusters = 0;
	
	Log_Print("freed ");
	PrintMemorySize(allocatedaasmem);
	Log_Print(" of AAS memory\n");
	allocatedaasmem = 0;
	//
	if (aas_vertexchain) FreeMemory(aas_vertexchain);
	aas_vertexchain = NULL;
	if (aas_planechain) FreeMemory(aas_planechain);
	aas_planechain = NULL;
	if (aas_edgechain) FreeMemory(aas_edgechain);
	aas_edgechain = NULL;
} //end of the function AAS_FreeMaxAAS
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
unsigned AAS_HashVec(vec3_t vec)
{
	int x, y;

	x = (MAX_MAP_BOUNDS + (int)(vec[0]+0.5)) >> VERTEX_HASH_SHIFT;
	y = (MAX_MAP_BOUNDS + (int)(vec[1]+0.5)) >> VERTEX_HASH_SHIFT;

	if (x < 0 || x >= VERTEX_HASH_SIZE || y < 0 || y >= VERTEX_HASH_SIZE)
	{
		Log_Print("WARNING! HashVec: point %f %f %f outside valid range\n", vec[0], vec[1], vec[2]);
		Log_Print("This should never happen!\n");
		return -1;
	} //end if
	
	return y*VERTEX_HASH_SIZE + x;
} //end of the function AAS_HashVec
//===========================================================================
// returns true if the vertex was found in the list
// stores the vertex number in *vnum
// stores a new vertex if not stored already
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
qboolean AAS_GetVertex(vec3_t v, int *vnum)
{
	int i;
#ifndef VERTEX_HASHING
	float diff;
#endif //VERTEX_HASHING

#ifdef VERTEX_HASHING
	int h, vn;
	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 = AAS_HashVec(vert);
	//if the vertex was outside the valid range
	if (h == -1)
	{
		*vnum = -1;
		return true;
	} //end if

	for (vn = aas_hashverts[h]; vn >= 0; vn = aas_vertexchain[vn])
	{
		if (fabs(aasworld.vertexes[vn][0] - vert[0]) < VERTEX_EPSILON
				&& fabs(aasworld.vertexes[vn][1] - vert[1]) < VERTEX_EPSILON