tools/quake2/q2map/portals.c

   1 /*
   2    Copyright (C) 1999-2007 id Software, Inc. and contributors.
   3    For a list of contributors, see the accompanying CONTRIBUTORS file.
   4
   5    This file is part of GtkRadiant.
   6
   7    GtkRadiant is free software; you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 2 of the License, or
  10    (at your option) any later version.
  11
  12    GtkRadiant is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with GtkRadiant; if not, write to the Free Software
  19    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  20  */
  21
  22 #include "qbsp.h"
  23
  24
  25 int c_active_portals;
  26 int c_peak_portals;
  27 int c_boundary;
  28 int c_boundary_sides;
  29
  30 /*
  31    ===========
  32    AllocPortal
  33    ===========
  34  */
  35 portal_t *AllocPortal( void ){
  36         portal_t    *p;
  37
  38         if ( numthreads == 1 ) {
  39                 c_active_portals++;
  40         }
  41         if ( c_active_portals > c_peak_portals ) {
  42                 c_peak_portals = c_active_portals;
  43         }
  44
  45         p = malloc( sizeof( portal_t ) );
  46         memset( p, 0, sizeof( portal_t ) );
  47
  48         return p;
  49 }
  50
  51 void FreePortal( portal_t *p ){
  52         if ( p->winding ) {
  53                 FreeWinding( p->winding );
  54         }
  55         if ( numthreads == 1 ) {
  56                 c_active_portals--;
  57         }
  58         free( p );
  59 }
  60
  61 //==============================================================
  62
  63 /*
  64    ==============
  65    VisibleContents
  66
  67    Returns the single content bit of the
  68    strongest visible content present
  69    ==============
  70  */
  71 int VisibleContents( int contents ){
  72         int i;
  73
  74         for ( i = 1 ; i <= LAST_VISIBLE_CONTENTS ; i <<= 1 )
  75                 if ( contents & i ) {
  76                         return i;
  77                 }
  78
  79         return 0;
  80 }
  81
  82
  83 /*
  84    ===============
  85    ClusterContents
  86    ===============
  87  */
  88 int ClusterContents( node_t *node ){
  89         int c1, c2, c;
  90
  91         if ( node->planenum == PLANENUM_LEAF ) {
  92                 return node->contents;
  93         }
  94
  95         c1 = ClusterContents( node->children[0] );
  96         c2 = ClusterContents( node->children[1] );
  97         c = c1 | c2;
  98
  99         // a cluster may include some solid detail areas, but
 100         // still be seen into
 101         if ( !( c1 & CONTENTS_SOLID ) || !( c2 & CONTENTS_SOLID ) ) {
 102                 c &= ~CONTENTS_SOLID;
 103         }
 104         return c;
 105 }
 106
 107 /*
 108    =============
 109    Portal_VisFlood
 110
 111    Returns true if the portal is empty or translucent, allowing
 112    the PVS calculation to see through it.
 113    The nodes on either side of the portal may actually be clusters,
 114    not leafs, so all contents should be ored together
 115    =============
 116  */
 117 qboolean Portal_VisFlood( portal_t *p ){
 118         int c1, c2;
 119
 120         if ( !p->onnode ) {
 121                 return false;   // to global outsideleaf
 122
 123         }
 124         c1 = ClusterContents( p->nodes[0] );
 125         c2 = ClusterContents( p->nodes[1] );
 126
 127         if ( !VisibleContents( c1 ^ c2 ) ) {
 128                 return true;
 129         }
 130
 131         if ( c1 & ( CONTENTS_TRANSLUCENT | CONTENTS_DETAIL ) ) {
 132                 c1 = 0;
 133         }
 134         if ( c2 & ( CONTENTS_TRANSLUCENT | CONTENTS_DETAIL ) ) {
 135                 c2 = 0;
 136         }
 137
 138         if ( ( c1 | c2 ) & CONTENTS_SOLID ) {
 139                 return false;       // can't see through solid
 140
 141         }
 142         if ( !( c1 ^ c2 ) ) {
 143                 return true;        // identical on both sides
 144
 145         }
 146         if ( !VisibleContents( c1 ^ c2 ) ) {
 147                 return true;
 148         }
 149         return false;
 150 }
 151
 152
 153 /*
 154    ===============
 155    Portal_EntityFlood
 156
 157    The entity flood determines which areas are
 158    "outside" on the map, which are then filled in.
 159    Flowing from side s to side !s
 160    ===============
 161  */
 162 qboolean Portal_EntityFlood( portal_t *p, int s ){
 163         if ( p->nodes[0]->planenum != PLANENUM_LEAF
 164                  || p->nodes[1]->planenum != PLANENUM_LEAF ) {
 165                 Error( "Portal_EntityFlood: not a leaf" );
 166         }
 167
 168         // can never cross to a solid
 169         if ( ( p->nodes[0]->contents & CONTENTS_SOLID )
 170                  || ( p->nodes[1]->contents & CONTENTS_SOLID ) ) {
 171                 return false;
 172         }
 173
 174         // can flood through everything else
 175         return true;
 176 }
 177
 178
 179 //=============================================================================
 180
 181 int c_tinyportals;
 182
 183 /*
 184    =============
 185    AddPortalToNodes
 186    =============
 187  */
 188 void AddPortalToNodes( portal_t *p, node_t *front, node_t *back ){
 189         if ( p->nodes[0] || p->nodes[1] ) {
 190                 Error( "AddPortalToNode: allready included" );
 191         }
 192
 193         p->nodes[0] = front;
 194         p->next[0] = front->portals;
 195         front->portals = p;
 196
 197         p->nodes[1] = back;
 198         p->next[1] = back->portals;
 199         back->portals = p;
 200 }
 201
 202
 203 /*
 204    =============
 205    RemovePortalFromNode
 206    =============
 207  */
 208 void RemovePortalFromNode( portal_t *portal, node_t *l ){
 209         portal_t    **pp, *t;
 210
 211 // remove reference to the current portal
 212         pp = &l->portals;
 213         while ( 1 )
 214         {
 215                 t = *pp;
 216                 if ( !t ) {
 217                         Error( "RemovePortalFromNode: portal not in leaf" );
 218                 }
 219
 220                 if ( t == portal ) {
 221                         break;
 222                 }
 223
 224                 if ( t->nodes[0] == l ) {
 225                         pp = &t->next[0];
 226                 }
 227                 else if ( t->nodes[1] == l ) {
 228                         pp = &t->next[1];
 229                 }
 230                 else{
 231                         Error( "RemovePortalFromNode: portal not bounding leaf" );
 232                 }
 233         }
 234
 235         if ( portal->nodes[0] == l ) {
 236                 *pp = portal->next[0];
 237                 portal->nodes[0] = NULL;
 238         }
 239         else if ( portal->nodes[1] == l ) {
 240                 *pp = portal->next[1];
 241                 portal->nodes[1] = NULL;
 242         }
 243 }
 244
 245 //============================================================================
 246
 247 void PrintPortal( portal_t *p ){
 248         int i;
 249         winding_t   *w;
 250
 251         w = p->winding;
 252         for ( i = 0 ; i < w->numpoints ; i++ )
 253                 Sys_Printf( "(%5.0f,%5.0f,%5.0f)\n",w->p[i][0]
 254                                         , w->p[i][1], w->p[i][2] );
 255 }
 256
 257 /*
 258    ================
 259    MakeHeadnodePortals
 260
 261    The created portals will face the global outside_node
 262    ================
 263  */
 264 #define SIDESPACE   8
 265 void MakeHeadnodePortals( tree_t *tree ){
 266         vec3_t bounds[2];
 267         int i, j, n;
 268         portal_t    *p, *portals[6];
 269         plane_t bplanes[6], *pl;
 270         node_t *node;
 271
 272         node = tree->headnode;
 273
 274 // pad with some space so there will never be null volume leafs
 275         for ( i = 0 ; i < 3 ; i++ )
 276         {
 277                 bounds[0][i] = tree->mins[i] - SIDESPACE;
 278                 bounds[1][i] = tree->maxs[i] + SIDESPACE;
 279         }
 280
 281         tree->outside_node.planenum = PLANENUM_LEAF;
 282         tree->outside_node.brushlist = NULL;
 283         tree->outside_node.portals = NULL;
 284         tree->outside_node.contents = 0;
 285
 286         for ( i = 0 ; i < 3 ; i++ )
 287                 for ( j = 0 ; j < 2 ; j++ )
 288                 {
 289                         n = j * 3 + i;
 290
 291                         p = AllocPortal();
 292                         portals[n] = p;
 293
 294                         pl = &bplanes[n];
 295                         memset( pl, 0, sizeof( *pl ) );
 296                         if ( j ) {
 297                                 pl->normal[i] = -1;
 298                                 pl->dist = -bounds[j][i];
 299                         }
 300                         else
 301                         {
 302                                 pl->normal[i] = 1;
 303                                 pl->dist = bounds[j][i];
 304                         }
 305                         p->plane = *pl;
 306                         p->winding = BaseWindingForPlane( pl->normal, pl->dist );
 307                         AddPortalToNodes( p, node, &tree->outside_node );
 308                 }
 309
 310 // clip the basewindings by all the other planes
 311         for ( i = 0 ; i < 6 ; i++ )
 312         {
 313                 for ( j = 0 ; j < 6 ; j++ )
 314                 {
 315                         if ( j == i ) {
 316                                 continue;
 317                         }
 318                         ChopWindingInPlace( &portals[i]->winding, bplanes[j].normal, bplanes[j].dist, ON_EPSILON );
 319                 }
 320         }
 321 }
 322
 323 //===================================================
 324
 325
 326 /*
 327    ================
 328    BaseWindingForNode
 329    ================
 330  */
 331 #define BASE_WINDING_EPSILON    0.001
 332 #define SPLIT_WINDING_EPSILON   0.001
 333
 334 winding_t   *BaseWindingForNode( node_t *node ){
 335         winding_t   *w;
 336         node_t      *n;
 337         plane_t     *plane;
 338         vec3_t normal;
 339         vec_t dist;
 340
 341         w = BaseWindingForPlane( mapplanes[node->planenum].normal
 342                                                          , mapplanes[node->planenum].dist );
 343
 344         // clip by all the parents
 345         for ( n = node->parent ; n && w ; )
 346         {
 347                 plane = &mapplanes[n->planenum];
 348
 349                 if ( n->children[0] == node ) { // take front
 350                         ChopWindingInPlace( &w, plane->normal, plane->dist, BASE_WINDING_EPSILON );
 351                 }
 352                 else
 353                 {   // take back
 354                         VectorSubtract( vec3_origin, plane->normal, normal );
 355                         dist = -plane->dist;
 356                         ChopWindingInPlace( &w, normal, dist, BASE_WINDING_EPSILON );
 357                 }
 358                 node = n;
 359                 n = n->parent;
 360         }
 361
 362         return w;
 363 }
 364
 365 //============================================================
 366
 367 qboolean WindingIsTiny( winding_t *w );
 368
 369 /*
 370    ==================
 371    MakeNodePortal
 372
 373    create the new portal by taking the full plane winding for the cutting plane
 374    and clipping it by all of parents of this node
 375    ==================
 376  */
 377 void MakeNodePortal( node_t *node ){
 378         portal_t    *new_portal, *p;
 379         winding_t   *w;
 380         vec3_t normal;
 381         float dist;
 382         int side;
 383
 384         w = BaseWindingForNode( node );
 385
 386         // clip the portal by all the other portals in the node
 387         for ( p = node->portals ; p && w; p = p->next[side] )
 388         {
 389                 if ( p->nodes[0] == node ) {
 390                         side = 0;
 391                         VectorCopy( p->plane.normal, normal );
 392                         dist = p->plane.dist;
 393                 }
 394                 else if ( p->nodes[1] == node ) {
 395                         side = 1;
 396                         VectorSubtract( vec3_origin, p->plane.normal, normal );
 397                         dist = -p->plane.dist;
 398                 }
 399                 else{
 400                         Error( "CutNodePortals_r: mislinked portal" );
 401                 }
 402
 403                 ChopWindingInPlace( &w, normal, dist, 0.1 );
 404         }
 405
 406         if ( !w ) {
 407                 return;
 408         }
 409
 410         if ( WindingIsTiny( w ) ) {
 411                 c_tinyportals++;
 412                 FreeWinding( w );
 413                 return;
 414         }
 415
 416
 417         new_portal = AllocPortal();
 418         new_portal->plane = mapplanes[node->planenum];
 419         new_portal->onnode = node;
 420         new_portal->winding = w;
 421         AddPortalToNodes( new_portal, node->children[0], node->children[1] );
 422 }
 423
 424
 425 /*
 426    ==============
 427    SplitNodePortals
 428
 429    Move or split the portals that bound node so that the node's
 430    children have portals instead of node.
 431    ==============
 432  */
 433 void SplitNodePortals( node_t *node ){
 434         portal_t    *p, *next_portal, *new_portal;
 435         node_t      *f, *b, *other_node;
 436         int side;
 437         plane_t     *plane;
 438         winding_t   *frontwinding, *backwinding;
 439
 440         plane = &mapplanes[node->planenum];
 441         f = node->children[0];
 442         b = node->children[1];
 443
 444         for ( p = node->portals ; p ; p = next_portal )
 445         {
 446                 if ( p->nodes[0] == node ) {
 447                         side = 0;
 448                 }
 449                 else if ( p->nodes[1] == node ) {
 450                         side = 1;
 451                 }
 452                 else{
 453                         Error( "CutNodePortals_r: mislinked portal" );
 454                 }
 455                 next_portal = p->next[side];
 456
 457                 other_node = p->nodes[!side];
 458                 RemovePortalFromNode( p, p->nodes[0] );
 459                 RemovePortalFromNode( p, p->nodes[1] );
 460
 461 //
 462 // cut the portal into two portals, one on each side of the cut plane
 463 //
 464                 ClipWindingEpsilon( p->winding, plane->normal, plane->dist,
 465                                                         SPLIT_WINDING_EPSILON, &frontwinding, &backwinding );
 466
 467                 if ( frontwinding && WindingIsTiny( frontwinding ) ) {
 468                         FreeWinding( frontwinding );
 469                         frontwinding = NULL;
 470                         c_tinyportals++;
 471                 }
 472
 473                 if ( backwinding && WindingIsTiny( backwinding ) ) {
 474                         FreeWinding( backwinding );
 475                         backwinding = NULL;
 476                         c_tinyportals++;
 477                 }
 478
 479                 if ( !frontwinding && !backwinding ) { // tiny windings on both sides
 480                         continue;
 481                 }
 482
 483                 if ( !frontwinding ) {
 484                         FreeWinding( backwinding );
 485                         if ( side == 0 ) {
 486                                 AddPortalToNodes( p, b, other_node );
 487                         }
 488                         else{
 489                                 AddPortalToNodes( p, other_node, b );
 490                         }
 491                         continue;
 492                 }
 493                 if ( !backwinding ) {
 494                         FreeWinding( frontwinding );
 495                         if ( side == 0 ) {
 496                                 AddPortalToNodes( p, f, other_node );
 497                         }
 498                         else{
 499                                 AddPortalToNodes( p, other_node, f );
 500                         }
 501                         continue;
 502                 }
 503
 504                 // the winding is split
 505                 new_portal = AllocPortal();
 506                 *new_portal = *p;
 507                 new_portal->winding = backwinding;
 508                 FreeWinding( p->winding );
 509                 p->winding = frontwinding;
 510
 511                 if ( side == 0 ) {
 512                         AddPortalToNodes( p, f, other_node );
 513                         AddPortalToNodes( new_portal, b, other_node );
 514                 }
 515                 else
 516                 {
 517                         AddPortalToNodes( p, other_node, f );
 518                         AddPortalToNodes( new_portal, other_node, b );
 519                 }
 520         }
 521
 522         node->portals = NULL;
 523 }
 524
 525
 526 /*
 527    ================
 528    CalcNodeBounds
 529    ================
 530  */
 531 void CalcNodeBounds( node_t *node ){
 532         portal_t    *p;
 533         int s;
 534         int i;
 535
 536         // calc mins/maxs for both leafs and nodes
 537         ClearBounds( node->mins, node->maxs );
 538         for ( p = node->portals ; p ; p = p->next[s] )
 539         {
 540                 s = ( p->nodes[1] == node );
 541                 for ( i = 0 ; i < p->winding->numpoints ; i++ )
 542                         AddPointToBounds( p->winding->p[i], node->mins, node->maxs );
 543         }
 544 }
 545
 546
 547 /*
 548    ==================
 549    MakeTreePortals_r
 550    ==================
 551  */
 552 void MakeTreePortals_r( node_t *node ){
 553         int i;
 554
 555         CalcNodeBounds( node );
 556         if ( node->mins[0] >= node->maxs[0] ) {
 557                 Sys_FPrintf( SYS_WRN, "WARNING: node without a volume\n" );
 558         }
 559
 560         for ( i = 0 ; i < 3 ; i++ )
 561         {
 562                 if ( node->mins[i] < -8000 || node->maxs[i] > 8000 ) {
 563                         Sys_FPrintf( SYS_WRN, "WARNING: node with unbounded volume\n" );
 564                         break;
 565                 }
 566         }
 567         if ( node->planenum == PLANENUM_LEAF ) {
 568                 return;
 569         }
 570
 571         MakeNodePortal( node );
 572         SplitNodePortals( node );
 573
 574         MakeTreePortals_r( node->children[0] );
 575         MakeTreePortals_r( node->children[1] );
 576 }
 577
 578 /*
 579    ==================
 580    MakeTreePortals
 581    ==================
 582  */
 583 void MakeTreePortals( tree_t *tree ){
 584         MakeHeadnodePortals( tree );
 585         MakeTreePortals_r( tree->headnode );
 586 }
 587
 588 /*
 589    =========================================================
 590
 591    FLOOD ENTITIES
 592
 593    =========================================================
 594  */
 595
 596 /*
 597    =============
 598    FloodPortals_r
 599    =============
 600  */
 601 void FloodPortals_r( node_t *node, int dist ){
 602         portal_t    *p;
 603         int s;
 604
 605         node->occupied = dist;
 606
 607         for ( p = node->portals ; p ; p = p->next[s] )
 608         {
 609                 s = ( p->nodes[1] == node );
 610
 611                 if ( p->nodes[!s]->occupied ) {
 612                         continue;
 613                 }
 614
 615                 if ( !Portal_EntityFlood( p, s ) ) {
 616                         continue;
 617                 }
 618
 619                 FloodPortals_r( p->nodes[!s], dist + 1 );
 620         }
 621 }
 622
 623 /*
 624    =============
 625    PlaceOccupant
 626    =============
 627  */
 628 qboolean PlaceOccupant( node_t *headnode, vec3_t origin, entity_t *occupant ){
 629         node_t  *node;
 630         vec_t d;
 631         plane_t *plane;
 632
 633         // find the leaf to start in
 634         node = headnode;
 635         while ( node->planenum != PLANENUM_LEAF )
 636         {
 637                 plane = &mapplanes[node->planenum];
 638                 d = DotProduct( origin, plane->normal ) - plane->dist;
 639                 if ( d >= 0 ) {
 640                         node = node->children[0];
 641                 }
 642                 else{
 643                         node = node->children[1];
 644                 }
 645         }
 646
 647         if ( node->contents == CONTENTS_SOLID ) {
 648                 return false;
 649         }
 650         node->occupant = occupant;
 651
 652         FloodPortals_r( node, 1 );
 653
 654         return true;
 655 }
 656
 657 /*
 658    =============
 659    FloodEntities
 660
 661    Marks all nodes that can be reached by entites
 662    =============
 663  */
 664 qboolean FloodEntities( tree_t *tree ){
 665         int i;
 666         vec3_t origin;
 667         char    *cl;
 668         qboolean inside;
 669         node_t *headnode;
 670
 671         headnode = tree->headnode;
 672         Sys_FPrintf( SYS_VRB, "--- FloodEntities ---\n" );
 673         inside = false;
 674         tree->outside_node.occupied = 0;
 675
 676         for ( i = 1 ; i < num_entities ; i++ )
 677         {
 678                 GetVectorForKey( &entities[i], "origin", origin );
 679                 if ( VectorCompare( origin, vec3_origin ) ) {
 680                         continue;
 681                 }
 682
 683                 cl = ValueForKey( &entities[i], "classname" );
 684                 origin[2] += 1; // so objects on floor are ok
 685
 686                 // nudge playerstart around if needed so clipping hulls allways
 687                 // have a vlaid point
 688                 if ( !strcmp( cl, "info_player_start" ) ) {
 689                         int x, y;
 690
 691                         for ( x = -16 ; x <= 16 ; x += 16 )
 692                         {
 693                                 for ( y = -16 ; y <= 16 ; y += 16 )
 694                                 {
 695                                         origin[0] += x;
 696                                         origin[1] += y;
 697                                         if ( PlaceOccupant( headnode, origin, &entities[i] ) ) {
 698                                                 inside = true;
 699                                                 goto gotit;
 700                                         }
 701                                         origin[0] -= x;
 702                                         origin[1] -= y;
 703                                 }
 704                         }
 705 gotit: ;
 706                 }
 707                 else
 708                 {
 709                         if ( PlaceOccupant( headnode, origin, &entities[i] ) ) {
 710                                 inside = true;
 711                         }
 712                 }
 713         }
 714
 715         if ( !inside ) {
 716                 Sys_FPrintf( SYS_VRB, "no entities in open -- no filling\n" );
 717         }
 718         else if ( tree->outside_node.occupied ) {
 719                 Sys_FPrintf( SYS_VRB, "entity reached from outside -- no filling\n" );
 720         }
 721
 722         return (qboolean)( inside && !tree->outside_node.occupied );
 723 }
 724
 725 /*
 726    =========================================================
 727
 728    FLOOD AREAS
 729
 730    =========================================================
 731  */
 732
 733 int c_areas;
 734
 735 /*
 736    =============
 737    FloodAreas_r
 738    =============
 739  */
 740 void FloodAreas_r( node_t *node ){
 741         portal_t    *p;
 742         int s;
 743         bspbrush_t  *b;
 744         entity_t    *e;
 745
 746         if ( node->contents == CONTENTS_AREAPORTAL ) {
 747                 // this node is part of an area portal
 748                 b = node->brushlist;
 749                 e = &entities[b->original->entitynum];
 750
 751                 // if the current area has allready touched this
 752                 // portal, we are done
 753                 if ( e->portalareas[0] == c_areas || e->portalareas[1] == c_areas ) {
 754                         return;
 755                 }
 756
 757                 // note the current area as bounding the portal
 758                 if ( e->portalareas[1] ) {
 759                         Sys_FPrintf( SYS_WRN, "WARNING: areaportal entity %i touches > 2 areas\n", b->original->entitynum );
 760                         return;
 761                 }
 762                 if ( e->portalareas[0] ) {
 763                         e->portalareas[1] = c_areas;
 764                 }
 765                 else{
 766                         e->portalareas[0] = c_areas;
 767                 }
 768
 769                 return;
 770         }
 771
 772         if ( node->area ) {
 773                 return;     // allready got it
 774         }
 775         node->area = c_areas;
 776
 777         for ( p = node->portals ; p ; p = p->next[s] )
 778         {
 779                 s = ( p->nodes[1] == node );
 780 #if 0
 781                 if ( p->nodes[!s]->occupied ) {
 782                         continue;
 783                 }
 784 #endif
 785                 if ( !Portal_EntityFlood( p, s ) ) {
 786                         continue;
 787                 }
 788
 789                 FloodAreas_r( p->nodes[!s] );
 790         }
 791 }
 792
 793 /*
 794    =============
 795    FindAreas_r
 796
 797    Just decend the tree, and for each node that hasn't had an
 798    area set, flood fill out from there
 799    =============
 800  */
 801 void FindAreas_r( node_t *node ){
 802         if ( node->planenum != PLANENUM_LEAF ) {
 803                 FindAreas_r( node->children[0] );
 804                 FindAreas_r( node->children[1] );
 805                 return;
 806         }
 807
 808         if ( node->area ) {
 809                 return;     // allready got it
 810
 811         }
 812         if ( node->contents & CONTENTS_SOLID ) {
 813                 return;
 814         }
 815
 816         if ( !node->occupied ) {
 817                 return;         // not reachable by entities
 818
 819         }
 820         // area portals are allways only flooded into, never
 821         // out of
 822         if ( node->contents == CONTENTS_AREAPORTAL ) {
 823                 return;
 824         }
 825
 826         c_areas++;
 827         FloodAreas_r( node );
 828 }
 829
 830 /*
 831    =============
 832    SetAreaPortalAreas_r
 833
 834    Just decend the tree, and for each node that hasn't had an
 835    area set, flood fill out from there
 836    =============
 837  */
 838 void SetAreaPortalAreas_r( node_t *node ){
 839         bspbrush_t  *b;
 840         entity_t    *e;
 841
 842         if ( node->planenum != PLANENUM_LEAF ) {
 843                 SetAreaPortalAreas_r( node->children[0] );
 844                 SetAreaPortalAreas_r( node->children[1] );
 845                 return;
 846         }
 847
 848         if ( node->contents == CONTENTS_AREAPORTAL ) {
 849                 if ( node->area ) {
 850                         return;     // allready set
 851
 852                 }
 853                 b = node->brushlist;
 854                 e = &entities[b->original->entitynum];
 855                 node->area = e->portalareas[0];
 856                 if ( !e->portalareas[1] ) {
 857                         Sys_FPrintf( SYS_WRN, "WARNING: areaportal entity %i doesn't touch two areas\n", b->original->entitynum );
 858                         return;
 859                 }
 860         }
 861 }
 862
 863 /*
 864    =============
 865    EmitAreaPortals
 866
 867    =============
 868  */
 869 void EmitAreaPortals( node_t *headnode ){
 870         int i, j;
 871         entity_t        *e;
 872         dareaportal_t   *dp;
 873
 874         if ( c_areas > MAX_MAP_AREAS ) {
 875                 Error( "MAX_MAP_AREAS" );
 876         }
 877         numareas = c_areas + 1;
 878         numareaportals = 1;     // leave 0 as an error
 879
 880         for ( i = 1 ; i <= c_areas ; i++ )
 881         {
 882                 dareas[i].firstareaportal = numareaportals;
 883                 for ( j = 0 ; j < num_entities ; j++ )
 884                 {
 885                         e = &entities[j];
 886                         if ( !e->areaportalnum ) {
 887                                 continue;
 888                         }
 889                         dp = &dareaportals[numareaportals];
 890                         if ( e->portalareas[0] == i ) {
 891                                 dp->portalnum = e->areaportalnum;
 892                                 dp->otherarea = e->portalareas[1];
 893                                 numareaportals++;
 894                         }
 895                         else if ( e->portalareas[1] == i ) {
 896                                 dp->portalnum = e->areaportalnum;
 897                                 dp->otherarea = e->portalareas[0];
 898                                 numareaportals++;
 899                         }
 900                 }
 901                 dareas[i].numareaportals = numareaportals - dareas[i].firstareaportal;
 902         }
 903
 904         Sys_FPrintf( SYS_VRB, "%5i numareas\n", numareas );
 905         Sys_FPrintf( SYS_VRB, "%5i numareaportals\n", numareaportals );
 906 }
 907
 908 /*
 909    =============
 910    FloodAreas
 911
 912    Mark each leaf with an area, bounded by CONTENTS_AREAPORTAL
 913    =============
 914  */
 915 void FloodAreas( tree_t *tree ){
 916         Sys_FPrintf( SYS_VRB, "--- FloodAreas ---\n" );
 917         FindAreas_r( tree->headnode );
 918         SetAreaPortalAreas_r( tree->headnode );
 919         Sys_FPrintf( SYS_VRB, "%5i areas\n", c_areas );
 920 }
 921
 922 //======================================================
 923
 924 int c_outside;
 925 int c_inside;
 926 int c_solid;
 927
 928 void FillOutside_r( node_t *node ){
 929         if ( node->planenum != PLANENUM_LEAF ) {
 930                 FillOutside_r( node->children[0] );
 931                 FillOutside_r( node->children[1] );
 932                 return;
 933         }
 934
 935         // anything not reachable by an entity
 936         // can be filled away
 937         if ( !node->occupied ) {
 938                 if ( node->contents != CONTENTS_SOLID ) {
 939                         c_outside++;
 940                         node->contents = CONTENTS_SOLID;
 941                 }
 942                 else{
 943                         c_solid++;
 944                 }
 945         }
 946         else{
 947                 c_inside++;
 948         }
 949
 950 }
 951
 952 /*
 953    =============
 954    FillOutside
 955
 956    Fill all nodes that can't be reached by entities
 957    =============
 958  */
 959 void FillOutside( node_t *headnode ){
 960         c_outside = 0;
 961         c_inside = 0;
 962         c_solid = 0;
 963         Sys_FPrintf( SYS_VRB, "--- FillOutside ---\n" );
 964         FillOutside_r( headnode );
 965         Sys_FPrintf( SYS_VRB, "%5i solid leafs\n", c_solid );
 966         Sys_FPrintf( SYS_VRB, "%5i leafs filled\n", c_outside );
 967         Sys_FPrintf( SYS_VRB, "%5i inside leafs\n", c_inside );
 968 }
 969
 970
 971 //==============================================================
 972
 973 /*
 974    ============
 975    FindPortalSide
 976
 977    Finds a brush side to use for texturing the given portal
 978    ============
 979  */
 980 void FindPortalSide( portal_t *p ){
 981         int viscontents;
 982         bspbrush_t  *bb;
 983         mapbrush_t  *brush;
 984         node_t      *n;
 985         int i,j;
 986         int planenum;
 987         side_t      *side, *bestside;
 988         float dot, bestdot;
 989         plane_t     *p1, *p2;
 990
 991         // decide which content change is strongest
 992         // solid > lava > water, etc
 993         viscontents = VisibleContents( p->nodes[0]->contents ^ p->nodes[1]->contents );
 994         if ( !viscontents ) {
 995                 return;
 996         }
 997
 998         planenum = p->onnode->planenum;
 999         bestside = NULL;
1000         bestdot = 0;
1001
1002         for ( j = 0 ; j < 2 ; j++ )
1003         {
1004                 n = p->nodes[j];
1005                 p1 = &mapplanes[p->onnode->planenum];
1006                 for ( bb = n->brushlist ; bb ; bb = bb->next )
1007                 {
1008                         brush = bb->original;
1009                         if ( !( brush->contents & viscontents ) ) {
1010                                 continue;
1011                         }
1012                         for ( i = 0 ; i < brush->numsides ; i++ )
1013                         {
1014                                 side = &brush->original_sides[i];
1015                                 if ( side->bevel ) {
1016                                         continue;
1017                                 }
1018                                 if ( side->texinfo == TEXINFO_NODE ) {
1019                                         continue;       // non-visible
1020                                 }
1021                                 if ( ( side->planenum & ~1 ) == planenum ) { // exact match
1022                                         bestside = &brush->original_sides[i];
1023                                         goto gotit;
1024                                 }
1025                                 // see how close the match is
1026                                 p2 = &mapplanes[side->planenum & ~1];
1027                                 dot = DotProduct( p1->normal, p2->normal );
1028                                 if ( dot > bestdot ) {
1029                                         bestdot = dot;
1030                                         bestside = side;
1031                                 }
1032                         }
1033                 }
1034         }
1035
1036 gotit:
1037         if ( !bestside ) {
1038                 Sys_FPrintf( SYS_VRB, "WARNING: side not found for portal\n" );
1039         }
1040
1041         p->sidefound = true;
1042         p->side = bestside;
1043 }
1044
1045
1046 /*
1047    ===============
1048    MarkVisibleSides_r
1049
1050    ===============
1051  */
1052 void MarkVisibleSides_r( node_t *node ){
1053         portal_t    *p;
1054         int s;
1055
1056         if ( node->planenum != PLANENUM_LEAF ) {
1057                 MarkVisibleSides_r( node->children[0] );
1058                 MarkVisibleSides_r( node->children[1] );
1059                 return;
1060         }
1061
1062         // empty leafs are never boundary leafs
1063         if ( !node->contents ) {
1064                 return;
1065         }
1066
1067         // see if there is a visible face
1068         for ( p = node->portals ; p ; p = p->next[!s] )
1069         {
1070                 s = ( p->nodes[0] == node );
1071                 if ( !p->onnode ) {
1072                         continue;       // edge of world
1073                 }
1074                 if ( !p->sidefound ) {
1075                         FindPortalSide( p );
1076                 }
1077                 if ( p->side ) {
1078                         p->side->visible = true;
1079                 }
1080         }
1081
1082 }
1083
1084 /*
1085    =============
1086    MarkVisibleSides
1087
1088    =============
1089  */
1090 void MarkVisibleSides( tree_t *tree, int startbrush, int endbrush ){
1091         int i, j;
1092         mapbrush_t  *mb;
1093         int numsides;
1094
1095         Sys_FPrintf( SYS_VRB, "--- MarkVisibleSides ---\n" );
1096
1097         // clear all the visible flags
1098         for ( i = startbrush ; i < endbrush ; i++ )
1099         {
1100                 mb = &mapbrushes[i];
1101
1102                 numsides = mb->numsides;
1103                 for ( j = 0 ; j < numsides ; j++ )
1104                         mb->original_sides[j].visible = false;
1105         }
1106
1107         // set visible flags on the sides that are used by portals
1108         MarkVisibleSides_r( tree->headnode );
1109 }