map.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 "l_bsp_hl.h"
#include "l_bsp_q1.h"
#include "l_bsp_q2.h"
#include "l_bsp_q3.h"
#include "l_bsp_sin.h"
#include "l_mem.h"
#include "../botlib/aasfile.h"		//aas_bbox_t
#include "aas_store.h"		//AAS_MAX_BBOXES
#include "aas_cfg.h"

#define Sign(x)		(x < 0 ? 1 : 0)

int					nummapbrushes;
mapbrush_t			mapbrushes[MAX_MAPFILE_BRUSHES];

int					nummapbrushsides;
side_t				brushsides[MAX_MAPFILE_BRUSHSIDES];
brush_texture_t		side_brushtextures[MAX_MAPFILE_BRUSHSIDES];

int					nummapplanes;
plane_t				mapplanes[MAX_MAPFILE_PLANES];
int					mapplaneusers[MAX_MAPFILE_PLANES];

#define				PLANE_HASHES	1024
plane_t				*planehash[PLANE_HASHES];
vec3_t				map_mins, map_maxs;

#ifdef SIN
textureref_t		side_newrefs[MAX_MAPFILE_BRUSHSIDES];
#endif

map_texinfo_t		map_texinfo[MAX_MAPFILE_TEXINFO];
int					map_numtexinfo;
int					loadedmaptype;		//loaded map type

// undefine to make plane finding use linear sort
#define	USE_HASHING

int c_boxbevels;
int c_edgebevels;
int c_areaportals;
int c_clipbrushes;
int c_squattbrushes;
int c_writtenbrushes;

/*
=============================================================================

PLANE FINDING

=============================================================================
*/


//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
int PlaneSignBits(vec3_t normal)
{
	int i, signbits;

	signbits = 0;
	for (i = 2; i >= 0; i--)
	{
		signbits = (signbits << 1) + Sign(normal[i]);
	} //end for
	return signbits;
} //end of the function PlaneSignBits
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
int PlaneTypeForNormal(vec3_t normal)
{
	vec_t	ax, ay, az;
	
// NOTE: should these have an epsilon around 1.0?		
	if (normal[0] == 1.0 || normal[0] == -1.0)
		return PLANE_X;
	if (normal[1] == 1.0 || normal[1] == -1.0)
		return PLANE_Y;
	if (normal[2] == 1.0 || normal[2] == -1.0)
		return PLANE_Z;
		
	ax = fabs(normal[0]);
	ay = fabs(normal[1]);
	az = fabs(normal[2]);
	
	if (ax >= ay && ax >= az)
		return PLANE_ANYX;
	if (ay >= ax && ay >= az)
		return PLANE_ANYY;
	return PLANE_ANYZ;
} //end of the function PlaneTypeForNormal
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
//ME NOTE: changed from 0.00001
#define	NORMAL_EPSILON	0.0001
//ME NOTE: changed from 0.01
#define	DIST_EPSILON	0.02
qboolean	PlaneEqual(plane_t *p, vec3_t normal, vec_t dist)
{
#if 1
	if (
	   fabs(p->normal[0] - normal[0]) < NORMAL_EPSILON
	&& fabs(p->normal[1] - normal[1]) < NORMAL_EPSILON
	&& fabs(p->normal[2] - normal[2]) < NORMAL_EPSILON
	&& fabs(p->dist - dist) < DIST_EPSILON )
		return true;
#else
	if (p->normal[0] == normal[0]
		&& p->normal[1] == normal[1]
		&& p->normal[2] == normal[2]
		&& p->dist == dist)
		return true;
#endif
	return false;
} //end of the function PlaneEqual
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AddPlaneToHash(plane_t *p)
{
	int		hash;

	hash = (int)fabs(p->dist) / 8;
	hash &= (PLANE_HASHES-1);

	p->hash_chain = planehash[hash];
	planehash[hash] = p;
} //end of the function AddPlaneToHash
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
int CreateNewFloatPlane (vec3_t normal, vec_t dist)
{
	plane_t	*p, temp;

	if (VectorLength(normal) < 0.5)
		Error ("FloatPlane: bad normal");
	// create a new plane
	if (nummapplanes+2 > MAX_MAPFILE_PLANES)
		Error ("MAX_MAPFILE_PLANES");

	p = &mapplanes[nummapplanes];
	VectorCopy (normal, p->normal);
	p->dist = dist;
	p->type = (p+1)->type = PlaneTypeForNormal (p->normal);
	p->signbits = PlaneSignBits(p->normal);

	VectorSubtract (vec3_origin, normal, (p+1)->normal);
	(p+1)->dist = -dist;
	(p+1)->signbits = PlaneSignBits((p+1)->normal);

	nummapplanes += 2;

	// allways put axial planes facing positive first
	if (p->type < 3)
	{
		if (p->normal[0] < 0 || p->normal[1] < 0 || p->normal[2] < 0)
		{
			// flip order
			temp = *p;
			*p = *(p+1);
			*(p+1) = temp;

			AddPlaneToHash (p);
			AddPlaneToHash (p+1);
			return nummapplanes - 1;
		}
	}

	AddPlaneToHash (p);
	AddPlaneToHash (p+1);
	return nummapplanes - 2;
} //end of the function CreateNewFloatPlane
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void SnapVector(vec3_t normal)
{
	int		i;

	for (i=0 ; i<3 ; i++)
	{
		if ( fabs(normal[i] - 1) < NORMAL_EPSILON )
		{
			VectorClear (normal);
			normal[i] = 1;
			break;
		}
		if ( fabs(normal[i] - -1) < NORMAL_EPSILON )
		{
			VectorClear (normal);
			normal[i] = -1;
			break;
		}
	}
} //end of the function SnapVector
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void SnapPlane(vec3_t normal, vec_t *dist)
{
	SnapVector(normal);

	if (fabs(*dist-Q_rint(*dist)) < DIST_EPSILON)
		*dist = Q_rint(*dist);
} //end of the function SnapPlane
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
#ifndef USE_HASHING
int FindFloatPlane(vec3_t normal, vec_t dist)
{
	int i;
	plane_t *p;

	SnapPlane(normal, &dist);
	for (i = 0, p = mapplanes; i < nummapplanes; i++, p++)
	{
		if (PlaneEqual (p, normal, dist))
		{
			mapplaneusers[i]++;
			return i;
		} //end if
	} //end for
	i = CreateNewFloatPlane (normal, dist);
	mapplaneusers[i]++;
	return i;
} //end of the function FindFloatPlane
#else
int FindFloatPlane (vec3_t normal, vec_t dist)
{
	int i;
	plane_t *p;
	int hash, h;

	SnapPlane (normal, &dist);
	hash = (int)fabs(dist) / 8;
	hash &= (PLANE_HASHES-1);

	// search the border bins as well
	for (i = -1; i <= 1; i++)
	{
		h = (hash+i)&(PLANE_HASHES-1);
		for (p = planehash[h]; p; p = p->hash_chain)
		{
			if (PlaneEqual(p, normal, dist))
			{
				mapplaneusers[p-mapplanes]++;
				return p - mapplanes;
			} //end if
		} //end for
	} //end for
	i = CreateNewFloatPlane (normal, dist);
	mapplaneusers[i]++;
	return i;
} //end of the function FindFloatPlane
#endif
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
int PlaneFromPoints (int *p0, int *p1, int *p2)
{
	vec3_t	t1, t2, normal;
	vec_t	dist;

	VectorSubtract (p0, p1, t1);
	VectorSubtract (p2, p1, t2);
	CrossProduct (t1, t2, normal);
	VectorNormalize (normal);

	dist = DotProduct (p0, normal);

	return FindFloatPlane (normal, dist);
} //end of the function PlaneFromPoints
//===========================================================================
// Adds any additional planes necessary to allow the brush to be expanded
// against axial bounding boxes
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AddBrushBevels (mapbrush_t *b)
{
	int		axis, dir;
	int		i, j, k, l, order;
	side_t	sidetemp;
	brush_texture_t	tdtemp;
#ifdef SIN
   textureref_t trtemp;
#endif
	side_t	*s, *s2;
	vec3_t	normal;
	float	dist;
	winding_t	*w, *w2;
	vec3_t	vec, vec2;
	float	d;

	//
	// add the axial planes
	//
	order = 0;
	for (axis=0 ; axis <3 ; axis++)
	{
		for (dir=-1 ; dir <= 1 ; dir+=2, order++)
		{
			// see if the plane is allready present
			for (i=0, s=b->original_sides ; i<b->numsides ; i++,s++)
			{
				if (mapplanes[s->planenum].normal[axis] == dir)
					break;
			}

			if (i == b->numsides)
			{	// add a new side
				if (nummapbrushsides == MAX_MAP_BRUSHSIDES)
					Error ("MAX_MAP_BRUSHSIDES");
				nummapbrushsides++;
				b->numsides++;
				VectorClear (normal);
				normal[axis] = dir;
				if (dir == 1)
					dist = b->maxs[axis];
				else
					dist = -b->mins[axis];
				s->planenum = FindFloatPlane (normal, dist);
				s->texinfo = b->original_sides[0].texinfo;
#ifdef SIN
				s->lightinfo = b->original_sides[0].lightinfo;
#endif
				s->contents = b->original_sides[0].contents;
				s->flags |= SFL_BEVEL;
				c_boxbevels++;
			}

			// if the plane is not in it canonical order, swap it
			if (i != order)
			{
				sidetemp = b->original_sides[order];
				b->original_sides[order] = b->original_sides[i];
				b->original_sides[i] = sidetemp;

				j = b->original_sides - brushsides;
				tdtemp = side_brushtextures[j+order];
				side_brushtextures[j+order] = side_brushtextures[j+i];
				side_brushtextures[j+i] = tdtemp;

#ifdef SIN
				trtemp = side_newrefs[j+order];
				side_newrefs[j+order] = side_newrefs[j+i];
				side_newrefs[j+i] = trtemp;
#endif
			}
		}
	}

	//
	// add the edge bevels
	//
	if (b->numsides == 6)
		return;		// pure axial

	// test the non-axial plane edges
	for (i=6 ; i<b->numsides ; i++)
	{
		s = b->original_sides + i;
		w = s->winding;
		if (!w)
			continue;
		for (j=0 ; j<w->numpoints ; j++)