X-Git-Url: http://git.xonotic.org/?a=blobdiff_plain;f=radiant%2Fcsg.cpp;h=f28bdc98d202d0465f8bac6654f4e05b2abbfe4b;hb=f01b611436ae1403b915260c2c21473f4edef946;hp=5f50e7099de07e0bf926df6954a35e81dc0e9f1e;hpb=830125fad042fad35dc029b6eb57c8156ad7e176;p=xonotic%2Fnetradiant.git diff --git a/radiant/csg.cpp b/radiant/csg.cpp index 5f50e709..f28bdc98 100644 --- a/radiant/csg.cpp +++ b/radiant/csg.cpp @@ -1,5 +1,5 @@ /* - Copyright (C) 1999-2007 id Software, Inc. and contributors. + Copyright (C) 1999-2006 Id Software, Inc. and contributors. For a list of contributors, see the accompanying CONTRIBUTORS file. This file is part of GtkRadiant. @@ -19,610 +19,486 @@ Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ -#include "stdafx.h" -#include "winding.h" -#include "filters.h" +#include "csg.h" -/* - ============= - CSG_MakeHollow - ============= - */ +#include "debugging/debugging.h" -void Brush_Scale( brush_t* b ){ - for ( face_t* f = b->brush_faces ; f ; f = f->next ) - { - for ( int i = 0 ; i < 3 ; i++ ) - { - VectorScale( f->planepts[i], g_qeglobals.d_gridsize, f->planepts[i] ); - } - } -} - -void CSG_MakeHollow( void ){ - brush_t *b, *front, *back, *next; - face_t *f; - face_t split; - vec3_t move; - int i; +#include - for ( b = selected_brushes.next ; b != &selected_brushes ; b = next ) - { - next = b->next; +#include "map.h" +#include "brushmanip.h" +#include "brushnode.h" +#include "grid.h" - if ( b->owner->eclass->fixedsize || b->patchBrush || b->bFiltered ) { - continue; +void Face_makeBrush( Face& face, const Brush& brush, brush_vector_t& out, float offset ){ + if ( face.contributes() ) { + out.push_back( new Brush( brush ) ); + std::shared_ptr newFace = out.back()->addFace( face ); + if ( newFace != 0 ) { + newFace->flipWinding(); + newFace->getPlane().offset( offset ); + newFace->planeChanged(); } + } +} - for ( f = b->brush_faces ; f ; f = f->next ) - { - split = *f; - VectorScale( f->plane.normal, g_qeglobals.d_gridsize, move ); - for ( i = 0 ; i < 3 ; i++ ) - VectorSubtract( split.planepts[i], move, split.planepts[i] ); - - Brush_SplitBrushByFace( b, &split, &front, &back ); - if ( back ) { - Brush_Free( back ); - } - if ( front ) { - Brush_AddToList( front, &selected_brushes ); - } +void Face_makeRoom( Face &face, const Brush &brush, brush_vector_t &out, float offset ){ + if ( face.contributes() ) { + face.getPlane().offset( offset ); + out.push_back( new Brush( brush ) ); + face.getPlane().offset( -offset ); + std::shared_ptr newFace = out.back()->addFace( face ); + if ( newFace != 0 ) { + newFace->flipWinding(); + newFace->planeChanged(); } - Brush_Free( b ); } - Sys_UpdateWindows( W_ALL ); } -/* - ============= - Brush_Merge +void Brush_makeHollow( const Brush &brush, brush_vector_t &out, float offset ){ + Brush_forEachFace( brush, [&]( Face &face ) { + Face_makeBrush( face, brush, out, offset ); + } ); +} - Returns a new brush that is created by merging brush1 and brush2. - May return NULL if brush1 and brush2 do not create a convex brush when merged. - The input brushes brush1 and brush2 stay intact. +void Brush_makeRoom( const Brush &brush, brush_vector_t &out, float offset ){ + Brush_forEachFace( brush, [&]( Face &face ) { + Face_makeRoom( face, brush, out, offset ); + } ); +} - if onlyshape is true then the merge is allowed based on the shape only - otherwise the texture/shader references of faces in the same plane have to - be the same as well. - ============= - */ -brush_t *Brush_Merge( brush_t *brush1, brush_t *brush2, int onlyshape ){ - int i, shared; - brush_t *newbrush; - face_t *face1, *face2, *newface, *f; +class BrushHollowSelectedWalker : public scene::Graph::Walker +{ +float m_offset; +bool m_makeRoom; +public: +BrushHollowSelectedWalker( float offset, bool makeRoom ) + : m_offset( offset ), m_makeRoom( makeRoom ){ +} - // check for bounding box overlapp - for ( i = 0; i < 3; i++ ) - { - if ( brush1->mins[i] > brush2->maxs[i] + ON_EPSILON - || brush1->maxs[i] < brush2->mins[i] - ON_EPSILON ) { - // never merge if the brushes overlap - return NULL; - } - } - // - shared = 0; - // check if the new brush would be convex... flipped planes make a brush non-convex - for ( face1 = brush1->brush_faces; face1; face1 = face1->next ) - { - // don't check the faces of brush 1 and 2 touching each other - for ( face2 = brush2->brush_faces; face2; face2 = face2->next ) - { - if ( Plane_Equal( &face1->plane, &face2->plane, true ) ) { - shared++; - // there may only be ONE shared side - if ( shared > 1 ) { - return NULL; - } - break; +bool pre( const scene::Path& path, scene::Instance& instance ) const { + if ( path.top().get().visible() ) { + Brush* brush = Node_getBrush( path.top() ); + if ( brush != 0 + && Instance_getSelectable( instance )->isSelected() + && path.size() > 1 ) { + brush_vector_t out; + + if ( m_makeRoom ) { + Brush_makeRoom(* brush, out, m_offset ); } - } - // if this face plane is shared - if ( face2 ) { - continue; - } - // - for ( face2 = brush2->brush_faces; face2; face2 = face2->next ) - { - // don't check the faces of brush 1 and 2 touching each other - for ( f = brush1->brush_faces; f; f = f->next ) + else { - if ( Plane_Equal( &face2->plane, &f->plane, true ) ) { - break; - } - } - if ( f ) { - continue; - } - // - if ( Plane_Equal( &face1->plane, &face2->plane, false ) ) { - //if the texture/shader references should be the same but are not - if ( !onlyshape && stricmp( face1->texdef.GetName(), face2->texdef.GetName() ) != 0 ) { - return NULL; - } - continue; + Brush_makeHollow(* brush, out, m_offset ); } - // - if ( Winding_PlanesConcave( face1->face_winding, face2->face_winding, - face1->plane.normal, face2->plane.normal, - face1->plane.dist, face2->plane.dist ) ) { - return NULL; - } //end if - } //end for - } //end for - // - newbrush = Brush_Alloc(); - // - for ( face1 = brush1->brush_faces; face1; face1 = face1->next ) - { - // don't add the faces of brush 1 and 2 touching each other - for ( face2 = brush2->brush_faces; face2; face2 = face2->next ) - { - if ( Plane_Equal( &face1->plane, &face2->plane, true ) ) { - break; - } - } - if ( face2 ) { - continue; - } - // don't add faces with the same plane twice - for ( f = newbrush->brush_faces; f; f = f->next ) - { - if ( Plane_Equal( &face1->plane, &f->plane, false ) ) { - break; - } - if ( Plane_Equal( &face1->plane, &f->plane, true ) ) { - break; + + for ( brush_vector_t::const_iterator i = out.begin(); i != out.end(); ++i ) + { + ( *i )->removeEmptyFaces(); + NodeSmartReference node( ( new BrushNode() )->node() ); + Node_getBrush( node )->copy( *( *i ) ); + delete ( *i ); + Node_getTraversable( path.parent() )->insert( node ); } } - if ( f ) { - continue; - } - // - newface = Face_Alloc(); - newface->texdef = face1->texdef; - VectorCopy( face1->planepts[0], newface->planepts[0] ); - VectorCopy( face1->planepts[1], newface->planepts[1] ); - VectorCopy( face1->planepts[2], newface->planepts[2] ); - newface->plane = face1->plane; - newface->next = newbrush->brush_faces; - newbrush->brush_faces = newface; } - // - for ( face2 = brush2->brush_faces; face2; face2 = face2->next ) - { - // don't add the faces of brush 1 and 2 touching each other - for ( face1 = brush1->brush_faces; face1; face1 = face1->next ) - { - if ( Plane_Equal( &face2->plane, &face1->plane, true ) ) { - break; - } - } - if ( face1 ) { - continue; - } - // don't add faces with the same plane twice - for ( f = newbrush->brush_faces; f; f = f->next ) - { - if ( Plane_Equal( &face2->plane, &f->plane, false ) ) { - break; - } - if ( Plane_Equal( &face2->plane, &f->plane, true ) ) { - break; - } + return true; +} +}; + +typedef std::list brushlist_t; + +class BrushGatherSelected : public scene::Graph::Walker +{ +brush_vector_t& m_brushlist; +public: +BrushGatherSelected( brush_vector_t& brushlist ) + : m_brushlist( brushlist ){ +} + +bool pre( const scene::Path& path, scene::Instance& instance ) const { + if ( path.top().get().visible() ) { + Brush* brush = Node_getBrush( path.top() ); + if ( brush != 0 + && Instance_getSelectable( instance )->isSelected() ) { + m_brushlist.push_back( brush ); } - if ( f ) { - continue; + } + return true; +} +}; + +class BrushDeleteSelected : public scene::Graph::Walker +{ +public: +bool pre( const scene::Path& path, scene::Instance& instance ) const { + return true; +} +void post( const scene::Path& path, scene::Instance& instance ) const { + if ( path.top().get().visible() ) { + Brush* brush = Node_getBrush( path.top() ); + if ( brush != 0 + && Instance_getSelectable( instance )->isSelected() + && path.size() > 1 ) { + Path_deleteTop( path ); } - // - newface = Face_Alloc(); - newface->texdef = face2->texdef; - VectorCopy( face2->planepts[0], newface->planepts[0] ); - VectorCopy( face2->planepts[1], newface->planepts[1] ); - VectorCopy( face2->planepts[2], newface->planepts[2] ); - newface->plane = face2->plane; - newface->next = newbrush->brush_faces; - newbrush->brush_faces = newface; } - // link the new brush to an entity - Entity_LinkBrush( brush1->owner, newbrush ); - // build windings for the faces - Brush_BuildWindings( newbrush, false ); +} +}; - return newbrush; +void Scene_BrushMakeHollow_Selected( scene::Graph& graph, bool makeRoom ){ + GlobalSceneGraph().traverse( BrushHollowSelectedWalker( GetGridSize(), makeRoom ) ); + GlobalSceneGraph().traverse( BrushDeleteSelected() ); } /* ============= - Brush_MergeListPairs - - Returns a list with merged brushes. - Tries to merge brushes pair wise. - The input list is destroyed. - Input and output should be a single linked list using .next + CSG_MakeHollow ============= */ -brush_t *Brush_MergeListPairs( brush_t *brushlist, int onlyshape ){ - int nummerges, merged; - brush_t *b1, *b2, *tail, *newbrush, *newbrushlist; - brush_t *lastb2; - if ( !brushlist ) { - return NULL; - } +void CSG_MakeHollow( void ){ + UndoableCommand undo( "brushHollow" ); - nummerges = 0; - do - { - for ( tail = brushlist; tail; tail = tail->next ) - { - if ( !tail->next ) { - break; - } - } - merged = 0; - newbrushlist = NULL; - for ( b1 = brushlist; b1; b1 = brushlist ) - { - lastb2 = b1; - for ( b2 = b1->next; b2; b2 = b2->next ) - { - newbrush = Brush_Merge( b1, b2, onlyshape ); - if ( newbrush ) { - tail->next = newbrush; - lastb2->next = b2->next; - brushlist = brushlist->next; - b1->next = b1->prev = NULL; - b2->next = b2->prev = NULL; - Brush_Free( b1 ); - Brush_Free( b2 ); - for ( tail = brushlist; tail; tail = tail->next ) - { - if ( !tail->next ) { - break; - } - } //end for - merged++; - nummerges++; - break; - } - lastb2 = b2; - } - //if b1 can't be merged with any of the other brushes - if ( !b2 ) { - brushlist = brushlist->next; - //keep b1 - b1->next = newbrushlist; - newbrushlist = b1; - } - } - brushlist = newbrushlist; - } while ( merged ); - return newbrushlist; + Scene_BrushMakeHollow_Selected( GlobalSceneGraph(), false ); + + SceneChangeNotify(); } -/* - ============= - Brush_MergeList +void CSG_MakeRoom( void ){ + UndoableCommand undo( "brushRoom" ); - Tries to merge all brushes in the list into one new brush. - The input brush list stays intact. - Returns NULL if no merged brush can be created. - To create a new brush the brushes in the list may not overlap and - the outer faces of the brushes together should make a new convex brush. + Scene_BrushMakeHollow_Selected( GlobalSceneGraph(), true ); - if onlyshape is true then the merge is allowed based on the shape only - otherwise the texture/shader references of faces in the same plane have to - be the same as well. - ============= - */ -brush_t *Brush_MergeList( brush_t *brushlist, int onlyshape ){ - brush_t *brush1, *brush2, *brush3, *newbrush; - face_t *face1, *face2, *face3, *newface, *f; + SceneChangeNotify(); +} + +template +class RemoveReference +{ +public: +typedef Type type; +}; + +template +class RemoveReference +{ +public: +typedef Type type; +}; + +template +class Dereference +{ +const Functor& functor; +public: +Dereference( const Functor& functor ) : functor( functor ){ +} +get_result_type operator()( typename RemoveReference>::type *firstArgument ) const { + return functor( *firstArgument ); +} +}; + +template +inline Dereference makeDereference( const Functor& functor ){ + return Dereference( functor ); +} + +template +class BindArguments1 +{ +typedef get_argument FirstBound; +FirstBound firstBound; +public: +BindArguments1( FirstBound firstBound ) + : firstBound( firstBound ){ +} + +get_result_type operator()( get_argument firstArgument ) const { + return Caller::call( firstArgument, firstBound ); +} +}; + +template +class BindArguments2 +{ +typedef get_argument FirstBound; +typedef get_argument SecondBound; +FirstBound firstBound; +SecondBound secondBound; +public: +BindArguments2( FirstBound firstBound, SecondBound secondBound ) + : firstBound( firstBound ), secondBound( secondBound ){ +} + +get_result_type operator()( get_argument firstArgument ) const { + return Caller::call( firstArgument, firstBound, secondBound ); +} +}; + +template +BindArguments2 bindArguments( const Caller& caller, FirstBound firstBound, SecondBound secondBound ){ + return BindArguments2( firstBound, secondBound ); +} + +inline bool Face_testPlane( const Face& face, const Plane3& plane, bool flipped ){ + return face.contributes() && !Winding_TestPlane( face.getWinding(), plane, flipped ); +} - if ( !brushlist ) { - return NULL; +typedef Function FaceTestPlane; + + +/// \brief Returns true if +/// \li !flipped && brush is BACK or ON +/// \li flipped && brush is FRONT or ON +bool Brush_testPlane( const Brush& brush, const Plane3& plane, bool flipped ){ + brush.evaluateBRep(); + for ( Brush::const_iterator i( brush.begin() ); i != brush.end(); ++i ) + { + if ( Face_testPlane( *( *i ), plane, flipped ) ) { + return false; + } } - for ( brush1 = brushlist; brush1; brush1 = brush1->next ) + return true; +} + +brushsplit_t Brush_classifyPlane( const Brush& brush, const Plane3& plane ){ + brush.evaluateBRep(); + brushsplit_t split; + for ( Brush::const_iterator i( brush.begin() ); i != brush.end(); ++i ) { - // check if the new brush would be convex... flipped planes make a brush concave - for ( face1 = brush1->brush_faces; face1; face1 = face1->next ) + if ( ( *i )->contributes() ) { + split += Winding_ClassifyPlane( ( *i )->getWinding(), plane ); + } + } + return split; +} + +bool Brush_subtract( const Brush& brush, const Brush& other, brush_vector_t& ret_fragments ){ + if ( aabb_intersects_aabb( brush.localAABB(), other.localAABB() ) ) { + brush_vector_t fragments; + fragments.reserve( other.size() ); + Brush back( brush ); + + for ( const std::shared_ptr& b : other ) { - // don't check face1 if it touches another brush - for ( brush2 = brushlist; brush2; brush2 = brush2->next ) - { - if ( brush2 == brush1 ) { - continue; - } - for ( face2 = brush2->brush_faces; face2; face2 = face2->next ) - { - if ( Plane_Equal( &face1->plane, &face2->plane, true ) ) { - break; + if ( b->contributes() ) { + brushsplit_t split = Brush_classifyPlane( back, b->plane3() ); + if ( split.counts[ePlaneFront] != 0 + && split.counts[ePlaneBack] != 0 ) { + fragments.push_back( new Brush( back ) ); + std::shared_ptr newFace = fragments.back()->addFace( *b ); + if ( newFace != nullptr ) { + newFace->flipWinding(); } + back.addFace( *b ); } - if ( face2 ) { - break; + else if ( split.counts[ePlaneBack] == 0 ) { + for ( Brush *i : fragments ) { + delete( i ); + } + fragments.clear(); + return false; } } - // if face1 touches another brush - if ( brush2 ) { - continue; - } - // - for ( brush2 = brush1->next; brush2; brush2 = brush2->next ) + } + ret_fragments.insert( ret_fragments.end(), fragments.begin(), fragments.end() ); + return true; + } + return false; +} + +class SubtractBrushesFromUnselected : public scene::Graph::Walker +{ +const brush_vector_t& m_brushlist; +std::size_t& m_before; +std::size_t& m_after; +public: +SubtractBrushesFromUnselected( const brush_vector_t& brushlist, std::size_t& before, std::size_t& after ) + : m_brushlist( brushlist ), m_before( before ), m_after( after ){ +} + +bool pre( const scene::Path& path, scene::Instance& instance ) const { + return true; +} + +void post( const scene::Path& path, scene::Instance& instance ) const { + if ( path.top().get().visible() ) { + Brush* brush = Node_getBrush( path.top() ); + if ( brush != 0 + && !Instance_getSelectable( instance )->isSelected() ) { + brush_vector_t buffer[2]; + bool swap = false; + Brush* original = new Brush( *brush ); + buffer[static_cast( swap )].push_back( original ); + { - // don't check the faces of brush 2 touching another brush - for ( face2 = brush2->brush_faces; face2; face2 = face2->next ) + for ( brush_vector_t::const_iterator i( m_brushlist.begin() ); i != m_brushlist.end(); ++i ) { - for ( brush3 = brushlist; brush3; brush3 = brush3->next ) + for ( brush_vector_t::iterator j( buffer[static_cast( swap )].begin() ); j != buffer[static_cast( swap )].end(); ++j ) { - if ( brush3 == brush2 ) { - continue; + if ( Brush_subtract( *( *j ), *( *i ), buffer[static_cast( !swap )] ) ) { + delete ( *j ); } - for ( face3 = brush3->brush_faces; face3; face3 = face3->next ) + else { - if ( Plane_Equal( &face2->plane, &face3->plane, true ) ) { - break; - } - } - if ( face3 ) { - break; + buffer[static_cast( !swap )].push_back( ( *j ) ); } } - // if face2 touches another brush - if ( brush3 ) { - continue; - } - // - if ( Plane_Equal( &face1->plane, &face2->plane, false ) ) { - //if the texture/shader references should be the same but are not - if ( !onlyshape && stricmp( face1->texdef.GetName(), face2->texdef.GetName() ) != 0 ) { - return NULL; - } - continue; - } - // - if ( Winding_PlanesConcave( face1->face_winding, face2->face_winding, - face1->plane.normal, face2->plane.normal, - face1->plane.dist, face2->plane.dist ) ) { - return NULL; - } + buffer[static_cast( swap )].clear(); + swap = !swap; } } - } - } - // - newbrush = Brush_Alloc(); - // - for ( brush1 = brushlist; brush1; brush1 = brush1->next ) - { - for ( face1 = brush1->brush_faces; face1; face1 = face1->next ) - { - // don't add face1 to the new brush if it touches another brush - for ( brush2 = brushlist; brush2; brush2 = brush2->next ) - { - if ( brush2 == brush1 ) { - continue; - } - for ( face2 = brush2->brush_faces; face2; face2 = face2->next ) - { - if ( Plane_Equal( &face1->plane, &face2->plane, true ) ) { - break; - } - } - if ( face2 ) { - break; - } - } - if ( brush2 ) { - continue; + + brush_vector_t& out = buffer[static_cast( swap )]; + + if ( out.size() == 1 && out.back() == original ) { + delete original; } - // don't add faces with the same plane twice - for ( f = newbrush->brush_faces; f; f = f->next ) + else { - if ( Plane_Equal( &face1->plane, &f->plane, false ) ) { - break; - } - if ( Plane_Equal( &face1->plane, &f->plane, true ) ) { - break; + ++m_before; + for ( Brush *b : out ) { + ++m_after; + b->removeEmptyFaces(); + if ( !b->empty() ) { + NodeSmartReference node( ( new BrushNode() )->node() ); + Node_getBrush( node )->copy( *b ); + Node_getTraversable( path.parent() )->insert( node ); + } + delete b; } + Path_deleteTop( path ); } - if ( f ) { - continue; - } - // - newface = Face_Alloc(); - newface->texdef = face1->texdef; - VectorCopy( face1->planepts[0], newface->planepts[0] ); - VectorCopy( face1->planepts[1], newface->planepts[1] ); - VectorCopy( face1->planepts[2], newface->planepts[2] ); - newface->plane = face1->plane; - newface->next = newbrush->brush_faces; - newbrush->brush_faces = newface; } } - // link the new brush to an entity - Entity_LinkBrush( brushlist->owner, newbrush ); - // build windings for the faces - Brush_BuildWindings( newbrush, false ); - - return newbrush; } +}; -/* - ============= - Brush_Subtract +void CSG_Subtract(){ + brush_vector_t selected_brushes; + GlobalSceneGraph().traverse( BrushGatherSelected( selected_brushes ) ); - Returns a list of brushes that remain after B is subtracted from A. - May by empty if A is contained inside B. - The originals are undisturbed. - ============= - */ -brush_t *Brush_Subtract( brush_t *a, brush_t *b ){ - // a - b = out (list) - brush_t *front, *back; - brush_t *in, *out, *next; - face_t *f; - - in = a; - out = NULL; - for ( f = b->brush_faces; f && in; f = f->next ) - { - Brush_SplitBrushByFace( in, f, &front, &back ); - if ( in != a ) { - Brush_Free( in ); - } - if ( front ) { // add to list - front->next = out; - out = front; - } - in = back; - } - //NOTE: in != a just in case brush b has no faces - if ( in && in != a ) { - Brush_Free( in ); - } - else - { //didn't really intersect - for ( b = out; b; b = next ) - { - next = b->next; - b->next = b->prev = NULL; - Brush_Free( b ); - } - return a; + if ( selected_brushes.empty() ) { + globalOutputStream() << "CSG Subtract: No brushes selected.\n"; + } else { + globalOutputStream() << "CSG Subtract: Subtracting " << Unsigned( selected_brushes.size() ) << " brushes.\n"; + + UndoableCommand undo( "brushSubtract" ); + + // subtract selected from unselected + std::size_t before = 0; + std::size_t after = 0; + GlobalSceneGraph().traverse( SubtractBrushesFromUnselected( selected_brushes, before, after ) ); + globalOutputStream() << "CSG Subtract: Result: " + << Unsigned( after ) << " fragment" << ( after == 1 ? "" : "s" ) + << " from " << Unsigned( before ) << " brush" << ( before == 1 ? "" : "es" ) << ".\n"; + + SceneChangeNotify(); } - return out; } -/* - ============= - CSG_Subtract - ============= - */ -void CSG_Subtract( void ){ - brush_t *b, *s, *fragments, *nextfragment, *frag, *next, *snext; - brush_t fragmentlist; - int i, numfragments, numbrushes; +class BrushSplitByPlaneSelected : public scene::Graph::Walker +{ +const Vector3& m_p0; +const Vector3& m_p1; +const Vector3& m_p2; +const char* m_shader; +const TextureProjection& m_projection; +EBrushSplit m_split; +public: +BrushSplitByPlaneSelected( const Vector3& p0, const Vector3& p1, const Vector3& p2, const char* shader, const TextureProjection& projection, EBrushSplit split ) + : m_p0( p0 ), m_p1( p1 ), m_p2( p2 ), m_shader( shader ), m_projection( projection ), m_split( split ){ +} - Sys_Printf( "Subtracting...\n" ); +bool pre( const scene::Path& path, scene::Instance& instance ) const { + return true; +} - if ( selected_brushes.next == &selected_brushes ) { - Sys_Printf( "No brushes selected.\n" ); +void post( const scene::Path& path, scene::Instance& instance ) const { + if ( !path.top().get().visible() ) { return; } - fragmentlist.next = &fragmentlist; - fragmentlist.prev = &fragmentlist; - - numfragments = 0; - numbrushes = 0; - for ( b = selected_brushes.next ; b != &selected_brushes ; b = next ) - { - next = b->next; - - if ( b->owner->eclass->fixedsize ) { - continue; // can't use texture from a fixed entity, so don't subtract + Brush* brush = Node_getBrush( path.top() ); + if ( brush == nullptr || !Instance_getSelectable( instance )->isSelected() ) { + return; + } - } - // chop all fragments further up - for ( s = fragmentlist.next; s != &fragmentlist; s = snext ) - { - snext = s->next; + Plane3 plane( plane3_for_points( m_p0, m_p1, m_p2 ) ); + if ( !plane3_valid( plane ) ) { + return; + } - for ( i = 0 ; i < 3 ; i++ ) - if ( b->mins[i] >= s->maxs[i] - ON_EPSILON - || b->maxs[i] <= s->mins[i] + ON_EPSILON ) { - break; - } - if ( i != 3 ) { - continue; // definately don't touch - } - fragments = Brush_Subtract( s, b ); - // if the brushes did not really intersect - if ( fragments == s ) { - continue; + brushsplit_t split = Brush_classifyPlane( *brush, m_split == eFront ? plane3_flipped( plane ) : plane ); + if ( split.counts[ePlaneBack] && split.counts[ePlaneFront] ) { + // the plane intersects this brush + if ( m_split == eFrontAndBack ) { + NodeSmartReference node( ( new BrushNode() )->node() ); + Brush* fragment = Node_getBrush( node ); + fragment->copy( *brush ); + std::shared_ptr newFace = + fragment->addPlane( m_p0, m_p1, m_p2, m_shader, m_projection ); + if ( newFace != 0 && m_split != eFront ) { + newFace->flipWinding(); } - // try to merge fragments - fragments = Brush_MergeListPairs( fragments, true ); - // add the fragments to the list - for ( frag = fragments; frag; frag = nextfragment ) + fragment->removeEmptyFaces(); + ASSERT_MESSAGE( !fragment->empty(), "brush left with no faces after split" ); + + Node_getTraversable( path.parent() )->insert( node ); { - nextfragment = frag->next; - frag->next = NULL; - frag->owner = s->owner; - Brush_AddToList( frag, &fragmentlist ); + scene::Path fragmentPath = path; + fragmentPath.top() = makeReference( node.get() ); + selectPath( fragmentPath, true ); } - // free the original brush - Brush_Free( s ); } - // chop any active brushes up - for ( s = active_brushes.next; s != &active_brushes; s = snext ) - { - snext = s->next; - - if ( s->owner->eclass->fixedsize || s->patchBrush || s->bFiltered ) { - continue; - } + std::shared_ptr newFace = brush->addPlane( m_p0, m_p1, m_p2, m_shader, m_projection ); + if ( newFace != 0 && m_split == eFront ) { + newFace->flipWinding(); + } + brush->removeEmptyFaces(); + ASSERT_MESSAGE( !brush->empty(), "brush left with no faces after split" ); + } + else + // the plane does not intersect this brush + if ( m_split != eFrontAndBack && split.counts[ePlaneBack] != 0 ) { + // the brush is "behind" the plane + Path_deleteTop( path ); + } +} +}; - if ( s->brush_faces->pShader->getFlags() & QER_NOCARVE ) { - continue; - } +void Scene_BrushSplitByPlane( scene::Graph& graph, const Vector3& p0, const Vector3& p1, const Vector3& p2, const char* shader, EBrushSplit split ){ + TextureProjection projection; + TexDef_Construct_Default( projection ); + graph.traverse( BrushSplitByPlaneSelected( p0, p1, p2, shader, projection, split ) ); + SceneChangeNotify(); +} - for ( i = 0 ; i < 3 ; i++ ) - if ( b->mins[i] >= s->maxs[i] - ON_EPSILON - || b->maxs[i] <= s->mins[i] + ON_EPSILON ) { - break; - } - if ( i != 3 ) { - continue; // definately don't touch - } - fragments = Brush_Subtract( s, b ); - // if the brushes did not really intersect - if ( fragments == s ) { - continue; - } - // - Undo_AddBrush( s ); - // one extra brush chopped up - numbrushes++; - // try to merge fragments - fragments = Brush_MergeListPairs( fragments, true ); - // add the fragments to the list - for ( frag = fragments; frag; frag = nextfragment ) - { - nextfragment = frag->next; - frag->next = NULL; - frag->owner = s->owner; - Brush_AddToList( frag, &fragmentlist ); - } - // free the original brush - Brush_Free( s ); - } - } +class BrushInstanceSetClipPlane : public scene::Graph::Walker +{ +Plane3 m_plane; +public: +BrushInstanceSetClipPlane( const Plane3& plane ) + : m_plane( plane ){ +} - // move all fragments to the active brush list - for ( frag = fragmentlist.next; frag != &fragmentlist; frag = nextfragment ) - { - nextfragment = frag->next; - numfragments++; - Brush_RemoveFromList( frag ); - Brush_AddToList( frag, &active_brushes ); - Undo_EndBrush( frag ); +bool pre( const scene::Path& path, scene::Instance& instance ) const { + BrushInstance* brush = Instance_getBrush( instance ); + if ( brush != 0 + && path.top().get().visible() + && brush->isSelected() ) { + BrushInstance& brushInstance = *brush; + brushInstance.setClipPlane( m_plane ); } + return true; +} +}; - /*if (numfragments == 0) - { - Sys_Printf("Selected brush%s did not intersect with any other brushes.\n", - (selected_brushes.next->next == &selected_brushes) ? "":"es"); - return; - }*/ - Sys_Printf( "done. (created %d fragment%s out of %d brush%s)\n", numfragments, ( numfragments == 1 ) ? "" : "s", - numbrushes, ( numbrushes == 1 ) ? "" : "es" ); - Sys_UpdateWindows( W_ALL ); +void Scene_BrushSetClipPlane( scene::Graph& graph, const Plane3& plane ){ + graph.traverse( BrushInstanceSetClipPlane( plane ) ); } /* @@ -630,93 +506,127 @@ void CSG_Subtract( void ){ CSG_Merge ============= */ -void CSG_Merge( void ){ - brush_t *b, *next, *newlist, *newbrush; - struct entity_s *owner; +bool Brush_merge( Brush& brush, const brush_vector_t& in, bool onlyshape ){ + // gather potential outer faces - Sys_Printf( "Merging...\n" ); + { + typedef std::vector Faces; + Faces faces; + for ( brush_vector_t::const_iterator i( in.begin() ); i != in.end(); ++i ) + { + ( *i )->evaluateBRep(); + for ( Brush::const_iterator j( ( *i )->begin() ); j != ( *i )->end(); ++j ) + { + if ( !( *j )->contributes() ) { + continue; + } - if ( selected_brushes.next == &selected_brushes ) { - Sys_Printf( "No brushes selected.\n" ); - return; - } + const Face& face1 = *( *j ); - if ( selected_brushes.next->next == &selected_brushes ) { - Sys_Printf( "At least two brushes have to be selected.\n" ); - return; - } + bool skip = false; + // test faces of all input brushes + //!\todo SPEEDUP: Flag already-skip faces and only test brushes from i+1 upwards. + for ( brush_vector_t::const_iterator k( in.begin() ); !skip && k != in.end(); ++k ) + { + if ( k != i ) { // don't test a brush against itself + for ( Brush::const_iterator l( ( *k )->begin() ); !skip && l != ( *k )->end(); ++l ) + { + const Face& face2 = *( *l ); - owner = selected_brushes.next->owner; + // face opposes another face + if ( plane3_opposing( face1.plane3(), face2.plane3() ) ) { + // skip opposing planes + skip = true; + break; + } + } + } + } - for ( b = selected_brushes.next; b != &selected_brushes; b = next ) - { - next = b->next; + // check faces already stored + for ( Faces::const_iterator m = faces.begin(); !skip && m != faces.end(); ++m ) + { + const Face& face2 = *( *m ); - if ( b->owner->eclass->fixedsize ) { - // can't use texture from a fixed entity, so don't subtract - Sys_Printf( "Cannot add fixed size entities.\n" ); - return; - } + // face equals another face + if ( plane3_equal( face1.plane3(), face2.plane3() ) ) { + //if the texture/shader references should be the same but are not + if ( !onlyshape && !shader_equal( face1.getShader().getShader(), face2.getShader().getShader() ) ) { + return false; + } + // skip duplicate planes + skip = true; + break; + } - if ( b->patchBrush ) { - Sys_Printf( "Cannot add patches.\n" ); - return; - } + // face1 plane intersects face2 winding or vice versa + if ( Winding_PlanesConcave( face1.getWinding(), face2.getWinding(), face1.plane3(), face2.plane3() ) ) { + // result would not be convex + return false; + } + } - // TTimo: cleanup - // disable the qer_nocarve for CSG-MERGE operations -#if 0 - if ( b->brush_faces->d_texture->bFromShader && ( b->brush_faces->d_texture->nShaderFlags & QER_NOCARVE ) ) { - Sys_Printf( "Cannot add brushes using shaders that don't allows CSG operations.\n" ); - return; + if ( !skip ) { + faces.push_back( &face1 ); + } + } } -#endif - - if ( b->owner != owner ) { - Sys_Printf( "Cannot add brushes from different entities.\n" ); - return; + for ( Faces::const_iterator i = faces.begin(); i != faces.end(); ++i ) + { + if ( !brush.addFace( *( *i ) ) ) { + // result would have too many sides + return false; + } } - } - newlist = NULL; - for ( b = selected_brushes.next; b != &selected_brushes; b = next ) - { - next = b->next; + brush.removeEmptyFaces(); + + return true; +} - Brush_RemoveFromList( b ); - b->next = newlist; - b->prev = NULL; - newlist = b; +void CSG_Merge( void ){ + brush_vector_t selected_brushes; + + // remove selected + GlobalSceneGraph().traverse( BrushGatherSelected( selected_brushes ) ); + + if ( selected_brushes.empty() ) { + globalOutputStream() << "CSG Merge: No brushes selected.\n"; + return; } - newbrush = Brush_MergeList( newlist, true ); - // if the new brush would not be convex - if ( !newbrush ) { - // add the brushes back into the selection - for ( b = newlist; b; b = next ) - { - next = b->next; - b->next = NULL; - b->prev = NULL; - Brush_AddToList( b, &selected_brushes ); - } - Sys_Printf( "Cannot add a set of brushes with a concave hull.\n" ); + if ( selected_brushes.size() < 2 ) { + globalOutputStream() << "CSG Merge: At least two brushes have to be selected.\n"; return; } - // free the original brushes - for ( b = newlist; b; b = next ) - { - next = b->next; - b->next = NULL; - b->prev = NULL; - Brush_Free( b ); + + globalOutputStream() << "CSG Merge: Merging " << Unsigned( selected_brushes.size() ) << " brushes.\n"; + + UndoableCommand undo( "brushMerge" ); + + scene::Path merged_path = GlobalSelectionSystem().ultimateSelected().path(); + + NodeSmartReference node( ( new BrushNode() )->node() ); + Brush* brush = Node_getBrush( node ); + // if the new brush would not be convex + if ( !Brush_merge( *brush, selected_brushes, true ) ) { + globalOutputStream() << "CSG Merge: Failed - result would not be convex.\n"; } + else + { + ASSERT_MESSAGE( !brush->empty(), "brush left with no faces after merge" ); - newbrush->bFiltered = FilterBrush( newbrush ); // spog - set filters for the new brush + // free the original brushes + GlobalSceneGraph().traverse( BrushDeleteSelected() ); - Brush_AddToList( newbrush, &selected_brushes ); + merged_path.pop(); + Node_getTraversable( merged_path.top() )->insert( node ); + merged_path.push( makeReference( node.get() ) ); - Sys_Printf( "done.\n" ); - Sys_UpdateWindows( W_ALL ); + selectPath( merged_path, true ); + + globalOutputStream() << "CSG Merge: Succeeded.\n"; + SceneChangeNotify(); + } }