Journal Article

An adaptive and rapid 3D Delaunay triangulation for randomly distributed point cloud data

Liu, Haixing, Ding, Ming, Zhou, Lin, Cui, Aiju, Su, Tianyun, Wang, Wen, Liu, Zhendong, Song, Zhuanling, Li, Xinfang, Jia, Zhen

2022

Overview

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.

• Publisher: Springer Berlin Heidelberg,Springer Nature B.V
• Subject: Algorithms / Artificial Intelligence / Computer Graphics / Computer peripherals / Computer Science / Construction / Delaunay triangulation / Efficiency / Hilbert curve / Image Processing and Computer Vision / Insertion / Original Article / Tetrahedra / Three dimensional models