l_bsp_sin.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 "l_cmd.h"
#include "l_math.h"
#include "l_mem.h"
#include "l_log.h"
#include "l_poly.h"
#include "../botlib/l_script.h"
#include "l_bsp_ent.h"
#include "l_bsp_sin.h"

void GetLeafNums (void);

//=============================================================================

int					sin_nummodels;
sin_dmodel_t		*sin_dmodels;//[SIN_MAX_MAP_MODELS];

int					sin_visdatasize;
byte				*sin_dvisdata;//[SIN_MAX_MAP_VISIBILITY];
sin_dvis_t			*sin_dvis;// = (sin_dvis_t *)sin_sin_dvisdata;

int					sin_lightdatasize;
byte				*sin_dlightdata;//[SIN_MAX_MAP_LIGHTING];

int					sin_entdatasize;
char				*sin_dentdata;//[SIN_MAX_MAP_ENTSTRING];

int					sin_numleafs;
sin_dleaf_t			*sin_dleafs;//[SIN_MAX_MAP_LEAFS];

int					sin_numplanes;
sin_dplane_t		*sin_dplanes;//[SIN_MAX_MAP_PLANES];

int					sin_numvertexes;
sin_dvertex_t		*sin_dvertexes;//[SIN_MAX_MAP_VERTS];

int					sin_numnodes;
sin_dnode_t			*sin_dnodes;//[SIN_MAX_MAP_NODES];

int					sin_numtexinfo;
sin_texinfo_t		*sin_texinfo;//[SIN_MAX_MAP_sin_texinfo];

int					sin_numfaces;
sin_dface_t			*sin_dfaces;//[SIN_MAX_MAP_FACES];

int					sin_numedges;
sin_dedge_t			*sin_dedges;//[SIN_MAX_MAP_EDGES];

int					sin_numleaffaces;
unsigned short		*sin_dleaffaces;//[SIN_MAX_MAP_LEAFFACES];

int					sin_numleafbrushes;
unsigned short		*sin_dleafbrushes;//[SIN_MAX_MAP_LEAFBRUSHES];

int					sin_numsurfedges;
int					*sin_dsurfedges;//[SIN_MAX_MAP_SURFEDGES];

int					sin_numbrushes;
sin_dbrush_t		*sin_dbrushes;//[SIN_MAX_MAP_BRUSHES];

int					sin_numbrushsides;
sin_dbrushside_t	*sin_dbrushsides;//[SIN_MAX_MAP_BRUSHSIDES];

int					sin_numareas;
sin_darea_t			*sin_dareas;//[SIN_MAX_MAP_AREAS];

int					sin_numareaportals;
sin_dareaportal_t	*sin_dareaportals;//[SIN_MAX_MAP_AREAPORTALS];

int					sin_numlightinfo;
sin_lightvalue_t	*sin_lightinfo;//[SIN_MAX_MAP_LIGHTINFO];

byte				sin_dpop[256];

char				sin_dbrushsidetextured[SIN_MAX_MAP_BRUSHSIDES];

int sin_bspallocated = false;
int sin_allocatedbspmem = 0;

void Sin_AllocMaxBSP(void)
{
	//models
	sin_nummodels = 0;
	sin_dmodels = (sin_dmodel_t *) GetClearedMemory(SIN_MAX_MAP_MODELS * sizeof(sin_dmodel_t));
	sin_allocatedbspmem += SIN_MAX_MAP_MODELS * sizeof(sin_dmodel_t);
	//vis data
	sin_visdatasize = 0;
	sin_dvisdata = (byte *) GetClearedMemory(SIN_MAX_MAP_VISIBILITY * sizeof(byte));
	sin_dvis = (sin_dvis_t *) sin_dvisdata;
	sin_allocatedbspmem += SIN_MAX_MAP_VISIBILITY * sizeof(byte);
	//light data
	sin_lightdatasize = 0;
	sin_dlightdata = (byte *) GetClearedMemory(SIN_MAX_MAP_LIGHTING * sizeof(byte));
	sin_allocatedbspmem += SIN_MAX_MAP_LIGHTING * sizeof(byte);
	//entity data
	sin_entdatasize = 0;
	sin_dentdata = (char *) GetClearedMemory(SIN_MAX_MAP_ENTSTRING * sizeof(char));
	sin_allocatedbspmem += SIN_MAX_MAP_ENTSTRING * sizeof(char);
	//leafs
	sin_numleafs = 0;
	sin_dleafs = (sin_dleaf_t *) GetClearedMemory(SIN_MAX_MAP_LEAFS * sizeof(sin_dleaf_t));
	sin_allocatedbspmem += SIN_MAX_MAP_LEAFS * sizeof(sin_dleaf_t);
	//planes
	sin_numplanes = 0;
	sin_dplanes = (sin_dplane_t *) GetClearedMemory(SIN_MAX_MAP_PLANES * sizeof(sin_dplane_t));
	sin_allocatedbspmem += SIN_MAX_MAP_PLANES * sizeof(sin_dplane_t);
	//vertexes
	sin_numvertexes = 0;
	sin_dvertexes = (sin_dvertex_t *) GetClearedMemory(SIN_MAX_MAP_VERTS * sizeof(sin_dvertex_t));
	sin_allocatedbspmem += SIN_MAX_MAP_VERTS * sizeof(sin_dvertex_t);
	//nodes
	sin_numnodes = 0;
	sin_dnodes = (sin_dnode_t *) GetClearedMemory(SIN_MAX_MAP_NODES * sizeof(sin_dnode_t));
	sin_allocatedbspmem += SIN_MAX_MAP_NODES * sizeof(sin_dnode_t);
	//texture info
	sin_numtexinfo = 0;
	sin_texinfo = (sin_texinfo_t *) GetClearedMemory(SIN_MAX_MAP_TEXINFO * sizeof(sin_texinfo_t));
	sin_allocatedbspmem += SIN_MAX_MAP_TEXINFO * sizeof(sin_texinfo_t);
	//faces
	sin_numfaces = 0;
	sin_dfaces = (sin_dface_t *) GetClearedMemory(SIN_MAX_MAP_FACES * sizeof(sin_dface_t));
	sin_allocatedbspmem += SIN_MAX_MAP_FACES * sizeof(sin_dface_t);
	//edges
	sin_numedges = 0;
	sin_dedges = (sin_dedge_t *) GetClearedMemory(SIN_MAX_MAP_EDGES * sizeof(sin_dedge_t));
	sin_allocatedbspmem += SIN_MAX_MAP_EDGES * sizeof(sin_dedge_t);
	//leaf faces
	sin_numleaffaces = 0;
	sin_dleaffaces = (unsigned short *) GetClearedMemory(SIN_MAX_MAP_LEAFFACES * sizeof(unsigned short));
	sin_allocatedbspmem += SIN_MAX_MAP_LEAFFACES * sizeof(unsigned short);
	//leaf brushes
	sin_numleafbrushes = 0;
	sin_dleafbrushes = (unsigned short *) GetClearedMemory(SIN_MAX_MAP_LEAFBRUSHES * sizeof(unsigned short));
	sin_allocatedbspmem += SIN_MAX_MAP_LEAFBRUSHES * sizeof(unsigned short);
	//surface edges
	sin_numsurfedges = 0;
	sin_dsurfedges = (int *) GetClearedMemory(SIN_MAX_MAP_SURFEDGES * sizeof(int));
	sin_allocatedbspmem += SIN_MAX_MAP_SURFEDGES * sizeof(int);
	//brushes
	sin_numbrushes = 0;
	sin_dbrushes = (sin_dbrush_t *) GetClearedMemory(SIN_MAX_MAP_BRUSHES * sizeof(sin_dbrush_t));
	sin_allocatedbspmem += SIN_MAX_MAP_BRUSHES * sizeof(sin_dbrush_t);
	//brushsides
	sin_numbrushsides = 0;
	sin_dbrushsides = (sin_dbrushside_t *) GetClearedMemory(SIN_MAX_MAP_BRUSHSIDES * sizeof(sin_dbrushside_t));
	sin_allocatedbspmem += SIN_MAX_MAP_BRUSHSIDES * sizeof(sin_dbrushside_t);
	//areas
	sin_numareas = 0;
	sin_dareas = (sin_darea_t *) GetClearedMemory(SIN_MAX_MAP_AREAS * sizeof(sin_darea_t));
	sin_allocatedbspmem += SIN_MAX_MAP_AREAS * sizeof(sin_darea_t);
	//area portals
	sin_numareaportals = 0;
	sin_dareaportals = (sin_dareaportal_t *) GetClearedMemory(SIN_MAX_MAP_AREAPORTALS * sizeof(sin_dareaportal_t));
	sin_allocatedbspmem += SIN_MAX_MAP_AREAPORTALS * sizeof(sin_dareaportal_t);
	//light info
	sin_numlightinfo = 0;
	sin_lightinfo = (sin_lightvalue_t *) GetClearedMemory(SIN_MAX_MAP_LIGHTINFO * sizeof(sin_lightvalue_t));
	sin_allocatedbspmem += SIN_MAX_MAP_LIGHTINFO * sizeof(sin_lightvalue_t);
	//print allocated memory
	Log_Print("allocated ");
	PrintMemorySize(sin_allocatedbspmem);
	Log_Print(" of BSP memory\n");
} //end of the function Sin_AllocMaxBSP

void Sin_FreeMaxBSP(void)
{
	//models
	sin_nummodels = 0;
	FreeMemory(sin_dmodels);
	sin_dmodels = NULL;
	//vis data
	sin_visdatasize = 0;
	FreeMemory(sin_dvisdata);
	sin_dvisdata = NULL;
	sin_dvis = NULL;
	//light data
	sin_lightdatasize = 0;
	FreeMemory(sin_dlightdata);
	sin_dlightdata = NULL;
	//entity data
	sin_entdatasize = 0;
	FreeMemory(sin_dentdata);
	sin_dentdata = NULL;
	//leafs
	sin_numleafs = 0;
	FreeMemory(sin_dleafs);
	sin_dleafs = NULL;
	//planes
	sin_numplanes = 0;
	FreeMemory(sin_dplanes);
	sin_dplanes = NULL;
	//vertexes
	sin_numvertexes = 0;
	FreeMemory(sin_dvertexes);
	sin_dvertexes = NULL;
	//nodes
	sin_numnodes = 0;
	FreeMemory(sin_dnodes);
	sin_dnodes = NULL;
	//texture info
	sin_numtexinfo = 0;
	FreeMemory(sin_texinfo);
	sin_texinfo = NULL;
	//faces
	sin_numfaces = 0;
	FreeMemory(sin_dfaces);
	sin_dfaces = NULL;
	//edges
	sin_numedges = 0;
	FreeMemory(sin_dedges);
	sin_dedges = NULL;
	//leaf faces
	sin_numleaffaces = 0;
	FreeMemory(sin_dleaffaces);
	sin_dleaffaces = NULL;
	//leaf brushes
	sin_numleafbrushes = 0;
	FreeMemory(sin_dleafbrushes);
	sin_dleafbrushes = NULL;
	//surface edges
	sin_numsurfedges = 0;
	FreeMemory(sin_dsurfedges);
	sin_dsurfedges = NULL;
	//brushes
	sin_numbrushes = 0;
	FreeMemory(sin_dbrushes);
	sin_dbrushes = NULL;
	//brushsides
	sin_numbrushsides = 0;
	FreeMemory(sin_dbrushsides);
	sin_dbrushsides = NULL;
	//areas
	sin_numareas = 0;
	FreeMemory(sin_dareas);
	sin_dareas = NULL;
	//area portals
	sin_numareaportals = 0;
	FreeMemory(sin_dareaportals);
	sin_dareaportals = NULL;
	//light info
	sin_numlightinfo = 0;
	FreeMemory(sin_lightinfo);
	sin_lightinfo = NULL;
	//
	Log_Print("freed ");
	PrintMemorySize(sin_allocatedbspmem);
	Log_Print(" of BSP memory\n");
	sin_allocatedbspmem = 0;
} //end of the function Sin_FreeMaxBSP

#define WCONVEX_EPSILON		0.5

//===========================================================================
// returns the amount the face and the winding overlap
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
float Sin_FaceOnWinding(sin_dface_t *face, winding_t *winding)
{
	int i, edgenum, side;
	float dist, area;
	sin_dplane_t plane;
	vec_t *v1, *v2;
	vec3_t normal, edgevec;
	winding_t *w;

	//
	w = CopyWinding(winding);
	memcpy(&plane, &sin_dplanes[face->planenum], sizeof(sin_dplane_t));
	//check on which side of the plane the face is
	if (face->side)
	{
		VectorNegate(plane.normal, plane.normal);
		plane.dist = -plane.dist;
	} //end if
	for (i = 0; i < face->numedges && w; i++)
	{
		//get the first and second vertex of the edge
		edgenum = sin_dsurfedges[face->firstedge + i];
		side = edgenum > 0;
		//if the face plane is flipped
		v1 = sin_dvertexes[sin_dedges[abs(edgenum)].v[side]].point;
		v2 = sin_dvertexes[sin_dedges[abs(edgenum)].v[!side]].point;
		//create a plane through the edge vector, orthogonal to the face plane
		//and with the normal vector pointing out of the face
		VectorSubtract(v1, v2, edgevec);
		CrossProduct(edgevec, plane.normal, normal);
		VectorNormalize(normal);
		dist = DotProduct(normal, v1);
		//
		ChopWindingInPlace(&w, normal, dist, 0.9); //CLIP_EPSILON
	} //end for
	if (w)
	{
		area = WindingArea(w);
		FreeWinding(w);
		return area;
	} //end if
	return 0;
} //end of the function Sin_FaceOnWinding
//===========================================================================
// creates a winding for the given brush side on the given brush
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
winding_t *Sin_BrushSideWinding(sin_dbrush_t *brush, sin_dbrushside_t *baseside)
{
	int i;
	sin_dplane_t *baseplane, *plane;
	sin_dbrushside_t *side;
	winding_t *w;
	
	//create a winding for the brush side with the given planenumber
	baseplane = &sin_dplanes[baseside->planenum];
	w = BaseWindingForPlane(baseplane->normal, baseplane->dist);
	for (i = 0; i < brush->numsides && w; i++)
	{
		side = &sin_dbrushsides[brush->firstside + i];
		//don't chop with the base plane
		if (side->planenum == baseside->planenum) continue;
		//also don't use planes that are almost equal
		plane = &sin_dplanes[side->planenum];
		if (DotProduct(baseplane->normal, plane->normal) > 0.999
				&& fabs(baseplane->dist - plane->dist) < 0.01) continue;
		//
		plane = &sin_dplanes[side->planenum^1];
		ChopWindingInPlace(&w, plane->normal, plane->dist, 0); //CLIP_EPSILON);
	} //end for
	return w;
} //end of the function Sin_BrushSideWinding
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
int Sin_HintSkipBrush(sin_dbrush_t *brush)
{
	int j;
	sin_dbrushside_t *brushside;

	for (j = 0; j < brush->numsides; j++)
	{
		brushside = &sin_dbrushsides[brush->firstside + j];
		if (brushside->texinfo > 0)
		{
			if (sin_texinfo[brushside->texinfo].flags & (SURF_SKIP|SURF_HINT))
			{
				return true;
			} //end if
		} //end if
	} //end for
	return false;
} //end of the function Sin_HintSkipBrush
//===========================================================================
// fix screwed brush texture references
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
qboolean WindingIsTiny(winding_t *w);

void Sin_FixTextureReferences(void)
{
	int i, j, k, we;
	sin_dbrushside_t *brushside;
	sin_dbrush_t *brush;
	sin_dface_t *face;
	winding_t *w;