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 Brush_makeHollow(const Brush &brush, brush_vector_t &out, float offset)
48 Brush_forEachFace(brush, [&](Face &face) {
49 Face_makeBrush(face, brush, out, offset);
53 class BrushHollowSelectedWalker : public scene::Graph::Walker {
56 BrushHollowSelectedWalker(float offset)
61 bool pre(const scene::Path &path, scene::Instance &instance) const
63 if (path.top().get().visible()) {
64 Brush *brush = Node_getBrush(path.top());
66 && Instance_getSelectable(instance)->isSelected()
69 Brush_makeHollow(*brush, out, m_offset);
70 for (brush_vector_t::const_iterator i = out.begin(); i != out.end(); ++i) {
71 (*i)->removeEmptyFaces();
72 NodeSmartReference node((new BrushNode())->node());
73 Node_getBrush(node)->copy(*(*i));
75 Node_getTraversable(path.parent())->insert(node);
83 typedef std::list<Brush *> brushlist_t;
85 class BrushGatherSelected : public scene::Graph::Walker {
86 brush_vector_t &m_brushlist;
88 BrushGatherSelected(brush_vector_t &brushlist)
89 : m_brushlist(brushlist)
93 bool pre(const scene::Path &path, scene::Instance &instance) const
95 if (path.top().get().visible()) {
96 Brush *brush = Node_getBrush(path.top());
98 && Instance_getSelectable(instance)->isSelected()) {
99 m_brushlist.push_back(brush);
106 class BrushDeleteSelected : public scene::Graph::Walker {
108 bool pre(const scene::Path &path, scene::Instance &instance) const
113 void post(const scene::Path &path, scene::Instance &instance) const
115 if (path.top().get().visible()) {
116 Brush *brush = Node_getBrush(path.top());
118 && Instance_getSelectable(instance)->isSelected()
119 && path.size() > 1) {
120 Path_deleteTop(path);
126 void Scene_BrushMakeHollow_Selected(scene::Graph &graph)
128 GlobalSceneGraph().traverse(BrushHollowSelectedWalker(GetGridSize()));
129 GlobalSceneGraph().traverse(BrushDeleteSelected());
138 void CSG_MakeHollow(void)
140 UndoableCommand undo("brushHollow");
142 Scene_BrushMakeHollow_Selected(GlobalSceneGraph());
147 template<typename Type>
148 class RemoveReference {
153 template<typename Type>
154 class RemoveReference<Type &> {
159 template<typename Functor>
161 const Functor &functor;
163 Dereference(const Functor &functor) : functor(functor)
167 get_result_type<Functor> operator()(typename RemoveReference<get_argument<Functor, 0>>::type *firstArgument) const
169 return functor(*firstArgument);
173 template<typename Functor>
174 inline Dereference<Functor> makeDereference(const Functor &functor)
176 return Dereference<Functor>(functor);
179 typedef Face *FacePointer;
180 const FacePointer c_nullFacePointer = 0;
182 template<typename Predicate>
183 Face *Brush_findIf(const Brush &brush, const Predicate &predicate)
185 Brush::const_iterator i = std::find_if(brush.begin(), brush.end(), makeDereference(predicate));
186 return i == brush.end() ? c_nullFacePointer
187 : *i; // uses c_nullFacePointer instead of 0 because otherwise gcc 4.1 attempts conversion to int
190 template<typename Caller>
191 class BindArguments1 {
192 typedef get_argument<Caller, 1> FirstBound;
193 FirstBound firstBound;
195 BindArguments1(FirstBound firstBound)
196 : firstBound(firstBound)
200 get_result_type<Caller> operator()(get_argument<Caller, 0> firstArgument) const
202 return Caller::call(firstArgument, firstBound);
206 template<typename Caller>
207 class BindArguments2 {
208 typedef get_argument<Caller, 1> FirstBound;
209 typedef get_argument<Caller, 2> SecondBound;
210 FirstBound firstBound;
211 SecondBound secondBound;
213 BindArguments2(FirstBound firstBound, SecondBound secondBound)
214 : firstBound(firstBound), secondBound(secondBound)
218 get_result_type<Caller> operator()(get_argument<Caller, 0> firstArgument) const
220 return Caller::call(firstArgument, firstBound, secondBound);
224 template<typename Caller, typename FirstBound, typename SecondBound>
225 BindArguments2<Caller> bindArguments(const Caller &caller, FirstBound firstBound, SecondBound secondBound)
227 return BindArguments2<Caller>(firstBound, secondBound);
230 inline bool Face_testPlane(const Face &face, const Plane3 &plane, bool flipped)
232 return face.contributes() && !Winding_TestPlane(face.getWinding(), plane, flipped);
235 typedef Function<bool(const Face &, const Plane3 &, bool), Face_testPlane> FaceTestPlane;
238 /// \brief Returns true if
239 /// \li !flipped && brush is BACK or ON
240 /// \li flipped && brush is FRONT or ON
241 bool Brush_testPlane(const Brush &brush, const Plane3 &plane, bool flipped)
243 brush.evaluateBRep();
245 for (Brush::const_iterator i(brush.begin()); i != brush.end(); ++i) {
246 if (Face_testPlane(*(*i), plane, flipped)) {
252 return Brush_findIf( brush, bindArguments( FaceTestPlane(), makeReference( plane ), flipped ) ) == 0;
256 brushsplit_t Brush_classifyPlane(const Brush &brush, const Plane3 &plane)
258 brush.evaluateBRep();
260 for (Brush::const_iterator i(brush.begin()); i != brush.end(); ++i) {
261 if ((*i)->contributes()) {
262 split += Winding_ClassifyPlane((*i)->getWinding(), plane);
268 bool Brush_subtract(const Brush &brush, const Brush &other, brush_vector_t &ret_fragments)
270 if (aabb_intersects_aabb(brush.localAABB(), other.localAABB())) {
271 brush_vector_t fragments;
272 fragments.reserve(other.size());
275 for (Brush::const_iterator i(other.begin()); i != other.end(); ++i) {
276 if ((*i)->contributes()) {
277 brushsplit_t split = Brush_classifyPlane(back, (*i)->plane3());
278 if (split.counts[ePlaneFront] != 0
279 && split.counts[ePlaneBack] != 0) {
280 fragments.push_back(new Brush(back));
281 Face *newFace = fragments.back()->addFace(*(*i));
283 newFace->flipWinding();
286 } else if (split.counts[ePlaneBack] == 0) {
287 for (brush_vector_t::iterator i = fragments.begin(); i != fragments.end(); ++i) {
294 ret_fragments.insert(ret_fragments.end(), fragments.begin(), fragments.end());
300 class SubtractBrushesFromUnselected : public scene::Graph::Walker {
301 const brush_vector_t &m_brushlist;
302 std::size_t &m_before;
303 std::size_t &m_after;
305 SubtractBrushesFromUnselected(const brush_vector_t &brushlist, std::size_t &before, std::size_t &after)
306 : m_brushlist(brushlist), m_before(before), m_after(after)
310 bool pre(const scene::Path &path, scene::Instance &instance) const
315 void post(const scene::Path &path, scene::Instance &instance) const
317 if (path.top().get().visible()) {
318 Brush *brush = Node_getBrush(path.top());
320 && !Instance_getSelectable(instance)->isSelected()) {
321 brush_vector_t buffer[2];
323 Brush *original = new Brush(*brush);
324 buffer[static_cast<std::size_t>( swap )].push_back(original);
327 for (brush_vector_t::const_iterator i(m_brushlist.begin()); i != m_brushlist.end(); ++i) {
328 for (brush_vector_t::iterator j(buffer[static_cast<std::size_t>( swap )].begin());
329 j != buffer[static_cast<std::size_t>( swap )].end(); ++j) {
330 if (Brush_subtract(*(*j), *(*i), buffer[static_cast<std::size_t>( !swap )])) {
333 buffer[static_cast<std::size_t>( !swap )].push_back((*j));
336 buffer[static_cast<std::size_t>( swap )].clear();
341 brush_vector_t &out = buffer[static_cast<std::size_t>( swap )];
343 if (out.size() == 1 && out.back() == original) {
347 for (brush_vector_t::const_iterator i = out.begin(); i != out.end(); ++i) {
349 (*i)->removeEmptyFaces();
350 if (!(*i)->empty()) {
351 NodeSmartReference node((new BrushNode())->node());
352 Node_getBrush(node)->copy(*(*i));
354 Node_getTraversable(path.parent())->insert(node);
359 Path_deleteTop(path);
368 brush_vector_t selected_brushes;
369 GlobalSceneGraph().traverse(BrushGatherSelected(selected_brushes));
371 if (selected_brushes.empty()) {
372 globalOutputStream() << "CSG Subtract: No brushes selected.\n";
374 globalOutputStream() << "CSG Subtract: Subtracting " << Unsigned(selected_brushes.size()) << " brushes.\n";
376 UndoableCommand undo("brushSubtract");
378 // subtract selected from unselected
379 std::size_t before = 0;
380 std::size_t after = 0;
381 GlobalSceneGraph().traverse(SubtractBrushesFromUnselected(selected_brushes, before, after));
382 globalOutputStream() << "CSG Subtract: Result: "
383 << Unsigned(after) << " fragment" << (after == 1 ? "" : "s")
384 << " from " << Unsigned(before) << " brush" << (before == 1 ? "" : "es") << ".\n";
390 class BrushSplitByPlaneSelected : public scene::Graph::Walker {
394 const char *m_shader;
395 const TextureProjection &m_projection;
398 BrushSplitByPlaneSelected(const Vector3 &p0, const Vector3 &p1, const Vector3 &p2, const char *shader,
399 const TextureProjection &projection, EBrushSplit split)
400 : m_p0(p0), m_p1(p1), m_p2(p2), m_shader(shader), m_projection(projection), m_split(split)
404 bool pre(const scene::Path &path, scene::Instance &instance) const
409 void post(const scene::Path &path, scene::Instance &instance) const
411 if (path.top().get().visible()) {
412 Brush *brush = Node_getBrush(path.top());
414 && Instance_getSelectable(instance)->isSelected()) {
415 Plane3 plane(plane3_for_points(m_p0, m_p1, m_p2));
416 if (plane3_valid(plane)) {
417 brushsplit_t split = Brush_classifyPlane(*brush, m_split == eFront ? plane3_flipped(plane) : plane);
418 if (split.counts[ePlaneBack] && split.counts[ePlaneFront]) {
419 // the plane intersects this brush
420 if (m_split == eFrontAndBack) {
421 NodeSmartReference node((new BrushNode())->node());
422 Brush *fragment = Node_getBrush(node);
423 fragment->copy(*brush);
424 Face *newFace = fragment->addPlane(m_p0, m_p1, m_p2, m_shader, m_projection);
425 if (newFace != 0 && m_split != eFront) {
426 newFace->flipWinding();
428 fragment->removeEmptyFaces();
429 ASSERT_MESSAGE(!fragment->empty(), "brush left with no faces after split");
431 Node_getTraversable(path.parent())->insert(node);
433 scene::Path fragmentPath = path;
434 fragmentPath.top() = makeReference(node.get());
435 selectPath(fragmentPath, true);
439 Face *newFace = brush->addPlane(m_p0, m_p1, m_p2, m_shader, m_projection);
440 if (newFace != 0 && m_split == eFront) {
441 newFace->flipWinding();
443 brush->removeEmptyFaces();
444 ASSERT_MESSAGE(!brush->empty(), "brush left with no faces after split");
446 // the plane does not intersect this brush
447 if (m_split != eFrontAndBack && split.counts[ePlaneBack] != 0) {
448 // the brush is "behind" the plane
449 Path_deleteTop(path);
457 void Scene_BrushSplitByPlane(scene::Graph &graph, const Vector3 &p0, const Vector3 &p1, const Vector3 &p2,
458 const char *shader, EBrushSplit split)
460 TextureProjection projection;
461 TexDef_Construct_Default(projection);
462 graph.traverse(BrushSplitByPlaneSelected(p0, p1, p2, shader, projection, split));
467 class BrushInstanceSetClipPlane : public scene::Graph::Walker {
470 BrushInstanceSetClipPlane(const Plane3 &plane)
475 bool pre(const scene::Path &path, scene::Instance &instance) const
477 BrushInstance *brush = Instance_getBrush(instance);
479 && path.top().get().visible()
480 && brush->isSelected()) {
481 BrushInstance &brushInstance = *brush;
482 brushInstance.setClipPlane(m_plane);
488 void Scene_BrushSetClipPlane(scene::Graph &graph, const Plane3 &plane)
490 graph.traverse(BrushInstanceSetClipPlane(plane));
498 bool Brush_merge(Brush &brush, const brush_vector_t &in, bool onlyshape)
500 // gather potential outer faces
503 typedef std::vector<const Face *> Faces;
505 for (brush_vector_t::const_iterator i(in.begin()); i != in.end(); ++i) {
506 (*i)->evaluateBRep();
507 for (Brush::const_iterator j((*i)->begin()); j != (*i)->end(); ++j) {
508 if (!(*j)->contributes()) {
512 const Face &face1 = *(*j);
515 // test faces of all input brushes
516 //!\todo SPEEDUP: Flag already-skip faces and only test brushes from i+1 upwards.
517 for (brush_vector_t::const_iterator k(in.begin()); !skip && k != in.end(); ++k) {
518 if (k != i) { // don't test a brush against itself
519 for (Brush::const_iterator l((*k)->begin()); !skip && l != (*k)->end(); ++l) {
520 const Face &face2 = *(*l);
522 // face opposes another face
523 if (plane3_opposing(face1.plane3(), face2.plane3())) {
524 // skip opposing planes
532 // check faces already stored
533 for (Faces::const_iterator m = faces.begin(); !skip && m != faces.end(); ++m) {
534 const Face &face2 = *(*m);
536 // face equals another face
537 if (plane3_equal(face1.plane3(), face2.plane3())) {
538 //if the texture/shader references should be the same but are not
539 if (!onlyshape && !shader_equal(face1.getShader().getShader(), face2.getShader().getShader())) {
542 // skip duplicate planes
547 // face1 plane intersects face2 winding or vice versa
548 if (Winding_PlanesConcave(face1.getWinding(), face2.getWinding(), face1.plane3(), face2.plane3())) {
549 // result would not be convex
555 faces.push_back(&face1);
559 for (Faces::const_iterator i = faces.begin(); i != faces.end(); ++i) {
560 if (!brush.addFace(*(*i))) {
561 // result would have too many sides
567 brush.removeEmptyFaces();
574 brush_vector_t selected_brushes;
577 GlobalSceneGraph().traverse(BrushGatherSelected(selected_brushes));
579 if (selected_brushes.empty()) {
580 globalOutputStream() << "CSG Merge: No brushes selected.\n";
584 if (selected_brushes.size() < 2) {
585 globalOutputStream() << "CSG Merge: At least two brushes have to be selected.\n";
589 globalOutputStream() << "CSG Merge: Merging " << Unsigned(selected_brushes.size()) << " brushes.\n";
591 UndoableCommand undo("brushMerge");
593 scene::Path merged_path = GlobalSelectionSystem().ultimateSelected().path();
595 NodeSmartReference node((new BrushNode())->node());
596 Brush *brush = Node_getBrush(node);
597 // if the new brush would not be convex
598 if (!Brush_merge(*brush, selected_brushes, true)) {
599 globalOutputStream() << "CSG Merge: Failed - result would not be convex.\n";
601 ASSERT_MESSAGE(!brush->empty(), "brush left with no faces after merge");
603 // free the original brushes
604 GlobalSceneGraph().traverse(BrushDeleteSelected());
607 Node_getTraversable(merged_path.top())->insert(node);
608 merged_path.push(makeReference(node.get()));
610 selectPath(merged_path, true);
612 globalOutputStream() << "CSG Merge: Succeeded.\n";