基于GPU编程的地形可视化

基于GPU编程的地形可视化第13卷第11期2008年11月中国图象图形JournalofImageandGraphicsVolJ13.No.11Nov.,2008基于GPU编程的地形可视化罗岱谢茂金曹卫群(北京林业大学信息学院,j京100083)黄心渊摘要由于地形模型固有的复杂性,致使计算机硬件水平一直难以满足大规模地形模型的实时显示需求.为了在现有的硬件水平上实现地形模型的快速绘制,在对传统的ROAM算法进行改进的基础上,提出一种基于GPU编程的地形可视化算法,实现了视点依赖的大规模地形的快速可视化.该算法首先基于改进的ROAM(rea1.timeoptimallyadaptivemeshes)算法生成视点依赖的优化连续LOD模型;然后用GPU编程计算顶点的变换,法向量,纹理坐标,纹理采样和面元光照;最后完成地形的着色.实验结果表明,利用GPU编程不仅能有效提高算法速度,而且能实现较大规模地形的实时漫游.关键词GPU编程地形可视化R0AM中图法分类号:TP391.4文献标识码:A文章编号:10068961(2008)l1.2244.06ATerrainVisualizationAlgorithmBasedonGPUProgrammingLUODai,XIEMao-jin,CAOWei-qun,HUANGXinyuan(SchoolofInformationScienceandTechnology,BeijingForestryUniversity,Beijing100083)AbstractDuetotheinherentcomplexityofterrainmodels,thedevelopmentspeedofcomputerhardwareisfarfromsatisfactionforreal-timerenderingoflargescaleterrainmode1.Toresolvethisproblem,weenhancethetraditionalROAMalgorithmandthereforerealizeviewdependentreal-timerenderingoflargescaleterrainmodelwithGPUprogramming.Here,theenhancedROAM(real-timeoptimallyadaptivemeshes)algorithmisemployedtocreateviewdependentcontinuousLODmodels,andtheGPUprogrammingisemployedtocalculatetheveicestransform,normalvector,texturecoordinate,texturesamplingandfragmentlightingandaccomplishtherenderingfortheterrainintheend.Experimentalresultsshowthat,GPUprogrammingisaneffectivewaytoimprovethealgorithmperformanceandtoachieverealtimeroamingonrelativelylargescaleterrain.KeywordsGPUprogramming,terrainvisualization,realtimeoptimallyadaptivemeshes(ROAM)1引言随着雷达,卫星,遥感等相关技术的发展,海量地形数据的获取已经变得相对容易,而且地形可视化的应用也越来越广泛,比如3维游戏,虚拟现实,GIS,计算机仿真等.然而由于硬件发展水平的限制和地形模型几何复杂度高的特征,致使海量地形数据的显示依然是当今计算机图形学的难题之一.为了在现有的硬件水平上,实现地形模型的快速绘制,自1976年Clark提出由模型简化来构造多分辨率模型的思想以来,各类LOD(1evelsofdetail)模型的建立已成为提高地形绘制速度的重要方法之一,而硬件上则主要依赖于图形卡厂商显卡性能的提高.此外,该领域也有一些CPU(centerprocessingunit)多媒体指令和并行计算方法的应用研究.近年来,可编程图形处理单元(graphic基金项目:国家自然科学基金项目(60703006);国家高技术研究发展计划(863)项目(2006AA10Z232)收稿日期:2007.0306;改回日期:20070713第一作者简介:罗岱(1974一),男.讲师.现为北京林业大学林业装备工程专业博士研究生.主要研究方向为数字林业,多媒体技术,计算机仿真.E.mail:ed17878第11期罗岱等:基于GPU编程的地形可视化processingunit,GPU)的出现,给复杂图形的快速绘制注人了新的活力,而高级GPU编程语言的出现则使基于GPU编程的应用开始普及起来.相继提出的各类静态LOD算法通常是先预处理好一系列不同层次细节的模型,然后在实时显示时,则根据具体的视觉要求选择合适的细节层次.这类方法能满足一些特定的应用,而对于地形数据来说,由于其本身通常就是大文件,同时静态LOD算法生成的多个模型会增加存储的负担,所以容易造成存储瓶颈.此外,基于静态的LOD模型建立的地形场景,当不同层次的模型切换时,由于容易产生视觉跳跃现象,因此需要合适的几何平滑过渡.连续LOD模型(CLOD)则根据模型在世界坐标系的几何误差阈值和在屏幕坐标系的投影误差阈值,用依赖于视点的细分方法来生成连续分辨率模型.基于规则三角形网的连续四叉树LOD模型首先由Linstrom等人提出.一年后Duchaineauy等人又提出了实时优化适应性网格(rea1.timeoptimallyadaptivemeshes,ROAM).该算法是目前应用最广泛的算法之一.与静态LOD模型不同,由于CLOD不需预先处理生成多个不同层次细节的模型,而是根据视点的变化动态来生成适当分辨率的模型,因此比静态LOD模型节省存储空间.这类算法通常与广泛采用的规则格网地形数据相适应.对于CLOD,目前生成多分辨率地形的模型简化判断依据主要是屏幕投影误差或其变相表达地形粗糙度.屏幕投影误差u一是根据透视投影的原理来衡量误差.杜金莲等人从能量传播的角度出发,提出了一个适合对距离视点较远的区域进行简化的残余能量准则,同时将其与屏幕投影误差结合,建立了一个基于视觉原理的多分辨率地形生成准则.另一方面,GPU自1999年首先由NVidia公司提出来后,其发展速度是CPU更迭速度的3倍多.文献11对GPU在近年来的发展和应用进行了比较全面的介绍.Losasso等人提出在几何裁剪图上镶嵌规则格网的地形LOD算法.该算法提出了一套适合GPU流水线的LOD框架,其能够充分利用GPU强大的图形处理能力,并在提高算法速度方面取得了很大的成功,但是其压缩和误差控制尚不尽人意.JensSchneider对几何裁剪图进行了改进,即通过对包含几何变形的CLOD表示和图片纹理的支持进行高质量的地形绘制,以保证在用户定义的屏幕坐标和世界坐标误差阈值内进行地形模型的细分.该算法还通过对最高分辨率模型进行优化的几何过滤避免了走样.为了获得高带宽效率,该算法在运行时,先对具有离散分辨率的简化网格的集合进行逐步传输,然后在GPUShader中对这些离散的网格模型进行插值和绘制,并生成了连续分辨率的模型.Clasen等人将基于GPU的几何裁剪图应用于球形地形数据的可视化,其是通过映射纹理坐标,并基于顶点偏移和视点参数来计算球形地形数据高度图的采样位置.本文尝试将传统的ROAM算法和GPU编程结合起来对地形进行可视化.2算法思想本文在改进的ROAM算法的基础上,利用GPU编程来提高地形可视化算法的效率.为了对算法进行描述,首先给出以下几个定义:定义1期望三角面片数:根据计算机的绘制能力预先设置的每帧期望得到的三角面片个数,比如20000.定义2面片数帧差:前一帧绘制的三角面片个数与其期望的三角面片数的差值.定义3帧阈值:当前帧的误差阈值.该值可根据面片数帧差进行动态调整.算法在对地形数据集根据帧阈值进行非均匀采样时,首先实时构造ROAM网格,然后用GPU进行绘制输出.3算法的实现3.1地形数据的载入由于地形数据集的数据量通常比较大,为了解决存储问题,地形数据采用了Windows操作系统的内存映射机制.内存映射机制是Windows操作系统为大文件的读写和共享所设计的解决方案.它采用高速页面缓冲的形式,最大可以支持4GB的文件.内存映射不仅操作简单,且效率也比较高.3.2帧阈值的动态调整将数据载入后,算法即根据面片数的帧差来动态调整帧阈值.如果面片数的帧差不为0时,即调中国图象图形第13卷整帧阈值,那么当动画停下来一段时间后,由于帧阈值的调整,使得面片数的帧差会接近0,这样帧阈值会在其平衡点附近进行小范围的浮动,从而出现小部分网格闪烁的现象.为了防止这种闪烁现象,算法采用了滞后处理的方法,即只有某帧得到的三角面片数与期望的三角面片数的差值超过某个合适范围尺的时候才进行帧阈值的调整,并将调整的速度乘上一个系数Js,以控制帧阈值的适应速度,以便使得每帧得到的三角面片的数量相对稳定.R和s这两个常数属于经验数值,需要根据多次实验方可获得比较理想的值.一般来说,不宜过大或过小(本实验中取500比较合适),由于若过大,则导致帧速率调整滞后严重,从而出现帧速率下降或者三角面片数过少的问题,而过小则还会出现网格闪烁.Js的取值与R正相关,如果过大,则画面有可能会出现轻微的跳跃,而过小则增加调整的时间.本实验5取值50,视觉上几乎感觉不到画面的跳跃.实验表明,若和Js选取合适,则可以得到流畅的画面.3.3地形分块1998年,Hoppe等人将视点依赖的渐进网格(viewdependentprogressivemeshes,VDPM)应用到地形绘制中,实现了大规模地形的实时漫游.其分块的方法对于大规模地形的绘制有着重要的指导意义.地形分块有以下优点:有利于提高裁剪效率;有利于地形数据读取;有利于纹理映射和并行绘制;有利于提高算法的适应性,以适应非正方形地形的绘制.为了避免块与块之间出现拼接缝,本文采用了边缘重叠的方法.比如每个块的数据是6464,则实际处理的数据是6565.这样,每块四周(边缘块的外侧除外)都有一排宽度为1的数据相重叠.分块与重叠如图1所示.图1地形分块Fig.1Terrainblocking3.4视锥预裁剪为了初步减少算法所处理的数据量,本文采用了视锥预裁剪的方法.视锥预裁剪是在地形分块的基础上进行的.为了提高算法运行效率,考虑到地形漫游动画的特殊性,其视域裁剪可以简化成只进行相对于视锥的左右两个侧面和远裁剪面在水平面上的三角形投影的裁剪,首先产生一个较粗的裁剪结果,之后将各个块是否可见进行标记.视锥预裁剪如图2所示,其中浅色部分为可见区域.一一一一熏一一一一一一一曩囊一曩蠢囊一蕾蟹黼蠢曩露曩戮蠢鬃鬈翟爨囊蠢曩一一一一一一一图2视锥预裁剪Fig.2Frustumpreculling3.5基于GPU编程实现地形模型的绘制(1)顶点法向量计算大家知道,对物体表面进行光照计算,需要每个顶点的法向量信息.求取法向量的传统做法是预先计算好每个顶点的法向量存储成法向图,使用的时候直接对法向图进行采样.但是如果地形数据本身比较大,比如81928192大小的地形,其顶点数是64M个,如果用法向图的方式,用4Byte表示一个浮点数,则法向图的大小达到6434=768MByte.这种存储瓶颈将会显着限制可视化地形的鬈第11期罗岱等:基于GPU编程的地形可视化大小.另一种做法是在CPU上实时计算顶点的法向量.但是向量的叉乘运算和归一化要涉及多次加减乘除和开平方运算,也需要消耗多个CPU时钟周期.如果一帧需计算1万个三角面片,每个顶点用其周围4个顶点围成的4个三角面片的法向量的平均值来近似,则需要12万次这样的计算,因此容易造成计算瓶颈.由于本文将顶点法向的计算过程转移到GPU中实时进行,充分利用了GPU强大的浮点向量计算能力,并利用了cg语言提供的叉乘函数,向量标准化函数和线性插值函数,因此能够非常方便地完成法向量的计算和标准化工作.如果把地形的高度图当作一张明度纹理,并用cg语言中的texRECT函数对高度图进行采样,那么即可得到顶点周围4个顶点的高度值,据此即可计算顶点的法向量.实验表明,这种方式比CPU直接对内存进行访问的方式在性能上有较大程度的提高,在作者所进行的测试实验中约可快15fps.而且在帧速率提高的同时,帧速率变得更加平稳.(2)地面光照计算本文采用了Phong模型计算地面的光照.由于可编程GPU具有可根据需要灵活控制图形生成的特性,且算法基于地形表面一般不存在镜面反射的考虑,因此在利用GPU生成图形的计算中就去除了其镜面反射计算的部分,以加速地形场景的绘制.4实验结果算法的测试采用了81928192大小的地形数据.PC平台关键硬件配置如下:CPU:IntelPentium42.8G,内存:Kingston1GDDRII,显卡:NVidia7800GT,显示器:Philips107B5.操作系统为MicrosoftWindowsXPPro.Version2002ServicePack2.Cg编译器版本为1.50.开发环境为MicrosoftVisualC+6.0sp5.测试结果:图3显示了一组对比实验的数据曲线.实验都使用了相同的ROAM算法,其中帧速率数据为一次漫游过程中,中间连续30秒的帧速率数据(测试编号中的”A”表示采用GPU编程加速,”B”表示未采用GPU编程加速,数字表示地形网格的大小,比如”A1024”表示”采用GPU编程加速,地形网格大小为10241024”.)由图3可见,A组的5条曲线都在B组的5条曲线上方.实际上,从表1统计的平均帧速率可以看出,A组的平均帧速率大约是B组平均帧速率的4倍.一讲蚓餐图3帧速率分析Fig.3Framerateanalysis表1测试结果统计分析Tab.1Statisticanalysisoftestresult表1统计了各组测试的平均帧速率和帧频方差数据,图4则展示了各组测试的平均帧速率和帧频方差的变化曲线.该统计结果表明:平均帧速率不会随地形数据的增大而急剧下降;整体上看,ROAM算法帧频方差较小,帧速率稳定,这说明ROAM算法适合于大规模地形的实时绘制;帧频方差与地形网格的大小相关,不论是A组或者是B组,过大或者过小的地形都显示出较大的方差,而81928192大小的地形的方差最小;A组的帧频方差明显高于B组,这可能是由于GPU编程加速放大了方差的缘故.眺一一2248一中国图象图形第13卷斛地形网格人小氆一AtH平均帧速率+B组平均帧速率1.一A组方差一B组方差图4帧速率统计分析Fig.4Frameratestatisticanalysis实验结果表明,该算法所得漫游画面平稳,视觉效果良好.运行屏幕截图如图5(a)所示.(a)运行效果截图5结论(b1LoD州格图5测试结果Fig.5Testingresult本文描述了一种在改进的ROAM算法基础上结合GPU编程的地形可视化方法.该方法首先用改进ROAM算法结合分块和视锥预裁剪等技巧实时生成视域内物体的连续LOD模型;然后用GPU编程实时计算物体表面的顶点法向以及光照,纹理采样,进而实现物体表面的着色.实验表明,该算法不仅节省存储空间,而且具有较高的效率,能够在高帧速率下实现大规模地形数据的可视化,且帧速率平稳,视觉效果较好,有能力对更大规模的地形实现实时可视化,具有一定的应用价值.由于没有采取反走样的相关措施,致使图像出现了边缘锯齿状等走样现象.为了进一步提高图像质量,寻找一种合适的反走样方法是必要的.由于地形采用分块纹理,致使距离视点较远的纹理重复比较明显,因此对顶点纹理坐标进行合适的扰动,使生成的地形场景更为自然真实,也是下一步要开展的工作.通过测试发现,CPU的负担依然比较重,这是由于地形表面细分时进行的平方根运算比较费时的缘故,此外,CPU对映射文件高度图数据的频繁访问,也是很重要的原因.对该部分进行优化或者进行转移计算,方可进一步提高算法的性能.GPU技术日新月异,市场上不断有高端的GPU推出.目前,三角面片的绘制速度已经达到100M个/s,其顶点处理速度也不断增加,同时GPU还具备很强的并行计算能力.因此充分利用GPU强大的功能来对地形数据进行绘制,压缩,对地形高度图进行纹理分块,是进一步增加可实时绘制的地形数据规模,提高纹理和地形采样效率的一个改进方向.一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一第11期罗岱等:基于GPU编程的地形可视化2249continuouslevelofdetailrenderingofheightfieldsA.In:ProceedingsofSIGGRAPHC,NewOrleans,Louisiana,USA,1996:109118.8DuchaineauM,WolinskyM,SigetiDE,eta1.ROAMingterrian:Real-timeoptimallyadaptivemeshesA.In:ProccedingsofIEEEConferenceonVisualizationC,Phoenix,Arizona,USA,1997:8188.9DuJinlian,Duwei,ChiZhongxian.VisiontheorybasedmuftisolutionterraingenerationprinciplesJ.JournalofImageandGraphics,2003,8(11):12951298.杜金莲,杜薇,迟忠先.基于视觉原理的多分辨率地形生成准则J.中国图象图形,2003,8(11):12951298.10TangZesheng.3DDataFieldVisualizationM.Beijing:TsinghuaUniversityPress,1999.唐泽圣.三维数据场可视化M.北京:清华大学出版社,1999.11WuEn-hua.ThepresenttechniquesituationandchallengeoftheGPUusedasaGPGPUJ.JournalofSoftware,2004,15(10):14931504.吴恩华.图形处理器用于通用计算的技术现状及其挑战J.软件,2004,15(10):14931504.12LosassoF.HoppeH.Geometrycllpmaps:TerrainRenderingUsingNestedRegularGridsA.In:ProceedingsofACMSIGGRAPHC.LosAngeles,California,USA,2004:769776.13JensSchneider,RudigerWestermann.GPU?friendlyhigh-qualityterrainrenderingJ.JournalofWSCG,2006,14(1):4956.14ClasenMalte,HegeHans-Christian.TerrainrenderingusingsphericalclipmapsA,In:ProceedingsofIEEEConferenceonVisualizationC,Lisbon,Pougal,2006:9198.15FernadoRandima,KilgardMarkJ.TheCgTutorial:TheDefinitiveGuidetoProgrammableRealTimeGraphicsM.Beijing:Posts&TelecomPress,2004.FernadoRandima,KilgardMarkJ.cg教程可编程实时图形权威指南.北京:人民邮电出版社,2004.16FernandoRandima.GPUGemsProgrammingTechniques,Tips,andTricksforRealTimeGraphicsM.Beijing:Posts&TelecomPress,2006.RandimaFernando.GPU精粹实时图形编程的技术,技巧和技艺M.北京:人民邮电出版社,2006.