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