DOOM-3/neo/d3xp/Pvs.cpp

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

Doom 3 GPL Source Code
Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company. 

This file is part of the Doom 3 GPL Source Code (?Doom 3 Source Code?).  

Doom 3 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.

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

In addition, the Doom 3 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 Doom 3 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.

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

#include "../idlib/precompiled.h"
#pragma hdrstop

#include "Game_local.h"

#define MAX_BOUNDS_AREAS	16


typedef struct pvsPassage_s {
	byte *				canSee;		// bit set for all portals that can be seen through this passage
} pvsPassage_t;


typedef struct pvsPortal_s {
	int					areaNum;	// area this portal leads to
	idWinding *			w;			// winding goes counter clockwise seen from the area this portal is part of
	idBounds			bounds;		// winding bounds
	idPlane				plane;		// winding plane, normal points towards the area this portal leads to
	pvsPassage_t *		passages;	// passages to portals in the area this portal leads to
	bool				done;		// true if pvs is calculated for this portal
	byte *				vis;		// PVS for this portal
	byte *				mightSee;	// used during construction
} pvsPortal_t;


typedef struct pvsArea_s {
	int					numPortals;	// number of portals in this area
	idBounds			bounds;		// bounds of the whole area
	pvsPortal_t **		portals;	// array with pointers to the portals of this area
} pvsArea_t;


typedef struct pvsStack_s {
	struct pvsStack_s *	next;		// next stack entry
	byte *				mightSee;	// bit set for all portals that might be visible through this passage/portal stack
} pvsStack_t;


/*
================
idPVS::idPVS
================
*/
idPVS::idPVS( void ) {
	int i;

	numAreas = 0;
	numPortals = 0;

	connectedAreas = NULL;
	areaQueue = NULL;
	areaPVS = NULL;

	for ( i = 0; i < MAX_CURRENT_PVS; i++ ) {
		currentPVS[i].handle.i = -1;
		currentPVS[i].handle.h = 0;
		currentPVS[i].pvs = NULL;
	}

	pvsAreas = NULL;
	pvsPortals = NULL;
}

/*
================
idPVS::~idPVS
================
*/
idPVS::~idPVS( void ) {
	Shutdown();
}

/*
================
idPVS::GetPortalCount
================
*/
int idPVS::GetPortalCount( void ) const {
	int i, na, np;

	na = gameRenderWorld->NumAreas();
	np = 0;
	for ( i = 0; i < na; i++ ) {
		np += gameRenderWorld->NumPortalsInArea( i );
	}
	return np;
}

/*
================
idPVS::CreatePVSData
================
*/
void idPVS::CreatePVSData( void ) {
	int i, j, n, cp;
	exitPortal_t portal;
	pvsArea_t *area;
	pvsPortal_t *p, **portalPtrs;

	if ( !numPortals ) {
		return;
	}

	pvsPortals = new pvsPortal_t[numPortals];
	pvsAreas = new pvsArea_t[numAreas];
	memset( pvsAreas, 0, numAreas * sizeof( *pvsAreas ) );

	cp = 0;
	portalPtrs = new pvsPortal_t*[numPortals];

	for ( i = 0; i < numAreas; i++ ) {

		area = &pvsAreas[i];
		area->bounds.Clear();
		area->portals = portalPtrs + cp;

		n = gameRenderWorld->NumPortalsInArea( i );

		for ( j = 0; j < n; j++ ) {

			portal = gameRenderWorld->GetPortal( i, j );

			p = &pvsPortals[cp++];
			// the winding goes counter clockwise seen from this area
			p->w = portal.w->Copy();
			p->areaNum = portal.areas[1];	// area[1] is always the area the portal leads to

			p->vis = new byte[portalVisBytes];
			memset( p->vis, 0, portalVisBytes );
			p->mightSee = new byte[portalVisBytes];
			memset( p->mightSee, 0, portalVisBytes );
			p->w->GetBounds( p->bounds );
			p->w->GetPlane( p->plane );
			// plane normal points to outside the area
			p->plane = -p->plane;
			// no PVS calculated for this portal yet
			p->done = false;

			area->portals[area->numPortals] = p;
			area->numPortals++;

			area->bounds += p->bounds;
		}
	}
}

/*
================
idPVS::DestroyPVSData
================
*/
void idPVS::DestroyPVSData( void ) {
	int i;

	if ( !pvsAreas ) {
		return;
	}

	// delete portal pointer array
	delete[] pvsAreas[0].portals;

	// delete all areas
	delete[] pvsAreas;
	pvsAreas = NULL;

	// delete portal data
	for ( i = 0; i < numPortals; i++ ) {
		delete[] pvsPortals[i].vis;
		delete[] pvsPortals[i].mightSee;
		delete pvsPortals[i].w;
	}

	// delete portals
	delete[] pvsPortals;
	pvsPortals = NULL;
}

/*
================
idPVS::FloodFrontPortalPVS_r
================
*/
void idPVS::FloodFrontPortalPVS_r( pvsPortal_t *portal, int areaNum ) const {
	int i, n;
	pvsArea_t *area;
	pvsPortal_t *p;

	area = &pvsAreas[ areaNum ];

	for ( i = 0; i < area->numPortals; i++ ) {
		p = area->portals[i];
		n = p - pvsPortals;
		// don't flood through if this portal is not at the front
		if ( !( portal->mightSee[ n>>3 ] & (1 << (n&7)) ) ) {
			continue;
		}
		// don't flood through if already visited this portal
		if ( portal->vis[ n>>3 ] & (1 << (n&7)) ) {
			continue;
		}
		// this portal might be visible
		portal->vis[ n>>3 ] |= (1 << (n&7));
		// flood through the portal
		FloodFrontPortalPVS_r( portal, p->areaNum );
	}
}

/*
================
idPVS::FrontPortalPVS
================
*/
void idPVS::FrontPortalPVS( void ) const {
	int i, j, k, n, p, side1, side2, areaSide;
	pvsPortal_t *p1, *p2;
	pvsArea_t *area;

	for ( i = 0; i < numPortals; i++ ) {
		p1 = &pvsPortals[i];

		for ( j = 0; j < numAreas; j++ ) {

			area = &pvsAreas[j];

			areaSide = side1 = area->bounds.PlaneSide( p1->plane );

			// if the whole area is at the back side of the portal
			if ( areaSide == PLANESIDE_BACK ) {
				continue;
			}

			for ( p = 0; p < area->numPortals; p++ ) {
	
				p2 = area->portals[p];

				// if we the whole area is not at the front we need to check
				if ( areaSide != PLANESIDE_FRONT ) {
					// if the second portal is completely at the back side of the first portal
					side1 = p2->bounds.PlaneSide( p1->plane );
					if ( side1 == PLANESIDE_BACK ) {
						continue;
					}
				}

				// if the first portal is completely at the front of the second portal
				side2 = p1->bounds.PlaneSide( p2->plane );
				if ( side2 == PLANESIDE_FRONT ) {
					continue;
				}

				// if the second portal is not completely at the front of the first portal
				if ( side1 != PLANESIDE_FRONT ) {
					// more accurate check
					for ( k = 0; k < p2->w->GetNumPoints(); k++ ) {
						// if more than an epsilon at the front side
						if ( p1->plane.Side( (*p2->w)[k].ToVec3(), ON_EPSILON ) == PLANESIDE_FRONT ) {
							break;
						}
					}
					if ( k >= p2->w->GetNumPoints() ) {
						continue;	// second portal is at the back of the first portal
					}
				}

				// if the first portal is not completely at the back side of the second portal
				if ( side2 != PLANESIDE_BACK ) {
					// more accurate check
					for ( k = 0; k < p1->w->GetNumPoints(); k++ ) {
						// if more than an epsilon at the back side
						if ( p2->plane.Side( (*p1->w)[k].ToVec3(), ON_EPSILON ) == PLANESIDE_BACK ) {
							break;
						}
					}
					if ( k >= p1->w->GetNumPoints() ) {
						continue;	// first portal is at the front of the second portal
					}
				}

				// the portal might be visible at the front
				n = p2 - pvsPortals;
				p1->mightSee[ n >> 3 ] |= 1 << (n&7);
			}
		}
	}

	// flood the front portal pvs for all portals
	for ( i = 0; i < numPortals; i++ ) {
		p1 = &pvsPortals[i];
		FloodFrontPortalPVS_r( p1, p1->areaNum );
	}
}

/*
===============
idPVS::FloodPassagePVS_r
===============
*/
pvsStack_t *idPVS::FloodPassagePVS_r( pvsPortal_t *source, const pvsPortal_t *portal, pvsStack_t *prevStack ) const {
	int i, j, n, m;
	pvsPortal_t *p;
	pvsArea_t *area;
	pvsStack_t *stack;
	pvsPassage_t *passage;
	long *sourceVis, *passageVis, *portalVis, *mightSee, *prevMightSee, more;

	area = &pvsAreas[portal->areaNum];

	stack = prevStack->next;
	// if no next stack entry allocated
	if ( !stack ) {
		stack = reinterpret_cast<pvsStack_t*>(new byte[sizeof(pvsStack_t) + portalVisBytes]);
		stack->mightSee = (reinterpret_cast<byte *>(stack)) + sizeof(pvsStack_t);
		stack->next = NULL;
		prevStack->next = stack;
	}

	// check all portals for flooding into other areas
	for ( i = 0; i < area->numPortals; i++ ) {

		passage = &portal->passages[i];

		// if this passage is completely empty
		if ( !passage->canSee ) {
			continue;
		}

		p = area->portals[i];
		n = p - pvsPortals;

		// if this portal cannot be seen through our current portal/passage stack
		if ( !( prevStack->mightSee[n >> 3] & (1 << (n & 7)) ) ) {
			continue;
		}

		// mark the portal as visible
		source->vis[n >> 3] |= (1 << (n & 7));

		// get pointers to vis data
		prevMightSee = reinterpret_cast<long *>(prevStack->mightSee);
		passageVis = reinterpret_cast<long *>(passage->canSee);
		sourceVis = reinterpret_cast<long *>(source->vis);
		mightSee = reinterpret_cast<long *>(stack->mightSee);

		more = 0;
		// use the portal PVS if it has been calculated
		if ( p->done ) {
			portalVis = reinterpret_cast<long *>(p->vis);
			for ( j = 0; j < portalVisLongs; j++ ) {
				// get new PVS which is decreased by going through this passage
				m = *prevMightSee++ & *passageVis++ & *portalVis++;
				// check if anything might be visible through this passage that wasn't yet visible
				more |= (m & ~(*sourceVis++));
				// store new PVS
				*mightSee++ = m;
			}
		}
		else {
			// the p->mightSee is implicitely stored in the passageVis
			for ( j = 0; j < portalVisLongs; j++ ) {
				// get new PVS which is decreased by going through this passage
				m = *prevMightSee++ & *passageVis++;
				// check if anything might be visible through this passage that wasn't yet visible
				more |= (m & ~(*sourceVis++));
				// store new PVS
				*mightSee++ = m;
			}
		}

		// if nothing more can be seen
		if ( !more ) {
			continue;
		}

		// go through the portal
		stack->next = FloodPassagePVS_r( source, p, stack );
	}

	return stack;
}

/*
===============
idPVS::PassagePVS
===============
*/
void idPVS::PassagePVS( void ) const {
	int i;
	pvsPortal_t *source;
	pvsStack_t *stack, *s;

	// create the passages
	CreatePassages();

	// allocate first stack entry
	stack = reinterpret_cast<pvsStack_t*>(new byte[sizeof(pvsStack_t) + portalVisBytes]);
	stack->mightSee = (reinterpret_cast<byte *>(stack)) + sizeof(pvsStack_t);
	stack->next = NULL;

	// calculate portal PVS by flooding through the passages
	for ( i = 0; i < numPortals; i++ ) {
		source = &pvsPortals[i];
		memset( source->vis, 0, portalVisBytes );
		memcpy( stack->mightSee, source->mightSee, portalVisBytes );
		FloodPassagePVS_r( source, source, stack );
		source->done = true;
	}

	// free the allocated stack
	for ( s = stack; s; s = stack ) {
		stack = stack->next;
		delete[] s;
	}

	// destroy the passages
	DestroyPassages();
}

/*
===============
idPVS::AddPassageBoundaries
===============
*/
void idPVS::AddPassageBoundaries( const idWinding &source, const idWinding &pass, bool flipClip, idPlane *bounds, int &numBounds, int maxBounds ) const {
	int			i, j, k, l;
	idVec3		v1, v2, normal;
	float		d, dist;
	bool		flipTest, front;
	idPlane		plane;


	// check all combinations	
	for ( i = 0; i < source.GetNumPoints(); i++ ) {

		l = (i + 1) % source.GetNumPoints();
		v1 = source[l].ToVec3() - source[i].ToVec3();

		// find a vertex of pass that makes a plane that puts all of the
		// vertices of pass on the front side and all of the vertices of
		// source on the back side
		for ( j = 0; j < pass.GetNumPoints(); j++ ) {

			v2 = pass[j].ToVec3() - source[i].ToVec3();

			normal = v1.Cross( v2 );
			if ( normal.Normalize() < 0.01f ) {
				continue;
			}
			dist = normal * pass[j].ToVec3();

			//
			// find out which side of the generated seperating plane has the
			// source portal
			//
			flipTest = false;
			for ( k = 0; k < source.GetNumPoints(); k++ ) {
				if ( k == i || k == l ) {
					continue;
				}
				d = source[k].ToVec3() * normal - dist;
				if ( d < -ON_EPSILON ) {
					// source is on the negative side, so we want all
					// pass and target on the positive side
					flipTest = false;
					break;
				}
				else if ( d > ON_EPSILON ) {
					// source is on the positive side, so we want all
					// pass and target on the negative side
					flipTest = true;
					break;
				}
			}
			if ( k == source.GetNumPoints() ) {
				continue;		// planar with source portal
			}

			// flip the normal if the source portal is backwards
			if (flipTest) {
				normal = -normal;
				dist = -dist;
			}

			// if all of the pass portal points are now on the positive side,
			// this is the seperating plane
			front = false;
			for ( k = 0; k < pass.GetNumPoints(); k++ ) {
				if ( k == j ) {
					continue;
				}
				d = pass[k].ToVec3() * normal - dist;
				if ( d < -ON_EPSILON ) {
					break;
				}
				else if ( d > ON_EPSILON ) {
					front = true;
				}
			}
			if ( k < pass.GetNumPoints() ) {
				continue;	// points on negative side, not a seperating plane
			}
			if ( !front ) {
				continue;	// planar with seperating plane
			}

			// flip the normal if we want the back side
			if ( flipClip ) {
				plane.SetNormal( -normal );
				plane.SetDist( -dist );
			}
			else {
				plane.SetNormal( normal );
				plane.SetDist( dist );
			}

			// check if the plane is already a passage boundary
			for ( k = 0; k < numBounds; k++ ) {
				if ( plane.Compare( bounds[k], 0.001f, 0.01f ) ) {
					break;
				}
			}
			if ( k < numBounds ) {
				break;
			}

			if ( numBounds >= maxBounds ) {
				gameLocal.Warning( "max passage boundaries." );
				break;
			}
			bounds[numBounds] = plane;
			numBounds++;
			break;
		}
	}
}

/*
================
idPVS::CreatePassages
================
*/
#define MAX_PASSAGE_BOUNDS		128

void idPVS::CreatePassages( void ) const {
	int i, j, l, n, numBounds, front, passageMemory, byteNum, bitNum;
	int sides[MAX_PASSAGE_BOUNDS];
	idPlane passageBounds[MAX_PASSAGE_BOUNDS];
	pvsPortal_t *source, *target, *p;
	pvsArea_t *area;
	pvsPassage_t *passage;
	idFixedWinding winding;
	byte canSee, mightSee, bit;

	passageMemory = 0;
	for ( i = 0; i < numPortals; i++ ) {
		source = &pvsPortals[i];
		area = &pvsAreas[source->areaNum];

		source->passages = new pvsPassage_t[area->numPortals];

		for ( j = 0; j < area->numPortals; j++ ) {
			target = area->portals[j];
			n = target - pvsPortals;

			passage = &source->passages[j];

			// if the source portal cannot see this portal
			if ( !( source->mightSee[ n>>3 ] & (1 << (n&7)) ) ) {
				// not all portals in the area have to be visible because areas are not necesarily convex
				// also no passage has to be created for the portal which is the opposite of the source
				passage->canSee = NULL;
				continue;
			}

			passage->canSee = new byte[portalVisBytes];
			passageMemory += portalVisBytes;

			// boundary plane normals point inwards
			numBounds = 0;
			AddPassageBoundaries( *(source->w), *(target->w), false, passageBounds, numBounds, MAX_PASSAGE_BOUNDS );
			AddPassageBoundaries( *(target->w), *(source->w), true, passageBounds, numBounds, MAX_PASSAGE_BOUNDS );

			// get all portals visible through this passage
			for ( byteNum = 0; byteNum < portalVisBytes; byteNum++) {

				canSee = 0;
				mightSee = source->mightSee[byteNum] & target->mightSee[byteNum];

				// go through eight portals at a time to speed things up
				for ( bitNum = 0; bitNum < 8; bitNum++ ) {

					bit = 1 << bitNum;

					if ( !( mightSee & bit ) ) {
						continue;
					}

					p = &pvsPortals[(byteNum << 3) + bitNum];
	
					if ( p->areaNum == source->areaNum ) {
						continue;
					}

					for ( front = 0, l = 0; l < numBounds; l++ ) {
						sides[l] = p->bounds.PlaneSide( passageBounds[l] );
						// if completely at the back of the passage bounding plane
						if ( sides[l] == PLANESIDE_BACK ) {
							break;
						}
						// if completely at the front
						if ( sides[l] == PLANESIDE_FRONT ) {
							front++;
						}
					}
					// if completely outside the passage
					if ( l < numBounds ) {
						continue;
					}

					// if not at the front of all bounding planes and thus not completely inside the passage
					if ( front != numBounds ) {

						winding = *p->w;

						for ( l = 0; l < numBounds; l++ ) {
							// only clip if the winding possibly crosses this plane
							if ( sides[l] != PLANESIDE_CROSS ) {
								continue;
							}
							// clip away the part at the back of the bounding plane
							winding.ClipInPlace( passageBounds[l] );
							// if completely clipped away
							if ( !winding.GetNumPoints() ) {
								break;
							}
						}
						// if completely outside the passage
						if ( l < numBounds ) {
							continue;
						}
					}

					canSee |= bit;
				}

				// store results of all eight portals
				passage->canSee[byteNum] = canSee;
			}

			// can always see the target portal
			passage->canSee[n >> 3] |= (1 << (n&7));
		}
	}
	if ( passageMemory < 1024 ) {
		gameLocal.Printf( "%5d bytes passage memory used to build PVS\n", passageMemory );
	}
	else {
		gameLocal.Printf( "%5d KB passage memory used to build PVS\n", passageMemory>>10 );
	}
}

/*
================
idPVS::DestroyPassages
================
*/
void idPVS::DestroyPassages( void ) const {
	int i, j;
	pvsPortal_t *p;
	pvsArea_t *area;

	for ( i = 0; i < numPortals; i++ ) {
		p = &pvsPortals[i];
		area = &pvsAreas[p->areaNum];
		for ( j = 0; j < area->numPortals; j++ ) {
			if ( p->passages[j].canSee ) {
				delete[] p->passages[j].canSee;
			}
		}
		delete[] p->passages;
	}
}

/*
================
idPVS::CopyPortalPVSToMightSee
================
*/
void idPVS::CopyPortalPVSToMightSee( void ) const {
	int i;
	pvsPortal_t *p;

	for ( i = 0; i < numPortals; i++ ) {
		p = &pvsPortals[i];
		memcpy( p->mightSee, p->vis, portalVisBytes );
	}
}

/*
================
idPVS::AreaPVSFromPortalPVS
================
*/
int idPVS::AreaPVSFromPortalPVS( void ) const {
	int i, j, k, areaNum, totalVisibleAreas;
	long *p1, *p2;
	byte *pvs, *portalPVS;
	pvsArea_t *area;

	totalVisibleAreas = 0;

	if ( !numPortals ) {
		return totalVisibleAreas;
	}

	memset( areaPVS, 0, numAreas * areaVisBytes );

	for ( i = 0; i < numAreas; i++ ) {
		area = &pvsAreas[i];
		pvs = areaPVS + i * areaVisBytes;

		// the area is visible to itself
		pvs[ i >> 3 ] |= 1 << (i & 7);

		if ( !area->numPortals ) {
			continue;
		}

		// store the PVS of all portals in this area at the first portal
		for ( j = 1; j < area->numPortals; j++ ) {
			p1 = reinterpret_cast<long *>(area->portals[0]->vis);
			p2 = reinterpret_cast<long *>(area->portals[j]->vis);
			for ( k = 0; k < portalVisLongs; k++ ) {
				*p1++ |= *p2++;
			}
		}

		// the portals of this area are always visible
		for ( j = 0; j < area->numPortals; j++ ) {
			k = area->portals[j] - pvsPortals;
			area->portals[0]->vis[ k >> 3 ] |= 1 << (k & 7);
		}

		// set all areas to visible that can be seen from the portals of this area
		portalPVS = area->portals[0]->vis;
		for ( j = 0; j < numPortals; j++ ) {
			// if this portal is visible
			if ( portalPVS[j>>3] & (1 << (j&7)) ) {
				areaNum = pvsPortals[j].areaNum;
				pvs[ areaNum >> 3 ] |= 1 << (areaNum & 7);
			}
		}

		// count the number of visible areas
		for ( j = 0; j < numAreas; j++ ) {
			if ( pvs[j>>3] & (1 << (j&7)) ) {
				totalVisibleAreas++;
			}
		}
	}
	return totalVisibleAreas;
}

/*
================
idPVS::Init
================
*/
void idPVS::Init( void ) {
	int totalVisibleAreas;

	Shutdown();

	numAreas = gameRenderWorld->NumAreas();
	if ( numAreas <= 0 ) {
		return;
	}

	connectedAreas = new bool[numAreas];
	areaQueue = new int[numAreas];

	areaVisBytes = ( ((numAreas+31)&~31) >> 3);
	areaVisLongs = areaVisBytes/sizeof(long);

	areaPVS = new byte[numAreas * areaVisBytes];
	memset( areaPVS, 0xFF, numAreas * areaVisBytes );

	numPortals = GetPortalCount();

	portalVisBytes = ( ((numPortals+31)&~31) >> 3);
	portalVisLongs = portalVisBytes/sizeof(long);

	for ( int i = 0; i < MAX_CURRENT_PVS; i++ ) {
		currentPVS[i].handle.i = -1;
		currentPVS[i].handle.h = 0;
		currentPVS[i].pvs = new byte[areaVisBytes];
		memset( currentPVS[i].pvs, 0, areaVisBytes );
	}

	idTimer timer;
	timer.Start();

	CreatePVSData();

	FrontPortalPVS();

	CopyPortalPVSToMightSee();

	PassagePVS();

	totalVisibleAreas = AreaPVSFromPortalPVS();

	DestroyPVSData();

	timer.Stop();

	gameLocal.Printf( "%5.0f msec to calculate PVS\n", timer.Milliseconds() );
	gameLocal.Printf( "%5d areas\n", numAreas );
	gameLocal.Printf( "%5d portals\n", numPortals );
	gameLocal.Printf( "%5d areas visible on average\n", totalVisibleAreas / numAreas );
	if ( numAreas * areaVisBytes < 1024 ) {
		gameLocal.Printf( "%5d bytes PVS data\n", numAreas * areaVisBytes );
	}
	else {
		gameLocal.Printf( "%5d KB PVS data\n", (numAreas * areaVisBytes) >> 10 );
	}
}

/*
================
idPVS::Shutdown
================
*/
void idPVS::Shutdown( void ) {
	if ( connectedAreas ) {
		delete connectedAreas;
		connectedAreas = NULL;
	}
	if ( areaQueue ) {
		delete areaQueue;
		areaQueue = NULL;
	}
	if ( areaPVS ) {
		delete areaPVS;
		areaPVS = NULL;
	}
	if ( currentPVS ) {
		for ( int i = 0; i < MAX_CURRENT_PVS; i++ ) {
			delete currentPVS[i].pvs;
			currentPVS[i].pvs = NULL;
		}
	}
}

/*
================
idPVS::GetConnectedAreas

  assumes the 'areas' array is initialized to false
================
*/
void idPVS::GetConnectedAreas( int srcArea, bool *areas ) const {
	int curArea, nextArea;
	int queueStart, queueEnd;
	int i, n;
	exitPortal_t portal;

	queueStart = -1;
	queueEnd = 0;
	areas[srcArea] = true;

	for ( curArea = srcArea; queueStart < queueEnd; curArea = areaQueue[++queueStart] ) {

		n = gameRenderWorld->NumPortalsInArea( curArea );

		for ( i = 0; i < n; i++ ) {
			portal = gameRenderWorld->GetPortal( curArea, i );

			if ( portal.blockingBits & PS_BLOCK_VIEW ) {
				continue;
			}

			// area[1] is always the area the portal leads to
			nextArea = portal.areas[1];

			// if already visited this area
			if ( areas[nextArea] ) {
				continue;
			}

			// add area to queue
			areaQueue[queueEnd++] = nextArea;
			areas[nextArea] = true;
		}
	}
}

/*
================
idPVS::GetPVSArea
================
*/
int idPVS::GetPVSArea( const idVec3 &point ) const {
	return gameRenderWorld->PointInArea( point );
}

/*
================
idPVS::GetPVSAreas
================
*/
int idPVS::GetPVSAreas( const idBounds &bounds, int *areas, int maxAreas ) const {
	return gameRenderWorld->BoundsInAreas( bounds, areas, maxAreas );
}

/*
================
idPVS::SetupCurrentPVS
================
*/
pvsHandle_t idPVS::SetupCurrentPVS( const idVec3 &source, const pvsType_t type ) const {
	int sourceArea;

	sourceArea = gameRenderWorld->PointInArea( source );

	return SetupCurrentPVS( sourceArea, type );
}

/*
================
idPVS::SetupCurrentPVS
================
*/
pvsHandle_t idPVS::SetupCurrentPVS( const idBounds &source, const pvsType_t type ) const {
	int numSourceAreas, sourceAreas[MAX_BOUNDS_AREAS];

	numSourceAreas = gameRenderWorld->BoundsInAreas( source, sourceAreas, MAX_BOUNDS_AREAS );

	return SetupCurrentPVS( sourceAreas, numSourceAreas, type );
}

/*
================
idPVS::SetupCurrentPVS
================
*/
pvsHandle_t idPVS::SetupCurrentPVS( const int sourceArea, const pvsType_t type ) const {
	int i;
	pvsHandle_t handle;

	handle = AllocCurrentPVS( *reinterpret_cast<const unsigned int *>(&sourceArea) );

	if ( sourceArea < 0 || sourceArea >= numAreas ) {
		memset( currentPVS[handle.i].pvs, 0, areaVisBytes );
		return handle;
	}

	if ( type != PVS_CONNECTED_AREAS ) {
		memcpy( currentPVS[handle.i].pvs, areaPVS + sourceArea * areaVisBytes, areaVisBytes );
	} else {
		memset( currentPVS[handle.i].pvs, -1, areaVisBytes );
	}

	if ( type == PVS_ALL_PORTALS_OPEN ) {
		return handle;
	}

	memset( connectedAreas, 0, numAreas * sizeof( *connectedAreas ) );

	GetConnectedAreas( sourceArea, connectedAreas );

	for ( i = 0; i < numAreas; i++ ) {
		if ( !connectedAreas[i] ) {
			currentPVS[handle.i].pvs[i>>3] &= ~(1 << (i&7));
		}
	}

	return handle;
}

/*
================
idPVS::SetupCurrentPVS
================
*/
pvsHandle_t idPVS::SetupCurrentPVS( const int *sourceAreas, const int numSourceAreas, const pvsType_t type ) const {
	int i, j;
	unsigned int h;
	long *vis, *pvs;
	pvsHandle_t handle;

	h = 0;
	for ( i = 0; i < numSourceAreas; i++ ) {
		h ^= *reinterpret_cast<const unsigned int *>(&sourceAreas[i]);
	}
	handle = AllocCurrentPVS( h );

	if ( !numSourceAreas || sourceAreas[0] < 0 || sourceAreas[0] >= numAreas) {
		memset( currentPVS[handle.i].pvs, 0, areaVisBytes );
		return handle;
	}

	if ( type != PVS_CONNECTED_AREAS ) {
		// merge PVS of all areas the source is in
		memcpy( currentPVS[handle.i].pvs, areaPVS + sourceAreas[0] * areaVisBytes, areaVisBytes );
		for ( i = 1; i < numSourceAreas; i++ ) {

			assert( sourceAreas[i] >= 0 && sourceAreas[i] < numAreas );

			vis = reinterpret_cast<long*>(areaPVS + sourceAreas[i] * areaVisBytes);
			pvs = reinterpret_cast<long*>(currentPVS[handle.i].pvs);
			for ( j = 0; j < areaVisLongs; j++ ) {
				*pvs++ |= *vis++;
			}
		}
	} else {
		memset( currentPVS[handle.i].pvs, -1, areaVisBytes );
	}

	if ( type == PVS_ALL_PORTALS_OPEN ) {
		return handle;
	}

	memset( connectedAreas, 0, numAreas * sizeof( *connectedAreas ) );

	// get all areas connected to any of the source areas
	for ( i = 0; i < numSourceAreas; i++ ) {
		if ( !connectedAreas[sourceAreas[i]] ) {
			GetConnectedAreas( sourceAreas[i], connectedAreas );
		}
	}

	// remove unconnected areas from the PVS
	for ( i = 0; i < numAreas; i++ ) {
		if ( !connectedAreas[i] ) {
			currentPVS[handle.i].pvs[i>>3] &= ~(1 << (i&7));
		}
	}

	return handle;
}

/*
================
idPVS::MergeCurrentPVS
================
*/
pvsHandle_t idPVS::MergeCurrentPVS( pvsHandle_t pvs1, pvsHandle_t pvs2 ) const {
	int i;
	long *pvs1Ptr, *pvs2Ptr, *ptr;
	pvsHandle_t handle;

	if ( pvs1.i < 0 || pvs1.i >= MAX_CURRENT_PVS || pvs1.h != currentPVS[pvs1.i].handle.h ||
		pvs2.i < 0 || pvs2.i >= MAX_CURRENT_PVS || pvs2.h != currentPVS[pvs2.i].handle.h ) {
		gameLocal.Error( "idPVS::MergeCurrentPVS: invalid handle" );
	}

	handle = AllocCurrentPVS( pvs1.h ^ pvs2.h );

	ptr = reinterpret_cast<long*>(currentPVS[handle.i].pvs);
	pvs1Ptr = reinterpret_cast<long*>(currentPVS[pvs1.i].pvs);
	pvs2Ptr = reinterpret_cast<long*>(currentPVS[pvs2.i].pvs);

	for ( i = 0; i < areaVisLongs; i++ ) {
		*ptr++ = *pvs1Ptr++ | *pvs2Ptr++;
	}

	return handle;
}

/*
================
idPVS::AllocCurrentPVS
================
*/
pvsHandle_t idPVS::AllocCurrentPVS( unsigned int h ) const {
	int i;
	pvsHandle_t handle;

	for ( i = 0; i < MAX_CURRENT_PVS; i++ ) {
		if ( currentPVS[i].handle.i == -1 ) {
			currentPVS[i].handle.i = i;
			currentPVS[i].handle.h = h;
			return currentPVS[i].handle;
		}
	}

	gameLocal.Error( "idPVS::AllocCurrentPVS: no free PVS left" );

	handle.i = -1;
	handle.h = 0;
	return handle;
}

/*
================
idPVS::FreeCurrentPVS
================
*/
void idPVS::FreeCurrentPVS( pvsHandle_t handle ) const {
	if ( handle.i < 0 || handle.i >= MAX_CURRENT_PVS || handle.h != currentPVS[handle.i].handle.h ) {
		gameLocal.Error( "idPVS::FreeCurrentPVS: invalid handle" );
	}
	currentPVS[handle.i].handle.i = -1;
}

/*
================
idPVS::InCurrentPVS
================
*/
bool idPVS::InCurrentPVS( const pvsHandle_t handle, const idVec3 &target ) const {
	int targetArea;

	if ( handle.i < 0 || handle.i >= MAX_CURRENT_PVS ||
		handle.h != currentPVS[handle.i].handle.h ) {
		gameLocal.Error( "idPVS::InCurrentPVS: invalid handle" );
	}

	targetArea = gameRenderWorld->PointInArea( target );

	if ( targetArea == -1 ) {
		return false;
	}

	return ( ( currentPVS[handle.i].pvs[targetArea>>3] & (1 << (targetArea&7)) ) != 0 );
}

/*
================
idPVS::InCurrentPVS
================
*/
bool idPVS::InCurrentPVS( const pvsHandle_t handle, const idBounds &target ) const {
	int i, numTargetAreas, targetAreas[MAX_BOUNDS_AREAS];

	if ( handle.i < 0 || handle.i >= MAX_CURRENT_PVS ||
		handle.h != currentPVS[handle.i].handle.h ) {
		gameLocal.Error( "idPVS::InCurrentPVS: invalid handle" );
	}

	numTargetAreas = gameRenderWorld->BoundsInAreas( target, targetAreas, MAX_BOUNDS_AREAS );

	for ( i = 0; i < numTargetAreas; i++ ) {
		if ( currentPVS[handle.i].pvs[targetAreas[i]>>3] & (1 << (targetAreas[i]&7)) ) {
			return true;
		}
	}
	return false;
}

/*
================
idPVS::InCurrentPVS
================
*/
bool idPVS::InCurrentPVS( const pvsHandle_t handle, const int targetArea ) const {

	if ( handle.i < 0 || handle.i >= MAX_CURRENT_PVS ||
		handle.h != currentPVS[handle.i].handle.h ) {
		gameLocal.Error( "idPVS::InCurrentPVS: invalid handle" );
	}

	if ( targetArea < 0 || targetArea >= numAreas ) {
		return false;
	}

	return ( ( currentPVS[handle.i].pvs[targetArea>>3] & (1 << (targetArea&7)) ) != 0 );
}

/*
================
idPVS::InCurrentPVS
================
*/
bool idPVS::InCurrentPVS( const pvsHandle_t handle, const int *targetAreas, int numTargetAreas ) const {
	int i;

	if ( handle.i < 0 || handle.i >= MAX_CURRENT_PVS ||
		handle.h != currentPVS[handle.i].handle.h ) {
		gameLocal.Error( "idPVS::InCurrentPVS: invalid handle" );
	}

	for ( i = 0; i < numTargetAreas; i++ ) {
		if ( targetAreas[i] < 0 || targetAreas[i] >= numAreas ) {
			continue;
		}
		if ( currentPVS[handle.i].pvs[targetAreas[i]>>3] & (1 << (targetAreas[i]&7)) ) {
			return true;
		}
	}
	return false;
}

/*
================
idPVS::DrawPVS
================
*/
void idPVS::DrawPVS( const idVec3 &source, const pvsType_t type ) const {
	int i, j, k, numPoints, n, sourceArea;
	exitPortal_t portal;
	idPlane plane;
	idVec3 offset;
	idVec4 *color;
	pvsHandle_t handle;

	sourceArea = gameRenderWorld->PointInArea( source );

	if ( sourceArea == -1 ) {
		return;
	}

	handle = SetupCurrentPVS( source, type );

	for ( j = 0; j < numAreas; j++ ) {

		if ( !( currentPVS[handle.i].pvs[j>>3] & (1 << (j&7)) ) ) {
			continue;
		}

		if ( j == sourceArea ) {
			color = &colorRed;
		}
		else {
			color = &colorCyan;
		}

		n = gameRenderWorld->NumPortalsInArea( j );

		// draw all the portals of the area
		for ( i = 0; i < n; i++ ) {
			portal = gameRenderWorld->GetPortal( j, i );

			numPoints = portal.w->GetNumPoints();

			portal.w->GetPlane( plane );
			offset = plane.Normal() * 4.0f;
			for ( k = 0; k < numPoints; k++ ) {
				gameRenderWorld->DebugLine( *color, (*portal.w)[k].ToVec3() + offset, (*portal.w)[(k+1)%numPoints].ToVec3() + offset );
			}
		}
	}

	FreeCurrentPVS( handle );
}

/*
================
idPVS::DrawPVS
================
*/
void idPVS::DrawPVS( const idBounds &source, const pvsType_t type ) const {
	int i, j, k, numPoints, n, num, areas[MAX_BOUNDS_AREAS];
	exitPortal_t portal;
	idPlane plane;
	idVec3 offset;
	idVec4 *color;
	pvsHandle_t handle;

	num = gameRenderWorld->BoundsInAreas( source, areas, MAX_BOUNDS_AREAS );

	if ( !num ) {
		return;
	}

	handle = SetupCurrentPVS( source, type );

	for ( j = 0; j < numAreas; j++ ) {

		if ( !( currentPVS[handle.i].pvs[j>>3] & (1 << (j&7)) ) ) {
			continue;
		}

		for ( i = 0; i < num; i++ ) {
			if ( j == areas[i] ) {
				break;
			}
		}
		if ( i < num ) {
			color = &colorRed;
		}
		else {
			color = &colorCyan;
		}

		n = gameRenderWorld->NumPortalsInArea( j );

		// draw all the portals of the area
		for ( i = 0; i < n; i++ ) {
			portal = gameRenderWorld->GetPortal( j, i );

			numPoints = portal.w->GetNumPoints();

			portal.w->GetPlane( plane );
			offset = plane.Normal() * 4.0f;
			for ( k = 0; k < numPoints; k++ ) {
				gameRenderWorld->DebugLine( *color, (*portal.w)[k].ToVec3() + offset, (*portal.w)[(k+1)%numPoints].ToVec3() + offset );
			}
		}
	}

	FreeCurrentPVS( handle );
}

/*
================
idPVS::DrawPVS
================
*/
void idPVS::DrawCurrentPVS( const pvsHandle_t handle, const idVec3 &source ) const {
	int i, j, k, numPoints, n, sourceArea;
	exitPortal_t portal;
	idPlane plane;
	idVec3 offset;
	idVec4 *color;

	if ( handle.i < 0 || handle.i >= MAX_CURRENT_PVS ||
		handle.h != currentPVS[handle.i].handle.h ) {
		gameLocal.Error( "idPVS::DrawCurrentPVS: invalid handle" );
	}

	sourceArea = gameRenderWorld->PointInArea( source );

	if ( sourceArea == -1 ) {
		return;
	}

	for ( j = 0; j < numAreas; j++ ) {

		if ( !( currentPVS[handle.i].pvs[j>>3] & (1 << (j&7)) ) ) {
			continue;
		}

		if ( j == sourceArea ) {
			color = &colorRed;
		}
		else {
			color = &colorCyan;
		}

		n = gameRenderWorld->NumPortalsInArea( j );

		// draw all the portals of the area
		for ( i = 0; i < n; i++ ) {
			portal = gameRenderWorld->GetPortal( j, i );

			numPoints = portal.w->GetNumPoints();

			portal.w->GetPlane( plane );
			offset = plane.Normal() * 4.0f;
			for ( k = 0; k < numPoints; k++ ) {
				gameRenderWorld->DebugLine( *color, (*portal.w)[k].ToVec3() + offset, (*portal.w)[(k+1)%numPoints].ToVec3() + offset );
			}
		}
	}
}

#if ASYNC_WRITE_PVS

/*
===================
idPVS::WritePVS
===================
*/
void idPVS::WritePVS( const pvsHandle_t handle, idBitMsg &msg ) {
	msg.WriteData( currentPVS[ handle.i ].pvs, areaVisBytes );
}

/*
===================
idPVS::ReadPVS
===================
*/
void idPVS::ReadPVS( const pvsHandle_t handle, const idBitMsg &msg ) {
	byte	l_pvs[ 256 ];
	int		i;

	assert( areaVisBytes <= 256 );
	msg.ReadData( l_pvs, areaVisBytes );
	if ( memcmp( l_pvs, currentPVS[ handle.i ].pvs, areaVisBytes ) ) {
		common->Printf( "PVS not matching ( %d areaVisBytes ) - server then client:\n", areaVisBytes );
		for ( i = 0; i < areaVisBytes; i++ ) {
			common->Printf( "%x ", l_pvs[ i ] );
		}
		common->Printf( "\n" );
		for ( i = 0; i < areaVisBytes; i++ ) {
			common->Printf( "%x ", currentPVS[ handle.i ].pvs[ i ] );
		}
		common->Printf( "\n" );
	}
}

#endif


#ifdef _D3XP
/*
================
idPVS::CheckAreasForPortalSky
================
*/
bool idPVS::CheckAreasForPortalSky( const pvsHandle_t handle, const idVec3 &origin ) {
	int j, sourceArea;

	if ( handle.i < 0 || handle.i >= MAX_CURRENT_PVS || handle.h != currentPVS[handle.i].handle.h ) {
		return false;
	}

	sourceArea = gameRenderWorld->PointInArea( origin );

	if ( sourceArea == -1 ) {
		return false;
	}

	for ( j = 0; j < numAreas; j++ ) {

		if ( !( currentPVS[handle.i].pvs[j>>3] & (1 << (j&7)) ) ) {
			continue;
		}

		if ( gameRenderWorld->CheckAreaForPortalSky( j ) ) {
			return true;
		}
	}

	return false;
}
#endif