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