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 Face* newFace = out.back()->addFace( face );
38 newFace->flipWinding();
39 newFace->getPlane().offset( offset );
40 newFace->planeChanged();
51 FaceMakeBrush( const Brush& brush, brush_vector_t& out, float offset )
52 : brush( brush ), out( out ), offset( offset ){
54 void operator()( Face& face ) const {
55 Face_makeBrush( face, brush, out, offset );
59 void Brush_makeHollow( const Brush& brush, brush_vector_t& out, float offset ){
60 Brush_forEachFace( brush, FaceMakeBrush( brush, out, offset ) );
63 class BrushHollowSelectedWalker : public scene::Graph::Walker
67 BrushHollowSelectedWalker( float offset )
70 bool pre( const scene::Path& path, scene::Instance& instance ) const {
71 if ( path.top().get().visible() ) {
72 Brush* brush = Node_getBrush( path.top() );
74 && Instance_getSelectable( instance )->isSelected()
75 && path.size() > 1 ) {
77 Brush_makeHollow( *brush, out, m_offset );
78 for ( brush_vector_t::const_iterator i = out.begin(); i != out.end(); ++i )
80 ( *i )->removeEmptyFaces();
81 NodeSmartReference node( ( new BrushNode() )->node() );
82 Node_getBrush( node )->copy( *( *i ) );
84 Node_getTraversable( path.parent() )->insert( node );
92 typedef std::list<Brush*> brushlist_t;
94 class BrushGatherSelected : public scene::Graph::Walker
96 brush_vector_t& m_brushlist;
98 BrushGatherSelected( brush_vector_t& brushlist )
99 : m_brushlist( brushlist ){
101 bool pre( const scene::Path& path, scene::Instance& instance ) const {
102 if ( path.top().get().visible() ) {
103 Brush* brush = Node_getBrush( path.top() );
105 && Instance_getSelectable( instance )->isSelected() ) {
106 m_brushlist.push_back( brush );
113 class BrushDeleteSelected : public scene::Graph::Walker
116 bool pre( const scene::Path& path, scene::Instance& instance ) const {
119 void post( 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 && path.size() > 1 ) {
125 Path_deleteTop( path );
131 void Scene_BrushMakeHollow_Selected( scene::Graph& graph ){
132 GlobalSceneGraph().traverse( BrushHollowSelectedWalker( GetGridSize() ) );
133 GlobalSceneGraph().traverse( BrushDeleteSelected() );
142 void CSG_MakeHollow( void ){
143 UndoableCommand undo( "brushHollow" );
145 Scene_BrushMakeHollow_Selected( GlobalSceneGraph() );
150 template<typename Type>
151 class RemoveReference
157 template<typename Type>
158 class RemoveReference<Type&>
164 template<typename Functor>
167 const Functor& functor;
169 typedef typename RemoveReference<typename Functor::first_argument_type>::type* first_argument_type;
170 typedef typename Functor::result_type result_type;
171 Dereference( const Functor& functor ) : functor( functor ){
173 result_type operator()( first_argument_type firstArgument ) const {
174 return functor( *firstArgument );
178 template<typename Functor>
179 inline Dereference<Functor> makeDereference( const Functor& functor ){
180 return Dereference<Functor>( functor );
183 typedef Face* FacePointer;
184 const FacePointer c_nullFacePointer = 0;
186 template<typename Predicate>
187 Face* Brush_findIf( const Brush& brush, const Predicate& predicate ){
188 Brush::const_iterator i = std::find_if( brush.begin(), brush.end(), makeDereference( predicate ) );
189 return i == brush.end() ? c_nullFacePointer : *i; // uses c_nullFacePointer instead of 0 because otherwise gcc 4.1 attempts conversion to int
192 template<typename Caller>
195 typedef typename Caller::second_argument_type FirstBound;
196 FirstBound firstBound;
198 typedef typename Caller::result_type result_type;
199 typedef typename Caller::first_argument_type first_argument_type;
200 BindArguments1( FirstBound firstBound )
201 : firstBound( firstBound ){
203 result_type operator()( first_argument_type firstArgument ) const {
204 return Caller::call( firstArgument, firstBound );
208 template<typename Caller>
211 typedef typename Caller::second_argument_type FirstBound;
212 typedef typename Caller::third_argument_type SecondBound;
213 FirstBound firstBound;
214 SecondBound secondBound;
216 typedef typename Caller::result_type result_type;
217 typedef typename Caller::first_argument_type first_argument_type;
218 BindArguments2( FirstBound firstBound, SecondBound secondBound )
219 : firstBound( firstBound ), secondBound( secondBound ){
221 result_type operator()( first_argument_type firstArgument ) const {
222 return Caller::call( firstArgument, firstBound, secondBound );
226 template<typename Caller, typename FirstBound, typename SecondBound>
227 BindArguments2<Caller> bindArguments( const Caller& caller, FirstBound firstBound, SecondBound secondBound ){
228 return BindArguments2<Caller>( firstBound, secondBound );
231 inline bool Face_testPlane( const Face& face, const Plane3& plane, bool flipped ){
232 return face.contributes() && !Winding_TestPlane( face.getWinding(), plane, flipped );
234 typedef Function3<const Face&, const Plane3&, bool, 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 ){
242 brush.evaluateBRep();
244 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 ){
257 brush.evaluateBRep();
259 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 ){
269 if ( aabb_intersects_aabb( brush.localAABB(), other.localAABB() ) ) {
270 brush_vector_t fragments;
271 fragments.reserve( other.size() );
274 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 ) );
282 if ( newFace != 0 ) {
283 newFace->flipWinding();
285 back.addFace( *( *i ) );
287 else if ( split.counts[ePlaneBack] == 0 ) {
288 for ( brush_vector_t::iterator i = fragments.begin(); i != fragments.end(); ++i )
296 ret_fragments.insert( ret_fragments.end(), fragments.begin(), fragments.end() );
302 class SubtractBrushesFromUnselected : public scene::Graph::Walker
304 const brush_vector_t& m_brushlist;
305 std::size_t& m_before;
306 std::size_t& m_after;
308 SubtractBrushesFromUnselected( const brush_vector_t& brushlist, std::size_t& before, std::size_t& after )
309 : m_brushlist( brushlist ), m_before( before ), m_after( after ){
311 bool pre( const scene::Path& path, scene::Instance& instance ) const {
314 void post( const scene::Path& path, scene::Instance& instance ) const {
315 if ( path.top().get().visible() ) {
316 Brush* brush = Node_getBrush( path.top() );
318 && !Instance_getSelectable( instance )->isSelected() ) {
319 brush_vector_t buffer[2];
321 Brush* original = new Brush( *brush );
322 buffer[static_cast<std::size_t>( swap )].push_back( original );
325 for ( brush_vector_t::const_iterator i( m_brushlist.begin() ); i != m_brushlist.end(); ++i )
327 for ( brush_vector_t::iterator j( buffer[static_cast<std::size_t>( swap )].begin() ); j != buffer[static_cast<std::size_t>( swap )].end(); ++j )
329 if ( Brush_subtract( *( *j ), *( *i ), buffer[static_cast<std::size_t>( !swap )] ) ) {
334 buffer[static_cast<std::size_t>( !swap )].push_back( ( *j ) );
337 buffer[static_cast<std::size_t>( swap )].clear();
342 brush_vector_t& out = buffer[static_cast<std::size_t>( swap )];
344 if ( out.size() == 1 && out.back() == original ) {
350 for ( brush_vector_t::const_iterator i = out.begin(); i != out.end(); ++i )
353 ( *i )->removeEmptyFaces();
354 if ( !( *i )->empty() ) {
355 NodeSmartReference node( ( new BrushNode() )->node() );
356 Node_getBrush( node )->copy( *( *i ) );
358 Node_getTraversable( path.parent() )->insert( node );
364 Path_deleteTop( path );
372 brush_vector_t selected_brushes;
373 GlobalSceneGraph().traverse( BrushGatherSelected( selected_brushes ) );
375 if ( selected_brushes.empty() ) {
376 globalOutputStream() << "CSG Subtract: No brushes selected.\n";
380 globalOutputStream() << "CSG Subtract: Subtracting " << Unsigned( selected_brushes.size() ) << " brushes.\n";
382 UndoableCommand undo( "brushSubtract" );
384 // subtract selected from unselected
385 std::size_t before = 0;
386 std::size_t after = 0;
387 GlobalSceneGraph().traverse( SubtractBrushesFromUnselected( selected_brushes, before, after ) );
388 globalOutputStream() << "CSG Subtract: Result: "
389 << Unsigned( after ) << " fragment" << ( after == 1 ? "" : "s" )
390 << " from " << Unsigned( before ) << " brush" << ( before == 1 ? "" : "es" ) << ".\n";
396 class BrushSplitByPlaneSelected : public scene::Graph::Walker
401 const char* m_shader;
402 const TextureProjection& m_projection;
405 BrushSplitByPlaneSelected( const Vector3& p0, const Vector3& p1, const Vector3& p2, const char* shader, const TextureProjection& projection, EBrushSplit split )
406 : m_p0( p0 ), m_p1( p1 ), m_p2( p2 ), m_shader( shader ), m_projection( projection ), m_split( split ){
408 bool pre( const scene::Path& path, scene::Instance& instance ) const {
411 void post( const scene::Path& path, scene::Instance& instance ) const {
412 if ( path.top().get().visible() ) {
413 Brush* brush = Node_getBrush( path.top() );
415 && Instance_getSelectable( instance )->isSelected() ) {
416 Plane3 plane( plane3_for_points( m_p0, m_p1, m_p2 ) );
417 if ( plane3_valid( plane ) ) {
418 brushsplit_t split = Brush_classifyPlane( *brush, m_split == eFront ? plane3_flipped( plane ) : plane );
419 if ( split.counts[ePlaneBack] && split.counts[ePlaneFront] ) {
420 // the plane intersects this brush
421 if ( m_split == eFrontAndBack ) {
422 NodeSmartReference node( ( new BrushNode() )->node() );
423 Brush* fragment = Node_getBrush( node );
424 fragment->copy( *brush );
425 Face* newFace = fragment->addPlane( m_p0, m_p1, m_p2, m_shader, m_projection );
426 if ( newFace != 0 && m_split != eFront ) {
427 newFace->flipWinding();
429 fragment->removeEmptyFaces();
430 ASSERT_MESSAGE( !fragment->empty(), "brush left with no faces after split" );
432 Node_getTraversable( path.parent() )->insert( node );
434 scene::Path fragmentPath = path;
435 fragmentPath.top() = makeReference( node.get() );
436 selectPath( fragmentPath, true );
440 Face* newFace = brush->addPlane( m_p0, m_p1, m_p2, m_shader, m_projection );
441 if ( newFace != 0 && m_split == eFront ) {
442 newFace->flipWinding();
444 brush->removeEmptyFaces();
445 ASSERT_MESSAGE( !brush->empty(), "brush left with no faces after split" );
448 // the plane does not intersect this brush
449 if ( m_split != eFrontAndBack && split.counts[ePlaneBack] != 0 ) {
450 // the brush is "behind" the plane
451 Path_deleteTop( path );
459 void Scene_BrushSplitByPlane( scene::Graph& graph, const Vector3& p0, const Vector3& p1, const Vector3& p2, 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
471 BrushInstanceSetClipPlane( const Plane3& plane )
474 bool pre( const scene::Path& path, scene::Instance& instance ) const {
475 BrushInstance* brush = Instance_getBrush( instance );
477 && path.top().get().visible()
478 && brush->isSelected() ) {
479 BrushInstance& brushInstance = *brush;
480 brushInstance.setClipPlane( m_plane );
486 void Scene_BrushSetClipPlane( scene::Graph& graph, const Plane3& plane ){
487 graph.traverse( BrushInstanceSetClipPlane( plane ) );
495 bool Brush_merge( Brush& brush, const brush_vector_t& in, bool onlyshape ){
496 // gather potential outer faces
499 typedef std::vector<const Face*> Faces;
501 for ( brush_vector_t::const_iterator i( in.begin() ); i != in.end(); ++i )
503 ( *i )->evaluateBRep();
504 for ( Brush::const_iterator j( ( *i )->begin() ); j != ( *i )->end(); ++j )
506 if ( !( *j )->contributes() ) {
510 const Face& face1 = *( *j );
513 // test faces of all input brushes
514 //!\todo SPEEDUP: Flag already-skip faces and only test brushes from i+1 upwards.
515 for ( brush_vector_t::const_iterator k( in.begin() ); !skip && k != in.end(); ++k )
517 if ( k != i ) { // don't test a brush against itself
518 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 )
535 const Face& face2 = *( *m );
537 // face equals another face
538 if ( plane3_equal( face1.plane3(), face2.plane3() ) ) {
539 //if the texture/shader references should be the same but are not
540 if ( !onlyshape && !shader_equal( face1.getShader().getShader(), face2.getShader().getShader() ) ) {
543 // skip duplicate planes
548 // face1 plane intersects face2 winding or vice versa
549 if ( Winding_PlanesConcave( face1.getWinding(), face2.getWinding(), face1.plane3(), face2.plane3() ) ) {
550 // result would not be convex
556 faces.push_back( &face1 );
560 for ( Faces::const_iterator i = faces.begin(); i != faces.end(); ++i )
562 if ( !brush.addFace( *( *i ) ) ) {
563 // result would have too many sides
569 brush.removeEmptyFaces();
574 void CSG_Merge( void ){
575 brush_vector_t selected_brushes;
578 GlobalSceneGraph().traverse( BrushGatherSelected( selected_brushes ) );
580 if ( selected_brushes.empty() ) {
581 globalOutputStream() << "CSG Merge: No brushes selected.\n";
585 if ( selected_brushes.size() < 2 ) {
586 globalOutputStream() << "CSG Merge: At least two brushes have to be selected.\n";
590 globalOutputStream() << "CSG Merge: Merging " << Unsigned( selected_brushes.size() ) << " brushes.\n";
592 UndoableCommand undo( "brushMerge" );
594 scene::Path merged_path = GlobalSelectionSystem().ultimateSelected().path();
596 NodeSmartReference node( ( new BrushNode() )->node() );
597 Brush* brush = Node_getBrush( node );
598 // if the new brush would not be convex
599 if ( !Brush_merge( *brush, selected_brushes, true ) ) {
600 globalOutputStream() << "CSG Merge: Failed - result would not be convex.\n";
604 ASSERT_MESSAGE( !brush->empty(), "brush left with no faces after merge" );
606 // free the original brushes
607 GlobalSceneGraph().traverse( BrushDeleteSelected() );
610 Node_getTraversable( merged_path.top() )->insert( node );
611 merged_path.push( makeReference( node.get() ) );
613 selectPath( merged_path, true );
615 globalOutputStream() << "CSG Merge: Succeeded.\n";