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