#ifndef _VspBspTree_H__
#define _VspBspTree_H__

#include "Mesh.h"
#include "Containers.h"
#include "Polygon3.h"
#include <stack>
#include "Statistics.h"
#include "VssRay.h"
#include "RayInfo.h"
#include "ViewCellBsp.h"

class ViewCell;
//class BspViewCell;
class Plane3;
class VspBspTree;  
class BspInterior;
class BspNode;
class AxisAlignedBox3;
class Ray;
class ViewCellsStatistics;
class ViewCellsManager;
class BspMergeCandidate;
class Beam;

struct BspRay;


/**
	This is a view space partitioning specialised BSPtree.  
	There are no polygon splits, but we split the sample rays. 
	The candidates for the next split plane are evaluated only 
	by checking the sampled	visibility information. 
	The polygons are employed merely as candidates for the next split planes.
*/
class VspBspTree 
{
	friend class ViewCellsParseHandlers;
	friend class VspBspViewCellsManager;
public:
	
	/** Additional data which is passed down the BSP tree during traversal.
	*/
	struct VspBspTraversalData
	{  
		/// the current node
		BspNode *mNode;
		/// polygonal data for splitting
		PolygonContainer *mPolygons;
		/// current depth
		int mDepth;
		/// rays piercing this node
		RayInfoContainer *mRays;
		/// the probability that this node contains view point
		float mProbability;
		/// geometry of node as induced by planes
		BspNodeGeometry *mGeometry;
		/// pvs size
		int mPvs;
		/// how often this branch has missed the max-cost ratio
		int mMaxCostMisses;
		/// if this node is a kd-node (i.e., boundaries are axis aligned
		bool mIsKdNode;
		/// bounding box of current view space.
		///AxisAlignedBox3 mBbox;
		
		/** Returns average ray contribution.
		*/
		float GetAvgRayContribution() const
		{
			return (float)mPvs / ((float)mRays->size() + Limits::Small);
		}


		VspBspTraversalData():
		mNode(NULL),
		mPolygons(NULL),
		mDepth(0),
		mRays(NULL),
		mPvs(0),
		mProbability(0.0),
		mGeometry(NULL),
		mMaxCostMisses(0), 
		mIsKdNode(false)
		{}
		
		VspBspTraversalData(BspNode *node, 
							PolygonContainer *polys, 
							const int depth, 
							RayInfoContainer *rays,
							const int pvs,
							const float p,
							BspNodeGeometry *geom): 
		mNode(node), 
		mPolygons(polys), 
		mDepth(depth), 
		mRays(rays),
		mPvs(pvs),
		mProbability(p),
		mGeometry(geom),
		mMaxCostMisses(0),
		mIsKdNode(false)
		{}

		VspBspTraversalData(PolygonContainer *polys, 
							const int depth, 
							RayInfoContainer *rays,
							BspNodeGeometry *geom): 
		mNode(NULL), 
		mPolygons(polys), 
		mDepth(depth), 
		mRays(rays),
		mPvs(0),
		mProbability(0),
		mGeometry(geom),
		mMaxCostMisses(0),
		mIsKdNode(false)
		{}

		/** Returns cost of the traversal data.
		*/
		float GetCost() const
		{
#if 1
			return mPvs * mProbability;
#endif
#if 0
			return (float)(mPvs * (int)mRays->size());
#endif
#if 0
			return (float)mPvs;
#endif
#if 0
			return mProbabiliy * (float)mRays->size();
#endif
		}

		// deletes contents and sets them to NULL
		void Clear()
		{
			DEL_PTR(mPolygons);
			DEL_PTR(mRays);
			DEL_PTR(mGeometry);
		}

		friend bool operator<(const VspBspTraversalData &a, const VspBspTraversalData &b)
		{
			return a.GetCost() < b.GetCost();
		}
    };
	
	typedef std::priority_queue<VspBspTraversalData> VspBspTraversalStack;
	//typedef std::stack<VspBspTraversalData> VspBspTraversalStack;

	/** Default constructor creating an empty tree.
	*/ 
	VspBspTree();

	/** Default destructor.
	*/
	~VspBspTree();

	/** Returns BSP Tree statistics.
	*/
	const BspTreeStatistics &GetStatistics() const; 
  

	/** Constructs the tree from a given set of rays.
		@param sampleRays the set of sample rays the construction is based on
		@param viewCells if not NULL, new view cells are 
		created in the leafs and stored in the container
	*/
	void Construct(const VssRayContainer &sampleRays,
				   AxisAlignedBox3 *forcedBoundingBox);

	/** Returns list of BSP leaves with pvs smaller than
		a certain threshold.
		@param onlyUnmailed if only the unmailed leaves should be considered
		@param maxPvs the maximal pvs (-1 means unlimited)
	*/
	void CollectLeaves(vector<BspLeaf *> &leaves, 
					   const bool onlyUnmailed = false,
					   const int maxPvs = -1) const;

	/** Returns box which bounds the whole tree.
	*/
	AxisAlignedBox3 GetBoundingBox()const;

	/** Returns root of BSP tree.
	*/
	BspNode *GetRoot() const;

	/** Collects the leaf view cells of the tree
		@param viewCells returns the view cells 
	*/
	void CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const;

	/** A ray is cast possible intersecting the tree.
		@param the ray that is cast.
		@returns the number of intersections with objects stored in the tree.
	*/
	int CastRay(Ray &ray);

	/// bsp tree construction types
	enum {FROM_INPUT_VIEW_CELLS, FROM_SCENE_GEOMETRY, FROM_SAMPLES};

	/** finds neighbouring leaves of this tree node.
	*/
	int FindNeighbors(BspNode *n, 
					  vector<BspLeaf *> &neighbors, 
					  const bool onlyUnmailed) const;

	/** Constructs geometry associated with the half space intersections 
		leading to this node.
	*/
	void ConstructGeometry(BspNode *n, BspNodeGeometry &geom) const;
	
	/** Construct geometry of view cell.
	*/
	void ConstructGeometry(BspViewCell *vc, BspNodeGeometry &geom) const;

	/** Returns random leaf of BSP tree.
		@param halfspace defines the halfspace from which the leaf is taken.
	*/
	BspLeaf *GetRandomLeaf(const Plane3 &halfspace);

	/** Returns random leaf of BSP tree.
		@param onlyUnmailed if only unmailed leaves should be returned.
	*/
	BspLeaf *GetRandomLeaf(const bool onlyUnmailed = false);

	/** Returns epsilon of this tree.
	*/
	float GetEpsilon() const;

	/** Casts line segment into the tree.
		@param origin the origin of the line segment
		@param termination the end point of the line segment
		@returns view cells intersecting the line segment.
	*/
    int CastLineSegment(const Vector3 &origin,
						const Vector3 &termination,
						ViewCellContainer &viewcells);

		
	/** Sets pointer to view cells manager.
	*/
	void SetViewCellsManager(ViewCellsManager *vcm);

	/** Returns distance from node 1 to node 2.
	*/
	int TreeDistance(BspNode *n1, BspNode *n2) const;

	/** Merges view cells according to some cost heuristics.
	*/
	int MergeViewCells(const VssRayContainer &rays, const ObjectContainer &objects);
	
	/** Refines view cells using shuffling, i.e., border leaves 
		of two view cells are exchanged if the resulting view cells
		are tested to be "better" than the old ones.
		@returns number of refined view cells
	*/
	int RefineViewCells(const VssRayContainer &rays, const ObjectContainer &objects);

	/** Collapses the tree with respect to the view cell partition.
		@returns number of collapsed nodes
	*/
	int CollapseTree();

	/** Returns view cell the current point is located in.
	*/
	ViewCell *GetViewCell(const Vector3 &point);

	/** Constructs bsp rays for post processing and visualization.
	*/
	void ConstructBspRays(vector<BspRay *> &bspRays,
						  const VssRayContainer &rays);
	
	/** Merge view cells of leaves l1 and l2.
	*/
	bool MergeViewCells(BspLeaf *l1, BspLeaf *l2); //const;

	/** Returns true if this view point is in a valid view space,
		false otherwise.
	*/
	bool ViewPointValid(const Vector3 &viewPoint) const;

	/** Returns view cell corresponding to 
		the invalid view space.
	*/
	BspViewCell *GetOutOfBoundsCell();

	/** Writes tree to output stream
	*/
	bool Export(ofstream &stream);

	/** Casts beam, i.e. a 5D frustum of rays, into tree.
		Tests conservative using the bounding box of the nodes.
		@returns number of view cells it intersected
	*/
	int CastBeam(Beam &beam);

	void CollectViewCells(BspNode *root, 
						  bool onlyValid, 
						  ViewCellContainer &viewCells,
						  bool onlyUnmailed = false) const;

	
	/** Checks validy of view cells.
		if not valid, sets regions invalid and deletes view cell.
	*/
	void ValidateTree();

protected:

	// --------------------------------------------------------------
	// For sorting objects
	// --------------------------------------------------------------
	struct SortableEntry
	{
		enum EType 
		{
			ERayMin,
			ERayMax
		};

		int type;
		float value;
		VssRay *ray;
  
		SortableEntry() {}
		SortableEntry(const int t, const float v, VssRay *r):type(t),
					  value(v), ray(r) 
		{
		}
		
		friend bool operator<(const SortableEntry &a, const SortableEntry &b) 
		{
			return a.value < b.value;
		}
	};

	/** faster evaluation of split plane cost for kd axis aligned cells.
	*/
	float EvalAxisAlignedSplitCost(const VspBspTraversalData &data,
								   const AxisAlignedBox3 &box,
								   const int axis,
								   const float &position,
								   float &pFront,
								   float &pBack) const;

	/** Returns view cell corresponding to 
		the invalid view space. If it does not exist, it is created.
	*/
	BspViewCell *GetOrCreateOutOfBoundsCell();

	/** Collapses the tree with respect to the view cell partition,
		i.e. leaves having the same view cell are collapsed.
		@param node the root of the subtree to be collapsed
		@param collapsed returns the number of collapsed nodes
		@returns node of type leaf if the node could be collapsed, 
		this node otherwise
	*/
	BspNode *CollapseTree(BspNode *node, int &collapsed);

	/** Shuffles the leaves, i.e., tests if exchanging
		the leaves helps in improving the view cells.
	*/
	bool ShuffleLeaves(BspLeaf *leaf1, BspLeaf *leaf2) const;

	/** Helper function revalidating the view cell leaf list after merge.
	*/
	void RepairViewCellsLeafLists();

	/** Evaluates tree stats in the BSP tree leafs.
	*/
	void EvaluateLeafStats(const VspBspTraversalData &data);

	/** Subdivides node with respect to the traversal data.
	    @param tStack current traversal stack
		@param tData traversal data also holding node to be subdivided
		@returns new root of the subtree
	*/
	BspNode *Subdivide(VspBspTraversalStack &tStack, 
					   VspBspTraversalData &tData);

	/** Constructs the tree from the given traversal data.
		@param polys stores set of polygons on which subdivision may be based
		@param rays storesset of rays on which subdivision may be based
	*/
	void Construct(const PolygonContainer &polys, RayInfoContainer *rays);

	/** Selects the best possible splitting plane. 
		@param plane returns the split plane
		@param leaf the leaf to be split
		@param polys the polygon list on which the split decition is based
		@param rays ray container on which selection may be based
		@note the polygons can be reordered in the process
		@returns true if the cost of the split is under maxCostRatio

	*/
	bool SelectPlane(Plane3 &plane, 
					 BspLeaf *leaf, 
					 VspBspTraversalData &data,
					 VspBspTraversalData &frontData,
					 VspBspTraversalData &backData);
	
	/** Strategies where the effect of the split plane is tested
	    on all input rays.

		@returns the cost of the candidate split plane
	*/
	float SplitPlaneCost(const Plane3 &candidatePlane, 
						 const VspBspTraversalData &data,
						 BspNodeGeometry &geomFront,
						 BspNodeGeometry &geomBack,
						 float &pFront,
						 float &pBack) const;

	/** Subdivide leaf.
		@param leaf the leaf to be subdivided
		
		@param polys the polygons to be split
		@param frontPolys returns the polygons in front of the split plane
		@param backPolys returns the polygons in the back of the split plane
		
		@param rays the polygons to be filtered
		@param frontRays returns the polygons in front of the split plane
		@param backRays returns the polygons in the back of the split plane

		@returns the root of the subdivision
	*/

	BspNode *SubdivideNode(VspBspTraversalData &tData,
						   VspBspTraversalData &frontData,
						   VspBspTraversalData &backData,
						   PolygonContainer &coincident);

	/** Extracts the meshes of the objects and adds them to polygons. 
		Adds object aabb to the aabb of the tree.
		@param maxPolys the maximal number of objects to be stored as polygons
		@returns the number of polygons
	*/
	int AddToPolygonSoup(const ObjectContainer &objects, 
						 PolygonContainer &polys, 
						 int maxObjects = 0);

	/** Extracts the meshes of the view cells and and adds them to polygons.
		Adds view cell aabb to the aabb of the tree.
		@param maxPolys the maximal number of objects to be stored as polygons
		@returns the number of polygons
	*/
	int AddToPolygonSoup(const ViewCellContainer &viewCells, 
						 PolygonContainer &polys, 
						 int maxObjects = 0);

	/** Extract polygons of this mesh and add to polygon container.
		@param mesh the mesh that drives the polygon construction
		@param parent the parent intersectable this polygon is constructed from
		@returns number of polygons
	*/
	int AddMeshToPolygons(Mesh *mesh, PolygonContainer &polys, MeshInstance *parent);

	/** Selects an axis aligned for the next split.
		@returns cost for this split
	*/
	float SelectAxisAlignedPlane(Plane3 &plane, 
								 const VspBspTraversalData &tData,
								 int &axis,
								 BspNodeGeometry **frontGeom,
								 BspNodeGeometry **backGeom,
								 float &pFront,
								 float &pBack,
								 const bool useKdSplit);

	/** Sorts split candidates for surface area heuristics for axis aligned splits.
		@param polys the input for choosing split candidates
		@param axis the current split axis
		@param splitCandidates returns sorted list of split candidates
	*/
	void SortSplitCandidates(const RayInfoContainer &rays, const int axis);

	/** Computes best cost for axis aligned planes.
	*/
	float BestCostRatioHeuristics(const RayInfoContainer &rays,
								  const AxisAlignedBox3 &box,
								  const int pvsSize,
								  const int &axis,
								  float &position);

	/** Selects an axis aligned split plane.
		@Returns true if split is valied
	*/
	bool SelectAxisAlignedPlane(Plane3 &plane, const PolygonContainer &polys) const;

	/** Subdivides the rays into front and back rays according to the split plane.
		
		@param plane the split plane
		@param rays contains the rays to be split. The rays are 
			   distributed into front and back rays.
		@param frontRays returns rays on the front side of the plane
		@param backRays returns rays on the back side of the plane
		
		@returns the number of splits
	*/
	int SplitRays(const Plane3 &plane,
				  RayInfoContainer &rays, 
			      RayInfoContainer &frontRays, 
				  RayInfoContainer &backRays);


	/** Extracts the split planes representing the space bounded by node n.
	*/
	void ExtractHalfSpaces(BspNode *n, vector<Plane3> &halfSpaces) const;

	/** Adds the object to the pvs of the front and back leaf with a given classification.

		@param obj the object to be added
		@param cf the ray classification regarding the split plane
		@param frontPvs returns the PVS of the front partition
		@param backPvs returns the PVS of the back partition
	
	*/
	void AddObjToPvs(Intersectable *obj, 
					 const int cf, 
					 int &frontPvs, 
					 int &backPvs, 
					 int &totalPvs) const;
	
	/** Computes PVS size induced by the rays.
	*/
	int ComputePvsSize(const RayInfoContainer &rays) const;

	/** Returns true if tree can be terminated.
	*/
	inline bool TerminationCriteriaMet(const VspBspTraversalData &data) const;

	/** Computes accumulated ray lenght of this rays.
	*/
	float AccumulatedRayLength(const RayInfoContainer &rays) const;

	/** Splits polygons with respect to the split plane.

		@param plane the split plane
		@param polys the polygons to be split. the polygons are consumed and
			   distributed to the containers frontPolys, backPolys, coincident.
		@param frontPolys returns the polygons in the front of the split plane
		@param backPolys returns the polygons in the back of the split plane
		@param coincident returns the polygons coincident to the split plane

		@returns the number of splits	
	*/
	int SplitPolygons(const Plane3 &plane,
					  PolygonContainer &polys, 
					  PolygonContainer &frontPolys, 
					  PolygonContainer &backPolys, 
					  PolygonContainer &coincident) const;

	/** Adds ray sample contributions to the PVS.
		@param sampleContributions the number contributions of the samples
		@param contributingSampels the number of contributing rays
		
	*/
	void AddToPvs(BspLeaf *leaf,
				  const RayInfoContainer &rays, 
				  float &sampleContributions,
				  int &contributingSamples);


	/** Collects candidates for the merge in the merge queue.
		@param leaves the leaves to be merged
		@returns number of leaves in queue
	*/
	int CollectMergeCandidates(const vector<BspLeaf *> leaves);
	/** Collects candidates for the merge in the merge queue.
		@returns number of leaves in queue
	*/
	int CollectMergeCandidates(const VssRayContainer &rays);

	/** Take 3 ray endpoints, where two are minimum and one a maximum
		point or the other way round.
	*/
	Plane3 ChooseCandidatePlane(const RayInfoContainer &rays) const;

	/** Take plane normal as plane normal and the midpoint of the ray.
		PROBLEM: does not resemble any point where visibility is 
		likely to change
	*/
	Plane3 ChooseCandidatePlane2(const RayInfoContainer &rays) const;

	/** Fit the plane between the two lines so that the plane 
		has equal shortest distance to both lines.
	*/
	Plane3 ChooseCandidatePlane3(const RayInfoContainer &rays) const;
  
	/** Shuffles, i.e. takes border leaf from view cell 1 and adds it 
		to view cell 2.
	*/
	void ShuffleLeaf(BspLeaf *leaf, 
					 BspViewCell *vc1, 
					 BspViewCell *vc2) const;

	
	/** Propagates valid flag up the tree.
	*/
	void PropagateUpValidity(BspNode *node);

	/** Writes the node to disk
		@note: should be implemented as visitor
	*/
	void ExportNode(BspNode *node, ofstream &stream);

	/** Returns memory usage of tree.
	*/
	float GetMemUsage() const;

	/** Calculates cost for merge of view cell 1 and 2.
	*/
	float GetShuffledVcCost(BspLeaf *leaf, BspViewCell *vc1, BspViewCell *vc2) const;

	void ExportMergedViewCells(ViewCellContainer &viewCells, 
							   const ObjectContainer &objects,
							   const int nViewCells);

	/// Pointer to the root of the tree
	BspNode *mRoot;
		
	BspTreeStatistics mStat;

	/// Strategies for choosing next split plane.
	enum {NO_STRATEGY = 0,
		  RANDOM_POLYGON = 1, 
		  AXIS_ALIGNED = 2,
		  LEAST_RAY_SPLITS = 256,
		  BALANCED_RAYS = 512,
		  PVS = 1024
		};

	/// box around the whole view domain
	AxisAlignedBox3 mBox;

	/// minimal number of rays before subdivision termination
	int mTermMinRays;
	/// maximal possible depth
	int mTermMaxDepth;
	/// mininum probability
	float mTermMinProbability;
	/// mininum PVS
	int mTermMinPvs;
	/// maximal contribution per ray
	float mTermMaxRayContribution;
	/// minimal accumulated ray length
	float mTermMinAccRayLength;

	ofstream mStats;

	//-- termination criteria for axis aligned split

	/// minimal number of rays for axis aligned split
	int mTermMinRaysForAxisAligned;
	// max ray contribution
	float mTermMaxRayContriForAxisAligned;

	/// strategy to get the best split plane
	int mSplitPlaneStrategy;
	/// number of candidates evaluated for the next split plane
	int mMaxPolyCandidates;
	/// number of candidates for split planes evaluated using the rays
	int mMaxRayCandidates;
	/// balancing factor for PVS criterium
	float mCtDivCi;

	//-- axis aligned split criteria
	float mAxisAlignedCtDivCi;
	/// spezifies the split border of the axis aligned split
	float mAxisAlignedSplitBorder;

	/// maximal acceptable cost ratio
	float mTermMaxCostRatio;
	/// tolerance value indicating how often the max cost ratio can be failed
	int mTermMissTolerance;

	//-- factors guiding the split plane heuristics
	float mLeastRaySplitsFactor;
	float mBalancedRaysFactor;
	float mPvsFactor;

	/// if area or volume should be used for PVS heuristics
	bool mUseAreaForPvs;
	/// tolerance for polygon split
	float mEpsilon;
	/// maximal number of test rays used to evaluate candidate split plane
	int mMaxTests;
	/// normalizes different bsp split plane criteria
	float mCostNormalizer;
	/// maximal number of view cells
	int mMaxViewCells;
	/// minimal number of view cells
	int mMergeMinViewCells;
	/// maximal cost ratio for the merge
	float mMergeMaxCostRatio;

	// if rays should be stored in leaves
	bool mStoreRays;
	
	/// if only driving axis should be used for split
	bool mOnlyDrivingAxis;

	ViewCellsManager *mViewCellsManager;

	vector<SortableEntry> *mSplitCandidates;


	typedef priority_queue<BspMergeCandidate> MergeQueue;

	MergeQueue mMergeQueue;

	/// if rays should be used to collect merge candidates
	bool mUseRaysForMerge;
	
	/// View cell corresponding to the space outside the valid view space
	BspViewCell *mOutOfBoundsCell;

	int mCurrentViewCellsId;

	/// maximal tree memory
	float mMaxMemory;
	/// the tree is out of memory
	bool mOutOfMemory;
	/// if merge visualization should be shown
	bool mExportMergedViewCells;
	/// if merge statistics should be exported
	bool mExportMergeStats;

private:
	
	ViewCellContainer mOldViewCells;
	ViewCellContainer mNewViewCells;

	static const float sLeastRaySplitsTable[5];
	/** Evaluates split plane classification with respect to the plane's 
		contribution for balanced rays.
	*/
	static const float sBalancedRaysTable[5];

	/// Generates unique ids for PVS criterium
	static void GenerateUniqueIdsForPvs();

	//-- unique ids for PVS criterium
	static int sFrontId; 
	static int sBackId;
	static int sFrontAndBackId;
};

/**
	Candidate for leaf merging based on priority.
*/
class BspMergeCandidate
{  
public:

	BspMergeCandidate(BspLeaf *l1, BspLeaf *l2);

	/** If this merge pair is still valid.
	*/
	bool Valid() const;

	/** Sets this merge candidate to be valid.
	*/
	void SetValid();

	friend bool operator<(const BspMergeCandidate &leafa, const BspMergeCandidate &leafb)
	{
		return leafb.GetMergeCost() < leafa.GetMergeCost();
	}

	void SetLeaf1(BspLeaf *l);
	void SetLeaf2(BspLeaf *l);

	BspLeaf *GetLeaf1();
	BspLeaf *GetLeaf2();

	/** Merge cost of this candidate pair.
	*/
	float GetMergeCost() const;

	/** Returns cost of leaf 1.
	*/
	float GetLeaf1Cost() const;
	/** Returns cost of leaf 2.
	*/
	float GetLeaf2Cost() const;

	/// maximal pvs size
	static int sMaxPvsSize;
	/// minimal pvs size
	//static int sMinPvsSize;

	/// overall cost used to normalize cost ratio
	static float sOverallCost;
	// if area or volume should be used for the merge heuristics
	static bool sUseArea;

	/** Evaluates the merge costs of the leaves.
	*/
	void EvalMergeCost();

protected:

	/** Cost of a view cell.
	*/
	float GetCost(ViewCell *vc) const;
	
	int mLeaf1Id;
	int mLeaf2Id;

	float mMergeCost;
	
	BspLeaf *mLeaf1;
	BspLeaf *mLeaf2;
};


class MergeStatistics: public StatisticsBase
{
public:
	
	int merged;
	int siblings;
	int candidates;
	int nodes;

	int accTreeDist;
	int maxTreeDist;
	
	Real collectTime;
	Real mergeTime;

	Real overallCost;

	// Constructor
	MergeStatistics() 
	{
		Reset();
	}
	
	double AvgTreeDist() const {return (double)accTreeDist / (double)merged;}; 

	void Reset() 
	{
		nodes = 0;
		merged = 0;
		siblings = 0;
		candidates = 0;
	
		accTreeDist = 0;
		maxTreeDist = 0;

		collectTime = 0;
		mergeTime = 0;
		overallCost = 0;
	}

	void Print(ostream &app) const;

	friend ostream &operator<<(ostream &s, const MergeStatistics &stat) 
	{
		stat.Print(s);
		return s;
	} 
};

#endif