An extension to VORO plus plus for multithreaded computation of Voronoi cells

JY Lu and EA Lazar and CH Rycroft, COMPUTER PHYSICS COMMUNICATIONS, 291, 108832 (2023).

DOI: 10.1016/j.cpc.2023.108832

VORO++ is a software library written in C++ for computing the Voronoi tessellation, a technique in computational geometry that is widely used for analyzing systems of particles. VORO++ was released in 2009 and is based on computing the Voronoi cell for each particle individually. Here, we take advantage of modern computer hardware, and extend the original serial version to allow for multithreaded computation of Voronoi cells via the OpenMP application programming interface. We test the performance of the code, and demonstrate that it can achieve parallel efficiencies greater than 95% in many cases. The multithreaded extension follows standard OpenMP programming paradigms, allowing it to be incorporated into other programs. We provide an example of this using the VoroTop software library, performing a multithreaded Voronoi cell topology analysis of up to 102.4 million particles.Program summaryProgram title: VORO++CPC Library link to program files: https://doi .org /10 .17632 /tddc4w4zkk.1Developer's repository link: https://github .com /chr1shr /voro Licensing provisions: BSD 3-clause (with LBNL modification) Programming language: C++External routines/libraries: OpenMPNature of problem: Multithreaded computation of the Voronoi tessellation in two and three dimensions Solution method: The VORO++ library is built around several C++ classes that can be incorporated into other programs. The two largest components are the container... classes that spatially sort input particles into a grid- based data structure, allowing for efficient searches of nearby particles, and the voronoicell... classes that represent a single Voronoi cell as an arbitrary convex polygon or polyhedron. The Voronoi cell for each particle is built by considering a sequence of plane cuts based on neighboring particles, after which many different statistics (e.g. volume, centroid, number of vertices) can be computed. Since each Voronoi cell is calculated individually, the Voronoi cells can be computed using multithreading via OpenMP.& COPY; 2023 Elsevier B.V. All rights reserved.

Return to Publications page