基于三维狄洛尼三角网的曲面重建算法

doi:10.11947/j.AGCS.2018.20170490

测绘学报 ›› 2018, Vol. 47 ›› Issue (2): 281-290.doi: 10.11947/j.AGCS.2018.20170490

• • 上一篇

基于三维狄洛尼三角网的曲面重建算法

贾军辉^1,2, 黄明^1,2,3, 刘祥磊¹

1. 北京建筑大学测绘与城市空间信息学院, 北京 100044;
2. 北京市建筑遗产精细重构与健康监测重点实验室, 北京 100044;
3. 代表性建筑与古建筑数据库教育部工程中心, 北京 100044

收稿日期:2017-08-31 修回日期:2017-12-05 出版日期:2018-02-20 发布日期:2018-03-02
通讯作者: 黄明 E-mail:huangming@bucea.edu.cn
作者简介:贾军辉(1993-),男,硕士生,研究方向为三维建模技术与应用、曲面重建理论与算法。E-mail:jjhlaoga@foxmail.com
基金资助:
北京市教育委员会科技计划一般项目（2016子项目49）；国家自然科学基金（41601409；41501494）；北京市自然科学基金（8172016）；北京市科委2017年度创新基地培育与发展专项（Z171100002217075）

Surface Reconstruction Algorithm Based on 3D Delaunay Triangulation

JIA Junhui^1,2, HUANG Ming^1,2,3, LIU Xianglei¹

1. School of Geomatics and Urban Spatial Information, Beijing University of Civil Engineering and Architecture, Beijing 100044, China;
2. Beijing Key Laboratory for Architectural Heritage Fine Reconstruction & Health Monitoring, Beijing 100044, China;
3. Engineering Research Center of Representative Building and Architectural Heritage Database, Ministry of Education, Beijing 100044, China

Received:2017-08-31 Revised:2017-12-05 Online:2018-02-20 Published:2018-03-02
Supported by:
The General Project of Science and Technology Program of Beijing Municipal Commission of Education (2016 sub project No. 49);The National Natural Science Foundation of China (Nos. 41601409;41501494);Natural Science Foundation of Beijing (No. 8172016);2017 Annual Innovation Base Breeding and Development of Beijing Municipal Science and Technology Commission (No. Z171100002217075)

摘要/Abstract

摘要： 随着三维激光扫描技术应用领域的不断拓展，对点云数据三维建模的需求越来越迫切。曲面重建技术作为三维建模的核心技术之一，在逆向工程、计算机视觉、计算机制图以及虚拟现实等技术领域都有着非常广泛的应用前景。本文提出一种基于三维狄洛尼三角网的曲面重建算法，其本质是一种结合了曲面生长算法思想的贪心算法，即在一定约束条件下，按照最优三角形选择标准，算法从预先构建好的三维狄洛尼三角网中，逐个筛选出最优三角形添加到生长曲面上，最终输出由一系列显式三角形所组成的流形曲面。这种方法对比目前主流的隐式曲面重建算法具有参数依赖性较小、不需要计算法线等优点，并且能够重建地形扫描、建筑物扫描和精细化扫描的点云模型。利用此算法对多种点云模型进行曲面重建试验，结果表明该算法生成曲面质量好、重建效率高、实用性强，能够很好地应用于三维建模领域。

关键词: 三维建模, 三维狄洛尼三角网, 贪心算法, 曲面重建

Abstract: With the development of 3D laser scanning technology,the demand for 3D modeling of point cloud data is increasing.As one of the core technologies of 3D modeling,surface reconstruction technology has an extremely widespread application prospect in reverse engineering,computer vision,computer graphics and virtual reality technology.This paper presents a surface reconstruction algorithm based on three-dimensional Delaunay triangulation,it is essentially a greedy algorithm,and combined with the idea of surface region growing algorithm.Manifold surface composed of a selection of explicit triangles can be reconstructed by this algorithm under a certain topological limit,the best triangles are selected from the preconstructed 3D Delaunay triangulation according to the appropriate triangle selection criteria by this algorithm,and added to the growing surface one by one.Compared with the current mainstream implicit surface reconstruction algorithm,this method has the advantages of less parameter dependency and no need to calculate normal line,and it can reconstruct the point cloud model of terrain scanning,building scanning and fine scanning.Using this algorithm to reconstruct the surface of a variety of point cloud models,experimental results show that the quality of the surface generated by the algorithm is choiceness,and the efficiency of reconstruction is faster,this surface reconstruction algorithm has stronger practicability and can be better applied in the field of 3D modeling.

Key words: 3D modeling, 3D Delaunay triangulation, greedy algorithm, surface reconstruction

中图分类号:

P237

贾军辉, 黄明, 刘祥磊. 基于三维狄洛尼三角网的曲面重建算法[J]. 测绘学报, 2018, 47(2): 281-290.

JIA Junhui, HUANG Ming, LIU Xianglei. Surface Reconstruction Algorithm Based on 3D Delaunay Triangulation[J]. Acta Geodaetica et Cartographica Sinica, 2018, 47(2): 281-290.

参考文献

[1] BOISSONNAT J D. Geometric Structures for Three-dimensional Shape Representation[J]. ACM Transactions on Graphics (TOG), 1984, 3(4):266-286.
[2] TURK G, O'BRIEN J F. Shape Transformation Using Variational Implicit Functions[C]//Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques. New York:ACM, 1999:335-342.
[3] TURK G, O'BRIEN J F. Modelling with Implicit Surfaces that Interpolate[J]. ACM Transactions on Graphics (TOG), 2002, 21(4):855-873.
[4] ZHAO Hongkai, OSHER S, MERRIMAN B, et al. Implicit and Nonparametric Shape Reconstruction from Unorganized Data Using a Variational Level Set Method[J]. Computer Vision and Image Understanding, 2000, 80(3):295-314.
[5] PARK S H, LEE S S, KIM J H. A Surface Reconstruction Algorithm Using Weighted Alpha Shapes[M]//WANG Lipo, JIN Yaochu. Fuzzy Systems and Knowledge Discovery. Berlin:Springer, 2005:1141-1150.
[6] BOISSONNAT J D, CAZALS F. Smooth Surface Reconstruction via Natural Neighbour Interpolation of Distance Functions[J]. Computational Geometry, 2002, 22(1-3):185-203.
[7] MEDIONI G, LEE M S, TANG C K. A Computational Framework for Segmentation and Grouping[M]. New York, NY, USA:Elsevier, 2000:243-253.
[8] DIGNE J. An Implementation and Parallelization of the Scale Space Meshing Algorithm[J]. Image Processing On Line, 2015, 5:282-295.
[9] LHUILLIER M. Overview of Shelling for 2-manifold Surface Reconstruction Based on 3D Delaunay Triangulation[J]. Journal of Mathematical Imaging and Vision, 2017, 59(2):318-340.
[10] MERRY B, GAIN J, MARAIS P. Moving Least-squares Reconstruction of Large Models with GPUs[J]. IEEE Transactions on Visualization and Computer Graphics, 2014, 20(2):249-261.
[11] KAZHDAN M, BOLITHO M, HOPPE H. Poisson Surface Reconstruction[C]//Proceedings of the 4th Eurographics Symposium on Geometry Processing. Cagliari, Sardinia, Italy:Eurographics Association, 2006:61-70.
[12] KAZHDAN M, HOPPE H. Screened Poisson Surface Reconstruction[J]. ACM Transactions on Graphics (TOG), 2013, 32(3):29.
[13] BOLITHO M, KAZHDAN M, BURNS R, et al. Multilevel Streaming for Out-of-core Surface Reconstruction[C]//Proceedings of the 5th Eurographics Symposium on Geometry Processing. Barcelona, Spain:Eurographics Association, 2007:69-78.
[14] LIU Shengjun, WANG C C L, BRUNNETT G, et al. A Closed-form Formulation of HRBF-based Surface Reconstruction by Approximate Solution[J]. Computer-aided Design, 2016, 78:147-157.
[15] YANG Long, YAN Qing'an, XIAO Chunxia. Shape-Controllable Geometry Completion for Point Cloud Models[J]. The Visual Computer:International Journal of Computer Graphics, 2017, 33(3):385-398.
[16] LORENSEN W E, CLINE H E. Marching Cubes:A High Resolution 3D Surface Construction Algorithm[J]. ACM SIGGRAPH Computer Graphics, 1987, 21(4):163-169.
[17] SCHAEFER S, JU Tao, WARREN J. Manifold Dual Contouring[J]. IEEE Transactions on Visualization and Computer Graphics, 2007, 13(3):610-619.
[18] EDELSBRUNNER H. Surface Reconstruction by Wrapping Finite Sets in Space[M]//ARONOV B, BASU S, PACH J, et al. Discrete and Computational Geometry. Berlin:Springer, 2003:379-404.
[19] DIGNE J, MOREL J M, SOUZANI C M, et al. Scale Space Meshing of Raw Data Point Sets[J]. Computer Graphics Forum, 2011, 30(6):1630-1642.
[20] FUHRMANN S, GOESELE M. Floating Scale Surface Reconstruction[J]. ACM Transactions on Graphics (TOG), 2014, 33(4):46.
[21] AN Yi, ZHAO Peng, LI Zhuohan, et al. Self-adaptive Polygon Mesh Reconstruction Based on Ball-pivoting Algorithm[J]. International Journal of Computer Applications in Technology, 2016, 54(1):51-60.
[22] BOISSONNAT J D, CAZALS F. Smooth Surface Reconstruction via Natural Neighbour Interpolation of Distance Functions[C]//Proceedings of the 16th Annual Symposium on Computational Geometry. Hong Kong, China:ACM, 2000:223-232.
[23] COHEN-STEINER D, DA F. A Greedy Delaunay-based Surface Reconstruction Algorithm[J]. The Visual Computer:International Journal of Computer Graphics, 2004, 20(1):4-16.
[24] KUO Chuanchu, YAU H T. A Delaunay-based Region-growing Approach to Surface Reconstruction from Unorganized Points[J]. Computer-Aided Design, 2005, 37(8):825-835.
[25] TEILLAUD M. Three Dimensional Triangulations in CGAL[C]//Abstracts 15th European Workshop Computational Geometry.[S.l.]:INRIA Sophia-Antipolis, 1999:175-158.
[26] SI Hang. Three Dimensional Boundary Conforming Delaunay Mesh Generation[D]. Berlin:Technische Universität Berlin, 2008.
[27] PARK M K, LEE S J, JANG I Y, et al. Feature-aware Filtering for Point-set Surface Denoising[J]. Computers & Graphics, 2013, 37(6):589-595.
[28] BOULCH A, MARLET R. Fast and Robust Normal Estimation for Point Clouds with Sharp Features[J]. Computer Graphics Forum, 2012, 31(5):1765-1774.

基于三维狄洛尼三角网的曲面重建算法

Surface Reconstruction Algorithm Based on 3D Delaunay Triangulation

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

本文评价

[1]	李卉,钟成,黄先锋,李德仁. 集成激光雷达数据和遥感影像的立交桥自动检测方法[J]. 测绘学报, 2012, 41(3): 0-416.
[2]	孙敏,胡争. 基于向量匹配的稀疏深度图生成算法[J]. 测绘学报, 2011, 40(1): 90-95.
[3]	孙中昶; 卢秀山; 田茂义. 矿山巷道三维建模算法研究及实现[J]. 测绘学报, 2009, 38(3): 0-201.