roam.cpp

VC++ DEMO, used for the beginners and the amour

#include "HEADERS.H"
#include "FRUSTUM.H"
#include "CAMERA.H"
#include "ROAM.H"
USING NAMESPACE CGE::MATRIX;
USING NAMESPACE CGE::TERRAIN;
USING NAMESPACE CGE::CULLING;
/////////////////////////////////////////////////////////////////////////////////////
LONG LANDSCAPE::m_NextTriNode = 0;
BinTriangleNode LANDSCAPE::m_TriPool[POOL_SIZE];
std::vector<TRIFACE> PATCH::m_vTriangles;
/////////////////////////////////////////////////////////////////////////////////////
LANDSCAPE::LANDSCAPE()
{
	m_pD3DDevice = NULL;
	m_Frustum = NULL;
	m_pLandTexture = NULL;
	m_pLandVB = NULL;
	m_fXTile = m_fYTile = 0;
	m_fFrameVariance = 0;
	m_nMaxDesiredTris = 0;
}

LANDSCAPE::~LANDSCAPE()
{
	SAFE_RELEASE(m_pLandTexture);
	SAFE_RELEASE(m_pLandVB);
	SAFE_DELETE(m_Frustum);
	free(m_pHeightMap);
}

PATCH::PATCH()
{
	m_CurrentVariance = NULL;
	m_HeightMap = NULL;
	m_ParentLand = 0;
}

PATCH::~PATCH()
{

}

BOOL PATCH::CreatePatch(LANDSCAPE * ParentLand,LONG heightX, LONG heightY, LONG worldX, LONG worldY, BYTE *hMap)
{
	// Clear all the relationships
	m_BaseLeft.RightNeighbour = m_BaseLeft.LeftNeighbour = m_BaseRight.RightNeighbour = m_BaseRight.LeftNeighbour =
	m_BaseLeft.LeftChild = m_BaseLeft.RightChild = m_BaseRight.LeftChild = m_BaseLeft.LeftChild = NULL;

	// Attach the two m_Base triangles together
	m_BaseLeft.BaseNeighbour = &m_BaseRight;
	m_BaseRight.BaseNeighbour = &m_BaseLeft;

	// Store Patch offsets for the world and heightmap.
	m_WorldX = worldX;
	m_WorldY = worldY;

	// Store pointer to first byte of the height data for this patch.
	m_HeightMap = &hMap[heightY * MAP_SIZE + heightX];

	// Initialize flags
	m_VarianceDirty = 1;

	m_ParentLand = ParentLand;

	return TRUE;
}

BinTriangleNode * LANDSCAPE::AllocateNode()
{
	BinTriangleNode *pTri;

	// IF we've run out of TriTreeNodes, just return NULL (this is handled gracefully)
	if ( m_NextTriNode >= POOL_SIZE )
		return NULL;

	pTri = &(m_TriPool[m_NextTriNode++]);
	pTri->LeftChild = pTri->RightChild = NULL;
	return pTri;
}

VOID PATCH::ComputeVariance()
{
	// Compute variance on each of the base triangles...

	m_CurrentVariance = m_VarianceLeft;
	ComputeVariance(0, PATCH_SIZE, m_HeightMap[PATCH_SIZE * MAP_SIZE],
					PATCH_SIZE, 0,          m_HeightMap[PATCH_SIZE],
					0,          0,          m_HeightMap[0],	1);

	m_CurrentVariance = m_VarianceRight;
	ComputeVariance(PATCH_SIZE, 0, m_HeightMap[ PATCH_SIZE],
					0, PATCH_SIZE, m_HeightMap[ PATCH_SIZE * MAP_SIZE],
					PATCH_SIZE, PATCH_SIZE, m_HeightMap[(PATCH_SIZE * MAP_SIZE) + PATCH_SIZE],
					1);

	// Clear the dirty flag for this patch
	m_VarianceDirty = 0;
}

BYTE PATCH::ComputeVariance(INT leftX, INT leftY, BYTE leftZ, INT rightX, INT rightY, BYTE rightZ, INT apexX, INT apexY, BYTE apexZ, INT node)
{
	//        /|\
	//      /  |  \
	//    /    |    \
	//  /      |      \
	//  ~~~~~~~*~~~~~~~  <-- Compute the X and Y coordinates of '*'
	//
	LONG centerX = (leftX + rightX) >>1;		// Compute X coordinate of center of Hypotenuse
	LONG centerY = (leftY + rightY) >>1;		// Compute Y coord...
	BYTE variance;

	// Get the height value at the middle of the Hypotenuse
	BYTE centerZ  = m_HeightMap[(centerY * MAP_SIZE) + centerX];

	// Variance of this triangle is the actual height at it's hypotenuse midpoint minus the interpolated height.
	// Use values passed on the stack instead of re-accessing the Height Field.
	variance = abs((LONG)centerZ - (((LONG)leftZ + (LONG)rightZ)>>1));

	// Since we're after speed and not perfect representations,
	//    only calculate variance down to an 8x8 block
	if ( (abs(leftX - rightX) >= 8) ||
		 (abs(leftY - rightY) >= 8) )
	{
		// Final Variance for this node is the max of it's own variance and that of it's children.
		variance = max( variance, ComputeVariance( apexX,   apexY,  apexZ, leftX, leftY, leftZ, centerX, centerY, centerZ,    node<<1 ) );
		variance = max( variance, ComputeVariance( rightX, rightY, rightZ, apexX, apexY, apexZ, centerX, centerY, centerZ, 1+(node<<1)) );
	}

	// Store the final variance for this node.  Note Variance is never zero.
	if (node < (1<<VARIANCE_DEPTH))
		m_CurrentVariance[node] = 1 + variance;

	return variance;
}

VOID PATCH::Split(BinTriangleNode *tri)
{
	// We are already split, no need to do it again.
	if (tri->LeftChild)
		return;
	
	// If this triangle is not in a proper diamond, force split our base Neighbour
	if ( tri->BaseNeighbour && (tri->BaseNeighbour->BaseNeighbour != tri) )
		Split(tri->BaseNeighbour);
	
	// Create children and link into mesh
	tri->LeftChild  = LANDSCAPE::AllocateNode();
	tri->RightChild = LANDSCAPE::AllocateNode();
	
	// If creation failed, just exit.
	if ( !tri->LeftChild )
		return;
	
	// Fill in the information we can get from the parent (Neighbour pointers)
	tri->LeftChild->BaseNeighbour  = tri->LeftNeighbour;
	tri->LeftChild->LeftNeighbour  = tri->RightChild;
	
	tri->RightChild->BaseNeighbour  = tri->RightNeighbour;
	tri->RightChild->RightNeighbour = tri->LeftChild;
	
	// Link our Left Neighbour to the new children
	if (tri->LeftNeighbour != NULL)
	{
		if (tri->LeftNeighbour->BaseNeighbour == tri)
			tri->LeftNeighbour->BaseNeighbour = tri->LeftChild;
		else if (tri->LeftNeighbour->LeftNeighbour == tri)
			tri->LeftNeighbour->LeftNeighbour = tri->LeftChild;
		else if (tri->LeftNeighbour->RightNeighbour == tri)
			tri->LeftNeighbour->RightNeighbour = tri->LeftChild;
	}
	
	// Link our Right Neighbour to the new children
	if (tri->RightNeighbour != NULL)
	{
		if (tri->RightNeighbour->BaseNeighbour == tri)
			tri->RightNeighbour->BaseNeighbour = tri->RightChild;
		else if (tri->RightNeighbour->RightNeighbour == tri)
			tri->RightNeighbour->RightNeighbour = tri->RightChild;
		else if (tri->RightNeighbour->LeftNeighbour == tri)
			tri->RightNeighbour->LeftNeighbour = tri->RightChild;
	}
	
	// Link our Base Neighbour to the new children
	if (tri->BaseNeighbour != NULL)
	{
		if ( tri->BaseNeighbour->LeftChild )
		{
			tri->BaseNeighbour->LeftChild->RightNeighbour = tri->RightChild;
			tri->BaseNeighbour->RightChild->LeftNeighbour = tri->LeftChild;
			tri->LeftChild->RightNeighbour = tri->BaseNeighbour->RightChild;
			tri->RightChild->LeftNeighbour = tri->BaseNeighbour->LeftChild;
		}
		else
			Split( tri->BaseNeighbour);  // Base Neighbour (in a diamond with us) was not split yet, so do that now.
	}
	else
	{
		// An edge triangle, trivial case.
		tri->LeftChild->RightNeighbour = NULL;
		tri->RightChild->LeftNeighbour = NULL;
	}
}

VOID LANDSCAPE::SetNewFrame(LPFRUSTUM Frustum)
{
	LONG X, Y;
	PATCH *patch;
	if ( Frustum == NULL )
	{
		Frustum = new CULLING::FRUSTUM;
		Frustum->CalculateFrustum(m_pD3DDevice,0.0f);
		m_Frustum = Frustum;
	}

	// Set the next free triangle pointer back to the beginning
	SetNextTriNode(0);
	// Go through the patches performing resets, compute variances, and linking.
	for ( Y=0; Y < NUM_PATCHES_PER_SIDE; Y++ )
	{
		for ( X=0; X < NUM_PATCHES_PER_SIDE; X++)
		{
			patch = &(m_vPatches[Y][X]);
			
			// Reset the patch
			patch->Reset();
			// Check to see if this patch has been deformed since last frame.
			// If so, recompute the varience tree for it.
			if ( patch->IsDirty() )
			{
				patch->ComputeVariance();
			}

			if ( patch->IsVisible() )
			{
				// Link all the patches together.
				if ( X > 0 )
					patch->GetBaseLeft()->LeftNeighbour = m_vPatches[Y][X-1].GetBaseRight();
				else
					patch->GetBaseLeft()->LeftNeighbour = NULL;		// Link to bordering Landscape here..
				
				if ( X < (NUM_PATCHES_PER_SIDE-1) )
					patch->GetBaseRight()->LeftNeighbour = m_vPatches[Y][X+1].GetBaseLeft();
				else
					patch->GetBaseRight()->LeftNeighbour = NULL;		// Link to bordering Landscape here..
				
				if ( Y > 0 )
					patch->GetBaseLeft()->RightNeighbour = m_vPatches[Y-1][X].GetBaseRight();
				else
					patch->GetBaseLeft()->RightNeighbour = NULL;		// Link to bordering Landscape here..
				
				if ( Y < (NUM_PATCHES_PER_SIDE-1) )
					patch->GetBaseRight()->RightNeighbour = m_vPatches[Y+1][X].GetBaseLeft();
				else
					patch->GetBaseRight()->RightNeighbour = NULL;	// Link to bordering Landscape here..
			}
		}
	}
}

VOID LANDSCAPE::LandInScene()
{
	LONG nCount;
	PATCH *patch = &(m_vPatches[0][0]);