地形渲染的动态LOD四叉树算法详细实现
作者：野草 email:JerryLi@sina.com
声明：请将本文档和程序配合使用，旨在使读者费很少的时间和精力就能理解此算法。读者应该熟悉递归程序设计,以及基本的VC OpenGL编程.
渲染地形时，如果采用固定地形精度等级，则会随着地形面积的增大，渲染的三角形数量会随着面积的增大而增长。采用动态精度等级，越远处的地形画的三角形面积越大(精度越低)，越近的地形面积越小(精度越高)，坡度高的地方精度高，平坦的地方精度低，这样能有效地减少画三角形的数量，提高游戏引擎的速度.
采用四叉树算法，可有效把地形不在视野内的网格去掉,降低程序的时间复杂度
其基本思路是：先把地形一分为四，用递归的方法对每个网格渲染。对每个网格，如果达到最高精度，则退出；如果不在视野内，也退出。再对符合条件的网格递归下去。
渲染网格的方法是用GL_TRIANGLE_FAN方法，如下图
但是这样在相邻精度等级相差1倍或1倍以上时，渲染的地形会出现裂缝。
解决方法见下图：
这样相邻的网格可以相差任意级精度
参见下面的截图：看中间的那个大正方形。
程序如下：
void CTerrain::Render()
{
………
//细分标记数组清0（这里为了节约内存，一个网格用一个bit表示）
m_cFlag.Reset();
//在细分标记数组记录需要细分的网格
Update((m_nMapSize-1)/2,(m_nMapSize-1)/2,(m_nMapSize-1)/2,1);
//根据细分标记数组递归渲染网格
RenderQuad((m_nMapSize-1)/2,(m_nMapSize-1)/2,(m_nMapSize-1)/2);
…….
}
//渲染网格的递归程序
//参数:
// nXCenter: 网格中心点坐的X值
// nZCenter: 网格中心点坐的Y值
// nSize:网格大小
//返回:渲染的三角形数量
//使用前提:m_cFlag需要细分数组要先调用Update函数记录好.
int CTerrain::RenderQuad(int nXCenter,int nZCenter,int nSize)
{
int nCount = 0;
int nH0 = Height(nXCenter,nZCenter);
int nH1 = Height(nXCenter-nSize,nZCenter-nSize);
int nH2 = Height(nXCenter+nSize,nZCenter-nSize);
int nH3 = Height(nXCenter+nSize,nZCenter+nSize);
int nH4 = Height(nXCenter-nSize,nZCenter+nSize);
//求网格5个点中高度最大和最小值
int nMax = nH0,nMin = nH0;
if(nMax<nH1)nMax = nH1;
if(nMax<nH2)nMax = nH2;
if(nMax<nH3)nMax = nH3;
if(nMax<nH4)nMax = nH4;
if(nMin>nH1)nMin = nH1;
if(nMin>nH2)nMin = nH2;
if(nMin>nH3)nMin = nH3;
if(nMin>nH4)nMin = nH4;
SIZE size;
size.cx = nSize;size.cy=(nMax-nMin)/2;
//如果此网格不在视野内，返回
if(!m_pFrustum->CubeInFrustum(nXCenter,(nMax+nMin)/2,nZCenter,max(size.cx,size.cy)))
return 0;
if(m_cFlag.IsTrue(nXCenter,nZCenter))//需要细分,递归渲染4个子网格
{
nCount += RenderQuad(nXCenter-nSize/2,nZCenter-nSize/2,nSize/2);
nCount += RenderQuad(nXCenter+nSize/2,nZCenter-nSize/2,nSize/2);
nCount += RenderQuad(nXCenter+nSize/2,nZCenter+nSize/2,nSize/2);
nCount += RenderQuad(nXCenter-nSize/2,nZCenter+nSize/2,nSize/2);
}
else//渲染此网格
{
glBegin( GL_TRIANGLE_FAN );
SetTextureCoord(nXCenter,nZCenter); // center
glVertex3i(nXCenter, nH0, nZCenter);
SetTextureCoord(nXCenter-nSize,nZCenter-nSize); //left top
glVertex3i(nXCenter-nSize,nH1 , nZCenter-nSize);
//为了避免出现裂缝而多画三角形扇（就是多加那些红线啦）
RemedyTop(nXCenter,nZCenter,nSize);
SetTextureCoord(nXCenter+nSize,nZCenter-nSize); //right top
glVertex3i(nXCenter+nSize, nH2, nZCenter-nSize);
//为了避免出现裂缝而多画三角形扇（就是多加那些红线啦）
RemedyRight(nXCenter,nZCenter,nSize);
SetTextureCoord(nXCenter+nSize,nZCenter+nSize); //right bottom
glVertex3i(nXCenter+nSize, nH3, nZCenter+nSize);
//为了避免出现裂缝而多画三角形扇（就是多加那些红线啦）
RemedyBottom(nXCenter,nZCenter,nSize);
SetTextureCoord(nXCenter-nSize,nZCenter+nSize);//left bottom
glVertex3i(nXCenter-nSize, nH4, nZCenter+nSize);
//为了避免出现裂缝而多画三角形扇（就是多加那些红线啦）
RemedyLeft(nXCenter,nZCenter,nSize);
SetTextureCoord(nXCenter-nSize,nZCenter-nSize); //left top
glVertex3i(nXCenter-nSize, nH1, nZCenter-nSize);
glEnd();
nCount += 4;//这里为求简单，计算渲染的三角形数目并不是十分准确,比实际要小些
}
return nCount;
}
//更新细分记录数组的递归函数
//参数:
// nXCenter: 网格中心点坐的X值
// nZCenter: 网格中心点坐的Y值
// nSize:网格大小
// nLevel:当前的细分等级(其实可由nSize计算出来)
void CTerrain::Update(int nXCenter,int nZCenter,int nSize,int nLevel)
{
CVector3 vPos = m_pCamera->GetPos();
// int nSize = (m_nMapSize-1)/pow(2,nLevel);//由细节级度得到当前渲染矩形的大小
//求网格5个点中高度最大和最小值
int nMax = Height(nXCenter,nZCenter);
int nMin = nMax;
int nH1 = Height(nXCenter-nSize,nZCenter-nSize);
int nH2 = Height(nXCenter+nSize,nZCenter-nSize);
int nH3 = Height(nXCenter+nSize,nZCenter+nSize);
int nH4 = Height(nXCenter-nSize,nZCenter+nSize);
if(nMax<nH1)nMax = nH1;
if(nMax<nH2)nMax = nH2;
if(nMax<nH3)nMax = nH3;
if(nMax<nH4)nMax = nH4;
if(nMin>nH1)nMin = nH1;
if(nMin>nH2)nMin = nH2;
if(nMin>nH3)nMin = nH3;
if(nMin>nH4)nMin = nH4;
//网格的中心点坐标
CVector3 vDst(nXCenter,(nMax+nMin)/2,nZCenter);
SIZE size;
size.cx = nSize;size.cy=(nMax-nMin)/2;
//如果此网格不在视野内，返回
if(!m_pFrustum->CubeInFrustum(nXCenter,(nMax+nMin)/2,nZCenter,max(size.cx,size.cy)))
return ;
//视点到网格中心点的距离
int nDist = Dist(vPos,vDst);
if(nDist>2000)//距离大于2000时才将距离和误差(坡度)2个因素考虑
{
//与距离成正比,与误差(坡度)成反比,还与当前细分等级有关
if(70.0*Dist(vPos,vDst)/nSize/CalcError(nXCenter,nZCenter,nSize)>nLevel)
return;//此网格不需要细分
}
else//近距离(<2000)时只考虑误差(坡度)因素(因为动态LOD会造成地表呼吸现象,为减弱此现象不考虑距离因素)
{
if(CalcError(nXCenter,nZCenter,nSize)<30)
return;//此网格不需要细分
}
if(nSize!=MIN_GRID)
{ ////此网格需要细分
m_cFlag.Set(nXCenter,nZCenter,true);//把细分数组相应位设为true
//递归4个子网格
Update(nXCenter-nSize/2,nZCenter-nSize/2,nSize/2,nLevel+1);
Update(nXCenter+nSize/2,nZCenter-nSize/2,nSize/2,nLevel+1);
Update(nXCenter+nSize/2,nZCenter+nSize/2,nSize/2,nLevel+1);
Update(nXCenter-nSize/2,nZCenter+nSize/2,nSize/2,nLevel+1);
}
//此网格不需要细分
}
//计算误差(坡度)的函数
//参数:
// nXCenter: 网格中心点坐的X值
// nZCenter: 网格中心点坐的Y值
// nSize:网格大小
//返回: 误差大小
//说明:只是计算某些点细分与不细分的高度值差的和
inline int CTerrain::CalcError(int nXCenter,int nZCenter,int nSize)
{
int nError = 0;
int nH0 = Height(nXCenter,nZCenter);
int nH1 = Height(nXCenter-nSize,nZCenter-nSize);
int nH2 = Height(nXCenter+nSize,nZCenter-nSize);
int nH3 = Height(nXCenter+nSize,nZCenter+nSize);
int nH4 = Height(nXCenter-nSize,nZCenter+nSize);
nError += abs(Height(nXCenter,nZCenter-nSize)-(nH1+nH2)/2);
nError += abs(Height(nXCenter+nSize,nZCenter)-(nH2+nH3)/2);
nError += abs(Height(nXCenter,nZCenter+nSize)-(nH3+nH4)/2);
nError += abs(Height(nXCenter-nSize,nZCenter)-(nH4+nH1)/2);
nError +=abs(Height(nXCenter-nSize/2,nZCenter-nSize/2)-(nH0+nH1)/2);
nError +=abs(Height(nXCenter+nSize/2,nZCenter-nSize/2)-(nH0+nH2)/2);
nError +=abs(Height(nXCenter+nSize/2,nZCenter+nSize/2)-(nH0+nH3)/2);
nError +=abs(Height(nXCenter-nSize/2,nZCenter+nSize/2)-(nH0+nH4)/2);
return nError;
}
如下图:
当不细分时红点的高度值是它所在线段的两个端点的平均值,细分时就是它实际的高度值,这2个值是不一样的. 两者这间的高度差就是误差,把所有红点的误差相加就是此网格的误差
//修补网格顶部裂缝的函数
//参数:
// nXCenter: 网格中心点坐的X值
// nZCenter: 网格中心点坐的Y值
// nSize:网格大小
void CTerrain::RemedyTop(int nXCenter,int nZCenter,int nSize)
{
if(nZCenter-2*nSize>=0)//保证寻址不越界
{
if(!m_cFlag.IsTrue(nXCenter,nZCenter-2*nSize))//此网格相邻的顶部网格(同级的)没有细分
return;
}
else
return;
//此网格相邻的顶部网格(同级的)已经细分
//对顶部一分为二递归(跨级精度的情况)
RemedyTop(nXCenter-nSize/2,nZCenter-nSize/2,nSize/2);
SetTextureCoord(nXCenter,nZCenter-nSize);
glVertex3i(nXCenter,Height(nXCenter,nZCenter-nSize),nZCenter-nSize);
RemedyTop(nXCenter+nSize/2,nZCenter-nSize/2,nSize/2);
}
其它的修补裂缝的函数也是一样的流程.
近处没有考虑距离因素,只考虑误差(坡度)因素
距离越运,精度越低
感谢你的阅读,如果你有什么更好的思路或更好的算法(比如能消除地表呼吸现象),请和我联系:JerryLi@sina.com