brushbsp.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_mem.h"
#include "../botlib/aasfile.h"
#include "aas_store.h"
#include "aas_cfg.h"

#include <assert.h>

/*
each side has a count of the other sides it splits

the best split will be the one that minimizes the total split counts
of all remaining sides

precalc side on plane table

evaluate split side
{
cost = 0
for all sides
	for all sides
		get 
		if side splits side and splitside is on same child
			cost++;
}
*/

int c_nodes;
int c_nonvis;
int c_active_brushes;
int c_solidleafnodes;
int c_totalsides;
int c_brushmemory;
int c_peak_brushmemory;
int c_nodememory;
int c_peak_totalbspmemory;

// if a brush just barely pokes onto the other side,
// let it slide by without chopping
#define	PLANESIDE_EPSILON	0.001
//0.1

//#ifdef DEBUG
typedef struct cname_s
{
	int value;
	char *name;
} cname_t;

cname_t contentnames[] =
{
	{CONTENTS_SOLID,"CONTENTS_SOLID"},
	{CONTENTS_WINDOW,"CONTENTS_WINDOW"},
	{CONTENTS_AUX,"CONTENTS_AUX"},
	{CONTENTS_LAVA,"CONTENTS_LAVA"},
	{CONTENTS_SLIME,"CONTENTS_SLIME"},
	{CONTENTS_WATER,"CONTENTS_WATER"},
	{CONTENTS_MIST,"CONTENTS_MIST"},
	{LAST_VISIBLE_CONTENTS,"LAST_VISIBLE_CONTENTS"},

	{CONTENTS_AREAPORTAL,"CONTENTS_AREAPORTAL"},
	{CONTENTS_PLAYERCLIP,"CONTENTS_PLAYERCLIP"},
	{CONTENTS_MONSTERCLIP,"CONTENTS_MONSTERCLIP"},
	{CONTENTS_CURRENT_0,"CONTENTS_CURRENT_0"},
	{CONTENTS_CURRENT_90,"CONTENTS_CURRENT_90"},
	{CONTENTS_CURRENT_180,"CONTENTS_CURRENT_180"},
	{CONTENTS_CURRENT_270,"CONTENTS_CURRENT_270"},
	{CONTENTS_CURRENT_UP,"CONTENTS_CURRENT_UP"},
	{CONTENTS_CURRENT_DOWN,"CONTENTS_CURRENT_DOWN"},
	{CONTENTS_ORIGIN,"CONTENTS_ORIGIN"},
	{CONTENTS_MONSTER,"CONTENTS_MONSTER"},
	{CONTENTS_DEADMONSTER,"CONTENTS_DEADMONSTER"},
	{CONTENTS_DETAIL,"CONTENTS_DETAIL"},
	{CONTENTS_Q2TRANSLUCENT,"CONTENTS_TRANSLUCENT"},
	{CONTENTS_LADDER,"CONTENTS_LADDER"},
	{0, 0}
};

void PrintContents(int contents)
{
	int i;

	for (i = 0; contentnames[i].value; i++)
	{
		if (contents & contentnames[i].value)
		{
			Log_Write("%s,", contentnames[i].name);
		} //end if
	} //end for
} //end of the function PrintContents

//#endif DEBUG

//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
void ResetBrushBSP(void)
{
	c_nodes = 0;
	c_nonvis = 0;
	c_active_brushes = 0;
	c_solidleafnodes = 0;
	c_totalsides = 0;
	c_brushmemory = 0;
	c_peak_brushmemory = 0;
	c_nodememory = 0;
	c_peak_totalbspmemory = 0;
} //end of the function ResetBrushBSP
//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
void FindBrushInTree (node_t *node, int brushnum)
{
	bspbrush_t	*b;

	if (node->planenum == PLANENUM_LEAF)
	{
		for (b=node->brushlist ; b ; b=b->next)
			if (b->original->brushnum == brushnum)
				Log_Print ("here\n");
		return;
	}
	FindBrushInTree(node->children[0], brushnum);
	FindBrushInTree(node->children[1], brushnum);
} //end of the function FindBrushInTree
//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
void DrawBrushList (bspbrush_t *brush, node_t *node)
{
	int		i;
	side_t	*s;

	GLS_BeginScene ();
	for ( ; brush ; brush=brush->next)
	{
		for (i=0 ; i<brush->numsides ; i++)
		{
			s = &brush->sides[i];
			if (!s->winding)
				continue;
			if (s->texinfo == TEXINFO_NODE)
				GLS_Winding (s->winding, 1);
			else if (!(s->flags & SFL_VISIBLE))
				GLS_Winding (s->winding, 2);
			else
				GLS_Winding (s->winding, 0);
		}
	}
	GLS_EndScene ();
} //end of the function DrawBrushList
//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
void WriteBrushList (char *name, bspbrush_t *brush, qboolean onlyvis)
{
	int		i;
	side_t	*s;
	FILE	*f;

	qprintf ("writing %s\n", name);
	f = SafeOpenWrite (name);

	for ( ; brush ; brush=brush->next)
	{
		for (i=0 ; i<brush->numsides ; i++)
		{
			s = &brush->sides[i];
			if (!s->winding)
				continue;
			if (onlyvis && !(s->flags & SFL_VISIBLE))
				continue;
			OutputWinding (brush->sides[i].winding, f);
		}
	}

	fclose (f);
} //end of the function WriteBrushList
//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
void PrintBrush (bspbrush_t *brush)
{
	int		i;

	printf ("brush: %p\n", brush);
	for (i=0;i<brush->numsides ; i++)
	{
		pw(brush->sides[i].winding);
		printf ("\n");
	} //end for
} //end of the function PrintBrush
//===========================================================================
// Sets the mins/maxs based on the windings
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
void BoundBrush (bspbrush_t *brush)
{
	int			i, j;
	winding_t	*w;

	ClearBounds (brush->mins, brush->maxs);
	for (i=0 ; i<brush->numsides ; i++)
	{
		w = brush->sides[i].winding;
		if (!w)
			continue;
		for (j=0 ; j<w->numpoints ; j++)
			AddPointToBounds (w->p[j], brush->mins, brush->maxs);
	}
} //end of the function BoundBrush
//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
void CreateBrushWindings (bspbrush_t *brush)
{
	int			i, j;
	winding_t	*w;
	side_t		*side;
	plane_t		*plane;

	for (i=0 ; i<brush->numsides ; i++)
	{
		side = &brush->sides[i];
		plane = &mapplanes[side->planenum];
		w = BaseWindingForPlane (plane->normal, plane->dist);
		for (j=0 ; j<brush->numsides && w; j++)
		{
			if (i == j)
				continue;
			if (brush->sides[j].flags & SFL_BEVEL)
				continue;
			plane = &mapplanes[brush->sides[j].planenum^1];
			ChopWindingInPlace (&w, plane->normal, plane->dist, 0); //CLIP_EPSILON);
		}

		side->winding = w;
	}

	BoundBrush (brush);
} //end of the function CreateBrushWindings
//===========================================================================
// Creates a new axial brush
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
bspbrush_t	*BrushFromBounds (vec3_t mins, vec3_t maxs)
{
	bspbrush_t *b;
	int i;
	vec3_t normal;
	vec_t dist;

	b = AllocBrush (6);
	b->numsides = 6;
	for (i=0 ; i<3 ; i++)
	{
		VectorClear (normal);
		normal[i] = 1;
		dist = maxs[i];
		b->sides[i].planenum = FindFloatPlane (normal, dist);

		normal[i] = -1;
		dist = -mins[i];
		b->sides[3+i].planenum = FindFloatPlane (normal, dist);
	}

	CreateBrushWindings (b);

	return b;
} //end of the function BrushFromBounds
//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
int BrushOutOfBounds(bspbrush_t *brush, vec3_t mins, vec3_t maxs, float epsilon)
{
	int i, j, n;
	winding_t *w;
	side_t *side;

	for (i = 0; i < brush->numsides; i++)
	{
		side = &brush->sides[i];
		w = side->winding;
		for (j = 0; j < w->numpoints; j++)
		{
			for (n = 0; n < 3; n++)
			{
				if (w->p[j][n] < (mins[n] + epsilon) || w->p[j][n] > (maxs[n] - epsilon)) return true;
			} //end for
		} //end for
	} //end for
	return false;
} //end of the function BrushOutOfBounds
//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
vec_t BrushVolume (bspbrush_t *brush)
{
	int i;
	winding_t *w;
	vec3_t corner;
	vec_t d, area, volume;
	plane_t *plane;

	if (!brush) return 0;

	// grab the first valid point as the corner
	w = NULL;
	for (i = 0; i < brush->numsides; i++)
	{
		w = brush->sides[i].winding;
		if (w) break;
	} //end for
	if (!w) return 0;
	VectorCopy (w->p[0], corner);

	// make tetrahedrons to all other faces
	volume = 0;
	for ( ; i < brush->numsides; i++)
	{
		w = brush->sides[i].winding;
		if (!w) continue;
		plane = &mapplanes[brush->sides[i].planenum];
		d = -(DotProduct (corner, plane->normal) - plane->dist);
		area = WindingArea(w);
		volume += d * area;
	} //end for

	volume /= 3;
	return volume;
} //end of the function BrushVolume
//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
int CountBrushList (bspbrush_t *brushes)
{
	int c;

	c = 0;
	for ( ; brushes; brushes = brushes->next) c++;
	return c;
} //end of the function CountBrushList
//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
node_t *AllocNode (void)
{
	node_t	*node;

	node = GetMemory(sizeof(*node));
	memset (node, 0, sizeof(*node));
	if (numthreads == 1)
	{
		c_nodememory += MemorySize(node);
	} //end if
	return node;
} //end of the function AllocNode
//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
bspbrush_t *AllocBrush (int numsides)
{
	bspbrush_t	*bb;
	int			c;

	c = (int)&(((bspbrush_t *)0)->sides[numsides]);
	bb = GetMemory(c);
	memset (bb, 0, c);
	if (numthreads == 1)
	{
		c_active_brushes++;
		c_brushmemory += MemorySize(bb);
		if (c_brushmemory > c_peak_brushmemory)
				c_peak_brushmemory = c_brushmemory;
	} //end if
	return bb;
} //end of the function AllocBrush
//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
void FreeBrush (bspbrush_t *brushes)
{
	int			i;

	for (i=0 ; i<brushes->numsides ; i++)
		if (brushes->sides[i].winding)
			FreeWinding(brushes->sides[i].winding);
	if (numthreads == 1)
	{
		c_active_brushes--;
		c_brushmemory -= MemorySize(brushes);
		if (c_brushmemory < 0) c_brushmemory = 0;
	} //end if
	FreeMemory(brushes);
} //end of the function FreeBrush
//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
void FreeBrushList (bspbrush_t *brushes)
{
	bspbrush_t	*next;