基于顶点重要度和层次聚类树的地形网格简化
|
摘要
为提高基于精细DEM数据的地形网格简化效率,在传统顶点聚类算法的基础上,提出一种基于顶点重要度和层次聚类树的地形网格简化算法。对地形分块顶点进行聚类,引入由顶点特征值和简化误差构成的顶点重要度来筛选簇代表点;根据代表点构建粗化网格,迭代缝合与简化过程直至完成整个地形网格简化;采用内存层次聚类树对简化的中间结果进行组织,将之用于地形多分辨率绘制中,指导网格的简化和细分。实验结果表明,该算法较好地保持了原始地形特征,缩减了内存消耗,中间结果的利用有效提升了地形渲染效率。
To improve the efficiency of simpilification for terrain mesh based on digital elevation model(DEM),on the basis of traditional vertex clustering algorithm,an mesh simplification method based on vertex importance and hierarchical clustering tree was presented.The vertexes of terrain blocks were clustered,and the importance of vertex which consisted of eigenvalue and simplification error was used to choose the representative vertexes of clusters.Coarse meshes were constructed using these representative vertexs.By carrying on the suture and simplification process iteratively,the whole terrain mesh was simplified.A hierarchial clustering tree in internal memory was used to organize the intermediate simplification meshes and to guide the simplification and tessellation in the view-dependent level-of-detail rendering for terrain.Experimental results show that the algorithm gains good performance in remaining the terrain feature and reduces memory consumption.The efficiency of rendering is improved by taking use of the intermediate simplification results.
To improve the efficiency of simpilification for terrain mesh based on digital elevation model(DEM),on the basis of traditional vertex clustering algorithm,an mesh simplification method based on vertex importance and hierarchical clustering tree was presented.The vertexes of terrain blocks were clustered,and the importance of vertex which consisted of eigenvalue and simplification error was used to choose the representative vertexes of clusters.Coarse meshes were constructed using these representative vertexs.By carrying on the suture and simplification process iteratively,the whole terrain mesh was simplified.A hierarchial clustering tree in internal memory was used to organize the intermediate simplification meshes and to guide the simplification and tessellation in the view-dependent level-of-detail rendering for terrain.Experimental results show that the algorithm gains good performance in remaining the terrain feature and reduces memory consumption.The efficiency of rendering is improved by taking use of the intermediate simplification results.
引文
[1]ZHANG Yaping,XIONG Hua,JIANG Xiaohong,et al.A survey of simplification and multiresolution techniques for massive meshes[J].Journal of Computer-Aided Design&Computer Graphics,2010,22(4):559-568(in Chinese).[张亚萍,熊华,姜晓红,等.大型网格模型简化和多分辨率技术综述[J].计算机辅助设计与图形学学报,2010,22(4):559-568.]
[2]Yu Z,Wong H S,Peng H,et al.ASM:An adaptive simplification method for 3Dpoint-based models[J].Computer-Aided Design,2010,42(7):598-612.
[3]Du Z,Jaromersky P,Chiang Y J,et al.Out-of-core progressive lossless compression and selective decompression of large triangle meshes[J].Data Compression Conference Dcc,2009:420-429.
[4]Zhang S,Zhao J,Wang B.A local feature based simplification method for animated mesh sequence[C]//2nd International Conference on Computer Engineering and Technology.IEEE,2010:681-685.
[5]Lu Y,Li N,Gao P,et al.A parallel memory efficient framework for out-of-core mesh simplification[C]//IEEE International Conference on High Performance Computing and Communication&IEEE International Conference on Embedded Software and Systems,2009:666-671.
[6]Richter R,Dllner J.Out-of-core real-time visualization of massive 3Dpoint clouds[C]//Proceedings of the 7th International Conference on Computer Graphics,Virtual Reality,Visualisation and Interaction in Africa.ACM,2010:121-128.
[7]Zhang G,Liu X.Surface reconstruction and application of subdivision[C]//International Conference on Control,Automation and Systems Engineering,2011:1-4.
[8]Li W,Chen Y,Wang Z,et al.An improved decimation of triangle meshes based on curvature[M]//Rough Sets and Knowledge Technology.Springer International Publishing,2014:260-271.
[9]HUA Haiyang,ZHAO Huaici.Mesh simplification algorithm for terrain model based on feature degree[J].Journal of Computer-Aided Design&Computer Graphics,2011,23(4):594-599(in Chinese).[花海洋,赵怀慈.保持地形特征的网格模型简化算法[J].计算机辅助设计与图形学学报,2011,23(4):594-599.]
[10]ZHU Qinglu.The research and application of LOD technology in large scale scene[D].Beijing:Beijing University of Posts and Telecommunications,2009(in Chinese).[祝清鲁.大规模场景中LOD技术的研究与应用[D].北京:北京邮电大学,2009.]
[11]Hu L,Sander P V,Hoppe H.Parallel view-dependent refinement of progressive meshes[C]//Proceedings of the Symposium on Interactived Graphics&Games,2009:169-176.
[12]Filip Strugar.Continuous distance-dependent level of detail for rendering heightmaps[J].Journal of Graphics Gpu&Game Tools,2009,14(4):57-74.
[13]Paredes E G,Bóo M,Amor M,et al.Extended hybrid meshing algorithm for multiresolution terrain models[J].International Journal of Geographical Information Science,2012,26(5):771-793.
[14]DeVore R,Petrova G,Hielsberg M,et al.Processing terrain point cloud data[J].SIAM Journal on Imaging Sciences,2013,6(1):1-31.
[15]WANG Yanyan,HUI Lifeng,LUO Xiaofeng,et al.Adaptive Loop subdivision algorithm for triangle mesh based on vertex’s importance[J].Computer Engineering and Applications,2014,50(13):201-204(in Chinese).[王艳艳,惠丽峰,罗晓锋,等.三角网格顶点重要度的自适应Loop细分算法[J].计算机工程与应用,2014,50(13):201-204.]
[16]LI Haiting.Research on map tiles’indexing and compression in network[D].Wuhan:Wuhan University,2010(in Chinese).[李海亭.网络环境中地图瓦片的索引与压缩方法研究[D].武汉:武汉大学,2010.]
[17]WU Xiaoyan,GU Yunhua,ZHANG Junyong,et al.Threedimensional terrain modeling method based on cluster analysis and dynamic LOD[J].Computer Engineering and Design,2015,36(2):469-475(in Chinese).[吴晓彦,顾韵华,张俊勇,等.基于聚类和动态LOD的三维地形建模方法[J].计算机工程与设计,2015,36(2):469-475.]
[18]Kang H Y,Jang H,Cho C S,et al.Multi-resolution terrain rendering with GPU tessellation[J].Visual Computer,2015,31(4):455-469.
[2]Yu Z,Wong H S,Peng H,et al.ASM:An adaptive simplification method for 3Dpoint-based models[J].Computer-Aided Design,2010,42(7):598-612.
[3]Du Z,Jaromersky P,Chiang Y J,et al.Out-of-core progressive lossless compression and selective decompression of large triangle meshes[J].Data Compression Conference Dcc,2009:420-429.
[4]Zhang S,Zhao J,Wang B.A local feature based simplification method for animated mesh sequence[C]//2nd International Conference on Computer Engineering and Technology.IEEE,2010:681-685.
[5]Lu Y,Li N,Gao P,et al.A parallel memory efficient framework for out-of-core mesh simplification[C]//IEEE International Conference on High Performance Computing and Communication&IEEE International Conference on Embedded Software and Systems,2009:666-671.
[6]Richter R,Dllner J.Out-of-core real-time visualization of massive 3Dpoint clouds[C]//Proceedings of the 7th International Conference on Computer Graphics,Virtual Reality,Visualisation and Interaction in Africa.ACM,2010:121-128.
[7]Zhang G,Liu X.Surface reconstruction and application of subdivision[C]//International Conference on Control,Automation and Systems Engineering,2011:1-4.
[8]Li W,Chen Y,Wang Z,et al.An improved decimation of triangle meshes based on curvature[M]//Rough Sets and Knowledge Technology.Springer International Publishing,2014:260-271.
[9]HUA Haiyang,ZHAO Huaici.Mesh simplification algorithm for terrain model based on feature degree[J].Journal of Computer-Aided Design&Computer Graphics,2011,23(4):594-599(in Chinese).[花海洋,赵怀慈.保持地形特征的网格模型简化算法[J].计算机辅助设计与图形学学报,2011,23(4):594-599.]
[10]ZHU Qinglu.The research and application of LOD technology in large scale scene[D].Beijing:Beijing University of Posts and Telecommunications,2009(in Chinese).[祝清鲁.大规模场景中LOD技术的研究与应用[D].北京:北京邮电大学,2009.]
[11]Hu L,Sander P V,Hoppe H.Parallel view-dependent refinement of progressive meshes[C]//Proceedings of the Symposium on Interactived Graphics&Games,2009:169-176.
[12]Filip Strugar.Continuous distance-dependent level of detail for rendering heightmaps[J].Journal of Graphics Gpu&Game Tools,2009,14(4):57-74.
[13]Paredes E G,Bóo M,Amor M,et al.Extended hybrid meshing algorithm for multiresolution terrain models[J].International Journal of Geographical Information Science,2012,26(5):771-793.
[14]DeVore R,Petrova G,Hielsberg M,et al.Processing terrain point cloud data[J].SIAM Journal on Imaging Sciences,2013,6(1):1-31.
[15]WANG Yanyan,HUI Lifeng,LUO Xiaofeng,et al.Adaptive Loop subdivision algorithm for triangle mesh based on vertex’s importance[J].Computer Engineering and Applications,2014,50(13):201-204(in Chinese).[王艳艳,惠丽峰,罗晓锋,等.三角网格顶点重要度的自适应Loop细分算法[J].计算机工程与应用,2014,50(13):201-204.]
[16]LI Haiting.Research on map tiles’indexing and compression in network[D].Wuhan:Wuhan University,2010(in Chinese).[李海亭.网络环境中地图瓦片的索引与压缩方法研究[D].武汉:武汉大学,2010.]
[17]WU Xiaoyan,GU Yunhua,ZHANG Junyong,et al.Threedimensional terrain modeling method based on cluster analysis and dynamic LOD[J].Computer Engineering and Design,2015,36(2):469-475(in Chinese).[吴晓彦,顾韵华,张俊勇,等.基于聚类和动态LOD的三维地形建模方法[J].计算机工程与设计,2015,36(2):469-475.]
[18]Kang H Y,Jang H,Cho C S,et al.Multi-resolution terrain rendering with GPU tessellation[J].Visual Computer,2015,31(4):455-469.