www.pudn.com > roam.rar > Patch.cpp
// Patch.cpp: implementation of the Patch class.
//
//////////////////////////////////////////////////////////////////////
#include "stdafx.h"
#include "ROAM.h"
#include "Patch.h"
#include "Landscape.h"
#include "math.h"
#include "ncgcolor.h"
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif
int gNumTrisRendered=0;
int eyeX;
int eyeY;
GLfloat gClipAngle=0;
int m_eyeX;
int m_eyeY;
//////////////////////////////////////////////////////////////////////
// Landscape Class
//////////////////////////////////////////////////////////////////////
// ---------------------------------------------------------------------
// Definition of the static member variables
//
int Landscape::m_NextTriNode;
TriTreeNode Landscape::m_TriPool[POOL_SIZE];
// Beginning frame varience (should be high, it will adjust automatically)
float gFrameVariance = 1000;
// Desired number of Binary Triangle tessellations per frame.
// This is not the desired number of triangles rendered!
// There are usually twice as many Binary Triangle structures as there are rendered triangles.
int gDesiredTris = 150000;
float m_zmin;
float m_zmax;
Landscape::Landscape()
{
}
Landscape::~Landscape()
{
}
void Landscape::Init(double *hMap)
{
Patch *patch;
int X, Y;
// Initialize all terrain patches
for ( Y=0; Y < NUM_PATCHES_PER_SIDE; Y++)
for ( X=0; X < NUM_PATCHES_PER_SIDE; X++ )
{
patch = &(m_Patches[Y][X]);
patch->Init( X*PATCH_SIZE, Y*PATCH_SIZE, X*PATCH_SIZE, Y*PATCH_SIZE, hMap );
patch->ComputeVariance();
}
}
// ---------------------------------------------------------------------
// 重置所有地形块，重新计算误差判断准则
//
void Landscape::Reset(int viewPosX,int viewPosY)
{
// 根据视角范围，判断地形是否可视
const float PI_DIV_180 = M_PI / 180.0f;
const float FOV_DIV_2 = 90/2;
m_eyeX = (int)(viewPosX + PATCH_SIZE * sinf( gClipAngle * PI_DIV_180 ));//eyeX;
m_eyeY = (int)(viewPosY + PATCH_SIZE * cosf( gClipAngle * PI_DIV_180 ));//eyeY;
int leftX = (int)(m_eyeX + 100.0f * sinf( (gClipAngle-FOV_DIV_2) * PI_DIV_180 ));
int leftY = (int)(m_eyeY - 100.0f * cosf( (gClipAngle-FOV_DIV_2) * PI_DIV_180 ));
int rightX = (int)(m_eyeX + 100.0f * sinf( (gClipAngle+FOV_DIV_2) * PI_DIV_180 ));
int rightY = (int)(m_eyeY - 100.0f * cosf( (gClipAngle+FOV_DIV_2) * PI_DIV_180 ));
int X, Y;
Patch *patch;
// Set the next free triangle pointer back to the beginning
SetNextTriNode(0);
// Reset rendered triangle count.
gNumTrisRendered = 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_Patches[Y][X]);
// Reset the patch
patch->Reset();
patch->m_isVisible =1;
// 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->isVisibile() )
{
// Link all the patches together.
if ( X > 0 )
patch->GetBaseLeft()->LeftNeighbor = m_Patches[Y][X-1].GetBaseRight();
else
patch->GetBaseLeft()->LeftNeighbor = NULL; // Link to bordering Landscape here..
if ( X < (NUM_PATCHES_PER_SIDE-1) )
patch->GetBaseRight()->LeftNeighbor = m_Patches[Y][X+1].GetBaseLeft();
else
patch->GetBaseRight()->LeftNeighbor = NULL; // Link to bordering Landscape here..
if ( Y > 0 )
patch->GetBaseLeft()->RightNeighbor = m_Patches[Y-1][X].GetBaseRight();
else
patch->GetBaseLeft()->RightNeighbor = NULL; // Link to bordering Landscape here..
if ( Y < (NUM_PATCHES_PER_SIDE-1) )
patch->GetBaseRight()->RightNeighbor = m_Patches[Y+1][X].GetBaseLeft();
else
patch->GetBaseRight()->RightNeighbor = NULL; // Link to bordering Landscape here..
}
}
}
//////////////////////////////////////////
/////// 分配内存 ///////////////////
//////////////////////////////////////////
TriTreeNode * Landscape::AllocateTri()
{
TriTreeNode *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;
}
///////////////////////////////////////////
///////// 建立lod //////////////////
///////////////////////////////////////////
void Landscape::Tessellate()
{
// Perform Tessellation
int nCount;
Patch *patch = &(m_Patches[0][0]);
for (nCount=0; nCount < NUM_PATCHES_PER_SIDE*NUM_PATCHES_PER_SIDE; nCount++, patch++ )
{
if (patch->isVisibile())
patch->Tessellate( );
}
}
///////////////////////////////////////////
///////// 绘制地形 //////////////////
///////////////////////////////////////////
void Landscape::Render()
{
int nCount;
Patch *patch = &(m_Patches[0][0]);
for (nCount=0; nCount < NUM_PATCHES_PER_SIDE*NUM_PATCHES_PER_SIDE; nCount++, patch++ )
{
if (patch->isVisibile())
patch->Render();
}
// Check to see if we got close to the desired number of triangles.
// Adjust the frame variance to a better value.
// if ( GetNextTriNode() != gDesiredTris )
// gFrameVariance += ((float)GetNextTriNode() - (float)gDesiredTris) / (float)gDesiredTris;
// Bounds checking.
// if ( gFrameVariance < 0 )
// gFrameVariance = 0;
}
//////////////////////////////////////////////////////////////////////
// Patch Class
//////////////////////////////////////////////////////////////////////
Patch::Patch()
{
}
Patch::~Patch()
{
}
void Patch::Init(int heightX, int heightY, int worldX, int worldY, double *hMap)
{
// Clear all the relationships
m_BaseLeft.RightNeighbor = m_BaseLeft.LeftNeighbor = m_BaseRight.RightNeighbor = m_BaseRight.LeftNeighbor =
m_BaseLeft.LeftChild = m_BaseLeft.RightChild = m_BaseRight.LeftChild = m_BaseLeft.LeftChild = NULL;
// Attach the two m_Base triangles together
m_BaseLeft.BaseNeighbor = &m_BaseRight;
m_BaseRight.BaseNeighbor = &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_isVisible = 0; //设不可见
}
void Patch::Reset()
{
// 预先假设地形是不可见的.
m_isVisible = 0;
// Reset the important relationships
m_BaseLeft.LeftChild = m_BaseLeft.RightChild = m_BaseRight.LeftChild = m_BaseLeft.LeftChild = NULL;
// Attach the two m_Base triangles together
m_BaseLeft.BaseNeighbor = &m_BaseRight;
m_BaseRight.BaseNeighbor = &m_BaseLeft;
// Clear the other relationships.
m_BaseLeft.RightNeighbor = m_BaseLeft.LeftNeighbor = m_BaseRight.RightNeighbor = m_BaseRight.LeftNeighbor = NULL;
}
// ---------------------------------------------------------------------
// Discover the orientation of a triangle's points:
//
// Taken from "Programming Principles in Computer Graphics", L. Ammeraal (Wiley)
//
inline int orientation( int pX, int pY, int qX, int qY, int rX, int rY )
{
int aX, aY, bX, bY;
float d;
aX = qX - pX;
aY = qY - pY;
bX = rX - pX;
bY = rY - pY;
d = (float)aX * (float)bY - (float)aY * (float)bX;
return (d < 0) ? (-1) : (d > 0);
}
void Patch::SetVisibility(int eyeX, int eyeY, int leftX, int leftY, int rightX, int rightY)
{
// Get patch's center point
int patchCenterX = m_WorldX + PATCH_SIZE / 2;
int patchCenterY = m_WorldY + PATCH_SIZE / 2;
// Set visibility flag (orientation of both triangles must be counter clockwise)
m_isVisible = true;//(orientation( eyeX, eyeY, rightX, rightY, patchCenterX, patchCenterY ) < 0) &&
//(orientation( leftX, leftY, eyeX, eyeY, patchCenterX, patchCenterY ) < 0);
}
//////////////////////////////////////
///// 计算图像空间误差 /////////
//////////////////////////////////////
void Patch::ComputeVariance()
{
// 计算每个三角形的误差
m_CurrentVariance = m_VarianceLeft;
RecursComputeVariance( 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;
RecursComputeVariance( 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;
}
/////////////////////////////////////////////////////
//////////// 递归求解各层三角形的变形误差 //////////
/////////////////////////////////////////////////////
unsigned char Patch::RecursComputeVariance( int leftX, int leftY, double leftZ,
int rightX, int rightY, double rightZ,
int apexX, int apexY, double apexZ,
int node)
{
// /|\
// / | \
// / | \
// / | \
// ~~~~~~~*~~~~~~~ <-- Compute the X and Y coordinates of '*'
//
int centerX = (leftX + rightX) >>1; // Compute X coordinate of center of Hypotenuse
int centerY = (leftY + rightY) >>1; // Compute Y coord...
unsigned char myVariance;
// Get the height value at the middle of the Hypotenuse
double 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.
myVariance = abs((int)centerZ - (((int)leftZ + (int)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.
myVariance = MAX( myVariance, RecursComputeVariance( apexX, apexY, apexZ, leftX, leftY, leftZ, centerX, centerY, centerZ, node<<1 ) );
myVariance = MAX( myVariance, RecursComputeVariance( 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<>1; // Compute X coordinate of center of Hypotenuse
int centerY = (leftY + rightY)>>1; // Compute Y coord...
float distance;
if ( node < (1<= (1< gFrameVariance)) // OR if we are not below the variance tree, test for variance.
// ((float)m_CurrentVariance[node] * MAP_SIZE * 0.08) > distance)
{
Split(tri); // Split this triangle.
if (tri->LeftChild && // If this triangle was split, try to split it's children as well.
((abs(leftX - rightX) >= 8) || (abs(leftY - rightY) >= 8))) // Tessellate all the way down to one vertex per height field entry
{
RecursTessellate( tri->LeftChild, apexX, apexY, leftX, leftY, centerX, centerY, node<<1 );
RecursTessellate( tri->RightChild, rightX, rightY, apexX, apexY, centerX, centerY, 1+(node<<1) );
}
}
}
//////////////////////////////////////
///////// 绘制地形 /////////////
//////////////////////////////////////
void Patch::Render()
{
// Store old matrix
glPushMatrix();
glPolygonMode(GL_FRONT_AND_BACK,GL_LINE);
// Translate the patch to the proper world coordinates
glTranslatef( (GLfloat)m_WorldX, (GLfloat)m_WorldY,0 );
glBegin(GL_TRIANGLES);
RecursRender ( &m_BaseLeft,
0, PATCH_SIZE,
PATCH_SIZE, 0,
0, 0);
RecursRender( &m_BaseRight,
PATCH_SIZE, 0,
0, PATCH_SIZE,
PATCH_SIZE, PATCH_SIZE);
glEnd();
// Restore the matrix
glPopMatrix();
}
// ---------------------------------------------------------------------
// Render the tree. Simple no-fan method.
//
void Patch::RecursRender( TriTreeNode *tri, int leftX, int leftY, int rightX, int rightY, int apexX, int apexY )
{
if ( tri->LeftChild ) // All non-leaf nodes have both children, so just check for one
{
int centerX = (leftX + rightX)>>1; // Compute X coordinate of center of Hypotenuse
int centerY = (leftY + rightY)>>1; // Compute Y coord...
RecursRender( tri->LeftChild, apexX, apexY, leftX, leftY, centerX, centerY );
RecursRender( tri->RightChild, rightX, rightY, apexX, apexY, centerX, centerY );
}
else // A leaf node! Output a triangle to be rendered.
{
// Actual number of rendered triangles...
gNumTrisRendered++;
GLdouble leftZ = m_HeightMap[(leftY *MAP_SIZE)+leftX ];
GLdouble rightZ = m_HeightMap[(rightY*MAP_SIZE)+rightX];
GLdouble apexZ = m_HeightMap[(apexY *MAP_SIZE)+apexX ];
int col = MAP_SIZE;
FCOLOR color;
meGetPseudoColor(leftZ,m_zmax,m_zmin,color,1);
glColor3f(color.red,color.green,color.blue);
glVertex3f( (GLfloat) leftX,
(GLfloat) leftY,
(GLfloat) leftZ/20);
meGetPseudoColor(rightZ,m_zmax,m_zmin,color,1);
glColor3f(color.red,color.green,color.blue);
glVertex3f( (GLfloat) rightX,
(GLfloat) rightY,
(GLfloat) rightZ/20);
meGetPseudoColor(apexZ,m_zmax,m_zmin,color,1);
glColor3f(color.red,color.green,color.blue);
glVertex3f( (GLfloat) apexX,
(GLfloat) apexY,
(GLfloat) apexZ/20);
}
}
// ---------------------------------------------------------------------
// Split a single Triangle and link it into the mesh.
// Will correctly force-split diamonds.
//
void Patch::Split(TriTreeNode *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 neighbor
if ( tri->BaseNeighbor && (tri->BaseNeighbor->BaseNeighbor != tri) )
Split(tri->BaseNeighbor);
// Create children and link into mesh
tri->LeftChild = Landscape::AllocateTri();
tri->RightChild = Landscape::AllocateTri();
// If creation failed, just exit.
if ( !tri->LeftChild )
return;
// Fill in the information we can get from the parent (neighbor pointers)
tri->LeftChild->BaseNeighbor = tri->LeftNeighbor;
tri->LeftChild->LeftNeighbor = tri->RightChild;
tri->RightChild->BaseNeighbor = tri->RightNeighbor;
tri->RightChild->RightNeighbor = tri->LeftChild;
// Link our Left Neighbor to the new children
if (tri->LeftNeighbor != NULL)
{
if (tri->LeftNeighbor->BaseNeighbor == tri)
tri->LeftNeighbor->BaseNeighbor = tri->LeftChild;
else if (tri->LeftNeighbor->LeftNeighbor == tri)
tri->LeftNeighbor->LeftNeighbor = tri->LeftChild;
else if (tri->LeftNeighbor->RightNeighbor == tri)
tri->LeftNeighbor->RightNeighbor = tri->LeftChild;
else
;// Illegal Left Neighbor!
}
// Link our Right Neighbor to the new children
if (tri->RightNeighbor != NULL)
{
if (tri->RightNeighbor->BaseNeighbor == tri)
tri->RightNeighbor->BaseNeighbor = tri->RightChild;
else if (tri->RightNeighbor->RightNeighbor == tri)
tri->RightNeighbor->RightNeighbor = tri->RightChild;
else if (tri->RightNeighbor->LeftNeighbor == tri)
tri->RightNeighbor->LeftNeighbor = tri->RightChild;
else
;// Illegal Right Neighbor!
}
// Link our Base Neighbor to the new children
if (tri->BaseNeighbor != NULL)
{
if ( tri->BaseNeighbor->LeftChild )
{
tri->BaseNeighbor->LeftChild->RightNeighbor = tri->RightChild;
tri->BaseNeighbor->RightChild->LeftNeighbor = tri->LeftChild;
tri->LeftChild->RightNeighbor = tri->BaseNeighbor->RightChild;
tri->RightChild->LeftNeighbor = tri->BaseNeighbor->LeftChild;
}
else
Split( tri->BaseNeighbor); // Base Neighbor (in a diamond with us) was not split yet, so do that now.
}
else
{
// An edge triangle, trivial case.
tri->LeftChild->RightNeighbor = NULL;
tri->RightChild->LeftNeighbor = NULL;
}
}
void SetMinMaxElevation(float zmin,float zmax)
{
m_zmin = zmin;
m_zmax = zmax;
}