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