tools/quake3/q3map2/portals.c

   1 /* -------------------------------------------------------------------------------
   2
   3    Copyright (C) 1999-2007 id Software, Inc. and contributors.
   4    For a list of contributors, see the accompanying CONTRIBUTORS file.
   5
   6    This file is part of GtkRadiant.
   7
   8    GtkRadiant is free software; you can redistribute it and/or modify
   9    it under the terms of the GNU General Public License as published by
  10    the Free Software Foundation; either version 2 of the License, or
  11    (at your option) any later version.
  12
  13    GtkRadiant is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16    GNU General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with GtkRadiant; if not, write to the Free Software
  20    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  21
  22    ----------------------------------------------------------------------------------
  23
  24    This code has been altered significantly from its original form, to support
  25    several games based on the Quake III Arena engine, in the form of "Q3Map2."
  26
  27    ------------------------------------------------------------------------------- */
  28
  29
  30
  31 /* marker */
  32 #define PORTALS_C
  33
  34
  35
  36 /* dependencies */
  37 #include "q3map2.h"
  38
  39
  40
  41 /* ydnar: to fix broken portal windings */
  42 extern qboolean FixWinding( winding_t *w );
  43
  44
  45 int c_active_portals;
  46 int c_peak_portals;
  47 int c_boundary;
  48 int c_boundary_sides;
  49
  50 /*
  51    ===========
  52    AllocPortal
  53    ===========
  54  */
  55 portal_t *AllocPortal( void ){
  56         portal_t    *p;
  57
  58         if ( numthreads == 1 ) {
  59                 c_active_portals++;
  60         }
  61         if ( c_active_portals > c_peak_portals ) {
  62                 c_peak_portals = c_active_portals;
  63         }
  64
  65         p = safe_malloc( sizeof( portal_t ) );
  66         memset( p, 0, sizeof( portal_t ) );
  67
  68         return p;
  69 }
  70
  71 void FreePortal( portal_t *p ){
  72         if ( p->winding ) {
  73                 FreeWinding( p->winding );
  74         }
  75         if ( numthreads == 1 ) {
  76                 c_active_portals--;
  77         }
  78         free( p );
  79 }
  80
  81
  82
  83 /*
  84    PortalPassable
  85    returns true if the portal has non-opaque leafs on both sides
  86  */
  87
  88 qboolean PortalPassable( portal_t *p ){
  89         /* is this to global outside leaf? */
  90         if ( !p->onnode ) {
  91                 return qfalse;
  92         }
  93
  94         /* this should never happen */
  95         if ( p->nodes[ 0 ]->planenum != PLANENUM_LEAF ||
  96                  p->nodes[ 1 ]->planenum != PLANENUM_LEAF ) {
  97                 Error( "Portal_EntityFlood: not a leaf" );
  98         }
  99
 100         /* ydnar: added antiportal to supress portal generation for visibility blocking */
 101         if ( p->compileFlags & C_ANTIPORTAL ) {
 102                 return qfalse;
 103         }
 104
 105         /* both leaves on either side of the portal must be passable */
 106         if ( p->nodes[ 0 ]->opaque == qfalse && p->nodes[ 1 ]->opaque == qfalse ) {
 107                 return qtrue;
 108         }
 109
 110         /* otherwise this isn't a passable portal */
 111         return qfalse;
 112 }
 113
 114
 115
 116
 117 int c_tinyportals;
 118 int c_badportals;       /* ydnar */
 119
 120 /*
 121    =============
 122    AddPortalToNodes
 123    =============
 124  */
 125 void AddPortalToNodes( portal_t *p, node_t *front, node_t *back ){
 126         if ( p->nodes[0] || p->nodes[1] ) {
 127                 Error( "AddPortalToNode: allready included" );
 128         }
 129
 130         p->nodes[0] = front;
 131         p->next[0] = front->portals;
 132         front->portals = p;
 133
 134         p->nodes[1] = back;
 135         p->next[1] = back->portals;
 136         back->portals = p;
 137 }
 138
 139
 140 /*
 141    =============
 142    RemovePortalFromNode
 143    =============
 144  */
 145 void RemovePortalFromNode( portal_t *portal, node_t *l ){
 146         portal_t    **pp, *t;
 147
 148 // remove reference to the current portal
 149         pp = &l->portals;
 150         while ( 1 )
 151         {
 152                 t = *pp;
 153                 if ( !t ) {
 154                         Error( "RemovePortalFromNode: portal not in leaf" );
 155                 }
 156
 157                 if ( t == portal ) {
 158                         break;
 159                 }
 160
 161                 if ( t->nodes[0] == l ) {
 162                         pp = &t->next[0];
 163                 }
 164                 else if ( t->nodes[1] == l ) {
 165                         pp = &t->next[1];
 166                 }
 167                 else{
 168                         Error( "RemovePortalFromNode: portal not bounding leaf" );
 169                 }
 170         }
 171
 172         if ( portal->nodes[0] == l ) {
 173                 *pp = portal->next[0];
 174                 portal->nodes[0] = NULL;
 175         }
 176         else if ( portal->nodes[1] == l ) {
 177                 *pp = portal->next[1];
 178                 portal->nodes[1] = NULL;
 179         }
 180 }
 181
 182 //============================================================================
 183
 184 void PrintPortal( portal_t *p ){
 185         int i;
 186         winding_t   *w;
 187
 188         w = p->winding;
 189         for ( i = 0 ; i < w->numpoints ; i++ )
 190                 Sys_Printf( "(%5.0f,%5.0f,%5.0f)\n",w->p[i][0]
 191                                         , w->p[i][1], w->p[i][2] );
 192 }
 193
 194 /*
 195    ================
 196    MakeHeadnodePortals
 197
 198    The created portals will face the global outside_node
 199    ================
 200  */
 201 #define SIDESPACE   8
 202 void MakeHeadnodePortals( tree_t *tree ){
 203         vec3_t bounds[2];
 204         int i, j, n;
 205         portal_t    *p, *portals[6];
 206         plane_t bplanes[6], *pl;
 207         node_t *node;
 208
 209         node = tree->headnode;
 210
 211 // pad with some space so there will never be null volume leafs
 212         for ( i = 0 ; i < 3 ; i++ )
 213         {
 214                 bounds[0][i] = tree->mins[i] - SIDESPACE;
 215                 bounds[1][i] = tree->maxs[i] + SIDESPACE;
 216                 if ( bounds[0][i] >= bounds[1][i] ) {
 217                         Error( "Backwards tree volume" );
 218                 }
 219         }
 220
 221         tree->outside_node.planenum = PLANENUM_LEAF;
 222         tree->outside_node.brushlist = NULL;
 223         tree->outside_node.portals = NULL;
 224         tree->outside_node.opaque = qfalse;
 225
 226         for ( i = 0 ; i < 3 ; i++ )
 227                 for ( j = 0 ; j < 2 ; j++ )
 228                 {
 229                         n = j * 3 + i;
 230
 231                         p = AllocPortal();
 232                         portals[n] = p;
 233
 234                         pl = &bplanes[n];
 235                         memset( pl, 0, sizeof( *pl ) );
 236                         if ( j ) {
 237                                 pl->normal[i] = -1;
 238                                 pl->dist = -bounds[j][i];
 239                         }
 240                         else
 241                         {
 242                                 pl->normal[i] = 1;
 243                                 pl->dist = bounds[j][i];
 244                         }
 245                         p->plane = *pl;
 246                         p->winding = BaseWindingForPlane( pl->normal, pl->dist );
 247                         AddPortalToNodes( p, node, &tree->outside_node );
 248                 }
 249
 250 // clip the basewindings by all the other planes
 251         for ( i = 0 ; i < 6 ; i++ )
 252         {
 253                 for ( j = 0 ; j < 6 ; j++ )
 254                 {
 255                         if ( j == i ) {
 256                                 continue;
 257                         }
 258                         ChopWindingInPlace( &portals[i]->winding, bplanes[j].normal, bplanes[j].dist, ON_EPSILON );
 259                 }
 260         }
 261 }
 262
 263 //===================================================
 264
 265
 266 /*
 267    ================
 268    BaseWindingForNode
 269    ================
 270  */
 271 #define BASE_WINDING_EPSILON    0.001
 272 #define SPLIT_WINDING_EPSILON   0.001
 273
 274 winding_t   *BaseWindingForNode( node_t *node ){
 275         winding_t   *w;
 276         node_t      *n;
 277         plane_t     *plane;
 278         vec3_t normal;
 279         vec_t dist;
 280
 281         w = BaseWindingForPlane( mapplanes[node->planenum].normal
 282                                                          , mapplanes[node->planenum].dist );
 283
 284         // clip by all the parents
 285         for ( n = node->parent ; n && w ; )
 286         {
 287                 plane = &mapplanes[n->planenum];
 288
 289                 if ( n->children[0] == node ) { // take front
 290                         ChopWindingInPlace( &w, plane->normal, plane->dist, BASE_WINDING_EPSILON );
 291                 }
 292                 else
 293                 {   // take back
 294                         VectorSubtract( vec3_origin, plane->normal, normal );
 295                         dist = -plane->dist;
 296                         ChopWindingInPlace( &w, normal, dist, BASE_WINDING_EPSILON );
 297                 }
 298                 node = n;
 299                 n = n->parent;
 300         }
 301
 302         return w;
 303 }
 304
 305 //============================================================
 306
 307 /*
 308    ==================
 309    MakeNodePortal
 310
 311    create the new portal by taking the full plane winding for the cutting plane
 312    and clipping it by all of parents of this node
 313    ==================
 314  */
 315 void MakeNodePortal( node_t *node ){
 316         portal_t    *new_portal, *p;
 317         winding_t   *w;
 318         vec3_t normal;
 319         float dist;
 320         int side;
 321
 322         w = BaseWindingForNode( node );
 323
 324         // clip the portal by all the other portals in the node
 325         for ( p = node->portals ; p && w; p = p->next[side] )
 326         {
 327                 if ( p->nodes[0] == node ) {
 328                         side = 0;
 329                         VectorCopy( p->plane.normal, normal );
 330                         dist = p->plane.dist;
 331                 }
 332                 else if ( p->nodes[1] == node ) {
 333                         side = 1;
 334                         VectorSubtract( vec3_origin, p->plane.normal, normal );
 335                         dist = -p->plane.dist;
 336                 }
 337                 else{
 338                         Error( "CutNodePortals_r: mislinked portal" );
 339                 }
 340
 341                 ChopWindingInPlace( &w, normal, dist, CLIP_EPSILON );
 342         }
 343
 344         if ( !w ) {
 345                 return;
 346         }
 347
 348
 349         /* ydnar: adding this here to fix degenerate windings */
 350         #if 0
 351         if ( FixWinding( w ) == qfalse ) {
 352                 c_badportals++;
 353                 FreeWinding( w );
 354                 return;
 355         }
 356         #endif
 357
 358         if ( WindingIsTiny( w ) ) {
 359                 c_tinyportals++;
 360                 FreeWinding( w );
 361                 return;
 362         }
 363
 364         new_portal = AllocPortal();
 365         new_portal->plane = mapplanes[node->planenum];
 366         new_portal->onnode = node;
 367         new_portal->winding = w;
 368         new_portal->compileFlags = node->compileFlags;
 369         AddPortalToNodes( new_portal, node->children[0], node->children[1] );
 370 }
 371
 372
 373 /*
 374    ==============
 375    SplitNodePortals
 376
 377    Move or split the portals that bound node so that the node's
 378    children have portals instead of node.
 379    ==============
 380  */
 381 void SplitNodePortals( node_t *node ){
 382         portal_t    *p, *next_portal, *new_portal;
 383         node_t      *f, *b, *other_node;
 384         int side;
 385         plane_t     *plane;
 386         winding_t   *frontwinding, *backwinding;
 387
 388         plane = &mapplanes[node->planenum];
 389         f = node->children[0];
 390         b = node->children[1];
 391
 392         for ( p = node->portals ; p ; p = next_portal )
 393         {
 394                 if ( p->nodes[0] == node ) {
 395                         side = 0;
 396                 }
 397                 else if ( p->nodes[1] == node ) {
 398                         side = 1;
 399                 }
 400                 else{
 401                         Error( "SplitNodePortals: mislinked portal" );
 402                 }
 403                 next_portal = p->next[side];
 404
 405                 other_node = p->nodes[!side];
 406                 RemovePortalFromNode( p, p->nodes[0] );
 407                 RemovePortalFromNode( p, p->nodes[1] );
 408
 409 //
 410 // cut the portal into two portals, one on each side of the cut plane
 411 //
 412                 /* not strict, we want to always keep one of them even if coplanar */
 413                 ClipWindingEpsilon( p->winding, plane->normal, plane->dist,
 414                                                         SPLIT_WINDING_EPSILON, &frontwinding, &backwinding );
 415
 416                 if ( frontwinding && WindingIsTiny( frontwinding ) ) {
 417                         if ( !f->tinyportals ) {
 418                                 VectorCopy( frontwinding->p[0], f->referencepoint );
 419                         }
 420                         f->tinyportals++;
 421                         if ( !other_node->tinyportals ) {
 422                                 VectorCopy( frontwinding->p[0], other_node->referencepoint );
 423                         }
 424                         other_node->tinyportals++;
 425
 426                         FreeWinding( frontwinding );
 427                         frontwinding = NULL;
 428                         c_tinyportals++;
 429                 }
 430
 431                 if ( backwinding && WindingIsTiny( backwinding ) ) {
 432                         if ( !b->tinyportals ) {
 433                                 VectorCopy( backwinding->p[0], b->referencepoint );
 434                         }
 435                         b->tinyportals++;
 436                         if ( !other_node->tinyportals ) {
 437                                 VectorCopy( backwinding->p[0], other_node->referencepoint );
 438                         }
 439                         other_node->tinyportals++;
 440
 441                         FreeWinding( backwinding );
 442                         backwinding = NULL;
 443                         c_tinyportals++;
 444                 }
 445
 446                 if ( !frontwinding && !backwinding ) { // tiny windings on both sides
 447                         continue;
 448                 }
 449
 450                 if ( !frontwinding ) {
 451                         FreeWinding( backwinding );
 452                         if ( side == 0 ) {
 453                                 AddPortalToNodes( p, b, other_node );
 454                         }
 455                         else{
 456                                 AddPortalToNodes( p, other_node, b );
 457                         }
 458                         continue;
 459                 }
 460                 if ( !backwinding ) {
 461                         FreeWinding( frontwinding );
 462                         if ( side == 0 ) {
 463                                 AddPortalToNodes( p, f, other_node );
 464                         }
 465                         else{
 466                                 AddPortalToNodes( p, other_node, f );
 467                         }
 468                         continue;
 469                 }
 470
 471                 // the winding is split
 472                 new_portal = AllocPortal();
 473                 *new_portal = *p;
 474                 new_portal->winding = backwinding;
 475                 FreeWinding( p->winding );
 476                 p->winding = frontwinding;
 477
 478                 if ( side == 0 ) {
 479                         AddPortalToNodes( p, f, other_node );
 480                         AddPortalToNodes( new_portal, b, other_node );
 481                 }
 482                 else
 483                 {
 484                         AddPortalToNodes( p, other_node, f );
 485                         AddPortalToNodes( new_portal, other_node, b );
 486                 }
 487         }
 488
 489         node->portals = NULL;
 490 }
 491
 492
 493 /*
 494    ================
 495    CalcNodeBounds
 496    ================
 497  */
 498 void CalcNodeBounds( node_t *node ){
 499         portal_t    *p;
 500         int s;
 501         int i;
 502
 503         // calc mins/maxs for both leafs and nodes
 504         ClearBounds( node->mins, node->maxs );
 505         for ( p = node->portals ; p ; p = p->next[s] )
 506         {
 507                 s = ( p->nodes[1] == node );
 508                 for ( i = 0 ; i < p->winding->numpoints ; i++ )
 509                         AddPointToBounds( p->winding->p[i], node->mins, node->maxs );
 510         }
 511 }
 512
 513 /*
 514    ==================
 515    MakeTreePortals_r
 516    ==================
 517  */
 518 void MakeTreePortals_r( node_t *node ){
 519         int i;
 520
 521         CalcNodeBounds( node );
 522         if ( node->mins[0] >= node->maxs[0] ) {
 523                 Sys_FPrintf( SYS_WRN, "WARNING: node without a volume\n" );
 524                 Sys_Printf( "node has %d tiny portals\n", node->tinyportals );
 525                 Sys_Printf( "node reference point %1.2f %1.2f %1.2f\n", node->referencepoint[0],
 526                                         node->referencepoint[1],
 527                                         node->referencepoint[2] );
 528         }
 529
 530         for ( i = 0 ; i < 3 ; i++ )
 531         {
 532                 if ( node->mins[i] < MIN_WORLD_COORD || node->maxs[i] > MAX_WORLD_COORD ) {
 533                         if ( node->portals && node->portals->winding ) {
 534                                 xml_Winding( "WARNING: Node With Unbounded Volume", node->portals->winding->p, node->portals->winding->numpoints, qfalse );
 535                         }
 536
 537                         break;
 538                 }
 539         }
 540         if ( node->planenum == PLANENUM_LEAF ) {
 541                 return;
 542         }
 543
 544         MakeNodePortal( node );
 545         SplitNodePortals( node );
 546
 547         MakeTreePortals_r( node->children[0] );
 548         MakeTreePortals_r( node->children[1] );
 549 }
 550
 551 /*
 552    ==================
 553    MakeTreePortals
 554    ==================
 555  */
 556 void MakeTreePortals( tree_t *tree ){
 557         Sys_FPrintf( SYS_VRB, "--- MakeTreePortals ---\n" );
 558         MakeHeadnodePortals( tree );
 559         MakeTreePortals_r( tree->headnode );
 560         Sys_FPrintf( SYS_VRB, "%9d tiny portals\n", c_tinyportals );
 561         Sys_FPrintf( SYS_VRB, "%9d bad portals\n", c_badportals );  /* ydnar */
 562 }
 563
 564 /*
 565    =========================================================
 566
 567    FLOOD ENTITIES
 568
 569    =========================================================
 570  */
 571
 572 int c_floodedleafs;
 573
 574 /*
 575    =============
 576    FloodPortals_r
 577    =============
 578  */
 579
 580 void FloodPortals_r( node_t *node, int dist, qboolean skybox ){
 581         int s;
 582         portal_t    *p;
 583
 584
 585         if ( skybox ) {
 586                 node->skybox = skybox;
 587         }
 588
 589         if ( node->opaque ) {
 590                 return;
 591         }
 592
 593         if ( node->occupied ) {
 594                 if ( node->occupied > dist ) {
 595                         /* reduce distance! */
 596                         /* for better leak line */
 597                         /* note: node->occupied will also be true for all further nodes, then */
 598                         node->occupied = dist;
 599                         for ( p = node->portals; p; p = p->next[ s ] )
 600                         {
 601                                 s = ( p->nodes[ 1 ] == node );
 602                                 FloodPortals_r( p->nodes[ !s ], dist + 1, skybox );
 603                         }
 604                 }
 605                 return;
 606         }
 607
 608         c_floodedleafs++;
 609         node->occupied = dist;
 610
 611         for ( p = node->portals; p; p = p->next[ s ] )
 612         {
 613                 s = ( p->nodes[ 1 ] == node );
 614                 FloodPortals_r( p->nodes[ !s ], dist + 1, skybox );
 615         }
 616 }
 617
 618
 619
 620 /*
 621    =============
 622    PlaceOccupant
 623    =============
 624  */
 625
 626 qboolean PlaceOccupant( node_t *headnode, vec3_t origin, entity_t *occupant, qboolean skybox ){
 627         vec_t d;
 628         node_t  *node;
 629         plane_t *plane;
 630
 631
 632         // find the leaf to start in
 633         node = headnode;
 634         while ( node->planenum != PLANENUM_LEAF )
 635         {
 636                 plane = &mapplanes[ node->planenum ];
 637                 d = DotProduct( origin, plane->normal ) - plane->dist;
 638                 if ( d >= 0 ) {
 639                         node = node->children[ 0 ];
 640                 }
 641                 else{
 642                         node = node->children[ 1 ];
 643                 }
 644         }
 645
 646         if ( node->opaque ) {
 647                 return qfalse;
 648         }
 649         node->occupant = occupant;
 650         node->skybox = skybox;
 651
 652         FloodPortals_r( node, 1, skybox );
 653
 654         return qtrue;
 655 }
 656
 657 /*
 658    =============
 659    FloodEntities
 660
 661    Marks all nodes that can be reached by entites
 662    =============
 663  */
 664
 665 int FloodEntities( tree_t *tree ){
 666         int i, s;
 667         vec3_t origin, offset, scale, angles;
 668         qboolean r, inside, skybox, found;
 669         node_t      *headnode;
 670         entity_t    *e, *tripped;
 671         const char  *value;
 672         int tripcount = 0;
 673
 674
 675         headnode = tree->headnode;
 676         Sys_FPrintf( SYS_VRB,"--- FloodEntities ---\n" );
 677         inside = qfalse;
 678         tree->outside_node.occupied = 0;
 679
 680         tripped = NULL;
 681         c_floodedleafs = 0;
 682         for ( i = 1; i < numEntities; i++ )
 683         {
 684                 /* get entity */
 685                 e = &entities[ i ];
 686
 687                 /* get origin */
 688                 found = GetVectorForKey( e, "origin", origin );
 689
 690                 /* as a special case, allow origin-less entities */
 691                 if ( !found ) {
 692                         continue;
 693                 }
 694
 695                 /* also allow bmodel entities outside, as they could be on a moving path that will go into the map */
 696                 if ( e->brushes != NULL || e->patches != NULL ) {
 697                         continue;
 698                 }
 699
 700                 /* handle skybox entities */
 701                 value = ValueForKey( e, "classname" );
 702                 if ( !Q_stricmp( value, "_skybox" ) ) {
 703                         skybox = qtrue;
 704                         skyboxPresent = qtrue;
 705
 706                         /* invert origin */
 707                         VectorScale( origin, -1.0f, offset );
 708
 709                         /* get scale */
 710                         VectorSet( scale, 64.0f, 64.0f, 64.0f );
 711                         value = ValueForKey( e, "_scale" );
 712                         if ( value[ 0 ] != '\0' ) {
 713                                 s = sscanf( value, "%f %f %f", &scale[ 0 ], &scale[ 1 ], &scale[ 2 ] );
 714                                 if ( s == 1 ) {
 715                                         scale[ 1 ] = scale[ 0 ];
 716                                         scale[ 2 ] = scale[ 0 ];
 717                                 }
 718                         }
 719
 720                         /* get "angle" (yaw) or "angles" (pitch yaw roll) */
 721                         VectorClear( angles );
 722                         angles[ 2 ] = FloatForKey( e, "angle" );
 723                         value = ValueForKey( e, "angles" );
 724                         if ( value[ 0 ] != '\0' ) {
 725                                 sscanf( value, "%f %f %f", &angles[ 1 ], &angles[ 2 ], &angles[ 0 ] );
 726                         }
 727
 728                         /* set transform matrix (thanks spog) */
 729                         m4x4_identity( skyboxTransform );
 730                         m4x4_pivoted_transform_by_vec3( skyboxTransform, offset, angles, eXYZ, scale, origin );
 731                 }
 732                 else{
 733                         skybox = qfalse;
 734                 }
 735
 736                 /* nudge off floor */
 737                 origin[ 2 ] += 1;
 738
 739                 /* debugging code */
 740                 //%     if( i == 1 )
 741                 //%             origin[ 2 ] += 4096;
 742
 743                 /* find leaf */
 744                 r = PlaceOccupant( headnode, origin, e, skybox );
 745                 if ( r ) {
 746                         inside = qtrue;
 747                 }
 748                 if ( !r ) {
 749                         Sys_Printf( "Entity %i, Brush %i: Entity in solid\n", e->mapEntityNum, 0 );
 750                 }
 751                 else if ( tree->outside_node.occupied ) {
 752                         if ( !tripped || tree->outside_node.occupied < tripcount ) {
 753                                 tripped = e;
 754                                 tripcount = tree->outside_node.occupied;
 755                         }
 756                 }
 757         }
 758
 759         if ( tripped ) {
 760                 xml_Select( "Entity leaked", e->mapEntityNum, 0, qfalse );
 761         }
 762
 763         Sys_FPrintf( SYS_VRB, "%9d flooded leafs\n", c_floodedleafs );
 764
 765         if ( !inside ) {
 766                 Sys_FPrintf( SYS_VRB, "no entities in open -- no filling\n" );
 767                 return FLOODENTITIES_EMPTY;
 768         }
 769         if ( tree->outside_node.occupied ) {
 770                 Sys_FPrintf( SYS_VRB, "entity reached from outside -- leak detected\n" );
 771                 return FLOODENTITIES_LEAKED;
 772         }
 773
 774         return FLOODENTITIES_GOOD;
 775 }
 776
 777 /*
 778    =========================================================
 779
 780    FLOOD AREAS
 781
 782    =========================================================
 783  */
 784
 785 int c_areas;
 786
 787
 788
 789 /*
 790    FloodAreas_r()
 791    floods through leaf portals to tag leafs with an area
 792  */
 793
 794 void FloodAreas_r( node_t *node ){
 795         int s;
 796         portal_t    *p;
 797         brush_t     *b;
 798
 799
 800         if ( node->areaportal ) {
 801                 if ( node->area == -1 ) {
 802                         node->area = c_areas;
 803                 }
 804
 805                 /* this node is part of an area portal brush */
 806                 b = node->brushlist->original;
 807
 808                 /* if the current area has already touched this portal, we are done */
 809                 if ( b->portalareas[ 0 ] == c_areas || b->portalareas[ 1 ] == c_areas ) {
 810                         return;
 811                 }
 812
 813                 // note the current area as bounding the portal
 814                 if ( b->portalareas[ 1 ] != -1 ) {
 815                         Sys_FPrintf( SYS_WRN, "WARNING: areaportal brush %i touches > 2 areas\n", b->brushNum );
 816                         return;
 817                 }
 818                 if ( b->portalareas[ 0 ] != -1 ) {
 819                         b->portalareas[ 1 ] = c_areas;
 820                 }
 821                 else{
 822                         b->portalareas[ 0 ] = c_areas;
 823                 }
 824
 825                 return;
 826         }
 827
 828         if ( node->area != -1 ) {
 829                 return;
 830         }
 831         if ( node->cluster == -1 ) {
 832                 return;
 833         }
 834
 835         node->area = c_areas;
 836
 837         /* ydnar: skybox nodes set the skybox area */
 838         if ( node->skybox ) {
 839                 skyboxArea = c_areas;
 840         }
 841
 842         for ( p = node->portals; p; p = p->next[ s ] )
 843         {
 844                 s = ( p->nodes[1] == node );
 845
 846                 /* ydnar: allow areaportal portals to block area flow */
 847                 if ( p->compileFlags & C_AREAPORTAL ) {
 848                         continue;
 849                 }
 850
 851                 if ( !PortalPassable( p ) ) {
 852                         continue;
 853                 }
 854
 855                 FloodAreas_r( p->nodes[ !s ] );
 856         }
 857 }
 858
 859 /*
 860    =============
 861    FindAreas_r
 862
 863    Just decend the tree, and for each node that hasn't had an
 864    area set, flood fill out from there
 865    =============
 866  */
 867 void FindAreas_r( node_t *node ){
 868         if ( node->planenum != PLANENUM_LEAF ) {
 869                 FindAreas_r( node->children[ 0 ] );
 870                 FindAreas_r( node->children[ 1 ] );
 871                 return;
 872         }
 873
 874         if ( node->opaque || node->areaportal || node->area != -1 ) {
 875                 return;
 876         }
 877
 878         FloodAreas_r( node );
 879         c_areas++;
 880 }
 881
 882 /*
 883    =============
 884    CheckAreas_r
 885    =============
 886  */
 887 void CheckAreas_r( node_t *node ){
 888         brush_t *b;
 889
 890         if ( node->planenum != PLANENUM_LEAF ) {
 891                 CheckAreas_r( node->children[0] );
 892                 CheckAreas_r( node->children[1] );
 893                 return;
 894         }
 895
 896         if ( node->opaque ) {
 897                 return;
 898         }
 899
 900         if ( node->cluster != -1 ) {
 901                 if ( node->area == -1 ) {
 902                         Sys_FPrintf( SYS_WRN, "WARNING: cluster %d has area set to -1\n", node->cluster );
 903                 }
 904         }
 905         if ( node->areaportal ) {
 906                 b = node->brushlist->original;
 907
 908                 // check if the areaportal touches two areas
 909                 if ( b->portalareas[0] == -1 || b->portalareas[1] == -1 ) {
 910                         Sys_FPrintf( SYS_WRN, "WARNING: areaportal brush %i doesn't touch two areas\n", b->brushNum );
 911                 }
 912         }
 913 }
 914
 915
 916
 917 /*
 918    FloodSkyboxArea_r() - ydnar
 919    sets all nodes with the skybox area to skybox
 920  */
 921
 922 void FloodSkyboxArea_r( node_t *node ){
 923         if ( skyboxArea < 0 ) {
 924                 return;
 925         }
 926
 927         if ( node->planenum != PLANENUM_LEAF ) {
 928                 FloodSkyboxArea_r( node->children[ 0 ] );
 929                 FloodSkyboxArea_r( node->children[ 1 ] );
 930                 return;
 931         }
 932
 933         if ( node->opaque || node->area != skyboxArea ) {
 934                 return;
 935         }
 936
 937         node->skybox = qtrue;
 938 }
 939
 940
 941
 942 /*
 943    FloodAreas()
 944    mark each leaf with an area, bounded by C_AREAPORTAL
 945  */
 946
 947 void FloodAreas( tree_t *tree ){
 948         Sys_FPrintf( SYS_VRB,"--- FloodAreas ---\n" );
 949         FindAreas_r( tree->headnode );
 950
 951         /* ydnar: flood all skybox nodes */
 952         FloodSkyboxArea_r( tree->headnode );
 953
 954         /* check for areaportal brushes that don't touch two areas */
 955         /* ydnar: fix this rather than just silence the warnings */
 956         //%     CheckAreas_r( tree->headnode );
 957
 958         Sys_FPrintf( SYS_VRB, "%9d areas\n", c_areas );
 959 }
 960
 961
 962
 963 //======================================================
 964
 965 int c_outside;
 966 int c_inside;
 967 int c_solid;
 968
 969 void FillOutside_r( node_t *node ){
 970         if ( node->planenum != PLANENUM_LEAF ) {
 971                 FillOutside_r( node->children[0] );
 972                 FillOutside_r( node->children[1] );
 973                 return;
 974         }
 975
 976         // anything not reachable by an entity
 977         // can be filled away
 978         if ( !node->occupied ) {
 979                 if ( !node->opaque ) {
 980                         c_outside++;
 981                         node->opaque = qtrue;
 982                 }
 983                 else {
 984                         c_solid++;
 985                 }
 986         }
 987         else {
 988                 c_inside++;
 989         }
 990
 991 }
 992
 993 /*
 994    =============
 995    FillOutside
 996
 997    Fill all nodes that can't be reached by entities
 998    =============
 999  */
1000 void FillOutside( node_t *headnode ){
1001         c_outside = 0;
1002         c_inside = 0;
1003         c_solid = 0;
1004         Sys_FPrintf( SYS_VRB,"--- FillOutside ---\n" );
1005         FillOutside_r( headnode );
1006         Sys_FPrintf( SYS_VRB,"%9d solid leafs\n", c_solid );
1007         Sys_Printf( "%9d leafs filled\n", c_outside );
1008         Sys_FPrintf( SYS_VRB, "%9d inside leafs\n", c_inside );
1009 }
1010
1011
1012 //==============================================================