neo/d3xp/Pvs.cpp

   1 /*
   2 ===========================================================================
   3
   4 Doom 3 GPL Source Code
   5 Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company.
   6
   7 This file is part of the Doom 3 GPL Source Code (?Doom 3 Source Code?).
   8
   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.
  13
  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.
  18
  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/>.
  21
  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.
  23
  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.
  25
  26 ===========================================================================
  27 */
  28
  29 #include "../idlib/precompiled.h"
  30 #pragma hdrstop
  31
  32 #include "Game_local.h"
  33
  34 #define MAX_BOUNDS_AREAS        16
  35
  36
  37 typedef struct pvsPassage_s {
  38         byte *                          canSee;         // bit set for all portals that can be seen through this passage
  39 } pvsPassage_t;
  40
  41
  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
  51 } pvsPortal_t;
  52
  53
  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
  58 } pvsArea_t;
  59
  60
  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
  64 } pvsStack_t;
  65
  66
  67 /*
  68 ================
  69 idPVS::idPVS
  70 ================
  71 */
  72 idPVS::idPVS( void ) {
  73         int i;
  74
  75         numAreas = 0;
  76         numPortals = 0;
  77
  78         connectedAreas = NULL;
  79         areaQueue = NULL;
  80         areaPVS = NULL;
  81
  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;
  86         }
  87
  88         pvsAreas = NULL;
  89         pvsPortals = NULL;
  90 }
  91
  92 /*
  93 ================
  94 idPVS::~idPVS
  95 ================
  96 */
  97 idPVS::~idPVS( void ) {
  98         Shutdown();
  99 }
 100
 101 /*
 102 ================
 103 idPVS::GetPortalCount
 104 ================
 105 */
 106 int idPVS::GetPortalCount( void ) const {
 107         int i, na, np;
 108
 109         na = gameRenderWorld->NumAreas();
 110         np = 0;
 111         for ( i = 0; i < na; i++ ) {
 112                 np += gameRenderWorld->NumPortalsInArea( i );
 113         }
 114         return np;
 115 }
 116
 117 /*
 118 ================
 119 idPVS::CreatePVSData
 120 ================
 121 */
 122 void idPVS::CreatePVSData( void ) {
 123         int i, j, n, cp;
 124         exitPortal_t portal;
 125         pvsArea_t *area;
 126         pvsPortal_t *p, **portalPtrs;
 127
 128         if ( !numPortals ) {
 129                 return;
 130         }
 131
 132         pvsPortals = new pvsPortal_t[numPortals];
 133         pvsAreas = new pvsArea_t[numAreas];
 134         memset( pvsAreas, 0, numAreas * sizeof( *pvsAreas ) );
 135
 136         cp = 0;
 137         portalPtrs = new pvsPortal_t*[numPortals];
 138
 139         for ( i = 0; i < numAreas; i++ ) {
 140
 141                 area = &pvsAreas[i];
 142                 area->bounds.Clear();
 143                 area->portals = portalPtrs + cp;
 144
 145                 n = gameRenderWorld->NumPortalsInArea( i );
 146
 147                 for ( j = 0; j < n; j++ ) {
 148
 149                         portal = gameRenderWorld->GetPortal( i, j );
 150
 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
 155
 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
 165                         p->done = false;
 166
 167                         area->portals[area->numPortals] = p;
 168                         area->numPortals++;
 169
 170                         area->bounds += p->bounds;
 171                 }
 172         }
 173 }
 174
 175 /*
 176 ================
 177 idPVS::DestroyPVSData
 178 ================
 179 */
 180 void idPVS::DestroyPVSData( void ) {
 181         int i;
 182
 183         if ( !pvsAreas ) {
 184                 return;
 185         }
 186
 187         // delete portal pointer array
 188         delete[] pvsAreas[0].portals;
 189
 190         // delete all areas
 191         delete[] pvsAreas;
 192         pvsAreas = NULL;
 193
 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;
 199         }
 200
 201         // delete portals
 202         delete[] pvsPortals;
 203         pvsPortals = NULL;
 204 }
 205
 206 /*
 207 ================
 208 idPVS::FloodFrontPortalPVS_r
 209 ================
 210 */
 211 void idPVS::FloodFrontPortalPVS_r( pvsPortal_t *portal, int areaNum ) const {
 212         int i, n;
 213         pvsArea_t *area;
 214         pvsPortal_t *p;
 215
 216         area = &pvsAreas[ areaNum ];
 217
 218         for ( i = 0; i < area->numPortals; i++ ) {
 219                 p = area->portals[i];
 220                 n = p - pvsPortals;
 221                 // don't flood through if this portal is not at the front
 222                 if ( !( portal->mightSee[ n>>3 ] & (1 << (n&7)) ) ) {
 223                         continue;
 224                 }
 225                 // don't flood through if already visited this portal
 226                 if ( portal->vis[ n>>3 ] & (1 << (n&7)) ) {
 227                         continue;
 228                 }
 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 );
 233         }
 234 }
 235
 236 /*
 237 ================
 238 idPVS::FrontPortalPVS
 239 ================
 240 */
 241 void idPVS::FrontPortalPVS( void ) const {
 242         int i, j, k, n, p, side1, side2, areaSide;
 243         pvsPortal_t *p1, *p2;
 244         pvsArea_t *area;
 245
 246         for ( i = 0; i < numPortals; i++ ) {
 247                 p1 = &pvsPortals[i];
 248
 249                 for ( j = 0; j < numAreas; j++ ) {
 250
 251                         area = &pvsAreas[j];
 252
 253                         areaSide = side1 = area->bounds.PlaneSide( p1->plane );
 254
 255                         // if the whole area is at the back side of the portal
 256                         if ( areaSide == PLANESIDE_BACK ) {
 257                                 continue;
 258                         }
 259
 260                         for ( p = 0; p < area->numPortals; p++ ) {
 261
 262                                 p2 = area->portals[p];
 263
 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 ) {
 269                                                 continue;
 270                                         }
 271                                 }
 272
 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 ) {
 276                                         continue;
 277                                 }
 278
 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 ) {
 285                                                         break;
 286                                                 }
 287                                         }
 288                                         if ( k >= p2->w->GetNumPoints() ) {
 289                                                 continue;       // second portal is at the back of the first portal
 290                                         }
 291                                 }
 292
 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 ) {
 299                                                         break;
 300                                                 }
 301                                         }
 302                                         if ( k >= p1->w->GetNumPoints() ) {
 303                                                 continue;       // first portal is at the front of the second portal
 304                                         }
 305                                 }
 306
 307                                 // the portal might be visible at the front
 308                                 n = p2 - pvsPortals;
 309                                 p1->mightSee[ n >> 3 ] |= 1 << (n&7);
 310                         }
 311                 }
 312         }
 313
 314         // flood the front portal pvs for all portals
 315         for ( i = 0; i < numPortals; i++ ) {
 316                 p1 = &pvsPortals[i];
 317                 FloodFrontPortalPVS_r( p1, p1->areaNum );
 318         }
 319 }
 320
 321 /*
 322 ===============
 323 idPVS::FloodPassagePVS_r
 324 ===============
 325 */
 326 pvsStack_t *idPVS::FloodPassagePVS_r( pvsPortal_t *source, const pvsPortal_t *portal, pvsStack_t *prevStack ) const {
 327         int i, j, n, m;
 328         pvsPortal_t *p;
 329         pvsArea_t *area;
 330         pvsStack_t *stack;
 331         pvsPassage_t *passage;
 332         long *sourceVis, *passageVis, *portalVis, *mightSee, *prevMightSee, more;
 333
 334         area = &pvsAreas[portal->areaNum];
 335
 336         stack = prevStack->next;
 337         // if no next stack entry allocated
 338         if ( !stack ) {
 339                 stack = reinterpret_cast<pvsStack_t*>(new byte[sizeof(pvsStack_t) + portalVisBytes]);
 340                 stack->mightSee = (reinterpret_cast<byte *>(stack)) + sizeof(pvsStack_t);
 341                 stack->next = NULL;
 342                 prevStack->next = stack;
 343         }
 344
 345         // check all portals for flooding into other areas
 346         for ( i = 0; i < area->numPortals; i++ ) {
 347
 348                 passage = &portal->passages[i];
 349
 350                 // if this passage is completely empty
 351                 if ( !passage->canSee ) {
 352                         continue;
 353                 }
 354
 355                 p = area->portals[i];
 356                 n = p - pvsPortals;
 357
 358                 // if this portal cannot be seen through our current portal/passage stack
 359                 if ( !( prevStack->mightSee[n >> 3] & (1 << (n & 7)) ) ) {
 360                         continue;
 361                 }
 362
 363                 // mark the portal as visible
 364                 source->vis[n >> 3] |= (1 << (n & 7));
 365
 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);
 371
 372                 more = 0;
 373                 // use the portal PVS if it has been calculated
 374                 if ( p->done ) {
 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++));
 381                                 // store new PVS
 382                                 *mightSee++ = m;
 383                         }
 384                 }
 385                 else {
 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++));
 392                                 // store new PVS
 393                                 *mightSee++ = m;
 394                         }
 395                 }
 396
 397                 // if nothing more can be seen
 398                 if ( !more ) {
 399                         continue;
 400                 }
 401
 402                 // go through the portal
 403                 stack->next = FloodPassagePVS_r( source, p, stack );
 404         }
 405
 406         return stack;
 407 }
 408
 409 /*
 410 ===============
 411 idPVS::PassagePVS
 412 ===============
 413 */
 414 void idPVS::PassagePVS( void ) const {
 415         int i;
 416         pvsPortal_t *source;
 417         pvsStack_t *stack, *s;
 418
 419         // create the passages
 420         CreatePassages();
 421
 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);
 425         stack->next = NULL;
 426
 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 );
 433                 source->done = true;
 434         }
 435
 436         // free the allocated stack
 437         for ( s = stack; s; s = stack ) {
 438                 stack = stack->next;
 439                 delete[] s;
 440         }
 441
 442         // destroy the passages
 443         DestroyPassages();
 444 }
 445
 446 /*
 447 ===============
 448 idPVS::AddPassageBoundaries
 449 ===============
 450 */
 451 void idPVS::AddPassageBoundaries( const idWinding &source, const idWinding &pass, bool flipClip, idPlane *bounds, int &numBounds, int maxBounds ) const {
 452         int                     i, j, k, l;
 453         idVec3          v1, v2, normal;
 454         float           d, dist;
 455         bool            flipTest, front;
 456         idPlane         plane;
 457
 458
 459         // check all combinations
 460         for ( i = 0; i < source.GetNumPoints(); i++ ) {
 461
 462                 l = (i + 1) % source.GetNumPoints();
 463                 v1 = source[l].ToVec3() - source[i].ToVec3();
 464
 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++ ) {
 469
 470                         v2 = pass[j].ToVec3() - source[i].ToVec3();
 471
 472                         normal = v1.Cross( v2 );
 473                         if ( normal.Normalize() < 0.01f ) {
 474                                 continue;
 475                         }
 476                         dist = normal * pass[j].ToVec3();
 477
 478                         //
 479                         // find out which side of the generated seperating plane has the
 480                         // source portal
 481                         //
 482                         flipTest = false;
 483                         for ( k = 0; k < source.GetNumPoints(); k++ ) {
 484                                 if ( k == i || k == l ) {
 485                                         continue;
 486                                 }
 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
 491                                         flipTest = false;
 492                                         break;
 493                                 }
 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
 497                                         flipTest = true;
 498                                         break;
 499                                 }
 500                         }
 501                         if ( k == source.GetNumPoints() ) {
 502                                 continue;               // planar with source portal
 503                         }
 504
 505                         // flip the normal if the source portal is backwards
 506                         if (flipTest) {
 507                                 normal = -normal;
 508                                 dist = -dist;
 509                         }
 510
 511                         // if all of the pass portal points are now on the positive side,
 512                         // this is the seperating plane
 513                         front = false;
 514                         for ( k = 0; k < pass.GetNumPoints(); k++ ) {
 515                                 if ( k == j ) {
 516                                         continue;
 517                                 }
 518                                 d = pass[k].ToVec3() * normal - dist;
 519                                 if ( d < -ON_EPSILON ) {
 520                                         break;
 521                                 }
 522                                 else if ( d > ON_EPSILON ) {
 523                                         front = true;
 524                                 }
 525                         }
 526                         if ( k < pass.GetNumPoints() ) {
 527                                 continue;       // points on negative side, not a seperating plane
 528                         }
 529                         if ( !front ) {
 530                                 continue;       // planar with seperating plane
 531                         }
 532
 533                         // flip the normal if we want the back side
 534                         if ( flipClip ) {
 535                                 plane.SetNormal( -normal );
 536                                 plane.SetDist( -dist );
 537                         }
 538                         else {
 539                                 plane.SetNormal( normal );
 540                                 plane.SetDist( dist );
 541                         }
 542
 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 ) ) {
 546                                         break;
 547                                 }
 548                         }
 549                         if ( k < numBounds ) {
 550                                 break;
 551                         }
 552
 553                         if ( numBounds >= maxBounds ) {
 554                                 gameLocal.Warning( "max passage boundaries." );
 555                                 break;
 556                         }
 557                         bounds[numBounds] = plane;
 558                         numBounds++;
 559                         break;
 560                 }
 561         }
 562 }
 563
 564 /*
 565 ================
 566 idPVS::CreatePassages
 567 ================
 568 */
 569 #define MAX_PASSAGE_BOUNDS              128
 570
 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;
 576         pvsArea_t *area;
 577         pvsPassage_t *passage;
 578         idFixedWinding winding;
 579         byte canSee, mightSee, bit;
 580
 581         passageMemory = 0;
 582         for ( i = 0; i < numPortals; i++ ) {
 583                 source = &pvsPortals[i];
 584                 area = &pvsAreas[source->areaNum];
 585
 586                 source->passages = new pvsPassage_t[area->numPortals];
 587
 588                 for ( j = 0; j < area->numPortals; j++ ) {
 589                         target = area->portals[j];
 590                         n = target - pvsPortals;
 591
 592                         passage = &source->passages[j];
 593
 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;
 599                                 continue;
 600                         }
 601
 602                         passage->canSee = new byte[portalVisBytes];
 603                         passageMemory += portalVisBytes;
 604
 605                         // boundary plane normals point inwards
 606                         numBounds = 0;
 607                         AddPassageBoundaries( *(source->w), *(target->w), false, passageBounds, numBounds, MAX_PASSAGE_BOUNDS );
 608                         AddPassageBoundaries( *(target->w), *(source->w), true, passageBounds, numBounds, MAX_PASSAGE_BOUNDS );
 609
 610                         // get all portals visible through this passage
 611                         for ( byteNum = 0; byteNum < portalVisBytes; byteNum++) {
 612
 613                                 canSee = 0;
 614                                 mightSee = source->mightSee[byteNum] & target->mightSee[byteNum];
 615
 616                                 // go through eight portals at a time to speed things up
 617                                 for ( bitNum = 0; bitNum < 8; bitNum++ ) {
 618
 619                                         bit = 1 << bitNum;
 620
 621                                         if ( !( mightSee & bit ) ) {
 622                                                 continue;
 623                                         }
 624
 625                                         p = &pvsPortals[(byteNum << 3) + bitNum];
 626
 627                                         if ( p->areaNum == source->areaNum ) {
 628                                                 continue;
 629                                         }
 630
 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 ) {
 635                                                         break;
 636                                                 }
 637                                                 // if completely at the front
 638                                                 if ( sides[l] == PLANESIDE_FRONT ) {
 639                                                         front++;
 640                                                 }
 641                                         }
 642                                         // if completely outside the passage
 643                                         if ( l < numBounds ) {
 644                                                 continue;
 645                                         }
 646
 647                                         // if not at the front of all bounding planes and thus not completely inside the passage
 648                                         if ( front != numBounds ) {
 649
 650                                                 winding = *p->w;
 651
 652                                                 for ( l = 0; l < numBounds; l++ ) {
 653                                                         // only clip if the winding possibly crosses this plane
 654                                                         if ( sides[l] != PLANESIDE_CROSS ) {
 655                                                                 continue;
 656                                                         }
 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() ) {
 661                                                                 break;
 662                                                         }
 663                                                 }
 664                                                 // if completely outside the passage
 665                                                 if ( l < numBounds ) {
 666                                                         continue;
 667                                                 }
 668                                         }
 669
 670                                         canSee |= bit;
 671                                 }
 672
 673                                 // store results of all eight portals
 674                                 passage->canSee[byteNum] = canSee;
 675                         }
 676
 677                         // can always see the target portal
 678                         passage->canSee[n >> 3] |= (1 << (n&7));
 679                 }
 680         }
 681         if ( passageMemory < 1024 ) {
 682                 gameLocal.Printf( "%5d bytes passage memory used to build PVS\n", passageMemory );
 683         }
 684         else {
 685                 gameLocal.Printf( "%5d KB passage memory used to build PVS\n", passageMemory>>10 );
 686         }
 687 }
 688
 689 /*
 690 ================
 691 idPVS::DestroyPassages
 692 ================
 693 */
 694 void idPVS::DestroyPassages( void ) const {
 695         int i, j;
 696         pvsPortal_t *p;
 697         pvsArea_t *area;
 698
 699         for ( i = 0; i < numPortals; i++ ) {
 700                 p = &pvsPortals[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;
 705                         }
 706                 }
 707                 delete[] p->passages;
 708         }
 709 }
 710
 711 /*
 712 ================
 713 idPVS::CopyPortalPVSToMightSee
 714 ================
 715 */
 716 void idPVS::CopyPortalPVSToMightSee( void ) const {
 717         int i;
 718         pvsPortal_t *p;
 719
 720         for ( i = 0; i < numPortals; i++ ) {
 721                 p = &pvsPortals[i];
 722                 memcpy( p->mightSee, p->vis, portalVisBytes );
 723         }
 724 }
 725
 726 /*
 727 ================
 728 idPVS::AreaPVSFromPortalPVS
 729 ================
 730 */
 731 int idPVS::AreaPVSFromPortalPVS( void ) const {
 732         int i, j, k, areaNum, totalVisibleAreas;
 733         long *p1, *p2;
 734         byte *pvs, *portalPVS;
 735         pvsArea_t *area;
 736
 737         totalVisibleAreas = 0;
 738
 739         if ( !numPortals ) {
 740                 return totalVisibleAreas;
 741         }
 742
 743         memset( areaPVS, 0, numAreas * areaVisBytes );
 744
 745         for ( i = 0; i < numAreas; i++ ) {
 746                 area = &pvsAreas[i];
 747                 pvs = areaPVS + i * areaVisBytes;
 748
 749                 // the area is visible to itself
 750                 pvs[ i >> 3 ] |= 1 << (i & 7);
 751
 752                 if ( !area->numPortals ) {
 753                         continue;
 754                 }
 755
 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++ ) {
 761                                 *p1++ |= *p2++;
 762                         }
 763                 }
 764
 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);
 769                 }
 770
 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);
 778                         }
 779                 }
 780
 781                 // count the number of visible areas
 782                 for ( j = 0; j < numAreas; j++ ) {
 783                         if ( pvs[j>>3] & (1 << (j&7)) ) {
 784                                 totalVisibleAreas++;
 785                         }
 786                 }
 787         }
 788         return totalVisibleAreas;
 789 }
 790
 791 /*
 792 ================
 793 idPVS::Init
 794 ================
 795 */
 796 void idPVS::Init( void ) {
 797         int totalVisibleAreas;
 798
 799         Shutdown();
 800
 801         numAreas = gameRenderWorld->NumAreas();
 802         if ( numAreas <= 0 ) {
 803                 return;
 804         }
 805
 806         connectedAreas = new bool[numAreas];
 807         areaQueue = new int[numAreas];
 808
 809         areaVisBytes = ( ((numAreas+31)&~31) >> 3);
 810         areaVisLongs = areaVisBytes/sizeof(long);
 811
 812         areaPVS = new byte[numAreas * areaVisBytes];
 813         memset( areaPVS, 0xFF, numAreas * areaVisBytes );
 814
 815         numPortals = GetPortalCount();
 816
 817         portalVisBytes = ( ((numPortals+31)&~31) >> 3);
 818         portalVisLongs = portalVisBytes/sizeof(long);
 819
 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 );
 825         }
 826
 827         idTimer timer;
 828         timer.Start();
 829
 830         CreatePVSData();
 831
 832         FrontPortalPVS();
 833
 834         CopyPortalPVSToMightSee();
 835
 836         PassagePVS();
 837
 838         totalVisibleAreas = AreaPVSFromPortalPVS();
 839
 840         DestroyPVSData();
 841
 842         timer.Stop();
 843
 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 );
 850         }
 851         else {
 852                 gameLocal.Printf( "%5d KB PVS data\n", (numAreas * areaVisBytes) >> 10 );
 853         }
 854 }
 855
 856 /*
 857 ================
 858 idPVS::Shutdown
 859 ================
 860 */
 861 void idPVS::Shutdown( void ) {
 862         if ( connectedAreas ) {
 863                 delete connectedAreas;
 864                 connectedAreas = NULL;
 865         }
 866         if ( areaQueue ) {
 867                 delete areaQueue;
 868                 areaQueue = NULL;
 869         }
 870         if ( areaPVS ) {
 871                 delete areaPVS;
 872                 areaPVS = NULL;
 873         }
 874         if ( currentPVS ) {
 875                 for ( int i = 0; i < MAX_CURRENT_PVS; i++ ) {
 876                         delete currentPVS[i].pvs;
 877                         currentPVS[i].pvs = NULL;
 878                 }
 879         }
 880 }
 881
 882 /*
 883 ================
 884 idPVS::GetConnectedAreas
 885
 886   assumes the 'areas' array is initialized to false
 887 ================
 888 */
 889 void idPVS::GetConnectedAreas( int srcArea, bool *areas ) const {
 890         int curArea, nextArea;
 891         int queueStart, queueEnd;
 892         int i, n;
 893         exitPortal_t portal;
 894
 895         queueStart = -1;
 896         queueEnd = 0;
 897         areas[srcArea] = true;
 898
 899         for ( curArea = srcArea; queueStart < queueEnd; curArea = areaQueue[++queueStart] ) {
 900
 901                 n = gameRenderWorld->NumPortalsInArea( curArea );
 902
 903                 for ( i = 0; i < n; i++ ) {
 904                         portal = gameRenderWorld->GetPortal( curArea, i );
 905
 906                         if ( portal.blockingBits & PS_BLOCK_VIEW ) {
 907                                 continue;
 908                         }
 909
 910                         // area[1] is always the area the portal leads to
 911                         nextArea = portal.areas[1];
 912
 913                         // if already visited this area
 914                         if ( areas[nextArea] ) {
 915                                 continue;
 916                         }
 917
 918                         // add area to queue
 919                         areaQueue[queueEnd++] = nextArea;
 920                         areas[nextArea] = true;
 921                 }
 922         }
 923 }
 924
 925 /*
 926 ================
 927 idPVS::GetPVSArea
 928 ================
 929 */
 930 int idPVS::GetPVSArea( const idVec3 &point ) const {
 931         return gameRenderWorld->PointInArea( point );
 932 }
 933
 934 /*
 935 ================
 936 idPVS::GetPVSAreas
 937 ================
 938 */
 939 int idPVS::GetPVSAreas( const idBounds &bounds, int *areas, int maxAreas ) const {
 940         return gameRenderWorld->BoundsInAreas( bounds, areas, maxAreas );
 941 }
 942
 943 /*
 944 ================
 945 idPVS::SetupCurrentPVS
 946 ================
 947 */
 948 pvsHandle_t idPVS::SetupCurrentPVS( const idVec3 &source, const pvsType_t type ) const {
 949         int sourceArea;
 950
 951         sourceArea = gameRenderWorld->PointInArea( source );
 952
 953         return SetupCurrentPVS( sourceArea, type );
 954 }
 955
 956 /*
 957 ================
 958 idPVS::SetupCurrentPVS
 959 ================
 960 */
 961 pvsHandle_t idPVS::SetupCurrentPVS( const idBounds &source, const pvsType_t type ) const {
 962         int numSourceAreas, sourceAreas[MAX_BOUNDS_AREAS];
 963
 964         numSourceAreas = gameRenderWorld->BoundsInAreas( source, sourceAreas, MAX_BOUNDS_AREAS );
 965
 966         return SetupCurrentPVS( sourceAreas, numSourceAreas, type );
 967 }
 968
 969 /*
 970 ================
 971 idPVS::SetupCurrentPVS
 972 ================
 973 */
 974 pvsHandle_t idPVS::SetupCurrentPVS( const int sourceArea, const pvsType_t type ) const {
 975         int i;
 976         pvsHandle_t handle;
 977
 978         handle = AllocCurrentPVS( *reinterpret_cast<const unsigned int *>(&sourceArea) );
 979
 980         if ( sourceArea < 0 || sourceArea >= numAreas ) {
 981                 memset( currentPVS[handle.i].pvs, 0, areaVisBytes );
 982                 return handle;
 983         }
 984
 985         if ( type != PVS_CONNECTED_AREAS ) {
 986                 memcpy( currentPVS[handle.i].pvs, areaPVS + sourceArea * areaVisBytes, areaVisBytes );
 987         } else {
 988                 memset( currentPVS[handle.i].pvs, -1, areaVisBytes );
 989         }
 990
 991         if ( type == PVS_ALL_PORTALS_OPEN ) {
 992                 return handle;
 993         }
 994
 995         memset( connectedAreas, 0, numAreas * sizeof( *connectedAreas ) );
 996
 997         GetConnectedAreas( sourceArea, connectedAreas );
 998
 999         for ( i = 0; i < numAreas; i++ ) {
1000                 if ( !connectedAreas[i] ) {
1001                         currentPVS[handle.i].pvs[i>>3] &= ~(1 << (i&7));
1002                 }
1003         }
1004
1005         return handle;
1006 }
1007
1008 /*
1009 ================
1010 idPVS::SetupCurrentPVS
1011 ================
1012 */
1013 pvsHandle_t idPVS::SetupCurrentPVS( const int *sourceAreas, const int numSourceAreas, const pvsType_t type ) const {
1014         int i, j;
1015         unsigned int h;
1016         long *vis, *pvs;
1017         pvsHandle_t handle;
1018
1019         h = 0;
1020         for ( i = 0; i < numSourceAreas; i++ ) {
1021                 h ^= *reinterpret_cast<const unsigned int *>(&sourceAreas[i]);
1022         }
1023         handle = AllocCurrentPVS( h );
1024
1025         if ( !numSourceAreas || sourceAreas[0] < 0 || sourceAreas[0] >= numAreas) {
1026                 memset( currentPVS[handle.i].pvs, 0, areaVisBytes );
1027                 return handle;
1028         }
1029
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++ ) {
1034
1035                         assert( sourceAreas[i] >= 0 && sourceAreas[i] < numAreas );
1036
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++ ) {
1040                                 *pvs++ |= *vis++;
1041                         }
1042                 }
1043         } else {
1044                 memset( currentPVS[handle.i].pvs, -1, areaVisBytes );
1045         }
1046
1047         if ( type == PVS_ALL_PORTALS_OPEN ) {
1048                 return handle;
1049         }
1050
1051         memset( connectedAreas, 0, numAreas * sizeof( *connectedAreas ) );
1052
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 );
1057                 }
1058         }
1059
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));
1064                 }
1065         }
1066
1067         return handle;
1068 }
1069
1070 /*
1071 ================
1072 idPVS::MergeCurrentPVS
1073 ================
1074 */
1075 pvsHandle_t idPVS::MergeCurrentPVS( pvsHandle_t pvs1, pvsHandle_t pvs2 ) const {
1076         int i;
1077         long *pvs1Ptr, *pvs2Ptr, *ptr;
1078         pvsHandle_t handle;
1079
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" );
1083         }
1084
1085         handle = AllocCurrentPVS( pvs1.h ^ pvs2.h );
1086
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);
1090
1091         for ( i = 0; i < areaVisLongs; i++ ) {
1092                 *ptr++ = *pvs1Ptr++ | *pvs2Ptr++;
1093         }
1094
1095         return handle;
1096 }
1097
1098 /*
1099 ================
1100 idPVS::AllocCurrentPVS
1101 ================
1102 */
1103 pvsHandle_t idPVS::AllocCurrentPVS( unsigned int h ) const {
1104         int i;
1105         pvsHandle_t handle;
1106
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;
1112                 }
1113         }
1114
1115         gameLocal.Error( "idPVS::AllocCurrentPVS: no free PVS left" );
1116
1117         handle.i = -1;
1118         handle.h = 0;
1119         return handle;
1120 }
1121
1122 /*
1123 ================
1124 idPVS::FreeCurrentPVS
1125 ================
1126 */
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" );
1130         }
1131         currentPVS[handle.i].handle.i = -1;
1132 }
1133
1134 /*
1135 ================
1136 idPVS::InCurrentPVS
1137 ================
1138 */
1139 bool idPVS::InCurrentPVS( const pvsHandle_t handle, const idVec3 &target ) const {
1140         int targetArea;
1141
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" );
1145         }
1146
1147         targetArea = gameRenderWorld->PointInArea( target );
1148
1149         if ( targetArea == -1 ) {
1150                 return false;
1151         }
1152
1153         return ( ( currentPVS[handle.i].pvs[targetArea>>3] & (1 << (targetArea&7)) ) != 0 );
1154 }
1155
1156 /*
1157 ================
1158 idPVS::InCurrentPVS
1159 ================
1160 */
1161 bool idPVS::InCurrentPVS( const pvsHandle_t handle, const idBounds &target ) const {
1162         int i, numTargetAreas, targetAreas[MAX_BOUNDS_AREAS];
1163
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" );
1167         }
1168
1169         numTargetAreas = gameRenderWorld->BoundsInAreas( target, targetAreas, MAX_BOUNDS_AREAS );
1170
1171         for ( i = 0; i < numTargetAreas; i++ ) {
1172                 if ( currentPVS[handle.i].pvs[targetAreas[i]>>3] & (1 << (targetAreas[i]&7)) ) {
1173                         return true;
1174                 }
1175         }
1176         return false;
1177 }
1178
1179 /*
1180 ================
1181 idPVS::InCurrentPVS
1182 ================
1183 */
1184 bool idPVS::InCurrentPVS( const pvsHandle_t handle, const int targetArea ) const {
1185
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" );
1189         }
1190
1191         if ( targetArea < 0 || targetArea >= numAreas ) {
1192                 return false;
1193         }
1194
1195         return ( ( currentPVS[handle.i].pvs[targetArea>>3] & (1 << (targetArea&7)) ) != 0 );
1196 }
1197
1198 /*
1199 ================
1200 idPVS::InCurrentPVS
1201 ================
1202 */
1203 bool idPVS::InCurrentPVS( const pvsHandle_t handle, const int *targetAreas, int numTargetAreas ) const {
1204         int i;
1205
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" );
1209         }
1210
1211         for ( i = 0; i < numTargetAreas; i++ ) {
1212                 if ( targetAreas[i] < 0 || targetAreas[i] >= numAreas ) {
1213                         continue;
1214                 }
1215                 if ( currentPVS[handle.i].pvs[targetAreas[i]>>3] & (1 << (targetAreas[i]&7)) ) {
1216                         return true;
1217                 }
1218         }
1219         return false;
1220 }
1221
1222 /*
1223 ================
1224 idPVS::DrawPVS
1225 ================
1226 */
1227 void idPVS::DrawPVS( const idVec3 &source, const pvsType_t type ) const {
1228         int i, j, k, numPoints, n, sourceArea;
1229         exitPortal_t portal;
1230         idPlane plane;
1231         idVec3 offset;
1232         idVec4 *color;
1233         pvsHandle_t handle;
1234
1235         sourceArea = gameRenderWorld->PointInArea( source );
1236
1237         if ( sourceArea == -1 ) {
1238                 return;
1239         }
1240
1241         handle = SetupCurrentPVS( source, type );
1242
1243         for ( j = 0; j < numAreas; j++ ) {
1244
1245                 if ( !( currentPVS[handle.i].pvs[j>>3] & (1 << (j&7)) ) ) {
1246                         continue;
1247                 }
1248
1249                 if ( j == sourceArea ) {
1250                         color = &colorRed;
1251                 }
1252                 else {
1253                         color = &colorCyan;
1254                 }
1255
1256                 n = gameRenderWorld->NumPortalsInArea( j );
1257
1258                 // draw all the portals of the area
1259                 for ( i = 0; i < n; i++ ) {
1260                         portal = gameRenderWorld->GetPortal( j, i );
1261
1262                         numPoints = portal.w->GetNumPoints();
1263
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 );
1268                         }
1269                 }
1270         }
1271
1272         FreeCurrentPVS( handle );
1273 }
1274
1275 /*
1276 ================
1277 idPVS::DrawPVS
1278 ================
1279 */
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;
1283         idPlane plane;
1284         idVec3 offset;
1285         idVec4 *color;
1286         pvsHandle_t handle;
1287
1288         num = gameRenderWorld->BoundsInAreas( source, areas, MAX_BOUNDS_AREAS );
1289
1290         if ( !num ) {
1291                 return;
1292         }
1293
1294         handle = SetupCurrentPVS( source, type );
1295
1296         for ( j = 0; j < numAreas; j++ ) {
1297
1298                 if ( !( currentPVS[handle.i].pvs[j>>3] & (1 << (j&7)) ) ) {
1299                         continue;
1300                 }
1301
1302                 for ( i = 0; i < num; i++ ) {
1303                         if ( j == areas[i] ) {
1304                                 break;
1305                         }
1306                 }
1307                 if ( i < num ) {
1308                         color = &colorRed;
1309                 }
1310                 else {
1311                         color = &colorCyan;
1312                 }
1313
1314                 n = gameRenderWorld->NumPortalsInArea( j );
1315
1316                 // draw all the portals of the area
1317                 for ( i = 0; i < n; i++ ) {
1318                         portal = gameRenderWorld->GetPortal( j, i );
1319
1320                         numPoints = portal.w->GetNumPoints();
1321
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 );
1326                         }
1327                 }
1328         }
1329
1330         FreeCurrentPVS( handle );
1331 }
1332
1333 /*
1334 ================
1335 idPVS::DrawPVS
1336 ================
1337 */
1338 void idPVS::DrawCurrentPVS( const pvsHandle_t handle, const idVec3 &source ) const {
1339         int i, j, k, numPoints, n, sourceArea;
1340         exitPortal_t portal;
1341         idPlane plane;
1342         idVec3 offset;
1343         idVec4 *color;
1344
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" );
1348         }
1349
1350         sourceArea = gameRenderWorld->PointInArea( source );
1351
1352         if ( sourceArea == -1 ) {
1353                 return;
1354         }
1355
1356         for ( j = 0; j < numAreas; j++ ) {
1357
1358                 if ( !( currentPVS[handle.i].pvs[j>>3] & (1 << (j&7)) ) ) {
1359                         continue;
1360                 }
1361
1362                 if ( j == sourceArea ) {
1363                         color = &colorRed;
1364                 }
1365                 else {
1366                         color = &colorCyan;
1367                 }
1368
1369                 n = gameRenderWorld->NumPortalsInArea( j );
1370
1371                 // draw all the portals of the area
1372                 for ( i = 0; i < n; i++ ) {
1373                         portal = gameRenderWorld->GetPortal( j, i );
1374
1375                         numPoints = portal.w->GetNumPoints();
1376
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 );
1381                         }
1382                 }
1383         }
1384 }
1385
1386 #if ASYNC_WRITE_PVS
1387
1388 /*
1389 ===================
1390 idPVS::WritePVS
1391 ===================
1392 */
1393 void idPVS::WritePVS( const pvsHandle_t handle, idBitMsg &msg ) {
1394         msg.WriteData( currentPVS[ handle.i ].pvs, areaVisBytes );
1395 }
1396
1397 /*
1398 ===================
1399 idPVS::ReadPVS
1400 ===================
1401 */
1402 void idPVS::ReadPVS( const pvsHandle_t handle, const idBitMsg &msg ) {
1403         byte    l_pvs[ 256 ];
1404         int             i;
1405
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 ] );
1412                 }
1413                 common->Printf( "\n" );
1414                 for ( i = 0; i < areaVisBytes; i++ ) {
1415                         common->Printf( "%x ", currentPVS[ handle.i ].pvs[ i ] );
1416                 }
1417                 common->Printf( "\n" );
1418         }
1419 }
1420
1421 #endif
1422
1423
1424 #ifdef _D3XP
1425 /*
1426 ================
1427 idPVS::CheckAreasForPortalSky
1428 ================
1429 */
1430 bool idPVS::CheckAreasForPortalSky( const pvsHandle_t handle, const idVec3 &origin ) {
1431         int j, sourceArea;
1432
1433         if ( handle.i < 0 || handle.i >= MAX_CURRENT_PVS || handle.h != currentPVS[handle.i].handle.h ) {
1434                 return false;
1435         }
1436
1437         sourceArea = gameRenderWorld->PointInArea( origin );
1438
1439         if ( sourceArea == -1 ) {
1440                 return false;
1441         }
1442
1443         for ( j = 0; j < numAreas; j++ ) {
1444
1445                 if ( !( currentPVS[handle.i].pvs[j>>3] & (1 << (j&7)) ) ) {
1446                         continue;
1447                 }
1448
1449                 if ( gameRenderWorld->CheckAreaForPortalSky( j ) ) {
1450                         return true;
1451                 }
1452         }
1453
1454         return false;
1455 }
1456 #endif