octree.cpp

3D游戏场景的演示原码

		// Check if the current depth value is greater than the max depth stored.
		if(currentDepth > maxDepth)		maxDepth  = currentDepth;
	}

	// Set the member variable dimensions to the max ones found.
	// We multiply the max dimensions by 2 because this will give us the
	// full width, height and depth.  Otherwise, we just have half the size
	// because we are calculating from the center of the scene.
	maxWidth *= 2;		maxHeight *= 2;		maxDepth *= 2;

	// Check if the width is the highest value and assign that for the cube dimension
	if(maxWidth > maxHeight && maxWidth > maxDepth)
		m_Width = maxWidth;

	// Check if the height is the heighest value and assign that for the cube dimension
	else if(maxHeight > maxWidth && maxHeight > maxDepth)
		m_Width = maxHeight;

	// Else it must be the depth or it's the same value as some of the other ones
	else
		m_Width = maxDepth;
}


///////////////////////////////// GET NEW NODE CENTER \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
/////
/////	This returns the center point of the new subdivided node, depending on the ID
/////
///////////////////////////////// GET NEW NODE CENTER \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*

CVector3 COctree::GetNewNodeCenter(CVector3 vCenter, float width, int nodeID)
{
	// I created this function which takes an enum ID to see which node's center
	// we need to calculate.  Once we find that we need to subdivide a node we find
	// the centers of each of the 8 new nodes.  This is what that function does.
	// We just tell it which node we want.

	// Initialize the new node center
	CVector3 vNodeCenter(0, 0, 0);

	// Create a dummy variable to cut down the code size
	CVector3 vCtr = vCenter;

	// Switch on the ID to see which subdivided node we are finding the center
	switch(nodeID)							
	{
		case TOP_LEFT_FRONT:
			// Calculate the center of this new node
			vNodeCenter = CVector3(vCtr.x - width/4, vCtr.y + width/4, vCtr.z + width/4);
			break;

		case TOP_LEFT_BACK:
			// Calculate the center of this new node
			vNodeCenter = CVector3(vCtr.x - width/4, vCtr.y + width/4, vCtr.z - width/4);
			break;

		case TOP_RIGHT_BACK:
			// Calculate the center of this new node
			vNodeCenter = CVector3(vCtr.x + width/4, vCtr.y + width/4, vCtr.z - width/4);
			break;

		case TOP_RIGHT_FRONT:
			// Calculate the center of this new node
			vNodeCenter = CVector3(vCtr.x + width/4, vCtr.y + width/4, vCtr.z + width/4);
			break;

		case BOTTOM_LEFT_FRONT:
			// Calculate the center of this new node
			vNodeCenter = CVector3(vCtr.x - width/4, vCtr.y - width/4, vCtr.z + width/4);
			break;

		case BOTTOM_LEFT_BACK:
			// Calculate the center of this new node
			vNodeCenter = CVector3(vCtr.x - width/4, vCtr.y - width/4, vCtr.z - width/4);
			break;

		case BOTTOM_RIGHT_BACK:
			// Calculate the center of this new node
			vNodeCenter = CVector3(vCtr.x + width/4, vCtr.y - width/4, vCtr.z - width/4);
			break;

		case BOTTOM_RIGHT_FRONT:
			// Calculate the center of this new node
			vNodeCenter = CVector3(vCtr.x + width/4, vCtr.y - width/4, vCtr.z + width/4);
			break;
	}

	// Return the new node center
	return vNodeCenter;
}


///////////////////////////////// CREATE NEW NODE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
/////
/////	This figures out the new node information and then passes it into CreateNode()
/////
///////////////////////////////// CREATE NEW NODE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*

void COctree::CreateNewNode(CVector3 *pVertices, vector<bool> pList, int numberOfVerts,
					  	    CVector3 vCenter,	 float width,        int triangleCount, int nodeID)
{
	// This function helps us set up the new node that is being created.  We only
	// want to create a new node if it found triangles in it's area.  If there were
	// no triangle found in this node's cube, then we ignore it and don't create a node.

	// Check if the first node found some triangles in it
	if(triangleCount)		
	{
		// Allocate memory for the triangles found in this node (tri's * 3 for vertices)
		CVector3 *pNodeVertices = new CVector3 [triangleCount * 3];

		// Create an counter to count the current index of the new node vertices
		int index = 0;

		// Go through all the vertices and assign the vertices to the node's list
		for(int i = 0; i < numberOfVerts; i++)
		{
			// If this current triangle is in the node, assign it's vertices to it
			if(pList[i / 3])	
			{
				pNodeVertices[index] = pVertices[i];
				index++;
			}
		}

		// Now comes the initialization of the node.  First we allocate memory for
		// our node and then get it's center point.  Depending on the nodeID, 
		// GetNewNodeCenter() knows which center point to pass back (TOP_LEFT_FRONT, etc..)

		// Allocate a new node for this octree
		m_pOctreeNodes[nodeID] = new COctree;

		// Get the new node's center point depending on the nodexIndex (which of the 8 subdivided cubes).
		CVector3 vNodeCenter = GetNewNodeCenter(vCenter, width, nodeID);
		
		// Below, before and after we recurse further down into the tree, we keep track
		// of the level of subdivision that we are in.  This way we can restrict it.

		// Increase the current level of subdivision
		g_CurrentSubdivision++;

		// Recurse through this node and subdivide it if necessary
		m_pOctreeNodes[nodeID]->CreateNode(pNodeVertices, triangleCount * 3, vNodeCenter, width / 2);

		// Decrease the current level of subdivision
		g_CurrentSubdivision--;

		// Free the allocated vertices for the triangles found in this node
		delete [] pNodeVertices;
	}
}


///////////////////////////////// CREATE NODE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
/////
/////	This is our recursive function that goes through and subdivides our nodes
/////
///////////////////////////////// CREATE NODE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*

void COctree::CreateNode(CVector3 *pVertices, int numberOfVerts, CVector3 vCenter, float width)
{
	// This is our main function that creates the octree.  We will recurse through
	// this function until we finish subdividing.  Either this will be because we
	// subdivided too many levels or we divided all of the triangles up.

	// Create a variable to hold the number of triangles
	int numberOfTriangles = numberOfVerts / 3;

	// Initialize this node's center point.  Now we know the center of this node.
	m_vCenter = vCenter;

	// Initialize this nodes cube width.  Now we know the width of this current node.
	m_Width = width;

	// Add the current node to our debug rectangle list so we can visualize it.
	// We can now see this node visually as a cube when we render the rectangles.
	// Since it's a cube we pass in the width for width, height and depth.
	g_Debug.AddDebugRectangle(vCenter, width, width, width);

	// Check if we have too many triangles in this node and we haven't subdivided
	// above our max subdivisions.  If so, then we need to break this node into
	// 8 more nodes (hence the word OCTree).  Both must be true to divide this node.
	if( (numberOfTriangles > g_MaxTriangles) && (g_CurrentSubdivision < g_MaxSubdivisions) )
	{
		// Since we need to subdivide more we set the divided flag to true.
		// This let's us know that this node does NOT have any vertices assigned to it,
		// but nodes that perhaps have vertices stored in them (Or their nodes, etc....)
		// We will querey this variable when we are drawing the octree.
		m_bSubDivided = true;

		// Create a list for each new node to store if a triangle should be stored in it's
		// triangle list.  For each index it will be a true or false to tell us if that triangle
		// is in the cube of that node.  Below we check every point to see where it's
		// position is from the center (I.E. if it's above the center, to the left and 
		// back it's the TOP_LEFT_BACK node).  Depending on the node we set the pList 
		// index to true.  This will tell us later which triangles go to which node.
		// You might catch that this way will produce doubles in some nodes.  Some
		// triangles will intersect more than 1 node right?  We won't split the triangles
		// in this tutorial just to keep it simple, but the next tutorial we will.

		// Create the list of booleans for each triangle index
		vector<bool> pList1(numberOfTriangles);		// TOP_LEFT_FRONT node list
		vector<bool> pList2(numberOfTriangles);		// TOP_LEFT_BACK node list
		vector<bool> pList3(numberOfTriangles);		// TOP_RIGHT_BACK node list
		vector<bool> pList4(numberOfTriangles);		// TOP_RIGHT_FRONT node list
		vector<bool> pList5(numberOfTriangles);		// BOTTOM_LEFT_FRONT node list
		vector<bool> pList6(numberOfTriangles);		// BOTTOM_LEFT_BACK node list
		vector<bool> pList7(numberOfTriangles);		// BOTTOM_RIGHT_BACK node list
		vector<bool> pList8(numberOfTriangles);		// BOTTOM_RIGHT_FRONT node list
	
		// Create this variable to cut down the thickness of the code below (easier to read)
		CVector3 vCtr = vCenter;

		// Go through all of the vertices and check which node they belong too.  The way
		// we do this is use the center of our current node and check where the point
		// lies in relationship to the center.  For instance, if the point is 
		// above, left and back from the center point it's the TOP_LEFT_BACK node.
		// You'll see we divide by 3 because there are 3 points in a triangle.
		// If the vertex index 0 and 1 are in a node, 0 / 3 and 1 / 3 is 0 so it will
		// just set the 0'th index to TRUE twice, which doesn't hurt anything.  When
		// we get to the 3rd vertex index of pVertices[] it will then be checking the
		// 1st index of the pList*[] array.  We do this because we want a list of the
		// triangles in the node, not the vertices.
		for(int i = 0; i < numberOfVerts; i++)
		{
			// Create some variables to cut down the thickness of the code (easier to read)
			CVector3 vPoint = pVertices[i];

			// Check if the point lines within the TOP LEFT FRONT node
			if( (vPoint.x <= vCtr.x) && (vPoint.y >= vCtr.y) && (vPoint.z >= vCtr.z) ) 
				pList1[i / 3] = true;

			// Check if the point lines within the TOP LEFT BACK node
			if( (vPoint.x <= vCtr.x) && (vPoint.y >= vCtr.y) && (vPoint.z <= vCtr.z) ) 
				pList2[i / 3] = true;

			// Check if the point lines within the TOP RIGHT BACK node
			if( (vPoint.x >= vCtr.x) && (vPoint.y >= vCtr.y) && (vPoint.z <= vCtr.z) ) 
				pList3[i / 3] = true;

			// Check if the point lines within the TOP RIGHT FRONT node
			if( (vPoint.x >= vCtr.x) && (vPoint.y >= vCtr.y) && (vPoint.z >= vCtr.z) ) 
				pList4[i / 3] = true;

			// Check if the point lines within the BOTTOM LEFT FRONT node
			if( (vPoint.x <= vCtr.x) && (vPoint.y <= vCtr.y) && (vPoint.z >= vCtr.z) ) 
				pList5[i / 3] = true;

			// Check if the point lines within the BOTTOM LEFT BACK node
			if( (vPoint.x <= vCtr.x) && (vPoint.y <= vCtr.y) && (vPoint.z <= vCtr.z) ) 
				pList6[i / 3] = true;

			// Check if the point lines within the BOTTOM RIGHT BACK node
			if( (vPoint.x >= vCtr.x) && (vPoint.y <= vCtr.y) && (vPoint.z <= vCtr.z) ) 
				pList7[i / 3] = true;

			// Check if the point lines within the BOTTOM RIGHT FRONT node
			if( (vPoint.x >= vCtr.x) && (vPoint.y <= vCtr.y) && (vPoint.z >= vCtr.z) ) 
				pList8[i / 3] = true;
		}	

		// Here we create a variable for each list that holds how many triangles
		// were found for each of the 8 subdivided nodes.
		int triCount1 = 0;	int triCount2 = 0;	int triCount3 = 0;	int triCount4 = 0;
		int triCount5 = 0;	int triCount6 = 0;	int triCount7 = 0;	int triCount8 = 0;
		
		// Go through each of the lists and increase the triangle count for each node.
		for(i = 0; i < numberOfTriangles; i++)  
		{
			// Increase the triangle count for each node that has a "true" for the index i.
			if(pList1[i])	triCount1++;	if(pList2[i])	triCount2++;
			if(pList3[i])	triCount3++;	if(pList4[i])	triCount4++;
			if(pList5[i])	triCount5++;	if(pList6[i])	triCount6++;
			if(pList7[i])	triCount7++;	if(pList8[i])	triCount8++;
		}
	
		// Next we do the dirty work.  We need to set up the new nodes with the triangles
		// that are assigned to each node, along with the new center point of the node.
		// Through recursion we subdivide this node into 8 more nodes.

		// Create the subdivided nodes if necessary and then recurse through them.
		// The information passed into CreateNewNode() are essential for creating the
		// new nodes.  We pass the 8 ID's in so it knows how to calculate it's new center.
		CreateNewNode(pVertices, pList1, numberOfVerts, vCenter, width, triCount1, TOP_LEFT_FRONT);
		CreateNewNode(pVertices, pList2, numberOfVerts, vCenter, width, triCount2, TOP_LEFT_BACK);
		CreateNewNode(pVertices, pList3, numberOfVerts, vCenter, width, triCount3, TOP_RIGHT_BACK);
		CreateNewNode(pVertices, pList4, numberOfVerts, vCenter, width, triCount4, TOP_RIGHT_FRONT);