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

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