Quake-III-Arena

portals.c (33180B)

---

 /*
 ===========================================================================
 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"
 
 int		c_active_portals;
 int		c_peak_portals;
 int		c_boundary;
 int		c_boundary_sides;
 int		c_portalmemory;
 
 //portal_t *portallist = NULL;
 //===========================================================================
 //
 // Parameter:				-
 // Returns:					-
 // Changes Globals:		-
 //===========================================================================
 portal_t *AllocPortal (void)
 {
 	portal_t	*p;
 	
 	p = GetMemory(sizeof(portal_t));
 	memset (p, 0, sizeof(portal_t));
 
 	if (numthreads == 1)
 	{
 		c_active_portals++;
 		if (c_active_portals > c_peak_portals)
 		{
 			c_peak_portals = c_active_portals;
 		} //end if
 		c_portalmemory += MemorySize(p);	
 	} //end if
 
 //	p->nextportal = portallist;
 //	portallist = p;
 	
 	return p;
 } //end of the function AllocPortal
 //===========================================================================
 //
 // Parameter:				-
 // Returns:					-
 // Changes Globals:		-
 //===========================================================================
 void FreePortal (portal_t *p)
 {
 	if (p->winding) FreeWinding(p->winding);
 	if (numthreads == 1)
 	{
 		c_active_portals--;
 		c_portalmemory -= MemorySize(p);
 	} //end if
 	FreeMemory(p);
 } //end of the function FreePortal
 //===========================================================================
 // Returns the single content bit of the
 // strongest visible content present
 //
 // Parameter:				-
 // Returns:					-
 // Changes Globals:		-
 //===========================================================================
 int VisibleContents (int contents)
 {
 	int		i;
 
 	for (i=1 ; i<=LAST_VISIBLE_CONTENTS ; i<<=1)
 		if (contents & i )
 			return i;
 
 	return 0;
 } //end of the function VisibleContents
 //===========================================================================
 //
 // Parameter:				-
 // Returns:					-
 // Changes Globals:		-
 //===========================================================================
 int ClusterContents (node_t *node)
 {
 	int		c1, c2, c;
 
 	if (node->planenum == PLANENUM_LEAF)
 		return node->contents;
 
 	c1 = ClusterContents(node->children[0]);
 	c2 = ClusterContents(node->children[1]);
 	c = c1|c2;
 
 	// a cluster may include some solid detail areas, but
 	// still be seen into
 	if ( ! (c1&CONTENTS_SOLID) || ! (c2&CONTENTS_SOLID) )
 		c &= ~CONTENTS_SOLID;
 	return c;
 } //end of the function ClusterContents
 
 //===========================================================================
 // Returns true if the portal is empty or translucent, allowing
 // the PVS calculation to see through it.
 // The nodes on either side of the portal may actually be clusters,
 // not leaves, so all contents should be ored together
 //
 // Parameter:				-
 // Returns:					-
 // Changes Globals:		-
 //===========================================================================
 qboolean Portal_VisFlood (portal_t *p)
 {
 	int		c1, c2;
 
 	if (!p->onnode)
 		return false;	// to global outsideleaf
 
 	c1 = ClusterContents(p->nodes[0]);
 	c2 = ClusterContents(p->nodes[1]);
 
 	if (!VisibleContents (c1^c2))
 		return true;
 
 	if (c1 & (CONTENTS_Q2TRANSLUCENT|CONTENTS_DETAIL))
 		c1 = 0;
 	if (c2 & (CONTENTS_Q2TRANSLUCENT|CONTENTS_DETAIL))
 		c2 = 0;
 
 	if ( (c1|c2) & CONTENTS_SOLID )
 		return false;		// can't see through solid
 
 	if (! (c1 ^ c2))
 		return true;		// identical on both sides
 
 	if (!VisibleContents (c1^c2))
 		return true;
 	return false;
 } //end of the function Portal_VisFlood
 //===========================================================================
 // The entity flood determines which areas are
 // "outside" on the map, which are then filled in.
 // Flowing from side s to side !s
 //
 // Parameter:				-
 // Returns:					-
 // Changes Globals:		-
 //===========================================================================
 qboolean Portal_EntityFlood (portal_t *p, int s)
 {
 	if (p->nodes[0]->planenum != PLANENUM_LEAF
 		|| p->nodes[1]->planenum != PLANENUM_LEAF)
 		Error ("Portal_EntityFlood: not a leaf");
 
 	// can never cross to a solid 
 	if ( (p->nodes[0]->contents & CONTENTS_SOLID)
 	|| (p->nodes[1]->contents & CONTENTS_SOLID) )
 		return false;
 
 	// can flood through everything else
 	return true;
 }
 
 
 //=============================================================================
 
 int		c_tinyportals;
 
 //===========================================================================
 //
 // Parameter:				-
 // Returns:					-
 // Changes Globals:		-
 //===========================================================================
 void AddPortalToNodes (portal_t *p, node_t *front, node_t *back)
 {
 	if (p->nodes[0] || p->nodes[1])
 		Error ("AddPortalToNode: allready included");
 
 	p->nodes[0] = front;
 	p->next[0] = front->portals;
 	front->portals = p;
 	
 	p->nodes[1] = back;
 	p->next[1] = back->portals;
 	back->portals = p;
 } //end of the function AddPortalToNodes
 //===========================================================================
 //
 // Parameter:				-
 // Returns:					-
 // Changes Globals:		-
 //===========================================================================
 void RemovePortalFromNode (portal_t *portal, node_t *l)
 {
 	portal_t	**pp, *t;
 
 	int s, i, n;
 	portal_t *p;
 	portal_t *portals[4096];
 	
 // remove reference to the current portal
 	pp = &l->portals;
 	while (1)
 	{
 		t = *pp;
 		if (!t)
 			Error ("RemovePortalFromNode: portal not in leaf");	
 
 		if ( t == portal )
 			break;
 
 		if (t->nodes[0] == l)
 			pp = &t->next[0];
 		else if (t->nodes[1] == l)
 			pp = &t->next[1];
 		else
 			Error ("RemovePortalFromNode: portal not bounding leaf");
 	}
 	
 	if (portal->nodes[0] == l)
 	{
 		*pp = portal->next[0];
 		portal->nodes[0] = NULL;
 	} //end if
 	else if (portal->nodes[1] == l)
 	{
 		*pp = portal->next[1];	
 		portal->nodes[1] = NULL;
 	} //end else if
 	else
 	{
 		Error("RemovePortalFromNode: mislinked portal");
 	} //end else
 //#ifdef ME
 	n = 0;
 	for (p = l->portals; p; p = p->next[s])
 	{
 		for (i = 0; i < n; i++)
 		{
 			if (p == portals[i]) Error("RemovePortalFromNode: circular linked\n");
 		} //end for
 		if (p->nodes[0] != l && p->nodes[1] != l)
 		{
 			Error("RemovePortalFromNodes: portal does not belong to node\n");
 		} //end if
 		portals[n] = p;
 		s = (p->nodes[1] == l);
 //		if (++n >= 4096) Error("RemovePortalFromNode: more than 4096 portals\n");
 	} //end for
 //#endif
 } //end of the function RemovePortalFromNode
 //===========================================================================
 //
 // Parameter:				-
 // Returns:					-
 // Changes Globals:		-
 //===========================================================================
 void PrintPortal (portal_t *p)
 {
 	int			i;
 	winding_t	*w;
 	
 	w = p->winding;
 	for (i=0 ; i<w->numpoints ; i++)
 		printf ("(%5.0f,%5.0f,%5.0f)\n",w->p[i][0]
 		, w->p[i][1], w->p[i][2]);
 } //end of the function PrintPortal
 //===========================================================================
 // The created portals will face the global outside_node
 //
 // Parameter:				-
 // Returns:					-
 // Changes Globals:		-
 //===========================================================================
 #define	SIDESPACE	8
 
 void MakeHeadnodePortals (tree_t *tree)
 {
 	vec3_t		bounds[2];
 	int			i, j, n;
 	portal_t	*p, *portals[6];
 	plane_t		bplanes[6], *pl;
 	node_t *node;
 
 	node = tree->headnode;
 
 // pad with some space so there will never be null volume leaves
 	for (i=0 ; i<3 ; i++)
 	{
 		bounds[0][i] = tree->mins[i] - SIDESPACE;
 		bounds[1][i] = tree->maxs[i] + SIDESPACE;
 		if ( bounds[0][i] > bounds[1][i] ) {
 			Error("empty BSP tree");
 		}
 	}
 	
 	tree->outside_node.planenum = PLANENUM_LEAF;
 	tree->outside_node.brushlist = NULL;
 	tree->outside_node.portals = NULL;
 	tree->outside_node.contents = 0;
 
 	for (i=0 ; i<3 ; i++)
 		for (j=0 ; j<2 ; j++)
 		{
 			n = j*3 + i;
 
 			p = AllocPortal ();
 			portals[n] = p;
 			
 			pl = &bplanes[n];
 			memset (pl, 0, sizeof(*pl));
 			if (j)
 			{
 				pl->normal[i] = -1;
 				pl->dist = -bounds[j][i];
 			}
 			else
 			{
 				pl->normal[i] = 1;
 				pl->dist = bounds[j][i];
 			}
 			p->plane = *pl;
 			p->winding = BaseWindingForPlane (pl->normal, pl->dist);
 			AddPortalToNodes (p, node, &tree->outside_node);
 		}
 		
 // clip the basewindings by all the other planes
 	for (i=0 ; i<6 ; i++)
 	{
 		for (j=0 ; j<6 ; j++)
 		{
 			if (j == i) continue;
 			ChopWindingInPlace (&portals[i]->winding, bplanes[j].normal, bplanes[j].dist, ON_EPSILON);
 		} //end for
 	} //end for
 } //end of the function MakeHeadNodePortals
 //===========================================================================
 //
 // Parameter:				-
 // Returns:					-
 // Changes Globals:		-
 //===========================================================================
 #define	BASE_WINDING_EPSILON		0.001
 #define	SPLIT_WINDING_EPSILON	0.001
 
 winding_t *BaseWindingForNode (node_t *node)
 {
 	winding_t	*w;
 	node_t		*n;
 	plane_t		*plane;
 	vec3_t		normal;
 	vec_t		dist;
 
 	w = BaseWindingForPlane (mapplanes[node->planenum].normal
 		, mapplanes[node->planenum].dist);
 
 	// clip by all the parents
 	for (n=node->parent ; n && w ; )
 	{
 		plane = &mapplanes[n->planenum];
 
 		if (n->children[0] == node)
 		{	// take front
 			ChopWindingInPlace (&w, plane->normal, plane->dist, BASE_WINDING_EPSILON);
 		}
 		else
 		{	// take back
 			VectorSubtract (vec3_origin, plane->normal, normal);
 			dist = -plane->dist;
 			ChopWindingInPlace (&w, normal, dist, BASE_WINDING_EPSILON);
 		}
 		node = n;
 		n = n->parent;
 	}
 
 	return w;
 } //end of the function BaseWindingForNode
 //===========================================================================
 // create the new portal by taking the full plane winding for the cutting
 // plane and clipping it by all of parents of this node
 //
 // Parameter:				-
 // Returns:					-
 // Changes Globals:		-
 //===========================================================================
 qboolean WindingIsTiny (winding_t *w);
 
 void MakeNodePortal (node_t *node)
 {
 	portal_t	*new_portal, *p;
 	winding_t	*w;
 	vec3_t		normal;
 	float		dist;
 	int			side;
 
 	w = BaseWindingForNode (node);
 
 	// clip the portal by all the other portals in the node
 	for (p = node->portals; p && w; p = p->next[side])	
 	{
 		if (p->nodes[0] == node)
 		{
 			side = 0;
 			VectorCopy (p->plane.normal, normal);
 			dist = p->plane.dist;
 		} //end if
 		else if (p->nodes[1] == node)
 		{
 			side = 1;
 			VectorSubtract (vec3_origin, p->plane.normal, normal);
 			dist = -p->plane.dist;
 		} //end else if
 		else
 		{
 			Error ("MakeNodePortal: mislinked portal");
 		} //end else
 		ChopWindingInPlace (&w, normal, dist, 0.1);
 	} //end for
 
 	if (!w)
 	{
 		return;
 	} //end if
 
 	if (WindingIsTiny (w))
 	{
 		c_tinyportals++;
 		FreeWinding(w);
 		return;
 	} //end if
 
 #ifdef DEBUG
 /* //NOTE: don't use this winding ok check
 	// all the invalid windings only have a degenerate edge
 	if (WindingError(w))
 	{
 		Log_Print("MakeNodePortal: %s\n", WindingErrorString());
 		FreeWinding(w);
 		return;
 	} //end if*/
 #endif //DEBUG
 
 
 	new_portal = AllocPortal();
 	new_portal->plane = mapplanes[node->planenum];
 
 #ifdef ME
 	new_portal->planenum = node->planenum;
 #endif //ME
 
 	new_portal->onnode = node;
 	new_portal->winding = w;
 	AddPortalToNodes (new_portal, node->children[0], node->children[1]);
 } //end of the function MakeNodePortal
 //===========================================================================
 // Move or split the portals that bound node so that the node's
 // children have portals instead of node.
 //
 // Parameter:				-
 // Returns:					-
 // Changes Globals:		-
 //===========================================================================
 void SplitNodePortals (node_t *node)
 {
 	portal_t	*p, *next_portal, *new_portal;
 	node_t *f, *b, *other_node;
 	int side;
 	plane_t *plane;
 	winding_t *frontwinding, *backwinding;
 
 	plane = &mapplanes[node->planenum];
 	f = node->children[0];
 	b = node->children[1];
 
 	for (p = node->portals ; p ; p = next_portal)	
 	{
 		if (p->nodes[0] == node) side = 0;
 		else if (p->nodes[1] == node) side = 1;
 		else Error ("SplitNodePortals: mislinked portal");
 		next_portal = p->next[side];
 
 		other_node = p->nodes[!side];
 		RemovePortalFromNode (p, p->nodes[0]);
 		RemovePortalFromNode (p, p->nodes[1]);
 
 //
 // cut the portal into two portals, one on each side of the cut plane
 //
 		ClipWindingEpsilon (p->winding, plane->normal, plane->dist,
 				SPLIT_WINDING_EPSILON, &frontwinding, &backwinding);
 
 		if (frontwinding && WindingIsTiny(frontwinding))
 		{
 			FreeWinding (frontwinding);
 			frontwinding = NULL;
 			c_tinyportals++;
 		} //end if
 
 		if (backwinding && WindingIsTiny(backwinding))
 		{
 			FreeWinding (backwinding);
 			backwinding = NULL;
 			c_tinyportals++;
 		} //end if
 
 #ifdef DEBUG
 /* 	//NOTE: don't use this winding ok check
 		// all the invalid windings only have a degenerate edge
 		if (frontwinding && WindingError(frontwinding))
 		{
 			Log_Print("SplitNodePortals: front %s\n", WindingErrorString());
 			FreeWinding(frontwinding);
 			frontwinding = NULL;
 		} //end if
 		if (backwinding && WindingError(backwinding))
 		{
 			Log_Print("SplitNodePortals: back %s\n", WindingErrorString());
 			FreeWinding(backwinding);
 			backwinding = NULL;
 		} //end if*/
 #endif //DEBUG
 
 		if (!frontwinding && !backwinding)
 		{	// tiny windings on both sides
 			continue;
 		}
 
 		if (!frontwinding)
 		{
 			FreeWinding (backwinding);
 			if (side == 0) AddPortalToNodes (p, b, other_node);
 			else AddPortalToNodes (p, other_node, b);
 			continue;
 		}
 		if (!backwinding)
 		{
 			FreeWinding (frontwinding);
 			if (side == 0) AddPortalToNodes (p, f, other_node);
 			else AddPortalToNodes (p, other_node, f);
 			continue;
 		}
 		
 	// the winding is split
 		new_portal = AllocPortal();
 		*new_portal = *p;
 		new_portal->winding = backwinding;
 		FreeWinding (p->winding);
 		p->winding = frontwinding;
 
 		if (side == 0)
 		{
 			AddPortalToNodes (p, f, other_node);
 			AddPortalToNodes (new_portal, b, other_node);
 		} //end if
 		else
 		{
 			AddPortalToNodes (p, other_node, f);
 			AddPortalToNodes (new_portal, other_node, b);
 		} //end else
 	}
 
 	node->portals = NULL;
 } //end of the function SplitNodePortals
 //===========================================================================
 //
 // Parameter:				-
 // Returns:					-
 // Changes Globals:		-
 //===========================================================================
 void CalcNodeBounds (node_t *node)
 {
 	portal_t	*p;
 	int			s;
 	int			i;
 
 	// calc mins/maxs for both leaves and nodes
 	ClearBounds (node->mins, node->maxs);
 	for (p = node->portals ; p ; p = p->next[s])	
 	{
 		s = (p->nodes[1] == node);
 		for (i=0 ; i<p->winding->numpoints ; i++)
 			AddPointToBounds (p->winding->p[i], node->mins, node->maxs);
 	}
 } //end of the function CalcNodeBounds
 //===========================================================================
 //
 // Parameter:				-
 // Returns:					-
 // Changes Globals:		-
 //===========================================================================
 int c_numportalizednodes;
 
 void MakeTreePortals_r (node_t *node)
 {
 	int		i;
 
 #ifdef ME
 	qprintf("\r%6d", ++c_numportalizednodes);
 	if (cancelconversion) return;
 #endif //ME
 
 	CalcNodeBounds (node);
 	if (node->mins[0] >= node->maxs[0])
 	{
 		Log_Print("WARNING: node without a volume\n");
 	}
 
 	for (i=0 ; i<3 ; i++)
 	{
 		if (node->mins[i] < -MAX_MAP_BOUNDS || node->maxs[i] > MAX_MAP_BOUNDS)
 		{
 			Log_Print("WARNING: node with unbounded volume\n");
 			break;
 		}
 	}
 	if (node->planenum == PLANENUM_LEAF)
 		return;
 
 	MakeNodePortal (node);
 	SplitNodePortals (node);
 
 	MakeTreePortals_r (node->children[0]);
 	MakeTreePortals_r (node->children[1]);
 } //end of the function MakeTreePortals_r
 //===========================================================================
 //
 // Parameter:				-
 // Returns:					-
 // Changes Globals:		-
 //===========================================================================
 void MakeTreePortals(tree_t *tree)
 {
 
 #ifdef ME
 	Log_Print("---- Node Portalization ----\n");
 	c_numportalizednodes = 0;
 	c_portalmemory = 0;
 	qprintf("%6d nodes portalized", c_numportalizednodes);
 #endif //ME
 
 	MakeHeadnodePortals(tree);
 	MakeTreePortals_r(tree->headnode);
 
 #ifdef ME
 	qprintf("\n");
 	Log_Write("%6d nodes portalized\r\n", c_numportalizednodes);
 	Log_Print("%6d tiny portals\r\n", c_tinyportals);
 	Log_Print("%6d KB of portal memory\r\n", c_portalmemory >> 10);
 	Log_Print("%6i KB of winding memory\r\n", WindingMemory() >> 10);
 #endif //ME
 } //end of the function MakeTreePortals
 
 /*
 =========================================================
 
 FLOOD ENTITIES
 
 =========================================================
 */
 //#define P_NODESTACK
 
 node_t *p_firstnode;
 node_t *p_lastnode;
 
 //===========================================================================
 //
 // Parameter:				-
 // Returns:					-
 // Changes Globals:		-
 //===========================================================================
 #ifdef P_NODESTACK
 void P_AddNodeToList(node_t *node)
 {
 	node->next = p_firstnode;
 	p_firstnode = node;
 	if (!p_lastnode) p_lastnode = node;
 } //end of the function P_AddNodeToList
 #else //it's a node queue
 //add the node to the end of the node list
 void P_AddNodeToList(node_t *node)
 {
 	node->next = NULL;
 	if (p_lastnode) p_lastnode->next = node;
 	else p_firstnode = node;
 	p_lastnode = node;
 } //end of the function P_AddNodeToList
 #endif //P_NODESTACK
 //===========================================================================
 // get the first node from the front of the node list
 //
 // Parameter:				-
 // Returns:					-
 // Changes Globals:		-
 //===========================================================================
 node_t *P_NextNodeFromList(void)
 {
 	node_t *node;
 
 	node = p_firstnode;
 	if (p_firstnode) p_firstnode = p_firstnode->next;
 	if (!p_firstnode) p_lastnode = NULL;
 	return node;
 } //end of the function P_NextNodeFromList
 //===========================================================================
 //
 // Parameter:				-
 // Returns:					-
 // Changes Globals:		-
 //===========================================================================
 void FloodPortals(node_t *firstnode)
 {
 	node_t *node;
 	portal_t *p;
 	int s;
 
 	firstnode->occupied = 1;
 	P_AddNodeToList(firstnode);
 
 	for (node = P_NextNodeFromList(); node; node = P_NextNodeFromList())
 	{
 		for (p = node->portals; p; p = p->next[s])
 		{
 			s = (p->nodes[1] == node);
 			//if the node at the other side of the portal is occupied already
 			if (p->nodes[!s]->occupied) continue;
 			//if it isn't possible to flood through this portal
 			if (!Portal_EntityFlood(p, s)) continue;
 			//
 			p->nodes[!s]->occupied = node->occupied + 1;
 			//
 			P_AddNodeToList(p->nodes[!s]);
 		} //end for
 	} //end for
 } //end of the function FloodPortals
 //===========================================================================
 //
 // Parameter:				-
 // Returns:					-
 // Changes Globals:		-
 //===========================================================================
 int numrec;
 
 void FloodPortals_r (node_t *node, int dist)
 {
 	portal_t *p;
 	int s;
 //	int i;
 
 	Log_Print("\r%6d", ++numrec);
 
 	if (node->occupied) Error("FloodPortals_r: node already occupied\n");
 	if (!node)
 	{
 		Error("FloodPortals_r: NULL node\n");
 	} //end if*/
 	node->occupied = dist;
 
 	for (p = node->portals; p; p = p->next[s])
 	{
 		s = (p->nodes[1] == node);
 		//if the node at the other side of the portal is occupied already
 		if (p->nodes[!s]->occupied) continue;
 		//if it isn't possible to flood through this portal
 		if (!Portal_EntityFlood(p, s)) continue;
 		//flood recursively through the current portal
 		FloodPortals_r(p->nodes[!s], dist+1);
 	} //end for
 	Log_Print("\r%6d", --numrec);
 } //end of the function FloodPortals_r
 //===========================================================================
 //
 // Parameter:				-
 // Returns:					-
 // Changes Globals:		-
 //===========================================================================
 qboolean PlaceOccupant (node_t *headnode, vec3_t origin, entity_t *occupant)
 {
 	node_t *node;
 	vec_t	d;
 	plane_t *plane;
 
 	//find the leaf to start in
 	node = headnode;
 	while(node->planenum != PLANENUM_LEAF)
 	{
 		if (node->planenum < 0 || node->planenum > nummapplanes)
 		{
 			Error("PlaceOccupant: invalid node->planenum\n");
 		} //end if
 		plane = &mapplanes[node->planenum];
 		d = DotProduct(origin, plane->normal) - plane->dist;
 		if (d >= 0) node = node->children[0];
 		else node = node->children[1];
 		if (!node)
 		{
 			Error("PlaceOccupant: invalid child %d\n", d < 0);
 		} //end if
 	} //end while
 	//don't start in solid
 //	if (node->contents == CONTENTS_SOLID)
 	//ME: replaced because in LeafNode in brushbsp.c
 	//    some nodes have contents solid with other contents
 	if (node->contents & CONTENTS_SOLID) return false;
 	//if the node is already occupied
 	if (node->occupied) return false;
 
 	//place the occupant in the first leaf
 	node->occupant = occupant;
 
 	numrec = 0;
 //	Log_Print("%6d recurses", numrec);
 //	FloodPortals_r(node, 1);
 //	Log_Print("\n");
 	FloodPortals(node);
 
 	return true;
 } //end of the function PlaceOccupant
 //===========================================================================
 // Marks all nodes that can be reached by entites
 //
 // Parameter:				-
 // Returns:					-
 // Changes Globals:		-
 //===========================================================================
 qboolean FloodEntities (tree_t *tree)
 {
 	int i;
 	int x, y;
 	vec3_t origin;
 	char *cl;
 	qboolean inside;
 	node_t *headnode;
 
 	headnode = tree->headnode;
 	Log_Print("------ FloodEntities -------\n");
 	inside = false;
 	tree->outside_node.occupied = 0;
 
 	//start at entity 1 not the world ( = 0)
 	for (i = 1; i < num_entities; i++)
 	{
 		GetVectorForKey(&entities[i], "origin", origin);
 		if (VectorCompare(origin, vec3_origin)) continue;
 
 		cl = ValueForKey(&entities[i], "classname");
 		origin[2] += 1;	//so objects on floor are ok
 
 //		Log_Print("flooding from entity %d: %s\n", i, cl);
 		//nudge playerstart around if needed so clipping hulls allways
 		//have a valid point
 		if (!strcmp(cl, "info_player_start"))
 		{
 			for (x = -16; x <= 16; x += 16)
 			{
 				for (y = -16; y <= 16; y += 16)
 				{
 					origin[0] += x;
 					origin[1] += y;
 					if (PlaceOccupant(headnode, origin, &entities[i]))
 					{
 						inside = true;
 						x = 999; //stop for this info_player_start
 						break;
 					} //end if
 					origin[0] -= x;
 					origin[1] -= y;
 				} //end for
 			} //end for
 		} //end if
 		else
 		{
 			if (PlaceOccupant(headnode, origin, &entities[i]))
 			{
 				inside = true;
 			} //end if
 		} //end else
 	} //end for
 
 	if (!inside)
 	{
 		Log_Print("WARNING: no entities inside\n");
 	} //end if
 	else if (tree->outside_node.occupied)
 	{
 		Log_Print("WARNING: entity reached from outside\n");
 	} //end else if
 
 	return (qboolean)(inside && !tree->outside_node.occupied);
 } //end of the function FloodEntities
 
 /*
 =========================================================
 
 FILL OUTSIDE
 
 =========================================================
 */
 
 int c_outside;
 int c_inside;
 int c_solid;
 
 //===========================================================================
 //
 // Parameter:				-
 // Returns:					-
 // Changes Globals:		-
 //===========================================================================
 void FillOutside_r (node_t *node)
 {
 	if (node->planenum != PLANENUM_LEAF)
 	{
 		FillOutside_r (node->children[0]);
 		FillOutside_r (node->children[1]);
 		return;
 	} //end if
 	// anything not reachable by an entity
 	// can be filled away (by setting solid contents)
 	if (!node->occupied)
 	{
 		if (!(node->contents & CONTENTS_SOLID))
 		{
 			c_outside++;
 			node->contents |= CONTENTS_SOLID;
 		} //end if
 		else
 		{
 			c_solid++;
 		} //end else
 	} //end if
 	else
 	{
 		c_inside++;
 	} //end else
 } //end of the function FillOutside_r
 //===========================================================================
 // Fill all nodes that can't be reached by entities
 //
 // Parameter:				-
 // Returns:					-
 // Changes Globals:		-
 //===========================================================================
 void FillOutside (node_t *headnode)
 {
 	c_outside = 0;
 	c_inside = 0;
 	c_solid = 0;
 	Log_Print("------- FillOutside --------\n");
 	FillOutside_r (headnode);
 	Log_Print("%5i solid leaves\n", c_solid);
 	Log_Print("%5i leaves filled\n", c_outside);
 	Log_Print("%5i inside leaves\n", c_inside);
 } //end of the function FillOutside
 
 /*
 =========================================================
 
 FLOOD AREAS
 
 =========================================================
 */
 
 int		c_areas;
 
 //===========================================================================
 //
 // Parameter:				-
 // Returns:					-
 // Changes Globals:		-
 //===========================================================================
 void FloodAreas_r (node_t *node)
 {
 	portal_t	*p;
 	int			s;
 	bspbrush_t	*b;
 	entity_t	*e;
 
 	if (node->contents == CONTENTS_AREAPORTAL)
 	{
 		// this node is part of an area portal
 		b = node->brushlist;
 		e = &entities[b->original->entitynum];
 
 		// if the current area has allready touched this
 		// portal, we are done
 		if (e->portalareas[0] == c_areas || e->portalareas[1] == c_areas)
 			return;
 
 		// note the current area as bounding the portal
 		if (e->portalareas[1])
 		{
 			Log_Print("WARNING: areaportal entity %i touches > 2 areas\n", b->original->entitynum);
 			return;
 		}
 		if (e->portalareas[0])
 			e->portalareas[1] = c_areas;
 		else
 			e->portalareas[0] = c_areas;
 
 		return;
 	} //end if
 
 	if (node->area)
 		return;		// allready got it
 	node->area = c_areas;
 
 	for (p=node->portals ; p ; p = p->next[s])
 	{
 		s = (p->nodes[1] == node);
 #if 0
 		if (p->nodes[!s]->occupied)
 			continue;
 #endif
 		if (!Portal_EntityFlood (p, s))
 			continue;
 
 		FloodAreas_r (p->nodes[!s]);
 	} //end for
 } //end of the function FloodAreas_r
 //===========================================================================
 // Just decend the tree, and for each node that hasn't had an
 // area set, flood fill out from there
 //
 // Parameter:				-
 // Returns:					-
 // Changes Globals:		-
 //===========================================================================
 void FindAreas_r (node_t *node)
 {
 	if (node->planenum != PLANENUM_LEAF)
 	{
 		FindAreas_r (node->children[0]);
 		FindAreas_r (node->children[1]);
 		return;
 	}
 
 	if (node->area)
 		return;		// allready got it
 
 	if (node->contents & CONTENTS_SOLID)
 		return;
 
 	if (!node->occupied)
 		return;			// not reachable by entities
 
 	// area portals are allways only flooded into, never
 	// out of
 	if (node->contents == CONTENTS_AREAPORTAL)
 		return;
 
 	c_areas++;
 	FloodAreas_r (node);
 } //end of the function FindAreas_r
 //===========================================================================
 // Just decend the tree, and for each node that hasn't had an
 // area set, flood fill out from there
 //
 // Parameter:				-
 // Returns:					-
 // Changes Globals:		-
 //===========================================================================
 void SetAreaPortalAreas_r (node_t *node)
 {
 	bspbrush_t	*b;
 	entity_t	*e;
 
 	if (node->planenum != PLANENUM_LEAF)
 	{
 		SetAreaPortalAreas_r (node->children[0]);
 		SetAreaPortalAreas_r (node->children[1]);
 		return;
 	} //end if
 
 	if (node->contents == CONTENTS_AREAPORTAL)
 	{
 		if (node->area)
 			return;		// allready set
 
 		b = node->brushlist;
 		e = &entities[b->original->entitynum];
 		node->area = e->portalareas[0];
 		if (!e->portalareas[1])
 		{
 			Log_Print("WARNING: areaportal entity %i doesn't touch two areas\n", b->original->entitynum);
 			return;
 		} //end if
 	} //end if
 } //end of the function SetAreaPortalAreas_r
 //===========================================================================
 //
 // Parameter:				-
 // Returns:					-
 // Changes Globals:		-
 //===========================================================================
 /*
 void EmitAreaPortals(node_t *headnode)
 {
 	int				i, j;
 	entity_t		*e;
 	dareaportal_t	*dp;
 
 	if (c_areas > MAX_MAP_AREAS)
 		Error ("MAX_MAP_AREAS");
 	numareas = c_areas+1;
 	numareaportals = 1;		// leave 0 as an error
 
 	for (i=1 ; i<=c_areas ; i++)
 	{
 		dareas[i].firstareaportal = numareaportals;
 		for (j=0 ; j<num_entities ; j++)
 		{
 			e = &entities[j];
 			if (!e->areaportalnum)
 				continue;
 			dp = &dareaportals[numareaportals];
 			if (e->portalareas[0] == i)
 			{
 				dp->portalnum = e->areaportalnum;
 				dp->otherarea = e->portalareas[1];
 				numareaportals++;
 			} //end if
 			else if (e->portalareas[1] == i)
 			{
 				dp->portalnum = e->areaportalnum;
 				dp->otherarea = e->portalareas[0];
 				numareaportals++;
 			} //end else if
 		} //end for
 		dareas[i].numareaportals = numareaportals - dareas[i].firstareaportal;
 	} //end for
 
 	Log_Print("%5i numareas\n", numareas);
 	Log_Print("%5i numareaportals\n", numareaportals);
 } //end of the function EmitAreaPortals
 */
 //===========================================================================
 // Mark each leaf with an area, bounded by CONTENTS_AREAPORTAL
 //
 // Parameter:				-
 // Returns:					-
 // Changes Globals:		-
 //===========================================================================
 void FloodAreas (tree_t *tree)
 {
 	Log_Print("--- FloodAreas ---\n");
 	FindAreas_r (tree->headnode);
 	SetAreaPortalAreas_r (tree->headnode);
 	Log_Print("%5i areas\n", c_areas);
 } //end of the function FloodAreas
 //===========================================================================
 // Finds a brush side to use for texturing the given portal
 //
 // Parameter:				-
 // Returns:					-
 // Changes Globals:		-
 //===========================================================================
 void FindPortalSide (portal_t *p)
 {
 	int			viscontents;
 	bspbrush_t	*bb;
 	mapbrush_t	*brush;
 	node_t		*n;
 	int			i,j;
 	int			planenum;
 	side_t		*side, *bestside;
 	float		dot, bestdot;
 	plane_t		*p1, *p2;
 
 	// decide which content change is strongest
 	// solid > lava > water, etc
 	viscontents = VisibleContents (p->nodes[0]->contents ^ p->nodes[1]->contents);
 	if (!viscontents)
 		return;
 
 	planenum = p->onnode->planenum;
 	bestside = NULL;
 	bestdot = 0;
 
 	for (j=0 ; j<2 ; j++)
 	{
 		n = p->nodes[j];
 		p1 = &mapplanes[p->onnode->planenum];
 		for (bb=n->brushlist ; bb ; bb=bb->next)
 		{
 			brush = bb->original;
 			if ( !(brush->contents & viscontents) )
 				continue;
 			for (i=0 ; i<brush->numsides ; i++)
 			{
 				side = &brush->original_sides[i];
 				if (side->flags & SFL_BEVEL)
 					continue;
 				if (side->texinfo == TEXINFO_NODE)
 					continue;		// non-visible
 				if ((side->planenum&~1) == planenum)
 				{	// exact match
 					bestside = &brush->original_sides[i];
 					goto gotit;
 				} //end if
 				// see how close the match is
 				p2 = &mapplanes[side->planenum&~1];
 				dot = DotProduct (p1->normal, p2->normal);
 				if (dot > bestdot)
 				{
 					bestdot = dot;
 					bestside = side;
 				} //end if
 			} //end for
 		} //end for
 	} //end for
 
 gotit:
 	if (!bestside)
 		Log_Print("WARNING: side not found for portal\n");
 
 	p->sidefound = true;
 	p->side = bestside;
 } //end of the function FindPortalSide
 //===========================================================================
 //
 // Parameter:				-
 // Returns:					-
 // Changes Globals:		-
 //===========================================================================
 void MarkVisibleSides_r (node_t *node)
 {
 	portal_t *p;
 	int s;
 
 	if (node->planenum != PLANENUM_LEAF)
 	{
 		MarkVisibleSides_r (node->children[0]);
 		MarkVisibleSides_r (node->children[1]);
 		return;
 	} //end if
 
 	// empty leaves are never boundary leaves
 	if (!node->contents) return;
 
 	// see if there is a visible face
 	for (p=node->portals ; p ; p = p->next[!s])
 	{
 		s = (p->nodes[0] == node);
 		if (!p->onnode)
 			continue;		// edge of world
 		if (!p->sidefound)
 			FindPortalSide (p);
 		if (p->side)
 			p->side->flags |= SFL_VISIBLE;
 	} //end for
 } //end of the function MarkVisibleSides_r
 //===========================================================================
 //
 // Parameter:				-
 // Returns:					-
 // Changes Globals:		-
 //===========================================================================
 void MarkVisibleSides(tree_t *tree, int startbrush, int endbrush)
 {
 	int		i, j;
 	mapbrush_t	*mb;
 	int		numsides;
 
 	Log_Print("--- MarkVisibleSides ---\n");
 
 	// clear all the visible flags
 	for (i=startbrush ; i<endbrush ; i++)
 	{
 		mb = &mapbrushes[i];
 
 		numsides = mb->numsides;
 		for (j=0 ; j<numsides ; j++)
 			mb->original_sides[j].flags &= ~SFL_VISIBLE;
 	}
 
 	// set visible flags on the sides that are used by portals
 	MarkVisibleSides_r (tree->headnode);
 } //end of the function MarkVisibleSides