#ifndef _FromPointVisibilityTree_H__
#define _FromPointVisibilityTree_H__

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

namespace GtpVisibilityPreprocessor {

class ViewCell;
class Plane3;
class FromPointVisibilityTree;  
class BspInterior;
class BspNode;
class AxisAlignedBox3;
class Ray;
class ViewCellsStatistics;
class ViewCellsManager;
class MergeCandidate;
class Beam;
class ViewCellsTree;



/** A location in space representing from point-visibility.
*/
struct VisibilityPoint
{
	Vector3 mPosition;

	/// from point visibility => visible objects, not potentially
	ObjectPvs mVisibleObjects;
};


/**
	This is a tree which partitions from point queries in a greedy optimal fashion.
*/
class FromPointVisibilityTree 
{
	friend class ViewCellsParseHandlers;
	friend class VspBspViewCellsManager;

public:
	
	/** Additional data which is passed down the BSP tree during traversal.
	*/
	class VspBspTraversalData
	{  
	public:
		/// 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;
		// current axis
		int mAxis;
		// current priority
		float mPriority;

		
		/** 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),
		mPriority(0),
		mAxis(0)
		{}
		
		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),
		mPriority(0),
		mAxis(0)
		{}

		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),
		mAxis(0)
		{}

		/** Returns cost of the traversal data.
		*/
		float GetCost() const
		{
			//cout << mPriority << endl;
			return mPriority;
		}

		// 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> VspBspTraversalQueue;
	
	
	struct VspBspSplitCandidate
	{  
		/// the current node
		Plane3 mSplitPlane;
		/// split axis of this plane (0, 1, 2, or 3 if non-axis-aligned)
		int mSplitAxis;
		/// the number of misses of max cost ratio until this split
		int mMaxCostMisses;

		// parent data
		VspBspTraversalData mParentData;
		// cost of applying this split
		float mRenderCost;

		VspBspSplitCandidate(): mRenderCost(0) 
		{};

		VspBspSplitCandidate(const Plane3 &plane, const VspBspTraversalData &tData): 
		mSplitPlane(plane), mParentData(tData), mRenderCost(0)
		{}

		/** Returns cost of the traversal data.
		*/
		float GetCost() const
		{
#if 1
			return mRenderCost;
#endif
#if 0
			return (float) (-mDepth); // for kd tree
#endif
		}

		friend bool operator<(const VspBspSplitCandidate &a, const VspBspSplitCandidate &b)
		{
			return a.GetCost() < b.GetCost();
		}
    };

	typedef std::priority_queue<VspBspSplitCandidate> VspBspSplitQueue;

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

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

	/** 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
	*/
	void Construct(const VssRayContainer &sampleRays,
				   AxisAlignedBox3 *forcedBoundingBox);

	
	/** Constructs the tree from a given set of visibility points
		@param visibiltiyPointe visibility points the construction is based on
	*/
	void Construct(const VisibilityPointsContainer &visibilityPoints, 
				   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(ViewCell *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;

	/** 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);


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

	
	int FindApproximateNeighbors(BspNode *n, 
							     vector<BspLeaf *> &neighbors,
								 const bool onlyUnmailed) const;

	/** Checks if tree validity-flags are right 
		with respect to view cell valitiy.
		If not, marks subtree as invalid.
	*/
	void ValidateTree();

	/** Invalid view cells are added to the unbounded space
	*/
	void CollapseViewCells();

	/** Collects rays stored in the leaves.
	*/
	void CollectRays(VssRayContainer &rays);

	/** Intersects box with the tree and returns the number of intersected boxes.
		@returns number of view cells found
	*/
	int ComputeBoxIntersections(const AxisAlignedBox3 &box, ViewCellContainer &viewCells) const;

	// pointer to the hierarchy of view cells
	ViewCellsTree *mViewCellsTree;


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;

	/** Evaluates candidate for splitting.
	*/
	void EvalSplitCandidate(VspBspTraversalData &tData, VspBspSplitCandidate &splitData);

	/** Computes priority of the traversal data and stores it in tData.
	*/
	void EvalPriority(VspBspTraversalData &tData) const;

	float EvalRenderCostDecrease(const Plane3 &candidatePlane,
								 const VspBspTraversalData &data) const;

	void ConstructWithSplitQueue(const PolygonContainer &polys, RayInfoContainer *rays);


	/** 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);

	/** 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(VspBspTraversalQueue &tStack, 
					   VspBspTraversalData &tData);

	BspNode *Subdivide(VspBspSplitQueue &tQueue,
					   VspBspSplitCandidate &splitCandidate);

	/** 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,
					 int &splitAxis);
	
	/** Strategies where the effect of the split plane is tested
	    on all input rays.

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

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

	BspInterior *SubdivideNode(const Plane3 &splitPlane,
							   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, 
							 float minBand, 
							 float maxBand);

	/** 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) const;


	/** 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, 
					 float &frontPvs, 
					 float &backPvs, 
					 float &totalPvs) const;
	
	/** Computes PVS size induced by the rays.
	*/
	int ComputePvsSize(const RayInfoContainer &rays) const;

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

	/** Returns true if global tree can be terminated.
	*/
	inline bool GlobalTerminationCriteriaMet(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);





	
	/** 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;
  
	/** Collects candidates for merging.
		@param leaves the leaves to be merged
		@returns number of leaves in queue
	*/
	int CollectMergeCandidates(const vector<BspLeaf *> leaves, vector<MergeCandidate> &candidates);

	/** Collects candidates for the merge in the merge queue.
		@returns number of leaves in queue
	*/
	int CollectMergeCandidates(const VssRayContainer &rays, vector<MergeCandidate> &candidates);
	
	/** Preprocesses polygons and throws out all polygons which are coincident to
		the view space box faces (they can be problematic).
	*/
	void PreprocessPolygons(PolygonContainer &polys);
	
	/** 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 estimated memory usage of tree.
	*/
	//float GetMemUsage(const VspBspTraversalQueue &tstack) const;
	float GetMemUsage() const;



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

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

	bool mUseCostHeuristics;

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

	//HACK
	int mTermMinPolygons;

	float mTermMinGlobalCostRatio;
	int mTermGlobalCostMissTolerance;

	int mGlobalCostMisses;

	bool mUseSplitCostQueue;
	//-- 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;
	
	ofstream  mSubdivisionStats;

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

	
	float mRenderCostWeight;
	/// View cell corresponding to the space outside the valid view space
	BspViewCell *mOutOfBoundsCell;

	/// maximal tree memory
	float mMaxMemory;
	/// the tree is out of memory
	bool mOutOfMemory;
	
	float mTotalCost;
	int mTotalPvsSize;

	float mMinBand;
	float mMaxBand;

	//int mSplits;
	/// subdivision stats output file
	ofstream mSubdivsionStats;
	/// if random split axis should be used
	bool mUseRandomAxis;
	/// use polygon split whenever there are polys left
	bool mUsePolygonSplitIfAvailable;
	/// current time stamp (used for keeping split history)
	int mTimeStamp;
	/// number of currenly generated view cells
	int mCreatedViewCells;
	/// if vsp bsp tree should simulate octree
	bool mCirculatingAxis;

	/// if we should use breath first priority for the splits
	int mNodePriorityQueueType;

	// priority queue strategy
	enum {BREATH_FIRST, DEPTH_FIRST, COST_BASED};


private:

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

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

}


#endif