基于离散数据的三维地形建模技术研究
|
摘要
地形三维可视化技术一直以来是地理信息系统(GIS)、虚拟现实(VR)、计算机图形学等领域研究的热点。本文针对当前地形三维建模及可视化技术的研究现状,围绕着地形数字模型的建立、地形模型简化以及地形多分辨率模型构建等关键技术内容展开讨论与研究,目标是由离散数据构建地形数字化模型并且实现三维地形的可视化模拟。主要完成了如下研究工作:
(1)在离散数据构建地形数字模型方面,研究了地形数字高程数据的获取方法与DEM的地形表面建模方法。
(2)在分析了常用三角剖分算法的基础上,针对大规模离散数据生成三角网速度较慢的问题,提出了一个改进的三角网生成算法,先将离散点集进行自适应分块,然后对每一块进行三角剖分,最后对所有的子三角网的进行归并,以生成覆盖全区域的三角网模型。
(3)针对用计算机处理复杂的地形模型时,在显示、渲染、存储等方面存在着很多困难,为了解决这些问题,提出了一个改进的基于渐进网格的模型简化算法。算法是根据实际的地形的特征,给出了边优先级和点重要度的计算方法,通过确定地形三角网中每条边的优先级,删除的一些重要度小的点,以实现地形模型的简化。
(4)根据视点的位置,构造了基于TIN的地形多分辨率模型。最后,本文根据上述研究的基础上,结合视区裁剪算法与任意方向的漫游方法,实现了基于离散数据的三维地形模型建立与地形实时模拟显示。
Three-dimensional (3D) terrain visualization is always a hot topic in Geographic Information System (GIS), Virtual Reality (VR), Computer Graphics and other related fields. According to the current research situation of 3D terrain modeling and visualization technology, this thesis focuses on discussion and research of the key modeling technology , digital terrain modeling, terrain model simplification and construction of multi-resolution modeling. The thesis aimed to construct digital terrain modeling by discrete data, and to realize the simulation of 3D terrain surface. The main research results are summarized as follows.
(1) DEM data acquisition method and terrain surface modeling method are researched in the construction of digital terrain model by discrete data.
(2) On the basis of common Delaunay triangulation algorithm analysis, to solve the existing problems of low speed that triangle network building with large scale discrete data, an improved algorithm is presented in this thesis. First, discrete points are adaptively divided into many sub-blocks, then the discrete points in each sub-block are triangulated, fnally all of the sub- triangulation network are incorporated into together, in order to construct triangulation model that covers the whole area.
(3)When these complex models are dealt with by computer, there are many difficulties such as display, rendering, storage and so on. In order to solve these problems, this thesis presented an algorithm of simplification for terrain model based on progressive meshes. The calculation methods of priority of edge and importance degree of point are provided in the improvement algorithm by real terrain feature, the algorithm determines the priority level on each edge and delete some less important degree point in the terrain triangular mesh, to realize the simplified terrain model.
(4) According to the position of viewpoint,the terrain multi-resolution model based on the TIN is constructed in this thesis. Finally, based on research above, combining with Clipping Algorithm of visual areas and arbitrary direction roaming method, this thesis realized the 3D terrain modeling and real-time simulation of terrain based on discrete data.
(1)在离散数据构建地形数字模型方面,研究了地形数字高程数据的获取方法与DEM的地形表面建模方法。
(2)在分析了常用三角剖分算法的基础上,针对大规模离散数据生成三角网速度较慢的问题,提出了一个改进的三角网生成算法,先将离散点集进行自适应分块,然后对每一块进行三角剖分,最后对所有的子三角网的进行归并,以生成覆盖全区域的三角网模型。
(3)针对用计算机处理复杂的地形模型时,在显示、渲染、存储等方面存在着很多困难,为了解决这些问题,提出了一个改进的基于渐进网格的模型简化算法。算法是根据实际的地形的特征,给出了边优先级和点重要度的计算方法,通过确定地形三角网中每条边的优先级,删除的一些重要度小的点,以实现地形模型的简化。
(4)根据视点的位置,构造了基于TIN的地形多分辨率模型。最后,本文根据上述研究的基础上,结合视区裁剪算法与任意方向的漫游方法,实现了基于离散数据的三维地形模型建立与地形实时模拟显示。
Three-dimensional (3D) terrain visualization is always a hot topic in Geographic Information System (GIS), Virtual Reality (VR), Computer Graphics and other related fields. According to the current research situation of 3D terrain modeling and visualization technology, this thesis focuses on discussion and research of the key modeling technology , digital terrain modeling, terrain model simplification and construction of multi-resolution modeling. The thesis aimed to construct digital terrain modeling by discrete data, and to realize the simulation of 3D terrain surface. The main research results are summarized as follows.
(1) DEM data acquisition method and terrain surface modeling method are researched in the construction of digital terrain model by discrete data.
(2) On the basis of common Delaunay triangulation algorithm analysis, to solve the existing problems of low speed that triangle network building with large scale discrete data, an improved algorithm is presented in this thesis. First, discrete points are adaptively divided into many sub-blocks, then the discrete points in each sub-block are triangulated, fnally all of the sub- triangulation network are incorporated into together, in order to construct triangulation model that covers the whole area.
(3)When these complex models are dealt with by computer, there are many difficulties such as display, rendering, storage and so on. In order to solve these problems, this thesis presented an algorithm of simplification for terrain model based on progressive meshes. The calculation methods of priority of edge and importance degree of point are provided in the improvement algorithm by real terrain feature, the algorithm determines the priority level on each edge and delete some less important degree point in the terrain triangular mesh, to realize the simplified terrain model.
(4) According to the position of viewpoint,the terrain multi-resolution model based on the TIN is constructed in this thesis. Finally, based on research above, combining with Clipping Algorithm of visual areas and arbitrary direction roaming method, this thesis realized the 3D terrain modeling and real-time simulation of terrain based on discrete data.
引文
[1]齐敏,郝重阳,佟明安.三维地形生成与实时显示技术研究进展[J].中国图象图形学报,2000,5(4):269-274.
[2]张慧杰,孙吉贵,刘雪洁等.大规模三维地形可视化算法研究进展[J].计算机科学,2007,34(3):10-16.
[3]王永明.地形可视化[J].中国图象图形学报,2000,5 (6):449-456.
[4]彭仪普.地形三维可视化及其实时绘制技术研究[D].成都:西南交通大学,2002.
[5]吴立新,史文中.地理信息系统原理与算法[M].北京:科学出版社,2005.
[6]胡金星等.高效构建Delaunay三角网数字地形模型算法研究[J].北京大学学报(自然科学版),2003,39(5):736-741
[7]邵春丽,胡鹏,黄承义.Delaunay三角网的算法详述及其应用发展前景[J].测绘科学,2004,29(6):68～71.
[8] Kolingerova I, Zalik B. Improvements to Randomized Incremental Delaunay Insertion[J]. Computers&Graphics, 2002, 26(3):477-490.
[9] Sohler C.Fast Reconstruction of Delaunay Triangulations.Computational Geometry,2005,31(3):166-178.
[10] Sheng Zhou,Jones C B.HCPO:An Efficient Insertion Order for Incremental Delaunay Triangulation.Information Processing LeaerS.2005,(93):37-42. [1l]吴宇晓,张登荣.生成Delaunay三角网的快速合成算法[J].浙江大学学报, 2004, 31(3): 343-348.
[12] Levcopoulos C, Krznaric D. The Greedy Triangulation Can be Computed from the Delaunay Triangulation in Linear Time[J].Computational Geometry,1999,14(4):197-220.
[13] Zalik B. An Efficient Sweep-Line Delaunay Triangulation Algorithm[J].Computer Aided Design,2005,37(10):1027-1038.
[14]章孝灿.快速高精度DEM生成技术研究[D].杭州:浙江大学,2003.
[15]陈学工,陈树强,王丽青.基于凸壳技术的Delaunay三角网生成算法[J].计算机工程与应用,2006,42(6):27～29.
[16]刘学军,龚健雅.约束数据域的Delaunay三角剖分与修改算法[J]..测绘学报,2001,30(1):82～88.
[17] Domiter V. Constrained Delaunay Triangulation using Plane Subdivision. www.cescg.org/CESCG-2004/papers/41_DomiterVid.pdf,2004.
[18] Paul Morrison, Ju Jia Zou. Triangle refinement in a constrained Delaunay triangulation skeleton[J]. Pattern Recognition, 2007,40(10): 2754-2765.
[19]陈学工,潘懋.平面散乱点集约束Delaunay三角形剖分切割算法.计算机工程与应用,2001,(15):96-97.
[20] Kallmann M,Bieri H,Thalmann D.Fully Dynamic Constrained Delaunay Triangulations. Geometric Modelling for Scientific Visualization, Heidelberg, Germany,2003.
[21]曾薇,孟祥旭,杨承磊等.平面多边形域的快速约束Delaunay三角化[J]..计算机辅助设计与图形学学报,2005,17(9):1934-1940.
[22] Clark,James.Hierarchical Geometric Models for Visible Surface Algorithms [J]. Communications of the ACM,1976(10):547-554.
[23] M Duchaineauy,M Wolinsky.ROAMing terrain:real-time,optimally adapting meshes [J]. Proceedings of IEEE Visualization 1997 Conference,Held in Phoenix Arizona,October 1997:18-88.
[24] Hoppe H.Progressive meshes.Computer Graphic(SIGGRAPH Proceedings),1996:99-108.
[25] William Evans,David Kirkpatrick,etc. Right Triangulated Irregular Networks. Technical Report 97-09,University of Arizona,May.
[26] M. D. Berg ,K.T.G. Dobrindt. On Levels of Detail in Terrains .Graphical models and image processing: GMIP1998, 60( 1), 001–012.
[27] R. Klein and D. Cohen-Or. Incremental View dependent Multiresolution Triangulation Terrain. Proceeding of Pacific Graphics, 1998.
[28]陈刚,杨明果,王科伟.地形TIN模型的实时连续LOD算法设计与实现[J].测绘学院学报,2003,20(4):286-289.
[29]余明,左小清,李清泉.一种基于TIN的视相关动态多分辨率地形模型[J].武汉大学学报(信息科学版),2004,29(12):1106-1110.
[30] Luebke, D. e Erikson, C. View-dependent simplification of arbitrary polygonal environments. Computer Graphics 31, Annual Conference Series (1997), 199–208.
[31] Hoppe H. View-dependent refinement of progressive meshes[J].Computer Graphics,1997,31: 189-198.
[32] Hoppe H. Smooth View Dependant Level-of-Detail Control and its Application to TerrainRendering. Procceedings of IEEE Visualization,1998:35-42.
[33]蒲浩,宋占峰,詹振炎.一种大规模地形模型的视相关简化算法[J].西安交通大学学报,2004,24(9):13-15.
[34]许妙忠.虚拟现实中三维地形建模和可视化技术及算法研究[D].武汉大学,2003.
[35]张淑军,周忠等.基于运动估算的多分辨率地形分块调度方法[J].计算机辅助设计与图形学学报2009,21(7):880-885.
[36]李清泉,杨必胜等.三维空间数据的实时获取、建模与可视化[M].武汉:武汉大学出版社,2003.
[37]汤国安,刘学军.数字高程模型及地学分析原理与方法[M].北京:科学出版社,2005.
[38]吴晓波,王世新等. Delaunay三角网的生成算法研究.测绘学报. 1999.2,28(1):28-35
[39]周培德.计算几何——算法设计与分析(第三版)[M].北京:清华大学出版社, 2008.
[40]王高峰.地形三维建模与可视化技术研究[D].河南理工大学,2007.
[41] W.J.Schroeder,J.A.Zarge. Decimation of triangle meshes[J].Computer Graphics,1992,26(2):65-70
[42]顾耀林,朱晓燕.基于渐进网格的复杂模型简化算法[J].计算机工程与应用,2007, 43(2): 78-80.
[43]王玉琨,姚华.基于渐进网格的地形模型简化算法的研究[J].微计算机信息.2010,8-3:203-205.
[44]宋华,刘江.一种基于二次误差测度的三维累进网格生成算法. [J].计算机应用.2008, 28(12):3160-3162.
[45]冯洁,查红彬.大型三维网格模型的简化及基于视点的LOD控制[J].计算机辅助设计与图形学学报.2006,18(2):186-193.
[46]董杰,汤松涛,韩敏.一种基于TIN的大规模地形实时可视化算法研究[J].小型微型计算机系统.2009,30(6):1148-1152.
[47]许妙忠,李德仁.地形可视化中快速视区裁剪算法研究[J].武汉大学学报(信息科学版).2004, 29(12):1080-1083.
[48]吴亚东,刘玉树.地形实时绘制中的视区裁剪算法[J].计算机应用.2000,20:24
[49]李利军,李丹.基于视角的可视区动态裁剪算法研究[J].计算机与数字工程, 2006, 34(9):35-37.
[50]闫长青,岳天祥.高精度高速度曲面建模的3维地表模拟和漫游算法[J].中国图象图形学报,2010, 15(7): 1126-1132.
[51]赵争鸣,顾耀林.基于三角形折叠的视相关多层次细节模型[J].计算机工程, 2007,33(4):277-279.
[52]陈少强,朱铁稳等.大规模多分辨率地形模型简化生成算法[J].计算机辅助设计与图形学学报.2005, 17(2):273-278.
[53] Garland M, Heckbert P. Surface simplification using quadric error metrics. In Proc. SIGGRAPH, Los Angeles, USA, Aug. 3-8, 1997 :209-216.
[54]王玉琨,王高峰,刘启平.基于四叉树的地形可视化研究[J].地理与地理信息科学.2008, 24(2):30-32.
[2]张慧杰,孙吉贵,刘雪洁等.大规模三维地形可视化算法研究进展[J].计算机科学,2007,34(3):10-16.
[3]王永明.地形可视化[J].中国图象图形学报,2000,5 (6):449-456.
[4]彭仪普.地形三维可视化及其实时绘制技术研究[D].成都:西南交通大学,2002.
[5]吴立新,史文中.地理信息系统原理与算法[M].北京:科学出版社,2005.
[6]胡金星等.高效构建Delaunay三角网数字地形模型算法研究[J].北京大学学报(自然科学版),2003,39(5):736-741
[7]邵春丽,胡鹏,黄承义.Delaunay三角网的算法详述及其应用发展前景[J].测绘科学,2004,29(6):68～71.
[8] Kolingerova I, Zalik B. Improvements to Randomized Incremental Delaunay Insertion[J]. Computers&Graphics, 2002, 26(3):477-490.
[9] Sohler C.Fast Reconstruction of Delaunay Triangulations.Computational Geometry,2005,31(3):166-178.
[10] Sheng Zhou,Jones C B.HCPO:An Efficient Insertion Order for Incremental Delaunay Triangulation.Information Processing LeaerS.2005,(93):37-42. [1l]吴宇晓,张登荣.生成Delaunay三角网的快速合成算法[J].浙江大学学报, 2004, 31(3): 343-348.
[12] Levcopoulos C, Krznaric D. The Greedy Triangulation Can be Computed from the Delaunay Triangulation in Linear Time[J].Computational Geometry,1999,14(4):197-220.
[13] Zalik B. An Efficient Sweep-Line Delaunay Triangulation Algorithm[J].Computer Aided Design,2005,37(10):1027-1038.
[14]章孝灿.快速高精度DEM生成技术研究[D].杭州:浙江大学,2003.
[15]陈学工,陈树强,王丽青.基于凸壳技术的Delaunay三角网生成算法[J].计算机工程与应用,2006,42(6):27～29.
[16]刘学军,龚健雅.约束数据域的Delaunay三角剖分与修改算法[J]..测绘学报,2001,30(1):82～88.
[17] Domiter V. Constrained Delaunay Triangulation using Plane Subdivision. www.cescg.org/CESCG-2004/papers/41_DomiterVid.pdf,2004.
[18] Paul Morrison, Ju Jia Zou. Triangle refinement in a constrained Delaunay triangulation skeleton[J]. Pattern Recognition, 2007,40(10): 2754-2765.
[19]陈学工,潘懋.平面散乱点集约束Delaunay三角形剖分切割算法.计算机工程与应用,2001,(15):96-97.
[20] Kallmann M,Bieri H,Thalmann D.Fully Dynamic Constrained Delaunay Triangulations. Geometric Modelling for Scientific Visualization, Heidelberg, Germany,2003.
[21]曾薇,孟祥旭,杨承磊等.平面多边形域的快速约束Delaunay三角化[J]..计算机辅助设计与图形学学报,2005,17(9):1934-1940.
[22] Clark,James.Hierarchical Geometric Models for Visible Surface Algorithms [J]. Communications of the ACM,1976(10):547-554.
[23] M Duchaineauy,M Wolinsky.ROAMing terrain:real-time,optimally adapting meshes [J]. Proceedings of IEEE Visualization 1997 Conference,Held in Phoenix Arizona,October 1997:18-88.
[24] Hoppe H.Progressive meshes.Computer Graphic(SIGGRAPH Proceedings),1996:99-108.
[25] William Evans,David Kirkpatrick,etc. Right Triangulated Irregular Networks. Technical Report 97-09,University of Arizona,May.
[26] M. D. Berg ,K.T.G. Dobrindt. On Levels of Detail in Terrains .Graphical models and image processing: GMIP1998, 60( 1), 001–012.
[27] R. Klein and D. Cohen-Or. Incremental View dependent Multiresolution Triangulation Terrain. Proceeding of Pacific Graphics, 1998.
[28]陈刚,杨明果,王科伟.地形TIN模型的实时连续LOD算法设计与实现[J].测绘学院学报,2003,20(4):286-289.
[29]余明,左小清,李清泉.一种基于TIN的视相关动态多分辨率地形模型[J].武汉大学学报(信息科学版),2004,29(12):1106-1110.
[30] Luebke, D. e Erikson, C. View-dependent simplification of arbitrary polygonal environments. Computer Graphics 31, Annual Conference Series (1997), 199–208.
[31] Hoppe H. View-dependent refinement of progressive meshes[J].Computer Graphics,1997,31: 189-198.
[32] Hoppe H. Smooth View Dependant Level-of-Detail Control and its Application to TerrainRendering. Procceedings of IEEE Visualization,1998:35-42.
[33]蒲浩,宋占峰,詹振炎.一种大规模地形模型的视相关简化算法[J].西安交通大学学报,2004,24(9):13-15.
[34]许妙忠.虚拟现实中三维地形建模和可视化技术及算法研究[D].武汉大学,2003.
[35]张淑军,周忠等.基于运动估算的多分辨率地形分块调度方法[J].计算机辅助设计与图形学学报2009,21(7):880-885.
[36]李清泉,杨必胜等.三维空间数据的实时获取、建模与可视化[M].武汉:武汉大学出版社,2003.
[37]汤国安,刘学军.数字高程模型及地学分析原理与方法[M].北京:科学出版社,2005.
[38]吴晓波,王世新等. Delaunay三角网的生成算法研究.测绘学报. 1999.2,28(1):28-35
[39]周培德.计算几何——算法设计与分析(第三版)[M].北京:清华大学出版社, 2008.
[40]王高峰.地形三维建模与可视化技术研究[D].河南理工大学,2007.
[41] W.J.Schroeder,J.A.Zarge. Decimation of triangle meshes[J].Computer Graphics,1992,26(2):65-70
[42]顾耀林,朱晓燕.基于渐进网格的复杂模型简化算法[J].计算机工程与应用,2007, 43(2): 78-80.
[43]王玉琨,姚华.基于渐进网格的地形模型简化算法的研究[J].微计算机信息.2010,8-3:203-205.
[44]宋华,刘江.一种基于二次误差测度的三维累进网格生成算法. [J].计算机应用.2008, 28(12):3160-3162.
[45]冯洁,查红彬.大型三维网格模型的简化及基于视点的LOD控制[J].计算机辅助设计与图形学学报.2006,18(2):186-193.
[46]董杰,汤松涛,韩敏.一种基于TIN的大规模地形实时可视化算法研究[J].小型微型计算机系统.2009,30(6):1148-1152.
[47]许妙忠,李德仁.地形可视化中快速视区裁剪算法研究[J].武汉大学学报(信息科学版).2004, 29(12):1080-1083.
[48]吴亚东,刘玉树.地形实时绘制中的视区裁剪算法[J].计算机应用.2000,20:24
[49]李利军,李丹.基于视角的可视区动态裁剪算法研究[J].计算机与数字工程, 2006, 34(9):35-37.
[50]闫长青,岳天祥.高精度高速度曲面建模的3维地表模拟和漫游算法[J].中国图象图形学报,2010, 15(7): 1126-1132.
[51]赵争鸣,顾耀林.基于三角形折叠的视相关多层次细节模型[J].计算机工程, 2007,33(4):277-279.
[52]陈少强,朱铁稳等.大规模多分辨率地形模型简化生成算法[J].计算机辅助设计与图形学学报.2005, 17(2):273-278.
[53] Garland M, Heckbert P. Surface simplification using quadric error metrics. In Proc. SIGGRAPH, Los Angeles, USA, Aug. 3-8, 1997 :209-216.
[54]王玉琨,王高峰,刘启平.基于四叉树的地形可视化研究[J].地理与地理信息科学.2008, 24(2):30-32.