tree.cpp

/*
===========================================================================
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"

extern int c_nodes;
int	c_pruned;
int freedtreemem = 0;

void RemovePortalFromNode (portal_t *portal, node_t *l);

//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
node_t *NodeForPoint (node_t *node, vec3_t origin)
{
	plane_t	*plane;
	vec_t	d;

	while (node->planenum != PLANENUM_LEAF)
	{
		plane = &mapplanes[node->planenum];
		d = DotProduct (origin, plane->normal) - plane->dist;
		if (d >= 0)
			node = node->children[0];
		else
			node = node->children[1];
	}
	return node;
} //end of the function NodeForPoint
//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
void Tree_FreePortals_r (node_t *node)
{
	portal_t	*p, *nextp;
	int			s;

	// free children
	if (node->planenum != PLANENUM_LEAF)
	{
		Tree_FreePortals_r(node->children[0]);
		Tree_FreePortals_r(node->children[1]);
	}

	// free portals
	for (p = node->portals; p; p = nextp)
	{
		s = (p->nodes[1] == node);
		nextp = p->next[s];

		RemovePortalFromNode (p, p->nodes[!s]);
#ifdef ME
		if (p->winding) freedtreemem += MemorySize(p->winding);
		freedtreemem += MemorySize(p);
#endif //ME
		FreePortal(p);
	}
	node->portals = NULL;
} //end of the function Tree_FreePortals_r
//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
void Tree_Free_r (node_t *node)
{
//	face_t *f, *nextf;
	bspbrush_t *brush, *nextbrush;

	//free children
	if (node->planenum != PLANENUM_LEAF)
	{
		Tree_Free_r (node->children[0]);
		Tree_Free_r (node->children[1]);
	} //end if
	//free bspbrushes
//	FreeBrushList (node->brushlist);
	for (brush = node->brushlist; brush; brush = nextbrush)
	{
		nextbrush = brush->next;
#ifdef ME
		freedtreemem += MemorySize(brush);
#endif //ME
		FreeBrush(brush);
	} //end for
	node->brushlist = NULL;

	/*
	NOTE: only used when creating Q2 bsp
	// free faces
	for (f = node->faces; f; f = nextf)
	{
		nextf = f->next;
#ifdef ME
		if (f->w) freedtreemem += MemorySize(f->w);
		freedtreemem += sizeof(face_t);
#endif //ME
		FreeFace(f);
	} //end for
	*/

	// free the node
	if (node->volume)
	{
#ifdef ME
		freedtreemem += MemorySize(node->volume);
#endif //ME
		FreeBrush (node->volume);
	} //end if

	if (numthreads == 1) c_nodes--;
#ifdef ME
	freedtreemem += MemorySize(node);
#endif //ME
	FreeMemory(node);
} //end of the function Tree_Free_r
//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
void Tree_Free(tree_t *tree)
{
	//if no tree just return
	if (!tree) return;
	//
	freedtreemem = 0;
	//
	Tree_FreePortals_r(tree->headnode);
	Tree_Free_r(tree->headnode);
#ifdef ME
	freedtreemem += MemorySize(tree);
#endif //ME
	FreeMemory(tree);
#ifdef ME
	Log_Print("freed ");
	PrintMemorySize(freedtreemem);
	Log_Print(" of tree memory\n");
#endif //ME
} //end of the function Tree_Free
//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
tree_t *Tree_Alloc(void)
{
	tree_t	*tree;

	tree = (tree_t*)GetMemory(sizeof(*tree));
	memset (tree, 0, sizeof(*tree));
	ClearBounds (tree->mins, tree->maxs);

	return tree;
} //end of the function Tree_Alloc
//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
void Tree_Print_r (node_t *node, int depth)
{
	int		i;
	plane_t	*plane;
	bspbrush_t	*bb;

	for (i=0 ; i<depth ; i++)
		printf ("  ");
	if (node->planenum == PLANENUM_LEAF)
	{
		if (!node->brushlist)
			printf ("NULL\n");
		else
		{
			for (bb=node->brushlist ; bb ; bb=bb->next)
				printf ("%i ", bb->original->brushnum);
			printf ("\n");
		}
		return;
	}

	plane = &mapplanes[node->planenum];
	printf ("#%i (%5.2f %5.2f %5.2f):%5.2f\n", node->planenum,
		plane->normal[0], plane->normal[1], plane->normal[2],
		plane->dist);
	Tree_Print_r (node->children[0], depth+1);
	Tree_Print_r (node->children[1], depth+1);
} //end of the function Tree_Print_r
//===========================================================================
// NODES THAT DON'T SEPERATE DIFFERENT CONTENTS CAN BE PRUNED
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
void Tree_PruneNodes_r (node_t *node)
{
	bspbrush_t *b, *next;

	if (node->planenum == PLANENUM_LEAF) return;

	Tree_PruneNodes_r (node->children[0]);
	Tree_PruneNodes_r (node->children[1]);

	if (create_aas)
	{
		if ((node->children[0]->contents & CONTENTS_LADDER) ||
				(node->children[1]->contents & CONTENTS_LADDER)) return;
	}

	if ((node->children[0]->contents & CONTENTS_SOLID)
		&& (node->children[1]->contents & CONTENTS_SOLID))
	{
		if (node->faces)
			Error ("node->faces seperating CONTENTS_SOLID");
		if (node->children[0]->faces || node->children[1]->faces)
			Error ("!node->faces with children");
		// FIXME: free stuff
		node->planenum = PLANENUM_LEAF;
		node->contents = CONTENTS_SOLID;
		node->detail_seperator = qfalse;

		if (node->brushlist)
			Error ("PruneNodes: node->brushlist");
		// combine brush lists
		node->brushlist = node->children[1]->brushlist;

		for (b = node->children[0]->brushlist; b; b = next)
		{
			next = b->next;
			b->next = node->brushlist;
			node->brushlist = b;
		} //end for
		//free the child nodes
		FreeMemory(node->children[0]);
		FreeMemory(node->children[1]);
		//two nodes are cut away
		c_pruned += 2;
	} //end if
} //end of the function Tree_PruneNodes_r
//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
void Tree_PruneNodes(node_t *node)
{
	Log_Print("------- Prune Nodes --------\n");
	c_pruned = 0;
	Tree_PruneNodes_r(node);
	Log_Print("%5i pruned nodes\n", c_pruned);
} //end of the function Tree_PruneNodes