“Meshless voronoi on the GPU”
Conference:
Type(s):
Title:
- Meshless voronoi on the GPU
Session/Category Title: Meshing
Presenter(s)/Author(s):
Moderator(s):
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.
References:
1. Mridul Aanjaneya, Ming Gao, Haixiang Liu, Christopher Batty, and Eftychios Sifakis. 2017. Power diagrams and sparse paged grids for high resolution adaptive liquids. ACM Trans. Graph. 36, 4 (2017), 140:1–140:12. Google ScholarDigital Library
2. Shostko Alexander and Löhner Rainald. 1995. Three-dimensional parallel unstructured grid generation. Internat. J. Numer. Methods Engrg. 38, 6 (1995), 905–925.Google ScholarCross Ref
3. Nina Amenta, Sunghee Choi, Tamal K. Dey, and N. Leekha. 2002. A Simple Algorithm for Homeomorphic Surface Reconstruction. Int. J. Comput. Geometry Appl. 12, 1–2 (2002), 125–141.Google ScholarCross Ref
4. Nina Amenta, Sunghee Choi, and Günter Rote. 2003. Incremental constructions con BRIO. In Proceedings of the 19th ACM Symposium on Computational Geometry, San Diego, CA, USA, June 8–10, 2003. 211–219. Google ScholarDigital Library
5. Ricardo J. Barrientos, Fabricio Millaguir, José L. Sánchez, and Enrique Arias. 2017. GPU-based Exhaustive Algorithms Processing kNN Queries. J. Supercomput. 73, 10 (Oct. 2017), 4611–4634. Google ScholarDigital Library
6. Vincente H.F. Batista, David L. Millman, Sylvain Pion, and Johannes Singler. 2010. Parallel geometric algorithms for multi-core computers. Internat. J. Numer. Methods Engrg. 43, 8 (2010), 663–677. Google ScholarDigital Library
7. Dobrina Boltcheva and Bruno Lévy. 2017. Surface reconstruction by computing restricted Voronoi cells in parallel. Computer-Aided Design 90 (2017), 123–134.Google ScholarDigital Library
8. Adrian Bowyer. 1981. Computing Dirichlet Tessellations. Comput. J. 24, 2 (1981), 162–166.Google ScholarCross Ref
9. Y. Brenier, U. Frisch, M. Henon, G. Loeper, S. Matarrese, R. Mohayaee, and A. Sobolevskii. 2003. Reconstruction of the early Universe as a convex optimization problem. arXiv (September 2003). https://arxiv.org/abs/astro-ph/0304214 arXiv:astro-ph/0304214v3.Google Scholar
10. Tyson Brochu, Christopher Batty, and Robert Bridson. 2010. Matching fluid simulation elements to surface geometry and topology. ACM Trans. Graph. 29, 4 (2010), 47:1–47:9. Google ScholarDigital Library
11. Thanh-Tung Cao. 2014. Fundamental Computational Geometry on the GPU.Google Scholar
12. Thanh-Tung Cao, Ashwin Nanjappa, Mingcen Gao, and Tiow Seng Tan. 2014. A GPU accelerated algorithm for 3D Delaunay triangulation. In Symposium on Interactive 3D Graphics and Games, I3D ’14, San Francisco, CA, USA – March 14–16, 2014. 47–54. Google ScholarDigital Library
13. Nicolas Cuntz and Andreas Kolb. 2007. Fast Hierarchical 3D Distance Transforms on the GPU. In EG Short Papers, Paolo Cignoni and Jiri Sochor (Eds.). The Eurographics Association.Google Scholar
14. H. L. De Cougny and M. S Shephard. 1999. Parallel refinement and coarsening of tetrahedral meshes. Internat. J. Numer. Methods Engrg. 46, 7 (1999), 1101–1125.Google ScholarCross Ref
15. Fernando de Goes, Corentin Wallez, Jin Huang, Dmitry Pavlov, and Mathieu Desbrun. 2015. Power particles: an incompressible fluid solver based on power diagrams. ACM Trans. Graph. 34, 4 (2015), 50:1–50:11. Google ScholarDigital Library
16. Christophe Delage and Olivier Devillers. 2018. Spatial Sorting. In CGAL User and Reference Manual (4.12.1 ed.). CGAL Editorial Board. https://doc.cgal.org/4.12.1/Manual/packages.html#PkgSpatialSortingSummaryGoogle Scholar
17. Qiang Du, Vance Faber, and Max Gunzburger. 1999. Centroidal Voronoi Tessellations: Applications and Algorithms. SIAM Rev. 41, 4 (Dec. 1999), 637–676. Google ScholarDigital Library
18. Herbert Edelsbrunner and Ernst P. Mücke. 1994. Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms. CoRR abs/math/9410209 (1994). arXiv:math/9410209 http://arxiv.org/abs/math/9410209Google Scholar
19. Yun Fei, Guodong Rong, Bin Wang, and Wenping Wang. 2014. Parallel L-BFGS-B algorithm on GPU. Computers & Graphics 40 (2014), 1 — 9. Google ScholarDigital Library
20. Ian Fischer and Craig Gotsman. 2006. Fast Approximation of High-Order Voronoi Diagrams and Distance Transforms on the GPU. J. Graphics Tools 11 (2006), 39–60.Google ScholarCross Ref
21. Thomas O. Gallouët and Quentin Mérigot. 2017. A Lagrangian Scheme à la Brenier for the Incompressible Euler Equations. Foundations of Computational Mathematics (23 May 2017).Google Scholar
22. V. Garcia, E. Debreuve, and M. Barlaud. 2008. Fast k nearest neighbor search using GPU. In 2008 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops. 1–6.Google Scholar
23. V. Garcia, E. Debreuve, F. Nielsen, and M. Barlaud. 2010. K-nearest neighbor search: Fast GPU-based implementations and application to high-dimensional feature matching. In 2010 IEEE International Conference on Image Processing. 3757–3760.Google Scholar
24. R.E. González. 2016. PARAVT: Parallel Voronoi tessellation code. Astronomy and Computing 17 (2016), 80 — 85.Google ScholarCross Ref
25. RC Hoetzlein. 2014. Fast fixed-radius nearest neighbors: interactive million-particle fluids. In GPU Technology Conference. 18.Google Scholar
26. Kenneth E. Hoff, III, John Keyser, Ming Lin, Dinesh Manocha, and Tim Culver. 1999. Fast Computation of Generalized Voronoi Diagrams Using Graphics Hardware. In Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’99). ACM Press/Addison-Wesley Publishing Co., New York, NY, USA, 277–286. Google ScholarDigital Library
27. project ALICE-GRAPHYS Inria. 2018. Geogram: a programming library of geometric algorithms. http://alice.loria.fr/software/geogram/doc/html/index.html.Google Scholar
28. Bruno Lévy. 2016. Robustness and efficiency of geometric programs: The Predicate Construction Kit (PCK). Computer-Aided Design 72 (2016), 3–12. Google ScholarDigital Library
29. Bruno Lévy and Nicolas Bonneel. 2013. Variational Anisotropic Surface Meshing with Voronoi Parallel Linear Enumeration. In Proceedings of the 21st International Meshing Roundtable, Xiangmin Jiao and Jean-Christophe Weill (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 349–366.Google ScholarCross Ref
30. Bruno Lévy and Yang Liu. 2010. Lp Centroidal Voronoi Tessellation and its applications. ACM Trans. Graph. 29, 4 (2010), 119:1–119:11. Google ScholarDigital Library
31. Shengren Li and Nina Amenta. 2015. Brute-Force k-Nearest Neighbors Search on the GPU. In Proceedings of the 8th International Conference on Similarity Search and Applications – Volume 9371 (SISAP 2015). Springer-Verlag, Berlin, Heidelberg, 259–270. Google ScholarDigital Library
32. Yang Liu, Wenping Wang, Bruno Lévy, Feng Sun, Dong-Ming Yan, Lin Lu, and Chenglei Yang. 2009. On centroidal voronoi tessellation – energy smoothness and fast computation. ACM Trans. Graph. 28, 4 (2009), 101:1–101:17. Google ScholarDigital Library
33. Stuart P. Lloyd. 1982. Least squares quantization in pcm. IEEE Transactions on Information Theory 28 (1982), 129–137. Google ScholarDigital Library
34. Celestin Marot, Jeanne Pellerin, and Jean-Francois Remacle. 2018. One Machine, One minute, Three billion tetrahedra. https://arxiv.org/abs/1805.08831.Google Scholar
35. Guillaume Melquiond and Sylvain Pion. 2007. Formally certified floating-point filters for homogeneous geometric predicates. ITA 41, 1 (2007), 57–69.Google Scholar
36. Chrisochoides Nikos and Nave Damian. 2003. Parallel Delaunay mesh generation kernel. Internat. J. Numer. Methods Engrg. 58, 2 (2003), 161–176.Google ScholarCross Ref
37. Tom Peterka, Dmitriy Morozov, and Carolyn Phillips. 2014. High-Performance Computation of Distributed-Memory Parallel 3D Voronoi and Delaunay Tessellation. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC). 997–1007. Google ScholarDigital Library
38. Jean-François Remacle. 2017. A two-level multithreaded Delaunay kernel. Computer-Aided Design 85 (2017), 2–9. Google ScholarDigital Library
39. G. Rong, Y. Liu, W. Wang, X. Yin, D. Gu, and X. Guo. 2011. GPU-Assisted Computation of Centroidal Voronoi Tessellation. IEEE Transactions on Visualization and Computer Graphics 17, 3 (March 2011), 345–356. Google ScholarDigital Library
40. Guodong Rong and Tiow-Seng Tan. 2006. Jump Flooding in GPU with Applications to Voronoi Diagram and Distance Transform. In Proceedings of the 2006 Symposium on Interactive 3D Graphics and Games (I3D ’06). ACM, New York, NY, USA, 109–116. Google ScholarDigital Library
41. Chris Rycroft. 2009. Voro++: A Three-Dimensional Voronoi Cell Library in C++. 19 (12 2009), 041111.Google ScholarCross Ref
42. Jens Schneider, Martin Kraus, and Rüdiger Westermann. 2010. GPU-Based Euclidean Distance Transforms and Their Application to Volume Rendering. In Computer Vision, Imaging and Computer Graphics. Theory and Applications, AlpeshKumar Ranchordas, João Madeiras Pereira, Hélder J. Araújo, and João Manuel R. S. Tavares (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 215–228.Google Scholar
43. Jonathan Richard Shewchuk. 1996. Robust Adaptive Floating-Point Geometric Predicates. In Proceedings of the Twelfth Annual Symposium on Computational Geometry, Philadelphia, PA, USA, May 24–26, 1996. 141–150. Google ScholarDigital Library
44. C. Sigg, R. Peikert, and M. Gross. 2003. Signed distance transform using graphics hardware. In IEEE Visualization, 2003. VIS 2003. 83–90. Google ScholarDigital Library
45. Funshing Sin, Adam W. Bargteil, and Jessica K. Hodgins. 2009. A Point-based Method for Animating Incompressible Flow. In Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA ’09). ACM, New York, NY, USA, 247–255. Google ScholarDigital Library
46. Volker Springel. 2011. Moving-mesh hydrodynamics with the AREPO code. Computational Star Formation (2011).Google Scholar
47. Avneesh Sud, Naga Govindaraju, Russell Gayle, and Dinesh Manocha. 2006. Interactive 3D Distance Field Computation Using Linear Factorization. In Proceedings of the 2006 Symposium on Interactive 3D Graphics and Games (I3D ’06). ACM, New York, NY, USA, 117–124. Google ScholarDigital Library
48. Avneesh Sud, Naga Govindaraju, and Dinesh Manocha. 2005. Interactive computation of discrete generalized voronoi diagrams using range culling. In In Proceedings of the international symposium on Voronoi diagrams in science and engineering.Google Scholar
49. Avneesh Sud, Miguel A. Otaduy, and Dinesh Manocha. 2004. DiFi: Fast 3D Distance Field Computation Using Graphics Hardware. Computer Graphics Forum 23, 3 (2004), 557–566.Google ScholarCross Ref
50. The CGAL Project. 2018. CGAL User and Reference Manual (4.12.1 ed.). CGAL Editorial Board. https://doc.cgal.org/4.12.1/Manual/packages.htmlGoogle Scholar
51. David Watson. 1981. Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes. Comput. J. 24, 2 (1981), 167–172.Google ScholarCross Ref
52. Simon D. M. White and Volker Springel. 1999. Fitting the universe on a supercomputer. Computing in Science and Engineering 1, 2 (1999), 36–45. Google ScholarDigital Library
