quadtree.h

3D赛车游戏源代码-用Visual Studio 2005

//////////////////////////////////////////////////////////////////////////
//  CQuadTree类，四叉树类，碰撞和可视性检测用。
//
//  QuadTree.h: CQuadTree类的声明
//
//  Copy Rights Wonderful 2006
//////////////////////////////////////////////////////////////////////////

#ifndef __QUADTREE_H_INCLUDED__
#define __QUADTREE_H_INCLUDED__

#include "OGLutil.h"

//-------------------------------------------------------------------------------
// 前向声明
//-------------------------------------------------------------------------------
class Vector3;
class CMatrix44F;
class TriMesh;

//-------------------------------------------------------------------------------
// 这些从0 - 3的值保存了四叉树节点数组的ID
//-------------------------------------------------------------------------------
enum EOctreeNodes
{
	LEFT_FRONT,			// 左前
	LEFT_BACK,			// 左后
	RIGHT_BACK,			// 右后
	RIGHT_FRONT,		// 右前
};

//-------------------------------------------------------------------------------
// 四叉树节点类
//-------------------------------------------------------------------------------
struct TQuadTreeNode
{
	float			fMinX, fMaxX;		// 本节点的X范围
	float			fMinY, fMaxY;		// 本节点的Y范围
	bool			bSubDivided;		// 是否分割？
	int				iTriCount;			// 三角形数量
	RenderTri		*pTris;				// 三角形数据
	TQuadTreeNode	*pChildren[4];		// 子节点

	float GetXCenter() { return (fMinX + fMaxX) * 0.5f; }
	float GetYCenter() { return (fMinY + fMaxY) * 0.5f; }
};

//-------------------------------------------------------------------------------
// 四叉树类
//-------------------------------------------------------------------------------
class CQuadTree
{
public:
	// 构造析构函数
	CQuadTree();
	~CQuadTree();

	// 创建四叉树
	bool CreateQuadTree(TriMesh *pMesh, TextureReference *pTex, float fWidth, float fHeight);

	// 绘制四叉树
	void DrawQuadTree();

	// 初始化数据成员
	void InitQuadTree();

	// 释放四叉树的内存并重置变量
	void DestroyQuadTree();

	// 设置最大分割层次
	void SetMaxSubdivisions(int iMaxSub) { m_iMaxSubdivisions = iMaxSub; }
	int GetMaxSubdivisions() const { return m_iMaxSubdivisions; }

	// 设置一个节点的最大三角形数量
	void SetMaxTriangles(int iCount) { m_iMaxTriangles = iCount; }
	int GetMaxTriangles() const { return m_iMaxTriangles; }

	// 获取一个顶点的x, y所在的多边形，没有则返回NULL
	RenderTri *FindTri(const Vector3 &pos);

protected:
	// 初始化一个节点的数据
	void InitNode(TQuadTreeNode *pNode);
	// 释放一个节点的数据
	void DestroyNode(TQuadTreeNode *pNode);

	// 根据节点宽度和三角形来分割一个节点
	void CreateNode(TQuadTreeNode *pNode, RenderTri *pTris, int iTriCount, Vector3 vCenter, Vector3 vSize);
	// 新分割节点的创建操作
	void CreateNewNode(TQuadTreeNode *pNode, RenderTri *pTris, vector<bool> pList, int iTriCount, 
						Vector3 vCenter, Vector3 vSize, int iNodeTriCount, EOctreeNodes eNodeID);
	// 根据先前节点的中心、尺寸和分割的是哪个节点的ID来返回新节点的中心
	Vector3 GetNewNodeCenter(Vector3 vCenter, Vector3 vSize, EOctreeNodes eNodeID);
	// 一旦我们完成分割，我们需要把三角形都赋给叶子节点
	void AssignVerticesToNode(TQuadTreeNode *pNode, RenderTri *pTris, int iTrisCount);
	// 这个遍历每个节点并画出叶子节点的顶点，这个函数要从根结点开始调用
	void DrawNode(TQuadTreeNode *pNode);
	// 获取一个顶点的x, y所在的多边形，没有则返回NULL
	RenderTri *FindTri(TQuadTreeNode *pNode, const Vector3 &pos);

protected:
	int					m_iMaxSubdivisions;		// 分割的最大层次
	int					m_iMaxTriangles;		// 一个节点最大的三角形数量
	int					m_iEndNodeCount;		// 四叉树建立的叶子节点数量
	int					m_iCurrentSubdivision;	// 当前分割层次
	int					m_iDrawNodeNum;			// 绘制节点数，调试用
	TriMesh				*m_pMesh;				// 四叉树分割的网孔
	TextureReference	*m_pMeshTex;			// 四叉树分割的网孔纹理
	float				m_fWidth;				// 宽
	float				m_fHeight;				// 高
	TQuadTreeNode		*m_pRoot;				// 四叉树的根结点
};

#endif