tools/quake2/q2map/csg.c

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