// 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"
//#include "SceneEntity.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 BvhLoader;
	friend class mygreaterdistance;

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);
	/** Returns true if this node is a leaf.
	*/
	//virtual bool IsPseudoLeaf() = 0;
	/** Virtual destructor doing nothing.
	*/
	virtual ~BvhNode();
	/** 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 bool IsLeaf() const = 0;

	bool IsVirtualLeaf() const { return mIsVirtualLeaf; }


	////////////////
	//-- 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() { return mBox; }
	/** Return index of this node.
	*/
	inline int GetId() const { return mId; }
	/** See get
	*/
	inline void SetId(int id) { mId = 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;

	static void SetCurrentState(int _state) { sCurrentState = _state; }


protected:

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


	//////////////
	//-- members that define the current state

	/// stores the visibility related info 
	VisibilityInfo mVisibility[NUM_STATES];
	
	/// used for view frustum culling
	int mPlaneMask[NUM_STATES];
	int mPreferredPlane[NUM_STATES];

	/// when the node was last rendered
	int mLastRenderedFrame[NUM_STATES];


	// the current state
	static int sCurrentState;


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


	/// #leaves under this node
	int mNumLeaves;


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

	/// the bounding boxes of these nodes are queries instead of the current node
	int mTestNodesIdx;
	/// the number of tighter bounding volumes used for this node
	int mNumTestNodes;
	/// used for efficient element array rendering
	int mIndicesPtr;

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



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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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

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


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





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

public:

	BvhInterior(BvhNode *parent): mBack(NULL), mFront(NULL), BvhNode(parent)
	{}
	virtual bool IsLeaf() const { return false; }
	/** Back child.
	*/
	inline BvhNode *GetBack() { return mBack; }
	/** Front child.
	*/
	inline BvhNode *GetFront() { return mFront; }
	/** Recursivly delete hierarchy.
	*/
	virtual ~BvhInterior();

protected:

	BvhNode *mBack;
	BvhNode *mFront;
};


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

public:

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

	~BvhLeaf();

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


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

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


/** Class representing a bounding volume hierarchy.
*/
class Bvh
{
	friend class BvhLoader;

	/** Bvh properties
	*/
	struct BvhStats
	{
		BvhStats(): 
		mInteriorSA(0),
		mLeafSA(0),
		mInteriorVol(0),
		mLeafVol(0),
		mTriangles(0),
		mTriangleRatio(0),
		mGeometryRatio(0),
		mMaxGeometry(0),
		mMaxTriangles(0)
		{}
		
		float mInteriorSA;
		float mLeafSA;
		float mInteriorVol;
		float mLeafVol; 
		
		int mTriangles;

		float mTriangleRatio;
		float mGeometryRatio;

		int mMaxGeometry;
		int mMaxTriangles;
	};

public:

	/** Destructor.
	*/
	~Bvh();
	/** Returns number of bvh nodes.
	*/
	inline int GetNumNodes() const { return mNumNodes; }
	/** Returns number of bvh leaves.
	*/
	inline int GetNumLeaves() const { return mNumNodes / 2 + 1;}
	/** Returns number of 'virtual' nodes in the hierarchy, i.e.
		the number of nodes actually used for traversal.
	*/
	int GetNumVirtualNodes() const  { return mNumVirtualNodes; }
	/** Returns number of bvh leaves.
	*/
	inline int GetNumVirtualLeaves() const { return mNumVirtualNodes / 2 + 1;}
	/** Returns root node of the bvh.
	*/
	BvhNode *GetRoot() { return mRoot; }
	/** Sets the scene camera
	*/
	//void SetCamera(Camera * camera) { mCamera = camera; }

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

	void CollectNodes(BvhNode *node, BvhNodeContainer &nodes, int depth);
	void CollectNodes(BvhNode *node, BvhNodeContainer &nodes);
	void CollectLeaves(BvhNode *node, BvhLeafContainer &leaves);
	/** Collect only the virtual leaves.
	*/
	void CollectVirtualLeaves(BvhNode *node, BvhNodeContainer &leaves);


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

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


	/////////////
	//-- 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);
	/** Returns the bounding box of this bvh.
	*/
	inline const AxisAlignedBox3 &GetBox() { return mBox; }


	//////////////
	//-- 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);
	/** 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
	*/
	void CalcDistance(BvhNode *node) const;
	/** Returns the stored distance.
	*/
	float GetDistance(BvhNode *node) const  { return node->mDistance; }
	/** 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();
	/** Helper function that renders the bounding boxes of the leaves as
		wireframes for visualization purpose.
	*/
	//void RenderBoundingBoxesForViz(int mode);
	/** Count triangles the node contains.
	*/
	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.
	*/
	void SetVirtualLeaves(int numTriangles);
	

	////////
	//-- functions influencing tighter bounds


	/** Sets maximal depth for taking the bounding boxes to test the
		visibility of a node. 
		Deeper => the bounds adapt more to the geometry.
	*/
	void SetMaxDepthForTestingChildren(int maxDepth);

	void SetAreaRatioThresholdForTestingChildren(float ratio);


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

	/** Returns stats.
	*/
	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
	*/
	const Bvh(const SceneEntityContainer &entities);
	/** Called by the constructor. Initializes important members.
	*/
	void Init();

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

	void ComputeBvhStats();
	void PrintBvhStats() const;


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

	int PrepareBoundsWithDrawArrays(const BvhNodeContainer &nodes);
	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);



	////////////////////////
	
	/// the bounding box of the bvh
	AxisAlignedBox3 mBox;
	/// the root of the hierarchy
	BvhNode *mRoot;
	/// pointers to the geometry associated with this node
	SceneEntity **mGeometry;
	/// #of entities
	size_t mGeometrySize;


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

}

#endif // __BVH_H