三维地形生成算法分析、研究与改进
|
摘要
三角剖分是计算机辅助几何设计、几何造型及计算机图形学中的重要研究内容之一,在曲面重构、三维有限元方法的预处理、医学可视化及地理信息系统等领域有着广泛的应用。对于三角剖分算法来说,最重要的就是其复杂度低和高质量网格的形成。Delaunay三角剖分算法由于其良好的优化特性受到青睐,本文对其算法进行研究及改进有着重要的理论意义和重大的应用价值。
本文研究的是空间三维散乱点的三角剖分方法,由三维散乱点的导入、三角剖分过程到最后的结果显示输出,涉及到了计算几何、计算机图形学等相关知识。平面的三角剖分方法已经较为成熟,而三维三角剖分方法仍需进一步完善和改进,这正是本文对其进行研究的目的。
根据三维散乱点集构造曲面剖分在CAD、反求工程等方面有着十分广泛的应用,本文介绍了几种常用的剖分方法,主要阐述和分析了直接三维三角剖分方法中的一种增量算法——Choi算法以及几种常用的剖分优化准则。在研究和分析了典型的三角剖分算法的思想后,针对Choi算法提出改进意见。针对原算法当中点预处理过程中可见点不一定存在以及原算法当中存在的数据冗余等问题进行改进,采用一种新的点预处理方法来替代原算法的点预处理方法并针对原算法的数据结构进行部分改进。采用一种优化准则对剖分结果进行优化,从而得到最终的剖分结果。
最后通过对改进前算法和改进后算法的运行实验结果进行分析,改进后的算法比改进前算法的数据结构更加简练,运行时间更短,达到了算法改进的目的。
Delaunay triangulation is one of the key parts in the field of computer-aided design, geometric modeling and computer graphics, triangulation has been widly applied in areas of surface reconstruction, three-dimensional pretreatment of finite element method, medical visualization and geographic information system(GIS), etc. For triangulation algorithrm, the important things are lower time complexity and higher quality mesh. Delaunay triangulation algorithrm attract attentions because of its good characters, The study and optimization of the algorithrm in this paper make lots of sence both in theory and application.
This paper studies the Delaunay triangulation method of three-dimensional scattered points, including loading scattered points, triangulation and the results display, which relates to knowledges about computational geometry, computer graphics, etc. Delaunay triangulation algorithm in two dimension has been studied very well, but in three dimension, it still needs to be improved, that is also our study purpose.
Surface triangulations based-on 3D arbitrary point-sets are widely applied in CAD and reverseengineering, etc. This paper introduces several proverbial triangulation algorithm, mainly expatiate and analyses one incremental algorithm of direct triangulation algorithm called Choi algorithm and some proverbial optimal criteria. After studying and analysising the typical algorithms of Delaunay triangulation in this paper, we put forward improving ideas about Choi algorithm. About Choi algorithm, there has some problems, such as visible point can not been found in point pretreatment and data redundancy exists in Choi algorithm, etc. We improve Choi algorithm, adopt a new point pretreatment method to replace the former point pretreatment method and improve parts of the data structures of algorithm. After using one optimal criteria to optimize the result of the triangulation, we can gained final result.
Finally the experiment proves that the data structures of improved algorithm is more concise and the runtime is more short, gain one's ends of improving algorithm.
本文研究的是空间三维散乱点的三角剖分方法,由三维散乱点的导入、三角剖分过程到最后的结果显示输出,涉及到了计算几何、计算机图形学等相关知识。平面的三角剖分方法已经较为成熟,而三维三角剖分方法仍需进一步完善和改进,这正是本文对其进行研究的目的。
根据三维散乱点集构造曲面剖分在CAD、反求工程等方面有着十分广泛的应用,本文介绍了几种常用的剖分方法,主要阐述和分析了直接三维三角剖分方法中的一种增量算法——Choi算法以及几种常用的剖分优化准则。在研究和分析了典型的三角剖分算法的思想后,针对Choi算法提出改进意见。针对原算法当中点预处理过程中可见点不一定存在以及原算法当中存在的数据冗余等问题进行改进,采用一种新的点预处理方法来替代原算法的点预处理方法并针对原算法的数据结构进行部分改进。采用一种优化准则对剖分结果进行优化,从而得到最终的剖分结果。
最后通过对改进前算法和改进后算法的运行实验结果进行分析,改进后的算法比改进前算法的数据结构更加简练,运行时间更短,达到了算法改进的目的。
Delaunay triangulation is one of the key parts in the field of computer-aided design, geometric modeling and computer graphics, triangulation has been widly applied in areas of surface reconstruction, three-dimensional pretreatment of finite element method, medical visualization and geographic information system(GIS), etc. For triangulation algorithrm, the important things are lower time complexity and higher quality mesh. Delaunay triangulation algorithrm attract attentions because of its good characters, The study and optimization of the algorithrm in this paper make lots of sence both in theory and application.
This paper studies the Delaunay triangulation method of three-dimensional scattered points, including loading scattered points, triangulation and the results display, which relates to knowledges about computational geometry, computer graphics, etc. Delaunay triangulation algorithm in two dimension has been studied very well, but in three dimension, it still needs to be improved, that is also our study purpose.
Surface triangulations based-on 3D arbitrary point-sets are widely applied in CAD and reverseengineering, etc. This paper introduces several proverbial triangulation algorithm, mainly expatiate and analyses one incremental algorithm of direct triangulation algorithm called Choi algorithm and some proverbial optimal criteria. After studying and analysising the typical algorithms of Delaunay triangulation in this paper, we put forward improving ideas about Choi algorithm. About Choi algorithm, there has some problems, such as visible point can not been found in point pretreatment and data redundancy exists in Choi algorithm, etc. We improve Choi algorithm, adopt a new point pretreatment method to replace the former point pretreatment method and improve parts of the data structures of algorithm. After using one optimal criteria to optimize the result of the triangulation, we can gained final result.
Finally the experiment proves that the data structures of improved algorithm is more concise and the runtime is more short, gain one's ends of improving algorithm.
引文
[1]王永明.地形可视化,中国图像图形学报,2000,6(6):449-456页.
[2]张继开,古梅,黄心渊.三维地形可视化技术的研究.计算机仿真,2005,7(7);118-120页.
[3]靳海亮,高井祥.三维地形可视化技术研究进展.测绘科学,2006,11.6(31):162-165页.
[4]陶闯,林宗坚,卢健.分形地形模型.计算机辅助设计与图形学学报,1996,8(3):178-186.
[5]F Kenton Musgrave et al.The synthesis and rendering of eroded fractal terrains.Computer Graphics.1989,23(3):41-50.
[6]Alvy Ray Smith.Plants,Fractal,and Formal languages.Computer Graphics,1984,18(3):1-10.
[7]汤安国,刘学军等.数字高程模型及地学分析的原理与方法.科学出版社,2005.
[8]刘学军,符锌砂,赵建.三等.三角网数字地面模型快速构建算法研究.中国公路学报,2000,4.13(2):31-36页.
[9]邢建业,杨艳艳.Delaunay三角网生成算法研究.内江科技,2007,5.
[10]易法令,韩德志等.带特征线约束的Delaunay三角网剖分最优算法的研究及实现.计算机工程,2001,6.27(6):32-34页.
[11]刘新.一种改进的构建凸包的分治算法.计算机工程与科学,2006,28(8):63-65.
[12]周秋生.建立数字地面模型算法研究.测绘工程,2001(1):15-18页.
[13]张永春,达飞鹏,宋文忠.三维散乱点集的曲面三角剖分.[M]…计算机图形学报,2006,12:1379-1388页.
[14]戴晓明,朱萍.平面散乱点三角剖分分治算法的实现.计算机技术与发展,2006,1(16):11-13.
[15]He Meifang,Zhou Laishui,Zhang Liyan,Liu Shenglan.《Segmentation of scattered point data through a new curvature analysis algorithm》.[M]...Journal of Southeast University,2004,1:243-246页.
[16]Rui Yi-Kang,Wang Jie-Chen.《New study of compound algorithm based on sweep line and divide-and-conquer algorithms for constructing Delaunay triangulation》.SinoMaps Press,2007,8:157-168页.
[17]Brouns Gert,De Wulf Alain,Constales Denis.《Delaunay triangulation algorithms useful for multibeam echosounding》.American Society of Civil Engineers,2003,5:275-279页.
[18]Hoope H,DeRose T,Duchamp T etal.Surface reconstruction from unorganized points.In:Cunningham Sed.Proceedings of the SIGGRA PH'92.Danvers:Addison-Wesley Publishing Company,1992:71-78
[19]Hoppe H,DeRose T,Duchamp T et al.Mesh optimization.In:Cunninghum Sed.Proceeding of the SIGGRA PH'93,Danvers:Addison-Wesley Publishing Company,1993.
[20]Foley T A,Hagen H,Nielson GM.Visualizing and modeling unstructured data.The Visual Computer International Journal of Computer Graphics,1993,9(8):439-449.
[21]Pratt V.Direct least-squares fitting of algebraic surfaces.In:Stone MC ed.Proceedings of the SIGGRA PH'87.Danvers:Addison-Wesley Publishing Company,1987:145-152.
[22]Lawson C L.C~1 surface interpolation for scattered data on a sphere J.Rocky Mount J Math,1984,14(1):223-237.
[23]Sibson R.Locally equiangular triangulations.The Computer Journal,1978,21(3):243-245
[24]Green P J,Sibson R.Computing dirichlet tessellations in the plane.The Computer Journal,1978,21(2):168-173.
[25]Bowyer A.Computing drichlet tesselation Computing Journal.1981,24(2).:162-166.
[26]Watson D F.Computing the n-dimensional Delannay tessellation with application to Voronoi polytopes.The Computer Journal,1981,24(2):167-172.
[27]Dey T K,Sngihara K,Bajaj C L.Delaunay triangulations in three dimensions with finite precision arithm eric.Computer Aided Geometric Design,1992,9(5):457-470.
[28]Amenta N,BernM,Kam vysselisM.A new voronoi-based surface reconstruction algorithm.In:CohenM ed.Proceedings of the SIGGRA PH'98,Danvers:Addison-Wesley Publishing Company,1992:415-421.
[29]Heff K E,Culver T,Keyser Jet al.Fast computation of generalized voronoi-diagrams using graphics hardware.In:Rockwood A ed.Proceedings of the SIGGRA PH'9.Danvers:Addison-Wesley Publishing Company,1992:277-286
[30]Boissonnat J2D.Geometric structures for three-dimensional shape representation.ACM Transactions on Graphics,1984,3(4):266-286
[31]Edelsbrunner H,Mucke E E Three-Dimensional alphashapes.ACM Transactions on Graphics,1994,13(1):43-72.
[32]Bajaj C L,Bernardini F,G.A utomatic reconstruction of surfaces and scalar fields from 3D scans.In:Cook Red.Proceedings of the SIGGRA PH'95.Danvers:Addison-Wesley Publishing Company,1995:109-118
[33]Xu X,Harada K.Automatic Surface Reconatruction with Alphe.shape Method.Visual Computer,2003,19(7-8):431-443
[34]孙肖霞,孙殿柱,李延瑞,等.散乱数据点的快速三角剖分算法.中国机械工程,2006,8(17):245-248.
[35]周儒荣,张丽艳,苏旭等.海量散乱点的曲面重建算法J..软件学报,2001,12(2):249-255.
[36]Brouns Gert,De Wulf Alain,Constales Denis.《Delaunay triangulation algorithms useful for multibeam echosounding》 American Society of Civil Engineers,2003,5:275-279页.
[37]熊英,胡于进.基于映射法和Delaunay方法的曲面三角网格划分算法[J].计算机辅助设计与图形学学报,2002,14(1):56-60页.
[38]SHEN Hui cun,ZHOU Lai shui,ZHANG Li yan.《PARAMETERIZATION OF TRIANGULARM ESHES》[M].Transactions of Nanjing University of Aeronautics & A stronautics,2004,2:P274-250.
[39]Lai Jiing-Yih,Chi Chen-Tung,Ueng Wen-Der.《On the development of a surface-based triangulation algorithm for 3D cloud points》.Chinese Mechanical Engineering Society,2005,3:P301-309.
[40]孟宪海,蔡强,李吉刚等.面向四面体网格生成的曲面Delaunay三角化算法.工程图学学报,2006,1:76-81页.
[41]陈慧群,陈少克.一种基于格子分块的快速Delaunay三角剖分算法.计算机与数字工程,2007,2(35):9-11.
[42]Mark P Kumler.A Quantitative Comparsion of Regular and Irregular Digital Terrain Models.GIS/LIS' 90,1990
[43]Hu W,Yang W,Y.An Adaptive Mesh Model for 3D Reconatruction from Unorganized Data Points. International Journal of Advanced Manufacturing Technology,2005,26(11-12):1362-1369.
[44]肖双九,张树生,邱泽阳等.散乱数据点三角网格综合优化及分析.中国机械工程,2002,13(19):1666-1669.
[45]王群,李爱平,马淑梅.狭长三角网格优化方法的研究及实现.组合机床与自动化加工技术,2004,4:40-41页.
[46]单东日,柯映林.基于二维Delaunay近邻的空间散乱数据曲面重建算法.中国机械工程,2003,14(9):756-759.
[47]贺磊,纪英舵,许萌.空间散乱点Delaunay三角剖分.科技资讯,2003,33:201-202.
[48]张永春,达飞鹏,宋文忠.基于一种曲率最小优化准则的散乱点三角剖分.东南大学报,2004,11(6);851-856.
[49]孔德慧,陈其明,汪叔淳.一种新的曲面剖分优化准则.工程图学学报,1995,16(1):28-34.
[50]柯映林,周儒荣.实现3D离散点优化三角剖分的三维算法[J.计算机辅助设计与图形学学报,1994,6(4):241-248.
[51]姜寿山,杨海成,候增选.用空间形状优化准则完成散乱数据的三角剖分[J.计算机辅助设计与图形学学报,1995,7(4):241-249.
[52]Choi B K,Shin H Y,Yoon Y I,et al..Triangulation of scattered data in 3D space J.Computer Aided Design,1988,20(5):239-248.
[53]Fang T P,Piegl L.A Algorithm for delaunary triangulation and convex-huel computation using a sparse matrix.Computer Aided Design,1992,24(8).
[2]张继开,古梅,黄心渊.三维地形可视化技术的研究.计算机仿真,2005,7(7);118-120页.
[3]靳海亮,高井祥.三维地形可视化技术研究进展.测绘科学,2006,11.6(31):162-165页.
[4]陶闯,林宗坚,卢健.分形地形模型.计算机辅助设计与图形学学报,1996,8(3):178-186.
[5]F Kenton Musgrave et al.The synthesis and rendering of eroded fractal terrains.Computer Graphics.1989,23(3):41-50.
[6]Alvy Ray Smith.Plants,Fractal,and Formal languages.Computer Graphics,1984,18(3):1-10.
[7]汤安国,刘学军等.数字高程模型及地学分析的原理与方法.科学出版社,2005.
[8]刘学军,符锌砂,赵建.三等.三角网数字地面模型快速构建算法研究.中国公路学报,2000,4.13(2):31-36页.
[9]邢建业,杨艳艳.Delaunay三角网生成算法研究.内江科技,2007,5.
[10]易法令,韩德志等.带特征线约束的Delaunay三角网剖分最优算法的研究及实现.计算机工程,2001,6.27(6):32-34页.
[11]刘新.一种改进的构建凸包的分治算法.计算机工程与科学,2006,28(8):63-65.
[12]周秋生.建立数字地面模型算法研究.测绘工程,2001(1):15-18页.
[13]张永春,达飞鹏,宋文忠.三维散乱点集的曲面三角剖分.[M]…计算机图形学报,2006,12:1379-1388页.
[14]戴晓明,朱萍.平面散乱点三角剖分分治算法的实现.计算机技术与发展,2006,1(16):11-13.
[15]He Meifang,Zhou Laishui,Zhang Liyan,Liu Shenglan.《Segmentation of scattered point data through a new curvature analysis algorithm》.[M]...Journal of Southeast University,2004,1:243-246页.
[16]Rui Yi-Kang,Wang Jie-Chen.《New study of compound algorithm based on sweep line and divide-and-conquer algorithms for constructing Delaunay triangulation》.SinoMaps Press,2007,8:157-168页.
[17]Brouns Gert,De Wulf Alain,Constales Denis.《Delaunay triangulation algorithms useful for multibeam echosounding》.American Society of Civil Engineers,2003,5:275-279页.
[18]Hoope H,DeRose T,Duchamp T etal.Surface reconstruction from unorganized points.In:Cunningham Sed.Proceedings of the SIGGRA PH'92.Danvers:Addison-Wesley Publishing Company,1992:71-78
[19]Hoppe H,DeRose T,Duchamp T et al.Mesh optimization.In:Cunninghum Sed.Proceeding of the SIGGRA PH'93,Danvers:Addison-Wesley Publishing Company,1993.
[20]Foley T A,Hagen H,Nielson GM.Visualizing and modeling unstructured data.The Visual Computer International Journal of Computer Graphics,1993,9(8):439-449.
[21]Pratt V.Direct least-squares fitting of algebraic surfaces.In:Stone MC ed.Proceedings of the SIGGRA PH'87.Danvers:Addison-Wesley Publishing Company,1987:145-152.
[22]Lawson C L.C~1 surface interpolation for scattered data on a sphere J.Rocky Mount J Math,1984,14(1):223-237.
[23]Sibson R.Locally equiangular triangulations.The Computer Journal,1978,21(3):243-245
[24]Green P J,Sibson R.Computing dirichlet tessellations in the plane.The Computer Journal,1978,21(2):168-173.
[25]Bowyer A.Computing drichlet tesselation Computing Journal.1981,24(2).:162-166.
[26]Watson D F.Computing the n-dimensional Delannay tessellation with application to Voronoi polytopes.The Computer Journal,1981,24(2):167-172.
[27]Dey T K,Sngihara K,Bajaj C L.Delaunay triangulations in three dimensions with finite precision arithm eric.Computer Aided Geometric Design,1992,9(5):457-470.
[28]Amenta N,BernM,Kam vysselisM.A new voronoi-based surface reconstruction algorithm.In:CohenM ed.Proceedings of the SIGGRA PH'98,Danvers:Addison-Wesley Publishing Company,1992:415-421.
[29]Heff K E,Culver T,Keyser Jet al.Fast computation of generalized voronoi-diagrams using graphics hardware.In:Rockwood A ed.Proceedings of the SIGGRA PH'9.Danvers:Addison-Wesley Publishing Company,1992:277-286
[30]Boissonnat J2D.Geometric structures for three-dimensional shape representation.ACM Transactions on Graphics,1984,3(4):266-286
[31]Edelsbrunner H,Mucke E E Three-Dimensional alphashapes.ACM Transactions on Graphics,1994,13(1):43-72.
[32]Bajaj C L,Bernardini F,G.A utomatic reconstruction of surfaces and scalar fields from 3D scans.In:Cook Red.Proceedings of the SIGGRA PH'95.Danvers:Addison-Wesley Publishing Company,1995:109-118
[33]Xu X,Harada K.Automatic Surface Reconatruction with Alphe.shape Method.Visual Computer,2003,19(7-8):431-443
[34]孙肖霞,孙殿柱,李延瑞,等.散乱数据点的快速三角剖分算法.中国机械工程,2006,8(17):245-248.
[35]周儒荣,张丽艳,苏旭等.海量散乱点的曲面重建算法J..软件学报,2001,12(2):249-255.
[36]Brouns Gert,De Wulf Alain,Constales Denis.《Delaunay triangulation algorithms useful for multibeam echosounding》 American Society of Civil Engineers,2003,5:275-279页.
[37]熊英,胡于进.基于映射法和Delaunay方法的曲面三角网格划分算法[J].计算机辅助设计与图形学学报,2002,14(1):56-60页.
[38]SHEN Hui cun,ZHOU Lai shui,ZHANG Li yan.《PARAMETERIZATION OF TRIANGULARM ESHES》[M].Transactions of Nanjing University of Aeronautics & A stronautics,2004,2:P274-250.
[39]Lai Jiing-Yih,Chi Chen-Tung,Ueng Wen-Der.《On the development of a surface-based triangulation algorithm for 3D cloud points》.Chinese Mechanical Engineering Society,2005,3:P301-309.
[40]孟宪海,蔡强,李吉刚等.面向四面体网格生成的曲面Delaunay三角化算法.工程图学学报,2006,1:76-81页.
[41]陈慧群,陈少克.一种基于格子分块的快速Delaunay三角剖分算法.计算机与数字工程,2007,2(35):9-11.
[42]Mark P Kumler.A Quantitative Comparsion of Regular and Irregular Digital Terrain Models.GIS/LIS' 90,1990
[43]Hu W,Yang W,Y.An Adaptive Mesh Model for 3D Reconatruction from Unorganized Data Points. International Journal of Advanced Manufacturing Technology,2005,26(11-12):1362-1369.
[44]肖双九,张树生,邱泽阳等.散乱数据点三角网格综合优化及分析.中国机械工程,2002,13(19):1666-1669.
[45]王群,李爱平,马淑梅.狭长三角网格优化方法的研究及实现.组合机床与自动化加工技术,2004,4:40-41页.
[46]单东日,柯映林.基于二维Delaunay近邻的空间散乱数据曲面重建算法.中国机械工程,2003,14(9):756-759.
[47]贺磊,纪英舵,许萌.空间散乱点Delaunay三角剖分.科技资讯,2003,33:201-202.
[48]张永春,达飞鹏,宋文忠.基于一种曲率最小优化准则的散乱点三角剖分.东南大学报,2004,11(6);851-856.
[49]孔德慧,陈其明,汪叔淳.一种新的曲面剖分优化准则.工程图学学报,1995,16(1):28-34.
[50]柯映林,周儒荣.实现3D离散点优化三角剖分的三维算法[J.计算机辅助设计与图形学学报,1994,6(4):241-248.
[51]姜寿山,杨海成,候增选.用空间形状优化准则完成散乱数据的三角剖分[J.计算机辅助设计与图形学学报,1995,7(4):241-249.
[52]Choi B K,Shin H Y,Yoon Y I,et al..Triangulation of scattered data in 3D space J.Computer Aided Design,1988,20(5):239-248.
[53]Fang T P,Piegl L.A Algorithm for delaunary triangulation and convex-huel computation using a sparse matrix.Computer Aided Design,1992,24(8).