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