///////////////////////////////////////////////////////////////////////////////
/// @file deObjectTree.hpp
///
/// @brief [Adaptive] Binary Tree for objects
///
/// @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 Mar 2004
/// @author Assassin
/// @remarks Creation
///
///////////////////////////////////////////////////////////////////////////////

#ifndef DE_OBJECTTREE_HPP
#define DE_OBJECTTREE_HPP

#include "deGlobalTypes.hpp"
#include "deHash.hpp"
#include "deList.hpp"

class IdeSceneObject;
class IdeBoundingVolume;

class deObjectTree
{
public:
	deObjectTree();
	~deObjectTree();

	deBoolean AddObject(IdeSceneObject* object);
	void RemoveObject(IdeSceneObject* object);
	deBoolean RepositionObject(IdeSceneObject* object);

	void IntersectionTest(IdeBoundingVolume* BV, deTList<IdeSceneObject*>& outList);


private:
	/// a split in an ABT node, along an axis (0,1,2)=(x,y,z) at a certain percentage
	struct ABTSplit
	{
		long		Axis;
		deDouble	Percent;
	};
	/// a partition within the ABT.
	/// can have both child partitions and objects stored inside.
	/// non-leaf nodes can have faces if in limbo while compiling.
	struct ABTPartition
	{
		deAABB BBox;
		ABTSplit Split;
		ABTPartition* Parent;
		ABTPartition* Children[2]; // 0 = minside, 1 = maxside
		deTList<IdeSceneObject*> Objects;
	};
	/// information about a split - most important being the score.
	/// used only while partitioning a box, to score the various sampled splits
	struct ABTSplitStat
	{
		ABTSplit Split;
		dePlane Plane;
		long FrontBackDiff;
		long NumOn;
		deFloat	Score;
	};

	typedef deTHashInt<ABTPartition*> ObjectHash_t;
	ABTPartition* m_Root;
	ObjectHash_t m_ObjectHash;
	int mObjectThreshold;
	int mDepthMax;

	ABTPartition* CreatePartition(ABTPartition* parent, int ChildNum, int AxisNum);
	deBoolean SplitPartition(ABTPartition* part, int Depth);
	void DestroyPartition(ABTPartition* part);
	void PrunePartition(ABTPartition* part, long Depth);
	deBoolean InsertObject(ABTPartition* part, IdeSceneObject* object, int Depth);
	deBoolean ExpandRoot(IdeSceneObject* outlier);
	void IntersectionHelper(ABTPartition* part, IdeBoundingVolume* BV, deTList<IdeSceneObject*>& outList);
};

#endif