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 ){
34 if ( face.contributes() ) {
35 out.push_back( new Brush( brush ) );
36 std::shared_ptr<Face> newFace = out.back()->addFace( face );
38 newFace->flipWinding();
39 newFace->getPlane().offset( offset );
40 newFace->planeChanged();
45 void Face_makeRoom( Face &face, const Brush &brush, brush_vector_t &out, float offset ){
46 if ( face.contributes() ) {
47 face.getPlane().offset( offset );
48 out.push_back( new Brush( brush ) );
49 face.getPlane().offset( -offset );
50 std::shared_ptr<Face> newFace = out.back()->addFace( face );
52 newFace->flipWinding();
53 newFace->planeChanged();
58 void Brush_makeHollow( const Brush &brush, brush_vector_t &out, float offset ){
59 Brush_forEachFace( brush, [&]( Face &face ) {
60 Face_makeBrush( face, brush, out, offset );
64 void Brush_makeRoom( const Brush &brush, brush_vector_t &out, float offset ){
65 Brush_forEachFace( brush, [&]( Face &face ) {
66 Face_makeRoom( face, brush, out, offset );
70 class BrushHollowSelectedWalker : public scene::Graph::Walker
75 BrushHollowSelectedWalker( float offset, bool makeRoom )
76 : m_offset( offset ), m_makeRoom( makeRoom ){
79 bool pre( const scene::Path& path, scene::Instance& instance ) const {
80 if ( path.top().get().visible() ) {
81 Brush* brush = Node_getBrush( path.top() );
83 && Instance_getSelectable( instance )->isSelected()
84 && path.size() > 1 ) {
88 Brush_makeRoom(* brush, out, m_offset );
92 Brush_makeHollow(* brush, out, m_offset );
95 for ( brush_vector_t::const_iterator i = out.begin(); i != out.end(); ++i )
97 ( *i )->removeEmptyFaces();
98 NodeSmartReference node( ( new BrushNode() )->node() );
99 Node_getBrush( node )->copy( *( *i ) );
101 Node_getTraversable( path.parent() )->insert( node );
109 typedef std::list<Brush*> brushlist_t;
111 class BrushGatherSelected : public scene::Graph::Walker
113 brush_vector_t& m_brushlist;
115 BrushGatherSelected( brush_vector_t& brushlist )
116 : m_brushlist( brushlist ){
119 bool pre( const scene::Path& path, scene::Instance& instance ) const {
120 if ( path.top().get().visible() ) {
121 Brush* brush = Node_getBrush( path.top() );
123 && Instance_getSelectable( instance )->isSelected() ) {
124 m_brushlist.push_back( brush );
131 class BrushDeleteSelected : public scene::Graph::Walker
134 bool pre( const scene::Path& path, scene::Instance& instance ) const {
137 void post( const scene::Path& path, scene::Instance& instance ) const {
138 if ( path.top().get().visible() ) {
139 Brush* brush = Node_getBrush( path.top() );
141 && Instance_getSelectable( instance )->isSelected()
142 && path.size() > 1 ) {
143 Path_deleteTop( path );
149 void Scene_BrushMakeHollow_Selected( scene::Graph& graph, bool makeRoom ){
150 GlobalSceneGraph().traverse( BrushHollowSelectedWalker( GetGridSize(), makeRoom ) );
151 GlobalSceneGraph().traverse( BrushDeleteSelected() );
160 void CSG_MakeHollow( void ){
161 UndoableCommand undo( "brushHollow" );
163 Scene_BrushMakeHollow_Selected( GlobalSceneGraph(), false );
168 void CSG_MakeRoom( void ){
169 UndoableCommand undo( "brushRoom" );
171 Scene_BrushMakeHollow_Selected( GlobalSceneGraph(), true );
176 template<typename Type>
177 class RemoveReference
183 template<typename Type>
184 class RemoveReference<Type&>
190 template<typename Functor>
193 const Functor& functor;
195 Dereference( const Functor& functor ) : functor( functor ){
197 get_result_type<Functor> operator()( typename RemoveReference<get_argument<Functor, 0>>::type *firstArgument ) const {
198 return functor( *firstArgument );
202 template<typename Functor>
203 inline Dereference<Functor> makeDereference( const Functor& functor ){
204 return Dereference<Functor>( functor );
207 template<typename Caller>
210 typedef get_argument<Caller, 1> FirstBound;
211 FirstBound firstBound;
213 BindArguments1( FirstBound firstBound )
214 : firstBound( firstBound ){
217 get_result_type<Caller> operator()( get_argument<Caller, 0> firstArgument ) const {
218 return Caller::call( firstArgument, firstBound );
222 template<typename Caller>
225 typedef get_argument<Caller, 1> FirstBound;
226 typedef get_argument<Caller, 2> SecondBound;
227 FirstBound firstBound;
228 SecondBound secondBound;
230 BindArguments2( FirstBound firstBound, SecondBound secondBound )
231 : firstBound( firstBound ), secondBound( secondBound ){
234 get_result_type<Caller> operator()( get_argument<Caller, 0> firstArgument ) const {
235 return Caller::call( firstArgument, firstBound, secondBound );
239 template<typename Caller, typename FirstBound, typename SecondBound>
240 BindArguments2<Caller> bindArguments( const Caller& caller, FirstBound firstBound, SecondBound secondBound ){
241 return BindArguments2<Caller>( firstBound, secondBound );
244 inline bool Face_testPlane( const Face& face, const Plane3& plane, bool flipped ){
245 return face.contributes() && !Winding_TestPlane( face.getWinding(), plane, flipped );
248 typedef Function<bool ( const Face &, const Plane3 &, 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 ){
255 brush.evaluateBRep();
256 for ( Brush::const_iterator i( brush.begin() ); i != brush.end(); ++i )
258 if ( Face_testPlane( *( *i ), plane, flipped ) ) {
265 brushsplit_t Brush_classifyPlane( const Brush& brush, const Plane3& plane ){
266 brush.evaluateBRep();
268 for ( Brush::const_iterator i( brush.begin() ); i != brush.end(); ++i )
270 if ( ( *i )->contributes() ) {
271 split += Winding_ClassifyPlane( ( *i )->getWinding(), plane );
277 bool Brush_subtract( const Brush& brush, const Brush& other, brush_vector_t& ret_fragments ){
278 if ( aabb_intersects_aabb( brush.localAABB(), other.localAABB() ) ) {
279 brush_vector_t fragments;
280 fragments.reserve( other.size() );
283 for ( const std::shared_ptr<Face>& b : other )
285 if ( b->contributes() ) {
286 brushsplit_t split = Brush_classifyPlane( back, b->plane3() );
287 if ( split.counts[ePlaneFront] != 0
288 && split.counts[ePlaneBack] != 0 ) {
289 fragments.push_back( new Brush( back ) );
290 std::shared_ptr<Face> newFace = fragments.back()->addFace( *b );
291 if ( newFace != nullptr ) {
292 newFace->flipWinding();
296 else if ( split.counts[ePlaneBack] == 0 ) {
297 for ( Brush *i : fragments ) {
305 ret_fragments.insert( ret_fragments.end(), fragments.begin(), fragments.end() );
311 class SubtractBrushesFromUnselected : public scene::Graph::Walker
313 const brush_vector_t& m_brushlist;
314 std::size_t& m_before;
315 std::size_t& m_after;
317 SubtractBrushesFromUnselected( const brush_vector_t& brushlist, std::size_t& before, std::size_t& after )
318 : m_brushlist( brushlist ), m_before( before ), m_after( after ){
321 bool pre( const scene::Path& path, scene::Instance& instance ) const {
325 void post( const scene::Path& path, scene::Instance& instance ) const {
326 if ( path.top().get().visible() ) {
327 Brush* brush = Node_getBrush( path.top() );
329 && !Instance_getSelectable( instance )->isSelected() ) {
330 brush_vector_t buffer[2];
332 Brush* original = new Brush( *brush );
333 buffer[static_cast<std::size_t>( swap )].push_back( original );
336 for ( brush_vector_t::const_iterator i( m_brushlist.begin() ); i != m_brushlist.end(); ++i )
338 for ( brush_vector_t::iterator j( buffer[static_cast<std::size_t>( swap )].begin() ); j != buffer[static_cast<std::size_t>( swap )].end(); ++j )
340 if ( Brush_subtract( *( *j ), *( *i ), buffer[static_cast<std::size_t>( !swap )] ) ) {
345 buffer[static_cast<std::size_t>( !swap )].push_back( ( *j ) );
348 buffer[static_cast<std::size_t>( swap )].clear();
353 brush_vector_t& out = buffer[static_cast<std::size_t>( swap )];
355 if ( out.size() == 1 && out.back() == original ) {
361 for ( Brush *b : out ) {
363 b->removeEmptyFaces();
365 NodeSmartReference node( ( new BrushNode() )->node() );
366 Node_getBrush( node )->copy( *b );
367 Node_getTraversable( path.parent() )->insert( node );
371 Path_deleteTop( path );
379 brush_vector_t selected_brushes;
380 GlobalSceneGraph().traverse( BrushGatherSelected( selected_brushes ) );
382 if ( selected_brushes.empty() ) {
383 globalOutputStream() << "CSG Subtract: No brushes selected.\n";
385 globalOutputStream() << "CSG Subtract: Subtracting " << Unsigned( selected_brushes.size() ) << " brushes.\n";
387 UndoableCommand undo( "brushSubtract" );
389 // subtract selected from unselected
390 std::size_t before = 0;
391 std::size_t after = 0;
392 GlobalSceneGraph().traverse( SubtractBrushesFromUnselected( selected_brushes, before, after ) );
393 globalOutputStream() << "CSG Subtract: Result: "
394 << Unsigned( after ) << " fragment" << ( after == 1 ? "" : "s" )
395 << " from " << Unsigned( before ) << " brush" << ( before == 1 ? "" : "es" ) << ".\n";
401 class BrushSplitByPlaneSelected : public scene::Graph::Walker
406 const char* m_shader;
407 const TextureProjection& m_projection;
410 BrushSplitByPlaneSelected( const Vector3& p0, const Vector3& p1, const Vector3& p2, const char* shader, const TextureProjection& projection, EBrushSplit split )
411 : m_p0( p0 ), m_p1( p1 ), m_p2( p2 ), m_shader( shader ), m_projection( projection ), m_split( split ){
414 bool pre( const scene::Path& path, scene::Instance& instance ) const {
418 void post( const scene::Path& path, scene::Instance& instance ) const {
419 if ( !path.top().get().visible() ) {
423 Brush* brush = Node_getBrush( path.top() );
424 if ( brush == nullptr || !Instance_getSelectable( instance )->isSelected() ) {
428 Plane3 plane( plane3_for_points( m_p0, m_p1, m_p2 ) );
429 if ( !plane3_valid( plane ) ) {
433 brushsplit_t split = Brush_classifyPlane( *brush, m_split == eFront ? plane3_flipped( plane ) : plane );
434 if ( split.counts[ePlaneBack] && split.counts[ePlaneFront] ) {
435 // the plane intersects this brush
436 if ( m_split == eFrontAndBack ) {
437 NodeSmartReference node( ( new BrushNode() )->node() );
438 Brush* fragment = Node_getBrush( node );
439 fragment->copy( *brush );
440 std::shared_ptr<Face> newFace =
441 fragment->addPlane( m_p0, m_p1, m_p2, m_shader, m_projection );
442 if ( newFace != 0 && m_split != eFront ) {
443 newFace->flipWinding();
445 fragment->removeEmptyFaces();
446 ASSERT_MESSAGE( !fragment->empty(), "brush left with no faces after split" );
448 Node_getTraversable( path.parent() )->insert( node );
450 scene::Path fragmentPath = path;
451 fragmentPath.top() = makeReference( node.get() );
452 selectPath( fragmentPath, true );
456 std::shared_ptr<Face> newFace = brush->addPlane( m_p0, m_p1, m_p2, m_shader, m_projection );
457 if ( newFace != 0 && m_split == eFront ) {
458 newFace->flipWinding();
460 brush->removeEmptyFaces();
461 ASSERT_MESSAGE( !brush->empty(), "brush left with no faces after split" );
464 // the plane does not intersect this brush
465 if ( m_split != eFrontAndBack && split.counts[ePlaneBack] != 0 ) {
466 // the brush is "behind" the plane
467 Path_deleteTop( path );
472 void Scene_BrushSplitByPlane( scene::Graph& graph, const Vector3& p0, const Vector3& p1, const Vector3& p2, const char* shader, EBrushSplit split ){
473 TextureProjection projection;
474 TexDef_Construct_Default( projection );
475 graph.traverse( BrushSplitByPlaneSelected( p0, p1, p2, shader, projection, split ) );
480 class BrushInstanceSetClipPlane : public scene::Graph::Walker
484 BrushInstanceSetClipPlane( const Plane3& plane )
488 bool pre( const scene::Path& path, scene::Instance& instance ) const {
489 BrushInstance* brush = Instance_getBrush( instance );
491 && path.top().get().visible()
492 && brush->isSelected() ) {
493 BrushInstance& brushInstance = *brush;
494 brushInstance.setClipPlane( m_plane );
500 void Scene_BrushSetClipPlane( scene::Graph& graph, const Plane3& plane ){
501 graph.traverse( BrushInstanceSetClipPlane( plane ) );
509 bool Brush_merge( Brush& brush, const brush_vector_t& in, bool onlyshape ){
510 // gather potential outer faces
513 typedef std::vector<const Face*> Faces;
515 for ( brush_vector_t::const_iterator i( in.begin() ); i != in.end(); ++i )
517 ( *i )->evaluateBRep();
518 for ( Brush::const_iterator j( ( *i )->begin() ); j != ( *i )->end(); ++j )
520 if ( !( *j )->contributes() ) {
524 const Face& face1 = *( *j );
527 // test faces of all input brushes
528 //!\todo SPEEDUP: Flag already-skip faces and only test brushes from i+1 upwards.
529 for ( brush_vector_t::const_iterator k( in.begin() ); !skip && k != in.end(); ++k )
531 if ( k != i ) { // don't test a brush against itself
532 for ( Brush::const_iterator l( ( *k )->begin() ); !skip && l != ( *k )->end(); ++l )
534 const Face& face2 = *( *l );
536 // face opposes another face
537 if ( plane3_opposing( face1.plane3(), face2.plane3() ) ) {
538 // skip opposing planes
546 // check faces already stored
547 for ( Faces::const_iterator m = faces.begin(); !skip && m != faces.end(); ++m )
549 const Face& face2 = *( *m );
551 // face equals another face
552 if ( plane3_equal( face1.plane3(), face2.plane3() ) ) {
553 //if the texture/shader references should be the same but are not
554 if ( !onlyshape && !shader_equal( face1.getShader().getShader(), face2.getShader().getShader() ) ) {
557 // skip duplicate planes
562 // face1 plane intersects face2 winding or vice versa
563 if ( Winding_PlanesConcave( face1.getWinding(), face2.getWinding(), face1.plane3(), face2.plane3() ) ) {
564 // result would not be convex
570 faces.push_back( &face1 );
574 for ( Faces::const_iterator i = faces.begin(); i != faces.end(); ++i )
576 if ( !brush.addFace( *( *i ) ) ) {
577 // result would have too many sides
583 brush.removeEmptyFaces();
588 void CSG_Merge( void ){
589 brush_vector_t selected_brushes;
592 GlobalSceneGraph().traverse( BrushGatherSelected( selected_brushes ) );
594 if ( selected_brushes.empty() ) {
595 globalOutputStream() << "CSG Merge: No brushes selected.\n";
599 if ( selected_brushes.size() < 2 ) {
600 globalOutputStream() << "CSG Merge: At least two brushes have to be selected.\n";
604 globalOutputStream() << "CSG Merge: Merging " << Unsigned( selected_brushes.size() ) << " brushes.\n";
606 UndoableCommand undo( "brushMerge" );
608 scene::Path merged_path = GlobalSelectionSystem().ultimateSelected().path();
610 NodeSmartReference node( ( new BrushNode() )->node() );
611 Brush* brush = Node_getBrush( node );
612 // if the new brush would not be convex
613 if ( !Brush_merge( *brush, selected_brushes, true ) ) {
614 globalOutputStream() << "CSG Merge: Failed - result would not be convex.\n";
618 ASSERT_MESSAGE( !brush->empty(), "brush left with no faces after merge" );
620 // free the original brushes
621 GlobalSceneGraph().traverse( BrushDeleteSelected() );
624 Node_getTraversable( merged_path.top() )->insert( node );
625 merged_path.push( makeReference( node.get() ) );
627 selectPath( merged_path, true );
629 globalOutputStream() << "CSG Merge: Succeeded.\n";