tools/quake3/q3map2/brush.c

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