/*
   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.

   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.

   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 "csg.h"

#include "debugging/debugging.h"

#include <list>

#include "map.h"
#include "brushmanip.h"
#include "brushnode.h"
#include "grid.h"

/*
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<Face> newFace = out.back()->addFace( face );
		face.getPlane().offset( -offset );
		face.planeChanged();
		if ( newFace != 0 ) {
			newFace->flipWinding();
			newFace->getPlane().offset( offset );
			newFace->planeChanged();
		}
	}
}

void Face_extrude( 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<Face> newFace = out.back()->addFace( face );
		if ( newFace != 0 ) {
			newFace->flipWinding();
			newFace->planeChanged();
		}
	}
}
*/
#include "preferences.h"
#include "texwindow.h"


enum eHollowType
{
	diag = 0,
	wrap = 1,
	extrude = 2,
	pull = 3,
	room = 4,
};

const char* getCaulkShader(){
	const char* gotShader = g_pGameDescription->getKeyValue( "shader_caulk" );
	if ( gotShader && *gotShader ){
		return gotShader;
	}
	return "textures/common/caulk";
}

class CaulkFace
{
DoubleVector3 ExclusionAxis;
double &mindot;
double &maxdot;
public:
CaulkFace( DoubleVector3 ExclusionAxis,
			double &mindot,
			double &maxdot ):
			ExclusionAxis( ExclusionAxis ),
			mindot( mindot ),
			maxdot( maxdot ){}
void operator()( Face& face ) const {
	double dot = vector3_dot( face.getPlane().plane3().normal(), ExclusionAxis );
	if( dot == 0 || ( dot > mindot + 0.005 && dot < maxdot - 0.005 ) )
		face.SetShader( getCaulkShader() );
}
};

class FaceMakeBrush
{
const Brush& brush;
brush_vector_t& out;
float offset;
eHollowType HollowType;
DoubleVector3 ExclusionAxis;
double &mindot;
double &maxdot;
bool caulk;
bool RemoveInner;
public:
FaceMakeBrush( const Brush& brush,
			brush_vector_t& out,
			float offset,
			eHollowType HollowType,
			DoubleVector3 ExclusionAxis,
			double &mindot,
			double &maxdot,
			bool caulk,
			bool RemoveInner )
	: brush( brush ),
	out( out ),
	offset( offset ),
	HollowType( HollowType ),
	ExclusionAxis( ExclusionAxis ),
	mindot( mindot ),
	maxdot( maxdot ),
	caulk( caulk ),
	RemoveInner( RemoveInner ){
}
void operator()( Face& face ) const {
	double dot = vector3_dot( face.getPlane().plane3().normal(), ExclusionAxis );
	if( dot == 0 || ( dot > mindot + 0.005 && dot < maxdot - 0.005 ) ){
		if( HollowType == pull ){
			if ( face.contributes() ) {
				face.getPlane().offset( offset );
				face.planeChanged();
				out.push_back( new Brush( brush ) );
				face.getPlane().offset( -offset );
				face.planeChanged();

				if( caulk ){
					Brush_forEachFace( *out.back(), CaulkFace( ExclusionAxis, mindot, maxdot ) );
				}
				std::shared_ptr<Face> newFace = out.back()->addFace( face );
				if ( newFace != 0 ) {
					newFace->flipWinding();
				}
			}
		}
		else if( HollowType == wrap ){
			//Face_makeBrush( face, brush, out, offset );
			if ( face.contributes() ) {
				face.undoSave();
				out.push_back( new Brush( brush ) );
				if( !RemoveInner && caulk )
					face.SetShader( getCaulkShader() );
				std::shared_ptr<Face> newFace = out.back()->addFace( face );
				face.getPlane().offset( -offset );
				face.planeChanged();
				if( caulk )
					face.SetShader( getCaulkShader() );
				if ( newFace != 0 ) {
					newFace->flipWinding();
					newFace->getPlane().offset( offset );
					newFace->planeChanged();
				}
			}
		}
		else if( HollowType == extrude ){
			if ( face.contributes() ) {
				//face.undoSave();
				out.push_back( new Brush( brush ) );
				out.back()->clear();

				std::shared_ptr<Face> newFace = out.back()->addFace( face );
				if ( newFace != 0 ) {
					newFace->getPlane().offset( offset );
					newFace->planeChanged();
				}

				if( !RemoveInner && caulk )
					face.SetShader( getCaulkShader() );
				newFace = out.back()->addFace( face );
				if ( newFace != 0 ) {
					newFace->flipWinding();
				}
				Winding& winding = face.getWinding();
				TextureProjection projection;
				TexDef_Construct_Default( projection );
				for ( Winding::iterator j = winding.begin(); j != winding.end(); ++j ){
					std::size_t index = std::distance( winding.begin(), j );
					std::size_t next = Winding_next( winding, index );

					out.back()->addPlane( winding[index].vertex, winding[next].vertex, winding[next].vertex + face.getPlane().plane3().normal() * offset, TextureBrowser_GetSelectedShader( GlobalTextureBrowser() ), projection );
				}
			}
		}
		else if( HollowType == diag ){
			if ( face.contributes() ) {
				out.push_back( new Brush( brush ) );
				out.back()->clear();

				std::shared_ptr<Face> newFace = out.back()->addFace( face );
				if ( newFace != 0 ) {

					newFace->planeChanged();
				}
				newFace = out.back()->addFace( face );

				if ( newFace != 0 ) {
					if( !RemoveInner && caulk )
						newFace->SetShader( getCaulkShader() );
					newFace->flipWinding();
					newFace->getPlane().offset( offset );
					newFace->planeChanged();
				}

				Winding& winding = face.getWinding();
				TextureProjection projection;
				TexDef_Construct_Default( projection );
				for ( Winding::iterator i = winding.begin(); i != winding.end(); ++i ){
					std::size_t index = std::distance( winding.begin(), i );
					std::size_t next = Winding_next( winding, index );
					Vector3 BestPoint;
					float bestdist = 999999;

					for( Brush::const_iterator j = brush.begin(); j != brush.end(); ++j ){
						Winding& winding2 = ( *j )->getWinding();
						for ( Winding::iterator k = winding2.begin(); k != winding2.end(); ++k ){
							std::size_t index2 = std::distance( winding2.begin(), k );
							float testdist = vector3_length( winding[index].vertex - winding2[index2].vertex );
							if( testdist < bestdist ){
								bestdist = testdist;
								BestPoint = winding2[index2].vertex;
							}
						}
					}
					out.back()->addPlane( winding[next].vertex, winding[index].vertex, BestPoint, caulk? getCaulkShader() : TextureBrowser_GetSelectedShader( GlobalTextureBrowser() ), projection );
				}
			}
		}
	}
}
};

class FaceExclude
{
DoubleVector3 ExclusionAxis;
double &mindot;
double &maxdot;
public:
FaceExclude( DoubleVector3 ExclusionAxis, double &mindot, double &maxdot )
	: ExclusionAxis( ExclusionAxis ), mindot( mindot ), maxdot( maxdot ){
}
void operator()( Face& face ) const {
	if( vector3_length_squared( ExclusionAxis ) != 0 ){
		double dot = vector3_dot( face.getPlane().plane3().normal(), ExclusionAxis );
		if( dot < mindot ){
			mindot = dot;
		}
		else if( dot > maxdot ){
			maxdot = dot;
		}
	}
}
};

class FaceOffset
{
float offset;
DoubleVector3 ExclusionAxis;
double &mindot;
double &maxdot;
public:
FaceOffset( float offset, DoubleVector3 ExclusionAxis, double &mindot, double &maxdot )
	: offset( offset ), ExclusionAxis( ExclusionAxis ), mindot( mindot ), maxdot( maxdot ){
}
void operator()( Face& face ) const {
	double dot = vector3_dot( face.getPlane().plane3().normal(), ExclusionAxis );
	if( dot == 0 || ( dot > mindot + 0.005 && dot < maxdot - 0.005 ) ){
		face.undoSave();
		face.getPlane().offset( offset );
		face.planeChanged();
	}
}
};


DoubleVector3 getExclusion();
bool getCaulk();
bool getRemoveInner();

class BrushHollowSelectedWalker : public scene::Graph::Walker
{
float offset;
eHollowType HollowType;
public:
BrushHollowSelectedWalker( float offset, eHollowType HollowType )
	: offset( offset ), HollowType( HollowType ){
}
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;
			double mindot = 0;
			double maxdot = 0;
			if( HollowType != room ){
				Brush_forEachFace( *brush, FaceExclude( getExclusion(), mindot, maxdot ) );
			}
			if( HollowType == room ){
				Brush* tmpbrush = new Brush( *brush );
				tmpbrush->removeEmptyFaces();
				Brush_forEachFace( *brush, FaceMakeBrush( *brush, out, offset, pull, DoubleVector3( 0, 0, 0 ), mindot, maxdot, true, true ) );
				delete tmpbrush;
			}
			else if( HollowType == pull ){
				if( !getRemoveInner() && getCaulk() ){
					Brush_forEachFace( *brush, CaulkFace( getExclusion(), mindot, maxdot ) );
				}
				Brush* tmpbrush = new Brush( *brush );
				tmpbrush->removeEmptyFaces();
				Brush_forEachFace( *tmpbrush, FaceMakeBrush( *tmpbrush, out, offset, HollowType, getExclusion(), mindot, maxdot, getCaulk(), getRemoveInner() ) );
				delete tmpbrush;
			}
			else if( HollowType == diag ){
				Brush* tmpbrush = new Brush( *brush );
				Brush_forEachFace( *tmpbrush, FaceOffset( offset, getExclusion(), mindot, maxdot ) );
				tmpbrush->removeEmptyFaces();
				Brush_forEachFace( *tmpbrush, FaceMakeBrush( *brush, out, offset, HollowType, getExclusion(), mindot, maxdot, getCaulk(), getRemoveInner() ) );
				delete tmpbrush;
				if( !getRemoveInner() && getCaulk() ){
					Brush_forEachFace( *brush, CaulkFace( getExclusion(), mindot, maxdot ) );
				}
			}
			else{
				Brush_forEachFace( *brush, FaceMakeBrush( *brush, out, offset, HollowType, getExclusion(), mindot, maxdot, getCaulk(), getRemoveInner() ) );
			}
			for ( brush_vector_t::const_iterator i = out.begin(); i != out.end(); ++i )
			{
				( *i )->removeEmptyFaces();
				if( ( *i )->hasContributingFaces() ){
				NodeSmartReference node( ( new BrushNode() )->node() );
				Node_getBrush( node )->copy( *( *i ) );
				delete ( *i );
				Node_getTraversable( path.parent() )->insert( node );
					//path.push( makeReference( node.get() ) );
					//selectPath( path, true );
					//Instance_getSelectable( *GlobalSceneGraph().find( path ) )->setSelected( true );
					//Path_deleteTop( path );
				}
			}
		}
	}
	return true;
}
};

typedef std::list<Brush*> 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 );
		}
	}
	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 );
		}
	}
}
};
*/
#include "ientity.h"

class BrushDeleteSelected : public scene::Graph::Walker
{
scene::Node* m_keepNode;
mutable bool m_eraseParent;
public:
BrushDeleteSelected( scene::Node* keepNode ): m_keepNode( keepNode ), m_eraseParent( false ){
}
BrushDeleteSelected(): m_keepNode( NULL ), m_eraseParent( false ){
}
bool pre( const scene::Path& path, scene::Instance& instance ) const {
	return true;
}
void post( const scene::Path& path, scene::Instance& instance ) const {
	//globalOutputStream() << path.size() << "\n";
	if ( path.top().get().visible() ) {
		Brush* brush = Node_getBrush( path.top() );
		if ( brush != 0
			 && Instance_getSelectable( instance )->isSelected()
			 && path.size() > 1 ) {
			scene::Node& parent = path.parent();
			Path_deleteTop( path );
			if( Node_getTraversable( parent )->empty() ){
				m_eraseParent = true;
				//globalOutputStream() << "Empty node?!.\n";
			}
		}
	}
	if( m_eraseParent && !Node_isPrimitive( path.top() ) && path.size() > 1 ){
		//globalOutputStream() << "about to Delete empty node!.\n";
		m_eraseParent = false;
		Entity* entity = Node_getEntity( path.top() );
		if ( entity != 0 && path.top().get_pointer() != Map_FindWorldspawn( g_map )
			&& Node_getTraversable( path.top() )->empty() && path.top().get_pointer() != m_keepNode ) {
			//globalOutputStream() << "now Deleting empty node!.\n";
			Path_deleteTop( path );
		}
	}
}
};

/*
   =============
   CSG_MakeRoom
   =============
 */
void CSG_MakeRoom( void ){
	UndoableCommand undo( "makeRoom" );
	GlobalSceneGraph().traverse( BrushHollowSelectedWalker( GetGridSize(), room ) );
	GlobalSceneGraph().traverse( BrushDeleteSelected() );
	SceneChangeNotify();
}

template<typename Type>
class RemoveReference
{
public:
typedef Type type;
};

template<typename Type>
class RemoveReference<Type&>
{
public:
typedef Type type;
};

template<typename Functor>
class Dereference
{
const Functor& functor;
public:
Dereference( const Functor& functor ) : functor( functor ){
}
get_result_type<Functor> operator()( typename RemoveReference<get_argument<Functor, 0>>::type *firstArgument ) const {
	return functor( *firstArgument );
}
};

template<typename Functor>
inline Dereference<Functor> makeDereference( const Functor& functor ){
	return Dereference<Functor>( functor );
}

template<typename Caller>
class BindArguments1
{
typedef get_argument<Caller, 1> FirstBound;
FirstBound firstBound;
public:
BindArguments1( FirstBound firstBound )
	: firstBound( firstBound ){
}

get_result_type<Caller> operator()( get_argument<Caller, 0> firstArgument ) const {
	return Caller::call( firstArgument, firstBound );
}
};

template<typename Caller>
class BindArguments2
{
typedef get_argument<Caller, 1> FirstBound;
typedef get_argument<Caller, 2> SecondBound;
FirstBound firstBound;
SecondBound secondBound;
public:
BindArguments2( FirstBound firstBound, SecondBound secondBound )
	: firstBound( firstBound ), secondBound( secondBound ){
}

get_result_type<Caller> operator()( get_argument<Caller, 0> firstArgument ) const {
	return Caller::call( firstArgument, firstBound, secondBound );
}
};

template<typename Caller, typename FirstBound, typename SecondBound>
BindArguments2<Caller> bindArguments( const Caller& caller, FirstBound firstBound, SecondBound secondBound ){
	return BindArguments2<Caller>( 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<bool ( const Face &, const Plane3 &, bool ), Face_testPlane> 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;
		}
	}
	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 );
		}
	}
	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<Face>& b : other )
		{
			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<Face> newFace = fragments.back()->addFace( *b );
					if ( newFace != nullptr ) {
						newFace->flipWinding();
					}
					back.addFace( *b );
				}
				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;
	}
	return false;
}

class SubtractBrushesFromUnselected : public scene::Graph::Walker
{
const brush_vector_t& m_brushlist;
std::size_t& m_before;
std::size_t& m_after;
mutable bool m_eraseParent;
public:
SubtractBrushesFromUnselected( const brush_vector_t& brushlist, std::size_t& before, std::size_t& after )
	: m_brushlist( brushlist ), m_before( before ), m_after( after ), m_eraseParent( false ){
}

bool pre( const scene::Path& path, scene::Instance& instance ) const {
	if ( path.top().get().visible() ) {
		return true;
	}
	return false;
}

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<std::size_t>( swap )].push_back( original );

			{
				for ( brush_vector_t::const_iterator i( m_brushlist.begin() ); i != m_brushlist.end(); ++i )
				{
					for ( brush_vector_t::iterator j( buffer[static_cast<std::size_t>( swap )].begin() ); j != buffer[static_cast<std::size_t>( swap )].end(); ++j )
					{
						if ( Brush_subtract( *( *j ), *( *i ), buffer[static_cast<std::size_t>( !swap )] ) ) {
							delete ( *j );
						}
						else
						{
							buffer[static_cast<std::size_t>( !swap )].push_back( ( *j ) );
						}
					}
					buffer[static_cast<std::size_t>( swap )].clear();
					swap = !swap;
				}
			}

			brush_vector_t& out = buffer[static_cast<std::size_t>( swap )];

			if ( out.size() == 1 && out.back() == original ) {
				delete original;
			}
			else
			{
				++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;
				}
				scene::Node& parent = path.parent();
				Path_deleteTop( path );
				if( Node_getTraversable( parent )->empty() ){
					m_eraseParent = true;
				}
			}
		}
	}
	if( m_eraseParent && !Node_isPrimitive( path.top() ) && path.size() > 1 ){
		m_eraseParent = false;
		Entity* entity = Node_getEntity( path.top() );
		if ( entity != 0 && path.top().get_pointer() != Map_FindWorldspawn( g_map )
			&& Node_getTraversable( path.top() )->empty() ) {
			Path_deleteTop( path );
		}
	}
}
};

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();
	}
}

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 ){
}

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() ) {
		return;
	}

		Brush* brush = Node_getBrush( path.top() );
	if ( brush == nullptr || !Instance_getSelectable( instance )->isSelected() ) {
		return;
	}

			Plane3 plane( plane3_for_points( m_p0, m_p1, m_p2 ) );
	if ( !plane3_valid( plane ) ) {
		return;
	}

				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<Face> 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" );

						Node_getTraversable( path.parent() )->insert( node );
						{
							scene::Path fragmentPath = path;
							fragmentPath.top() = makeReference( node.get() );
							selectPath( fragmentPath, true );
						}
					}

		std::shared_ptr<Face> 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 );
	}
}
};

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();
}


class BrushInstanceSetClipPlane : public scene::Graph::Walker
{
Plane3 m_plane;
public:
BrushInstanceSetClipPlane( const Plane3& plane )
	: m_plane( plane ){
}

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;
}
};

void Scene_BrushSetClipPlane( scene::Graph& graph, const Plane3& plane ){
	graph.traverse( BrushInstanceSetClipPlane( plane ) );
}

/*
   =============
   CSG_Merge
   =============
 */
bool Brush_merge( Brush& brush, const brush_vector_t& in, bool onlyshape ){
	// gather potential outer faces

	{
		typedef std::vector<const Face*> 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;
				}

				const Face& face1 = *( *j );

				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;
							}
						}
					}
				}

				// check faces already stored
				for ( Faces::const_iterator m = faces.begin(); !skip && m != faces.end(); ++m )
				{
					const Face& face2 = *( *m );

					// 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;
					}

					// 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;
					}
				}

				if ( !skip ) {
					faces.push_back( &face1 );
				}
			}
		}
		for ( Faces::const_iterator i = faces.begin(); i != faces.end(); ++i )
		{
			if ( !brush.addFace( *( *i ) ) ) {
				// result would have too many sides
				return false;
			}
		}
	}

	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;
	}

	if ( selected_brushes.size() < 2 ) {
		globalOutputStream() << "CSG Merge: At least two brushes have to be selected.\n";
		return;
	}

	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" );

		// free the original brushes
		GlobalSceneGraph().traverse( BrushDeleteSelected( merged_path.parent().get_pointer() ) );

		merged_path.pop();
		Node_getTraversable( merged_path.top() )->insert( node );
		merged_path.push( makeReference( node.get() ) );

		selectPath( merged_path, true );

		globalOutputStream() << "CSG Merge: Succeeded.\n";
		SceneChangeNotify();
	}
}






/*
   =============
   CSG_Tool
   =============
 */
#include "mainframe.h"
#include <gtk/gtk.h>
#include "gtkutil/dialog.h"
#include "gtkutil/button.h"
#include "gtkutil/accelerator.h"

struct CSGToolDialog
{
	GtkSpinButton* spin;
	bool allocated{false};
	ui::Window window{ui::null};
	GtkToggleButton *radXYZ, *radX, *radY, *radZ, *caulk, *removeInner;
};

CSGToolDialog g_csgtool_dialog;

DoubleVector3 getExclusion(){
	if( gtk_toggle_button_get_active( g_csgtool_dialog.radX ) ){
		return DoubleVector3( 1, 0, 0 );
	}
	else if( gtk_toggle_button_get_active( g_csgtool_dialog.radY ) ){
		return DoubleVector3( 0, 1, 0 );
	}
	else if( gtk_toggle_button_get_active( g_csgtool_dialog.radZ ) ){
		return DoubleVector3( 0, 0, 1 );
	}
	return DoubleVector3( 0, 0, 0 );
}

bool getCaulk(){
		if( gtk_toggle_button_get_active( g_csgtool_dialog.caulk ) ){
		return true;
	}
	return false;
}

bool getRemoveInner(){
		if( gtk_toggle_button_get_active( g_csgtool_dialog.removeInner ) ){
		return true;
	}
	return false;
}

class BrushFaceOffset
{
float offset;
public:
BrushFaceOffset( float offset )
	: offset( offset ){
}
void operator()( BrushInstance& brush ) const {
	double mindot = 0;
	double maxdot = 0;
	Brush_forEachFace( brush, FaceExclude( getExclusion(), mindot, maxdot ) );
	Brush_forEachFace( brush, FaceOffset( offset, getExclusion(), mindot, maxdot ) );
}
};

//=================DLG

static gboolean CSGdlg_HollowDiag( GtkWidget *widget, CSGToolDialog* dialog ){
	float offset = static_cast<float>( gtk_spin_button_get_value( dialog->spin ) );
	UndoableCommand undo( "brushHollow::Diag" );
	GlobalSceneGraph().traverse( BrushHollowSelectedWalker( offset, diag ) );
	if( getRemoveInner() )
		GlobalSceneGraph().traverse( BrushDeleteSelected() );
	SceneChangeNotify();
	return TRUE;
}

static gboolean CSGdlg_HollowWrap( GtkWidget *widget, CSGToolDialog* dialog ){
	float offset = static_cast<float>( gtk_spin_button_get_value( dialog->spin ) );
	UndoableCommand undo( "brushHollow::Wrap" );
	GlobalSceneGraph().traverse( BrushHollowSelectedWalker( offset, wrap ) );
	if( getRemoveInner() )
		GlobalSceneGraph().traverse( BrushDeleteSelected() );
	SceneChangeNotify();
	return TRUE;
}

static gboolean CSGdlg_HollowExtrude( GtkWidget *widget, CSGToolDialog* dialog ){
	float offset = static_cast<float>( gtk_spin_button_get_value( dialog->spin ) );
	UndoableCommand undo( "brushHollow::Extrude" );
	GlobalSceneGraph().traverse( BrushHollowSelectedWalker( offset, extrude ) );
	if( getRemoveInner() )
		GlobalSceneGraph().traverse( BrushDeleteSelected() );
	SceneChangeNotify();
	return TRUE;
}

static gboolean CSGdlg_HollowPull( GtkWidget *widget, CSGToolDialog* dialog ){
	float offset = static_cast<float>( gtk_spin_button_get_value( dialog->spin ) );
	UndoableCommand undo( "brushHollow::Pull" );
	GlobalSceneGraph().traverse( BrushHollowSelectedWalker( offset, pull ) );
	if( getRemoveInner() )
		GlobalSceneGraph().traverse( BrushDeleteSelected() );
	SceneChangeNotify();
	return TRUE;
}

static gboolean CSGdlg_BrushShrink( GtkWidget *widget, CSGToolDialog* dialog ){
	gtk_spin_button_update ( dialog->spin );
	float offset = static_cast<float>( gtk_spin_button_get_value( dialog->spin ) );
	offset *= -1;
	UndoableCommand undo( "Shrink brush" );
//	GlobalSceneGraph().traverse( OffsetBrushFacesSelectedWalker( offset ) );
	//Scene_ForEachSelectedBrush_ForEachFace( GlobalSceneGraph(), BrushFaceOffset( offset ) );
	Scene_forEachSelectedBrush( BrushFaceOffset( offset ) );
	SceneChangeNotify();
	return TRUE;
}

static gboolean CSGdlg_BrushExpand( GtkWidget *widget, CSGToolDialog* dialog ){
	gtk_spin_button_update ( dialog->spin );
	float offset = static_cast<float>( gtk_spin_button_get_value( dialog->spin ) );
	UndoableCommand undo( "Expand brush" );
//	GlobalSceneGraph().traverse( OffsetBrushFacesSelectedWalker( offset ) );
	//Scene_ForEachSelectedBrush_ForEachFace( GlobalSceneGraph(), BrushFaceOffset( offset ) );
	Scene_forEachSelectedBrush( BrushFaceOffset( offset ) );
	SceneChangeNotify();
	return TRUE;
}

static gboolean CSGdlg_grid2spin( GtkWidget *widget, CSGToolDialog* dialog ){
	gtk_spin_button_set_value( dialog->spin, GetGridSize() );
	return TRUE;
}

static gboolean CSGdlg_delete( GtkWidget *widget, GdkEventAny *event, CSGToolDialog* dialog ){
	gtk_widget_hide( GTK_WIDGET( dialog->window ) );
	return TRUE;
}

void CSG_Tool(){
	// FIXME: there is probably improvements to do less raw GTK stuff, more GTK wrapper
	if ( !g_csgtool_dialog.allocated ) {
		g_csgtool_dialog.allocated = true;
		g_csgtool_dialog.window = MainFrame_getWindow().create_dialog_window( "CSG Tool", G_CALLBACK( CSGdlg_delete ), &g_csgtool_dialog );
		gtk_window_set_type_hint( g_csgtool_dialog.window, GDK_WINDOW_TYPE_HINT_UTILITY );

		//GtkAccelGroup* accel = gtk_accel_group_new();
		//gtk_window_add_accel_group( g_csgtool_dialog.window, accel );
		global_accel_connect_window( g_csgtool_dialog.window );

		{
			auto hbox = create_dialog_hbox( 4, 4 );
			gtk_container_add( GTK_CONTAINER( g_csgtool_dialog.window ), GTK_WIDGET( hbox ) );
			{
				auto table = create_dialog_table( 3, 8, 4, 4 );
				gtk_box_pack_start( GTK_BOX( hbox ), GTK_WIDGET( table ), TRUE, TRUE, 0 );
				{
					//GtkWidget* label = gtk_label_new( "<->" );
					//gtk_widget_show( label );
					auto button = ui::Button( "Grid->" );
					table.attach( button, {0, 1, 0, 1}, {0, 0} );
					button.show();
					g_signal_connect( G_OBJECT( button ), "clicked", G_CALLBACK( CSGdlg_grid2spin ), &g_csgtool_dialog );
				}
				{
					GtkAdjustment* adj = GTK_ADJUSTMENT( gtk_adjustment_new( 16, 0, 9999, 1, 10, 0 ) );
					GtkSpinButton* spin = GTK_SPIN_BUTTON( gtk_spin_button_new( adj, 1, 3 ) );
					gtk_widget_show( GTK_WIDGET( spin ) );
					gtk_widget_set_tooltip_text( GTK_WIDGET( spin ), "Thickness" );
					gtk_table_attach( table, GTK_WIDGET( spin ), 1, 2, 0, 1,
									  (GtkAttachOptions) ( GTK_EXPAND | GTK_FILL ),
									  (GtkAttachOptions) ( 0 ), 0, 0 );
					gtk_widget_set_size_request( GTK_WIDGET( spin ), 64, -1 );
					gtk_spin_button_set_numeric( spin, TRUE );

					g_csgtool_dialog.spin = spin;
				}
				{
					//radio button group for choosing the exclude axis
					GtkWidget* radXYZ = gtk_radio_button_new_with_label( NULL, "XYZ" );
					GtkWidget* radX = gtk_radio_button_new_with_label_from_widget( GTK_RADIO_BUTTON(radXYZ), "-X" );
					GtkWidget* radY = gtk_radio_button_new_with_label_from_widget( GTK_RADIO_BUTTON(radXYZ), "-Y" );
					GtkWidget* radZ = gtk_radio_button_new_with_label_from_widget( GTK_RADIO_BUTTON(radXYZ), "-Z" );
					gtk_widget_show( radXYZ );
					gtk_widget_show( radX );
					gtk_widget_show( radY );
					gtk_widget_show( radZ );

					gtk_table_attach( table, radXYZ, 2, 3, 0, 1,
									(GtkAttachOptions) ( GTK_EXPAND | GTK_FILL ),
									(GtkAttachOptions) ( 0 ), 0, 0 );
					gtk_table_attach( table, radX, 3, 4, 0, 1,
									(GtkAttachOptions) ( GTK_EXPAND | GTK_FILL ),
									(GtkAttachOptions) ( 0 ), 0, 0 );
					gtk_table_attach( table, radY, 4, 5, 0, 1,
									(GtkAttachOptions) ( GTK_EXPAND | GTK_FILL ),
									(GtkAttachOptions) ( 0 ), 0, 0 );
					gtk_table_attach( table, radZ, 5, 6, 0, 1,
									(GtkAttachOptions) ( GTK_EXPAND | GTK_FILL ),
									(GtkAttachOptions) ( 0 ), 0, 0 );

					g_csgtool_dialog.radXYZ = GTK_TOGGLE_BUTTON( radXYZ );
					g_csgtool_dialog.radX = GTK_TOGGLE_BUTTON( radX );
					g_csgtool_dialog.radY = GTK_TOGGLE_BUTTON( radY );
					g_csgtool_dialog.radZ = GTK_TOGGLE_BUTTON( radZ );
				}
				{
					GtkWidget* button = gtk_toggle_button_new();
					auto ubutton = ui::Button::from( button );
					button_set_icon( ubutton, "f-caulk.png" );
					gtk_button_set_relief( GTK_BUTTON( button ), GTK_RELIEF_NONE );
					table.attach( ubutton, { 6, 7, 0, 1 }, { GTK_EXPAND, 0 } );
					gtk_widget_set_tooltip_text( button, "Caulk some faces" );
					gtk_toggle_button_set_active( GTK_TOGGLE_BUTTON( button ), TRUE );
					ubutton.show();
					g_csgtool_dialog.caulk = GTK_TOGGLE_BUTTON( button );
				}
				{
					GtkWidget* button = gtk_toggle_button_new();
					auto ubutton = ui::Button::from( button );
					button_set_icon( ubutton, "csgtool_removeinner.png" );
					gtk_button_set_relief( GTK_BUTTON( button ), GTK_RELIEF_NONE );
					table.attach( ubutton, { 7, 8, 0, 1 }, { GTK_EXPAND, 0 } );
					gtk_widget_set_tooltip_text( button, "Remove inner brush" );
					gtk_toggle_button_set_active( GTK_TOGGLE_BUTTON( button ), TRUE );
					ubutton.show();
					g_csgtool_dialog.removeInner = GTK_TOGGLE_BUTTON( button );
				}
				{
					GtkWidget* sep = gtk_hseparator_new();
					gtk_widget_show( sep );
					gtk_table_attach( table, sep, 0, 8, 1, 2,
									(GtkAttachOptions) ( GTK_EXPAND | GTK_FILL ),
									(GtkAttachOptions) ( 0 ), 0, 0 );
				}
				{
					GtkWidget* button = gtk_button_new();
					auto ubutton = ui::Button::from( button );
					button_set_icon( ubutton, "csgtool_shrink.png" );
					table.attach( ubutton, { 0, 1, 2, 3 }, { GTK_EXPAND, 0 } );
					gtk_widget_set_tooltip_text( button, "Shrink brush" );
					ubutton.show();
					g_signal_connect( G_OBJECT( button ), "clicked", G_CALLBACK( CSGdlg_BrushShrink ), &g_csgtool_dialog );
				}
				{
					GtkWidget* button = gtk_button_new();
					auto ubutton = ui::Button::from( button );
					button_set_icon( ubutton, "csgtool_expand.png" );
					table.attach( ubutton, { 1, 2, 2, 3 }, { GTK_EXPAND, 0 } );
					gtk_widget_set_tooltip_text( button, "Expand brush" );
					ubutton.show();
					g_signal_connect( G_OBJECT( button ), "clicked", G_CALLBACK( CSGdlg_BrushExpand ), &g_csgtool_dialog );
				}
				{
					GtkWidget* button = gtk_button_new();
					auto ubutton = ui::Button::from( button );
					button_set_icon( ubutton, "csgtool_diagonal.png" );
					table.attach( ubutton, { 3, 4, 2, 3 }, { GTK_EXPAND, 0 } );
					gtk_widget_set_tooltip_text( button, "Hollow::diagonal joints" );
					ubutton.show();
					g_signal_connect( G_OBJECT( button ), "clicked", G_CALLBACK( CSGdlg_HollowDiag ), &g_csgtool_dialog );
				}
				{
					GtkWidget* button = gtk_button_new();
					auto ubutton = ui::Button::from( button );
					button_set_icon( ubutton, "csgtool_wrap.png" );
					table.attach( ubutton, { 4, 5, 2, 3 }, { GTK_EXPAND, 0 } );
					gtk_widget_set_tooltip_text( button, "Hollow::warp" );
					ubutton.show();
					g_signal_connect( G_OBJECT( button ), "clicked", G_CALLBACK( CSGdlg_HollowWrap ), &g_csgtool_dialog );
				}
				{
					GtkWidget* button = gtk_button_new();
					auto ubutton = ui::Button::from( button );
					button_set_icon( ubutton, "csgtool_extrude.png" );
					table.attach( ubutton, { 5, 6, 2, 3 }, { GTK_EXPAND, 0 } );
					gtk_widget_set_tooltip_text( button, "Hollow::extrude faces" );
					ubutton.show();
					g_signal_connect( G_OBJECT( button ), "clicked", G_CALLBACK( CSGdlg_HollowExtrude ), &g_csgtool_dialog );
				}
				{
					GtkWidget* button = gtk_button_new();
					auto ubutton = ui::Button::from( button );
					button_set_icon( ubutton, "csgtool_pull.png" );
					table.attach( ubutton, { 6, 7, 2, 3 }, { GTK_EXPAND, 0 } );
					gtk_widget_set_tooltip_text( button, "Hollow::pull faces" );
					ubutton.show();
					g_signal_connect( G_OBJECT( button ), "clicked", G_CALLBACK( CSGdlg_HollowPull ), &g_csgtool_dialog );
				}

			}
		}
	}

	gtk_widget_show( GTK_WIDGET( g_csgtool_dialog.window ) );
	gtk_window_present( g_csgtool_dialog.window );
}