基于GPU的大规模地形时空连续性建模及实时可视化研究
|
摘要
地形可视化在三维游戏、虚拟现实及飞行训练等众多领域的应用越来越广泛。随着地形规模越来越大,细节越来越复杂,绘制算法的时间和空间连续性问题成为亟需解决的问题之一。本文的研究目标为实现大规模时空连续性地形建模和实时可视化。
首先,在分析了国内外地形绘制技术研究现状的基础上,选择目前应用比较广泛的多分辨率分块四叉树结构来建立地形模型。为使四叉树多分辨率地形可视化方法更符合实时性的要求,对数据进行重组织,采取双线程调度策略,缓解渲染效率与数据读取速度之间的矛盾。
其次,在建立地形模型的基础上,为解决地形可视化过程中的时间和空间连续性问题,提出基于几何过渡的时空连续性一体化处理算法,实现整个地形的平滑可视化,时空连续性处理部分使用GPU顶点着色器,保证了算法的执行效率。
再次,为提高地形绘制效率,从多方面对地形绘制效率进行优化,重点研究在全局范围内构建饱和四叉树包围球,自顶向下进行视域剔除;对局部绘制的规则网格进行三角形条带化处理;对结点评价函数进一步的优化,从硬件和算法角度提高大规模地形的绘制效率。
最后,为验证多分辨率地形绘制算法的实时性和真实性,设计并实现了大规模时空连续性地形可视化系统。实验表明该系统可以取得较高的帧率和逼真的绘制效果,能够实现大规模地形的平滑漫游。
The terrain visualization is widely applied in 3D games, virtual reality, flight training and so on. With the increasing scale of the terrain, more and more complex of the details, the rendering algorithm is facing increasingly serious continuity problems. The research goals of this paper are modeling of the large scale space-time continuity terrain and real time visualization. The work plays an important theoretical and realistic role in the research.
Firstly, the multi-resolution block quad tree structure was selected based on the analysis of the status of domestic and foreign terrain rendering technique. It was applied widely to build the terrain model. To make multi-resolution quad tree terrain visualization method suitable for more real time requirements, we reorganize the terrain data, and take the double-thread scheduling policy. Our algorithm eases the contradiction between the data read speed and the rendering efficiency.
Secondly, we propose time-space continuity process integrated algorithm. It solves the time and space continuity problem in terrain visualization based on the establishment of the terrain model. It can realize the whole terrain smooth visualization. The design of GPU-oriented algorithm ensures its implement efficiency.
Thirdly, the rendering efficiency was optimized from many aspects. This paper principally studied about constructing a saturated quad tree ball over the whole scale to cull view frustum up-to-down, drawing local grid by Cluster Triangulations, and further optimizes node evaluation function. Thus we improve the efficiency of large scale terrain rendering from the perspective of hardware and algorithms.
Finally, the large scale terrain visualization system was designed and realized to validate the effectiveness of the multi-resolution terrain model. As a result, the system could achieve a good visual effect and a high frame rate, and implement visualization roaming freely and wholly on the large-scale terrain.
The multi-resolution terrain model was applied successfully in the 863 issue on large-scale visualization system. It realizes high speed rendering and roaming on large space scene. The multi-resolution terrain model plays an important role in studying large-scale terrain panorama visualization roaming technology.
首先,在分析了国内外地形绘制技术研究现状的基础上,选择目前应用比较广泛的多分辨率分块四叉树结构来建立地形模型。为使四叉树多分辨率地形可视化方法更符合实时性的要求,对数据进行重组织,采取双线程调度策略,缓解渲染效率与数据读取速度之间的矛盾。
其次,在建立地形模型的基础上,为解决地形可视化过程中的时间和空间连续性问题,提出基于几何过渡的时空连续性一体化处理算法,实现整个地形的平滑可视化,时空连续性处理部分使用GPU顶点着色器,保证了算法的执行效率。
再次,为提高地形绘制效率,从多方面对地形绘制效率进行优化,重点研究在全局范围内构建饱和四叉树包围球,自顶向下进行视域剔除;对局部绘制的规则网格进行三角形条带化处理;对结点评价函数进一步的优化,从硬件和算法角度提高大规模地形的绘制效率。
最后,为验证多分辨率地形绘制算法的实时性和真实性,设计并实现了大规模时空连续性地形可视化系统。实验表明该系统可以取得较高的帧率和逼真的绘制效果,能够实现大规模地形的平滑漫游。
The terrain visualization is widely applied in 3D games, virtual reality, flight training and so on. With the increasing scale of the terrain, more and more complex of the details, the rendering algorithm is facing increasingly serious continuity problems. The research goals of this paper are modeling of the large scale space-time continuity terrain and real time visualization. The work plays an important theoretical and realistic role in the research.
Firstly, the multi-resolution block quad tree structure was selected based on the analysis of the status of domestic and foreign terrain rendering technique. It was applied widely to build the terrain model. To make multi-resolution quad tree terrain visualization method suitable for more real time requirements, we reorganize the terrain data, and take the double-thread scheduling policy. Our algorithm eases the contradiction between the data read speed and the rendering efficiency.
Secondly, we propose time-space continuity process integrated algorithm. It solves the time and space continuity problem in terrain visualization based on the establishment of the terrain model. It can realize the whole terrain smooth visualization. The design of GPU-oriented algorithm ensures its implement efficiency.
Thirdly, the rendering efficiency was optimized from many aspects. This paper principally studied about constructing a saturated quad tree ball over the whole scale to cull view frustum up-to-down, drawing local grid by Cluster Triangulations, and further optimizes node evaluation function. Thus we improve the efficiency of large scale terrain rendering from the perspective of hardware and algorithms.
Finally, the large scale terrain visualization system was designed and realized to validate the effectiveness of the multi-resolution terrain model. As a result, the system could achieve a good visual effect and a high frame rate, and implement visualization roaming freely and wholly on the large-scale terrain.
The multi-resolution terrain model was applied successfully in the 863 issue on large-scale visualization system. It realizes high speed rendering and roaming on large space scene. The multi-resolution terrain model plays an important role in studying large-scale terrain panorama visualization roaming technology.
引文
1姜陆.三位大规模地形实时现实与渲染. [电子科技大学硕士学位论文]. 2005:7-8
2 R. Azuma, G. Bishop. Improving Static and Dynamic Registration in an Optical See-Through HMD. Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, Orlando Florida, 1994:197-204
3 P. Lindstrom, D. Koller, W. Ribarsky. Real-Time, Continuous Level of Detail Rendering of Height Fields. Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, New Orleans, 1996:109-118
4 S. Rttger, W. Heidrich. Real-Time Generation of Continuous Levels of Detail for Height Fields. International Conference in Central Europe on Computer Graphics and Visualization, Pilsen, 1998:315-322
5 H. Hoppe. Smooth View-Dependent Level-of-Detail Control and its Application to Terrain Rendering. Proceedings of Visualization’98. Piscataway, 1998:35-42
6 H. Hoppe, View-Dependent Refinement of Progressive Meshes." Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, Los Angeles, 1997:189-198
7 D. Luebke, C. Erikson. View-Dependent Simplification of Arbitrary Polygonal Environments. Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, Los Angeles, 1997:199-208
8 P. Cignoni, F. Ganovelli, E. Gobbetti. Adaptive TetraPuzzles: Efficient Out-of-Core Construction and Visualization of Gigantic Multi-resolution Polygonal Models. Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, Los Angeles, 2004:203-206
9 P. Lindstrom. Out-of-Core Construction and Visualization of Multi-resolution Surfaces. Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, Monterey, 2003:28-30
10 R. Pajarola. Large Scale Terrain Visualization Using the Reatricted QuadtreeTriangulation.In Proceedings visualization 98, North Carolina, 1998:19-26, 515
11 L. Velho. Using Semi-regular 4-8 Meshes for Subdivision Surfaces. Journal of Graphies Tools, 2001:5(3)35-47
12 L. Velho, J. Gomes. Variable Resolution 4-k Meshes: Concepts and Application. Computer Graphics Forum, 2000:19(4), 195-214
13 T. Ulrich. Render Massive Terrains Using Chunked Level of Detail Control. Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, San Antonio, 2002:1-14
14卓亚芬. ChunkedLOD海量地形的实时绘制系统. [浙江大学硕士学位论文]. 2004: 40-42
15曹振宇,齐华.虚拟地理环境中地形地貌建模研究. [西南交通大学硕士学位论文]. 2004:45-52
16芮小平.一种基于不完全四叉树的LOD生成算法.中国图形图像学报, 2005, 10(9):1152-1160
17 Duchaineau, M. Wolinsky, D.E. Sigeti. ROAMing Terrain: Real-time Optimally Adapting Meshes. Proceedings of Visualization, Phoenix, 1997:81-88
18 Jonathan Blow. Terrain Rendering at High Levels of Detail. Paper for the Game Developers’Conference 2000, California, USA, 2000:1-17
19 H. Hoppe. Progressive meshes. Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, New Orleans, 1996:99-108
20 F. Losasoo, H. Hoppe. Geometry clipmaps: Terrain rendering using nested regular grids. Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, Los Angeles, 2004:769-776
21 Asirvatham A, Hoppe H. Terrain Rendering Using GPU-Based Geometry Clipmaps. GPU Gem, 2005:27-45
22 M. Clasen, H. Hege. Terrain rendering using spherical clipmaps. In Proc. EuroVis, 2006: 91-98
23 J. Schneider, R. Westermann. GPU-Friendly High-quality Terrain Rendering. Journal of WSCG, 2006, 14(1):49-56
24 Y. Livny, N. Sokoloysky, T. Grinshpoun. Persistent Grid Mapping: A GPU-based Framework for Interactive Terrain Rendering. In proceeding to Pacific Graphics conference, 2006:1-10
25 Y. Livny, Z. Kogan, Jihad. Seamless Patches for GPU-Based Terrain Rendering. Proceeding to WSCG conference 2007, Pilsen, 2007:201-208
26 R. Pajarola, E. Gobbetti. Survey on Semi-Regular Multi-resolution Models for Interactive Terrain Rendering. The Visual Computer. 2007, 23(8):583-605
27 L. Cantlay. Adaptive Terrain Tessellation on the GPU. Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, Los Angeles, 2008:1-20
28 Xingquan Cai, Jinhong Li, Zhitong Su. Large-Scale Terrain Rendering Using Strip Masks of Terrain Blocks. IEEE 7th World Congress on Intelligent Control and Automation, 2008:1768-1772
29 Yotam Livny, Zvi Kogan, Jihad El-Sana. Seamless patches for GPU-based terrain rendering. The Visual Computer 2009, 25(3):197-208
30 Yacine Amara,Xavier Marsult.A GPU Tile-Load-Map architecture for terrain rendering:theory and applications.Vis Comput(2009)25:805-824.
31 Christian Dick, Jens Krüger, Rüdiger Westermann. GPU Ray-Casting for Scalable Terrain Rendering. The Eurographics Association. 2009:15-20.
32 Peter Lindstrom, Jonathan D.Cohen.On-the-Fly Decompression and Rendering of Multiresolution Terrain.ACM SIGGRAPH symposium on Interactive 3DGraphics and Games,New York,February,2010:65-73.
33殷媛,陈国军,吴威.地形分块绘制中的边界裂缝处理算法.计算机辅助设计与图形学学报, 2006, 18(10):1557-1562.
34 Robert L.Ferguson, Richard Economy, William A. Kelly, and Pedro P.Ramos,“Continuous terrain level of detail for visual simulation”in proceedings of the 1990 IMAGE V Conference, Tempe, Arizona, June 1990, pp.144-151.
35 Peter Lindstrom and V. Pascucci. Terrain Simplification Simplified: A General Framework for View-Dependent Out-of-Core Visualization. IEEE Transaction on Visualization and Computer Graphics,2002,8(3):239-254.
36陆艳青.海量地形数据实时绘制技术的研究.浙江大学博士学位论文. 2003.
37 P. Lindstrom, V. Pascucci. Visualization of Large Terrains Made Easy. Proceedings of IEEE Visualization 2001, San Diego, 2001:363-370
38戴星光,张永生,邓雪清.一种实时可视化的海量地形数据组织与管理方法.系统仿真学报, 2005, 17(2):406-413
39杜莹,武玉国,王晓明.全球多分辨率虚拟地形环境的金字塔模型研究.系统仿真学报, 2006, 18(4):955-958, 967
40李胜,冀俊峰,刘学慧.超大规模地形场景的高性能漫游. Journal of Soft. 2006, 17(3):535-545
41 S. E. Yoon, P. Lindstrom. Mesh Layouts for Block-Based Caches. IEEE Transaction on Visualization and Computer Graphics, 2006, 12(5):1213-1220
42李惠,翟磊,林诚凯. ROAM算法在超大规模地形渲染中的作用.中国图象图形学报. 2003, 8(2):526-529
43李惠,翟磊,林诚凯.一种超大规模地形的实时渲染方法.系统仿真学报, 2004, 16(4):736-739
44冷志光,汤晓安,郝建新.大规模地形动态快速绘制技术研究.系统仿真学报, 2006, 18(10):2832-2835
45李立杰,李凤霞,黄天羽.一种大规模地形可视化的平滑调度算法.软件学报, vol.18,December 2007:26-33.
46 D. Hilbert. Uber Die Stetige Abbildung Einer Linie Auf Ein Flachenstück.. Mathematische Annalen, 1891, 38:459-460
47 S. Kamata, Y. Bandou. An Address Generator of a Pseudo-Hilbert Scan in a Rectangle Region. In International Conference on Image Processing, Washington, DC, 1997:707-714
48 Y. Bandou, S. I. Kamata. An Address Generator for an N-dimensional Pseudo-hilbert Scan in a Hyper-rectangular Parallelepiped Region. Proceedings. 2000 International Conference, 2000, 1(1):707-714
49 DAI Chen-guang, DENG Xue-qing. Fast rendering of massive textured terrain data. Journal of Communication and Computer, ISSN1548-7709, USA, 2007,4(3):63-68
50 J. Blow. Terrain Rendering at High Levels of Detail. Paper for the Game Developers’Conference 2000, California, 2000:1-17
51 V. Pascucci, R. J. Frank. Global Static Indexing for Real-time Exploration of Very Large Regular Grids. Proceedings of the 2001 ACM/IEEE conference on Supercomputing, Denver, 2001:45-64
52 Paul Hansen. OpenGL Texture-Mapping With Very Large Datasets and Multi-Resolution Tiles. ACM Siggraph, 1999:207-214
2 R. Azuma, G. Bishop. Improving Static and Dynamic Registration in an Optical See-Through HMD. Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, Orlando Florida, 1994:197-204
3 P. Lindstrom, D. Koller, W. Ribarsky. Real-Time, Continuous Level of Detail Rendering of Height Fields. Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, New Orleans, 1996:109-118
4 S. Rttger, W. Heidrich. Real-Time Generation of Continuous Levels of Detail for Height Fields. International Conference in Central Europe on Computer Graphics and Visualization, Pilsen, 1998:315-322
5 H. Hoppe. Smooth View-Dependent Level-of-Detail Control and its Application to Terrain Rendering. Proceedings of Visualization’98. Piscataway, 1998:35-42
6 H. Hoppe, View-Dependent Refinement of Progressive Meshes." Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, Los Angeles, 1997:189-198
7 D. Luebke, C. Erikson. View-Dependent Simplification of Arbitrary Polygonal Environments. Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, Los Angeles, 1997:199-208
8 P. Cignoni, F. Ganovelli, E. Gobbetti. Adaptive TetraPuzzles: Efficient Out-of-Core Construction and Visualization of Gigantic Multi-resolution Polygonal Models. Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, Los Angeles, 2004:203-206
9 P. Lindstrom. Out-of-Core Construction and Visualization of Multi-resolution Surfaces. Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, Monterey, 2003:28-30
10 R. Pajarola. Large Scale Terrain Visualization Using the Reatricted QuadtreeTriangulation.In Proceedings visualization 98, North Carolina, 1998:19-26, 515
11 L. Velho. Using Semi-regular 4-8 Meshes for Subdivision Surfaces. Journal of Graphies Tools, 2001:5(3)35-47
12 L. Velho, J. Gomes. Variable Resolution 4-k Meshes: Concepts and Application. Computer Graphics Forum, 2000:19(4), 195-214
13 T. Ulrich. Render Massive Terrains Using Chunked Level of Detail Control. Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, San Antonio, 2002:1-14
14卓亚芬. ChunkedLOD海量地形的实时绘制系统. [浙江大学硕士学位论文]. 2004: 40-42
15曹振宇,齐华.虚拟地理环境中地形地貌建模研究. [西南交通大学硕士学位论文]. 2004:45-52
16芮小平.一种基于不完全四叉树的LOD生成算法.中国图形图像学报, 2005, 10(9):1152-1160
17 Duchaineau, M. Wolinsky, D.E. Sigeti. ROAMing Terrain: Real-time Optimally Adapting Meshes. Proceedings of Visualization, Phoenix, 1997:81-88
18 Jonathan Blow. Terrain Rendering at High Levels of Detail. Paper for the Game Developers’Conference 2000, California, USA, 2000:1-17
19 H. Hoppe. Progressive meshes. Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, New Orleans, 1996:99-108
20 F. Losasoo, H. Hoppe. Geometry clipmaps: Terrain rendering using nested regular grids. Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, Los Angeles, 2004:769-776
21 Asirvatham A, Hoppe H. Terrain Rendering Using GPU-Based Geometry Clipmaps. GPU Gem, 2005:27-45
22 M. Clasen, H. Hege. Terrain rendering using spherical clipmaps. In Proc. EuroVis, 2006: 91-98
23 J. Schneider, R. Westermann. GPU-Friendly High-quality Terrain Rendering. Journal of WSCG, 2006, 14(1):49-56
24 Y. Livny, N. Sokoloysky, T. Grinshpoun. Persistent Grid Mapping: A GPU-based Framework for Interactive Terrain Rendering. In proceeding to Pacific Graphics conference, 2006:1-10
25 Y. Livny, Z. Kogan, Jihad. Seamless Patches for GPU-Based Terrain Rendering. Proceeding to WSCG conference 2007, Pilsen, 2007:201-208
26 R. Pajarola, E. Gobbetti. Survey on Semi-Regular Multi-resolution Models for Interactive Terrain Rendering. The Visual Computer. 2007, 23(8):583-605
27 L. Cantlay. Adaptive Terrain Tessellation on the GPU. Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, Los Angeles, 2008:1-20
28 Xingquan Cai, Jinhong Li, Zhitong Su. Large-Scale Terrain Rendering Using Strip Masks of Terrain Blocks. IEEE 7th World Congress on Intelligent Control and Automation, 2008:1768-1772
29 Yotam Livny, Zvi Kogan, Jihad El-Sana. Seamless patches for GPU-based terrain rendering. The Visual Computer 2009, 25(3):197-208
30 Yacine Amara,Xavier Marsult.A GPU Tile-Load-Map architecture for terrain rendering:theory and applications.Vis Comput(2009)25:805-824.
31 Christian Dick, Jens Krüger, Rüdiger Westermann. GPU Ray-Casting for Scalable Terrain Rendering. The Eurographics Association. 2009:15-20.
32 Peter Lindstrom, Jonathan D.Cohen.On-the-Fly Decompression and Rendering of Multiresolution Terrain.ACM SIGGRAPH symposium on Interactive 3DGraphics and Games,New York,February,2010:65-73.
33殷媛,陈国军,吴威.地形分块绘制中的边界裂缝处理算法.计算机辅助设计与图形学学报, 2006, 18(10):1557-1562.
34 Robert L.Ferguson, Richard Economy, William A. Kelly, and Pedro P.Ramos,“Continuous terrain level of detail for visual simulation”in proceedings of the 1990 IMAGE V Conference, Tempe, Arizona, June 1990, pp.144-151.
35 Peter Lindstrom and V. Pascucci. Terrain Simplification Simplified: A General Framework for View-Dependent Out-of-Core Visualization. IEEE Transaction on Visualization and Computer Graphics,2002,8(3):239-254.
36陆艳青.海量地形数据实时绘制技术的研究.浙江大学博士学位论文. 2003.
37 P. Lindstrom, V. Pascucci. Visualization of Large Terrains Made Easy. Proceedings of IEEE Visualization 2001, San Diego, 2001:363-370
38戴星光,张永生,邓雪清.一种实时可视化的海量地形数据组织与管理方法.系统仿真学报, 2005, 17(2):406-413
39杜莹,武玉国,王晓明.全球多分辨率虚拟地形环境的金字塔模型研究.系统仿真学报, 2006, 18(4):955-958, 967
40李胜,冀俊峰,刘学慧.超大规模地形场景的高性能漫游. Journal of Soft. 2006, 17(3):535-545
41 S. E. Yoon, P. Lindstrom. Mesh Layouts for Block-Based Caches. IEEE Transaction on Visualization and Computer Graphics, 2006, 12(5):1213-1220
42李惠,翟磊,林诚凯. ROAM算法在超大规模地形渲染中的作用.中国图象图形学报. 2003, 8(2):526-529
43李惠,翟磊,林诚凯.一种超大规模地形的实时渲染方法.系统仿真学报, 2004, 16(4):736-739
44冷志光,汤晓安,郝建新.大规模地形动态快速绘制技术研究.系统仿真学报, 2006, 18(10):2832-2835
45李立杰,李凤霞,黄天羽.一种大规模地形可视化的平滑调度算法.软件学报, vol.18,December 2007:26-33.
46 D. Hilbert. Uber Die Stetige Abbildung Einer Linie Auf Ein Flachenstück.. Mathematische Annalen, 1891, 38:459-460
47 S. Kamata, Y. Bandou. An Address Generator of a Pseudo-Hilbert Scan in a Rectangle Region. In International Conference on Image Processing, Washington, DC, 1997:707-714
48 Y. Bandou, S. I. Kamata. An Address Generator for an N-dimensional Pseudo-hilbert Scan in a Hyper-rectangular Parallelepiped Region. Proceedings. 2000 International Conference, 2000, 1(1):707-714
49 DAI Chen-guang, DENG Xue-qing. Fast rendering of massive textured terrain data. Journal of Communication and Computer, ISSN1548-7709, USA, 2007,4(3):63-68
50 J. Blow. Terrain Rendering at High Levels of Detail. Paper for the Game Developers’Conference 2000, California, 2000:1-17
51 V. Pascucci, R. J. Frank. Global Static Indexing for Real-time Exploration of Very Large Regular Grids. Proceedings of the 2001 ACM/IEEE conference on Supercomputing, Denver, 2001:45-64
52 Paul Hansen. OpenGL Texture-Mapping With Very Large Datasets and Multi-Resolution Tiles. ACM Siggraph, 1999:207-214