/*
-----------------------------------------------------------------------------
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))

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

#include <OgreRoot.h>

#include <stack>



namespace Ogre
{
	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(int level, AxisAlignedBox& aabb, Branch * parent):
			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;
			
			// consider using typesafe callback functions
			//virtual void cbInsert(KdTree * caller, KdRenderable * rend) = 0;

			WireBoundingBox * getWireBoundingBox()
			{
				if (mWBB == 0)
					mWBB = new WireBoundingBox();

				mWBB->setupBoundingBox(mAABB);
				
#ifdef KDTREE_DEBUG
				int level = -1;
				bool boxes = false;
				if (Root::getSingleton()._getCurrentSceneManager()->getOption("HighlightLevel",&level))
				{
					if (mLevel == level)
					{
						//mWBB->setMaterial("BaseGreenNoLighting");
						mWBB->setMaterial("aabbHiLite");
						return mWBB;
					}
					else
					{
						mWBB->setMaterial("BaseWhiteNoLighting");
						if (Root::getSingleton()._getCurrentSceneManager()->getOption("ShowAllBoxes", &boxes))
						{
							if (boxes)
								return mWBB;
							else
								return 0;
						}
					}
				}
#else
				mWBB->setMaterial("BaseWhiteNoLighting");
#endif // KDTREE_DEBUG
				return mWBB;

			}

			// 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; };
			/** Gets this node's parent (NULL if this is the root).
			*/	
			KdTree::Branch *getParent(void) { return mParent; };
			/** 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() = 0;


			Branch * mParent;
			int mLevel;
			AxisAlignedBox mAABB;
		protected:
			WireBoundingBox * mWBB;

			// for the CHC hierarchy interface
			/** the real extent of the node. */
			AxisAlignedBox mWorldAABB;
			
			unsigned int mLastRendered;
			unsigned int mLastVisited;
			bool mVisible;
		};

		class Branch : public Node
		{
		public:
			Branch(int level, AxisAlignedBox& aabb, Branch * parent, Plane * splitplane, PlaneEvent::Side side):
				Node(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; };

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

				if (mLeft)
					mWorldAABB.merge(mLeft->_getWorldAABB());
				if (mRight)
					mWorldAABB.merge(mRight->_getWorldAABB());

				// update parent recursively
				if (mParent)
					mParent->_updateBounds();
			}
			
			Node * mLeft;
			Node * mRight;
			Plane  * mSplitPlane;
			PlaneEvent::Side mPlaneSide;
		};

		class Leaf : public Node
		{
		public:
			Leaf(int level, AxisAlignedBox& aabb, Branch * parent):
			  Node(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(); };

			// update the world aabb based on the contained geometry
			virtual void _updateBounds();

			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::set<LeafPtr> LeafSet;

		typedef struct Stats_
		{
			unsigned int mNumNodes;
			unsigned int mNumLeaves;
			unsigned int mNumSceneNodes;

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

		enum RenderMethod
		{
			KDRM_INTERNAL,
			KDRM_GTP_VFC,
			KDRM_GTP_SWC,
			KDRM_GTP_CHC

		};

		enum BuildMethod
		{
			KDBM_RECURSIVE,
			KDBM_PRIORITYQUEUE
		};
		
		KdTree(int maxdepth);
		virtual ~KdTree();

		// DEBUG
		void dump(void);
		Real calcCost(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(Camera* cam, RenderQueue* queue, bool onlyShadowCasters, 
			RenderMethod renderMethod, bool showBoxes = false);

		// self-explanatory ...
		int getMaxDepth(void) { return mMaxDepth; };
		Stats getStats(void) const { return mStats; };
		AxisAlignedBox getBox(void) { if (mKdRoot) return mKdRoot->mAABB; else return AxisAlignedBox(); };
		void setBuildMethod(BuildMethod bm) { mBuildMethod = bm; }
	protected:
		// 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, 
			Camera* cam, RenderQueue* queue, bool onlyShadowCasters, bool showBoxes);

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

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

} // namespace Ogre

#endif // _OgreKdTree_H__