//
// Asura_LBAABB_Tree.cpp
//
// Created by KJFL - Thursday, January 20, 2005
//
// Copyright (C) 2005 Rebellion, All Rights Reserved.
//

#include "Core/Asura.h"

// This file's header.
#include "Core/Asura_LBAABB_Tree.h"

// Asura includes...
#include "ChunkSystem/Asura_Chunk_Stream.h"
#include "Core/Memory/Asura_Mem.h"

static const float fCOMPRESSION_SCALE = 127.0f;
static const float fDECOMPRESSION_SCALE = 1.0f / fCOMPRESSION_SCALE;

#ifdef ASURA_TOOLS
static const int iMAX_VALUE = 127;
static const int iMIN_VALUE = -128;
#endif

enum 
{
	ASURA_LBAABB_LEFT_OFFSET_X,
	ASURA_LBAABB_LEFT_OFFSET_Y,
	ASURA_LBAABB_LEFT_OFFSET_Z,
	ASURA_LBAABB_RIGHT_OFFSET_X,
	ASURA_LBAABB_RIGHT_OFFSET_Y,
	ASURA_LBAABB_RIGHT_OFFSET_Z,
};


// KJFL - Friday, January 28, 2005 - PHYSICSTODO: place this stack on scratch pad of PS2.
// Output list needs smaller limit (potentially) with over-flow check (definitely).
// Not happy with split cache idea currently being used to cope with 'face calls' with 'sector calls'
// (AW - 18.08.2005) - Overflow check implemented.
static Asura_LBAABB_Tree_StackElement g_axStack[2][32];
static const u_int uMAX_BB_TEST_OUTPUT = 1024;
static u_int g_auOutputList[2][uMAX_BB_TEST_OUTPUT];

// Left bounding box and Right bounding box should both equal the parent bounding box when this 
// function is called. Assertion has been omitted since this code is called so heavily.
static inline void AdjustBoundingBoxes(const char* pcArray, Asura_Bounding_Box& xLeftBB, Asura_Bounding_Box& xRightBB)
{
	// This code jumps through hoops to avoid branching. It uses the sign bit as an
	// offset into the bounding box element array.
	const float fXMultiplier = fDECOMPRESSION_SCALE * (xLeftBB.MaxX - xLeftBB.MinX);
	const float fYMultiplier = fDECOMPRESSION_SCALE * (xLeftBB.MaxY - xLeftBB.MinY);
	const float fZMultiplier = fDECOMPRESSION_SCALE * (xLeftBB.MaxZ - xLeftBB.MinZ);

	// Left
	const float fLeftOffsetX = static_cast<float>(pcArray[ASURA_LBAABB_LEFT_OFFSET_X]) * fXMultiplier;
	const float fLeftOffsetY = static_cast<float>(pcArray[ASURA_LBAABB_LEFT_OFFSET_Y]) * fYMultiplier;
	const float fLeftOffsetZ = static_cast<float>(pcArray[ASURA_LBAABB_LEFT_OFFSET_Z]) * fZMultiplier;

	xLeftBB.m_fElement[static_cast<const u_char>(pcArray[ASURA_LBAABB_LEFT_OFFSET_X]) >> 7] += fLeftOffsetX;
	xLeftBB.m_fElement[2 + (static_cast<const u_char>(pcArray[ASURA_LBAABB_LEFT_OFFSET_Y]) >> 7)] += fLeftOffsetY;
	xLeftBB.m_fElement[4 + (static_cast<const u_char>(pcArray[ASURA_LBAABB_LEFT_OFFSET_Z]) >> 7)] += fLeftOffsetZ;

	// Right.
	const float fRightOffsetX = static_cast<float>(pcArray[ASURA_LBAABB_RIGHT_OFFSET_X]) * fXMultiplier;
	const float fRightOffsetY = static_cast<float>(pcArray[ASURA_LBAABB_RIGHT_OFFSET_Y]) * fYMultiplier;
	const float fRightOffsetZ = static_cast<float>(pcArray[ASURA_LBAABB_RIGHT_OFFSET_Z]) * fZMultiplier;

	xRightBB.m_fElement[static_cast<const u_char>(pcArray[ASURA_LBAABB_RIGHT_OFFSET_X]) >> 7] += fRightOffsetX;
	xRightBB.m_fElement[2 + (static_cast<const u_char>(pcArray[ASURA_LBAABB_RIGHT_OFFSET_Y]) >> 7)] += fRightOffsetY;
	xRightBB.m_fElement[4 + (static_cast<const u_char>(pcArray[ASURA_LBAABB_RIGHT_OFFSET_Z]) >> 7)] += fRightOffsetZ;
}

void Asura_LBAABB_Tree::TestTreeWithPoint( const Asura_Vector_3& xPos, Asura_LBAABB_Callback pfnOutputCallback) const
{
	Asura_Bounding_Box xBB;
	xBB.SetToPoint(xPos);
	TestTreeWithBB(xBB, pfnOutputCallback);
}

void Asura_LBAABB_Tree::TestTreeWithBB(  const Asura_Bounding_Box& xTestBB, void(*pfnOutputCallback)(const u_int uIndex), const u_int uCache  ) const
{
	if (!m_uNumberOfNodes)
	{
		if (xTestBB.Intersects( m_xRootBoundingBox ) )
		{
			pfnOutputCallback(0);
		}
		return;
	}
	
	Asura_LBAABB_Tree_StackElement* pxStack = &g_axStack[uCache][0];

	pxStack->m_uIndex = 0;
	pxStack->m_xBB = m_xRootBoundingBox;
	++pxStack;

	u_int uNumberOfResults = 0;

	while (pxStack != &g_axStack[uCache][0] )
	{
		--pxStack;

		const u_int uNodeIndex = pxStack->m_uIndex;

		// To prevent unnecessary copying of BBs, we use the BB on the stack as 
		// our right bounding box.
		Asura_Bounding_Box xLeftBB = pxStack->m_xBB;

        const Asura_LBAABB_Tree_Double_Node& xNode = m_pxNodes[uNodeIndex >> 1];
		AdjustBoundingBoxes(xNode.m_aacElements[uNodeIndex & 1], xLeftBB, pxStack->m_xBB);
	
		const bool bIntersectsLeft = xTestBB.Intersects(xLeftBB);
		const bool bIntersectsRight = xTestBB.Intersects(pxStack->m_xBB);

		/// Kevin Lea - 14/05/2002 11:03:41 - if Right is leaf, output index if overlap occurs
		if (bIntersectsRight)
		{
			const u_int uRightIndex = uNodeIndex * 2 + 2;

			if ( uRightIndex >= m_uNumberOfNodes )
			{
				// if we've filled up our cache with data, flush it via the callback function
				if( uNumberOfResults == uMAX_BB_TEST_OUTPUT )
				{
					do
					{
						pfnOutputCallback( g_auOutputList[ uCache ][ --uNumberOfResults ] );
					}
					while( uNumberOfResults );
				}

				// add result to cache
				const u_int uLeaf =  uRightIndex - m_uNumberOfNodes ;
				g_auOutputList[uCache][ uNumberOfResults++ ] = uLeaf;
			}
			else
			{
				pxStack->m_uIndex = uRightIndex;
				++pxStack;
				// If right is branch then so is left.
				if (bIntersectsLeft)
				{
					pxStack->m_uIndex = uRightIndex - 1;
					pxStack->m_xBB = xLeftBB;
					++pxStack;
				}
				continue;
			}
		}

		/// Kevin Lea - 14/05/2002 11:03:41 - if left is leaf, output index if overlap occurs
		if (bIntersectsLeft)
		{
			const u_int uLeftIndex =  uNodeIndex * 2 + 1;

			if (uLeftIndex >= m_uNumberOfNodes )
			{
				// if we've filled up our cache with data, flush it via the callback function
				if( uNumberOfResults == uMAX_BB_TEST_OUTPUT )
				{
					do
					{
						pfnOutputCallback( g_auOutputList[ uCache ][ --uNumberOfResults ] );
					}
					while( uNumberOfResults );
				}

				// add result to cache
				const u_int uLeaf =  uLeftIndex - m_uNumberOfNodes ;
				g_auOutputList[uCache][ uNumberOfResults++ ] = uLeaf;
			}
			else
			{
				pxStack->m_uIndex = uLeftIndex;
				pxStack->m_xBB = xLeftBB;
				++pxStack;
			}

		}

	}
	
	while( uNumberOfResults-- )
	{
		pfnOutputCallback( g_auOutputList[uCache][ uNumberOfResults ] );
	}
}


// Based on Asura_Maths::RayIntersectsBoundingBox. Optimised and inlined specically 
// for the needs of Asura_AABB_Tree::TestNodeWithRay
// Main differences are : 
//  - Removal of unneeded parameters.
//  - Inlined.
//  - fDistance an input parameter as well as an output parameter to support early rejection.
//  - Loop near the end of the function is unwrapped

// AJG - 20/10/05 - Added this to avoid dividing by too small a number when calculating the temp distance value, preventing an overflow FP exception.
static const float fBETAEPSILON = 0.000001f;

static inline bool Fast_RayIntersectsBoundingBox( const Asura_Vector_3& xAlpha,
											const Asura_Vector_3& xBeta,
											const Asura_Bounding_Box& xBox,
											float& fDistance)
{
	Asura_Vector_3 xMinCorner(xBox.MinX, xBox.MinY, xBox.MinZ);
	Asura_Vector_3 xMaxCorner(xBox.MaxX, xBox.MaxY, xBox.MaxZ);
	float fHighestDistance = -1.0f;
	int iPlane = -1;

	for(int i=0; i<3; i++)
	{
		float fTempDistance = -1.0f;
		if (xAlpha[i] < xMinCorner[i])
		{
			if (xBeta[i] <= fBETAEPSILON) return false;
			fTempDistance = (xMinCorner[i] - xAlpha[i]) / xBeta[i];
		}
		else if (xAlpha[i] > xMaxCorner[i])
		{
			if (xBeta[i] >= -fBETAEPSILON) return false;
			fTempDistance = (xMaxCorner[i] - xAlpha[i]) / xBeta[i];	
		}
		if (fTempDistance > fHighestDistance)
		{
			fHighestDistance = fTempDistance;
			iPlane = i;
		}
	}

	// Ray origin inside bounding box? Return as a hit.
	// (NOTE: also a hit if the ray starts on the surface of the BB.)
	if (iPlane == -1)
	{
		fDistance = 0.0f;
		return true;
	}

	// Distance more than our input distance.
	if (fHighestDistance > fDistance)
	{
		return false;
	}

	Asura_Assert(fHighestDistance>0.0f,"Impossible value");
	//if (xLambda[iPlane]<0.0f) return false; // MGH: this should be impossible, so the test is not needed.

#if 0
	for (int i=0; i<3; i++)
	{
		if (i != iPlane)
		{
			const float fIntersection = xAlpha[i] + fHighestDistance * xBeta[i];
			if (fIntersection < xMinCorner[i] || fIntersection > xMaxCorner[i]) return false;
		}
	}
#else
	// Unwrapped the above loop
	const int iIndex1 = (iPlane + 1) % 3;
	const float fIntersection1 = xAlpha[iIndex1] + fHighestDistance * xBeta[iIndex1];
	if (fIntersection1 < xMinCorner[iIndex1] || fIntersection1 > xMaxCorner[iIndex1]) return false;

	const int iIndex2 = (iPlane + 2) % 3;
	const float fIntersection2 = xAlpha[iIndex2] + fHighestDistance * xBeta[iIndex2];
	if (fIntersection2 < xMinCorner[iIndex2] || fIntersection2 > xMaxCorner[iIndex2]) return false;
#endif

	/// We have an intersection then.
	fDistance = fHighestDistance;
	return true;
}
// End of Fast_RayIntersectsBoundingBox


void Asura_LBAABB_Tree::TestTreeWithRay( const Asura_Vector_3& xRayOrigin, const Asura_Vector_3& xRayDirection, float* pfDistance, void(*pfnRayTestCallback)( const u_int uIndex ), const u_int uCache ) const
{
	if (!m_uNumberOfNodes)
	{
		float fDistance = *pfDistance;
		if ( Fast_RayIntersectsBoundingBox( xRayOrigin, xRayDirection, m_xRootBoundingBox, fDistance) )
		{
			pfnRayTestCallback(0);
		}

		return;
	}
	if (xRayDirection.y == 1.0f)
	{
		// (AW - 17/08/05) - It seems very common for vertically downward LOS tests tests to
		// occur (about 30% of all LOS on Rogue). TestTreeWithRay_VertDown is optimised to 
		// take advantage of this fact.
		TestTreeWithRay_VertDown(xRayOrigin, pfDistance, pfnRayTestCallback, uCache);
		return;
	}
	
	
	Asura_LBAABB_Tree_StackElement* pxStack = &g_axStack[uCache][0];

	pxStack->m_uIndex = 0;
	pxStack->m_xBB = m_xRootBoundingBox;
	++pxStack;

	while (pxStack != &g_axStack[uCache][0] )
	{
		--pxStack;

		// To prevent unnecessary copying of BBs, we use the BB on the stack as 
		// our left bounding box.
		Asura_Bounding_Box xRightBB = pxStack->m_xBB;

		const u_int uNodeIndex = pxStack->m_uIndex;
        const Asura_LBAABB_Tree_Double_Node& xNode = m_pxNodes[uNodeIndex >> 1];
		AdjustBoundingBoxes(xNode.m_aacElements[uNodeIndex & 1], pxStack->m_xBB, xRightBB);

		float fLeftDistance = *pfDistance;
		bool bLeftHit = Fast_RayIntersectsBoundingBox( xRayOrigin, xRayDirection, pxStack->m_xBB, fLeftDistance);

		float fRightDistance = *pfDistance;
		bool bRightHit = Fast_RayIntersectsBoundingBox( xRayOrigin, xRayDirection, xRightBB, fRightDistance);

		const u_int uLeftIndex  = 2 * pxStack->m_uIndex + 1;
		const u_int uRightIndex = uLeftIndex + 1;

		const bool bLeftFirst = (bLeftHit && bRightHit) && (fLeftDistance<fRightDistance);

		// if the left is nearer and a leaf, let's find the distance to the leaf
		if (bLeftFirst && uLeftIndex >= m_uNumberOfNodes )
		{
			const u_int uLeaf = uLeftIndex - m_uNumberOfNodes;
			pfnRayTestCallback( uLeaf );

			// we're finished with this leaf
			bLeftHit = false;
			// Check to see if right hit distance is still smaller than current distance.
			bRightHit &= (*pfDistance > fRightDistance);
		}


		// if right is leaf, let's find the distance to the leaf
		if (bRightHit && uRightIndex >= m_uNumberOfNodes )
		{
			const u_int uLeaf =  uRightIndex - m_uNumberOfNodes ;
			pfnRayTestCallback( uLeaf );
	
			// we're finished with this leaf
			bRightHit = false;

			// is the left node still valid?
			bLeftHit &= (*pfDistance > fLeftDistance);
		}

		// do we still have the left node/leaf to consider?
		if (bLeftHit && !bLeftFirst)
		{
			// if it's a leaf, test it
			if ( uLeftIndex >= m_uNumberOfNodes )
			{
				const u_int uLeaf =  uLeftIndex - m_uNumberOfNodes ;
				pfnRayTestCallback( uLeaf );
				// If left is leaf, we know that the right is also a leaf so we're done.
				continue;
			}
			// otherwise it's a node, so add it to the stack (before right node)
			else
			{
				pxStack->m_uIndex = uLeftIndex;
				++pxStack;
			}
		}
	
		if (bRightHit)
		{
			// if we're still considering right node, add it to the stack
			// This is complicated slightly by the fact our left BB is stored there.
			pxStack->m_uIndex = uRightIndex;
			(pxStack+1)->m_xBB = pxStack->m_xBB;
			pxStack->m_xBB = xRightBB;
			++pxStack;
		}

		// and similarly for the left node
		if (bLeftHit && bLeftFirst)
		{
			pxStack->m_uIndex = uLeftIndex;
			++pxStack;
		}
	}
}

static inline bool TestBBVertDown(const Asura_Vector_3& xRayOrigin, const Asura_Bounding_Box& xBB, float& fDistance)
{
	if (xRayOrigin.x >= xBB.MinX &&
		 xRayOrigin.x <= xBB.MaxX &&
		 xRayOrigin.z >= xBB.MinZ &&
		 xRayOrigin.z <= xBB.MaxZ &&
		 xRayOrigin.y <= xBB.MaxY &&
		 xRayOrigin.y + fDistance >= xBB.MinY)
	{
		fDistance = Asura_Maths::Max(0.0f, xBB.MinY - xRayOrigin.y);
		return true;
	}
	return false;
}


void Asura_LBAABB_Tree::TestTreeWithRay_VertDown( const Asura_Vector_3& xRayOrigin, float* pfDistance, void(*pfnRayTestCallback)( const u_int uIndex ), const u_int uCache/* = 0*/ ) const
{
	Asura_LBAABB_Tree_StackElement* pxStack = &g_axStack[uCache][0];

	pxStack->m_uIndex = 0;
	pxStack->m_xBB = m_xRootBoundingBox;
	++pxStack;

	while (pxStack != &g_axStack[uCache][0] )
	{
		--pxStack;

		// To prevent unnecessary copying of BBs, we use the BB on the stack as 
		// our left bounding box.
		Asura_Bounding_Box xRightBB = pxStack->m_xBB;

		const u_int uNodeIndex = pxStack->m_uIndex;
        const Asura_LBAABB_Tree_Double_Node& xNode = m_pxNodes[uNodeIndex >> 1];
		AdjustBoundingBoxes(xNode.m_aacElements[uNodeIndex & 1], pxStack->m_xBB, xRightBB);

		float fLeftDistance = *pfDistance;
		bool bLeftHit = TestBBVertDown( xRayOrigin, pxStack->m_xBB, fLeftDistance);

		float fRightDistance = *pfDistance;
		bool bRightHit = TestBBVertDown( xRayOrigin, xRightBB, fRightDistance);

		const u_int uLeftIndex  = 2 * pxStack->m_uIndex + 1;
		const u_int uRightIndex = uLeftIndex + 1;

		const bool bLeftFirst = (bLeftHit && bRightHit) && (fLeftDistance<fRightDistance);

		// if the left is nearer and a leaf, let's find the distance to the leaf
		if (bLeftFirst && uLeftIndex >= m_uNumberOfNodes )
		{
			const u_int uLeaf = uLeftIndex - m_uNumberOfNodes;
			pfnRayTestCallback( uLeaf );

			// we're finished with this leaf
			bLeftHit = false;
			// Check to see if right hit distance is still smaller than current distance.
			bRightHit &= (*pfDistance > fRightDistance);
		}


		// if right is leaf, let's find the distance to the leaf
		if (bRightHit && uRightIndex >= m_uNumberOfNodes )
		{
			const u_int uLeaf =  uRightIndex - m_uNumberOfNodes ;
			pfnRayTestCallback( uLeaf );
	
			// we're finished with this leaf
			bRightHit = false;

			// is the left node still valid?
			bLeftHit &= (*pfDistance > fLeftDistance);
		}

		// do we still have the left node/leaf to consider?
		if (bLeftHit && !bLeftFirst)
		{
			// if it's a leaf, test it
			if ( uLeftIndex >= m_uNumberOfNodes )
			{
				const u_int uLeaf =  uLeftIndex - m_uNumberOfNodes ;
				pfnRayTestCallback( uLeaf );
				// If left is leaf, we know that the right is also a leaf so we're done.
				continue;
			}
			// otherwise it's a node, so add it to the stack (before right node)
			else
			{
				pxStack->m_uIndex = uLeftIndex;
				++pxStack;
			}
		}
	
		if (bRightHit)
		{
			// if we're still considering right node, add it to the stack
			// This is complicated slightly by the fact our left BB is stored there.
			pxStack->m_uIndex = uRightIndex;
			(pxStack+1)->m_xBB = pxStack->m_xBB;
			pxStack->m_xBB = xRightBB;
			++pxStack;
		}

		// and similarly for the left node
		if (bLeftHit && bLeftFirst)
		{
			pxStack->m_uIndex = uLeftIndex;
			++pxStack;
		}
	}
}

#ifdef ASURA_TOOLS	
////////////////////////////////////////////////////////////
//  TODO - move to Tools file?
////////////////////////////////////////////////////////////

#include "Core/Asura_PlatformBasics.h" // using qsort


u_int*						Tools_LBAABB_Tree::s_puLeafArray;
u_int*						Tools_LBAABB_Tree::s_puLeafArraySortedInX;
u_int*						Tools_LBAABB_Tree::s_puLeafArraySortedInY;
u_int*						Tools_LBAABB_Tree::s_puLeafArraySortedInZ;
const Asura_Bounding_Box*	Tools_LBAABB_Tree::s_pxLeafBBs;
const Asura_Vector_3*		Tools_LBAABB_Tree::s_pxLeafCentres;

Tools_LBAABB_Tree::Tools_LBAABB_Tree( const u_int uNumberOfLeaves, const Asura_Bounding_Box* pxLeafBBs, const Asura_Vector_3* pxLeafCentres )
{
	Asura_ResourcePushType(ASURA_RESOURCE_MODULE);
	{
		// initialise
		m_pxNodes = 0;
		m_uNumberOfNodes = uNumberOfLeaves - 1;
		m_xRootBoundingBox.Reset();

		if ( uNumberOfLeaves == 0 )
		{
			Asura_Assert( false, "Trying to make a tree with zero leaves" );
		}
		// "n" leaves means we need "n-1" nodes
		else if ( m_uNumberOfNodes == 0 )
		{
			m_xRootBoundingBox = pxLeafBBs[0];

			// allocate and initialise run-time tree
			m_pxRunTimeTree = new Asura_LBAABB_Tree;

			m_pxRunTimeTree->m_uNumberOfNodes = m_uNumberOfNodes;
			m_pxRunTimeTree->m_xRootBoundingBox = m_xRootBoundingBox;
			m_pxRunTimeTree->m_pxNodes = 0;
			m_puLeafTranslationArray =  new u_int[1];
			m_puLeafTranslationArray[0] = 0;
		}
		else
		{
			Asura_ResourceAllocateArray(m_pxNodes, m_uNumberOfNodes);

			for ( u_int u=0; u<m_uNumberOfNodes; u++ )
			{
				Tools_LBAABB_Tree_Node& xNode = m_pxNodes[u];

				const u_int uLeft  = 2 * u + 1;

				if ( uLeft >= m_uNumberOfNodes )
				{
					xNode.m_uLeftIndex = 0xffffffff;
					xNode.m_bLeftIsLeaf = true;
				}
				else
				{
					xNode.m_uLeftIndex = uLeft;
					xNode.m_bLeftIsLeaf = false;
				}

				const u_int uRight = 2 * u + 2;

				if ( uRight >= m_uNumberOfNodes )
				{
					xNode.m_uRightIndex = 0xffffffff;
					xNode.m_bRightIsLeaf = true;
				}
				else
				{
					xNode.m_uRightIndex = uRight;
					xNode.m_bRightIsLeaf = false;
				}
			}

			for ( u_int u=m_uNumberOfNodes; u>0; u-- )
			{
				Tools_LBAABB_Tree_Node& xNode = m_pxNodes[u-1];

				if (xNode.m_bLeftIsLeaf)
				{
					xNode.m_uNumberOfLeavesToLeft = 1;
				}
				else
				{
					u_int uLeftNode = xNode.m_uLeftIndex;
					xNode.m_uNumberOfLeavesToLeft = m_pxNodes[uLeftNode].m_uNumberOfLeavesToLeft + m_pxNodes[uLeftNode].m_uNumberOfLeavesToRight;
				}


				if (xNode.m_bRightIsLeaf)
				{
					xNode.m_uNumberOfLeavesToRight = 1;
				}
				else
				{
					u_int uRightNode = xNode.m_uRightIndex;
					xNode.m_uNumberOfLeavesToRight = m_pxNodes[uRightNode].m_uNumberOfLeavesToLeft + m_pxNodes[uRightNode].m_uNumberOfLeavesToRight;
				}
			}

			s_pxLeafBBs = pxLeafBBs;
			s_pxLeafCentres = pxLeafCentres;

			s_puLeafArraySortedInX = new u_int[uNumberOfLeaves];
			s_puLeafArraySortedInY = new u_int[uNumberOfLeaves];
			s_puLeafArraySortedInZ = new u_int[uNumberOfLeaves];

			s_puLeafArray = new u_int[uNumberOfLeaves];

			for (u_int u=0; u<uNumberOfLeaves; u++)
			{
				s_puLeafArray[u] = u;

				m_xRootBoundingBox.Set( s_pxLeafBBs[u] );
			}


			// allocate and initialise run-time tree
			m_pxRunTimeTree = new Asura_LBAABB_Tree;

			m_pxRunTimeTree->m_uNumberOfNodes = m_uNumberOfNodes;
			m_pxRunTimeTree->m_xRootBoundingBox = m_xRootBoundingBox;
			Asura_Assert(m_pxRunTimeTree->GetNumberOfDoubleNodes() != 0, "Should have already exitted this function");
			Asura_ResourceAllocateArray(m_pxRunTimeTree->m_pxNodes, m_pxRunTimeTree->GetNumberOfDoubleNodes());


			SortNodes( 0, 0, m_uNumberOfNodes, m_xRootBoundingBox );

			delete [] s_puLeafArraySortedInX;
			delete [] s_puLeafArraySortedInY;
			delete [] s_puLeafArraySortedInZ;
			delete [] s_puLeafArray;

			m_puLeafTranslationArray =  new u_int[uNumberOfLeaves];

			for (u_int u=0; u<m_uNumberOfNodes; u++)
			{
				Tools_LBAABB_Tree_Node& xNode = m_pxNodes[u];

				if (xNode.m_bLeftIsLeaf)
				{
					u_int uIndex = 2 * u + 1 - m_uNumberOfNodes;

					m_puLeafTranslationArray[ uIndex ] = xNode.m_uLeftIndex;
				}
				if (xNode.m_bRightIsLeaf)
				{
					u_int uIndex = 2 * u + 2 - m_uNumberOfNodes;

					m_puLeafTranslationArray[ uIndex ] = xNode.m_uRightIndex;
				}
			}
			Asura_ResourceDeallocateArray(m_pxNodes);
		}
	}
	Asura_ResourcePopType();
}

Tools_LBAABB_Tree::~Tools_LBAABB_Tree()
{
	delete m_pxRunTimeTree;
}

static inline void FillRuntimeNode(const Asura_Bounding_Box& xParentBB, const Asura_Bounding_Box& xLeftBB, const Asura_Bounding_Box& xRightBB, char* pcArray)
{
	int iLeftValues[3];
	int iRightValues[3];
	for (int i=0;i<3;i++)
	{
		int iMinElement = i * 2;
		int iMaxElement = iMinElement + 1;
		float fParentDiff = xParentBB.m_fElement[iMaxElement] - xParentBB.m_fElement[iMinElement];
		if (fParentDiff < 0.001f)
		{
			// Avoid divide-by-zero trouble.
			fParentDiff = Asura_Maths::LargeFloat;
		}
		{
			// Left
			float fLeftNeg = (xParentBB.m_fElement[iMaxElement] - xLeftBB.m_fElement[iMaxElement]) / fParentDiff;
			float fLeftPos = (xLeftBB.m_fElement[iMinElement] - xParentBB.m_fElement[iMinElement]) / fParentDiff;

			float fValue = (fLeftNeg > fLeftPos) ? -fLeftNeg : fLeftPos;
			iLeftValues[i] = Asura_Maths::FloatToInt_Chop(fValue * fCOMPRESSION_SCALE);
		}

		{
			// Right
			float fRightNeg = (xParentBB.m_fElement[iMaxElement] - xRightBB.m_fElement[iMaxElement]) / fParentDiff;
			float fRightPos = (xRightBB.m_fElement[iMinElement] - xParentBB.m_fElement[iMinElement]) / fParentDiff;

			float fValue = (fRightNeg > fRightPos) ? -fRightNeg : fRightPos;
			iRightValues[i] = Asura_Maths::FloatToInt_Chop(fValue * fCOMPRESSION_SCALE);
		}
	}


	// (AW - 22/08/05) - Had some trouble with floating point inaccuracy in this process when reducing a 
	// bounding box to nothing (overshot slightly resulting in MinZ > MaxZ. Solution is to clamp to reduced
	// range here, it can be fixed up in the trial-and-error bit later on.
	const int iTempMin = iMIN_VALUE + 2;
	const int iTempMax = iMAX_VALUE - 1;
	pcArray[ASURA_LBAABB_LEFT_OFFSET_X] = static_cast<char>(Asura_Maths::ClampToRange(iLeftValues[0], iTempMin, iTempMax));
	pcArray[ASURA_LBAABB_LEFT_OFFSET_Y] = static_cast<char>(Asura_Maths::ClampToRange(iLeftValues[1], iTempMin, iTempMax));
	pcArray[ASURA_LBAABB_LEFT_OFFSET_Z] = static_cast<char>(Asura_Maths::ClampToRange(iLeftValues[2], iTempMin, iTempMax));

	pcArray[ASURA_LBAABB_RIGHT_OFFSET_X] = static_cast<char>(Asura_Maths::ClampToRange(iRightValues[0], iTempMin, iTempMax));
	pcArray[ASURA_LBAABB_RIGHT_OFFSET_Y] = static_cast<char>(Asura_Maths::ClampToRange(iRightValues[1], iTempMin, iTempMax));
	pcArray[ASURA_LBAABB_RIGHT_OFFSET_Z] = static_cast<char>(Asura_Maths::ClampToRange(iRightValues[2], iTempMin, iTempMax));
}



void Tools_LBAABB_Tree::SortNodes( const u_int uCurrentNode, const u_int uStartLeaf, const u_int uEndLeaf, const Asura_Bounding_Box& xParentBB )
{
	Tools_LBAABB_Tree_Node& xNode = m_pxNodes[uCurrentNode];
	
	const u_int uRequiredLeavesToLeft = xNode.m_uNumberOfLeavesToLeft;

	const u_int uNumberOfLeaves = uEndLeaf - uStartLeaf + 1;

	Asura_Assert ( uRequiredLeavesToLeft + xNode.m_uNumberOfLeavesToRight == uNumberOfLeaves, "Leaves mismatch" );

	// Create sorted arrays for the three axes we might split the tree along.
	// (AW - 17/08/05) - Might we gain by also considering the 4 diagonals?
	Asura_Mem::Copy( s_puLeafArraySortedInX + uStartLeaf, s_puLeafArray + uStartLeaf, sizeof(u_int) * uNumberOfLeaves );
	Asura_Mem::Copy( s_puLeafArraySortedInY + uStartLeaf, s_puLeafArray + uStartLeaf, sizeof(u_int) * uNumberOfLeaves );
	Asura_Mem::Copy( s_puLeafArraySortedInZ + uStartLeaf, s_puLeafArray + uStartLeaf, sizeof(u_int) * uNumberOfLeaves );

	qsort( s_puLeafArraySortedInX + uStartLeaf, uNumberOfLeaves, sizeof(u_int), CompareForLeavesInX );
	qsort( s_puLeafArraySortedInY + uStartLeaf, uNumberOfLeaves, sizeof(u_int), CompareForLeavesInY );
	qsort( s_puLeafArraySortedInZ + uStartLeaf, uNumberOfLeaves, sizeof(u_int), CompareForLeavesInZ );

	Asura_Bounding_Box xLeftBB[3], xRightBB[3], xNodeBB;

	xNodeBB.Reset();

	for ( u_int v=0; v<3; v++ )
	{	
		xLeftBB[v].Reset();
		xRightBB[v].Reset();
	}

	for ( u_int u=uStartLeaf; u<uStartLeaf+uRequiredLeavesToLeft; u++ )
	{
//		float fCentreX = s_pxLeafCentres[ s_puLeafArraySortedInX[u] ].x;
//		float fCentreY = s_pxLeafCentres[ s_puLeafArraySortedInY[u] ].y;
//		float fCentreZ = s_pxLeafCentres[ s_puLeafArraySortedInZ[u] ].z;
		xLeftBB[0].Set( s_pxLeafBBs[ s_puLeafArraySortedInX[u] ] );
		xLeftBB[1].Set( s_pxLeafBBs[ s_puLeafArraySortedInY[u] ] );
		xLeftBB[2].Set( s_pxLeafBBs[ s_puLeafArraySortedInZ[u] ] );
	}

	for ( u_int u=uStartLeaf+uRequiredLeavesToLeft; u<= uEndLeaf; u++ )
	{
		xRightBB[0].Set( s_pxLeafBBs[ s_puLeafArraySortedInX[u] ] );
		xRightBB[1].Set( s_pxLeafBBs[ s_puLeafArraySortedInY[u] ] );
		xRightBB[2].Set( s_pxLeafBBs[ s_puLeafArraySortedInZ[u] ] );
	}

	xNodeBB.Set( xLeftBB[0] );
	xNodeBB.Set( xRightBB[0] );

	// Try all three axes and see which gives the best score.
	float afScore[3];
	for (int i=0;i<3;i++)
	{
		Asura_LBAABB_Tree_Double_Node& xTempNode = m_pxRunTimeTree->m_pxNodes[uCurrentNode >> 1];
		char *pcArrayPointer = xTempNode.m_aacElements[uCurrentNode & 1];
		FillRuntimeNode(xParentBB, xLeftBB[i], xRightBB[i], pcArrayPointer);
		Asura_Bounding_Box xTempEstimatedLeftBB = xParentBB;
		Asura_Bounding_Box xTempEstimatedRightBB = xParentBB;
		AdjustBoundingBoxes(pcArrayPointer, xTempEstimatedLeftBB, xTempEstimatedRightBB);

		// This heuristic is quite important in terms of results.
#if 0
		//
		// **** Minimise total bounding box surface area ****
		//
		afScore[i] = xTempEstimatedLeftBB.GetSurfaceArea() + xTempEstimatedRightBB.GetSurfaceArea();
#elif (0)
		//
		// **** Minimise total volume ****
		//
		afScore[i] = xTempEstimatedLeftBB.GetVolume() * xTempEstimatedRightBB.GetVolume();
#else
		//
		// **** Minimise total bounding box surface area squared ****
		//
		afScore[i] = xTempEstimatedLeftBB.GetSurfaceArea() * xTempEstimatedLeftBB.GetSurfaceArea() + xTempEstimatedRightBB.GetSurfaceArea() * xTempEstimatedRightBB.GetSurfaceArea();
#endif
	}
	u_int uBestAxis = 2;
	if ( afScore[0] < afScore[1] )
	{
		if ( afScore[0] < afScore[2] )
		{
			uBestAxis = 0;
		}
	}
	else if ( afScore[1] < afScore[2] )
	{
		uBestAxis = 1;
	}

	switch ( uBestAxis )
	{
		default:	
		case 0:
		{
			Asura_Mem::Copy( s_puLeafArray + uStartLeaf, s_puLeafArraySortedInX + uStartLeaf, sizeof(u_int) * uNumberOfLeaves );
			break;
		}
		case 1:
		{
			Asura_Mem::Copy( s_puLeafArray + uStartLeaf, s_puLeafArraySortedInY + uStartLeaf, sizeof(u_int) * uNumberOfLeaves );
			break;
		}
		case 2:
		{
			Asura_Mem::Copy( s_puLeafArray + uStartLeaf, s_puLeafArraySortedInZ + uStartLeaf, sizeof(u_int) * uNumberOfLeaves );
			break;
		}
	}
	// fill out the run-time node
	Asura_LBAABB_Tree_Double_Node& xRTNode = m_pxRunTimeTree->m_pxNodes[uCurrentNode >> 1];

	// Calculate the values for the node.
	char *pcArrayPointer = xRTNode.m_aacElements[uCurrentNode & 1];
	FillRuntimeNode(xParentBB, xLeftBB[uBestAxis], xRightBB[uBestAxis], pcArrayPointer);

	// Work out the output from the node.
	Asura_Bounding_Box xRTEstimatedLeftBB = xParentBB;
	Asura_Bounding_Box xRTEstimatedRightBB = xParentBB;
	AdjustBoundingBoxes(pcArrayPointer, xRTEstimatedLeftBB, xRTEstimatedRightBB);

	if(!xRTEstimatedLeftBB.Contains(xLeftBB[uBestAxis]) || !xRTEstimatedRightBB.Contains(xRightBB[uBestAxis]))
	{
		//Very occasionally the decompressed bounding boxes don't quite contain the left/right bounding boxes , but
		//are off by a minute amount as a result of numerical innaccuracies.
		//Try adjusting the appropriate compressed values by one to widen the boxes to fix this.
		//RAR 17/01/2008
		if(xRTEstimatedLeftBB.MinX>xLeftBB[uBestAxis].MinX) pcArrayPointer[ASURA_LBAABB_LEFT_OFFSET_X]--;
		else if(xRTEstimatedLeftBB.MaxX<xLeftBB[uBestAxis].MaxX) pcArrayPointer[ASURA_LBAABB_LEFT_OFFSET_X]++;

		if(xRTEstimatedLeftBB.MinY>xLeftBB[uBestAxis].MinY) pcArrayPointer[ASURA_LBAABB_LEFT_OFFSET_Y]--;
		else if(xRTEstimatedLeftBB.MaxY<xLeftBB[uBestAxis].MaxY) pcArrayPointer[ASURA_LBAABB_LEFT_OFFSET_Y]++;

		if(xRTEstimatedLeftBB.MinZ>xLeftBB[uBestAxis].MinZ) pcArrayPointer[ASURA_LBAABB_LEFT_OFFSET_Z]--;
		else if(xRTEstimatedLeftBB.MaxZ<xLeftBB[uBestAxis].MaxZ) pcArrayPointer[ASURA_LBAABB_LEFT_OFFSET_Z]++;

		if(xRTEstimatedRightBB.MinX>xRightBB[uBestAxis].MinX) pcArrayPointer[ASURA_LBAABB_RIGHT_OFFSET_X]--;
		else if(xRTEstimatedRightBB.MaxX<xRightBB[uBestAxis].MaxX) pcArrayPointer[ASURA_LBAABB_RIGHT_OFFSET_X]++;

		if(xRTEstimatedRightBB.MinY>xRightBB[uBestAxis].MinY) pcArrayPointer[ASURA_LBAABB_RIGHT_OFFSET_Y]--;
		else if(xRTEstimatedRightBB.MaxY<xRightBB[uBestAxis].MaxY) pcArrayPointer[ASURA_LBAABB_RIGHT_OFFSET_Y]++;

		if(xRTEstimatedRightBB.MinZ>xRightBB[uBestAxis].MinZ) pcArrayPointer[ASURA_LBAABB_RIGHT_OFFSET_Z]--;
		else if(xRTEstimatedRightBB.MaxZ<xRightBB[uBestAxis].MaxZ) pcArrayPointer[ASURA_LBAABB_RIGHT_OFFSET_Z]++;

		//Check to see if the BBs are now fixed
		xRTEstimatedLeftBB = xParentBB;
		xRTEstimatedRightBB = xParentBB;
		AdjustBoundingBoxes(pcArrayPointer, xRTEstimatedLeftBB, xRTEstimatedRightBB);
		
		Asura_Assertf(xRTEstimatedLeftBB.Contains(xLeftBB[uBestAxis]), ("Error calculating LBAABB tree.\n (%f %f) (%f %f) (%f %f)\n (%f %f) (%f %f) (%f %f)", 
		xRTEstimatedLeftBB.MinX, xRTEstimatedLeftBB.MaxX, xRTEstimatedLeftBB.MinY, xRTEstimatedLeftBB.MaxY, xRTEstimatedLeftBB.MinZ, xRTEstimatedLeftBB.MaxZ,
		xLeftBB[uBestAxis].MinX, xLeftBB[uBestAxis].MaxX, xLeftBB[uBestAxis].MinY, xLeftBB[uBestAxis].MaxY, xLeftBB[uBestAxis].MinZ, xLeftBB[uBestAxis].MaxZ
		));

		Asura_Assertf(xRTEstimatedRightBB.Contains(xRightBB[uBestAxis]), ("Error calculating LBAABB tree.\n (%f %f) (%f %f) (%f %f)\n (%f %f) (%f %f) (%f %f)", 
		xRTEstimatedRightBB.MinX, xRTEstimatedRightBB.MaxX, xRTEstimatedRightBB.MinY, xRTEstimatedRightBB.MaxY, xRTEstimatedRightBB.MinZ, xRTEstimatedRightBB.MaxZ,
		xRightBB[uBestAxis].MinX, xRightBB[uBestAxis].MaxX, xRightBB[uBestAxis].MinY, xRightBB[uBestAxis].MaxY, xRightBB[uBestAxis].MinZ, xRightBB[uBestAxis].MaxZ
		));
	}
	

	// Check if we've been too conservative.
	// This code originally asserted if we were too conservative, however, it kept firing and I don't 
	// have time to look into why. I'm just going to allow this to correct the calculations in an iterative
	// process which should get the exact right result without me having to figure out where my code is wrong.
	// Hardly ideal - but works well.
	const int iMaxIterations = 16;
	for (int j=0;j<iMaxIterations;j++)
	{
		bool bBreak = true;
		for (int i=0;i<3;i++)
		{
			char acTempArray[6];
			for (int k=0;k<6;k++)
			{
				acTempArray[k] = pcArrayPointer[k];
			}
			acTempArray[i] = static_cast<char>(Asura_Maths::ClampToRange(acTempArray[i] + Asura_Maths::Sign(acTempArray[i]), iMIN_VALUE, iMAX_VALUE));
			acTempArray[i + 3] = static_cast<char>(Asura_Maths::ClampToRange(acTempArray[i + 3] + Asura_Maths::Sign(acTempArray[i + 3]), iMIN_VALUE, iMAX_VALUE));

			Asura_Bounding_Box xRTEstimatedLeftBB = xParentBB;
			Asura_Bounding_Box xRTEstimatedRightBB = xParentBB;
			AdjustBoundingBoxes(acTempArray, xRTEstimatedLeftBB, xRTEstimatedRightBB);

			if (xRTEstimatedLeftBB.Contains(xLeftBB[uBestAxis]))
			{
				if (pcArrayPointer[i] != acTempArray[i])
				{
					pcArrayPointer[i] = acTempArray[i];
					bBreak = false;
				}
			}

			if (xRTEstimatedRightBB.Contains(xRightBB[uBestAxis]))
			{
				if (pcArrayPointer[i + 3] != acTempArray[i + 3])
				{
					pcArrayPointer[i + 3] = acTempArray[i + 3];
					bBreak = false;
				}
			}
		}
		if (bBreak)
		{
			break;
		}
		else
		{
			// (AW - 07/10/05) - Discovered that this assertion can fire when geometry is far from the
			// origin and fp-accuracy causes issues. The geometry in question was 100,000 metres away 
			// from the origin (EA's mesh), I recommend art fixes in this case.
			Asura_Assert(j < iMaxIterations - 1, "Original estimate far too conservative. May be caused by geometry very far away from the origin.");
		}
	}

	// Test we didn't break anything.
	xRTEstimatedLeftBB = xRTEstimatedRightBB = xParentBB;
	AdjustBoundingBoxes(pcArrayPointer, xRTEstimatedLeftBB, xRTEstimatedRightBB);
	Asura_Assertf(xRTEstimatedLeftBB.Contains(xLeftBB[uBestAxis]), ("Error calculating LBAABB tree.\n (%f %f) (%f %f) (%f %f)\n (%f %f) (%f %f) (%f %f)", 
		xRTEstimatedLeftBB.MinX, xRTEstimatedLeftBB.MaxX, xRTEstimatedLeftBB.MinY, xRTEstimatedLeftBB.MaxY, xRTEstimatedLeftBB.MinZ, xRTEstimatedLeftBB.MaxZ,
		xLeftBB[uBestAxis].MinX, xLeftBB[uBestAxis].MaxX, xLeftBB[uBestAxis].MinY, xLeftBB[uBestAxis].MaxY, xLeftBB[uBestAxis].MinZ, xLeftBB[uBestAxis].MaxZ
		));
	Asura_Assertf(xRTEstimatedRightBB.Contains(xRightBB[uBestAxis]), ("Error calculating LBAABB tree.\n (%f %f) (%f %f) (%f %f)\n (%f %f) (%f %f) (%f %f)", 
		xRTEstimatedRightBB.MinX, xRTEstimatedRightBB.MaxX, xRTEstimatedRightBB.MinY, xRTEstimatedRightBB.MaxY, xRTEstimatedRightBB.MinZ, xRTEstimatedRightBB.MaxZ,
		xRightBB[uBestAxis].MinX, xRightBB[uBestAxis].MaxX, xRightBB[uBestAxis].MinY, xRightBB[uBestAxis].MaxY, xRightBB[uBestAxis].MinZ, xRightBB[uBestAxis].MaxZ
		));

	if ( !xNode.m_bLeftIsLeaf )
	{
		SortNodes( xNode.m_uLeftIndex, uStartLeaf, uStartLeaf+uRequiredLeavesToLeft-1, xRTEstimatedLeftBB );
	}
	else
	{
		Asura_Assert ( uRequiredLeavesToLeft == 1, "more than one leaf left" );
		xNode.m_uLeftIndex = s_puLeafArray[uStartLeaf];

	}

	if ( !xNode.m_bRightIsLeaf )
	{
		SortNodes( xNode.m_uRightIndex, uStartLeaf+uRequiredLeavesToLeft, uEndLeaf, xRTEstimatedRightBB );
	}
	else
	{
		Asura_Assert ( uStartLeaf + uRequiredLeavesToLeft == uEndLeaf, "more than one leaf left" );
		xNode.m_uRightIndex = s_puLeafArray[uEndLeaf];
	
	}

}

int Tools_LBAABB_Tree::CompareForLeavesInX( const void *pC1, const void *pC2 )
{
	const u_int uIndex1 = *(const u_int*)(pC1);
	const u_int uIndex2 = *(const u_int*)(pC2);

	const Asura_Vector_3& xV1 = s_pxLeafCentres[uIndex1];
	const Asura_Vector_3& xV2 = s_pxLeafCentres[uIndex2];

	if (xV1.x > xV2.x)
		return 1;
	if (xV1.x < xV2.x)
		return -1;

	return 0;
}

int Tools_LBAABB_Tree::CompareForLeavesInY( const void *pC1, const void *pC2 )
{
	const u_int uIndex1 = *(const u_int*)(pC1);
	const u_int uIndex2 = *(const u_int*)(pC2);

	const Asura_Vector_3& xV1 = s_pxLeafCentres[uIndex1];
	const Asura_Vector_3& xV2 = s_pxLeafCentres[uIndex2];

	if (xV1.y > xV2.y)
		return 1;
	if (xV1.y < xV2.y)
		return -1;

	return 0;
}

int Tools_LBAABB_Tree::CompareForLeavesInZ( const void *pC1, const void *pC2 )
{ 
	const u_int uIndex1 = *(const u_int*)(pC1);
	const u_int uIndex2 = *(const u_int*)(pC2);

	const Asura_Vector_3& xV1 = s_pxLeafCentres[uIndex1];
	const Asura_Vector_3& xV2 = s_pxLeafCentres[uIndex2];

	if (xV1.z > xV2.z)
		return 1;
	if (xV1.z < xV2.z)
		return -1;

	return 0;
}

#endif // ASURA_TOOLS



////////////////////////////////////////////////////////////////////////////////
// Function     : Asura_LBAABB_Tree_Node::ReadFromChunkStream
// Author       : Andy Tate
// Date         : 14-Jul-2005
//
// Description  : Reads the tree-node data from the specified chunk stream.
//
// Parameters   : A reference to the chunk-stream to read from.
//
// Return value : None.
////////////////////////////////////////////////////////////////////////////////

void Asura_LBAABB_Tree_Double_Node::ReadFromChunkStream (Asura_Chunk_Stream& xStream)
{
	Asura_ReadFromStream_Array_Wrapper<char>	xArrayWrapper (12, m_acElements);


	// Read the data...

	xStream >> xArrayWrapper;
}

/// End of function 'Asura_LBAABB_Tree_Node::ReadFromChunkStream'. ///



////////////////////////////////////////////////////////////////////////////////
// Function     : Asura_LBAABB_Tree_Node::WriteToChunkStream
// Author       : Andy Tate
// Date         : 14-Jul-2005
//
// Description  : Writes the tree-node data to the specified chunk stream.
//
// Parameters   : A reference to the chunk-stream to write to.
//
// Return value : None.
////////////////////////////////////////////////////////////////////////////////

void Asura_LBAABB_Tree_Double_Node::WriteToChunkStream (Asura_Chunk_Stream& xStream) const
{
	Asura_WriteToStream_Array_Wrapper<char>	xArrayWrapper(12, m_acElements);


	// Write the data...

	xStream << xArrayWrapper;
}

/// End of function 'Asura_LBAABB_Tree_Node::WriteToChunkStream'. ///



////////////////////////////////////////////////////////////////////////////////
// Function     : Asura_LBAABB_Tree::ReadHeaderFromChunkStream
// Author       : Andy Tate
// Date         : 14-Jul-2005
//
// Description  : Reads the tree data from the specified chunk-stream.
//
// Parameters   : A reference to the chunk-stream to read from.
//
// Return value : None.
////////////////////////////////////////////////////////////////////////////////

void Asura_LBAABB_Tree::ReadHeaderFromChunkStream (Asura_Chunk_Stream& xStream)
{
	// Read the data...

	xStream >> m_uNumberOfNodes;
   	xStream >> m_xRootBoundingBox;
}

// End of function 'Asura_LBAABB_Tree::ReadFromChunkStream'. ///



////////////////////////////////////////////////////////////////////////////////
// Function     : Asura_LBAABB_Tree::WriteHeaderToChunkStream
// Author       : Andy Tate
// Date         : 14-Jul-2005
//
// Description  : Write the tree data to the specified chunk-stream.
//
// Parameters   : A reference to the chunk-stream to write to.
//
// Return value : None.
////////////////////////////////////////////////////////////////////////////////

void Asura_LBAABB_Tree::WriteHeaderToChunkStream (Asura_Chunk_Stream& xStream,const Asura_Vector_3& xDisplacement) const
{
	// Write the data...

	xStream << m_uNumberOfNodes;

	Asura_Bounding_Box xBB = m_xRootBoundingBox;
	xBB.Displace(xDisplacement);
   	xStream << xBB;
}

// End of function 'Asura_LBAABB_Tree::WriteToChunkStream'. ///


/*
	Read function which reads the header and then
	allocates and reads the nodes from the stream
*/
void Asura_LBAABB_Tree::ReadTreeAndNodesFromChunkStream( Asura_Chunk_Stream& xStream )
{
	ReadHeaderFromChunkStream( xStream );

	unsigned int uNumNodes = GetNumberOfDoubleNodes();

	if ( uNumNodes )
	{

		Asura_ResourceAllocateArray( m_pxNodes, uNumNodes );

		for ( unsigned int n = 0; n < uNumNodes; n++ )
		{
			m_pxNodes[ n ].ReadFromChunkStream( xStream );
		}
	}
	else
	{
		m_pxNodes = NULL;
	}
}


/*
	Write function that writes the header and the
	nodes.
*/
void Asura_LBAABB_Tree::WriteTreeAndNodesToChunkStream( Asura_Chunk_Stream& xStream, const Asura_Vector_3& xDisplacement )
{

	WriteHeaderToChunkStream( xStream, xDisplacement );

	unsigned int uNumNodes = GetNumberOfDoubleNodes();

	for ( unsigned int n = 0; n < uNumNodes; n++ )
	{
		m_pxNodes[ n ].WriteToChunkStream( xStream );
	}

}
