#ifndef _VspOspTree_H__
#define _VspOspTree_H__

#include <stack>

#include "Mesh.h"
#include "Containers.h"
#include "Statistics.h"
#include "VssRay.h"
#include "RayInfo.h"
#include "gzstream.h"
#include "FlexibleHeap.h"


namespace GtpVisibilityPreprocessor {

class ViewCellLeaf;
//class VspViewCell;
class Plane3;
class AxisAlignedBox3;
class Ray;
class ViewCellsStatistics;
class ViewCellsManager;
class MergeCandidate;
class Beam;
class ViewCellsTree;
class Environment;
class VspInterior;
class VspLeaf;
class VspNode;
class KdNode;
class KdInterior;
class KdLeaf;
class OspTree;
class KdIntersectable;
class KdTree;
class VspTree;
class KdTreeStatistics;



template <typename T> class GtPriority
{
public:
	bool operator() (const T c1, const T c2) const
	{
		//return false;
		return c1->GetPriority() < c2->GetPriority();
	}
};


/** Candidate for a view space / object space split.
*/
class SplitCandidate: public Heapable
{  
public:

	enum {OBJECT_SPACE, VIEW_SPACE};

	/// the current split plane
	AxisAlignedPlane 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;

	/// priority of this split
	//float mPriority;
	
	SplitCandidate()
	{};

	SplitCandidate(const AxisAlignedPlane &plane): mSplitPlane(plane)
	{}

	virtual void EvalPriority() = 0;
	virtual int Type() const = 0;
	virtual bool GlobalTerminationCriteriaMet() const = 0;
};


/** View space partition statistics.
*/
class VspTreeStatistics: public StatisticsBase
{
public:
	// total number of nodes
	int nodes;
	// number of splits
	int splits[3];
	
	// totals number of rays
	int rays;
	// maximal reached depth
	int maxDepth;
	// minimal depth
	int minDepth;
	
	// max depth nodes
	int maxDepthNodes;
	// minimum depth nodes
	int minDepthNodes;
	// max depth nodes
	int minPvsNodes;
	// nodes with minimum PVS
	int minRaysNodes;
	// max ray contribution nodes
	int maxRayContribNodes;
	// minimum area nodes
	int minProbabilityNodes;
	/// nodes termination because of max cost ratio;
	int maxCostNodes;
	// max number of rays per node
	int maxObjectRefs;
	/// samples contributing to pvs
	int contributingSamples;
	/// sample contributions to pvs
	int sampleContributions;
	/// largest pvs
	int maxPvs;
	/// number of invalid leaves
	int invalidLeaves;
	/// accumulated number of rays refs
	int accumRays;
	int pvs;
	// accumulated depth (used to compute average)
	int accumDepth;

	// Constructor
	VspTreeStatistics() 
	{
		Reset();
	}

	int Nodes() const {return nodes;}
	int Interior() const { return nodes / 2; }
	int Leaves() const { return (nodes / 2) + 1; }
	
	// TODO: computation wrong
	double AvgDepth() const { return accumDepth / (double)Leaves();}; 
	double AvgRays() const { return accumRays / (double)Leaves();}; 

	void Reset() 
	{
		nodes = 0;
		for (int i = 0; i < 3; ++ i)
			splits[i] = 0;
		
		maxDepth = 0;
		minDepth = 99999;
		accumDepth = 0;
        pvs = 0;
		maxDepthNodes = 0;
		minPvsNodes = 0;
		minRaysNodes = 0;
		maxRayContribNodes = 0;
		minProbabilityNodes = 0;
		maxCostNodes = 0;

		contributingSamples = 0;
		sampleContributions = 0;

		maxPvs = 0;
		invalidLeaves = 0;
		accumRays = 0;
	}

	void Print(ostream &app) const;

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


/** View space partition statistics.
*/
class OspTreeStatistics: public StatisticsBase
{
public:
	// total number of nodes
	int nodes;
	// number of splits
	int splits[3];
	
	// maximal reached depth
	int maxDepth;
	// minimal depth
	int minDepth;
	
	// max depth nodes
	int maxDepthNodes;
	// minimum depth nodes
	int minDepthNodes;
	// max depth nodes
	int minPvsNodes;
	// minimum area nodes
	int minProbabilityNodes;
	/// nodes termination because of max cost ratio;
	int maxCostNodes;
	// max number of objects per node
	int maxObjectRefs;
	int objectRefs;
	/// samples contributing to pvs
	int contributingSamples;
	/// sample contributions to pvs
	int sampleContributions;
	/// largest pvs
	int maxPvs;
	/// number of invalid leaves
	int invalidLeaves;
	/// accumulated number of rays refs
	int accumRays;
	/// potentially visible objects from this leaf
	int pvs;

	// accumulated depth (used to compute average)
	int accumDepth;

	// Constructor
	OspTreeStatistics() 
	{
		Reset();
	}

	int Nodes() const {return nodes;}
	int Interior() const { return nodes / 2; }
	int Leaves() const { return (nodes / 2) + 1; }
	
	// TODO: computation wrong
	double AvgDepth() const { return accumDepth / (double)Leaves();}; 
	

	void Reset() 
	{
		nodes = 0;
		for (int i = 0; i < 3; ++ i)
			splits[i] = 0;
		
		maxDepth = 0;
		minDepth = 99999;
		accumDepth = 0;
        pvs = 0;
		maxDepthNodes = 0;
		minPvsNodes = 0;
	
		minProbabilityNodes = 0;
		maxCostNodes = 0;

		contributingSamples = 0;
		sampleContributions = 0;

		maxPvs = 0;
		invalidLeaves = 0;
		objectRefs = 0;
	}


	void Print(ostream &app) const;

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


/**
    VspNode abstract class serving for interior and leaf node implementation
*/
class VspNode
{
public:
	
	// types of vsp nodes
	enum {Interior, Leaf};

	VspNode();
	virtual ~VspNode(){};
	VspNode(VspInterior *parent);

	/** Determines whether this node is a leaf or not
		@return true if leaf
	*/
	virtual bool IsLeaf() const = 0;

	virtual int Type() const = 0;

	/** Determines whether this node is a root
		@return true if root
	*/
	virtual bool IsRoot() const;

	/** Returns parent node.
	*/
	VspInterior *GetParent();

	/** Sets parent node.
	*/
	void SetParent(VspInterior *parent);

	/** Returns true if this node is a sibling of node n.
	*/
	bool IsSibling(VspNode *n) const;

	/** returns depth of the node.
	*/
	int GetDepth() const;

	/** returns true if the whole subtree is valid
	*/
	bool TreeValid() const;

	void SetTreeValid(const bool v);

	//-- mailing options

	void Mail() { mMailbox = sMailId; }
	static void NewMail() { ++ sMailId; }
	bool Mailed() const { return mMailbox == sMailId; }

	static int sMailId;
	int mMailbox;

	int mTimeStamp;

protected:

	/// if this sub tree is a completely valid view space region
	bool mTreeValid;
	/// parent of this node
	VspInterior *mParent;
};


/** BSP interior node implementation 
*/
class VspInterior: public VspNode 
{
public:
	/** Standard contructor taking split plane as argument.
	*/
	VspInterior(const AxisAlignedPlane &plane);

	~VspInterior();
	/** @return false since it is an interior node 
	*/
	bool IsLeaf() const;

	int Type() const;

	VspNode *GetBack();
	VspNode *GetFront();

	/** Returns split plane.
	*/
	AxisAlignedPlane GetPlane() const;

	/** Returns position of split plane.
	*/
	float GetPosition() const;

	/** Returns split axis.
	*/
	int GetAxis() const;

	/** Replace front or back child with new child.
	*/
	void ReplaceChildLink(VspNode *oldChild, VspNode *newChild);

	/** Replace front and back child.
	*/
	void SetupChildLinks(VspNode *front, VspNode *back);

	friend ostream &operator<<(ostream &s, const VspInterior &A)
	{
		return s << A.mPlane.mAxis << " " << A.mPlane.mPosition;
	}

	AxisAlignedBox3 GetBoundingBox() const;
	void SetBoundingBox(const AxisAlignedBox3 &box);

	/** Computes intersection of this plane with the ray segment.
	*/
	int ComputeRayIntersection(const RayInfo &rayData, float &t) const
	{
		return rayData.ComputeRayIntersection(mPlane.mAxis, mPlane.mPosition, t);
	}


protected:

	AxisAlignedBox3 mBoundingBox;

	/// Splitting plane corresponding to this node
	AxisAlignedPlane mPlane;

	/// back node
	VspNode *mBack;
	/// front node
	VspNode *mFront;
};


/** BSP leaf node implementation.
*/
class VspLeaf: public VspNode 
{
	friend VspTree;

public:
	VspLeaf();
	VspLeaf(ViewCellLeaf *viewCell);
	VspLeaf(VspInterior *parent);
	VspLeaf(VspInterior *parent, ViewCellLeaf *viewCell);

	~VspLeaf();

	/** @return true since it is an interior node 
	*/
	bool IsLeaf() const;
	
	int Type() const;

	/** Returns pointer of view cell.
	*/
	ViewCellLeaf *GetViewCell() const;

	/** Sets pointer to view cell.
	*/
	void SetViewCell(ViewCellLeaf *viewCell);

	SplitCandidate *GetSplitCandidate() const 
	{ return mSplitCandidate; }

public:

	/// Rays piercing this leaf.
	VssRayContainer mVssRays;
	
	/// leaf pvs
	ObjectPvs *mPvs;

	/// Probability that the view point lies in this leaf
	float mProbability;

protected:

	/// pointer to a split plane candidate splitting this leaf
	SplitCandidate *mSplitCandidate;

	/// if NULL this does not correspond to feasible viewcell
	ViewCellLeaf *mViewCell;
};


#if 0
typedef std::priority_queue<SplitCandidate *, 
							std::vector<SplitCandidate *>, 
							GtPriority<std::vector<SplitCandidate *>::value_type> > SplitQueue;
#endif

typedef map<KdNode *, KdIntersectable *> KdIntersectableMap;

typedef FlexibleHeap<SplitCandidate *> SplitQueue;

/** View Space Partitioning tree.
*/
class VspTree 
{
	friend class ViewCellsParseHandlers;
	friend class HierarchyManager;

public:
	
	/** Additional data which is passed down the BSP tree during traversal.
	*/
	class VspTraversalData
	{  
	public:
		/// the current node
		VspLeaf *mNode;
		/// current depth
		int mDepth;
		/// rays piercing this node
		RayInfoContainer *mRays;
		/// the probability that this node contains view point
		float mProbability;
		/// the bounding box of the node
		AxisAlignedBox3 mBoundingBox;
		/// pvs size
		int mPvs;
		/// how often this branch has missed the max-cost ratio
		int mMaxCostMisses;
		// current priority
		float mPriority;

		
		/** Returns average ray contribution.
		*/
		float GetAvgRayContribution() const
		{
			return (float)mPvs / ((float)mRays->size() + Limits::Small);
		}


		VspTraversalData():
		mNode(NULL),
		mDepth(0),
		mRays(NULL),
		mPvs(0),
		mProbability(0.0),
		mMaxCostMisses(0), 
		mPriority(0)
		{}
		
		VspTraversalData(VspLeaf *node, 
						 const int depth, 
						 RayInfoContainer *rays,
						 const int pvs,
						 const float p,
						 const AxisAlignedBox3 &box):
		mNode(node), 
		mDepth(depth), 
		mRays(rays),
		mPvs(pvs),
		mProbability(p),
		mBoundingBox(box),
		mMaxCostMisses(0),
		mPriority(0)
		{}

		VspTraversalData(const int depth, 
						 RayInfoContainer *rays,
						 const AxisAlignedBox3 &box): 
		mNode(NULL), 
		mDepth(depth), 
		mRays(rays),
		mPvs(0),
		mProbability(0),
		mMaxCostMisses(0),
		mBoundingBox(box)
		{}

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

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

	/** Candidate for a view space split.
	*/
	class VspSplitCandidate: public SplitCandidate
	{  
	public:

		static VspTree* sVspTree;

		/// parent node traversal data
		VspTraversalData mParentData;
		
		VspSplitCandidate(const VspTraversalData &tData): mParentData(tData)
		{};

		int Type() const { return VIEW_SPACE; }

		void EvalPriority()
		{
			sVspTree->EvalSplitCandidate(*this);	
		}

		bool GlobalTerminationCriteriaMet() const
		{
			return sVspTree->GlobalTerminationCriteriaMet(mParentData);
		}

		VspSplitCandidate(const AxisAlignedPlane &plane, const VspTraversalData &tData): 
		SplitCandidate(plane), mParentData(tData)
		{}
	};

	/** Struct for traversing line segment.
	*/
	struct LineTraversalData 
	{
		VspNode *mNode;
		Vector3 mExitPoint;
		
		float mMaxT;
    
		LineTraversalData () {}
		LineTraversalData (VspNode *n, const Vector3 &p, const float maxt):
		mNode(n), mExitPoint(p), mMaxT(maxt) {}
	};

	//typedef std::priority_queue<VspTraversalData> VspOspTraversalQueue;

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

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

	/** Returns BSP Tree statistics.
	*/
	const VspTreeStatistics &GetStatistics() const; 
  
	/** Returns bounding box of the specified node.
	*/
	AxisAlignedBox3 GetBBox(VspNode *node) const;

	/** 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 of a leaf to be added (-1 means unlimited)
	*/
	void CollectLeaves(vector<VspLeaf *> &leaves, 
					   const bool onlyUnmailed = false,
					   const int maxPvs = -1) const;

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

	/** Returns root of the view space partitioning tree.
	*/
	VspNode *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);


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

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

	/** Returns random leaf of BSP tree.
		@param onlyUnmailed if only unmailed leaves should be returned.
	*/
	VspLeaf *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 view cell the current point is located in.
		@param point the current view point
		@param active if currently active view cells should be returned or
		elementary view cell
	*/
	ViewCell *GetViewCell(const Vector3 &point, const bool active = false);


	/** 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.
	*/
	VspViewCell *GetOutOfBoundsCell();

	/** Writes tree to output stream
	*/
#if ZIPPED_VIEWCELLS
	bool Export(ogzstream &stream);
#else
	bool Export(ofstream &stream);
#endif

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


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

	/** Remove the references of the parent view cell from the kd nodes associated with
		the objects.
	*/
	void RemoveParentViewCellReferences(ViewCell *parent) const;

	/** Adds references to the view cell to the kd nodes associated with the objects.
	*/
	void AddViewCellReferences(ViewCell *vc) const;

	/** Returns view cells of this ray, either taking precomputed cells
		or by recomputation.
	*/
	void GetViewCells(const VssRay &ray, ViewCellContainer &viewCells);


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

	OspTree *mOspTree;

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 EvalLocalSplitCost(const VspTraversalData &data,
							 const AxisAlignedBox3 &box,
							 const int axis,
							 const float &position,
							 float &pFront,
							 float &pBack) const;

	void ComputeBoundingBox(const VssRayContainer &rays,
							AxisAlignedBox3 *forcedBoundingBox);

	/** Evaluates candidate for splitting.
	*/
	void EvalSplitCandidate(VspSplitCandidate &splitData);

	/** Evaluates render cost decrease of next split.
	*/
	float EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
								 const VspTraversalData &data) const;

	/** Collects view cells in the subtree under root.
	*/
	void CollectViewCells(VspNode *root, 
						  bool onlyValid, 
						  ViewCellContainer &viewCells,
						  bool onlyUnmailed = false) const;

	/** Returns view cell corresponding to 
		the invalid view space. If it does not exist, it is created.
	*/
	VspViewCell *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
	*/
	VspNode *CollapseTree(VspNode *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 VspTraversalData &data);

	/** Subdivides node using a best split priority queue.
	    @param tQueue the best split priority queue
		@param splitCandidate the candidate for the next split
		@param globalCriteriaMet if the global termination criteria were already met
		@returns new root of the subtree
	*/
	VspNode *Subdivide(SplitQueue &tQueue,
					   VspSplitCandidate &splitCandidate,
					   const bool globalCriteriaMet);

	/** Adds stats to subdivision log file.
	*/
	void AddSubdivisionStats(const int viewCells,
							 const float renderCostDecr,
							 const float splitCandidateCost,
							 const float totalRenderCost,
							 const float avgRenderCost);
	
	/** Subdivides leaf.
			
		@param tData data object holding, e.g., a pointer to the leaf
		@param frontData returns the data (e.g.,  pointer to the leaf) in front of the split plane
		@param backData returns the data (e.g.,  pointer to the leaf) 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
	
		@returns the root of the subdivision
	*/
	VspInterior *SubdivideNode(const AxisAlignedPlane &splitPlane,
							   VspTraversalData &tData,
							   VspTraversalData &frontData,
                               VspTraversalData &backData);

	/** Selects an axis aligned for the next split.
		@returns cost for this split
	*/
	float SelectSplitPlane(const VspTraversalData &tData,
						   AxisAlignedPlane &plane,
						   float &pFront,
						   float &pBack);

	/** Sorts split candidates along the specified axis.
		The split candidates are generated on possible visibility
		events (i.e., where ray segments intersect the ray boundaries).
		The sorted candidates are needed to compute the heuristics.

		@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 pvs increase with respect to the previous pvs for heuristics.
	*/
	int GetPvsIncr(Intersectable *object, const KdPvsMap &activeNodes);

	/** Returns absolute pvs contribution of this object.
	*/
	int GetPvsContribution(Intersectable *object) const;

	/** Computes best cost for axis aligned planes.
	*/
	float EvalLocalCostHeuristics(const VspTraversalData &tData,
								  const AxisAlignedBox3 &box,
								  const int axis,
								  float &position);

	/** Evaluates the influence on the pvs of the visibility event ve.
		@param ve the visibility event
		@param pvsLeft updates the left pvs
		@param rightPvs updates the right pvs
	*/
	void EvalPvsIncr(const SortableEntry &ve,
					  int &pvsLeft,
					  int &pvsRight) const;

	void RemoveContriFromPvs(KdLeaf *leaf, int &pvs) const;
	void AddContriToPvs(KdLeaf *leaf, int &pvs) const;

	/** Prepares objects for the heuristics.
		@returns pvs size of the ray container
	*/
	int PrepareHeuristics(const RayInfoContainer &rays);

	int PrepareHeuristics(KdLeaf *leaf);

	/** 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 AxisAlignedPlane &plane,
				  RayInfoContainer &rays, 
			      RayInfoContainer &frontRays, 
				  RayInfoContainer &backRays) 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;
	
	/** Collects pvs from rays.
	*/
	void CollectPvs(const RayInfoContainer &rays,
					ObjectContainer &objects) const;

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

	/** Returns true if global tree can be terminated.
	*/
	inline bool GlobalTerminationCriteriaMet(const VspTraversalData &data) const;

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

	bool AddKdLeafToPvs(KdLeaf *leaf, ViewCell *vc, float &pvs, float &contribution);

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

	/** Writes the node to disk
		@note: should be implemented as visitor.
	*/
#if ZIPPED_VIEWCELLS
	void ExportNode(VspNode *node, ogzstream &stream);
#else
	void ExportNode(VspNode *node, ofstream &stream);
#endif

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

	void ProcessViewCellObjects(ViewCell *parent, 
		ViewCell *front, 
		ViewCell *back) const;

	void CreateViewCell(VspTraversalData &tData, const bool updatePvs);

	void CollectDirtyCandidates(VspSplitCandidate *sc, 
		vector<SplitCandidate *> &dirtyList);

	KdNode *GetKdNode(VssRay &ray, const bool termination) const;

	void ProcessRays(const VssRayContainer &sampleRays,
		RayInfoContainer &rays);

protected:

	bool mUseKdPvsForHeuristics;
	bool mStoreKdPvs;

	ViewCellsManager *mViewCellsManager;
	
	vector<SortableEntry> *mSplitCandidates;

	/// Pointer to the root of the tree
	VspNode *mRoot;
		
	VspTreeStatistics mVspStats;
	
	/// View cell corresponding to the space outside the valid view space
	VspViewCell *mOutOfBoundsCell;

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


	//-- local termination

	/// 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;
	/// maximal acceptable cost ratio
	float mTermMaxCostRatio;
	/// tolerance value indicating how often the max cost ratio can be failed
	int mTermMissTolerance;


	//-- global criteria
	float mTermMinGlobalCostRatio;
	int mTermGlobalCostMissTolerance;
	int mGlobalCostMisses;

	/// maximal number of view cells
	int mMaxViewCells;
	/// maximal tree memory
	float mMaxMemory;
	/// the tree is out of memory
	bool mOutOfMemory;



	//-- split heuristics based parameters
	
	bool mUseCostHeuristics;
	/// balancing factor for PVS criterium
	float mCtDivCi;	
	/// if only driving axis should be used for split
	bool mOnlyDrivingAxis;
	/// if random split axis should be used
	bool mUseRandomAxis;
	/// if vsp bsp tree should simulate octree
	bool mCirculatingAxis;
	/// minimal relative position where the split axis can be placed
	float mMinBand;
	/// maximal relative position where the split axis can be placed
	float mMaxBand;


	/// current time stamp (used for keeping split history)
	int mTimeStamp;
	// if rays should be stored in leaves
	bool mStoreRays;

	/// epsilon for geometric comparisons
	float mEpsilon;


	/// subdivision stats output file
	ofstream  mSubdivisionStats;
	/// keeps track of cost during subdivision
	float mTotalCost;
	/// keeps track of overall pvs size during subdivision
	int mTotalPvsSize;
	/// number of currenly generated view cells
	int mCreatedViewCells;

	/// weight between render cost decrease and node render cost
	float mRenderCostDecreaseWeight;
};


/** View Space Partitioning tree.
*/
class OspTree 
{
	friend class ViewCellsParseHandlers;
	friend class HierarchyManager;

public:
	
	/** Additional data which is passed down the BSP tree during traversal.
	*/
	class OspTraversalData
	{  
	public:
		/// the current node
		KdLeaf *mNode;
		/// current depth
		int mDepth;
		/// rays piercing this node
		RayInfoContainer *mRays;
		/// the probability that this node contains view point
		float mProbability;
		/// the bounding box of the node
		AxisAlignedBox3 mBoundingBox;
		/// pvs size
		int mPvs;
		/// how often this branch has missed the max-cost ratio
		int mMaxCostMisses;
		// current axis
		int mAxis;
		// current priority
		float mPriority;


		OspTraversalData():
		mNode(NULL),
		mRays(NULL),
		mDepth(0),
		mPvs(0),
		mProbability(0.0),
		mMaxCostMisses(0), 
		mPriority(0),
		mAxis(0)
		{}
		
		OspTraversalData(KdLeaf *node, 
						 const int depth,
                         RayInfoContainer *rays,
						 const int pvs,
						 const float p,
						 const AxisAlignedBox3 &box):
		mNode(node), 
		mDepth(depth),
		mRays(rays),
		mPvs(pvs),
		mProbability(p),
		mBoundingBox(box),
		mMaxCostMisses(0),
		mPriority(0),
		mAxis(0)
		{}

		OspTraversalData(const int depth, 
			RayInfoContainer *rays,
			const AxisAlignedBox3 &box): 
		mNode(NULL), 
		mDepth(depth),
		mRays(rays),
		mPvs(0),
		mProbability(0),
		mMaxCostMisses(0),
		mAxis(0),
		mBoundingBox(box)
		{}

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


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

	/** Candidate for a view space split.
	*/
	class OspSplitCandidate: public SplitCandidate
	{  
	public:
		static OspTree* sOspTree;

		/// parent data
		OspTraversalData mParentData;
		
		OspSplitCandidate(const OspTraversalData &tData): mParentData(tData)
		{};

		int Type() const { return OBJECT_SPACE; }
	
		void EvalPriority()
		{
			sOspTree->EvalSplitCandidate(*this);	
		}

		bool GlobalTerminationCriteriaMet() const
		{
			return sOspTree->GlobalTerminationCriteriaMet(mParentData);
		}


		OspSplitCandidate(const AxisAlignedPlane &plane, const OspTraversalData &tData): 
		SplitCandidate(plane), mParentData(tData)
		{}
	};

	/** Struct for traversing line segment.
	*/
	struct LineTraversalData 
	{
		KdNode *mNode;
		Vector3 mExitPoint;
		
		float mMaxT;
    
		LineTraversalData () {}
		LineTraversalData (KdNode *n, const Vector3 &p, const float maxt):
		mNode(n), mExitPoint(p), mMaxT(maxt) {}
	};

	//typedef std::priority_queue<VspTraversalData> VspOspTraversalQueue;

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

	OspTree(const KdTree &kdTree);

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

	/** Returns tree statistics.
	*/
	const OspTreeStatistics &GetStatistics() const; 
  
	/** Returns bounding box of the specified node.
	*/
	AxisAlignedBox3 GetBBox(KdNode *node) const;

	/** Returns list of leaves with pvs smaller than
		a certain threshold.
		@param onlyUnmailed if only the unmailed leaves should be considered
		@param maxPvs the maximal pvs of a leaf to be added (-1 means unlimited)
	*/
	
	void CollectLeaves(vector<KdLeaf *> &leaves) const;


	/** Returns bounding box of the whole tree (= bbox of root node)
	*/
	AxisAlignedBox3 GetBoundingBox()const;

	/** Returns root of the view space partitioning tree.
	*/
	KdNode *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);

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

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

	/** Returns random leaf of BSP tree.
		@param onlyUnmailed if only unmailed leaves should be returned.
	*/
	KdLeaf *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);

	/** Writes tree to output stream
	*/
#if ZIPPED_VIEWCELLS
	bool Export(ogzstream &stream);
#else
	bool Export(ofstream &stream);
#endif

	/** Returns or creates a new intersectable for use in a kd based pvs.
		The OspTree is responsible for destruction of the intersectable.
	*/
	KdIntersectable *GetOrCreateKdIntersectable(KdNode *node);

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


	/** Compute "pvs size of this object container
		@ note bot relly pvs size just weighted sum of object taking their
		appearances in pvss into account
	*/
	int ComputePvsSize(const ObjectContainer &objects) const;

	KdLeaf *GetLeaf(const Vector3 &pt, KdNode *node) const;


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


protected:

	// --------------------------------------------------------------
	// For sorting objects
	// --------------------------------------------------------------
	struct SortableEntry
	{
		/** There is a 3th "event" for rays which intersect a
			box in the middle. These "events" don't induce a change in
			pvs size, but may induce a change in view cell volume.
		*/
		enum EType 
		{
			BOX_MIN,
			BOX_MAX,
			BOX_INTERSECT
		};

		int mType;
		//int mPvs;
		float mPos;
		VssRay *mRay;
		
		Intersectable *mObject;

		SortableEntry() {}

		SortableEntry(const int type,
			//const float pvs, 
			const float pos,
			Intersectable *obj,
			VssRay *ray):
		mType(type), 
		//mPvs(pvs), 
		mPos(pos), 
		mObject(obj),
		mRay(ray)
		{}

		bool operator<(const SortableEntry &b) const 
		{
			return mPos < b.mPos;
		}
	};

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

	/** Evaluates candidate for splitting.
	*/
	void EvalSplitCandidate(OspSplitCandidate &splitData);

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

	/** Evaluates render cost decrease of next split.
	*/
	float EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
								 const OspTraversalData &data) const;


	/** Collects view cells in the subtree under root.
	*/
	void CollectViewCells(KdNode *root, 
						  bool onlyValid, 
						  ViewCellContainer &viewCells,
						  bool onlyUnmailed = false) const;

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

	/** Subdivides node using a best split priority queue.
	    @param tQueue the best split priority queue
		@param splitCandidate the candidate for the next split
		@param globalCriteriaMet if the global termination criteria were already met
		@returns new root of the subtree
	*/
	KdNode *Subdivide(SplitQueue &tQueue,
					  OspSplitCandidate &splitCandidate,
					  const bool globalCriteriaMet);
	
	/** 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
	*/
	KdInterior *SubdivideNode(
		const AxisAlignedPlane &splitPlane,
		const OspTraversalData &tData,
		OspTraversalData &frontData,
		OspTraversalData &backData);

	void SplitObjects(KdLeaf *leaf,
					  const AxisAlignedPlane & splitPlane,
					  const ObjectContainer &objects,
					  ObjectContainer &front,
					  ObjectContainer &back);

	/** does some post processing on the objects in the new child leaves.
	*/
	void ProcessMultipleRefs(KdLeaf *leaf) const;

	/** Selects an axis aligned for the next split.
		@returns cost for this split
	*/
	float SelectPlane(const OspTraversalData &tData,
					  AxisAlignedPlane &plane,
					  float &pFront,
					  float &pBack);

	/** Sorts split candidates for cost heuristics using axis aligned splits.
		@param node the current node
		@param axis the current split axis
	*/
	void SortSplitCandidates(const OspTraversalData &data,
							 const int axis, 
							 float minBand, 
							 float maxBand);

	/** Computes best cost for axis aligned planes.
	*/
	float EvalLocalCostHeuristics(const OspTraversalData &tData,
		const AxisAlignedBox3 &box,
		const int axis,
		float &position,
		int &objectsFront,
		int &objectsBack);

	/** 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 AxisAlignedPlane &plane,
				  RayInfoContainer &rays, 
			      RayInfoContainer &frontRays, 
				  RayInfoContainer &backRays) 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;
	
	/** Returns true if tree can be terminated.
	*/
	inline bool LocalTerminationCriteriaMet(const OspTraversalData &data) const;

	/** Returns true if global tree can be terminated.
	*/
	inline bool GlobalTerminationCriteriaMet(const OspTraversalData &data) const;

	float SelectSplitPlane(const OspTraversalData &tData,
		AxisAlignedPlane &plane,
		float &pFront,
		float &pBack);
	
	/** Propagates valid flag up the tree.
	*/
	void PropagateUpValidity(KdNode *node);

	/** Writes the node to disk
		@note: should be implemented as visitor.
	*/
#if ZIPPED_VIEWCELLS
	void ExportNode(KdNode *node, ogzstream &stream);
#else
	void ExportNode(KdNode *node, ofstream &stream);
#endif

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

	/** Evaluates the influence on the pvs of the event.
		@param ve the visibility event
		@param pvsLeft updates the left pvs
		@param rightPvs updates the right pvs
	*/
	void EvalHeuristicsContribution(const SortableEntry &ci,
		float &volLeft,
		float &volRight,
		int &pvsLeft,
		int &pvsRight);

	/** Evaluate the contributions of view cell volume of the left and the right view cell.
	*/
	void EvalVolumeContribution(const VssRay &ray, float &volLeft, float &volRight);

	/** Prepares objects for the cost heuristics.
		@returns pvs size of the node
	*/
	float PrepareHeuristics(const OspTraversalData &tData);

	/** Prepares heuristics for a particular ray.
	*/
	float PrepareHeuristics(const VssRay &ray);

	/** Prepares construction for vsp and osp trees.
	*/
	void ComputeBoundingBox(const ObjectContainer &objects,
							AxisAlignedBox3 *forcedBoundingBox);

	void CollectDirtyCandidates(OspSplitCandidate *sc,
		vector<SplitCandidate *> &dirtyList);

	/** Collect view cells which see this kd leaf.
	*/
	void CollectViewCells(KdLeaf *leaf, 
		ViewCellContainer &viewCells);

	void ProcessRays(const VssRayContainer &sampleRays,
		RayInfoContainer &rays);


	void ReadEnvironment();

protected:

	VspTree *mVspTree;

	/// The view cells manager
	ViewCellsManager *mViewCellsManager;

	/// candidates for placing split planes during cost heuristics
	vector<SortableEntry> *mSplitCandidates;

	/// Pointer to the root of the tree
	KdNode *mRoot;
		
	/// Statistics for the object space partition
	OspTreeStatistics mOspStats;
	
	/// box around the whole view domain
	AxisAlignedBox3 mBoundingBox;


	//-- local termination

	/// maximal possible depth
	int mTermMaxDepth;
	/// mininum probability
	float mTermMinProbability;
	/// minimal number of objects
	int mTermMinObjects;
	/// maximal contribution per ray
	float mTermMaxRayContribution;
	/// maximal acceptable cost ratio
	float mTermMaxCostRatio;
	/// tolerance value indicating how often the max cost ratio can be failed
	int mTermMissTolerance;


	//-- global criteria

	float mTermMinGlobalCostRatio;
	int mTermGlobalCostMissTolerance;
	int mGlobalCostMisses;

	/// maximal number of view cells
	int mTermMaxLeaves;
	/// maximal tree memory
	float mMaxMemory;
	/// the tree is out of memory
	bool mOutOfMemory;


	//-- split heuristics based parameters
	
	bool mUseCostHeuristics;
	/// balancing factor for PVS criterium
	float mCtDivCi;	
	/// if only driving axis should be used for split
	bool mOnlyDrivingAxis;
	
	/// current time stamp (used for keeping split history)
	int mTimeStamp;
	// if rays should be stored in leaves
	bool mStoreRays;

	/// epsilon for geometric comparisons
	float mEpsilon;

	/// subdivision stats output file
	ofstream  mSubdivisionStats;
	/// keeps track of cost during subdivision
	float mTotalCost;
	/// keeps track of overall pvs size during subdivision
	int mTotalPvsSize;
	/// number of currenly generated view cells
	int mCreatedLeaves;

	/// represents min and max band for sweep
	float mSplitBorder;

	/// weight between  render cost decrease and node render cost
	float mRenderCostDecreaseWeight;

	/// stores the kd node intersectables used for pvs
	KdIntersectableMap mKdIntersectables;


private:

	bool mCopyFromKdTree;
};


/** This class implements a structure holding two different hierarchies,
	one for object space partitioning and one for view space partitioning.

	The object space and the view space are subdivided using a cost heuristics.
	If an object space split or a view space split is chosen is also evaluated
	based on the heuristics. 
	
	The view space heuristics is evaluated by weighting and adding the pvss of the back and
	front node of each specific split. unlike for the standalone method vspbsp tree,
	the pvs of an object would not be the pvs of single object but that of all objects
	which are contained in the same leaf of the object subdivision. This could be done
	by storing the pointer to the object space partition parent, which would allow access to all children.
	Another possibility is to include traced kd-cells in the ray casing process.

	Accordingly, the object space heuristics is evaluated by storing a pvs of view cells with each object.
	the contribution to an object to the pvs is the number of view cells it can be seen from.

	@note
	There is a potential efficiency problem involved in a sense that once a certain type
	of split is chosen for view space / object space, the candidates for the next split of 
	object space / view space must be reevaluated.
	
*/
class HierarchyManager
{
public:
	/** Constructor taking an object space partition and a view space partition tree.
	*/
	HierarchyManager(VspTree &vspTree, OspTree &ospTree);

	/** Constructs the view space and object space subdivision from a given set of rays
		and a set of objects.
		@param sampleRays the set of sample rays the construction is based on
		@param objects the set of objects
	*/
	void Construct(const VssRayContainer &sampleRays,
				   const ObjectContainer &objects,
				   AxisAlignedBox3 *forcedViewSpace);

	/** Constructs first view cells, then object space partition.
	*/
	void Construct2(const VssRayContainer &sampleRays,
					const ObjectContainer &objects,
					AxisAlignedBox3 *forcedViewSpace);

	/** Constructs only vsp tree.
	*/
	void Construct3(const VssRayContainer &sampleRays,
					const ObjectContainer &objects,
					AxisAlignedBox3 *forcedViewSpace);

public:
	VspTree &mVspTree;
	OspTree &mOspTree;

protected:

	bool GlobalTerminationCriteriaMet(SplitCandidate *candidate) const;

	void PrepareConstruction(const VssRayContainer &sampleRays,
		const ObjectContainer &objects,
		AxisAlignedBox3 *forcedViewSpace,
		RayInfoContainer &viewSpaceRays,
		RayInfoContainer &objectSpaceRays);

	bool FinishedConstruction();

	SplitCandidate *NextSplitCandidate();

	void RepairQueue();

	void CollectDirtyCandidates(vector<SplitCandidate *> &dirtyList);

	SplitCandidate *PrepareVsp(const VssRayContainer &sampleRays,
							   AxisAlignedBox3 *forcedViewSpace,
							   RayInfoContainer &rays);

	SplitCandidate *PrepareOsp(const VssRayContainer &sampleRays,
		const ObjectContainer &objects,
		AxisAlignedBox3 *forcedObjectSpace,
		RayInfoContainer &rays);


protected:

	AxisAlignedBox3 mBoundingBox;

	SplitQueue mTQueue;

	SplitCandidate *mCurrentCandidate;

	//-- global criteria
	float mTermMinGlobalCostRatio;
	int mTermGlobalCostMissTolerance;
	int mGlobalCostMisses;

	/// keeps track of cost during subdivision
	float mTotalCost;
};

}

#endif