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()) {
36 out.push_back(new Brush(brush));
37 Face *newFace = out.back()->addFace(face);
39 newFace->flipWinding();
40 newFace->getPlane().offset(offset);
41 newFace->planeChanged();
46 void Face_makeRoom(Face &face, const Brush &brush, brush_vector_t &out, float offset)
48 if (face.contributes()) {
49 face.getPlane().offset(offset);
50 out.push_back(new Brush(brush));
51 face.getPlane().offset(-offset);
52 Face *newFace = out.back()->addFace(face);
54 newFace->flipWinding();
55 newFace->planeChanged();
60 void Brush_makeHollow(const Brush &brush, brush_vector_t &out, float offset)
62 Brush_forEachFace(brush, [&](Face &face) {
63 Face_makeBrush(face, brush, out, offset);
67 void Brush_makeRoom(const Brush &brush, brush_vector_t &out, float offset)
69 Brush_forEachFace(brush, [&](Face &face) {
70 Face_makeRoom(face, brush, out, offset);
74 class BrushHollowSelectedWalker : public scene::Graph::Walker {
78 BrushHollowSelectedWalker(float offset, bool makeRoom)
79 : m_offset(offset), m_makeRoom(makeRoom)
83 bool pre(const scene::Path &path, scene::Instance &instance) const
85 if (path.top().get().visible()) {
86 Brush *brush = Node_getBrush(path.top());
88 && Instance_getSelectable(instance)->isSelected()
93 Brush_makeRoom(*brush, out, m_offset);
96 Brush_makeHollow(*brush, out, m_offset);
99 for (brush_vector_t::const_iterator i = out.begin(); i != out.end(); ++i) {
100 (*i)->removeEmptyFaces();
101 NodeSmartReference node((new BrushNode())->node());
102 Node_getBrush(node)->copy(*(*i));
104 Node_getTraversable(path.parent())->insert(node);
112 typedef std::list<Brush *> brushlist_t;
114 class BrushGatherSelected : public scene::Graph::Walker {
115 brush_vector_t &m_brushlist;
117 BrushGatherSelected(brush_vector_t &brushlist)
118 : m_brushlist(brushlist)
122 bool pre(const scene::Path &path, scene::Instance &instance) const
124 if (path.top().get().visible()) {
125 Brush *brush = Node_getBrush(path.top());
127 && Instance_getSelectable(instance)->isSelected()) {
128 m_brushlist.push_back(brush);
135 class BrushDeleteSelected : public scene::Graph::Walker {
137 bool pre(const scene::Path &path, scene::Instance &instance) const
142 void post(const scene::Path &path, scene::Instance &instance) const
144 if (path.top().get().visible()) {
145 Brush *brush = Node_getBrush(path.top());
147 && Instance_getSelectable(instance)->isSelected()
148 && path.size() > 1) {
149 Path_deleteTop(path);
155 void Scene_BrushMakeHollow_Selected(scene::Graph &graph, bool makeRoom)
157 GlobalSceneGraph().traverse(BrushHollowSelectedWalker(GetGridSize(), makeRoom));
158 GlobalSceneGraph().traverse(BrushDeleteSelected());
167 void CSG_MakeHollow(void)
169 UndoableCommand undo("brushHollow");
171 Scene_BrushMakeHollow_Selected(GlobalSceneGraph(), false);
176 void CSG_MakeRoom(void)
178 UndoableCommand undo("brushRoom");
180 Scene_BrushMakeHollow_Selected(GlobalSceneGraph(), true);
185 template<typename Type>
186 class RemoveReference {
191 template<typename Type>
192 class RemoveReference<Type &> {
197 template<typename Functor>
199 const Functor &functor;
201 Dereference(const Functor &functor) : functor(functor)
205 get_result_type<Functor> operator()(typename RemoveReference<get_argument<Functor, 0>>::type *firstArgument) const
207 return functor(*firstArgument);
211 template<typename Functor>
212 inline Dereference<Functor> makeDereference(const Functor &functor)
214 return Dereference<Functor>(functor);
217 typedef Face *FacePointer;
218 const FacePointer c_nullFacePointer = 0;
220 template<typename Predicate>
221 Face *Brush_findIf(const Brush &brush, const Predicate &predicate)
223 Brush::const_iterator i = std::find_if(brush.begin(), brush.end(), makeDereference(predicate));
224 return i == brush.end() ? c_nullFacePointer
225 : *i; // uses c_nullFacePointer instead of 0 because otherwise gcc 4.1 attempts conversion to int
228 template<typename Caller>
229 class BindArguments1 {
230 typedef get_argument<Caller, 1> FirstBound;
231 FirstBound firstBound;
233 BindArguments1(FirstBound firstBound)
234 : firstBound(firstBound)
238 get_result_type<Caller> operator()(get_argument<Caller, 0> firstArgument) const
240 return Caller::call(firstArgument, firstBound);
244 template<typename Caller>
245 class BindArguments2 {
246 typedef get_argument<Caller, 1> FirstBound;
247 typedef get_argument<Caller, 2> SecondBound;
248 FirstBound firstBound;
249 SecondBound secondBound;
251 BindArguments2(FirstBound firstBound, SecondBound secondBound)
252 : firstBound(firstBound), secondBound(secondBound)
256 get_result_type<Caller> operator()(get_argument<Caller, 0> firstArgument) const
258 return Caller::call(firstArgument, firstBound, secondBound);
262 template<typename Caller, typename FirstBound, typename SecondBound>
263 BindArguments2<Caller> bindArguments(const Caller &caller, FirstBound firstBound, SecondBound secondBound)
265 return BindArguments2<Caller>(firstBound, secondBound);
268 inline bool Face_testPlane(const Face &face, const Plane3 &plane, bool flipped)
270 return face.contributes() && !Winding_TestPlane(face.getWinding(), plane, flipped);
273 typedef Function<bool(const Face &, const Plane3 &, bool), Face_testPlane> FaceTestPlane;
276 /// \brief Returns true if
277 /// \li !flipped && brush is BACK or ON
278 /// \li flipped && brush is FRONT or ON
279 bool Brush_testPlane(const Brush &brush, const Plane3 &plane, bool flipped)
281 brush.evaluateBRep();
283 for (Brush::const_iterator i(brush.begin()); i != brush.end(); ++i) {
284 if (Face_testPlane(*(*i), plane, flipped)) {
290 return Brush_findIf( brush, bindArguments( FaceTestPlane(), makeReference( plane ), flipped ) ) == 0;
294 brushsplit_t Brush_classifyPlane(const Brush &brush, const Plane3 &plane)
296 brush.evaluateBRep();
298 for (Brush::const_iterator i(brush.begin()); i != brush.end(); ++i) {
299 if ((*i)->contributes()) {
300 split += Winding_ClassifyPlane((*i)->getWinding(), plane);
306 bool Brush_subtract(const Brush &brush, const Brush &other, brush_vector_t &ret_fragments)
308 if (aabb_intersects_aabb(brush.localAABB(), other.localAABB())) {
309 brush_vector_t fragments;
310 fragments.reserve(other.size());
313 for (Brush::const_iterator i(other.begin()); i != other.end(); ++i) {
314 if ((*i)->contributes()) {
315 brushsplit_t split = Brush_classifyPlane(back, (*i)->plane3());
316 if (split.counts[ePlaneFront] != 0
317 && split.counts[ePlaneBack] != 0) {
318 fragments.push_back(new Brush(back));
319 Face *newFace = fragments.back()->addFace(*(*i));
321 newFace->flipWinding();
324 } else if (split.counts[ePlaneBack] == 0) {
325 for (brush_vector_t::iterator i = fragments.begin(); i != fragments.end(); ++i) {
332 ret_fragments.insert(ret_fragments.end(), fragments.begin(), fragments.end());
338 class SubtractBrushesFromUnselected : public scene::Graph::Walker {
339 const brush_vector_t &m_brushlist;
340 std::size_t &m_before;
341 std::size_t &m_after;
343 SubtractBrushesFromUnselected(const brush_vector_t &brushlist, std::size_t &before, std::size_t &after)
344 : m_brushlist(brushlist), m_before(before), m_after(after)
348 bool pre(const scene::Path &path, scene::Instance &instance) const
353 void post(const scene::Path &path, scene::Instance &instance) const
355 if (path.top().get().visible()) {
356 Brush *brush = Node_getBrush(path.top());
358 && !Instance_getSelectable(instance)->isSelected()) {
359 brush_vector_t buffer[2];
361 Brush *original = new Brush(*brush);
362 buffer[static_cast<std::size_t>( swap )].push_back(original);
365 for (brush_vector_t::const_iterator i(m_brushlist.begin()); i != m_brushlist.end(); ++i) {
366 for (brush_vector_t::iterator j(buffer[static_cast<std::size_t>( swap )].begin());
367 j != buffer[static_cast<std::size_t>( swap )].end(); ++j) {
368 if (Brush_subtract(*(*j), *(*i), buffer[static_cast<std::size_t>( !swap )])) {
371 buffer[static_cast<std::size_t>( !swap )].push_back((*j));
374 buffer[static_cast<std::size_t>( swap )].clear();
379 brush_vector_t &out = buffer[static_cast<std::size_t>( swap )];
381 if (out.size() == 1 && out.back() == original) {
385 for (brush_vector_t::const_iterator i = out.begin(); i != out.end(); ++i) {
387 (*i)->removeEmptyFaces();
388 if (!(*i)->empty()) {
389 NodeSmartReference node((new BrushNode())->node());
390 Node_getBrush(node)->copy(*(*i));
392 Node_getTraversable(path.parent())->insert(node);
397 Path_deleteTop(path);
406 brush_vector_t selected_brushes;
407 GlobalSceneGraph().traverse(BrushGatherSelected(selected_brushes));
409 if (selected_brushes.empty()) {
410 globalOutputStream() << "CSG Subtract: No brushes selected.\n";
412 globalOutputStream() << "CSG Subtract: Subtracting " << Unsigned(selected_brushes.size()) << " brushes.\n";
414 UndoableCommand undo("brushSubtract");
416 // subtract selected from unselected
417 std::size_t before = 0;
418 std::size_t after = 0;
419 GlobalSceneGraph().traverse(SubtractBrushesFromUnselected(selected_brushes, before, after));
420 globalOutputStream() << "CSG Subtract: Result: "
421 << Unsigned(after) << " fragment" << (after == 1 ? "" : "s")
422 << " from " << Unsigned(before) << " brush" << (before == 1 ? "" : "es") << ".\n";
428 class BrushSplitByPlaneSelected : public scene::Graph::Walker {
432 const char *m_shader;
433 const TextureProjection &m_projection;
436 BrushSplitByPlaneSelected(const Vector3 &p0, const Vector3 &p1, const Vector3 &p2, const char *shader,
437 const TextureProjection &projection, EBrushSplit split)
438 : m_p0(p0), m_p1(p1), m_p2(p2), m_shader(shader), m_projection(projection), m_split(split)
442 bool pre(const scene::Path &path, scene::Instance &instance) const
447 void post(const scene::Path &path, scene::Instance &instance) const
449 if (path.top().get().visible()) {
450 Brush *brush = Node_getBrush(path.top());
452 && Instance_getSelectable(instance)->isSelected()) {
453 Plane3 plane(plane3_for_points(m_p0, m_p1, m_p2));
454 if (plane3_valid(plane)) {
455 brushsplit_t split = Brush_classifyPlane(*brush, m_split == eFront ? plane3_flipped(plane) : plane);
456 if (split.counts[ePlaneBack] && split.counts[ePlaneFront]) {
457 // the plane intersects this brush
458 if (m_split == eFrontAndBack) {
459 NodeSmartReference node((new BrushNode())->node());
460 Brush *fragment = Node_getBrush(node);
461 fragment->copy(*brush);
462 Face *newFace = fragment->addPlane(m_p0, m_p1, m_p2, m_shader, m_projection);
463 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) {
479 newFace->flipWinding();
481 brush->removeEmptyFaces();
482 ASSERT_MESSAGE(!brush->empty(), "brush left with no faces after split");
484 // the plane does not intersect this brush
485 if (m_split != eFrontAndBack && split.counts[ePlaneBack] != 0) {
486 // the brush is "behind" the plane
487 Path_deleteTop(path);
495 void Scene_BrushSplitByPlane(scene::Graph &graph, const Vector3 &p0, const Vector3 &p1, const Vector3 &p2,
496 const char *shader, EBrushSplit split)
498 TextureProjection projection;
499 TexDef_Construct_Default(projection);
500 graph.traverse(BrushSplitByPlaneSelected(p0, p1, p2, shader, projection, split));
505 class BrushInstanceSetClipPlane : public scene::Graph::Walker {
508 BrushInstanceSetClipPlane(const Plane3 &plane)
513 bool pre(const scene::Path &path, scene::Instance &instance) const
515 BrushInstance *brush = Instance_getBrush(instance);
517 && path.top().get().visible()
518 && brush->isSelected()) {
519 BrushInstance &brushInstance = *brush;
520 brushInstance.setClipPlane(m_plane);
526 void Scene_BrushSetClipPlane(scene::Graph &graph, const Plane3 &plane)
528 graph.traverse(BrushInstanceSetClipPlane(plane));
536 bool Brush_merge(Brush &brush, const brush_vector_t &in, bool onlyshape)
538 // gather potential outer faces
541 typedef std::vector<const Face *> Faces;
543 for (brush_vector_t::const_iterator i(in.begin()); i != in.end(); ++i) {
544 (*i)->evaluateBRep();
545 for (Brush::const_iterator j((*i)->begin()); j != (*i)->end(); ++j) {
546 if (!(*j)->contributes()) {
550 const Face &face1 = *(*j);
553 // test faces of all input brushes
554 //!\todo SPEEDUP: Flag already-skip faces and only test brushes from i+1 upwards.
555 for (brush_vector_t::const_iterator k(in.begin()); !skip && k != in.end(); ++k) {
556 if (k != i) { // don't test a brush against itself
557 for (Brush::const_iterator l((*k)->begin()); !skip && l != (*k)->end(); ++l) {
558 const Face &face2 = *(*l);
560 // face opposes another face
561 if (plane3_opposing(face1.plane3(), face2.plane3())) {
562 // skip opposing planes
570 // check faces already stored
571 for (Faces::const_iterator m = faces.begin(); !skip && m != faces.end(); ++m) {
572 const Face &face2 = *(*m);
574 // face equals another face
575 if (plane3_equal(face1.plane3(), face2.plane3())) {
576 //if the texture/shader references should be the same but are not
577 if (!onlyshape && !shader_equal(face1.getShader().getShader(), face2.getShader().getShader())) {
580 // skip duplicate planes
585 // face1 plane intersects face2 winding or vice versa
586 if (Winding_PlanesConcave(face1.getWinding(), face2.getWinding(), face1.plane3(), face2.plane3())) {
587 // result would not be convex
593 faces.push_back(&face1);
597 for (Faces::const_iterator i = faces.begin(); i != faces.end(); ++i) {
598 if (!brush.addFace(*(*i))) {
599 // result would have too many sides
605 brush.removeEmptyFaces();
612 brush_vector_t selected_brushes;
615 GlobalSceneGraph().traverse(BrushGatherSelected(selected_brushes));
617 if (selected_brushes.empty()) {
618 globalOutputStream() << "CSG Merge: No brushes selected.\n";
622 if (selected_brushes.size() < 2) {
623 globalOutputStream() << "CSG Merge: At least two brushes have to be selected.\n";
627 globalOutputStream() << "CSG Merge: Merging " << Unsigned(selected_brushes.size()) << " brushes.\n";
629 UndoableCommand undo("brushMerge");
631 scene::Path merged_path = GlobalSelectionSystem().ultimateSelected().path();
633 NodeSmartReference node((new BrushNode())->node());
634 Brush *brush = Node_getBrush(node);
635 // if the new brush would not be convex
636 if (!Brush_merge(*brush, selected_brushes, true)) {
637 globalOutputStream() << "CSG Merge: Failed - result would not be convex.\n";
639 ASSERT_MESSAGE(!brush->empty(), "brush left with no faces after merge");
641 // free the original brushes
642 GlobalSceneGraph().traverse(BrushDeleteSelected());
645 Node_getTraversable(merged_path.top())->insert(node);
646 merged_path.push(makeReference(node.get()));
648 selectPath(merged_path, true);
650 globalOutputStream() << "CSG Merge: Succeeded.\n";