/** @file QuadTree.h 
@brief 四叉树只用做按照四叉树结构构造包围盒层级树，本身不用做场景管理
<pre>
*	Copyright (c) 2007，第九城市游戏研发中心
*	All rights reserved.
*
*	当前版本：0.70
*	作    者：Shi Yazheng
*	完成日期：2008-01-19
*	描	  述：完成 用四叉树构造包围盒层级树
*			  
*
*	取代版本：0.69	(有bug)
*	作    者：Shi Yazheng
*	完成日期：2008-01-18
*	描	  述：作废 根据视锥创建可视列表功能
*			  增加 根据四叉树构造包围盒层级树功能
*
*	取代版本：0.6 （未测试）
*	作    者：Shi Yazheng
*	完成日期：2008-01-16
*	描	  述：完成 物件集填加 及 根据视锥创建可视列表
*
*	取代版本：0.1
*	作    者：Zhaixufeng
*	完成日期：2007-09-26
</pre>*/
#ifndef	QUADTREE_H 
#define	QUADTREE_H

#ifndef CODE_INGAME

// 每个四叉树节点可拥有的子节点数
#define	QUAD_NUM	4

// 最小节点边长
#define MIN_EDGE_LENGTH	6
class CTerrain;

#include "tinyxml.h"

/// 四叉树节点定义
struct MAIN_ENTRY stQuadNode
{
	/// 父节点
	stQuadNode*		pParent;

	/// 四孩子节点
	stQuadNode*		pChild[QUAD_NUM];	// child node 0-LU 1-RU 2-LB 3-RB

	/// 叶子标志
	bool			bIsLeaf;			// leaf signal

	/// 层次级别
	int				iLevel;				// level index

	int				iLength;			// 节点边长

	/// 包围盒
	NiBoxBV			boundingBox;

	/// 可编辑对象集, 依层级存放于叶子节点,初始保存于根节点
	//vector< CEditableBaseObj* >	objsArray;

	/// 
	vector< NiAVObject* >	niObjsArray;
	vector<int>				iEntityIDArray;

	/// 默认构造
	stQuadNode() : pParent( 0 ), bIsLeaf( false ), iLevel( 0 )
	{
		memset(pChild, 0, sizeof(void*)*QUAD_NUM);
	}

	/**
	*	<BR>功能说明：获取某子节点.
	*	<BR>可访问性：
	*	<BR>注    释：如果该节点已存在，返回该节点。如果不存在则创建后再返回。
	*	@param	iWhich[in]		子节点编号
	*	@return 获取的子节点
	*/
	stQuadNode* GetChild(int iWhich);

	/**
	*	<BR>功能说明：将一个 CEditableBaseObj对象添加到四叉树节点中
	*	<BR>可访问性：
	*	<BR>注    释：将pObj添加到从空间上能完全容纳该pObj，并且iLevel最大的节点中。 
	*	@param	pObj[in]		被添加的CEditableBaseObj对象指针
	*	@return 接受 pObj 加入objArray的四叉树节点
	*/
	//stQuadNode* AttachObject(CEditableBaseObj* pObj);
	stQuadNode*	AttachObject(NiAVObject*	pObj, int iEntityID);

	/// 计算某子节点的包围盒。该子节点可以不存在。
	NiBoxBV	GetChildAABB(int iWhich);

	/// 用当前四叉树节点（及所有子节点）构件场景图 
	NiNodePtr	BuildSceneGraph();

	// 根据视锥对quadTree进行剔除，创建可视列表
	// 函数作废。使用quadTree构建包围盒层级树，交由引擎进行可视剔除
	//void BuilderVisibleSet(NiFrustumPlanes* pFrustum, NiVisibleArray *pVisible);

	// 按照 xml 方式获取节点
	TiXmlElement* GetAsXMLElement();

};

/// 四叉树
class MAIN_ENTRY CQuadTree
{	
public:
	/// 构造
	CQuadTree(  const NiPoint3& kCenter, const NiPoint3& kExtends);

	/// 析构
	~CQuadTree() { this->_Destroy(); }

	/// 将物件添加到四叉树中
	stQuadNode*		AttachObject(NiAVObject*	pObj, int iID);

	/// 用四叉树构造场景图
	NiNodePtr		BuildSceneGraph();

	TiXmlElement*  GetAsXMLElement();

protected:
	/// 销毁所有节点
	void			_Destroy();

	/// 销毁节点及其所有子节点
	void			_DestroyNode( stQuadNode*& pNode );

	/// 根节点
	stQuadNode*		m_pRoot;
};

#endif

#endif