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