Meshless Voronoi on the GPU

Nicolas Ray 1 Dmitry Sokolov 1 Sylvain Lefebvre 2 Bruno Lévy 1
1 ALICE - Geometry and Lighting
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
2 MFX - Matter from Graphics
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : We propose a GPU algorithm that computes a 3D Voronoi diagram. Our algorithm is tailored for applications that solely make use of the geometry of the Voronoi cells, such as Lloyd's relaxation used in meshing, or some numerical schemes used in fluid simulations and astrophysics. Since these applications only require the geometry of the Voronoi cells, they do not need the combinatorial mesh data structure computed by the classical algorithms (Bowyer-Watson). Thus, by exploiting the specific spatial distribution of the point-sets used in this type of applications, our algorithm computes each cell independently, in parallel, based on its nearest neighbors. In addition, we show how to compute integrals over the Voronoi cells by decomposing them on the fly into tetrahedra, without needing to compute any global combinatorial information. The advantages of our algorithm is that it is fast, very simple to implement, has constant memory usage per thread and does not need any synchronization primitive. These specificities make it particularly efficient on the GPU: it gains one order of magnitude as compared to the fastest state-of-the-art multi-core CPU implementations. To ease the reproducibility of our results, the full documented source code is included in the supplemental material.
Type de document :
Article dans une revue
ACM Transactions on Graphics, Association for Computing Machinery, In press, 37, 〈10.1145/3272127.3275092〉
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01927559
Contributeur : Dmitry Sokolov <>
Soumis le : mercredi 21 novembre 2018 - 13:35:51
Dernière modification le : mardi 18 décembre 2018 - 16:30:02

Fichier

voroGPU.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Nicolas Ray, Dmitry Sokolov, Sylvain Lefebvre, Bruno Lévy. Meshless Voronoi on the GPU. ACM Transactions on Graphics, Association for Computing Machinery, In press, 37, 〈10.1145/3272127.3275092〉. 〈hal-01927559〉

Partager

Métriques

Consultations de la notice

402

Téléchargements de fichiers

319