tools/quake2/q2map/brushbsp.c

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