第37卷第3期2009年3月同济大学学报(自然科学版)JO URNAL OF TON GJI UNIVERSITY (NATURAL SCIEN CE )Vol .37No .3　Mar .2009文章编号:0253-374X (2009)03-0414-05收稿日期:2007-11-29基金项目:教育部新世纪优秀人才支持计划资助项目(NCE T 050385);上海市登山行动计划资助项目(06dz12012)作者简介:刘　丁(1981—),男,博士生,主要研究方向为地理信息系统.E -m ail :liu ding1981@yah oo .com .cn许惠平(1965—),男,教授,理学博士,博士生导师,主要研究方向为地理信息系统.E -mail :xuhuiping @tongji .edu .cn基于OpenGL 索引顶点数组的大尺度海面LOD 算法刘　丁,许惠平,陈华根(同济大学海洋地质国家重点实验室,上海200092)摘要:分析了大尺度海面与地形数据的区别,提出一种基于O penG L 索引顶点数组的细节层次(LO D )算法.采用视点相关技术,建立了一种网格模板,将每级网格划分为8个矩形区域和4个T 型裂缝缝补区域,使用索引顶点数组高效绘制所有区域.根据视点进行可见性判断,对可见点使用P M 海浪谱实时反演海面数据,逼真地实现了大尺度海面的漫游.关键词:视点相关细节层次;大尺度海面;O pe nG L ;索引顶点数组;网格模板中图分类号:T P 391.9　文献标识码:AA LOD Algorithm for Large Scale Ocean Based on OpenGL Index Vertex ArrayLIU Di ng ,XU Huiping ,C HEN Huagen(Sta te Key La boratory of Marine Ge ology ,Tongji University ,Sha nghai 200092,China )Abstract :Starting from the analysis of difference between large scale ocean and terrain ,the paper presents a level ofdetail (L O D )algorithm based on OpenGL index vertex array .A grid template is built with the view -dependent method .The template treats a grid as 8normal rectangle areas and 4repair areas of T -crac ks and dynamically c alc ulates index a rray for each area .By sending vertex array and index arrays of each grid to O penG L ,the tem plate renders each grid of LOD efficiently .Then ,a real -time vivid ocean waves scene is ac hieved by adopting the view -dependent method to decide which vertexes should be inverted by P M wave spectrum ,Key wo rds :view -dependent level of detail ;large sc ale ocean ;O penG L ;index vertex array ;grid template 随着海洋科学的日益兴盛,大尺度海面的实时模拟在海洋研究中的重要性也日渐突显.准确高效地模拟自然界的海面一直是一个难点,国内外许多学者对此进行了大量的尝试.在解决模拟的准确性方面一般有四种方法:①通过求解流体力学方程组(Navie r -Stokes 方程)描述海浪内部各质点的运动[1];②采用几何曲线(面)如正弦曲线(面)、Bezier 曲线(面)等来描述海浪的形状[2];③采用分形几何学的方法对基本曲线(面)进行变形生成随机海浪[3];④用线性叠加法采用适当的海浪谱反演出海浪[4-6].第四种方法建立在海洋学已有的统计、观测成果的基础上,在目前使用最多,因此本文使用该方法选择P -M 海浪谱[7]对海面进行实时反演.在解决模拟大规模地形数字高程模型(digital elevation mo del ,DEM )的效率方面,目前已经有了许多优秀的算法,例如基于二叉树的实时最优适配网络(ROAM )[8]、受限四叉树[9]和视点相关渐进网络[10]等,但这些算法需要对数据进行预处理,把地形剖析至多个层次,运算量很大,在模拟大规模动态海面时效率不高.其原因在于海面DEM 与地形DEM 有本质的区别:①海面区域远远大于一般地形区域;②海面是动态的,而地形是固定不变的,前者数据点需要实时计算而后者可以预先计算出所有数据点;③粗糙度是反映局部起伏剧烈程度的特征量,海面各点的粗糙度比较平均,而地形的粗糙度变化很大,需要对后者进行判别;④海面数据点的高程通过反演进行计算,而地形数据点的高程是通过插值进行计算,前者运算量更大.根据这些区别,本文在采用P -M 海浪谱的基础上,提出一种基于OpenGL 索引顶点数组的大尺度海面细节层次(level of detail ,LOD )算法,将每一级网格作为一个模板来绘制,同时只做视点相关判断而不做裁剪,无需复杂的实时简化算法,即可实现海面的高效动态模拟.该算法的基本思想是:计算出最　第3期刘　丁,等:基于OpenG L 索引顶点数组的大尺度海面LOD 算法 低级网格的水平坐标,然后将视点所看位置附近的网格不断进行二分剖分,按模板要求实时生成每一级的网格点水平坐标(8个矩形区域)和法线向量并对产生的T 型裂缝(4个缝补区域)进行缝补;接下来做视点相关判别,只对视线范围内的网格点反演计算其高程和法向量,最后调用模板使用OpenGL 索引顶点数组对每级网格进行绘制.接下来再对整个算法和其中的一些关键技术(T 型裂缝缝补、法线平均和视点相关性判断)进行详细的阐述.1　网格模板的建立首先根据视点与海面距离确定LOD 的级数、每级的网格数和每级网格占据上一级网格区域的大小.例如:当视点离海面相当远时,可以设置较低的LOD 级数.如图1a 所示,设为2级,最低级网格数设为4×4,下一级网格占据上一级网格的2×2区域,该区域根据视点位置动态确定,以保证视点所看位置始终在该区域中心,并对该区域进行二分剖分;这样,每一级网格的分辨率均是最低分辨率的2n(n =0,1,2,……)倍,并且在动态漫游过程中,视点所看位置的细节层次始终为最高级,可以消除渐进描绘中的图像跳动.当视点逐渐接近海面时,动态改变上述参数,如图1b ,LOD 变为3级,第一级网格为8×8,下一级网格占据上一级网格的4×4区域.图1　不同等级的LOD 网格Fig .1　LOD o f different level接下来,由最低级至最高级计算出每级网格点的坐标值,然后将其传入OpenG L 顶点数组.本算法不同于通常地形DEM 的LOD 算法:不是将网格按照单独的三角片来绘制,而是将除顶级网格外的每一级网格划分为如图2所示的8个矩形区域(区域1～8)和4个T 型裂缝缝补区域(区域9～12),每个区域作为一个整体来绘制,所有区域又整合为一个更高层次的整体来处理.图中虚线区域为高一级的网格.因此,只需依次计算每个区域的索引数组(共12个),再配合先前计算得到的1个顶点数组就能绘制出各级网格.显然,除顶级网格外的每一级网格都基于相同的数据结构和算法,因此,本算法创建了一个网格模板,该模板包含1个顶点数组和12个索引数组,通过索引数组的指引依次绘制如图2所示的12个矩形区域.只要给定每一级网格的级数、中心点位置,该模板就能迅速计算出指定网格的三维坐标并进行渲染.对于任意多级的LOD ,可以循环调用该模板由底至顶地绘制每一级网格.最后,在中心区域正常绘制最顶级网格,就完成了整个海面LOD 的绘制.图2　网格模板Fig .2　Template of grid2　T 型裂缝的缝补因为本算法是采用与视点相关的LOD 网格,离视点近的网格密度大、细节高,离视点远的网格密度小、细节低.因此,在细节层次等级不一样的网格边缘会产生“T ”型裂缝,本文采用如图3a 所示的方法对网格的边界进行实时的缝补:在两个不同等级的网格边界处,通过线性插值得到低一级网格上的二分点,图中黑色实心点即为插值得到的二分点,黑色空心点为网格实际数据点,实心点与相邻的两个空心点在同一条直线上.这些插值点与高一级网格的边界点组成一个矩形区域(图中黑色粗线标示区域),使用索引顶点数组绘制该区域就实现了裂缝的缝补,如图3b 所示.图3　T 型裂缝缝补Fig .3　Repair o f T -cracks415 同济大学学报(自然科学版)第37卷　3　法线的平均一个物体的法线向量定义了其表面在空间的方向,特别是其相对于光源的方向,OpenGL利用这些向量来确定物体在顶点处接受了多少光,只有在加入了光照条件后,三维物体才会有鲜明的三维效果.最普通的法线计算方法是计算每个三角片的法线,然后将其作为顶点法向量传入OpenG L进行绘制,但是这样的绘制方法会在变化剧烈的区域得到锯齿状的光照效果.因此本文使用平均法线的方法来指定每个顶点的法向量:由于网格模板的建立是基于已经计算得到网格所有数据点的基础上,因此可以在计算索引数组的同时非常方便地计算出共享一个顶点的每个三角片的法线,一共六个法向量,然后求出它们的平均值作为该点的法向量,由于OpenGL要求法向量为单位向量,所以求出的平均法向量要做归一化.从直观上来讲,这个平均法向量就是对共享一个顶点的每个三角片的法线在方向上进行了平均.4　视点相关性判别在绘制大规模的LOD地形时,会使用复杂的算法进行视点相关性判别,将不在当前视线范围内的三角片裁剪掉,以提高图形处理器(g raphic pro cessing unit,GPU)绘制的效率.但是与地形模拟不同,在实时模拟大尺度海面的时候,大量计算时间消耗在CPU用海浪谱对海浪的反演上,而不是GPU对三角片的渲染上.同时,利用索引顶点数组一次绘制整片矩形区域的速度比绘制独立的三角片要高出3～7倍[11],因此,本算法对地形LOD中的视点相关性判别方法进行了简化:不做可见性裁剪,只做可见性判断,即不在视场范围内的网格点的高程z 值不做海浪谱的反演计算,直接赋0值,反之则利用P-M海浪谱根据网格点的(x,y)值计算出z值,这样既简化了视点相关性裁剪算法,又大大节省了不可见点反演的计算量,同时还保证了网格模板能够始终按照12个矩形区域绘制每一级网格.一般的可见性判断会同时考虑视见体的六个面,而海面相对地形来说平缓得多,视野远得多,所有网格都在视见体的上下平面范围内,因此只需考虑视见体的左右两个面.原理如图4所示:L点是视见体左平面与海平面的交线上的一点,R点是视见体右平面与海平面的交线上的一点,E ye点为视点.求出:p—1=l—1×l—2,p—2=r—1×r—2.当点P在视线范围内时,如图4a所示,p—1和p—2的方向都应该水平向上或为零,即p—1和p—2的z值应该均非负;当点P在视线范围外时,如图4b所示,p—1和p—2的z值应该不全为非负值[12].图4　网格点可见性判断Fig.4　Grid point visibility judgment为了直观表达上述算法,将计算用的可视角度设定为小于实际可视角度,经过视点相关的可见性判断后,绘制的海面LOD如图5所示.图5　可见性判断后绘制的LOD网格Fig.5　Rendered L OD after visibility judgment5　使用P-M谱反演海面实际的海浪是一个非常复杂的自然现象,简单的波动理论不足以描述真实的海浪.但对于充分成长的风成浪,在一段时间内,将其作为一个平稳随机过程是足够精确的[13].它可由多个(理论上应为无穷多个)不同周期和不同随机初始相位的余弦波叠加而成,为了能够产生平面上多个方向的子波叠加形成海浪场,将海浪频谱的能量在各个方向展开,从而形成了海浪的方向谱[14]:η(x,y,t)=∑Mi=1∑Nj=12S(ωi,θj)ΔωiΔθj·cos(k i x cosθj+k i y sinθj-ωi t+εij)式中,η(x,y,t)是固定点(x,y)处的海面在t时刻的瞬时高度,ωi和k i是第i个组成波的圆频率和波数,εij为初始相位.S(ω,θ)为方向谱,一般可以写成如下形式:S(ω,θ)=S(ω)G(ω,θ).S(ω)为海浪的频谱,G (ω,θ)为海浪的方向分布函数.本算法采用P-M海浪谱,即S(ω)=(0.78/ω5)exp[-3.11/(ω4H21/3)],式中,H1/3为有效波高,即:将所有连续测量的波高416　第3期刘　丁,等:基于OpenG L索引顶点数组的大尺度海面LOD算法 按大小排列,取其总个数的三分之一大波波高的平均值.6　实验结果本文将上述算法用和OpenGL编程实现,电脑配置为:Intel Quad2.4G CPU,NVIDIA Quadro FX3500显卡,2G内存,Window s XP操作系统.实验时组成波波数设定为16个(M=16),传播方向设定为8个(N=8),在1024×768的分辨率下,当靠近海面时,LOD设置为6级,最低级网格数为32,能够达到流畅的40帧·s-1,实验效果如图6所示.图6　实验效果图Fig.6　Experimental results7　结论本文提出的基于OpenGL索引顶点数组的大尺度海面LOD算法,充分考虑了大尺度海面数据与大规模地形数据的区别,算法理论简单可行,在大尺度海面实时模拟的逼真度和效率上都取得了较好的效果.相对于其他海面LOD算法有如下优势:①实现方便,无需复杂的DEM粗糙度判别算法;②根据视点实时设置LOD级数和网格数,不再受预处理数据的限制;③通过OpenG L索引顶点数组按网格模板成片绘制区域,大大提高绘制速度;④只做可视性判断不做三角片裁剪,节省大量运算,提高了海面的实时反演和绘制效率.下一步的研究方向将从波浪的卷曲、破碎及泡沫,海面对光线的反射、折射以及洋流对海面的影响几个方面入手,以期获得更加真实的海面.参考文献:[1]　Foster N.Realis tic anim ation of liquids[J].Graphical M odeland Im age Processin g,1996,58(5):471.[2]　Fournier A.A sim ple model of ocean w aves[J].ACMSIGGRAPH Com puter Graphics,1986,20(4):75.[3]　严承华.分形仿真技术在海上视景图形显示中的应用[J].计算机工程,1994,20(1):36.YAN Chenghua.Application of the fractal simu lation to thevisu al scene of the sea[J].C om puter Engineering,1994,20(1):36.[4]　M astin G A,Watterberg P A,M areda J F.Fou rier syn thesisof ocean s cen es[J].IEEE Computer Grap hics andApplication s,1987,7(3):16.[5]　Tes sen dorf J.Simulating ocean w ater[C]∥SIGGRAPH'00:Cou rse Notes,New Orleans:ACM Press,2000:23-28. [6]　杨怀平,孙家广.基于海浪谱的波浪模拟[J].系统仿真学报,2002,14(9):1175.YANG Huaiping,S UN Jiagu ang.W ave sim ulation based onocean wave spectrums[J].Journal of Sys tem Sim ulation,2002,14(9):1175.[7]　Pierson W J,M osk ow itz L.A p rop os ed spectral form forfully developed w ind s eas based on similarity theory of S.A.Kitaigorod skii[J].J ournal of Geop hysical Research,1964,69:5181.[8]　Duchaineau M,Wolin sky M.ROAM terrain:real-timeoptimally adapting m es hes[C]∥IEE E Visualization.LosAlamitos:IEEE Compu ter S ociety Pres s,1997:81-88. [9]　Pajarola rge scale ter rain visualization usin g the417 同济大学学报(自然科学版)第37卷　restricted quad tree triangulation[C]∥Proceedings of IEE EVisualization.Los Alamitos:IE EE Computer S ociety Pres s,1998:19-26.[10]　H oppe H.Progres sive meshes[C]∥SIGG RAPH'96:An nualConf Series,New Orleans:Addison W esley,1996:99-108.[11]　Larsen B D,Chris tensen N J.Real-time ter rain renderingu sing smooth hardw are optimized level of detail[J].J ou rnalof W SCG,2003,11(1):1213.[12]　吴晶,徐晓刚,王建国,等.大尺度海面的快速漫游[J].系统仿真学报,2006,18(9):2505.W U Jing,XU Xiaogang,WANG Jiangu o,et al.Real-timew alkth roug h of large scale ocean[J].Jou rnal of SystemSimulation,2006,18(9):2505.[13]　陆志慧.大规模虚拟战场环境中海洋场景的建模与绘制技术研究[D].长沙:国防科学技术大学计算机科学与技术学院,2005.LU Zhihui.The study of m odeling and rendering tech nologyfor m arin e scenes in large-s cale virtual battlefield environment[D].Changsha:C om puter C ollege.National University ofDefen se Tech nology,2005.[14]　马杰,田金文,柳健,等.三维海浪场的数字模拟及其动态仿真[J].系统仿真学报,2001,13:40.M A Jie,TIAN Jinw en,LI U Jian,et al.Numeric imitationand dy namic simulation of three-dimensional ocean w ave[J].J ou rnal of S ystem Sim ulation,2001,13:40.(上接第403页)的.然后对现有路径负载均衡算法进行分析比较,提出了一种可屏蔽失效路径的动态负载均衡算法,并用理论和实验证明了该方法是有效的.通过本文的研究可以看出负载均衡算法对于对于提高系统可用性有着重要意义.如何对不同系统参数信息进行科学有效的分析,迅速做出负载转发策略,对于提高负载均衡的算法效率有很大的作用,这是今后继续深入研究的一个切入点.参考文献:[1]　GAN Xuehong,Sch roeder Trevor,Goddard Steve,et al.H ighly Available and S calab le Clu ster-based W eb S ervers[DB/O L].http:∥/gan99highly.html,1999-10-25.[2]　Dias M,Kish W,M u kherjee R,et al.A scalable an d highlyavailable W eb server[C]∥Proceeding of41s t IEEEInternational C onference on Data Engineering.Santa C lara:IEEE Compu ter S ociety Pres s,1997:85-92.[3]　Iyer R,Kalbarc zyk Z,Kalyanakrishnan M.Performance evaluationperformance evaluation origins and directions:measurement-basedanalys is of netw orked system availability[M].H eidelberg:Springer,2000:161-199.[4]　T hak ur A,Iyer R K.Analyze-NOW-An environment forcollection and analysis of failures in a netw ork of wo rk stations[J].IEEE T ran saction on Reliability,1996,45(3):561. [5]　H ortos W S.Genetic routing algorithms to optimizeavailability in b roadband w ireless n etw orks with loadbalan cing[C]∥T he International S ociety for OpticalEngineering.O rlando:SPIE,2002:9-27.[6]　Faizan J,El-Rew inni H,Khalil M.Introducin g reliability andload balancing in home link of mobile IPv6b as ed netw orks[C]∥Proceedings for ICPS:2006ACS/IE EE InternationalConference on Pervasive Services.Lyon:Perser,2006:98-107.[7]　Ganesh R B,Thirumurthy R,Gonsalves.Load Bal anc ing M odelfor M ultiple Internet Access Links[C]∥Proceedings of ICCC2002-15th International Conference on Computer Communication.Los Angeles:IEEE,2002:228-238.[8]　Adam an tios M,Pantelis V.Application of quantitativeaccelerated life m odels on load sharing redundancy[C]∥IEE E50th Ann ual Reliabil ity and M aintainability S ymposium.Tu sson:Reliasoft Co rp,2004:293-296.[9]　N N,M athematical models of redundancy[M].Blatteeding:VDI-Richtlinie4008,1986.[10]　Balandin I S,Heiner P A.Dynamic localized load balancing[C]∥Proceeding of Performance and Control of Next-Generation Commu nication s Netw orks.Orlando:SPIE,2003:164-172.418。