Pvs.cpp

Go to the documentation of this file.

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

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