// This file has been written by Jiri Bittner, October 2006

#ifndef __BVH_H
#define __BVH_H

#include "Geometry.h"
//#include "FlexibleHeap.h"


namespace CHCDemo
{

////////
// Forward declarations

class SceneGeometry;
class Camera;


/** A node in the bv hierarchy.
*/
class BvhNode
{
	friend class Bvh;

public:

	/** visibility related options
	*/
	struct VisibilityInfo
	{
		VisibilityInfo() { Reset(); }		
		/** Reset the visibility info.
		*/
		void Reset();

		/// if the node is visible
		bool mIsVisible;
		/// #frames this node is assumed to stay visible
		int mAssumedVisibleFrames;
		/// the frame when this node was last touched during traversal
		int mLastVisitedFrame;
		/// #times this node was invisible (only valid if the node actually is invisible)
		int mTimesInvisible;
		/// if the node is view frustum culled
		bool mIsFrustumCulled;
		/// if the node is newly processed with no prior history available
		bool mIsNew;
	};

	/** Constructor taking the parent node.
	*/
	BvhNode(BvhNode *parent);
	
	/** Returns true if this node is a leaf.
	*/
	//virtual bool IsPseudoLeaf() = 0;
	/** Virtual destructor doing nothing.
	*/
	virtual ~BvhNode();
	/** Returns unique id for this node.
	*/
	//inline int GetId() {return mId;}
	/** Depth of this node in the tree.
	*/
	inline int GetDepth() const {return mDepth;}
	/** Returns parent of this bvh node, NULL if it is root.
	*/
	inline BvhNode *GetParent() {return mParent;}
	/** Number of leaves in the subtree induced by this node.
	*/
	inline int GetNumLeaves() const {return mNumLeaves;}
	/** Reset the status of this node.
	*/
	virtual void ResetVisibility();

	virtual int GetType() = 0; //{ return BVH_NODE; }


	/////////////////////
	//-- visibility culling related functions

	inline int GetLastVisitedFrame() const;

	inline void SetLastVisitedFrame(const int lastVisited);
	/** If this node is considered visible.
	*/
	inline bool IsVisible() const;
	/** Set visibility flag of the node.
	*/
	inline void SetVisible(const bool visible);
	/** The assumed visible time span of this node.
	*/
	inline void SetAssumedVisibleFrames(const int t);
	/** See set.
	*/
	inline int GetAssumedVisibleFrames() const;
	/** The time span this node remains visible.
	*/
	inline void SetRemainingVisibleFrames(const int t);
	/** Decrease the time this node is considered visible.
	*/
	inline void DecAssumedVisibleFrames();
	/** Increases the #times this node was
		successfully tested invisible.
	*/
	inline void IncTimesInvisible();
	
	inline int GetTimesInvisible() const;
	inline void SetTimesInvisible(const int t);
	
	inline int GetTurnedVisibleFrame() const;
	inline void SetTurnedVisibleFrame(const int turnedVisibleFrame);

	inline int GetLastTestedFrame();
	inline void SetLastTestedFrame(const int lastTested);
	
	inline bool IsViewFrustumCulled() const;
	inline void SetViewFrustumCulled(const bool frustumCulled);

	inline bool IsNew() const;
	inline void SetIsNew(const bool isNew);


	//////////
	//-- rendering
	
	/** Returns the frame in which this node was last rendered.
	*/
	inline int GetLastRenderedFrame() const;
	/** See get.
	*/
	inline void SetLastRenderedFrame(int lastRenderedFrame);
	/** Does this node contain renderable geometry?
	*/
	inline bool Empty() const;
	/** Counts #geometry stored in the subtree.
	*/
	inline int CountPrimitives() const;


protected:

	/////////////
	
	/// some flags
	int mFlags;
	/// the depth of this node
	unsigned char mDepth;
	/// the split axis
	char mAxis;
	/// the parent node
	BvhNode *mParent;
	/// stores the visibility related parameters
	VisibilityInfo mVisibility;

	/////////
	// used for view frustum culling

	int mPlaneMask;
	int mPreferredPlane;


	////////////
	//-- rendering related options
	
	/// when the node was last rendered
	int mLastRenderedFrame;
	/// #leaves under this node
	int mNumLeaves;
	
	// Indices to first and last triangle in the triangle array
	// assumes the triangle are placed in continuous chunk of memory
	// however this need not be a global array!
	
	/// the index of the first triangle
	int mFirst;
	/// the index of the last triangle
	int mLast;

	/// these nodes can be tested instead of the current node
	int mTestNodesIdx;
	int mNumTestNodes;
	int mIndicesPtr;
	/// Area of this node
	float mArea;
};


/////////////////
//-- public inline functions

int BvhNode::GetLastVisitedFrame() const 
{ 
	return mVisibility.mLastVisitedFrame; 
}


void BvhNode::SetLastVisitedFrame(const int lastVisited) 
{ 
	mVisibility.mLastVisitedFrame = lastVisited; 
}


bool BvhNode::IsVisible() const 
{ 
	return mVisibility.mIsVisible; 
}


void BvhNode::SetVisible(const bool visible) 
{ 
	mVisibility.mIsVisible = visible; 
}


void BvhNode::IncTimesInvisible() 
{ 
	++ mVisibility.mTimesInvisible; 
}


int BvhNode::GetTimesInvisible() const 
{ 
	return mVisibility.mTimesInvisible; 
}


void BvhNode::SetTimesInvisible(const int t) 
{ 
	mVisibility.mTimesInvisible = t; 
}


bool BvhNode::IsViewFrustumCulled() const 
{ 
	return mVisibility.mIsFrustumCulled; 
}


void BvhNode::SetViewFrustumCulled(const bool frustumCulled) 
{ 
	mVisibility.mIsFrustumCulled = frustumCulled; 
}


bool BvhNode::IsNew() const 
{ 
	return mVisibility.mIsNew;
}


void BvhNode::SetIsNew(const bool isNew) 
{ 
	mVisibility.mIsNew = isNew; 
}


int BvhNode::GetLastRenderedFrame() const 
{ 
	return mLastRenderedFrame; 
}
	

void BvhNode::SetLastRenderedFrame(int lastRenderedFrame)
{
	mLastRenderedFrame = lastRenderedFrame;
}
	
	
bool BvhNode::Empty() const 
{ 
	return mFirst == -1; 
}


int BvhNode::CountPrimitives() const 
{
	return mLast - mFirst + 1; 
}


void BvhNode::SetAssumedVisibleFrames(const int t) 
{ 
	mVisibility.mAssumedVisibleFrames = t; 
}


int BvhNode::GetAssumedVisibleFrames() const 
{ 
	return mVisibility.mAssumedVisibleFrames;
}

void BvhNode::DecAssumedVisibleFrames() 
{
	-- mVisibility.mAssumedVisibleFrames; 
}


/** Internal node of the bv hierarchy.
*/
class BvhInterior: public BvhNode
{
friend class Bvh;

public:
	BvhInterior(BvhNode *parent): mBack(NULL), mFront(NULL), BvhNode(parent)
	{}
	virtual bool IsLeaf() {return false;}
	/** Back child.
	*/
	inline BvhNode *GetBack() { return mBack;}
	/** Front child.
	*/
	inline BvhNode *GetFront() { return mFront;}
	/** recursivly delete tree.
	*/
	virtual ~BvhInterior() { if (mBack) delete mBack; if (mFront) delete mFront;}
	/** Returns split axis of this interior node.
	*/
	inline int GetAxis() {return (int)mAxis;}
	/** Returns position of the split axis.
	*/
	inline float GetPosition() {return (float)mPosition;}


protected:

	/// the position of the split plane
	float mPosition;
	
	BvhNode *mBack;
	BvhNode *mFront;
};


class BvhLeaf: public BvhNode
{
friend class Bvh;

public:

	BvhLeaf(BvhNode *parent): BvhNode(parent)
	{}

	~BvhLeaf();

	virtual bool IsLeaf() { return true; }
};


/** Class representing a bounding volume hierarchy.
*/
class Bvh
{
	/** Bvh properties
	*/
	struct BvhStats
	{
		BvhStats(): 
		mInteriorSA(0),
		mLeafSA(0),
		mInteriorVol(0),
		mLeafVol(0),
		mBoundsInteriorSA(0),
		mBoundsLeafSA(0),
		mBoundsInteriorVol(0),
		mBoundsLeafVol(0),
		mBoundsLeavesCount(0),
		mTriangles(0),
		mTriangleRatio(0),
		mGeometryRatio(0),
		mMaxGeometry(0),
		mMaxTriangles(0)
		{}
		
		float mInteriorSA;
		float mLeafSA;
		float mInteriorVol;
		float mLeafVol; 
		float mBoundsInteriorSA;
		float mBoundsLeafSA;
		float mBoundsInteriorVol;
		float mBoundsLeafVol;
		int mBoundsLeavesCount;
		int mTriangles;

		float mTriangleRatio;
		float mGeometryRatio;

		int mMaxGeometry;
		int mMaxTriangles;
	};

public:

	/** Returns number of bvh nodes.
	*/
	inline int GetNumNodes() const {return mNumNodes;}
	/** Returns number of bvh leaves.
	*/
	inline int GetNumLeaves() const {return mNumNodes / 2 + 1;}
	/** Constructs the bounding volume hierarchy.
	*/
	void Construct();
	/** Returns root node of the bvh.
	*/
	BvhNode *GetRoot() {return mRoot;}
	/** Counts the triangle in this leaf.
	*/
	int CountTriangles(BvhLeaf *leaf) const;


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

	/** Returns geometry by reference (faster).
	*/
	SceneGeometry **GetGeometry(BvhNode *node, int &size);


	/////////////
	//-- Rendering related options

	/** Renders the bounding box of this node (Or the tigher bounding boxes of some subnodes).
	*/
	void RenderBoundingBox(BvhNode *node);
	/** Renders bounding boxes of the collection of nodes.
		@returns #rendered boxes
	*/
	int RenderBoundingBoxes(const BvhNodeContainer &nodes);



	//////////////
	//-- Traversal related options

	/** Pulls up visible classification.
	*/
	void MakeParentsVisible(BvhNode *node);
	/** Does the view frustum culling for this node with respect to the previous culls
		@returns: 0 if completely outside, 1 if completely inside, -1 if intersecting (partly inside),
	*/
	int	IsWithinViewFrustum(BvhNode *node);
	/** sets frame dependent values.
	*/
	void InitFrame(Camera *camera, const int currentFrameId);
	/** this gives the orthogonal distance from the viewpoint to the nearest bounding box vertex
		note that negative values can appear because culling is done only afterwards
	*/
	float CalcDistance(BvhNode *node) const;
	/** Sets maximal depth for taking the bounding boxes to test the
		visibility of a node. The deeper the more the box fits to the geometry.
	*/
	void SetMaxDepthForTestingChildren(const int maxDepth);
	/** Pulls up the fully visible classification in the bvh.
	*/
	void UpdateFullVisibility(BvhNode *node) const;
	/** Pulls up the last visited classification in the bvh.
	*/
	void PullUpLastVisited(BvhNode *node, const int frameId) const;
	/** Resets the node classifications in the tree.
	*/
	void ResetNodeClassifications();
	/** Helper function that renders the bounding boxes of the leaves as
		wireframes for visualization purpose.
	*/
	void RenderBoundingBoxesForViz(const int mode);
	/** Returns squared min distance to the view point.
	*/
	float GetSquareDistance(BvhNode *node) const;
	/** Count triangles the node contains.
	*/
	int CountTriangles(BvhNode *node) const;
	/** Returns area of the geometry contained in the node.
	*/
	float GetGeometryArea(BvhNode *node) const;


	////////////
	//-- functions that change the boundaries of the nodes

	void SetUseTighterBoundsForTests(bool tighterBoundsForTests);

	void SetAreaRatioThresholdForTestingChildren(const float ratio);


	const BvhStats &GetBvhStats() const {return mBvhStats;}

	void SetCollectTighterBoundsWithMaxLevel(bool t);


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

	static unsigned int sCurrentVboId;
	

protected:

	/** Small struct representing a frustum.
	*/
	struct Frustum
	{
		/// the 6 clip planes
		float mClipPlane[6][4];
	};
	


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

	/** Constructor loading the bvh from disc
	*/
	Bvh(const std::string &filename);
	/** protected constructor: do nothing.
	*/
	//Bvh(): mCamera(NULL), mFrameId(-1), mVertices(NULL), mRenderer(NULL) {}
	/** Destructor.
	*/
	~Bvh();


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

	void ComputeBvhStats();
	void PrintBvhStats() const;


	//////////
	//-- Helper methods for bounding box rendering in immediate and vbo mode.
	
	void PrepareVertices();

	int PrepareBoundingBoxesWithDrawArrays(const BvhNodeContainer &nodes);
	void RenderBoundingBoxesWithDrawArrays(int numNodes);

	int RenderBoundingBoxesImmediate(const BvhNodeContainer &nodes);
	/** Renders a bounding box in immediate mode using index restart
		and restarts the strip only if wished.
	*/
	void RenderBoundingBoxImmediate(const AxisAlignedBox3 &box, bool restartStrip);
	/** Create the indices that each node needs to use vbo rendering.
	*/
	void CreateIndices();
	/** Create the list of nodes whose bounding boxes are tested instead of the
		bounding box of the node itself.
	*/
	bool CreateNodeRenderList(BvhNode *node);
	/** Recursivly updates indices so we can 
		render also interior nodes without traversing hierarchy
	*/
	void UpdateInteriors(BvhNode *node);
	/** Recomputes the boundaries of the nodes. This function is always called if
		some boundary options are changed.
	*/
	void RecomputeBounds();
	/** Does some postprocessing on the leaves.
		@returns #leaves that were chosen for tighter bounds.
	*/
	int PostProcessLeaves(BvhLeafContainer &leaves);


	int	IsWithinViewFrustumLocal(BvhNode *node);

	int	IsWithinViewFrustum(const AxisAlignedBox3 &box, int planeMask, int preferredPlane);
	
	float GetMinSquareDistance(const AxisAlignedBox3 &box) const;
	
	
	////////////////////////

	/// the root of the hierarchy
	BvhNode *mRoot;
	/// pointers to the geometry associated with this node
	SceneGeometry **mGeometry;
	/// #of entities
	size_t mGeometrySize;


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


	/// these values are valid for all nodes
	char mClipPlaneAABBVertexIndices[6][2];
	/// the current view frustum
	Frustum mFrustum;
	/// the current camera
	Camera *mCamera;
	// current frame id
	int mFrameId;
	/// a vertex array used if working with indexed arrays (without vbo)
	//Point3f *mVertices;
	/// indices used for draw array rendering
	unsigned int *mIndices;

	/** maximal depth from which children are fetched for 
		testing instead of the current node
	*/
	int mMaxDepthForTestingChildren;

	float mAreaRatioThreshold;
	float mVolRatioThreshold;

	BvhStats mBvhStats;

	//HierarchyNodeContainer mTestNodes;
	
	unsigned int *mTestIndices;
	/// a pointer to the end of the indices array
	int mCurrentIndicesPtr;

	float mScale;

	Vector3 mNearPlane;
	float mNearPlaneD;
	int mNumNodes;
};

}

#endif // __BVH_H