tools/quake3/q3map2/brush.c

   1 /* -------------------------------------------------------------------------------
   2
   3    Copyright (C) 1999-2007 id Software, Inc. and contributors.
   4    For a list of contributors, see the accompanying CONTRIBUTORS file.
   5
   6    This file is part of GtkRadiant.
   7
   8    GtkRadiant is free software; you can redistribute it and/or modify
   9    it under the terms of the GNU General Public License as published by
  10    the Free Software Foundation; either version 2 of the License, or
  11    (at your option) any later version.
  12
  13    GtkRadiant is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16    GNU General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with GtkRadiant; if not, write to the Free Software
  20    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  21
  22    ----------------------------------------------------------------------------------
  23
  24    This code has been altered significantly from its original form, to support
  25    several games based on the Quake III Arena engine, in the form of "Q3Map2."
  26
  27    ------------------------------------------------------------------------------- */
  28
  29
  30
  31 /* marker */
  32 #define BRUSH_C
  33
  34
  35
  36 /* dependencies */
  37 #include "q3map2.h"
  38
  39
  40
  41 /* -------------------------------------------------------------------------------
  42
  43    functions
  44
  45    ------------------------------------------------------------------------------- */
  46
  47 /*
  48    AllocSideRef() - ydnar
  49    allocates and assigns a brush side reference
  50  */
  51
  52 sideRef_t *AllocSideRef( side_t *side, sideRef_t *next ){
  53         sideRef_t *sideRef;
  54
  55
  56         /* dummy check */
  57         if ( side == NULL ) {
  58                 return next;
  59         }
  60
  61         /* allocate and return */
  62         sideRef = safe_malloc( sizeof( *sideRef ) );
  63         sideRef->side = side;
  64         sideRef->next = next;
  65         return sideRef;
  66 }
  67
  68
  69
  70 /*
  71    CountBrushList()
  72    counts the number of brushes in a brush linked list
  73  */
  74
  75 int CountBrushList( brush_t *brushes ){
  76         int c = 0;
  77
  78
  79         /* count brushes */
  80         for ( ; brushes != NULL; brushes = brushes->next )
  81                 c++;
  82         return c;
  83 }
  84
  85
  86
  87 /*
  88    AllocBrush()
  89    allocates a new brush
  90  */
  91
  92 brush_t *AllocBrush( int numSides ){
  93         brush_t     *bb;
  94         size_t c;
  95
  96         /* allocate and clear */
  97         /*if ( numSides <= 0 ) {
  98                 Error( "AllocBrush called with numsides = %d", numSides );
  99         }
 100         c = (size_t)&( ( (brush_t*) 0 )->sides[ numSides ] );*/
 101         c = sizeof(*bb) + (numSides > 6 ? sizeof(side_t)*(numSides - 6) : 0);
 102         bb = safe_malloc0( c );
 103         if ( numthreads == 1 ) {
 104                 numActiveBrushes++;
 105         }
 106
 107         /* return it */
 108         return bb;
 109 }
 110
 111
 112
 113 /*
 114    FreeBrush()
 115    frees a single brush and all sides/windings
 116  */
 117
 118 void FreeBrush( brush_t *b ){
 119         int i;
 120
 121
 122         /* error check */
 123         if ( *( (unsigned int*) b ) == 0xFEFEFEFE ) {
 124                 Sys_FPrintf( SYS_VRB, "WARNING: Attempt to free an already freed brush!\n" );
 125                 return;
 126         }
 127
 128         /* free brush sides */
 129         for ( i = 0; i < b->numsides; i++ )
 130                 if ( b->sides[i].winding != NULL ) {
 131                         FreeWinding( b->sides[ i ].winding );
 132                 }
 133
 134         /* ydnar: overwrite it */
 135         memset( b, 0xFE, (size_t)&( ( (brush_t*) 0 )->sides[ b->numsides ] ) );
 136         *( (unsigned int*) b ) = 0xFEFEFEFE;
 137
 138         /* free it */
 139         free( b );
 140         if ( numthreads == 1 ) {
 141                 numActiveBrushes--;
 142         }
 143 }
 144
 145
 146
 147 /*
 148    FreeBrushList()
 149    frees a linked list of brushes
 150  */
 151
 152 void FreeBrushList( brush_t *brushes ){
 153         brush_t     *next;
 154
 155
 156         /* walk brush list */
 157         for ( ; brushes != NULL; brushes = next )
 158         {
 159                 next = brushes->next;
 160                 FreeBrush( brushes );
 161         }
 162 }
 163
 164
 165
 166 /*
 167    CopyBrush()
 168    duplicates the brush, sides, and windings
 169  */
 170
 171 brush_t *CopyBrush( brush_t *brush ){
 172         brush_t     *newBrush;
 173         size_t size;
 174         int i;
 175
 176
 177         /* copy brush */
 178         size = (size_t)&( ( (brush_t*) 0 )->sides[ brush->numsides ] );
 179         newBrush = AllocBrush( brush->numsides );
 180         memcpy( newBrush, brush, size );
 181
 182         /* ydnar: nuke linked list */
 183         newBrush->next = NULL;
 184
 185         /* copy sides */
 186         for ( i = 0; i < brush->numsides; i++ )
 187         {
 188                 if ( brush->sides[ i ].winding != NULL ) {
 189                         newBrush->sides[ i ].winding = CopyWinding( brush->sides[ i ].winding );
 190                 }
 191         }
 192
 193         /* return it */
 194         return newBrush;
 195 }
 196
 197
 198
 199
 200 /*
 201    BoundBrush()
 202    sets the mins/maxs based on the windings
 203    returns false if the brush doesn't enclose a valid volume
 204  */
 205
 206 qboolean BoundBrush( brush_t *brush ){
 207         int i, j;
 208         winding_t   *w;
 209
 210
 211         ClearBounds( brush->mins, brush->maxs );
 212         for ( i = 0; i < brush->numsides; i++ )
 213         {
 214                 w = brush->sides[ i ].winding;
 215                 if ( w == NULL ) {
 216                         continue;
 217                 }
 218                 for ( j = 0; j < w->numpoints; j++ )
 219                         AddPointToBounds( w->p[ j ], brush->mins, brush->maxs );
 220         }
 221
 222         for ( i = 0; i < 3; i++ )
 223         {
 224                 if ( brush->mins[ i ] < MIN_WORLD_COORD || brush->maxs[ i ] > MAX_WORLD_COORD || brush->mins[i] >= brush->maxs[ i ] ) {
 225                         return qfalse;
 226                 }
 227         }
 228
 229         return qtrue;
 230 }
 231
 232
 233
 234
 235 /*
 236    SnapWeldVector() - ydnar
 237    welds two vec3_t's into a third, taking into account nearest-to-integer
 238    instead of averaging
 239  */
 240
 241 #define SNAP_EPSILON    0.01
 242
 243 void SnapWeldVector( vec3_t a, vec3_t b, vec3_t out ){
 244         int i;
 245         vec_t ai, bi, outi;
 246
 247
 248         /* dummy check */
 249         if ( a == NULL || b == NULL || out == NULL ) {
 250                 return;
 251         }
 252
 253         /* do each element */
 254         for ( i = 0; i < 3; i++ )
 255         {
 256                 /* round to integer */
 257                 ai = Q_rint( a[ i ] );
 258                 bi = Q_rint( b[ i ] );
 259
 260                 /* prefer exact integer */
 261                 if ( ai == a[ i ] ) {
 262                         out[ i ] = a[ i ];
 263                 }
 264                 else if ( bi == b[ i ] ) {
 265                         out[ i ] = b[ i ];
 266                 }
 267
 268                 /* use nearest */
 269                 else if ( fabs( ai - a[ i ] ) < fabs( bi - b[ i ] ) ) {
 270                         out[ i ] = a[ i ];
 271                 }
 272                 else{
 273                         out[ i ] = b[ i ];
 274                 }
 275
 276                 /* snap */
 277                 outi = Q_rint( out[ i ] );
 278                 if ( fabs( outi - out[ i ] ) <= SNAP_EPSILON ) {
 279                         out[ i ] = outi;
 280                 }
 281         }
 282 }
 283
 284
 285
 286 /*
 287    ==================
 288    SnapWeldVectorAccu
 289
 290    Welds two vectors into a third, taking into account nearest-to-integer
 291    instead of averaging.
 292    ==================
 293  */
 294 void SnapWeldVectorAccu( vec3_accu_t a, vec3_accu_t b, vec3_accu_t out ){
 295         // I'm just preserving what I think was the intended logic of the original
 296         // SnapWeldVector().  I'm not actually sure where this function should even
 297         // be used.  I'd like to know which kinds of problems this function addresses.
 298
 299         // TODO: I thought we're snapping all coordinates to nearest 1/8 unit?
 300         // So what is natural about snapping to the nearest integer?  Maybe we should
 301         // be snapping to the nearest 1/8 unit instead?
 302
 303         int i;
 304         vec_accu_t ai, bi, ad, bd;
 305
 306         if ( a == NULL || b == NULL || out == NULL ) {
 307                 Error( "SnapWeldVectorAccu: NULL argument" );
 308         }
 309
 310         for ( i = 0; i < 3; i++ )
 311         {
 312                 ai = Q_rintAccu( a[i] );
 313                 bi = Q_rintAccu( b[i] );
 314                 ad = fabs( ai - a[i] );
 315                 bd = fabs( bi - b[i] );
 316
 317                 if ( ad < bd ) {
 318                         if ( ad < SNAP_EPSILON ) {
 319                                 out[i] = ai;
 320                         }
 321                         else{out[i] = a[i]; }
 322                 }
 323                 else
 324                 {
 325                         if ( bd < SNAP_EPSILON ) {
 326                                 out[i] = bi;
 327                         }
 328                         else{out[i] = b[i]; }
 329                 }
 330         }
 331 }
 332
 333
 334
 335 /*
 336    FixWinding() - ydnar
 337    removes degenerate edges from a winding
 338    returns qtrue if the winding is valid
 339  */
 340
 341 #define DEGENERATE_EPSILON  0.1
 342
 343 qboolean FixWinding( winding_t *w ){
 344         qboolean valid = qtrue;
 345         int i, j, k;
 346         vec3_t vec;
 347         float dist;
 348
 349
 350         /* dummy check */
 351         if ( !w ) {
 352                 return qfalse;
 353         }
 354
 355         /* check all verts */
 356         for ( i = 0; i < w->numpoints; i++ )
 357         {
 358                 /* don't remove points if winding is a triangle */
 359                 if ( w->numpoints == 3 ) {
 360                         return valid;
 361                 }
 362
 363                 /* get second point index */
 364                 j = ( i + 1 ) % w->numpoints;
 365
 366                 /* degenerate edge? */
 367                 VectorSubtract( w->p[ i ], w->p[ j ], vec );
 368                 dist = VectorLength( vec );
 369                 if ( dist < DEGENERATE_EPSILON ) {
 370                         valid = qfalse;
 371                         //Sys_FPrintf( SYS_VRB, "WARNING: Degenerate winding edge found, fixing...\n" );
 372
 373                         /* create an average point (ydnar 2002-01-26: using nearest-integer weld preference) */
 374                         SnapWeldVector( w->p[ i ], w->p[ j ], vec );
 375                         VectorCopy( vec, w->p[ i ] );
 376                         //VectorAdd( w->p[ i ], w->p[ j ], vec );
 377                         //VectorScale( vec, 0.5, w->p[ i ] );
 378
 379                         /* move the remaining verts */
 380                         for ( k = i + 2; k < w->numpoints; k++ )
 381                         {
 382                                 VectorCopy( w->p[ k ], w->p[ k - 1 ] );
 383                         }
 384                         w->numpoints--;
 385                 }
 386         }
 387
 388         /* one last check and return */
 389         if ( w->numpoints < 3 ) {
 390                 valid = qfalse;
 391         }
 392         return valid;
 393 }
 394
 395 /*
 396    ==================
 397    FixWindingAccu
 398
 399    Removes degenerate edges (edges that are too short) from a winding.
 400    Returns qtrue if the winding has been altered by this function.
 401    Returns qfalse if the winding is untouched by this function.
 402
 403    It's advised that you check the winding after this function exits to make
 404    sure it still has at least 3 points.  If that is not the case, the winding
 405    cannot be considered valid.  The winding may degenerate to one or two points
 406    if the some of the winding's points are close together.
 407    ==================
 408  */
 409 qboolean FixWindingAccu( winding_accu_t *w ){
 410         int i, j, k;
 411         vec3_accu_t vec;
 412         vec_accu_t dist;
 413         qboolean done, altered;
 414
 415         if ( w == NULL ) {
 416                 Error( "FixWindingAccu: NULL argument" );
 417         }
 418
 419         altered = qfalse;
 420
 421         while ( qtrue )
 422         {
 423                 if ( w->numpoints < 2 ) {
 424                         break;                   // Don't remove the only remaining point.
 425                 }
 426                 done = qtrue;
 427                 for ( i = 0; i < w->numpoints; i++ )
 428                 {
 429                         j = ( ( ( i + 1 ) == w->numpoints ) ? 0 : ( i + 1 ) );
 430
 431                         VectorSubtractAccu( w->p[i], w->p[j], vec );
 432                         dist = VectorLengthAccu( vec );
 433                         if ( dist < DEGENERATE_EPSILON ) {
 434                                 // TODO: I think the "snap weld vector" was written before
 435                                 // some of the math precision fixes, and its purpose was
 436                                 // probably to address math accuracy issues.  We can think
 437                                 // about changing the logic here.  Maybe once plane distance
 438                                 // gets 64 bits, we can look at it then.
 439                                 SnapWeldVectorAccu( w->p[i], w->p[j], vec );
 440                                 VectorCopyAccu( vec, w->p[i] );
 441                                 for ( k = j + 1; k < w->numpoints; k++ )
 442                                 {
 443                                         VectorCopyAccu( w->p[k], w->p[k - 1] );
 444                                 }
 445                                 w->numpoints--;
 446                                 altered = qtrue;
 447                                 // The only way to finish off fixing the winding consistently and
 448                                 // accurately is by fixing the winding all over again.  For example,
 449                                 // the point at index i and the point at index i-1 could now be
 450                                 // less than the epsilon distance apart.  There are too many special
 451                                 // case problems we'd need to handle if we didn't start from the
 452                                 // beginning.
 453                                 done = qfalse;
 454                                 break; // This will cause us to return to the "while" loop.
 455                         }
 456                 }
 457                 if ( done ) {
 458                         break;
 459                 }
 460         }
 461
 462         return altered;
 463 }
 464
 465
 466 /*
 467    CreateBrushWindings()
 468    makes basewindigs for sides and mins/maxs for the brush
 469    returns false if the brush doesn't enclose a valid volume
 470  */
 471
 472 qboolean CreateBrushWindings( brush_t *brush ){
 473         int i, j;
 474 #if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES
 475         winding_accu_t  *w;
 476 #else
 477         winding_t   *w;
 478 #endif
 479         side_t      *side;
 480         plane_t     *plane;
 481
 482
 483         /* walk the list of brush sides */
 484         for ( i = 0; i < brush->numsides; i++ )
 485         {
 486                 /* get side and plane */
 487                 side = &brush->sides[ i ];
 488                 plane = &mapplanes[ side->planenum ];
 489
 490                 /* make huge winding */
 491 #if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES
 492                 w = BaseWindingForPlaneAccu( plane->normal, plane->dist );
 493 #else
 494                 w = BaseWindingForPlane( plane->normal, plane->dist );
 495 #endif
 496
 497                 /* walk the list of brush sides */
 498                 for ( j = 0; j < brush->numsides && w != NULL; j++ )
 499                 {
 500                         if ( i == j ) {
 501                                 continue;
 502                         }
 503                         if ( brush->sides[ j ].planenum == ( brush->sides[ i ].planenum ^ 1 ) ) {
 504                                 continue;       /* back side clipaway */
 505                         }
 506                         if ( brush->sides[ j ].bevel ) {
 507                                 continue;
 508                         }
 509                         plane = &mapplanes[ brush->sides[ j ].planenum ^ 1 ];
 510 #if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES
 511                         ChopWindingInPlaceAccu( &w, plane->normal, plane->dist, 0 );
 512 #else
 513                         ChopWindingInPlace( &w, plane->normal, plane->dist, 0 ); // CLIP_EPSILON );
 514 #endif
 515
 516                         /* ydnar: fix broken windings that would generate trifans */
 517 #if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES
 518                         // I think it's better to FixWindingAccu() once after we chop with all planes
 519                         // so that error isn't multiplied.  There is nothing natural about welding
 520                         // the points unless they are the final endpoints.  ChopWindingInPlaceAccu()
 521                         // is able to handle all kinds of degenerate windings.
 522 #else
 523                         FixWinding( w );
 524 #endif
 525                 }
 526
 527                 /* set side winding */
 528 #if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES
 529                 if ( w != NULL ) {
 530                         FixWindingAccu( w );
 531                         if ( w->numpoints < 3 ) {
 532                                 FreeWindingAccu( w );
 533                                 w = NULL;
 534                         }
 535                 }
 536                 side->winding = ( w ? CopyWindingAccuToRegular( w ) : NULL );
 537                 if ( w ) {
 538                         FreeWindingAccu( w );
 539                 }
 540 #else
 541                 side->winding = w;
 542 #endif
 543         }
 544
 545         /* find brush bounds */
 546         return BoundBrush( brush );
 547 }
 548
 549
 550
 551
 552 /*
 553    ==================
 554    BrushFromBounds
 555
 556    Creates a new axial brush
 557    ==================
 558  */
 559 brush_t *BrushFromBounds( vec3_t mins, vec3_t maxs ){
 560         brush_t     *b;
 561         int i;
 562         vec3_t normal;
 563         vec_t dist;
 564
 565         b = AllocBrush( 6 );
 566         b->numsides = 6;
 567         for ( i = 0 ; i < 3 ; i++ )
 568         {
 569                 VectorClear( normal );
 570                 normal[i] = 1;
 571                 dist = maxs[i];
 572                 b->sides[i].planenum = FindFloatPlane( normal, dist, 1, (vec3_t*) &maxs );
 573
 574                 normal[i] = -1;
 575                 dist = -mins[i];
 576                 b->sides[3 + i].planenum = FindFloatPlane( normal, dist, 1, (vec3_t*) &mins );
 577         }
 578
 579         CreateBrushWindings( b );
 580
 581         return b;
 582 }
 583
 584 /*
 585    ==================
 586    BrushVolume
 587
 588    ==================
 589  */
 590 vec_t BrushVolume( brush_t *brush ){
 591         int i;
 592         winding_t   *w;
 593         vec3_t corner;
 594         vec_t d, area, volume;
 595         plane_t     *plane;
 596
 597         if ( !brush ) {
 598                 return 0;
 599         }
 600
 601         // grab the first valid point as the corner
 602
 603         w = NULL;
 604         for ( i = 0 ; i < brush->numsides ; i++ )
 605         {
 606                 w = brush->sides[i].winding;
 607                 if ( w ) {
 608                         break;
 609                 }
 610         }
 611         if ( !w ) {
 612                 return 0;
 613         }
 614         VectorCopy( w->p[0], corner );
 615
 616         // make tetrahedrons to all other faces
 617
 618         volume = 0;
 619         for ( ; i < brush->numsides ; i++ )
 620         {
 621                 w = brush->sides[i].winding;
 622                 if ( !w ) {
 623                         continue;
 624                 }
 625                 plane = &mapplanes[brush->sides[i].planenum];
 626                 d = -( DotProduct( corner, plane->normal ) - plane->dist );
 627                 area = WindingArea( w );
 628                 volume += d * area;
 629         }
 630
 631         volume /= 3;
 632         return volume;
 633 }
 634
 635
 636
 637 /*
 638    WriteBSPBrushMap()
 639    writes a map with the split bsp brushes
 640  */
 641
 642 void WriteBSPBrushMap( char *name, brush_t *list ){
 643         FILE        *f;
 644         side_t      *s;
 645         int i;
 646         winding_t   *w;
 647
 648
 649         /* note it */
 650         Sys_Printf( "Writing %s\n", name );
 651
 652         /* open the map file */
 653         f = fopen( name, "wb" );
 654         if ( f == NULL ) {
 655                 Error( "Can't write %s\b", name );
 656         }
 657
 658         fprintf( f, "{\n\"classname\" \"worldspawn\"\n" );
 659
 660         for ( ; list ; list = list->next )
 661         {
 662                 fprintf( f, "{\n" );
 663                 for ( i = 0,s = list->sides ; i < list->numsides ; i++,s++ )
 664                 {
 665                         // TODO: See if we can use a smaller winding to prevent resolution loss.
 666                         // Is WriteBSPBrushMap() used only to decompile maps?
 667                         w = BaseWindingForPlane( mapplanes[s->planenum].normal, mapplanes[s->planenum].dist );
 668
 669                         fprintf( f,"( %i %i %i ) ", (int)w->p[0][0], (int)w->p[0][1], (int)w->p[0][2] );
 670                         fprintf( f,"( %i %i %i ) ", (int)w->p[1][0], (int)w->p[1][1], (int)w->p[1][2] );
 671                         fprintf( f,"( %i %i %i ) ", (int)w->p[2][0], (int)w->p[2][1], (int)w->p[2][2] );
 672
 673                         fprintf( f, "notexture 0 0 0 1 1\n" );
 674                         FreeWinding( w );
 675                 }
 676                 fprintf( f, "}\n" );
 677         }
 678         fprintf( f, "}\n" );
 679
 680         fclose( f );
 681
 682 }
 683
 684
 685
 686 /*
 687    FilterBrushIntoTree_r()
 688    adds brush reference to any intersecting bsp leafnode
 689  */
 690
 691 int FilterBrushIntoTree_r( brush_t *b, node_t *node ){
 692         brush_t     *front, *back;
 693         int c;
 694
 695
 696         /* dummy check */
 697         if ( b == NULL ) {
 698                 return 0;
 699         }
 700
 701         /* add it to the leaf list */
 702         if ( node->planenum == PLANENUM_LEAF ) {
 703                 /* something somewhere is hammering brushlist */
 704                 b->next = node->brushlist;
 705                 node->brushlist = b;
 706
 707                 /* classify the leaf by the structural brush */
 708                 if ( !b->detail ) {
 709                         if ( b->opaque ) {
 710                                 node->opaque = qtrue;
 711                                 node->areaportal = qfalse;
 712                         }
 713                         else if ( b->compileFlags & C_AREAPORTAL ) {
 714                                 if ( !node->opaque ) {
 715                                         node->areaportal = qtrue;
 716                                 }
 717                         }
 718                 }
 719
 720                 return 1;
 721         }
 722
 723         /* split it by the node plane */
 724         c = b->numsides;
 725         SplitBrush( b, node->planenum, &front, &back );
 726         FreeBrush( b );
 727
 728         c = 0;
 729         c += FilterBrushIntoTree_r( front, node->children[ 0 ] );
 730         c += FilterBrushIntoTree_r( back, node->children[ 1 ] );
 731
 732         return c;
 733 }
 734
 735
 736
 737 /*
 738    FilterDetailBrushesIntoTree
 739    fragment all the detail brushes into the structural leafs
 740  */
 741
 742 void FilterDetailBrushesIntoTree( entity_t *e, tree_t *tree ){
 743         brush_t             *b, *newb;
 744         int r;
 745         int c_unique, c_clusters;
 746         int i;
 747
 748
 749         /* note it */
 750         Sys_FPrintf( SYS_VRB,  "--- FilterDetailBrushesIntoTree ---\n" );
 751
 752         /* walk the list of brushes */
 753         c_unique = 0;
 754         c_clusters = 0;
 755         for ( b = e->brushes; b; b = b->next )
 756         {
 757                 if ( !b->detail ) {
 758                         continue;
 759                 }
 760                 c_unique++;
 761                 newb = CopyBrush( b );
 762                 r = FilterBrushIntoTree_r( newb, tree->headnode );
 763                 c_clusters += r;
 764
 765                 /* mark all sides as visible so drawsurfs are created */
 766                 if ( r ) {
 767                         for ( i = 0; i < b->numsides; i++ )
 768                         {
 769                                 if ( b->sides[ i ].winding ) {
 770                                         b->sides[ i ].visible = qtrue;
 771                                 }
 772                         }
 773                 }
 774         }
 775
 776         /* emit some statistics */
 777         Sys_FPrintf( SYS_VRB, "%9d detail brushes\n", c_unique );
 778         Sys_FPrintf( SYS_VRB, "%9d cluster references\n", c_clusters );
 779 }
 780
 781 /*
 782    =====================
 783    FilterStructuralBrushesIntoTree
 784
 785    Mark the leafs as opaque and areaportals
 786    =====================
 787  */
 788 void FilterStructuralBrushesIntoTree( entity_t *e, tree_t *tree ) {
 789         brush_t         *b, *newb;
 790         int r;
 791         int c_unique, c_clusters;
 792         int i;
 793
 794         Sys_FPrintf( SYS_VRB, "--- FilterStructuralBrushesIntoTree ---\n" );
 795
 796         c_unique = 0;
 797         c_clusters = 0;
 798         for ( b = e->brushes ; b ; b = b->next ) {
 799                 if ( b->detail ) {
 800                         continue;
 801                 }
 802                 c_unique++;
 803                 newb = CopyBrush( b );
 804                 r = FilterBrushIntoTree_r( newb, tree->headnode );
 805                 c_clusters += r;
 806
 807                 // mark all sides as visible so drawsurfs are created
 808                 if ( r ) {
 809                         for ( i = 0 ; i < b->numsides ; i++ ) {
 810                                 if ( b->sides[i].winding ) {
 811                                         b->sides[i].visible = qtrue;
 812                                 }
 813                         }
 814                 }
 815         }
 816
 817         /* emit some statistics */
 818         Sys_FPrintf( SYS_VRB, "%9d structural brushes\n", c_unique );
 819         Sys_FPrintf( SYS_VRB, "%9d cluster references\n", c_clusters );
 820 }
 821
 822
 823
 824 /*
 825    ================
 826    AllocTree
 827    ================
 828  */
 829 tree_t *AllocTree( void ){
 830         tree_t  *tree;
 831
 832         tree = safe_malloc0( sizeof( *tree ) );
 833         ClearBounds( tree->mins, tree->maxs );
 834
 835         return tree;
 836 }
 837
 838 /*
 839    ================
 840    AllocNode
 841    ================
 842  */
 843 node_t *AllocNode( void ){
 844         node_t  *node;
 845
 846         node = safe_malloc0( sizeof( *node ) );
 847
 848         return node;
 849 }
 850
 851
 852 /*
 853    ================
 854    WindingIsTiny
 855
 856    Returns true if the winding would be crunched out of
 857    existance by the vertex snapping.
 858    ================
 859  */
 860 #define EDGE_LENGTH 0.2
 861 qboolean WindingIsTiny( winding_t *w ){
 862 /*
 863     if (WindingArea (w) < 1)
 864         return qtrue;
 865     return qfalse;
 866  */
 867         int i, j;
 868         vec_t len;
 869         vec3_t delta;
 870         int edges;
 871
 872         edges = 0;
 873         for ( i = 0 ; i < w->numpoints ; i++ )
 874         {
 875                 j = i == w->numpoints - 1 ? 0 : i + 1;
 876                 VectorSubtract( w->p[j], w->p[i], delta );
 877                 len = VectorLength( delta );
 878                 if ( len > EDGE_LENGTH ) {
 879                         if ( ++edges == 3 ) {
 880                                 return qfalse;
 881                         }
 882                 }
 883         }
 884         return qtrue;
 885 }
 886
 887 /*
 888    ================
 889    WindingIsHuge
 890
 891    Returns true if the winding still has one of the points
 892    from basewinding for plane
 893    ================
 894  */
 895 qboolean WindingIsHuge( winding_t *w ){
 896         int i, j;
 897
 898         for ( i = 0 ; i < w->numpoints ; i++ )
 899         {
 900                 for ( j = 0 ; j < 3 ; j++ )
 901                         if ( w->p[i][j] <= MIN_WORLD_COORD || w->p[i][j] >= MAX_WORLD_COORD ) {
 902                                 return qtrue;
 903                         }
 904         }
 905         return qfalse;
 906 }
 907
 908 //============================================================
 909
 910 /*
 911    ==================
 912    BrushMostlyOnSide
 913
 914    ==================
 915  */
 916 int BrushMostlyOnSide( brush_t *brush, plane_t *plane ){
 917         int i, j;
 918         winding_t   *w;
 919         vec_t d, max;
 920         int side;
 921
 922         max = 0;
 923         side = PSIDE_FRONT;
 924         for ( i = 0 ; i < brush->numsides ; i++ )
 925         {
 926                 w = brush->sides[i].winding;
 927                 if ( !w ) {
 928                         continue;
 929                 }
 930                 for ( j = 0 ; j < w->numpoints ; j++ )
 931                 {
 932                         d = DotProduct( w->p[j], plane->normal ) - plane->dist;
 933                         if ( d > max ) {
 934                                 max = d;
 935                                 side = PSIDE_FRONT;
 936                         }
 937                         if ( -d > max ) {
 938                                 max = -d;
 939                                 side = PSIDE_BACK;
 940                         }
 941                 }
 942         }
 943         return side;
 944 }
 945
 946
 947
 948 /*
 949    SplitBrush()
 950    generates two new brushes, leaving the original unchanged
 951  */
 952
 953 void SplitBrush( brush_t *brush, int planenum, brush_t **front, brush_t **back ){
 954         brush_t     *b[2];
 955         int i, j;
 956         winding_t   *w, *cw[2], *midwinding;
 957         plane_t     *plane, *plane2;
 958         side_t      *s, *cs;
 959         float d, d_front, d_back;
 960
 961
 962         *front = NULL;
 963         *back = NULL;
 964         plane = &mapplanes[planenum];
 965
 966         // check all points
 967         d_front = d_back = 0;
 968         for ( i = 0 ; i < brush->numsides ; i++ )
 969         {
 970                 w = brush->sides[i].winding;
 971                 if ( !w ) {
 972                         continue;
 973                 }
 974                 for ( j = 0 ; j < w->numpoints ; j++ )
 975                 {
 976                         d = DotProduct( w->p[j], plane->normal ) - plane->dist;
 977                         if ( d > 0 && d > d_front ) {
 978                                 d_front = d;
 979                         }
 980                         if ( d < 0 && d < d_back ) {
 981                                 d_back = d;
 982                         }
 983                 }
 984         }
 985
 986         if ( d_front < 0.1 ) { // PLANESIDE_EPSILON)
 987                 // only on back
 988                 *back = CopyBrush( brush );
 989                 return;
 990         }
 991
 992         if ( d_back > -0.1 ) { // PLANESIDE_EPSILON)
 993                 // only on front
 994                 *front = CopyBrush( brush );
 995                 return;
 996         }
 997
 998         // create a new winding from the split plane
 999         w = BaseWindingForPlane( plane->normal, plane->dist );
1000         for ( i = 0 ; i < brush->numsides && w ; i++ )
1001         {
1002                 plane2 = &mapplanes[brush->sides[i].planenum ^ 1];
1003                 ChopWindingInPlace( &w, plane2->normal, plane2->dist, 0 ); // PLANESIDE_EPSILON);
1004         }
1005
1006         if ( !w || WindingIsTiny( w ) ) { // the brush isn't really split
1007                 int side;
1008
1009                 side = BrushMostlyOnSide( brush, plane );
1010                 if ( side == PSIDE_FRONT ) {
1011                         *front = CopyBrush( brush );
1012                 }
1013                 if ( side == PSIDE_BACK ) {
1014                         *back = CopyBrush( brush );
1015                 }
1016                 return;
1017         }
1018
1019         if ( WindingIsHuge( w ) ) {
1020                 Sys_FPrintf( SYS_VRB,"WARNING: huge winding\n" );
1021         }
1022
1023         midwinding = w;
1024
1025         // split it for real
1026
1027         for ( i = 0 ; i < 2 ; i++ )
1028         {
1029                 b[i] = AllocBrush( brush->numsides + 1 );
1030                 memcpy( b[i], brush, sizeof( brush_t ) - sizeof( brush->sides ) );
1031                 b[i]->numsides = 0;
1032                 b[i]->next = NULL;
1033                 b[i]->original = brush->original;
1034         }
1035
1036         // split all the current windings
1037
1038         for ( i = 0 ; i < brush->numsides ; i++ )
1039         {
1040                 s = &brush->sides[i];
1041                 w = s->winding;
1042                 if ( !w ) {
1043                         continue;
1044                 }
1045                 /* strict, in parallel case we get the face back because it also is the midwinding */
1046                 ClipWindingEpsilonStrict( w, plane->normal, plane->dist,
1047                                                         0 /*PLANESIDE_EPSILON*/, &cw[0], &cw[1] );
1048                 for ( j = 0 ; j < 2 ; j++ )
1049                 {
1050                         if ( !cw[j] ) {
1051                                 continue;
1052                         }
1053                         cs = &b[j]->sides[b[j]->numsides];
1054                         b[j]->numsides++;
1055                         *cs = *s;
1056                         cs->winding = cw[j];
1057                 }
1058         }
1059
1060
1061         // see if we have valid polygons on both sides
1062         for ( i = 0 ; i < 2 ; i++ )
1063         {
1064                 if ( b[i]->numsides < 3 || !BoundBrush( b[i] ) ) {
1065                         if ( b[i]->numsides >= 3 ) {
1066                                 Sys_FPrintf( SYS_VRB,"bogus brush after clip\n" );
1067                         }
1068                         FreeBrush( b[i] );
1069                         b[i] = NULL;
1070                 }
1071         }
1072
1073         if ( !( b[0] && b[1] ) ) {
1074                 if ( !b[0] && !b[1] ) {
1075                         Sys_FPrintf( SYS_VRB,"split removed brush\n" );
1076                 }
1077                 else{
1078                         Sys_FPrintf( SYS_VRB,"split not on both sides\n" );
1079                 }
1080                 if ( b[0] ) {
1081                         FreeBrush( b[0] );
1082                         *front = CopyBrush( brush );
1083                 }
1084                 if ( b[1] ) {
1085                         FreeBrush( b[1] );
1086                         *back = CopyBrush( brush );
1087                 }
1088                 return;
1089         }
1090
1091         // add the midwinding to both sides
1092         for ( i = 0 ; i < 2 ; i++ )
1093         {
1094                 cs = &b[i]->sides[b[i]->numsides];
1095                 b[i]->numsides++;
1096
1097                 cs->planenum = planenum ^ i ^ 1;
1098                 cs->shaderInfo = NULL;
1099                 if ( i == 0 ) {
1100                         cs->winding = CopyWinding( midwinding );
1101                 }
1102                 else{
1103                         cs->winding = midwinding;
1104                 }
1105         }
1106
1107         {
1108                 vec_t v1;
1109                 int i;
1110
1111
1112                 for ( i = 0 ; i < 2 ; i++ )
1113                 {
1114                         v1 = BrushVolume( b[i] );
1115                         if ( v1 < 1.0 ) {
1116                                 FreeBrush( b[i] );
1117                                 b[i] = NULL;
1118                                 //                      Sys_FPrintf (SYS_VRB,"tiny volume after clip\n");
1119                         }
1120                 }
1121         }
1122
1123         *front = b[0];
1124         *back = b[1];
1125 }