44fefdc863484ec9759fb806724b08f04268fa8c
[xonotic/netradiant.git] / radiant / csg.cpp
1 /*
2    Copyright (C) 1999-2006 Id Software, Inc. and contributors.
3    For a list of contributors, see the accompanying CONTRIBUTORS file.
4
5    This file is part of GtkRadiant.
6
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.
11
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.
16
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
20  */
21
22 #include "csg.h"
23
24 #include "debugging/debugging.h"
25
26 #include <list>
27
28 #include "map.h"
29 #include "brushmanip.h"
30 #include "brushnode.h"
31 #include "grid.h"
32
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 );
37                 if ( newFace != 0 ) {
38                         newFace->flipWinding();
39                         newFace->getPlane().offset( offset );
40                         newFace->planeChanged();
41                 }
42         }
43 }
44
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                 Face* newFace = out.back()->addFace( face );
51                 if ( newFace != 0 ) {
52                         newFace->flipWinding();
53                         newFace->planeChanged();
54                 }
55         }
56 }
57
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 );
61         } );
62 }
63
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 );
67         } );
68 }
69
70 class BrushHollowSelectedWalker : public scene::Graph::Walker
71 {
72 float m_offset;
73 bool m_makeRoom;
74 public:
75 BrushHollowSelectedWalker( float offset, bool makeRoom )
76         : m_offset( offset ), m_makeRoom( makeRoom ){
77 }
78
79 bool pre( const scene::Path& path, scene::Instance& instance ) const {
80         if ( path.top().get().visible() ) {
81                 Brush* brush = Node_getBrush( path.top() );
82                 if ( brush != 0
83                          && Instance_getSelectable( instance )->isSelected()
84                          && path.size() > 1 ) {
85                         brush_vector_t out;
86
87                         if ( m_makeRoom ) {
88                                 Brush_makeRoom(* brush, out, m_offset );
89                         }
90                         else
91                         {
92                                 Brush_makeHollow(* brush, out, m_offset );
93                         }
94
95                         for ( brush_vector_t::const_iterator i = out.begin(); i != out.end(); ++i )
96                         {
97                                 ( *i )->removeEmptyFaces();
98                                 NodeSmartReference node( ( new BrushNode() )->node() );
99                                 Node_getBrush( node )->copy( *( *i ) );
100                                 delete ( *i );
101                                 Node_getTraversable( path.parent() )->insert( node );
102                         }
103                 }
104         }
105         return true;
106 }
107 };
108
109 typedef std::list<Brush*> brushlist_t;
110
111 class BrushGatherSelected : public scene::Graph::Walker
112 {
113 brush_vector_t& m_brushlist;
114 public:
115 BrushGatherSelected( brush_vector_t& brushlist )
116         : m_brushlist( brushlist ){
117 }
118
119 bool pre( const scene::Path& path, scene::Instance& instance ) const {
120         if ( path.top().get().visible() ) {
121                 Brush* brush = Node_getBrush( path.top() );
122                 if ( brush != 0
123                          && Instance_getSelectable( instance )->isSelected() ) {
124                         m_brushlist.push_back( brush );
125                 }
126         }
127         return true;
128 }
129 };
130
131 class BrushDeleteSelected : public scene::Graph::Walker
132 {
133 public:
134 bool pre( const scene::Path& path, scene::Instance& instance ) const {
135         return true;
136 }
137 void post( const scene::Path& path, scene::Instance& instance ) const {
138         if ( path.top().get().visible() ) {
139                 Brush* brush = Node_getBrush( path.top() );
140                 if ( brush != 0
141                          && Instance_getSelectable( instance )->isSelected()
142                          && path.size() > 1 ) {
143                         Path_deleteTop( path );
144                 }
145         }
146 }
147 };
148
149 void Scene_BrushMakeHollow_Selected( scene::Graph& graph, bool makeRoom ){
150         GlobalSceneGraph().traverse( BrushHollowSelectedWalker( GetGridSize(), makeRoom ) );
151         GlobalSceneGraph().traverse( BrushDeleteSelected() );
152 }
153
154 /*
155    =============
156    CSG_MakeHollow
157    =============
158  */
159
160 void CSG_MakeHollow( void ){
161         UndoableCommand undo( "brushHollow" );
162
163         Scene_BrushMakeHollow_Selected( GlobalSceneGraph(), false );
164
165         SceneChangeNotify();
166 }
167
168 void CSG_MakeRoom( void ){
169         UndoableCommand undo( "brushRoom" );
170
171         Scene_BrushMakeHollow_Selected( GlobalSceneGraph(), true );
172
173         SceneChangeNotify();
174 }
175
176 template<typename Type>
177 class RemoveReference
178 {
179 public:
180 typedef Type type;
181 };
182
183 template<typename Type>
184 class RemoveReference<Type&>
185 {
186 public:
187 typedef Type type;
188 };
189
190 template<typename Functor>
191 class Dereference
192 {
193 const Functor& functor;
194 public:
195 Dereference( const Functor& functor ) : functor( functor ){
196 }
197 get_result_type<Functor> operator()( typename RemoveReference<get_argument<Functor, 0>>::type *firstArgument ) const {
198         return functor( *firstArgument );
199 }
200 };
201
202 template<typename Functor>
203 inline Dereference<Functor> makeDereference( const Functor& functor ){
204         return Dereference<Functor>( functor );
205 }
206
207 typedef Face* FacePointer;
208 const FacePointer c_nullFacePointer = 0;
209
210 template<typename Predicate>
211 Face* Brush_findIf( const Brush& brush, const Predicate& predicate ){
212         Brush::const_iterator i = std::find_if( brush.begin(), brush.end(), makeDereference( predicate ) );
213         return i == brush.end() ? c_nullFacePointer : *i; // uses c_nullFacePointer instead of 0 because otherwise gcc 4.1 attempts conversion to int
214 }
215
216 template<typename Caller>
217 class BindArguments1
218 {
219 typedef get_argument<Caller, 1> FirstBound;
220 FirstBound firstBound;
221 public:
222 BindArguments1( FirstBound firstBound )
223         : firstBound( firstBound ){
224 }
225
226 get_result_type<Caller> operator()( get_argument<Caller, 0> firstArgument ) const {
227         return Caller::call( firstArgument, firstBound );
228 }
229 };
230
231 template<typename Caller>
232 class BindArguments2
233 {
234 typedef get_argument<Caller, 1> FirstBound;
235 typedef get_argument<Caller, 2> SecondBound;
236 FirstBound firstBound;
237 SecondBound secondBound;
238 public:
239 BindArguments2( FirstBound firstBound, SecondBound secondBound )
240         : firstBound( firstBound ), secondBound( secondBound ){
241 }
242
243 get_result_type<Caller> operator()( get_argument<Caller, 0> firstArgument ) const {
244         return Caller::call( firstArgument, firstBound, secondBound );
245 }
246 };
247
248 template<typename Caller, typename FirstBound, typename SecondBound>
249 BindArguments2<Caller> bindArguments( const Caller& caller, FirstBound firstBound, SecondBound secondBound ){
250         return BindArguments2<Caller>( firstBound, secondBound );
251 }
252
253 inline bool Face_testPlane( const Face& face, const Plane3& plane, bool flipped ){
254         return face.contributes() && !Winding_TestPlane( face.getWinding(), plane, flipped );
255 }
256
257 typedef Function<bool ( const Face &, const Plane3 &, bool ), Face_testPlane> FaceTestPlane;
258
259
260 /// \brief Returns true if
261 /// \li !flipped && brush is BACK or ON
262 /// \li flipped && brush is FRONT or ON
263 bool Brush_testPlane( const Brush& brush, const Plane3& plane, bool flipped ){
264         brush.evaluateBRep();
265 #if 1
266         for ( Brush::const_iterator i( brush.begin() ); i != brush.end(); ++i )
267         {
268                 if ( Face_testPlane( *( *i ), plane, flipped ) ) {
269                         return false;
270                 }
271         }
272         return true;
273 #else
274         return Brush_findIf( brush, bindArguments( FaceTestPlane(), makeReference( plane ), flipped ) ) == 0;
275 #endif
276 }
277
278 brushsplit_t Brush_classifyPlane( const Brush& brush, const Plane3& plane ){
279         brush.evaluateBRep();
280         brushsplit_t split;
281         for ( Brush::const_iterator i( brush.begin() ); i != brush.end(); ++i )
282         {
283                 if ( ( *i )->contributes() ) {
284                         split += Winding_ClassifyPlane( ( *i )->getWinding(), plane );
285                 }
286         }
287         return split;
288 }
289
290 bool Brush_subtract( const Brush& brush, const Brush& other, brush_vector_t& ret_fragments ){
291         if ( aabb_intersects_aabb( brush.localAABB(), other.localAABB() ) ) {
292                 brush_vector_t fragments;
293                 fragments.reserve( other.size() );
294                 Brush back( brush );
295
296                 for ( Brush::const_iterator i( other.begin() ); i != other.end(); ++i )
297                 {
298                         if ( ( *i )->contributes() ) {
299                                 brushsplit_t split = Brush_classifyPlane( back, ( *i )->plane3() );
300                                 if ( split.counts[ePlaneFront] != 0
301                                          && split.counts[ePlaneBack] != 0 ) {
302                                         fragments.push_back( new Brush( back ) );
303                                         Face* newFace = fragments.back()->addFace( *( *i ) );
304                                         if ( newFace != 0 ) {
305                                                 newFace->flipWinding();
306                                         }
307                                         back.addFace( *( *i ) );
308                                 }
309                                 else if ( split.counts[ePlaneBack] == 0 ) {
310                                         for ( brush_vector_t::iterator i = fragments.begin(); i != fragments.end(); ++i )
311                                         {
312                                                 delete( *i );
313                                         }
314                                         return false;
315                                 }
316                         }
317                 }
318                 ret_fragments.insert( ret_fragments.end(), fragments.begin(), fragments.end() );
319                 return true;
320         }
321         return false;
322 }
323
324 class SubtractBrushesFromUnselected : public scene::Graph::Walker
325 {
326 const brush_vector_t& m_brushlist;
327 std::size_t& m_before;
328 std::size_t& m_after;
329 public:
330 SubtractBrushesFromUnselected( const brush_vector_t& brushlist, std::size_t& before, std::size_t& after )
331         : m_brushlist( brushlist ), m_before( before ), m_after( after ){
332 }
333
334 bool pre( const scene::Path& path, scene::Instance& instance ) const {
335         return true;
336 }
337
338 void post( const scene::Path& path, scene::Instance& instance ) const {
339         if ( path.top().get().visible() ) {
340                 Brush* brush = Node_getBrush( path.top() );
341                 if ( brush != 0
342                          && !Instance_getSelectable( instance )->isSelected() ) {
343                         brush_vector_t buffer[2];
344                         bool swap = false;
345                         Brush* original = new Brush( *brush );
346                         buffer[static_cast<std::size_t>( swap )].push_back( original );
347
348                         {
349                                 for ( brush_vector_t::const_iterator i( m_brushlist.begin() ); i != m_brushlist.end(); ++i )
350                                 {
351                                         for ( brush_vector_t::iterator j( buffer[static_cast<std::size_t>( swap )].begin() ); j != buffer[static_cast<std::size_t>( swap )].end(); ++j )
352                                         {
353                                                 if ( Brush_subtract( *( *j ), *( *i ), buffer[static_cast<std::size_t>( !swap )] ) ) {
354                                                         delete ( *j );
355                                                 }
356                                                 else
357                                                 {
358                                                         buffer[static_cast<std::size_t>( !swap )].push_back( ( *j ) );
359                                                 }
360                                         }
361                                         buffer[static_cast<std::size_t>( swap )].clear();
362                                         swap = !swap;
363                                 }
364                         }
365
366                         brush_vector_t& out = buffer[static_cast<std::size_t>( swap )];
367
368                         if ( out.size() == 1 && out.back() == original ) {
369                                 delete original;
370                         }
371                         else
372                         {
373                                 ++m_before;
374                                 for ( brush_vector_t::const_iterator i = out.begin(); i != out.end(); ++i )
375                                 {
376                                         ++m_after;
377                                         ( *i )->removeEmptyFaces();
378                                         if ( !( *i )->empty() ) {
379                                                 NodeSmartReference node( ( new BrushNode() )->node() );
380                                                 Node_getBrush( node )->copy( *( *i ) );
381                                                 delete ( *i );
382                                                 Node_getTraversable( path.parent() )->insert( node );
383                                         }
384                                         else{
385                                                 delete ( *i );
386                                         }
387                                 }
388                                 Path_deleteTop( path );
389                         }
390                 }
391         }
392 }
393 };
394
395 void CSG_Subtract(){
396         brush_vector_t selected_brushes;
397         GlobalSceneGraph().traverse( BrushGatherSelected( selected_brushes ) );
398
399         if ( selected_brushes.empty() ) {
400                 globalOutputStream() << "CSG Subtract: No brushes selected.\n";
401         }
402         else
403         {
404                 globalOutputStream() << "CSG Subtract: Subtracting " << Unsigned( selected_brushes.size() ) << " brushes.\n";
405
406                 UndoableCommand undo( "brushSubtract" );
407
408                 // subtract selected from unselected
409                 std::size_t before = 0;
410                 std::size_t after = 0;
411                 GlobalSceneGraph().traverse( SubtractBrushesFromUnselected( selected_brushes, before, after ) );
412                 globalOutputStream() << "CSG Subtract: Result: "
413                                                          << Unsigned( after ) << " fragment" << ( after == 1 ? "" : "s" )
414                                                          << " from " << Unsigned( before ) << " brush" << ( before == 1 ? "" : "es" ) << ".\n";
415
416                 SceneChangeNotify();
417         }
418 }
419
420 class BrushSplitByPlaneSelected : public scene::Graph::Walker
421 {
422 const Vector3& m_p0;
423 const Vector3& m_p1;
424 const Vector3& m_p2;
425 const char* m_shader;
426 const TextureProjection& m_projection;
427 EBrushSplit m_split;
428 public:
429 BrushSplitByPlaneSelected( const Vector3& p0, const Vector3& p1, const Vector3& p2, const char* shader, const TextureProjection& projection, EBrushSplit split )
430         : m_p0( p0 ), m_p1( p1 ), m_p2( p2 ), m_shader( shader ), m_projection( projection ), m_split( split ){
431 }
432
433 bool pre( const scene::Path& path, scene::Instance& instance ) const {
434         return true;
435 }
436
437 void post( const scene::Path& path, scene::Instance& instance ) const {
438         if ( path.top().get().visible() ) {
439                 Brush* brush = Node_getBrush( path.top() );
440                 if ( brush != 0
441                          && Instance_getSelectable( instance )->isSelected() ) {
442                         Plane3 plane( plane3_for_points( m_p0, m_p1, m_p2 ) );
443                         if ( plane3_valid( plane ) ) {
444                                 brushsplit_t split = Brush_classifyPlane( *brush, m_split == eFront ? plane3_flipped( plane ) : plane );
445                                 if ( split.counts[ePlaneBack] && split.counts[ePlaneFront] ) {
446                                         // the plane intersects this brush
447                                         if ( m_split == eFrontAndBack ) {
448                                                 NodeSmartReference node( ( new BrushNode() )->node() );
449                                                 Brush* fragment = Node_getBrush( node );
450                                                 fragment->copy( *brush );
451                                                 Face* newFace = fragment->addPlane( m_p0, m_p1, m_p2, m_shader, m_projection );
452                                                 if ( newFace != 0 && m_split != eFront ) {
453                                                         newFace->flipWinding();
454                                                 }
455                                                 fragment->removeEmptyFaces();
456                                                 ASSERT_MESSAGE( !fragment->empty(), "brush left with no faces after split" );
457
458                                                 Node_getTraversable( path.parent() )->insert( node );
459                                                 {
460                                                         scene::Path fragmentPath = path;
461                                                         fragmentPath.top() = makeReference( node.get() );
462                                                         selectPath( fragmentPath, true );
463                                                 }
464                                         }
465
466                                         Face* newFace = brush->addPlane( m_p0, m_p1, m_p2, m_shader, m_projection );
467                                         if ( newFace != 0 && m_split == eFront ) {
468                                                 newFace->flipWinding();
469                                         }
470                                         brush->removeEmptyFaces();
471                                         ASSERT_MESSAGE( !brush->empty(), "brush left with no faces after split" );
472                                 }
473                                 else
474                                 // the plane does not intersect this brush
475                                 if ( m_split != eFrontAndBack && split.counts[ePlaneBack] != 0 ) {
476                                         // the brush is "behind" the plane
477                                         Path_deleteTop( path );
478                                 }
479                         }
480                 }
481         }
482 }
483 };
484
485 void Scene_BrushSplitByPlane( scene::Graph& graph, const Vector3& p0, const Vector3& p1, const Vector3& p2, const char* shader, EBrushSplit split ){
486         TextureProjection projection;
487         TexDef_Construct_Default( projection );
488         graph.traverse( BrushSplitByPlaneSelected( p0, p1, p2, shader, projection, split ) );
489         SceneChangeNotify();
490 }
491
492
493 class BrushInstanceSetClipPlane : public scene::Graph::Walker
494 {
495 Plane3 m_plane;
496 public:
497 BrushInstanceSetClipPlane( const Plane3& plane )
498         : m_plane( plane ){
499 }
500
501 bool pre( const scene::Path& path, scene::Instance& instance ) const {
502         BrushInstance* brush = Instance_getBrush( instance );
503         if ( brush != 0
504                  && path.top().get().visible()
505                  && brush->isSelected() ) {
506                 BrushInstance& brushInstance = *brush;
507                 brushInstance.setClipPlane( m_plane );
508         }
509         return true;
510 }
511 };
512
513 void Scene_BrushSetClipPlane( scene::Graph& graph, const Plane3& plane ){
514         graph.traverse( BrushInstanceSetClipPlane( plane ) );
515 }
516
517 /*
518    =============
519    CSG_Merge
520    =============
521  */
522 bool Brush_merge( Brush& brush, const brush_vector_t& in, bool onlyshape ){
523         // gather potential outer faces
524
525         {
526                 typedef std::vector<const Face*> Faces;
527                 Faces faces;
528                 for ( brush_vector_t::const_iterator i( in.begin() ); i != in.end(); ++i )
529                 {
530                         ( *i )->evaluateBRep();
531                         for ( Brush::const_iterator j( ( *i )->begin() ); j != ( *i )->end(); ++j )
532                         {
533                                 if ( !( *j )->contributes() ) {
534                                         continue;
535                                 }
536
537                                 const Face& face1 = *( *j );
538
539                                 bool skip = false;
540                                 // test faces of all input brushes
541                                 //!\todo SPEEDUP: Flag already-skip faces and only test brushes from i+1 upwards.
542                                 for ( brush_vector_t::const_iterator k( in.begin() ); !skip && k != in.end(); ++k )
543                                 {
544                                         if ( k != i ) { // don't test a brush against itself
545                                                 for ( Brush::const_iterator l( ( *k )->begin() ); !skip && l != ( *k )->end(); ++l )
546                                                 {
547                                                         const Face& face2 = *( *l );
548
549                                                         // face opposes another face
550                                                         if ( plane3_opposing( face1.plane3(), face2.plane3() ) ) {
551                                                                 // skip opposing planes
552                                                                 skip  = true;
553                                                                 break;
554                                                         }
555                                                 }
556                                         }
557                                 }
558
559                                 // check faces already stored
560                                 for ( Faces::const_iterator m = faces.begin(); !skip && m != faces.end(); ++m )
561                                 {
562                                         const Face& face2 = *( *m );
563
564                                         // face equals another face
565                                         if ( plane3_equal( face1.plane3(), face2.plane3() ) ) {
566                                                 //if the texture/shader references should be the same but are not
567                                                 if ( !onlyshape && !shader_equal( face1.getShader().getShader(), face2.getShader().getShader() ) ) {
568                                                         return false;
569                                                 }
570                                                 // skip duplicate planes
571                                                 skip = true;
572                                                 break;
573                                         }
574
575                                         // face1 plane intersects face2 winding or vice versa
576                                         if ( Winding_PlanesConcave( face1.getWinding(), face2.getWinding(), face1.plane3(), face2.plane3() ) ) {
577                                                 // result would not be convex
578                                                 return false;
579                                         }
580                                 }
581
582                                 if ( !skip ) {
583                                         faces.push_back( &face1 );
584                                 }
585                         }
586                 }
587                 for ( Faces::const_iterator i = faces.begin(); i != faces.end(); ++i )
588                 {
589                         if ( !brush.addFace( *( *i ) ) ) {
590                                 // result would have too many sides
591                                 return false;
592                         }
593                 }
594         }
595
596         brush.removeEmptyFaces();
597
598         return true;
599 }
600
601 void CSG_Merge( void ){
602         brush_vector_t selected_brushes;
603
604         // remove selected
605         GlobalSceneGraph().traverse( BrushGatherSelected( selected_brushes ) );
606
607         if ( selected_brushes.empty() ) {
608                 globalOutputStream() << "CSG Merge: No brushes selected.\n";
609                 return;
610         }
611
612         if ( selected_brushes.size() < 2 ) {
613                 globalOutputStream() << "CSG Merge: At least two brushes have to be selected.\n";
614                 return;
615         }
616
617         globalOutputStream() << "CSG Merge: Merging " << Unsigned( selected_brushes.size() ) << " brushes.\n";
618
619         UndoableCommand undo( "brushMerge" );
620
621         scene::Path merged_path = GlobalSelectionSystem().ultimateSelected().path();
622
623         NodeSmartReference node( ( new BrushNode() )->node() );
624         Brush* brush = Node_getBrush( node );
625         // if the new brush would not be convex
626         if ( !Brush_merge( *brush, selected_brushes, true ) ) {
627                 globalOutputStream() << "CSG Merge: Failed - result would not be convex.\n";
628         }
629         else
630         {
631                 ASSERT_MESSAGE( !brush->empty(), "brush left with no faces after merge" );
632
633                 // free the original brushes
634                 GlobalSceneGraph().traverse( BrushDeleteSelected() );
635
636                 merged_path.pop();
637                 Node_getTraversable( merged_path.top() )->insert( node );
638                 merged_path.push( makeReference( node.get() ) );
639
640                 selectPath( merged_path, true );
641
642                 globalOutputStream() << "CSG Merge: Succeeded.\n";
643                 SceneChangeNotify();
644         }
645 }