Fix line endings. WHAMMY.

1 files changed, 1684 insertions, 1684 deletions

diff --git a/mp/src/utils/vbsp/portals.cpp b/mp/src/utils/vbsp/portals.cpp
index ec2a2695..6c59cffa 100644
--- a/mp/src/utils/vbsp/portals.cpp
+++ b/mp/src/utils/vbsp/portals.cpp
@@ -1,1684 +1,1684 @@
-//========= Copyright Valve Corporation, All rights reserved. ============//

-//

-// Purpose: 

-//

-// $NoKeywords: $

-//

-//=============================================================================//

-

-#include "vbsp.h"

-#include "utlvector.h"

-#include "mathlib/vmatrix.h"

-#include "iscratchpad3d.h"

-#include "csg.h"

-#include "fmtstr.h"

-

-int		c_active_portals;

-int		c_peak_portals;

-int		c_boundary;

-int		c_boundary_sides;

-

-/*

-===========

-AllocPortal

-===========

-*/

-portal_t *AllocPortal (void)

-{

-	static int s_PortalCount = 0;

-

-	portal_t	*p;

-	

-	if (numthreads == 1)

-		c_active_portals++;

-	if (c_active_portals > c_peak_portals)

-		c_peak_portals = c_active_portals;

-	

-	p = (portal_t*)malloc (sizeof(portal_t));

-	memset (p, 0, sizeof(portal_t));

-	p->id = s_PortalCount;

-	++s_PortalCount;

-

-	return p;

-}

-

-void FreePortal (portal_t *p)

-{

-	if (p->winding)

-		FreeWinding (p->winding);

-	if (numthreads == 1)

-		c_active_portals--;

-	free (p);

-}

-

-//==============================================================

-

-/*

-==============

-VisibleContents

-

-Returns the single content bit of the

-strongest visible content present

-==============

-*/

-int VisibleContents (int contents)

-{

-	int		i;

-

-	for (i=1 ; i<=LAST_VISIBLE_CONTENTS ; i<<=1)

-	{

-		if (contents & i )

-		{

-			return i;

-		}

-	}

-

-	return 0;

-}

-

-

-/*

-===============

-ClusterContents

-===============

-*/

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

-}

-

-/*

-=============

-Portal_VisFlood

-

-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 leafs, so all contents should be ored together

-=============

-*/

-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_TRANSLUCENT|CONTENTS_DETAIL))

-		c1 = 0;

-	if (c2 & (CONTENTS_TRANSLUCENT|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;

-}

-

-

-/*

-===============

-Portal_EntityFlood

-

-The entity flood determines which areas are

-"outside" on the map, which are then filled in.

-Flowing from side s to side !s

-===============

-*/

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

-}

-

-qboolean Portal_AreaLeakFlood (portal_t *p, int s)

-{

-	if ( !Portal_EntityFlood( p, s ) )

-		return false;

-

-	// can never cross through areaportal

-	if ( (p->nodes[0]->contents & CONTENTS_AREAPORTAL)

-	|| (p->nodes[1]->contents & CONTENTS_AREAPORTAL) )

-		return false;

-

-	// can flood through everything else

-	return true;

-}

-

-

-//=============================================================================

-

-int		c_tinyportals;

-

-/*

-=============

-AddPortalToNodes

-=============

-*/

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

-}

-

-

-/*

-=============

-RemovePortalFromNode

-=============

-*/

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

-{

-	portal_t	**pp, *t;

-	

-// 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;

-	}

-	else if (portal->nodes[1] == l)

-	{

-		*pp = portal->next[1];	

-		portal->nodes[1] = NULL;

-	}

-}

-

-//============================================================================

-

-void PrintPortal (portal_t *p)

-{

-	int			i;

-	winding_t	*w;

-	

-	w = p->winding;

-	for (i=0 ; i<w->numpoints ; i++)

-		Msg ("(%5.0f,%5.0f,%5.0f)\n",w->p[i][0]

-		, w->p[i][1], w->p[i][2]);

-}

-

-// because of water areaportals support, the areaportal may not be the only brush on this node

-bspbrush_t *AreaportalBrushForNode( node_t *node )

-{

-	bspbrush_t *b = node->brushlist;

-	while ( b && !(b->original->contents & CONTENTS_AREAPORTAL) )

-	{

-		b = b->next;

-	}

-	Assert( b->original->entitynum != 0 );

-	return b;

-}

-

-/*

-================

-MakeHeadnodePortals

-

-The created portals will face the global outside_node

-================

-*/

-// buffer space around sides of nodes

-#define	SIDESPACE	8

-void MakeHeadnodePortals (tree_t *tree)

-{

-	Vector		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 leafs

-	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);

-		}

-	}

-}

-

-//===================================================

-

-

-/*

-================

-BaseWindingForNode

-================

-*/

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

-	Vector		normal;

-	vec_t		dist;

-

-	w = BaseWindingForPlane (g_MainMap->mapplanes[node->planenum].normal, g_MainMap->mapplanes[node->planenum].dist);

-

-	// clip by all the parents

-	for (n=node->parent ; n && w ; )

-	{

-		plane = &g_MainMap->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;

-}

-

-//============================================================

-

-/*

-==================

-MakeNodePortal

-

-create the new portal by taking the full plane winding for the cutting plane

-and clipping it by all of parents of this node

-==================

-*/

-void MakeNodePortal (node_t *node)

-{

-	portal_t	*new_portal, *p;

-	winding_t	*w;

-	Vector		normal;

-	float		dist = 0.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;

-		}

-		else if (p->nodes[1] == node)

-		{

-			side = 1;

-			VectorSubtract (vec3_origin, p->plane.normal, normal);

-			dist = -p->plane.dist;

-		}

-		else

-		{

-			Error ("CutNodePortals_r: mislinked portal");

-		}

-

-		ChopWindingInPlace (&w, normal, dist, 0.1);

-	}

-

-	if (!w)

-	{

-		return;

-	}

-

-	if (WindingIsTiny (w))

-	{

-		c_tinyportals++;

-		FreeWinding (w);

-		return;

-	}

-

-

-	new_portal = AllocPortal ();

-	new_portal->plane = g_MainMap->mapplanes[node->planenum];

-	new_portal->onnode = node;

-	new_portal->winding = w;	

-

-	AddPortalToNodes (new_portal, node->children[0], node->children[1]);

-}

-

-

-/*

-==============

-SplitNodePortals

-

-Move or split the portals that bound node so that the node's

-children have portals instead of node.

-==============

-*/

-void SplitNodePortals (node_t *node)

-{

-	portal_t	*p, *next_portal, *new_portal;

-	node_t		*f, *b, *other_node;

-	int			side = 0;

-	plane_t		*plane;

-	winding_t	*frontwinding, *backwinding;

-

-	plane = &g_MainMap->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 ("CutNodePortals_r: 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++;

-		}

-

-		if (backwinding && WindingIsTiny(backwinding))

-		{

-			FreeWinding (backwinding);

-			backwinding = NULL;

-			c_tinyportals++;

-		}

-

-		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);

-		}

-		else

-		{

-			AddPortalToNodes (p, other_node, f);

-			AddPortalToNodes (new_portal, other_node, b);

-		}

-	}

-

-	node->portals = NULL;

-}

-

-

-/*

-================

-CalcNodeBounds

-================

-*/

-void CalcNodeBounds (node_t *node)

-{

-	portal_t	*p;

-	int			s;

-	int			i;

-

-	// calc mins/maxs for both leafs 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);

-	}

-}

-

-

-/*

-==================

-MakeTreePortals_r

-==================

-*/

-void MakeTreePortals_r (node_t *node)

-{

-	int		i;

-

-	CalcNodeBounds (node);

-	if (node->mins[0] >= node->maxs[0])

-	{

-		Warning("WARNING: node without a volume\n");

-	}

-

-	for (i=0 ; i<3 ; i++)

-	{

-		if (node->mins[i] < (MIN_COORD_INTEGER-SIDESPACE) || node->maxs[i] > (MAX_COORD_INTEGER+SIDESPACE))

-		{

-			const char *pMatName = "<NO BRUSH>";

-			// split by brush side

-			if ( node->side )

-			{

-				texinfo_t *pTexInfo = &texinfo[node->side->texinfo];

-				dtexdata_t *pTexData = GetTexData( pTexInfo->texdata );

-				pMatName = TexDataStringTable_GetString( pTexData->nameStringTableID );

-			}

-			Vector point = node->portals->winding->p[0];

-			Warning("WARNING: BSP node with unbounded volume (material: %s, near %s)\n", pMatName, VecToString(point) );

-			break;

-		}

-	}

-	if (node->planenum == PLANENUM_LEAF)

-		return;

-

-	MakeNodePortal (node);

-	SplitNodePortals (node);

-

-	MakeTreePortals_r (node->children[0]);

-	MakeTreePortals_r (node->children[1]);

-}

-

-/*

-==================

-MakeTreePortals

-==================

-*/

-void MakeTreePortals (tree_t *tree)

-{

-	MakeHeadnodePortals (tree);

-	MakeTreePortals_r (tree->headnode);

-}

-

-/*

-=========================================================

-

-FLOOD ENTITIES

-

-=========================================================

-*/

-

-//-----------------------------------------------------------------------------

-// Purpose: Floods outward from the given node, marking visited nodes with

-//			the number of hops from a node with an entity. If we ever mark

-//			the outside_node for this tree, we've leaked.

-// Input  : node - 

-//			dist - 

-//-----------------------------------------------------------------------------

-void FloodPortals_r (node_t *node, int dist)

-{

-	portal_t	*p;

-	int			s;

-

-	node->occupied = dist;

-

-	for (p=node->portals ; p ; p = p->next[s])

-	{

-		s = (p->nodes[1] == node);

-

-		// Skip nodes that have already been marked.

-		if (p->nodes[!s]->occupied)

-			continue;

-

-		// Skip portals that lead to or from nodes with solid contents.

-		if (!Portal_EntityFlood (p, s))

-			continue;

-

-		FloodPortals_r (p->nodes[!s], dist+1);

-	}

-}

-

-void FloodAreaLeak_r( node_t *node, int dist )

-{

-	portal_t	*p;

-	int			s;

-

-	node->occupied = dist;

-

-	for (p=node->portals ; p ; p = p->next[s])

-	{

-		s = (p->nodes[1] == node);

-

-		if (p->nodes[!s]->occupied)

-			continue;

-

-		if (!Portal_AreaLeakFlood (p, s))

-			continue;

-

-		FloodAreaLeak_r( p->nodes[!s], dist+1 );

-	}

-}

-

-void ClearOccupied_r( node_t *headnode )

-{

-	if ( !headnode )

-		return;

-

-	headnode->occupied = 0;

-	ClearOccupied_r( headnode->children[0] );

-	ClearOccupied_r( headnode->children[1] );

-}

-

-void FloodAreaLeak( node_t *headnode, node_t *pFirstSide )

-{

-	ClearOccupied_r( headnode );

-	FloodAreaLeak_r( pFirstSide, 2 );

-}

-

-//-----------------------------------------------------------------------------

-// Purpose: For the given entity at the given origin, finds the leaf node in the

-//			BSP tree that the entity occupies.

-//

-//			We then flood outward from that leaf to see if the entity leaks.

-// Input  : headnode - 

-//			origin - 

-//			occupant - 

-// Output : Returns false if the entity is in solid, true if it is not.

-//-----------------------------------------------------------------------------

-qboolean PlaceOccupant (node_t *headnode, Vector& 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)

-	{

-		plane = &g_MainMap->mapplanes[node->planenum];

-		d = DotProduct (origin, plane->normal) - plane->dist;

-		if (d >= 0)

-			node = node->children[0];

-		else

-			node = node->children[1];

-	}

-

-	if (node->contents == CONTENTS_SOLID)

-		return false;

-

-	node->occupant = occupant;

-

-	// Flood outward from here to see if this entity leaks.

-	FloodPortals_r (node, 1);

-

-	return true;

-}

-

-/*

-=============

-FloodEntities

-

-Marks all nodes that can be reached by entites

-=============

-*/

-qboolean FloodEntities (tree_t *tree)

-{

-	int		i;

-	Vector	origin;

-	char	*cl;

-	qboolean	inside;

-	node_t *headnode;

-

-	headnode = tree->headnode;

-	qprintf ("--- FloodEntities ---\n");

-	inside = false;

-	tree->outside_node.occupied = 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

-

-		// nudge playerstart around if needed so clipping hulls allways

-		// have a valid point

-		if (!strcmp (cl, "info_player_start"))

-		{

-			int	x, y;

-

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

-						goto gotit;

-					}

-					origin[0] -= x;

-					origin[1] -= y;

-				}

-			}

-gotit: ;

-		}

-		else

-		{

-			if (PlaceOccupant (headnode, origin, &entities[i]))

-				inside = true;

-		}

-	}

-

-	if (!inside)

-	{

-		qprintf ("no entities in open -- no filling\n");

-	}

-

-	if (tree->outside_node.occupied)

-	{

-		qprintf ("entity reached from outside -- no filling\n" );

-	}

-

-	return (qboolean)(inside && !tree->outside_node.occupied);

-}

-

-

-/*

-=========================================================

-

-FLOOD AREAS

-

-=========================================================

-*/

-

-int		c_areas;

-

-bool IsAreaportalNode( node_t *node )

-{

-	return ( node->contents & CONTENTS_AREAPORTAL ) ? true : false;

-}

-/*

-=============

-FloodAreas_r

-=============

-*/

-

-void FloodAreas_r (node_t *node, portal_t *pSeeThrough)

-{

-	portal_t	*p;

-	int			s;

-	bspbrush_t	*b;

-	entity_t	*e;

-

-	if ( IsAreaportalNode(node) )

-	{

-		// this node is part of an area portal

-		b = AreaportalBrushForNode( node );

-		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])

-		{

-			Warning("WARNING: areaportal entity %i (brush %i) touches > 2 areas\n", b->original->entitynum, b->original->id );

-			return;

-		}

-		

-		if (e->portalareas[0])

-		{

-			e->portalareas[1] = c_areas;

-			e->m_pPortalsLeadingIntoAreas[1] = pSeeThrough;

-		}

-		else

-		{

-			e->portalareas[0] = c_areas;

-			e->m_pPortalsLeadingIntoAreas[0] = pSeeThrough;

-		}

-

-		return;

-	}

-

-	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], p);

-	}

-}

-

-/*

-=============

-FindAreas_r

-

-Just decend the tree, and for each node that hasn't had an

-area set, flood fill out from there

-=============

-*/

-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 (IsAreaportalNode(node))

-		return;

-

-	c_areas++;

-	FloodAreas_r (node, NULL);

-}

-

-

-void ReportAreaportalLeak( tree_t *tree, node_t *node )

-{

-	portal_t *p, *pStart = NULL;

-	int s;

-

-	// Find a portal out of this areaportal into empty space

-	for (p=node->portals ; p ; p = p->next[s])

-	{

-		s = (p->nodes[1] == node);

-		if ( !Portal_EntityFlood( p, !s ) )

-			continue;

-		if ( p->nodes[!s]->contents & CONTENTS_AREAPORTAL )

-			continue;

-

-		pStart = p;

-		break;

-	}

-

-	if ( pStart )

-	{

-		s = pStart->nodes[0] == node;

-		Assert(!(pStart->nodes[s]->contents & CONTENTS_AREAPORTAL) );

-		// flood fill the area outside this areaportal brush

-		FloodAreaLeak( tree->headnode, pStart->nodes[s] );

-

-		// find the portal into the longest path around the portal

-		portal_t *pBest = NULL;

-		int bestDist = 0;

-		for (p=node->portals ; p ; p = p->next[s])

-		{

-			if ( p == pStart )

-				continue;

-

-			s = (p->nodes[1] == node);

-			if ( p->nodes[!s]->occupied > bestDist )

-			{

-				pBest = p;

-				bestDist = p->nodes[!s]->occupied;

-			}

-		}

-		if ( pBest )

-		{

-			s = (pBest->nodes[0] == node);

-			// write the linefile that goes from pBest to pStart

-			AreaportalLeakFile( tree, pStart, pBest, pBest->nodes[s] );

-		}

-	}

-}

-

-

-/*

-=============

-SetAreaPortalAreas_r

-

-Just decend the tree, and for each node that hasn't had an

-area set, flood fill out from there

-=============

-*/

-void SetAreaPortalAreas_r (tree_t *tree, node_t *node)

-{

-	bspbrush_t	*b;

-	entity_t	*e;

-

-	if (node->planenum != PLANENUM_LEAF)

-	{

-		SetAreaPortalAreas_r (tree, node->children[0]);

-		SetAreaPortalAreas_r (tree, node->children[1]);

-		return;

-	}

-

-	if (IsAreaportalNode(node))

-	{

-		if (node->area)

-			return;		// already set

-

-		b = AreaportalBrushForNode( node );

-		e = &entities[b->original->entitynum];

-		node->area = e->portalareas[0];

-		if (!e->portalareas[1])

-		{

-			ReportAreaportalLeak( tree, node );

-			Warning("\nBrush %i: areaportal brush doesn't touch two areas\n", b->original->id);

-			return;

-		}

-	}

-}

-

-

-// Return a positive value between 0 and 2*PI telling the angle distance

-// from flBaseAngle to flTestAngle.

-float AngleOffset( float flBaseAngle, float flTestAngle )

-{

-	while( flTestAngle > flBaseAngle )

-		flTestAngle -= 2 * M_PI;

-

-	return fmod( flBaseAngle - flTestAngle, (float) (2 * M_PI) );

-}

-

-

-int FindUniquePoints( const Vector2D *pPoints, int nPoints, int *indexMap, int nMaxIndexMapPoints, float flTolerance )

-{

-	float flToleranceSqr = flTolerance * flTolerance;

-

-	// This could be slightly more efficient.

-	int nUniquePoints = 0;

-	for ( int i=0; i < nPoints; i++ )

-	{

-		int j;

-		for ( j=0; j < nUniquePoints; j++ )

-		{

-			if ( pPoints[i].DistToSqr( pPoints[indexMap[j]] ) < flToleranceSqr )

-				break;

-		}

-		if ( j == nUniquePoints )

-		{

-			if ( nUniquePoints >= nMaxIndexMapPoints )

-				Error( "FindUniquePoints: overflowed unique point list (size %d).", nMaxIndexMapPoints );

-

-			indexMap[nUniquePoints++] = i;

-		}

-	}

-	

-	return nUniquePoints;

-}

-

-// Build a 2D convex hull of the set of points.

-// This essentially giftwraps the points as it walks around the perimeter.

-int Convex2D( Vector2D const *pPoints, int nPoints, int *indices, int nMaxIndices )

-{

-	int nIndices = 0;

-	bool touched[512];

-	int indexMap[512];

-

-	if( nPoints == 0 )

-		return 0;

-

-

-	// If we don't collapse the points into a unique set, we can loop around forever

-	// and max out nMaxIndices.

-	nPoints = FindUniquePoints( pPoints, nPoints, indexMap, ARRAYSIZE( indexMap ), 0.1f );

-	memset( touched, 0, nPoints*sizeof(touched[0]) );

-

-	// Find the (lower) left side.

-	int i;

-	int iBest = 0;

-	for( i=1; i < nPoints; i++ )

-	{

-		if( pPoints[indexMap[i]].x < pPoints[indexMap[iBest]].x ||

-			(pPoints[indexMap[i]].x == pPoints[indexMap[iBest]].x && pPoints[indexMap[i]].y < pPoints[indexMap[iBest]].y) )

-		{

-			iBest = i;

-		}

-	}

-

-	touched[iBest] = true;

-	indices[0] = indexMap[iBest];

-	nIndices = 1;

-

-	Vector2D curEdge( 0, 1 );

-

-	// Wind around clockwise.

-	while( 1 )

-	{

-		Vector2D const *pStartPoint = &pPoints[ indices[nIndices-1] ];

-

-		float flEdgeAngle = atan2( curEdge.y, curEdge.x );

-		

-		int iMinAngle = -1;

-		float flMinAngle = 5000;

-

-		for( i=0; i < nPoints; i++ )

-		{

-			Vector2D vTo = pPoints[indexMap[i]] - *pStartPoint;

-			float flDistToSqr = vTo.LengthSqr();

-			if ( flDistToSqr <= 0.1f )

-				continue;

-

-			// Get the angle from the edge to this point.

-			float flAngle = atan2( vTo.y, vTo.x );

-			flAngle = AngleOffset( flEdgeAngle, flAngle );

-

-			if( fabs( flAngle - flMinAngle ) < 0.00001f )

-			{

-				float flDistToTestSqr = pStartPoint->DistToSqr( pPoints[iMinAngle] );

-

-				// If the angle is the same, pick the point farthest away.

-				// unless the current one is closing the face loop

-				if ( iMinAngle != indices[0] && flDistToSqr > flDistToTestSqr )

-				{

-					flMinAngle = flAngle;

-					iMinAngle = indexMap[i];

-				}

-			}

-			else if( flAngle < flMinAngle )

-			{

-				flMinAngle = flAngle;

-				iMinAngle = indexMap[i];

-			}

-		}

-

-		if( iMinAngle == -1 )

-		{

-			// Couldn't find a point?

-			Assert( false );

-			break;

-		}

-		else if( iMinAngle == indices[0] )

-		{

-			// Finished.

-			break;

-		}

-		else

-		{

-			// Add this point.

-			if( nIndices >= nMaxIndices )

-				break;

-

-			for ( int jj = 0; jj < nIndices; jj++ )

-			{

-				// if this assert hits, this routine is broken and is generating a spiral

-				// rather than a closed polygon - basically an edge overlap of some kind

-				Assert(indices[jj] != iMinAngle );

-			}

-

-			indices[nIndices] = iMinAngle;

-			++nIndices;

-		}

-

-		curEdge = pPoints[indices[nIndices-1]] - pPoints[indices[nIndices-2]];

-	}

-	

-	return nIndices;

-}

-

-void FindPortalsLeadingToArea_R( 

-	node_t *pHeadNode, 

-	int iSrcArea, 

-	int iDestArea, 

-	plane_t *pPlane, 

-	CUtlVector<portal_t*> &portals )

-{

-	if (pHeadNode->planenum != PLANENUM_LEAF)

-	{

-		FindPortalsLeadingToArea_R( pHeadNode->children[0], iSrcArea, iDestArea, pPlane, portals );

-		FindPortalsLeadingToArea_R( pHeadNode->children[1], iSrcArea, iDestArea, pPlane, portals );

-		return;

-	}

-

-	// Ok.. this is a leaf, check its portals.

-	int s;

-	for( portal_t *p = pHeadNode->portals; p ;p = p->next[!s] )

-	{

-		s = (p->nodes[0] == pHeadNode);

-

-		if( !p->nodes[0]->occupied || !p->nodes[1]->occupied )

-			continue;

-	

-		if( p->nodes[1]->area == iDestArea && p->nodes[0]->area == iSrcArea ||

-			p->nodes[0]->area == iDestArea && p->nodes[1]->area == iSrcArea )

-		{

-			// Make sure the plane normals point the same way.

-			plane_t *pMapPlane = &g_MainMap->mapplanes[p->onnode->planenum];

-			float flDot = fabs( pMapPlane->normal.Dot( pPlane->normal ) );

-			if( fabs( 1 - flDot ) < 0.01f )

-			{

-				Vector vPlanePt1 = pPlane->normal * pPlane->dist;

-				Vector vPlanePt2 = pMapPlane->normal * pMapPlane->dist;

-

-				if( vPlanePt1.DistToSqr( vPlanePt2 ) < 0.01f )

-				{

-					portals.AddToTail( p );

-				}

-			}

-		}

-	}

-}

-

-

-void EmitClipPortalGeometry( node_t *pHeadNode, portal_t *pPortal, int iSrcArea, dareaportal_t *dp )

-{

-	// Build a list of all the points in portals from the same original face.

-	CUtlVector<portal_t*> portals;

-	FindPortalsLeadingToArea_R( 

-		pHeadNode, 

-		iSrcArea, 

-		dp->otherarea, 

-		&pPortal->plane,

-		portals );

-

-	CUtlVector<Vector> points;

-	for( int iPortal=0; iPortal < portals.Size(); iPortal++ )

-	{

-		portal_t *pPointPortal = portals[iPortal];

-		winding_t *pWinding = pPointPortal->winding;

-		for( int i=0; i < pWinding->numpoints; i++ )

-		{

-			points.AddToTail( pWinding->p[i] );

-		}

-	}

-

-	// Get the 2D convex hull.

-

-	//// First transform them into a plane.

-	QAngle vAngles;

-	Vector vecs[3];

-

-	VectorAngles( pPortal->plane.normal, vAngles );

-	AngleVectors( vAngles, &vecs[0], &vecs[1], &vecs[2] );

-	VMatrix mTransform;

-	mTransform.Identity();

-	mTransform.SetBasisVectors( vecs[0], vecs[1], vecs[2] );

-	VMatrix mInvTransform = mTransform.Transpose();

-

-	int i;

-	CUtlVector<Vector2D> points2D;

-	for( i=0; i < points.Size(); i++ )

-	{

-		Vector vTest = mTransform * points[i];

-		points2D.AddToTail( Vector2D( vTest.y, vTest.z ) );

-	}

-

-	// Build the hull.

-	int indices[512];

-	int nIndices = Convex2D( points2D.Base(), points2D.Size(), indices, 512 );

-

-	// Output the hull.

-	dp->m_FirstClipPortalVert = g_nClipPortalVerts;

-	dp->m_nClipPortalVerts = nIndices;

-

-	if ( nIndices >= 32 )

-	{

-		Warning( "Warning: area portal has %d verts. Could be a vbsp bug.\n", nIndices );

-	}

-

-	if( dp->m_FirstClipPortalVert + dp->m_nClipPortalVerts >= MAX_MAP_PORTALVERTS )

-	{

-		Vector *p = pPortal->winding->p;

-		Error( "MAX_MAP_PORTALVERTS (probably a broken areaportal near %.1f %.1f %.1f ", p->x, p->y, p->z );

-	}

-	

-	for( i=0; i < nIndices; i++ )

-	{

-		g_ClipPortalVerts[g_nClipPortalVerts] = points[ indices[i] ];

-		++g_nClipPortalVerts;

-	}

-}

-

-

-// Sets node_t::area for non-leaf nodes (this allows an optimization in the renderer).

-void SetNodeAreaIndices_R( node_t *node )

-{

-	// All leaf area indices should already be set.

-	if( node->planenum == PLANENUM_LEAF )

-		return;

-

-	// Have the children set their area indices.

-	SetNodeAreaIndices_R( node->children[0] );

-	SetNodeAreaIndices_R( node->children[1] );

-

-	// If all children (leaves or nodes) are in the same area, then set our area

-	// to this area as well. Otherwise, set it to -1.

-	if( node->children[0]->area == node->children[1]->area )

-		node->area = node->children[0]->area;

-	else

-		node->area = -1;	

-}

-

-

-/*

-=============

-EmitAreaPortals

-

-=============

-*/

-void EmitAreaPortals (node_t *headnode)

-{

-	entity_t		*e;

-	dareaportal_t	*dp;

-

-	if (c_areas > MAX_MAP_AREAS)

-		Error ("Map is split into too many unique areas (max = %d)\nProbably too many areaportals", MAX_MAP_AREAS);

-	numareas = c_areas+1;

-	numareaportals = 1;		// leave 0 as an error

-

-	// Reset the clip portal vert info.

-	g_nClipPortalVerts = 0;

-

-	for (int iSrcArea=1 ; iSrcArea<=c_areas ; iSrcArea++)

-	{

-		dareas[iSrcArea].firstareaportal = numareaportals;

-		for (int j=0 ; j<num_entities ; j++)

-		{

-			e = &entities[j];

-			if (!e->areaportalnum)

-				continue;

-			

-			if (e->portalareas[0] == iSrcArea || e->portalareas[1] == iSrcArea)

-			{

-				int iSide = (e->portalareas[0] == iSrcArea);

-

-				// We're only interested in the portal that divides the two areas.

-				// One of the portals that leads into the CONTENTS_AREAPORTAL just bounds

-				// the same two areas but the other bounds two different ones.

-				portal_t *pLeadingPortal = e->m_pPortalsLeadingIntoAreas[0];

-				if( pLeadingPortal->nodes[0]->area == pLeadingPortal->nodes[1]->area )

-					pLeadingPortal = e->m_pPortalsLeadingIntoAreas[1];

-

-				if( pLeadingPortal )

-				{

-					Assert( pLeadingPortal->nodes[0]->area != pLeadingPortal->nodes[1]->area );

-

-					dp = &dareaportals[numareaportals];

-					numareaportals++;

-

-					dp->m_PortalKey = e->areaportalnum;

-					dp->otherarea = e->portalareas[iSide];

-					dp->planenum = pLeadingPortal->onnode->planenum;

-

-					Assert( pLeadingPortal->nodes[0]->planenum == PLANENUM_LEAF );

-					Assert( pLeadingPortal->nodes[1]->planenum == PLANENUM_LEAF );

-

-					if( pLeadingPortal->nodes[0]->area == dp->otherarea )

-					{

-						// Use the flipped version of the plane.

-						dp->planenum = (dp->planenum & ~1) | (~dp->planenum & 1);

-					}

-

-					EmitClipPortalGeometry( headnode, pLeadingPortal, iSrcArea, dp );

-				}

-			}

-		}

-

-		dareas[iSrcArea].numareaportals = numareaportals - dareas[iSrcArea].firstareaportal;

-	}

-

-	SetNodeAreaIndices_R( headnode );

-

-	qprintf ("%5i numareas\n", numareas);

-	qprintf ("%5i numareaportals\n", numareaportals);

-}

-

-/*

-=============

-FloodAreas

-

-Mark each leaf with an area, bounded by CONTENTS_AREAPORTAL

-=============

-*/

-void FloodAreas (tree_t *tree)

-{

-	int start = Plat_FloatTime();

-	qprintf ("--- FloodAreas ---\n");

-	Msg("Processing areas...");

-	FindAreas_r (tree->headnode);

-	SetAreaPortalAreas_r (tree, tree->headnode);

-	qprintf ("%5i areas\n", c_areas);

-	Msg("done (%d)\n", (int)(Plat_FloatTime() - start) );

-}

-

-//======================================================

-

-int		c_outside;

-int		c_inside;

-int		c_solid;

-

-void FillOutside_r (node_t *node)

-{

-	if (node->planenum != PLANENUM_LEAF)

-	{

-		FillOutside_r (node->children[0]);

-		FillOutside_r (node->children[1]);

-		return;

-	}

-

-	// anything not reachable by an entity

-	// can be filled away

-	if (!node->occupied)

-	{

-		if (node->contents != CONTENTS_SOLID)

-		{

-			c_outside++;

-			node->contents = CONTENTS_SOLID;

-		}

-		else

-			c_solid++;

-	}

-	else

-		c_inside++;

-

-}

-

-/*

-=============

-FillOutside

-

-Fill all nodes that can't be reached by entities

-=============

-*/

-void FillOutside (node_t *headnode)

-{

-	c_outside = 0;

-	c_inside = 0;

-	c_solid = 0;

-	qprintf ("--- FillOutside ---\n");

-	FillOutside_r (headnode);

-	qprintf ("%5i solid leafs\n", c_solid);

-	qprintf ("%5i leafs filled\n", c_outside);

-	qprintf ("%5i inside leafs\n", c_inside);

-}

-

-

-static float ComputeDistFromPlane( winding_t *pWinding, plane_t *pPlane, float maxdist )

-{

-	float totaldist = 0.0f;

-	for (int i = 0; i < pWinding->numpoints; ++i)

-	{

-		totaldist += fabs(DotProduct( pPlane->normal, pWinding->p[i] ) - pPlane->dist);

-		if (totaldist > maxdist)

-			return totaldist;

-	}

-	return totaldist;

-}

-

-

-//-----------------------------------------------------------------------------

-// Display portal error

-//-----------------------------------------------------------------------------

-static void DisplayPortalError( portal_t *p, int viscontents )

-{

-	char contents[3][1024];

-	PrintBrushContentsToString( p->nodes[0]->contents, contents[0], sizeof( contents[0] ) );

-	PrintBrushContentsToString( p->nodes[1]->contents, contents[1], sizeof( contents[1] ) );

-	PrintBrushContentsToString( viscontents, contents[2], sizeof( contents[2] ) );

-

-	Vector center;

-	WindingCenter( p->winding, center );

-	Warning( "\nFindPortalSide: Couldn't find a good match for which brush to assign to a portal near (%.1f %.1f %.1f)\n", center.x, center.y, center.z);

-	Warning( "Leaf 0 contents: %s\n", contents[0] );

-	Warning( "Leaf 1 contents: %s\n", contents[1] );

-	Warning( "viscontents (node 0 contents ^ node 1 contents): %s\n", contents[2] );

-	Warning( "This means that none of the brushes in leaf 0 or 1 that touches the portal has %s\n", contents[2] );

-	Warning( "Check for a huge brush enclosing the coordinates above that has contents %s\n", contents[2] );

-	Warning( "Candidate brush IDs: " );

-

-	CUtlVector<int> listed;

-	for (int j=0 ; j<2 ; j++)

-	{

-		node_t *n = p->nodes[j];

-		for (bspbrush_t *bb=n->brushlist ; bb ; bb=bb->next)

-		{

-			mapbrush_t *brush = bb->original;

-			if ( brush->contents & viscontents )

-			{

-				if ( listed.Find( brush->brushnum ) == -1 )

-				{

-					listed.AddToTail( brush->brushnum );

-					Warning( "Brush %d: ", brush->id );

-				}

-			}

-		}

-	}

-	Warning( "\n\n" );

-}

-

-

-//==============================================================

-

-/*

-============

-FindPortalSide

-

-Finds a brush side to use for texturing the given portal

-============

-*/

-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		bestdist;

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

-	bestdist = 1000000;

-

-	for (j=0 ; j<2 ; j++)

-	{

-		n = p->nodes[j];

-		p1 = &g_MainMap->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->bevel)

-					continue;

-				if (side->texinfo == TEXINFO_NODE)

-					continue;		// non-visible

-

-				if ((side->planenum&~1) == planenum)

-				{	// exact match

-					bestside = &brush->original_sides[i];

-					bestdist = 0.0f;

-					goto gotit;

-				}

-

-				p2 = &g_MainMap->mapplanes[side->planenum&~1];

-

-				float dist = ComputeDistFromPlane( p->winding, p2, bestdist );

-				if (dist < bestdist)

-				{

-					bestside = side;

-					bestdist = dist;

-				}

-			}

-		}

-	}

-

-gotit:

-	if (!bestside)

-		qprintf ("WARNING: side not found for portal\n");

-

-	// Compute average dist, check for problems...

-	if ((bestdist / p->winding->numpoints) > 2)

-	{

-		static int nWarnCount = 0;

-		if ( nWarnCount < 8 )

-		{

-			DisplayPortalError( p, viscontents );

-			if ( ++nWarnCount == 8 )

-			{

-				Warning("*** Suppressing further FindPortalSide errors.... ***\n" );

-			}

-		}

-	}

-

-	p->sidefound = true;

-	p->side = bestside;

-}

-

-

-/*

-===============

-MarkVisibleSides_r

-

-===============

-*/

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

-	}

-

-	// empty leafs are never boundary leafs

-	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->visible = true;

-	}

-

-}

-

-/*

-=============

-MarkVisibleSides

-

-=============

-*/

-// UNDONE: Put detail brushes in a separate list (not mapbrushes) ?

-void MarkVisibleSides (tree_t *tree, int startbrush, int endbrush, int detailScreen)

-{

-	int		i, j;

-	mapbrush_t	*mb;

-	int		numsides;

-	qboolean detail;

-

-	qprintf ("--- MarkVisibleSides ---\n");

-

-	// clear all the visible flags

-	for (i=startbrush ; i<endbrush ; i++)

-	{

-		mb = &g_MainMap->mapbrushes[i];

-

-		if ( detailScreen != FULL_DETAIL )

-		{

-			qboolean onlyDetail = (detailScreen==ONLY_DETAIL)?true:false;

-			// true for detail brushes

-			detail = (mb->contents & CONTENTS_DETAIL) ? true : false;

-			if ( onlyDetail ^ detail )

-			{

-				// both of these must have the same value or we're not interested in this brush

-				continue;

-			}

-		}

-

-		numsides = mb->numsides;

-		for (j=0 ; j<numsides ; j++)

-			mb->original_sides[j].visible = false;

-	}

-

-	// set visible flags on the sides that are used by portals

-	MarkVisibleSides_r (tree->headnode);

-}

-

-

-//-----------------------------------------------------------------------------

-// Used to determine which sides are visible

-//-----------------------------------------------------------------------------

-void MarkVisibleSides (tree_t *tree, mapbrush_t **ppBrushes, int nCount )

-{

-	qprintf ("--- MarkVisibleSides ---\n");

-

-	// clear all the visible flags

-	int	i, j;

-	for ( i=0; i < nCount; ++i )

-	{

-		mapbrush_t *mb = ppBrushes[i];

-		int numsides = mb->numsides;

-		for (j=0 ; j<numsides ; j++)

-		{

-			mb->original_sides[j].visible = false;

-		}

-	}

-

-	// set visible flags on the sides that are used by portals

-	MarkVisibleSides_r( tree->headnode );

-}

-

+//========= Copyright Valve Corporation, All rights reserved. ============//
+//
+// Purpose: 
+//
+// $NoKeywords: $
+//
+//=============================================================================//
+
+#include "vbsp.h"
+#include "utlvector.h"
+#include "mathlib/vmatrix.h"
+#include "iscratchpad3d.h"
+#include "csg.h"
+#include "fmtstr.h"
+
+int		c_active_portals;
+int		c_peak_portals;
+int		c_boundary;
+int		c_boundary_sides;
+
+/*
+===========
+AllocPortal
+===========
+*/
+portal_t *AllocPortal (void)
+{
+	static int s_PortalCount = 0;
+
+	portal_t	*p;
+	
+	if (numthreads == 1)
+		c_active_portals++;
+	if (c_active_portals > c_peak_portals)
+		c_peak_portals = c_active_portals;
+	
+	p = (portal_t*)malloc (sizeof(portal_t));
+	memset (p, 0, sizeof(portal_t));
+	p->id = s_PortalCount;
+	++s_PortalCount;
+
+	return p;
+}
+
+void FreePortal (portal_t *p)
+{
+	if (p->winding)
+		FreeWinding (p->winding);
+	if (numthreads == 1)
+		c_active_portals--;
+	free (p);
+}
+
+//==============================================================
+
+/*
+==============
+VisibleContents
+
+Returns the single content bit of the
+strongest visible content present
+==============
+*/
+int VisibleContents (int contents)
+{
+	int		i;
+
+	for (i=1 ; i<=LAST_VISIBLE_CONTENTS ; i<<=1)
+	{
+		if (contents & i )
+		{
+			return i;
+		}
+	}
+
+	return 0;
+}
+
+
+/*
+===============
+ClusterContents
+===============
+*/
+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;
+}
+
+/*
+=============
+Portal_VisFlood
+
+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 leafs, so all contents should be ored together
+=============
+*/
+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_TRANSLUCENT|CONTENTS_DETAIL))
+		c1 = 0;
+	if (c2 & (CONTENTS_TRANSLUCENT|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;
+}
+
+
+/*
+===============
+Portal_EntityFlood
+
+The entity flood determines which areas are
+"outside" on the map, which are then filled in.
+Flowing from side s to side !s
+===============
+*/
+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;
+}
+
+qboolean Portal_AreaLeakFlood (portal_t *p, int s)
+{
+	if ( !Portal_EntityFlood( p, s ) )
+		return false;
+
+	// can never cross through areaportal
+	if ( (p->nodes[0]->contents & CONTENTS_AREAPORTAL)
+	|| (p->nodes[1]->contents & CONTENTS_AREAPORTAL) )
+		return false;
+
+	// can flood through everything else
+	return true;
+}
+
+
+//=============================================================================
+
+int		c_tinyportals;
+
+/*
+=============
+AddPortalToNodes
+=============
+*/
+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;
+}
+
+
+/*
+=============
+RemovePortalFromNode
+=============
+*/
+void RemovePortalFromNode (portal_t *portal, node_t *l)
+{
+	portal_t	**pp, *t;
+	
+// 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;
+	}
+	else if (portal->nodes[1] == l)
+	{
+		*pp = portal->next[1];	
+		portal->nodes[1] = NULL;
+	}
+}
+
+//============================================================================
+
+void PrintPortal (portal_t *p)
+{
+	int			i;
+	winding_t	*w;
+	
+	w = p->winding;
+	for (i=0 ; i<w->numpoints ; i++)
+		Msg ("(%5.0f,%5.0f,%5.0f)\n",w->p[i][0]
+		, w->p[i][1], w->p[i][2]);
+}
+
+// because of water areaportals support, the areaportal may not be the only brush on this node
+bspbrush_t *AreaportalBrushForNode( node_t *node )
+{
+	bspbrush_t *b = node->brushlist;
+	while ( b && !(b->original->contents & CONTENTS_AREAPORTAL) )
+	{
+		b = b->next;
+	}
+	Assert( b->original->entitynum != 0 );
+	return b;
+}
+
+/*
+================
+MakeHeadnodePortals
+
+The created portals will face the global outside_node
+================
+*/
+// buffer space around sides of nodes
+#define	SIDESPACE	8
+void MakeHeadnodePortals (tree_t *tree)
+{
+	Vector		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 leafs
+	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);
+		}
+	}
+}
+
+//===================================================
+
+
+/*
+================
+BaseWindingForNode
+================
+*/
+#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;
+	Vector		normal;
+	vec_t		dist;
+
+	w = BaseWindingForPlane (g_MainMap->mapplanes[node->planenum].normal, g_MainMap->mapplanes[node->planenum].dist);
+
+	// clip by all the parents
+	for (n=node->parent ; n && w ; )
+	{
+		plane = &g_MainMap->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;
+}
+
+//============================================================
+
+/*
+==================
+MakeNodePortal
+
+create the new portal by taking the full plane winding for the cutting plane
+and clipping it by all of parents of this node
+==================
+*/
+void MakeNodePortal (node_t *node)
+{
+	portal_t	*new_portal, *p;
+	winding_t	*w;
+	Vector		normal;
+	float		dist = 0.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;
+		}
+		else if (p->nodes[1] == node)
+		{
+			side = 1;
+			VectorSubtract (vec3_origin, p->plane.normal, normal);
+			dist = -p->plane.dist;
+		}
+		else
+		{
+			Error ("CutNodePortals_r: mislinked portal");
+		}
+
+		ChopWindingInPlace (&w, normal, dist, 0.1);
+	}
+
+	if (!w)
+	{
+		return;
+	}
+
+	if (WindingIsTiny (w))
+	{
+		c_tinyportals++;
+		FreeWinding (w);
+		return;
+	}
+
+
+	new_portal = AllocPortal ();
+	new_portal->plane = g_MainMap->mapplanes[node->planenum];
+	new_portal->onnode = node;
+	new_portal->winding = w;	
+
+	AddPortalToNodes (new_portal, node->children[0], node->children[1]);
+}
+
+
+/*
+==============
+SplitNodePortals
+
+Move or split the portals that bound node so that the node's
+children have portals instead of node.
+==============
+*/
+void SplitNodePortals (node_t *node)
+{
+	portal_t	*p, *next_portal, *new_portal;
+	node_t		*f, *b, *other_node;
+	int			side = 0;
+	plane_t		*plane;
+	winding_t	*frontwinding, *backwinding;
+
+	plane = &g_MainMap->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 ("CutNodePortals_r: 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++;
+		}
+
+		if (backwinding && WindingIsTiny(backwinding))
+		{
+			FreeWinding (backwinding);
+			backwinding = NULL;
+			c_tinyportals++;
+		}
+
+		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);
+		}
+		else
+		{
+			AddPortalToNodes (p, other_node, f);
+			AddPortalToNodes (new_portal, other_node, b);
+		}
+	}
+
+	node->portals = NULL;
+}
+
+
+/*
+================
+CalcNodeBounds
+================
+*/
+void CalcNodeBounds (node_t *node)
+{
+	portal_t	*p;
+	int			s;
+	int			i;
+
+	// calc mins/maxs for both leafs 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);
+	}
+}
+
+
+/*
+==================
+MakeTreePortals_r
+==================
+*/
+void MakeTreePortals_r (node_t *node)
+{
+	int		i;
+
+	CalcNodeBounds (node);
+	if (node->mins[0] >= node->maxs[0])
+	{
+		Warning("WARNING: node without a volume\n");
+	}
+
+	for (i=0 ; i<3 ; i++)
+	{
+		if (node->mins[i] < (MIN_COORD_INTEGER-SIDESPACE) || node->maxs[i] > (MAX_COORD_INTEGER+SIDESPACE))
+		{
+			const char *pMatName = "<NO BRUSH>";
+			// split by brush side
+			if ( node->side )
+			{
+				texinfo_t *pTexInfo = &texinfo[node->side->texinfo];
+				dtexdata_t *pTexData = GetTexData( pTexInfo->texdata );
+				pMatName = TexDataStringTable_GetString( pTexData->nameStringTableID );
+			}
+			Vector point = node->portals->winding->p[0];
+			Warning("WARNING: BSP node with unbounded volume (material: %s, near %s)\n", pMatName, VecToString(point) );
+			break;
+		}
+	}
+	if (node->planenum == PLANENUM_LEAF)
+		return;
+
+	MakeNodePortal (node);
+	SplitNodePortals (node);
+
+	MakeTreePortals_r (node->children[0]);
+	MakeTreePortals_r (node->children[1]);
+}
+
+/*
+==================
+MakeTreePortals
+==================
+*/
+void MakeTreePortals (tree_t *tree)
+{
+	MakeHeadnodePortals (tree);
+	MakeTreePortals_r (tree->headnode);
+}
+
+/*
+=========================================================
+
+FLOOD ENTITIES
+
+=========================================================
+*/
+
+//-----------------------------------------------------------------------------
+// Purpose: Floods outward from the given node, marking visited nodes with
+//			the number of hops from a node with an entity. If we ever mark
+//			the outside_node for this tree, we've leaked.
+// Input  : node - 
+//			dist - 
+//-----------------------------------------------------------------------------
+void FloodPortals_r (node_t *node, int dist)
+{
+	portal_t	*p;
+	int			s;
+
+	node->occupied = dist;
+
+	for (p=node->portals ; p ; p = p->next[s])
+	{
+		s = (p->nodes[1] == node);
+
+		// Skip nodes that have already been marked.
+		if (p->nodes[!s]->occupied)
+			continue;
+
+		// Skip portals that lead to or from nodes with solid contents.
+		if (!Portal_EntityFlood (p, s))
+			continue;
+
+		FloodPortals_r (p->nodes[!s], dist+1);
+	}
+}
+
+void FloodAreaLeak_r( node_t *node, int dist )
+{
+	portal_t	*p;
+	int			s;
+
+	node->occupied = dist;
+
+	for (p=node->portals ; p ; p = p->next[s])
+	{
+		s = (p->nodes[1] == node);
+
+		if (p->nodes[!s]->occupied)
+			continue;
+
+		if (!Portal_AreaLeakFlood (p, s))
+			continue;
+
+		FloodAreaLeak_r( p->nodes[!s], dist+1 );
+	}
+}
+
+void ClearOccupied_r( node_t *headnode )
+{
+	if ( !headnode )
+		return;
+
+	headnode->occupied = 0;
+	ClearOccupied_r( headnode->children[0] );
+	ClearOccupied_r( headnode->children[1] );
+}
+
+void FloodAreaLeak( node_t *headnode, node_t *pFirstSide )
+{
+	ClearOccupied_r( headnode );
+	FloodAreaLeak_r( pFirstSide, 2 );
+}
+
+//-----------------------------------------------------------------------------
+// Purpose: For the given entity at the given origin, finds the leaf node in the
+//			BSP tree that the entity occupies.
+//
+//			We then flood outward from that leaf to see if the entity leaks.
+// Input  : headnode - 
+//			origin - 
+//			occupant - 
+// Output : Returns false if the entity is in solid, true if it is not.
+//-----------------------------------------------------------------------------
+qboolean PlaceOccupant (node_t *headnode, Vector& 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)
+	{
+		plane = &g_MainMap->mapplanes[node->planenum];
+		d = DotProduct (origin, plane->normal) - plane->dist;
+		if (d >= 0)
+			node = node->children[0];
+		else
+			node = node->children[1];
+	}
+
+	if (node->contents == CONTENTS_SOLID)
+		return false;
+
+	node->occupant = occupant;
+
+	// Flood outward from here to see if this entity leaks.
+	FloodPortals_r (node, 1);
+
+	return true;
+}
+
+/*
+=============
+FloodEntities
+
+Marks all nodes that can be reached by entites
+=============
+*/
+qboolean FloodEntities (tree_t *tree)
+{
+	int		i;
+	Vector	origin;
+	char	*cl;
+	qboolean	inside;
+	node_t *headnode;
+
+	headnode = tree->headnode;
+	qprintf ("--- FloodEntities ---\n");
+	inside = false;
+	tree->outside_node.occupied = 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
+
+		// nudge playerstart around if needed so clipping hulls allways
+		// have a valid point
+		if (!strcmp (cl, "info_player_start"))
+		{
+			int	x, y;
+
+			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;
+						goto gotit;
+					}
+					origin[0] -= x;
+					origin[1] -= y;
+				}
+			}
+gotit: ;
+		}
+		else
+		{
+			if (PlaceOccupant (headnode, origin, &entities[i]))
+				inside = true;
+		}
+	}
+
+	if (!inside)
+	{
+		qprintf ("no entities in open -- no filling\n");
+	}
+
+	if (tree->outside_node.occupied)
+	{
+		qprintf ("entity reached from outside -- no filling\n" );
+	}
+
+	return (qboolean)(inside && !tree->outside_node.occupied);
+}
+
+
+/*
+=========================================================
+
+FLOOD AREAS
+
+=========================================================
+*/
+
+int		c_areas;
+
+bool IsAreaportalNode( node_t *node )
+{
+	return ( node->contents & CONTENTS_AREAPORTAL ) ? true : false;
+}
+/*
+=============
+FloodAreas_r
+=============
+*/
+
+void FloodAreas_r (node_t *node, portal_t *pSeeThrough)
+{
+	portal_t	*p;
+	int			s;
+	bspbrush_t	*b;
+	entity_t	*e;
+
+	if ( IsAreaportalNode(node) )
+	{
+		// this node is part of an area portal
+		b = AreaportalBrushForNode( node );
+		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])
+		{
+			Warning("WARNING: areaportal entity %i (brush %i) touches > 2 areas\n", b->original->entitynum, b->original->id );
+			return;
+		}
+		
+		if (e->portalareas[0])
+		{
+			e->portalareas[1] = c_areas;
+			e->m_pPortalsLeadingIntoAreas[1] = pSeeThrough;
+		}
+		else
+		{
+			e->portalareas[0] = c_areas;
+			e->m_pPortalsLeadingIntoAreas[0] = pSeeThrough;
+		}
+
+		return;
+	}
+
+	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], p);
+	}
+}
+
+/*
+=============
+FindAreas_r
+
+Just decend the tree, and for each node that hasn't had an
+area set, flood fill out from there
+=============
+*/
+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 (IsAreaportalNode(node))
+		return;
+
+	c_areas++;
+	FloodAreas_r (node, NULL);
+}
+
+
+void ReportAreaportalLeak( tree_t *tree, node_t *node )
+{
+	portal_t *p, *pStart = NULL;
+	int s;
+
+	// Find a portal out of this areaportal into empty space
+	for (p=node->portals ; p ; p = p->next[s])
+	{
+		s = (p->nodes[1] == node);
+		if ( !Portal_EntityFlood( p, !s ) )
+			continue;
+		if ( p->nodes[!s]->contents & CONTENTS_AREAPORTAL )
+			continue;
+
+		pStart = p;
+		break;
+	}
+
+	if ( pStart )
+	{
+		s = pStart->nodes[0] == node;
+		Assert(!(pStart->nodes[s]->contents & CONTENTS_AREAPORTAL) );
+		// flood fill the area outside this areaportal brush
+		FloodAreaLeak( tree->headnode, pStart->nodes[s] );
+
+		// find the portal into the longest path around the portal
+		portal_t *pBest = NULL;
+		int bestDist = 0;
+		for (p=node->portals ; p ; p = p->next[s])
+		{
+			if ( p == pStart )
+				continue;
+
+			s = (p->nodes[1] == node);
+			if ( p->nodes[!s]->occupied > bestDist )
+			{
+				pBest = p;
+				bestDist = p->nodes[!s]->occupied;
+			}
+		}
+		if ( pBest )
+		{
+			s = (pBest->nodes[0] == node);
+			// write the linefile that goes from pBest to pStart
+			AreaportalLeakFile( tree, pStart, pBest, pBest->nodes[s] );
+		}
+	}
+}
+
+
+/*
+=============
+SetAreaPortalAreas_r
+
+Just decend the tree, and for each node that hasn't had an
+area set, flood fill out from there
+=============
+*/
+void SetAreaPortalAreas_r (tree_t *tree, node_t *node)
+{
+	bspbrush_t	*b;
+	entity_t	*e;
+
+	if (node->planenum != PLANENUM_LEAF)
+	{
+		SetAreaPortalAreas_r (tree, node->children[0]);
+		SetAreaPortalAreas_r (tree, node->children[1]);
+		return;
+	}
+
+	if (IsAreaportalNode(node))
+	{
+		if (node->area)
+			return;		// already set
+
+		b = AreaportalBrushForNode( node );
+		e = &entities[b->original->entitynum];
+		node->area = e->portalareas[0];
+		if (!e->portalareas[1])
+		{
+			ReportAreaportalLeak( tree, node );
+			Warning("\nBrush %i: areaportal brush doesn't touch two areas\n", b->original->id);
+			return;
+		}
+	}
+}
+
+
+// Return a positive value between 0 and 2*PI telling the angle distance
+// from flBaseAngle to flTestAngle.
+float AngleOffset( float flBaseAngle, float flTestAngle )
+{
+	while( flTestAngle > flBaseAngle )
+		flTestAngle -= 2 * M_PI;
+
+	return fmod( flBaseAngle - flTestAngle, (float) (2 * M_PI) );
+}
+
+
+int FindUniquePoints( const Vector2D *pPoints, int nPoints, int *indexMap, int nMaxIndexMapPoints, float flTolerance )
+{
+	float flToleranceSqr = flTolerance * flTolerance;
+
+	// This could be slightly more efficient.
+	int nUniquePoints = 0;
+	for ( int i=0; i < nPoints; i++ )
+	{
+		int j;
+		for ( j=0; j < nUniquePoints; j++ )
+		{
+			if ( pPoints[i].DistToSqr( pPoints[indexMap[j]] ) < flToleranceSqr )
+				break;
+		}
+		if ( j == nUniquePoints )
+		{
+			if ( nUniquePoints >= nMaxIndexMapPoints )
+				Error( "FindUniquePoints: overflowed unique point list (size %d).", nMaxIndexMapPoints );
+
+			indexMap[nUniquePoints++] = i;
+		}
+	}
+	
+	return nUniquePoints;
+}
+
+// Build a 2D convex hull of the set of points.
+// This essentially giftwraps the points as it walks around the perimeter.
+int Convex2D( Vector2D const *pPoints, int nPoints, int *indices, int nMaxIndices )
+{
+	int nIndices = 0;
+	bool touched[512];
+	int indexMap[512];
+
+	if( nPoints == 0 )
+		return 0;
+
+
+	// If we don't collapse the points into a unique set, we can loop around forever
+	// and max out nMaxIndices.
+	nPoints = FindUniquePoints( pPoints, nPoints, indexMap, ARRAYSIZE( indexMap ), 0.1f );
+	memset( touched, 0, nPoints*sizeof(touched[0]) );
+
+	// Find the (lower) left side.
+	int i;
+	int iBest = 0;
+	for( i=1; i < nPoints; i++ )
+	{
+		if( pPoints[indexMap[i]].x < pPoints[indexMap[iBest]].x ||
+			(pPoints[indexMap[i]].x == pPoints[indexMap[iBest]].x && pPoints[indexMap[i]].y < pPoints[indexMap[iBest]].y) )
+		{
+			iBest = i;
+		}
+	}
+
+	touched[iBest] = true;
+	indices[0] = indexMap[iBest];
+	nIndices = 1;
+
+	Vector2D curEdge( 0, 1 );
+
+	// Wind around clockwise.
+	while( 1 )
+	{
+		Vector2D const *pStartPoint = &pPoints[ indices[nIndices-1] ];
+
+		float flEdgeAngle = atan2( curEdge.y, curEdge.x );
+		
+		int iMinAngle = -1;
+		float flMinAngle = 5000;
+
+		for( i=0; i < nPoints; i++ )
+		{
+			Vector2D vTo = pPoints[indexMap[i]] - *pStartPoint;
+			float flDistToSqr = vTo.LengthSqr();
+			if ( flDistToSqr <= 0.1f )
+				continue;
+
+			// Get the angle from the edge to this point.
+			float flAngle = atan2( vTo.y, vTo.x );
+			flAngle = AngleOffset( flEdgeAngle, flAngle );
+
+			if( fabs( flAngle - flMinAngle ) < 0.00001f )
+			{
+				float flDistToTestSqr = pStartPoint->DistToSqr( pPoints[iMinAngle] );
+
+				// If the angle is the same, pick the point farthest away.
+				// unless the current one is closing the face loop
+				if ( iMinAngle != indices[0] && flDistToSqr > flDistToTestSqr )
+				{
+					flMinAngle = flAngle;
+					iMinAngle = indexMap[i];
+				}
+			}
+			else if( flAngle < flMinAngle )
+			{
+				flMinAngle = flAngle;
+				iMinAngle = indexMap[i];
+			}
+		}
+
+		if( iMinAngle == -1 )
+		{
+			// Couldn't find a point?
+			Assert( false );
+			break;
+		}
+		else if( iMinAngle == indices[0] )
+		{
+			// Finished.
+			break;
+		}
+		else
+		{
+			// Add this point.
+			if( nIndices >= nMaxIndices )
+				break;
+
+			for ( int jj = 0; jj < nIndices; jj++ )
+			{
+				// if this assert hits, this routine is broken and is generating a spiral
+				// rather than a closed polygon - basically an edge overlap of some kind
+				Assert(indices[jj] != iMinAngle );
+			}
+
+			indices[nIndices] = iMinAngle;
+			++nIndices;
+		}
+
+		curEdge = pPoints[indices[nIndices-1]] - pPoints[indices[nIndices-2]];
+	}
+	
+	return nIndices;
+}
+
+void FindPortalsLeadingToArea_R( 
+	node_t *pHeadNode, 
+	int iSrcArea, 
+	int iDestArea, 
+	plane_t *pPlane, 
+	CUtlVector<portal_t*> &portals )
+{
+	if (pHeadNode->planenum != PLANENUM_LEAF)
+	{
+		FindPortalsLeadingToArea_R( pHeadNode->children[0], iSrcArea, iDestArea, pPlane, portals );
+		FindPortalsLeadingToArea_R( pHeadNode->children[1], iSrcArea, iDestArea, pPlane, portals );
+		return;
+	}
+
+	// Ok.. this is a leaf, check its portals.
+	int s;
+	for( portal_t *p = pHeadNode->portals; p ;p = p->next[!s] )
+	{
+		s = (p->nodes[0] == pHeadNode);
+
+		if( !p->nodes[0]->occupied || !p->nodes[1]->occupied )
+			continue;
+	
+		if( p->nodes[1]->area == iDestArea && p->nodes[0]->area == iSrcArea ||
+			p->nodes[0]->area == iDestArea && p->nodes[1]->area == iSrcArea )
+		{
+			// Make sure the plane normals point the same way.
+			plane_t *pMapPlane = &g_MainMap->mapplanes[p->onnode->planenum];
+			float flDot = fabs( pMapPlane->normal.Dot( pPlane->normal ) );
+			if( fabs( 1 - flDot ) < 0.01f )
+			{
+				Vector vPlanePt1 = pPlane->normal * pPlane->dist;
+				Vector vPlanePt2 = pMapPlane->normal * pMapPlane->dist;
+
+				if( vPlanePt1.DistToSqr( vPlanePt2 ) < 0.01f )
+				{
+					portals.AddToTail( p );
+				}
+			}
+		}
+	}
+}
+
+
+void EmitClipPortalGeometry( node_t *pHeadNode, portal_t *pPortal, int iSrcArea, dareaportal_t *dp )
+{
+	// Build a list of all the points in portals from the same original face.
+	CUtlVector<portal_t*> portals;
+	FindPortalsLeadingToArea_R( 
+		pHeadNode, 
+		iSrcArea, 
+		dp->otherarea, 
+		&pPortal->plane,
+		portals );
+
+	CUtlVector<Vector> points;
+	for( int iPortal=0; iPortal < portals.Size(); iPortal++ )
+	{
+		portal_t *pPointPortal = portals[iPortal];
+		winding_t *pWinding = pPointPortal->winding;
+		for( int i=0; i < pWinding->numpoints; i++ )
+		{
+			points.AddToTail( pWinding->p[i] );
+		}
+	}
+
+	// Get the 2D convex hull.
+
+	//// First transform them into a plane.
+	QAngle vAngles;
+	Vector vecs[3];
+
+	VectorAngles( pPortal->plane.normal, vAngles );
+	AngleVectors( vAngles, &vecs[0], &vecs[1], &vecs[2] );
+	VMatrix mTransform;
+	mTransform.Identity();
+	mTransform.SetBasisVectors( vecs[0], vecs[1], vecs[2] );
+	VMatrix mInvTransform = mTransform.Transpose();
+
+	int i;
+	CUtlVector<Vector2D> points2D;
+	for( i=0; i < points.Size(); i++ )
+	{
+		Vector vTest = mTransform * points[i];
+		points2D.AddToTail( Vector2D( vTest.y, vTest.z ) );
+	}
+
+	// Build the hull.
+	int indices[512];
+	int nIndices = Convex2D( points2D.Base(), points2D.Size(), indices, 512 );
+
+	// Output the hull.
+	dp->m_FirstClipPortalVert = g_nClipPortalVerts;
+	dp->m_nClipPortalVerts = nIndices;
+
+	if ( nIndices >= 32 )
+	{
+		Warning( "Warning: area portal has %d verts. Could be a vbsp bug.\n", nIndices );
+	}
+
+	if( dp->m_FirstClipPortalVert + dp->m_nClipPortalVerts >= MAX_MAP_PORTALVERTS )
+	{
+		Vector *p = pPortal->winding->p;
+		Error( "MAX_MAP_PORTALVERTS (probably a broken areaportal near %.1f %.1f %.1f ", p->x, p->y, p->z );
+	}
+	
+	for( i=0; i < nIndices; i++ )
+	{
+		g_ClipPortalVerts[g_nClipPortalVerts] = points[ indices[i] ];
+		++g_nClipPortalVerts;
+	}
+}
+
+
+// Sets node_t::area for non-leaf nodes (this allows an optimization in the renderer).
+void SetNodeAreaIndices_R( node_t *node )
+{
+	// All leaf area indices should already be set.
+	if( node->planenum == PLANENUM_LEAF )
+		return;
+
+	// Have the children set their area indices.
+	SetNodeAreaIndices_R( node->children[0] );
+	SetNodeAreaIndices_R( node->children[1] );
+
+	// If all children (leaves or nodes) are in the same area, then set our area
+	// to this area as well. Otherwise, set it to -1.
+	if( node->children[0]->area == node->children[1]->area )
+		node->area = node->children[0]->area;
+	else
+		node->area = -1;	
+}
+
+
+/*
+=============
+EmitAreaPortals
+
+=============
+*/
+void EmitAreaPortals (node_t *headnode)
+{
+	entity_t		*e;
+	dareaportal_t	*dp;
+
+	if (c_areas > MAX_MAP_AREAS)
+		Error ("Map is split into too many unique areas (max = %d)\nProbably too many areaportals", MAX_MAP_AREAS);
+	numareas = c_areas+1;
+	numareaportals = 1;		// leave 0 as an error
+
+	// Reset the clip portal vert info.
+	g_nClipPortalVerts = 0;
+
+	for (int iSrcArea=1 ; iSrcArea<=c_areas ; iSrcArea++)
+	{
+		dareas[iSrcArea].firstareaportal = numareaportals;
+		for (int j=0 ; j<num_entities ; j++)
+		{
+			e = &entities[j];
+			if (!e->areaportalnum)
+				continue;
+			
+			if (e->portalareas[0] == iSrcArea || e->portalareas[1] == iSrcArea)
+			{
+				int iSide = (e->portalareas[0] == iSrcArea);
+
+				// We're only interested in the portal that divides the two areas.
+				// One of the portals that leads into the CONTENTS_AREAPORTAL just bounds
+				// the same two areas but the other bounds two different ones.
+				portal_t *pLeadingPortal = e->m_pPortalsLeadingIntoAreas[0];
+				if( pLeadingPortal->nodes[0]->area == pLeadingPortal->nodes[1]->area )
+					pLeadingPortal = e->m_pPortalsLeadingIntoAreas[1];
+
+				if( pLeadingPortal )
+				{
+					Assert( pLeadingPortal->nodes[0]->area != pLeadingPortal->nodes[1]->area );
+
+					dp = &dareaportals[numareaportals];
+					numareaportals++;
+
+					dp->m_PortalKey = e->areaportalnum;
+					dp->otherarea = e->portalareas[iSide];
+					dp->planenum = pLeadingPortal->onnode->planenum;
+
+					Assert( pLeadingPortal->nodes[0]->planenum == PLANENUM_LEAF );
+					Assert( pLeadingPortal->nodes[1]->planenum == PLANENUM_LEAF );
+
+					if( pLeadingPortal->nodes[0]->area == dp->otherarea )
+					{
+						// Use the flipped version of the plane.
+						dp->planenum = (dp->planenum & ~1) | (~dp->planenum & 1);
+					}
+
+					EmitClipPortalGeometry( headnode, pLeadingPortal, iSrcArea, dp );
+				}
+			}
+		}
+
+		dareas[iSrcArea].numareaportals = numareaportals - dareas[iSrcArea].firstareaportal;
+	}
+
+	SetNodeAreaIndices_R( headnode );
+
+	qprintf ("%5i numareas\n", numareas);
+	qprintf ("%5i numareaportals\n", numareaportals);
+}
+
+/*
+=============
+FloodAreas
+
+Mark each leaf with an area, bounded by CONTENTS_AREAPORTAL
+=============
+*/
+void FloodAreas (tree_t *tree)
+{
+	int start = Plat_FloatTime();
+	qprintf ("--- FloodAreas ---\n");
+	Msg("Processing areas...");
+	FindAreas_r (tree->headnode);
+	SetAreaPortalAreas_r (tree, tree->headnode);
+	qprintf ("%5i areas\n", c_areas);
+	Msg("done (%d)\n", (int)(Plat_FloatTime() - start) );
+}
+
+//======================================================
+
+int		c_outside;
+int		c_inside;
+int		c_solid;
+
+void FillOutside_r (node_t *node)
+{
+	if (node->planenum != PLANENUM_LEAF)
+	{
+		FillOutside_r (node->children[0]);
+		FillOutside_r (node->children[1]);
+		return;
+	}
+
+	// anything not reachable by an entity
+	// can be filled away
+	if (!node->occupied)
+	{
+		if (node->contents != CONTENTS_SOLID)
+		{
+			c_outside++;
+			node->contents = CONTENTS_SOLID;
+		}
+		else
+			c_solid++;
+	}
+	else
+		c_inside++;
+
+}
+
+/*
+=============
+FillOutside
+
+Fill all nodes that can't be reached by entities
+=============
+*/
+void FillOutside (node_t *headnode)
+{
+	c_outside = 0;
+	c_inside = 0;
+	c_solid = 0;
+	qprintf ("--- FillOutside ---\n");
+	FillOutside_r (headnode);
+	qprintf ("%5i solid leafs\n", c_solid);
+	qprintf ("%5i leafs filled\n", c_outside);
+	qprintf ("%5i inside leafs\n", c_inside);
+}
+
+
+static float ComputeDistFromPlane( winding_t *pWinding, plane_t *pPlane, float maxdist )
+{
+	float totaldist = 0.0f;
+	for (int i = 0; i < pWinding->numpoints; ++i)
+	{
+		totaldist += fabs(DotProduct( pPlane->normal, pWinding->p[i] ) - pPlane->dist);
+		if (totaldist > maxdist)
+			return totaldist;
+	}
+	return totaldist;
+}
+
+
+//-----------------------------------------------------------------------------
+// Display portal error
+//-----------------------------------------------------------------------------
+static void DisplayPortalError( portal_t *p, int viscontents )
+{
+	char contents[3][1024];
+	PrintBrushContentsToString( p->nodes[0]->contents, contents[0], sizeof( contents[0] ) );
+	PrintBrushContentsToString( p->nodes[1]->contents, contents[1], sizeof( contents[1] ) );
+	PrintBrushContentsToString( viscontents, contents[2], sizeof( contents[2] ) );
+
+	Vector center;
+	WindingCenter( p->winding, center );
+	Warning( "\nFindPortalSide: Couldn't find a good match for which brush to assign to a portal near (%.1f %.1f %.1f)\n", center.x, center.y, center.z);
+	Warning( "Leaf 0 contents: %s\n", contents[0] );
+	Warning( "Leaf 1 contents: %s\n", contents[1] );
+	Warning( "viscontents (node 0 contents ^ node 1 contents): %s\n", contents[2] );
+	Warning( "This means that none of the brushes in leaf 0 or 1 that touches the portal has %s\n", contents[2] );
+	Warning( "Check for a huge brush enclosing the coordinates above that has contents %s\n", contents[2] );
+	Warning( "Candidate brush IDs: " );
+
+	CUtlVector<int> listed;
+	for (int j=0 ; j<2 ; j++)
+	{
+		node_t *n = p->nodes[j];
+		for (bspbrush_t *bb=n->brushlist ; bb ; bb=bb->next)
+		{
+			mapbrush_t *brush = bb->original;
+			if ( brush->contents & viscontents )
+			{
+				if ( listed.Find( brush->brushnum ) == -1 )
+				{
+					listed.AddToTail( brush->brushnum );
+					Warning( "Brush %d: ", brush->id );
+				}
+			}
+		}
+	}
+	Warning( "\n\n" );
+}
+
+
+//==============================================================
+
+/*
+============
+FindPortalSide
+
+Finds a brush side to use for texturing the given portal
+============
+*/
+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		bestdist;
+	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;
+	bestdist = 1000000;
+
+	for (j=0 ; j<2 ; j++)
+	{
+		n = p->nodes[j];
+		p1 = &g_MainMap->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->bevel)
+					continue;
+				if (side->texinfo == TEXINFO_NODE)
+					continue;		// non-visible
+
+				if ((side->planenum&~1) == planenum)
+				{	// exact match
+					bestside = &brush->original_sides[i];
+					bestdist = 0.0f;
+					goto gotit;
+				}
+
+				p2 = &g_MainMap->mapplanes[side->planenum&~1];
+
+				float dist = ComputeDistFromPlane( p->winding, p2, bestdist );
+				if (dist < bestdist)
+				{
+					bestside = side;
+					bestdist = dist;
+				}
+			}
+		}
+	}
+
+gotit:
+	if (!bestside)
+		qprintf ("WARNING: side not found for portal\n");
+
+	// Compute average dist, check for problems...
+	if ((bestdist / p->winding->numpoints) > 2)
+	{
+		static int nWarnCount = 0;
+		if ( nWarnCount < 8 )
+		{
+			DisplayPortalError( p, viscontents );
+			if ( ++nWarnCount == 8 )
+			{
+				Warning("*** Suppressing further FindPortalSide errors.... ***\n" );
+			}
+		}
+	}
+
+	p->sidefound = true;
+	p->side = bestside;
+}
+
+
+/*
+===============
+MarkVisibleSides_r
+
+===============
+*/
+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;
+	}
+
+	// empty leafs are never boundary leafs
+	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->visible = true;
+	}
+
+}
+
+/*
+=============
+MarkVisibleSides
+
+=============
+*/
+// UNDONE: Put detail brushes in a separate list (not mapbrushes) ?
+void MarkVisibleSides (tree_t *tree, int startbrush, int endbrush, int detailScreen)
+{
+	int		i, j;
+	mapbrush_t	*mb;
+	int		numsides;
+	qboolean detail;
+
+	qprintf ("--- MarkVisibleSides ---\n");
+
+	// clear all the visible flags
+	for (i=startbrush ; i<endbrush ; i++)
+	{
+		mb = &g_MainMap->mapbrushes[i];
+
+		if ( detailScreen != FULL_DETAIL )
+		{
+			qboolean onlyDetail = (detailScreen==ONLY_DETAIL)?true:false;
+			// true for detail brushes
+			detail = (mb->contents & CONTENTS_DETAIL) ? true : false;
+			if ( onlyDetail ^ detail )
+			{
+				// both of these must have the same value or we're not interested in this brush
+				continue;
+			}
+		}
+
+		numsides = mb->numsides;
+		for (j=0 ; j<numsides ; j++)
+			mb->original_sides[j].visible = false;
+	}
+
+	// set visible flags on the sides that are used by portals
+	MarkVisibleSides_r (tree->headnode);
+}
+
+
+//-----------------------------------------------------------------------------
+// Used to determine which sides are visible
+//-----------------------------------------------------------------------------
+void MarkVisibleSides (tree_t *tree, mapbrush_t **ppBrushes, int nCount )
+{
+	qprintf ("--- MarkVisibleSides ---\n");
+
+	// clear all the visible flags
+	int	i, j;
+	for ( i=0; i < nCount; ++i )
+	{
+		mapbrush_t *mb = ppBrushes[i];
+		int numsides = mb->numsides;
+		for (j=0 ; j<numsides ; j++)
+		{
+			mb->original_sides[j].visible = false;
+		}
+	}
+
+	// set visible flags on the sides that are used by portals
+	MarkVisibleSides_r( tree->headnode );
+}
+