2 ===========================================================================
5 Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company.
7 This file is part of the Doom 3 GPL Source Code (?Doom 3 Source Code?).
9 Doom 3 Source Code is free software: you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation, either version 3 of the License, or
12 (at your option) any later version.
14 Doom 3 Source Code is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
19 You should have received a copy of the GNU General Public License
20 along with Doom 3 Source Code. If not, see <http://www.gnu.org/licenses/>.
22 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.
24 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.
26 ===========================================================================
29 #include "../idlib/precompiled.h"
32 #include "Game_local.h"
34 #define MAX_BOUNDS_AREAS 16
37 typedef struct pvsPassage_s {
38 byte * canSee; // bit set for all portals that can be seen through this passage
42 typedef struct pvsPortal_s {
43 int areaNum; // area this portal leads to
44 idWinding * w; // winding goes counter clockwise seen from the area this portal is part of
45 idBounds bounds; // winding bounds
46 idPlane plane; // winding plane, normal points towards the area this portal leads to
47 pvsPassage_t * passages; // passages to portals in the area this portal leads to
48 bool done; // true if pvs is calculated for this portal
49 byte * vis; // PVS for this portal
50 byte * mightSee; // used during construction
54 typedef struct pvsArea_s {
55 int numPortals; // number of portals in this area
56 idBounds bounds; // bounds of the whole area
57 pvsPortal_t ** portals; // array with pointers to the portals of this area
61 typedef struct pvsStack_s {
62 struct pvsStack_s * next; // next stack entry
63 byte * mightSee; // bit set for all portals that might be visible through this passage/portal stack
72 idPVS::idPVS( void ) {
78 connectedAreas = NULL;
82 for ( i = 0; i < MAX_CURRENT_PVS; i++ ) {
83 currentPVS[i].handle.i = -1;
84 currentPVS[i].handle.h = 0;
85 currentPVS[i].pvs = NULL;
97 idPVS::~idPVS( void ) {
103 idPVS::GetPortalCount
106 int idPVS::GetPortalCount( void ) const {
109 na = gameRenderWorld->NumAreas();
111 for ( i = 0; i < na; i++ ) {
112 np += gameRenderWorld->NumPortalsInArea( i );
122 void idPVS::CreatePVSData( void ) {
126 pvsPortal_t *p, **portalPtrs;
132 pvsPortals = new pvsPortal_t[numPortals];
133 pvsAreas = new pvsArea_t[numAreas];
134 memset( pvsAreas, 0, numAreas * sizeof( *pvsAreas ) );
137 portalPtrs = new pvsPortal_t*[numPortals];
139 for ( i = 0; i < numAreas; i++ ) {
142 area->bounds.Clear();
143 area->portals = portalPtrs + cp;
145 n = gameRenderWorld->NumPortalsInArea( i );
147 for ( j = 0; j < n; j++ ) {
149 portal = gameRenderWorld->GetPortal( i, j );
151 p = &pvsPortals[cp++];
152 // the winding goes counter clockwise seen from this area
153 p->w = portal.w->Copy();
154 p->areaNum = portal.areas[1]; // area[1] is always the area the portal leads to
156 p->vis = new byte[portalVisBytes];
157 memset( p->vis, 0, portalVisBytes );
158 p->mightSee = new byte[portalVisBytes];
159 memset( p->mightSee, 0, portalVisBytes );
160 p->w->GetBounds( p->bounds );
161 p->w->GetPlane( p->plane );
162 // plane normal points to outside the area
163 p->plane = -p->plane;
164 // no PVS calculated for this portal yet
167 area->portals[area->numPortals] = p;
170 area->bounds += p->bounds;
177 idPVS::DestroyPVSData
180 void idPVS::DestroyPVSData( void ) {
187 // delete portal pointer array
188 delete[] pvsAreas[0].portals;
194 // delete portal data
195 for ( i = 0; i < numPortals; i++ ) {
196 delete[] pvsPortals[i].vis;
197 delete[] pvsPortals[i].mightSee;
198 delete pvsPortals[i].w;
208 idPVS::FloodFrontPortalPVS_r
211 void idPVS::FloodFrontPortalPVS_r( pvsPortal_t *portal, int areaNum ) const {
216 area = &pvsAreas[ areaNum ];
218 for ( i = 0; i < area->numPortals; i++ ) {
219 p = area->portals[i];
221 // don't flood through if this portal is not at the front
222 if ( !( portal->mightSee[ n>>3 ] & (1 << (n&7)) ) ) {
225 // don't flood through if already visited this portal
226 if ( portal->vis[ n>>3 ] & (1 << (n&7)) ) {
229 // this portal might be visible
230 portal->vis[ n>>3 ] |= (1 << (n&7));
231 // flood through the portal
232 FloodFrontPortalPVS_r( portal, p->areaNum );
238 idPVS::FrontPortalPVS
241 void idPVS::FrontPortalPVS( void ) const {
242 int i, j, k, n, p, side1, side2, areaSide;
243 pvsPortal_t *p1, *p2;
246 for ( i = 0; i < numPortals; i++ ) {
249 for ( j = 0; j < numAreas; j++ ) {
253 areaSide = side1 = area->bounds.PlaneSide( p1->plane );
255 // if the whole area is at the back side of the portal
256 if ( areaSide == PLANESIDE_BACK ) {
260 for ( p = 0; p < area->numPortals; p++ ) {
262 p2 = area->portals[p];
264 // if we the whole area is not at the front we need to check
265 if ( areaSide != PLANESIDE_FRONT ) {
266 // if the second portal is completely at the back side of the first portal
267 side1 = p2->bounds.PlaneSide( p1->plane );
268 if ( side1 == PLANESIDE_BACK ) {
273 // if the first portal is completely at the front of the second portal
274 side2 = p1->bounds.PlaneSide( p2->plane );
275 if ( side2 == PLANESIDE_FRONT ) {
279 // if the second portal is not completely at the front of the first portal
280 if ( side1 != PLANESIDE_FRONT ) {
281 // more accurate check
282 for ( k = 0; k < p2->w->GetNumPoints(); k++ ) {
283 // if more than an epsilon at the front side
284 if ( p1->plane.Side( (*p2->w)[k].ToVec3(), ON_EPSILON ) == PLANESIDE_FRONT ) {
288 if ( k >= p2->w->GetNumPoints() ) {
289 continue; // second portal is at the back of the first portal
293 // if the first portal is not completely at the back side of the second portal
294 if ( side2 != PLANESIDE_BACK ) {
295 // more accurate check
296 for ( k = 0; k < p1->w->GetNumPoints(); k++ ) {
297 // if more than an epsilon at the back side
298 if ( p2->plane.Side( (*p1->w)[k].ToVec3(), ON_EPSILON ) == PLANESIDE_BACK ) {
302 if ( k >= p1->w->GetNumPoints() ) {
303 continue; // first portal is at the front of the second portal
307 // the portal might be visible at the front
309 p1->mightSee[ n >> 3 ] |= 1 << (n&7);
314 // flood the front portal pvs for all portals
315 for ( i = 0; i < numPortals; i++ ) {
317 FloodFrontPortalPVS_r( p1, p1->areaNum );
323 idPVS::FloodPassagePVS_r
326 pvsStack_t *idPVS::FloodPassagePVS_r( pvsPortal_t *source, const pvsPortal_t *portal, pvsStack_t *prevStack ) const {
331 pvsPassage_t *passage;
332 long *sourceVis, *passageVis, *portalVis, *mightSee, *prevMightSee, more;
334 area = &pvsAreas[portal->areaNum];
336 stack = prevStack->next;
337 // if no next stack entry allocated
339 stack = reinterpret_cast<pvsStack_t*>(new byte[sizeof(pvsStack_t) + portalVisBytes]);
340 stack->mightSee = (reinterpret_cast<byte *>(stack)) + sizeof(pvsStack_t);
342 prevStack->next = stack;
345 // check all portals for flooding into other areas
346 for ( i = 0; i < area->numPortals; i++ ) {
348 passage = &portal->passages[i];
350 // if this passage is completely empty
351 if ( !passage->canSee ) {
355 p = area->portals[i];
358 // if this portal cannot be seen through our current portal/passage stack
359 if ( !( prevStack->mightSee[n >> 3] & (1 << (n & 7)) ) ) {
363 // mark the portal as visible
364 source->vis[n >> 3] |= (1 << (n & 7));
366 // get pointers to vis data
367 prevMightSee = reinterpret_cast<long *>(prevStack->mightSee);
368 passageVis = reinterpret_cast<long *>(passage->canSee);
369 sourceVis = reinterpret_cast<long *>(source->vis);
370 mightSee = reinterpret_cast<long *>(stack->mightSee);
373 // use the portal PVS if it has been calculated
375 portalVis = reinterpret_cast<long *>(p->vis);
376 for ( j = 0; j < portalVisLongs; j++ ) {
377 // get new PVS which is decreased by going through this passage
378 m = *prevMightSee++ & *passageVis++ & *portalVis++;
379 // check if anything might be visible through this passage that wasn't yet visible
380 more |= (m & ~(*sourceVis++));
386 // the p->mightSee is implicitely stored in the passageVis
387 for ( j = 0; j < portalVisLongs; j++ ) {
388 // get new PVS which is decreased by going through this passage
389 m = *prevMightSee++ & *passageVis++;
390 // check if anything might be visible through this passage that wasn't yet visible
391 more |= (m & ~(*sourceVis++));
397 // if nothing more can be seen
402 // go through the portal
403 stack->next = FloodPassagePVS_r( source, p, stack );
414 void idPVS::PassagePVS( void ) const {
417 pvsStack_t *stack, *s;
419 // create the passages
422 // allocate first stack entry
423 stack = reinterpret_cast<pvsStack_t*>(new byte[sizeof(pvsStack_t) + portalVisBytes]);
424 stack->mightSee = (reinterpret_cast<byte *>(stack)) + sizeof(pvsStack_t);
427 // calculate portal PVS by flooding through the passages
428 for ( i = 0; i < numPortals; i++ ) {
429 source = &pvsPortals[i];
430 memset( source->vis, 0, portalVisBytes );
431 memcpy( stack->mightSee, source->mightSee, portalVisBytes );
432 FloodPassagePVS_r( source, source, stack );
436 // free the allocated stack
437 for ( s = stack; s; s = stack ) {
442 // destroy the passages
448 idPVS::AddPassageBoundaries
451 void idPVS::AddPassageBoundaries( const idWinding &source, const idWinding &pass, bool flipClip, idPlane *bounds, int &numBounds, int maxBounds ) const {
453 idVec3 v1, v2, normal;
455 bool flipTest, front;
459 // check all combinations
460 for ( i = 0; i < source.GetNumPoints(); i++ ) {
462 l = (i + 1) % source.GetNumPoints();
463 v1 = source[l].ToVec3() - source[i].ToVec3();
465 // find a vertex of pass that makes a plane that puts all of the
466 // vertices of pass on the front side and all of the vertices of
467 // source on the back side
468 for ( j = 0; j < pass.GetNumPoints(); j++ ) {
470 v2 = pass[j].ToVec3() - source[i].ToVec3();
472 normal = v1.Cross( v2 );
473 if ( normal.Normalize() < 0.01f ) {
476 dist = normal * pass[j].ToVec3();
479 // find out which side of the generated seperating plane has the
483 for ( k = 0; k < source.GetNumPoints(); k++ ) {
484 if ( k == i || k == l ) {
487 d = source[k].ToVec3() * normal - dist;
488 if ( d < -ON_EPSILON ) {
489 // source is on the negative side, so we want all
490 // pass and target on the positive side
494 else if ( d > ON_EPSILON ) {
495 // source is on the positive side, so we want all
496 // pass and target on the negative side
501 if ( k == source.GetNumPoints() ) {
502 continue; // planar with source portal
505 // flip the normal if the source portal is backwards
511 // if all of the pass portal points are now on the positive side,
512 // this is the seperating plane
514 for ( k = 0; k < pass.GetNumPoints(); k++ ) {
518 d = pass[k].ToVec3() * normal - dist;
519 if ( d < -ON_EPSILON ) {
522 else if ( d > ON_EPSILON ) {
526 if ( k < pass.GetNumPoints() ) {
527 continue; // points on negative side, not a seperating plane
530 continue; // planar with seperating plane
533 // flip the normal if we want the back side
535 plane.SetNormal( -normal );
536 plane.SetDist( -dist );
539 plane.SetNormal( normal );
540 plane.SetDist( dist );
543 // check if the plane is already a passage boundary
544 for ( k = 0; k < numBounds; k++ ) {
545 if ( plane.Compare( bounds[k], 0.001f, 0.01f ) ) {
549 if ( k < numBounds ) {
553 if ( numBounds >= maxBounds ) {
554 gameLocal.Warning( "max passage boundaries." );
557 bounds[numBounds] = plane;
566 idPVS::CreatePassages
569 #define MAX_PASSAGE_BOUNDS 128
571 void idPVS::CreatePassages( void ) const {
572 int i, j, l, n, numBounds, front, passageMemory, byteNum, bitNum;
573 int sides[MAX_PASSAGE_BOUNDS];
574 idPlane passageBounds[MAX_PASSAGE_BOUNDS];
575 pvsPortal_t *source, *target, *p;
577 pvsPassage_t *passage;
578 idFixedWinding winding;
579 byte canSee, mightSee, bit;
582 for ( i = 0; i < numPortals; i++ ) {
583 source = &pvsPortals[i];
584 area = &pvsAreas[source->areaNum];
586 source->passages = new pvsPassage_t[area->numPortals];
588 for ( j = 0; j < area->numPortals; j++ ) {
589 target = area->portals[j];
590 n = target - pvsPortals;
592 passage = &source->passages[j];
594 // if the source portal cannot see this portal
595 if ( !( source->mightSee[ n>>3 ] & (1 << (n&7)) ) ) {
596 // not all portals in the area have to be visible because areas are not necesarily convex
597 // also no passage has to be created for the portal which is the opposite of the source
598 passage->canSee = NULL;
602 passage->canSee = new byte[portalVisBytes];
603 passageMemory += portalVisBytes;
605 // boundary plane normals point inwards
607 AddPassageBoundaries( *(source->w), *(target->w), false, passageBounds, numBounds, MAX_PASSAGE_BOUNDS );
608 AddPassageBoundaries( *(target->w), *(source->w), true, passageBounds, numBounds, MAX_PASSAGE_BOUNDS );
610 // get all portals visible through this passage
611 for ( byteNum = 0; byteNum < portalVisBytes; byteNum++) {
614 mightSee = source->mightSee[byteNum] & target->mightSee[byteNum];
616 // go through eight portals at a time to speed things up
617 for ( bitNum = 0; bitNum < 8; bitNum++ ) {
621 if ( !( mightSee & bit ) ) {
625 p = &pvsPortals[(byteNum << 3) + bitNum];
627 if ( p->areaNum == source->areaNum ) {
631 for ( front = 0, l = 0; l < numBounds; l++ ) {
632 sides[l] = p->bounds.PlaneSide( passageBounds[l] );
633 // if completely at the back of the passage bounding plane
634 if ( sides[l] == PLANESIDE_BACK ) {
637 // if completely at the front
638 if ( sides[l] == PLANESIDE_FRONT ) {
642 // if completely outside the passage
643 if ( l < numBounds ) {
647 // if not at the front of all bounding planes and thus not completely inside the passage
648 if ( front != numBounds ) {
652 for ( l = 0; l < numBounds; l++ ) {
653 // only clip if the winding possibly crosses this plane
654 if ( sides[l] != PLANESIDE_CROSS ) {
657 // clip away the part at the back of the bounding plane
658 winding.ClipInPlace( passageBounds[l] );
659 // if completely clipped away
660 if ( !winding.GetNumPoints() ) {
664 // if completely outside the passage
665 if ( l < numBounds ) {
673 // store results of all eight portals
674 passage->canSee[byteNum] = canSee;
677 // can always see the target portal
678 passage->canSee[n >> 3] |= (1 << (n&7));
681 if ( passageMemory < 1024 ) {
682 gameLocal.Printf( "%5d bytes passage memory used to build PVS\n", passageMemory );
685 gameLocal.Printf( "%5d KB passage memory used to build PVS\n", passageMemory>>10 );
691 idPVS::DestroyPassages
694 void idPVS::DestroyPassages( void ) const {
699 for ( i = 0; i < numPortals; i++ ) {
701 area = &pvsAreas[p->areaNum];
702 for ( j = 0; j < area->numPortals; j++ ) {
703 if ( p->passages[j].canSee ) {
704 delete[] p->passages[j].canSee;
707 delete[] p->passages;
713 idPVS::CopyPortalPVSToMightSee
716 void idPVS::CopyPortalPVSToMightSee( void ) const {
720 for ( i = 0; i < numPortals; i++ ) {
722 memcpy( p->mightSee, p->vis, portalVisBytes );
728 idPVS::AreaPVSFromPortalPVS
731 int idPVS::AreaPVSFromPortalPVS( void ) const {
732 int i, j, k, areaNum, totalVisibleAreas;
734 byte *pvs, *portalPVS;
737 totalVisibleAreas = 0;
740 return totalVisibleAreas;
743 memset( areaPVS, 0, numAreas * areaVisBytes );
745 for ( i = 0; i < numAreas; i++ ) {
747 pvs = areaPVS + i * areaVisBytes;
749 // the area is visible to itself
750 pvs[ i >> 3 ] |= 1 << (i & 7);
752 if ( !area->numPortals ) {
756 // store the PVS of all portals in this area at the first portal
757 for ( j = 1; j < area->numPortals; j++ ) {
758 p1 = reinterpret_cast<long *>(area->portals[0]->vis);
759 p2 = reinterpret_cast<long *>(area->portals[j]->vis);
760 for ( k = 0; k < portalVisLongs; k++ ) {
765 // the portals of this area are always visible
766 for ( j = 0; j < area->numPortals; j++ ) {
767 k = area->portals[j] - pvsPortals;
768 area->portals[0]->vis[ k >> 3 ] |= 1 << (k & 7);
771 // set all areas to visible that can be seen from the portals of this area
772 portalPVS = area->portals[0]->vis;
773 for ( j = 0; j < numPortals; j++ ) {
774 // if this portal is visible
775 if ( portalPVS[j>>3] & (1 << (j&7)) ) {
776 areaNum = pvsPortals[j].areaNum;
777 pvs[ areaNum >> 3 ] |= 1 << (areaNum & 7);
781 // count the number of visible areas
782 for ( j = 0; j < numAreas; j++ ) {
783 if ( pvs[j>>3] & (1 << (j&7)) ) {
788 return totalVisibleAreas;
796 void idPVS::Init( void ) {
797 int totalVisibleAreas;
801 numAreas = gameRenderWorld->NumAreas();
802 if ( numAreas <= 0 ) {
806 connectedAreas = new bool[numAreas];
807 areaQueue = new int[numAreas];
809 areaVisBytes = ( ((numAreas+31)&~31) >> 3);
810 areaVisLongs = areaVisBytes/sizeof(long);
812 areaPVS = new byte[numAreas * areaVisBytes];
813 memset( areaPVS, 0xFF, numAreas * areaVisBytes );
815 numPortals = GetPortalCount();
817 portalVisBytes = ( ((numPortals+31)&~31) >> 3);
818 portalVisLongs = portalVisBytes/sizeof(long);
820 for ( int i = 0; i < MAX_CURRENT_PVS; i++ ) {
821 currentPVS[i].handle.i = -1;
822 currentPVS[i].handle.h = 0;
823 currentPVS[i].pvs = new byte[areaVisBytes];
824 memset( currentPVS[i].pvs, 0, areaVisBytes );
834 CopyPortalPVSToMightSee();
838 totalVisibleAreas = AreaPVSFromPortalPVS();
844 gameLocal.Printf( "%5.0f msec to calculate PVS\n", timer.Milliseconds() );
845 gameLocal.Printf( "%5d areas\n", numAreas );
846 gameLocal.Printf( "%5d portals\n", numPortals );
847 gameLocal.Printf( "%5d areas visible on average\n", totalVisibleAreas / numAreas );
848 if ( numAreas * areaVisBytes < 1024 ) {
849 gameLocal.Printf( "%5d bytes PVS data\n", numAreas * areaVisBytes );
852 gameLocal.Printf( "%5d KB PVS data\n", (numAreas * areaVisBytes) >> 10 );
861 void idPVS::Shutdown( void ) {
862 if ( connectedAreas ) {
863 delete connectedAreas;
864 connectedAreas = NULL;
875 for ( int i = 0; i < MAX_CURRENT_PVS; i++ ) {
876 delete currentPVS[i].pvs;
877 currentPVS[i].pvs = NULL;
884 idPVS::GetConnectedAreas
886 assumes the 'areas' array is initialized to false
889 void idPVS::GetConnectedAreas( int srcArea, bool *areas ) const {
890 int curArea, nextArea;
891 int queueStart, queueEnd;
897 areas[srcArea] = true;
899 for ( curArea = srcArea; queueStart < queueEnd; curArea = areaQueue[++queueStart] ) {
901 n = gameRenderWorld->NumPortalsInArea( curArea );
903 for ( i = 0; i < n; i++ ) {
904 portal = gameRenderWorld->GetPortal( curArea, i );
906 if ( portal.blockingBits & PS_BLOCK_VIEW ) {
910 // area[1] is always the area the portal leads to
911 nextArea = portal.areas[1];
913 // if already visited this area
914 if ( areas[nextArea] ) {
919 areaQueue[queueEnd++] = nextArea;
920 areas[nextArea] = true;
930 int idPVS::GetPVSArea( const idVec3 &point ) const {
931 return gameRenderWorld->PointInArea( point );
939 int idPVS::GetPVSAreas( const idBounds &bounds, int *areas, int maxAreas ) const {
940 return gameRenderWorld->BoundsInAreas( bounds, areas, maxAreas );
945 idPVS::SetupCurrentPVS
948 pvsHandle_t idPVS::SetupCurrentPVS( const idVec3 &source, const pvsType_t type ) const {
951 sourceArea = gameRenderWorld->PointInArea( source );
953 return SetupCurrentPVS( sourceArea, type );
958 idPVS::SetupCurrentPVS
961 pvsHandle_t idPVS::SetupCurrentPVS( const idBounds &source, const pvsType_t type ) const {
962 int numSourceAreas, sourceAreas[MAX_BOUNDS_AREAS];
964 numSourceAreas = gameRenderWorld->BoundsInAreas( source, sourceAreas, MAX_BOUNDS_AREAS );
966 return SetupCurrentPVS( sourceAreas, numSourceAreas, type );
971 idPVS::SetupCurrentPVS
974 pvsHandle_t idPVS::SetupCurrentPVS( const int sourceArea, const pvsType_t type ) const {
978 handle = AllocCurrentPVS( *reinterpret_cast<const unsigned int *>(&sourceArea) );
980 if ( sourceArea < 0 || sourceArea >= numAreas ) {
981 memset( currentPVS[handle.i].pvs, 0, areaVisBytes );
985 if ( type != PVS_CONNECTED_AREAS ) {
986 memcpy( currentPVS[handle.i].pvs, areaPVS + sourceArea * areaVisBytes, areaVisBytes );
988 memset( currentPVS[handle.i].pvs, -1, areaVisBytes );
991 if ( type == PVS_ALL_PORTALS_OPEN ) {
995 memset( connectedAreas, 0, numAreas * sizeof( *connectedAreas ) );
997 GetConnectedAreas( sourceArea, connectedAreas );
999 for ( i = 0; i < numAreas; i++ ) {
1000 if ( !connectedAreas[i] ) {
1001 currentPVS[handle.i].pvs[i>>3] &= ~(1 << (i&7));
1010 idPVS::SetupCurrentPVS
1013 pvsHandle_t idPVS::SetupCurrentPVS( const int *sourceAreas, const int numSourceAreas, const pvsType_t type ) const {
1020 for ( i = 0; i < numSourceAreas; i++ ) {
1021 h ^= *reinterpret_cast<const unsigned int *>(&sourceAreas[i]);
1023 handle = AllocCurrentPVS( h );
1025 if ( !numSourceAreas || sourceAreas[0] < 0 || sourceAreas[0] >= numAreas) {
1026 memset( currentPVS[handle.i].pvs, 0, areaVisBytes );
1030 if ( type != PVS_CONNECTED_AREAS ) {
1031 // merge PVS of all areas the source is in
1032 memcpy( currentPVS[handle.i].pvs, areaPVS + sourceAreas[0] * areaVisBytes, areaVisBytes );
1033 for ( i = 1; i < numSourceAreas; i++ ) {
1035 assert( sourceAreas[i] >= 0 && sourceAreas[i] < numAreas );
1037 vis = reinterpret_cast<long*>(areaPVS + sourceAreas[i] * areaVisBytes);
1038 pvs = reinterpret_cast<long*>(currentPVS[handle.i].pvs);
1039 for ( j = 0; j < areaVisLongs; j++ ) {
1044 memset( currentPVS[handle.i].pvs, -1, areaVisBytes );
1047 if ( type == PVS_ALL_PORTALS_OPEN ) {
1051 memset( connectedAreas, 0, numAreas * sizeof( *connectedAreas ) );
1053 // get all areas connected to any of the source areas
1054 for ( i = 0; i < numSourceAreas; i++ ) {
1055 if ( !connectedAreas[sourceAreas[i]] ) {
1056 GetConnectedAreas( sourceAreas[i], connectedAreas );
1060 // remove unconnected areas from the PVS
1061 for ( i = 0; i < numAreas; i++ ) {
1062 if ( !connectedAreas[i] ) {
1063 currentPVS[handle.i].pvs[i>>3] &= ~(1 << (i&7));
1072 idPVS::MergeCurrentPVS
1075 pvsHandle_t idPVS::MergeCurrentPVS( pvsHandle_t pvs1, pvsHandle_t pvs2 ) const {
1077 long *pvs1Ptr, *pvs2Ptr, *ptr;
1080 if ( pvs1.i < 0 || pvs1.i >= MAX_CURRENT_PVS || pvs1.h != currentPVS[pvs1.i].handle.h ||
1081 pvs2.i < 0 || pvs2.i >= MAX_CURRENT_PVS || pvs2.h != currentPVS[pvs2.i].handle.h ) {
1082 gameLocal.Error( "idPVS::MergeCurrentPVS: invalid handle" );
1085 handle = AllocCurrentPVS( pvs1.h ^ pvs2.h );
1087 ptr = reinterpret_cast<long*>(currentPVS[handle.i].pvs);
1088 pvs1Ptr = reinterpret_cast<long*>(currentPVS[pvs1.i].pvs);
1089 pvs2Ptr = reinterpret_cast<long*>(currentPVS[pvs2.i].pvs);
1091 for ( i = 0; i < areaVisLongs; i++ ) {
1092 *ptr++ = *pvs1Ptr++ | *pvs2Ptr++;
1100 idPVS::AllocCurrentPVS
1103 pvsHandle_t idPVS::AllocCurrentPVS( unsigned int h ) const {
1107 for ( i = 0; i < MAX_CURRENT_PVS; i++ ) {
1108 if ( currentPVS[i].handle.i == -1 ) {
1109 currentPVS[i].handle.i = i;
1110 currentPVS[i].handle.h = h;
1111 return currentPVS[i].handle;
1115 gameLocal.Error( "idPVS::AllocCurrentPVS: no free PVS left" );
1124 idPVS::FreeCurrentPVS
1127 void idPVS::FreeCurrentPVS( pvsHandle_t handle ) const {
1128 if ( handle.i < 0 || handle.i >= MAX_CURRENT_PVS || handle.h != currentPVS[handle.i].handle.h ) {
1129 gameLocal.Error( "idPVS::FreeCurrentPVS: invalid handle" );
1131 currentPVS[handle.i].handle.i = -1;
1139 bool idPVS::InCurrentPVS( const pvsHandle_t handle, const idVec3 &target ) const {
1142 if ( handle.i < 0 || handle.i >= MAX_CURRENT_PVS ||
1143 handle.h != currentPVS[handle.i].handle.h ) {
1144 gameLocal.Error( "idPVS::InCurrentPVS: invalid handle" );
1147 targetArea = gameRenderWorld->PointInArea( target );
1149 if ( targetArea == -1 ) {
1153 return ( ( currentPVS[handle.i].pvs[targetArea>>3] & (1 << (targetArea&7)) ) != 0 );
1161 bool idPVS::InCurrentPVS( const pvsHandle_t handle, const idBounds &target ) const {
1162 int i, numTargetAreas, targetAreas[MAX_BOUNDS_AREAS];
1164 if ( handle.i < 0 || handle.i >= MAX_CURRENT_PVS ||
1165 handle.h != currentPVS[handle.i].handle.h ) {
1166 gameLocal.Error( "idPVS::InCurrentPVS: invalid handle" );
1169 numTargetAreas = gameRenderWorld->BoundsInAreas( target, targetAreas, MAX_BOUNDS_AREAS );
1171 for ( i = 0; i < numTargetAreas; i++ ) {
1172 if ( currentPVS[handle.i].pvs[targetAreas[i]>>3] & (1 << (targetAreas[i]&7)) ) {
1184 bool idPVS::InCurrentPVS( const pvsHandle_t handle, const int targetArea ) const {
1186 if ( handle.i < 0 || handle.i >= MAX_CURRENT_PVS ||
1187 handle.h != currentPVS[handle.i].handle.h ) {
1188 gameLocal.Error( "idPVS::InCurrentPVS: invalid handle" );
1191 if ( targetArea < 0 || targetArea >= numAreas ) {
1195 return ( ( currentPVS[handle.i].pvs[targetArea>>3] & (1 << (targetArea&7)) ) != 0 );
1203 bool idPVS::InCurrentPVS( const pvsHandle_t handle, const int *targetAreas, int numTargetAreas ) const {
1206 if ( handle.i < 0 || handle.i >= MAX_CURRENT_PVS ||
1207 handle.h != currentPVS[handle.i].handle.h ) {
1208 gameLocal.Error( "idPVS::InCurrentPVS: invalid handle" );
1211 for ( i = 0; i < numTargetAreas; i++ ) {
1212 if ( targetAreas[i] < 0 || targetAreas[i] >= numAreas ) {
1215 if ( currentPVS[handle.i].pvs[targetAreas[i]>>3] & (1 << (targetAreas[i]&7)) ) {
1227 void idPVS::DrawPVS( const idVec3 &source, const pvsType_t type ) const {
1228 int i, j, k, numPoints, n, sourceArea;
1229 exitPortal_t portal;
1235 sourceArea = gameRenderWorld->PointInArea( source );
1237 if ( sourceArea == -1 ) {
1241 handle = SetupCurrentPVS( source, type );
1243 for ( j = 0; j < numAreas; j++ ) {
1245 if ( !( currentPVS[handle.i].pvs[j>>3] & (1 << (j&7)) ) ) {
1249 if ( j == sourceArea ) {
1256 n = gameRenderWorld->NumPortalsInArea( j );
1258 // draw all the portals of the area
1259 for ( i = 0; i < n; i++ ) {
1260 portal = gameRenderWorld->GetPortal( j, i );
1262 numPoints = portal.w->GetNumPoints();
1264 portal.w->GetPlane( plane );
1265 offset = plane.Normal() * 4.0f;
1266 for ( k = 0; k < numPoints; k++ ) {
1267 gameRenderWorld->DebugLine( *color, (*portal.w)[k].ToVec3() + offset, (*portal.w)[(k+1)%numPoints].ToVec3() + offset );
1272 FreeCurrentPVS( handle );
1280 void idPVS::DrawPVS( const idBounds &source, const pvsType_t type ) const {
1281 int i, j, k, numPoints, n, num, areas[MAX_BOUNDS_AREAS];
1282 exitPortal_t portal;
1288 num = gameRenderWorld->BoundsInAreas( source, areas, MAX_BOUNDS_AREAS );
1294 handle = SetupCurrentPVS( source, type );
1296 for ( j = 0; j < numAreas; j++ ) {
1298 if ( !( currentPVS[handle.i].pvs[j>>3] & (1 << (j&7)) ) ) {
1302 for ( i = 0; i < num; i++ ) {
1303 if ( j == areas[i] ) {
1314 n = gameRenderWorld->NumPortalsInArea( j );
1316 // draw all the portals of the area
1317 for ( i = 0; i < n; i++ ) {
1318 portal = gameRenderWorld->GetPortal( j, i );
1320 numPoints = portal.w->GetNumPoints();
1322 portal.w->GetPlane( plane );
1323 offset = plane.Normal() * 4.0f;
1324 for ( k = 0; k < numPoints; k++ ) {
1325 gameRenderWorld->DebugLine( *color, (*portal.w)[k].ToVec3() + offset, (*portal.w)[(k+1)%numPoints].ToVec3() + offset );
1330 FreeCurrentPVS( handle );
1338 void idPVS::DrawCurrentPVS( const pvsHandle_t handle, const idVec3 &source ) const {
1339 int i, j, k, numPoints, n, sourceArea;
1340 exitPortal_t portal;
1345 if ( handle.i < 0 || handle.i >= MAX_CURRENT_PVS ||
1346 handle.h != currentPVS[handle.i].handle.h ) {
1347 gameLocal.Error( "idPVS::DrawCurrentPVS: invalid handle" );
1350 sourceArea = gameRenderWorld->PointInArea( source );
1352 if ( sourceArea == -1 ) {
1356 for ( j = 0; j < numAreas; j++ ) {
1358 if ( !( currentPVS[handle.i].pvs[j>>3] & (1 << (j&7)) ) ) {
1362 if ( j == sourceArea ) {
1369 n = gameRenderWorld->NumPortalsInArea( j );
1371 // draw all the portals of the area
1372 for ( i = 0; i < n; i++ ) {
1373 portal = gameRenderWorld->GetPortal( j, i );
1375 numPoints = portal.w->GetNumPoints();
1377 portal.w->GetPlane( plane );
1378 offset = plane.Normal() * 4.0f;
1379 for ( k = 0; k < numPoints; k++ ) {
1380 gameRenderWorld->DebugLine( *color, (*portal.w)[k].ToVec3() + offset, (*portal.w)[(k+1)%numPoints].ToVec3() + offset );
1393 void idPVS::WritePVS( const pvsHandle_t handle, idBitMsg &msg ) {
1394 msg.WriteData( currentPVS[ handle.i ].pvs, areaVisBytes );
1402 void idPVS::ReadPVS( const pvsHandle_t handle, const idBitMsg &msg ) {
1406 assert( areaVisBytes <= 256 );
1407 msg.ReadData( l_pvs, areaVisBytes );
1408 if ( memcmp( l_pvs, currentPVS[ handle.i ].pvs, areaVisBytes ) ) {
1409 common->Printf( "PVS not matching ( %d areaVisBytes ) - server then client:\n", areaVisBytes );
1410 for ( i = 0; i < areaVisBytes; i++ ) {
1411 common->Printf( "%x ", l_pvs[ i ] );
1413 common->Printf( "\n" );
1414 for ( i = 0; i < areaVisBytes; i++ ) {
1415 common->Printf( "%x ", currentPVS[ handle.i ].pvs[ i ] );
1417 common->Printf( "\n" );
1427 idPVS::CheckAreasForPortalSky
1430 bool idPVS::CheckAreasForPortalSky( const pvsHandle_t handle, const idVec3 &origin ) {
1433 if ( handle.i < 0 || handle.i >= MAX_CURRENT_PVS || handle.h != currentPVS[handle.i].handle.h ) {
1437 sourceArea = gameRenderWorld->PointInArea( origin );
1439 if ( sourceArea == -1 ) {
1443 for ( j = 0; j < numAreas; j++ ) {
1445 if ( !( currentPVS[handle.i].pvs[j>>3] & (1 << (j&7)) ) ) {
1449 if ( gameRenderWorld->CheckAreaForPortalSky( j ) ) {