radiant/csg.cpp

   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 "csg.h"
  23
  24 #include "debugging/debugging.h"
  25
  26 #include <list>
  27
  28 #include "map.h"
  29 #include "brushmanip.h"
  30 #include "brushnode.h"
  31 #include "grid.h"
  32
  33 void Face_makeBrush(Face &face, const Brush &brush, brush_vector_t &out, float offset)
  34 {
  35     if (face.contributes()) {
  36         out.push_back(new Brush(brush));
  37         Face *newFace = out.back()->addFace(face);
  38         if (newFace != 0) {
  39             newFace->flipWinding();
  40             newFace->getPlane().offset(offset);
  41             newFace->planeChanged();
  42         }
  43     }
  44 }
  45
  46 void Face_makeRoom(Face &face, const Brush &brush, brush_vector_t &out, float offset)
  47 {
  48     if (face.contributes()) {
  49         face.getPlane().offset(offset);
  50         out.push_back(new Brush(brush));
  51         face.getPlane().offset(-offset);
  52         Face *newFace = out.back()->addFace(face);
  53         if (newFace != 0) {
  54             newFace->flipWinding();
  55             newFace->planeChanged();
  56         }
  57     }
  58 }
  59
  60 void Brush_makeHollow(const Brush &brush, brush_vector_t &out, float offset)
  61 {
  62     Brush_forEachFace(brush, [&](Face &face) {
  63         Face_makeBrush(face, brush, out, offset);
  64     });
  65 }
  66
  67 void Brush_makeRoom(const Brush &brush, brush_vector_t &out, float offset)
  68 {
  69     Brush_forEachFace(brush, [&](Face &face) {
  70         Face_makeRoom(face, brush, out, offset);
  71     });
  72 }
  73
  74 class BrushHollowSelectedWalker : public scene::Graph::Walker {
  75     float m_offset;
  76     bool m_makeRoom;
  77 public:
  78     BrushHollowSelectedWalker(float offset, bool makeRoom)
  79             : m_offset(offset), m_makeRoom(makeRoom)
  80     {
  81     }
  82
  83     bool pre(const scene::Path &path, scene::Instance &instance) const
  84     {
  85         if (path.top().get().visible()) {
  86             Brush *brush = Node_getBrush(path.top());
  87             if (brush != 0
  88                 && Instance_getSelectable(instance)->isSelected()
  89                 && path.size() > 1) {
  90                 brush_vector_t out;
  91
  92                 if (m_makeRoom) {
  93                     Brush_makeRoom(*brush, out, m_offset);
  94                 }
  95                 else {
  96                     Brush_makeHollow(*brush, out, m_offset);
  97                 }
  98
  99                 for (brush_vector_t::const_iterator i = out.begin(); i != out.end(); ++i) {
 100                     (*i)->removeEmptyFaces();
 101                     NodeSmartReference node((new BrushNode())->node());
 102                     Node_getBrush(node)->copy(*(*i));
 103                     delete (*i);
 104                     Node_getTraversable(path.parent())->insert(node);
 105                 }
 106             }
 107         }
 108         return true;
 109     }
 110 };
 111
 112 typedef std::list<Brush *> brushlist_t;
 113
 114 class BrushGatherSelected : public scene::Graph::Walker {
 115     brush_vector_t &m_brushlist;
 116 public:
 117     BrushGatherSelected(brush_vector_t &brushlist)
 118             : m_brushlist(brushlist)
 119     {
 120     }
 121
 122     bool pre(const scene::Path &path, scene::Instance &instance) const
 123     {
 124         if (path.top().get().visible()) {
 125             Brush *brush = Node_getBrush(path.top());
 126             if (brush != 0
 127                 && Instance_getSelectable(instance)->isSelected()) {
 128                 m_brushlist.push_back(brush);
 129             }
 130         }
 131         return true;
 132     }
 133 };
 134
 135 class BrushDeleteSelected : public scene::Graph::Walker {
 136 public:
 137     bool pre(const scene::Path &path, scene::Instance &instance) const
 138     {
 139         return true;
 140     }
 141
 142     void post(const scene::Path &path, scene::Instance &instance) const
 143     {
 144         if (path.top().get().visible()) {
 145             Brush *brush = Node_getBrush(path.top());
 146             if (brush != 0
 147                 && Instance_getSelectable(instance)->isSelected()
 148                 && path.size() > 1) {
 149                 Path_deleteTop(path);
 150             }
 151         }
 152     }
 153 };
 154
 155 void Scene_BrushMakeHollow_Selected(scene::Graph &graph, bool makeRoom)
 156 {
 157     GlobalSceneGraph().traverse(BrushHollowSelectedWalker(GetGridSize(), makeRoom));
 158     GlobalSceneGraph().traverse(BrushDeleteSelected());
 159 }
 160
 161 /*
 162    =============
 163    CSG_MakeHollow
 164    =============
 165  */
 166
 167 void CSG_MakeHollow(void)
 168 {
 169     UndoableCommand undo("brushHollow");
 170
 171     Scene_BrushMakeHollow_Selected(GlobalSceneGraph(), false);
 172
 173     SceneChangeNotify();
 174 }
 175
 176 void CSG_MakeRoom(void)
 177 {
 178     UndoableCommand undo("brushRoom");
 179
 180     Scene_BrushMakeHollow_Selected(GlobalSceneGraph(), true);
 181
 182     SceneChangeNotify();
 183 }
 184
 185 template<typename Type>
 186 class RemoveReference {
 187 public:
 188     typedef Type type;
 189 };
 190
 191 template<typename Type>
 192 class RemoveReference<Type &> {
 193 public:
 194     typedef Type type;
 195 };
 196
 197 template<typename Functor>
 198 class Dereference {
 199     const Functor &functor;
 200 public:
 201     Dereference(const Functor &functor) : functor(functor)
 202     {
 203     }
 204
 205     get_result_type<Functor> operator()(typename RemoveReference<get_argument<Functor, 0>>::type *firstArgument) const
 206     {
 207         return functor(*firstArgument);
 208     }
 209 };
 210
 211 template<typename Functor>
 212 inline Dereference<Functor> makeDereference(const Functor &functor)
 213 {
 214     return Dereference<Functor>(functor);
 215 }
 216
 217 typedef Face *FacePointer;
 218 const FacePointer c_nullFacePointer = 0;
 219
 220 template<typename Predicate>
 221 Face *Brush_findIf(const Brush &brush, const Predicate &predicate)
 222 {
 223     Brush::const_iterator i = std::find_if(brush.begin(), brush.end(), makeDereference(predicate));
 224     return i == brush.end() ? c_nullFacePointer
 225                             : *i; // uses c_nullFacePointer instead of 0 because otherwise gcc 4.1 attempts conversion to int
 226 }
 227
 228 template<typename Caller>
 229 class BindArguments1 {
 230     typedef get_argument<Caller, 1> FirstBound;
 231     FirstBound firstBound;
 232 public:
 233     BindArguments1(FirstBound firstBound)
 234             : firstBound(firstBound)
 235     {
 236     }
 237
 238     get_result_type<Caller> operator()(get_argument<Caller, 0> firstArgument) const
 239     {
 240         return Caller::call(firstArgument, firstBound);
 241     }
 242 };
 243
 244 template<typename Caller>
 245 class BindArguments2 {
 246     typedef get_argument<Caller, 1> FirstBound;
 247     typedef get_argument<Caller, 2> SecondBound;
 248     FirstBound firstBound;
 249     SecondBound secondBound;
 250 public:
 251     BindArguments2(FirstBound firstBound, SecondBound secondBound)
 252             : firstBound(firstBound), secondBound(secondBound)
 253     {
 254     }
 255
 256     get_result_type<Caller> operator()(get_argument<Caller, 0> firstArgument) const
 257     {
 258         return Caller::call(firstArgument, firstBound, secondBound);
 259     }
 260 };
 261
 262 template<typename Caller, typename FirstBound, typename SecondBound>
 263 BindArguments2<Caller> bindArguments(const Caller &caller, FirstBound firstBound, SecondBound secondBound)
 264 {
 265     return BindArguments2<Caller>(firstBound, secondBound);
 266 }
 267
 268 inline bool Face_testPlane(const Face &face, const Plane3 &plane, bool flipped)
 269 {
 270     return face.contributes() && !Winding_TestPlane(face.getWinding(), plane, flipped);
 271 }
 272
 273 typedef Function<bool(const Face &, const Plane3 &, bool), Face_testPlane> FaceTestPlane;
 274
 275
 276 /// \brief Returns true if
 277 /// \li !flipped && brush is BACK or ON
 278 /// \li flipped && brush is FRONT or ON
 279 bool Brush_testPlane(const Brush &brush, const Plane3 &plane, bool flipped)
 280 {
 281     brush.evaluateBRep();
 282 #if 1
 283     for (Brush::const_iterator i(brush.begin()); i != brush.end(); ++i) {
 284         if (Face_testPlane(*(*i), plane, flipped)) {
 285             return false;
 286         }
 287     }
 288     return true;
 289 #else
 290     return Brush_findIf( brush, bindArguments( FaceTestPlane(), makeReference( plane ), flipped ) ) == 0;
 291 #endif
 292 }
 293
 294 brushsplit_t Brush_classifyPlane(const Brush &brush, const Plane3 &plane)
 295 {
 296     brush.evaluateBRep();
 297     brushsplit_t split;
 298     for (Brush::const_iterator i(brush.begin()); i != brush.end(); ++i) {
 299         if ((*i)->contributes()) {
 300             split += Winding_ClassifyPlane((*i)->getWinding(), plane);
 301         }
 302     }
 303     return split;
 304 }
 305
 306 bool Brush_subtract(const Brush &brush, const Brush &other, brush_vector_t &ret_fragments)
 307 {
 308     if (aabb_intersects_aabb(brush.localAABB(), other.localAABB())) {
 309         brush_vector_t fragments;
 310         fragments.reserve(other.size());
 311         Brush back(brush);
 312
 313         for (Brush::const_iterator i(other.begin()); i != other.end(); ++i) {
 314             if ((*i)->contributes()) {
 315                 brushsplit_t split = Brush_classifyPlane(back, (*i)->plane3());
 316                 if (split.counts[ePlaneFront] != 0
 317                     && split.counts[ePlaneBack] != 0) {
 318                     fragments.push_back(new Brush(back));
 319                     Face *newFace = fragments.back()->addFace(*(*i));
 320                     if (newFace != 0) {
 321                         newFace->flipWinding();
 322                     }
 323                     back.addFace(*(*i));
 324                 } else if (split.counts[ePlaneBack] == 0) {
 325                     for (brush_vector_t::iterator i = fragments.begin(); i != fragments.end(); ++i) {
 326                         delete (*i);
 327                     }
 328                     return false;
 329                 }
 330             }
 331         }
 332         ret_fragments.insert(ret_fragments.end(), fragments.begin(), fragments.end());
 333         return true;
 334     }
 335     return false;
 336 }
 337
 338 class SubtractBrushesFromUnselected : public scene::Graph::Walker {
 339     const brush_vector_t &m_brushlist;
 340     std::size_t &m_before;
 341     std::size_t &m_after;
 342 public:
 343     SubtractBrushesFromUnselected(const brush_vector_t &brushlist, std::size_t &before, std::size_t &after)
 344             : m_brushlist(brushlist), m_before(before), m_after(after)
 345     {
 346     }
 347
 348     bool pre(const scene::Path &path, scene::Instance &instance) const
 349     {
 350         return true;
 351     }
 352
 353     void post(const scene::Path &path, scene::Instance &instance) const
 354     {
 355         if (path.top().get().visible()) {
 356             Brush *brush = Node_getBrush(path.top());
 357             if (brush != 0
 358                 && !Instance_getSelectable(instance)->isSelected()) {
 359                 brush_vector_t buffer[2];
 360                 bool swap = false;
 361                 Brush *original = new Brush(*brush);
 362                 buffer[static_cast<std::size_t>( swap )].push_back(original);
 363
 364                 {
 365                     for (brush_vector_t::const_iterator i(m_brushlist.begin()); i != m_brushlist.end(); ++i) {
 366                         for (brush_vector_t::iterator j(buffer[static_cast<std::size_t>( swap )].begin());
 367                              j != buffer[static_cast<std::size_t>( swap )].end(); ++j) {
 368                             if (Brush_subtract(*(*j), *(*i), buffer[static_cast<std::size_t>( !swap )])) {
 369                                 delete (*j);
 370                             } else {
 371                                 buffer[static_cast<std::size_t>( !swap )].push_back((*j));
 372                             }
 373                         }
 374                         buffer[static_cast<std::size_t>( swap )].clear();
 375                         swap = !swap;
 376                     }
 377                 }
 378
 379                 brush_vector_t &out = buffer[static_cast<std::size_t>( swap )];
 380
 381                 if (out.size() == 1 && out.back() == original) {
 382                     delete original;
 383                 } else {
 384                     ++m_before;
 385                     for (brush_vector_t::const_iterator i = out.begin(); i != out.end(); ++i) {
 386                         ++m_after;
 387                         (*i)->removeEmptyFaces();
 388                         if (!(*i)->empty()) {
 389                             NodeSmartReference node((new BrushNode())->node());
 390                             Node_getBrush(node)->copy(*(*i));
 391                             delete (*i);
 392                             Node_getTraversable(path.parent())->insert(node);
 393                         } else {
 394                             delete (*i);
 395                         }
 396                     }
 397                     Path_deleteTop(path);
 398                 }
 399             }
 400         }
 401     }
 402 };
 403
 404 void CSG_Subtract()
 405 {
 406     brush_vector_t selected_brushes;
 407     GlobalSceneGraph().traverse(BrushGatherSelected(selected_brushes));
 408
 409     if (selected_brushes.empty()) {
 410         globalOutputStream() << "CSG Subtract: No brushes selected.\n";
 411     } else {
 412         globalOutputStream() << "CSG Subtract: Subtracting " << Unsigned(selected_brushes.size()) << " brushes.\n";
 413
 414         UndoableCommand undo("brushSubtract");
 415
 416         // subtract selected from unselected
 417         std::size_t before = 0;
 418         std::size_t after = 0;
 419         GlobalSceneGraph().traverse(SubtractBrushesFromUnselected(selected_brushes, before, after));
 420         globalOutputStream() << "CSG Subtract: Result: "
 421                              << Unsigned(after) << " fragment" << (after == 1 ? "" : "s")
 422                              << " from " << Unsigned(before) << " brush" << (before == 1 ? "" : "es") << ".\n";
 423
 424         SceneChangeNotify();
 425     }
 426 }
 427
 428 class BrushSplitByPlaneSelected : public scene::Graph::Walker {
 429     const Vector3 &m_p0;
 430     const Vector3 &m_p1;
 431     const Vector3 &m_p2;
 432     const char *m_shader;
 433     const TextureProjection &m_projection;
 434     EBrushSplit m_split;
 435 public:
 436     BrushSplitByPlaneSelected(const Vector3 &p0, const Vector3 &p1, const Vector3 &p2, const char *shader,
 437                               const TextureProjection &projection, EBrushSplit split)
 438             : m_p0(p0), m_p1(p1), m_p2(p2), m_shader(shader), m_projection(projection), m_split(split)
 439     {
 440     }
 441
 442     bool pre(const scene::Path &path, scene::Instance &instance) const
 443     {
 444         return true;
 445     }
 446
 447     void post(const scene::Path &path, scene::Instance &instance) const
 448     {
 449         if (path.top().get().visible()) {
 450             Brush *brush = Node_getBrush(path.top());
 451             if (brush != 0
 452                 && Instance_getSelectable(instance)->isSelected()) {
 453                 Plane3 plane(plane3_for_points(m_p0, m_p1, m_p2));
 454                 if (plane3_valid(plane)) {
 455                     brushsplit_t split = Brush_classifyPlane(*brush, m_split == eFront ? plane3_flipped(plane) : plane);
 456                     if (split.counts[ePlaneBack] && split.counts[ePlaneFront]) {
 457                         // the plane intersects this brush
 458                         if (m_split == eFrontAndBack) {
 459                             NodeSmartReference node((new BrushNode())->node());
 460                             Brush *fragment = Node_getBrush(node);
 461                             fragment->copy(*brush);
 462                             Face *newFace = fragment->addPlane(m_p0, m_p1, m_p2, m_shader, m_projection);
 463                             if (newFace != 0 && m_split != eFront) {
 464                                 newFace->flipWinding();
 465                             }
 466                             fragment->removeEmptyFaces();
 467                             ASSERT_MESSAGE(!fragment->empty(), "brush left with no faces after split");
 468
 469                             Node_getTraversable(path.parent())->insert(node);
 470                             {
 471                                 scene::Path fragmentPath = path;
 472                                 fragmentPath.top() = makeReference(node.get());
 473                                 selectPath(fragmentPath, true);
 474                             }
 475                         }
 476
 477                         Face *newFace = brush->addPlane(m_p0, m_p1, m_p2, m_shader, m_projection);
 478                         if (newFace != 0 && m_split == eFront) {
 479                             newFace->flipWinding();
 480                         }
 481                         brush->removeEmptyFaces();
 482                         ASSERT_MESSAGE(!brush->empty(), "brush left with no faces after split");
 483                     } else
 484                         // the plane does not intersect this brush
 485                     if (m_split != eFrontAndBack && split.counts[ePlaneBack] != 0) {
 486                         // the brush is "behind" the plane
 487                         Path_deleteTop(path);
 488                     }
 489                 }
 490             }
 491         }
 492     }
 493 };
 494
 495 void Scene_BrushSplitByPlane(scene::Graph &graph, const Vector3 &p0, const Vector3 &p1, const Vector3 &p2,
 496                              const char *shader, EBrushSplit split)
 497 {
 498     TextureProjection projection;
 499     TexDef_Construct_Default(projection);
 500     graph.traverse(BrushSplitByPlaneSelected(p0, p1, p2, shader, projection, split));
 501     SceneChangeNotify();
 502 }
 503
 504
 505 class BrushInstanceSetClipPlane : public scene::Graph::Walker {
 506     Plane3 m_plane;
 507 public:
 508     BrushInstanceSetClipPlane(const Plane3 &plane)
 509             : m_plane(plane)
 510     {
 511     }
 512
 513     bool pre(const scene::Path &path, scene::Instance &instance) const
 514     {
 515         BrushInstance *brush = Instance_getBrush(instance);
 516         if (brush != 0
 517             && path.top().get().visible()
 518             && brush->isSelected()) {
 519             BrushInstance &brushInstance = *brush;
 520             brushInstance.setClipPlane(m_plane);
 521         }
 522         return true;
 523     }
 524 };
 525
 526 void Scene_BrushSetClipPlane(scene::Graph &graph, const Plane3 &plane)
 527 {
 528     graph.traverse(BrushInstanceSetClipPlane(plane));
 529 }
 530
 531 /*
 532    =============
 533    CSG_Merge
 534    =============
 535  */
 536 bool Brush_merge(Brush &brush, const brush_vector_t &in, bool onlyshape)
 537 {
 538     // gather potential outer faces
 539
 540     {
 541         typedef std::vector<const Face *> Faces;
 542         Faces faces;
 543         for (brush_vector_t::const_iterator i(in.begin()); i != in.end(); ++i) {
 544             (*i)->evaluateBRep();
 545             for (Brush::const_iterator j((*i)->begin()); j != (*i)->end(); ++j) {
 546                 if (!(*j)->contributes()) {
 547                     continue;
 548                 }
 549
 550                 const Face &face1 = *(*j);
 551
 552                 bool skip = false;
 553                 // test faces of all input brushes
 554                 //!\todo SPEEDUP: Flag already-skip faces and only test brushes from i+1 upwards.
 555                 for (brush_vector_t::const_iterator k(in.begin()); !skip && k != in.end(); ++k) {
 556                     if (k != i) { // don't test a brush against itself
 557                         for (Brush::const_iterator l((*k)->begin()); !skip && l != (*k)->end(); ++l) {
 558                             const Face &face2 = *(*l);
 559
 560                             // face opposes another face
 561                             if (plane3_opposing(face1.plane3(), face2.plane3())) {
 562                                 // skip opposing planes
 563                                 skip = true;
 564                                 break;
 565                             }
 566                         }
 567                     }
 568                 }
 569
 570                 // check faces already stored
 571                 for (Faces::const_iterator m = faces.begin(); !skip && m != faces.end(); ++m) {
 572                     const Face &face2 = *(*m);
 573
 574                     // face equals another face
 575                     if (plane3_equal(face1.plane3(), face2.plane3())) {
 576                         //if the texture/shader references should be the same but are not
 577                         if (!onlyshape && !shader_equal(face1.getShader().getShader(), face2.getShader().getShader())) {
 578                             return false;
 579                         }
 580                         // skip duplicate planes
 581                         skip = true;
 582                         break;
 583                     }
 584
 585                     // face1 plane intersects face2 winding or vice versa
 586                     if (Winding_PlanesConcave(face1.getWinding(), face2.getWinding(), face1.plane3(), face2.plane3())) {
 587                         // result would not be convex
 588                         return false;
 589                     }
 590                 }
 591
 592                 if (!skip) {
 593                     faces.push_back(&face1);
 594                 }
 595             }
 596         }
 597         for (Faces::const_iterator i = faces.begin(); i != faces.end(); ++i) {
 598             if (!brush.addFace(*(*i))) {
 599                 // result would have too many sides
 600                 return false;
 601             }
 602         }
 603     }
 604
 605     brush.removeEmptyFaces();
 606
 607     return true;
 608 }
 609
 610 void CSG_Merge(void)
 611 {
 612     brush_vector_t selected_brushes;
 613
 614     // remove selected
 615     GlobalSceneGraph().traverse(BrushGatherSelected(selected_brushes));
 616
 617     if (selected_brushes.empty()) {
 618         globalOutputStream() << "CSG Merge: No brushes selected.\n";
 619         return;
 620     }
 621
 622     if (selected_brushes.size() < 2) {
 623         globalOutputStream() << "CSG Merge: At least two brushes have to be selected.\n";
 624         return;
 625     }
 626
 627     globalOutputStream() << "CSG Merge: Merging " << Unsigned(selected_brushes.size()) << " brushes.\n";
 628
 629     UndoableCommand undo("brushMerge");
 630
 631     scene::Path merged_path = GlobalSelectionSystem().ultimateSelected().path();
 632
 633     NodeSmartReference node((new BrushNode())->node());
 634     Brush *brush = Node_getBrush(node);
 635     // if the new brush would not be convex
 636     if (!Brush_merge(*brush, selected_brushes, true)) {
 637         globalOutputStream() << "CSG Merge: Failed - result would not be convex.\n";
 638     } else {
 639         ASSERT_MESSAGE(!brush->empty(), "brush left with no faces after merge");
 640
 641         // free the original brushes
 642         GlobalSceneGraph().traverse(BrushDeleteSelected());
 643
 644         merged_path.pop();
 645         Node_getTraversable(merged_path.top())->insert(node);
 646         merged_path.push(makeReference(node.get()));
 647
 648         selectPath(merged_path, true);
 649
 650         globalOutputStream() << "CSG Merge: Succeeded.\n";
 651         SceneChangeNotify();
 652     }
 653 }