One machine, one minute, three billion tetrahedra

Celestin Marot, Jeanne Pellerin, Jean-Francois Remacle
Universite catholique de Louvain, iMMC, Avenue Georges Lemaitre 4, bte L4.05.02, 1348 Louvain-la-Neuve, Belgium
arXiv:1805.08831 [cs.CG], (22 May 2018)


   title={One machine, one minute, three billion tetrahedra},

   author={Marot, Celestin and Pellerin, Jeanne and Remacle, Jean-Francois},






This paper presents a new scalable parallelization scheme to generate the 3D Delaunay triangulation of a given set of points. Our first contribution is an efficient serial implementation of the incremental Delaunay insertion algorithm. A simple dedicated data structure and a number of improvements in the insertion algorithm have permitted to accelerate by a factor three reference implementations. Our second contribution is a multi-threaded version of the Delaunay kernel able to concurrently insert vertices. Moore curve coordinates are used to partition the point set, avoiding so heavy synchronization overheads. Conflicts are managed by modification of the partition with a simple rescaling of the space-filling curve. The performances of our implementation have been measured on three different processors, Intel core-i7, Intel Xeon Phi and AMD EPYC, on which we have been able to compute 3 billion tetrahedra in 53 seconds. This corresponds to a generation rate of over 55 million tetrahedra per second which is, to our best knowledge, three times the rate reached by the current fastest implementation. It is finally shown how this very efficient parallel Delaunay triangulation can be integrated in a Delaunay refinement mesh generator taking as input the boundary of the domain to mesh.
Rating: 1.0/5. From 1 vote.
Please wait...

* * *

* * *

Featured events

Hida Takayama, Japan

The Third International Workshop on GPU Computing and AI (GCA), 2018

Nagoya University, Japan

The 5th International Conference on Power and Energy Systems Engineering (CPESE), 2018

MediaCityUK, Salford Quays, Greater Manchester, England

The 10th International Conference on Information Management and Engineering (ICIME), 2018

No. 1037, Luoyu Road, Hongshan District, Wuhan, China

The 4th International Conference on Control Science and Systems Engineering (ICCSSE), 2018

Nanyang Executive Centre in Nanyang Technological University, Singapore

The 2018 International Conference on Cloud Computing and Internet of Things (CCIOT’18), 2018

HGPU group © 2010-2018 hgpu.org

All rights belong to the respective authors

Contact us: