分形在虚拟现实场景中的应用研究
摘要
虚拟现实技术在计算机仿真、数字地球和游戏娱乐等领域都有广泛的应用。这些应用不仅要生成高度真实的复杂虚拟环境,而且用户要和虚拟环境进行互动,增强交互性和沉浸感。使人可以随心所欲的在环境中漫游,跟在真实的环境中体验一样。随着虚拟现实技术应用的深入,人们对虚拟场景的要求越来越高,远远超过了计算机图形硬件实时处理能力。因此如何在PC机上进行三维地形场景的真实感绘制是一个挑战性课题。
本论文从分形理论,三维地形建模和虚拟场景三个方面逐步进行了深入讨论。首先,讨论了基于OpenGL三维图形库及其工作原理,对三维真实感地形生成的基本过程进行了详细剖析,提出了一些加强渲染效果的具体措施。其次,基于分形的原理,对采用分形布朗运动模拟地形的方法进行了系统研究,给出了采用随机中点位移法中的“diamond-square”算法实现分形地形模拟的具体细节。第三,为了使生成的三维地形更具实时性,提出了一种改进的实时连续LOD生成算法。该算法首先采用Mortan码的编码方式对地形数据进行简化,并利用不完全四叉树存储简化后的高程数据;然后根据视点位置和网格空间对象误差的关系建立基于不完全四叉树的LOD模型,同时采用逐层找邻法调整不同层次之间的裂缝,并给出了寻找不同类型邻居的实现过程;最后采用背面剔除算法将起伏地形的不可见部分去除。实际编程时,由于采用了Hibert填充曲线方式存储四叉树结点,并采用隔层四叉树方式访问结点数据,从而提高了大规模地形的绘制效率,取得了良好的地形实时绘制效果。
Virtual Reality has been widely used in the fields such as computer simulation, digital earth, game and entertainment, etc. These applications need not only realism complex Virtual Environment, but also require the user to interact with the virtual scenes at interaction frame rate. As long as meeting the real-time rendering, the user can feel the virtual environment which is the same as the real world and immerse into the environment. However, Virtual reality communities and other visualizations have always faced the problem that their "desirable" visualization dataset sizes are one or more orders of magnitude larger than what the hardware can display at interactive rates. Thus Realistic rendering of 3D terrain scenes is a challenging subject.
Fractal theory, 3D terrain modeling and virtual scene are discussed in details. Firstly, based on OpenGL library and its work principle, the process of 3D real-time terrain surface rendering is analyzed at length. Some methods are presented to improve rendering effects and to speed up graphic display. Secondly, on the basis of fractal theory, the terrain simulation is systematically studied and carried out by using fractal Brown motion (FBM) method. For the fractal terrain simulation, the "diamond-square" algorithm based on random midpoint displacement (RMD) is given in detail. Thirdly, in order to render 3D terrain in real time, this paper presents an improved LOD algorithm. This algorithm firstly simplifies the DEM data by using Mortan coding principle and stores the simplified data with an unfull quatree. Then, it builds the real-time continuous LOD based on this unfull quadtree according to the relationship between viewer position and grid object space error. The author brings out a method named“find the neighbors layer by layer”to patch the cracks between different layers and the procedures to find the different type neighbors are presented in this paper. Finally, it wipes off the invisible grids through back-culling algorithm. In order to improve the rendering speed during the programming, it uses Hibert filling curve method to store and interleaved quatree method to access the unfull quatree nodes. The author uses the improved method to simulate the terrain area and obtains a good effect.
本论文从分形理论,三维地形建模和虚拟场景三个方面逐步进行了深入讨论。首先,讨论了基于OpenGL三维图形库及其工作原理,对三维真实感地形生成的基本过程进行了详细剖析,提出了一些加强渲染效果的具体措施。其次,基于分形的原理,对采用分形布朗运动模拟地形的方法进行了系统研究,给出了采用随机中点位移法中的“diamond-square”算法实现分形地形模拟的具体细节。第三,为了使生成的三维地形更具实时性,提出了一种改进的实时连续LOD生成算法。该算法首先采用Mortan码的编码方式对地形数据进行简化,并利用不完全四叉树存储简化后的高程数据;然后根据视点位置和网格空间对象误差的关系建立基于不完全四叉树的LOD模型,同时采用逐层找邻法调整不同层次之间的裂缝,并给出了寻找不同类型邻居的实现过程;最后采用背面剔除算法将起伏地形的不可见部分去除。实际编程时,由于采用了Hibert填充曲线方式存储四叉树结点,并采用隔层四叉树方式访问结点数据,从而提高了大规模地形的绘制效率,取得了良好的地形实时绘制效果。
Virtual Reality has been widely used in the fields such as computer simulation, digital earth, game and entertainment, etc. These applications need not only realism complex Virtual Environment, but also require the user to interact with the virtual scenes at interaction frame rate. As long as meeting the real-time rendering, the user can feel the virtual environment which is the same as the real world and immerse into the environment. However, Virtual reality communities and other visualizations have always faced the problem that their "desirable" visualization dataset sizes are one or more orders of magnitude larger than what the hardware can display at interactive rates. Thus Realistic rendering of 3D terrain scenes is a challenging subject.
Fractal theory, 3D terrain modeling and virtual scene are discussed in details. Firstly, based on OpenGL library and its work principle, the process of 3D real-time terrain surface rendering is analyzed at length. Some methods are presented to improve rendering effects and to speed up graphic display. Secondly, on the basis of fractal theory, the terrain simulation is systematically studied and carried out by using fractal Brown motion (FBM) method. For the fractal terrain simulation, the "diamond-square" algorithm based on random midpoint displacement (RMD) is given in detail. Thirdly, in order to render 3D terrain in real time, this paper presents an improved LOD algorithm. This algorithm firstly simplifies the DEM data by using Mortan coding principle and stores the simplified data with an unfull quatree. Then, it builds the real-time continuous LOD based on this unfull quadtree according to the relationship between viewer position and grid object space error. The author brings out a method named“find the neighbors layer by layer”to patch the cracks between different layers and the procedures to find the different type neighbors are presented in this paper. Finally, it wipes off the invisible grids through back-culling algorithm. In order to improve the rendering speed during the programming, it uses Hibert filling curve method to store and interleaved quatree method to access the unfull quatree nodes. The author uses the improved method to simulate the terrain area and obtains a good effect.
引文
[1] Macedonia Michael. Games Soldiers Play [J]. IEEE SPECTRUM,2002, (3): 32-37.
[2] 汪成为, 高文, 王行仁. 灵境(虚拟现实)技术的理论、实现及应用[M]. 北京: 清华大学出版社, 1996:20-32
[3] 张茂军. 虚拟现实系统[M]. 北京: 科学出版社, 2001:15-31
[4]石教英主编.虚拟显示基础及实用算法.北京:科学出版社,2002:10-25
[5] 王东生,曹磊.混沌、分形及其应用[M].合肥:中国科学技术出版,1995:10-16
[6] 曾文曲,刘世耀译.分形几何一数学基础及其应用[M].沈阳:东北工学院出版,1991:23-29
[7]费广正,芦丽丹,陈立新编著.可视化 OpenGL 程序设计[M].北京:清华大学出版社,2001:15-23
[8] 齐敏,郝重阳等.基于分形技术的多分辨率三维地景建模方法研究[J].中国图像图形学报.2000.5(7):568-572.
[9] 李富平,蔡秀云.基于迭代的中点位移法对山脉地形的模拟[J].华南理[大学学报(自然科学版).1999, 2: 121-124.
[10]齐敏,郝重阳,佟明安.基于分形技术的多分辨率三维地景建模方法研究[J].中国图象图形学报.2000,5(A).7:568-572e
[11]胡瑞安,胡纪阳,徐树公著.分形的计算机图象及其应用[M].北京:中国铁道出版社,1995:40-46
[12]李富平,蔡秀云.基于迭代的中点位移法对山脉地形的模拟[J].华南理工大学学报(自然科学版).1999, 27.2:121-1240
[13]彭群生,鲍虎军,金小刚编著.计算机真实感图形的算法基础[M].北京:科学出版社,1999:25-36 [14」胡月友,钱志峰,伍铁军.分形技术生成凹凸纹理的应用研究[J].微机发展.2003,13.10:48-500
[15] Xiao GY, Li BZ, Zhou YH. Terrain modeling at variable resolution with fractalinterpolation Proceedings on Computer Aided Design&Computer Graphics. 1999:790794.
[16] Ahmadzadeh, M.R,Duree P,Petrou M. Comparative study of terrain interpolation methods. Proceedings of SPIE. 1999,356:365
[17] Cochran WO, Lewis RR, Hart JC. The normal of a fractal surface. VISUAL COMPUT. 2001,17.4:209-218.
[18] Cohen-Or D, Chrysanthou Y, Silva C.T. A Survey of Visibility for Walkthrough Applications.
[19] Kumar S, Manocha D, Garrett W, and Lin M. Hierarchical back-face computation. Computersand Graphics, 1999, 23.5:681-692.
[20] Slater. M and Chrysanthou Y. View volume culling using a probabilistic cashing scheme. In S. Wilbur and M. Bergamasco, editors, Proceedings of Framework for Immersive Virtual Environments FIVE, December 1996.
[21] Coorg S and Teller S. Temporally coherent conservative visibility. In Proc. 12th Annu. ACM Sympos. Comput. Geom. 1996: 78-87.
[22] Coorg S and Teller S. Real-time occlusion culling for models with large occluders. 1997 Symposium on Interactive 3D Graphics, 1997:83-90.
[23] Schaufler G, Nailboards: A Rendering Primitive for Image Caching in Dynamic Scenes, Eurographics Rendering Workshop 1997: 151-162.
[24] Shade, J., Lischinski D, Salesin D, DeRose T, and Snyder J, Hierarchical Image Caching for Accelerated Walkthroughs of Complex Environments, Computer Graphics (SIGGRAPH '96 Proceedings), 1996: 75-82.
[25] Shade, J., Gortler S, He L, and Szeliski R, Layered Depth Images, Computer Graphics (SIGGRAPH '98 Proceedings), 1998: 231-242.
[26] P. Lindstrom, d. Koller, et al.Real-time continue level of detailrendering of height fields,Computer Graphics(SIGGRAPH' 96Proceedings),1996:109-118
[27] Mark Duchaineauy, Murray Wolinsky, et al Roaming Terrain:Real-timeOptimally Adapting Meashes. IEEE Visualization’97proceedings,1997:81-88
[28] M. de Berg and K. T. G. Dobrindt. On levels of detail in terrains.Technical ReportUU-CS-1995-12, Department of Computer Science,Utrecht University, 1995.
[29] M. Garland and P. S. Heckbert. Fast polygonal approximation of terrains and height fields. Technical Report CMU-CS 95-181,Department of Computer Science,Carnegie Mellon University, 1995: 163-165
[30] M. Garland and P. S. Heckbert.Surface using quadric‘error metrics. Computer Graphics (SIGGRAPH’97 Proceedings),1997:209-216,.
[31] M. Garland and P. S. Heckbert. Simplifying surfaces with color and texture using quadric error metrics. In Proceedings IEEE Visualization’98, 1998:263-269.
[32] H.Hoppe. Progressive meshes. Computer Graphics (SIGGRAPH’96 Proceedings),1996:99-108.
[33] 李志林,朱庆.数字高程模型[M]武汉:测绘科技大学出版社,2000:3-8
[34] 唐泽圣.三维数据场可视化[M].北京:清华大学出版,1999:22-25
[35] Lindstrom P, Koller D, Ribarsky W, Hodges L F, Faust N and Turner GA. Real-Time, Continuous Level of Detail Rendering of Height Fields .In SIGGRAPH'96 Conference Proceedings, 1996:109-118,
[36] Duchaineau M, Wolinski M, Sigeti D E, Miller M C, Aldrich C and Mineev-Weinstein M B. ROAMing Terrain: Real-time, Optimally Adapting Meshes. Proceedings of the Conference on Visualization '97, 1997: 81-88
[37]卢文成,陈文智,潘志庚,石教英.基于对象对应关系的 LOD 模型连续过渡[J].小型微型计算机系统,2001, 22.2:35-36
[38]齐敏,郝重阳,佟明安.三维地形生成及实时显示技术研究进展[J].中国图象图形学报,2000,5(4):269-275
[39]王永明.地形可视化[J].中国图象图形学报,2000,5(6):449-456
[40]Lindstromp, Koller D, Ribarsky W, et al. Real-time continuous level of detail rendering of heigh fields[A]. In Proceeds of SIGGRAPH’ 96[C], New Orleans Louisiana, USA,1996:109-118
[41]Mark Duchaineau, Murray Wolinsky, David E, et al. Roaming terrain Real-time optimally adapting meshes[A]. In Proceedings of Visualization’97, Phoenix Arizona, USA, 1977:81-88
[42]淮永建,郝重阳,范金余等. 基于自适应四叉树视相关的多分辩率地形简化[J]. 系统仿真学报,2002,14(6):748-751
[43]王源,刘建永,江南等.视点相关实时 LOD 地形模型动态构网算法[J].测绘学报,2003,32(1):46-52
[44]谭兵,徐青,马东洋.用约束四叉树实现地形的实时多分辩率绘制[J].计算机辅助设计与图形学学报,2003,15(3):270-276
[45]ZHU Zhi-fan, Machiraju Raghu, Bryan Fry, et al. Wavelet-based multiresolution representation of computational field simulation datasets[A]. In Proceeding of Visualization’97[C],Phoenix,Arizona, USA.1997:151-158
[46] 芮 小 平 . 一 种 基 于 不 完 全 四 叉 树 的 LOD 生 成 算 法 [J]. 中 国 图 象 图 形 学报,2005,10(9):1154-1156
[47]Gross M H, Gatti R. Fast multiresolution surface meshing[A].In proceedings of Visualization’95[C],Atlanta,Georgia, USA,1995:135-142
[2] 汪成为, 高文, 王行仁. 灵境(虚拟现实)技术的理论、实现及应用[M]. 北京: 清华大学出版社, 1996:20-32
[3] 张茂军. 虚拟现实系统[M]. 北京: 科学出版社, 2001:15-31
[4]石教英主编.虚拟显示基础及实用算法.北京:科学出版社,2002:10-25
[5] 王东生,曹磊.混沌、分形及其应用[M].合肥:中国科学技术出版,1995:10-16
[6] 曾文曲,刘世耀译.分形几何一数学基础及其应用[M].沈阳:东北工学院出版,1991:23-29
[7]费广正,芦丽丹,陈立新编著.可视化 OpenGL 程序设计[M].北京:清华大学出版社,2001:15-23
[8] 齐敏,郝重阳等.基于分形技术的多分辨率三维地景建模方法研究[J].中国图像图形学报.2000.5(7):568-572.
[9] 李富平,蔡秀云.基于迭代的中点位移法对山脉地形的模拟[J].华南理[大学学报(自然科学版).1999, 2: 121-124.
[10]齐敏,郝重阳,佟明安.基于分形技术的多分辨率三维地景建模方法研究[J].中国图象图形学报.2000,5(A).7:568-572e
[11]胡瑞安,胡纪阳,徐树公著.分形的计算机图象及其应用[M].北京:中国铁道出版社,1995:40-46
[12]李富平,蔡秀云.基于迭代的中点位移法对山脉地形的模拟[J].华南理工大学学报(自然科学版).1999, 27.2:121-1240
[13]彭群生,鲍虎军,金小刚编著.计算机真实感图形的算法基础[M].北京:科学出版社,1999:25-36 [14」胡月友,钱志峰,伍铁军.分形技术生成凹凸纹理的应用研究[J].微机发展.2003,13.10:48-500
[15] Xiao GY, Li BZ, Zhou YH. Terrain modeling at variable resolution with fractalinterpolation Proceedings on Computer Aided Design&Computer Graphics. 1999:790794.
[16] Ahmadzadeh, M.R,Duree P,Petrou M. Comparative study of terrain interpolation methods. Proceedings of SPIE. 1999,356:365
[17] Cochran WO, Lewis RR, Hart JC. The normal of a fractal surface. VISUAL COMPUT. 2001,17.4:209-218.
[18] Cohen-Or D, Chrysanthou Y, Silva C.T. A Survey of Visibility for Walkthrough Applications.
[19] Kumar S, Manocha D, Garrett W, and Lin M. Hierarchical back-face computation. Computersand Graphics, 1999, 23.5:681-692.
[20] Slater. M and Chrysanthou Y. View volume culling using a probabilistic cashing scheme. In S. Wilbur and M. Bergamasco, editors, Proceedings of Framework for Immersive Virtual Environments FIVE, December 1996.
[21] Coorg S and Teller S. Temporally coherent conservative visibility. In Proc. 12th Annu. ACM Sympos. Comput. Geom. 1996: 78-87.
[22] Coorg S and Teller S. Real-time occlusion culling for models with large occluders. 1997 Symposium on Interactive 3D Graphics, 1997:83-90.
[23] Schaufler G, Nailboards: A Rendering Primitive for Image Caching in Dynamic Scenes, Eurographics Rendering Workshop 1997: 151-162.
[24] Shade, J., Lischinski D, Salesin D, DeRose T, and Snyder J, Hierarchical Image Caching for Accelerated Walkthroughs of Complex Environments, Computer Graphics (SIGGRAPH '96 Proceedings), 1996: 75-82.
[25] Shade, J., Gortler S, He L, and Szeliski R, Layered Depth Images, Computer Graphics (SIGGRAPH '98 Proceedings), 1998: 231-242.
[26] P. Lindstrom, d. Koller, et al.Real-time continue level of detailrendering of height fields,Computer Graphics(SIGGRAPH' 96Proceedings),1996:109-118
[27] Mark Duchaineauy, Murray Wolinsky, et al Roaming Terrain:Real-timeOptimally Adapting Meashes. IEEE Visualization’97proceedings,1997:81-88
[28] M. de Berg and K. T. G. Dobrindt. On levels of detail in terrains.Technical ReportUU-CS-1995-12, Department of Computer Science,Utrecht University, 1995.
[29] M. Garland and P. S. Heckbert. Fast polygonal approximation of terrains and height fields. Technical Report CMU-CS 95-181,Department of Computer Science,Carnegie Mellon University, 1995: 163-165
[30] M. Garland and P. S. Heckbert.Surface using quadric‘error metrics. Computer Graphics (SIGGRAPH’97 Proceedings),1997:209-216,.
[31] M. Garland and P. S. Heckbert. Simplifying surfaces with color and texture using quadric error metrics. In Proceedings IEEE Visualization’98, 1998:263-269.
[32] H.Hoppe. Progressive meshes. Computer Graphics (SIGGRAPH’96 Proceedings),1996:99-108.
[33] 李志林,朱庆.数字高程模型[M]武汉:测绘科技大学出版社,2000:3-8
[34] 唐泽圣.三维数据场可视化[M].北京:清华大学出版,1999:22-25
[35] Lindstrom P, Koller D, Ribarsky W, Hodges L F, Faust N and Turner GA. Real-Time, Continuous Level of Detail Rendering of Height Fields .In SIGGRAPH'96 Conference Proceedings, 1996:109-118,
[36] Duchaineau M, Wolinski M, Sigeti D E, Miller M C, Aldrich C and Mineev-Weinstein M B. ROAMing Terrain: Real-time, Optimally Adapting Meshes. Proceedings of the Conference on Visualization '97, 1997: 81-88
[37]卢文成,陈文智,潘志庚,石教英.基于对象对应关系的 LOD 模型连续过渡[J].小型微型计算机系统,2001, 22.2:35-36
[38]齐敏,郝重阳,佟明安.三维地形生成及实时显示技术研究进展[J].中国图象图形学报,2000,5(4):269-275
[39]王永明.地形可视化[J].中国图象图形学报,2000,5(6):449-456
[40]Lindstromp, Koller D, Ribarsky W, et al. Real-time continuous level of detail rendering of heigh fields[A]. In Proceeds of SIGGRAPH’ 96[C], New Orleans Louisiana, USA,1996:109-118
[41]Mark Duchaineau, Murray Wolinsky, David E, et al. Roaming terrain Real-time optimally adapting meshes[A]. In Proceedings of Visualization’97, Phoenix Arizona, USA, 1977:81-88
[42]淮永建,郝重阳,范金余等. 基于自适应四叉树视相关的多分辩率地形简化[J]. 系统仿真学报,2002,14(6):748-751
[43]王源,刘建永,江南等.视点相关实时 LOD 地形模型动态构网算法[J].测绘学报,2003,32(1):46-52
[44]谭兵,徐青,马东洋.用约束四叉树实现地形的实时多分辩率绘制[J].计算机辅助设计与图形学学报,2003,15(3):270-276
[45]ZHU Zhi-fan, Machiraju Raghu, Bryan Fry, et al. Wavelet-based multiresolution representation of computational field simulation datasets[A]. In Proceeding of Visualization’97[C],Phoenix,Arizona, USA.1997:151-158
[46] 芮 小 平 . 一 种 基 于 不 完 全 四 叉 树 的 LOD 生 成 算 法 [J]. 中 国 图 象 图 形 学报,2005,10(9):1154-1156
[47]Gross M H, Gatti R. Fast multiresolution surface meshing[A].In proceedings of Visualization’95[C],Atlanta,Georgia, USA,1995:135-142