radiant/brush: use std::shared_ptr
[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                 std::shared_ptr<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                 std::shared_ptr<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 template<typename Caller>
208 class BindArguments1
209 {
210 typedef get_argument<Caller, 1> FirstBound;
211 FirstBound firstBound;
212 public:
213 BindArguments1( FirstBound firstBound )
214         : firstBound( firstBound ){
215 }
216
217 get_result_type<Caller> operator()( get_argument<Caller, 0> firstArgument ) const {
218         return Caller::call( firstArgument, firstBound );
219 }
220 };
221
222 template<typename Caller>
223 class BindArguments2
224 {
225 typedef get_argument<Caller, 1> FirstBound;
226 typedef get_argument<Caller, 2> SecondBound;
227 FirstBound firstBound;
228 SecondBound secondBound;
229 public:
230 BindArguments2( FirstBound firstBound, SecondBound secondBound )
231         : firstBound( firstBound ), secondBound( secondBound ){
232 }
233
234 get_result_type<Caller> operator()( get_argument<Caller, 0> firstArgument ) const {
235         return Caller::call( firstArgument, firstBound, secondBound );
236 }
237 };
238
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 );
242 }
243
244 inline bool Face_testPlane( const Face& face, const Plane3& plane, bool flipped ){
245         return face.contributes() && !Winding_TestPlane( face.getWinding(), plane, flipped );
246 }
247
248 typedef Function<bool ( const Face &, const Plane3 &, bool ), Face_testPlane> FaceTestPlane;
249
250
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 )
257         {
258                 if ( Face_testPlane( *( *i ), plane, flipped ) ) {
259                         return false;
260                 }
261         }
262         return true;
263 }
264
265 brushsplit_t Brush_classifyPlane( const Brush& brush, const Plane3& plane ){
266         brush.evaluateBRep();
267         brushsplit_t split;
268         for ( Brush::const_iterator i( brush.begin() ); i != brush.end(); ++i )
269         {
270                 if ( ( *i )->contributes() ) {
271                         split += Winding_ClassifyPlane( ( *i )->getWinding(), plane );
272                 }
273         }
274         return split;
275 }
276
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() );
281                 Brush back( brush );
282
283                 for ( const std::shared_ptr<Face>& b : other )
284                 {
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();
293                                         }
294                                         back.addFace( *b );
295                                 }
296                                 else if ( split.counts[ePlaneBack] == 0 ) {
297                                         for ( Brush *i : fragments ) {
298                                                 delete( i );
299                                         }
300                                         fragments.clear();
301                                         return false;
302                                 }
303                         }
304                 }
305                 ret_fragments.insert( ret_fragments.end(), fragments.begin(), fragments.end() );
306                 return true;
307         }
308         return false;
309 }
310
311 class SubtractBrushesFromUnselected : public scene::Graph::Walker
312 {
313 const brush_vector_t& m_brushlist;
314 std::size_t& m_before;
315 std::size_t& m_after;
316 public:
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 ){
319 }
320
321 bool pre( const scene::Path& path, scene::Instance& instance ) const {
322         return true;
323 }
324
325 void post( const scene::Path& path, scene::Instance& instance ) const {
326         if ( path.top().get().visible() ) {
327                 Brush* brush = Node_getBrush( path.top() );
328                 if ( brush != 0
329                          && !Instance_getSelectable( instance )->isSelected() ) {
330                         brush_vector_t buffer[2];
331                         bool swap = false;
332                         Brush* original = new Brush( *brush );
333                         buffer[static_cast<std::size_t>( swap )].push_back( original );
334
335                         {
336                                 for ( brush_vector_t::const_iterator i( m_brushlist.begin() ); i != m_brushlist.end(); ++i )
337                                 {
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 )
339                                         {
340                                                 if ( Brush_subtract( *( *j ), *( *i ), buffer[static_cast<std::size_t>( !swap )] ) ) {
341                                                         delete ( *j );
342                                                 }
343                                                 else
344                                                 {
345                                                         buffer[static_cast<std::size_t>( !swap )].push_back( ( *j ) );
346                                                 }
347                                         }
348                                         buffer[static_cast<std::size_t>( swap )].clear();
349                                         swap = !swap;
350                                 }
351                         }
352
353                         brush_vector_t& out = buffer[static_cast<std::size_t>( swap )];
354
355                         if ( out.size() == 1 && out.back() == original ) {
356                                 delete original;
357                         }
358                         else
359                         {
360                                 ++m_before;
361                                 for ( brush_vector_t::const_iterator i = out.begin(); i != out.end(); ++i )
362                                 {
363                                         ++m_after;
364                                         ( *i )->removeEmptyFaces();
365                                         if ( !( *i )->empty() ) {
366                                                 NodeSmartReference node( ( new BrushNode() )->node() );
367                                                 Node_getBrush( node )->copy( *( *i ) );
368                                                 delete ( *i );
369                                                 Node_getTraversable( path.parent() )->insert( node );
370                                         }
371                                         else{
372                                                 delete ( *i );
373                                         }
374                                 }
375                                 Path_deleteTop( path );
376                         }
377                 }
378         }
379 }
380 };
381
382 void CSG_Subtract(){
383         brush_vector_t selected_brushes;
384         GlobalSceneGraph().traverse( BrushGatherSelected( selected_brushes ) );
385
386         if ( selected_brushes.empty() ) {
387                 globalOutputStream() << "CSG Subtract: No brushes selected.\n";
388         }
389         else
390         {
391                 globalOutputStream() << "CSG Subtract: Subtracting " << Unsigned( selected_brushes.size() ) << " brushes.\n";
392
393                 UndoableCommand undo( "brushSubtract" );
394
395                 // subtract selected from unselected
396                 std::size_t before = 0;
397                 std::size_t after = 0;
398                 GlobalSceneGraph().traverse( SubtractBrushesFromUnselected( selected_brushes, before, after ) );
399                 globalOutputStream() << "CSG Subtract: Result: "
400                                                          << Unsigned( after ) << " fragment" << ( after == 1 ? "" : "s" )
401                                                          << " from " << Unsigned( before ) << " brush" << ( before == 1 ? "" : "es" ) << ".\n";
402
403                 SceneChangeNotify();
404         }
405 }
406
407 class BrushSplitByPlaneSelected : public scene::Graph::Walker
408 {
409 const Vector3& m_p0;
410 const Vector3& m_p1;
411 const Vector3& m_p2;
412 const char* m_shader;
413 const TextureProjection& m_projection;
414 EBrushSplit m_split;
415 public:
416 BrushSplitByPlaneSelected( const Vector3& p0, const Vector3& p1, const Vector3& p2, const char* shader, const TextureProjection& projection, EBrushSplit split )
417         : m_p0( p0 ), m_p1( p1 ), m_p2( p2 ), m_shader( shader ), m_projection( projection ), m_split( split ){
418 }
419
420 bool pre( const scene::Path& path, scene::Instance& instance ) const {
421         return true;
422 }
423
424 void post( const scene::Path& path, scene::Instance& instance ) const {
425         if ( path.top().get().visible() ) {
426                 Brush* brush = Node_getBrush( path.top() );
427                 if ( brush != 0
428                          && Instance_getSelectable( instance )->isSelected() ) {
429                         Plane3 plane( plane3_for_points( m_p0, m_p1, m_p2 ) );
430                         if ( plane3_valid( plane ) ) {
431                                 brushsplit_t split = Brush_classifyPlane( *brush, m_split == eFront ? plane3_flipped( plane ) : plane );
432                                 if ( split.counts[ePlaneBack] && split.counts[ePlaneFront] ) {
433                                         // the plane intersects this brush
434                                         if ( m_split == eFrontAndBack ) {
435                                                 NodeSmartReference node( ( new BrushNode() )->node() );
436                                                 Brush* fragment = Node_getBrush( node );
437                                                 fragment->copy( *brush );
438                                                 std::shared_ptr<Face> newFace =
439                                                         fragment->addPlane( m_p0, m_p1, m_p2, m_shader, m_projection );
440                                                 if ( newFace != 0 && m_split != eFront ) {
441                                                         newFace->flipWinding();
442                                                 }
443                                                 fragment->removeEmptyFaces();
444                                                 ASSERT_MESSAGE( !fragment->empty(), "brush left with no faces after split" );
445
446                                                 Node_getTraversable( path.parent() )->insert( node );
447                                                 {
448                                                         scene::Path fragmentPath = path;
449                                                         fragmentPath.top() = makeReference( node.get() );
450                                                         selectPath( fragmentPath, true );
451                                                 }
452                                         }
453
454                                         std::shared_ptr<Face> newFace = brush->addPlane( m_p0, m_p1, m_p2, m_shader, m_projection );
455                                         if ( newFace != 0 && m_split == eFront ) {
456                                                 newFace->flipWinding();
457                                         }
458                                         brush->removeEmptyFaces();
459                                         ASSERT_MESSAGE( !brush->empty(), "brush left with no faces after split" );
460                                 }
461                                 else
462                                 // the plane does not intersect this brush
463                                 if ( m_split != eFrontAndBack && split.counts[ePlaneBack] != 0 ) {
464                                         // the brush is "behind" the plane
465                                         Path_deleteTop( path );
466                                 }
467                         }
468                 }
469         }
470 }
471 };
472
473 void Scene_BrushSplitByPlane( scene::Graph& graph, const Vector3& p0, const Vector3& p1, const Vector3& p2, const char* shader, EBrushSplit split ){
474         TextureProjection projection;
475         TexDef_Construct_Default( projection );
476         graph.traverse( BrushSplitByPlaneSelected( p0, p1, p2, shader, projection, split ) );
477         SceneChangeNotify();
478 }
479
480
481 class BrushInstanceSetClipPlane : public scene::Graph::Walker
482 {
483 Plane3 m_plane;
484 public:
485 BrushInstanceSetClipPlane( const Plane3& plane )
486         : m_plane( plane ){
487 }
488
489 bool pre( const scene::Path& path, scene::Instance& instance ) const {
490         BrushInstance* brush = Instance_getBrush( instance );
491         if ( brush != 0
492                  && path.top().get().visible()
493                  && brush->isSelected() ) {
494                 BrushInstance& brushInstance = *brush;
495                 brushInstance.setClipPlane( m_plane );
496         }
497         return true;
498 }
499 };
500
501 void Scene_BrushSetClipPlane( scene::Graph& graph, const Plane3& plane ){
502         graph.traverse( BrushInstanceSetClipPlane( plane ) );
503 }
504
505 /*
506    =============
507    CSG_Merge
508    =============
509  */
510 bool Brush_merge( Brush& brush, const brush_vector_t& in, bool onlyshape ){
511         // gather potential outer faces
512
513         {
514                 typedef std::vector<const Face*> Faces;
515                 Faces faces;
516                 for ( brush_vector_t::const_iterator i( in.begin() ); i != in.end(); ++i )
517                 {
518                         ( *i )->evaluateBRep();
519                         for ( Brush::const_iterator j( ( *i )->begin() ); j != ( *i )->end(); ++j )
520                         {
521                                 if ( !( *j )->contributes() ) {
522                                         continue;
523                                 }
524
525                                 const Face& face1 = *( *j );
526
527                                 bool skip = false;
528                                 // test faces of all input brushes
529                                 //!\todo SPEEDUP: Flag already-skip faces and only test brushes from i+1 upwards.
530                                 for ( brush_vector_t::const_iterator k( in.begin() ); !skip && k != in.end(); ++k )
531                                 {
532                                         if ( k != i ) { // don't test a brush against itself
533                                                 for ( Brush::const_iterator l( ( *k )->begin() ); !skip && l != ( *k )->end(); ++l )
534                                                 {
535                                                         const Face& face2 = *( *l );
536
537                                                         // face opposes another face
538                                                         if ( plane3_opposing( face1.plane3(), face2.plane3() ) ) {
539                                                                 // skip opposing planes
540                                                                 skip  = true;
541                                                                 break;
542                                                         }
543                                                 }
544                                         }
545                                 }
546
547                                 // check faces already stored
548                                 for ( Faces::const_iterator m = faces.begin(); !skip && m != faces.end(); ++m )
549                                 {
550                                         const Face& face2 = *( *m );
551
552                                         // face equals another face
553                                         if ( plane3_equal( face1.plane3(), face2.plane3() ) ) {
554                                                 //if the texture/shader references should be the same but are not
555                                                 if ( !onlyshape && !shader_equal( face1.getShader().getShader(), face2.getShader().getShader() ) ) {
556                                                         return false;
557                                                 }
558                                                 // skip duplicate planes
559                                                 skip = true;
560                                                 break;
561                                         }
562
563                                         // face1 plane intersects face2 winding or vice versa
564                                         if ( Winding_PlanesConcave( face1.getWinding(), face2.getWinding(), face1.plane3(), face2.plane3() ) ) {
565                                                 // result would not be convex
566                                                 return false;
567                                         }
568                                 }
569
570                                 if ( !skip ) {
571                                         faces.push_back( &face1 );
572                                 }
573                         }
574                 }
575                 for ( Faces::const_iterator i = faces.begin(); i != faces.end(); ++i )
576                 {
577                         if ( !brush.addFace( *( *i ) ) ) {
578                                 // result would have too many sides
579                                 return false;
580                         }
581                 }
582         }
583
584         brush.removeEmptyFaces();
585
586         return true;
587 }
588
589 void CSG_Merge( void ){
590         brush_vector_t selected_brushes;
591
592         // remove selected
593         GlobalSceneGraph().traverse( BrushGatherSelected( selected_brushes ) );
594
595         if ( selected_brushes.empty() ) {
596                 globalOutputStream() << "CSG Merge: No brushes selected.\n";
597                 return;
598         }
599
600         if ( selected_brushes.size() < 2 ) {
601                 globalOutputStream() << "CSG Merge: At least two brushes have to be selected.\n";
602                 return;
603         }
604
605         globalOutputStream() << "CSG Merge: Merging " << Unsigned( selected_brushes.size() ) << " brushes.\n";
606
607         UndoableCommand undo( "brushMerge" );
608
609         scene::Path merged_path = GlobalSelectionSystem().ultimateSelected().path();
610
611         NodeSmartReference node( ( new BrushNode() )->node() );
612         Brush* brush = Node_getBrush( node );
613         // if the new brush would not be convex
614         if ( !Brush_merge( *brush, selected_brushes, true ) ) {
615                 globalOutputStream() << "CSG Merge: Failed - result would not be convex.\n";
616         }
617         else
618         {
619                 ASSERT_MESSAGE( !brush->empty(), "brush left with no faces after merge" );
620
621                 // free the original brushes
622                 GlobalSceneGraph().traverse( BrushDeleteSelected() );
623
624                 merged_path.pop();
625                 Node_getTraversable( merged_path.top() )->insert( node );
626                 merged_path.push( makeReference( node.get() ) );
627
628                 selectPath( merged_path, true );
629
630                 globalOutputStream() << "CSG Merge: Succeeded.\n";
631                 SceneChangeNotify();
632         }
633 }