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             NodeSmartReference node((new BrushNode())->node());
 401             (*i)->removeEmptyFaces();
 402             ASSERT_MESSAGE(!(*i)->empty(), "brush left with no faces after subtract");
 403             Node_getBrush(node)->copy(*(*i));
 404             delete (*i);
 405             Node_getTraversable(path.parent())->insert(node);
 406           }
 407           Path_deleteTop(path);
 408         }
 409       }
 410     }
 411   }
 412 };
 413
 414 void CSG_Subtract()
 415 {
 416   brush_vector_t selected_brushes;
 417   GlobalSceneGraph().traverse(BrushGatherSelected(selected_brushes));
 418
 419   if (selected_brushes.empty())
 420   {
 421     globalOutputStream() << "CSG Subtract: No brushes selected.\n";
 422   }
 423   else
 424   {
 425     globalOutputStream() << "CSG Subtract: Subtracting " << Unsigned(selected_brushes.size()) << " brushes.\n";
 426
 427     UndoableCommand undo("brushSubtract");
 428
 429     // subtract selected from unselected
 430     std::size_t before = 0;
 431     std::size_t after = 0;
 432     GlobalSceneGraph().traverse(SubtractBrushesFromUnselected(selected_brushes, before, after));
 433     globalOutputStream() << "CSG Subtract: Result: "
 434       << Unsigned(after) << " fragment" << (after == 1 ? "" : "s")
 435       << " from " << Unsigned(before) << " brush" << (before == 1? "" : "es") << ".\n";
 436
 437     SceneChangeNotify();
 438   }
 439 }
 440
 441 class BrushSplitByPlaneSelected : public scene::Graph::Walker
 442 {
 443   const Vector3& m_p0;
 444   const Vector3& m_p1;
 445   const Vector3& m_p2;
 446   const char* m_shader;
 447   const TextureProjection& m_projection;
 448   EBrushSplit m_split;
 449 public:
 450   BrushSplitByPlaneSelected(const Vector3& p0, const Vector3& p1, const Vector3& p2, const char* shader, const TextureProjection& projection, EBrushSplit split)
 451     : m_p0(p0), m_p1(p1), m_p2(p2), m_shader(shader), m_projection(projection), m_split(split)
 452   {
 453   }
 454   bool pre(const scene::Path& path, scene::Instance& instance) const
 455   {
 456     return true;
 457   }
 458   void post(const scene::Path& path, scene::Instance& instance) const
 459   {
 460     if(path.top().get().visible())
 461     {
 462       Brush* brush = Node_getBrush(path.top());
 463       if(brush != 0
 464         && Instance_getSelectable(instance)->isSelected())
 465       {
 466         Plane3 plane(plane3_for_points(m_p0, m_p1, m_p2));
 467         if(plane3_valid(plane))
 468         {
 469           brushsplit_t split = Brush_classifyPlane(*brush, m_split == eFront ? plane3_flipped(plane) : plane);
 470           if(split.counts[ePlaneBack] && split.counts[ePlaneFront])
 471           {
 472             // the plane intersects this brush
 473             if(m_split == eFrontAndBack)
 474             {
 475               NodeSmartReference node((new BrushNode())->node());
 476               Brush* fragment = Node_getBrush(node);
 477               fragment->copy(*brush);
 478               Face* newFace = fragment->addPlane(m_p0, m_p1, m_p2, m_shader, m_projection);
 479               if(newFace != 0 && m_split != eFront)
 480               {
 481                 newFace->flipWinding();
 482               }
 483               fragment->removeEmptyFaces();
 484               ASSERT_MESSAGE(!fragment->empty(), "brush left with no faces after split");
 485
 486               Node_getTraversable(path.parent())->insert(node);
 487               {
 488                 scene::Path fragmentPath = path;
 489                 fragmentPath.top() = makeReference(node.get());
 490                 selectPath(fragmentPath, true);
 491               }
 492             }
 493
 494             Face* newFace = brush->addPlane(m_p0, m_p1, m_p2, m_shader, m_projection);
 495             if(newFace != 0 && m_split == eFront)
 496             {
 497               newFace->flipWinding();
 498             }
 499             brush->removeEmptyFaces();
 500             ASSERT_MESSAGE(!brush->empty(), "brush left with no faces after split");
 501           }
 502           else
 503             // the plane does not intersect this brush
 504           if(m_split != eFrontAndBack && split.counts[ePlaneBack] != 0)
 505           {
 506             // the brush is "behind" the plane
 507             Path_deleteTop(path);
 508           }
 509         }
 510       }
 511     }
 512   }
 513 };
 514
 515 void Scene_BrushSplitByPlane(scene::Graph& graph, const Vector3& p0, const Vector3& p1, const Vector3& p2, const char* shader, EBrushSplit split)
 516 {
 517   TextureProjection projection;
 518   TexDef_Construct_Default(projection);
 519   graph.traverse(BrushSplitByPlaneSelected(p0, p1, p2, shader, projection, split));
 520   SceneChangeNotify();
 521 }
 522
 523
 524 class BrushInstanceSetClipPlane : public scene::Graph::Walker
 525 {
 526   Plane3 m_plane;
 527 public:
 528   BrushInstanceSetClipPlane(const Plane3& plane)
 529     : m_plane(plane)
 530   {
 531   }
 532   bool pre(const scene::Path& path, scene::Instance& instance) const
 533   {
 534     BrushInstance* brush = Instance_getBrush(instance);
 535     if(brush != 0
 536       && path.top().get().visible()
 537       && brush->isSelected())
 538     {
 539       BrushInstance& brushInstance = *brush;
 540       brushInstance.setClipPlane(m_plane);
 541     }
 542     return true;
 543   }
 544 };
 545
 546 void Scene_BrushSetClipPlane(scene::Graph& graph, const Plane3& plane)
 547 {
 548   graph.traverse(BrushInstanceSetClipPlane(plane));
 549 }
 550
 551 /*
 552 =============
 553 CSG_Merge
 554 =============
 555 */
 556 bool Brush_merge(Brush& brush, const brush_vector_t& in, bool onlyshape)
 557 {
 558   // gather potential outer faces
 559
 560   {
 561     typedef std::vector<const Face*> Faces;
 562     Faces faces;
 563     for(brush_vector_t::const_iterator i(in.begin()); i != in.end(); ++i)
 564     {
 565       (*i)->evaluateBRep();
 566       for(Brush::const_iterator j((*i)->begin()); j != (*i)->end(); ++j)
 567       {
 568         if(!(*j)->contributes())
 569         {
 570           continue;
 571         }
 572
 573         const Face& face1 = *(*j);
 574
 575         bool skip = false;
 576         // test faces of all input brushes
 577         //!\todo SPEEDUP: Flag already-skip faces and only test brushes from i+1 upwards.
 578         for(brush_vector_t::const_iterator k(in.begin()); !skip && k != in.end(); ++k)
 579         {
 580           if(k != i) // don't test a brush against itself
 581           {
 582             for(Brush::const_iterator l((*k)->begin()); !skip && l != (*k)->end(); ++l)
 583             {
 584               const Face& face2 = *(*l);
 585
 586               // face opposes another face
 587               if(plane3_opposing(face1.plane3(), face2.plane3()))
 588               {
 589                 // skip opposing planes
 590                 skip  = true;
 591                 break;
 592               }
 593             }
 594           }
 595         }
 596
 597         // check faces already stored
 598         for(Faces::const_iterator m = faces.begin(); !skip && m != faces.end(); ++m)
 599         {
 600           const Face& face2 = *(*m);
 601
 602           // face equals another face
 603           if (plane3_equal(face1.plane3(), face2.plane3()))
 604           {
 605             //if the texture/shader references should be the same but are not
 606             if (!onlyshape && !shader_equal(face1.getShader().getShader(), face2.getShader().getShader()))
 607             {
 608               return false;
 609             }
 610             // skip duplicate planes
 611             skip = true;
 612             break;
 613           }
 614
 615           // face1 plane intersects face2 winding or vice versa
 616           if (Winding_PlanesConcave(face1.getWinding(), face2.getWinding(), face1.plane3(), face2.plane3()))
 617           {
 618             // result would not be convex
 619             return false;
 620           }
 621         }
 622
 623         if(!skip)
 624         {
 625           faces.push_back(&face1);
 626         }
 627       }
 628     }
 629     for(Faces::const_iterator i = faces.begin(); i != faces.end(); ++i)
 630     {
 631       if(!brush.addFace(*(*i)))
 632       {
 633         // result would have too many sides
 634         return false;
 635       }
 636     }
 637   }
 638
 639   brush.removeEmptyFaces();
 640
 641   return true;
 642 }
 643
 644 void CSG_Merge(void)
 645 {
 646   brush_vector_t selected_brushes;
 647
 648   // remove selected
 649   GlobalSceneGraph().traverse(BrushGatherSelected(selected_brushes));
 650
 651   if (selected_brushes.empty())
 652   {
 653     globalOutputStream() << "CSG Merge: No brushes selected.\n";
 654     return;
 655   }
 656
 657   if (selected_brushes.size() < 2)
 658   {
 659     globalOutputStream() << "CSG Merge: At least two brushes have to be selected.\n";
 660     return;
 661   }
 662
 663   globalOutputStream() << "CSG Merge: Merging " << Unsigned(selected_brushes.size()) << " brushes.\n";
 664
 665   UndoableCommand undo("brushMerge");
 666
 667   scene::Path merged_path = GlobalSelectionSystem().ultimateSelected().path();
 668
 669   NodeSmartReference node((new BrushNode())->node());
 670   Brush* brush = Node_getBrush(node);
 671   // if the new brush would not be convex
 672   if(!Brush_merge(*brush, selected_brushes, true))
 673   {
 674     globalOutputStream() << "CSG Merge: Failed - result would not be convex.\n";
 675   }
 676   else
 677   {
 678     ASSERT_MESSAGE(!brush->empty(), "brush left with no faces after merge");
 679
 680     // free the original brushes
 681     GlobalSceneGraph().traverse(BrushDeleteSelected());
 682
 683     merged_path.pop();
 684     Node_getTraversable(merged_path.top())->insert(node);
 685     merged_path.push(makeReference(node.get()));
 686
 687     selectPath(merged_path, true);
 688
 689     globalOutputStream() << "CSG Merge: Succeeded.\n";
 690     SceneChangeNotify();
 691   }
 692 }