tools/quake2/extra/bsp/qbsp3/portals.c

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