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