近年来,海量三维地形在战场仿真、三维网络游戏、地理信息系统以及飞行驾驶模拟等领域中的应用越来越广泛。但是,海量地形的渲染数据量是非常惊人的,这就需要对庞大的地形数据进行合适的调度,改变以往一次性将全部地形数据资源加载到内存的方法。一次性加载大量数据会在程序初始化时极大地增加加载响应时间,并在程序运行中占用大部分内存资源。由于外总线传输速率与内总线速率相比非常缓慢,数据在内、外存之间拷贝的效率与外总线速率密切相关。CPU的等待时间可能会随着数据量的增大而增加。分页加载模式极大地减少了等待时间,采取使用“谁”就加载“谁”的方法,加载一次只占用少量的I/O时间;同时采用预加载策略,把那些可能马上会被使用的页面数据也部分加载至内存,这样既满足了效率的提高,又实现了漫游不同页面之间的平滑过渡。
采用分页调度管理模式,只将当前(或未来短时间内)需要的页面加载到内存中。经过分割处理后的地形高度数据图被放入地形分页数组中,与经过分割的地形纹理等资源数组绑定。这时,以单个页面为单位的资源组的加载方式将比之前的一次性资源加载方式更节省内存资源,也减少了等待时间。
本文提出的分页调度策略实现了动态加载地形页面和基于几何纹理贴图的LOD(level of detail,层次细节)的结合,大大优化了一次性调度策略并显著提高了渲染帧率。理论上,本方法可以实现海量地形数据的实时渲染。基于本方法实现的演示程序,使用了含有复杂地形的16 385×16 385个采样点的高度图来产生分页地形,取得了不错的渲染效果。
1 分页调度策略
本文提出的策略方法的核心思想是对海量地形数据进行空间页面(page)划分,将地形网格顶点数据划分为多个page,每个page又包含若干地形块。Page是地形数据调度的基本单位,每一个地形页面对应一个材质(material),并定义了纹理的大小和多重纹理的混合方式。Tile则是地形LOD的基本单位,它负责管理几何LOD。Page和tile是一种抽象的层次逻辑关系,它们的实际顶点信息和索引顶点信息则保存在可渲染体(renderable)中。Renderable包含实际的vertex/index信息,它实际上是地形tile的几何表示,与tile是对应关系。地形数据的结构划分如图1所示。
在程序的运行过程中,是通过场景摄像机在地形场景中漫游,因此,能看见场景中的哪一部分是由当前的场景摄像机提供的位置和可视范围等信息决定的。系统根据当前摄像机参数,在每帧作出是否加载或卸载地形页面的决策(图2):加载那些将要进入可视区的页面数据,卸载那些远离观察者视点的页面数据。对于使用过的地形纹理图片则根据时间就近原则,保存那些可能被重复使用的数据。
1.1 数据结构划分
整个地形数据被划分成若干page,每一个page都是场景树的一个节点,它们的索引值被保存于一个地形页面二维索引数组(terraPageTable)中,每一个page将会保存自己的X、Z方向索引值:tablex、tablez。Page还会保存自己的上、下、左、右四个邻居索引,这些索引存储在邻居数组(pageNeighbors)里面。同时,page还将知道自己包含了多少个tile,所以它会维护一个整型变量(numberTiles)用来存储tile的个数。另外,由于需要被实时调度,page的状态信息也是必不可少的,主要有inited(已初始化)、preloaded(就绪)、textureload(已纹理化)、loaded(已加载)、unloaded(已卸载)。
根据以上几种状态,创建四个用于方便调度的地形页面队列:加载队列(qPageLoad)、就绪队列(qPagePreLoad)、纹理化队列(qTextureLoad)和卸载队列(qUnLoad)。相应的地形块tile也有自己的队列,即加载队列(qTileLoad)、就绪队列(qTilePreLoad)和卸载队列(qTileUnLoad)。
1.2 动态加载的算法描述
整个地形page的调度就是基于以上队列的。当应用程序启动,场景初始化完成后,首先加载第一个page。可以通过当前场景摄像机的位置cameraPos来获取当前page在二维索引数组中的索引值和page本身的渲染数据并立即显示,同时将页面加入qPageLoad队列中。当加载首个page完成后,开始加载视点周围的page,并填充qPageLoad和qPagePreLoad队列。填充队列的操作每一帧进行一次,这样可以避免单帧加载过多数据而导致的帧冲击。
根据当前场景摄像机位置,判断视点周围page的状态,从而进行相应队列操作的算法描述如下:
a)确定一个相机最远视距阈值cameraThreshold。上一帧摄像机位置为lastPos,当前位置为pos。如果cameraThreshold<|lastPos.x-pos.x|或cameraThreshold<|lastPos.z-pos.z|并且lastPos不等于pos,表明视点发生了改变,并且在阈值之内,此时需要进行page更新。
(a)获取当前page以及属于该page的tiles,并获取page的索引值。
(b)如果page在qTextureLoad中,则将之移除,并加入到qPageLoad。
(c)更新场景相机位置。
b)如果这一帧摄像机移动出上一帧所在的范围,及oldPage不等于page,则需要通知page的邻居们,以确定它们应该属于qPageLoad还是qPagePreLoad。定义场景中x、z方向page的初始加载数目和最终加载数目分别为iniX(iniZ)、finX(finZ),初始预加载数目和最终预加载数目为preIniX(preIniZ)、prefinX(prefinZ)。
(a)在preIni到prefin的范围内逐个取出page,再获取每个page的索引值。
(b)判断该page是否在qPageLoad中,如没有则再判断该page的索引是否介于iniX(iniZ)与finX(finZ)之间,如是则加入到qPageLoad队列中。
(c)否则判断是否在qTextureLoad或qPagePreLoad中,如都没有,则将其加入到就绪队列qPagePreLoad中。
c)更新所有已加载的page。
(a)更新摄像机视锥体,以便重新获取摄像机位置(cameraPos)。通过当前索引与ini和fin比较,通知在范围内的page进行更新。判断光照、纹理等是否需要更新,是则更新。
(b)范围外的page不再更新。
d)根据当前相机位置来加载与page相应的顶点数据renderables的集合。
(a)根据当前的cameraPos,对qTileLoad队列中的tile进行视点—tile由近及远排序。
(b)依次取出每一个tile作为地形场景子节点,并与它的实际顶点信息体renderable绑定。
(c)设置当前tile的邻居索引值。
基于漫游视点的地形页面动态加载如图3所示。
1.3 垃圾回收算法
以上的算法模型包含了整个页面加载的全部过程,即填充加载队列、就绪队列和纹理化队列的全过程。下面要实现的就是页面卸载算法。
a)检查qPageLoad队列中的Page是否应该被卸载。在本算法模型中,设置一个计数器timeUntouched。当计数器大于0时,表明该page在最近几帧被使用过;当计数器小于等于0时,表明page使用过期,应该被收回。同时设置一个touch操作,每进行一次touch(),就是把timeUntouched计数器重置为初始值。当系统初始化,进行就绪队列和纹理化队列加载,加载qPageLoad队列时都要进行一次计数器重置,而每进行一次untouch()操作则将计数器减一。检查page是否应该被卸载,就是检查计数器的值,将计数器值小于等于0的page卸载。
b)同样检查qPagePreLoad和qTextureLoad,卸载那些需要被回收的page。
上述回收算法采用的计数器方法有效地对加载/卸载的执行次数进行了限制,就是说只加载/卸载那些应该被执行该操作的page,这样就把数据操作对程序性能的影响减到最低,使显示帧率大幅提高。
1.4 调度策略的实现价值
a)对庞大的地形数据进行了分割,便于分批加载的实现。
b)Page、tile和renderable三个逻辑层次结构使地形页面的索引值与实际的顶点信息和顶点索引信息分离开来,极大地减少了无谓的数据加载,可以节省很多CPU时间和内存容量。
c)加载page以帧为单位分批进行。以不同的page、tile状态为依据执行不同队列的填充,只加载那些应该被加载的page,从而构成了一条数据调度流水线,使地形渲染平稳进行,减少了对帧率的冲击。
d)使用了智能的垃圾回收机制,最近最少使用算法使状态转换和无谓卸载减到最低,节省了CPU时间。
2 分块实时渲染
前面介绍过,地形块tile是对地形网格更细级别的划分,一个地形page就是由一个N×N的tile矩阵构成的。Tile同时是地形LOD的基本单位。
在page被加载的同时,它包含的tile和与之对应的rende-rable也同时被加载到内存当中。此时内存中的地形数据仍然是比较庞大的。如果图形显卡直接对所有细节进行渲染,三维数据几何复杂度仍然太高,这就需要在不影响视觉效果的前提下降低数据的几何复杂度,减少图形系统实时处理的图形数量,提高渲染效率。当前,LOD模型是业界广泛采用的地形几何数据简化方法,GeoMipMap算法就是其中一种LOD模型。
本文在tile层次上实施GeoMipMap(几何纹理贴图) LOD算法。GeoMipMap算法是Willem de Boer 根据纹理Mip贴图的概念提出的。纹理Mip贴图预先计算一系列缩小的纹理图(1/2、1/4等),称为Mip贴图。在生成纹理时,不同距离的三角形用最接近屏幕尺寸的Mip图贴图。根据这个概念,Willem de Boer把整个地形场景在xz平面上进行分块(block),如用65×65的block把1025×1025的地形表示为16×16个block。每个分块可用不同分辨率的网格模型来描述,在同一分块内,网格模型的分辨率相同,采用隔行采样的方式生成不同分辨率的网格。
利用此算法要解决的一个问题是:两个不同分辨率tile相邻接时会产生几何裂纹和间隙,这样会破坏地形连续性。最好的解决方案是改变高细节网格的连接,使其与低细节网格无缝地混合。简单地说,已经有高细节网格和低细节网格(图4(a)),只需要重构高细节网格,使其与低细节网格整齐连接即可。只要在高细节网格中跳过一个顶点,就可以保证两个网格无缝连接不会有间隔,即高细节网格中有一些顶点不用,但结果不会很明显。
3 实验和分析结果
本文的成果应用于国家“863”计划基金项目网络游戏内容创作平台的地形编辑器系统当中。采用了由噪声函数生成的高度图创建的超大规模地形数据,地形数据被分割为多个1025×1025的page,每个page包含16×16个65×65的tile。在地形中漫游,FPS分别达到了30 fps和110 fps。
实验结果运行的平台为:P4 双核 2.6 GHz CPU,nVidia 8600GT 256 MB显卡,2 GB内存。实验效果图如图5所示。
实验结果表明,本文提出的海量地形分页调度策略和分块几何纹理贴图LOD较好地解决了海量网格数据的实时渲染,这种层次化的调度实现了大量数据的平滑加载,使大规模地形的渲染效率有了很大的提高。
参考文献:
[1]胡斌,江南,刘琛,等 .基于粗粒度分页和细粒度分片的大地形动态调度机制研究[J].计算机应用, 2006, 26(Z1):4-7.
[2]李惠,翟磊,林诚凯,等 .一种超大规模地形的实时渲染方法[J].系统仿真学报, 2004, 16(4):736-739.
[3]SPEARS Ⅲ V L. Terrain level of detail in first person-ground perspective simulations[D]. California:Naval Post Graduate School Monterey, 2002.
[4]HOPPE H.Smooth view-dependant level-of-detail control and its application to terrain rendering[EB/OL].(1998). http://research.micorsof.tcom/～hoppe/.
[5]LINDSTROM P, HODGES L F, FAUST N. Real-time, continuous level of detail rendering of height fields[C]// Proc of ACM SIGGRAPH. 1996: 109-118.
[6]赵友兵,石教英,周骥,等.一种大规模地形的快速漫游算法[J].计算机辅助设计与图形学学报,2002, 14(7):624-628.
[7]马照亭,潘懋,胡金星,等. 一种基于数据分块的海量地形快速漫游方法[J].北京大学学报:自然科学版,2004, 40(4):619-625.
饮水思源，不忘初心。
要面包，也要有诗和远方。