quadtree.cpp

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

void CQuadTree::CreateNode(TQuadTreeNode *pNode, RenderTri *pTris, int iTriCount, Vector3 vCenter, Vector3 vSize)
{
	// 这个是我们创建四叉树的主函数。我们会递归调用这个函数直到我们完成分割。否则
	// 它会根据我们分割的层次或三角形数量不够而停止分割。

	// 初始化这个节点的包围盒。
	float fHalfWidth  = vSize.x * 0.5f;
	float fHalfHeight = vSize.y * 0.5f;

	pNode->fMinX = vCenter.x - fHalfWidth;
	pNode->fMaxX = vCenter.x + fHalfWidth;
	pNode->fMinY = vCenter.y - fHalfHeight;
	pNode->fMaxY = vCenter.y + fHalfHeight;


	// 检测我们是否有太多的三角形在这个节点并且我们没有分割到最大层次，如果是，我们需要
	// 把这个节点分割成8个节点（因此世界是由八叉树组成）。
	if ((iTriCount > m_iMaxTriangles) && (m_iCurrentSubdivision < m_iMaxSubdivisions))
	{
		// 因为我们需要分割，所以设置分割标记为真。这让我们知道这个节点没有顶点，但它有
		// 顶点在它的子节点。我们在绘制八叉树的时候会查询这个变量
		pNode->bSubDivided = true;

		// 给每个要分割的新节点创建一个列表给它，表示是否一个三角形要保存在这个节点当中，
		// 对每个所以都有一个true或false来告诉我们这个三角形是否在节点的立方体包围盒里。
		// 下面我们检测每个顶点来看它离顶点的位置（例如，如果它在中心的上面，靠近左后
		// 则它是属于TOP_LEFT_BACK节点）。根据节点，我们设置它的pList的对应index未true。
		// 这个会等下告诉我们哪个三角形分配到哪个节点。你会注意到可能有三角形横跨几个
		// 节点，本节我们不会分割三角形来保持简单。

		// 每个三角形索引的bool值列表
		vector<bool> pList1(iTriCount);		// LEFT_FRONT节点列表
		vector<bool> pList2(iTriCount);		// LEFT_BACK节点列表
		vector<bool> pList3(iTriCount);		// RIGHT_BACK节点列表
		vector<bool> pList4(iTriCount);		// RIGHT_FRONT节点列表
	

		// 创建一个中心别名
		Vector3 vCtr = vCenter;
		// 取出网孔顶点数组
		RenderVertex *pVers = m_pMesh->GetVertexList();

		// 遍历所以三角形并判断它属于哪个节点
		for (int i = 0; i < iTriCount; ++i)
		{
			// 取出三角形的三个顶点
			const RenderVertex& v1 = pVers[pTris[i].index[0]];
			const RenderVertex& v2 = pVers[pTris[i].index[1]];
			const RenderVertex& v3 = pVers[pTris[i].index[2]];

			// 顶点平均值
			Vector3 vPoint(v1.p);
			vPoint.x = (v1.p.x + v2.p.x + v3.p.x) / 3.f;
			vPoint.y = (v1.p.y + v2.p.y + v3.p.y) / 3.f;

			// 检测顶点是否在LEFT FRONT节点
			if ((vPoint.x <= vCtr.x) && (vPoint.y <= vCtr.y)) 
			{
				pList1[i] = true;
			}

			// 检测顶点是否在LEFT BACK节点
			if ((vPoint.x <= vCtr.x) && (vPoint.y >= vCtr.y)) 
			{
				pList2[i] = true;
			}

			// 检测顶点是否在RIGHT BACK节点
			if ((vPoint.x >= vCtr.x) && (vPoint.y >= vCtr.y)) 
			{
				pList3[i] = true;
			}

			// 检测顶点是否在RIGHT FRONT节点
			if ((vPoint.x >= vCtr.x) && (vPoint.y <= vCtr.y)) 
			{
				pList4[i] = true;
			}
		}	

		// 这里给每个节点建立一个变量记录它的三角形数量
		int triCount1 = 0;	int triCount2 = 0;	int triCount3 = 0;	int triCount4 = 0;

		// 对每个三角形
		for (i = 0; i < iTriCount; ++i)  
		{
			// 如果节点的三角形列表的索引i为真则增加它的三角形数量
			if (pList1[i])	triCount1++;	if (pList2[i])	triCount2++;
			if (pList3[i])	triCount3++;	if (pList4[i])	triCount4++;
		}

		// 下面我们需要安装新节点联合我们赋值给它的三角形，连同节点的新中心，并递归分割

		// 需要的话创建分割节点并递归调用它们，传入CreateNewNode()函数信息是为了创建新节点的基本信息。
		// 我们传入8个ID，让它知道如何计算新节点的中心。
		CreateNewNode(pNode, pTris, pList1, iTriCount, vCenter, vSize, triCount1, LEFT_FRONT);
		CreateNewNode(pNode, pTris, pList2, iTriCount, vCenter, vSize, triCount2, LEFT_BACK);
		CreateNewNode(pNode, pTris, pList3, iTriCount, vCenter, vSize, triCount3, RIGHT_BACK);
		CreateNewNode(pNode, pTris, pList4, iTriCount, vCenter, vSize, triCount4, RIGHT_FRONT);
	}
	else
	{
		// 如果我们到达这里，是因为分割层次达到最大或者，三角形数量小于一个节点的最小值。

		// 把顶点赋值给节点，因为我们到达了叶子节点。这个会是真正要画的叶子节点。
		// 我们只要把顶点数组和数量传入并赋给这个节点就行了。
		AssignVerticesToNode(pNode, pTris, iTriCount);
	}
}

//-------------------------------------------------------------------------------
// 新分割节点的创建操作
//-------------------------------------------------------------------------------
void CQuadTree::CreateNewNode(TQuadTreeNode *pNode, RenderTri *pTris, vector<bool> pList, int iTriCount, 
							  Vector3 vCenter, Vector3 vSize, int iNodeTriCount, EOctreeNodes eNodeID)
{
	// 本函数帮组我们安装新节点，我们只需要创建一个新节点并查找有哪些三角形在这里，如果
	// 没有三角形在新节点的立方体离，我们就忽略并不创建。

	// 首先查找是否有三角形在节点里
	if (iNodeTriCount)		
	{
		// 分配内存来存储在节点的三角形 
		RenderTri *pNodeTris = new RenderTri[iNodeTriCount];

		// 创建一个计数器来统计节点当前顶点的索引
		int index = 0;

		// 遍历所有三角形，并把在本节点里的三角形赋给节点三角形数组
		for (int i = 0; i < iTriCount; ++i)
		{
			// 如果当前三角形在节点中，分配它的顶点给节点
			if (pList[i])	
			{
				pNodeTris[index] = pTris[i];
				++index;
			}
		}

		// 现在是初始化节点的时候了，首先我们分配内存给节点并得到它的中心点，根据节点ID， 
		// GetNewNodeCenter() 知道要传回什么中心点(LEFT_FRONT, etc..)

		// 分配一个新节点
		pNode->pChildren[eNodeID] = new TQuadTreeNode;
		InitNode(pNode->pChildren[eNodeID]);

		// 获取这个新节点的中心点
		Vector3 vNodeCenter = GetNewNodeCenter(vCenter, vSize, eNodeID);

		// 下面在我们递归调用节点分割的时候，记录下我们分割的层次，一边我们可以控制它。

		// 增加当前分割等级
		m_iCurrentSubdivision++;

		vSize.x *= 0.5f;
		vSize.y *= 0.5f;

		// 递归调用这个新节点的分割函数，如果需要则分割
		CreateNode(pNode->pChildren[eNodeID], pNodeTris, iNodeTriCount, vNodeCenter, vSize);

		// 减少当前分割等级
		m_iCurrentSubdivision--;

		// 释放这个节点分配的找到的三角形顶点
		delete [] pNodeTris;
	}
}

//-------------------------------------------------------------------------------
// 根据先前节点的中心、尺寸和分割的是哪个节点的ID来返回新节点的中心
//-------------------------------------------------------------------------------
Vector3 CQuadTree::GetNewNodeCenter(Vector3 vCenter, Vector3 vSize, EOctreeNodes eNodeID)
{
	// 我们用一个枚举ID来看是需要计算哪个节点的中心，一旦我们需要分割一个节点，
	// 我们需要找到它的8个子节点的中心，这个函数就是计算这些中心的。

	// 初始化新节点中心
	Vector3 vNodeCenter(0.f, 0.f, 0.f);

	// 创建一个别名变量
	Vector3 vCtr = vCenter;

	// 根据不同ID来看我们是要找哪个子节点的中心
	switch (eNodeID)							
	{
	case LEFT_FRONT:
		vNodeCenter = Vector3(vCtr.x - vSize.x/4.f, vCtr.y - vSize.y/4.f, vCtr.z);
		break;

	case LEFT_BACK:
		vNodeCenter = Vector3(vCtr.x - vSize.x/4.f, vCtr.y + vSize.y/4.f, vCtr.z);
		break;

	case RIGHT_BACK:
		vNodeCenter = Vector3(vCtr.x + vSize.x/4.f, vCtr.y + vSize.y/4.f, vCtr.z);
		break;

	case RIGHT_FRONT:
		vNodeCenter = Vector3(vCtr.x + vSize.x/4.f, vCtr.y - vSize.y/4.f, vCtr.z);
		break;
	}

	// 返回新节点中心
	return vNodeCenter;
}

//-------------------------------------------------------------------------------
// 一旦我们完成分割，我们需要把三角形都赋给叶子节点
//-------------------------------------------------------------------------------
void CQuadTree::AssignVerticesToNode(TQuadTreeNode *pNode, RenderTri *pTris, int iTrisCount)
{
	// 因为我们不再分割这个节点，所以我们设置分割标记为false
	pNode->bSubDivided = false;

	// 初始化这个节点的三角形数量 (顶点数 / 3 = 三角形数)
	pNode->iTriCount = iTrisCount;

	// 分配足够内存来保存每个三角形的顶点
	pNode->pTris = new RenderTri[iTrisCount];

	// 初始化顶点值为0
	memset(pNode->pTris, 0, sizeof(RenderTri) * iTrisCount);

	// 拷贝传入顶点数组到节点
	memcpy(pNode->pTris, pTris, sizeof(RenderTri) * iTrisCount);

	// 增加叶子节点数量
	++m_iEndNodeCount;
}

//-------------------------------------------------------------------------------
// 这个遍历每个节点并画出叶子节点的顶点，这个函数要从根结点开始调用
//-------------------------------------------------------------------------------
void CQuadTree::DrawNode(TQuadTreeNode *pNode)
{
	// 调用这个函数时要保证四叉树创建好了。这个会遍历所有节点直到叶子节点并
	// 画出它们存储的三角形。在我们画一个节点前，我们检测它是不是一个分割节点，
	// 如果是我们就递归遍历树，否则我们画它。

	// 确认是传入一个有效节点
	if (!pNode) 
		return;

	Vector3 vMin(pNode->fMinX, pNode->fMinY, m_pMesh->GetBoundingBox().min.z);
	Vector3 vMax(pNode->fMaxX, pNode->fMaxY, m_pMesh->GetBoundingBox().max.z);

	AABB3 oNodeBox;
	oNodeBox.min = vMin;
	oNodeBox.max = vMax;
	
	if (!g_Frustum.CubeInFrustum(oNodeBox))
	{
		return ;
	}

	// 如果节点是分割的，我们递归调用
	if (pNode->bSubDivided)
	{
		DrawNode(pNode->pChildren[LEFT_FRONT]);
		DrawNode(pNode->pChildren[LEFT_BACK]);
		DrawNode(pNode->pChildren[RIGHT_BACK]);
		DrawNode(pNode->pChildren[RIGHT_FRONT]);
	}
	else
	{
		// 确认这个节点中有有效顶点
		if (!pNode->pTris) 
			return;

		g_Renderer.RenderTriMesh(m_pMesh->GetVertexList(), m_pMesh->GetVertexCount(), 
			pNode->pTris, pNode->iTriCount);
		
		/*g_Renderer.RenderBox(vMin, vMax);*/
		++m_iDrawNodeNum;
	}
}