/*
-----------------------------------------------------------------------------
This source file is part of the GameTools Project
http://www.gametools.org

Author: Martin Szydlowski
-----------------------------------------------------------------------------
*/

#ifndef _OgreBiHierarchy_H__
#define _OgreBiHierarchy_H__

#define BIHNODE_CAST(a) (static_cast<BiHierarchy::Node>(a))
#define BIHBRANCH_CAST(a) (static_cast<BiHierarchy::Branch>(a))
#define BIHLEAF_CAST(a) (static_cast<BiHierarchy::Leaf>(a))
#define BIHNODEPTR_CAST(a) (static_cast<BiHierarchy::Node *>(a))
#define BIHBRANCHPTR_CAST(a) (static_cast<BiHierarchy::Branch *>(a))
#define BIHLEAFPTR_CAST(a) (static_cast<BiHierarchy::Leaf *>(a))

#define BiHierarchy_LOGNAME "BiHierarchyBuild.log"

#include <OgreAxisAlignedBox.h>
#include <OgreWireBoundingBox.h>
#include <OgrePlane.h>
#include <OgreVector3.h>

#include <OgreRoot.h>

#include <stack>

#include "OgreBiHierarchyCamera.h"
#include "HierarchyInterface.h"
#include "OgreKdTree.h"

namespace Ogre
{
	class BiHierarchyCamera;
	class BihRenderable;
	struct BihSplitInfo;
	
	class BihPlaneEvent
	{
	public:
		enum Type
		{
			PET_END,
			PET_ON,
			PET_START
		};

		enum Dimension
		{
			PED_X,
			PED_Y,
			PED_Z
		};

		enum Side
		{
			PES_LEFT = 0x01,
			PES_RIGHT = 0x02,
			PES_BOTH = PES_LEFT | PES_RIGHT
		};

		BihPlaneEvent(): mRenderable(0), mPosition(Vector3()), mDimension(PED_X), mType(PET_ON)
		{ };

		BihPlaneEvent(BihRenderable *rend, const Vector3& pos, BihPlaneEvent::Dimension dim, BihPlaneEvent::Type type):
			mRenderable(rend), mPosition(pos), mDimension(dim), mType(type) 
		{ };

		~BihPlaneEvent() {};

		// the less operator for plane events
		// first sort by position, then by dimension and finally by type
		bool operator < (const BihPlaneEvent& e) const
		{
			if(mPosition[mDimension] < e.mPosition[e.mDimension])
			{
				return true;
			}

			if(mPosition[mDimension] == e.mPosition[e.mDimension])
			{
				if (mDimension < e.mDimension)
				{
					return true;
				}
				if (mDimension == e.mDimension)
				{
					if (mType < e.mType)
					{
						return true;
					}
				}
			}

			return false;
		};

		// the equals operator for tree events
		bool operator == (const BihPlaneEvent& e) const
		{
			return	(mPosition[mDimension] == e.mPosition[e.mDimension]) &&
				(mDimension == e.mDimension) &&
				(mType == e.mType);
		};

		bool equalsType(const BihPlaneEvent& e, BihPlaneEvent::Type t)
		{
			return	(mPosition[mDimension] == e.mPosition[e.mDimension]) &&
				(mDimension == e.mDimension) &&
				(mType == t);
		};

		void classify(const BihPlaneEvent& e, BihPlaneEvent::Side side, bool absolute);

		BihPlaneEvent clip(AxisAlignedBox& box, BihPlaneEvent::Dimension dim);

		BihPlaneEvent::Type GetType() { return mType;};

		void ClearGrowBB()
		{
			IncBB.setNull();
		}

		void GrowBB(AxisAlignedBox bb)
		{
			IncBB.merge(bb);
		}

		AxisAlignedBox GetGrowBB()
		{
			return IncBB;
		}





		Plane * getSplitPlane() const
		{
			Vector3 normal(0,0,0);
			normal[mDimension] = 1;
			return new Plane(normal, mPosition);
		}

	    Vector3 getPosition()
		{
			return mPosition;
		}

		BihRenderable * getRenderable() const //??
		{
			return mRenderable;
		};

		BihPlaneEvent::Dimension getDimension() const //??
		{
			return mDimension;
		};

		// DEBUG
		String print();
	protected:
		// event info
		BihRenderable *			mRenderable;
		Vector3					mPosition;
		BihPlaneEvent::Dimension	mDimension;
		BihPlaneEvent::Type		mType;
		AxisAlignedBox IncBB;

		// ------------------------------------------------------------------------------//
		// functions to determine the cost of splitting the node parent with the plane
		// represented by this event
		// TODO discuss if these functions really belong here, OO & SE - wise
		// pros: convenient, don't have to pass internal data to the outside
		// cons: BihSplitInfo ... 
	public:
		// compute "global" surface area heuristic (SAH) for the plane represented by this event
		// use only with priority queue build method
		void pqSAH(Real globalSA, Real parentSA, int nLeft, int nPlane, int nRight, AxisAlignedBox& parentBox, BihSplitInfo& split);
		static Real pqSplitCost(Real p, Real pl, Real pr, int nLeft, int nRight, Real mu);

		// compute the surface area heuristic (SAH) for the plane represented by this event
		void SAH(const AxisAlignedBox& parent, int nLeft, int nPlane, int nRight, BihSplitInfo& split);
		void SAH(const AxisAlignedBox& parent, int nLeft, int nPlane, int nRight, BihSplitInfo& split,AxisAlignedBox left,AxisAlignedBox right);

		// the variables determining the cost of a branch traversal (KT) and a leaf intersection (KI)
		static Real KT;
		static Real KI;
		// helper functions
		static Real splitCost(Real pl, Real pr, int nLeft, int nRight);
		static Real splitCost(Real pl, Real pr, int nLeft, int nRight, Real mu);
		static Real surfaceArea(const AxisAlignedBox& box);
		static Real lookupPenalty(Real p);
	protected:
		Real splitBox(const AxisAlignedBox& parent, AxisAlignedBox& left, AxisAlignedBox& right);
	};

	// Holds all the important information on a split
	struct BihSplitInfo
	{
		AxisAlignedBox bleft;
		AxisAlignedBox bright;
		int nleft;
		int nright;
		Real cost;
		BihPlaneEvent::Side side;
		BihPlaneEvent event;

		// DEBUG
		String print();
	};

	typedef std::list<BihRenderable *> BihRenderableList;
	typedef std::list<BihPlaneEvent> BihPlaneEventList;
	
	class BiHierarchy
	{
	protected:
		class Branch;
		class Leaf;

		class Node
		{
		public:
			Node(BiHierarchy * owner, int level, AxisAlignedBox& aabb, Branch * parent):
			mOwner(owner),
			mLevel(level),
			mAABB(aabb),
			mParent(parent),
			mWBB(0),
			m_iSide(0)
			{ };

			virtual ~Node()
			{
				delete mWBB;
			};

			virtual bool isLeaf() const = 0;
			virtual bool isEmpty() const = 0;
			virtual bool hasGeometry() const = 0;
			
			virtual void mergeLeaves(std::set<Leaf *>& leaves) = 0;

			// Gets this node's parent (NULL if this is the root).
			BiHierarchy::Node *getParent(void) const { return mParent; };

			// Gets the nodes left & right child nodes, or NULL if not present or node is leaf
			virtual BiHierarchy::Node *getLeftChild(void) const = 0;
			virtual BiHierarchy::Node *getRightChild(void) const = 0;

			// add contained objects to render queue
			virtual void queueVisibleObjects(unsigned long currentFrame, 
				Camera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes, bool fullVis = false) = 0;

			// add contained geometry (Entities) to list
			virtual void getGeometryList(GeometryVector *geometryList) = 0;
			
			// create (when necessary), setup and return wire bounding box representing the node
			WireBoundingBox * getWireBoundingBox()
			{
				if (mWBB == 0)
					mWBB = new WireBoundingBox();

				if (mOwner->getShowNodes())
					mWBB->setupBoundingBox(mAABB);
				else
					mWBB->setupBoundingBox(mWorldAABB);

				// cse
				if (mOwner->getHiLiteLevel() == mLevel)
					switch (m_iSide)
					{
					case 0:
						{ 
							mWBB->setMaterial("BiHierarchy/BoxViz"); break;
						}
					case 1: {
						     mWBB->setMaterial("BiHierarchy/BoxLeft"); break;
							}
					default: 
						{ 
							mWBB->setMaterial("BiHierarchy/BoxRight");
						}
					}
				 else if (mOwner->getHiLiteLevel() == (mLevel+1))
				 {
					
							mWBB->setMaterial("BiHierarchy/BoxViz");
					
					
				 } else
				 {
					switch (m_iSide)
					{
					case 0:
						{ 
							mWBB->setMaterial("BiHierarchy/BoxViz"); break;
						}
					case 1: {
						     mWBB->setMaterial("BiHierarchy/BoxLeftDark"); break;
							}
					default: 
						{ 
							mWBB->setMaterial("BiHierarchy/BoxRightDark");
						}
					}
				
					
				 }
				
				return mWBB;
			}

			// returns the level the node is on
			int getLevel(void) const { return mLevel; };

			void SetToLeft() {
				m_iSide=1; 
			};
			void SetToRight() { 
				m_iSide=2; 
			};
			int GetSide() { return m_iSide; };


			// functions for the CHC hierarchy interface

			/** Returns last visited frame id. */
			unsigned int lastVisited(void) { return mLastVisited; };
			/** Set to current frame id.
			@param current frame id.
			*/
			void setLastVisited(unsigned int frameid) { mLastVisited = frameid; };
			/** Makes this octree become visible / invisble.
			@param visible Whether this node is to be made visible or invisible
			*/
			void setNodeVisible(bool visible) { mVisible = visible; };
			/** Returns true if this node is marked visible, false otherwise. 
			*/
			bool isNodeVisible(void) { return mVisible; };
			/** Frame id when this octree was last rendered. 
			@return last rendered frame id
			*/	
			unsigned int lastRendered(void) { return mLastRendered; };
			/** Sets frame id when this octree was last rendered. 
			@param last rendered frame id
			*/
			void setLastRendered(unsigned int frameid) { mLastRendered = frameid; };
			/** Returns real extent of the BiHierarchy, i.e., the merged extent of the bounding boxes. 
			*/
			AxisAlignedBox _getWorldAABB(void) const { return mAABB; };
			/** Updates bound of the real aabb of BiHierarchy
			*/
			virtual void _updateBounds(bool recurse = true) = 0;
			
			/** bounding box of the node
			*/
			AxisAlignedBox mAABB;

			/** bounding box of all objects inside the node 
			*/
			AxisAlignedBox mWorldAABB;


		protected:
			BiHierarchy * mOwner;
			Branch * mParent;
			int mLevel;
			int m_iSide; // defines the side ( left / right ) for better debugging. 

			WireBoundingBox * mWBB;
			
			// for the CHC hierarchy interface
			unsigned int mLastRendered;
			unsigned int mLastVisited;
			bool mVisible;
		};

		class Branch : public Node
		{
		public:
			Branch(BiHierarchy * owner, int level, AxisAlignedBox& aabb, Branch * parent, 
				Plane * splitplane, BihPlaneEvent::Side side):
			Node(owner, level, aabb, parent), 
			mSplitPlane(splitplane), 
			mLeft(0), 
			mRight(0),
			mPlaneSide(side)
			{ };

			virtual ~Branch()
			{
				delete mLeft;
				delete mRight;
				delete mSplitPlane;
			};

			// a branch is not a leaf 
			virtual bool isLeaf() const { return false; };

			// s branch is empty when it does not have children
			virtual bool isEmpty() const { return (mLeft == 0 && mRight == 0); }

			// a branch never has geometry
			virtual bool hasGeometry() const { return false; };

			virtual void mergeLeaves(std::set<Leaf *>& leaves)
			{
				for (std::set<Leaf *>::iterator it = mLeaves.begin(); it != mLeaves.end(); it++)
					leaves.insert(*it);
			}

			// a branch should have at least one child
			virtual BiHierarchy::Node * getLeftChild() const { return mLeft; };
			virtual BiHierarchy::Node * getRightChild() const { return mRight; };

			virtual void queueVisibleObjects(unsigned long currentFrame, 
				Camera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes, bool fullVis = false)
			{
				// cse 
				showBoxes=true;
				if (showBoxes)
				{
					/*
					if (mLevel == mOwner->getHiLiteLevel()|| (mLevel-1) == mOwner->getHiLiteLevel() || mOwner->getShowAllBoxes())
					queue->addRenderable(getWireBoundingBox());
					*/
					
					if (mLevel == mOwner->getHiLiteLevel() || mOwner->getShowAllBoxes())
						queue->addRenderable(getWireBoundingBox());
					
				}

				if (fullVis)
					for (std::set<Leaf *>::iterator it = mLeaves.begin(); it != mLeaves.end(); it ++)
						(*it)->queueVisibleObjects(currentFrame, cam, queue, onlyShadowCasters, showBoxes, fullVis);
			}

			// a branch has no geometry, do nothing
			virtual void getGeometryList(GeometryVector *geometryList) { }

			// branches do not posses geometry => just merge child aabbs
			virtual void _updateBounds(bool recurse = true)
			{
				// reset box
				mWorldAABB.setNull();

				// merge box & leaves
				if (mLeft)
				{
					mWorldAABB.merge(mLeft->mWorldAABB);
					mLeft->mergeLeaves(mLeaves);
				}
				if (mRight)
				{
					mWorldAABB.merge(mRight->mWorldAABB);
					mRight->mergeLeaves(mLeaves);
				}

				// update parent recursively
				if (recurse && mParent)
					mParent->_updateBounds(recurse);
			}
			
			Node * mLeft;
			Node * mRight;
			Plane  * mSplitPlane;
			BihPlaneEvent::Side mPlaneSide;
		protected:
			std::set<Leaf *> mLeaves;
		};

		class Leaf : public Node
		{
		public:
			Leaf(BiHierarchy * owner, int level, AxisAlignedBox& aabb, Branch *parent):
			Node(owner, level, aabb, parent) 
			{};

			virtual ~Leaf();

			// a leaf is a leaf, dammit
			virtual bool isLeaf() const { return true; }

			// a leaf is empty when it does not posses renderables
			virtual bool isEmpty() const { return mBihRenderables.empty(); }

			// a leaf has geometry when it has renderables
			virtual bool hasGeometry() const { return !mBihRenderables.empty(); }

			// a leaf adds itself to the leaf set
			virtual void mergeLeaves(std::set<Leaf *>& leaves)	{ leaves.insert(this); }

			// a leaf never has children 
			virtual BiHierarchy::Node * getLeftChild() const { return 0; };
			virtual BiHierarchy::Node * getRightChild() const { return 0; };

			virtual void queueVisibleObjects(unsigned long currentFrame, 
				Camera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes, bool fullVis = false);

			virtual void getGeometryList(GeometryVector *geometryList);

			// update the world aabb based on the contained geometry
			virtual void _updateBounds(bool recurse = true);

			virtual void remove(BihRenderable * rend)
			{
				mBihRenderables.remove(rend);
				//mBihRenderables.erase(find(mBihRenderables.begin(), mBihRenderables.end(), rend));
			};

			virtual void insert(BihRenderable * rend)
			{
				mBihRenderables.push_back(rend);
			};

			BihRenderableList mBihRenderables;
		};

		struct BihSubdivisionCandidate
		{
			BihSubdivisionCandidate(BihPlaneEventList * e, int n, AxisAlignedBox& a,
				BiHierarchy::Branch * p, Real c, Real d, BihSplitInfo * b, BihPlaneEvent::Side s):
			events(e), nObjects(n), aabb(a), parent(p), cost(c), decrease(d), best(b), side(s)
			{ };

			bool operator < (const BihSubdivisionCandidate& rhs) const
			{
				return decrease < rhs.decrease;
			};

			void operator = (const BihSubdivisionCandidate& rhs)
			{
				decrease = rhs.decrease;
				cost = rhs.cost;
				nObjects = rhs.nObjects;
				side = rhs.side;
				aabb = rhs.aabb;
				events = rhs.events;
				parent = rhs.parent;
				best = rhs.best;
			};

			// DEBUG
			String print();

			Real decrease;
			Real cost;
			int nObjects;
			BihPlaneEvent::Side side;
			AxisAlignedBox aabb;
			BihPlaneEventList *events;
			BiHierarchy::Branch * parent;
			BihSplitInfo * best;
		};

		// typedef std::stack<BihSubdivisionCandidate> SplitCandidatePQ;
		typedef std::priority_queue<BihSubdivisionCandidate> SplitCandidatePQ;

		// nodestack for the stack-based rendering function
		typedef std::stack<BiHierarchy::Node *> NodeStack;
	public:
		friend class BiHierarchyInterface;

		typedef BiHierarchy::Node * NodePtr;
		typedef BiHierarchy::Branch * BranchPtr;
		typedef BiHierarchy::Leaf * LeafPtr;

		typedef std::list<NodePtr> NodeList;
		typedef std::set<LeafPtr> LeafSet;

		struct TreeStats
		{
			unsigned int mNumNodes;
			unsigned int mNumLeaves;
			unsigned int mNumSceneNodes;

			void clear(void)
			{
				mNumNodes = 0;
				mNumLeaves = 0;
				mNumSceneNodes = 0;
			}
		};

		struct FrameStats 
		{
			unsigned int mTraversedNodes;
			unsigned int mRenderedNodes;
			unsigned int mFrustumCulledNodes;

			void clear(void)
			{
				mTraversedNodes = 0;
				mRenderedNodes = 0;
				mFrustumCulledNodes = 0;
			}
		};

		enum RenderMethod
		{
			BIHRM_INTERNAL,
			BIHRM_GTP_VFC,
			BIHRM_GTP_SWC,
			BIHRM_GTP_CHC,
			BIHRM_GTP_RU,
			// invalid modes, just for convenience
			BIHRM_SIZE,
			BIHRM_NOTSET
		};

		enum BuildMethod
		{
			BIHBM_RECURSIVE,
			BIHBM_PRIORITYQUEUE,
			// invalid modes, just for convenience
			BIHBM_SIZE,
			BIHBM_NOTSET
		};

		enum PlaneAlorithm
		{
			BIHAL_SAH,
			BIHAL_MID
		};


		const static int HILITE_OFF  = -1;
		
		BiHierarchy(int maxdepth, BuildMethod bm);
		BiHierarchy(int maxdepth, BuildMethod bm, int hilite, bool allboxes, bool shownodes);
		virtual ~BiHierarchy();

		// DEBUG
		void dump(void);
		Real calcCost(void);

		// sets the level to highlight or turns it off (when hilite < 0)
		inline void setHiLiteLevel(int hilite) { mHiLiteLevel = hilite; };
		inline int  getHiLiteLevel(void) { return mHiLiteLevel; };

		// toggles displaying the BiHierarchy boxes
		inline void setShowAllBoxes(bool show) { mShowAllBoxes = show; };
		inline bool getShowAllBoxes(void) { return mShowAllBoxes; };

		// toggles between displaying the bounding box of the node and
		// the box of the contained scene nodes
		inline void setShowNodes(bool show = true) { mShowNodes = show; };
		inline bool getShowNodes(void) { return mShowNodes; };

		// changes vis mode (simple/enhanced with NONE/PART/FULL vis)
		void setEnhancedVis(bool enh);
		bool getEnhancedVis(void);

		NodePtr getRoot(void) const { return mBihRoot; };

		// insert a new scene node into an existing Bihierarchy
		void insert(BihRenderable * rend);
		// remove a scene node from the tree
		void remove(BihRenderable * rend);
		// function to initialize a kd-tree based on the contents of the scene
		void build(BihRenderable * sceneRoot);

		// test visibility of objects and add to render	queue
		void queueVisibleObjects(BiHierarchyCamera* cam, RenderQueue* queue, bool onlyShadowCasters, 
			bool showBoxes, BiHierarchy::NodeList& visibleNodes);

		// find visible nodes & place in list
		//void findVisibleNodes(NodeList& visibleNodes, Camera * cam);

		/** Recurses the BiHierarchy, adding any nodes intersecting with the 
		box/sphere/volume/ray into the given list.
		It ignores the exclude scene node.
		*/
		void findNodesIn(const AxisAlignedBox &box, std::list<SceneNode *> &list, SceneNode *exclude = 0);
		void findNodesIn(const Sphere &sphere, std::list<SceneNode *> &list, SceneNode *exclude = 0);
		void findNodesIn(const PlaneBoundedVolume &volume, std::list<SceneNode *> &list, SceneNode *exclude = 0);
		void findNodesIn(const Ray &ray, std::list<SceneNode *> &list, SceneNode *exclude = 0);

		// self-explanatory ...
		int getMaxDepth(void) { return mMaxDepth; }
		const TreeStats& getTreeStats(void) const { return mTreeStats; }
		const FrameStats& getFramesStats(void) const { return mFrameStats; }
		AxisAlignedBox getBox(void) { if (mBihRoot) return mBihRoot->mAABB; else return AxisAlignedBox(); }
		void setBuildMethod(BuildMethod bm) { mBuildMethod = bm; }
	protected:
		// init materials, logs and stuff
		void init();
		// recursive insert funciton
		void recInsert(BiHierarchy::Node * node, BihRenderable * rend);
		// helper functions for insert
		void recInsertNew(BiHierarchy::Branch * parent, BihPlaneEvent::Side side, BihRenderable * rend);
		void splitBox(const BiHierarchy::Branch& parent, AxisAlignedBox& left, AxisAlignedBox& right);
		void rebuildSubtree(BiHierarchy::Node * node, BihRenderable * rend);
		// build scene from a list of nodes rather than a hierarchy
		BiHierarchy::Node * buildFromList(BihRenderableList& nodelist, BiHierarchy::Branch * parent, AxisAlignedBox& aabb);
		void addRendToList(BiHierarchy::Node * node, BihRenderableList& nodelist);

		// recursively delete empty nodes
		void recDelete(BiHierarchy::Node * node);

		// find the best plane for node division
		BihSplitInfo * pqFindPlane(BihPlaneEventList * events, int nObjects, AxisAlignedBox& aabb, Real globalSA);

		// priority queue based build function
		BiHierarchy::Node * pqBuild(BihPlaneEventList& events, int nObjects, AxisAlignedBox& aabb, BiHierarchy::Branch * parent);
		// recursive build function
		BiHierarchy::Node * recBuild(BihPlaneEventList& events, int nObjects, AxisAlignedBox& aabb, BiHierarchy::Branch * parent);

		// recursive rendering function
		void recQueueVisibleObjects(BiHierarchy::Node * node, unsigned long currentFrame, BiHierarchyCamera* cam,
			RenderQueue* queue, bool onlyShadowCasters, bool showBoxes, 
			BiHierarchy::NodeList& visibleNodes, bool fullVis = false);

		// recursively find visible nodes
		//void recFindVisibleNodes(BiHierarchy::Node * node, NodeList& visibleNodes, Camera * cam);

		/** Recurses the BiHierarchy, adding any nodes intersecting with the 
		box/sphere/volume/ray into the given list.
		It ignores the exclude scene node.
		*/
		void recFindNodesIn(const AxisAlignedBox &box, std::list<SceneNode *> &list, SceneNode *exclude, Node * node, bool full = false);
		void recFindNodesIn(const Sphere &sphere, std::list<SceneNode *> &list, SceneNode *exclude, Node * node, bool full = false);
		void recFindNodesIn(const PlaneBoundedVolume &volume, std::list<SceneNode *> &list, SceneNode *exclude, Node * node, bool full = false);
		void recFindNodesIn(const Ray &ray, std::list<SceneNode *> &list, SceneNode *exclude, Node * node, bool full = false);

		// the root node of the BiHierarchy
		BiHierarchy::Node * mBihRoot;
		// Maximum depth of the tree
		int mMaxDepth;

		// how to build the tree
		BuildMethod mBuildMethod;

		// what algorithm will be used to find the split plane
		PlaneAlorithm mAlgorithm;

		// logfile for tree creation
		Log * mBuildLog;

		// statistical information on the tree
		TreeStats mTreeStats;

		// statistical info on a single rendered frame
		FrameStats mFrameStats;

		/** Visualization flags **/
		// show/highlight selected level in BiHierarchy
		int mHiLiteLevel;
		// show whole kd-tree
		bool mShowAllBoxes;
		// show node or object boxes
		bool mShowNodes;

		// function pointer to the getVisibility function
		// allows choosing between regular vis (NONE/PART, same es isVisible)
		// and enhaced vis (NONE/PART/FULL) for early traversal abort
		BiHierarchyCamera::NodeVisibility (BiHierarchyCamera::*getVisibility)(const AxisAlignedBox& box) const;

		// DEBUG
		void BiHierarchy::dump(BiHierarchy::Node * node);
		Real BiHierarchy::calcCost(BiHierarchy::Node * node, Real vs);
	}; // class BiHierarchy

} // namespace Ogre

#endif // _OgreBiHierarchy_H__