tools/quake2/q2map/portals.c

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