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
  97         /* allocate and clear */
  98         if ( numSides <= 0 ) {
  99                 Error( "AllocBrush called with numsides = %d", numSides );
 100         }
 101         c = (size_t)&( ( (brush_t*) 0 )->sides[ numSides ] );
 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( a[ 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    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    FixWinding() - ydnar
 334    removes degenerate edges from a winding
 335    returns qtrue if the winding is valid
 336  */
 337
 338 #define DEGENERATE_EPSILON  0.1
 339
 340 qboolean FixWinding( winding_t *w ){
 341         qboolean valid = qtrue;
 342         int i, j, k;
 343         vec3_t vec;
 344         float dist;
 345
 346
 347         /* dummy check */
 348         if ( !w ) {
 349                 return qfalse;
 350         }
 351
 352         /* check all verts */
 353         for ( i = 0; i < w->numpoints; i++ )
 354         {
 355                 /* don't remove points if winding is a triangle */
 356                 if ( w->numpoints == 3 ) {
 357                         return valid;
 358                 }
 359
 360                 /* get second point index */
 361                 j = ( i + 1 ) % w->numpoints;
 362
 363                 /* degenerate edge? */
 364                 VectorSubtract( w->p[ i ], w->p[ j ], vec );
 365                 dist = VectorLength( vec );
 366                 if ( dist < DEGENERATE_EPSILON ) {
 367                         valid = qfalse;
 368                         //Sys_FPrintf( SYS_VRB, "WARNING: Degenerate winding edge found, fixing...\n" );
 369
 370                         /* create an average point (ydnar 2002-01-26: using nearest-integer weld preference) */
 371                         SnapWeldVector( w->p[ i ], w->p[ j ], vec );
 372                         VectorCopy( vec, w->p[ i ] );
 373                         //VectorAdd( w->p[ i ], w->p[ j ], vec );
 374                         //VectorScale( vec, 0.5, w->p[ i ] );
 375
 376                         /* move the remaining verts */
 377                         for ( k = i + 2; k < w->numpoints; k++ )
 378                         {
 379                                 VectorCopy( w->p[ k ], w->p[ k - 1 ] );
 380                         }
 381                         w->numpoints--;
 382                 }
 383         }
 384
 385         /* one last check and return */
 386         if ( w->numpoints < 3 ) {
 387                 valid = qfalse;
 388         }
 389         return valid;
 390 }
 391
 392 /*
 393    ==================
 394    FixWindingAccu
 395
 396    Removes degenerate edges (edges that are too short) from a winding.
 397    Returns qtrue if the winding has been altered by this function.
 398    Returns qfalse if the winding is untouched by this function.
 399
 400    It's advised that you check the winding after this function exits to make
 401    sure it still has at least 3 points.  If that is not the case, the winding
 402    cannot be considered valid.  The winding may degenerate to one or two points
 403    if the some of the winding's points are close together.
 404    ==================
 405  */
 406 qboolean FixWindingAccu( winding_accu_t *w ){
 407         int i, j, k;
 408         vec3_accu_t vec;
 409         vec_accu_t dist;
 410         qboolean done, altered;
 411
 412         if ( w == NULL ) {
 413                 Error( "FixWindingAccu: NULL argument" );
 414         }
 415
 416         altered = qfalse;
 417
 418         while ( qtrue )
 419         {
 420                 if ( w->numpoints < 2 ) {
 421                         break;                   // Don't remove the only remaining point.
 422                 }
 423                 done = qtrue;
 424                 for ( i = 0; i < w->numpoints; i++ )
 425                 {
 426                         j = ( ( ( i + 1 ) == w->numpoints ) ? 0 : ( i + 1 ) );
 427
 428                         VectorSubtractAccu( w->p[i], w->p[j], vec );
 429                         dist = VectorLengthAccu( vec );
 430                         if ( dist < DEGENERATE_EPSILON ) {
 431                                 // TODO: I think the "snap weld vector" was written before
 432                                 // some of the math precision fixes, and its purpose was
 433                                 // probably to address math accuracy issues.  We can think
 434                                 // about changing the logic here.  Maybe once plane distance
 435                                 // gets 64 bits, we can look at it then.
 436                                 SnapWeldVectorAccu( w->p[i], w->p[j], vec );
 437                                 VectorCopyAccu( vec, w->p[i] );
 438                                 for ( k = j + 1; k < w->numpoints; k++ )
 439                                 {
 440                                         VectorCopyAccu( w->p[k], w->p[k - 1] );
 441                                 }
 442                                 w->numpoints--;
 443                                 altered = qtrue;
 444                                 // The only way to finish off fixing the winding consistently and
 445                                 // accurately is by fixing the winding all over again.  For example,
 446                                 // the point at index i and the point at index i-1 could now be
 447                                 // less than the epsilon distance apart.  There are too many special
 448                                 // case problems we'd need to handle if we didn't start from the
 449                                 // beginning.
 450                                 done = qfalse;
 451                                 break; // This will cause us to return to the "while" loop.
 452                         }
 453                 }
 454                 if ( done ) {
 455                         break;
 456                 }
 457         }
 458
 459         return altered;
 460 }
 461
 462
 463 /*
 464    CreateBrushWindings()
 465    makes basewindigs for sides and mins/maxs for the brush
 466    returns false if the brush doesn't enclose a valid volume
 467  */
 468
 469 qboolean CreateBrushWindings( brush_t *brush ){
 470         int i, j;
 471 #if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES
 472         winding_accu_t  *w;
 473 #else
 474         winding_t   *w;
 475 #endif
 476         side_t      *side;
 477         plane_t     *plane;
 478
 479
 480         /* walk the list of brush sides */
 481         for ( i = 0; i < brush->numsides; i++ )
 482         {
 483                 /* get side and plane */
 484                 side = &brush->sides[ i ];
 485                 plane = &mapplanes[ side->planenum ];
 486
 487                 /* make huge winding */
 488 #if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES
 489                 w = BaseWindingForPlaneAccu( plane->normal, plane->dist );
 490 #else
 491                 w = BaseWindingForPlane( plane->normal, plane->dist );
 492 #endif
 493
 494                 /* walk the list of brush sides */
 495                 for ( j = 0; j < brush->numsides && w != NULL; j++ )
 496                 {
 497                         if ( i == j ) {
 498                                 continue;
 499                         }
 500                         if ( brush->sides[ j ].planenum == ( brush->sides[ i ].planenum ^ 1 ) ) {
 501                                 continue;       /* back side clipaway */
 502                         }
 503                         if ( brush->sides[ j ].bevel ) {
 504                                 continue;
 505                         }
 506                         plane = &mapplanes[ brush->sides[ j ].planenum ^ 1 ];
 507 #if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES
 508                         ChopWindingInPlaceAccu( &w, plane->normal, plane->dist, 0 );
 509 #else
 510                         ChopWindingInPlace( &w, plane->normal, plane->dist, 0 ); // CLIP_EPSILON );
 511 #endif
 512
 513                         /* ydnar: fix broken windings that would generate trifans */
 514 #if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES
 515                         // I think it's better to FixWindingAccu() once after we chop with all planes
 516                         // so that error isn't multiplied.  There is nothing natural about welding
 517                         // the points unless they are the final endpoints.  ChopWindingInPlaceAccu()
 518                         // is able to handle all kinds of degenerate windings.
 519 #else
 520                         FixWinding( w );
 521 #endif
 522                 }
 523
 524                 /* set side winding */
 525 #if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES
 526                 if ( w != NULL ) {
 527                         FixWindingAccu( w );
 528                         if ( w->numpoints < 3 ) {
 529                                 FreeWindingAccu( w );
 530                                 w = NULL;
 531                         }
 532                 }
 533                 side->winding = ( w ? CopyWindingAccuToRegular( w ) : NULL );
 534                 if ( w ) {
 535                         FreeWindingAccu( w );
 536                 }
 537 #else
 538                 side->winding = w;
 539 #endif
 540         }
 541
 542         /* find brush bounds */
 543         return BoundBrush( brush );
 544 }
 545
 546
 547
 548
 549 /*
 550    ==================
 551    BrushFromBounds
 552
 553    Creates a new axial brush
 554    ==================
 555  */
 556 brush_t *BrushFromBounds( vec3_t mins, vec3_t maxs ){
 557         brush_t     *b;
 558         int i;
 559         vec3_t normal;
 560         vec_t dist;
 561
 562         b = AllocBrush( 6 );
 563         b->numsides = 6;
 564         for ( i = 0 ; i < 3 ; i++ )
 565         {
 566                 VectorClear( normal );
 567                 normal[i] = 1;
 568                 dist = maxs[i];
 569                 b->sides[i].planenum = FindFloatPlane( normal, dist, 1, (vec3_t*) &maxs );
 570
 571                 normal[i] = -1;
 572                 dist = -mins[i];
 573                 b->sides[3 + i].planenum = FindFloatPlane( normal, dist, 1, (vec3_t*) &mins );
 574         }
 575
 576         CreateBrushWindings( b );
 577
 578         return b;
 579 }
 580
 581 /*
 582    ==================
 583    BrushVolume
 584
 585    ==================
 586  */
 587 vec_t BrushVolume( brush_t *brush ){
 588         int i;
 589         winding_t   *w;
 590         vec3_t corner;
 591         vec_t d, area, volume;
 592         plane_t     *plane;
 593
 594         if ( !brush ) {
 595                 return 0;
 596         }
 597
 598         // grab the first valid point as the corner
 599
 600         w = NULL;
 601         for ( i = 0 ; i < brush->numsides ; i++ )
 602         {
 603                 w = brush->sides[i].winding;
 604                 if ( w ) {
 605                         break;
 606                 }
 607         }
 608         if ( !w ) {
 609                 return 0;
 610         }
 611         VectorCopy( w->p[0], corner );
 612
 613         // make tetrahedrons to all other faces
 614
 615         volume = 0;
 616         for ( ; i < brush->numsides ; i++ )
 617         {
 618                 w = brush->sides[i].winding;
 619                 if ( !w ) {
 620                         continue;
 621                 }
 622                 plane = &mapplanes[brush->sides[i].planenum];
 623                 d = -( DotProduct( corner, plane->normal ) - plane->dist );
 624                 area = WindingArea( w );
 625                 volume += d * area;
 626         }
 627
 628         volume /= 3;
 629         return volume;
 630 }
 631
 632
 633
 634 /*
 635    WriteBSPBrushMap()
 636    writes a map with the split bsp brushes
 637  */
 638
 639 void WriteBSPBrushMap( char *name, brush_t *list ){
 640         FILE        *f;
 641         side_t      *s;
 642         int i;
 643         winding_t   *w;
 644
 645
 646         /* note it */
 647         Sys_Printf( "Writing %s\n", name );
 648
 649         /* open the map file */
 650         f = fopen( name, "wb" );
 651         if ( f == NULL ) {
 652                 Error( "Can't write %s\b", name );
 653         }
 654
 655         fprintf( f, "{\n\"classname\" \"worldspawn\"\n" );
 656
 657         for ( ; list ; list = list->next )
 658         {
 659                 fprintf( f, "{\n" );
 660                 for ( i = 0,s = list->sides ; i < list->numsides ; i++,s++ )
 661                 {
 662                         // TODO: See if we can use a smaller winding to prevent resolution loss.
 663                         // Is WriteBSPBrushMap() used only to decompile maps?
 664                         w = BaseWindingForPlane( mapplanes[s->planenum].normal, mapplanes[s->planenum].dist );
 665
 666                         fprintf( f,"( %i %i %i ) ", (int)w->p[0][0], (int)w->p[0][1], (int)w->p[0][2] );
 667                         fprintf( f,"( %i %i %i ) ", (int)w->p[1][0], (int)w->p[1][1], (int)w->p[1][2] );
 668                         fprintf( f,"( %i %i %i ) ", (int)w->p[2][0], (int)w->p[2][1], (int)w->p[2][2] );
 669
 670                         fprintf( f, "notexture 0 0 0 1 1\n" );
 671                         FreeWinding( w );
 672                 }
 673                 fprintf( f, "}\n" );
 674         }
 675         fprintf( f, "}\n" );
 676
 677         fclose( f );
 678
 679 }
 680
 681
 682
 683 /*
 684    FilterBrushIntoTree_r()
 685    adds brush reference to any intersecting bsp leafnode
 686  */
 687
 688 int FilterBrushIntoTree_r( brush_t *b, node_t *node ){
 689         brush_t     *front, *back;
 690         int c;
 691
 692
 693         /* dummy check */
 694         if ( b == NULL ) {
 695                 return 0;
 696         }
 697
 698         /* add it to the leaf list */
 699         if ( node->planenum == PLANENUM_LEAF ) {
 700                 /* something somewhere is hammering brushlist */
 701                 b->next = node->brushlist;
 702                 node->brushlist = b;
 703
 704                 /* classify the leaf by the structural brush */
 705                 if ( !b->detail ) {
 706                         if ( b->opaque ) {
 707                                 node->opaque = qtrue;
 708                                 node->areaportal = qfalse;
 709                         }
 710                         else if ( b->compileFlags & C_AREAPORTAL ) {
 711                                 if ( !node->opaque ) {
 712                                         node->areaportal = qtrue;
 713                                 }
 714                         }
 715                 }
 716
 717                 return 1;
 718         }
 719
 720         /* split it by the node plane */
 721         c = b->numsides;
 722         SplitBrush( b, node->planenum, &front, &back );
 723         FreeBrush( b );
 724
 725         c = 0;
 726         c += FilterBrushIntoTree_r( front, node->children[ 0 ] );
 727         c += FilterBrushIntoTree_r( back, node->children[ 1 ] );
 728
 729         return c;
 730 }
 731
 732
 733
 734 /*
 735    FilterDetailBrushesIntoTree
 736    fragment all the detail brushes into the structural leafs
 737  */
 738
 739 void FilterDetailBrushesIntoTree( entity_t *e, tree_t *tree ){
 740         brush_t             *b, *newb;
 741         int r;
 742         int c_unique, c_clusters;
 743         int i;
 744
 745
 746         /* note it */
 747         Sys_FPrintf( SYS_VRB,  "--- FilterDetailBrushesIntoTree ---\n" );
 748
 749         /* walk the list of brushes */
 750         c_unique = 0;
 751         c_clusters = 0;
 752         for ( b = e->brushes; b; b = b->next )
 753         {
 754                 if ( !b->detail ) {
 755                         continue;
 756                 }
 757                 c_unique++;
 758                 newb = CopyBrush( b );
 759                 r = FilterBrushIntoTree_r( newb, tree->headnode );
 760                 c_clusters += r;
 761
 762                 /* mark all sides as visible so drawsurfs are created */
 763                 if ( r ) {
 764                         for ( i = 0; i < b->numsides; i++ )
 765                         {
 766                                 if ( b->sides[ i ].winding ) {
 767                                         b->sides[ i ].visible = qtrue;
 768                                 }
 769                         }
 770                 }
 771         }
 772
 773         /* emit some statistics */
 774         Sys_FPrintf( SYS_VRB, "%9d detail brushes\n", c_unique );
 775         Sys_FPrintf( SYS_VRB, "%9d cluster references\n", c_clusters );
 776 }
 777
 778 /*
 779    =====================
 780    FilterStructuralBrushesIntoTree
 781
 782    Mark the leafs as opaque and areaportals
 783    =====================
 784  */
 785 void FilterStructuralBrushesIntoTree( entity_t *e, tree_t *tree ) {
 786         brush_t         *b, *newb;
 787         int r;
 788         int c_unique, c_clusters;
 789         int i;
 790
 791         Sys_FPrintf( SYS_VRB, "--- FilterStructuralBrushesIntoTree ---\n" );
 792
 793         c_unique = 0;
 794         c_clusters = 0;
 795         for ( b = e->brushes ; b ; b = b->next ) {
 796                 if ( b->detail ) {
 797                         continue;
 798                 }
 799                 c_unique++;
 800                 newb = CopyBrush( b );
 801                 r = FilterBrushIntoTree_r( newb, tree->headnode );
 802                 c_clusters += r;
 803
 804                 // mark all sides as visible so drawsurfs are created
 805                 if ( r ) {
 806                         for ( i = 0 ; i < b->numsides ; i++ ) {
 807                                 if ( b->sides[i].winding ) {
 808                                         b->sides[i].visible = qtrue;
 809                                 }
 810                         }
 811                 }
 812         }
 813
 814         /* emit some statistics */
 815         Sys_FPrintf( SYS_VRB, "%9d structural brushes\n", c_unique );
 816         Sys_FPrintf( SYS_VRB, "%9d cluster references\n", c_clusters );
 817 }
 818
 819
 820
 821 /*
 822    ================
 823    AllocTree
 824    ================
 825  */
 826 tree_t *AllocTree( void ){
 827         tree_t  *tree;
 828
 829         tree = safe_malloc( sizeof( *tree ) );
 830         memset( tree, 0, sizeof( *tree ) );
 831         ClearBounds( tree->mins, tree->maxs );
 832
 833         return tree;
 834 }
 835
 836 /*
 837    ================
 838    AllocNode
 839    ================
 840  */
 841 node_t *AllocNode( void ){
 842         node_t  *node;
 843
 844         node = safe_malloc( sizeof( *node ) );
 845         memset( node, 0, 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                 ClipWindingEpsilonStrict( w, plane->normal, plane->dist,
1045                                                                   0 /*PLANESIDE_EPSILON*/, &cw[0], &cw[1] ); /* strict, in parallel case we get the face back because it also is the midwinding */
1046                 for ( j = 0 ; j < 2 ; j++ )
1047                 {
1048                         if ( !cw[j] ) {
1049                                 continue;
1050                         }
1051                         cs = &b[j]->sides[b[j]->numsides];
1052                         b[j]->numsides++;
1053                         *cs = *s;
1054                         cs->winding = cw[j];
1055                 }
1056         }
1057
1058
1059         // see if we have valid polygons on both sides
1060         for ( i = 0 ; i < 2 ; i++ )
1061         {
1062                 if ( b[i]->numsides < 3 || !BoundBrush( b[i] ) ) {
1063                         if ( b[i]->numsides >= 3 ) {
1064                                 Sys_FPrintf( SYS_VRB,"bogus brush after clip\n" );
1065                         }
1066                         FreeBrush( b[i] );
1067                         b[i] = NULL;
1068                 }
1069         }
1070
1071         if ( !( b[0] && b[1] ) ) {
1072                 if ( !b[0] && !b[1] ) {
1073                         Sys_FPrintf( SYS_VRB,"split removed brush\n" );
1074                 }
1075                 else{
1076                         Sys_FPrintf( SYS_VRB,"split not on both sides\n" );
1077                 }
1078                 if ( b[0] ) {
1079                         FreeBrush( b[0] );
1080                         *front = CopyBrush( brush );
1081                 }
1082                 if ( b[1] ) {
1083                         FreeBrush( b[1] );
1084                         *back = CopyBrush( brush );
1085                 }
1086                 return;
1087         }
1088
1089         // add the midwinding to both sides
1090         for ( i = 0 ; i < 2 ; i++ )
1091         {
1092                 cs = &b[i]->sides[b[i]->numsides];
1093                 b[i]->numsides++;
1094
1095                 cs->planenum = planenum ^ i ^ 1;
1096                 cs->shaderInfo = NULL;
1097                 if ( i == 0 ) {
1098                         cs->winding = CopyWinding( midwinding );
1099                 }
1100                 else{
1101                         cs->winding = midwinding;
1102                 }
1103         }
1104
1105         {
1106                 vec_t v1;
1107                 int i;
1108
1109
1110                 for ( i = 0 ; i < 2 ; i++ )
1111                 {
1112                         v1 = BrushVolume( b[i] );
1113                         if ( v1 < 1.0 ) {
1114                                 FreeBrush( b[i] );
1115                                 b[i] = NULL;
1116                                 //                      Sys_FPrintf (SYS_VRB,"tiny volume after clip\n");
1117                         }
1118                 }
1119         }
1120
1121         *front = b[0];
1122         *back = b[1];
1123 }