carrier image

Toward one billion tetrahedra per minute

Marot, Célestin, Jeanne Pellerin, Jonathan Lambrechts, Jean-François Remacle

Research Notes, 26th International Meshing Roundtable, Sandia National Laboratories, September 18-21 2017


26th International Meshing Roundtable
Barcelona, Spain
September 18-21, 2017

Célestin Marot, Université catholique de Louvain, BE,
Jeanne Pellerin, Université catholique de Louvain, BE,
Jonathan Lambrechts, Université catholique de Louvain, BE,
Jean-François Remacle, Université catholique de Louvain, BE,

Research Note Abstract
In this research note, we propose a new scalable parallelization scheme to generate the Delaunay tetrahedrization of a given set of points.Our first contribution is a very efficient serial implementation. From this base we developed a multi-threaded version of the Delaunay kernel that concurrently insert points into the tetrahedrization. We use the Hilbert curve coordinates to distribute the work between threads. Our strategy is free from heavy synchronization overhead. The key idea to manage conflicts is to modify the partitions by enlarging the space filled by the Hilbert curve. Our implementation is very simple and outperforms previous existing methods.

Download Full Paper (PDF)

Contact author(s) or publisher for availability and copyright information on above referenced article