摘要
地形实时绘制是虚拟现实技术中的重要组成部分,在军事仿真、地理信息系统等领域有着广泛的应用。但是实时绘制技术主要是面向单机的,由于单个机器硬件条件的限制,会出现在多用户同时访问情况下,地形服务器或工作站不能满足用户的实时绘制。
本文在研究单机地形实时绘制技术和网格计算的基础上,提出了基于网格环境的地形绘制技术。利用网格中的任务调度,解决多用户同时访问时,地形实时绘制因为硬件条件造成的绘制效率低下问题。本文在利用网格任务调度实现地形绘制方面主要做了以下工作:
1.提出了符合地形块特点的T-MIN-MIN任务调度算法,并设计了地形块调度模型。T-MIN-MIN算法根据视点周围地形块的层次细节特点,首先调度一定比例的大地形块,然后按照MIN-MIN算法调度剩余的地形块,尽量保持资源之间的负载平衡。实验表明T-MIN-MIN算法具有更好的调度效果。
2.由于任务调度是按照运算量分配任务,所以本文提出了地形块LOD生成时间的估算方法。方法通过判断视点到三角形斜边中点的距离是否落在三角形的误差判据球内,找到满足条件的节点,通过公式快速计算出需要生成三角形的大体数目。地形块按照估算值进行分配,避免整个调度无任务量的盲目分配,保证了各资源之间的负载平衡。
3.针对视点变化后的地形绘制问题,在现有的网格任务负载平衡的基础上,提出了一种视点变化后的任务动态调整方法。该方法针对视点变化后地形块的细节层次变化,动态地对任务进行调整,减少地形块调整带来的时间和资源消耗。
最后对多用户的地形实时绘制在服务器和网格两种环境下进行了对比测试。结果表明,网格中地形分块调度方法,能更好地实现在多用户同时访问情况下的地形实时绘制。
Real-time rendering terrain is an important component of virtual reality technology, it have a wider range of applications in the military simulation, geographic information systems, and other fields. However, real-time rendering technology mainly face the single computer, as the hardware conditions restrictions of individual machines, it may appear that the terrain server or workstation users can not satisfy real-time rendering while multi-user visit at the same time.
Based on the study of single computer rendering technology and grid computing, this paper proposes a terrain rendering technology based on the grid. Using grid task scheduling to solve the inefficiency of terrain rendering caused by hardware reason in multi-user visit at the same time. This paper mainly did the following work to achieve terrain rendering in the use of grid task scheduling:
1. This paper porposed a T-MIN-MIN scheduling algorithm with the terrain characteristics, and designed a terrain block scheduling model. According to the terrain characteristics, T-MIN-MIN algorithm scheduled some certain proportion terrain blocks, and scheduled other blocks by MIN-MIN algorithm, this method can maintain load balancing. The test proved T-MIN-MIN scheduling algorithm had better effect.
2. As the task scheduling allocated by assignments of tasks, so this paper proposed terrain block LOD time estimation method. This method found to meet the conditions of the node by judging the distance between the midpoint and midpoint of triangle hypotenuse whether landed the error criterion ball, and fast calculated the overall number of triangular formation by the formula. The terrain block allocated by estimation, which can avoid the scheduling of tasks allocated blindly, ensure the load balance between the resources.
3. Against terrain rendering problems after viewpoint changed, this paper proposed a task dynamic change method after viewpoint changed base on the exiting algorithm of grid tasks’load balance. And against the changing of level detail after viewpoint changed this method dynamically adjust the mandate to reduce terrain block adjustment time and the consumption of resources.
Finally, this paper compared the multi-user real-time rendering of the terrain in the server with grid environment by tests. The results show that the grid can better achieve real-time rendering of the terrain while multi-user visit at the same time.
引文
[1]赵沁平. DVENET分布式虚拟环境[M].北京:科学出版社, 2002
[2] M.Reddy,Y.G.Leclerc,L.lverson,N.Bletter,and K.Vidimce.Modeling The Digital Earth in VRML[J].In Proceedin of SPIE-The Intemational Society for Optical Engineering, 3905:113-121.
[3]杨晓霞,齐华.一种大规模地形的高效绘制算法[J].计算机工程与应用,2005 41(14):229-232.
[4]李德仁.论21世纪遥感与GIS的发展[J].武汉大学学报(信息科学版),2003,28(2):127-131.
[5] R.Nabil. Physically-based Modeling and Real-time Simulation of Terrain Cratering and Fragmentation due to Explosions[D]. Orlando: University of Central Florida, 2001.
[6] L.D.Floriani, P.Marzano, E.Puppo Multiresolution Models for Topographic Surface Description[J]. The Visual Computer, 1996,12(7):317-345
[7] P.Lindstrom, D.Koller, W.Ribarsky et al. Real-time, continuous level of detail rendering of height fields[J]. In: Proceedings of SIGGRAPH’96, New Orleans, 1996:109-118.
[8] M.Duchaineau, M.Wolinsky, D.E.Sigeri et al. Roaming terrain:real-time optimally adapting meshes[A]. In: Proceedings of IEEE Visualization’97[C], Phoenix. 1997:81-88.
[9] H. Smooth.Hoppe View-dependent Level-of-detail Control and its Application to Terrain Rendering. In: Proceedings of IEEE Visualization’98,New Caledonia, 1998:135-142
[10] Jonathan Blow.Terrain rendering at high levels of detail.In:Proccedings of Game DeveloPers Conferenee .SanJose,Califomia,2000
[11]戴晨光,邓雪清,张永生.海量地形数据实时可视化算法[J].计算机辅助设计与图形学学报, 2004, 11
[12] Ian Foster,Carl Kesselman.金海,袁平鹏,石柯译.网格计算(第二版) [M].电子工业出版社.2004
[13]徐志伟,冯百明,李伟.网格计算技术[M].北京:电子工业出版社, 2004
[14] P.Lindstrom, V.PascucciTerrain Simplification Simplified:A General Frame work for View-Dependent Out-of-Core Visualization.IEEE Transactions on Visualization and Computer Graphics.2002
[15]卓广晟,周波,徐晓华.视点相关实时地形的生成方法[J].计算机工程,2000
[16]石教英.虚拟现实基础及实用算法[M].第一版.北京:科学出版社,2002,76-159
[17] C.Giger Digital Elevation Models and Digital Terrain Models [R]. Zurich : GeoInformation Technolgies Group, Swiss Federal Institute of Technology, 2002
[18] P.Lindstrom,V.Pascucci Visualization of Large Terrains Made Easy[A]. Proceedings of the Conference on Visualization'01[C], Washington:IEEE Computer Society, 2001:363-370
[19] H. Smooth.Hoppe Progressive Meshes[A]. Proceedings of SIGGRAPH’96[A], LosAngels,USA, 1996:99~108
[20]李辰.实时三维地形渲染系统的研究和开发[D].合肥:中国科学技术大学,2002
[21] John S.Falby, J.Michael Hierarchical Data Structures for Real-Time Three-Dimensional Visual Simulation.Computer&Graphic,2002,17(1):65-69
[22]都志辉,陈渝,刘鹏.网格计算[M],清华大学出版社,2002.
[23] N.Fujimoto, K.A.HagiharaComparison Among Grid Scheduling Algorithms for Independent Coarse-Grained Tasks. In:Proc.of the 2004 Symp.on Applications and the Internet-Workshops.Washington:IEEE computer society Press,2004:674-680
[31] Message Passing Interface Forum.MPI:A message passing interface standard.University of Tennessee,Tech Rep,1994.P94~230
[24]冷志光,汤晓安等.大规模地形动态快速绘制技术研究[J].系统仿真学报.2006(10):2832~2835
[25] R.Pajarola Large Scale Terrain Visualization Using the Restricted Quadtree Triangulation[A]. Proceedings of the Conference on Visualization’98[C], Washington:IEEE Computer Society, 1998:19-26
[26]王林旭,李思昆,潘晓辉.动态地形的实时可视化[J].计算机学报, 2003,6(11):1524- 1531
[27] J.Blow Terrain Rendering at High Levels of Detail[A]. Proceedings of Game Developers Conference 2000[A] ,San Jose ,2000:1-6
[28]殷媛.大规模地形分块绘制的研究与实现[D].北京:北京航空航天大学, 2006
[29] Liu Zhanping, Wang Hongwu, et al. VDDMTM: A View-Dependent Dynamic Multi-resolution Terrain Model[A]. The sixth international conference on Computer Aided Design and Computer Graphics[C], Shanghai, China, 1999:1209-1214
[30] T.Ulrich Rendering Massive Terrains Using Chunked Level of Detail Control. Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, San Antonio, Texas,2002.
[31]陈国军.面向分布交互仿真的动态地形实时绘制技术的研究[D].[博士论文]北京:北京航空航天大学.2007
[32]王宏武,董士海.一个与视点相关的动态多分辨率地形模型[J].计算机辅助设计与图形学学报. 2000, 12(8): 575~579
[33]曹怀虎等.网格环境中任务调度算法的研究[J].计算机工程与应用,2004年.第40卷第5期:87~90
[34]张宇晴,终振声,胡旦华.分布式系统中动态负载平衡算法的研究[J].计算机仿真,2003,20(9):69-71
[35] Henri Casanova.SimGrid:A Toolkit for the Simulation of Application Scheduling, Proceedings of the 1st International Symposium on Cluster Computing and the Grid,2001,P430
[36]王意洁,肖农,任浩等.数据网格及其关键技术研究[J].计算机研究与发展.2002. 39 (8) : 943-947.
[37]刘文杰,王刚,巴才国.网格安全体系结构及GSI安全策略研究[J].计算机工程,2005. 31(17):133-136.
[38]王一夫,陈松乔,范国闯.网格资源分配管理的问题研究及模型设计[J].计算机应用研究,2005. 10, 85-88.
[39] Alan Bradley, Kevin Curran, Gerard Parr. Discovering Resourcesin Computational GRID Environments[J]. The_Journal of Supercomputing,2006.35(1):27-49.
[40] GT4 Admin Guide http://www.globus.org/toolkit/docs/4.0/admin/ 2007