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