neo/tools/compilers/dmap/ubrush.cpp

   1 /*
   2 ===========================================================================
   3
   4 Doom 3 GPL Source Code
   5 Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company.
   6
   7 This file is part of the Doom 3 GPL Source Code (?Doom 3 Source Code?).
   8
   9 Doom 3 Source Code is free software: you can redistribute it and/or modify
  10 it under the terms of the GNU General Public License as published by
  11 the Free Software Foundation, either version 3 of the License, or
  12 (at your option) any later version.
  13
  14 Doom 3 Source Code is distributed in the hope that it will be useful,
  15 but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17 GNU General Public License for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with Doom 3 Source Code.  If not, see <http://www.gnu.org/licenses/>.
  21
  22 In addition, the Doom 3 Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the Doom 3 Source Code.  If not, please request a copy in writing from id Software at the address below.
  23
  24 If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.
  25
  26 ===========================================================================
  27 */
  28
  29 #include "../../../idlib/precompiled.h"
  30 #pragma hdrstop
  31
  32 #include "dmap.h"
  33
  34 int             c_active_brushes;
  35
  36 int             c_nodes;
  37
  38 // if a brush just barely pokes onto the other side,
  39 // let it slide by without chopping
  40 #define PLANESIDE_EPSILON       0.001
  41 //0.1
  42
  43
  44
  45
  46 /*
  47 ================
  48 CountBrushList
  49 ================
  50 */
  51 int     CountBrushList (uBrush_t *brushes)
  52 {
  53         int     c;
  54
  55         c = 0;
  56         for ( ; brushes ; brushes = brushes->next)
  57                 c++;
  58         return c;
  59 }
  60
  61
  62 int BrushSizeForSides( int numsides ) {
  63         int             c;
  64
  65         // allocate a structure with a variable number of sides at the end
  66 //      c = (int)&(((uBrush_t *)0)->sides[numsides]);   // bounds checker complains about this
  67         c = sizeof( uBrush_t ) + sizeof( side_t ) * (numsides - 6);
  68
  69         return c;
  70 }
  71
  72 /*
  73 ================
  74 AllocBrush
  75 ================
  76 */
  77 uBrush_t *AllocBrush (int numsides)
  78 {
  79         uBrush_t        *bb;
  80         int                     c;
  81
  82         c = BrushSizeForSides( numsides );
  83
  84         bb = (uBrush_t *)Mem_Alloc(c);
  85         memset (bb, 0, c);
  86         c_active_brushes++;
  87         return bb;
  88 }
  89
  90 /*
  91 ================
  92 FreeBrush
  93 ================
  94 */
  95 void FreeBrush (uBrush_t *brushes)
  96 {
  97         int                     i;
  98
  99         for ( i = 0 ; i < brushes->numsides ; i++ ) {
 100                 if ( brushes->sides[i].winding ) {
 101                         delete brushes->sides[i].winding;
 102                 }
 103                 if ( brushes->sides[i].visibleHull ) {
 104                         delete brushes->sides[i].visibleHull;
 105                 }
 106         }
 107         Mem_Free (brushes);
 108         c_active_brushes--;
 109 }
 110
 111
 112 /*
 113 ================
 114 FreeBrushList
 115 ================
 116 */
 117 void FreeBrushList (uBrush_t *brushes)
 118 {
 119         uBrush_t        *next;
 120
 121         for ( ; brushes ; brushes = next)
 122         {
 123                 next = brushes->next;
 124
 125                 FreeBrush (brushes);
 126         }
 127 }
 128
 129 /*
 130 ==================
 131 CopyBrush
 132
 133 Duplicates the brush, the sides, and the windings
 134 ==================
 135 */
 136 uBrush_t *CopyBrush (uBrush_t *brush)
 137 {
 138         uBrush_t *newbrush;
 139         int                     size;
 140         int                     i;
 141
 142         size = BrushSizeForSides( brush->numsides );
 143
 144         newbrush = AllocBrush (brush->numsides);
 145         memcpy (newbrush, brush, size);
 146
 147         for (i=0 ; i<brush->numsides ; i++)
 148         {
 149                 if (brush->sides[i].winding)
 150                         newbrush->sides[i].winding = brush->sides[i].winding->Copy();
 151         }
 152
 153         return newbrush;
 154 }
 155
 156
 157 /*
 158 ================
 159 DrawBrushList
 160 ================
 161 */
 162 void DrawBrushList (uBrush_t *brush)
 163 {
 164         int             i;
 165         side_t  *s;
 166
 167         GLS_BeginScene ();
 168         for ( ; brush ; brush=brush->next)
 169         {
 170                 for (i=0 ; i<brush->numsides ; i++)
 171                 {
 172                         s = &brush->sides[i];
 173                         if (!s->winding)
 174                                 continue;
 175                         GLS_Winding (s->winding, 0);
 176                 }
 177         }
 178         GLS_EndScene ();
 179 }
 180
 181
 182 /*
 183 =============
 184 PrintBrush
 185 =============
 186 */
 187 void PrintBrush (uBrush_t *brush)
 188 {
 189         int             i;
 190
 191         common->Printf( "brush: %p\n", brush );
 192         for ( i=0;i<brush->numsides ; i++ ) {
 193                 brush->sides[i].winding->Print();
 194                 common->Printf ("\n");
 195         }
 196 }
 197
 198 /*
 199 ==================
 200 BoundBrush
 201
 202 Sets the mins/maxs based on the windings
 203 returns false if the brush doesn't enclose a valid volume
 204 ==================
 205 */
 206 bool BoundBrush (uBrush_t *brush) {
 207         int                     i, j;
 208         idWinding       *w;
 209
 210         brush->bounds.Clear();
 211         for ( i = 0; i < brush->numsides; i++ ) {
 212                 w = brush->sides[i].winding;
 213                 if (!w)
 214                         continue;
 215                 for ( j = 0; j < w->GetNumPoints(); j++ )
 216                         brush->bounds.AddPoint( (*w)[j].ToVec3() );
 217         }
 218
 219         for ( i = 0; i < 3; i++ ) {
 220                 if (brush->bounds[0][i] < MIN_WORLD_COORD || brush->bounds[1][i] > MAX_WORLD_COORD
 221                         || brush->bounds[0][i] >= brush->bounds[1][i] ) {
 222                         return false;
 223                 }
 224         }
 225
 226         return true;
 227 }
 228
 229 /*
 230 ==================
 231 CreateBrushWindings
 232
 233 makes basewindigs for sides and mins / maxs for the brush
 234 returns false if the brush doesn't enclose a valid volume
 235 ==================
 236 */
 237 bool CreateBrushWindings (uBrush_t *brush) {
 238         int                     i, j;
 239         idWinding       *w;
 240         idPlane         *plane;
 241         side_t          *side;
 242
 243         for ( i = 0; i < brush->numsides; i++ ) {
 244                 side = &brush->sides[i];
 245                 plane = &dmapGlobals.mapPlanes[side->planenum];
 246                 w = new idWinding( *plane );
 247                 for ( j = 0; j < brush->numsides && w; j++ ) {
 248                         if ( i == j ) {
 249                                 continue;
 250                         }
 251                         if ( brush->sides[j].planenum == ( brush->sides[i].planenum ^ 1 ) ) {
 252                                 continue;               // back side clipaway
 253                         }
 254                         plane = &dmapGlobals.mapPlanes[brush->sides[j].planenum^1];
 255                         w = w->Clip( *plane, 0 );//CLIP_EPSILON);
 256                 }
 257                 if ( side->winding ) {
 258                         delete side->winding;
 259                 }
 260                 side->winding = w;
 261         }
 262
 263         return BoundBrush( brush );
 264 }
 265
 266 /*
 267 ==================
 268 BrushFromBounds
 269
 270 Creates a new axial brush
 271 ==================
 272 */
 273 uBrush_t        *BrushFromBounds( const idBounds &bounds ) {
 274         uBrush_t        *b;
 275         int                     i;
 276         idPlane         plane;
 277
 278         b = AllocBrush (6);
 279         b->numsides = 6;
 280         for (i=0 ; i<3 ; i++) {
 281                 plane[0] = plane[1] = plane[2] = 0;
 282                 plane[i] = 1;
 283                 plane[3] = -bounds[1][i];
 284                 b->sides[i].planenum = FindFloatPlane( plane );
 285
 286                 plane[i] = -1;
 287                 plane[3] = bounds[0][i];
 288                 b->sides[3+i].planenum = FindFloatPlane( plane );
 289         }
 290
 291         CreateBrushWindings (b);
 292
 293         return b;
 294 }
 295
 296 /*
 297 ==================
 298 BrushVolume
 299
 300 ==================
 301 */
 302 float BrushVolume (uBrush_t *brush) {
 303         int                     i;
 304         idWinding       *w;
 305         idVec3          corner;
 306         float           d, area, volume;
 307         idPlane         *plane;
 308
 309         if (!brush)
 310                 return 0;
 311
 312         // grab the first valid point as the corner
 313
 314         w = NULL;
 315         for ( i = 0; i < brush->numsides; i++ ) {
 316                 w = brush->sides[i].winding;
 317                 if (w)
 318                         break;
 319         }
 320         if (!w) {
 321                 return 0;
 322         }
 323         VectorCopy ( (*w)[0], corner);
 324
 325         // make tetrahedrons to all other faces
 326
 327         volume = 0;
 328         for ( ; i < brush->numsides; i++ )
 329         {
 330                 w = brush->sides[i].winding;
 331                 if (!w)
 332                         continue;
 333                 plane = &dmapGlobals.mapPlanes[brush->sides[i].planenum];
 334                 d = -plane->Distance( corner );
 335                 area = w->GetArea();
 336                 volume += d * area;
 337         }
 338
 339         volume /= 3;
 340         return volume;
 341 }
 342
 343
 344 /*
 345 ==================
 346 WriteBspBrushMap
 347
 348 FIXME: use new brush format
 349 ==================
 350 */
 351 void WriteBspBrushMap( const char *name, uBrush_t *list ) {
 352         idFile *        f;
 353         side_t *        s;
 354         int                     i;
 355         idWinding *     w;
 356
 357         common->Printf ("writing %s\n", name);
 358         f = fileSystem->OpenFileWrite( name );
 359
 360         if ( !f ) {
 361                 common->Error( "Can't write %s\b", name);
 362         }
 363
 364         f->Printf( "{\n\"classname\" \"worldspawn\"\n" );
 365
 366         for ( ; list ; list=list->next )
 367         {
 368                 f->Printf( "{\n" );
 369                 for (i=0,s=list->sides ; i<list->numsides ; i++,s++)
 370                 {
 371                         w = new idWinding( dmapGlobals.mapPlanes[s->planenum] );
 372
 373                         f->Printf ("( %i %i %i ) ", (int)(*w)[0][0], (int)(*w)[0][1], (int)(*w)[0][2]);
 374                         f->Printf ("( %i %i %i ) ", (int)(*w)[1][0], (int)(*w)[1][1], (int)(*w)[1][2]);
 375                         f->Printf ("( %i %i %i ) ", (int)(*w)[2][0], (int)(*w)[2][1], (int)(*w)[2][2]);
 376
 377                         f->Printf ("notexture 0 0 0 1 1\n" );
 378                         delete w;
 379                 }
 380                 f->Printf ("}\n");
 381         }
 382         f->Printf ("}\n");
 383
 384         fileSystem->CloseFile(f);
 385
 386 }
 387
 388
 389 //=====================================================================================
 390
 391 /*
 392 ====================
 393 FilterBrushIntoTree_r
 394
 395 ====================
 396 */
 397 int FilterBrushIntoTree_r( uBrush_t *b, node_t *node ) {
 398         uBrush_t                *front, *back;
 399         int                             c;
 400
 401         if ( !b ) {
 402                 return 0;
 403         }
 404
 405         // add it to the leaf list
 406         if ( node->planenum == PLANENUM_LEAF ) {
 407                 b->next = node->brushlist;
 408                 node->brushlist = b;
 409
 410                 // classify the leaf by the structural brush
 411                 if ( b->opaque ) {
 412                         node->opaque = true;
 413                 }
 414
 415                 return 1;
 416         }
 417
 418         // split it by the node plane
 419         SplitBrush ( b, node->planenum, &front, &back );
 420         FreeBrush( b );
 421
 422         c = 0;
 423         c += FilterBrushIntoTree_r( front, node->children[0] );
 424         c += FilterBrushIntoTree_r( back, node->children[1] );
 425
 426         return c;
 427 }
 428
 429
 430 /*
 431 =====================
 432 FilterBrushesIntoTree
 433
 434 Mark the leafs as opaque and areaportals and put brush
 435 fragments in each leaf so portal surfaces can be matched
 436 to materials
 437 =====================
 438 */
 439 void FilterBrushesIntoTree( uEntity_t *e ) {
 440         primitive_t                     *prim;
 441         uBrush_t                        *b, *newb;
 442         int                                     r;
 443         int                                     c_unique, c_clusters;
 444
 445         common->Printf( "----- FilterBrushesIntoTree -----\n");
 446
 447         c_unique = 0;
 448         c_clusters = 0;
 449         for ( prim = e->primitives ; prim ; prim = prim->next ) {
 450                 b = prim->brush;
 451                 if ( !b ) {
 452                         continue;
 453                 }
 454                 c_unique++;
 455                 newb = CopyBrush( b );
 456                 r = FilterBrushIntoTree_r( newb, e->tree->headnode );
 457                 c_clusters += r;
 458         }
 459
 460         common->Printf( "%5i total brushes\n", c_unique );
 461         common->Printf( "%5i cluster references\n", c_clusters );
 462 }
 463
 464
 465
 466 /*
 467 ================
 468 AllocTree
 469 ================
 470 */
 471 tree_t *AllocTree (void)
 472 {
 473         tree_t  *tree;
 474
 475         tree = (tree_t *)Mem_Alloc(sizeof(*tree));
 476         memset (tree, 0, sizeof(*tree));
 477         tree->bounds.Clear();
 478
 479         return tree;
 480 }
 481
 482 /*
 483 ================
 484 AllocNode
 485 ================
 486 */
 487 node_t *AllocNode (void)
 488 {
 489         node_t  *node;
 490
 491         node = (node_t *)Mem_Alloc(sizeof(*node));
 492         memset (node, 0, sizeof(*node));
 493
 494         return node;
 495 }
 496
 497 //============================================================
 498
 499 /*
 500 ==================
 501 BrushMostlyOnSide
 502
 503 ==================
 504 */
 505 int BrushMostlyOnSide (uBrush_t *brush, idPlane &plane) {
 506         int                     i, j;
 507         idWinding       *w;
 508         float           d, max;
 509         int                     side;
 510
 511         max = 0;
 512         side = PSIDE_FRONT;
 513         for ( i = 0; i < brush->numsides; i++ ) {
 514                 w = brush->sides[i].winding;
 515                 if (!w)
 516                         continue;
 517                 for ( j = 0; j < w->GetNumPoints(); j++ )
 518                 {
 519                         d = plane.Distance( (*w)[j].ToVec3() );
 520                         if (d > max)
 521                         {
 522                                 max = d;
 523                                 side = PSIDE_FRONT;
 524                         }
 525                         if (-d > max)
 526                         {
 527                                 max = -d;
 528                                 side = PSIDE_BACK;
 529                         }
 530                 }
 531         }
 532         return side;
 533 }
 534
 535 /*
 536 ================
 537 SplitBrush
 538
 539 Generates two new brushes, leaving the original
 540 unchanged
 541 ================
 542 */
 543 void SplitBrush (uBrush_t *brush, int planenum, uBrush_t **front, uBrush_t **back) {
 544         uBrush_t        *b[2];
 545         int                     i, j;
 546         idWinding       *w, *cw[2], *midwinding;
 547         side_t          *s, *cs;
 548         float           d, d_front, d_back;
 549
 550         *front = *back = NULL;
 551         idPlane &plane = dmapGlobals.mapPlanes[planenum];
 552
 553         // check all points
 554         d_front = d_back = 0;
 555         for ( i = 0; i < brush->numsides; i++ )
 556         {
 557                 w = brush->sides[i].winding;
 558                 if (!w) {
 559                         continue;
 560                 }
 561                 for ( j = 0; j < w->GetNumPoints(); j++ ) {
 562                         d = plane.Distance( (*w)[j].ToVec3() );
 563                         if (d > 0 && d > d_front)
 564                                 d_front = d;
 565                         if (d < 0 && d < d_back)
 566                                 d_back = d;
 567                 }
 568         }
 569         if (d_front < 0.1) // PLANESIDE_EPSILON)
 570         {       // only on back
 571                 *back = CopyBrush( brush );
 572                 return;
 573         }
 574         if (d_back > -0.1) // PLANESIDE_EPSILON)
 575         {       // only on front
 576                 *front = CopyBrush( brush );
 577                 return;
 578         }
 579
 580         // create a new winding from the split plane
 581
 582         w = new idWinding( plane );
 583         for ( i = 0; i < brush->numsides && w; i++ ) {
 584                 idPlane &plane2 = dmapGlobals.mapPlanes[brush->sides[i].planenum ^ 1];
 585                 w = w->Clip( plane2, 0 ); // PLANESIDE_EPSILON);
 586         }
 587
 588         if ( !w || w->IsTiny() ) {
 589                 // the brush isn't really split
 590                 int             side;
 591
 592                 side = BrushMostlyOnSide( brush, plane );
 593                 if (side == PSIDE_FRONT)
 594                         *front = CopyBrush (brush);
 595                 if (side == PSIDE_BACK)
 596                         *back = CopyBrush (brush);
 597                 return;
 598         }
 599
 600         if ( w->IsHuge() ) {
 601                 common->Printf ("WARNING: huge winding\n");
 602         }
 603
 604         midwinding = w;
 605
 606         // split it for real
 607
 608         for ( i = 0; i < 2; i++ ) {
 609                 b[i] = AllocBrush (brush->numsides+1);
 610                 memcpy( b[i], brush, sizeof( uBrush_t ) - sizeof( brush->sides ) );
 611                 b[i]->numsides = 0;
 612                 b[i]->next = NULL;
 613                 b[i]->original = brush->original;
 614         }
 615
 616         // split all the current windings
 617
 618         for ( i = 0; i < brush->numsides; i++ ) {
 619                 s = &brush->sides[i];
 620                 w = s->winding;
 621                 if (!w)
 622                         continue;
 623                 w->Split( plane, 0 /*PLANESIDE_EPSILON*/, &cw[0], &cw[1] );
 624                 for ( j = 0; j < 2; j++ ) {
 625                         if ( !cw[j] ) {
 626                                 continue;
 627                         }
 628 /*
 629                         if ( cw[j]->IsTiny() )
 630                         {
 631                                 delete cw[j];
 632                                 continue;
 633                         }
 634 */
 635                         cs = &b[j]->sides[b[j]->numsides];
 636                         b[j]->numsides++;
 637                         *cs = *s;
 638                         cs->winding = cw[j];
 639                 }
 640         }
 641
 642
 643         // see if we have valid polygons on both sides
 644
 645         for (i=0 ; i<2 ; i++)
 646         {
 647                 if ( !BoundBrush (b[i]) ) {
 648                         break;
 649                 }
 650
 651                 if ( b[i]->numsides < 3 )
 652                 {
 653                         FreeBrush (b[i]);
 654                         b[i] = NULL;
 655                 }
 656         }
 657
 658         if ( !(b[0] && b[1]) )
 659         {
 660                 if (!b[0] && !b[1])
 661                         common->Printf ("split removed brush\n");
 662                 else
 663                         common->Printf ("split not on both sides\n");
 664                 if (b[0])
 665                 {
 666                         FreeBrush (b[0]);
 667                         *front = CopyBrush (brush);
 668                 }
 669                 if (b[1])
 670                 {
 671                         FreeBrush (b[1]);
 672                         *back = CopyBrush (brush);
 673                 }
 674                 return;
 675         }
 676
 677         // add the midwinding to both sides
 678         for (i=0 ; i<2 ; i++)
 679         {
 680                 cs = &b[i]->sides[b[i]->numsides];
 681                 b[i]->numsides++;
 682
 683                 cs->planenum = planenum^i^1;
 684                 cs->material = NULL;
 685                 if (i==0)
 686                         cs->winding = midwinding->Copy();
 687                 else
 688                         cs->winding = midwinding;
 689         }
 690
 691 {
 692         float   v1;
 693         int             i;
 694
 695         for (i=0 ; i<2 ; i++)
 696         {
 697                 v1 = BrushVolume (b[i]);
 698                 if (v1 < 1.0)
 699                 {
 700                         FreeBrush (b[i]);
 701                         b[i] = NULL;
 702 //                      common->Printf ("tiny volume after clip\n");
 703                 }
 704         }
 705 }
 706
 707         *front = b[0];
 708         *back = b[1];
 709 }