您的当前位置：首页一种基于嵌入式环境的海量DEM数据快速绘制算法

一种基于嵌入式环境的海量DEM数据快速绘制算法

来源：年旅网

　第30卷　第1期　2009年　　1月航　空　学　报

ACTAAERONAUTICAETASTRONAUTICASINICAVol130No11Jan.　2009

　　文章编号:1000263(2009)0120132204

王金岩1,2,何亦征2,谢剑斌3,刘通3,庄钊文3,敬忠良4

(11上海交通大学电子信息与电气工程学院,上海　200030)

(21中国航空无线电电子研究所,上海　200233)

(31国防科学技术大学电子科学与工程学院,湖南长沙　410073)

(41上海交通大学空天科学技术研究院,上海　200030)

RapidProtractingArithmeticaboutLargeScaleDEMDataBasedonEmbeddedEnvironment

WangJinyan1,2,HeYizheng2,XieJianbin3,LiuTong3,ZhuangZhaowen3,JingZhongliang4

(1.SchoolofElectronicsandInformationTechnology,ShanghaiJiaotongUniversity,Shanghai　200030,China)

(2.ChinaNationalAeronauticalElectronicRadioResearchInstitute,Shanghai　200233,China)

(3.SchoolofElectronicsEngineering,NationalUniversityofDefenseTechnology,Changsha　410073,China)(4.InstituteofAerospaceScienceandTechnology,ShanghaiJiaotongUniversity,Shanghai　200030,China)

摘　要:采用海量数字高程模型(DEM)数据的地景模型在军事与民用领域具有非常重要的作用,其快速绘制问题是三维真实地形信息可视化的一个关键问题。提出了动态数据子块的概念,通过经纬度和飞行参数索引快速实现数据子块的装载,再通过有效数据组织和改进四叉树方法实现地形快速绘制。新算法在嵌入式环境中实现了海量DEM数据的实时绘制,而且画面流畅,无滞后现象。关键词:嵌入式环境;数字高程模型;装载;地形显示;计算机图形中图分类号:TP391.41　　　文献标识码:A

Abstract:Terrainmodelsarewidelyusedinthefieldsofaerospaceexplorationaswellascivilandmilitaryavia2tion,suchaswarfieldsimulation,flightvisualization,characteristicsmatching,specialeffectsinmoviesandtelevisions,etc.Thisarticlepresentsanewconceptcalledthesub2datasetandproposesanalgorithmtorealizeitsdataloadingrapidlybymeansoftheindexesofflightparametersandlongitudeandlatitudeinformation.Bymeansofthismethodlargescaledigitalelevationmodel(DEM)dataareloadedandrenderedreal2time,smoothlyandrapidly.Nowthemethodhasbeenusedonembeddedplatformandaccomplishedsomeflight2emulationexperiments.

Keywords:embeddedenvironment;digitalelevationmodel;loading;terrainvisualization;computergraphics

　　地景模型在军事与民用领域具有非常重要的

作用,如飞行仿真、飞行可视化、落点分析、军事战略与战术指挥以及地形特征匹配与仿真等。由于地景模型通常使用数字高程模型(DEM)数据,而模型数据量极其巨大,如何实现快速绘制仍然是一个相当复杂的课题。尤其是通常使用海量DEM数据的地景模型快速绘制问题是三维真实地形信息可视化的一个关键问题[123]。

针对海量DEM数据快速绘制的研究主要分为两个方面:场景简化和数据组织。场景简化是设计有效的简化模型对地形网格进行简化,使得简化后场景在视觉上与原始场景基本一样。J.H.Clark[1]给出了用于可见面判断算法的几何层

次模型,使覆盖屏幕较小区域的物体可以用较粗

收稿日期:2007209216;修订日期:2008211218基金项目:国家自然科学基金(6014102)

通讯作者:王金岩E2mail:wang_yuchen666@sina.com

的模型表示;M.J.DeHaemer等[4]提出了基于规则四边形网格表示物体的简化多边形网格方法;B.Hamann[5]给出了基于三角形移去的模型简化算法;P.Lindstrom等[6]对规则网格表示的地形模型提出了一种实时的连续层次细节(LOD)绘制算法;J.C.Xia等[7]提出了一种动态的、与视点相关的多边形网格简化算法。数据组织是指设计有效的数据组织和装载算法,解决海量DEM数据基于外存实时绘制速度缓慢的问题。L.Bal2melli[8]使用Z型填充曲线有效地表示网格的四叉树结构;P.Lindstrom等[9]在地形的可视化中采用了隔层四叉树、白色四叉树和黑色四叉树3种数据结构,并给出了有效的顶点索引,提出了类似于层次Z型的数据排列,用层次П型的数据组织地形顶点;陆艳青[10]提出了基于层次二叉树的顶点多分辨率组织,可有效地进行数据预测和装载。

嵌入式环境的软硬件受应用环境严格,

　第1期王金岩等:一种基于嵌入式环境的海量DEM数据快速绘制算法　133

资源相对较少,要求嵌入式软件、算法、程序等尽可能少占用资源。同时对海量DEM数据绘制算法要求更高,它不仅要求算法计算量小、耗时少,而且要求算法易于移植。国内外对于海量DEM数据绘制算法的研究都针对图形工作站平台,针对嵌入式环境的相关研究还不多见。

本文作者在文献[11]中提出了数据子块的概念,实现了DEM数据的快速装载。这里结合嵌入式环境的特点和飞行中存在的实际问题,提出了动态数据子块的概念。通过实时获取当前经纬度信息和飞行参数实现数据的快速装载,然后将动态数据子块的数据进行有效组织,再利用改进的固定四叉树实现数据快速绘制。新算法实现简单、计算量小、易于移植。目前在基于PowerPC750硬件平台和VxWorks操作系统的嵌入式环境中进行多个子任务联调时速度快,画面平缓流畅,地形绘制无滞后现象。

据块的情况。图1所示为动态数据子块占有9个DEM数据块的例子,其中灰色矩形框表示动态数据子块,9个白色矩形框表示其占有的DEM数据块。数据装载就是将动态数据子块所占有的数据块中相应位置的数据读入缓冲区,以便绘制。这里,动态数据子块的宽度和高度分别为W和H,起始点P(即左下方顶点)的坐标为(Px,Py),DEM数据块的宽度和高度分别为w和h,那么

x0=w-Px,y0=h-Pyx1=(W-x0)%wy1=(H-y0)%hkx=(W-x0-x1)/wky=(H-y0-y1)/h

(1)

式中:符号%表示整除后取余数;x0和x1表示动态数据子块横向上占有的非整块DEM数据块位置信息;y0和y1表示其纵向上占有的非整块DEM数据块位置信息;kx和ky分别表示其在横向和纵向上占有整块DEM数据块个数,本例中kx=ky=1。求取以上参数后即可方便地读取DEM数据文件中相应位置的DEM数据,实现动态数据子块的快速装载。

1　DEM数据的快速装载与组织方法

文献[11]提出了数据子块的概念,将DEM文件中用于当前显示的那一部分固定尺寸的数据称为数据子块,并提出了快速装载方法。但是在实际飞行过程中,由于飞机的飞行高度和俯仰角等飞行参数经常变化,这样可视场景的尺寸也随之变化,在这种情况下,装载固定尺寸的数据子块就无法正确显示当前的实际场景。因此,用于显示当前场景的数据子块的尺寸应当是可变的,这里称之为动态数据子块。111　数据快速装载方法

在飞行过程中,飞机所处的经纬度信息和飞行参数是可以实时获取的,由这些信息可以计算当前可视场景的经纬度信息。由于DEM数据与地形场景的经纬度信息有着一一对应的关系,这样就可以由当前可视场景的经纬度信息得到动态数据子块的相应信息。为了方便实现,动态数据子块采用规则网格模型,获取的动态数据子块信息包括起始位置P、宽度W和高度H。

依据获取的动态数据子块参数信息判别需要装载的数据文件,这里分两种情况进行处理。

(1)动态数据子块尺寸不大于以文件方式存储的DEM数据块尺寸。这种情况下,可以依据文献[11]提出的快速装载方法装载数据。

(2)动态数据子块尺寸大于DEM数据块尺寸。这种情况下,需要计算动态数据子块占有数

图1　动态数据子块与数据块关系图

Fig11　Relationshipofsub2datasetanddatablock

112　数据组织方法

为了实现嵌入式环境下地形数据的快速绘制,需要将装载的地形数据进行合理的组织。首先,在装载过程中,相邻两次装载的数据有较大重复,由于从文件(外存)中读取数据比较慢,为提高数据装载速度,另开辟了一个缓冲区,存储上一次装载的数据。在当前数据装载过程中,只需装载新数据,重复的数据直接从缓冲区(内存)拷贝到当前数据缓冲区相应的位置,通过牺牲少量存储空间的方式换取数据的快速装载。

13　4　

航　空　学　报第30卷

其次,动态数据子块尺寸不固定,不便于采用后续的固定四叉树方法实现地形的快速绘制。因此,在数据组织时,将动态数据子块数据看成一幅灰度图像(地形经纬度信息代表图像像素点坐标,地形高度信息代表图像像素点灰度值),利用图像缩放的方法将动态数据子块尺寸缩放为固定尺寸,以便于实现地形的快速绘制。

图3　顶点颜色计算流程图

Fig13　Flowchartofvertexcolorcalculation

2　动态数据子块数据快速绘制算法

211　四叉树地形绘制

由于嵌入式环境资源很少,传统的地形绘制

算法一般都比较复杂耗时。本文采用改进的四叉树方法绘制地形,算法的流程图如图2所示。计算顶点的颜色,首先要结合顶点周围4顶点高程计算其法向量,然后与光源向量取内积,将结果的正弦值作为光参量。同时依据顶点法向量和高程设置该顶点的三元色分量,再与光参量相乘,最后与光照模型融合,就得到了该顶点最终要显示的颜色值。非顶点颜色由顶点颜色插值生成。

为了实现实时绘制,选用简单的光照模型[10]:

(3)I=IaCa+IdCdnl+IsCs(nh)　　这里仅考虑太阳光的直接照射和环境泛光,

不考虑地形的遮挡关系。式中:I为最后的光亮度;Ia,Id和Is分别表示泛光、漫反射和镜面高光的亮度;Ca,Cd和Cs分别表示地表采样点处的泛反射、漫反射和镜面反射率;n表示法向;l表示光线方向;h表示视线和光线方向的角平分矢量。

m的变化范围一般是从1到10,它控制表面呈现

图2　地形绘制流程图

Fig12　Flowchartofterrainrendering

本文所绘制地形为固定网格结构,地形绘制

前首先对网格进行基于视点的四叉树剖分,依据近密远疏的原则,建立一棵包含区块三角化信息的固定四叉树。在三维场景漫游过程中,虽然子块数据不断更新,视点位置也在改变,但地形数据的横纵坐标和视点位置相对于固定网格来讲都没改变,故不需要重新剖分四叉树,只需相应地更新节点数据,就可以实时地得到用于三维显示输出的四叉树,从而快速实现地形绘制。

在绘制过程中,为了减少不同分辨率地形转化时引起的画面跳跃,采用了顶点渐变技术[2]来平滑地形,顶点渐变的公式为

p(x)=(1-x)p0+xp1,　x∈[0,1](2)式中:p0为节点细分前的顶点位置;p1为节点细分后的顶点位置。通过对节点细分前的顶点位置和节点细分后的位置进行线性插值,消除了不同层次细节网格转化时因细节度不同所引起的画面跳跃现象。212　颜色计算

的光洁度,表面越光洁m值越大,反之越小。在

实时绘制时,对三角形的每个顶点,使用光照模型计算顶点的光亮度值,然后对三角形投影到屏幕上的像素进行填充。

3　实验结果与分析

本文算法在基于PowerPC750硬件平台和VxWorks操作系统的嵌入式环境上通过了仿真实验,所用DEM数据为规则网格模型,网格尺寸为2×532,DEM数据块总数为1000个,设定动态数据子块缩放后的固定数据块尺寸为256×256。仿真实验取得很好的效果,整个漫游过程非常流畅,没有滞后现象,而且速度很快,平均帧率为35fps。图4为采用文献[11]的数据调度方法所截取的一帧仿真画面,数据子块尺寸为256×256,图5为采用本文数据调度方法所截取的同一

为了提高地形绘制的逼真度,需要给地形块添加颜色。地形块是由三角形面块填充而成的,所以这里主要是计算三角形各顶点的颜色,实现流程如图3所示。

帧仿真画面。可以看出,对于同一幅截图,本文算法显示的DEM数据量更大,可以适应可视场景尺寸的变化,因此在飞机的飞行高度和俯仰角等飞行参数变化时,采用动态数据子块装载数据的方法可以正确地显示当前的实际场景,满足实际飞行的海量DEM数据快速绘制要求。

　第1期王金岩等:一种基于嵌入式环境的海量DEM数据快速绘制算法　135

多个子任务联调时速度快,画面平缓流畅,地形绘

制无滞后现象,且易于向其他操作系统平台移植。

参　考　文　献

[1]　C1arkJH.Hierarchicalgeometricmodelsforvisiblesur2

facealgorithms[J].CommunicationsoftheACM,1976,19(10):725.

[2]　汤晓安,陈敏,孙茂印.地景模型的简化与快速绘制方法研

究[J].武汉大学学报:理学版,2001,26(4):3102314.

TangXiaoan,ChenMin,SunMaoyin.Anapproachofsimplificationandhigh2speedrenderingforterrainmodel[J].JournalofWuhanUniversity:NaturalScienceEdi2tion,2001,26(4):3102314.(inChinese)

[3]　姚丽,陈杰,窦丽华.一种基于DEM数据的可视化数字地

图4　数据调度算法仿真画面截图

algorithm[11]

[11]

Fig14　Ascreenshotfromsimulationimagesof

形绘制[J].北京理工大学学报,2002,22(3):3392342.

YaoLi,ChenJie,DouLihua.AmethodofvisualdigitalterraindisplaybasedonDEMdata[J].JournalofBeijingInstituteofTechnology,2002,22(3):3392342.(inChinese)[4]　DeHaemerMJ,ZydaMJ.Simplificationofobjectsren2

deredbypolygonalapproximations[J].ComputerGraphics,1991,15(2):1752184.

[5]　HamannB.Adatareductionschemefortriangulatedsur2

faces[J].ComputerAidedGeometricDesign,1994,11(2):1972214.

[6]　LindstromP,KollerD,RibarskyW,etal.Real2time

continuouslevelofdetailrenderingofheightfields[C]∥ProceedingsoftheACMSIGGRAPHConferenceonCom2puterGraphics.1996:1092117.

[7]　XiaJC,VarshneyA.Dynamicview2dependentsimplifica2

tionforpolygonalmodels[C]∥ProceedingsoftheIEEEVisualizationConference.1996:3272334.

[8]　BalmelliL.Rate2distortionoptimalmeshsimplificationfor

communications[D].Lausanne,Switzerland:EcolePoly2techniqueFederaledeLausanne,2001.

[9]　LindstromP,PascucciV.Terrainsimplificationsimpli2

fied:ageneralframeworkforview2dependentout2of2corevisualization[J].IEEETransactionsonVisualizationandComputerGraphics,2002,8(3):23922.

[10]　陆艳青.海量地形数据实时绘制的技术研究[D].杭州:浙

图5　本文算法仿真画面截图

Fig15　Ascreenshotfromsimulationimages

oftheproposedalgorithm

　　本文算法非常简捷,不需要在外存中事先组织数据,这样不仅避免文件碎片的产生,而且在仿

真过程中还可以根据需要随时增减DEM数据文件。另外,本文算法依据经纬度信息和飞行参数实时装载和绘制地形数据,不需要预测视点移动方向和预先装载非当前帧数据,这样相对于采用文献[9]算法的系统,CPU占用率减少30%以上,存储量占用率减少55%以上,能很好适应嵌入式环境资源少的特点。

江大学,2003.

LuYanqing.Onreal2timerenderingtechniqueofmasstopographicdata[D].Hangzhou:ZhejiangUniversity,2003.(inChinese)

[11]　XieJB,LiuT,ZhuangZW,etal.Anewmethodfordy2

namic2loadinglargeterraindatasetvisualizationinflightsimulation[C]∥Proceedings22ndWorkshoponDigitalMediaandItsApplicationinMuseumandHeritage.2007:2182222.

4　小　结

DEM模型是一种重要的地形模型,在军事与

民用领域具有非常重要的作用。由于其数据量极其巨大,因而对使用海量DEM数据的地景模型实现快速显示和快速绘制是三维真实地形信息可视化的一个关键问题和难题。本文结合嵌入式环境的特点,提出了一种面向工程的实用化海量DEM数据绘制新算法,算法在嵌入式环境中进行

作者简介:

王金岩(1966-)　男,博士,研究员。主要研究方向:控制理论与控制工程。

E2mail:wang_yuchen666@sina.com

(责任编辑:张利平)

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文