tools/quake2/q2map/csg.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 #include "qbsp.h"
  23
  24 /*
  25
  26    tag all brushes with original contents
  27    brushes may contain multiple contents
  28    there will be no brush overlap after csg phase
  29
  30
  31
  32
  33    each side has a count of the other sides it splits
  34
  35    the best split will be the one that minimizes the total split counts
  36    of all remaining sides
  37
  38    precalc side on plane table
  39
  40    evaluate split side
  41    {
  42    cost = 0
  43    for all sides
  44     for all sides
  45         get
  46         if side splits side and splitside is on same child
  47             cost++;
  48    }
  49
  50
  51  */
  52
  53 void SplitBrush2( bspbrush_t *brush, int planenum,
  54                                   bspbrush_t **front, bspbrush_t **back ){
  55         SplitBrush( brush, planenum, front, back );
  56 #if 0
  57         if ( *front && ( *front )->sides[( *front )->numsides - 1].texinfo == -1 ) {
  58                 ( *front )->sides[( *front )->numsides - 1].texinfo = ( *front )->sides[0].texinfo; // not -1
  59         }
  60         if ( *back && ( *back )->sides[( *back )->numsides - 1].texinfo == -1 ) {
  61                 ( *back )->sides[( *back )->numsides - 1].texinfo = ( *back )->sides[0].texinfo;    // not -1
  62         }
  63 #endif
  64 }
  65
  66 /*
  67    ===============
  68    SubtractBrush
  69
  70    Returns a list of brushes that remain after B is subtracted from A.
  71    May by empty if A is contained inside B.
  72
  73    The originals are undisturbed.
  74    ===============
  75  */
  76 bspbrush_t *SubtractBrush( bspbrush_t *a, bspbrush_t *b ){ // a - b = out (list)
  77         int i;
  78         bspbrush_t  *front, *back;
  79         bspbrush_t  *out, *in;
  80
  81         in = a;
  82         out = NULL;
  83         for ( i = 0 ; i < b->numsides && in ; i++ )
  84         {
  85                 SplitBrush2( in, b->sides[i].planenum, &front, &back );
  86                 if ( in != a ) {
  87                         FreeBrush( in );
  88                 }
  89                 if ( front ) { // add to list
  90                         front->next = out;
  91                         out = front;
  92                 }
  93                 in = back;
  94         }
  95         if ( in ) {
  96                 FreeBrush( in );
  97         }
  98         else
  99         {   // didn't really intersect
 100                 FreeBrushList( out );
 101                 return a;
 102         }
 103         return out;
 104 }
 105
 106 /*
 107    ===============
 108    IntersectBrush
 109
 110    Returns a single brush made up by the intersection of the
 111    two provided brushes, or NULL if they are disjoint.
 112
 113    The originals are undisturbed.
 114    ===============
 115  */
 116 bspbrush_t *IntersectBrush( bspbrush_t *a, bspbrush_t *b ){
 117         int i;
 118         bspbrush_t  *front, *back;
 119         bspbrush_t  *in;
 120
 121         in = a;
 122         for ( i = 0 ; i < b->numsides && in ; i++ )
 123         {
 124                 SplitBrush2( in, b->sides[i].planenum, &front, &back );
 125                 if ( in != a ) {
 126                         FreeBrush( in );
 127                 }
 128                 if ( front ) {
 129                         FreeBrush( front );
 130                 }
 131                 in = back;
 132         }
 133
 134         if ( in == a ) {
 135                 return NULL;
 136         }
 137
 138         in->next = NULL;
 139         return in;
 140 }
 141
 142
 143 /*
 144    ===============
 145    BrushesDisjoint
 146
 147    Returns true if the two brushes definately do not intersect.
 148    There will be false negatives for some non-axial combinations.
 149    ===============
 150  */
 151 qboolean BrushesDisjoint( bspbrush_t *a, bspbrush_t *b ){
 152         int i, j;
 153
 154         // check bounding boxes
 155         for ( i = 0 ; i < 3 ; i++ )
 156                 if ( a->mins[i] >= b->maxs[i]
 157                          || a->maxs[i] <= b->mins[i] ) {
 158                         return true;
 159                 }                   // bounding boxes don't overlap
 160
 161         // check for opposing planes
 162         for ( i = 0 ; i < a->numsides ; i++ )
 163         {
 164                 for ( j = 0 ; j < b->numsides ; j++ )
 165                 {
 166                         if ( a->sides[i].planenum ==
 167                                  ( b->sides[j].planenum ^ 1 ) ) {
 168                                 return true;    // opposite planes, so not touching
 169                         }
 170                 }
 171         }
 172
 173         return false;   // might intersect
 174 }
 175
 176 /*
 177    ===============
 178    IntersectionContents
 179
 180    Returns a content word for the intersection of two brushes.
 181    Some combinations will generate a combination (water + clip),
 182    but most will be the stronger of the two contents.
 183    ===============
 184  */
 185 int IntersectionContents( int c1, int c2 ){
 186         int out;
 187
 188         out = c1 | c2;
 189
 190         if ( out & CONTENTS_SOLID ) {
 191                 out = CONTENTS_SOLID;
 192         }
 193
 194         return out;
 195 }
 196
 197
 198 int minplanenums[3];
 199 int maxplanenums[3];
 200
 201 /*
 202    ===============
 203    ClipBrushToBox
 204
 205    Any planes shared with the box edge will be set to no texinfo
 206    ===============
 207  */
 208 bspbrush_t  *ClipBrushToBox( bspbrush_t *brush, vec3_t clipmins, vec3_t clipmaxs ){
 209         int i, j;
 210         bspbrush_t  *front, *back;
 211         int p;
 212
 213         for ( j = 0 ; j < 2 ; j++ )
 214         {
 215                 if ( brush->maxs[j] > clipmaxs[j] ) {
 216                         SplitBrush( brush, maxplanenums[j], &front, &back );
 217                         if ( front ) {
 218                                 FreeBrush( front );
 219                         }
 220                         brush = back;
 221                         if ( !brush ) {
 222                                 return NULL;
 223                         }
 224                 }
 225                 if ( brush->mins[j] < clipmins[j] ) {
 226                         SplitBrush( brush, minplanenums[j], &front, &back );
 227                         if ( back ) {
 228                                 FreeBrush( back );
 229                         }
 230                         brush = front;
 231                         if ( !brush ) {
 232                                 return NULL;
 233                         }
 234                 }
 235         }
 236
 237         // remove any colinear faces
 238
 239         for ( i = 0 ; i < brush->numsides ; i++ )
 240         {
 241                 p = brush->sides[i].planenum & ~1;
 242                 if ( p == maxplanenums[0] || p == maxplanenums[1]
 243                          || p == minplanenums[0] || p == minplanenums[1] ) {
 244                         brush->sides[i].texinfo = TEXINFO_NODE;
 245                         brush->sides[i].visible = false;
 246                 }
 247         }
 248         return brush;
 249 }
 250
 251 /*
 252    ===============
 253    MakeBspBrushList
 254    ===============
 255  */
 256 bspbrush_t *MakeBspBrushList( int startbrush, int endbrush,
 257                                                           vec3_t clipmins, vec3_t clipmaxs ){
 258         mapbrush_t  *mb;
 259         bspbrush_t  *brushlist, *newbrush;
 260         int i, j;
 261         int c_faces;
 262         int c_brushes;
 263         int numsides;
 264         int vis;
 265         vec3_t normal;
 266         float dist;
 267
 268         for ( i = 0 ; i < 2 ; i++ )
 269         {
 270                 VectorClear( normal );
 271                 normal[i] = 1;
 272                 dist = clipmaxs[i];
 273                 maxplanenums[i] = FindFloatPlane( normal, dist );
 274                 dist = clipmins[i];
 275                 minplanenums[i] = FindFloatPlane( normal, dist );
 276         }
 277
 278         brushlist = NULL;
 279         c_faces = 0;
 280         c_brushes = 0;
 281
 282         for ( i = startbrush ; i < endbrush ; i++ )
 283         {
 284                 mb = &mapbrushes[i];
 285
 286                 numsides = mb->numsides;
 287                 if ( !numsides ) {
 288                         continue;
 289                 }
 290                 // make sure the brush has at least one face showing
 291                 vis = 0;
 292                 for ( j = 0 ; j < numsides ; j++ )
 293                         if ( mb->original_sides[j].visible && mb->original_sides[j].winding ) {
 294                                 vis++;
 295                         }
 296 #if 0
 297                 if ( !vis ) {
 298                         continue;   // no faces at all
 299                 }
 300 #endif
 301                 // if the brush is outside the clip area, skip it
 302                 for ( j = 0 ; j < 3 ; j++ )
 303                         if ( mb->mins[j] >= clipmaxs[j]
 304                                  || mb->maxs[j] <= clipmins[j] ) {
 305                                 break;
 306                         }
 307                 if ( j != 3 ) {
 308                         continue;
 309                 }
 310
 311                 //
 312                 // make a copy of the brush
 313                 //
 314                 newbrush = AllocBrush( mb->numsides );
 315                 newbrush->original = mb;
 316                 newbrush->numsides = mb->numsides;
 317                 memcpy( newbrush->sides, mb->original_sides, numsides * sizeof( side_t ) );
 318                 for ( j = 0 ; j < numsides ; j++ )
 319                 {
 320                         if ( newbrush->sides[j].winding ) {
 321                                 newbrush->sides[j].winding = CopyWinding( newbrush->sides[j].winding );
 322                         }
 323                         if ( newbrush->sides[j].surf & SURF_HINT ) {
 324                                 newbrush->sides[j].visible = true;  // hints are always visible
 325                         }
 326                 }
 327                 VectorCopy( mb->mins, newbrush->mins );
 328                 VectorCopy( mb->maxs, newbrush->maxs );
 329
 330                 //
 331                 // carve off anything outside the clip box
 332                 //
 333                 newbrush = ClipBrushToBox( newbrush, clipmins, clipmaxs );
 334                 if ( !newbrush ) {
 335                         continue;
 336                 }
 337
 338                 c_faces += vis;
 339                 c_brushes++;
 340
 341                 newbrush->next = brushlist;
 342                 brushlist = newbrush;
 343         }
 344
 345         return brushlist;
 346 }
 347
 348 /*
 349    ===============
 350    AddBspBrushListToTail
 351    ===============
 352  */
 353 bspbrush_t *AddBrushListToTail( bspbrush_t *list, bspbrush_t *tail ){
 354         bspbrush_t  *walk, *next;
 355
 356         for ( walk = list ; walk ; walk = next )
 357         {   // add to end of list
 358                 next = walk->next;
 359                 walk->next = NULL;
 360                 tail->next = walk;
 361                 tail = walk;
 362         }
 363
 364         return tail;
 365 }
 366
 367 /*
 368    ===========
 369    CullList
 370
 371    Builds a new list that doesn't hold the given brush
 372    ===========
 373  */
 374 bspbrush_t *CullList( bspbrush_t *list, bspbrush_t *skip1 ){
 375         bspbrush_t  *newlist;
 376         bspbrush_t  *next;
 377
 378         newlist = NULL;
 379
 380         for ( ; list ; list = next )
 381         {
 382                 next = list->next;
 383                 if ( list == skip1 ) {
 384                         FreeBrush( list );
 385                         continue;
 386                 }
 387                 list->next = newlist;
 388                 newlist = list;
 389         }
 390         return newlist;
 391 }
 392
 393
 394 /*
 395    ==================
 396    WriteBrushMap
 397    ==================
 398  */
 399 void WriteBrushMap( char *name, bspbrush_t *list ){
 400         FILE    *f;
 401         side_t  *s;
 402         int i;
 403         winding_t   *w;
 404
 405         Sys_Printf( "writing %s\n", name );
 406         f = fopen( name, "wb" );
 407         if ( !f ) {
 408                 Error( "Can't write %s\b", name );
 409         }
 410
 411         fprintf( f, "{\n\"classname\" \"worldspawn\"\n" );
 412
 413         for ( ; list ; list = list->next )
 414         {
 415                 fprintf( f, "{\n" );
 416                 for ( i = 0,s = list->sides ; i < list->numsides ; i++,s++ )
 417                 {
 418                         w = BaseWindingForPlane( mapplanes[s->planenum].normal, mapplanes[s->planenum].dist );
 419
 420                         fprintf( f,"( %i %i %i ) ", (int)w->p[0][0], (int)w->p[0][1], (int)w->p[0][2] );
 421                         fprintf( f,"( %i %i %i ) ", (int)w->p[1][0], (int)w->p[1][1], (int)w->p[1][2] );
 422                         fprintf( f,"( %i %i %i ) ", (int)w->p[2][0], (int)w->p[2][1], (int)w->p[2][2] );
 423
 424                         fprintf( f, "%s 0 0 0 1 1\n", texinfo[s->texinfo].texture );
 425                         FreeWinding( w );
 426                 }
 427                 fprintf( f, "}\n" );
 428         }
 429         fprintf( f, "}\n" );
 430
 431         fclose( f );
 432
 433 }
 434
 435 /*
 436    ==================
 437    BrushGE
 438
 439    Returns true if b1 is allowed to bite b2
 440    ==================
 441  */
 442 qboolean BrushGE( bspbrush_t *b1, bspbrush_t *b2 ){
 443         // detail brushes never bite structural brushes
 444         if ( ( b1->original->contents & CONTENTS_DETAIL )
 445                  && !( b2->original->contents & CONTENTS_DETAIL ) ) {
 446                 return false;
 447         }
 448         if ( b1->original->contents & CONTENTS_SOLID ) {
 449                 return true;
 450         }
 451         return false;
 452 }
 453
 454 /*
 455    =================
 456    ChopBrushes
 457
 458    Carves any intersecting solid brushes into the minimum number
 459    of non-intersecting brushes.
 460    =================
 461  */
 462 bspbrush_t *ChopBrushes( bspbrush_t *head ){
 463         bspbrush_t  *b1, *b2, *next;
 464         bspbrush_t  *tail;
 465         bspbrush_t  *keep;
 466         bspbrush_t  *sub, *sub2;
 467         int c1, c2;
 468
 469         Sys_FPrintf( SYS_VRB, "---- ChopBrushes ----\n" );
 470         Sys_FPrintf( SYS_VRB, "original brushes: %i\n", CountBrushList( head ) );
 471
 472 #if 0
 473         if ( startbrush == 0 ) {
 474                 WriteBrushList( "before.gl", head, false );
 475         }
 476 #endif
 477         keep = NULL;
 478
 479 newlist:
 480         // find tail
 481         if ( !head ) {
 482                 return NULL;
 483         }
 484         for ( tail = head ; tail->next ; tail = tail->next )
 485                 ;
 486
 487         for ( b1 = head ; b1 ; b1 = next )
 488         {
 489                 next = b1->next;
 490                 for ( b2 = b1->next ; b2 ; b2 = b2->next )
 491                 {
 492                         if ( BrushesDisjoint( b1, b2 ) ) {
 493                                 continue;
 494                         }
 495
 496                         sub = NULL;
 497                         sub2 = NULL;
 498                         c1 = 999999;
 499                         c2 = 999999;
 500
 501                         if ( BrushGE( b2, b1 ) ) {
 502                                 sub = SubtractBrush( b1, b2 );
 503                                 if ( sub == b1 ) {
 504                                         continue;       // didn't really intersect
 505                                 }
 506                                 if ( !sub ) { // b1 is swallowed by b2
 507                                         head = CullList( b1, b1 );
 508                                         goto newlist;
 509                                 }
 510                                 c1 = CountBrushList( sub );
 511                         }
 512
 513                         if ( BrushGE( b1, b2 ) ) {
 514                                 sub2 = SubtractBrush( b2, b1 );
 515                                 if ( sub2 == b2 ) {
 516                                         continue;       // didn't really intersect
 517                                 }
 518                                 if ( !sub2 ) { // b2 is swallowed by b1
 519                                         FreeBrushList( sub );
 520                                         head = CullList( b1, b2 );
 521                                         goto newlist;
 522                                 }
 523                                 c2 = CountBrushList( sub2 );
 524                         }
 525
 526                         if ( !sub && !sub2 ) {
 527                                 continue;       // neither one can bite
 528
 529                         }
 530                         // only accept if it didn't fragment
 531                         // (commening this out allows full fragmentation)
 532                         if ( c1 > 1 && c2 > 1 ) {
 533                                 if ( sub2 ) {
 534                                         FreeBrushList( sub2 );
 535                                 }
 536                                 if ( sub ) {
 537                                         FreeBrushList( sub );
 538                                 }
 539                                 continue;
 540                         }
 541
 542                         if ( c1 < c2 ) {
 543                                 if ( sub2 ) {
 544                                         FreeBrushList( sub2 );
 545                                 }
 546                                 tail = AddBrushListToTail( sub, tail );
 547                                 head = CullList( b1, b1 );
 548                                 goto newlist;
 549                         }
 550                         else
 551                         {
 552                                 if ( sub ) {
 553                                         FreeBrushList( sub );
 554                                 }
 555                                 tail = AddBrushListToTail( sub2, tail );
 556                                 head = CullList( b1, b2 );
 557                                 goto newlist;
 558                         }
 559                 }
 560
 561                 if ( !b2 ) { // b1 is no longer intersecting anything, so keep it
 562                         b1->next = keep;
 563                         keep = b1;
 564                 }
 565         }
 566
 567         Sys_FPrintf( SYS_VRB, "output brushes: %i\n", CountBrushList( keep ) );
 568 #if 0
 569         {
 570                 WriteBrushList( "after.gl", keep, false );
 571                 WriteBrushMap( "after.map", keep );
 572         }
 573 #endif
 574         return keep;
 575 }
 576
 577
 578 /*
 579    =================
 580    InitialBrushList
 581    =================
 582  */
 583 bspbrush_t *InitialBrushList( bspbrush_t *list ){
 584         bspbrush_t *b;
 585         bspbrush_t  *out, *newb;
 586         int i;
 587
 588         // only return brushes that have visible faces
 589         out = NULL;
 590         for ( b = list ; b ; b = b->next )
 591         {
 592 #if 0
 593                 for ( i = 0 ; i < b->numsides ; i++ )
 594                         if ( b->sides[i].visible ) {
 595                                 break;
 596                         }
 597                 if ( i == b->numsides ) {
 598                         continue;
 599                 }
 600 #endif
 601                 newb = CopyBrush( b );
 602                 newb->next = out;
 603                 out = newb;
 604
 605                 // clear visible, so it must be set by MarkVisibleFaces_r
 606                 // to be used in the optimized list
 607                 for ( i = 0 ; i < b->numsides ; i++ )
 608                 {
 609                         newb->sides[i].original = &b->sides[i];
 610 //                      newb->sides[i].visible = true;
 611                         b->sides[i].visible = false;
 612                 }
 613         }
 614
 615         return out;
 616 }
 617
 618 /*
 619    =================
 620    OptimizedBrushList
 621    =================
 622  */
 623 bspbrush_t *OptimizedBrushList( bspbrush_t *list ){
 624         bspbrush_t *b;
 625         bspbrush_t  *out, *newb;
 626         int i;
 627
 628         // only return brushes that have visible faces
 629         out = NULL;
 630         for ( b = list ; b ; b = b->next )
 631         {
 632                 for ( i = 0 ; i < b->numsides ; i++ )
 633                         if ( b->sides[i].visible ) {
 634                                 break;
 635                         }
 636                 if ( i == b->numsides ) {
 637                         continue;
 638                 }
 639                 newb = CopyBrush( b );
 640                 newb->next = out;
 641                 out = newb;
 642         }
 643
 644 //      WriteBrushList ("vis.gl", out, true);
 645
 646         return out;
 647 }