neo/tools/compilers/dmap/portals.cpp

   1 /*
   2 ===========================================================================
   3
   4 Doom 3 GPL Source Code
   5 Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company.
   6
   7 This file is part of the Doom 3 GPL Source Code (?Doom 3 Source Code?).
   8
   9 Doom 3 Source Code is free software: you can redistribute it and/or modify
  10 it under the terms of the GNU General Public License as published by
  11 the Free Software Foundation, either version 3 of the License, or
  12 (at your option) any later version.
  13
  14 Doom 3 Source Code is distributed in the hope that it will be useful,
  15 but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17 GNU General Public License for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with Doom 3 Source Code.  If not, see <http://www.gnu.org/licenses/>.
  21
  22 In addition, the Doom 3 Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the Doom 3 Source Code.  If not, please request a copy in writing from id Software at the address below.
  23
  24 If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.
  25
  26 ===========================================================================
  27 */
  28
  29 #include "../../../idlib/precompiled.h"
  30 #pragma hdrstop
  31
  32 #include "dmap.h"
  33
  34
  35 interAreaPortal_t interAreaPortals[MAX_INTER_AREA_PORTALS];
  36 int                                     numInterAreaPortals;
  37
  38
  39 int             c_active_portals;
  40 int             c_peak_portals;
  41
  42 /*
  43 ===========
  44 AllocPortal
  45 ===========
  46 */
  47 uPortal_t       *AllocPortal (void)
  48 {
  49         uPortal_t       *p;
  50
  51         c_active_portals++;
  52         if (c_active_portals > c_peak_portals)
  53                 c_peak_portals = c_active_portals;
  54
  55         p = (uPortal_t *)Mem_Alloc (sizeof(uPortal_t ));
  56         memset (p, 0, sizeof(uPortal_t ));
  57
  58         return p;
  59 }
  60
  61
  62 void FreePortal (uPortal_t  *p)
  63 {
  64         if (p->winding)
  65                 delete p->winding;
  66         c_active_portals--;
  67         Mem_Free (p);
  68 }
  69
  70 //==============================================================
  71
  72 /*
  73 =============
  74 Portal_Passable
  75
  76 Returns true if the portal has non-opaque leafs on both sides
  77 =============
  78 */
  79 static bool Portal_Passable( uPortal_t  *p ) {
  80         if (!p->onnode) {
  81                 return false;   // to global outsideleaf
  82         }
  83
  84         if (p->nodes[0]->planenum != PLANENUM_LEAF
  85                 || p->nodes[1]->planenum != PLANENUM_LEAF) {
  86                 common->Error( "Portal_EntityFlood: not a leaf");
  87         }
  88
  89         if ( !p->nodes[0]->opaque && !p->nodes[1]->opaque ) {
  90                 return true;
  91         }
  92
  93         return false;
  94 }
  95
  96
  97 //=============================================================================
  98
  99 int             c_tinyportals;
 100
 101 /*
 102 =============
 103 AddPortalToNodes
 104 =============
 105 */
 106 void AddPortalToNodes (uPortal_t  *p, node_t *front, node_t *back) {
 107         if (p->nodes[0] || p->nodes[1]) {
 108                 common->Error( "AddPortalToNode: allready included");
 109         }
 110
 111         p->nodes[0] = front;
 112         p->next[0] = front->portals;
 113         front->portals = p;
 114
 115         p->nodes[1] = back;
 116         p->next[1] = back->portals;
 117         back->portals = p;
 118 }
 119
 120
 121 /*
 122 =============
 123 RemovePortalFromNode
 124 =============
 125 */
 126 void RemovePortalFromNode (uPortal_t  *portal, node_t *l)
 127 {
 128         uPortal_t       **pp, *t;
 129
 130 // remove reference to the current portal
 131         pp = &l->portals;
 132         while (1)
 133         {
 134                 t = *pp;
 135                 if (!t)
 136                         common->Error( "RemovePortalFromNode: portal not in leaf");
 137
 138                 if ( t == portal )
 139                         break;
 140
 141                 if (t->nodes[0] == l)
 142                         pp = &t->next[0];
 143                 else if (t->nodes[1] == l)
 144                         pp = &t->next[1];
 145                 else
 146                         common->Error( "RemovePortalFromNode: portal not bounding leaf");
 147         }
 148
 149         if ( portal->nodes[0] == l ) {
 150                 *pp = portal->next[0];
 151                 portal->nodes[0] = NULL;
 152         } else if ( portal->nodes[1] == l ) {
 153                 *pp = portal->next[1];
 154                 portal->nodes[1] = NULL;
 155         } else {
 156                 common->Error( "RemovePortalFromNode: mislinked" );
 157         }
 158 }
 159
 160 //============================================================================
 161
 162 void PrintPortal (uPortal_t *p)
 163 {
 164         int                     i;
 165         idWinding       *w;
 166
 167         w = p->winding;
 168         for ( i = 0; i < w->GetNumPoints(); i++ )
 169                 common->Printf("(%5.0f,%5.0f,%5.0f)\n",(*w)[i][0], (*w)[i][1], (*w)[i][2]);
 170 }
 171
 172 /*
 173 ================
 174 MakeHeadnodePortals
 175
 176 The created portals will face the global outside_node
 177 ================
 178 */
 179 #define SIDESPACE       8
 180 static void MakeHeadnodePortals( tree_t *tree ) {
 181         idBounds        bounds;
 182         int                     i, j, n;
 183         uPortal_t       *p, *portals[6];
 184         idPlane         bplanes[6], *pl;
 185         node_t *node;
 186
 187         node = tree->headnode;
 188
 189         tree->outside_node.planenum = PLANENUM_LEAF;
 190         tree->outside_node.brushlist = NULL;
 191         tree->outside_node.portals = NULL;
 192         tree->outside_node.opaque = false;
 193
 194         // if no nodes, don't go any farther
 195         if ( node->planenum == PLANENUM_LEAF ) {
 196                 return;
 197         }
 198
 199         // pad with some space so there will never be null volume leafs
 200         for (i=0 ; i<3 ; i++) {
 201                 bounds[0][i] = tree->bounds[0][i] - SIDESPACE;
 202                 bounds[1][i] = tree->bounds[1][i] + SIDESPACE;
 203                 if ( bounds[0][i] >= bounds[1][i] ) {
 204                         common->Error( "Backwards tree volume" );
 205                 }
 206         }
 207
 208         for (i=0 ; i<3 ; i++) {
 209                 for (j=0 ; j<2 ; j++) {
 210                         n = j*3 + i;
 211
 212                         p = AllocPortal ();
 213                         portals[n] = p;
 214
 215                         pl = &bplanes[n];
 216                         memset (pl, 0, sizeof(*pl));
 217                         if (j) {
 218                                 (*pl)[i] = -1;
 219                                 (*pl)[3] = bounds[j][i];
 220                         } else {
 221                                 (*pl)[i] = 1;
 222                                 (*pl)[3] = -bounds[j][i];
 223                         }
 224                         p->plane = *pl;
 225                         p->winding = new idWinding( *pl );
 226                         AddPortalToNodes (p, node, &tree->outside_node);
 227                 }
 228         }
 229
 230         // clip the basewindings by all the other planes
 231         for (i=0 ; i<6 ; i++) {
 232                 for (j=0 ; j<6 ; j++) {
 233                         if (j == i) {
 234                                 continue;
 235                         }
 236                         portals[i]->winding = portals[i]->winding->Clip( bplanes[j], ON_EPSILON );
 237                 }
 238         }
 239 }
 240
 241 //===================================================
 242
 243
 244 /*
 245 ================
 246 BaseWindingForNode
 247 ================
 248 */
 249 #define BASE_WINDING_EPSILON    0.001f
 250 #define SPLIT_WINDING_EPSILON   0.001f
 251
 252 idWinding *BaseWindingForNode (node_t *node) {
 253         idWinding       *w;
 254         node_t          *n;
 255
 256         w = new idWinding( dmapGlobals.mapPlanes[node->planenum] );
 257
 258         // clip by all the parents
 259         for ( n = node->parent ; n && w ; ) {
 260                 idPlane &plane = dmapGlobals.mapPlanes[n->planenum];
 261
 262                 if ( n->children[0] == node ) {
 263                         // take front
 264                         w = w->Clip( plane, BASE_WINDING_EPSILON );
 265                 } else {
 266                         // take back
 267                         idPlane back = -plane;
 268                         w = w->Clip( back, BASE_WINDING_EPSILON );
 269                 }
 270                 node = n;
 271                 n = n->parent;
 272         }
 273
 274         return w;
 275 }
 276
 277 //============================================================
 278
 279 /*
 280 ==================
 281 MakeNodePortal
 282
 283 create the new portal by taking the full plane winding for the cutting plane
 284 and clipping it by all of parents of this node
 285 ==================
 286 */
 287 static void MakeNodePortal( node_t *node ) {
 288         uPortal_t       *new_portal, *p;
 289         idWinding       *w;
 290         idVec3          normal;
 291         int                     side;
 292
 293         w = BaseWindingForNode (node);
 294
 295         // clip the portal by all the other portals in the node
 296         for (p = node->portals ; p && w; p = p->next[side])
 297         {
 298                 idPlane plane;
 299
 300                 if (p->nodes[0] == node)
 301                 {
 302                         side = 0;
 303                         plane = p->plane;
 304                 }
 305                 else if (p->nodes[1] == node)
 306                 {
 307                         side = 1;
 308                         plane = -p->plane;
 309                 }
 310                 else {
 311                         common->Error( "CutNodePortals_r: mislinked portal");
 312                         side = 0;       // quiet a compiler warning
 313                 }
 314
 315                 w = w->Clip( plane, CLIP_EPSILON );
 316         }
 317
 318         if (!w)
 319         {
 320                 return;
 321         }
 322
 323         if ( w->IsTiny() )
 324         {
 325                 c_tinyportals++;
 326                 delete w;
 327                 return;
 328         }
 329
 330
 331         new_portal = AllocPortal ();
 332         new_portal->plane = dmapGlobals.mapPlanes[node->planenum];
 333         new_portal->onnode = node;
 334         new_portal->winding = w;
 335         AddPortalToNodes (new_portal, node->children[0], node->children[1]);
 336 }
 337
 338
 339 /*
 340 ==============
 341 SplitNodePortals
 342
 343 Move or split the portals that bound node so that the node's
 344 children have portals instead of node.
 345 ==============
 346 */
 347 static void SplitNodePortals( node_t *node ) {
 348         uPortal_t       *p, *next_portal, *new_portal;
 349         node_t          *f, *b, *other_node;
 350         int                     side;
 351         idPlane         *plane;
 352         idWinding       *frontwinding, *backwinding;
 353
 354         plane = &dmapGlobals.mapPlanes[node->planenum];
 355         f = node->children[0];
 356         b = node->children[1];
 357
 358         for ( p = node->portals ; p ; p = next_portal ) {
 359                 if (p->nodes[0] == node ) {
 360                         side = 0;
 361                 } else if ( p->nodes[1] == node ) {
 362                         side = 1;
 363                 } else {
 364                         common->Error( "SplitNodePortals: mislinked portal" );
 365                         side = 0;       // quiet a compiler warning
 366                 }
 367                 next_portal = p->next[side];
 368
 369                 other_node = p->nodes[!side];
 370                 RemovePortalFromNode (p, p->nodes[0]);
 371                 RemovePortalFromNode (p, p->nodes[1]);
 372
 373         //
 374         // cut the portal into two portals, one on each side of the cut plane
 375         //
 376                 p->winding->Split( *plane, SPLIT_WINDING_EPSILON, &frontwinding, &backwinding);
 377
 378                 if ( frontwinding && frontwinding->IsTiny() )
 379                 {
 380                         delete frontwinding;
 381                         frontwinding = NULL;
 382                         c_tinyportals++;
 383                 }
 384
 385                 if ( backwinding && backwinding->IsTiny() )
 386                 {
 387                         delete backwinding;
 388                         backwinding = NULL;
 389                         c_tinyportals++;
 390                 }
 391
 392                 if ( !frontwinding && !backwinding )
 393                 {       // tiny windings on both sides
 394                         continue;
 395                 }
 396
 397                 if (!frontwinding)
 398                 {
 399                         delete backwinding;
 400                         if (side == 0)
 401                                 AddPortalToNodes (p, b, other_node);
 402                         else
 403                                 AddPortalToNodes (p, other_node, b);
 404                         continue;
 405                 }
 406                 if (!backwinding)
 407                 {
 408                         delete frontwinding;
 409                         if (side == 0)
 410                                 AddPortalToNodes (p, f, other_node);
 411                         else
 412                                 AddPortalToNodes (p, other_node, f);
 413                         continue;
 414                 }
 415
 416         // the winding is split
 417                 new_portal = AllocPortal ();
 418                 *new_portal = *p;
 419                 new_portal->winding = backwinding;
 420                 delete p->winding;
 421                 p->winding = frontwinding;
 422
 423                 if (side == 0)
 424                 {
 425                         AddPortalToNodes (p, f, other_node);
 426                         AddPortalToNodes (new_portal, b, other_node);
 427                 }
 428                 else
 429                 {
 430                         AddPortalToNodes (p, other_node, f);
 431                         AddPortalToNodes (new_portal, other_node, b);
 432                 }
 433         }
 434
 435         node->portals = NULL;
 436 }
 437
 438
 439 /*
 440 ================
 441 CalcNodeBounds
 442 ================
 443 */
 444 void CalcNodeBounds (node_t *node)
 445 {
 446         uPortal_t       *p;
 447         int                     s;
 448         int                     i;
 449
 450         // calc mins/maxs for both leafs and nodes
 451         node->bounds.Clear();
 452         for (p = node->portals ; p ; p = p->next[s]) {
 453                 s = (p->nodes[1] == node);
 454                 for ( i = 0; i < p->winding->GetNumPoints(); i++ ) {
 455                         node->bounds.AddPoint( (*p->winding)[i].ToVec3() );
 456                 }
 457         }
 458 }
 459
 460
 461 /*
 462 ==================
 463 MakeTreePortals_r
 464 ==================
 465 */
 466 void MakeTreePortals_r (node_t *node)
 467 {
 468         int             i;
 469
 470         CalcNodeBounds( node );
 471
 472         if ( node->bounds[0][0] >= node->bounds[1][0]) {
 473                 common->Warning( "node without a volume" );
 474         }
 475
 476         for ( i = 0; i < 3; i++ ) {
 477                 if ( node->bounds[0][i] < MIN_WORLD_COORD || node->bounds[1][i] > MAX_WORLD_COORD ) {
 478                         common->Warning( "node with unbounded volume");
 479                         break;
 480                 }
 481         }
 482         if ( node->planenum == PLANENUM_LEAF ) {
 483                 return;
 484         }
 485
 486         MakeNodePortal (node);
 487         SplitNodePortals (node);
 488
 489         MakeTreePortals_r (node->children[0]);
 490         MakeTreePortals_r (node->children[1]);
 491 }
 492
 493 /*
 494 ==================
 495 MakeTreePortals
 496 ==================
 497 */
 498 void MakeTreePortals (tree_t *tree)
 499 {
 500         common->Printf( "----- MakeTreePortals -----\n");
 501         MakeHeadnodePortals (tree);
 502         MakeTreePortals_r (tree->headnode);
 503 }
 504
 505 /*
 506 =========================================================
 507
 508 FLOOD ENTITIES
 509
 510 =========================================================
 511 */
 512
 513 int             c_floodedleafs;
 514
 515 /*
 516 =============
 517 FloodPortals_r
 518 =============
 519 */
 520 void FloodPortals_r (node_t *node, int dist) {
 521         uPortal_t       *p;
 522         int                     s;
 523
 524         if ( node->occupied ) {
 525                 return;
 526         }
 527
 528         if ( node->opaque ) {
 529                 return;
 530         }
 531
 532         c_floodedleafs++;
 533         node->occupied = dist;
 534
 535         for (p=node->portals ; p ; p = p->next[s]) {
 536                 s = (p->nodes[1] == node);
 537                 FloodPortals_r (p->nodes[!s], dist+1);
 538         }
 539 }
 540
 541 /*
 542 =============
 543 PlaceOccupant
 544 =============
 545 */
 546 bool PlaceOccupant( node_t *headnode, idVec3 origin, uEntity_t *occupant ) {
 547         node_t  *node;
 548         float   d;
 549         idPlane *plane;
 550
 551         // find the leaf to start in
 552         node = headnode;
 553         while ( node->planenum != PLANENUM_LEAF ) {
 554                 plane = &dmapGlobals.mapPlanes[node->planenum];
 555                 d = plane->Distance( origin );
 556                 if ( d >= 0.0f ) {
 557                         node = node->children[0];
 558                 } else {
 559                         node = node->children[1];
 560                 }
 561         }
 562
 563         if ( node->opaque ) {
 564                 return false;
 565         }
 566         node->occupant = occupant;
 567
 568         FloodPortals_r (node, 1);
 569
 570         return true;
 571 }
 572
 573 /*
 574 =============
 575 FloodEntities
 576
 577 Marks all nodes that can be reached by entites
 578 =============
 579 */
 580 bool FloodEntities( tree_t *tree ) {
 581         int             i;
 582         idVec3  origin;
 583         const char      *cl;
 584         bool    inside;
 585         node_t *headnode;
 586
 587         headnode = tree->headnode;
 588         common->Printf ("--- FloodEntities ---\n");
 589         inside = false;
 590         tree->outside_node.occupied = 0;
 591
 592         c_floodedleafs = 0;
 593         bool errorShown = false;
 594         for (i=1 ; i<dmapGlobals.num_entities ; i++) {
 595                 idMapEntity     *mapEnt;
 596
 597                 mapEnt = dmapGlobals.uEntities[i].mapEntity;
 598                 if ( !mapEnt->epairs.GetVector( "origin", "", origin) ) {
 599                         continue;
 600                 }
 601
 602                 // any entity can have "noFlood" set to skip it
 603                 if ( mapEnt->epairs.GetString( "noFlood", "", &cl ) ) {
 604                         continue;
 605                 }
 606
 607                 mapEnt->epairs.GetString( "classname", "", &cl );
 608
 609                 if ( !strcmp( cl, "light" ) ) {
 610                         const char      *v;
 611
 612                         // don't place lights that have a light_start field, because they can still
 613                         // be valid if their origin is outside the world
 614                         mapEnt->epairs.GetString( "light_start", "", &v);
 615                         if ( v[0] ) {
 616                                 continue;
 617                         }
 618
 619                         // don't place fog lights, because they often
 620                         // have origins outside the light
 621                         mapEnt->epairs.GetString( "texture", "", &v);
 622                         if ( v[0] ) {
 623                                 const idMaterial *mat = declManager->FindMaterial( v );
 624                                 if ( mat->IsFogLight() ) {
 625                                         continue;
 626                                 }
 627                         }
 628                 }
 629
 630                 if (PlaceOccupant (headnode, origin, &dmapGlobals.uEntities[i])) {
 631                         inside = true;
 632                 }
 633
 634                 if (tree->outside_node.occupied && !errorShown) {
 635                         errorShown = true;
 636                         common->Printf("Leak on entity # %d\n", i);
 637                         const char *p;
 638
 639                         mapEnt->epairs.GetString( "classname", "", &p);
 640                         common->Printf("Entity classname was: %s\n", p);
 641                         mapEnt->epairs.GetString( "name", "", &p);
 642                         common->Printf("Entity name was: %s\n", p);
 643                         idVec3 origin;
 644                         if ( mapEnt->epairs.GetVector( "origin", "", origin)) {
 645                                 common->Printf("Entity origin is: %f %f %f\n\n\n", origin.x, origin.y, origin.z);
 646                         }
 647                 }
 648         }
 649
 650         common->Printf("%5i flooded leafs\n", c_floodedleafs );
 651
 652         if (!inside)
 653         {
 654                 common->Printf ("no entities in open -- no filling\n");
 655         }
 656         else if (tree->outside_node.occupied)
 657         {
 658                 common->Printf ("entity reached from outside -- no filling\n");
 659         }
 660
 661         return (bool)(inside && !tree->outside_node.occupied);
 662 }
 663
 664 /*
 665 =========================================================
 666
 667 FLOOD AREAS
 668
 669 =========================================================
 670 */
 671
 672 static  int             c_areas;
 673 static  int             c_areaFloods;
 674
 675 /*
 676 =================
 677 FindSideForPortal
 678 =================
 679 */
 680 static side_t   *FindSideForPortal( uPortal_t *p ) {
 681         int             i, j, k;
 682         node_t  *node;
 683         uBrush_t        *b, *orig;
 684         side_t  *s, *s2;
 685
 686         // scan both bordering nodes brush lists for a portal brush
 687         // that shares the plane
 688         for ( i = 0 ; i < 2 ; i++ ) {
 689                 node = p->nodes[i];
 690                 for ( b = node->brushlist ; b ; b = b->next ) {
 691                         if ( !( b->contents & CONTENTS_AREAPORTAL ) ) {
 692                                 continue;
 693                         }
 694                         orig = b->original;
 695                         for ( j = 0 ; j < orig->numsides ; j++ ) {
 696                                 s = orig->sides + j;
 697                                 if ( !s->visibleHull ) {
 698                                         continue;
 699                                 }
 700                                 if ( !( s->material->GetContentFlags() & CONTENTS_AREAPORTAL ) ) {
 701                                         continue;
 702                                 }
 703                                 if ( ( s->planenum & ~1 ) != ( p->onnode->planenum & ~1 ) ) {
 704                                         continue;
 705                                 }
 706                                 // remove the visible hull from any other portal sides of this portal brush
 707                                 for ( k = 0; k < orig->numsides; k++ ) {
 708                                         if ( k == j ) {
 709                                                 continue;
 710                                         }
 711                                         s2 = orig->sides + k;
 712                                         if ( s2->visibleHull == NULL ) {
 713                                                 continue;
 714                                         }
 715                                         if ( !( s2->material->GetContentFlags() & CONTENTS_AREAPORTAL ) ) {
 716                                                 continue;
 717                                         }
 718                                         common->Warning( "brush has multiple area portal sides at %s", s2->visibleHull->GetCenter().ToString() );
 719                                         delete s2->visibleHull;
 720                                         s2->visibleHull = NULL;
 721                                 }
 722                                 return s;
 723                         }
 724                 }
 725         }
 726         return NULL;
 727 }
 728
 729 /*
 730 =============
 731 FloodAreas_r
 732 =============
 733 */
 734 void FloodAreas_r (node_t *node)
 735 {
 736         uPortal_t       *p;
 737         int                     s;
 738
 739         if ( node->area != -1 ) {
 740                 return;         // allready got it
 741         }
 742         if ( node->opaque ) {
 743                 return;
 744         }
 745
 746         c_areaFloods++;
 747         node->area = c_areas;
 748
 749         for ( p=node->portals ; p ; p = p->next[s] ) {
 750                 node_t  *other;
 751
 752                 s = (p->nodes[1] == node);
 753                 other = p->nodes[!s];
 754
 755                 if ( !Portal_Passable(p) ) {
 756                         continue;
 757                 }
 758
 759                 // can't flood through an area portal
 760                 if ( FindSideForPortal( p ) ) {
 761                         continue;
 762                 }
 763
 764                 FloodAreas_r( other );
 765         }
 766 }
 767
 768 /*
 769 =============
 770 FindAreas_r
 771
 772 Just decend the tree, and for each node that hasn't had an
 773 area set, flood fill out from there
 774 =============
 775 */
 776 void FindAreas_r( node_t *node ) {
 777         if ( node->planenum != PLANENUM_LEAF ) {
 778                 FindAreas_r (node->children[0]);
 779                 FindAreas_r (node->children[1]);
 780                 return;
 781         }
 782
 783         if ( node->opaque ) {
 784                 return;
 785         }
 786
 787         if ( node->area != -1 ) {
 788                 return;         // allready got it
 789         }
 790
 791         c_areaFloods = 0;
 792         FloodAreas_r (node);
 793         common->Printf( "area %i has %i leafs\n", c_areas, c_areaFloods );
 794         c_areas++;
 795 }
 796
 797 /*
 798 ============
 799 CheckAreas_r
 800 ============
 801 */
 802 void CheckAreas_r( node_t *node ) {
 803         if ( node->planenum != PLANENUM_LEAF ) {
 804                 CheckAreas_r (node->children[0]);
 805                 CheckAreas_r (node->children[1]);
 806                 return;
 807         }
 808         if ( !node->opaque && node->area < 0 ) {
 809                 common->Error( "CheckAreas_r: area = %i", node->area );
 810         }
 811 }
 812
 813 /*
 814 ============
 815 ClearAreas_r
 816
 817 Set all the areas to -1 before filling
 818 ============
 819 */
 820 void ClearAreas_r( node_t *node ) {
 821         if ( node->planenum != PLANENUM_LEAF ) {
 822                 ClearAreas_r (node->children[0]);
 823                 ClearAreas_r (node->children[1]);
 824                 return;
 825         }
 826         node->area = -1;
 827 }
 828
 829 //=============================================================
 830
 831
 832 /*
 833 =================
 834 FindInterAreaPortals_r
 835
 836 =================
 837 */
 838 static void FindInterAreaPortals_r( node_t *node ) {
 839         uPortal_t       *p;
 840         int                     s;
 841         int                     i;
 842         idWinding       *w;
 843         interAreaPortal_t       *iap;
 844         side_t          *side;
 845
 846         if ( node->planenum != PLANENUM_LEAF ) {
 847                 FindInterAreaPortals_r( node->children[0] );
 848                 FindInterAreaPortals_r( node->children[1] );
 849                 return;
 850         }
 851
 852         if ( node->opaque ) {
 853                 return;
 854         }
 855
 856         for ( p=node->portals ; p ; p = p->next[s] ) {
 857                 node_t  *other;
 858
 859                 s = (p->nodes[1] == node);
 860                 other = p->nodes[!s];
 861
 862                 if ( other->opaque ) {
 863                         continue;
 864                 }
 865
 866                 // only report areas going from lower number to higher number
 867                 // so we don't report the portal twice
 868                 if ( other->area <= node->area ) {
 869                         continue;
 870                 }
 871
 872                 side = FindSideForPortal( p );
 873 //              w = p->winding;
 874                 if ( !side ) {
 875                         common->Warning( "FindSideForPortal failed at %s", p->winding->GetCenter().ToString() );
 876                         continue;
 877                 }
 878                 w = side->visibleHull;
 879                 if ( !w ) {
 880                         continue;
 881                 }
 882
 883                 // see if we have created this portal before
 884                 for ( i = 0 ; i < numInterAreaPortals ; i++ ) {
 885                         iap = &interAreaPortals[i];
 886
 887                         if ( side == iap->side &&
 888                                 ( ( p->nodes[0]->area == iap->area0 && p->nodes[1]->area == iap->area1 )
 889                                 || ( p->nodes[1]->area == iap->area0 && p->nodes[0]->area == iap->area1 ) ) ) {
 890                                 break;
 891                         }
 892                 }
 893
 894                 if ( i != numInterAreaPortals ) {
 895                         continue;       // already emited
 896                 }
 897
 898                 iap = &interAreaPortals[numInterAreaPortals];
 899                 numInterAreaPortals++;
 900                 if ( side->planenum == p->onnode->planenum ) {
 901                         iap->area0 = p->nodes[0]->area;
 902                         iap->area1 = p->nodes[1]->area;
 903                 } else {
 904                         iap->area0 = p->nodes[1]->area;
 905                         iap->area1 = p->nodes[0]->area;
 906                 }
 907                 iap->side = side;
 908
 909         }
 910 }
 911
 912
 913
 914
 915
 916 /*
 917 =============
 918 FloodAreas
 919
 920 Mark each leaf with an area, bounded by CONTENTS_AREAPORTAL
 921 Sets e->areas.numAreas
 922 =============
 923 */
 924 void FloodAreas( uEntity_t *e ) {
 925         common->Printf ("--- FloodAreas ---\n");
 926
 927         // set all areas to -1
 928         ClearAreas_r( e->tree->headnode );
 929
 930         // flood fill from non-opaque areas
 931         c_areas = 0;
 932         FindAreas_r( e->tree->headnode );
 933
 934         common->Printf ("%5i areas\n", c_areas);
 935         e->numAreas = c_areas;
 936
 937         // make sure we got all of them
 938         CheckAreas_r( e->tree->headnode );
 939
 940         // identify all portals between areas if this is the world
 941         if ( e == &dmapGlobals.uEntities[0] ) {
 942                 numInterAreaPortals = 0;
 943                 FindInterAreaPortals_r( e->tree->headnode );
 944         }
 945 }
 946
 947 /*
 948 ======================================================
 949
 950 FILL OUTSIDE
 951
 952 ======================================================
 953 */
 954
 955 static  int             c_outside;
 956 static  int             c_inside;
 957 static  int             c_solid;
 958
 959 void FillOutside_r (node_t *node)
 960 {
 961         if (node->planenum != PLANENUM_LEAF)
 962         {
 963                 FillOutside_r (node->children[0]);
 964                 FillOutside_r (node->children[1]);
 965                 return;
 966         }
 967
 968         // anything not reachable by an entity
 969         // can be filled away
 970         if (!node->occupied) {
 971                 if ( !node->opaque ) {
 972                         c_outside++;
 973                         node->opaque = true;
 974                 } else {
 975                         c_solid++;
 976                 }
 977         } else {
 978                 c_inside++;
 979         }
 980
 981 }
 982
 983 /*
 984 =============
 985 FillOutside
 986
 987 Fill (set node->opaque = true) all nodes that can't be reached by entities
 988 =============
 989 */
 990 void FillOutside( uEntity_t *e ) {
 991         c_outside = 0;
 992         c_inside = 0;
 993         c_solid = 0;
 994         common->Printf ("--- FillOutside ---\n");
 995         FillOutside_r( e->tree->headnode );
 996         common->Printf ("%5i solid leafs\n", c_solid);
 997         common->Printf ("%5i leafs filled\n", c_outside);
 998         common->Printf ("%5i inside leafs\n", c_inside);
 999 }