2 Copyright (C) 1999-2006 Id Software, Inc. and contributors.
3 For a list of contributors, see the accompanying CONTRIBUTORS file.
5 This file is part of GtkRadiant.
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.
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.
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
24 #include "debugging/debugging.h"
29 #include "brushmanip.h"
30 #include "brushnode.h"
33 void Face_makeBrush(Face& face, const Brush& brush, brush_vector_t& out, float offset)
35 if(face.contributes())
37 out.push_back(new Brush(brush));
38 Face* newFace = out.back()->addFace(face);
41 newFace->flipWinding();
42 newFace->getPlane().offset(offset);
43 newFace->planeChanged();
54 FaceMakeBrush(const Brush& brush, brush_vector_t& out, float offset)
55 : brush(brush), out(out), offset(offset)
58 void operator()(Face& face) const
60 Face_makeBrush(face, brush, out, offset);
64 void Brush_makeHollow(const Brush& brush, brush_vector_t& out, float offset)
66 Brush_forEachFace(brush, FaceMakeBrush(brush, out, offset));
69 class BrushHollowSelectedWalker : public scene::Graph::Walker
73 BrushHollowSelectedWalker(float offset)
77 bool pre(const scene::Path& path, scene::Instance& instance) const
79 if(path.top().get().visible())
81 Brush* brush = Node_getBrush(path.top());
83 && Instance_getSelectable(instance)->isSelected()
87 Brush_makeHollow(*brush, out, m_offset);
88 for(brush_vector_t::const_iterator i = out.begin(); i != out.end(); ++i)
90 (*i)->removeEmptyFaces();
91 NodeSmartReference node((new BrushNode())->node());
92 Node_getBrush(node)->copy(*(*i));
94 Node_getTraversable(path.parent())->insert(node);
102 typedef std::list<Brush*> brushlist_t;
104 class BrushGatherSelected : public scene::Graph::Walker
106 brush_vector_t& m_brushlist;
108 BrushGatherSelected(brush_vector_t& brushlist)
109 : m_brushlist(brushlist)
112 bool pre(const scene::Path& path, scene::Instance& instance) const
114 if(path.top().get().visible())
116 Brush* brush = Node_getBrush(path.top());
118 && Instance_getSelectable(instance)->isSelected())
120 m_brushlist.push_back(brush);
127 class BrushDeleteSelected : public scene::Graph::Walker
130 bool pre(const scene::Path& path, scene::Instance& instance) const
134 void post(const scene::Path& path, scene::Instance& instance) const
136 if(path.top().get().visible())
138 Brush* brush = Node_getBrush(path.top());
140 && Instance_getSelectable(instance)->isSelected()
143 Path_deleteTop(path);
149 void Scene_BrushMakeHollow_Selected(scene::Graph& graph)
151 GlobalSceneGraph().traverse(BrushHollowSelectedWalker(GetGridSize()));
152 GlobalSceneGraph().traverse(BrushDeleteSelected());
161 void CSG_MakeHollow (void)
163 UndoableCommand undo("brushHollow");
165 Scene_BrushMakeHollow_Selected(GlobalSceneGraph());
170 template<typename Functor>
173 const Functor& functor;
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)
180 result_type operator()(first_argument_type firstArgument) const
182 return functor(*firstArgument);
186 template<typename Functor>
187 inline Dereference<Functor> makeDereference(const Functor& functor)
189 return Dereference<Functor>(functor);
192 template<typename Predicate>
193 Face* Brush_findIf(const Brush& brush, const Predicate& predicate)
195 Brush::const_iterator i = std::find_if(brush.begin(), brush.end(), makeDereference(predicate));
196 return i == brush.end() ? 0 : *i;
199 template<typename Caller>
202 typedef typename Caller::SecondArgument FirstBound;
203 FirstBound firstBound;
205 typedef typename Caller::Return Return;
206 typedef typename Caller::FirstArgument FirstArgument;
207 BindArguments1(FirstBound firstBound)
208 : firstBound(firstBound)
211 Return operator()(FirstArgument firstArgument) const
213 return Caller::call(firstArgument, firstBound);
217 template<typename Caller>
220 typedef typename Caller::SecondArgument FirstBound;
221 typedef typename Caller::ThirdArgument SecondBound;
222 FirstBound firstBound;
223 SecondBound secondBound;
225 typedef typename Caller::Return Return;
226 typedef typename Caller::FirstArgument FirstArgument;
227 BindArguments2(FirstBound firstBound, SecondBound secondBound)
228 : firstBound(firstBound), secondBound(secondBound)
231 Return operator()(FirstArgument firstArgument) const
233 return Caller::call(firstArgument, firstBound, secondBound);
237 template<typename Caller, typename FirstBound, typename SecondBound>
238 BindArguments2<Caller> bindArguments(const Caller& caller, FirstBound firstBound, SecondBound secondBound)
240 return BindArguments2<Caller>(firstBound, secondBound);
243 inline bool Face_testPlane(const Face& face, const Plane3& plane, bool flipped)
245 return face.contributes() && !Winding_TestPlane(face.getWinding(), plane, flipped);
247 typedef Function3<const Face&, const Plane3&, bool, bool, Face_testPlane> FaceTestPlane;
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)
256 brush.evaluateBRep();
258 for(Brush::const_iterator i(brush.begin()); i != brush.end(); ++i)
260 if(Face_testPlane(*(*i), plane, flipped))
267 return Brush_findIf(brush, bindArguments(FaceTestPlane(), makeReference(plane), flipped)) == 0;
271 brushsplit_t Brush_classifyPlane(const Brush& brush, const Plane3& plane)
273 brush.evaluateBRep();
275 for(Brush::const_iterator i(brush.begin()); i != brush.end(); ++i)
277 if((*i)->contributes())
279 split += Winding_ClassifyPlane((*i)->getWinding(), plane);
285 bool Brush_subtract(const Brush& brush, const Brush& other, brush_vector_t& ret_fragments)
287 if(aabb_intersects_aabb(brush.localAABB(), other.localAABB()))
289 brush_vector_t fragments;
290 fragments.reserve(other.size());
293 for(Brush::const_iterator i(other.begin()); i != other.end(); ++i)
295 if((*i)->contributes())
297 brushsplit_t split = Brush_classifyPlane(back, (*i)->plane3());
298 if(split.counts[ePlaneFront] != 0
299 && split.counts[ePlaneBack] != 0)
301 fragments.push_back(new Brush(back));
302 Face* newFace = fragments.back()->addFace(*(*i));
305 newFace->flipWinding();
309 else if(split.counts[ePlaneBack] == 0)
311 for(brush_vector_t::iterator i = fragments.begin(); i != fragments.end(); ++i)
319 ret_fragments.insert(ret_fragments.end(), fragments.begin(), fragments.end());
325 class SubtractBrushesFromUnselected : public scene::Graph::Walker
327 const brush_vector_t& m_brushlist;
328 std::size_t& m_before;
329 std::size_t& m_after;
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)
335 bool pre(const scene::Path& path, scene::Instance& instance) const
339 void post(const scene::Path& path, scene::Instance& instance) const
341 if(path.top().get().visible())
343 Brush* brush = Node_getBrush(path.top());
345 && !Instance_getSelectable(instance)->isSelected())
347 brush_vector_t buffer[2];
349 Brush* original = new Brush(*brush);
350 buffer[static_cast<std::size_t>(swap)].push_back(original);
353 for(brush_vector_t::const_iterator i(m_brushlist.begin()); i != m_brushlist.end(); ++i)
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)
357 if(Brush_subtract(*(*j), *(*i), buffer[static_cast<std::size_t>(!swap)]))
363 buffer[static_cast<std::size_t>(!swap)].push_back((*j));
366 buffer[static_cast<std::size_t>(swap)].clear();
371 brush_vector_t& out = buffer[static_cast<std::size_t>(swap)];
373 if(out.size() == 1 && out.back() == original)
380 for(brush_vector_t::const_iterator i = out.begin(); i != out.end(); ++i)
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));
388 Node_getTraversable(path.parent())->insert(node);
390 Path_deleteTop(path);
399 brush_vector_t selected_brushes;
400 GlobalSceneGraph().traverse(BrushGatherSelected(selected_brushes));
402 if (selected_brushes.empty())
404 globalOutputStream() << "CSG Subtract: No brushes selected.\n";
408 globalOutputStream() << "CSG Subtract: Subtracting " << Unsigned(selected_brushes.size()) << " brushes.\n";
410 UndoableCommand undo("brushSubtract");
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";
424 class BrushSplitByPlaneSelected : public scene::Graph::Walker
429 const char* m_shader;
430 const TextureProjection& m_projection;
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)
437 bool pre(const scene::Path& path, scene::Instance& instance) const
441 void post(const scene::Path& path, scene::Instance& instance) const
443 if(path.top().get().visible())
445 Brush* brush = Node_getBrush(path.top());
447 && Instance_getSelectable(instance)->isSelected())
449 Plane3 plane(plane3_for_points(m_p0, m_p1, m_p2));
450 if(plane3_valid(plane))
452 brushsplit_t split = Brush_classifyPlane(*brush, m_split == eFront ? plane3_flipped(plane) : plane);
453 if(split.counts[ePlaneBack] && split.counts[ePlaneFront])
455 // the plane intersects this brush
456 if(m_split == eFrontAndBack)
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)
464 newFace->flipWinding();
466 fragment->removeEmptyFaces();
467 ASSERT_MESSAGE(!fragment->empty(), "brush left with no faces after split");
469 Node_getTraversable(path.parent())->insert(node);
471 scene::Path fragmentPath = path;
472 fragmentPath.top() = makeReference(node.get());
473 selectPath(fragmentPath, true);
477 Face* newFace = brush->addPlane(m_p0, m_p1, m_p2, m_shader, m_projection);
478 if(newFace != 0 && m_split == eFront)
480 newFace->flipWinding();
482 brush->removeEmptyFaces();
483 ASSERT_MESSAGE(!brush->empty(), "brush left with no faces after split");
486 // the plane does not intersect this brush
487 if(m_split != eFrontAndBack && split.counts[ePlaneBack] != 0)
489 // the brush is "behind" the plane
490 Path_deleteTop(path);
498 void Scene_BrushSplitByPlane(scene::Graph& graph, const Vector3& p0, const Vector3& p1, const Vector3& p2, const char* shader, EBrushSplit split)
500 TextureProjection projection;
501 TexDef_Construct_Default(projection);
502 graph.traverse(BrushSplitByPlaneSelected(p0, p1, p2, shader, projection, split));
507 class BrushInstanceSetClipPlane : public scene::Graph::Walker
511 BrushInstanceSetClipPlane(const Plane3& plane)
515 bool pre(const scene::Path& path, scene::Instance& instance) const
517 BrushInstance* brush = Instance_getBrush(instance);
519 && path.top().get().visible()
520 && brush->isSelected())
522 BrushInstance& brushInstance = *brush;
523 brushInstance.setClipPlane(m_plane);
529 void Scene_BrushSetClipPlane(scene::Graph& graph, const Plane3& plane)
531 graph.traverse(BrushInstanceSetClipPlane(plane));
539 bool Brush_merge(Brush& brush, const brush_vector_t& in, bool onlyshape)
541 // gather potential outer faces
544 typedef std::vector<const Face*> Faces;
546 for(brush_vector_t::const_iterator i(in.begin()); i != in.end(); ++i)
548 (*i)->evaluateBRep();
549 for(Brush::const_iterator j((*i)->begin()); j != (*i)->end(); ++j)
551 if(!(*j)->contributes())
556 const Face& face1 = *(*j);
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)
563 if(k != i) // don't test a brush against itself
565 for(Brush::const_iterator l((*k)->begin()); !skip && l != (*k)->end(); ++l)
567 const Face& face2 = *(*l);
569 // face opposes another face
570 if(plane3_opposing(face1.plane3(), face2.plane3()))
572 // skip opposing planes
580 // check faces already stored
581 for(Faces::const_iterator m = faces.begin(); !skip && m != faces.end(); ++m)
583 const Face& face2 = *(*m);
585 // face equals another face
586 if (plane3_equal(face1.plane3(), face2.plane3()))
588 //if the texture/shader references should be the same but are not
589 if (!onlyshape && !shader_equal(face1.getShader().getShader(), face2.getShader().getShader()))
593 // skip duplicate planes
598 // face1 plane intersects face2 winding or vice versa
599 if (Winding_PlanesConcave(face1.getWinding(), face2.getWinding(), face1.plane3(), face2.plane3()))
601 // result would not be convex
608 faces.push_back(&face1);
612 for(Faces::const_iterator i = faces.begin(); i != faces.end(); ++i)
614 if(!brush.addFace(*(*i)))
616 // result would have too many sides
622 brush.removeEmptyFaces();
629 brush_vector_t selected_brushes;
632 GlobalSceneGraph().traverse(BrushGatherSelected(selected_brushes));
634 if (selected_brushes.empty())
636 globalOutputStream() << "CSG Merge: No brushes selected.\n";
640 if (selected_brushes.size() < 2)
642 globalOutputStream() << "CSG Merge: At least two brushes have to be selected.\n";
646 globalOutputStream() << "CSG Merge: Merging " << Unsigned(selected_brushes.size()) << " brushes.\n";
648 UndoableCommand undo("brushMerge");
650 scene::Path merged_path = GlobalSelectionSystem().ultimateSelected().path();
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))
657 globalOutputStream() << "CSG Merge: Failed - result would not be convex.\n";
661 ASSERT_MESSAGE(!brush->empty(), "brush left with no faces after merge");
663 // free the original brushes
664 GlobalSceneGraph().traverse(BrushDeleteSelected());
667 Node_getTraversable(merged_path.top())->insert(node);
668 merged_path.push(makeReference(node.get()));
670 selectPath(merged_path, true);
672 globalOutputStream() << "CSG Merge: Succeeded.\n";