tools/quake3/q3map2/brush.c

   1 /* -------------------------------------------------------------------------------
   2
   3 Copyright (C) 1999-2006 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; 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         int                     c;
  97
  98
  99         /* allocate and clear */
 100         if( numSides <= 0 )
 101                 Error( "AllocBrush called with numsides = %d", numSides );
 102         c = (int) &(((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( *((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, (int) &(((brush_t*) 0)->sides[ b->numsides ]) );
 138         *((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; 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         int                     size;
 177         int                     i;
 178
 179
 180         /* copy brush */
 181         size = (int) &(((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 /*
 283 FixWinding() - ydnar
 284 removes degenerate edges from a winding
 285 returns qtrue if the winding is valid
 286 */
 287
 288 #define DEGENERATE_EPSILON      0.1
 289
 290 qboolean FixWinding( winding_t *w )
 291 {
 292         qboolean        valid = qtrue;
 293         int                     i, j, k;
 294         vec3_t          vec;
 295         float           dist;
 296
 297
 298         /* dummy check */
 299         if( !w )
 300                 return qfalse;
 301
 302         /* check all verts */
 303         for( i = 0; i < w->numpoints; i++ )
 304         {
 305                 /* don't remove points if winding is a triangle */
 306                 if( w->numpoints == 3 )
 307                         return valid;
 308
 309                 /* get second point index */
 310                 j = (i + 1) % w->numpoints;
 311
 312                 /* degenerate edge? */
 313                 VectorSubtract( w->p[ i ], w->p[ j ], vec );
 314                 dist = VectorLength( vec );
 315                 if( dist < DEGENERATE_EPSILON )
 316                 {
 317                         valid = qfalse;
 318                         //Sys_FPrintf( SYS_VRB, "WARNING: Degenerate winding edge found, fixing...\n" );
 319
 320                         /* create an average point (ydnar 2002-01-26: using nearest-integer weld preference) */
 321                         SnapWeldVector( w->p[ i ], w->p[ j ], vec );
 322                         VectorCopy( vec, w->p[ i ] );
 323                         //VectorAdd( w->p[ i ], w->p[ j ], vec );
 324                         //VectorScale( vec, 0.5, w->p[ i ] );
 325
 326                         /* move the remaining verts */
 327                         for( k = i + 2; k < w->numpoints; k++ )
 328                         {
 329                                 VectorCopy( w->p[ k ], w->p[ k - 1 ] );
 330                         }
 331                         w->numpoints--;
 332                 }
 333         }
 334
 335         /* one last check and return */
 336         if( w->numpoints < 3 )
 337                 valid = qfalse;
 338         return valid;
 339 }
 340
 341
 342
 343
 344
 345
 346
 347 /*
 348 CreateBrushWindings()
 349 makes basewindigs for sides and mins/maxs for the brush
 350 returns false if the brush doesn't enclose a valid volume
 351 */
 352
 353 qboolean CreateBrushWindings( brush_t *brush )
 354 {
 355         int                     i, j;
 356         winding_t       *w;
 357         side_t          *side;
 358         plane_t         *plane;
 359
 360
 361         /* walk the list of brush sides */
 362         for( i = 0; i < brush->numsides; i++ )
 363         {
 364                 /* get side and plane */
 365                 side = &brush->sides[ i ];
 366                 plane = &mapplanes[ side->planenum ];
 367
 368                 /* make huge winding */
 369                 w = BaseWindingForPlane( plane->normal, plane->dist );
 370
 371                 /* walk the list of brush sides */
 372                 for( j = 0; j < brush->numsides && w != NULL; j++ )
 373                 {
 374                         if( i == j )
 375                                 continue;
 376                         if( brush->sides[ j ].planenum == (brush->sides[ i ].planenum ^ 1) )
 377                                 continue;               /* back side clipaway */
 378                         if( brush->sides[ j ].bevel )
 379                                 continue;
 380                         plane = &mapplanes[ brush->sides[ j ].planenum ^ 1 ];
 381                         ChopWindingInPlace( &w, plane->normal, plane->dist, 0 ); // CLIP_EPSILON );
 382
 383                         /* ydnar: fix broken windings that would generate trifans */
 384                         FixWinding( w );
 385                 }
 386
 387                 /* set side winding */
 388                 side->winding = w;
 389         }
 390
 391         /* find brush bounds */
 392         return BoundBrush( brush );
 393 }
 394
 395
 396
 397
 398 /*
 399 ==================
 400 BrushFromBounds
 401
 402 Creates a new axial brush
 403 ==================
 404 */
 405 brush_t *BrushFromBounds (vec3_t mins, vec3_t maxs)
 406 {
 407         brush_t         *b;
 408         int                     i;
 409         vec3_t          normal;
 410         vec_t           dist;
 411
 412         b = AllocBrush (6);
 413         b->numsides = 6;
 414         for (i=0 ; i<3 ; i++)
 415         {
 416                 VectorClear (normal);
 417                 normal[i] = 1;
 418                 dist = maxs[i];
 419                 b->sides[i].planenum = FindFloatPlane (normal, dist, 1, (vec3_t*) &maxs );
 420
 421                 normal[i] = -1;
 422                 dist = -mins[i];
 423                 b->sides[3+i].planenum = FindFloatPlane (normal, dist, 1, (vec3_t*) &mins );
 424         }
 425
 426         CreateBrushWindings (b);
 427
 428         return b;
 429 }
 430
 431 /*
 432 ==================
 433 BrushVolume
 434
 435 ==================
 436 */
 437 vec_t BrushVolume (brush_t *brush)
 438 {
 439         int                     i;
 440         winding_t       *w;
 441         vec3_t          corner;
 442         vec_t           d, area, volume;
 443         plane_t         *plane;
 444
 445         if (!brush)
 446                 return 0;
 447
 448         // grab the first valid point as the corner
 449
 450         w = NULL;
 451         for (i=0 ; i<brush->numsides ; i++)
 452         {
 453                 w = brush->sides[i].winding;
 454                 if (w)
 455                         break;
 456         }
 457         if (!w)
 458                 return 0;
 459         VectorCopy (w->p[0], corner);
 460
 461         // make tetrahedrons to all other faces
 462
 463         volume = 0;
 464         for ( ; i<brush->numsides ; i++)
 465         {
 466                 w = brush->sides[i].winding;
 467                 if (!w)
 468                         continue;
 469                 plane = &mapplanes[brush->sides[i].planenum];
 470                 d = -(DotProduct (corner, plane->normal) - plane->dist);
 471                 area = WindingArea (w);
 472                 volume += d*area;
 473         }
 474
 475         volume /= 3;
 476         return volume;
 477 }
 478
 479
 480
 481 /*
 482 WriteBSPBrushMap()
 483 writes a map with the split bsp brushes
 484 */
 485
 486 void WriteBSPBrushMap( char *name, brush_t *list )
 487 {
 488         FILE            *f;
 489         side_t          *s;
 490         int                     i;
 491         winding_t       *w;
 492
 493
 494         /* note it */
 495         Sys_Printf( "Writing %s\n", name );
 496
 497         /* open the map file */
 498         f = fopen( name, "wb" );
 499         if( f == NULL )
 500                 Error( "Can't write %s\b", name );
 501
 502         fprintf (f, "{\n\"classname\" \"worldspawn\"\n");
 503
 504         for ( ; list ; list=list->next )
 505         {
 506                 fprintf (f, "{\n");
 507                 for (i=0,s=list->sides ; i<list->numsides ; i++,s++)
 508                 {
 509                         w = BaseWindingForPlane (mapplanes[s->planenum].normal, mapplanes[s->planenum].dist);
 510
 511                         fprintf (f,"( %i %i %i ) ", (int)w->p[0][0], (int)w->p[0][1], (int)w->p[0][2]);
 512                         fprintf (f,"( %i %i %i ) ", (int)w->p[1][0], (int)w->p[1][1], (int)w->p[1][2]);
 513                         fprintf (f,"( %i %i %i ) ", (int)w->p[2][0], (int)w->p[2][1], (int)w->p[2][2]);
 514
 515                         fprintf (f, "notexture 0 0 0 1 1\n" );
 516                         FreeWinding (w);
 517                 }
 518                 fprintf (f, "}\n");
 519         }
 520         fprintf (f, "}\n");
 521
 522         fclose (f);
 523
 524 }
 525
 526
 527
 528 /*
 529 FilterBrushIntoTree_r()
 530 adds brush reference to any intersecting bsp leafnode
 531 */
 532
 533 int FilterBrushIntoTree_r( brush_t *b, node_t *node )
 534 {
 535         brush_t         *front, *back;
 536         int                     c;
 537
 538
 539         /* dummy check */
 540         if( b == NULL )
 541                 return 0;
 542
 543         /* add it to the leaf list */
 544         if( node->planenum == PLANENUM_LEAF )
 545         {
 546                 /* something somewhere is hammering brushlist */
 547                 b->next = node->brushlist;
 548                 node->brushlist = b;
 549
 550                 /* classify the leaf by the structural brush */
 551                 if( !b->detail )
 552                 {
 553                         if( b->opaque )
 554                         {
 555                                 node->opaque = qtrue;
 556                                 node->areaportal = qfalse;
 557                         }
 558                         else if( b->compileFlags & C_AREAPORTAL )
 559                         {
 560                                 if( !node->opaque )
 561                                         node->areaportal = qtrue;
 562                         }
 563                 }
 564
 565                 return 1;
 566         }
 567
 568         /* split it by the node plane */
 569         c = b->numsides;
 570         SplitBrush( b, node->planenum, &front, &back );
 571         FreeBrush( b );
 572
 573         c = 0;
 574         c += FilterBrushIntoTree_r( front, node->children[ 0 ] );
 575         c += FilterBrushIntoTree_r( back, node->children[ 1 ] );
 576
 577         return c;
 578 }
 579
 580
 581
 582 /*
 583 FilterDetailBrushesIntoTree
 584 fragment all the detail brushes into the structural leafs
 585 */
 586
 587 void FilterDetailBrushesIntoTree( entity_t *e, tree_t *tree )
 588 {
 589         brush_t                         *b, *newb;
 590         int                                     r;
 591         int                                     c_unique, c_clusters;
 592         int                                     i;
 593
 594
 595         /* note it */
 596         Sys_FPrintf( SYS_VRB,  "--- FilterDetailBrushesIntoTree ---\n" );
 597
 598         /* walk the list of brushes */
 599         c_unique = 0;
 600         c_clusters = 0;
 601         for( b = e->brushes; b; b = b->next )
 602         {
 603                 if( !b->detail )
 604                         continue;
 605                 c_unique++;
 606                 newb = CopyBrush( b );
 607                 r = FilterBrushIntoTree_r( newb, tree->headnode );
 608                 c_clusters += r;
 609
 610                 /* mark all sides as visible so drawsurfs are created */
 611                 if( r )
 612                 {
 613                         for( i = 0; i < b->numsides; i++ )
 614                         {
 615                                 if( b->sides[ i ].winding )
 616                                         b->sides[ i ].visible = qtrue;
 617                         }
 618                 }
 619         }
 620
 621         /* emit some statistics */
 622         Sys_FPrintf( SYS_VRB, "%9d detail brushes\n", c_unique );
 623         Sys_FPrintf( SYS_VRB, "%9d cluster references\n", c_clusters );
 624 }
 625
 626 /*
 627 =====================
 628 FilterStructuralBrushesIntoTree
 629
 630 Mark the leafs as opaque and areaportals
 631 =====================
 632 */
 633 void FilterStructuralBrushesIntoTree( entity_t *e, tree_t *tree ) {
 634         brush_t                 *b, *newb;
 635         int                                     r;
 636         int                                     c_unique, c_clusters;
 637         int                                     i;
 638
 639         Sys_FPrintf (SYS_VRB, "--- FilterStructuralBrushesIntoTree ---\n");
 640
 641         c_unique = 0;
 642         c_clusters = 0;
 643         for ( b = e->brushes ; b ; b = b->next ) {
 644                 if ( b->detail ) {
 645                         continue;
 646                 }
 647                 c_unique++;
 648                 newb = CopyBrush( b );
 649                 r = FilterBrushIntoTree_r( newb, tree->headnode );
 650                 c_clusters += r;
 651
 652                 // mark all sides as visible so drawsurfs are created
 653                 if ( r ) {
 654                         for ( i = 0 ; i < b->numsides ; i++ ) {
 655                                 if ( b->sides[i].winding ) {
 656                                         b->sides[i].visible = qtrue;
 657                                 }
 658                         }
 659                 }
 660         }
 661
 662         /* emit some statistics */
 663         Sys_FPrintf( SYS_VRB, "%9d structural brushes\n", c_unique );
 664         Sys_FPrintf( SYS_VRB, "%9d cluster references\n", c_clusters );
 665 }
 666
 667
 668
 669 /*
 670 ================
 671 AllocTree
 672 ================
 673 */
 674 tree_t *AllocTree (void)
 675 {
 676         tree_t  *tree;
 677
 678         tree = safe_malloc(sizeof(*tree));
 679         memset (tree, 0, sizeof(*tree));
 680         ClearBounds (tree->mins, tree->maxs);
 681
 682         return tree;
 683 }
 684
 685 /*
 686 ================
 687 AllocNode
 688 ================
 689 */
 690 node_t *AllocNode (void)
 691 {
 692         node_t  *node;
 693
 694         node = safe_malloc(sizeof(*node));
 695         memset (node, 0, sizeof(*node));
 696
 697         return node;
 698 }
 699
 700
 701 /*
 702 ================
 703 WindingIsTiny
 704
 705 Returns true if the winding would be crunched out of
 706 existance by the vertex snapping.
 707 ================
 708 */
 709 #define EDGE_LENGTH     0.2
 710 qboolean WindingIsTiny (winding_t *w)
 711 {
 712 /*
 713         if (WindingArea (w) < 1)
 714                 return qtrue;
 715         return qfalse;
 716 */
 717         int             i, j;
 718         vec_t   len;
 719         vec3_t  delta;
 720         int             edges;
 721
 722         edges = 0;
 723         for (i=0 ; i<w->numpoints ; i++)
 724         {
 725                 j = i == w->numpoints - 1 ? 0 : i+1;
 726                 VectorSubtract (w->p[j], w->p[i], delta);
 727                 len = VectorLength (delta);
 728                 if (len > EDGE_LENGTH)
 729                 {
 730                         if (++edges == 3)
 731                                 return qfalse;
 732                 }
 733         }
 734         return qtrue;
 735 }
 736
 737 /*
 738 ================
 739 WindingIsHuge
 740
 741 Returns true if the winding still has one of the points
 742 from basewinding for plane
 743 ================
 744 */
 745 qboolean WindingIsHuge (winding_t *w)
 746 {
 747         int             i, j;
 748
 749         for (i=0 ; i<w->numpoints ; i++)
 750         {
 751                 for (j=0 ; j<3 ; j++)
 752                         if (w->p[i][j] <= MIN_WORLD_COORD || w->p[i][j] >= MAX_WORLD_COORD)
 753                                 return qtrue;
 754         }
 755         return qfalse;
 756 }
 757
 758 //============================================================
 759
 760 /*
 761 ==================
 762 BrushMostlyOnSide
 763
 764 ==================
 765 */
 766 int BrushMostlyOnSide (brush_t *brush, plane_t *plane)
 767 {
 768         int                     i, j;
 769         winding_t       *w;
 770         vec_t           d, max;
 771         int                     side;
 772
 773         max = 0;
 774         side = PSIDE_FRONT;
 775         for (i=0 ; i<brush->numsides ; i++)
 776         {
 777                 w = brush->sides[i].winding;
 778                 if (!w)
 779                         continue;
 780                 for (j=0 ; j<w->numpoints ; j++)
 781                 {
 782                         d = DotProduct (w->p[j], plane->normal) - plane->dist;
 783                         if (d > max)
 784                         {
 785                                 max = d;
 786                                 side = PSIDE_FRONT;
 787                         }
 788                         if (-d > max)
 789                         {
 790                                 max = -d;
 791                                 side = PSIDE_BACK;
 792                         }
 793                 }
 794         }
 795         return side;
 796 }
 797
 798
 799
 800 /*
 801 SplitBrush()
 802 generates two new brushes, leaving the original unchanged
 803 */
 804
 805 void SplitBrush( brush_t *brush, int planenum, brush_t **front, brush_t **back )
 806 {
 807         brush_t         *b[2];
 808         int                     i, j;
 809         winding_t       *w, *cw[2], *midwinding;
 810         plane_t         *plane, *plane2;
 811         side_t          *s, *cs;
 812         float           d, d_front, d_back;
 813
 814
 815         *front = NULL;
 816         *back = NULL;
 817         plane = &mapplanes[planenum];
 818
 819         // check all points
 820         d_front = d_back = 0;
 821         for (i=0 ; i<brush->numsides ; i++)
 822         {
 823                 w = brush->sides[i].winding;
 824                 if (!w)
 825                         continue;
 826                 for (j=0 ; j<w->numpoints ; j++)
 827                 {
 828                         d = DotProduct (w->p[j], plane->normal) - plane->dist;
 829                         if (d > 0 && d > d_front)
 830                                 d_front = d;
 831                         if (d < 0 && d < d_back)
 832                                 d_back = d;
 833                 }
 834         }
 835
 836         if (d_front < 0.1) // PLANESIDE_EPSILON)
 837         {       // only on back
 838                 *back = CopyBrush( brush );
 839                 return;
 840         }
 841
 842         if (d_back > -0.1) // PLANESIDE_EPSILON)
 843         {       // only on front
 844                 *front = CopyBrush( brush );
 845                 return;
 846         }
 847
 848         // create a new winding from the split plane
 849         w = BaseWindingForPlane (plane->normal, plane->dist);
 850         for (i=0 ; i<brush->numsides && w ; i++)
 851         {
 852                 plane2 = &mapplanes[brush->sides[i].planenum ^ 1];
 853                 ChopWindingInPlace (&w, plane2->normal, plane2->dist, 0); // PLANESIDE_EPSILON);
 854         }
 855
 856         if (!w || WindingIsTiny (w) )
 857         {       // the brush isn't really split
 858                 int             side;
 859
 860                 side = BrushMostlyOnSide (brush, plane);
 861                 if (side == PSIDE_FRONT)
 862                         *front = CopyBrush (brush);
 863                 if (side == PSIDE_BACK)
 864                         *back = CopyBrush (brush);
 865                 return;
 866         }
 867
 868         if( WindingIsHuge( w ) )
 869                 Sys_FPrintf( SYS_VRB,"WARNING: huge winding\n" );
 870
 871         midwinding = w;
 872
 873         // split it for real
 874
 875         for (i=0 ; i<2 ; i++)
 876         {
 877                 b[i] = AllocBrush (brush->numsides+1);
 878                 memcpy( b[i], brush, sizeof( brush_t ) - sizeof( brush->sides ) );
 879                 b[i]->numsides = 0;
 880                 b[i]->next = NULL;
 881                 b[i]->original = brush->original;
 882         }
 883
 884         // split all the current windings
 885
 886         for (i=0 ; i<brush->numsides ; i++)
 887         {
 888                 s = &brush->sides[i];
 889                 w = s->winding;
 890                 if (!w)
 891                         continue;
 892                 ClipWindingEpsilon (w, plane->normal, plane->dist,
 893                         0 /*PLANESIDE_EPSILON*/, &cw[0], &cw[1]);
 894                 for (j=0 ; j<2 ; j++)
 895                 {
 896                         if (!cw[j])
 897                                 continue;
 898                         cs = &b[j]->sides[b[j]->numsides];
 899                         b[j]->numsides++;
 900                         *cs = *s;
 901                         cs->winding = cw[j];
 902                 }
 903         }
 904
 905
 906         // see if we have valid polygons on both sides
 907         for (i=0 ; i<2 ; i++)
 908         {
 909                 BoundBrush (b[i]);
 910                 for (j=0 ; j<3 ; j++)
 911                 {
 912                         if (b[i]->mins[j] < MIN_WORLD_COORD || b[i]->maxs[j] > MAX_WORLD_COORD)
 913                         {
 914                                 Sys_FPrintf (SYS_VRB,"bogus brush after clip\n");
 915                                 break;
 916                         }
 917                 }
 918
 919                 if (b[i]->numsides < 3 || j < 3)
 920                 {
 921                         FreeBrush (b[i]);
 922                         b[i] = NULL;
 923                 }
 924         }
 925
 926         if ( !(b[0] && b[1]) )
 927         {
 928                 if (!b[0] && !b[1])
 929                         Sys_FPrintf (SYS_VRB,"split removed brush\n");
 930                 else
 931                         Sys_FPrintf (SYS_VRB,"split not on both sides\n");
 932                 if (b[0])
 933                 {
 934                         FreeBrush (b[0]);
 935                         *front = CopyBrush (brush);
 936                 }
 937                 if (b[1])
 938                 {
 939                         FreeBrush (b[1]);
 940                         *back = CopyBrush (brush);
 941                 }
 942                 return;
 943         }
 944
 945         // add the midwinding to both sides
 946         for (i=0 ; i<2 ; i++)
 947         {
 948                 cs = &b[i]->sides[b[i]->numsides];
 949                 b[i]->numsides++;
 950
 951                 cs->planenum = planenum^i^1;
 952                 cs->shaderInfo = NULL;
 953                 if (i==0)
 954                         cs->winding = CopyWinding (midwinding);
 955                 else
 956                         cs->winding = midwinding;
 957         }
 958
 959         {
 960                 vec_t   v1;
 961                 int             i;
 962
 963
 964                 for (i=0 ; i<2 ; i++)
 965                 {
 966                         v1 = BrushVolume (b[i]);
 967                         if (v1 < 1.0)
 968                         {
 969                                 FreeBrush (b[i]);
 970                                 b[i] = NULL;
 971         //                      Sys_FPrintf (SYS_VRB,"tiny volume after clip\n");
 972                         }
 973                 }
 974         }
 975
 976         *front = b[0];
 977         *back = b[1];
 978 }