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_malloc( c );
 102         memset( bb, 0, 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_malloc( sizeof( *tree ) );
 833         memset( tree, 0, sizeof( *tree ) );
 834         ClearBounds( tree->mins, tree->maxs );
 835
 836         return tree;
 837 }
 838
 839 /*
 840    ================
 841    AllocNode
 842    ================
 843  */
 844 node_t *AllocNode( void ){
 845         node_t  *node;
 846
 847         node = safe_malloc( sizeof( *node ) );
 848         memset( node, 0, sizeof( *node ) );
 849
 850         return node;
 851 }
 852
 853
 854 /*
 855    ================
 856    WindingIsTiny
 857
 858    Returns true if the winding would be crunched out of
 859    existance by the vertex snapping.
 860    ================
 861  */
 862 #define EDGE_LENGTH 0.2
 863 qboolean WindingIsTiny( winding_t *w ){
 864 /*
 865     if (WindingArea (w) < 1)
 866         return qtrue;
 867     return qfalse;
 868  */
 869         int i, j;
 870         vec_t len;
 871         vec3_t delta;
 872         int edges;
 873
 874         edges = 0;
 875         for ( i = 0 ; i < w->numpoints ; i++ )
 876         {
 877                 j = i == w->numpoints - 1 ? 0 : i + 1;
 878                 VectorSubtract( w->p[j], w->p[i], delta );
 879                 len = VectorLength( delta );
 880                 if ( len > EDGE_LENGTH ) {
 881                         if ( ++edges == 3 ) {
 882                                 return qfalse;
 883                         }
 884                 }
 885         }
 886         return qtrue;
 887 }
 888
 889 /*
 890    ================
 891    WindingIsHuge
 892
 893    Returns true if the winding still has one of the points
 894    from basewinding for plane
 895    ================
 896  */
 897 qboolean WindingIsHuge( winding_t *w ){
 898         int i, j;
 899
 900         for ( i = 0 ; i < w->numpoints ; i++ )
 901         {
 902                 for ( j = 0 ; j < 3 ; j++ )
 903                         if ( w->p[i][j] <= MIN_WORLD_COORD || w->p[i][j] >= MAX_WORLD_COORD ) {
 904                                 return qtrue;
 905                         }
 906         }
 907         return qfalse;
 908 }
 909
 910 //============================================================
 911
 912 /*
 913    ==================
 914    BrushMostlyOnSide
 915
 916    ==================
 917  */
 918 int BrushMostlyOnSide( brush_t *brush, plane_t *plane ){
 919         int i, j;
 920         winding_t   *w;
 921         vec_t d, max;
 922         int side;
 923
 924         max = 0;
 925         side = PSIDE_FRONT;
 926         for ( i = 0 ; i < brush->numsides ; i++ )
 927         {
 928                 w = brush->sides[i].winding;
 929                 if ( !w ) {
 930                         continue;
 931                 }
 932                 for ( j = 0 ; j < w->numpoints ; j++ )
 933                 {
 934                         d = DotProduct( w->p[j], plane->normal ) - plane->dist;
 935                         if ( d > max ) {
 936                                 max = d;
 937                                 side = PSIDE_FRONT;
 938                         }
 939                         if ( -d > max ) {
 940                                 max = -d;
 941                                 side = PSIDE_BACK;
 942                         }
 943                 }
 944         }
 945         return side;
 946 }
 947
 948
 949
 950 /*
 951    SplitBrush()
 952    generates two new brushes, leaving the original unchanged
 953  */
 954
 955 void SplitBrush( brush_t *brush, int planenum, brush_t **front, brush_t **back ){
 956         brush_t     *b[2];
 957         int i, j;
 958         winding_t   *w, *cw[2], *midwinding;
 959         plane_t     *plane, *plane2;
 960         side_t      *s, *cs;
 961         float d, d_front, d_back;
 962
 963
 964         *front = NULL;
 965         *back = NULL;
 966         plane = &mapplanes[planenum];
 967
 968         // check all points
 969         d_front = d_back = 0;
 970         for ( i = 0 ; i < brush->numsides ; i++ )
 971         {
 972                 w = brush->sides[i].winding;
 973                 if ( !w ) {
 974                         continue;
 975                 }
 976                 for ( j = 0 ; j < w->numpoints ; j++ )
 977                 {
 978                         d = DotProduct( w->p[j], plane->normal ) - plane->dist;
 979                         if ( d > 0 && d > d_front ) {
 980                                 d_front = d;
 981                         }
 982                         if ( d < 0 && d < d_back ) {
 983                                 d_back = d;
 984                         }
 985                 }
 986         }
 987
 988         if ( d_front < 0.1 ) { // PLANESIDE_EPSILON)
 989                 // only on back
 990                 *back = CopyBrush( brush );
 991                 return;
 992         }
 993
 994         if ( d_back > -0.1 ) { // PLANESIDE_EPSILON)
 995                 // only on front
 996                 *front = CopyBrush( brush );
 997                 return;
 998         }
 999
1000         // create a new winding from the split plane
1001         w = BaseWindingForPlane( plane->normal, plane->dist );
1002         for ( i = 0 ; i < brush->numsides && w ; i++ )
1003         {
1004                 plane2 = &mapplanes[brush->sides[i].planenum ^ 1];
1005                 ChopWindingInPlace( &w, plane2->normal, plane2->dist, 0 ); // PLANESIDE_EPSILON);
1006         }
1007
1008         if ( !w || WindingIsTiny( w ) ) { // the brush isn't really split
1009                 int side;
1010
1011                 side = BrushMostlyOnSide( brush, plane );
1012                 if ( side == PSIDE_FRONT ) {
1013                         *front = CopyBrush( brush );
1014                 }
1015                 if ( side == PSIDE_BACK ) {
1016                         *back = CopyBrush( brush );
1017                 }
1018                 return;
1019         }
1020
1021         if ( WindingIsHuge( w ) ) {
1022                 Sys_FPrintf( SYS_VRB,"WARNING: huge winding\n" );
1023         }
1024
1025         midwinding = w;
1026
1027         // split it for real
1028
1029         for ( i = 0 ; i < 2 ; i++ )
1030         {
1031                 b[i] = AllocBrush( brush->numsides + 1 );
1032                 memcpy( b[i], brush, sizeof( brush_t ) - sizeof( brush->sides ) );
1033                 b[i]->numsides = 0;
1034                 b[i]->next = NULL;
1035                 b[i]->original = brush->original;
1036         }
1037
1038         // split all the current windings
1039
1040         for ( i = 0 ; i < brush->numsides ; i++ )
1041         {
1042                 s = &brush->sides[i];
1043                 w = s->winding;
1044                 if ( !w ) {
1045                         continue;
1046                 }
1047                 /* strict, in parallel case we get the face back because it also is the midwinding */
1048                 ClipWindingEpsilonStrict( w, plane->normal, plane->dist,
1049                                                         0 /*PLANESIDE_EPSILON*/, &cw[0], &cw[1] );
1050                 for ( j = 0 ; j < 2 ; j++ )
1051                 {
1052                         if ( !cw[j] ) {
1053                                 continue;
1054                         }
1055                         cs = &b[j]->sides[b[j]->numsides];
1056                         b[j]->numsides++;
1057                         *cs = *s;
1058                         cs->winding = cw[j];
1059                 }
1060         }
1061
1062
1063         // see if we have valid polygons on both sides
1064         for ( i = 0 ; i < 2 ; i++ )
1065         {
1066                 if ( b[i]->numsides < 3 || !BoundBrush( b[i] ) ) {
1067                         if ( b[i]->numsides >= 3 ) {
1068                                 Sys_FPrintf( SYS_VRB,"bogus brush after clip\n" );
1069                         }
1070                         FreeBrush( b[i] );
1071                         b[i] = NULL;
1072                 }
1073         }
1074
1075         if ( !( b[0] && b[1] ) ) {
1076                 if ( !b[0] && !b[1] ) {
1077                         Sys_FPrintf( SYS_VRB,"split removed brush\n" );
1078                 }
1079                 else{
1080                         Sys_FPrintf( SYS_VRB,"split not on both sides\n" );
1081                 }
1082                 if ( b[0] ) {
1083                         FreeBrush( b[0] );
1084                         *front = CopyBrush( brush );
1085                 }
1086                 if ( b[1] ) {
1087                         FreeBrush( b[1] );
1088                         *back = CopyBrush( brush );
1089                 }
1090                 return;
1091         }
1092
1093         // add the midwinding to both sides
1094         for ( i = 0 ; i < 2 ; i++ )
1095         {
1096                 cs = &b[i]->sides[b[i]->numsides];
1097                 b[i]->numsides++;
1098
1099                 cs->planenum = planenum ^ i ^ 1;
1100                 cs->shaderInfo = NULL;
1101                 if ( i == 0 ) {
1102                         cs->winding = CopyWinding( midwinding );
1103                 }
1104                 else{
1105                         cs->winding = midwinding;
1106                 }
1107         }
1108
1109         {
1110                 vec_t v1;
1111                 int i;
1112
1113
1114                 for ( i = 0 ; i < 2 ; i++ )
1115                 {
1116                         v1 = BrushVolume( b[i] );
1117                         if ( v1 < 1.0 ) {
1118                                 FreeBrush( b[i] );
1119                                 b[i] = NULL;
1120                                 //                      Sys_FPrintf (SYS_VRB,"tiny volume after clip\n");
1121                         }
1122                 }
1123         }
1124
1125         *front = b[0];
1126         *back = b[1];
1127 }