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