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