neo/renderer/RenderWorld_portals.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 "tr_local.h"
  33
  34 /*
  35
  36
  37 All that is done in these functions is the creation of viewLights
  38 and viewEntitys for the lightDefs and entityDefs that are visible
  39 in the portal areas that can be seen from the current viewpoint.
  40
  41 */
  42
  43
  44 // if we hit this many planes, we will just stop cropping the
  45 // view down, which is still correct, just conservative
  46 const int MAX_PORTAL_PLANES     = 20;
  47
  48 typedef struct portalStack_s {
  49         portal_t        *p;
  50         const struct portalStack_s *next;
  51
  52         idScreenRect    rect;
  53
  54         int                     numPortalPlanes;
  55         idPlane         portalPlanes[MAX_PORTAL_PLANES+1];
  56         // positive side is outside the visible frustum
  57 } portalStack_t;
  58
  59
  60 //====================================================================
  61
  62
  63 /*
  64 ===================
  65 idRenderWorldLocal::ScreenRectForWinding
  66 ===================
  67 */
  68 idScreenRect idRenderWorldLocal::ScreenRectFromWinding( const idWinding *w, viewEntity_t *space ) {
  69         idScreenRect    r;
  70         int                             i;
  71         idVec3                  v;
  72         idVec3                  ndc;
  73         float                   windowX, windowY;
  74
  75         r.Clear();
  76         for ( i = 0 ; i < w->GetNumPoints() ; i++ ) {
  77                 R_LocalPointToGlobal( space->modelMatrix, (*w)[i].ToVec3(), v );
  78                 R_GlobalToNormalizedDeviceCoordinates( v, ndc );
  79
  80                 windowX = 0.5f * ( 1.0f + ndc[0] ) * ( tr.viewDef->viewport.x2 - tr.viewDef->viewport.x1 );
  81                 windowY = 0.5f * ( 1.0f + ndc[1] ) * ( tr.viewDef->viewport.y2 - tr.viewDef->viewport.y1 );
  82
  83                 r.AddPoint( windowX, windowY );
  84         }
  85
  86         r.Expand();
  87
  88         return r;
  89 }
  90
  91 /*
  92 ===================
  93 PortalIsFoggedOut
  94 ===================
  95 */
  96 bool idRenderWorldLocal::PortalIsFoggedOut( const portal_t *p ) {
  97         idRenderLightLocal      *ldef;
  98         const idWinding *w;
  99         int                     i;
 100         idPlane         forward;
 101
 102         ldef = p->doublePortal->fogLight;
 103         if ( !ldef ) {
 104                 return false;
 105         }
 106
 107         // find the current density of the fog
 108         const idMaterial        *lightShader = ldef->lightShader;
 109         int             size = sizeof( float ) *lightShader->GetNumRegisters();
 110         float   *regs =(float *)_alloca( size );
 111
 112         lightShader->EvaluateRegisters( regs, ldef->parms.shaderParms, tr.viewDef, ldef->parms.referenceSound );
 113
 114         const shaderStage_t     *stage = lightShader->GetStage(0);
 115
 116         float alpha = regs[ stage->color.registers[3] ];
 117
 118
 119         // if they left the default value on, set a fog distance of 500
 120         float   a;
 121
 122         if ( alpha <= 1.0f ) {
 123                 a = -0.5f / DEFAULT_FOG_DISTANCE;
 124         } else {
 125                 // otherwise, distance = alpha color
 126                 a = -0.5f / alpha;
 127         }
 128
 129         forward[0] = a * tr.viewDef->worldSpace.modelViewMatrix[2];
 130         forward[1] = a * tr.viewDef->worldSpace.modelViewMatrix[6];
 131         forward[2] = a * tr.viewDef->worldSpace.modelViewMatrix[10];
 132         forward[3] = a * tr.viewDef->worldSpace.modelViewMatrix[14];
 133
 134         w = p->w;
 135         for ( i = 0 ; i < w->GetNumPoints() ; i++ ) {
 136                 float   d;
 137
 138                 d = forward.Distance( (*w)[i].ToVec3() );
 139                 if ( d < 0.5f ) {
 140                         return false;           // a point not clipped off
 141                 }
 142         }
 143
 144         return true;
 145 }
 146
 147 /*
 148 ===================
 149 FloodViewThroughArea_r
 150 ===================
 151 */
 152 void idRenderWorldLocal::FloodViewThroughArea_r( const idVec3 origin, int areaNum,
 153                                                                  const struct portalStack_s *ps ) {
 154         portal_t*               p;
 155         float                   d;
 156         portalArea_t *  area;
 157         const portalStack_t     *check;
 158         portalStack_t   newStack;
 159         int                             i, j;
 160         idVec3                  v1, v2;
 161         int                             addPlanes;
 162         idFixedWinding  w;              // we won't overflow because MAX_PORTAL_PLANES = 20
 163
 164         area = &portalAreas[ areaNum ];
 165
 166         // cull models and lights to the current collection of planes
 167         AddAreaRefs( areaNum, ps );
 168
 169         if ( areaScreenRect[areaNum].IsEmpty() ) {
 170                 areaScreenRect[areaNum] = ps->rect;
 171         } else {
 172                 areaScreenRect[areaNum].Union( ps->rect );
 173         }
 174
 175         // go through all the portals
 176         for ( p = area->portals; p; p = p->next ) {
 177                 // an enclosing door may have sealed the portal off
 178                 if ( p->doublePortal->blockingBits & PS_BLOCK_VIEW ) {
 179                         continue;
 180                 }
 181
 182                 // make sure this portal is facing away from the view
 183                 d = p->plane.Distance( origin );
 184                 if ( d < -0.1f ) {
 185                         continue;
 186                 }
 187
 188                 // make sure the portal isn't in our stack trace,
 189                 // which would cause an infinite loop
 190                 for ( check = ps; check; check = check->next ) {
 191                         if ( check->p == p ) {
 192                                 break;          // don't recursively enter a stack
 193                         }
 194                 }
 195                 if ( check ) {
 196                         continue;       // already in stack
 197                 }
 198
 199                 // if we are very close to the portal surface, don't bother clipping
 200                 // it, which tends to give epsilon problems that make the area vanish
 201                 if ( d < 1.0f ) {
 202
 203                         // go through this portal
 204                         newStack = *ps;
 205                         newStack.p = p;
 206                         newStack.next = ps;
 207                         FloodViewThroughArea_r( origin, p->intoArea, &newStack );
 208                         continue;
 209                 }
 210
 211                 // clip the portal winding to all of the planes
 212                 w = *p->w;
 213                 for ( j = 0; j < ps->numPortalPlanes; j++ ) {
 214                         if ( !w.ClipInPlace( -ps->portalPlanes[j], 0 ) ) {
 215                                 break;
 216                         }
 217                 }
 218                 if ( !w.GetNumPoints() ) {
 219                         continue;       // portal not visible
 220                 }
 221
 222                 // see if it is fogged out
 223                 if ( PortalIsFoggedOut( p ) ) {
 224                         continue;
 225                 }
 226
 227                 // go through this portal
 228                 newStack.p = p;
 229                 newStack.next = ps;
 230
 231                 // find the screen pixel bounding box of the remaining portal
 232                 // so we can scissor things outside it
 233                 newStack.rect = ScreenRectFromWinding( &w, &tr.identitySpace );
 234
 235                 // slop might have spread it a pixel outside, so trim it back
 236                 newStack.rect.Intersect( ps->rect );
 237
 238                 // generate a set of clipping planes that will further restrict
 239                 // the visible view beyond just the scissor rect
 240
 241                 addPlanes = w.GetNumPoints();
 242                 if ( addPlanes > MAX_PORTAL_PLANES ) {
 243                         addPlanes = MAX_PORTAL_PLANES;
 244                 }
 245
 246                 newStack.numPortalPlanes = 0;
 247                 for ( i = 0; i < addPlanes; i++ ) {
 248                         j = i+1;
 249                         if ( j == w.GetNumPoints() ) {
 250                                 j = 0;
 251                         }
 252
 253                         v1 = origin - w[i].ToVec3();
 254                         v2 = origin - w[j].ToVec3();
 255
 256                         newStack.portalPlanes[newStack.numPortalPlanes].Normal().Cross( v2, v1 );
 257
 258                         // if it is degenerate, skip the plane
 259                         if ( newStack.portalPlanes[newStack.numPortalPlanes].Normalize() < 0.01f ) {
 260                                 continue;
 261                         }
 262                         newStack.portalPlanes[newStack.numPortalPlanes].FitThroughPoint( origin );
 263
 264                         newStack.numPortalPlanes++;
 265                 }
 266
 267                 // the last stack plane is the portal plane
 268                 newStack.portalPlanes[newStack.numPortalPlanes] = p->plane;
 269                 newStack.numPortalPlanes++;
 270
 271                 FloodViewThroughArea_r( origin, p->intoArea, &newStack );
 272         }
 273 }
 274
 275 /*
 276 =======================
 277 FlowViewThroughPortals
 278
 279 Finds viewLights and viewEntities by flowing from an origin through the visible portals.
 280 origin point can see into.  The planes array defines a volume (positive
 281 sides facing in) that should contain the origin, such as a view frustum or a point light box.
 282 Zero planes assumes an unbounded volume.
 283 =======================
 284 */
 285 void idRenderWorldLocal::FlowViewThroughPortals( const idVec3 origin, int numPlanes, const idPlane *planes ) {
 286         portalStack_t   ps;
 287         int                             i;
 288
 289         ps.next = NULL;
 290         ps.p = NULL;
 291
 292         for ( i = 0 ; i < numPlanes ; i++ ) {
 293                 ps.portalPlanes[i] = planes[i];
 294         }
 295
 296         ps.numPortalPlanes = numPlanes;
 297         ps.rect = tr.viewDef->scissor;
 298
 299         if ( tr.viewDef->areaNum < 0 ){
 300
 301                 for ( i = 0; i < numPortalAreas; i++ ) {
 302                         areaScreenRect[i] = tr.viewDef->scissor;
 303                 }
 304
 305                 // if outside the world, mark everything
 306                 for ( i = 0 ; i < numPortalAreas ; i++ ) {
 307                         AddAreaRefs( i, &ps );
 308                 }
 309         } else {
 310
 311                 for ( i = 0; i < numPortalAreas; i++ ) {
 312                         areaScreenRect[i].Clear();
 313                 }
 314
 315                 // flood out through portals, setting area viewCount
 316                 FloodViewThroughArea_r( origin, tr.viewDef->areaNum, &ps );
 317         }
 318 }
 319
 320 //==================================================================================================
 321
 322
 323 /*
 324 ===================
 325 FloodLightThroughArea_r
 326 ===================
 327 */
 328 void idRenderWorldLocal::FloodLightThroughArea_r( idRenderLightLocal *light, int areaNum,
 329                                                                  const struct portalStack_s *ps ) {
 330         portal_t*               p;
 331         float                   d;
 332         portalArea_t *  area;
 333         const portalStack_t     *check, *firstPortalStack;
 334         portalStack_t   newStack;
 335         int                             i, j;
 336         idVec3                  v1, v2;
 337         int                             addPlanes;
 338         idFixedWinding  w;              // we won't overflow because MAX_PORTAL_PLANES = 20
 339
 340         area = &portalAreas[ areaNum ];
 341
 342         // add an areaRef
 343         AddLightRefToArea( light, area );
 344
 345         // go through all the portals
 346         for ( p = area->portals; p; p = p->next ) {
 347                 // make sure this portal is facing away from the view
 348                 d = p->plane.Distance( light->globalLightOrigin );
 349                 if ( d < -0.1f ) {
 350                         continue;
 351                 }
 352
 353                 // make sure the portal isn't in our stack trace,
 354                 // which would cause an infinite loop
 355                 for ( check = ps; check; check = check->next ) {
 356                         firstPortalStack = check;
 357                         if ( check->p == p ) {
 358                                 break;          // don't recursively enter a stack
 359                         }
 360                 }
 361                 if ( check ) {
 362                         continue;       // already in stack
 363                 }
 364
 365                 // if we are very close to the portal surface, don't bother clipping
 366                 // it, which tends to give epsilon problems that make the area vanish
 367                 if ( d < 1.0f ) {
 368                         // go through this portal
 369                         newStack = *ps;
 370                         newStack.p = p;
 371                         newStack.next = ps;
 372                         FloodLightThroughArea_r( light, p->intoArea, &newStack );
 373                         continue;
 374                 }
 375
 376                 // clip the portal winding to all of the planes
 377                 w = *p->w;
 378                 for ( j = 0; j < ps->numPortalPlanes; j++ ) {
 379                         if ( !w.ClipInPlace( -ps->portalPlanes[j], 0 ) ) {
 380                                 break;
 381                         }
 382                 }
 383                 if ( !w.GetNumPoints() ) {
 384                         continue;       // portal not visible
 385                 }
 386                 // also always clip to the original light planes, because they aren't
 387                 // necessarily extending to infinitiy like a view frustum
 388                 for ( j = 0; j < firstPortalStack->numPortalPlanes; j++ ) {
 389                         if ( !w.ClipInPlace( -firstPortalStack->portalPlanes[j], 0 ) ) {
 390                                 break;
 391                         }
 392                 }
 393                 if ( !w.GetNumPoints() ) {
 394                         continue;       // portal not visible
 395                 }
 396
 397                 // go through this portal
 398                 newStack.p = p;
 399                 newStack.next = ps;
 400
 401                 // generate a set of clipping planes that will further restrict
 402                 // the visible view beyond just the scissor rect
 403
 404                 addPlanes = w.GetNumPoints();
 405                 if ( addPlanes > MAX_PORTAL_PLANES ) {
 406                         addPlanes = MAX_PORTAL_PLANES;
 407                 }
 408
 409                 newStack.numPortalPlanes = 0;
 410                 for ( i = 0; i < addPlanes; i++ ) {
 411                         j = i+1;
 412                         if ( j == w.GetNumPoints() ) {
 413                                 j = 0;
 414                         }
 415
 416                         v1 = light->globalLightOrigin - w[i].ToVec3();
 417                         v2 = light->globalLightOrigin - w[j].ToVec3();
 418
 419                         newStack.portalPlanes[newStack.numPortalPlanes].Normal().Cross( v2, v1 );
 420
 421                         // if it is degenerate, skip the plane
 422                         if ( newStack.portalPlanes[newStack.numPortalPlanes].Normalize() < 0.01f ) {
 423                                 continue;
 424                         }
 425                         newStack.portalPlanes[newStack.numPortalPlanes].FitThroughPoint( light->globalLightOrigin );
 426
 427                         newStack.numPortalPlanes++;
 428                 }
 429
 430                 FloodLightThroughArea_r( light, p->intoArea, &newStack );
 431         }
 432 }
 433
 434
 435 /*
 436 =======================
 437 FlowLightThroughPortals
 438
 439 Adds an arearef in each area that the light center flows into.
 440 This can only be used for shadow casting lights that have a generated
 441 prelight, because shadows are cast from back side which may not be in visible areas.
 442 =======================
 443 */
 444 void idRenderWorldLocal::FlowLightThroughPortals( idRenderLightLocal *light ) {
 445         portalStack_t   ps;
 446         int                             i;
 447         const idVec3 origin = light->globalLightOrigin;
 448
 449         // if the light origin areaNum is not in a valid area,
 450         // the light won't have any area refs
 451         if ( light->areaNum == -1 ) {
 452                 return;
 453         }
 454
 455         memset( &ps, 0, sizeof( ps ) );
 456
 457         ps.numPortalPlanes = 6;
 458         for ( i = 0 ; i < 6 ; i++ ) {
 459                 ps.portalPlanes[i] = light->frustum[i];
 460         }
 461
 462         FloodLightThroughArea_r( light, light->areaNum, &ps );
 463 }
 464
 465 //======================================================================================================
 466
 467 /*
 468 ===================
 469 idRenderWorldLocal::FloodFrustumAreas_r
 470 ===================
 471 */
 472 areaNumRef_t *idRenderWorldLocal::FloodFrustumAreas_r( const idFrustum &frustum, const int areaNum, const idBounds &bounds, areaNumRef_t *areas ) {
 473         portal_t *p;
 474         portalArea_t *portalArea;
 475         idBounds newBounds;
 476         areaNumRef_t *a;
 477
 478         portalArea = &portalAreas[ areaNum ];
 479
 480         // go through all the portals
 481         for ( p = portalArea->portals; p; p = p->next ) {
 482
 483                 // check if we already visited the area the portal leads to
 484                 for ( a = areas; a; a = a->next ) {
 485                         if ( a->areaNum == p->intoArea ) {
 486                                 break;
 487                         }
 488                 }
 489                 if ( a ) {
 490                         continue;
 491                 }
 492
 493                 // the frustum origin must be at the front of the portal plane
 494                 if ( p->plane.Side( frustum.GetOrigin(), 0.1f ) == SIDE_BACK ) {
 495                         continue;
 496                 }
 497
 498                 // the frustum must cross the portal plane
 499                 if ( frustum.PlaneSide( p->plane, 0.0f ) != PLANESIDE_CROSS ) {
 500                         continue;
 501                 }
 502
 503                 // get the bounds for the portal winding projected in the frustum
 504                 frustum.ProjectionBounds( *p->w, newBounds );
 505
 506                 newBounds.IntersectSelf( bounds );
 507
 508                 if ( newBounds[0][0] > newBounds[1][0] || newBounds[0][1] > newBounds[1][1] || newBounds[0][2] > newBounds[1][2] ) {
 509                         continue;
 510                 }
 511
 512                 newBounds[1][0] = frustum.GetFarDistance();
 513
 514                 a = areaNumRefAllocator.Alloc();
 515                 a->areaNum = p->intoArea;
 516                 a->next = areas;
 517                 areas = a;
 518
 519                 areas = FloodFrustumAreas_r( frustum, p->intoArea, newBounds, areas );
 520         }
 521
 522         return areas;
 523 }
 524
 525 /*
 526 ===================
 527 idRenderWorldLocal::FloodFrustumAreas
 528
 529   Retrieves all the portal areas the frustum floods into where the frustum starts in the given areas.
 530   All portals are assumed to be open.
 531 ===================
 532 */
 533 areaNumRef_t *idRenderWorldLocal::FloodFrustumAreas( const idFrustum &frustum, areaNumRef_t *areas ) {
 534         idBounds bounds;
 535         areaNumRef_t *a;
 536
 537         // bounds that cover the whole frustum
 538         bounds[0].Set( frustum.GetNearDistance(), -1.0f, -1.0f );
 539         bounds[1].Set( frustum.GetFarDistance(), 1.0f, 1.0f );
 540
 541         for ( a = areas; a; a = a->next ) {
 542                 areas = FloodFrustumAreas_r( frustum, a->areaNum, bounds, areas );
 543         }
 544
 545         return areas;
 546 }
 547
 548
 549 /*
 550 =======================================================================
 551
 552 R_FindViewLightsAndEntities
 553
 554 =======================================================================
 555 */
 556
 557 /*
 558 ================
 559 CullEntityByPortals
 560
 561 Return true if the entity reference bounds do not intersect the current portal chain.
 562 ================
 563 */
 564 bool idRenderWorldLocal::CullEntityByPortals( const idRenderEntityLocal *entity, const portalStack_t *ps ) {
 565
 566         if ( !r_useEntityCulling.GetBool() ) {
 567                 return false;
 568         }
 569
 570         // try to cull the entire thing using the reference bounds.
 571         // we do not yet do callbacks or dynamic model creation,
 572         // because we want to do all touching of the model after
 573         // we have determined all the lights that may effect it,
 574         // which optimizes cache usage
 575         if ( R_CullLocalBox( entity->referenceBounds, entity->modelMatrix,
 576                                                         ps->numPortalPlanes, ps->portalPlanes ) ) {
 577                 return true;
 578         }
 579
 580         return false;
 581 }
 582
 583 /*
 584 ===================
 585 AddAreaEntityRefs
 586
 587 Any models that are visible through the current portalStack will
 588 have their scissor
 589 ===================
 590 */
 591 void idRenderWorldLocal::AddAreaEntityRefs( int areaNum, const portalStack_t *ps ) {
 592         areaReference_t         *ref;
 593         idRenderEntityLocal     *entity;
 594         portalArea_t            *area;
 595         viewEntity_t            *vEnt;
 596         idBounds                        b;
 597
 598         area = &portalAreas[ areaNum ];
 599
 600         for ( ref = area->entityRefs.areaNext ; ref != &area->entityRefs ; ref = ref->areaNext ) {
 601                 entity = ref->entity;
 602
 603                 // debug tool to allow viewing of only one entity at a time
 604                 if ( r_singleEntity.GetInteger() >= 0 && r_singleEntity.GetInteger() != entity->index ) {
 605                         continue;
 606                 }
 607
 608                 // remove decals that are completely faded away
 609                 R_FreeEntityDefFadedDecals( entity, tr.viewDef->renderView.time );
 610
 611                 // check for completely suppressing the model
 612                 if ( !r_skipSuppress.GetBool() ) {
 613                         if ( entity->parms.suppressSurfaceInViewID
 614                                         && entity->parms.suppressSurfaceInViewID == tr.viewDef->renderView.viewID ) {
 615                                 continue;
 616                         }
 617                         if ( entity->parms.allowSurfaceInViewID
 618                                         && entity->parms.allowSurfaceInViewID != tr.viewDef->renderView.viewID ) {
 619                                 continue;
 620                         }
 621                 }
 622
 623                 // cull reference bounds
 624                 if ( CullEntityByPortals( entity, ps ) ) {
 625                         // we are culled out through this portal chain, but it might
 626                         // still be visible through others
 627                         continue;
 628                 }
 629
 630                 vEnt = R_SetEntityDefViewEntity( entity );
 631
 632                 // possibly expand the scissor rect
 633                 vEnt->scissorRect.Union( ps->rect );
 634         }
 635 }
 636
 637 /*
 638 ================
 639 CullLightByPortals
 640
 641 Return true if the light frustum does not intersect the current portal chain.
 642 The last stack plane is not used because lights are not near clipped.
 643 ================
 644 */
 645 bool idRenderWorldLocal::CullLightByPortals( const idRenderLightLocal *light, const portalStack_t *ps ) {
 646         int                             i, j;
 647         const srfTriangles_t    *tri;
 648         float                   d;
 649         idFixedWinding  w;              // we won't overflow because MAX_PORTAL_PLANES = 20
 650
 651         if ( r_useLightCulling.GetInteger() == 0 ) {
 652                 return false;
 653         }
 654
 655         if ( r_useLightCulling.GetInteger() >= 2 ) {
 656                 // exact clip of light faces against all planes
 657                 for ( i = 0; i < 6; i++ ) {
 658                         // the light frustum planes face out from the light,
 659                         // so the planes that have the view origin on the negative
 660                         // side will be the "back" faces of the light, which must have
 661                         // some fragment inside the portalStack to be visible
 662                         if ( light->frustum[i].Distance( tr.viewDef->renderView.vieworg ) >= 0 ) {
 663                                 continue;
 664                         }
 665
 666                         // get the exact winding for this side
 667                         const idWinding *ow = light->frustumWindings[i];
 668
 669                         // projected lights may have one of the frustums degenerated
 670                         if ( !ow ) {
 671                                 continue;
 672                         }
 673
 674                         w = *ow;
 675
 676                         // now check the winding against each of the portalStack planes
 677                         for ( j = 0; j < ps->numPortalPlanes - 1; j++ ) {
 678                                 if ( !w.ClipInPlace( -ps->portalPlanes[j] ) ) {
 679                                         break;
 680                                 }
 681                         }
 682
 683                         if ( w.GetNumPoints() ) {
 684                                 // part of the winding is visible through the portalStack,
 685                                 // so the light is not culled
 686                                 return false;
 687                         }
 688                 }
 689                 // none of the light surfaces were visible
 690                 return true;
 691
 692         } else {
 693
 694                 // simple point check against each plane
 695                 tri = light->frustumTris;
 696
 697                 // check against frustum planes
 698                 for ( i = 0; i < ps->numPortalPlanes - 1; i++ ) {
 699                         for ( j = 0; j < tri->numVerts; j++ ) {
 700                                 d = ps->portalPlanes[i].Distance( tri->verts[j].xyz );
 701                                 if ( d < 0.0f ) {
 702                                         break;  // point is inside this plane
 703                                 }
 704                         }
 705                         if ( j == tri->numVerts ) {
 706                                 // all points were outside one of the planes
 707                                 tr.pc.c_box_cull_out++;
 708                                 return true;
 709                         }
 710                 }
 711         }
 712
 713         return false;
 714 }
 715
 716 /*
 717 ===================
 718 AddAreaLightRefs
 719
 720 This is the only point where lights get added to the viewLights list
 721 ===================
 722 */
 723 void idRenderWorldLocal::AddAreaLightRefs( int areaNum, const portalStack_t *ps ) {
 724         areaReference_t         *lref;
 725         portalArea_t            *area;
 726         idRenderLightLocal                      *light;
 727         viewLight_t                     *vLight;
 728
 729         area = &portalAreas[ areaNum ];
 730
 731         for ( lref = area->lightRefs.areaNext ; lref != &area->lightRefs ; lref = lref->areaNext ) {
 732                 light = lref->light;
 733
 734                 // debug tool to allow viewing of only one light at a time
 735                 if ( r_singleLight.GetInteger() >= 0 && r_singleLight.GetInteger() != light->index ) {
 736                         continue;
 737                 }
 738
 739                 // check for being closed off behind a door
 740                 // a light that doesn't cast shadows will still light even if it is behind a door
 741                 if ( r_useLightCulling.GetInteger() >= 3 &&
 742                                 !light->parms.noShadows && light->lightShader->LightCastsShadows()
 743                                         && light->areaNum != -1 && !tr.viewDef->connectedAreas[ light->areaNum ] ) {
 744                         continue;
 745                 }
 746
 747                 // cull frustum
 748                 if ( CullLightByPortals( light, ps ) ) {
 749                         // we are culled out through this portal chain, but it might
 750                         // still be visible through others
 751                         continue;
 752                 }
 753
 754                 vLight = R_SetLightDefViewLight( light );
 755
 756                 // expand the scissor rect
 757                 vLight->scissorRect.Union( ps->rect );
 758         }
 759 }
 760
 761 /*
 762 ===================
 763 AddAreaRefs
 764
 765 This may be entered multiple times with different planes
 766 if more than one portal sees into the area
 767 ===================
 768 */
 769 void idRenderWorldLocal::AddAreaRefs( int areaNum, const portalStack_t *ps ) {
 770         // mark the viewCount, so r_showPortals can display the
 771         // considered portals
 772         portalAreas[ areaNum ].viewCount = tr.viewCount;
 773
 774         // add the models and lights, using more precise culling to the planes
 775         AddAreaEntityRefs( areaNum, ps );
 776         AddAreaLightRefs( areaNum, ps );
 777 }
 778
 779 /*
 780 ===================
 781 BuildConnectedAreas_r
 782 ===================
 783 */
 784 void idRenderWorldLocal::BuildConnectedAreas_r( int areaNum ) {
 785         portalArea_t    *area;
 786         portal_t                *portal;
 787
 788         if ( tr.viewDef->connectedAreas[areaNum] ) {
 789                 return;
 790         }
 791
 792         tr.viewDef->connectedAreas[areaNum] = true;
 793
 794         // flood through all non-blocked portals
 795         area = &portalAreas[ areaNum ];
 796         for ( portal = area->portals ; portal ; portal = portal->next ) {
 797                 if ( !(portal->doublePortal->blockingBits & PS_BLOCK_VIEW) ) {
 798                         BuildConnectedAreas_r( portal->intoArea );
 799                 }
 800         }
 801 }
 802
 803 /*
 804 ===================
 805 BuildConnectedAreas
 806
 807 This is only valid for a given view, not all views in a frame
 808 ===================
 809 */
 810 void idRenderWorldLocal::BuildConnectedAreas( void ) {
 811         int             i;
 812
 813         tr.viewDef->connectedAreas = (bool *)R_FrameAlloc( numPortalAreas
 814                 * sizeof( tr.viewDef->connectedAreas[0] ) );
 815
 816         // if we are outside the world, we can see all areas
 817         if ( tr.viewDef->areaNum == -1 ) {
 818                 for ( i = 0 ; i < numPortalAreas ; i++ ) {
 819                         tr.viewDef->connectedAreas[i] = true;
 820                 }
 821                 return;
 822         }
 823
 824         // start with none visible, and flood fill from the current area
 825         memset( tr.viewDef->connectedAreas, 0, numPortalAreas * sizeof( tr.viewDef->connectedAreas[0] ) );
 826         BuildConnectedAreas_r( tr.viewDef->areaNum );
 827 }
 828
 829 /*
 830 =============
 831 FindViewLightsAndEntites
 832
 833 All the modelrefs and lightrefs that are in visible areas
 834 will have viewEntitys and viewLights created for them.
 835
 836 The scissorRects on the viewEntitys and viewLights may be empty if
 837 they were considered, but not actually visible.
 838 =============
 839 */
 840 void idRenderWorldLocal::FindViewLightsAndEntities( void ) {
 841         // clear the visible lightDef and entityDef lists
 842         tr.viewDef->viewLights = NULL;
 843         tr.viewDef->viewEntitys = NULL;
 844
 845         // find the area to start the portal flooding in
 846         if ( !r_usePortals.GetBool() ) {
 847                 // debug tool to force no portal culling
 848                 tr.viewDef->areaNum = -1;
 849         } else {
 850                 tr.viewDef->areaNum = PointInArea( tr.viewDef->initialViewAreaOrigin );
 851         }
 852
 853         // determine all possible connected areas for
 854         // light-behind-door culling
 855         BuildConnectedAreas();
 856
 857         // bump the view count, invalidating all
 858         // visible areas
 859         tr.viewCount++;
 860
 861         // flow through all the portals and add models / lights
 862         if ( r_singleArea.GetBool() ) {
 863                 // if debugging, only mark this area
 864                 // if we are outside the world, don't draw anything
 865                 if ( tr.viewDef->areaNum >= 0 ) {
 866                         portalStack_t   ps;
 867                         int                             i;
 868                         static int lastPrintedAreaNum;
 869
 870                         if ( tr.viewDef->areaNum != lastPrintedAreaNum ) {
 871                                 lastPrintedAreaNum = tr.viewDef->areaNum;
 872                                 common->Printf( "entering portal area %i\n", tr.viewDef->areaNum );
 873                         }
 874
 875                         for ( i = 0 ; i < 5 ; i++ ) {
 876                                 ps.portalPlanes[i] = tr.viewDef->frustum[i];
 877                         }
 878                         ps.numPortalPlanes = 5;
 879                         ps.rect = tr.viewDef->scissor;
 880
 881                         AddAreaRefs( tr.viewDef->areaNum, &ps );
 882                 }
 883         } else {
 884                 // note that the center of projection for flowing through portals may
 885                 // be a different point than initialViewAreaOrigin for subviews that
 886                 // may have the viewOrigin in a solid/invalid area
 887                 FlowViewThroughPortals( tr.viewDef->renderView.vieworg, 5, tr.viewDef->frustum );
 888         }
 889 }
 890
 891 /*
 892 ==============
 893 NumPortals
 894 ==============
 895 */
 896 int idRenderWorldLocal::NumPortals( void ) const {
 897         return numInterAreaPortals;
 898 }
 899
 900 /*
 901 ==============
 902 FindPortal
 903
 904 Game code uses this to identify which portals are inside doors.
 905 Returns 0 if no portal contacts the bounds
 906 ==============
 907 */
 908 qhandle_t idRenderWorldLocal::FindPortal( const idBounds &b ) const {
 909         int                             i, j;
 910         idBounds                wb;
 911         doublePortal_t  *portal;
 912         idWinding               *w;
 913
 914         for ( i = 0 ; i < numInterAreaPortals ; i++ ) {
 915                 portal = &doublePortals[i];
 916                 w = portal->portals[0]->w;
 917
 918                 wb.Clear();
 919                 for ( j = 0 ; j < w->GetNumPoints() ; j++ ) {
 920                         wb.AddPoint( (*w)[j].ToVec3() );
 921                 }
 922                 if ( wb.IntersectsBounds( b ) ) {
 923                         return i + 1;
 924                 }
 925         }
 926
 927         return 0;
 928 }
 929
 930 /*
 931 =============
 932 FloodConnectedAreas
 933 =============
 934 */
 935 void    idRenderWorldLocal::FloodConnectedAreas( portalArea_t *area, int portalAttributeIndex ) {
 936         if ( area->connectedAreaNum[portalAttributeIndex] == connectedAreaNum ) {
 937                 return;
 938         }
 939         area->connectedAreaNum[portalAttributeIndex] = connectedAreaNum;
 940
 941         for ( portal_t *p = area->portals ; p ; p = p->next ) {
 942                 if ( !(p->doublePortal->blockingBits & (1<<portalAttributeIndex) ) ) {
 943                         FloodConnectedAreas( &portalAreas[p->intoArea], portalAttributeIndex );
 944                 }
 945         }
 946 }
 947
 948 /*
 949 ==============
 950 AreasAreConnected
 951
 952 ==============
 953 */
 954 bool    idRenderWorldLocal::AreasAreConnected( int areaNum1, int areaNum2, portalConnection_t connection ) {
 955         if ( areaNum1 == -1 || areaNum2 == -1 ) {
 956                 return false;
 957         }
 958         if ( areaNum1 > numPortalAreas || areaNum2 > numPortalAreas || areaNum1 < 0 || areaNum2 < 0 ) {
 959                 common->Error( "idRenderWorldLocal::AreAreasConnected: bad parms: %i, %i", areaNum1, areaNum2 );
 960         }
 961
 962         int     attribute = 0;
 963
 964         int     intConnection = (int)connection;
 965
 966         while ( intConnection > 1 ) {
 967                 attribute++;
 968                 intConnection >>= 1;
 969         }
 970         if ( attribute >= NUM_PORTAL_ATTRIBUTES || ( 1 << attribute ) != (int)connection ) {
 971                 common->Error( "idRenderWorldLocal::AreasAreConnected: bad connection number: %i\n", (int)connection );
 972         }
 973
 974         return portalAreas[areaNum1].connectedAreaNum[attribute] == portalAreas[areaNum2].connectedAreaNum[attribute];
 975 }
 976
 977
 978 /*
 979 ==============
 980 SetPortalState
 981
 982 doors explicitly close off portals when shut
 983 ==============
 984 */
 985 void            idRenderWorldLocal::SetPortalState( qhandle_t portal, int blockTypes ) {
 986         if ( portal == 0 ) {
 987                 return;
 988         }
 989
 990         if ( portal < 1 || portal > numInterAreaPortals ) {
 991                 common->Error( "SetPortalState: bad portal number %i", portal );
 992         }
 993         int     old = doublePortals[portal-1].blockingBits;
 994         if ( old == blockTypes ) {
 995                 return;
 996         }
 997         doublePortals[portal-1].blockingBits = blockTypes;
 998
 999         // leave the connectedAreaGroup the same on one side,
1000         // then flood fill from the other side with a new number for each changed attribute
1001         for ( int i = 0 ; i < NUM_PORTAL_ATTRIBUTES ; i++ ) {
1002                 if ( ( old ^ blockTypes ) & ( 1 << i ) ) {
1003                         connectedAreaNum++;
1004                         FloodConnectedAreas( &portalAreas[doublePortals[portal-1].portals[1]->intoArea], i );
1005                 }
1006         }
1007
1008         if ( session->writeDemo ) {
1009                 session->writeDemo->WriteInt( DS_RENDER );
1010                 session->writeDemo->WriteInt( DC_SET_PORTAL_STATE );
1011                 session->writeDemo->WriteInt( portal );
1012                 session->writeDemo->WriteInt( blockTypes );
1013         }
1014 }
1015
1016 /*
1017 ==============
1018 GetPortalState
1019 ==============
1020 */
1021 int             idRenderWorldLocal::GetPortalState( qhandle_t portal ) {
1022         if ( portal == 0 ) {
1023                 return 0;
1024         }
1025
1026         if ( portal < 1 || portal > numInterAreaPortals ) {
1027                 common->Error( "GetPortalState: bad portal number %i", portal );
1028         }
1029
1030         return doublePortals[portal-1].blockingBits;
1031 }
1032
1033 /*
1034 =====================
1035 idRenderWorldLocal::ShowPortals
1036
1037 Debugging tool, won't work correctly with SMP or when mirrors are present
1038 =====================
1039 */
1040 void idRenderWorldLocal::ShowPortals() {
1041         int                     i, j;
1042         portalArea_t    *area;
1043         portal_t        *p;
1044         idWinding       *w;
1045
1046         // flood out through portals, setting area viewCount
1047         for ( i = 0 ; i < numPortalAreas ; i++ ) {
1048                 area = &portalAreas[i];
1049                 if ( area->viewCount != tr.viewCount ) {
1050                         continue;
1051                 }
1052                 for ( p = area->portals ; p ; p = p->next ) {
1053                         w = p->w;
1054                         if ( !w ) {
1055                                 continue;
1056                         }
1057
1058                         if ( portalAreas[ p->intoArea ].viewCount != tr.viewCount ) {
1059                                 // red = can't see
1060                                 qglColor3f( 1, 0, 0 );
1061                         } else {
1062                                 // green = see through
1063                                 qglColor3f( 0, 1, 0 );
1064                         }
1065
1066                         qglBegin( GL_LINE_LOOP );
1067                         for ( j = 0 ; j < w->GetNumPoints() ; j++ ) {
1068                                 qglVertex3fv( (*w)[j].ToFloatPtr() );
1069                         }
1070                         qglEnd();
1071                 }
1072         }
1073 }