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

#ifndef __BVH_H
#define __BVH_H

#include "common.h"
#include "Vector3.h"
#include "AxisAlignedBox3.h"



namespace CHCDemoEngine
{

// the number of visibility states
#define NUM_STATES 2

////////
//-- Forward declarations

class SceneEntity;
class Camera;
class RenderState;


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

public:

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

		/// if the node is visible
		bool mIsVisible;
		/// frame id until this node is assumed to stay visible
		int mAssumedVisibleFrameId;
		/// 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;
		/// the frame this node was last queried
		int mLastQueriedFrame;
	};

	/** Constructor taking the parent node.
	*/
	BvhNode(BvhNode *parent);
	/** Virtual destructor doing nothing.
	*/
	virtual ~BvhNode();
	/** Reset the status of this node.
	*/
	virtual void ResetVisibility();
	/** Returns true if this node is a leaf.
	*/
	virtual bool IsLeaf() const = 0;
	/** Depth of this node in the tree.
	*/
	inline int GetDepth() const;
	/** Returns parent of this bvh node, NULL if it is root.
	*/
	inline BvhNode *GetParent();
	/** Number of leaves in the subtree induced by this node.
	*/
	inline int GetNumLeaves() const;
	/** Returns true if this node is a "virtual" leaf,
		i.e., the node is handled as a leaf during traversal.
	*/
	inline bool IsVirtualLeaf() const;
	/** Returns the stored distance to the near plane.
	*/
	inline float GetDistance() const;


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

	inline int GetLastVisitedFrame() const;

	inline void SetLastVisitedFrame(int lastVisited);
	/** If this node is considered visible.
	*/
	inline bool IsVisible() const;
	/** Set visibility flag of the node.
	*/
	inline void SetVisible(bool visible);
	/** The frame id until this node is assumed visible
	*/
	inline void SetAssumedVisibleFrameId(int t);
	/** See set.
	*/
	inline int GetAssumedVisibleFrameId() const;
	/** Increases the #times this node was
		successfully tested invisible.
	*/
	inline void IncTimesTestedInvisible();
	
	inline int GetTimesTestedInvisible() const;
	inline void SetTimesTestedInvisible(int t);
	
	inline int GetTurnedVisibleFrame() const;
	inline void SetTurnedVisibleFrame(int turnedVisibleFrame);

	inline int GetLastQueriedFrame() const;
	inline void SetLastQueriedFrame(int lastTested);
	
	inline bool IsViewFrustumCulled() const;
	inline void SetViewFrustumCulled(bool frustumCulled);

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


	/** Returns the bounding box of this node.
	*/
	inline const AxisAlignedBox3 &GetBox() const;
	/** Return index of this node.
	*/
	inline int GetId() const;
	/** See get
	*/
	inline void SetId(int id);
	

	//////////
	//-- 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;
	/** This function is important in case you have more than one
		view position within a frame (e.g., camera view and shadow view for
		shadow mapping), because each camera needs its own state in
		order to not break temporal coherency.
	*/
	inline static void SetCurrentState(int _state);


protected:

	/// the depth of this node
	unsigned char mDepth;
	/// the split axis
	char mAxis;
	/// the parent node
	BvhNode *mParent;


	//////////////
	//-- members definig the current visibility state (one state per camera)

	/// the currently used state
	static int sCurrentState;

	/// stores the visibility related info 
	VisibilityInfo mVisibility[NUM_STATES];
	/// when the node was last rendered
	int mLastRenderedFrame[NUM_STATES];


	///////////////
	//-- members that help to speed up view frustum culling

	/// masks out planes of the frustum that do not have to be tested against
	int mPlaneMask[NUM_STATES];
	/// the plane that is usually responsible for culling this node. 
	/** if our educated guess was right, we save up to 5 comparisons.
	*/
	int mPreferredPlane[NUM_STATES];


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


	/// #leaves under this node
	int mNumLeaves;
	/// Area of this node
	float mArea;
	/// distance to the camera
	float mDistance;
	/// the index of this node
	unsigned int mId;
	/// the bounding box
	AxisAlignedBox3 mBox;
	/// if this node is a virtual leaf
	bool mIsVirtualLeaf;
	/** This marks the maximal depth where a virtual leaf can be defined.
	    From this point on it makes no sense to traverse down further, as all
		nodes below contain the same geometry, so no further refinement of visibility 
		can be archieved. All nodes below this point can merely used to define the 
		tighter bounds.
	*/
	bool mIsMaxDepthForVirtualLeaf;


	////////////
	//-- rendering related options
	
	// 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;


	////////////////
	//-- rendering related options

	/// we  query the bounding boxes of the test nodes when testing this node
	int mTestNodesIdx;
	/// the number of these test nodes
	int mNumTestNodes;
	/// used for efficient element array rendering
	int mIndicesPtr;
};



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

public:

	BvhInterior(BvhNode *parent);
	
	virtual bool IsLeaf() const;
	/** Back child.
	*/
	inline BvhNode *GetBack();
	/** Front child.
	*/
	inline BvhNode *GetFront();
	/** Recursivly delete hierarchy.
	*/
	virtual ~BvhInterior();


protected:

	BvhNode *mBack;
	BvhNode *mFront;
};



class BvhLeaf: public BvhNode
{
	friend class Bvh;
	friend class BvhFactory;

public:

	BvhLeaf(BvhNode *parent);

	~BvhLeaf();

	virtual bool IsLeaf() const;
};


/**	This class implements the compare operator for the priority queue.
	a lower distance has a higher value in the queue
*/
class GtDistance
{
public:
	bool operator() (BvhNode *v1, BvhNode *v2) const
    {
		return (v1->GetDistance() > v2->GetDistance());
    }
};


typedef std::priority_queue<BvhNode *, std::vector<BvhNode *>, GtDistance> TraversalQueue;


/** Class representing a bounding volume hierarchy.
*/
class Bvh
{
	friend class BvhFactory;
	friend class BvhConstructor;
	friend class BvhExporter;

	/** Bvh properties
	*/
	struct BvhStats
	{
		BvhStats() { Reset(); }

		void Reset() 
		{
			mInteriorSA = .0f;
			mLeafSA = .0f;
			mInteriorVol = .0f;
			mLeafVol = .0f;
			mTriangleRatio = .0f;
			mGeometryRatio = .0f;

			mTriangles = 0;
			mLeaves = 0;
		}

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

		float mInteriorSA;
		float mLeafSA;
		float mInteriorVol;
		float mLeafVol; 
		
		float mTriangleRatio;
		float mGeometryRatio;

		int mTriangles;
		int mLeaves;
	};

public:

	/** Destructor.
	*/
	~Bvh();
	/** Returns number of bvh nodes.
	*/
	inline int GetNumNodes() const;
	/** Counts the number of bvh nodes under this node
	*/
	int CountNumNodes(BvhNode *node) const;
	/** Returns number of bvh leaves.
	*/
	inline int GetNumLeaves() const;
	/** Returns number of 'virtual' nodes in the hierarchy, i.e.
		the number of nodes actually used for traversal.
	*/
	inline int GetNumVirtualNodes() const;
	/** Returns number of bvh leaves.
	*/
	inline int GetNumVirtualLeaves() const;
	/** Returns root node of the bvh.
	*/
	inline BvhNode *GetRoot();
	/** Returns the static root node of the bvh.
	*/
	inline BvhNode *GetStaticRoot();
	/** Returns the dynamic root node of the bvh.
	*/
	inline BvhNode *GetDynamicRoot();
	/** Returns the bounding box of this bvh.
	*/
	inline const AxisAlignedBox3 &GetBox() const;
	/** Returns true if the current bvh node intersects the near plane.
	*/
	bool IntersectsNearPlane(BvhNode *node) const; 


	///////////////
	//-- functions collecting nodes based on some criteria

	/** Collect all child nodes in a given depth from the specified node.
	*/
	void CollectNodes(BvhNode *node, BvhNodeContainer &nodes, int depth);
	/** Collect all child nodes.
	*/
	void CollectNodes(BvhNode *node, BvhNodeContainer &nodes);
	/** Collect the "physical" leaves of the hierarchy
	*/
	void CollectLeaves(BvhNode *node, BvhLeafContainer &leaves);
	/** Collect only the virtual leaves (can be anywhere in the hierarchy).
	*/
	void CollectVirtualLeaves(BvhNode *node, BvhNodeContainer &leaves);


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

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


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

	/** Renders the bounds of this node 
	    (the box of the node or the tigher bounds of some subnodes).
	*/
	void RenderBounds(BvhNode *node, RenderState *state, bool useTightBounds);
	/** Renders bounding boxes of the collection of nodes.
		@returns #rendered boxes
	*/
	int RenderBounds(const BvhNodeContainer &nodes, RenderState *state, bool useTightBounds);
	


	//////////////
	//-- 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, RenderState *state);
	/** Stores the orthogonal distance from the viewpoint to a point on the node.
		We choose the the nearest bounding box vertex . 
		Note that negative values can appear because culling is done only afterwards
	*/
	void UpdateDistance(BvhNode *node) const;
	/** Returns the maximum distance from the near plane to this node.
	*/
	float CalcMaxDistance(BvhNode *node) const;
	/** Pulls up the last visited classification in the bvh.
	*/
	void PullUpLastVisited(BvhNode *node, int frameId) const;
	/** Resets the node classifications in the tree.
	*/
	void ResetNodeClassifications();
	/** Counts the number of triangles contained in this node.
	*/
	int CountTriangles(BvhNode *node) const;
	/** Returns area of the the node.
	*/
	float GetArea(BvhNode *node) const;
	/** Compute unique ids for the nodes.
	*/
	void ComputeIds();
	/** Assign virtual leaves based on specified number of triangles per leaf.
		That means that we try to set the leaves at a point where we
		have less than numTriangles triangles within this leaf and beyond.

		Virtual leaves are nodes that are determined to be the leaves
		of the hierarchy during render traversal. These nodes are not necessarily 
		the same as the real leaves of the hierarchy and can be anywhere
		in the hierarchy. 
		Please refer to the article for more info about virtual leaves
	*/
	void SetVirtualLeaves(int numTriangles);
	

	////////////
	//-- these functions determine the 'tightness' of the bounds that are used for querying


	/** Sets maximal depth for taking the bounding boxes to test the
		visibility of a node. 
		Deeper level means that the bounds adapt more to the geometry but
		also that more boxes are rendered
	*/
	void SetMaxDepthForTestingChildren(int maxDepth);
	/** The ratio of area between node and subnodes where 
		testing the subnodes as proxy is still considered feasable
	*/
	void SetAreaRatioThresholdForTestingChildren(float ratio);


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

	/** Returns statistics.
	*/
	const BvhStats &GetBvhStats() const { return mBvhStats; }
	/** Render wireframe bvh for visualization purpose.
	*/
	void RenderBoundsForViz(BvhNode *node, RenderState *state, bool useTightBounds);


protected:

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

	/** protected constructor: do nothing.
	*/
	Bvh();
	/** Protected constructor taking scene geometry into account
		Sets the static and dynamic objects for the hierarchy.
	*/
	Bvh(const SceneEntityContainer &staticEntities, 
	    const SceneEntityContainer &dynamicEntities);
	/** Protected constructor taking scene geometry into account
		Sets the static and dynamic objects for the hierarchy.
	*/
	Bvh(const SceneEntityContainer &staticEntities, 
	    const SceneEntityContainer &dynamicEntities,
	    int maxDepthForTestingChildren);
	/** Called by the constructor. Initializes important members.
	*/
	void Init();

	/////////////
	/** Traverse hierarchy and compute stats.
	*/
	void ComputeBvhStats(BvhNode *root, BvhStats &bvhStats);
	/** Output the bvh statistics.
	*/
	void PrintBvhStats(const BvhStats &bvhStats, BvhNode *root) const;


	//////////
	//-- Helper methods for bounding box rendering in immediate and vbo mode.
	
	void PrepareVertices();
	/** Prepare nodes for vbo rendering.
	*/
	int PrepareBoundsWithDrawArrays(const BvhNodeContainer &nodes);
	/** Render the nodes from the vbo prepared previously.
	*/
	void RenderBoundsWithDrawArrays(int numNodes, RenderState *state);

	/** 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 nodes.
	*/
	void PostProcess();
	/** Helper method that updates the number of leaves in the subtree under
		this node.
	*/
	void UpdateNumLeaves(BvhNode *node) const;
	/** Frustum tests the ith plane.
	*/
	inline bool TestPlane(BvhNode *node, int i, bool &bIntersect);
	/** Renders a bounding box in immediate mode.
	*/
	void RenderBoundingBoxImmediate(const AxisAlignedBox3 &box);


	/////////////////////////////
	//-- functions used to construct the dynamic part of the hierarchy

	int SortTriangles(BvhLeaf *leaf, 
		              int axis, 
					  float position);

	int SortTrianglesSpatialMedian(BvhLeaf *leaf, 
		                           int axis);

	BvhNode *SubdivideLeaf(BvhLeaf *leaf, 
		                   int parentAxis);
	/** Recompute the dynamic branch of the hierarchy.
	*/
	void CreateDynamicBranch();

	void UpdateBoundingBoxes(BvhNode *node);

	inline bool TerminationCriteriaMet(BvhLeaf *leaf) const;

	void ComputeMaxDepthForVirtualLeaves();

	void CreateRoot();

	void UpdateDynamicBounds(RenderState *state);


	////////////////////////
	
	/// the bounding box of the bvh
	AxisAlignedBox3 mBox;
	/// the root of the hierarchy
	BvhInterior *mRoot;
	/// the root of static part of the the hierarchy
	BvhNode *mStaticRoot;
	/// the root of dynamic part of the the hierarchy
	BvhNode *mDynamicRoot;
	/// pointers to the geometry associated with this node
	SceneEntity **mGeometry;
	/// #of entities
	size_t mGeometrySize;
	/// #of static entities
	size_t mStaticGeometrySize;
	/// #of dynamic entities
	size_t mDynamicGeometrySize;


	////////////////
	//-- tigher bounds termination criteria

	/** maximal depth from which children are fetched for 
		testing instead of the current node
	*/
	int mMaxDepthForTestingChildren;
	/// threshold for computing tighter bounds
	float mAreaRatioThreshold;
	
	
	////////////////
	//-- statistics

	BvhStats mBvhStats;
	/// the overall number of nodes
	int mNumNodes;
	/// the number of "virtual" (=actually used) nodes
	int mNumVirtualNodes;


	////////////
	//-- rendering stuff

	/// these proxy nodes are tested instead of the current node
	BvhNodeContainer mTestNodes;
	/// the indices used for vbo index buffering
	unsigned int *mTestIndices;
	/// a pointer to the end of the indices array
	int mCurrentIndicesPtr;
	/// the vbo id
	unsigned int mVboId;
	/// a vertex array used if working with indexed arrays (without vbo)
	Vector3 *mVertices;
	/// indices used for draw array rendering
	unsigned int *mIndices;


	///////////
	//-- termination criteria for dynamic branch

	int mMaxDepthForDynamicBranch;

	//SceneEntityContainer mDynamicEntities;
};



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


inline int BvhNode::GetLastVisitedFrame() const 
{ 
	return mVisibility[sCurrentState].mLastVisitedFrame; 
}


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


inline bool BvhNode::IsVisible() const 
{ 
	return mVisibility[sCurrentState].mIsVisible; 
}


inline void BvhNode::SetVisible(bool visible) 
{ 
	mVisibility[sCurrentState].mIsVisible = visible; 
}


inline void BvhNode::IncTimesTestedInvisible() 
{ 
	++ mVisibility[sCurrentState].mTimesInvisible; 
}


inline int BvhNode::GetTimesTestedInvisible() const 
{ 
	return mVisibility[sCurrentState].mTimesInvisible; 
}


inline void BvhNode::SetTimesTestedInvisible(int t) 
{ 
	mVisibility[sCurrentState].mTimesInvisible = t; 
}


inline bool BvhNode::IsViewFrustumCulled() const 
{ 
	return mVisibility[sCurrentState].mIsFrustumCulled; 
}


inline void BvhNode::SetViewFrustumCulled(bool frustumCulled) 
{ 
	mVisibility[sCurrentState].mIsFrustumCulled = frustumCulled; 
}


inline bool BvhNode::IsNew() const 
{ 
	return mVisibility[sCurrentState].mIsNew;
}


inline void BvhNode::SetIsNew(bool isNew) 
{ 
	mVisibility[sCurrentState].mIsNew = isNew; 
}


inline void BvhNode::SetAssumedVisibleFrameId(int t) 
{ 
	mVisibility[sCurrentState].mAssumedVisibleFrameId = t; 
}


inline int BvhNode::GetAssumedVisibleFrameId() const 
{ 
	return mVisibility[sCurrentState].mAssumedVisibleFrameId;
}


inline int BvhNode::GetLastQueriedFrame() const
{
	return mVisibility[sCurrentState].mLastQueriedFrame;
}


inline void BvhNode::SetLastQueriedFrame(int lastTested)
{
	mVisibility[sCurrentState].mLastQueriedFrame = lastTested;
}


inline int BvhNode::GetLastRenderedFrame() const 
{ 
	return mLastRenderedFrame[sCurrentState]; 
}
	

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


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

inline int BvhNode::GetDepth() const 
{ 
	return mDepth; 
}


inline BvhNode *BvhNode::GetParent() 
{ 
	return mParent; 
}


inline int BvhNode::GetNumLeaves() const
{
	return mNumLeaves;
}


inline bool BvhNode::IsVirtualLeaf() const
{ 
	return mIsVirtualLeaf; 
}


inline float BvhNode::GetDistance() const
{
	return mDistance; 
}

	
inline const AxisAlignedBox3 &BvhNode::GetBox() const
{
	return mBox; 
}


inline int BvhNode::GetId() const 
{
	return mId; 
}


inline void BvhNode::SetId(int id) 
{
	mId = id; 
}


inline void BvhNode::SetCurrentState(int _state) 
{
	sCurrentState = _state; 
}


inline BvhNode *BvhInterior::GetBack()
{
	return mBack; 
}


inline BvhNode *BvhInterior::GetFront() 
{ 
	return mFront; 
}


inline int Bvh::GetNumNodes() const
{
	return mNumNodes; 
}


inline int Bvh::GetNumLeaves() const 
{ 
	return mNumNodes / 2 + 1;
}


inline int Bvh::GetNumVirtualNodes() const  
{ 
	return mNumVirtualNodes; 
}


inline int Bvh::GetNumVirtualLeaves() const
{
	return mNumVirtualNodes / 2 + 1;
}


inline BvhNode *Bvh::GetRoot()
{ 
	return mRoot; 
}


inline BvhNode *Bvh::GetDynamicRoot()
{ 
	return mDynamicRoot; 
}


inline BvhNode *Bvh::GetStaticRoot()
{ 
	return mStaticRoot; 
}


inline const AxisAlignedBox3 &Bvh::GetBox() const 
{ 
	return mBox; 
}


}

#endif // __BVH_H