octree.cpp

3D游戏场景的演示原码

//***********************************************************************//
//																		 //
//		- "Talk to me like I'm a 3 year old!" Programming Lessons -		 //
//                                                                       //
//		$Author:		DigiBen		[e-mail]			 //
//																		 //
//		$Program:		Octree2	 										 //
//																		 //
//		$Description:	Intergrates frustum culling with an octree		 //
//																		 //
//		$Date:			11/26/01										 //
//																		 //
//***********************************************************************//

// Include our associate .h file
#include "Octree.h"


// This file contains all the code for our debug and octree classes.  Just so
// we could visualize the subdivision of the octree, I created a class that draws
// wire frame cubes and lines.  A new cube is added to our list of points each time a 
// new node is created.  The cubes are yellow.  You will notice that there is only one
// cube surrounding the terrain in the beginning.  If you press '+' 8 more will be
// created.  Of course, when really using an octree you would not have these.  It
// is created just for the tutorial, so don't assume when you have many nodes that it
// will slow down the game.  It's because you have tons of lines being draw to represent
// the subdivision :)  It's good to note that the line list is created with an STL vector.
// Check out our STL vector tutorial at www.GameTutorials.com if you need help on these.
// Don't worry about the debug class if you don't understand any of it, it's not important.

// Extern our debug object because we use it in the octree code
extern CDebug g_Debug;

// Extern our global frustum object so we can check if our nodes are 
// inside the frustum before we draw them.
extern CFrustum g_Frustum;

// The current amount of subdivisions we are currently at.
// This is used to make sure we don't go over the max amount
int g_CurrentSubdivision = 0;

///////////////////////////////// RENDER DEBUG LINES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
/////
/////	This goes through all of the lines that we stored in our list and draws them
/////
///////////////////////////////// RENDER DEBUG LINES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*

void CDebug::RenderDebugLines()				// This renders all of the lines
{
	glDisable(GL_LIGHTING);					// Turn OFF lighting so the debug lines are bright yellow

	glBegin(GL_LINES);						// Start rendering lines

		glColor3ub(255, 255, 0);			// Turn the lines yellow

		// Go through the whole list of lines stored in the vector m_vLines.
		for(unsigned int i = 0; i < m_vLines.size(); i++)
		{
			// Pass in the current point to be rendered as part of a line
			glVertex3f(m_vLines[i].x, m_vLines[i].y, m_vLines[i].z);
		}	

	glEnd();								// Stop rendering lines

	// If we have lighting turned on, turn the lights back on
	if(g_bLighting) 
		glEnable(GL_LIGHTING);
}

///////////////////////////////// ADD DEBUG LINE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
/////
/////	This adds a debug LINE to the stack of lines
/////
///////////////////////////////// ADD DEBUG LINE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*

void CDebug::AddDebugLine(CVector3 vPoint1, CVector3 vPoint2)
{
	// Add the 2 points that make up the line into our line list.
	m_vLines.push_back(vPoint1);
	m_vLines.push_back(vPoint2);
}


///////////////////////////////// ADD DEBUG RECTANGLE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
/////
/////	This adds a debug RECTANGLE to the stack of lines
/////
///////////////////////////////// ADD DEBUG RECTANGLE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*

void CDebug::AddDebugRectangle(CVector3 vCenter, float width, float height, float depth)
{
	// So we can work with the code better, we divide the dimensions in half.
	// That way we can create the cube from the center outwards.
	width /= 2.0f;	height /= 2.0f;	depth /= 2.0f;

	// Below we create all the 8 points so it will be easier to input the lines
	// of the cube.  With the dimensions we calculate the points.
	CVector3 vTopLeftFront( vCenter.x - width, vCenter.y + height, vCenter.z + depth);
	CVector3 vTopLeftBack(  vCenter.x - width, vCenter.y + height, vCenter.z - depth);
	CVector3 vTopRightBack( vCenter.x + width, vCenter.y + height, vCenter.z - depth);
	CVector3 vTopRightFront(vCenter.x + width, vCenter.y + height, vCenter.z + depth);

	CVector3 vBottom_LeftFront( vCenter.x - width, vCenter.y - height, vCenter.z + depth);
	CVector3 vBottom_LeftBack(  vCenter.x - width, vCenter.y - height, vCenter.z - depth);
	CVector3 vBottomRightBack( vCenter.x + width, vCenter.y - height, vCenter.z - depth);
	CVector3 vBottomRightFront(vCenter.x + width, vCenter.y - height, vCenter.z + depth);

	////////// TOP LINES ////////// 

	// Store the top front line of the box
	m_vLines.push_back(vTopLeftFront);		m_vLines.push_back(vTopRightFront);

	// Store the top back line of the box
	m_vLines.push_back(vTopLeftBack);  		m_vLines.push_back(vTopRightBack);

	// Store the top left line of the box
	m_vLines.push_back(vTopLeftFront);		m_vLines.push_back(vTopLeftBack);

	// Store the top right line of the box
	m_vLines.push_back(vTopRightFront);		m_vLines.push_back(vTopRightBack);

	////////// BOTTOM LINES ////////// 

	// Store the bottom front line of the box
	m_vLines.push_back(vBottom_LeftFront);	m_vLines.push_back(vBottomRightFront);

	// Store the bottom back line of the box
	m_vLines.push_back(vBottom_LeftBack);	m_vLines.push_back(vBottomRightBack);

	// Store the bottom left line of the box
	m_vLines.push_back(vBottom_LeftFront);	m_vLines.push_back(vBottom_LeftBack);

	// Store the bottom right line of the box
	m_vLines.push_back(vBottomRightFront);	m_vLines.push_back(vBottomRightBack);

	////////// SIDE LINES ////////// 

	// Store the bottom front line of the box
	m_vLines.push_back(vTopLeftFront);		m_vLines.push_back(vBottom_LeftFront);

	// Store the back left line of the box
	m_vLines.push_back(vTopLeftBack);		m_vLines.push_back(vBottom_LeftBack);

	// Store the front right line of the box
	m_vLines.push_back(vTopRightBack);		m_vLines.push_back(vBottomRightBack);

	// Store the front left line of the box
	m_vLines.push_back(vTopRightFront);		m_vLines.push_back(vBottomRightFront);
}


///////////////////////////////// CLEAR \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
/////
/////	This clears all of the debug lines
/////
///////////////////////////////// CLEAR \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*

void CDebug::Clear()						
{
	// Destroy the list using the standard vector clear() function
	m_vLines.clear();
}


//-------------------------------------------------------------------------\\ 


///////////////////////////////// OCTREE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
/////
/////	The COctree contstructor which calls our init function
/////
///////////////////////////////// OCTREE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*

COctree::COctree()
{
	// We didn't just put the init code in here because it will allow us
	// to destroy the octree and initialize the octree without having to
	// create a new instance.  The same goes for our deconstructor

	// Initialize the data members
	InitOctree();	
}


///////////////////////////////// ~OCTREE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
/////
/////	The COctree destructor which calls our destroy function
/////
///////////////////////////////// ~OCTREE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*

COctree::~COctree()
{
	// Call our destroy function
	DestroyOctree();
}


///////////////////////////////// INIT OCTREE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
/////
/////	This initialize our octree data members
/////
///////////////////////////////// INIT OCTREE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*

void COctree::InitOctree()
{
	// Set the subdivided flag to false
	m_bSubDivided = false;

	// Set the dimensions of the box to false
	m_Width = 0; 

	// Initialize the triangle count
	m_TriangleCount = 0;

	// Initialize the center of the box to the 0
	m_vCenter = CVector3(0, 0, 0);

	// Set the triangle list to NULL
	m_pVertices = NULL;

	// Set the sub nodes to NULL
	memset(m_pOctreeNodes, 0, sizeof(m_pOctreeNodes));	
}


///////////////////////////////// OCTREE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*
/////
/////	This sets our initial width of the scene, as well as our center point
/////
///////////////////////////////// OCTREE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*

void COctree::GetSceneDimensions(CVector3 *pVertices, int numberOfVerts)
{
	// We pass in the list of vertices and the vertex count to get the
	// center point and width of the whole scene.  We use this information
	// to subdivide our octree.  Eventually, in the next tutorial it won't
	// just be a list of vertices, but another structure that holds all the
	// normals and texture information.  It's easy to do once you understand vertices.

	// Initialize some temporary variables to hold the max dimensions found
	float maxWidth = 0, maxHeight = 0, maxDepth = 0;

	// Return from this function if we passed in bad data
	if(!pVertices || numberOfVerts <= 0) return;

	// Below we calculate the center point of the scene.  To do this, all you
	// need to do is add up ALL the vertices, then divide that total by the
	// number of vertices added up.  So all the X's get added up together, then Y's, etc..
	// This doesn't mean in a single number, but 3 separate floats (totalX, totalY, totalZ).
	// Notice that we are adding 2 vectors together.  If you look in the CVector3 class
	// I overloaded the + and - operator to handle it correctly.  It cuts down on code
	// instead of added the x, then the y, then the z separately.  If you don't want
	// to use operator overloading just make a function called CVector AddVector(), etc...

	// Go through all of the vertices and add them up to eventually find the center
	for(int i = 0; i < numberOfVerts; i++)
	{
		// Add the current vertex to the center variable (Using operator overloading)
		m_vCenter = m_vCenter + pVertices[i];
	}

	// Divide the total by the number of vertices to get the center point.
	// We could have overloaded the / symbol but I chose not to because we rarely use it.
	m_vCenter.x /= numberOfVerts;
	m_vCenter.y /= numberOfVerts;	
	m_vCenter.z /= numberOfVerts;

	// Now that we have the center point, we want to find the farthest distance from
	// our center point.  That will tell us how big the width of the first node is.
	// Once we get the farthest height, width and depth, we then check them against each
	// other.  Which ever one is higher, we then use that value for the cube width.

	// Go through all of the vertices and find the max dimensions
	for(i = 0; i < numberOfVerts; i++)
	{
		// Get the current dimensions for this vertex.  We use the fabsf() function
		// to get the floating point absolute value because it might return a negative number.
		float currentWidth  = fabsf(pVertices[i].x - m_vCenter.x);	
		float currentHeight = fabsf(pVertices[i].y - m_vCenter.y);		
		float currentDepth  = fabsf(pVertices[i].z - m_vCenter.z);	

		// Check if the current width value is greater than the max width stored.
		if(currentWidth  > maxWidth)	maxWidth  = currentWidth;

		// Check if the current height value is greater than the max height stored.
		if(currentHeight > maxHeight)	maxHeight = currentHeight;