Parallel Computing for 3D Delaunay Triangulation of Non-Uniform Cloud Points

Abstract

3D acquisition technologies have favored the development of geometric modelling of 3D objects based on data from their digitization. The aim is to use the Delaunay triangulation (DT) approach to generate a digital model of the external surfaces of a physical object from point clouds. The generation of a DT from a non-uniform point clouds is an arduous and time-consuming task. Moreover, point clouds are very large and computationally intensive, which increases processing time and costs, especially if only one processor is used. The fastest DT algorithm is based on the divide-and-conquer, which is generally designed to be used for parallelism. This algorithm is carried out in two steps. The first step recursively partitions the points set into sub-regions; each is assigned to a processor. Independently, these regions are further triangulated simultaneously. The second step merges the sub-regions into the final mesh, which is applied in the reverse order of points set partitioning. This work deals with the generation of a 3D triangulation from any point cloud, which is partitioned to several sub-points using cells. Independently, the sub points are further triangulated simultaneously by parallelizing the calculations on several processors. After that, an allocated area of each cell is determined, as well as the strategy for the fusion. Finally, this solution is tested and validated through many unstructured point clouds.

Keywords

• Cloud of Points
• Cells
• 3D Delaunay Triangulation
• Merging
• Parallel Computing

References

1. Renata LME do Rego and Aluizio FR Araujo. A surface reconstruction method based on self-organizing maps and intrinsic Delaunay triangulation. In The 2010 International Joint Conference on Neural Networks (IJCNN), pages 1–8. IEEE, 2010.
2. Michael Kazhdan and Hugues Hoppe. Screened Poisson surface reconstruction. ACM Transactions on Graphics (ToG), 32(3):1–13, 2013.
3. Kavita Khanna and Navin Rajpal. Survey of curve and surface reconstruction algorithms from a set of unorganized points. In Proceedings of the Third International Conference on Soft Computing for Problem Solving: SocProS 2013, Volume 1, pages 451–458. Springer, 2014.
4. Charles L Lawson. Transforming triangulations. Discrete Mathematics, 3(4):365–372, 1972.
5. NA Golias and RW Dutton. Delaunay triangulation and 3D adaptive mesh generation. Finite Elements in Analysis and Design, 25(3-4):331–341, 1997.
6. L Yonghe, F Jinming, and S Yuehong. A simple sweep-line Delaunay triangulation algorithm. J. Algorithms Optim, 1:30–38, 2013.
7. Peter Su and Robert L Scot Drysdale. A comparison of sequential Delaunay triangulation algorithms. In Proceedings of the Eleventh Annual Symposium on Computational Geometry, pages 61–70, 1995.
8. Michael Ian Shamos and Dan Hoey. Closest-point problems. In 16th Annual Symposium on Foundations of Computer Science (SFCS 1975), pages 151–162. IEEE, 1975.

9. Jyrki Katajainen and Markku Koppinen. Constructing Delaunay triangulations by merging buckets in quad tree order. Fundamenta Informaticae, 11(3):275–288, 1988.
10. Paolo Cignoni, Claudio Montani, and Roberto Scopigno. DeWall: A fast divide and conquer Delaunay triangulation algorithm in 3D. Computer-Aided Design, 30(5):333–341, 1998.
11. Min-Bin Chen, Tyng-Ruey Chuang, and Jan-Jan Wu. Efficient parallel implementations of near Delaunay triangulation with High Performance Fortran. Concurrency and Computation: Practice and Experience, 16(12):1143–1159, 2004.
12. Min-Bin Chen. A parallel 3D Delaunay triangulation method. In 2011 IEEE Ninth International Symposium on Parallel and Distributed Processing with Applications, pages 52–56. IEEE, 2011.
13. Huayi Wu, Xuefeng Guan, and Jianya Gong. ParaStream: A parallel streaming Delaunay triangulation algorithm for LiDAR points on multicore architectures. Computers & Geosciences, 37(9):1355–1363, 2011.
14. SH Lo. Parallel Delaunay triangulation in three dimensions. Computer Methods in Applied Mechanics and Engineering, 237:88–106, 2012.
15. Tchantchane Zahida, Khadidja Bouhadja, Ouahiba Azouaoui, and Nassira Ghoualmi-Zine. Enhanced unstructured points cloud subdivision applied for parallel Delaunay triangulation. Cluster Computing, 26(3):1877–1889, 2023.
16. Wenzhou Wu, Yikang Rui, Fenzhen Su, Liang Cheng, and Jiechen Wang. Novel parallel algorithm for constructing Delaunay triangulation based on a twofold-divide-and-conquer scheme. GIScience & Remote Sensing, 51(5):537–554, 2014.
17. Min-Bin Chen. The merge phase of parallel divide-and-conquer scheme for 3D Delaunay triangulation. In International Symposium on Parallel and Distributed Processing with Applications, pages 224–230. IEEE, 2010.