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.
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)).
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.
About Berkeley Lab
Founded in 1931 on the belief that the biggest scientific challenges are best addressed by teams, Lawrence Berkeley National Laboratory and its scientists have been recognized with 14 Nobel Prizes. Today, Berkeley Lab researchers develop sustainable energy and environmental solutions, create useful new materials, advance the frontiers of computing, and probe the mysteries of life, matter, and the universe. Scientists from around the world rely on the Lab’s facilities for their own discovery science. Berkeley Lab is a multiprogram national laboratory, managed by the University of California for the U.S. Department of Energy’s Office of Science.
DOE’s Office of Science is the single largest supporter of basic research in the physical sciences in the United States, and is working to address some of the most pressing challenges of our time. For more information, please visit energy.gov/science.