tools/quake2/q2map/brushbsp.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_nodes;\r
  26 int             c_nonvis;\r
  27 int             c_active_brushes;\r
  28 \r
  29 // if a brush just barely pokes onto the other side,\r
  30 // let it slide by without chopping\r
  31 #define PLANESIDE_EPSILON       0.001\r
  32 //0.1\r
  33 \r
  34 #define PSIDE_FRONT                     1\r
  35 #define PSIDE_BACK                      2\r
  36 #define PSIDE_BOTH                      (PSIDE_FRONT|PSIDE_BACK)\r
  37 #define PSIDE_FACING            4\r
  38 \r
  39 \r
  40 void FindBrushInTree (node_t *node, int brushnum)\r
  41 {\r
  42         bspbrush_t      *b;\r
  43 \r
  44         if (node->planenum == PLANENUM_LEAF)\r
  45         {\r
  46                 for (b=node->brushlist ; b ; b=b->next)\r
  47                         if (b->original->brushnum == brushnum)\r
  48                                 Sys_Printf ("here\n");\r
  49                 return;\r
  50         }\r
  51         FindBrushInTree (node->children[0], brushnum);\r
  52         FindBrushInTree (node->children[1], brushnum);\r
  53 }\r
  54 \r
  55 //==================================================\r
  56 \r
  57 /*\r
  58 ================\r
  59 DrawBrushList\r
  60 ================\r
  61 */\r
  62 void DrawBrushList (bspbrush_t *brush, node_t *node)\r
  63 {\r
  64         int             i;\r
  65         side_t  *s;\r
  66 \r
  67         GLS_BeginScene ();\r
  68         for ( ; brush ; brush=brush->next)\r
  69         {\r
  70                 for (i=0 ; i<brush->numsides ; i++)\r
  71                 {\r
  72                         s = &brush->sides[i];\r
  73                         if (!s->winding)\r
  74                                 continue;\r
  75                         if (s->texinfo == TEXINFO_NODE)\r
  76                                 GLS_Winding (s->winding, 1);\r
  77                         else if (!s->visible)\r
  78                                 GLS_Winding (s->winding, 2);\r
  79                         else\r
  80                                 GLS_Winding (s->winding, 0);\r
  81                 }\r
  82         }\r
  83         GLS_EndScene ();\r
  84 }\r
  85 \r
  86 /*\r
  87 ================\r
  88 WriteBrushList\r
  89 ================\r
  90 */\r
  91 void WriteBrushList (char *name, bspbrush_t *brush, qboolean onlyvis)\r
  92 {\r
  93         int             i;\r
  94         side_t  *s;\r
  95         FILE    *f;\r
  96 \r
  97         Sys_FPrintf( SYS_VRB, "writing %s\n", name);\r
  98         f = SafeOpenWrite (name);\r
  99 \r
 100         for ( ; brush ; brush=brush->next)\r
 101         {\r
 102                 for (i=0 ; i<brush->numsides ; i++)\r
 103                 {\r
 104                         s = &brush->sides[i];\r
 105                         if (!s->winding)\r
 106                                 continue;\r
 107                         if (onlyvis && !s->visible)\r
 108                                 continue;\r
 109                         OutputWinding (brush->sides[i].winding, f);\r
 110                 }\r
 111         }\r
 112 \r
 113         fclose (f);\r
 114 }\r
 115 \r
 116 void PrintBrush (bspbrush_t *brush)\r
 117 {\r
 118         int             i;\r
 119 \r
 120         Sys_Printf ("brush: %p\n", brush);\r
 121         for (i=0;i<brush->numsides ; i++)\r
 122         {\r
 123                 pw(brush->sides[i].winding);\r
 124                 Sys_Printf ("\n");\r
 125         }\r
 126 }\r
 127 \r
 128 /*\r
 129 ==================\r
 130 BoundBrush\r
 131 \r
 132 Sets the mins/maxs based on the windings\r
 133 ==================\r
 134 */\r
 135 void BoundBrush (bspbrush_t *brush)\r
 136 {\r
 137         int                     i, j;\r
 138         winding_t       *w;\r
 139 \r
 140         ClearBounds (brush->mins, brush->maxs);\r
 141         for (i=0 ; i<brush->numsides ; i++)\r
 142         {\r
 143                 w = brush->sides[i].winding;\r
 144                 if (!w)\r
 145                         continue;\r
 146                 for (j=0 ; j<w->numpoints ; j++)\r
 147                         AddPointToBounds (w->p[j], brush->mins, brush->maxs);\r
 148         }\r
 149 }\r
 150 \r
 151 /*\r
 152 ==================\r
 153 CreateBrushWindings\r
 154 \r
 155 ==================\r
 156 */\r
 157 void CreateBrushWindings (bspbrush_t *brush)\r
 158 {\r
 159         int                     i, j;\r
 160         winding_t       *w;\r
 161         side_t          *side;\r
 162         plane_t         *plane;\r
 163 \r
 164         for (i=0 ; i<brush->numsides ; i++)\r
 165         {\r
 166                 side = &brush->sides[i];\r
 167                 plane = &mapplanes[side->planenum];\r
 168                 w = BaseWindingForPlane (plane->normal, plane->dist);\r
 169                 for (j=0 ; j<brush->numsides && w; j++)\r
 170                 {\r
 171                         if (i == j)\r
 172                                 continue;\r
 173                         if (brush->sides[j].bevel)\r
 174                                 continue;\r
 175                         plane = &mapplanes[brush->sides[j].planenum^1];\r
 176                         ChopWindingInPlace (&w, plane->normal, plane->dist, 0); //CLIP_EPSILON);\r
 177                 }\r
 178 \r
 179                 side->winding = w;\r
 180         }\r
 181 \r
 182         BoundBrush (brush);\r
 183 }\r
 184 \r
 185 /*\r
 186 ==================\r
 187 BrushFromBounds\r
 188 \r
 189 Creates a new axial brush\r
 190 ==================\r
 191 */\r
 192 bspbrush_t      *BrushFromBounds (vec3_t mins, vec3_t maxs)\r
 193 {\r
 194         bspbrush_t      *b;\r
 195         int                     i;\r
 196         vec3_t          normal;\r
 197         vec_t           dist;\r
 198 \r
 199         b = AllocBrush (6);\r
 200         b->numsides = 6;\r
 201         for (i=0 ; i<3 ; i++)\r
 202         {\r
 203                 VectorClear (normal);\r
 204                 normal[i] = 1;\r
 205                 dist = maxs[i];\r
 206                 b->sides[i].planenum = FindFloatPlane (normal, dist);\r
 207 \r
 208                 normal[i] = -1;\r
 209                 dist = -mins[i];\r
 210                 b->sides[3+i].planenum = FindFloatPlane (normal, dist);\r
 211         }\r
 212 \r
 213         CreateBrushWindings (b);\r
 214 \r
 215         return b;\r
 216 }\r
 217 \r
 218 /*\r
 219 ==================\r
 220 BrushVolume\r
 221 \r
 222 ==================\r
 223 */\r
 224 vec_t BrushVolume (bspbrush_t *brush)\r
 225 {\r
 226         int                     i;\r
 227         winding_t       *w;\r
 228         vec3_t          corner;\r
 229         vec_t           d, area, volume;\r
 230         plane_t         *plane;\r
 231 \r
 232         if (!brush)\r
 233                 return 0;\r
 234 \r
 235         // grab the first valid point as the corner\r
 236 \r
 237         w = NULL;\r
 238         for (i=0 ; i<brush->numsides ; i++)\r
 239         {\r
 240                 w = brush->sides[i].winding;\r
 241                 if (w)\r
 242                         break;\r
 243         }\r
 244         if (!w)\r
 245                 return 0;\r
 246         VectorCopy (w->p[0], corner);\r
 247 \r
 248         // make tetrahedrons to all other faces\r
 249 \r
 250         volume = 0;\r
 251         for ( ; i<brush->numsides ; i++)\r
 252         {\r
 253                 w = brush->sides[i].winding;\r
 254                 if (!w)\r
 255                         continue;\r
 256                 plane = &mapplanes[brush->sides[i].planenum];\r
 257                 d = -(DotProduct (corner, plane->normal) - plane->dist);\r
 258                 area = WindingArea (w);\r
 259                 volume += d*area;\r
 260         }\r
 261 \r
 262         volume /= 3;\r
 263         return volume;\r
 264 }\r
 265 \r
 266 /*\r
 267 ================\r
 268 CountBrushList\r
 269 ================\r
 270 */\r
 271 int     CountBrushList (bspbrush_t *brushes)\r
 272 {\r
 273         int     c;\r
 274 \r
 275         c = 0;\r
 276         for ( ; brushes ; brushes = brushes->next)\r
 277                 c++;\r
 278         return c;\r
 279 }\r
 280 \r
 281 /*\r
 282 ================\r
 283 AllocTree\r
 284 ================\r
 285 */\r
 286 tree_t *AllocTree (void)\r
 287 {\r
 288         tree_t  *tree;\r
 289 \r
 290         tree = malloc(sizeof(*tree));\r
 291         memset (tree, 0, sizeof(*tree));\r
 292         ClearBounds (tree->mins, tree->maxs);\r
 293 \r
 294         return tree;\r
 295 }\r
 296 \r
 297 /*\r
 298 ================\r
 299 AllocNode\r
 300 ================\r
 301 */\r
 302 node_t *AllocNode (void)\r
 303 {\r
 304         node_t  *node;\r
 305 \r
 306         node = malloc(sizeof(*node));\r
 307         memset (node, 0, sizeof(*node));\r
 308 \r
 309         return node;\r
 310 }\r
 311 \r
 312 \r
 313 /*\r
 314 ================\r
 315 AllocBrush\r
 316 ================\r
 317 */\r
 318 bspbrush_t *AllocBrush (int numsides)\r
 319 {\r
 320         bspbrush_t      *bb;\r
 321         int                     c;\r
 322 \r
 323         c = (int)&(((bspbrush_t *)0)->sides[numsides]);\r
 324         bb = malloc(c);\r
 325         memset (bb, 0, c);\r
 326         if (numthreads == 1)\r
 327                 c_active_brushes++;\r
 328         return bb;\r
 329 }\r
 330 \r
 331 /*\r
 332 ================\r
 333 FreeBrush\r
 334 ================\r
 335 */\r
 336 void FreeBrush (bspbrush_t *brushes)\r
 337 {\r
 338         int                     i;\r
 339 \r
 340         for (i=0 ; i<brushes->numsides ; i++)\r
 341                 if (brushes->sides[i].winding)\r
 342                         FreeWinding(brushes->sides[i].winding);\r
 343         free (brushes);\r
 344         if (numthreads == 1)\r
 345                 c_active_brushes--;\r
 346 }\r
 347 \r
 348 \r
 349 /*\r
 350 ================\r
 351 FreeBrushList\r
 352 ================\r
 353 */\r
 354 void FreeBrushList (bspbrush_t *brushes)\r
 355 {\r
 356         bspbrush_t      *next;\r
 357 \r
 358         for ( ; brushes ; brushes = next)\r
 359         {\r
 360                 next = brushes->next;\r
 361 \r
 362                 FreeBrush (brushes);\r
 363         }               \r
 364 }\r
 365 \r
 366 /*\r
 367 ==================\r
 368 CopyBrush\r
 369 \r
 370 Duplicates the brush, the sides, and the windings\r
 371 ==================\r
 372 */\r
 373 bspbrush_t *CopyBrush (bspbrush_t *brush)\r
 374 {\r
 375         bspbrush_t *newbrush;\r
 376         int                     size;\r
 377         int                     i;\r
 378         \r
 379         size = (int)&(((bspbrush_t *)0)->sides[brush->numsides]);\r
 380 \r
 381         newbrush = AllocBrush (brush->numsides);\r
 382         memcpy (newbrush, brush, size);\r
 383 \r
 384         for (i=0 ; i<brush->numsides ; i++)\r
 385         {\r
 386                 if (brush->sides[i].winding)\r
 387                         newbrush->sides[i].winding = CopyWinding (brush->sides[i].winding);\r
 388         }\r
 389 \r
 390         return newbrush;\r
 391 }\r
 392 \r
 393 \r
 394 /*\r
 395 ==================\r
 396 PointInLeaf\r
 397 \r
 398 ==================\r
 399 */\r
 400 node_t  *PointInLeaf (node_t *node, vec3_t point)\r
 401 {\r
 402         vec_t           d;\r
 403         plane_t         *plane;\r
 404 \r
 405         while (node->planenum != PLANENUM_LEAF)\r
 406         {\r
 407                 plane = &mapplanes[node->planenum];\r
 408                 d = DotProduct (point, plane->normal) - plane->dist;\r
 409                 if (d > 0)\r
 410                         node = node->children[0];\r
 411                 else\r
 412                         node = node->children[1];\r
 413         }\r
 414 \r
 415         return node;\r
 416 }\r
 417 \r
 418 //========================================================\r
 419 \r
 420 /*\r
 421 ==============\r
 422 BoxOnPlaneSide\r
 423 \r
 424 Returns PSIDE_FRONT, PSIDE_BACK, or PSIDE_BOTH\r
 425 ==============\r
 426 */\r
 427 int BoxOnPlaneSide (vec3_t mins, vec3_t maxs, plane_t *plane)\r
 428 {\r
 429         int             side;\r
 430         int             i;\r
 431         vec3_t  corners[2];\r
 432         vec_t   dist1, dist2;\r
 433 \r
 434         // axial planes are easy\r
 435         if (plane->type < 3)\r
 436         {\r
 437                 side = 0;\r
 438                 if (maxs[plane->type] > plane->dist+PLANESIDE_EPSILON)\r
 439                         side |= PSIDE_FRONT;\r
 440                 if (mins[plane->type] < plane->dist-PLANESIDE_EPSILON)\r
 441                         side |= PSIDE_BACK;\r
 442                 return side;\r
 443         }\r
 444 \r
 445         // create the proper leading and trailing verts for the box\r
 446 \r
 447         for (i=0 ; i<3 ; i++)\r
 448         {\r
 449                 if (plane->normal[i] < 0)\r
 450                 {\r
 451                         corners[0][i] = mins[i];\r
 452                         corners[1][i] = maxs[i];\r
 453                 }\r
 454                 else\r
 455                 {\r
 456                         corners[1][i] = mins[i];\r
 457                         corners[0][i] = maxs[i];\r
 458                 }\r
 459         }\r
 460 \r
 461         dist1 = DotProduct (plane->normal, corners[0]) - plane->dist;\r
 462         dist2 = DotProduct (plane->normal, corners[1]) - plane->dist;\r
 463         side = 0;\r
 464         if (dist1 >= PLANESIDE_EPSILON)\r
 465                 side = PSIDE_FRONT;\r
 466         if (dist2 < PLANESIDE_EPSILON)\r
 467                 side |= PSIDE_BACK;\r
 468 \r
 469         return side;\r
 470 }\r
 471 \r
 472 /*\r
 473 ============\r
 474 QuickTestBrushToPlanenum\r
 475 \r
 476 ============\r
 477 */\r
 478 int     QuickTestBrushToPlanenum (bspbrush_t *brush, int planenum, int *numsplits)\r
 479 {\r
 480         int                     i, num;\r
 481         plane_t         *plane;\r
 482         int                     s;\r
 483 \r
 484         *numsplits = 0;\r
 485 \r
 486         // if the brush actually uses the planenum,\r
 487         // we can tell the side for sure\r
 488         for (i=0 ; i<brush->numsides ; i++)\r
 489         {\r
 490                 num = brush->sides[i].planenum;\r
 491                 if (num >= 0x10000)\r
 492                         Error ("bad planenum");\r
 493                 if (num == planenum)\r
 494                         return PSIDE_BACK|PSIDE_FACING;\r
 495                 if (num == (planenum ^ 1) )\r
 496                         return PSIDE_FRONT|PSIDE_FACING;\r
 497         }\r
 498 \r
 499         // box on plane side\r
 500         plane = &mapplanes[planenum];\r
 501         s = BoxOnPlaneSide (brush->mins, brush->maxs, plane);\r
 502 \r
 503         // if both sides, count the visible faces split\r
 504         if (s == PSIDE_BOTH)\r
 505         {\r
 506                 *numsplits += 3;\r
 507         }\r
 508 \r
 509         return s;\r
 510 }\r
 511 \r
 512 /*\r
 513 ============\r
 514 TestBrushToPlanenum\r
 515 \r
 516 ============\r
 517 */\r
 518 int     TestBrushToPlanenum (bspbrush_t *brush, int planenum,\r
 519                                                  int *numsplits, qboolean *hintsplit, int *epsilonbrush)\r
 520 {\r
 521         int                     i, j, num;\r
 522         plane_t         *plane;\r
 523         int                     s;\r
 524         winding_t       *w;\r
 525         vec_t           d, d_front, d_back;\r
 526         int                     front, back;\r
 527 \r
 528         *numsplits = 0;\r
 529         *hintsplit = false;\r
 530 \r
 531         // if the brush actually uses the planenum,\r
 532         // we can tell the side for sure\r
 533         for (i=0 ; i<brush->numsides ; i++)\r
 534         {\r
 535                 num = brush->sides[i].planenum;\r
 536                 if (num >= 0x10000)\r
 537                         Error ("bad planenum");\r
 538                 if (num == planenum)\r
 539                         return PSIDE_BACK|PSIDE_FACING;\r
 540                 if (num == (planenum ^ 1) )\r
 541                         return PSIDE_FRONT|PSIDE_FACING;\r
 542         }\r
 543 \r
 544         // box on plane side\r
 545         plane = &mapplanes[planenum];\r
 546         s = BoxOnPlaneSide (brush->mins, brush->maxs, plane);\r
 547 \r
 548         if (s != PSIDE_BOTH)\r
 549                 return s;\r
 550 \r
 551 // if both sides, count the visible faces split\r
 552         d_front = d_back = 0;\r
 553 \r
 554         for (i=0 ; i<brush->numsides ; i++)\r
 555         {\r
 556                 if (brush->sides[i].texinfo == TEXINFO_NODE)\r
 557                         continue;               // on node, don't worry about splits\r
 558                 if (!brush->sides[i].visible)\r
 559                         continue;               // we don't care about non-visible\r
 560                 w = brush->sides[i].winding;\r
 561                 if (!w)\r
 562                         continue;\r
 563                 front = back = 0;\r
 564                 for (j=0 ; j<w->numpoints; j++)\r
 565                 {\r
 566                         d = DotProduct (w->p[j], plane->normal) - plane->dist;\r
 567                         if (d > d_front)\r
 568                                 d_front = d;\r
 569                         if (d < d_back)\r
 570                                 d_back = d;\r
 571 \r
 572                         if (d > 0.1) // PLANESIDE_EPSILON)\r
 573                                 front = 1;\r
 574                         if (d < -0.1) // PLANESIDE_EPSILON)\r
 575                                 back = 1;\r
 576                 }\r
 577                 if (front && back)\r
 578                 {\r
 579                         if ( !(brush->sides[i].surf & SURF_SKIP) )\r
 580                         {\r
 581                                 (*numsplits)++;\r
 582                                 if (brush->sides[i].surf & SURF_HINT)\r
 583                                         *hintsplit = true;\r
 584                         }\r
 585                 }\r
 586         }\r
 587 \r
 588         if ( (d_front > 0.0 && d_front < 1.0)\r
 589                 || (d_back < 0.0 && d_back > -1.0) )\r
 590                 (*epsilonbrush)++;\r
 591 \r
 592 #if 0\r
 593         if (*numsplits == 0)\r
 594         {       //      didn't really need to be split\r
 595                 if (front)\r
 596                         s = PSIDE_FRONT;\r
 597                 else if (back)\r
 598                         s = PSIDE_BACK;\r
 599                 else\r
 600                         s = 0;\r
 601         }\r
 602 #endif\r
 603 \r
 604         return s;\r
 605 }\r
 606 \r
 607 //========================================================\r
 608 \r
 609 /*\r
 610 ================\r
 611 WindingIsTiny\r
 612 \r
 613 Returns true if the winding would be crunched out of\r
 614 existance by the vertex snapping.\r
 615 ================\r
 616 */\r
 617 #define EDGE_LENGTH     0.2\r
 618 qboolean WindingIsTiny (winding_t *w)\r
 619 {\r
 620 #if 0\r
 621         if (WindingArea (w) < 1)\r
 622                 return true;\r
 623         return false;\r
 624 #else\r
 625         int             i, j;\r
 626         vec_t   len;\r
 627         vec3_t  delta;\r
 628         int             edges;\r
 629 \r
 630         edges = 0;\r
 631         for (i=0 ; i<w->numpoints ; i++)\r
 632         {\r
 633                 j = i == w->numpoints - 1 ? 0 : i+1;\r
 634                 VectorSubtract (w->p[j], w->p[i], delta);\r
 635                 len = (float) VectorLength (delta);\r
 636                 if (len > EDGE_LENGTH)\r
 637                 {\r
 638                         if (++edges == 3)\r
 639                                 return false;\r
 640                 }\r
 641         }\r
 642         return true;\r
 643 #endif\r
 644 }\r
 645 \r
 646 /*\r
 647 ================\r
 648 WindingIsHuge\r
 649 \r
 650 Returns true if the winding still has one of the points\r
 651 from basewinding for plane\r
 652 ================\r
 653 */\r
 654 qboolean WindingIsHuge (winding_t *w)\r
 655 {\r
 656         int             i, j;\r
 657 \r
 658         for (i=0 ; i<w->numpoints ; i++)\r
 659         {\r
 660                 for (j=0 ; j<3 ; j++)\r
 661                         if (w->p[i][j] < -8000 || w->p[i][j] > 8000)\r
 662                                 return true;\r
 663         }\r
 664         return false;\r
 665 }\r
 666 \r
 667 //============================================================\r
 668 \r
 669 /*\r
 670 ================\r
 671 Leafnode\r
 672 ================\r
 673 */\r
 674 void LeafNode (node_t *node, bspbrush_t *brushes)\r
 675 {\r
 676         bspbrush_t      *b;\r
 677         int                     i;\r
 678 \r
 679         node->planenum = PLANENUM_LEAF;\r
 680         node->contents = 0;\r
 681 \r
 682         for (b=brushes ; b ; b=b->next)\r
 683         {\r
 684                 // if the brush is solid and all of its sides are on nodes,\r
 685                 // it eats everything\r
 686                 if (b->original->contents & CONTENTS_SOLID)\r
 687                 {\r
 688                         for (i=0 ; i<b->numsides ; i++)\r
 689                                 if (b->sides[i].texinfo != TEXINFO_NODE)\r
 690                                         break;\r
 691                         if (i == b->numsides)\r
 692                         {\r
 693                                 node->contents = CONTENTS_SOLID;\r
 694                                 break;\r
 695                         }\r
 696                 }\r
 697                 node->contents |= b->original->contents;\r
 698         }\r
 699 \r
 700         node->brushlist = brushes;\r
 701 }\r
 702 \r
 703 \r
 704 //============================================================\r
 705 \r
 706 void CheckPlaneAgainstParents (int pnum, node_t *node)\r
 707 {\r
 708         node_t  *p;\r
 709 \r
 710         for (p=node->parent ; p ; p=p->parent)\r
 711         {\r
 712                 if (p->planenum == pnum)\r
 713                         Error ("Tried parent");\r
 714         }\r
 715 }\r
 716 \r
 717 qboolean CheckPlaneAgainstVolume (int pnum, node_t *node)\r
 718 {\r
 719         bspbrush_t      *front, *back;\r
 720         qboolean        good;\r
 721 \r
 722         SplitBrush (node->volume, pnum, &front, &back);\r
 723 \r
 724         good = (front && back);\r
 725 \r
 726         if (front)\r
 727                 FreeBrush (front);\r
 728         if (back)\r
 729                 FreeBrush (back);\r
 730 \r
 731         return good;\r
 732 }\r
 733 \r
 734 /*\r
 735 ================\r
 736 SelectSplitSide\r
 737 \r
 738 Using a hueristic, choses one of the sides out of the brushlist\r
 739 to partition the brushes with.\r
 740 Returns NULL if there are no valid planes to split with..\r
 741 ================\r
 742 */\r
 743 side_t *SelectSplitSide (bspbrush_t *brushes, node_t *node)\r
 744 {\r
 745         int                     value, bestvalue;\r
 746         bspbrush_t      *brush, *test;\r
 747         side_t          *side, *bestside;\r
 748         int                     i, j, pass, numpasses;\r
 749         int                     pnum;\r
 750         int                     s;\r
 751         int                     front, back, both, facing, splits;\r
 752         int                     bsplits;\r
 753         int                     bestsplits;\r
 754         int                     epsilonbrush;\r
 755         qboolean        hintsplit;\r
 756 \r
 757         bestside = NULL;\r
 758         bestvalue = -99999;\r
 759         bestsplits = 0;\r
 760 \r
 761         // the search order goes: visible-structural, visible-detail,\r
 762         // nonvisible-structural, nonvisible-detail.\r
 763         // If any valid plane is available in a pass, no further\r
 764         // passes will be tried.\r
 765         numpasses = 4;\r
 766         for (pass = 0 ; pass < numpasses ; pass++)\r
 767         {\r
 768                 for (brush = brushes ; brush ; brush=brush->next)\r
 769                 {\r
 770                         if ( (pass & 1) && !(brush->original->contents & CONTENTS_DETAIL) )\r
 771                                 continue;\r
 772                         if ( !(pass & 1) && (brush->original->contents & CONTENTS_DETAIL) )\r
 773                                 continue;\r
 774                         for (i=0 ; i<brush->numsides ; i++)\r
 775                         {\r
 776                                 side = brush->sides + i;\r
 777                                 if (side->bevel)\r
 778                                         continue;       // never use a bevel as a spliter\r
 779                                 if (!side->winding)\r
 780                                         continue;       // nothing visible, so it can't split\r
 781                                 if (side->texinfo == TEXINFO_NODE)\r
 782                                         continue;       // allready a node splitter\r
 783                                 if (side->tested)\r
 784                                         continue;       // we allready have metrics for this plane\r
 785                                 if (side->surf & SURF_SKIP)\r
 786                                         continue;       // skip surfaces are never chosen\r
 787                                 if ( side->visible ^ (pass<2) )\r
 788                                         continue;       // only check visible faces on first pass\r
 789 \r
 790                                 pnum = side->planenum;\r
 791                                 pnum &= ~1;     // allways use positive facing plane\r
 792 \r
 793                                 CheckPlaneAgainstParents (pnum, node);\r
 794 \r
 795                                 if (!CheckPlaneAgainstVolume (pnum, node))\r
 796                                         continue;       // would produce a tiny volume\r
 797 \r
 798                                 front = 0;\r
 799                                 back = 0;\r
 800                                 both = 0;\r
 801                                 facing = 0;\r
 802                                 splits = 0;\r
 803                                 epsilonbrush = 0;\r
 804 \r
 805                                 for (test = brushes ; test ; test=test->next)\r
 806                                 {\r
 807                                         s = TestBrushToPlanenum (test, pnum, &bsplits, &hintsplit, &epsilonbrush);\r
 808 \r
 809                                         splits += bsplits;\r
 810                                         if (bsplits && (s&PSIDE_FACING) )\r
 811                                                 Error ("PSIDE_FACING with splits");\r
 812 \r
 813                                         test->testside = s;\r
 814                                         // if the brush shares this face, don't bother\r
 815                                         // testing that facenum as a splitter again\r
 816                                         if (s & PSIDE_FACING)\r
 817                                         {\r
 818                                                 facing++;\r
 819                                                 for (j=0 ; j<test->numsides ; j++)\r
 820                                                 {\r
 821                                                         if ( (test->sides[j].planenum&~1) == pnum)\r
 822                                                                 test->sides[j].tested = true;\r
 823                                                 }\r
 824                                         }\r
 825                                         if (s & PSIDE_FRONT)\r
 826                                                 front++;\r
 827                                         if (s & PSIDE_BACK)\r
 828                                                 back++;\r
 829                                         if (s == PSIDE_BOTH)\r
 830                                                 both++;\r
 831                                 }\r
 832 \r
 833                                 // give a value estimate for using this plane\r
 834 \r
 835                                 value =  5*facing - 5*splits - abs(front-back);\r
 836 //                                      value =  -5*splits;\r
 837 //                                      value =  5*facing - 5*splits;\r
 838                                 if (mapplanes[pnum].type < 3)\r
 839                                         value+=5;               // axial is better\r
 840                                 value -= epsilonbrush*1000;     // avoid!\r
 841 \r
 842                                 // never split a hint side except with another hint\r
 843                                 if (hintsplit && !(side->surf & SURF_HINT) )\r
 844                                         value = -9999999;\r
 845 \r
 846                                 // save off the side test so we don't need\r
 847                                 // to recalculate it when we actually seperate\r
 848                                 // the brushes\r
 849                                 if (value > bestvalue)\r
 850                                 {\r
 851                                         bestvalue = value;\r
 852                                         bestside = side;\r
 853                                         bestsplits = splits;\r
 854                                         for (test = brushes ; test ; test=test->next)\r
 855                                                 test->side = test->testside;\r
 856                                 }\r
 857                         }\r
 858                 }\r
 859 \r
 860                 // if we found a good plane, don't bother trying any\r
 861                 // other passes\r
 862                 if (bestside)\r
 863                 {\r
 864                         if (pass > 1)\r
 865                         {\r
 866                                 if (numthreads == 1)\r
 867                                         c_nonvis++;\r
 868                         }\r
 869                         if (pass > 0)\r
 870                                 node->detail_seperator = true;  // not needed for vis\r
 871                         break;\r
 872                 }\r
 873         }\r
 874 \r
 875         //\r
 876         // clear all the tested flags we set\r
 877         //\r
 878         for (brush = brushes ; brush ; brush=brush->next)\r
 879         {\r
 880                 for (i=0 ; i<brush->numsides ; i++)\r
 881                         brush->sides[i].tested = false;\r
 882         }\r
 883 \r
 884         return bestside;\r
 885 }\r
 886 \r
 887 \r
 888 /*\r
 889 ==================\r
 890 BrushMostlyOnSide\r
 891 \r
 892 ==================\r
 893 */\r
 894 int BrushMostlyOnSide (bspbrush_t *brush, plane_t *plane)\r
 895 {\r
 896         int                     i, j;\r
 897         winding_t       *w;\r
 898         vec_t           d, max;\r
 899         int                     side;\r
 900 \r
 901         max = 0;\r
 902         side = PSIDE_FRONT;\r
 903         for (i=0 ; i<brush->numsides ; i++)\r
 904         {\r
 905                 w = brush->sides[i].winding;\r
 906                 if (!w)\r
 907                         continue;\r
 908                 for (j=0 ; j<w->numpoints ; j++)\r
 909                 {\r
 910                         d = DotProduct (w->p[j], plane->normal) - plane->dist;\r
 911                         if (d > max)\r
 912                         {\r
 913                                 max = d;\r
 914                                 side = PSIDE_FRONT;\r
 915                         }\r
 916                         if (-d > max)\r
 917                         {\r
 918                                 max = -d;\r
 919                                 side = PSIDE_BACK;\r
 920                         }\r
 921                 }\r
 922         }\r
 923         return side;\r
 924 }\r
 925 \r
 926 /*\r
 927 ================\r
 928 SplitBrush\r
 929 \r
 930 Generates two new brushes, leaving the original\r
 931 unchanged\r
 932 ================\r
 933 */\r
 934 void SplitBrush (bspbrush_t *brush, int planenum,\r
 935         bspbrush_t **front, bspbrush_t **back)\r
 936 {\r
 937         bspbrush_t      *b[2];\r
 938         int                     i, j;\r
 939         winding_t       *w, *cw[2], *midwinding;\r
 940         plane_t         *plane, *plane2;\r
 941         side_t          *s, *cs;\r
 942         float           d, d_front, d_back;\r
 943 \r
 944         *front = *back = NULL;\r
 945         plane = &mapplanes[planenum];\r
 946 \r
 947         // check all points\r
 948         d_front = d_back = 0;\r
 949         for (i=0 ; i<brush->numsides ; i++)\r
 950         {\r
 951                 w = brush->sides[i].winding;\r
 952                 if (!w)\r
 953                         continue;\r
 954                 for (j=0 ; j<w->numpoints ; j++)\r
 955                 {\r
 956                         d = DotProduct (w->p[j], plane->normal) - plane->dist;\r
 957                         if (d > 0 && d > d_front)\r
 958                                 d_front = d;\r
 959                         if (d < 0 && d < d_back)\r
 960                                 d_back = d;\r
 961                 }\r
 962         }\r
 963         if (d_front < 0.1) // PLANESIDE_EPSILON)\r
 964         {       // only on back\r
 965                 *back = CopyBrush (brush);\r
 966                 return;\r
 967         }\r
 968         if (d_back > -0.1) // PLANESIDE_EPSILON)\r
 969         {       // only on front\r
 970                 *front = CopyBrush (brush);\r
 971                 return;\r
 972         }\r
 973 \r
 974         // create a new winding from the split plane\r
 975 \r
 976         w = BaseWindingForPlane (plane->normal, plane->dist);\r
 977         for (i=0 ; i<brush->numsides && w ; i++)\r
 978         {\r
 979                 plane2 = &mapplanes[brush->sides[i].planenum ^ 1];\r
 980                 ChopWindingInPlace (&w, plane2->normal, plane2->dist, 0); // PLANESIDE_EPSILON);\r
 981         }\r
 982 \r
 983         if (!w || WindingIsTiny (w) )\r
 984         {       // the brush isn't really split\r
 985                 int             side;\r
 986 \r
 987                 side = BrushMostlyOnSide (brush, plane);\r
 988                 if (side == PSIDE_FRONT)\r
 989                         *front = CopyBrush (brush);\r
 990                 if (side == PSIDE_BACK)\r
 991                         *back = CopyBrush (brush);\r
 992                 return;\r
 993         }\r
 994 \r
 995         if (WindingIsHuge (w))\r
 996         {\r
 997                 Sys_FPrintf( SYS_VRB, "WARNING: huge winding\n");\r
 998         }\r
 999 \r
1000         midwinding = w;\r
1001 \r
1002         // split it for real\r
1003 \r
1004         for (i=0 ; i<2 ; i++)\r
1005         {\r
1006                 b[i] = AllocBrush (brush->numsides+1);\r
1007                 b[i]->original = brush->original;\r
1008         }\r
1009 \r
1010         // split all the current windings\r
1011 \r
1012         for (i=0 ; i<brush->numsides ; i++)\r
1013         {\r
1014                 s = &brush->sides[i];\r
1015                 w = s->winding;\r
1016                 if (!w)\r
1017                         continue;\r
1018                 ClipWindingEpsilon (w, plane->normal, plane->dist,\r
1019                         0 /*PLANESIDE_EPSILON*/, &cw[0], &cw[1]);\r
1020                 for (j=0 ; j<2 ; j++)\r
1021                 {\r
1022                         if (!cw[j])\r
1023                                 continue;\r
1024 #if 0\r
1025                         if (WindingIsTiny (cw[j]))\r
1026                         {\r
1027                                 FreeWinding (cw[j]);\r
1028                                 continue;\r
1029                         }\r
1030 #endif\r
1031                         cs = &b[j]->sides[b[j]->numsides];\r
1032                         b[j]->numsides++;\r
1033                         *cs = *s;\r
1034 //                      cs->planenum = s->planenum;\r
1035 //                      cs->texinfo = s->texinfo;\r
1036 //                      cs->visible = s->visible;\r
1037 //                      cs->original = s->original;\r
1038                         cs->winding = cw[j];\r
1039                         cs->tested = false;\r
1040                 }\r
1041         }\r
1042 \r
1043 \r
1044         // see if we have valid polygons on both sides\r
1045 \r
1046         for (i=0 ; i<2 ; i++)\r
1047         {\r
1048                 BoundBrush (b[i]);\r
1049                 for (j=0 ; j<3 ; j++)\r
1050                 {\r
1051                         if (b[i]->mins[j] < -4096 || b[i]->maxs[j] > 4096)\r
1052                         {\r
1053                                 Sys_FPrintf( SYS_VRB, "bogus brush after clip\n");\r
1054                                 break;\r
1055                         }\r
1056                 }\r
1057 \r
1058                 if (b[i]->numsides < 3 || j < 3)\r
1059                 {\r
1060                         FreeBrush (b[i]);\r
1061                         b[i] = NULL;\r
1062                 }\r
1063         }\r
1064 \r
1065         if ( !(b[0] && b[1]) )\r
1066         {\r
1067                 if (!b[0] && !b[1])\r
1068                         Sys_FPrintf( SYS_VRB, "split removed brush\n");\r
1069                 else\r
1070                         Sys_FPrintf( SYS_VRB, "split not on both sides\n");\r
1071                 if (b[0])\r
1072                 {\r
1073                         FreeBrush (b[0]);\r
1074                         *front = CopyBrush (brush);\r
1075                 }\r
1076                 if (b[1])\r
1077                 {\r
1078                         FreeBrush (b[1]);\r
1079                         *back = CopyBrush (brush);\r
1080                 }\r
1081                 return;\r
1082         }\r
1083 \r
1084         // add the midwinding to both sides\r
1085         for (i=0 ; i<2 ; i++)\r
1086         {\r
1087                 cs = &b[i]->sides[b[i]->numsides];\r
1088                 b[i]->numsides++;\r
1089 \r
1090                 cs->planenum = planenum^i^1;\r
1091                 cs->texinfo = TEXINFO_NODE;\r
1092                 cs->visible = false;\r
1093                 cs->tested = false;\r
1094                 if (i==0)\r
1095                         cs->winding = CopyWinding (midwinding);\r
1096                 else\r
1097                         cs->winding = midwinding;\r
1098         }\r
1099 \r
1100 {\r
1101         vec_t   v1;\r
1102         int             i;\r
1103 \r
1104         for (i=0 ; i<2 ; i++)\r
1105         {\r
1106                 v1 = BrushVolume (b[i]);\r
1107                 if (v1 < 1.0)\r
1108                 {\r
1109                         FreeBrush (b[i]);\r
1110                         b[i] = NULL;\r
1111                         Sys_FPrintf( SYS_VRB, "tiny volume after clip\n");\r
1112                 }\r
1113         }\r
1114 }\r
1115 \r
1116         *front = b[0];\r
1117         *back = b[1];\r
1118 }\r
1119 \r
1120 /*\r
1121 ================\r
1122 SplitBrushList\r
1123 ================\r
1124 */\r
1125 void SplitBrushList (bspbrush_t *brushes, \r
1126         node_t *node, bspbrush_t **front, bspbrush_t **back)\r
1127 {\r
1128         bspbrush_t      *brush, *newbrush, *newbrush2;\r
1129         side_t          *side;\r
1130         int                     sides;\r
1131         int                     i;\r
1132 \r
1133         *front = *back = NULL;\r
1134 \r
1135         for (brush = brushes ; brush ; brush=brush->next)\r
1136         {\r
1137                 sides = brush->side;\r
1138 \r
1139                 if (sides == PSIDE_BOTH)\r
1140                 {       // split into two brushes\r
1141                         SplitBrush (brush, node->planenum, &newbrush, &newbrush2);\r
1142                         if (newbrush)\r
1143                         {\r
1144                                 newbrush->next = *front;\r
1145                                 *front = newbrush;\r
1146                         }\r
1147                         if (newbrush2)\r
1148                         {\r
1149                                 newbrush2->next = *back;\r
1150                                 *back = newbrush2;\r
1151                         }\r
1152                         continue;\r
1153                 }\r
1154 \r
1155                 newbrush = CopyBrush (brush);\r
1156 \r
1157                 // if the planenum is actualy a part of the brush\r
1158                 // find the plane and flag it as used so it won't be tried\r
1159                 // as a splitter again\r
1160                 if (sides & PSIDE_FACING)\r
1161                 {\r
1162                         for (i=0 ; i<newbrush->numsides ; i++)\r
1163                         {\r
1164                                 side = newbrush->sides + i;\r
1165                                 if ( (side->planenum& ~1) == node->planenum)\r
1166                                         side->texinfo = TEXINFO_NODE;\r
1167                         }\r
1168                 }\r
1169 \r
1170 \r
1171                 if (sides & PSIDE_FRONT)\r
1172                 {\r
1173                         newbrush->next = *front;\r
1174                         *front = newbrush;\r
1175                         continue;\r
1176                 }\r
1177                 if (sides & PSIDE_BACK)\r
1178                 {\r
1179                         newbrush->next = *back;\r
1180                         *back = newbrush;\r
1181                         continue;\r
1182                 }\r
1183         }\r
1184 }\r
1185 \r
1186 \r
1187 /*\r
1188 ================\r
1189 BuildTree_r\r
1190 ================\r
1191 */\r
1192 node_t *BuildTree_r (node_t *node, bspbrush_t *brushes)\r
1193 {\r
1194         node_t          *newnode;\r
1195         side_t          *bestside;\r
1196         int                     i;\r
1197         bspbrush_t      *children[2];\r
1198 \r
1199         if (numthreads == 1)\r
1200                 c_nodes++;\r
1201 \r
1202         if (drawflag)\r
1203                 DrawBrushList (brushes, node);\r
1204 \r
1205         // find the best plane to use as a splitter\r
1206         bestside = SelectSplitSide (brushes, node);\r
1207         if (!bestside)\r
1208         {\r
1209                 // leaf node\r
1210                 node->side = NULL;\r
1211                 node->planenum = -1;\r
1212                 LeafNode (node, brushes);\r
1213                 return node;\r
1214         }\r
1215 \r
1216         // this is a splitplane node\r
1217         node->side = bestside;\r
1218         node->planenum = bestside->planenum & ~1;       // always use front facing\r
1219 \r
1220         SplitBrushList (brushes, node, &children[0], &children[1]);\r
1221         FreeBrushList (brushes);\r
1222 \r
1223         // allocate children before recursing\r
1224         for (i=0 ; i<2 ; i++)\r
1225         {\r
1226                 newnode = AllocNode ();\r
1227                 newnode->parent = node;\r
1228                 node->children[i] = newnode;\r
1229         }\r
1230 \r
1231         SplitBrush (node->volume, node->planenum, &node->children[0]->volume,\r
1232                 &node->children[1]->volume);\r
1233 \r
1234         // recursively process children\r
1235         for (i=0 ; i<2 ; i++)\r
1236         {\r
1237                 node->children[i] = BuildTree_r (node->children[i], children[i]);\r
1238         }\r
1239 \r
1240         return node;\r
1241 }\r
1242 \r
1243 //===========================================================\r
1244 \r
1245 /*\r
1246 =================\r
1247 BrushBSP\r
1248 \r
1249 The incoming list will be freed before exiting\r
1250 =================\r
1251 */\r
1252 tree_t *BrushBSP (bspbrush_t *brushlist, vec3_t mins, vec3_t maxs)\r
1253 {\r
1254         node_t          *node;\r
1255         bspbrush_t      *b;\r
1256         int                     c_faces, c_nonvisfaces;\r
1257         int                     c_brushes;\r
1258         tree_t          *tree;\r
1259         int                     i;\r
1260         vec_t           volume;\r
1261 \r
1262         Sys_FPrintf( SYS_VRB, "--- BrushBSP ---\n");\r
1263 \r
1264         tree = AllocTree ();\r
1265 \r
1266         c_faces = 0;\r
1267         c_nonvisfaces = 0;\r
1268         c_brushes = 0;\r
1269         for (b=brushlist ; b ; b=b->next)\r
1270         {\r
1271                 c_brushes++;\r
1272 \r
1273                 volume = BrushVolume (b);\r
1274                 if (volume < microvolume)\r
1275                 {\r
1276                         Sys_Printf ("WARNING: entity %i, brush %i: microbrush\n",\r
1277                                 b->original->entitynum, b->original->brushnum);\r
1278                 }\r
1279 \r
1280                 for (i=0 ; i<b->numsides ; i++)\r
1281                 {\r
1282                         if (b->sides[i].bevel)\r
1283                                 continue;\r
1284                         if (!b->sides[i].winding)\r
1285                                 continue;\r
1286                         if (b->sides[i].texinfo == TEXINFO_NODE)\r
1287                                 continue;\r
1288                         if (b->sides[i].visible)\r
1289                                 c_faces++;\r
1290                         else\r
1291                                 c_nonvisfaces++;\r
1292                 }\r
1293 \r
1294                 AddPointToBounds (b->mins, tree->mins, tree->maxs);\r
1295                 AddPointToBounds (b->maxs, tree->mins, tree->maxs);\r
1296         }\r
1297 \r
1298         Sys_FPrintf( SYS_VRB, "%5i brushes\n", c_brushes);\r
1299         Sys_FPrintf( SYS_VRB, "%5i visible faces\n", c_faces);\r
1300         Sys_FPrintf( SYS_VRB, "%5i nonvisible faces\n", c_nonvisfaces);\r
1301 \r
1302         c_nodes = 0;\r
1303         c_nonvis = 0;\r
1304         node = AllocNode ();\r
1305 \r
1306         node->volume = BrushFromBounds (mins, maxs);\r
1307 \r
1308         tree->headnode = node;\r
1309 \r
1310         node = BuildTree_r (node, brushlist);\r
1311         Sys_FPrintf( SYS_VRB, "%5i visible nodes\n", c_nodes/2 - c_nonvis);\r
1312         Sys_FPrintf( SYS_VRB, "%5i nonvis nodes\n", c_nonvis);\r
1313         Sys_FPrintf( SYS_VRB, "%5i leafs\n", (c_nodes+1)/2);\r
1314 #if 0\r
1315 {       // debug code\r
1316 static node_t   *tnode;\r
1317 vec3_t  p;\r
1318 \r
1319 p[0] = -1469;\r
1320 p[1] = -118;\r
1321 p[2] = 119;\r
1322 tnode = PointInLeaf (tree->headnode, p);\r
1323 Sys_Printf ("contents: %i\n", tnode->contents);\r
1324 p[0] = 0;\r
1325 }\r
1326 #endif\r
1327         return tree;\r
1328 }\r
1329 \r