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