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