Voro++: A Three-dimensional Voronoi Library in C++

Voro++ is an open source software library for the computation of the Voronoi diagram, a widely-used tessellation that has applications in many scientific fields. For a set of points in a domain, the tessellation is defined by associating a cell of space to each point, consisting of the part of the domain closer to that point than any other.

 Several mature software libraries exist for computing the Voronoi tessellation (such as Qhull, used by MATLAB, and CGAL) but these typically compute the Voronoi diagram as a single object: given a set of points they will return the complete mesh that divides those points into cells. Voro++ works differently, computing the Voronoi cell for each point individually, as a polyhedron surrounding the point. This makes it well-suited for applications that rely on cell-based statistics, where features of Voronoi cells (e.g., volume, centroid, number of faces) can be used to analyze a system of points or particles.

The library is structured around several C++ classes. The voronoicell class encapsulates all of the routines for representing a Voronoi cell as an irregular convex polyhedron (Fig. 1(a)). This class is then employed by the container class, which represents a system of particles (Fig. 1(b)), and can carry out a wide variety of computations. The code architecture makes it easy to modify and incorporate into other programs, and a large number of example programs are available on the library website. Figure 1(c) is taken from one of these examples, where the the Voronoi cell computation has been modified to approximate a cylindrical boundary condition.

Figure 1:  (a) A single Voronoi cell shown in isolation, which forms the basis of the Voro++ library’s computations.

Figure 1: (b) Voronoi tessellation of 216 particles in a cube.

Applications of the library

The library has been downloaded 698, 1,192, and 1,611 times during the years of 2009, 2010, and 2011 respectively. During the first four months of 2012, it has been downloaded 731 times. It is referenced in a number of peer-reviewed publications, and has been incorporated into other software projects. A selection of applications of the library are shown in Fig. 2. Perhaps the most common area of application is in condensed matter physics and materials science, where the Voronoi tessellation can be used to analyze particulate materials (Figs. 2(c,e,g,h)). In some situations, the Voronoi tessellation can be used for mesh generation (Figs. 2(b,f)). Certain natural processes and structures such as solidification patterns (Fig. 2(a)) and biological cells (Fig. 2(d)) can be modeled with the Voronoi tessellation. The library has also been used by the Antony Gormley studio in London as a method of designing abstract sculpture (Fig. 2(i)).

Figure 2: Applications of Voro++: (a) solidification processes (A. Phillion, UBC), (b) grid generation in Re-ALE schemes (M. Shashkov, LANL), (c) mechanics of sand swimmers (Y. Ding and D. Goldman, Georgia Tech), (d) modeling of an epithelial cell layer (L. Fenelon and M. Guillaud, BC Cancer Research Centre), (e) nanosphere system stability (C. Phillips and S. Glotzer, University of Michigan), (f) Representative Volume Element generation for fracture modeling (R. Twardowski, RWTH Aachen), (g) molecular dynamics simulation of metallic glasses (Y. Zhang, IFW Dresden), (h) volume fraction computations of tetrahedral liquids (I. Regev and I. Procaccia, Weizmann Institute), (i) Voronoi sculpture design (Antony Gormley studio, London).

Use of the library for high-throughput screening of porous materials

The software library has also been instrumental in forming a collaboration at LBL with the Scientific Computing group, to create new software tools for high-throughput screening of crystalline porous materials such as zeolites. These materials contain complex networks of void channels, that can be exploited in many industrial applications. A key requirement of the success of any nanoporous material is that the pore topology must be optimal for a given application. However, this is a difficult task, since the number of pore topologies is extremely large: thousands of materials have been synthesized and databases of millions of hypothetical structures are available.

The Voronoi tessellation provides a map of the channels within a given structure, and can be used to determine whether a given molecule can propagate between the atoms (Fig. 3(a)), and the Voro++ library was adapted to carry out these computations. While some materials have rectangular periodic unit cells (Fig. 3(b)), others have parallelepiped unit cells (Fig. 3(c)) which requires a more complex calculation. Once the Voronoi tessellation has been computed, it can be used to calculate several geometrical indicators of each material, such as the surface area accessible to a given molecular probe (Fig. 3(d)).

These computational tools have recently led to a further collaboration with the UC Berkeley chemistry department to identify porous materials that could be suitable for carbon capture applications. The main challenge is to identify structures that let power plant flue gases such as N₂ pass, while being capable of adsorbing CO₂; the porous structure can then be heated to purge the CO₂ for sequestration. A combination of screening and simulation techniques led to the identification of a variety of new materials that have the potential to be up to 30% more efficient than existing technologies.

Figure 3:  (a) the Voronoi tessellation for a planar particle arrangement, showing how it can be used to describe channels of empty space between particles, (b) computation of the Voronoi network (white) for the BIK zeolite in a rectangular unit cell, (c) computation of the Voronoi network for the YUG zeolite in a parallelepiped unit cell, (d) surface area computation for the DDR zeolite, where the Voronoi network is used to differentiate between accessible area (green) and inaccessible pockets (red), (e) an overview of porous materials suitable for carbon capture applications, measured in terms of the energy required to capture one kilogram of CO2; a number of the materials that have been identified are predicted to be up to 30% more efficient than current technologies based on scrubbing with amine solutions, shown by the horizontal green line.