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