在地形可视化中，如何实时地显示大地场景是一个主要问题，其中主要的算法是ROAM。
所谓ROAM算法，就是Real-time Optimally Adapting Mesh，就是实时自适应网格算法。ROAM算法试图生成最优的三角形网格,以便快速渲染大场景的地形地图.一般从一个单独的四边形开始,这个四边形包含两个三角形,就是整个地图.假如需要更多的地图细节,就在四边形的中间增加一个顶点,将两个三角形切分为四个三角形，同样的三角形以同样的方式进行递归地切分。
评价ROAM算法使用下面的12个准则：
1 达到给定的三角形数量所需的时间
算法的运行时间与每帧改变三角形的数目成比例，一般是总的网格大小的一部分。因此，ROAM算法对地形数据库扩展和分辨率不受影响的。
2 灵活选择基于视点的误差标准
ROAM使用荧幕空间的最大几何扭曲作为基本标准和队列优先级值。这个标准可以有多种实现方法：保证沿着视线有正确的视觉效果、提供物体下面正确的地形位置、消除隐藏面细节。
3 网格表示（预定义和实时选择）
使用一个三角形二叉树进行预计算。然后通过增加的、纹理细致的切分和合并步骤建立连续的、自适应的网格。这些三角形是右二等边三角形，因此避免了一些数值问题。
4 算法的简化
三角形二叉树的数据结构可以大大简化算法。同时操纵切分和合并的贪婪优先级队列技术提供了合并和扩展的简单机制。
5 给定三角形数量的网格质量
6 三角形数量的直接控制
ROAM直接产生特定三角形数量的网格。
7 严格的帧速率
8 保证误差限制
ROAM算法可以保证荧幕空间的几何扭曲的误差限制。这些限制可以从预处理的世界空间的限制转化到基于视点的荧幕空间得到。
9 内存需求
10 动态地形
11 降低地形的突变
12 任意的地形输入
三角形二叉树
下图是一个三角形二叉树，根三角形为（Va，V0，V1），定义为切分等级最高级的右二等边三角形，切分等级为L＝0。在下一个切分级中，L＝1，两个子三角形通过切分根的最长边得到。得到的新顶点为 Vc，T的右子树（Vc，V1，Va）。T的左子树为 （Vc，Va，V0），三角形二叉树的其他部分可以重复这个递归切分过程得到。
动态连续三角形网
世界空间中的网格可以通过把世界空间中的每个顶点赋值给每个二叉树顶点得到。如果二叉树三角形形成的网格没有两个三角形互相覆盖、有公共顶点和有公共边。称呼这样的连续网格为三角形网。下图显示了三角形网中三角形T的典型邻居关系。定义三角形Tb为T的底部邻居，共享底边（V0，V1）。TL为左邻居，共享左边（Va，V0）。Tr为右邻居，共享右边（V1，Va）。二叉树三角形网中的一个关键是邻居要么是同一切分等级L，或者是切分等级L＋1的左右邻居，或者是切分等级为L－1的底部邻居。下图中都有表示。
当T和Tb是同一切分等级时，称呼（T，Tb）为菱形。切分的相反操作为合并。切分T得到（T0，T1），切分Tb得到（Tb0，Tb1） 。切分操作在菱形中心引入新的顶点，形成了新的、连续的三角形网。当T没有底部邻居 时，只有T被切分。当T和Tb的子树都在三角形网中，合并可以施加给菱形（T，Tb）。在这种情况下，（T，Tb）称为三角形网的可合并菱形。
在三维网格中切分三角形时,必须注意不能在切分过程中产生裂缝.ROAM算法使用下面的规则处理这种情况:除了在地图的边缘,只有一个四边形可以切分.在这种情况下,四边形由两个同样大小的三角形组成,两个三角形共享最长的边.当需要切分一个三角形,而这个三角形最长边的邻居不是同样大小的三角形时,必须首先切分这个三角形的邻居,假如邻居不是四边形的一部分,那么必须检查邻居的最长边的三角形邻居,这个检查递归进行一直到得到一个四边形或者是到达地图的边缘,这条路径上的三角形当递归返回时,都被切分.示意图如下：
假设有四个顶点0（－1，0，－1），顶点1（1，0，－1），顶点2（－1，0,1),顶点3（1，0，1）
RenderSub( 0, verts[0], verts[1], verts[3] );
RenderSub( 0, verts[3], verts[2], verts[0] );
而RenderSub如下：
void CROAM::RenderSub( int iLevel, float* fpVert1, float* fpVert2, float* fpVert3 )
{
//中间顶点对准最长边
float fNewVert[3]; //新得到的顶点
//得到最长边,因为中间顶点对最长边,所以使用1和3顶点计算,没有开根号
fSqrEdge= SQR( ( fpVert3[0]-fpVert1[0] ) )+
SQR( ( fpVert3[1]-fpVert1[1] ) )+
SQR( ( fpVert3[2]-fpVert1[2] ) );
fNewVert[0]= ( fpVert1[0]+fpVert3[0] )/2.0f; //计算新顶点
fNewVert[1]= 0.0f;
fNewVert[2]= ( fpVert1[2]+fpVert3[2] )/2.0f;
//随机决定y的高度 ,通过x和z的值
~~~~~~~~~~~~~~~~~~~~~~~~~~ //fRandHeight就是随机高度偏移值
fNewVert[1]= ( ( fpVert1[1]+fpVert3[1] )/2.0f )+fRandHeight;
//计算视点和新的分离点之间的距离
fDistance= SQR( ( fNewVert[0]-m_vecCameraEye[0] ) )+
SQR( ( fNewVert[1]-m_vecCameraEye[1] ) )+
SQR( ( fNewVert[2]-m_vecCameraEye[2] ) );
//是否继续切分的判断条件
if( iLevel<LEVEL_MAX && fSqrEdge>fDistance*0.005f )
{
//得到的新顶点作为中间顶点.
RenderSub( iLevel+1, fpVert1, fNewVert, fpVert2 );
RenderSub( iLevel+1, fpVert2, fNewVert, fpVert3 );
return; //此顶点不需要渲染,是树根顶点
}
glBegin( GL_TRIANGLE_STRIP ); //渲染连续三角形
glTexCoord2fv( m_fGridtex_t[0] );
glVertex3fv( fpVert1 );
glTexCoord2fv( m_fGridtex_t[1] );
glVertex3fv( fpVert2 );
glTexCoord2fv( m_fGridtex_t[2] );
glVertex3fv( fpVert3 );
glEnd( );
}
算法示意图如下：
从上图可以看出，相当于对四边形根的左右三角形子树进行左优先深度遍历。假设某个结点的顶点为（v1，v2，v3），新得到的顶点为newvert，则这个结点的左子树为（v1，newvert，v2），右子树为（v2，newvert，v3）。从而保证了中间顶点总是面向最长边，而新得到的顶点总是最长边。
最后程序的效果如下：
如有任何问题，欢迎大家来信讨论！
starwolf8392@mop.com
|
