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 Functor>
 171 class Dereference
 172 {
 173   const Functor& functor;
 174 public:
 175   typedef typename Functor::first_argument_type first_argument_type;
 176   typedef typename Functor::result_type result_type;
 177   Dereference(const Functor& functor) : functor(functor)
 178   {
 179   }
 180   result_type operator()(first_argument_type firstArgument) const
 181   {
 182     return functor(*firstArgument);
 183   }
 184 };
 185
 186 template<typename Functor>
 187 inline Dereference<Functor> makeDereference(const Functor& functor)
 188 {
 189   return Dereference<Functor>(functor);
 190 }
 191
 192 template<typename Predicate>
 193 Face* Brush_findIf(const Brush& brush, const Predicate& predicate)
 194 {
 195   Brush::const_iterator i = std::find_if(brush.begin(), brush.end(), makeDereference(predicate));
 196   return i == brush.end() ? 0 : *i;
 197 }
 198
 199 template<typename Caller>
 200 class BindArguments1
 201 {
 202   typedef typename Caller::SecondArgument FirstBound;
 203   FirstBound firstBound;
 204 public:
 205   typedef typename Caller::Return Return;
 206   typedef typename Caller::FirstArgument FirstArgument;
 207   BindArguments1(FirstBound firstBound)
 208     : firstBound(firstBound)
 209   {
 210   }
 211   Return operator()(FirstArgument firstArgument) const
 212   {
 213     return Caller::call(firstArgument, firstBound);
 214   }
 215 };
 216
 217 template<typename Caller>
 218 class BindArguments2
 219 {
 220   typedef typename Caller::SecondArgument FirstBound;
 221   typedef typename Caller::ThirdArgument SecondBound;
 222   FirstBound firstBound;
 223   SecondBound secondBound;
 224 public:
 225   typedef typename Caller::Return Return;
 226   typedef typename Caller::FirstArgument FirstArgument;
 227   BindArguments2(FirstBound firstBound, SecondBound secondBound)
 228     : firstBound(firstBound), secondBound(secondBound)
 229   {
 230   }
 231   Return operator()(FirstArgument firstArgument) const
 232   {
 233     return Caller::call(firstArgument, firstBound, secondBound);
 234   }
 235 };
 236
 237 template<typename Caller, typename FirstBound, typename SecondBound>
 238 BindArguments2<Caller> bindArguments(const Caller& caller, FirstBound firstBound, SecondBound secondBound)
 239 {
 240   return BindArguments2<Caller>(firstBound, secondBound);
 241 }
 242
 243 inline bool Face_testPlane(const Face& face, const Plane3& plane, bool flipped)
 244 {
 245   return face.contributes() && !Winding_TestPlane(face.getWinding(), plane, flipped);
 246 }
 247 typedef Function3<const Face&, const Plane3&, bool, bool, Face_testPlane> FaceTestPlane;
 248
 249
 250
 251 /// \brief Returns true if
 252 /// \li !flipped && brush is BACK or ON
 253 /// \li flipped && brush is FRONT or ON
 254 bool Brush_testPlane(const Brush& brush, const Plane3& plane, bool flipped)
 255 {
 256   brush.evaluateBRep();
 257 #if 1
 258   for(Brush::const_iterator i(brush.begin()); i != brush.end(); ++i)
 259   {
 260     if(Face_testPlane(*(*i), plane, flipped))
 261     {
 262       return false;
 263     }
 264   }
 265   return true;
 266 #else
 267   return Brush_findIf(brush, bindArguments(FaceTestPlane(), makeReference(plane), flipped)) == 0;
 268 #endif
 269 }
 270
 271 brushsplit_t Brush_classifyPlane(const Brush& brush, const Plane3& plane)
 272 {
 273   brush.evaluateBRep();
 274   brushsplit_t split;
 275   for(Brush::const_iterator i(brush.begin()); i != brush.end(); ++i)
 276   {
 277     if((*i)->contributes())
 278     {
 279       split += Winding_ClassifyPlane((*i)->getWinding(), plane);
 280     }
 281   }
 282   return split;
 283 }
 284
 285 bool Brush_subtract(const Brush& brush, const Brush& other, brush_vector_t& ret_fragments)
 286 {
 287   if(aabb_intersects_aabb(brush.localAABB(), other.localAABB()))
 288   {
 289     brush_vector_t fragments;
 290     fragments.reserve(other.size());
 291     Brush back(brush);
 292
 293     for(Brush::const_iterator i(other.begin()); i != other.end(); ++i)
 294     {
 295       if((*i)->contributes())
 296       {
 297         brushsplit_t split = Brush_classifyPlane(back, (*i)->plane3());
 298         if(split.counts[ePlaneFront] != 0
 299           && split.counts[ePlaneBack] != 0)
 300         {
 301           fragments.push_back(new Brush(back));
 302           Face* newFace = fragments.back()->addFace(*(*i));
 303           if(newFace != 0)
 304           {
 305             newFace->flipWinding();
 306           }
 307           back.addFace(*(*i));
 308         }
 309         else if(split.counts[ePlaneBack] == 0)
 310         {
 311           for(brush_vector_t::iterator i = fragments.begin(); i != fragments.end(); ++i)
 312           {
 313             delete(*i);
 314           }
 315           return false;
 316         }
 317       }
 318     }
 319     ret_fragments.insert(ret_fragments.end(), fragments.begin(), fragments.end());
 320     return true;
 321   }
 322   return false;
 323 }
 324
 325 class SubtractBrushesFromUnselected : public scene::Graph::Walker
 326 {
 327   const brush_vector_t& m_brushlist;
 328   std::size_t& m_before;
 329   std::size_t& m_after;
 330 public:
 331   SubtractBrushesFromUnselected(const brush_vector_t& brushlist, std::size_t& before, std::size_t& after)
 332     : m_brushlist(brushlist), m_before(before), m_after(after)
 333   {
 334   }
 335   bool pre(const scene::Path& path, scene::Instance& instance) const
 336   {
 337     return true;
 338   }
 339   void post(const scene::Path& path, scene::Instance& instance) const
 340   {
 341     if(path.top().get().visible())
 342     {
 343       Brush* brush = Node_getBrush(path.top());
 344       if(brush != 0
 345         && !Instance_getSelectable(instance)->isSelected())
 346       {
 347         brush_vector_t buffer[2];
 348         bool swap = false;
 349         Brush* original = new Brush(*brush);
 350         buffer[static_cast<std::size_t>(swap)].push_back(original);
 351
 352         {
 353           for(brush_vector_t::const_iterator i(m_brushlist.begin()); i != m_brushlist.end(); ++i)
 354           {
 355             for(brush_vector_t::iterator j(buffer[static_cast<std::size_t>(swap)].begin()); j != buffer[static_cast<std::size_t>(swap)].end(); ++j)
 356             {
 357               if(Brush_subtract(*(*j), *(*i), buffer[static_cast<std::size_t>(!swap)]))
 358               {
 359                 delete (*j);
 360               }
 361               else
 362               {
 363                 buffer[static_cast<std::size_t>(!swap)].push_back((*j));
 364               }
 365             }
 366             buffer[static_cast<std::size_t>(swap)].clear();
 367             swap = !swap;
 368           }
 369         }
 370
 371         brush_vector_t& out = buffer[static_cast<std::size_t>(swap)];
 372
 373         if(out.size() == 1 && out.back() == original)
 374         {
 375           delete original;
 376         }
 377         else
 378         {
 379           ++m_before;
 380           for(brush_vector_t::const_iterator i = out.begin(); i != out.end(); ++i)
 381           {
 382             ++m_after;
 383             NodeSmartReference node((new BrushNode())->node());
 384             (*i)->removeEmptyFaces();
 385             ASSERT_MESSAGE(!(*i)->empty(), "brush left with no faces after subtract");
 386             Node_getBrush(node)->copy(*(*i));
 387             delete (*i);
 388             Node_getTraversable(path.parent())->insert(node);
 389           }
 390           Path_deleteTop(path);
 391         }
 392       }
 393     }
 394   }
 395 };
 396
 397 void CSG_Subtract()
 398 {
 399   brush_vector_t selected_brushes;
 400   GlobalSceneGraph().traverse(BrushGatherSelected(selected_brushes));
 401
 402   if (selected_brushes.empty())
 403   {
 404     globalOutputStream() << "CSG Subtract: No brushes selected.\n";
 405   }
 406   else
 407   {
 408     globalOutputStream() << "CSG Subtract: Subtracting " << Unsigned(selected_brushes.size()) << " brushes.\n";
 409
 410     UndoableCommand undo("brushSubtract");
 411
 412     // subtract selected from unselected
 413     std::size_t before = 0;
 414     std::size_t after = 0;
 415     GlobalSceneGraph().traverse(SubtractBrushesFromUnselected(selected_brushes, before, after));
 416     globalOutputStream() << "CSG Subtract: Result: "
 417       << Unsigned(after) << " fragment" << (after == 1 ? "" : "s")
 418       << " from " << Unsigned(before) << " brush" << (before == 1? "" : "es") << ".\n";
 419
 420     SceneChangeNotify();
 421   }
 422 }
 423
 424 class BrushSplitByPlaneSelected : public scene::Graph::Walker
 425 {
 426   const Vector3& m_p0;
 427   const Vector3& m_p1;
 428   const Vector3& m_p2;
 429   const char* m_shader;
 430   const TextureProjection& m_projection;
 431   EBrushSplit m_split;
 432 public:
 433   BrushSplitByPlaneSelected(const Vector3& p0, const Vector3& p1, const Vector3& p2, const char* shader, const TextureProjection& projection, EBrushSplit split)
 434     : m_p0(p0), m_p1(p1), m_p2(p2), m_shader(shader), m_projection(projection), m_split(split)
 435   {
 436   }
 437   bool pre(const scene::Path& path, scene::Instance& instance) const
 438   {
 439     return true;
 440   }
 441   void post(const scene::Path& path, scene::Instance& instance) const
 442   {
 443     if(path.top().get().visible())
 444     {
 445       Brush* brush = Node_getBrush(path.top());
 446       if(brush != 0
 447         && Instance_getSelectable(instance)->isSelected())
 448       {
 449         Plane3 plane(plane3_for_points(m_p0, m_p1, m_p2));
 450         if(plane3_valid(plane))
 451         {
 452           brushsplit_t split = Brush_classifyPlane(*brush, m_split == eFront ? plane3_flipped(plane) : plane);
 453           if(split.counts[ePlaneBack] && split.counts[ePlaneFront])
 454           {
 455             // the plane intersects this brush
 456             if(m_split == eFrontAndBack)
 457             {
 458               NodeSmartReference node((new BrushNode())->node());
 459               Brush* fragment = Node_getBrush(node);
 460               fragment->copy(*brush);
 461               Face* newFace = fragment->addPlane(m_p0, m_p1, m_p2, m_shader, m_projection);
 462               if(newFace != 0 && m_split != eFront)
 463               {
 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             {
 480               newFace->flipWinding();
 481             }
 482             brush->removeEmptyFaces();
 483             ASSERT_MESSAGE(!brush->empty(), "brush left with no faces after split");
 484           }
 485           else
 486             // the plane does not intersect this brush
 487           if(m_split != eFrontAndBack && split.counts[ePlaneBack] != 0)
 488           {
 489             // the brush is "behind" the plane
 490             Path_deleteTop(path);
 491           }
 492         }
 493       }
 494     }
 495   }
 496 };
 497
 498 void Scene_BrushSplitByPlane(scene::Graph& graph, const Vector3& p0, const Vector3& p1, const Vector3& p2, const char* shader, EBrushSplit split)
 499 {
 500   TextureProjection projection;
 501   TexDef_Construct_Default(projection);
 502   graph.traverse(BrushSplitByPlaneSelected(p0, p1, p2, shader, projection, split));
 503   SceneChangeNotify();
 504 }
 505
 506
 507 class BrushInstanceSetClipPlane : public scene::Graph::Walker
 508 {
 509   Plane3 m_plane;
 510 public:
 511   BrushInstanceSetClipPlane(const Plane3& plane)
 512     : m_plane(plane)
 513   {
 514   }
 515   bool pre(const scene::Path& path, scene::Instance& instance) const
 516   {
 517     BrushInstance* brush = Instance_getBrush(instance);
 518     if(brush != 0
 519       && path.top().get().visible()
 520       && brush->isSelected())
 521     {
 522       BrushInstance& brushInstance = *brush;
 523       brushInstance.setClipPlane(m_plane);
 524     }
 525     return true;
 526   }
 527 };
 528
 529 void Scene_BrushSetClipPlane(scene::Graph& graph, const Plane3& plane)
 530 {
 531   graph.traverse(BrushInstanceSetClipPlane(plane));
 532 }
 533
 534 /*
 535 =============
 536 CSG_Merge
 537 =============
 538 */
 539 bool Brush_merge(Brush& brush, const brush_vector_t& in, bool onlyshape)
 540 {
 541   // gather potential outer faces
 542
 543   {
 544     typedef std::vector<const Face*> Faces;
 545     Faces faces;
 546     for(brush_vector_t::const_iterator i(in.begin()); i != in.end(); ++i)
 547     {
 548       (*i)->evaluateBRep();
 549       for(Brush::const_iterator j((*i)->begin()); j != (*i)->end(); ++j)
 550       {
 551         if(!(*j)->contributes())
 552         {
 553           continue;
 554         }
 555
 556         const Face& face1 = *(*j);
 557
 558         bool skip = false;
 559         // test faces of all input brushes
 560         //!\todo SPEEDUP: Flag already-skip faces and only test brushes from i+1 upwards.
 561         for(brush_vector_t::const_iterator k(in.begin()); !skip && k != in.end(); ++k)
 562         {
 563           if(k != i) // don't test a brush against itself
 564           {
 565             for(Brush::const_iterator l((*k)->begin()); !skip && l != (*k)->end(); ++l)
 566             {
 567               const Face& face2 = *(*l);
 568
 569               // face opposes another face
 570               if(plane3_opposing(face1.plane3(), face2.plane3()))
 571               {
 572                 // skip opposing planes
 573                 skip  = true;
 574                 break;
 575               }
 576             }
 577           }
 578         }
 579
 580         // check faces already stored
 581         for(Faces::const_iterator m = faces.begin(); !skip && m != faces.end(); ++m)
 582         {
 583           const Face& face2 = *(*m);
 584
 585           // face equals another face
 586           if (plane3_equal(face1.plane3(), face2.plane3()))
 587           {
 588             //if the texture/shader references should be the same but are not
 589             if (!onlyshape && !shader_equal(face1.getShader().getShader(), face2.getShader().getShader()))
 590             {
 591               return false;
 592             }
 593             // skip duplicate planes
 594             skip = true;
 595             break;
 596           }
 597
 598           // face1 plane intersects face2 winding or vice versa
 599           if (Winding_PlanesConcave(face1.getWinding(), face2.getWinding(), face1.plane3(), face2.plane3()))
 600           {
 601             // result would not be convex
 602             return false;
 603           }
 604         }
 605
 606         if(!skip)
 607         {
 608           faces.push_back(&face1);
 609         }
 610       }
 611     }
 612     for(Faces::const_iterator i = faces.begin(); i != faces.end(); ++i)
 613     {
 614       if(!brush.addFace(*(*i)))
 615       {
 616         // result would have too many sides
 617         return false;
 618       }
 619     }
 620   }
 621
 622   brush.removeEmptyFaces();
 623
 624   return true;
 625 }
 626
 627 void CSG_Merge(void)
 628 {
 629   brush_vector_t selected_brushes;
 630
 631   // remove selected
 632   GlobalSceneGraph().traverse(BrushGatherSelected(selected_brushes));
 633
 634   if (selected_brushes.empty())
 635   {
 636     globalOutputStream() << "CSG Merge: No brushes selected.\n";
 637     return;
 638   }
 639
 640   if (selected_brushes.size() < 2)
 641   {
 642     globalOutputStream() << "CSG Merge: At least two brushes have to be selected.\n";
 643     return;
 644   }
 645
 646   globalOutputStream() << "CSG Merge: Merging " << Unsigned(selected_brushes.size()) << " brushes.\n";
 647
 648   UndoableCommand undo("brushMerge");
 649
 650   scene::Path merged_path = GlobalSelectionSystem().ultimateSelected().path();
 651
 652   NodeSmartReference node((new BrushNode())->node());
 653   Brush* brush = Node_getBrush(node);
 654   // if the new brush would not be convex
 655   if(!Brush_merge(*brush, selected_brushes, true))
 656   {
 657     globalOutputStream() << "CSG Merge: Failed - result would not be convex.\n";
 658   }
 659   else
 660   {
 661     ASSERT_MESSAGE(!brush->empty(), "brush left with no faces after merge");
 662
 663     // free the original brushes
 664     GlobalSceneGraph().traverse(BrushDeleteSelected());
 665
 666     merged_path.pop();
 667     Node_getTraversable(merged_path.top())->insert(node);
 668     merged_path.push(makeReference(node.get()));
 669
 670     selectPath(merged_path, true);
 671
 672     globalOutputStream() << "CSG Merge: Succeeded.\n";
 673     SceneChangeNotify();
 674   }
 675 }