/*
===========================================================================

Return to Castle Wolfenstein single player GPL Source Code
Copyright (C) 1999-2010 id Software LLC, a ZeniMax Media company. 

This file is part of the Return to Castle Wolfenstein single player GPL Source Code (“RTCW SP Source Code”).  

RTCW SP 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 3 of the License, or
(at your option) any later version.

RTCW SP 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 RTCW SP Source Code.  If not, see <http://www.gnu.org/licenses/>.

In addition, the RTCW SP Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the RTCW SP Source Code.  If not, please request a copy in writing from id Software at the address below.

If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.

===========================================================================
*/

//===========================================================================
//
// Name:			Portals
// Function:		partalizing a bsp tree, flooding through portals
// Programmer:		id Software & Mr Elusive (MrElusive@worldentity.com)
// Last update:		1999-08-10
// Tab Size:		3
//===========================================================================

#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;
	}

	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 = 0;       // TTimo: init
	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 = 0; // TTimo: init
	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( "\r%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