tools/quake2/q2map/portals.c

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