大规模地形的建模与动态绘制技术研究
|
摘要
随着数字地球概念的提出及虚拟现实技术广泛应用，作为其中不可缺少的组成部分，三维地形可视化技术扮演了越来越重要的角色。由于三维地形场景的生成一般基于真实的地形数据(DEM格网)和高分辨率的遥感影像，对于大规模地形场景的显示来说，如此庞大的数据量使得图形工作平台无法进行实时的显示。针对大规模地形场景的绘制问题，国内外的学者进行了大量的研究，其主要工作集中在不规则三角网的生成技术和多分辨率地形模型上。
本文在对南宁防洪指挥系统三维显示子模块若干技术重点、难点进行研究的基础上，对地形生成技术和多分辨率地形模型进行了深入的研究，并提出了一些改进算法。
本文具体研究内容集中于基于规则格网的不规则三角网生成算法、不规则三角网顶点法矢量的快速计算方法、多分辨率地形模型的构造方法和视点相关的实时绘制方法。本文中的算法效率高、误差较小，在给定精度的情况下，能够实现地形的快速显示及实时浏览，可满足大多数情况下的工程应用。
With the present of digital-earth concept and comprehensive application of virtual reality technology, 3D terrain visualization technology, as an indispensable part of those ,is playing an more important role in daily life. Actually 3D terrain visualization employs the real terrain data(DEM grid)and high resolution satellite images. Thus such huge quantity of data prevent the real-time visualization of large-scale terrain. In order to solve this problem, researchers have done a lot of work. And most of these work concentrates on the creation of irregular triangle network and multiresolution terrain models .
In this paper, a great deal of work has been done on the above two aspects to solve the problems concerning in the visualization part of NanNing Flooding Information System.
This paper mainly discusses the following aspects: the creation method of irregular triangular network from regular grids, fast computing method of vertex normals in TINs, the creation method of multiresolution terrain models and method of view-dependent real-time rendering. The algorithm in this paper works efficiently at a lower error. In most applications it is impossible to realize the fast visualization and fly-through of terrain at a given accuracy.
本文在对南宁防洪指挥系统三维显示子模块若干技术重点、难点进行研究的基础上，对地形生成技术和多分辨率地形模型进行了深入的研究，并提出了一些改进算法。
本文具体研究内容集中于基于规则格网的不规则三角网生成算法、不规则三角网顶点法矢量的快速计算方法、多分辨率地形模型的构造方法和视点相关的实时绘制方法。本文中的算法效率高、误差较小，在给定精度的情况下，能够实现地形的快速显示及实时浏览，可满足大多数情况下的工程应用。
With the present of digital-earth concept and comprehensive application of virtual reality technology, 3D terrain visualization technology, as an indispensable part of those ,is playing an more important role in daily life. Actually 3D terrain visualization employs the real terrain data(DEM grid)and high resolution satellite images. Thus such huge quantity of data prevent the real-time visualization of large-scale terrain. In order to solve this problem, researchers have done a lot of work. And most of these work concentrates on the creation of irregular triangle network and multiresolution terrain models .
In this paper, a great deal of work has been done on the above two aspects to solve the problems concerning in the visualization part of NanNing Flooding Information System.
This paper mainly discusses the following aspects: the creation method of irregular triangular network from regular grids, fast computing method of vertex normals in TINs, the creation method of multiresolution terrain models and method of view-dependent real-time rendering. The algorithm in this paper works efficiently at a lower error. In most applications it is impossible to realize the fast visualization and fly-through of terrain at a given accuracy.
引文
[1] 唐泽圣等，计算机图形学基础，清华大学出版社，1995
[2] 孙家广，杨长贵，计算机图形学，清华大学出版社，1995
[3] 李志林，朱庆，数字高程模型，武汉测绘科技大学出版社，2000
[4] Schroeder W J,Zarge J A et al. Decimation of triangle meshes. Computer Graphics, 1992,26(2):65—70
[5] HoppeH, DeRose T et al. Mesh optimization. Computer Graphics, Siggraph'93, 1993,27:19—26
[6] Rossignac J,Borrel P.Multi-resolution 3D approximation for rendering complex scenes.In:Falcidieno B,Kunii T.editors,Geometric Modeling in Computer Graphics.New York:Springer Verlag, 1993:455—465
[7] Hamann, B., Jean, B.A. and Razdan, A. (1999), Computer-aided geometric design techniques for surface grid generation (pdf), in: Thompson, J.F., Soni, B.K. and Weatherill, N.P. eds., Handbook of Grid Generation, CRC Press, Boca Raton, Florida, pp. 29-1-29-26
[8] Tsai V J D. Delaunay Triangulations in TIN Creation: an Overview and a Linear-time Algorithm. Int. J. of GIS, 1993,7(6):501～524
[9] M. Gross, R. Gatti, and O. Staadt. Fast Multiresolution Surface Meshing. IEEE Visualization '95, 135-142. Oct. 1995
[10] P. Lindstrom, D. Koller, W. Ribarsky, L. F. Hodges, N. Faust, and G. Turner. Real-Time, Continuous Level of Detail Rendering of Height Fields. Proceedings of SIGGRAPH 96, 109-118. Aug. 1996
[11] Mark A. Duchaineau, Murray Wolinsky, David E. Sigeti, Mark C. Miller, Charles Aldrich, and Mark B. Mineev-Weinstein, "ROAMing terrain: Real-time optimally adapting meshes," in IEEE Visualization '97, Roni Yagel and Hans Hagen, Eds., Phoenix, Arizona, Nov. 1997, pp. 81-88, IEEE
[12] 王永明，地形可视化，中国图象图形学报，2000．6
[13] 莫怀才，冯勤，虚拟战场视景仿真，测控技术，1999．6
[14] De Floriani, Paola Magilio. Visibility algorithm on triangulated digital terrain models. Int. J. Geographical Information Systems, 1994, g(1): 1341
[15] Choi Y K, Park K H. A heuristic triangulation algorithm for multiple planar contours using an extended double branching procedure. Visual Computer, 1994, (10):372387
[16] Macedonio G. An algorithm for the triangulation of arbitrarily distributed points: Applications to Volume Estimate and Terrain Fitting. Computer & Geoseiences, 1991, 17(7): 859874
[17] Garganini I. An effective way of represent quadtree. CACM, 1982,12:905910
[18] Lee D T, Schachter B J. Two algorithms for constructing a delaunay triangulation. Int. J .Computer Info. Sci. 1980,9(3):219242
[19] Fowler Robert J, Little James J. Automatic extraction of irregular network digital terrain models. Computer Graphics(SIGGRPH'79 Proc.), 1979,13(2) : 199207
[20] Garland M, Heckbert P S. Fast Polygonal Approximation of Terrenes and height fields. Tech. Report of CMU-CS-95-181, 1995.9
[21] Lawson C L. Software for C surface interpolation. Mathematical Software Ⅲ, New York; Academic Press, 1977,161194
[22] Lee J. Drop heuristic conversion method for extracting irregular network for digital elevation models. In:GIS/KIS'89 Proc.,Volume 1, American Congress on Surveying and Mapping, 1989:3039
[23] Hoppe H. Progressive mesh. Computer Graphics(SIGGRAPH'96 Proceedings)
[24] 齐敏 郝重阳 佟明安，三维地形生成及实时显示技术研究进展，中国图象图形学报，2000．4
[25] De Floriani et al .A hierarchical data structure for surface approximation.Computer and Graphics, 1984,8(2): 475484
[26] Von Herzen B Barr AH. Accurate Triangulations of Deformed. Intersecting Surface. Computer Graphics, 1987,21 (4): 103110
[27] Hoppe H. Progressive mesh. Computer Graphics(SIGGRAPH'96 Proceedings)
[28] L. De Floriani, E Magillo, Multiresolution Meshes, Principles of Multiresolution in Geometric Modeling - PRIMUS01 summer school, pp. 193-234, Munich, August 22-30, 2001
[29] 赵新华，大数据量网格模型的建模与简化技术研究，2002．1 国防科学技术大学研究生院，工学硕士学位论文
[30] Lingas A. The Greedy and Delaunay Triangulations are not Bad in the Average Case. Information Processing Letters, 1986(22): 25～31
[31] G. Dutton. Improving locational speci_city of map data - a multiresolution, metadata-driven approach and notation. International Journal of GeographicInformation Systems 10(3), 1996
[32] W. Evans, D. Kirkpatrick, and G. Townsend. Right triangular irregular networks.Algorithmica 30(2), 2001, 264-286. Special Issue on Algorithms for Geographical Information.
[33] Peter Lindstrom and Valerio Pascucci. Visualization of Large Terrains Made Easy. IEEE Visualization 2001 pp. 363-370, 574, October 2001
[34] 王璐锦 唐泽圣，基于分形维数的地表模型多分辨率动态绘制，软件学报 2000．11
[35] 周昆 潘志庚 石教英，基于混合多细节层次技术的实时绘制算法，软件学报，2001．12
[36] 廖巍，汤晓安，陈荦，吴秋云，一种视点相关的多分辨率地形实时绘制方法，计算机工程与科学，已录用
[37] P. Lindstrom and V. Pascucci, Terrain simplification Simplified: A General Framework for View-Dependent Out-of-Core Visualization. In IEEE Visualization 2002 pp. 247-253,357, May 2002
[2] 孙家广，杨长贵，计算机图形学，清华大学出版社，1995
[3] 李志林，朱庆，数字高程模型，武汉测绘科技大学出版社，2000
[4] Schroeder W J,Zarge J A et al. Decimation of triangle meshes. Computer Graphics, 1992,26(2):65—70
[5] HoppeH, DeRose T et al. Mesh optimization. Computer Graphics, Siggraph'93, 1993,27:19—26
[6] Rossignac J,Borrel P.Multi-resolution 3D approximation for rendering complex scenes.In:Falcidieno B,Kunii T.editors,Geometric Modeling in Computer Graphics.New York:Springer Verlag, 1993:455—465
[7] Hamann, B., Jean, B.A. and Razdan, A. (1999), Computer-aided geometric design techniques for surface grid generation (pdf), in: Thompson, J.F., Soni, B.K. and Weatherill, N.P. eds., Handbook of Grid Generation, CRC Press, Boca Raton, Florida, pp. 29-1-29-26
[8] Tsai V J D. Delaunay Triangulations in TIN Creation: an Overview and a Linear-time Algorithm. Int. J. of GIS, 1993,7(6):501～524
[9] M. Gross, R. Gatti, and O. Staadt. Fast Multiresolution Surface Meshing. IEEE Visualization '95, 135-142. Oct. 1995
[10] P. Lindstrom, D. Koller, W. Ribarsky, L. F. Hodges, N. Faust, and G. Turner. Real-Time, Continuous Level of Detail Rendering of Height Fields. Proceedings of SIGGRAPH 96, 109-118. Aug. 1996
[11] Mark A. Duchaineau, Murray Wolinsky, David E. Sigeti, Mark C. Miller, Charles Aldrich, and Mark B. Mineev-Weinstein, "ROAMing terrain: Real-time optimally adapting meshes," in IEEE Visualization '97, Roni Yagel and Hans Hagen, Eds., Phoenix, Arizona, Nov. 1997, pp. 81-88, IEEE
[12] 王永明，地形可视化，中国图象图形学报，2000．6
[13] 莫怀才，冯勤，虚拟战场视景仿真，测控技术，1999．6
[14] De Floriani, Paola Magilio. Visibility algorithm on triangulated digital terrain models. Int. J. Geographical Information Systems, 1994, g(1): 1341
[15] Choi Y K, Park K H. A heuristic triangulation algorithm for multiple planar contours using an extended double branching procedure. Visual Computer, 1994, (10):372387
[16] Macedonio G. An algorithm for the triangulation of arbitrarily distributed points: Applications to Volume Estimate and Terrain Fitting. Computer & Geoseiences, 1991, 17(7): 859874
[17] Garganini I. An effective way of represent quadtree. CACM, 1982,12:905910
[18] Lee D T, Schachter B J. Two algorithms for constructing a delaunay triangulation. Int. J .Computer Info. Sci. 1980,9(3):219242
[19] Fowler Robert J, Little James J. Automatic extraction of irregular network digital terrain models. Computer Graphics(SIGGRPH'79 Proc.), 1979,13(2) : 199207
[20] Garland M, Heckbert P S. Fast Polygonal Approximation of Terrenes and height fields. Tech. Report of CMU-CS-95-181, 1995.9
[21] Lawson C L. Software for C surface interpolation. Mathematical Software Ⅲ, New York; Academic Press, 1977,161194
[22] Lee J. Drop heuristic conversion method for extracting irregular network for digital elevation models. In:GIS/KIS'89 Proc.,Volume 1, American Congress on Surveying and Mapping, 1989:3039
[23] Hoppe H. Progressive mesh. Computer Graphics(SIGGRAPH'96 Proceedings)
[24] 齐敏 郝重阳 佟明安，三维地形生成及实时显示技术研究进展，中国图象图形学报，2000．4
[25] De Floriani et al .A hierarchical data structure for surface approximation.Computer and Graphics, 1984,8(2): 475484
[26] Von Herzen B Barr AH. Accurate Triangulations of Deformed. Intersecting Surface. Computer Graphics, 1987,21 (4): 103110
[27] Hoppe H. Progressive mesh. Computer Graphics(SIGGRAPH'96 Proceedings)
[28] L. De Floriani, E Magillo, Multiresolution Meshes, Principles of Multiresolution in Geometric Modeling - PRIMUS01 summer school, pp. 193-234, Munich, August 22-30, 2001
[29] 赵新华，大数据量网格模型的建模与简化技术研究，2002．1 国防科学技术大学研究生院，工学硕士学位论文
[30] Lingas A. The Greedy and Delaunay Triangulations are not Bad in the Average Case. Information Processing Letters, 1986(22): 25～31
[31] G. Dutton. Improving locational speci_city of map data - a multiresolution, metadata-driven approach and notation. International Journal of GeographicInformation Systems 10(3), 1996
[32] W. Evans, D. Kirkpatrick, and G. Townsend. Right triangular irregular networks.Algorithmica 30(2), 2001, 264-286. Special Issue on Algorithms for Geographical Information.
[33] Peter Lindstrom and Valerio Pascucci. Visualization of Large Terrains Made Easy. IEEE Visualization 2001 pp. 363-370, 574, October 2001
[34] 王璐锦 唐泽圣，基于分形维数的地表模型多分辨率动态绘制，软件学报 2000．11
[35] 周昆 潘志庚 石教英，基于混合多细节层次技术的实时绘制算法，软件学报，2001．12
[36] 廖巍，汤晓安，陈荦，吴秋云，一种视点相关的多分辨率地形实时绘制方法，计算机工程与科学，已录用
[37] P. Lindstrom and V. Pascucci, Terrain simplification Simplified: A General Framework for View-Dependent Out-of-Core Visualization. In IEEE Visualization 2002 pp. 247-253,357, May 2002