///////////////////////////////////////////////////////////////////////////////
/// @file deOctree.hpp
///
/// @brief octree for use in scenegraph, not for use outside scenegraph library
///
/// @author Assassin
///
/// This file is the intellectual property of Novus Delta, LLC.. Usage of the
/// contents of this file is subject to the Destiny3D Member License which
/// can be found at http://www.destiny3d.com.  Any other usage is prohibited.
///
/// This file is distributed "AS IS" without warranty of any kind.  Novus
/// Delta, LLC. does not guarantee the fitness of the contents of this file
/// for any particular purpose.
///
/// Copyright (C) 2001-2003 Novus Delta, LLC. All Rights Reserved.
///
/// <hr>
///                                 Change History
/// </hr>
///
/// @date Jun 2002
/// @author Assassin
/// @remarks Initial Creation
///
///////////////////////////////////////////////////////////////////////////////

#ifndef DEOCTREE_HPP
#define DEOCTREE_HPP

#include "deGlobalTypes.hpp"
#include "deScene.hpp"
#include "deList.hpp" // for collide info

#if defined(DESCENE_DLL_EXPORTS) || defined(DESTINY3D_EXPORT_ALL)
#	define DEOCTREE_API DEDLL_EXPORT
#elif defined(DESTINY3D_STATIC_LINK)
#	define DEOCTREE_API
#else
#	define DEOCTREE_API DEDLL_IMPORT
#endif

class IdeVertexBuffer;

class deSceneOctree
{
protected:
	virtual ~deSceneOctree();

public:
	deSceneOctree();
	int Release();

	void TEST();

	void SetMinOctSize(deDouble MinSize);
	deDouble GetMinOctSize();
	void SetMaxNodeNum(int MaxNum);
	int GetMaxNodeNum();

	IdeVertexBuffer * GetVB(int MaxPoints);
	
	deBoolean WipeTree();

	deBoolean AddNode(IdeSceneRoom * Node);
	deBoolean RemoveNode(IdeSceneRoom * Node);

	IdeSceneRoom * FindContainerNode(const deVec3d &Position);
	IdeSceneRoom * FindClosestNode(const deVec3d &Position);
	deBoolean FindIntersectingNodes(deTList <IdeSceneRoom*> &List, const deVec3d * Mins, const deVec3d * Maxs);

	deBoolean TraceRayCollision(const deVec3d & Start, const deVec3d & End, IdeCollision::deCollideInfo & Collision);

	void CleanUp();
	
private:
	enum Neighbor_t
	{
		n_None = -1,
		n_Left = 0,
		n_Right,
		n_Bottom,
		n_Top,
		n_Front,
		n_Back,
	};
	struct Octant
	{
		Octant* Parent;
		int ParentIndex;
		int NeighborRefs;
		Octant* Child[8];
		Octant* Neighbor[6];
		deTList <IdeSceneRoom*> FixedNodes;
		deTList <IdeSceneRoom*> AddedNodes;
		deVec3d Min, Max, Center;
		deBoolean CanBeRemoved;
		int TestNumber;
	};
	// root for the octant tree
	Octant * m_Root;
	// minimum dimension for an octant
	deDouble m_MinSize;
	// maximum number of objects to have in an octant. MinSize overrides this
	int m_MaxNodes;

	int m_TestNumber;

	IdeVertexBuffer * m_LineListVB;

	deBoolean FillOctantLinePoints(Octant * oct, deVertex * Buffer, int & LastPoint, int MaxPoints);

	void CleanUp(Octant * oct);
	deBoolean SubdivideOctant(Octant * oct);
	deBoolean Optimize(Octant * oct);
	deBoolean InsertNode(IdeSceneRoom * Node);

	deBoolean CalcNeighbors(Octant * oct);
	Octant* TraceNeighbor(Octant * Start, Octant * Current, Neighbor_t N, int Depth);

	deBoolean RayTestFromOctant(Octant * oct, const deVec3d & Start, const deVec3d & End, IdeCollision::deCollideInfo & Collision);
	deBoolean RayTestNodes(Octant * oct, const deVec3d & Start, const deVec3d & End, IdeCollision::deCollideInfo * Collision);
	deBoolean RayTestParents(Octant * oct, const deVec3d & Start, const deVec3d & Dir, IdeCollision::deCollideInfo * Collision);
	Neighbor_t RayToNeighbor(Octant * oct, const deVec3d & RayStart, const deVec3d & RayDir, deVec3d & ExitPoint);
	int DecideChildOctant(Octant * Parent, const deVec3d & Position);
	int DecideParentOctant(Octant * Child, const deVec3d & Position);
	
	deBoolean InitializeRoot();
	Octant * MakeOctant(const deVec3d &Min, const deVec3d &Max, Octant * ParentChild, int ParentID);
	Octant * MakeSubOctant(Octant * ParentChild, int ParentID);

	deBoolean RemoveOctant(Octant * oct, deTList <IdeSceneRoom*> * DumpList, deBoolean RemoveChildren, deBoolean IgnoreNeighbors = deFALSE);

	Octant * FindOctant(const deVec3d &Position);
	Octant * FindSubOctant(Octant * oct, const deVec3d &Position);
	Octant * FindOctant(const deVec3d &Min, const deVec3d &Max);
	Octant * FindSubOctant(Octant * oct, const deVec3d &Min, const deVec3d &Max);

	deBoolean TestOctantPoint(Octant * oct, const deVec3d &Position);
	deBoolean TestOctantBBox(Octant * oct, const deVec3d &Min, const deVec3d &Max);
};

#endif