tools/quake3/q3map2/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 \r
  23 This code has been altered significantly from its original form, to support\r
  24 several games based on the Quake III Arena engine, in the form of "Q3Map2."\r
  25 \r
  26 ------------------------------------------------------------------------------- */\r
  27 \r
  28 \r
  29 \r
  30 /* marker */\r
  31 #define PORTALS_C\r
  32 \r
  33 \r
  34 \r
  35 /* dependencies */\r
  36 #include "q3map2.h"\r
  37 \r
  38 \r
  39 \r
  40 /* ydnar: to fix broken portal windings */\r
  41 extern qboolean FixWinding( winding_t *w );\r
  42 \r
  43 \r
  44 int             c_active_portals;\r
  45 int             c_peak_portals;\r
  46 int             c_boundary;\r
  47 int             c_boundary_sides;\r
  48 \r
  49 /*\r
  50 ===========\r
  51 AllocPortal\r
  52 ===========\r
  53 */\r
  54 portal_t *AllocPortal (void)\r
  55 {\r
  56         portal_t        *p;\r
  57         \r
  58         if (numthreads == 1)\r
  59                 c_active_portals++;\r
  60         if (c_active_portals > c_peak_portals)\r
  61                 c_peak_portals = c_active_portals;\r
  62         \r
  63         p = safe_malloc (sizeof(portal_t));\r
  64         memset (p, 0, sizeof(portal_t));\r
  65         \r
  66         return p;\r
  67 }\r
  68 \r
  69 void FreePortal (portal_t *p)\r
  70 {\r
  71         if (p->winding)\r
  72                 FreeWinding (p->winding);\r
  73         if (numthreads == 1)\r
  74                 c_active_portals--;\r
  75         free (p);\r
  76 }\r
  77 \r
  78 \r
  79 \r
  80 /*\r
  81 PortalPassable\r
  82 returns true if the portal has non-opaque leafs on both sides\r
  83 */\r
  84 \r
  85 qboolean PortalPassable( portal_t *p )\r
  86 {\r
  87         /* is this to global outside leaf? */\r
  88         if( !p->onnode )\r
  89                 return qfalse;\r
  90         \r
  91         /* this should never happen */\r
  92         if( p->nodes[ 0 ]->planenum != PLANENUM_LEAF ||\r
  93                 p->nodes[ 1 ]->planenum != PLANENUM_LEAF )\r
  94                 Error( "Portal_EntityFlood: not a leaf" );\r
  95         \r
  96         /* ydnar: added antiportal to supress portal generation for visibility blocking */\r
  97         if( p->compileFlags & C_ANTIPORTAL )\r
  98                 return qfalse;\r
  99         \r
 100         /* both leaves on either side of the portal must be passable */\r
 101         if( p->nodes[ 0 ]->opaque == qfalse && p->nodes[ 1 ]->opaque == qfalse )\r
 102                 return qtrue;\r
 103         \r
 104         /* otherwise this isn't a passable portal */\r
 105         return qfalse;\r
 106 }\r
 107 \r
 108 \r
 109 \r
 110 \r
 111 int             c_tinyportals;\r
 112 int             c_badportals;   /* ydnar */\r
 113 \r
 114 /*\r
 115 =============\r
 116 AddPortalToNodes\r
 117 =============\r
 118 */\r
 119 void AddPortalToNodes (portal_t *p, node_t *front, node_t *back)\r
 120 {\r
 121         if (p->nodes[0] || p->nodes[1])\r
 122                 Error ("AddPortalToNode: allready included");\r
 123 \r
 124         p->nodes[0] = front;\r
 125         p->next[0] = front->portals;\r
 126         front->portals = p;\r
 127         \r
 128         p->nodes[1] = back;\r
 129         p->next[1] = back->portals;\r
 130         back->portals = p;\r
 131 }\r
 132 \r
 133 \r
 134 /*\r
 135 =============\r
 136 RemovePortalFromNode\r
 137 =============\r
 138 */\r
 139 void RemovePortalFromNode (portal_t *portal, node_t *l)\r
 140 {\r
 141         portal_t        **pp, *t;\r
 142         \r
 143 // remove reference to the current portal\r
 144         pp = &l->portals;\r
 145         while (1)\r
 146         {\r
 147                 t = *pp;\r
 148                 if (!t)\r
 149                         Error ("RemovePortalFromNode: portal not in leaf");     \r
 150 \r
 151                 if ( t == portal )\r
 152                         break;\r
 153 \r
 154                 if (t->nodes[0] == l)\r
 155                         pp = &t->next[0];\r
 156                 else if (t->nodes[1] == l)\r
 157                         pp = &t->next[1];\r
 158                 else\r
 159                         Error ("RemovePortalFromNode: portal not bounding leaf");\r
 160         }\r
 161         \r
 162         if (portal->nodes[0] == l)\r
 163         {\r
 164                 *pp = portal->next[0];\r
 165                 portal->nodes[0] = NULL;\r
 166         }\r
 167         else if (portal->nodes[1] == l)\r
 168         {\r
 169                 *pp = portal->next[1];  \r
 170                 portal->nodes[1] = NULL;\r
 171         }\r
 172 }\r
 173 \r
 174 //============================================================================\r
 175 \r
 176 void PrintPortal (portal_t *p)\r
 177 {\r
 178         int                     i;\r
 179         winding_t       *w;\r
 180         \r
 181         w = p->winding;\r
 182         for (i=0 ; i<w->numpoints ; i++)\r
 183                 Sys_Printf ("(%5.0f,%5.0f,%5.0f)\n",w->p[i][0]\r
 184                 , w->p[i][1], w->p[i][2]);\r
 185 }\r
 186 \r
 187 /*\r
 188 ================\r
 189 MakeHeadnodePortals\r
 190 \r
 191 The created portals will face the global outside_node\r
 192 ================\r
 193 */\r
 194 #define SIDESPACE       8\r
 195 void MakeHeadnodePortals (tree_t *tree)\r
 196 {\r
 197         vec3_t          bounds[2];\r
 198         int                     i, j, n;\r
 199         portal_t        *p, *portals[6];\r
 200         plane_t         bplanes[6], *pl;\r
 201         node_t *node;\r
 202 \r
 203         node = tree->headnode;\r
 204 \r
 205 // pad with some space so there will never be null volume leafs\r
 206         for (i=0 ; i<3 ; i++)\r
 207         {\r
 208                 bounds[0][i] = tree->mins[i] - SIDESPACE;\r
 209                 bounds[1][i] = tree->maxs[i] + SIDESPACE;\r
 210                 if ( bounds[0][i] >= bounds[1][i] ) {\r
 211                         Error( "Backwards tree volume" );\r
 212                 }\r
 213         }\r
 214         \r
 215         tree->outside_node.planenum = PLANENUM_LEAF;\r
 216         tree->outside_node.brushlist = NULL;\r
 217         tree->outside_node.portals = NULL;\r
 218         tree->outside_node.opaque = qfalse;\r
 219 \r
 220         for (i=0 ; i<3 ; i++)\r
 221                 for (j=0 ; j<2 ; j++)\r
 222                 {\r
 223                         n = j*3 + i;\r
 224 \r
 225                         p = AllocPortal ();\r
 226                         portals[n] = p;\r
 227                         \r
 228                         pl = &bplanes[n];\r
 229                         memset (pl, 0, sizeof(*pl));\r
 230                         if (j)\r
 231                         {\r
 232                                 pl->normal[i] = -1;\r
 233                                 pl->dist = -bounds[j][i];\r
 234                         }\r
 235                         else\r
 236                         {\r
 237                                 pl->normal[i] = 1;\r
 238                                 pl->dist = bounds[j][i];\r
 239                         }\r
 240                         p->plane = *pl;\r
 241                         p->winding = BaseWindingForPlane (pl->normal, pl->dist);\r
 242                         AddPortalToNodes (p, node, &tree->outside_node);\r
 243                 }\r
 244                 \r
 245 // clip the basewindings by all the other planes\r
 246         for (i=0 ; i<6 ; i++)\r
 247         {\r
 248                 for (j=0 ; j<6 ; j++)\r
 249                 {\r
 250                         if (j == i)\r
 251                                 continue;\r
 252                         ChopWindingInPlace (&portals[i]->winding, bplanes[j].normal, bplanes[j].dist, ON_EPSILON);\r
 253                 }\r
 254         }\r
 255 }\r
 256 \r
 257 //===================================================\r
 258 \r
 259 \r
 260 /*\r
 261 ================\r
 262 BaseWindingForNode\r
 263 ================\r
 264 */\r
 265 #define BASE_WINDING_EPSILON    0.001\r
 266 #define SPLIT_WINDING_EPSILON   0.001\r
 267 \r
 268 winding_t       *BaseWindingForNode (node_t *node)\r
 269 {\r
 270         winding_t       *w;\r
 271         node_t          *n;\r
 272         plane_t         *plane;\r
 273         vec3_t          normal;\r
 274         vec_t           dist;\r
 275 \r
 276         w = BaseWindingForPlane (mapplanes[node->planenum].normal\r
 277                 , mapplanes[node->planenum].dist);\r
 278 \r
 279         // clip by all the parents\r
 280         for (n=node->parent ; n && w ; )\r
 281         {\r
 282                 plane = &mapplanes[n->planenum];\r
 283 \r
 284                 if (n->children[0] == node)\r
 285                 {       // take front\r
 286                         ChopWindingInPlace (&w, plane->normal, plane->dist, BASE_WINDING_EPSILON);\r
 287                 }\r
 288                 else\r
 289                 {       // take back\r
 290                         VectorSubtract (vec3_origin, plane->normal, normal);\r
 291                         dist = -plane->dist;\r
 292                         ChopWindingInPlace (&w, normal, dist, BASE_WINDING_EPSILON);\r
 293                 }\r
 294                 node = n;\r
 295                 n = n->parent;\r
 296         }\r
 297 \r
 298         return w;\r
 299 }\r
 300 \r
 301 //============================================================\r
 302 \r
 303 /*\r
 304 ==================\r
 305 MakeNodePortal\r
 306 \r
 307 create the new portal by taking the full plane winding for the cutting plane\r
 308 and clipping it by all of parents of this node\r
 309 ==================\r
 310 */\r
 311 void MakeNodePortal (node_t *node)\r
 312 {\r
 313         portal_t        *new_portal, *p;\r
 314         winding_t       *w;\r
 315         vec3_t          normal;\r
 316         float           dist;\r
 317         int                     side;\r
 318 \r
 319         w = BaseWindingForNode (node);\r
 320 \r
 321         // clip the portal by all the other portals in the node\r
 322         for (p = node->portals ; p && w; p = p->next[side])     \r
 323         {\r
 324                 if (p->nodes[0] == node)\r
 325                 {\r
 326                         side = 0;\r
 327                         VectorCopy (p->plane.normal, normal);\r
 328                         dist = p->plane.dist;\r
 329                 }\r
 330                 else if (p->nodes[1] == node)\r
 331                 {\r
 332                         side = 1;\r
 333                         VectorSubtract (vec3_origin, p->plane.normal, normal);\r
 334                         dist = -p->plane.dist;\r
 335                 }\r
 336                 else\r
 337                         Error ("CutNodePortals_r: mislinked portal");\r
 338 \r
 339                 ChopWindingInPlace (&w, normal, dist, CLIP_EPSILON);\r
 340         }\r
 341 \r
 342         if (!w)\r
 343         {\r
 344                 return;\r
 345         }\r
 346         \r
 347         \r
 348         /* ydnar: adding this here to fix degenerate windings */\r
 349         #if 0\r
 350         if( FixWinding( w ) == qfalse )\r
 351         {\r
 352                 c_badportals++;\r
 353                 FreeWinding( w );\r
 354                 return;\r
 355         }\r
 356         #endif\r
 357         \r
 358         if (WindingIsTiny (w))\r
 359         {\r
 360                 c_tinyportals++;\r
 361                 FreeWinding (w);\r
 362                 return;\r
 363         }\r
 364 \r
 365         new_portal = AllocPortal ();\r
 366         new_portal->plane = mapplanes[node->planenum];\r
 367         new_portal->onnode = node;\r
 368         new_portal->winding = w;\r
 369         new_portal->compileFlags = node->compileFlags;\r
 370         AddPortalToNodes (new_portal, node->children[0], node->children[1]);\r
 371 }\r
 372 \r
 373 \r
 374 /*\r
 375 ==============\r
 376 SplitNodePortals\r
 377 \r
 378 Move or split the portals that bound node so that the node's\r
 379 children have portals instead of node.\r
 380 ==============\r
 381 */\r
 382 void SplitNodePortals (node_t *node)\r
 383 {\r
 384         portal_t        *p, *next_portal, *new_portal;\r
 385         node_t          *f, *b, *other_node;\r
 386         int                     side;\r
 387         plane_t         *plane;\r
 388         winding_t       *frontwinding, *backwinding;\r
 389 \r
 390         plane = &mapplanes[node->planenum];\r
 391         f = node->children[0];\r
 392         b = node->children[1];\r
 393 \r
 394         for (p = node->portals ; p ; p = next_portal)   \r
 395         {\r
 396                 if (p->nodes[0] == node)\r
 397                         side = 0;\r
 398                 else if (p->nodes[1] == node)\r
 399                         side = 1;\r
 400                 else\r
 401                         Error ("SplitNodePortals: mislinked portal");\r
 402                 next_portal = p->next[side];\r
 403 \r
 404                 other_node = p->nodes[!side];\r
 405                 RemovePortalFromNode (p, p->nodes[0]);\r
 406                 RemovePortalFromNode (p, p->nodes[1]);\r
 407 \r
 408 //\r
 409 // cut the portal into two portals, one on each side of the cut plane\r
 410 //\r
 411                 ClipWindingEpsilon (p->winding, plane->normal, plane->dist,\r
 412                         SPLIT_WINDING_EPSILON, &frontwinding, &backwinding);\r
 413 \r
 414                 if (frontwinding && WindingIsTiny(frontwinding))\r
 415                 {\r
 416                         if (!f->tinyportals)\r
 417                                 VectorCopy(frontwinding->p[0], f->referencepoint);\r
 418                         f->tinyportals++;\r
 419                         if (!other_node->tinyportals)\r
 420                                 VectorCopy(frontwinding->p[0], other_node->referencepoint);\r
 421                         other_node->tinyportals++;\r
 422 \r
 423                         FreeWinding (frontwinding);\r
 424                         frontwinding = NULL;\r
 425                         c_tinyportals++;\r
 426                 }\r
 427 \r
 428                 if (backwinding && WindingIsTiny(backwinding))\r
 429                 {\r
 430                         if (!b->tinyportals)\r
 431                                 VectorCopy(backwinding->p[0], b->referencepoint);\r
 432                         b->tinyportals++;\r
 433                         if (!other_node->tinyportals)\r
 434                                 VectorCopy(backwinding->p[0], other_node->referencepoint);\r
 435                         other_node->tinyportals++;\r
 436 \r
 437                         FreeWinding (backwinding);\r
 438                         backwinding = NULL;\r
 439                         c_tinyportals++;\r
 440                 }\r
 441 \r
 442                 if (!frontwinding && !backwinding)\r
 443                 {       // tiny windings on both sides\r
 444                         continue;\r
 445                 }\r
 446 \r
 447                 if (!frontwinding)\r
 448                 {\r
 449                         FreeWinding (backwinding);\r
 450                         if (side == 0)\r
 451                                 AddPortalToNodes (p, b, other_node);\r
 452                         else\r
 453                                 AddPortalToNodes (p, other_node, b);\r
 454                         continue;\r
 455                 }\r
 456                 if (!backwinding)\r
 457                 {\r
 458                         FreeWinding (frontwinding);\r
 459                         if (side == 0)\r
 460                                 AddPortalToNodes (p, f, other_node);\r
 461                         else\r
 462                                 AddPortalToNodes (p, other_node, f);\r
 463                         continue;\r
 464                 }\r
 465                 \r
 466         // the winding is split\r
 467                 new_portal = AllocPortal ();\r
 468                 *new_portal = *p;\r
 469                 new_portal->winding = backwinding;\r
 470                 FreeWinding (p->winding);\r
 471                 p->winding = frontwinding;\r
 472 \r
 473                 if (side == 0)\r
 474                 {\r
 475                         AddPortalToNodes (p, f, other_node);\r
 476                         AddPortalToNodes (new_portal, b, other_node);\r
 477                 }\r
 478                 else\r
 479                 {\r
 480                         AddPortalToNodes (p, other_node, f);\r
 481                         AddPortalToNodes (new_portal, other_node, b);\r
 482                 }\r
 483         }\r
 484 \r
 485         node->portals = NULL;\r
 486 }\r
 487 \r
 488 \r
 489 /*\r
 490 ================\r
 491 CalcNodeBounds\r
 492 ================\r
 493 */\r
 494 void CalcNodeBounds (node_t *node)\r
 495 {\r
 496         portal_t        *p;\r
 497         int                     s;\r
 498         int                     i;\r
 499 \r
 500         // calc mins/maxs for both leafs and nodes\r
 501         ClearBounds (node->mins, node->maxs);\r
 502         for (p = node->portals ; p ; p = p->next[s])    \r
 503         {\r
 504                 s = (p->nodes[1] == node);\r
 505                 for (i=0 ; i<p->winding->numpoints ; i++)\r
 506                         AddPointToBounds (p->winding->p[i], node->mins, node->maxs);\r
 507         }\r
 508 }\r
 509 \r
 510 /*\r
 511 ==================\r
 512 MakeTreePortals_r\r
 513 ==================\r
 514 */\r
 515 void MakeTreePortals_r (node_t *node)\r
 516 {\r
 517         int             i;\r
 518 \r
 519         CalcNodeBounds (node);\r
 520         if (node->mins[0] >= node->maxs[0])\r
 521         {\r
 522                 Sys_Printf ("WARNING: node without a volume\n");\r
 523                 Sys_Printf("node has %d tiny portals\n", node->tinyportals);\r
 524                 Sys_Printf("node reference point %1.2f %1.2f %1.2f\n", node->referencepoint[0],\r
 525                                                                                                                         node->referencepoint[1],\r
 526                                                                                                                         node->referencepoint[2]);\r
 527         }\r
 528 \r
 529         for (i=0 ; i<3 ; i++)\r
 530         {\r
 531                 if (node->mins[i] < MIN_WORLD_COORD || node->maxs[i] > MAX_WORLD_COORD)\r
 532                 {\r
 533       if(node->portals && node->portals->winding)\r
 534         xml_Winding("WARNING: Node With Unbounded Volume", node->portals->winding->p, node->portals->winding->numpoints, qfalse);\r
 535 \r
 536                         break;\r
 537                 }\r
 538         }\r
 539         if (node->planenum == PLANENUM_LEAF)\r
 540                 return;\r
 541 \r
 542         MakeNodePortal (node);\r
 543         SplitNodePortals (node);\r
 544 \r
 545         MakeTreePortals_r (node->children[0]);\r
 546         MakeTreePortals_r (node->children[1]);\r
 547 }\r
 548 \r
 549 /*\r
 550 ==================\r
 551 MakeTreePortals\r
 552 ==================\r
 553 */\r
 554 void MakeTreePortals (tree_t *tree)\r
 555 {\r
 556         Sys_FPrintf (SYS_VRB, "--- MakeTreePortals ---\n");\r
 557         MakeHeadnodePortals (tree);\r
 558         MakeTreePortals_r (tree->headnode);\r
 559         Sys_FPrintf( SYS_VRB, "%9d tiny portals\n", c_tinyportals );\r
 560         Sys_FPrintf( SYS_VRB, "%9d bad portals\n", c_badportals );      /* ydnar */\r
 561 }\r
 562 \r
 563 /*\r
 564 =========================================================\r
 565 \r
 566 FLOOD ENTITIES\r
 567 \r
 568 =========================================================\r
 569 */\r
 570 \r
 571 int             c_floodedleafs;\r
 572 \r
 573 /*\r
 574 =============\r
 575 FloodPortals_r\r
 576 =============\r
 577 */\r
 578 \r
 579 void FloodPortals_r( node_t *node, int dist, qboolean skybox )\r
 580 {\r
 581         int                     s;\r
 582         portal_t        *p;\r
 583         \r
 584         \r
 585         if( skybox )\r
 586                 node->skybox = skybox;\r
 587         \r
 588         if( node->occupied || node->opaque )\r
 589                 return;\r
 590         \r
 591         c_floodedleafs++;\r
 592         node->occupied = dist;\r
 593         \r
 594         for( p = node->portals; p; p = p->next[ s ] )\r
 595         {\r
 596                 s = (p->nodes[ 1 ] == node);\r
 597                 FloodPortals_r( p->nodes[ !s ], dist + 1, skybox );\r
 598         }\r
 599 }\r
 600 \r
 601 \r
 602 \r
 603 /*\r
 604 =============\r
 605 PlaceOccupant\r
 606 =============\r
 607 */\r
 608 \r
 609 qboolean PlaceOccupant( node_t *headnode, vec3_t origin, entity_t *occupant, qboolean skybox )\r
 610 {\r
 611         vec_t   d;\r
 612         node_t  *node;\r
 613         plane_t *plane;\r
 614         \r
 615         \r
 616         // find the leaf to start in\r
 617         node = headnode;\r
 618         while( node->planenum != PLANENUM_LEAF )\r
 619         {\r
 620                 plane = &mapplanes[ node->planenum ];\r
 621                 d = DotProduct( origin, plane->normal ) - plane->dist;\r
 622                 if( d >= 0 )\r
 623                         node = node->children[ 0 ];\r
 624                 else\r
 625                         node = node->children[ 1 ];\r
 626         }\r
 627         \r
 628         if( node->opaque )\r
 629                 return qfalse;\r
 630         node->occupant = occupant;\r
 631         node->skybox = skybox;\r
 632         \r
 633         FloodPortals_r( node, 1, skybox );\r
 634         \r
 635         return qtrue;\r
 636 }\r
 637 \r
 638 /*\r
 639 =============\r
 640 FloodEntities\r
 641 \r
 642 Marks all nodes that can be reached by entites\r
 643 =============\r
 644 */\r
 645 \r
 646 qboolean FloodEntities( tree_t *tree )\r
 647 {\r
 648         int                     i, s;\r
 649         vec3_t          origin, offset, scale, angles;\r
 650         qboolean        r, inside, tripped, skybox;\r
 651         node_t          *headnode;\r
 652         entity_t        *e;\r
 653         const char      *value;\r
 654         \r
 655         \r
 656         headnode = tree->headnode;\r
 657         Sys_FPrintf( SYS_VRB,"--- FloodEntities ---\n" );\r
 658         inside = qfalse;\r
 659         tree->outside_node.occupied = 0;\r
 660         \r
 661         tripped = qfalse;\r
 662         c_floodedleafs = 0;\r
 663         for( i = 1; i < numEntities; i++ )\r
 664         {\r
 665                 /* get entity */\r
 666                 e = &entities[ i ];\r
 667                 \r
 668                 /* get origin */\r
 669                 GetVectorForKey( e, "origin", origin );\r
 670                 if( VectorCompare( origin, vec3_origin ) ) \r
 671                         continue;\r
 672                 \r
 673                 /* handle skybox entities */\r
 674                 value = ValueForKey( e, "classname" );\r
 675                 if( !Q_stricmp( value, "_skybox" ) )\r
 676                 {\r
 677                         skybox = qtrue;\r
 678                         skyboxPresent = qtrue;\r
 679                         \r
 680                         /* invert origin */\r
 681                         VectorScale( origin, -1.0f, offset );\r
 682                         \r
 683                         /* get scale */\r
 684                         VectorSet( scale, 64.0f, 64.0f, 64.0f );\r
 685                         value = ValueForKey( e, "_scale" );\r
 686                         if( value[ 0 ] != '\0' )\r
 687                         {\r
 688                                 s = sscanf( value, "%f %f %f", &scale[ 0 ], &scale[ 1 ], &scale[ 2 ] );\r
 689                                 if( s == 1 )\r
 690                                 {\r
 691                                         scale[ 1 ] = scale[ 0 ];\r
 692                                         scale[ 2 ] = scale[ 0 ];\r
 693                                 }\r
 694                         }\r
 695                         \r
 696                         /* get "angle" (yaw) or "angles" (pitch yaw roll) */\r
 697                         VectorClear( angles );\r
 698                         angles[ 2 ] = FloatForKey( e, "angle" );\r
 699                         value = ValueForKey( e, "angles" );\r
 700                         if( value[ 0 ] != '\0' )\r
 701                                 sscanf( value, "%f %f %f", &angles[ 1 ], &angles[ 2 ], &angles[ 0 ] );\r
 702                         \r
 703                         /* set transform matrix (thanks spog) */\r
 704                         m4x4_identity( skyboxTransform );\r
 705                         m4x4_pivoted_transform_by_vec3( skyboxTransform, offset, angles, eXYZ, scale, origin );\r
 706                 }\r
 707                 else\r
 708                         skybox = qfalse;\r
 709                 \r
 710                 /* nudge off floor */\r
 711                 origin[ 2 ] += 1;\r
 712                 \r
 713                 /* debugging code */\r
 714                 //%     if( i == 1 )\r
 715                 //%             origin[ 2 ] += 4096;\r
 716                 \r
 717                 /* find leaf */\r
 718                 r = PlaceOccupant( headnode, origin, e, skybox );\r
 719                 if( r )\r
 720                         inside = qtrue;\r
 721                 if( (!r || tree->outside_node.occupied) && !tripped )\r
 722                 {\r
 723                         xml_Select( "Entity leaked", e->mapEntityNum, 0, qfalse );\r
 724                         tripped = qtrue;\r
 725                 }\r
 726         }\r
 727         \r
 728         Sys_FPrintf( SYS_VRB, "%9d flooded leafs\n", c_floodedleafs );\r
 729         \r
 730         if( !inside )\r
 731                 Sys_FPrintf( SYS_VRB, "no entities in open -- no filling\n" );\r
 732         else if( tree->outside_node.occupied )\r
 733                 Sys_FPrintf( SYS_VRB, "entity reached from outside -- no filling\n" );\r
 734         \r
 735         return (qboolean) (inside && !tree->outside_node.occupied);\r
 736 }\r
 737 \r
 738 /*\r
 739 =========================================================\r
 740 \r
 741 FLOOD AREAS\r
 742 \r
 743 =========================================================\r
 744 */\r
 745 \r
 746 int             c_areas;\r
 747 \r
 748 \r
 749 \r
 750 /*\r
 751 FloodAreas_r()\r
 752 floods through leaf portals to tag leafs with an area\r
 753 */\r
 754 \r
 755 void FloodAreas_r( node_t *node )\r
 756 {\r
 757         int                     s;\r
 758         portal_t        *p;\r
 759         brush_t         *b;\r
 760         \r
 761         \r
 762         if( node->areaportal )\r
 763         {\r
 764                 if( node->area == -1 )\r
 765                         node->area = c_areas;\r
 766                 \r
 767                 /* this node is part of an area portal brush */\r
 768                 b = node->brushlist->original;\r
 769 \r
 770                 /* if the current area has already touched this portal, we are done */\r
 771                 if( b->portalareas[ 0 ] == c_areas || b->portalareas[ 1 ] == c_areas )\r
 772                         return;\r
 773                 \r
 774                 // note the current area as bounding the portal\r
 775                 if( b->portalareas[ 1 ] != -1 )\r
 776                 {\r
 777                         Sys_Printf( "WARNING: areaportal brush %i touches > 2 areas\n", b->brushNum );\r
 778                         return;\r
 779                 }\r
 780                 if( b->portalareas[ 0 ] != -1 )\r
 781                         b->portalareas[ 1 ] = c_areas;\r
 782                 else\r
 783                         b->portalareas[ 0 ] = c_areas;\r
 784                 \r
 785                 return;\r
 786         }\r
 787 \r
 788         if( node->area != -1 )\r
 789                 return; \r
 790         if( node->cluster == -1 )\r
 791                 return;\r
 792 \r
 793         node->area = c_areas;\r
 794         \r
 795         /* ydnar: skybox nodes set the skybox area */\r
 796         if( node->skybox )\r
 797                 skyboxArea = c_areas;\r
 798         \r
 799         for( p = node->portals; p; p = p->next[ s ] )\r
 800         {\r
 801                 s = (p->nodes[1] == node);\r
 802                 \r
 803                 /* ydnar: allow areaportal portals to block area flow */\r
 804                 if( p->compileFlags & C_AREAPORTAL )\r
 805                         continue;\r
 806                 \r
 807                 if( !PortalPassable( p ) )\r
 808                         continue;\r
 809                 \r
 810                 FloodAreas_r( p->nodes[ !s ] );\r
 811         }\r
 812 }\r
 813 \r
 814 /*\r
 815 =============\r
 816 FindAreas_r\r
 817 \r
 818 Just decend the tree, and for each node that hasn't had an\r
 819 area set, flood fill out from there\r
 820 =============\r
 821 */\r
 822 void FindAreas_r( node_t *node )\r
 823 {\r
 824         if( node->planenum != PLANENUM_LEAF )\r
 825         {\r
 826                 FindAreas_r( node->children[ 0 ] );\r
 827                 FindAreas_r( node->children[ 1 ] );\r
 828                 return;\r
 829         }\r
 830         \r
 831         if( node->opaque || node->areaportal || node->area != -1 )\r
 832                 return;\r
 833         \r
 834         FloodAreas_r( node );\r
 835         c_areas++;\r
 836 }\r
 837 \r
 838 /*\r
 839 =============\r
 840 CheckAreas_r\r
 841 =============\r
 842 */\r
 843 void CheckAreas_r (node_t *node)\r
 844 {\r
 845         brush_t *b;\r
 846 \r
 847         if (node->planenum != PLANENUM_LEAF)\r
 848         {\r
 849                 CheckAreas_r (node->children[0]);\r
 850                 CheckAreas_r (node->children[1]);\r
 851                 return;\r
 852         }\r
 853 \r
 854         if (node->opaque)\r
 855                 return;\r
 856 \r
 857         if (node->cluster != -1)\r
 858                 if (node->area == -1)\r
 859                         Sys_Printf("WARNING: cluster %d has area set to -1\n", node->cluster);\r
 860         if (node->areaportal)\r
 861         {\r
 862                 b = node->brushlist->original;\r
 863 \r
 864                 // check if the areaportal touches two areas\r
 865                 if (b->portalareas[0] == -1 || b->portalareas[1] == -1)\r
 866                         Sys_Printf ("WARNING: areaportal brush %i doesn't touch two areas\n", b->brushNum);\r
 867         }\r
 868 }\r
 869 \r
 870 \r
 871 \r
 872 /*\r
 873 FloodSkyboxArea_r() - ydnar\r
 874 sets all nodes with the skybox area to skybox\r
 875 */\r
 876 \r
 877 void FloodSkyboxArea_r( node_t *node )\r
 878 {\r
 879         if( skyboxArea < 0 )\r
 880                 return;\r
 881         \r
 882         if( node->planenum != PLANENUM_LEAF )\r
 883         {\r
 884                 FloodSkyboxArea_r( node->children[ 0 ] );\r
 885                 FloodSkyboxArea_r( node->children[ 1 ] );\r
 886                 return;\r
 887         }\r
 888         \r
 889         if( node->opaque || node->area != skyboxArea )\r
 890                 return;\r
 891         \r
 892         node->skybox = qtrue;\r
 893 }\r
 894 \r
 895 \r
 896 \r
 897 /*\r
 898 FloodAreas()\r
 899 mark each leaf with an area, bounded by C_AREAPORTAL\r
 900 */\r
 901 \r
 902 void FloodAreas( tree_t *tree )\r
 903 {\r
 904         Sys_FPrintf( SYS_VRB,"--- FloodAreas ---\n" );\r
 905         FindAreas_r( tree->headnode );\r
 906         \r
 907         /* ydnar: flood all skybox nodes */\r
 908         FloodSkyboxArea_r( tree->headnode );\r
 909         \r
 910         /* check for areaportal brushes that don't touch two areas */\r
 911         /* ydnar: fix this rather than just silence the warnings */\r
 912         //%     CheckAreas_r( tree->headnode );\r
 913 \r
 914         Sys_FPrintf( SYS_VRB, "%9d areas\n", c_areas );\r
 915 }\r
 916 \r
 917 \r
 918 \r
 919 //======================================================\r
 920 \r
 921 int             c_outside;\r
 922 int             c_inside;\r
 923 int             c_solid;\r
 924 \r
 925 void FillOutside_r (node_t *node)\r
 926 {\r
 927         if (node->planenum != PLANENUM_LEAF)\r
 928         {\r
 929                 FillOutside_r (node->children[0]);\r
 930                 FillOutside_r (node->children[1]);\r
 931                 return;\r
 932         }\r
 933 \r
 934         // anything not reachable by an entity\r
 935         // can be filled away\r
 936         if (!node->occupied) {\r
 937                 if ( !node->opaque ) {\r
 938                         c_outside++;\r
 939                         node->opaque = qtrue;\r
 940                 } else {\r
 941                         c_solid++;\r
 942                 }\r
 943         } else {\r
 944                 c_inside++;\r
 945         }\r
 946 \r
 947 }\r
 948 \r
 949 /*\r
 950 =============\r
 951 FillOutside\r
 952 \r
 953 Fill all nodes that can't be reached by entities\r
 954 =============\r
 955 */\r
 956 void FillOutside (node_t *headnode)\r
 957 {\r
 958         c_outside = 0;\r
 959         c_inside = 0;\r
 960         c_solid = 0;\r
 961         Sys_FPrintf( SYS_VRB,"--- FillOutside ---\n" );\r
 962         FillOutside_r( headnode );\r
 963         Sys_FPrintf( SYS_VRB,"%9d solid leafs\n", c_solid );\r
 964         Sys_Printf( "%9d leafs filled\n", c_outside );\r
 965         Sys_FPrintf( SYS_VRB, "%9d inside leafs\n", c_inside );\r
 966 }\r
 967 \r
 968 \r
 969 //==============================================================\r
 970 \r