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