quadtree.cpp

小型的3D游戏引擎

#include <iostream>
#include "quadtree.h"
#include "../global.h"
#include "terrain.h"
using namespace std;


//////////////////////////////////////////////////////////////////////////////////

const int GcQuadtreeNode::MAX_OBJECTS = 1024;
const int GcQuadtree::MAX_DEPTH = 8;
int GcQuadtreeNode::numDrawn;
float GcQuadtree::nodeHeight = 1.0f;
int GcQuadtree::numObjectsDrawn;
int GcQuadtree::numStaticGeometryDrawn;

///////////////////////////////////////////////////////////////////////////////////////

GcQuadtree::GcQuadtree()
{
	m_debugMode = false;

	m_nodeHeight = 1.0f;

	numObjectsDrawn = 0;
	numStaticGeometryDrawn = 0;
}

///////////////////////////////////////////////////////////////////////////////////////

GcQuadtree::~GcQuadtree() 
{ 
	g_Debug->Log("~GcQuadtree Begin\n");
	
	if(m_rootNode)
	{
		delete m_rootNode;
		m_rootNode = NULL;
	}

	g_Debug->Log("~GcQuadtree End\n");
}

///////////////////////////////////////////////////////////////////////////////////////

bool GcQuadtree::Create( uint depth, float leafSide )
{
	if( depth <= 0 || depth > MAX_DEPTH )
		return false;

	m_depth = depth;
	m_leafSide = leafSide;
	
	m_treeSide = pow(2, depth - 1) * leafSide;
	
	//m_rootNode = new GcQuadtreeNode(this, depth, NULL, GcAABB( GcVector3(m_treeSide, m_treeSide, 1.0f) ) );
	//m_rootNode = new GcQuadtreeNode(this, depth, NULL, GcAABB( GcVector3(m_leafSide, 2, m_leafSide), GcVector3( ) );

	m_rootNode = new GcQuadtreeNode(this, depth, NULL, NULL);
		

	// Allocate memory for the nodes
	//CreateNodes();

	// Calculate the indices of the bounding cord for the map
/*	uint bound[] = { 0, mapWidth, (mapWidth * (mapWidth + 1)), 
					 ((mapWidth * (mapWidth + 1)) + mapWidth) };

	// Re-set the total tree id
	treeId = 0;

	// Build the nodes
	BuildNode(bound, 0, 0);*/

	// Get the active frustum
	m_frustum = ActiveFrustum();

	return true;
}

//////////////////////////////////////////////////////////////////////////////////

bool GcQuadtree::AttachNode( GcRenderNode * node )
{
	if(m_depth <= 0) {
		return false;
	}

	// The AttachNode function of the GcQuadtreeNode will automatically look for best leaf to put the GcRenderNode
	return m_rootNode->AttachNode(node);
}

///////////////////////////////////////////////////////////////////////////////////////

bool GcQuadtree::DetachNode( GcRenderNode * node )
{
	return false;
}

///////////////////////////////////////////////////////////////////////////////////////

void GcQuadtree::Render()
{
	GcFrustum * frustum = ActiveFrustum();

	GcQuadtreeNode::numDrawn = 0;
	GcQuadtree::numObjectsDrawn = 0;

	if(GcSettings::Fog()) {
		glEnable(GL_FOG);
	}
	
	// Do intersection test frustum - AABB here
	if( frustum->Contains( m_rootNode->AABB() ) )
	{
		m_rootNode->Render();
	}

	glDisable(GL_FOG);

	//dbgC.Write("Num drawn nodes: %d\n", GcQuadtreeNode::numDrawn);
	//dbgC.Write("Num drawn objects: %d\n\n", GcQuadtree::numObjectsDrawn);
		

	glColor3f(0.5f, 0.0f, 0.0f);

	glBegin(GL_LINES);
		glVertex3fv( GcVector3(GetTreeSide() / 2, -200, GetTreeSide() / 2) );
		glVertex3fv( GcVector3(GetTreeSide() / 2, 200, GetTreeSide() / 2) );
	glEnd();

}

///////////////////////////////////////////////////////////////////////////////////////

void GcQuadtree::Destroy()
{
	g_Debug->Log("~GcQuadtree Begin\n");
	
	if(m_rootNode)
	{
		delete m_rootNode;
		m_rootNode = NULL;
	}

	g_Debug->Log("~GcQuadtree End\n");
}

//////////////////////////////////////////////////////////////////////////////////


///////////////////////////////////////////////////////////////////////////////////////
// GcQuadtreeNode
///////////////////////////////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////////////////////////

GcQuadtreeNode::GcQuadtreeNode( GcQuadtree * quadtree, int depth, GcQuadtreeNode * parent, GcAABB * aabb  )
{
	GrowTree(quadtree, depth, parent, aabb);
}

//////////////////////////////////////////////////////////////////////////////////

void GcQuadtreeNode::GrowTree( GcQuadtree * quadtree, int depth, GcQuadtreeNode * parent, GcAABB * aabb )
{
	m_nodeDepth = depth;
	depth--;

	m_quadtree = quadtree;
	m_parent = parent;


	if( parent == NULL && aabb == NULL)
	{
		// Ok, this must be the root node
		// Create an AABB for the root node
		
		// FIXME: The 2 below to const from the class
		m_aabb = new GcAABB( GcVector3(quadtree->GetTreeSide() / 2, GcQuadtree::nodeHeight, quadtree->GetTreeSide() / 2 ) );
		
		m_aabb->SetTranslation( GcVector3(quadtree->GetTreeSide() / 2, 0, quadtree->GetTreeSide() / 2) );
	}
	else
		m_aabb = aabb;


	if( depth > 0 )
	{
		// We are a branch since we have leaves under us and depth is greater than 0
		m_type = GcQuadtree::Node::Branch;
		
		m_nodes = new GcQuadtreeNode[4];

		GcAABB * temp[4];

		GcVector3 & p = m_aabb->GetWorldTranslation();
		

		// The GcAABB's we create here will be deleted by the receiving nodes' destructors
		temp[0] = new GcAABB( GcVector3( m_aabb->Extent(0) / 2, m_aabb->Extent(1), m_aabb->Extent(2) / 2) );
		temp[0]->SetTranslation( GcVector3( p.x + m_aabb->Extent(0) / 2, p.y, p.z + m_aabb->Extent(2) / 2 ) );
		
		temp[1] = new GcAABB( GcVector3( m_aabb->Extent(0) / 2, m_aabb->Extent(1), m_aabb->Extent(2) / 2) );
		temp[1]->SetTranslation( GcVector3( p.x + m_aabb->Extent(0) / 2, p.y, p.z - m_aabb->Extent(2) / 2 ) );

		temp[2] = new GcAABB( GcVector3( m_aabb->Extent(0) / 2, m_aabb->Extent(1), m_aabb->Extent(2) / 2) );
		temp[2]->SetTranslation( GcVector3( p.x - m_aabb->Extent(0) / 2, p.y, p.z + m_aabb->Extent(2) / 2 ) );

		temp[3] = new GcAABB( GcVector3( m_aabb->Extent(0) / 2, m_aabb->Extent(1), m_aabb->Extent(2) / 2) );
		temp[3]->SetTranslation( GcVector3( p.x - m_aabb->Extent(0) / 2, p.y, p.z - m_aabb->Extent(2) / 2 ) );

		m_nodes[0].GrowTree( quadtree, depth, this, temp[0] );
		m_nodes[1].GrowTree( quadtree, depth, this, temp[1] );
		m_nodes[2].GrowTree( quadtree, depth, this, temp[2] );
		m_nodes[3].GrowTree( quadtree, depth, this, temp[3] );
	}
	else
	{
		// We are a leaf since the
		m_type = GcQuadtree::Node::Leaf;
		m_nodes = NULL;
		m_aabb = aabb;
	}
	
}

//////////////////////////////////////////////////////////////////////////////////

GcQuadtreeNode::GcQuadtreeNode()
{
	m_nodes = NULL;
	m_parent = NULL;
	m_neighbors = NULL;
	m_quadtree = NULL;
	m_aabb = NULL;

	m_nodeDepth = -1;

}

//////////////////////////////////////////////////////////////////////////////////

GcQuadtreeNode::~GcQuadtreeNode()
{
	int i;
	
	g_Debug->Log("~GcQuadtreeNode Begin\n");

	for( i = 0; i < m_objects.size(); ++i)
	{	
		if(m_objects[i])
		{
			delete m_objects[i];
			m_objects[i] = NULL;
		}
	}

	g_Debug->Log("~GcQuadtreeNode 1\n");

	for( i = 0; i < m_staticGeometry.size(); ++i )
	{
		if( m_staticGeometry[i] )
		{
			delete m_staticGeometry[i];
			m_staticGeometry[i] = NULL;
		}
	}
	
	g_Debug->Log("~GcQuadtreeNode 2\n");

	m_objects.clear();
	m_staticGeometry.clear();

	g_Debug->Log("~GcQuadtreeNode 3\n");

	if( m_nodes )
	{
		g_Debug->Log("~GcQuadtreeNode 4\n");
		
		delete [] m_nodes;
		
		g_Debug->Log("~GcQuadtreeNode 5\n");
		m_nodes = NULL;
	}

	if( m_aabb )
	{
		delete [] m_aabb;
		m_aabb = NULL;
	}

	g_Debug->Log("~GcQuadtreeNode End\n");
}

//////////////////////////////////////////////////////////////////////////////////

bool GcQuadtreeNode::AttachNode( GcRenderNode * node )
{
	if( m_type == GcQuadtree::Node::Branch && node->Intersects( AABB() ))
	{

		if( node->Intersects( m_nodes[0].AABB() ) ) return m_nodes[0].AttachNode(node);
		else if( node->Intersects( m_nodes[1].AABB() ) ) return m_nodes[1].AttachNode(node);
		else if( node->Intersects( m_nodes[2].AABB() ) ) return m_nodes[2].AttachNode(node);
		else if( node->Intersects( m_nodes[3].AABB() ) ) return m_nodes[3].AttachNode(node);
		
		g_DebugConsole->Write("ERROR! Node slipped intersection tests!");
	}
	else if( m_type == GcQuadtree::Node::Leaf )
	{
		g_DebugConsole->Write("Added object! Depth level: %d", m_nodeDepth);
		m_objects.push_back(node);
		return true;
	}

	return false;
}

//////////////////////////////////////////////////////////////////////////////////

bool GcQuadtreeNode::DetachNode( GcRenderNode * node )
{
	for( std::vector<GcRenderNode *>::iterator itRn = m_objects.begin(); itRn != m_objects.end(); ++itRn )
	{
		// Check if current node matches the one we passed
		if( (*itRn) == node )
		{
			// Delete it from our child list
			m_objects.erase( itRn );

			return true;
		}
	}

	// Nothing to detach
	return false;
}

//////////////////////////////////////////////////////////////////////////////////

void GcQuadtreeNode::Render()
{
	GcFrustum * frustum = ActiveFrustum();
	
	// Statistics for debugging
	++numDrawn;

	int i;


	if(m_quadtree->DebugMode()) {
		m_aabb->RenderOutlines();
	}

	if(m_type == GcQuadtree::Node::Leaf)
	{
		// Loop through and render all static geometry
		for( i = 0; i < m_staticGeometry.size(); ++i )
		{
			m_staticGeometry[i]->Render();
			GcQuadtree::numStaticGeometryDrawn++;
		}

		// Loop through and render all objects
		for( i = 0; i < m_objects.size(); ++i )
		{
			m_objects[i]->Render();
			
			GcQuadtree::numObjectsDrawn++;
		}
	}
	else
	{
		// Do frustum - AABB intersection test here
		if( frustum->Contains( m_nodes[0].AABB() ) ) m_nodes[0].Render();
		if( frustum->Contains( m_nodes[1].AABB() ) ) m_nodes[1].Render();
		if( frustum->Contains( m_nodes[2].AABB() ) ) m_nodes[2].Render();
		if( frustum->Contains( m_nodes[3].AABB() ) ) m_nodes[3].Render();
	}
}

//////////////////////////////////////////////////////////////////////////////////

void GcQuadtreeNode::Update( float deltaTime )
{
	if( m_type == GcQuadtree::Node::Branch )
		return;
		
	for( int i = 0; i < m_objects.size(); ++i )
	{
		m_objects[i]->Update(deltaTime);
	}


	// Static geometry doesn't need to be updated
}

//////////////////////////////////////////////////////////////////////////////////