#ifndef _BvHierarchy_H__
#define _BvHierarchy_H__

#include <stack>

#include "Mesh.h"
#include "Containers.h"
#include "Statistics.h"
#include "VssRay.h"
#include "RayInfo.h"
#include "gzstream.h"
#include "SubdivisionCandidate.h"
#include "AxisAlignedBox3.h"
#include "IntersectableWrapper.h"
#include "HierarchyManager.h"


namespace GtpVisibilityPreprocessor {


class ViewCellLeaf;
class Plane3;
class AxisAlignedBox3;
class Ray;
class ViewCellsStatistics;
class ViewCellsManager;
class MergeCandidate;
class Beam;
class ViewCellsTree;
class Environment;
class BvhInterior;
class BvhLeaf;
class BvhNode;
class BvhTree;
class VspTree;
class ViewCellsContainer;
class HierarchyManager;


/** View space partition statistics.
*/
class BvhStatistics: public StatisticsBase
{
public:
	
	/// Constructor
	BvhStatistics() 
	{
		Reset();
	}

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

	double AvgObjectRefs() const 
	{ return objectRefs / (double)Leaves(); } 

	double AvgRayRefs() const 
	{ return rayRefs / (double)Leaves(); } 

	
	void Reset() 
	{
		nodes = 0;
		splits = 0;
		maxDepth = 0;

		minDepth = 99999;
		accumDepth = 0;
       	maxDepthNodes = 0;
		minProbabilityNodes = 0;
		maxCostNodes = 0;
		///////////////////
		minObjectsNodes = 0;
		maxObjectRefs = 0;
		minObjectRefs = 999999999;
		objectRefs = 0;
		emptyNodes = 0;

		///////////////////
		minRaysNodes = 0;
		maxRayRefs = 0;
		minRayRefs = 999999999;
		rayRefs = 0;
		maxRayContriNodes = 0;
		mGlobalCostMisses = 0;
	}


public:

	// total number of nodes
	int nodes;
	// number of splits
	int splits;
	// maximal reached depth
	int maxDepth;
	// minimal depth
	int minDepth;
	// max depth nodes
	int maxDepthNodes;
	// accumulated depth (used to compute average)
	int accumDepth;
	// minimum area nodes
	int minProbabilityNodes;
	/// nodes termination because of max cost ratio;
	int maxCostNodes;
	// global cost ratio violations
	int mGlobalCostMisses;

	//////////////////
	// nodes with minimum objects
	int minObjectsNodes;
	// max number of rays per node
	int maxObjectRefs;
	// min number of rays per node
	int minObjectRefs;
	/// object references
	int objectRefs;
	// leaves with no objects
	int emptyNodes;

	//////////////////////////
	// nodes with minimum rays
	int minRaysNodes;
	// max number of rays per node
	int maxRayRefs;
	// min number of rays per node
	int minRayRefs;
	/// object references
	int rayRefs;
	/// nodes with max ray contribution
	int maxRayContriNodes;

	void Print(ostream &app) const;

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


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

	BvhNode();
	BvhNode(const AxisAlignedBox3 &bbox);
	BvhNode(const AxisAlignedBox3 &bbox, BvhInterior *parent);

	virtual ~BvhNode(){};

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

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

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

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

	/** collects all objects under this node.
	*/
	virtual void CollectObjects(ObjectContainer &objects) = 0;

	/** The bounding box specifies the node extent.
	*/
	inline 
	AxisAlignedBox3 GetBoundingBox() const
	{ return mBoundingBox; }

	/** Sets bouding box of this node.
	*/
	inline 
	void SetBoundingBox(const AxisAlignedBox3 &boundingBox) 
	{ mBoundingBox = boundingBox; }

	/** Cost of mergin this node.
	*/
	float GetMergeCost() {return (float)-mTimeStamp; }

	virtual int GetRandomEdgePoint(Vector3 &point, Vector3 &normal);

	inline int GetTimeStamp() const { return mTimeStamp; }
	inline void SetTimeStamp(const int timeStamp) { mTimeStamp = timeStamp; };


	////////////////////////
	//-- inherited functions from Intersectable

	AxisAlignedBox3 GetBox() const { return mBoundingBox; }
	
	int CastRay(Ray &ray) { return 0; }
	
	bool IsConvex() const { return true; }
	bool IsWatertight() const { return true; }
	float IntersectionComplexity() { return 1; }
  
	int NumberOfFaces() const { return 6; };
	
	int GetRandomSurfacePoint(GtpVisibilityPreprocessor::Vector3 &point, 
							  GtpVisibilityPreprocessor::Vector3 &normal)
	{
		// TODO
		return 0;
	}

	int GetRandomVisibleSurfacePoint(GtpVisibilityPreprocessor::Vector3 &point,
									 GtpVisibilityPreprocessor::Vector3 &normal,
									 const GtpVisibilityPreprocessor::Vector3 &viewpoint,
									 const int maxTries)
	{
		// TODO
		return 0;
	}
  
	int Type() const
	{
		return Intersectable::BVH_INTERSECTABLE;
	}

	ostream &Describe(ostream &s) { return s; }

	///////////////////////////////////

	float mRenderCost;

protected:
	
	/// the bounding box of the node
	AxisAlignedBox3 mBoundingBox;
	/// parent of this node
	BvhInterior *mParent;
	int mTimeStamp;
};


/** BSP interior node implementation 
*/
class BvhInterior: public BvhNode 
{
public:
	/** Standard contructor taking a bounding box as argument.
	*/
	BvhInterior(const AxisAlignedBox3 &bbox);
	BvhInterior(const AxisAlignedBox3 &bbox, BvhInterior *parent);

	~BvhInterior();
	/** @return false since it is an interior node 
	*/
	bool IsLeaf() const;
	
	BvhNode *GetBack() { return mBack; }
	BvhNode *GetFront() { return mFront; }

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

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

	friend ostream &operator<<(ostream &s, const BvhInterior &A)
	{
		return s << A.mBoundingBox;
	}

	virtual void CollectObjects(ObjectContainer &objects);

protected:

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


/** BSP leaf node implementation.
*/
class BvhLeaf: public BvhNode 
{
public:
	/** Standard contructor taking a bounding box as argument.
	*/
	BvhLeaf(const AxisAlignedBox3 &bbox);
	BvhLeaf(const AxisAlignedBox3 &bbox, BvhInterior *parent);
	BvhLeaf(const AxisAlignedBox3 &bbox, BvhInterior *parent, const int numObjects);

	~BvhLeaf();

	/** @return true since it is an interior node 
	*/
	bool IsLeaf() const;
	
	SubdivisionCandidate *GetSubdivisionCandidate()// const
	{ 
		return mSubdivisionCandidate; 
	}

	void SetSubdivisionCandidate(SubdivisionCandidate *candidate)
	{ 
		mSubdivisionCandidate = candidate; 
	}
	
	virtual void CollectObjects(ObjectContainer &objects);

	/** Returns level of the hierarchy that is "active" right now.
	*/
	BvhNode *GetActiveNode()
	{
		return mActiveNode;
	}

	/** Returns level of the hierarchy that is "active" right now.
	*/
	void SetActiveNode(BvhNode *node)
	{
		mActiveNode = node;
	}

public:
  // gl list use to store the geometry on the gl server
  int mGlList;
  
  /// objects
  ObjectContainer mObjects;
  
  
protected:
  
  /// pointer to a split plane candidate splitting this leaf
  SubdivisionCandidate *mSubdivisionCandidate;
  
  /// the active node which will be accounted for in the pvs
  BvhNode *mActiveNode;
};


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

protected:
	struct SortableEntry;
	typedef vector<SortableEntry> SortableEntryContainer;

public:
	
	/** Additional data which is passed down the BSP tree during traversal.
	*/
	class BvhTraversalData
	{  
	public:
		
		BvhTraversalData():
		mNode(NULL),
		mDepth(0),
		mMaxCostMisses(0), 
		mAxis(0),
		mNumRays(0),
		mCorrectedPvs(0),
		mPvs(0),
		mCorrectedVolume(0),
		mVolume(0)
		{
			for (int i = 0; i < 4; ++ i)
				mSortedObjects[i] = NULL;
		}
		
		BvhTraversalData(BvhLeaf *node, 
						 const int depth,
						 const float v,
						 const int numRays):
		mNode(node), 
		mDepth(depth),
		mMaxCostMisses(0),
		mAxis(0),
		mNumRays(numRays),
		mCorrectedPvs(0),
		mPvs(0),
		mCorrectedVolume(0),
		mVolume(v)
		{
			for (int i = 0; i < 4; ++ i)
				mSortedObjects[i] = NULL;
		}

		/** Deletes contents and sets them to NULL.
		*/
		void Clear()
		{
			DEL_PTR(mNode);
			for (int i = 0; i < 4; ++ i)
				DEL_PTR(mSortedObjects[i]);
		}

		/// the current node
		BvhLeaf *mNode;
		/// current depth
		int mDepth;
		/// the volume of the node
		float mVolume;
		/// the corrected volume
		float mCorrectedVolume;
		/// how often this branch has missed the max-cost ratio
		int mMaxCostMisses;
		/// current axis
		int mAxis;
		/// number of rays
		int mNumRays;
		/// parent Pvs;
		float mPvs;
		/// parent pvs correction factor
		float mCorrectedPvs;

		/// the sorted objects for the three dimensions
		ObjectContainer *mSortedObjects[4];		
    };


	/** Candidate for a object space split.
	*/
	class BvhSubdivisionCandidate: public SubdivisionCandidate
	{  
	public:

        BvhSubdivisionCandidate(const BvhTraversalData &tData): mParentData(tData)
		{};

		~BvhSubdivisionCandidate() 
		{ 
			mParentData.Clear(); 
		}

		int Type() const { return OBJECT_SPACE; }
	
		void EvalCandidate(bool computeSplitplane = true)
		{
            mDirty = false;
			sBvHierarchy->EvalSubdivisionCandidate(*this, computeSplitplane);
		}

		bool Apply(SplitQueue &splitQueue, bool terminationCriteriaMet)
		{
			BvhNode *n = sBvHierarchy->Subdivide(splitQueue, this, terminationCriteriaMet);

			// local or global termination criteria failed
			return !n->IsLeaf();		
		}

		void CollectDirtyCandidates(SubdivisionCandidateContainer &dirtyList,
									const bool onlyUnmailed)
		{
			sBvHierarchy->CollectDirtyCandidates(this, dirtyList, onlyUnmailed);
		}

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

		BvhSubdivisionCandidate(const ObjectContainer &frontObjects, 
								const ObjectContainer &backObjects, 
								const BvhTraversalData &tData): 
		mFrontObjects(frontObjects), mBackObjects(backObjects), mParentData(tData)
		{}

		float GetPriority() const
		{
			return (float)-mParentData.mDepth;
			//return mPriority;
		}

		/////////////////////////////7

		/// pointer to parent tree.
		static BvHierarchy *sBvHierarchy;

		/// parent data
		BvhTraversalData mParentData;
		/// the objects on the front of the potential split
		ObjectContainer mFrontObjects;
		/// the objects on the back of the potential split
		ObjectContainer mBackObjects;
			
		float mCorrectedFrontPvs;
		float mCorrectedBackPvs;

		float mCorrectedFrontVolume;
		float mCorrectedBackVolume;
	};

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


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

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

	/** Returns tree statistics.
	*/
	const BvhStatistics &GetStatistics() const; 
  
	/** Returns bounding box of the specified node.
	*/
	AxisAlignedBox3 GetBoundingBox(BvhNode *node) const;

	/** Reads parameters from environment singleton.
	*/
	void ReadEnvironment();

	/** Evaluates candidate for splitting.
	*/
	void EvalSubdivisionCandidate(BvhSubdivisionCandidate &splitData, 
								  bool computeSplitPlane = true);

	/** Returns vector of leaves.
	*/
	void CollectLeaves(BvhNode *root, vector<BvhLeaf *> &leaves) const;

	/** Returns vector of leaves.
	*/
	void CollectNodes(BvhNode *root, vector<BvhNode *> &nodes) const;

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

	/** Returns root of the view space partitioning tree.
	*/
	BvhNode *GetRoot() const;

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

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

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

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

	float GetViewSpaceVolume() const;
	/** Writes tree to output stream
	*/
	bool Export(OUT_STREAM &stream);

	/** Collects rays associated with the objects.
	*/
	void CollectRays(const ObjectContainer &objects, VssRayContainer &rays) const;

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

	/** Returns leaf the point pt lies in, starting from root.
	*/
	BvhLeaf *GetLeaf(Intersectable *obj, BvhNode *root = NULL) const;

	/** Sets a pointer to the view cells tree.
	*/
	ViewCellsTree *GetViewCellsTree() const { return mViewCellsTree; }
	
	/** See Get
	*/
	void SetViewCellsTree(ViewCellsTree *vt) { mViewCellsTree = vt; }

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

	/** Sets this node to be an active node.
	*/
	void SetActive(BvhNode *node) const;


	///////////////////////////
	// hacks in order to provide interleaved heurisitcs

	BvhNode *SubdivideAndCopy(SplitQueue &tQueue, SubdivisionCandidate *splitCandidate);

	/////////////////////////////////

	static float EvalAbsCost(const ObjectContainer &objects);

	float EvalProb(const ObjectContainer &objects) const;

	void CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects);

	float GetRenderCostIncrementially(BvhNode *node) const;

	void Compress();
	void CreateUniqueObjectIds();

protected:

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

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

	/** For sorting the objects during the heuristics
	*/
	struct SortableEntry
	{
		Intersectable *mObject;
		float mPos;

		SortableEntry() {}

		SortableEntry(Intersectable *obj, const float pos): 
		mObject(obj), mPos(pos)
		{}

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

	/** Evaluate balanced object partition.
	*/
	float EvalLocalObjectPartition(const BvhTraversalData &tData,
								   const int axis,
								   ObjectContainer &objectsFront,
								   ObjectContainer &objectsBack);

	/** Evaluate surface area heuristic for the node.
	*/
	float EvalSah(const BvhTraversalData &tData,
				  const int axis,
				  ObjectContainer &objectsFront,
				  ObjectContainer &objectsBack);


	/** Evaluates render cost of the bv induced by these objects
	*/
	float EvalRenderCost(const ObjectContainer &objects) const;

	/** Evaluates tree stats in the BSP tree leafs.
	*/
	void EvaluateLeafStats(const BvhTraversalData &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
	*/
	BvhNode *Subdivide(SplitQueue &tQueue, 
				 	   SubdivisionCandidate *splitCandidate,
					   const bool globalCriteriaMet);
	
	/** Subdivides leaf.
		@param sc the subdivisionCandidate holding all necessary data for subdivision		
		
		@param frontData returns the traversal data for the front node
		@param backData returns the traversal data for the back node

		@returns the new interior node = the of the subdivision
	*/
	BvhInterior *SubdivideNode(const BvhSubdivisionCandidate &sc,
							   BvhTraversalData &frontData,
							   BvhTraversalData &backData);

	/** Splits the objects for the next subdivision.
		@returns cost for this split
	*/
	float SelectObjectPartition(const BvhTraversalData &tData,
								ObjectContainer &frontObjects,
								ObjectContainer &backObjects,
								bool useVisibilityBasedHeuristics);
	
	/** Writes the node to disk
		@note: should be implemented as visitor.
	*/
	void ExportNode(BvhNode *node, OUT_STREAM &stream);

	/** Exports objects associated with this leaf.
	*/
	void ExportObjects(BvhLeaf *leaf, OUT_STREAM &stream);

	/** Associates the objects with their bvh leaves.
	*/
	static void AssociateObjectsWithLeaf(BvhLeaf *leaf);


	/////////////////////////////
	// Helper functions for local cost heuristics
	
	/** Prepare split candidates for cost heuristics using axis aligned splits.
		@param node the current node
		@param axis the current split axis
	*/
	void PrepareLocalSubdivisionCandidates(const BvhTraversalData &tData,
										   const int axis);

	static void CreateLocalSubdivisionCandidates(const ObjectContainer &objects, 
												 SortableEntryContainer **subdivisionCandidates,
												 const bool sort,
												 const int axis);

	float EvalPriority(const BvhSubdivisionCandidate &splitCandidate,
					   const float renderCostDecr,
					   const float oldRenderCost) const;

	/** Computes object partition with the best cost according to the heurisics.
		@param tData the traversal data
		@param axis the split axis
		@param objectsFront the objects in the front child bv
		@param objectsBack the objects in the back child bv
		@param backObjectsStart the iterator marking the position where the back objects begin

		@returns relative cost (relative to parent cost)
	*/
	float EvalLocalCostHeuristics(const BvhTraversalData &tData,
								  const int axis,
								  ObjectContainer &objectsFront,
								  ObjectContainer &objectsBack);

	/** Evaluates the contribution to the front and back volume
		when this object is changing sides in the bvs.

		@param object the object
		@param volLeft updates the left pvs
		@param volPvs updates the right pvs
	*/
	void EvalHeuristicsContribution(Intersectable *obj,
									float &volLeft, 
									float &volRight);

	/** Prepares objects for the cost heuristics.
		@returns sum of volume of associated view cells
	*/
	float PrepareHeuristics(const BvhTraversalData &tData, const int axis);
	
	/** Evaluates cost for a leaf given the surface area heuristics.
	*/
	float EvalSahCost(BvhLeaf *leaf) const;

	////////////////////////////////////////////////


	/** Prepares construction for vsp and osp trees.
	*/
	AxisAlignedBox3 EvalBoundingBox(const ObjectContainer &objects, 
									const AxisAlignedBox3 *parentBox = NULL) const;

	/** Collects list of invalid candidates. Candidates
		are invalidated by a view space subdivision step
		that affects this candidate.
	*/
	void CollectDirtyCandidates(BvhSubdivisionCandidate *sc,
								vector<SubdivisionCandidate *> &dirtyList,
								const bool onlyUnmailed);

	/** Collect view cells which see this bvh leaf.
	*/
	int CollectViewCells(const ObjectContainer &objects, 
						 ViewCellContainer &viewCells,
						 const bool setCounter,
						 const bool onlyUnmailedRays) const;

	/** Collects view cells which see an object.
		@param useMailBoxing if mailing should be used and
		only unmailed object should pass
		@param setCounter counter for the sweep algorithm
		@param onlyUnmailedRays if only unmailed rays should be considered
	*/
	int CollectViewCells(Intersectable *object, 
						 ViewCellContainer &viewCells, 
						 const bool useMailBoxing,
						 const bool setCounter,
						 const bool onlyUnmailedRays) const;

	/** Counts the view cells of this object. note: only
		counts unmailed objects.
	*/
	int CountViewCells(Intersectable *obj) const;

	/** Counts the view cells seen by this bvh leaf
	*/
	int CountViewCells(const ObjectContainer &objects) const;

	/** Evaluates increase in pvs size.
	*/
	int EvalPvsEntriesIncr(BvhSubdivisionCandidate &splitCandidate, const float avgRayContri) const;

	/** Rays will be clipped to the bounding box.
	*/
	void PreprocessRays(BvhLeaf *root, 
						const VssRayContainer &sampleRays,
						RayInfoContainer &rays);

	/** Print the subdivision stats in the subdivison log.
	*/
	void PrintSubdivisionStats(const SubdivisionCandidate &tData);

	/** Prints out the stats for this subdivision.
	*/
	void AddSubdivisionStats(const int viewCells,
							 const float renderCostDecr,
							 const float totalRenderCost);

	/** Stores rays with objects that see the rays.
	*/
	int AssociateObjectsWithRays(const VssRayContainer &rays) const;

	/** Tests if object is in this leaf.
		@note: assumes that objects are sorted by their id.
	*/
	bool IsObjectInLeaf(BvhLeaf *, Intersectable *object) const;

	/** Prepares the construction of the bv hierarchy and returns
		the first subdivision candidate.
	*/
	void PrepareConstruction(SplitQueue &tQueue,
							 const VssRayContainer &sampleRays,
							 const ObjectContainer &objects);

	/** Resets bv hierarchy. E.g. deletes root and resets stats.
	*/
	void Reset(SplitQueue &tQueue,
			   const VssRayContainer &rays, 
			   const ObjectContainer &objects);

	/** Evaluates volume of view cells that see the objects.
	*/
	float EvalViewCellsVolume(const ObjectContainer &objects) const;

	/** Assigns or newly creates initial list of sorted objects.
	*/
	void AssignInitialSortedObjectList(BvhTraversalData &tData,
									   const ObjectContainer &objects);

	/** Assigns sorted objects to front and back data.
	*/
	void AssignSortedObjects(const BvhSubdivisionCandidate &sc,
							 BvhTraversalData &frontData,
							 BvhTraversalData &backData);
	
	/** Creates new root of hierarchy and computes bounding box.
		Has to be called before the preparation of the subdivision.
	*/
	void Initialise(const ObjectContainer &objects);


	////////////////////
	// initial subdivision

	/** Makes an initial parititon of the object space based on
		some criteria (size, shader)
	*/
	void ApplyInitialSubdivision(SubdivisionCandidate *firstCandidate,
								 vector<SubdivisionCandidate *> &candidateContainer);

	void ApplyInitialSplit(const BvhTraversalData &tData,
						   ObjectContainer &frontObjects,
						   ObjectContainer &backObjects);

	bool InitialTerminationCriteriaMet(const BvhTraversalData &tData) const;

	/** Sets the bvh node ids.
	*/
	void SetUniqueNodeIds();

protected:
	
	/// pre-sorted subdivision candidtes for all three directions.
	vector<SortableEntry> *mGlobalSubdivisionCandidates[3];
	/// pointer to the hierarchy of view cells
	ViewCellsTree *mViewCellsTree;
	/// The view cells manager
	ViewCellsManager *mViewCellsManager;
	/// candidates for placing split planes during cost heuristics
	vector<SortableEntry> *mSubdivisionCandidates;
	/// Pointer to the root of the tree
	BvhNode *mRoot;
	/// Statistics for the object space partition
	BvhStatistics mBvhStats;	
	/// box around the whole view domain
	AxisAlignedBox3 mBoundingBox;
	/// the hierarchy manager
	HierarchyManager *mHierarchyManager;


	////////////////////
	//-- local termination criteria

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


	////////////////////
	//-- global termination criteria

	/// the minimal accepted global cost ratio
	float mTermMinGlobalCostRatio;
	//// number of accepted misses of the global cost ratio
	int mTermGlobalCostMissTolerance;
	/// maximal number of view cells
	int mTermMaxLeaves;
	/// maximal tree memory
	float mMaxMemory;
	/// the tree is out of memory
	bool mOutOfMemory;


	////////////////////////////////////////
	//-- split heuristics based parameters
	
	/// if a heuristics should be used for finding a split plane
    bool mUseCostHeuristics;
	/// if sah heuristcs should be used for finding a split plane
	bool mUseSah;
    /// 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;
	// subdivision stats output file
	ofstream  mSubdivisionStats;
	/// keeps track of cost during subdivision
	float mTotalCost;
	int mPvsEntries;
	/// 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;

	/// if the objects should be sorted in one global step
	bool mUseGlobalSorting;

	bool mUseBboxAreaForSah;

	//SortableEntryContainer *mSortedObjects[4];

	int mMinRaysForVisibility;

	/// constant value for driving the heuristics
	float mMemoryConst;

	int mMaxTests;

	bool mIsInitialSubdivision;

	bool mApplyInitialPartition;
	
	int mInitialMinObjects;
	float mInitialMaxAreaRatio;
	float mInitialMinArea;
};

}

#endif