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