octree.cpp

3D游戏场景的演示原码

		CreateNewNode(pVertices, pList5, numberOfVerts, vCenter, width, triCount5, BOTTOM_LEFT_FRONT);
		CreateNewNode(pVertices, pList6, numberOfVerts, vCenter, width, triCount6, BOTTOM_LEFT_BACK);
		CreateNewNode(pVertices, pList7, numberOfVerts, vCenter, width, triCount7, BOTTOM_RIGHT_BACK);
		CreateNewNode(pVertices, pList8, numberOfVerts, vCenter, width, triCount8, BOTTOM_RIGHT_FRONT);
	}
	else
	{
		// If we get here we must either be subdivided past our max level, or our triangle
		// count went below the minimum amount of triangles so we need to store them.
		
		// Assign the vertices to this node since we reached the end node.
		// This will be the end node that actually gets called to be drawn.
		// We just pass in the vertices and vertex count to be assigned to this node.
		AssignVerticesToNode(pVertices, numberOfVerts);
	}
}


//////////////////////////// ASSIGN VERTICES TO NODE \\\\\\\\\\\\\\\\\\\\\\\\\\\*
/////
/////	This allocates memory for the vertices to assign to the current end node
/////
//////////////////////////// ASSIGN VERTICES TO NODE \\\\\\\\\\\\\\\\\\\\\\\\\\\*

void COctree::AssignVerticesToNode(CVector3 *pVertices, int numberOfVerts)
{
	// Since we did not subdivide this node we want to set our flag to false
	m_bSubDivided = false;

	// Initialize the triangle count of this end node (total verts / 3 = total triangles)
	m_TriangleCount = numberOfVerts / 3;

	// Allocate enough memory to hold the needed vertices for the triangles
	m_pVertices = new CVector3 [numberOfVerts];

	// Initialize the vertices to 0 before we copy the data over to them
	memset(m_pVertices, 0, sizeof(CVector3) * numberOfVerts);

	// Copy the passed in vertex data over to our node vertice data
	memcpy(m_pVertices, pVertices, sizeof(CVector3) * numberOfVerts);

	// Increase the amount of end nodes created (Nodes with vertices stored)
	g_EndNodeCount++;
}

// *Note* The code below was thrown in to calculate the normals of the triangles
// that we are displaying.  Instead of complicating the tutorial with separating
// the normals too, I decided to just calculate face normals on the fly so we can
// the depth of the terrain better when we have lighting turned on. 


/////////////////////////////////////// CROSS \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
/////
/////	This returns a perpendicular vector from 2 given vectors by taking the cross product.
/////
/////////////////////////////////////// CROSS \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
												
CVector3 Cross(CVector3 vVector1, CVector3 vVector2)
{
	CVector3 vNormal;	

	// Calculate the cross product with the non communitive equation
	vNormal.x = ((vVector1.y * vVector2.z) - (vVector1.z * vVector2.y));
	vNormal.y = ((vVector1.z * vVector2.x) - (vVector1.x * vVector2.z));
	vNormal.z = ((vVector1.x * vVector2.y) - (vVector1.y * vVector2.x));

	// Return the cross product
	return vNormal;										 
}


/////////////////////////////////////// MAGNITUDE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
/////
/////	This returns the magnitude of a vector
/////
/////////////////////////////////////// MAGNITUDE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*

float Magnitude(CVector3 vNormal)
{
	// Here is the equation:  magnitude = sqrt(V.x^2 + V.y^2 + V.z^2) : Where V is the vector
	return (float)sqrt( (vNormal.x * vNormal.x) + 
						(vNormal.y * vNormal.y) + 
						(vNormal.z * vNormal.z) );
}


/////////////////////////////////////// NORMALIZE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
/////
/////	This returns a normalize vector (A vector exactly of length 1)
/////
/////////////////////////////////////// NORMALIZE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*

CVector3 Normalize(CVector3 vVector)
{
	// Get the magnitude of our normal
	float magnitude = Magnitude(vVector);				

	// Now that we have the magnitude, we can divide our vector by that magnitude.
	// That will make our vector a total length of 1.  
	vVector = vVector / magnitude;		
	
	// Finally, return our normalized vector
	return vVector;										
}


//////////////////////////////// DRAW OCTREE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
/////
/////	This function recurses through all the nodes and draws the end node's vertices
/////
//////////////////////////////// DRAW OCTREE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*

void COctree::DrawOctree(COctree *pNode)
{
	// We should already have the octree created before we call this function.
	// This only goes through the nodes that are in our frustum, then renders those
	// vertices stored in their end nodes.  Before we draw a node we check to
	// make sure it is a subdivided node (from m_bSubdivided).  If it is, then
	// we haven't reaches the end and we need to keep recursing through the tree.
	// Once we get to a node that isn't subdivided we draw it's vertices.

	// Make sure a valid node was passed in, otherwise go back to the last node
	if(!pNode) return;


/////// * /////////// * /////////// * NEW * /////// * /////////// * /////////// *

	// Before we do any checks with the current node, let's make sure we even need too.
	// We want to check if this node's cube is even in our frustum first.
	// To do that we pass in our center point of the node and 1/2 it's width to our 
	// CubeInFrustum() function.  This will return "true" if it is inside the frustum 
	// (camera's view), otherwise return false.  
	else if(g_Frustum.CubeInFrustum(pNode->m_vCenter.x, pNode->m_vCenter.y, 
									pNode->m_vCenter.z, pNode->m_Width / 2))

/////// * /////////// * /////////// * NEW * /////// * /////////// * /////////// *


	// Check if this node is subdivided. If so, then we need to recurse and draw it's nodes
	if(pNode->IsSubDivided())
	{
		// Recurse to the bottom of these nodes and draw the end node's vertices
		// Like creating the octree, we need to recurse through each of the 8 nodes.
		DrawOctree(pNode->m_pOctreeNodes[TOP_LEFT_FRONT]);
		DrawOctree(pNode->m_pOctreeNodes[TOP_LEFT_BACK]);
		DrawOctree(pNode->m_pOctreeNodes[TOP_RIGHT_BACK]);
		DrawOctree(pNode->m_pOctreeNodes[TOP_RIGHT_FRONT]);
		DrawOctree(pNode->m_pOctreeNodes[BOTTOM_LEFT_FRONT]);
		DrawOctree(pNode->m_pOctreeNodes[BOTTOM_LEFT_BACK]);
		DrawOctree(pNode->m_pOctreeNodes[BOTTOM_RIGHT_BACK]);
		DrawOctree(pNode->m_pOctreeNodes[BOTTOM_RIGHT_FRONT]);
	}
	else
	{
		// Increase the amount of nodes in our viewing frustum (camera's view)
		g_TotalNodesDrawn++;

		// Make sure we have valid vertices assigned to this node
		if(!pNode->m_pVertices) return;

		// Render the world data with triangles
		glBegin(GL_TRIANGLES);

		// Turn the polygons green
		glColor3ub(0, 255, 0);

		// Store the vertices in a local pointer to keep code more clean
		CVector3 *pVertices = pNode->m_pVertices;

		// Go through all of the vertices (the number of triangles * 3)
		for(int i = 0; i < pNode->GetTriangleCount() * 3; i += 3)
		{
			// Before we render the vertices we want to calculate the face normal
			// of the current polygon.  That way when lighting is turned on we can
			// see the definition of the terrain more clearly.  In reality you wouldn't do this.
			
			// Here we get a vector from each side of the triangle
			CVector3 vVector1 = pVertices[i + 1] - pVertices[i];
			CVector3 vVector2 = pVertices[i + 2] - pVertices[i];

			// Then we need to get the cross product of those 2 vectors (The normal's direction)
			CVector3 vNormal = Cross(vVector1, vVector2);

			// Now we normalize the normal so it is a unit vector (length of 1)
			vNormal = Normalize(vNormal);

			// Pass in the normal for this triangle so we can see better depth in the scene
			glNormal3f(vNormal.x, vNormal.y, vNormal.z);

			// Render the first point in the triangle
			glVertex3f(pVertices[i].x, pVertices[i].y, pVertices[i].z);

			// Render the next point in the triangle
			glVertex3f(pVertices[i + 1].x, pVertices[i + 1].y, pVertices[i + 1].z);

			// Render the last point in the triangle to form the current triangle
			glVertex3f(pVertices[i + 2].x, pVertices[i + 2].y, pVertices[i + 2].z);
		}

		// Quit Drawing
		glEnd();
	}
}


//////////////////////////////// DESTROY OCTREE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
/////
/////	This frees the memory allocated in the octree
/////
//////////////////////////////// DESTROY OCTREE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*

void COctree::DestroyOctree()
{
	// Free the triangle data if it's not NULL
	if( m_pVertices )
	{
		delete[] m_pVertices;	
		m_pVertices = NULL;
	}

	// Go through all of the nodes and free them if they were allocated
	for(int i = 0; i < 8; i++)
	{
		// Make sure this node is valid
		if(m_pOctreeNodes[i])
		{
			// Free this array index.  This will call the deconstructor which will
			// free the octree data correctly.  This allows us to forget about it's clean up
			delete m_pOctreeNodes[i];
			m_pOctreeNodes[i] = NULL;
		}
	}

	// Initialize the octree data members
	InitOctree();
}	


/////////////////////////////////////////////////////////////////////////////////
//
// * QUICK NOTES * 
//
// This tutorial was an add on to the last octree tutorial which just showed us
// how to create an octree.  There wasn't a lot added, but the power that is provides
// is incredible.  We now have a functional octree that only draws the vertices in
// our view.  There are 2 things we added to this tutorial since the last:
// 
// 1) We added the frustum code (frustum.cpp and frustum.h).  This is all explained
// in our frustum tutorial on our site if you don't understand the code.  Once we
// create our global CFrustum object: g_Frustum, we just need to call this every frame:
// 
// g_Frustum.CalculateFrustum();
// 
// We only really need to call it when the camera moves but you can do those checks 
// yourself.  Then, once the frustum planes are calculated we can use this function to
// check if the end nodes are in our frustum:
//
// g_Frustum.CubeInFrustum(center.x, center.y, center.z, cubeWidth / 2);
// 
// That's it for the frustum!  Simple, yet wonderfully usefull.  We left in the sphere
// and point code in frustum.cpp from the frustum tutorial just so if you wanted to
// include the frustum.cpp file in your application/game you didn't have to copy and
// paste them back in.  Just ingore those for this tutorial though.
// 
// 2) Finally we added a counter (g_TotalNodesDrawn) to tell us how many of the end 
// nodes are being drawn.  This let's us know how well the octree is working.  You 
// can view this information in the window's title bar, along with the other subdivision 
// information.
// 
// Also notice that we took our the rotating.  This is so all the cubes stay axis aligned.
//
// Hopefully by breaking the octree tutorial up into multiple parts it isn't so hard
// to digest.  The next tutorial will focus on reading in a real world with texture
// information, normals, etc...  Then you can actually use this code in a project.
// I also included the HTML octree tutorial with this tutorial as well just in case
// some people didn't want to download the first octree tutorial but wanted to get right
// to the good stuff.  This HTML file will explain in more detail the octree theory, etc...
// 
// Good luck!
// 
//
// Ben Humphrey
// Game Programmer
// [e-mail]
// www.GameTutorials.com
//
//