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