留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

三维场景实时建模中地形生成算法优化

袁凌 李丹 陶飞

袁凌, 李丹, 陶飞. 三维场景实时建模中地形生成算法优化[J]. 武汉大学学报 ● 信息科学版, 2017, 42(10): 1387-1393. doi: 10.13203/j.whugis20160100
引用本文: 袁凌, 李丹, 陶飞. 三维场景实时建模中地形生成算法优化[J]. 武汉大学学报 ● 信息科学版, 2017, 42(10): 1387-1393. doi: 10.13203/j.whugis20160100
YUAN Ling, LI Dan, TAO Fei. Optimization of Terrain Generation Algorithm in Three-dimensional Real-time Modeling[J]. Geomatics and Information Science of Wuhan University, 2017, 42(10): 1387-1393. doi: 10.13203/j.whugis20160100
Citation: YUAN Ling, LI Dan, TAO Fei. Optimization of Terrain Generation Algorithm in Three-dimensional Real-time Modeling[J]. Geomatics and Information Science of Wuhan University, 2017, 42(10): 1387-1393. doi: 10.13203/j.whugis20160100

三维场景实时建模中地形生成算法优化

doi: 10.13203/j.whugis20160100
基金项目: 

国家自然科学基金 61502185

详细信息

Optimization of Terrain Generation Algorithm in Three-dimensional Real-time Modeling

Funds: 

The National Natural Science Foundation of China 61502185

More Information
    Author Bio:

    YUAN Ling, PhD, associated professor, specializes in the data analysis, security and graph processing. E-mail:cherryyuanling@hust.edu.cn

    Corresponding author: LI Dan, PhD, associated professor. E-mail:lidanhust@hust.edu.cn
图(7)
计量
  • 文章访问数:  1382
  • HTML全文浏览量:  184
  • PDF下载量:  386
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-07-28
  • 刊出日期:  2017-10-05

三维场景实时建模中地形生成算法优化

doi: 10.13203/j.whugis20160100
    基金项目:

    国家自然科学基金 61502185

    作者简介:

    袁凌, 博士, 副教授, 主要从事数据分析与安全, 以及图形处理方面的研究.cherryyuanling@hust.edu.cn

    通讯作者: 李丹, 博士, 副教授.lidanhust@hust.edu.cn
  • 中图分类号: P208;TP311.1

摘要: 通过分析三维场景实时渲染中视点无关与视点相关地形生成算法的性能,提出了优化的视点相关地形生成算法。此算法主要针对地形拆分、可视精度计算、观察视点距离计算、以及地形可见性裁剪这4个方面的策略做出了详细的阐述。并以渲染精度为衡量标准,通过实验对比分析了优化后的视点相关地形生成算法与视点无关地形生成算法的性能。除此之外,以渲染效率为标准,通过实验分析对比了优化后的视点相关地形生成算法与原视点相关地形生成算法的性能,并给出了一个运用此优化算法构建的三维地形模型。

English Abstract

袁凌, 李丹, 陶飞. 三维场景实时建模中地形生成算法优化[J]. 武汉大学学报 ● 信息科学版, 2017, 42(10): 1387-1393. doi: 10.13203/j.whugis20160100
引用本文: 袁凌, 李丹, 陶飞. 三维场景实时建模中地形生成算法优化[J]. 武汉大学学报 ● 信息科学版, 2017, 42(10): 1387-1393. doi: 10.13203/j.whugis20160100
YUAN Ling, LI Dan, TAO Fei. Optimization of Terrain Generation Algorithm in Three-dimensional Real-time Modeling[J]. Geomatics and Information Science of Wuhan University, 2017, 42(10): 1387-1393. doi: 10.13203/j.whugis20160100
Citation: YUAN Ling, LI Dan, TAO Fei. Optimization of Terrain Generation Algorithm in Three-dimensional Real-time Modeling[J]. Geomatics and Information Science of Wuhan University, 2017, 42(10): 1387-1393. doi: 10.13203/j.whugis20160100
  • 在三维地形建模中,如果不考虑视点的变化,地形模型的生成过程相对比较简单,如Lindstrom[1]提出基于四叉树的连续动态地形生成算法与地形实时算法[2]。此类算法的主要思想是在精简后的地形高程图上选取渲染节点,通过三维图形处理库(open graphics library,OpenGL)命令传送到OpenGL渲染管道[3]中,便可以绘制出视点无关的地形模型。但视点无关算法在建立地形模型的时候不能达到很高的分辨率,从而会在场景逼真性上有所缺失。因此,视点无关地形生成算法一般适合对地形精细度要求不高的应用上[4-6]。视点相关算法多以基于块进行二叉树或四叉树分割简化地形模型。Hoppe[7]将视点相关渐进网络模型应用到地形实时绘制中,并采用几何形变消除不同层次之间的跳变。视点相关地形生成算法考虑了用户的视点变化,能够给用户带来更加精细更加逼真的地形模型体验,但是基于网格顶点和三角形的视图体裁剪,在采样点较密集时仍然需要大量计算,在一定程度上降低了算法效率。许妙忠、李德仁[8]提出了一种对于地形不规则三角网建立层次细节模型和实时动态显示的方法,在显示的过程中, 根据视点的远近从上述LOD模型自适应地获取和显示所需三角形,实现地形三角网的实时动态显示。

    实时优化自适应网格(real-time optimally adapting meshes,ROAM)算法[9, 10]是视点相关地形生成算法中应用最广泛的算法之一。该算法由Duchaineauy等人在1997年提出,通过对地形表面进行递归二分,构造出三角形二叉树,并以此为基础,对构造出的三角形进行分裂和合并操作以保证增加或删除顶点时所划分的网格的连续性。ROAM算法能够根据用户的视点实时地生成地形网格,并且能够动态地更改地形高程图,从而生成可根据用户视点变化的地形模型。Lowa大学仿真中心He[11]对基本的ROAM算法进行改进和扩展,改进后的ROAM算法满足动态地形实时可视化的要求。基于此,提出了动态地形可视化(DEXTER-real-time optimally adapting meshes,DEXTER-ROAM)算法,在对车辆驾驶模拟的可视化仿真中,DEXTER-ROAM算法得到了比较好的应用。在计算复杂性上,视点相关算法比视点无关算法复杂,但在精度上,视点相关算法比视点无关算法有所提升,本文将通过实验在精度上对视点无关算法和视点相关算法进行对比分析。通过分析ROAM算法,发现ROAM算法中每一帧都要计算用户观察视点到需要绘制的地形区块之间的距离,为提高计算的效率,本文提出了一种更有效的距离计算方法。另外,分析用户视点外区域可不用绘制在地形模型中,从而节省绘制视点外区域的时间,减少地形模型绘制的计算量,最终在不影响用户体验的前提下提高绘制的效率。通过实验对比分析可知,优化后的算法的性能有所提升。

    • 视点无关地形生成算法主要需要解决两个问题。一是地形高程图数据的简化问题,二是获取渲染节点,然后运用OpenGL渲染节点来绘制地形模型。

      首先解决地形高程图[12]的简化问题。地形模型的原始数据存储在地形高程图中,但由于地形高程图数据过于庞大,在使用前需要将其简化。如果尺寸符合(2M+1)·(2N+1),则将地形图数据读取到地形高程图数组中,其中MN分别代表高程图数组的行与列,将高程图压缩至原来的1/2。如果尺寸不符合要求,则将地形高度图中多出的部分剔除掉,对于长为(2M+2) 或者宽为(2N+2) 的地形图,则将其长或宽的最后一位数据剔除,剔除的部分最多只占一个数据单位,因而对整体高程图并无太大影响,然后更改记录地形高程值长宽尺寸的值,再将数据读取到地形高程图数组中。

      假设地形高程图所在的数组为heightMap[H ×H],分别表示地形高程图的长和宽,其中H=1 025,在地形高程图中,取单个网格大小为25×25,其中网格的长度用l,宽度用w表示,Terrain[m][n]表示地形模型的渲染节点,m表示地形高程图中需要渲染地形节点的行数,n表示每行选取地形节点的个数。所以mn的值均为1025 / 25 = 41。其中Terrain[i][j]表示在第i行第j列所对应的地形节点的高程值。那么Terrain[i][j]可以用式(1) 进行计算:

      $${\rm{Terrain}}\left[ i \right]\left[ j \right] = {\rm{heightMap}}\left[ {j \cdot w + i \cdot l} \right]$$ (1)

      在获取了渲染节点的位置和对应的高程值后,可将三维坐标通过OpenGL命令传送到OpenGL渲染管道中,从而绘制出视点无关的地形模型。

      视点无关地形算法的主要流程描述如下:

      1) OpenGL的初始化设置;

      2) 打开地形高程图,并记录地形高程图的长宽尺寸,如果尺寸符合(2M+1)·(2N+1),则将地形图数据读取到地形高程图数组中;如果尺寸不符合要求,则将地形高度图中不符合要求的部分剔除掉,然后更改记录地形高程值长宽尺寸的值,然后将数据读取到地形高程图数组中。在读入高程值时统计高程中的最大值和最小值;

      3) 根据地形高程图尺寸大小初始化地形网格的长宽间距;

      4) 根据高程最大值和最小值,计算最大值和最小值之间的间距,计算缩放因子;

      5) 计算对应在网格节点对应地形高程图中的xy坐标值,并根据xz坐标值获取对应高程值z,然后将坐标(xyz)送到OpenGL渲染管道进行绘制并显示三维地形模型。

    • 本文以ROAM算法为例来分析视点相关地形生成算法的主要特性。ROAM算法能够实时地优化生成地形网格,而且由于ROAM算法需要根据用户的视点生成地形模型,所以需要能够动态地更改地形高程图。而ROAM算法在对绘制地形进行拆分的时候主要利用二元三角树结构记录拆分过程。

    • 二元三角树结构[13]是ROAM算法中非常重要的数据结构,ROAM算法之所以能生成优化的地形网格, 主要是因为它使用二元三角树来保存三角形之间的坐标关系,而不是存储一个巨大的三角形坐标数组来构建地形模型。

      二元三角树的结构和二叉树的结构很类似,都是父节点指向自己的子节点,但是二元三角树不仅要考虑父子关系,还要考虑邻居的关系。二元三角树中节点的数据结构描述如下:

      struct BinaryTriTree

      {

      BinaryTriTree ×LeftChild; //左孩子节点

      BinaryTriTree ×RightChild;   //右孩子节点

      BinaryTriTree ×LeftNeighbor;  //左邻居节点

      BinaryTriTree ×RightNeighbor;  //右邻居节点

      BinaryTriTree ×BaseNeighbor;  //基邻居节点

      };

      ROAM算法中拆分地形是通过不断拆分等腰直角三角形来达到所需的细节等级,有时候可能需要将原始三角形拆分成几十个甚至上百个小三角形,如果使用数组结构来存储拆分产生的三角形的坐标和关系,就会很复杂。在拆分三角形的过程中,三角形的数量是随着拆分深度呈指数形式增长,采用数组就会占用大量的计算机内存,并且在遍历查找的过程中会占用大量的时间。采用二元三角树结构来记录三角形的拆分过程就可以很好的降低内存的使用。在最后输出三角形时由于知道拆分过程,可以较易计算出三角形的坐标,虽然也增加了一定的计算量,但是能够很好的控制内存的使用率。此外,二元三角树能很好地记录当前细节等级的三角形之间的相互关系,对拆分算法是有益的。

    • 在对二元三角树节点进行拆分的时候,需要知道拆分到什么程度才达到需要的细节等级,所以需要为地形模型建模设定可视精度[14]。而可视精度定义在节点误差的基础上,所以首先需要了解节点误差的概念。对于二元三角树节点拆分,一般使用斜边的中点作为新拆分节点的直角顶点,假设原节点网格的斜边中点为MM点的坐标为(x, y, z),左顶点高程值为L,右顶点高程值为R,地形高程图为HeightMap[x][y],那么斜边中点的高程值P=(L+R)/2,也就是说P是取左顶点高程值和右顶点高程值的平均值,但是真实的斜边中点的高程H=HeightMap[x][y],因此定义节点误差V =abs(H-P)。

    • ROAM算法是一个较为高效的视点相关地形生成算法,但依旧有优化的空间。本文提出了一个优化的ROAM算法来进行三维场景实时渲染中的地形建模,称为优化ROAM(optimized real-time optimally adapting meshes, OROAM)算法。下面主要描述OROAM算法的地形拆分、可视精度计算、观察视点距离计算以及地形可见性裁剪这几个方面的策略。

    • OROAM算法同样使用二元三角树数据结构进行地形节点拆分,表示节点与相邻节点之间的关系。因为每个节点都是等腰直角三角形,所以两个节点之间只有两种相邻关系:共直角边相邻或共斜边相邻。将共斜边相邻的两个地形节点所组成的结构称之为“钻石结构”[4],在对地形节点的斜边中点进行拆分的过程中,只有满足钻石结构的地形节点才能直接进行拆分,在其他的相邻情况下都要首先查找其基邻居是否满足钻石结构,如果不满足则继续查找基邻居的基邻居,一直到找到满足钻石结构的地形节点为止。对于满足钻石结构的节点在进行拆分的时候,其节点与基邻居节点都要从斜边中点拆分为两个子节点。

      图 1演示了非钻石结构节点的拆分过程。地形节点1与基邻居节点2之间不满足钻石结构,所以查找节点2的基邻居3,以此类推,直到查找4的基邻居5,他们满足钻石结构,进行拆分,拆分之后形成的节点7与节点3满足钻石结构,可以拆分,以此类推,直到将原始地形节点拆分完成。

      图  1  地形网格节点的强制拆分

      Figure 1.  Terrain Nodes Splitting

      当拆分一个节点的时候,存在以下3种可能的情况:

      1) 地形节点与其基邻居满足钻石结构,那么就直接拆分它和它的基邻居;

      2) 地形节点在地形模型的边界位置,那么只能拆分这一个节点;

      3) 地形节点不是钻石结构的一部分,那么就采用如图 1所示的方法强制拆分地形节点与其基邻居节点。

    • OROAM算法在地形绘制时,每一帧中对每个地形区块都要进行节点误差V值的计算。一般情况下由于建立地形模型的高程图不会发生改变,V值一般也不会发生改变,所以可以在初始化的过程中将不同深度二元三角树所对应的节点V值计算出来并存储,在后面绘制过程中根据节点的深度和节点值就能够直接查找到对应的V值。如§ 2.1所分析的,二元三角树和二叉树有很大的相似性,如果将二元三角树中不同深度节点的V值建立为一个二叉树,那么就可容易地查找到相应节点的V值。因此在地形建模系统中引进了V值二叉树结构。

      V值二叉树是一个满二叉树,在这个二叉树中,除了叶子节点之外,每个节点都有两个子节点,如果从根节点开始,从0开始编号,每个父节点n和子节点mk之间满足m =2nk=2n+1。这样将V值二叉树存储在一个数组中,这样通过父节点的下标值就能够很快的访问对应子节点的值。这能够减少地形模型的可视精度值的计算时间。

      二元三角树中不同深度的节点误差都存储在V值二叉树中,但是节点误差是静态的,不会随着用户观察视点与区块间的距离不同而变化,而可视精度是一个综合了节点误差、用户观察视点与地形区块距离、高程图尺寸的参数,能够很好的衡量地形节点拆分的精细程度。可视精度的计算公式为:

      $$A = \left( {V*S*2} \right)/d$$ (2)

      式中,A表示可视精度;V表示对应地形节点的节点误差;d表示用户观察视点与地形区块的距离;S表示地形高程图边长。

      A超过了最大可视精度X时,系统就要拆分地形节点,直到拆分后的地形可视精度在规定范围内。最大可视精度X的计算式为:

      $$X = \frac{{L \times D}}{N}$$ (3)

      式中,L为容忍限度,根据不同的渲染情形自行定义;D为当前渲染地形距离摄像机的距离;S为进行下一步拆分所成的节点数目。

    • ROAM算法要考虑到用户视点的变化,每一帧都要计算用户观察视点到需要绘制的地形区块之间的距离,其距离D的计算式为:

      $$D = \sqrt {\left( {x - p} \right)2 + {{\left( {y - q} \right)}^2}} $$ (4)

      式中,D表示用户观察视点到地形区块的距离;xy分别为用户观察视点的坐标;pq分别为地形区块中心位置坐标。

      由于距离D的计算过程中需要计算平方和、开平方,因此计算效率很低。一个地形模型有很多个地形区块组成,每个地形区块都要计算到观察视点的距离,所以精简距离D的计算量能够对算法性能起到一定程度的优化。

      对式(4) 进行近似计算,得到距离D的近似求解值,称相对距离:

      $$D = {\rm{abs}}\left( {\left( {x - p} \right) + \left( {y - q} \right)} \right)$$ (5)

      式中,abs()函数表示求绝对值函数;xy分别为用户观察视点的坐标;pq分别为地形区块中心位置坐标。这样只需要进行加减运算既能够获得距离D值。

    • 在ROAM地形系统中,每次都是把整个地形完整的绘制出来,但是在用户观察的时候,有很多地方是在视野之外的,这些区域其实是不需要绘制的,可以通过计算出地形区块中哪些区块在视野之外,在绘制的过程中将这些区块省略掉,就能有效减少系统绘制的计算量。

      图 2所示,从视点Eye出发到视点View位置的线为视线的中心线,射线a和射线b表示视野范围。正常情况下系统需要裁减掉在射线ab外面的区域。但是判断每个区块是否在视野范围内需要一定量的计算,并不能起到优化作用。

      图  2  视点剪裁示意图

      Figure 2.  Viewpoint Cutting

      可通过ab两条射线的方程来判断地形区块是否在视野范围内。这个方法的主要原理是在判断地形区块是否在视野范围内的时候,只需要将地形区块的中心点带入ab的方程中判断结果是否大于零即可。如果大于零,那么区块就在视线内;如果小于零,那么此地形区块就不在视线范围内。对于存在区块中心点在ab以下,而区块的某些部分又在ab上方,对于此种情况并不进行渲染,只以区块中心点作为唯一判断依据。

    • 在实验中,主要通过精度Alpha和帧速之间的关系来衡量算法的逼真程度和运行效率之间的关系,所使用的地形高程图尺寸为2 048×2 048单位。本算法的实验环境为:

      CPU: Intel®

      CoreTMi3 CPU M 380@2.53GZ, 2.53GZ,

      2GB内存;

      GPU: Intel ®

      HD Graphics, NVIDIA GeForce GT425M;

      编程工具:VS2010;

      语言:C++,主要用OpenGL4.0编程。

    • 一个地形模型精度[14]的影响因素主要有两个:绘制节点的个数和视点距离。建立的地形模型绘制的渲染节点数占地形高程图总地形节点数的比例越高,绘制的地形模型就会越真实,当比例达到1的时候,就是将所有节点全部绘制出来,这时候的精度最高。但是当比例很低的时候就基本上分不清地形的基本特征。对于用户来说,距离用户视点越近的点对用户观赏地形的影响就会越大,所以视点的距离是影响地形模型精度的一个主要因素。

      计算效率可以使用帧速来表示。帧速是描述计算机绘制图形快慢的数据量,帧速为计算机每秒绘制图形的次数,一般使用每秒帧数(frame per second,fp/s)表示。因此计算机绘制效率越高,那么帧速就会越高。

      精度评估值一般用Alpha表示。根据精度评估值的定义,假定地形高程图的尺寸为M·N (MN都满足2K+ 1),那么Alpha可由式(6) 计算:

      $${\rm{Alpha}} = \frac{{\sum W}}{{M \cdot N}}$$ (6)

      式中,Alpha表示地形模型精度;W表示每个地形渲染点的权值;M·N表示地形高程图的尺寸。其中权值W是与用户视点与地形区块之间的距离D相关的量。当距离D越小,表示地形渲染点距离视点越近,那么它的权值就会越大。设定当D在0~1之间的时候,设定权值W恒为1,当距离D大于1的时候,W为距离D的倒数。下面两个算法的分析比较以Alpha精度值作为衡量标准。

    • 对于视点无关地形生成算法,由于地形是静态的,能够在建立地形模型之前对模型进行计算并存储,可快速绘制,但缺乏较高的精确度。如图 3所示。

      图  3  视点无关算法和视点相关优化算法性能比较

      Figure 3.  Performance Comparison of Algorithms

      对于视点相关地形生成优化算法,也测试了Alpha与帧速fp/s之间的关系。由图 4可以看出,只有在Alpha很小的时候,视点无关算法的性能在地形生成优化算法之上,而在Alpha渐渐增大之后,地形生成优化算法就能够比视点无关算法更加精确。

      图  4  距离Distance计算优化前后算法性能对比

      Figure 4.  Performance Comparison of Distance Algorithm

    • 在优化观察视点距离计算方法时,就地形模型每行的区块数和建模的帧速上进行测试,测试结果如图 4所示,可以看出,距离计算优化的地形算法在相同的每行区块数具有更高的帧速。因此本文所提出的距离计算优化方法对算法的性能上有一定的提升。

      在测试地形可见性裁剪方法优化性能的时候,因为算法的帧速会随着裁剪掉的地形所占的比例不同而不同,所以在测试的时候选取地形中心位置进行测试。测试结果如图 5所示,可以看出在算法性能上得到了一定的提升。

      图  5  地形可见性裁剪优化前后算法性能对比

      Figure 5.  Performance Comparison of Terrain Visibility Cutting Algorithm

      地形生成优化算法与原算法的整体性能测试结果如图 6所示,可以看出,优化之后的算法性能与相同条件下原算法性能相比,有了一定的提升。特别是在每行区块数在20~80之间时效果明显,因此为了保证算法精度和性能的平衡,每行区块数尽量选择在20~80之间。

      图  6  优化前后算法性能比较

      Figure 6.  Performance Comparison of Algorithms

      运用优化后的视点相关地形生成算法OROAM建立的一个三维地形模型如图 7所示。从图中可以看出,在靠近视点的范围内,地形分辨率很高,距离视点越远的区域则地形的分辨率越低。这样不仅符合用户的体验感受,而且提高了三维场景下地形模型绘制的效率。

      图  7  地形模型线框展示

      Figure 7.  Terrain Model Grid

    • 本文在分析了三维场景实时渲染中视点无关与视点相关地形生成算法的基础上,提出了优化的视点相关地形生成算法。此算法主要针对地形拆分、可视精度计算、观察视点距离计算、以及地形可见性裁剪这4个方面的策略做出了阐述。并以渲染精度为衡量标准,通过实验对比分析了优化后的视点相关地形生成算法与视点无关地形生成算法的性能。除此之外,以渲染效率为标准,通过实验分析对比了优化后的视点相关地形生成算法与原视点相关地形生成算法的性能,并给出了一个运用此优化算法构建的三维地形模型。今后将运用更多有效方法来研究在保证渲染效率的前提下,能够获得更好的渲染精度。

参考文献 (14)

目录

    /

    返回文章
    返回