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