Surface Reconstruction Algorithm Based on 3D Delaunay Triangulation

doi:10.11947/j.AGCS.2018.20170490

Acta Geodaetica et Cartographica Sinica ›› 2018, Vol. 47 ›› Issue (2): 281-290.doi: 10.11947/j.AGCS.2018.20170490

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

CLC Number:

P237

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.

References

[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

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 1

Recommended Articles

Metrics

Comments