tools/quake3/q3map2/brush.c

   1 /*
   2 Copyright (C) 1999-2007 id Software, Inc. and contributors.
   3 For a list of contributors, see the accompanying CONTRIBUTORS file.
   4
   5 This file is part of GtkRadiant.
   6
   7 GtkRadiant is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2 of the License, or
  10 (at your option) any later version.
  11
  12 GtkRadiant is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GtkRadiant; if not, write to the Free Software
  19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  20
  21 ----------------------------------------------------------------------------------
  22
  23 This code has been altered significantly from its original form, to support
  24 several games based on the Quake III Arena engine, in the form of "Q3Map2."
  25
  26 ------------------------------------------------------------------------------- */
  27
  28
  29
  30 /* marker */
  31 #define BRUSH_C
  32
  33
  34
  35 /* dependencies */
  36 #include "q3map2.h"
  37
  38
  39
  40 /* -------------------------------------------------------------------------------
  41
  42 functions
  43
  44 ------------------------------------------------------------------------------- */
  45
  46 /*
  47 AllocSideRef() - ydnar
  48 allocates and assigns a brush side reference
  49 */
  50
  51 sideRef_t *AllocSideRef( side_t *side, sideRef_t *next )
  52 {
  53         sideRef_t *sideRef;
  54
  55
  56         /* dummy check */
  57         if( side == NULL )
  58                 return next;
  59
  60         /* allocate and return */
  61         sideRef = safe_malloc( sizeof( *sideRef ) );
  62         sideRef->side = side;
  63         sideRef->next = next;
  64         return sideRef;
  65 }
  66
  67
  68
  69 /*
  70 CountBrushList()
  71 counts the number of brushes in a brush linked list
  72 */
  73
  74 int     CountBrushList( brush_t *brushes )
  75 {
  76         int     c = 0;
  77
  78
  79         /* count brushes */
  80         for( brushes; brushes != NULL; brushes = brushes->next )
  81                 c++;
  82         return c;
  83 }
  84
  85
  86
  87 /*
  88 AllocBrush()
  89 allocates a new brush
  90 */
  91
  92 brush_t *AllocBrush( int numSides )
  93 {
  94         brush_t         *bb;
  95         int                     c;
  96
  97
  98         /* allocate and clear */
  99         if( numSides <= 0 )
 100                 Error( "AllocBrush called with numsides = %d", numSides );
 101         c = (int) &(((brush_t*) 0)->sides[ numSides ]);
 102         bb = safe_malloc( c );
 103         memset( bb, 0, c );
 104         if( numthreads == 1 )
 105                 numActiveBrushes++;
 106
 107         /* return it */
 108         return bb;
 109 }
 110
 111
 112
 113 /*
 114 FreeBrush()
 115 frees a single brush and all sides/windings
 116 */
 117
 118 void FreeBrush( brush_t *b )
 119 {
 120         int                     i;
 121
 122
 123         /* error check */
 124         if( *((int*) b) == 0xFEFEFEFE )
 125         {
 126                 Sys_FPrintf( SYS_VRB, "WARNING: Attempt to free an already freed brush!\n" );
 127                 return;
 128         }
 129
 130         /* free brush sides */
 131         for( i = 0; i < b->numsides; i++ )
 132                 if( b->sides[i].winding != NULL )
 133                         FreeWinding( b->sides[ i ].winding );
 134
 135         /* ydnar: overwrite it */
 136         memset( b, 0xFE, (int) &(((brush_t*) 0)->sides[ b->numsides ]) );
 137         *((int*) b) = 0xFEFEFEFE;
 138
 139         /* free it */
 140         free( b );
 141         if( numthreads == 1 )
 142                 numActiveBrushes--;
 143 }
 144
 145
 146
 147 /*
 148 FreeBrushList()
 149 frees a linked list of brushes
 150 */
 151
 152 void FreeBrushList( brush_t *brushes )
 153 {
 154         brush_t         *next;
 155
 156
 157         /* walk brush list */
 158         for( brushes; brushes != NULL; brushes = next )
 159         {
 160                 next = brushes->next;
 161                 FreeBrush( brushes );
 162         }
 163 }
 164
 165
 166
 167 /*
 168 CopyBrush()
 169 duplicates the brush, sides, and windings
 170 */
 171
 172 brush_t *CopyBrush( brush_t *brush )
 173 {
 174         brush_t         *newBrush;
 175         int                     size;
 176         int                     i;
 177
 178
 179         /* copy brush */
 180         size = (int) &(((brush_t*) 0)->sides[ brush->numsides ]);
 181         newBrush = AllocBrush( brush->numsides );
 182         memcpy( newBrush, brush, size );
 183
 184         /* ydnar: nuke linked list */
 185         newBrush->next = NULL;
 186
 187         /* copy sides */
 188         for( i = 0; i < brush->numsides; i++ )
 189         {
 190                 if( brush->sides[ i ].winding != NULL )
 191                         newBrush->sides[ i ].winding = CopyWinding( brush->sides[ i ].winding );
 192         }
 193
 194         /* return it */
 195         return newBrush;
 196 }
 197
 198
 199
 200
 201 /*
 202 BoundBrush()
 203 sets the mins/maxs based on the windings
 204 returns false if the brush doesn't enclose a valid volume
 205 */
 206
 207 qboolean BoundBrush( brush_t *brush )
 208 {
 209         int                     i, j;
 210         winding_t       *w;
 211
 212
 213         ClearBounds( brush->mins, brush->maxs );
 214         for( i = 0; i < brush->numsides; i++ )
 215         {
 216                 w = brush->sides[ i ].winding;
 217                 if( w == NULL )
 218                         continue;
 219                 for( j = 0; j < w->numpoints; j++ )
 220                         AddPointToBounds( w->p[ j ], brush->mins, brush->maxs );
 221         }
 222
 223         for( i = 0; i < 3; i++ )
 224         {
 225                 if( brush->mins[ i ] < MIN_WORLD_COORD || brush->maxs[ i ] > MAX_WORLD_COORD || brush->mins[i] >= brush->maxs[ i ] )
 226                         return qfalse;
 227         }
 228
 229         return qtrue;
 230 }
 231
 232
 233
 234
 235 /*
 236 SnapWeldVector() - ydnar
 237 welds two vec3_t's into a third, taking into account nearest-to-integer
 238 instead of averaging
 239 */
 240
 241 #define SNAP_EPSILON    0.01
 242
 243 void SnapWeldVector( vec3_t a, vec3_t b, vec3_t out )
 244 {
 245         int             i;
 246         vec_t   ai, bi, outi;
 247
 248
 249         /* dummy check */
 250         if( a == NULL || b == NULL || out == NULL )
 251                 return;
 252
 253         /* do each element */
 254         for( i = 0; i < 3; i++ )
 255         {
 256                 /* round to integer */
 257                 ai = Q_rint( a[ i ] );
 258                 bi = Q_rint( a[ i ] );
 259
 260                 /* prefer exact integer */
 261                 if( ai == a[ i ] )
 262                         out[ i ] = a[ i ];
 263                 else if( bi == b[ i ] )
 264                         out[ i ] = b[ i ];
 265
 266                 /* use nearest */
 267                 else if( fabs( ai - a[ i ] ) < fabs( bi < b[ i ] ) )
 268                         out[ i ] = a[ i ];
 269                 else
 270                         out[ i ] = b[ i ];
 271
 272                 /* snap */
 273                 outi = Q_rint( out[ i ] );
 274                 if( fabs( outi - out[ i ] ) <= SNAP_EPSILON )
 275                         out[ i ] = outi;
 276         }
 277 }
 278
 279
 280
 281 /*
 282 FixWinding() - ydnar
 283 removes degenerate edges from a winding
 284 returns qtrue if the winding is valid
 285 */
 286
 287 #define DEGENERATE_EPSILON      0.1
 288
 289 qboolean FixWinding( winding_t *w )
 290 {
 291         qboolean        valid = qtrue;
 292         int                     i, j, k;
 293         vec3_t          vec;
 294         float           dist;
 295
 296
 297         /* dummy check */
 298         if( !w )
 299                 return qfalse;
 300
 301         /* check all verts */
 302         for( i = 0; i < w->numpoints; i++ )
 303         {
 304                 /* don't remove points if winding is a triangle */
 305                 if( w->numpoints == 3 )
 306                         return valid;
 307
 308                 /* get second point index */
 309                 j = (i + 1) % w->numpoints;
 310
 311                 /* degenerate edge? */
 312                 VectorSubtract( w->p[ i ], w->p[ j ], vec );
 313                 dist = VectorLength( vec );
 314                 if( dist < DEGENERATE_EPSILON )
 315                 {
 316                         valid = qfalse;
 317                         //Sys_FPrintf( SYS_VRB, "WARNING: Degenerate winding edge found, fixing...\n" );
 318
 319                         /* create an average point (ydnar 2002-01-26: using nearest-integer weld preference) */
 320                         SnapWeldVector( w->p[ i ], w->p[ j ], vec );
 321                         VectorCopy( vec, w->p[ i ] );
 322                         //VectorAdd( w->p[ i ], w->p[ j ], vec );
 323                         //VectorScale( vec, 0.5, w->p[ i ] );
 324
 325                         /* move the remaining verts */
 326                         for( k = i + 2; k < w->numpoints; k++ )
 327                         {
 328                                 VectorCopy( w->p[ k ], w->p[ k - 1 ] );
 329                         }
 330                         w->numpoints--;
 331                 }
 332         }
 333
 334         /* one last check and return */
 335         if( w->numpoints < 3 )
 336                 valid = qfalse;
 337         return valid;
 338 }
 339
 340
 341
 342
 343
 344
 345
 346 /*
 347 CreateBrushWindings()
 348 makes basewindigs for sides and mins/maxs for the brush
 349 returns false if the brush doesn't enclose a valid volume
 350 */
 351
 352 qboolean CreateBrushWindings( brush_t *brush )
 353 {
 354         int                     i, j;
 355         winding_t       *w;
 356         side_t          *side;
 357         plane_t         *plane;
 358
 359
 360         /* walk the list of brush sides */
 361         for( i = 0; i < brush->numsides; i++ )
 362         {
 363                 /* get side and plane */
 364                 side = &brush->sides[ i ];
 365                 plane = &mapplanes[ side->planenum ];
 366
 367                 /* make huge winding */
 368                 w = BaseWindingForPlane( plane->normal, plane->dist );
 369
 370                 /* walk the list of brush sides */
 371                 for( j = 0; j < brush->numsides && w != NULL; j++ )
 372                 {
 373                         if( i == j )
 374                                 continue;
 375                         if( brush->sides[ j ].planenum == (brush->sides[ i ].planenum ^ 1) )
 376                                 continue;               /* back side clipaway */
 377                         if( brush->sides[ j ].bevel )
 378                                 continue;
 379                         if( brush->sides[ j ].backSide )
 380                                 continue;
 381                         plane = &mapplanes[ brush->sides[ j ].planenum ^ 1 ];
 382                         ChopWindingInPlace( &w, plane->normal, plane->dist, 0 ); // CLIP_EPSILON );
 383
 384                         /* ydnar: fix broken windings that would generate trifans */
 385                         FixWinding( w );
 386                 }
 387
 388                 /* set side winding */
 389                 side->winding = w;
 390         }
 391
 392         /* find brush bounds */
 393         return BoundBrush( brush );
 394 }
 395
 396
 397
 398
 399 /*
 400 ==================
 401 BrushFromBounds
 402
 403 Creates a new axial brush
 404 ==================
 405 */
 406 brush_t *BrushFromBounds (vec3_t mins, vec3_t maxs)
 407 {
 408         brush_t         *b;
 409         int                     i;
 410         vec3_t          normal;
 411         vec_t           dist;
 412
 413         b = AllocBrush (6);
 414         b->numsides = 6;
 415         for (i=0 ; i<3 ; i++)
 416         {
 417                 VectorClear (normal);
 418                 normal[i] = 1;
 419                 dist = maxs[i];
 420                 b->sides[i].planenum = FindFloatPlane (normal, dist, 1, (vec3_t*) &maxs );
 421
 422                 normal[i] = -1;
 423                 dist = -mins[i];
 424                 b->sides[3+i].planenum = FindFloatPlane (normal, dist, 1, (vec3_t*) &mins );
 425         }
 426
 427         CreateBrushWindings (b);
 428
 429         return b;
 430 }
 431
 432 /*
 433 ==================
 434 BrushVolume
 435
 436 ==================
 437 */
 438 vec_t BrushVolume (brush_t *brush)
 439 {
 440         int                     i;
 441         winding_t       *w;
 442         vec3_t          corner;
 443         vec_t           d, area, volume;
 444         plane_t         *plane;
 445
 446         if (!brush)
 447                 return 0;
 448
 449         // grab the first valid point as the corner
 450
 451         w = NULL;
 452         for (i=0 ; i<brush->numsides ; i++)
 453         {
 454                 w = brush->sides[i].winding;
 455                 if (w)
 456                         break;
 457         }
 458         if (!w)
 459                 return 0;
 460         VectorCopy (w->p[0], corner);
 461
 462         // make tetrahedrons to all other faces
 463
 464         volume = 0;
 465         for ( ; i<brush->numsides ; i++)
 466         {
 467                 w = brush->sides[i].winding;
 468                 if (!w)
 469                         continue;
 470                 plane = &mapplanes[brush->sides[i].planenum];
 471                 d = -(DotProduct (corner, plane->normal) - plane->dist);
 472                 area = WindingArea (w);
 473                 volume += d*area;
 474         }
 475
 476         volume /= 3;
 477         return volume;
 478 }
 479
 480
 481
 482 /*
 483 WriteBSPBrushMap()
 484 writes a map with the split bsp brushes
 485 */
 486
 487 void WriteBSPBrushMap( char *name, brush_t *list )
 488 {
 489         FILE            *f;
 490         side_t          *s;
 491         int                     i;
 492         winding_t       *w;
 493
 494
 495         /* note it */
 496         Sys_Printf( "Writing %s\n", name );
 497
 498         /* open the map file */
 499         f = fopen( name, "wb" );
 500         if( f == NULL )
 501                 Error( "Can't write %s\b", name );
 502
 503         fprintf (f, "{\n\"classname\" \"worldspawn\"\n");
 504
 505         for ( ; list ; list=list->next )
 506         {
 507                 fprintf (f, "{\n");
 508                 for (i=0,s=list->sides ; i<list->numsides ; i++,s++)
 509                 {
 510                         w = BaseWindingForPlane (mapplanes[s->planenum].normal, mapplanes[s->planenum].dist);
 511
 512                         fprintf (f,"( %i %i %i ) ", (int)w->p[0][0], (int)w->p[0][1], (int)w->p[0][2]);
 513                         fprintf (f,"( %i %i %i ) ", (int)w->p[1][0], (int)w->p[1][1], (int)w->p[1][2]);
 514                         fprintf (f,"( %i %i %i ) ", (int)w->p[2][0], (int)w->p[2][1], (int)w->p[2][2]);
 515
 516                         fprintf (f, "notexture 0 0 0 1 1\n" );
 517                         FreeWinding (w);
 518                 }
 519                 fprintf (f, "}\n");
 520         }
 521         fprintf (f, "}\n");
 522
 523         fclose (f);
 524
 525 }
 526
 527
 528
 529 /*
 530 FilterBrushIntoTree_r()
 531 adds brush reference to any intersecting bsp leafnode
 532 */
 533
 534 int FilterBrushIntoTree_r( brush_t *b, node_t *node )
 535 {
 536         brush_t         *front, *back;
 537         int                     c;
 538
 539
 540         /* dummy check */
 541         if( b == NULL )
 542                 return 0;
 543
 544         /* add it to the leaf list */
 545         if( node->planenum == PLANENUM_LEAF )
 546         {
 547                 /* something somewhere is hammering brushlist */
 548                 b->next = node->brushlist;
 549                 node->brushlist = b;
 550
 551                 /* classify the leaf by the structural brush */
 552                 if( !b->detail )
 553                 {
 554                         if( b->opaque )
 555                         {
 556                                 node->opaque = qtrue;
 557                                 node->areaportal = qfalse;
 558                         }
 559                         else if( b->compileFlags & C_AREAPORTAL )
 560                         {
 561                                 if( !node->opaque )
 562                                         node->areaportal = qtrue;
 563                         }
 564                 }
 565
 566                 return 1;
 567         }
 568
 569         /* split it by the node plane */
 570         c = b->numsides;
 571         SplitBrush( b, node->planenum, &front, &back );
 572         FreeBrush( b );
 573
 574         c = 0;
 575         c += FilterBrushIntoTree_r( front, node->children[ 0 ] );
 576         c += FilterBrushIntoTree_r( back, node->children[ 1 ] );
 577
 578         return c;
 579 }
 580
 581
 582
 583 /*
 584 FilterDetailBrushesIntoTree
 585 fragment all the detail brushes into the structural leafs
 586 */
 587
 588 void FilterDetailBrushesIntoTree( entity_t *e, tree_t *tree )
 589 {
 590         brush_t                         *b, *newb;
 591         int                                     r;
 592         int                                     c_unique, c_clusters;
 593         int                                     i;
 594
 595
 596         /* note it */
 597         Sys_FPrintf( SYS_VRB,  "--- FilterDetailBrushesIntoTree ---\n" );
 598
 599         /* walk the list of brushes */
 600         c_unique = 0;
 601         c_clusters = 0;
 602         for( b = e->brushes; b; b = b->next )
 603         {
 604                 if( !b->detail )
 605                         continue;
 606                 c_unique++;
 607                 newb = CopyBrush( b );
 608                 r = FilterBrushIntoTree_r( newb, tree->headnode );
 609                 c_clusters += r;
 610
 611                 /* mark all sides as visible so drawsurfs are created */
 612                 if( r )
 613                 {
 614                         for( i = 0; i < b->numsides; i++ )
 615                         {
 616                                 if( b->sides[ i ].winding )
 617                                         b->sides[ i ].visible = qtrue;
 618                         }
 619                 }
 620         }
 621
 622         /* emit some statistics */
 623         Sys_FPrintf( SYS_VRB, "%9d detail brushes\n", c_unique );
 624         Sys_FPrintf( SYS_VRB, "%9d cluster references\n", c_clusters );
 625 }
 626
 627 /*
 628 =====================
 629 FilterStructuralBrushesIntoTree
 630
 631 Mark the leafs as opaque and areaportals
 632 =====================
 633 */
 634 void FilterStructuralBrushesIntoTree( entity_t *e, tree_t *tree ) {
 635         brush_t                 *b, *newb;
 636         int                                     r;
 637         int                                     c_unique, c_clusters;
 638         int                                     i;
 639
 640         Sys_FPrintf (SYS_VRB, "--- FilterStructuralBrushesIntoTree ---\n");
 641
 642         c_unique = 0;
 643         c_clusters = 0;
 644         for ( b = e->brushes ; b ; b = b->next ) {
 645                 if ( b->detail ) {
 646                         continue;
 647                 }
 648                 c_unique++;
 649                 newb = CopyBrush( b );
 650                 r = FilterBrushIntoTree_r( newb, tree->headnode );
 651                 c_clusters += r;
 652
 653                 // mark all sides as visible so drawsurfs are created
 654                 if ( r ) {
 655                         for ( i = 0 ; i < b->numsides ; i++ ) {
 656                                 if ( b->sides[i].winding ) {
 657                                         b->sides[i].visible = qtrue;
 658                                 }
 659                         }
 660                 }
 661         }
 662
 663         /* emit some statistics */
 664         Sys_FPrintf( SYS_VRB, "%9d structural brushes\n", c_unique );
 665         Sys_FPrintf( SYS_VRB, "%9d cluster references\n", c_clusters );
 666 }
 667
 668
 669
 670 /*
 671 ================
 672 AllocTree
 673 ================
 674 */
 675 tree_t *AllocTree (void)
 676 {
 677         tree_t  *tree;
 678
 679         tree = safe_malloc(sizeof(*tree));
 680         memset (tree, 0, sizeof(*tree));
 681         ClearBounds (tree->mins, tree->maxs);
 682
 683         return tree;
 684 }
 685
 686 /*
 687 ================
 688 AllocNode
 689 ================
 690 */
 691 node_t *AllocNode (void)
 692 {
 693         node_t  *node;
 694
 695         node = safe_malloc(sizeof(*node));
 696         memset (node, 0, sizeof(*node));
 697
 698         return node;
 699 }
 700
 701
 702 /*
 703 ================
 704 WindingIsTiny
 705
 706 Returns true if the winding would be crunched out of
 707 existance by the vertex snapping.
 708 ================
 709 */
 710 #define EDGE_LENGTH     0.2
 711 qboolean WindingIsTiny (winding_t *w)
 712 {
 713 /*
 714         if (WindingArea (w) < 1)
 715                 return qtrue;
 716         return qfalse;
 717 */
 718         int             i, j;
 719         vec_t   len;
 720         vec3_t  delta;
 721         int             edges;
 722
 723         edges = 0;
 724         for (i=0 ; i<w->numpoints ; i++)
 725         {
 726                 j = i == w->numpoints - 1 ? 0 : i+1;
 727                 VectorSubtract (w->p[j], w->p[i], delta);
 728                 len = VectorLength (delta);
 729                 if (len > EDGE_LENGTH)
 730                 {
 731                         if (++edges == 3)
 732                                 return qfalse;
 733                 }
 734         }
 735         return qtrue;
 736 }
 737
 738 /*
 739 ================
 740 WindingIsHuge
 741
 742 Returns true if the winding still has one of the points
 743 from basewinding for plane
 744 ================
 745 */
 746 qboolean WindingIsHuge (winding_t *w)
 747 {
 748         int             i, j;
 749
 750         for (i=0 ; i<w->numpoints ; i++)
 751         {
 752                 for (j=0 ; j<3 ; j++)
 753                         if (w->p[i][j] <= MIN_WORLD_COORD || w->p[i][j] >= MAX_WORLD_COORD)
 754                                 return qtrue;
 755         }
 756         return qfalse;
 757 }
 758
 759 //============================================================
 760
 761 /*
 762 ==================
 763 BrushMostlyOnSide
 764
 765 ==================
 766 */
 767 int BrushMostlyOnSide (brush_t *brush, plane_t *plane)
 768 {
 769         int                     i, j;
 770         winding_t       *w;
 771         vec_t           d, max;
 772         int                     side;
 773
 774         max = 0;
 775         side = PSIDE_FRONT;
 776         for (i=0 ; i<brush->numsides ; i++)
 777         {
 778                 w = brush->sides[i].winding;
 779                 if (!w)
 780                         continue;
 781                 for (j=0 ; j<w->numpoints ; j++)
 782                 {
 783                         d = DotProduct (w->p[j], plane->normal) - plane->dist;
 784                         if (d > max)
 785                         {
 786                                 max = d;
 787                                 side = PSIDE_FRONT;
 788                         }
 789                         if (-d > max)
 790                         {
 791                                 max = -d;
 792                                 side = PSIDE_BACK;
 793                         }
 794                 }
 795         }
 796         return side;
 797 }
 798
 799
 800
 801 /*
 802 SplitBrush()
 803 generates two new brushes, leaving the original unchanged
 804 */
 805
 806 void SplitBrush( brush_t *brush, int planenum, brush_t **front, brush_t **back )
 807 {
 808         brush_t         *b[2];
 809         int                     i, j;
 810         winding_t       *w, *cw[2], *midwinding;
 811         plane_t         *plane, *plane2;
 812         side_t          *s, *cs;
 813         float           d, d_front, d_back;
 814
 815
 816         *front = NULL;
 817         *back = NULL;
 818         plane = &mapplanes[planenum];
 819
 820         // check all points
 821         d_front = d_back = 0;
 822         for (i=0 ; i<brush->numsides ; i++)
 823         {
 824                 w = brush->sides[i].winding;
 825                 if (!w)
 826                         continue;
 827                 for (j=0 ; j<w->numpoints ; j++)
 828                 {
 829                         d = DotProduct (w->p[j], plane->normal) - plane->dist;
 830                         if (d > 0 && d > d_front)
 831                                 d_front = d;
 832                         if (d < 0 && d < d_back)
 833                                 d_back = d;
 834                 }
 835         }
 836
 837         if (d_front < 0.1) // PLANESIDE_EPSILON)
 838         {       // only on back
 839                 *back = CopyBrush( brush );
 840                 return;
 841         }
 842
 843         if (d_back > -0.1) // PLANESIDE_EPSILON)
 844         {       // only on front
 845                 *front = CopyBrush( brush );
 846                 return;
 847         }
 848
 849         // create a new winding from the split plane
 850         w = BaseWindingForPlane (plane->normal, plane->dist);
 851         for (i=0 ; i<brush->numsides && w ; i++)
 852         {
 853                 if ( brush->sides[i].backSide ) {
 854                         continue;       // fake back-sided polygons never split
 855                 }
 856                 plane2 = &mapplanes[brush->sides[i].planenum ^ 1];
 857                 ChopWindingInPlace (&w, plane2->normal, plane2->dist, 0); // PLANESIDE_EPSILON);
 858         }
 859
 860         if (!w || WindingIsTiny (w) )
 861         {       // the brush isn't really split
 862                 int             side;
 863
 864                 side = BrushMostlyOnSide (brush, plane);
 865                 if (side == PSIDE_FRONT)
 866                         *front = CopyBrush (brush);
 867                 if (side == PSIDE_BACK)
 868                         *back = CopyBrush (brush);
 869                 return;
 870         }
 871
 872         if( WindingIsHuge( w ) )
 873                 Sys_FPrintf( SYS_VRB,"WARNING: huge winding\n" );
 874
 875         midwinding = w;
 876
 877         // split it for real
 878
 879         for (i=0 ; i<2 ; i++)
 880         {
 881                 b[i] = AllocBrush (brush->numsides+1);
 882                 memcpy( b[i], brush, sizeof( brush_t ) - sizeof( brush->sides ) );
 883                 b[i]->numsides = 0;
 884                 b[i]->next = NULL;
 885                 b[i]->original = brush->original;
 886         }
 887
 888         // split all the current windings
 889
 890         for (i=0 ; i<brush->numsides ; i++)
 891         {
 892                 s = &brush->sides[i];
 893                 w = s->winding;
 894                 if (!w)
 895                         continue;
 896                 ClipWindingEpsilon (w, plane->normal, plane->dist,
 897                         0 /*PLANESIDE_EPSILON*/, &cw[0], &cw[1]);
 898                 for (j=0 ; j<2 ; j++)
 899                 {
 900                         if (!cw[j])
 901                                 continue;
 902                         cs = &b[j]->sides[b[j]->numsides];
 903                         b[j]->numsides++;
 904                         *cs = *s;
 905                         cs->winding = cw[j];
 906                 }
 907         }
 908
 909
 910         // see if we have valid polygons on both sides
 911         for (i=0 ; i<2 ; i++)
 912         {
 913                 BoundBrush (b[i]);
 914                 for (j=0 ; j<3 ; j++)
 915                 {
 916                         if (b[i]->mins[j] < MIN_WORLD_COORD || b[i]->maxs[j] > MAX_WORLD_COORD)
 917                         {
 918                                 Sys_FPrintf (SYS_VRB,"bogus brush after clip\n");
 919                                 break;
 920                         }
 921                 }
 922
 923                 if (b[i]->numsides < 3 || j < 3)
 924                 {
 925                         FreeBrush (b[i]);
 926                         b[i] = NULL;
 927                 }
 928         }
 929
 930         if ( !(b[0] && b[1]) )
 931         {
 932                 if (!b[0] && !b[1])
 933                         Sys_FPrintf (SYS_VRB,"split removed brush\n");
 934                 else
 935                         Sys_FPrintf (SYS_VRB,"split not on both sides\n");
 936                 if (b[0])
 937                 {
 938                         FreeBrush (b[0]);
 939                         *front = CopyBrush (brush);
 940                 }
 941                 if (b[1])
 942                 {
 943                         FreeBrush (b[1]);
 944                         *back = CopyBrush (brush);
 945                 }
 946                 return;
 947         }
 948
 949         // add the midwinding to both sides
 950         for (i=0 ; i<2 ; i++)
 951         {
 952                 cs = &b[i]->sides[b[i]->numsides];
 953                 b[i]->numsides++;
 954
 955                 cs->planenum = planenum^i^1;
 956                 cs->shaderInfo = NULL;
 957                 if (i==0)
 958                         cs->winding = CopyWinding (midwinding);
 959                 else
 960                         cs->winding = midwinding;
 961         }
 962
 963         {
 964                 vec_t   v1;
 965                 int             i;
 966
 967
 968                 for (i=0 ; i<2 ; i++)
 969                 {
 970                         v1 = BrushVolume (b[i]);
 971                         if (v1 < 1.0)
 972                         {
 973                                 FreeBrush (b[i]);
 974                                 b[i] = NULL;
 975         //                      Sys_FPrintf (SYS_VRB,"tiny volume after clip\n");
 976                         }
 977                 }
 978         }
 979
 980         *front = b[0];
 981         *back = b[1];
 982 }