/*********************************************************************

Name:		Raytracer
Author:		Kamil Szatkowski "Netrix" (C)
Website:	http://www.netrix.org.pl/

Implementation based on source code from: http://www.devmaster.net/articles/raytracing_series/part1.php

*********************************************************************/
#pragma once
#include "Scene.hpp"
#include "NLib/nAlignedDynamicTable.hpp"
#include "NLib/nDataVector.hpp"
#include "NLib/nAlignedDataVector.hpp"

struct FacesListNode
{
	FaceData* pFace;
	FacesListNode* pNext;
};

class KDTreeNode
{
	static const NIne::NSize_t NODE_INFO_MASK = 0x7;
	static const NIne::NSize_t AXIS_INFO_MASK = 0x3;
	static const NIne::NSize_t LEAF_INFO_MASK = 0x4;
	static const NIne::NSize_t PRIM_LIST_MASK = NMAX_SIZE_T ^ NODE_INFO_MASK;
	static const NIne::NSize_t PRIM_LEAF_MASK = NMAX_SIZE_T ^ AXIS_INFO_MASK;

	static const NIne::NSize_t NODE_INFO_MASK_BIT_SIZE = 3;
#ifndef _WIN64
	static const NIne::NSize_t NODE_INFO_ROUND_MASK = 0xE0000000;
#else
	static const NIne::NSize_t NODE_INFO_ROUND_MASK = 0xE000000000000000;
#endif

public:
	KDTreeNode() : m_uData(6) {};

	void					setLeaf(bool bLeaf)						{ bLeaf ? m_uData |= LEAF_INFO_MASK : m_uData &= ~LEAF_INFO_MASK; }
	bool					isLeaf() const							{ return (m_uData & LEAF_INFO_MASK) != 0; }
	void					setAxis(NIne::NUint32 uAxis)			{ m_uData = (NIne::NSize_t)(m_uData & PRIM_LEAF_MASK) | uAxis; }
	NIne::NUint32			getAxis() const							{ return (NIne::NUint32)(m_uData & AXIS_INFO_MASK); }
	void					setPrimitiveList(FacesListNode* pFaces)	{ m_uData = (NIne::NSize_t)pFaces + (m_uData & NODE_INFO_MASK); }
	const FacesListNode*	getPrimitiveList() const				{ return (const FacesListNode*)(m_uData & PRIM_LIST_MASK); }
	void					setSplit(float fSplit)					{ m_fSplit = fSplit; }
	float					getSplit() const						{ return m_fSplit; }

	void					setChildren(KDTreeNode* pNodes)			{ m_uData = (NIne::NSize_t)pNodes + (m_uData & NODE_INFO_MASK); }
	KDTreeNode*				getLeftChild()							{ return (KDTreeNode*)(m_uData & PRIM_LIST_MASK); }
	KDTreeNode*				getRightChild()							{ return (KDTreeNode*)(m_uData & PRIM_LIST_MASK) + 1; }

// Build time functions - half of m_uData is axis and leaf info and half is index to children
public:
	void					bSetPrimitiveList(NIne::NSize_t uIndex)	{ m_uData = (NIne::NSize_t)(~uIndex << NODE_INFO_MASK_BIT_SIZE) + (m_uData & NODE_INFO_MASK); }
	NIne::NSize_t			bGetPrimitiveList() const				{ return (m_uData >> NODE_INFO_MASK_BIT_SIZE) == 0 ? NMAX_SIZE_T : ~(NIne::NSize_t)((m_uData >> NODE_INFO_MASK_BIT_SIZE) | NODE_INFO_ROUND_MASK); }

	void					bSetChildren(NIne::NSize_t uIndex)		{ bSetPrimitiveList(uIndex); }
	NIne::NSize_t			bGetLeftChild()							{ return bGetPrimitiveList(); }
	NIne::NSize_t			bGetRightChild()						{ return bGetPrimitiveList() + 1; }

public:
	NIne::NSize_t m_uData;	// 4/8
	float m_fSplit;		// 4
#ifdef _WIN64
	NIne::NUint32 m_uDummy; // 4
#endif
};


class KDTree
{
	struct SplitCandidate
	{
		float fSplitPosition;
		NIne::NUint32 uLNCount, uRNCount;
		SplitCandidate* pNext;
	};

	struct KDStackNode
	{
		KDTreeNode* node;						// 4/8
		float t;								// 4
		NIne::NMVector3f v3pb;					// 12
		NIne::NUint32 uPrev;					// 4
		NIne::NUint32 dummy1;					// 4
	#ifndef _WIN64
		NIne::NUint32 dummy2;
	#endif
	};	// 32

	typedef NIne::NAlignedDynamicTable<KDTreeNode> KDTreeNodeArray;
	typedef NIne::NAlignedDataVector<FacesListNode> FacesListNodeArray;
	typedef NIne::NDataVector<KDTreeNode> KDTreeNodeVector;
	typedef NIne::NAlignedDynamicTable<KDStackNode> KDStackNodeVector;

public:
	void buildTree(Scene* pScene, bool bResetCache);

	void saveTree(const char* szFile, const KDTreeNodeVector& nodes);

	bool loadTree(const char* szFile, KDTreeNodeVector* nodes);

	void release();

	const FaceData* findNearestFace(const NIne::NMVector3f& v3Origin, const NIne::NMVector3f& v3Direction, float fMaxDistance, RayTestOutput* pRTO);

	bool findObstacle(const NIne::NMVector3f& v3Origin, const NIne::NMVector3f& v3Direction, float fMaxDistance);

private:
	void subdivide(KDTreeNodeVector* pKdNodeVector, NIne::NSize_t uNode, SplitCandidate* pSCPool, const BoxAABB& aabb, NIne::NUint32 uDepth, NIne::NSize_t uFaces);

	// Functions related to mem managing of object list
	NIne::NSize_t getNewObjectListNode();

	void freeObjectListNodes(NIne::NSize_t uIndex);

	// Some other functions
	static void calculateRange(const FaceData* pFace, NIne::NUint32 uAxis, float* a, float* b);

	static void insertSplitPos(SplitCandidate** pSCPool, SplitCandidate** pSCList, float fSplitPos);

	// Debug
	bool walkthroughNodes(NIne::NUint32 uFace, KDTreeNode* pNode);

	bool walkthroughFacesList(NIne::NUint32 uFace, const FacesListNode* pFaceListNode);

private:
	Scene* m_pScene;
	KDTreeNode* m_pRoot;
	KDTreeNodeArray m_aKDNodes;
	KDStackNodeVector m_aKDStack;
	FacesListNodeArray m_dvObjectLists;
	NIne::NSize_t m_uObjectListPool;	// pool for object list
};
