portals.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"
#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 = (portal_t*)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 qtrue 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 qfalse;	// to global outsideleaf

	c1 = ClusterContents(p->nodes[0]);
	c2 = ClusterContents(p->nodes[1]);

	if (!VisibleContents (c1^c2))
		return qtrue;

	if (c1 & (CONTENTS_Q2TRANSLUCENT|CONTENTS_DETAIL))
		c1 = 0;
	if (c2 & (CONTENTS_Q2TRANSLUCENT|CONTENTS_DETAIL))
		c2 = 0;

	if ( (c1|c2) & CONTENTS_SOLID )
		return qfalse;		// can't see through solid

	if (! (c1 ^ c2))
		return qtrue;		// identical on both sides

	if (!VisibleContents (c1^c2))
		return qtrue;
	return qfalse;
} //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 qfalse;

	// can flood through everything else
	return qtrue;
}


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

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 =.0f;
	int			side = 0;

	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 qfalse;
	//if the node is already occupied
	if (node->occupied) return qfalse;

	//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 qtrue;
} //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;
	qboolean inside;
	node_t *headnode;

	headnode = tree->headnode;
	Log_Print("------ FloodEntities -------\n");
	inside = qfalse;
	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;

		const char* 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 = qtrue;
						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 = qtrue;
			} //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 = qtrue;
	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