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

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

#ifndef _OgreKdTree_H__
#define _OgreKdTree_H__

#define KDNODE_CAST(a) (static_cast<KdTree::Node>(a))
#define KDBRANCH_CAST(a) (static_cast<KdTree::Branch>(a))
#define KDLEAF_CAST(a) (static_cast<KdTree::Leaf>(a))
#define KDNODEPTR_CAST(a) (static_cast<KdTree::Node *>(a))
#define KDBRANCHPTR_CAST(a) (static_cast<KdTree::Branch *>(a))
#define KDLEAFPTR_CAST(a) (static_cast<KdTree::Leaf *>(a))

#define KDTREE_LOGNAME "KdTreeBuild.log"

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

#include <OgreRoot.h>

#include <stack>

#include "OgreKdTreeCamera.h"
#include "HierarchyInterface.h"


namespace Ogre
{
	class KdTreeCamera;
	class KdRenderable;
	struct SplitInfo;

	class PlaneEvent
	{
	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
		};

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

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

		~PlaneEvent() {};

		// the less operator for plane events
		// first sort by position, then by dimension and finally by type
		bool operator < (const PlaneEvent& 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 PlaneEvent& e) const
		{
			return	(mPosition[mDimension] == e.mPosition[e.mDimension]) &&
				(mDimension == e.mDimension) &&
				(mType == e.mType);
		};

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

		void classify(const PlaneEvent& e, PlaneEvent::Side side);

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

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

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

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

		// DEBUG
		String print();
	protected:
		// event info
		KdRenderable *			mRenderable;
		Vector3					mPosition;
		PlaneEvent::Dimension	mDimension;
		PlaneEvent::Type		mType;

		// ------------------------------------------------------------------------------//
		// 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: SplitInfo ... 
	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, SplitInfo& 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, SplitInfo& split);
		// 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 SplitInfo
	{
		AxisAlignedBox bleft;
		AxisAlignedBox bright;
		int nleft;
		int nright;
		Real cost;
		PlaneEvent::Side side;
		PlaneEvent event;

		// DEBUG
		String print();
	};

	typedef std::list<PlaneEvent> PlaneEventList;
	typedef std::list<KdRenderable *> KdRenderableList;
	
	class KdTree
	{
	protected:
		class Branch;
		class Leaf;

		class Node
		{
		public:
			Node(KdTree * owner, int level, AxisAlignedBox& aabb, Branch * parent):
			mOwner(owner),
			mLevel(level),
			mAABB(aabb),
			mParent(parent),
			mWBB(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).
			KdTree::Node *getParent(void) const { return mParent; };

			// Gets the nodes left & right child nodes, or NULL if not present or node is leaf
			virtual KdTree::Node *getLeftChild(void) const = 0;
			virtual KdTree::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(GtpVisibility::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);

				if (mOwner->getHiLiteLevel() == mLevel)
					mWBB->setMaterial("KdTree/BoxHiLite");
				else
					mWBB->setMaterial("BaseWhiteNoLighting");
				
				return mWBB;
			}

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

			// 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 kdtree, i.e., the merged extent of the bounding boxes. 
			*/
			AxisAlignedBox _getWorldAABB(void) const { return mAABB; };
			/** Updates bound of the real aabb of kdtree
			*/
			virtual void _updateBounds(bool recurse = true) = 0;
			
			/** bounding box of the node**/
			AxisAlignedBox mAABB;

			/** mounding box of all objects inside the node */
			AxisAlignedBox mWorldAABB;
		protected:
			KdTree * mOwner;
			Branch * mParent;
			int mLevel;

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

		class Branch : public Node
		{
		public:
			Branch(KdTree * owner, int level, AxisAlignedBox& aabb, Branch * parent, 
				Plane * splitplane, PlaneEvent::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 KdTree::Node * getLeftChild() const { return mLeft; };
			virtual KdTree::Node * getRightChild() const { return mRight; };

			virtual void queueVisibleObjects(unsigned long currentFrame, 
				Camera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes, bool fullVis = false)
			{
				if (showBoxes)
					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(GtpVisibility::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;
			PlaneEvent::Side mPlaneSide;
		protected:
			std::set<Leaf *> mLeaves;
		};

		class Leaf : public Node
		{
		public:
			Leaf(KdTree * 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 mKdRenderables.empty(); }

			// a leaf has geometry when it has renderables
			virtual bool hasGeometry() const { return !mKdRenderables.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 KdTree::Node * getLeftChild() const { return 0; };
			virtual KdTree::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(GtpVisibility::GeometryVector *geometryList);

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

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

			virtual void insert(KdRenderable * rend)
			{
				mKdRenderables.push_back(rend);
			};

			KdRenderableList mKdRenderables;
		};

		struct SplitCandidate
		{
			SplitCandidate(PlaneEventList * e, int n, AxisAlignedBox& a,
				KdTree::Branch * p, Real c, Real d, SplitInfo * b, PlaneEvent::Side s):
			events(e), nObjects(n), aabb(a), parent(p), cost(c), decrease(d), best(b), side(s)
			{ };

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

			void operator = (const SplitCandidate& 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;
			PlaneEvent::Side side;
			AxisAlignedBox aabb;
			PlaneEventList * events;
			KdTree::Branch * parent;
			SplitInfo * best;
		};

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

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

		typedef KdTree::Node * NodePtr;
		typedef KdTree::Branch * BranchPtr;
		typedef KdTree::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
		{
			KDRM_INTERNAL,
			KDRM_GTP_VFC,
			KDRM_GTP_SWC,
			KDRM_GTP_CHC,
			// invalid modes, just for convenience
			KDRM_SIZE,
			KDRM_NOTSET
		};

		enum BuildMethod
		{
			KDBM_RECURSIVE,
			KDBM_PRIORITYQUEUE,
			// invalid modes, just for convenience
			KDBM_SIZE,
			KDBM_NOTSET
		};


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

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

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

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

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

		/** Recurses the kdtree, 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 (mKdRoot) return mKdRoot->mAABB; else return AxisAlignedBox(); }
		void setBuildMethod(BuildMethod bm) { mBuildMethod = bm; }
	protected:
		// init materials, logs and stuff
		void init();
		// recursive insert funciton
		void recInsert(KdTree::Node * node, KdRenderable * rend);
		// helper functions for insert
		void recInsertNew(KdTree::Branch * parent, PlaneEvent::Side side, KdRenderable * rend);
		void splitBox(const KdTree::Branch& parent, AxisAlignedBox& left, AxisAlignedBox& right);
		void rebuildSubtree(KdTree::Node * node, KdRenderable * rend);
		// build scene from a list of nodes rather than a hierarchy
		KdTree::Node * buildFromList(KdRenderableList& nodelist, KdTree::Branch * parent, AxisAlignedBox& aabb);
		void addRendToList(KdTree::Node * node, KdRenderableList& nodelist);

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

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

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

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

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

		/** Recurses the kdtree, 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 kdtree
		KdTree::Node * mKdRoot;
		// Maximum depth of the tree
		int mMaxDepth;

		// how to build the tree
		BuildMethod mBuildMethod;

		// 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 kdtree
		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
		KdTreeCamera::NodeVisibility (KdTreeCamera::*getVisibility)(const AxisAlignedBox& box) const;

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

} // namespace Ogre

#endif // _OgreKdTree_H__