X-Git-Url: https://de.git.xonotic.org/?a=blobdiff_plain;f=radiant%2Fcsg.cpp;h=f28bdc98d202d0465f8bac6654f4e05b2abbfe4b;hb=fda66ae00e9a2ab6d3ebaede13b12fa6767cf856;hp=f5da8b74e65a712d19e2fdba49ebdf9a0adefba6;hpb=b1bfb19ecd5ec8355065b2028a6de0c850197b2d;p=xonotic%2Fnetradiant.git diff --git a/radiant/csg.cpp b/radiant/csg.cpp index f5da8b74..f28bdc98 100644 --- a/radiant/csg.cpp +++ b/radiant/csg.cpp @@ -1,687 +1,632 @@ /* -Copyright (C) 1999-2007 id Software, Inc. and contributors. -For a list of contributors, see the accompanying CONTRIBUTORS file. + 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. + This file is part of GtkRadiant. -GtkRadiant is free software; you can redistribute it and/or modify -it under the terms of the GNU General Public License as published by -the Free Software Foundation; either version 2 of the License, or -(at your option) any later version. + GtkRadiant is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. -GtkRadiant is distributed in the hope that it will be useful, -but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -GNU General Public License for more details. + GtkRadiant is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. -You should have received a copy of the GNU General Public License -along with GtkRadiant; if not, write to the Free Software -Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA -*/ + You should have received a copy of the GNU General Public License + along with GtkRadiant; if not, write to the Free Software + 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 -============= -*/ - -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]); - } - } -} +#include "debugging/debugging.h" -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 - - 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. - - 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) +void Brush_makeHollow( const Brush &brush, brush_vector_t &out, float offset ){ + Brush_forEachFace( brush, [&]( Face &face ) { + Face_makeBrush( face, brush, out, offset ); + } ); +} + +void Brush_makeRoom( const Brush &brush, brush_vector_t &out, float offset ){ + Brush_forEachFace( brush, [&]( Face &face ) { + Face_makeRoom( face, brush, out, offset ); + } ); +} + +class BrushHollowSelectedWalker : public scene::Graph::Walker { - int i, shared; - brush_t *newbrush; - face_t *face1, *face2, *newface, *f; +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; + Brush_makeHollow(* brush, out, m_offset ); } - if (f) - continue; - // - if (Plane_Equal(&face1->plane, &face2->plane, false)) + + for ( brush_vector_t::const_iterator i = out.begin(); i != out.end(); ++i ) { - //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; + ( *i )->removeEmptyFaces(); + NodeSmartReference node( ( new BrushNode() )->node() ); + Node_getBrush( node )->copy( *( *i ) ); + delete ( *i ); + Node_getTraversable( path.parent() )->insert( node ); } - // - 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; } - 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; + 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 (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; +} +}; + +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 ); } - if (f) - continue; - // - 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 -============= -*/ -brush_t *Brush_MergeListPairs(brush_t *brushlist, int onlyshape) + ============= + CSG_MakeHollow + ============= + */ + +void CSG_MakeHollow( void ){ + UndoableCommand undo( "brushHollow" ); + + Scene_BrushMakeHollow_Selected( GlobalSceneGraph(), false ); + + SceneChangeNotify(); +} + +void CSG_MakeRoom( void ){ + UndoableCommand undo( "brushRoom" ); + + Scene_BrushMakeHollow_Selected( GlobalSceneGraph(), true ); + + SceneChangeNotify(); +} + +template +class RemoveReference +{ +public: +typedef Type type; +}; + +template +class RemoveReference +{ +public: +typedef Type type; +}; + +template +class Dereference { - int nummerges, merged; - brush_t *b1, *b2, *tail, *newbrush, *newbrushlist; - brush_t *lastb2; +const Functor& functor; +public: +Dereference( const Functor& functor ) : functor( functor ){ +} +get_result_type operator()( typename RemoveReference>::type *firstArgument ) const { + return functor( *firstArgument ); +} +}; - if (!brushlist) return NULL; +template +inline Dereference makeDereference( const Functor& functor ){ + return Dereference( functor ); +} - nummerges = 0; - do +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 ); +} + +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 ) { - for (tail = brushlist; tail; tail = tail->next) - { - if (!tail->next) break; + if ( Face_testPlane( *( *i ), plane, flipped ) ) { + return false; } - 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; - } + } + 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 ) + { + if ( ( *i )->contributes() ) { + split += Winding_ClassifyPlane( ( *i )->getWinding(), plane ); } - brushlist = newbrushlist; - } while(merged); - return newbrushlist; + } + return split; } -/* -============= -Brush_MergeList - - 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. - - 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; +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 ); - if (!brushlist) return NULL; - for (brush1 = brushlist; brush1; brush1 = brush1->next) - { - // check if the new brush would be convex... flipped planes make a brush concave - for (face1 = brush1->brush_faces; face1; face1 = face1->next) + 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; - } - // if face1 touches another brush - if (brush2) continue; - // - for (brush2 = brush1->next; brush2; brush2 = brush2->next) - { - // don't check the faces of brush 2 touching another brush - for (face2 = brush2->brush_faces; face2; face2 = face2->next) - { - for (brush3 = brushlist; brush3; brush3 = brush3->next) - { - if (brush3 == brush2) continue; - for (face3 = brush3->brush_faces; face3; face3 = face3->next) - { - if (Plane_Equal(&face2->plane, &face3->plane, true)) break; - } - if (face3) break; - } - // 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; + else if ( split.counts[ePlaneBack] == 0 ) { + for ( Brush *i : fragments ) { + delete( i ); } + fragments.clear(); + return false; } } } + ret_fragments.insert( ret_fragments.end(), fragments.begin(), fragments.end() ); + return true; } - // - 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) + 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 ); + { - if (brush2 == brush1) continue; - for (face2 = brush2->brush_faces; face2; face2 = face2->next) + for ( brush_vector_t::const_iterator i( m_brushlist.begin() ); i != m_brushlist.end(); ++i ) { - if (Plane_Equal(&face1->plane, &face2->plane, true)) + for ( brush_vector_t::iterator j( buffer[static_cast( swap )].begin() ); j != buffer[static_cast( swap )].end(); ++j ) { - break; + if ( Brush_subtract( *( *j ), *( *i ), buffer[static_cast( !swap )] ) ) { + delete ( *j ); + } + else + { + buffer[static_cast( !swap )].push_back( ( *j ) ); + } } + buffer[static_cast( swap )].clear(); + swap = !swap; } - if (face2) break; } - if (brush2) continue; - // don't add faces with the same plane twice - for (f = newbrush->brush_faces; f; f = f->next) + + brush_vector_t& out = buffer[static_cast( swap )]; + + if ( out.size() == 1 && out.back() == original ) { + delete original; + } + 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 - - 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; +void CSG_Subtract(){ + brush_vector_t selected_brushes; + GlobalSceneGraph().traverse( BrushGatherSelected( selected_brushes ) ); + + 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) +class BrushSplitByPlaneSelected : public scene::Graph::Walker { - brush_t *b, *s, *fragments, *nextfragment, *frag, *next, *snext; - brush_t fragmentlist; - int i, numfragments, numbrushes; +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; + Brush* brush = Node_getBrush( path.top() ); + if ( brush == nullptr || !Instance_getSelectable( instance )->isSelected() ) { + return; + } - numfragments = 0; - numbrushes = 0; - for (b = selected_brushes.next ; b != &selected_brushes ; b=next) - { - next = b->next; + Plane3 plane( plane3_for_points( m_p0, m_p1, m_p2 ) ); + if ( !plane3_valid( plane ) ) { + return; + } - if (b->owner->eclass->fixedsize) - continue; // can't use texture from a fixed entity, so don't subtract + 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(); + } + fragment->removeEmptyFaces(); + ASSERT_MESSAGE( !fragment->empty(), "brush left with no faces after split" ); - // chop all fragments further up - for (s = fragmentlist.next; s != &fragmentlist; s = snext) - { - snext = s->next; - - 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; - // try to merge fragments - fragments = Brush_MergeListPairs(fragments, true); - // add the fragments to the list - for (frag = fragments; frag; frag = nextfragment) + 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; + 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->owner->eclass->fixedsize || s->patchBrush || s->bFiltered) - 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(); +} - if (s->brush_faces->pShader->getFlags() & QER_NOCARVE) - { - continue; - } - 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 ) ); } /* -============= -CSG_Merge -============= -*/ -void CSG_Merge(void) -{ - brush_t *b, *next, *newlist, *newbrush; - struct entity_s *owner; - - Sys_Printf ("Merging...\n"); + ============= + CSG_Merge + ============= + */ +bool Brush_merge( Brush& brush, const brush_vector_t& in, bool onlyshape ){ + // gather potential outer faces - if (selected_brushes.next == &selected_brushes) { - Sys_Printf("No brushes selected.\n"); - return; - } + 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->next == &selected_brushes) - { - Sys_Printf("At least two brushes have to be selected.\n"); - return; - } + const Face& face1 = *( *j ); - owner = selected_brushes.next->owner; + 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 ); + + // 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) + for ( Faces::const_iterator i = faces.begin(); i != faces.end(); ++i ) { - Sys_Printf("Cannot add brushes from different entities.\n"); - return; + 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; +} + +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; + } - Brush_RemoveFromList(b); - b->next = newlist; - b->prev = NULL; - newlist = b; + if ( selected_brushes.size() < 2 ) { + globalOutputStream() << "CSG Merge: At least two brushes have to be selected.\n"; + return; } - newbrush = Brush_MergeList(newlist, true); + 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 (!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"); - return; + if ( !Brush_merge( *brush, selected_brushes, true ) ) { + globalOutputStream() << "CSG Merge: Failed - result would not be convex.\n"; } - // free the original brushes - for (b = newlist; b; b = next) + else { - next = b->next; - b->next = NULL; - b->prev = NULL; - Brush_Free(b); - } + ASSERT_MESSAGE( !brush->empty(), "brush left with no faces after merge" ); + + // free the original brushes + GlobalSceneGraph().traverse( BrushDeleteSelected() ); - newbrush->bFiltered = FilterBrush(newbrush); // spog - set filters for the new brush + merged_path.pop(); + Node_getTraversable( merged_path.top() )->insert( node ); + merged_path.push( makeReference( node.get() ) ); - Brush_AddToList(newbrush, &selected_brushes); + selectPath( merged_path, true ); - Sys_Printf ("done.\n"); - Sys_UpdateWindows (W_ALL); + globalOutputStream() << "CSG Merge: Succeeded.\n"; + SceneChangeNotify(); + } }