123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422 |
- /*
- ===========================================================================
- Doom 3 BFG Edition GPL Source Code
- Copyright (C) 1993-2012 id Software LLC, a ZeniMax Media company.
- This file is part of the Doom 3 BFG Edition GPL Source Code ("Doom 3 BFG Edition Source Code").
- Doom 3 BFG Edition 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 BFG Edition 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 BFG Edition Source Code. If not, see <http://www.gnu.org/licenses/>.
- In addition, the Doom 3 BFG Edition 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 BFG Edition 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() {
- 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() {
- Shutdown();
- }
- /*
- ================
- idPVS::GetPortalCount
- ================
- */
- int idPVS::GetPortalCount() 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() {
- int i, j, n, cp;
- exitPortal_t portal;
- pvsArea_t *area;
- pvsPortal_t *p, **portalPtrs;
- if ( !numPortals ) {
- return;
- }
- pvsPortals = new (TAG_PVS) pvsPortal_t[numPortals];
- pvsAreas = new (TAG_PVS) pvsArea_t[numAreas];
- memset( pvsAreas, 0, numAreas * sizeof( *pvsAreas ) );
- cp = 0;
- portalPtrs = new (TAG_PVS) 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 (TAG_PVS) byte[portalVisBytes];
- memset( p->vis, 0, portalVisBytes );
- p->mightSee = new (TAG_PVS) 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() {
- 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() 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() 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() 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 (TAG_PVS) 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 (TAG_PVS) 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() 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() 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() 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() {
- int totalVisibleAreas;
- Shutdown();
- numAreas = gameRenderWorld->NumAreas();
- if ( numAreas <= 0 ) {
- return;
- }
- connectedAreas = new (TAG_PVS) bool[numAreas];
- areaQueue = new (TAG_PVS) int[numAreas];
- areaVisBytes = ( ((numAreas+31)&~31) >> 3);
- areaVisLongs = areaVisBytes/sizeof(long);
- areaPVS = new (TAG_PVS) 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 (TAG_PVS) 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() {
- if ( connectedAreas ) {
- delete connectedAreas;
- connectedAreas = NULL;
- }
- if ( areaQueue ) {
- delete areaQueue;
- areaQueue = NULL;
- }
- if ( areaPVS ) {
- delete areaPVS;
- areaPVS = NULL;
- }
- 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 = { 0 };
- 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" );
- return 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" );
- return;
- }
- 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.Warning( "idPVS::InCurrentPVS: invalid handle" );
- return false;
- }
- 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.Warning( "idPVS::InCurrentPVS: invalid handle" );
- return false;
- }
- 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.Warning( "idPVS::InCurrentPVS: invalid handle" );
- return false;
- }
- 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.Warning( "idPVS::InCurrentPVS: invalid handle" );
- return false;
- }
- 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" );
- return;
- }
- 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 );
- }
- }
- }
- }
- /*
- ================
- 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;
- }
|