abt.cpp

游戏编程精粹６中关于用自适度二叉树进行空间剖分

#include "ABT.h"



/* ***************************************************************** *\
|  CONSTRUCTION / DESTRUCTION
\* ***************************************************************** */
cABT::cABT() :
	m_Root(NULL),
	m_NumRenderedTris(0),
	m_NumFinalTris(0)
{
}


cABT::~cABT()
{
	release();
}


/* ***************************************************************** *\
|  create
|  *****************************************************************
|  Creates the ABT tree by calling the recursive r_create method.
\* ***************************************************************** */
bool cABT::create()
{
	// check if VBO extension is supported ...
	if(!m_OGLExt.isExtensionSupported("GL_ARB_vertex_buffer_object"))
	{
		printf("GL_ARB_vertex_buffer_object not supported!!\n\n");
		return false;
	}

	// call init to be sure the extensions are loaded
	m_OGLExt.init();

	// load our ply files
	cDataLoader loader;
	if(!loader.readPlyFiles())
		return false;

	// get the loaded data
	vector<Vertex> *vertexData = loader.getVertexData();
	uint32 numLoadedTris = vertexData->size() / 3;
	
	// reset final tris counter
	m_NumFinalTris = 0;

	// create the tree
	m_Root = r_create((*vertexData));

	printf("ABT created from %d triangles (contains now %d triangles)\n", numLoadedTris, m_NumFinalTris);

	return true;
}


/* ***************************************************************** *\
|  render
|  *****************************************************************
|  Renders the ABT tree by calling the recursive r_render method.
\* ***************************************************************** */
uint32 cABT::render()
{
	// update frustum
	updateFrustum();

	// reset rendered tris counter
	m_NumRenderedTris = 0;

	// enable pointers
	glEnableClientState(GL_VERTEX_ARRAY);
//	glEnableClientState(GL_COLOR_ARRAY);
	glEnableClientState(GL_NORMAL_ARRAY);

	// render the tree
	r_render(m_Root);

	// disable pointers
	glDisableClientState(GL_VERTEX_ARRAY);
//	glDisableClientState(GL_COLOR_ARRAY);
	glDisableClientState(GL_NORMAL_ARRAY);

	return m_NumRenderedTris;
}


/* ***************************************************************** *\
|  release
|  *****************************************************************
|  Releases the ABT tree by calling the recursive r_release method.
\* ***************************************************************** */
void cABT::release()
{
	r_release(m_Root);
	m_Root = NULL;
}


/* ***************************************************************** *\
|  r_create
|  *****************************************************************
|  Recursive ABT creation method.
\* ***************************************************************** */
ABTNode* cABT::r_create(vector<Vertex> &p_Vertex)
{
	// step1: determine the aabb of the current geometry set
	cAABoundingBox aabb;
	getAABB(p_Vertex, &aabb);

	// create a new node and assign the aabb
	ABTNode *pNewNode = new ABTNode;
	pNewNode->aabb = aabb;

	// step2: check if we reached the triangle threshold
	if(p_Vertex.size() > (ABT_MAX_NODEPRIMITIVES * 3))
	{
		// we don't have a leaf ...
		pNewNode->bIsLeaf = false;

		// find a new splitter for this node ...
		cPlane splitPlane;
		getSplitter(p_Vertex, &aabb, &splitPlane);

		// we define two planes that represent the maximum extend of a 
		// grown child bounding box
		cPlane splitPlaneGrow1, splitPlaneGrow2;

		splitPlaneGrow1 = splitPlane;
		splitPlaneGrow2 = splitPlane;

		// determine the axis perpendicular to our plane 
		uint32 iCurAxis = 0;
		for(uint32 i = 0; i < 3; i++)
		{
			if(splitPlane.n[i] == 1.0f)
				iCurAxis = i;
		}

		// calculate the grow planes
		float32 childAABBLen = (aabb.getSplitPercent(splitPlaneGrow1) * aabb.getAxisLen(iCurAxis));
		splitPlaneGrow1.p[iCurAxis] +=  childAABBLen * ABT_GROWTH_FACTOR;
		splitPlaneGrow2.p[iCurAxis] -= (aabb.getAxisLen(iCurAxis) - childAABBLen) * ABT_GROWTH_FACTOR;

		// split the node's geometry set
		vector<Vertex> childAVertex;
		vector<Vertex> childBVertex;

		// set the vectors' size to 3/4 of the original vector's size ...
		childAVertex.reserve(p_Vertex.size() * 3 / 4);
		childBVertex.reserve(p_Vertex.size() * 3 / 4);

		uint32 iNumSplits = 0;
		for(uint32 i = 0; i < p_Vertex.size(); i+=3)
		{
			// determine the current surface's location
			uint32 res = getTriangleSide(&splitPlane, &(p_Vertex[i]));

			// is a split required?
			if(res == ABT_SPANNING)
			{
				// check if we don't have to split if we grow the children's AABB
				res = getTriangleSide(&splitPlaneGrow1, &(p_Vertex[i]));
				if(res == ABT_SPANNING)
				{
					res = getTriangleSide(&splitPlaneGrow2, &(p_Vertex[i]));
					if(res == ABT_SPANNING)
					{
						// split the triangle
						vector<Vertex> frontFaces;
						vector<Vertex> backFaces;
						splitTriangle(&splitPlane, &(p_Vertex[i]), frontFaces, backFaces);

						if(frontFaces.size() % 3 || backFaces.size() % 3)
							DebugBreak();

						// add the new triangles to the list
						for(uint32 j = 0; j < frontFaces.size(); j++)
							childAVertex.push_back(frontFaces[j]);
						for(uint32 j = 0; j < backFaces.size(); j++)
							childBVertex.push_back(backFaces[j]);

						iNumSplits++;
						continue;
					}
				}
			}

			if(res == ABT_FRONT)
			{
				childAVertex.push_back(p_Vertex[i]);
				childAVertex.push_back(p_Vertex[i + 1]);
				childAVertex.push_back(p_Vertex[i + 2]);
			}
			else if(res == ABT_BACK)
			{
				childBVertex.push_back(p_Vertex[i]);
				childBVertex.push_back(p_Vertex[i + 1]);
				childBVertex.push_back(p_Vertex[i + 2]);
			}
			else
			{
				// coinciding ... add the triangle to the vector with the smaller
				// amount of vertices
				if(childAVertex.size() < childBVertex.size())
				{
					childAVertex.push_back(p_Vertex[i]);
					childAVertex.push_back(p_Vertex[i + 1]);
					childAVertex.push_back(p_Vertex[i + 2]);
				}
				else
				{
					childBVertex.push_back(p_Vertex[i]);
					childBVertex.push_back(p_Vertex[i + 1]);
					childBVertex.push_back(p_Vertex[i + 2]);
				}
			}
		}
		
		// now we can release the memory from our p_Vertex vector ..
		// little hack taken from: http://www.gotw.ca/gotw/054.htm
		vector<Vertex>().swap(p_Vertex);

		printf("Total splits: %d\n", iNumSplits);

		// continue recursion
		pNewNode->pChildA = r_create(childAVertex);
		pNewNode->pChildB = r_create(childBVertex);

	}else
	{
		// we have a leaf ...
		pNewNode->bIsLeaf = true;
		pNewNode->pChildA = pNewNode->pChildB = NULL;

		// create new vertex buffer objects
		m_OGLExt.glGenBuffersARB(1, &(pNewNode->iVertexBuffer));
		m_OGLExt.glBindBufferARB(GL_ARRAY_BUFFER_ARB, pNewNode->iVertexBuffer);

		// load the vertex data in our buffer
		m_OGLExt.glBufferDataARB(GL_ARRAY_BUFFER_ARB, p_Vertex.size() * sizeof(Vertex), 
			&(p_Vertex[0]), GL_STATIC_DRAW_ARB);

		// store the primitives number
		pNewNode->iVertexCount = (uint32)p_Vertex.size();

		// we don't need the vertex data further as it is already loaded
		// into the gfx card memory ...
		vector<Vertex>().swap(p_Vertex);

		printf("Leaf with %d faces created!\n", pNewNode->iVertexCount / 3);
		m_NumFinalTris += pNewNode->iVertexCount / 3;
	}

	return pNewNode;
}


/* ***************************************************************** *\
|  r_render
|  *****************************************************************
|  Recursive method to render the ABT.
\* ***************************************************************** */
void cABT::r_render(ABTNode *p_Node)
{
	if(p_Node)
	{
		// check if the node is visible ...
		if(!isInFrustum(p_Node->aabb))
			return;	// no - reject it and all its children
		
		if(p_Node->bIsLeaf)
		{
			// setup the node's data for rendering
			m_OGLExt.glBindBufferARB(GL_ARRAY_BUFFER_ARB, p_Node->iVertexBuffer);
			glVertexPointer(3, GL_FLOAT, sizeof(Vertex), (char*)(0));
			//glColorPointer(4, GL_BYTE, sizeof(Vertex), (char*)(6 * sizeof(float32)));
			glNormalPointer(GL_FLOAT, sizeof(Vertex), (char*)(3 * sizeof(float32)));
			
			// render
			glDrawArrays(GL_TRIANGLES, 0, p_Node->iVertexCount);

			// update counter
			m_NumRenderedTris += (p_Node->iVertexCount / 3);
		}else
		{
			// call r_render for the children
			r_render(p_Node->pChildA);
			r_render(p_Node->pChildB);
		}
	}
}


/* ***************************************************************** *\
|  r_release
|  *****************************************************************
|  Recursive method to free the allocated memory.
\* ***************************************************************** */
void cABT::r_release(ABTNode *p_Node)
{
	if(!p_Node)
		return;

	if(p_Node->bIsLeaf)
	{
		// release gl VBOs
		m_OGLExt.glDeleteBuffersARB(1, &(p_Node->iVertexBuffer));
	}
	else
	{
		// recursive call for children
		r_release(p_Node->pChildA);
		r_release(p_Node->pChildB);
	}

	// delete the node
	delete p_Node;
}


/* ***************************************************************** *\
|  getAABB
|  *****************************************************************
|  Calculates the AABB of the current geometry set
\* ***************************************************************** */
void cABT::getAABB(vector<Vertex> &p_Vertex, cAABoundingBox *p_AABB)
{
	float32 maxx, maxy, maxz;
	float32 minx, miny, minz;

	// check parameters
	if(!p_AABB)
	{
		printf("Invalid parameters passed to getAABB\n");
		return;
	}

	// init max/min values
	maxx = minx = p_Vertex[0].xyz[0];
	maxy = miny = p_Vertex[0].xyz[1];
	maxz = minz = p_Vertex[0].xyz[2];

	// determine size of the AABB
	vector<Vertex>::iterator i = p_Vertex.begin();
	for(i++; i != p_Vertex.end(); i++)
	{
		maxx = max(maxx, (*i).xyz[0]);
		maxy = max(maxy, (*i).xyz[1]);
		maxz = max(maxz, (*i).xyz[2]);

		minx = min(minx, (*i).xyz[0]);
		miny = min(miny, (*i).xyz[1]);
		minz = min(minz, (*i).xyz[2]);
	}

	// fill in aabb
	p_AABB->maxPt = cVector(maxx, maxy, maxz);
	p_AABB->minPt = cVector(minx, miny, minz);
	p_AABB->centerPt = cVector((minx + maxx) / 2.0f, (miny + maxy) / 2.0f, (minz + maxz) / 2.0f);
}


/* ***************************************************************** *\
|  getSplitter
|  *****************************************************************
|  Finds the best splitter for the given geometry set using Andy
|  Campbell's statistically weighted multi sampling.
\* ***************************************************************** */
void cABT::getSplitter(vector<Vertex> &p_Vertex, cAABoundingBox *p_AABB, cPlane *p_Plane)
{
	// init vars
	float32 fBestSplitterScore = 100000000.0f;
	float32 fLargestAxis;

	// determine largest axis
	fLargestAxis = max(max(p_AABB->getAxisLen(0), p_AABB->getAxisLen(1)), p_AABB->getAxisLen(2));

	// we scan each axis for a plane
	for(uint32 iCurAxis = 0; iCurAxis < 3; iCurAxis++)
	{
		// init a new plane object
		cPlane testPlane(cVector(0.0f, 0.0f, 0.0f), cVector(0.0f, 0.0f, 0.0f));

		// init the plane's normal
		testPlane.n[iCurAxis] = 1.0f;