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