An adaptive and rapid 3D Delaunay triangulation for randomly distributed point cloud data
- PDF / 4,085,584 Bytes
- 25 Pages / 595.276 x 790.866 pts Page_size
- 5 Downloads / 221 Views
ORIGINAL ARTICLE
An adaptive and rapid 3D Delaunay triangulation for randomly distributed point cloud data Tianyun Su1,2,3 · Wen Wang1 · Haixing Liu1,2,4 · Zhendong Liu1,3 · Xinfang Li1,2 · Zhen Jia1 · Lin Zhou1 · Zhuanling Song1 · Ming Ding1 · Aiju Cui1 Accepted: 27 October 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract Incremental algorithms are among the most popular approaches for Delaunay triangulation, and the point insertion sequence has a substantial impact on the amount of work needed to construct Delaunay triangulations in incremental algorithm triangulation. In this paper, 2D adaptive Hilbert curve insertion, including the method of dividing 3D multi-grids and adjusting the 3D adaptive Hilbert curve to avoid the “jump” phenomenon, is extended to 3D Delaunay triangulation. In addition, on the basis of adaptive Hilbert curve insertion, we continue to optimize the addition of control points by selecting control points in every order and every grid level. As a result, the number of conflicting elongated tetrahedra that have to be created and deleted multiple times and the number of search steps for positioning inserted points can both be reduced. Lastly, a new comparison method is used in the point location process to solve the precision problem in 3D Delaunay triangulation. As shown by detailed experiments and analysis, compared with previous adaptive Hilbert curve insertion, CGAL, regular grid insertion, multi-grid insertion and random insertion, the proposed 3D Delaunay triangulation is the most efficient for both artificial and real surface sampling point sets. Keywords Delaunay triangulation · Point cloud data · Multi-grid · Incremental algorithm · Adaptive Hilbert curve
1 Introduction The 3D Delaunay triangulation has a sound geometrical concept and strong theoretical basis that make it ubiquitous in various domains: data visualization and imaging [39], mesh generation [27], surface reconstruction from 3D scanElectronic supplementary material The online version of this article (https://doi.org/10.1007/s00371-020-02011-3) contains supplementary material, which is available to authorized users.
B
Wen Wang [email protected]
1
Marine Data and Information Center, The First Institute of Oceanography, MNR, Qingdao, China
2
Laboratory for Regional Oceanography and Numerical Modeling, Pilot National Laboratory for Marine Science and Technology, Qingdao, China
3
National Engineering Laboratory for Integrated Aero-Space-Ground-Ocean Big Data Application Technology, Xi’an, China
4
Key Laboratory of Marine Science and Numerical Modeling, Ministry of Natural Resources, Qingdao, China
ner point clouds [47], terrain modelling [46], etc. Delaunay triangulation can be divided into several categories, including divide-and-conquer algorithms [25], incremental insertion algorithms [24], triangle expanding algorithms [21], sweep line algorithms [17], gift wrapping algorithms [16] and convex hull-based algorithms [2]. Among them, incremental insertion algorithms are effective and si
Data Loading...
