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