空间三维点集建模的算法研究与实现
|
摘要
根据三维离散点集快速、准确地进行物体表面模型重建,在诸如虚拟环境、计算机视觉、逆向工程等领域有着重要的意义,是三维可视化技术的一个重要手段和方法。随着高分辨率遥感技术、数字摄影测量技术、激光扫描系统的发展,包含被测量物体的更多细节的的三维点集数据成为可能,并且成为了高精度测量建模的发展方向。
本文介绍了目前国内外有关三维点集建模的相关算法,例举了雕刻算法、距离函数法、表面生长法、映射法等算法的基本原理与步骤,分析了它们各自的优劣,然后给出了三维可视化、空间离散点集、凸壳、Voronoi图与Delaunay三角剖分、中轴和ε-采样、受限的Delaunay三角剖分、拓扑同胚的条件等与三维点集建模有关的一些理论知识,接着介绍了一种三维点集表面重建的方法以及实现过程,并对这种算法进行了算法实验。本算法结合了雕刻算法和表面生长法的优点,算法实现的基本步骤为：由空间三维离散点集数据导入开始,首先采用逐点插入法,建立四面体网,即建立起了点集之间的拓扑关系,完成了三维离散点集的Delaunay三角剖分；然后,利用每个采样点的法线方向与刚建立的Delaunay三角面之间的角度信息选取受限的Delaunay三角形,作为候选的表面三角形；最后,选取一个初始种子三角形,由这个种子三角形开始,基于每条边的邻接三角形关系,迭代地进行整个物体表面的三角形格网的生长。
最后,对全文的研究工作和研究成果进行了总结,并提出了仍待进一步解决的问题。
3D surface reconstruction rapidly and accuratly by discrete vertex collection has very important significance in many field such as virtual environment,computer vision,reverse engineering.It is also an important method for 3D Visualization.
This paper introduce the related algorithms currently.Introduce the basic principle of Sculpture Algorithm,Distance Function Algorithm,Surface Grow Algorithm and Mapping Algorithm.Analysis their Advantages and disadvantages.This paper also introduce some theory related to 3D surface reconstruction,for example Visualization, discrete vertex collection,convex hull,Voronoi Graphics and Delaunay Triangles,medial axis andε-sampling,Restricted Delaunay Triangles,the condition of Topological homeomorphism.Then introduce a algorithm for 3D surface reconstruction,and do the experiment for this algorithm.The algorithm's basic steps are as fllows:it is begin with the import of discrete vertex collection,first use incremental insertion method to create Tetrahedron network,it is also create topology between vertex collection,it is also finish the Delaunay Triangulation.Then,choose Restricted triangle using the angle imformation between the normal of vertex and the Delaunay triangle.Last,choose a seed triangle,and form this triangle,create the surface triangles network based on the adjacency triangles of extension edge.
By the end of this paper,It has a Summary of this paper's research,and proposed the problem to be resolved.
本文介绍了目前国内外有关三维点集建模的相关算法,例举了雕刻算法、距离函数法、表面生长法、映射法等算法的基本原理与步骤,分析了它们各自的优劣,然后给出了三维可视化、空间离散点集、凸壳、Voronoi图与Delaunay三角剖分、中轴和ε-采样、受限的Delaunay三角剖分、拓扑同胚的条件等与三维点集建模有关的一些理论知识,接着介绍了一种三维点集表面重建的方法以及实现过程,并对这种算法进行了算法实验。本算法结合了雕刻算法和表面生长法的优点,算法实现的基本步骤为：由空间三维离散点集数据导入开始,首先采用逐点插入法,建立四面体网,即建立起了点集之间的拓扑关系,完成了三维离散点集的Delaunay三角剖分；然后,利用每个采样点的法线方向与刚建立的Delaunay三角面之间的角度信息选取受限的Delaunay三角形,作为候选的表面三角形；最后,选取一个初始种子三角形,由这个种子三角形开始,基于每条边的邻接三角形关系,迭代地进行整个物体表面的三角形格网的生长。
最后,对全文的研究工作和研究成果进行了总结,并提出了仍待进一步解决的问题。
3D surface reconstruction rapidly and accuratly by discrete vertex collection has very important significance in many field such as virtual environment,computer vision,reverse engineering.It is also an important method for 3D Visualization.
This paper introduce the related algorithms currently.Introduce the basic principle of Sculpture Algorithm,Distance Function Algorithm,Surface Grow Algorithm and Mapping Algorithm.Analysis their Advantages and disadvantages.This paper also introduce some theory related to 3D surface reconstruction,for example Visualization, discrete vertex collection,convex hull,Voronoi Graphics and Delaunay Triangles,medial axis andε-sampling,Restricted Delaunay Triangles,the condition of Topological homeomorphism.Then introduce a algorithm for 3D surface reconstruction,and do the experiment for this algorithm.The algorithm's basic steps are as fllows:it is begin with the import of discrete vertex collection,first use incremental insertion method to create Tetrahedron network,it is also create topology between vertex collection,it is also finish the Delaunay Triangulation.Then,choose Restricted triangle using the angle imformation between the normal of vertex and the Delaunay triangle.Last,choose a seed triangle,and form this triangle,create the surface triangles network based on the adjacency triangles of extension edge.
By the end of this paper,It has a Summary of this paper's research,and proposed the problem to be resolved.
引文
[1]黄杏元、汤勤.《地理信息系统概论》,高等教育出版社,2001
[2]陈述彭,鲁学军,周成虎,地理信息系统导论.科学出版社,1999
[3]周培德,计算几何——算法设计与分析,清华大学出版社,2008
[4]朱庆,李逢春,张叶廷,一种改进的三维点集表面重建的区域生长算法,武汉大学学报信息科学版,2006,31(8)：667-670
[5]余小勇,李彩琴,3D空间离散点集三角划分的逐层收缩算法,西安邮电学院学报,2006,11(5)：83-85
[6]Amenta,Choi,Dey,Leekha, A simple algorithm for homeomorphic surface reconstruction
[7]Amenta,Bern, Surface reconstruction by Voronoi filtering. Discr. Comput. Geom,22,(1999),481-504
[8]徐永安,刘毓,沈玲玲,陈凌,大规模离散点集Delaunay三角剖分加点策略的分析,计算机工程与设计,2008,29(20)：5259-5261
[9]周儒荣,张丽艳,苏旭,周来水,海量散乱点的曲面重建算法研究,软件学报,2001,12(2)：249-255
[10]何金国,查红彬,基于BPLI从二维平行轮廓线重建三维表面的新方法,北京大学学报(自然科学版),2003,39(3)：399-411
[11]王永波,盛业华,田鹏,张凯,基于Delaunay规则的无组织采样点集表面重建方法,中国图像图形学报,2007,12(9)：1537-1543
[12]苏幸,黄临平,基于不规则四面体的三维离散数据地质建模算法,物探与化探,2008,32(2)：192-195
[13]李逢春,龚俊,王青,基于三维TIN的精细表面建模方法,计算机应用研究,2006,8：159-161
[14]苏幸,黄临平,林孝成,陈载林,基于四面体格网的三维地质体建模算法,煤田地质与勘探,2008,36(1)：5-13
[15]胡海彦,余旭出,方勇,基于随机增量式算法理论的地形建模方法研究,现代测绘,2007,30(4)：3-7
[16]顾泽元,周波,王洋,基于增量的三角剖分算法,黑龙江科技学院学报,2007,17(3)：238-242
[17]陈定造,空间散乱点集Delaunay三角剖分的算法优化及实现,硕士毕业论文
[18]刘雪娜,三维点集、(?)oronoi图的算法实现,计算机辅助工程,2006,15(1)：1-7
[19]郑顺义,苏国中,张祖勋,三维点集的自动表面重构算法,武汉大学学报信息科学版,2005,30(2)：154-157
[20]崔汉国,胡瑞安,金端峰,杨叔子,三维任意区域中点集的三角剖分算法,计算机辅助设计与图形学学报,1995,7(2)：103-108
[21]龚君芳,吴信才,刘修国,李圣文,三维四面体网格在煤储量计算中的应用,煤炭科学技术,2007,35(11)：33-35
[22]沈忱瑛,陈文亮,三维限定Delaunay四面体网格划分的算法,现代设计与先进制造技术,2009
[23]何小海,罗代升,陶青川,吴晓红,三维虚拟物体表面重建的研究,中国图像图形学报,2002,7(11)：1192-1197
[24]李立新,散乱点集曲面重建的理论、方法及应用研究,浙江大学博士学位论文
[25]王青,王融清,鲍虎军,彭群生,散乱数据点的增量快速曲面重建算法,软件学报,2000 11(9)：1221-1227
[26]梅中义,范玉青,一个基于格网前沿技术的三维实体四面体有限元网格剖分算法,计算机辅助工程,1999.3：34-39
[27]朱庆,李逢春,张叶廷,一种复杂轮廓线的真三维TIN算法,武汉大学学报信息科学版,200732(3)：259-262
[28]梁荣华,陈纯,潘志庚,张慧,一种面向三维点集的快速表面重构算法,中国图像图形学报,2008 8(1)：63-67
[29]孔娟华,郑江滨,一种三维离散点数据生成非结构四面体算法,计算机工程与科学,200931(1)：35-37
[30]胡海彦,方勇,余旭初,杨喆,一种随机增量式地形建模算法设计,测绘 科学与工程,2007 27(1)：10-14
[31]赵杰,程晓亮,于舒春,一种新的空间离散点集的直接剖分方法,机械工程师,200611：46-48
[32]温来祥,刘金义,一种支持三维Delaunay三角剖分与Voronoi图生成的数据结构,科学技术与工程,2010 10(12)：2974-2979
[33]刘爽,刘金义,陈鹏,用随机增量局部转换算法实现三维点集的Delaunay三角剖分,计算机应用,2003 23：111-113
[34]骆冠勇,曹洪,房营光,用逐点插入法生成Delaunay四面体自适应网格,计算力学学报,200724(6)：917-922
[35]郭际元,龚君芳,由三维离散数据生成四面体网格算法研究,地球科学——中国地质大学学报,2002,27(3)：271-273
[36]关文革,武强,贾丽萍,刘明海,约束数据域Delaunay四面体网格生成算法,华中科技大学学报(自然科学版),2005,33(5)：67-69
[37]欧军,黄地龙,逐点插入法在三维地质可视化系统中的应用研究,微计算机信息,200622(4)：230-242
[38]Hoppe H,DeRose T,,Duchamp T,Surface Reconstruction from Unorganized Points, Computer Graphics,1992,26(2):71-78
[39]Edelsbrunner H, Muche E P. Three-Dimensional Alpha Shapes [J]. ACM Trans on Graphics,1994,13(1):43—72
[40]Boissonnat J D. Geometric Structures for Three Dimensional Shape Representation [J]. ACM Trans on Graphics,1984,3(4):266—286
[41]Vehkamp R C. Boundaries Through Scattered Points of Unknown Density[J]. Graphical Models and Image Processing,1995,57(6): 441—452
[42]Amenta N, Bern M, Kamvysselis M. A New Voronoi—based Surface Reconstruction Algorithm [C]. SIGGRAPH'98, Orlando,1998
[43]Gopi M, Krishnan S, Silva C T. Surface Reconstruction Based on Lower Dimensional Localized Delaunay Triangulation[J]. Eurographics, 2000,19(3):467-478
[44]Bernardini F, Mittleman J, Rushmeier H, et al. The Ball-·pivoting Algorithm for Surface Recon struction[J]. IEEE Trans Visualization ComputGraphics 1999,5(4):349—359
[45]Lin Hongwei, Tai Chiewlan, Wang Guojin. A Mesh Reconstruction Algorithm Driven by Intrinsic Property of Point Cloud[J]. Computer-Aided Design,2004,36(Ⅰ):Ⅰ-9
[46]Edelsbrunner H, Shah N. Triangulating Topological Spaces[J]. International Journal of Computational Geometry and Applications,1997,7(4):365—378
[47]毋河海,龚健雅.地理信息系统空间数据结构与处理技术[M].北京：测绘出版社.1995,10(2)：35—87.
[48]Attene M, Spagnuolo M. Automatic Surface Reconshuction from Point Sets in Space[J]. Computer Graphics Forum,2000,19(3):457 · 465
[49]Mencl R. A Graph. based Approach to Surface Reconstruction [J]. Computer Graphics Forum,1995,14(3):445·456.
[50]Huang J, Menq C H. Combinatorial Manifold Mesh Reconstruction and Optimization from Unorganized Points with Arbitrary Topology [J]. Computer · Aided Design,2002,34(2):65·149
[51]Gopi M, Krishnan S, Silva C T. Surface Reconstruction Based on Lower Dimensional Localized Delaunay Triangulation[J]. Euragra。 phics,2000,19(3):467-478.
[2]陈述彭,鲁学军,周成虎,地理信息系统导论.科学出版社,1999
[3]周培德,计算几何——算法设计与分析,清华大学出版社,2008
[4]朱庆,李逢春,张叶廷,一种改进的三维点集表面重建的区域生长算法,武汉大学学报信息科学版,2006,31(8)：667-670
[5]余小勇,李彩琴,3D空间离散点集三角划分的逐层收缩算法,西安邮电学院学报,2006,11(5)：83-85
[6]Amenta,Choi,Dey,Leekha, A simple algorithm for homeomorphic surface reconstruction
[7]Amenta,Bern, Surface reconstruction by Voronoi filtering. Discr. Comput. Geom,22,(1999),481-504
[8]徐永安,刘毓,沈玲玲,陈凌,大规模离散点集Delaunay三角剖分加点策略的分析,计算机工程与设计,2008,29(20)：5259-5261
[9]周儒荣,张丽艳,苏旭,周来水,海量散乱点的曲面重建算法研究,软件学报,2001,12(2)：249-255
[10]何金国,查红彬,基于BPLI从二维平行轮廓线重建三维表面的新方法,北京大学学报(自然科学版),2003,39(3)：399-411
[11]王永波,盛业华,田鹏,张凯,基于Delaunay规则的无组织采样点集表面重建方法,中国图像图形学报,2007,12(9)：1537-1543
[12]苏幸,黄临平,基于不规则四面体的三维离散数据地质建模算法,物探与化探,2008,32(2)：192-195
[13]李逢春,龚俊,王青,基于三维TIN的精细表面建模方法,计算机应用研究,2006,8：159-161
[14]苏幸,黄临平,林孝成,陈载林,基于四面体格网的三维地质体建模算法,煤田地质与勘探,2008,36(1)：5-13
[15]胡海彦,余旭出,方勇,基于随机增量式算法理论的地形建模方法研究,现代测绘,2007,30(4)：3-7
[16]顾泽元,周波,王洋,基于增量的三角剖分算法,黑龙江科技学院学报,2007,17(3)：238-242
[17]陈定造,空间散乱点集Delaunay三角剖分的算法优化及实现,硕士毕业论文
[18]刘雪娜,三维点集、(?)oronoi图的算法实现,计算机辅助工程,2006,15(1)：1-7
[19]郑顺义,苏国中,张祖勋,三维点集的自动表面重构算法,武汉大学学报信息科学版,2005,30(2)：154-157
[20]崔汉国,胡瑞安,金端峰,杨叔子,三维任意区域中点集的三角剖分算法,计算机辅助设计与图形学学报,1995,7(2)：103-108
[21]龚君芳,吴信才,刘修国,李圣文,三维四面体网格在煤储量计算中的应用,煤炭科学技术,2007,35(11)：33-35
[22]沈忱瑛,陈文亮,三维限定Delaunay四面体网格划分的算法,现代设计与先进制造技术,2009
[23]何小海,罗代升,陶青川,吴晓红,三维虚拟物体表面重建的研究,中国图像图形学报,2002,7(11)：1192-1197
[24]李立新,散乱点集曲面重建的理论、方法及应用研究,浙江大学博士学位论文
[25]王青,王融清,鲍虎军,彭群生,散乱数据点的增量快速曲面重建算法,软件学报,2000 11(9)：1221-1227
[26]梅中义,范玉青,一个基于格网前沿技术的三维实体四面体有限元网格剖分算法,计算机辅助工程,1999.3：34-39
[27]朱庆,李逢春,张叶廷,一种复杂轮廓线的真三维TIN算法,武汉大学学报信息科学版,200732(3)：259-262
[28]梁荣华,陈纯,潘志庚,张慧,一种面向三维点集的快速表面重构算法,中国图像图形学报,2008 8(1)：63-67
[29]孔娟华,郑江滨,一种三维离散点数据生成非结构四面体算法,计算机工程与科学,200931(1)：35-37
[30]胡海彦,方勇,余旭初,杨喆,一种随机增量式地形建模算法设计,测绘 科学与工程,2007 27(1)：10-14
[31]赵杰,程晓亮,于舒春,一种新的空间离散点集的直接剖分方法,机械工程师,200611：46-48
[32]温来祥,刘金义,一种支持三维Delaunay三角剖分与Voronoi图生成的数据结构,科学技术与工程,2010 10(12)：2974-2979
[33]刘爽,刘金义,陈鹏,用随机增量局部转换算法实现三维点集的Delaunay三角剖分,计算机应用,2003 23：111-113
[34]骆冠勇,曹洪,房营光,用逐点插入法生成Delaunay四面体自适应网格,计算力学学报,200724(6)：917-922
[35]郭际元,龚君芳,由三维离散数据生成四面体网格算法研究,地球科学——中国地质大学学报,2002,27(3)：271-273
[36]关文革,武强,贾丽萍,刘明海,约束数据域Delaunay四面体网格生成算法,华中科技大学学报(自然科学版),2005,33(5)：67-69
[37]欧军,黄地龙,逐点插入法在三维地质可视化系统中的应用研究,微计算机信息,200622(4)：230-242
[38]Hoppe H,DeRose T,,Duchamp T,Surface Reconstruction from Unorganized Points, Computer Graphics,1992,26(2):71-78
[39]Edelsbrunner H, Muche E P. Three-Dimensional Alpha Shapes [J]. ACM Trans on Graphics,1994,13(1):43—72
[40]Boissonnat J D. Geometric Structures for Three Dimensional Shape Representation [J]. ACM Trans on Graphics,1984,3(4):266—286
[41]Vehkamp R C. Boundaries Through Scattered Points of Unknown Density[J]. Graphical Models and Image Processing,1995,57(6): 441—452
[42]Amenta N, Bern M, Kamvysselis M. A New Voronoi—based Surface Reconstruction Algorithm [C]. SIGGRAPH'98, Orlando,1998
[43]Gopi M, Krishnan S, Silva C T. Surface Reconstruction Based on Lower Dimensional Localized Delaunay Triangulation[J]. Eurographics, 2000,19(3):467-478
[44]Bernardini F, Mittleman J, Rushmeier H, et al. The Ball-·pivoting Algorithm for Surface Recon struction[J]. IEEE Trans Visualization ComputGraphics 1999,5(4):349—359
[45]Lin Hongwei, Tai Chiewlan, Wang Guojin. A Mesh Reconstruction Algorithm Driven by Intrinsic Property of Point Cloud[J]. Computer-Aided Design,2004,36(Ⅰ):Ⅰ-9
[46]Edelsbrunner H, Shah N. Triangulating Topological Spaces[J]. International Journal of Computational Geometry and Applications,1997,7(4):365—378
[47]毋河海,龚健雅.地理信息系统空间数据结构与处理技术[M].北京：测绘出版社.1995,10(2)：35—87.
[48]Attene M, Spagnuolo M. Automatic Surface Reconshuction from Point Sets in Space[J]. Computer Graphics Forum,2000,19(3):457 · 465
[49]Mencl R. A Graph. based Approach to Surface Reconstruction [J]. Computer Graphics Forum,1995,14(3):445·456.
[50]Huang J, Menq C H. Combinatorial Manifold Mesh Reconstruction and Optimization from Unorganized Points with Arbitrary Topology [J]. Computer · Aided Design,2002,34(2):65·149
[51]Gopi M, Krishnan S, Silva C T. Surface Reconstruction Based on Lower Dimensional Localized Delaunay Triangulation[J]. Euragra。 phics,2000,19(3):467-478.