quadtree.cpp

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

#include "StdAfx.h"
#include "QuadTree.h"
#include "../model/TriMesh.h"
#include "AABB3.h"
#include "Frustum.h"

//-------------------------------------------------------------------------------
// 求三角形面积
//-------------------------------------------------------------------------------
inline float TriangleArea(const Vector3 &p1, const Vector3 &p2, const Vector3 &p3)
{   
	return fabs((p1.x-p3.x)*(p2.y-p3.y) - (p2.x-p3.x)*(p1.y-p3.y)); 
}  

//-------------------------------------------------------------------------------
// 一个点是否在一个三角形中（2D判断x和y）
//-------------------------------------------------------------------------------
bool PointInsideTri(const RenderVertex &v1, const RenderVertex &v2, 
					const RenderVertex &v3, const Vector3 &p)
{   
	return  (fabs(TriangleArea(v1.p,v2.p,v3.p) - TriangleArea(p,v2.p,v3.p) 
				- TriangleArea(v1.p,p,v3.p) 
				- TriangleArea(v1.p,v2.p,p)) < 1.0e-20);
		   
}  

//-------------------------------------------------------------------------------
// 构造函数
//-------------------------------------------------------------------------------
CQuadTree::CQuadTree()
{
	InitQuadTree();
}

//-------------------------------------------------------------------------------
// 析构函数
//-------------------------------------------------------------------------------
CQuadTree::~CQuadTree()
{
	DestroyQuadTree();
}

//-------------------------------------------------------------------------------
// 创建四叉树
//-------------------------------------------------------------------------------
bool CQuadTree::CreateQuadTree(TriMesh *pMesh, TextureReference *pTex, float fWidth, float fHeight)
{
	if (pMesh == NULL)
	{
		return false;
	}

	m_pMesh = pMesh;
	m_pMeshTex = pTex;
	m_fWidth = fWidth;
	m_fHeight = fHeight;

	m_pRoot = new TQuadTreeNode;
	InitNode(m_pRoot);
	CreateNode(m_pRoot, m_pMesh->GetTriList(), m_pMesh->GetTriCount(), kZeroVector, Vector3(m_fWidth, m_fHeight, 0.f));
	return true;
}

//-------------------------------------------------------------------------------
// 绘制四叉树
//-------------------------------------------------------------------------------
void CQuadTree::DrawQuadTree()
{
	if (m_pRoot)
	{
		m_iDrawNodeNum = 0;
		g_Renderer.SelectTexture(*m_pMeshTex);
		DrawNode(m_pRoot);
	}
}

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

RenderTri *CQuadTree::FindTri(TQuadTreeNode *pNode, const Vector3 &pos)
{
	if (pNode == NULL)
	{
		return NULL;
	}

	Vector3 vMin(pNode->fMinX, pNode->fMinY, -2.f);
	Vector3 vMax(pNode->fMaxX, pNode->fMaxY, 4.f);

	AABB3 oNodeBox;
	oNodeBox.min = vMin;
	oNodeBox.max = vMax;

	if (!oNodeBox.Contains(pos))
	{
		return NULL;
	}

	Vector3 vCtr;
	vCtr.x = pNode->GetXCenter();
	vCtr.y = pNode->GetYCenter();

	// 如果本节点分割了的话，就从它的子节点找
	if (pNode->bSubDivided)
	{
		// 检测顶点是否在LEFT FRONT节点
		if ((pos.x <= vCtr.x) && (pos.y <= vCtr.y)) 
		{
			return FindTri(pNode->pChildren[LEFT_FRONT], pos);
		}
		// 检测顶点是否在LEFT BACK节点
		else if ((pos.x <= vCtr.x) && (pos.y >= vCtr.y)) 
		{
			return FindTri(pNode->pChildren[LEFT_BACK], pos);
		}
		// 检测顶点是否在RIGHT BACK节点
		else if ((pos.x >= vCtr.x) && (pos.y >= vCtr.y)) 
		{
			return FindTri(pNode->pChildren[RIGHT_BACK], pos);
		}
		// 检测顶点是否在RIGHT FRONT节点
		else
		{
			return FindTri(pNode->pChildren[RIGHT_FRONT], pos);
		}
	}
	else
	{
		// 取出网孔顶点数组
		RenderVertex *pVers = m_pMesh->GetVertexList();

		// 对于本节点的每个多边形
		for (int i=0; i<pNode->iTriCount; ++i)
		{
			// 取出三角形的三个顶点
			const RenderVertex& v1 = pVers[pNode->pTris[i].index[0]];
			const RenderVertex& v2 = pVers[pNode->pTris[i].index[1]];
			const RenderVertex& v3 = pVers[pNode->pTris[i].index[2]];

			float fMinX = v1.p.x;
			float fMaxX = v1.p.x;
			float fMinY = v1.p.y;
			float fMaxY = v1.p.y;

			if (v2.p.x < fMinX)
			{
				fMinX = v2.p.x;
			}
			else if (v2.p.x > fMaxX)
			{
				fMaxX = v2.p.x;
			}

			if (v2.p.y < fMinY)
			{
				fMinY = v2.p.y;
			}
			else if (v2.p.y > fMaxY)
			{
				fMaxY = v2.p.y;
			}

			if (v3.p.x < fMinX)
			{
				fMinX = v3.p.x;
			}
			else if (v3.p.x > fMaxX)
			{
				fMaxX = v3.p.x;
			}

			if (v3.p.y < fMinY)
			{
				fMinY = v3.p.y;
			}
			else if (v3.p.y > fMaxY)
			{
				fMaxY = v3.p.y;
			}

			// 如果在这个多边形上则返回本多边形指针
			if (pos.x >= fMinX && pos.x <= fMaxX
				&& pos.y >= fMinY && pos.y <= fMaxY)
			{
				return &(pNode->pTris[i]);
			}
		}

		return NULL;
	}
}

//-------------------------------------------------------------------------------
// 初始化数据成员
//-------------------------------------------------------------------------------
void CQuadTree::InitQuadTree()
{
	m_iMaxSubdivisions = 5;		// 分割的最大层次
	m_iMaxTriangles = 80;		// 一个节点最大的三角形数量
	m_iEndNodeCount = 0;		// 四叉树建立的叶子节点数量
	m_iCurrentSubdivision = 0;	// 当前分割层次
	m_pMesh = NULL;				// 四叉树分割的网孔
	m_pMeshTex = NULL;			// 四叉树分割的网孔纹理
	m_pRoot = NULL;				// 四叉树的根结点
}

//-------------------------------------------------------------------------------
// 释放四叉树的内存并重置变量
//-------------------------------------------------------------------------------
void CQuadTree::DestroyQuadTree()
{
	if (m_pRoot)
	{
		DestroyNode(m_pRoot);
	}

	delete m_pRoot;

	m_pMesh = NULL;			// 四叉树分割的网孔
	m_pMeshTex = NULL;		// 四叉树分割的网孔纹理
	m_pRoot = NULL;			// 四叉树的根结点
}

//-------------------------------------------------------------------------------
// 初始化一个节点的数据
//-------------------------------------------------------------------------------
void CQuadTree::InitNode(TQuadTreeNode *pNode)
{
	// 设置外围矩形为空
	pNode->fMinX = 0.f;
	pNode->fMaxX = 0.f;
	pNode->fMinY = 0.f;
	pNode->fMaxY = 0.f;

	// 设置分割标记为false
	pNode->bSubDivided = false;
	// 初始化三角形数量
	pNode->iTriCount = 0;
	// 设置三角形列表为空
	pNode->pTris = NULL;

	// 设置子节点为空
	memset(pNode->pChildren, 0, sizeof(pNode->pChildren));	
}

//-------------------------------------------------------------------------------
// 释放一个节点的数据
//-------------------------------------------------------------------------------
void CQuadTree::DestroyNode(TQuadTreeNode *pNode)
{
	// 释放三角形数据
	if (pNode->pTris)
	{
		delete [] pNode->pTris;	
		pNode->pTris = NULL;
	}

	// 对所有子节点并释放它们的内存
	for (int i = 0; i < 4; ++i)
	{
		// 如果该子节点有效
		if (pNode->pChildren[i])
		{
			DestroyNode(pNode->pChildren[i]);
			delete pNode->pChildren[i];
			pNode->pChildren[i] = NULL;
		}
	}

}

//-------------------------------------------------------------------------------
// 根据节点宽度和三角形来分割一个节点
//-------------------------------------------------------------------------------