A general overview
Voro++ is a open source software library for the computation of the Voronoi diagram, a widely-used tessellation that has applications in many scientific fields. While there are other software packages available to carry out these computations, Voro++ is written in way that makes it particularly suited for certain applications. Three main design features are:
- Cell-based computations – Some of the most popular existing codes 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 particle individually, as a polyhedron surrounding the particle. It is particularly well-suited for applications that rely on cell-based statistics, where features of Voronoi cells (eg. volume, centroid, number of faces) can be used to analyze a system of particles.
- 3D calculation – Increasingly, particle simulation studies concentrate on three-dimensional data and Voro++ is specifically tailored to this case.
- C++ architecture – The code is written in object-oriented C++ and is built as a static library. It has an extensive C++ coding interface that can be linked to by other programs. It can carry out calculations using a mix of periodic and non-periodic boundary conditions, and has a general class mechanism for handling different types of walls.
The structure of the code makes it particularly well-suited to many problems in physics and materials science, where Voronoi cells can be a useful method of analyzing particle packings. However, the library is also used in many other fields, including biological modeling, mesh generation, and computer graphics.
Features
In addition to the C++ routines for carrying out the Voronoi tessellation, Voro++ has a number of other features:
- Command-line utility – Voro++ contains a command-line utility that can access much of the library's functionality and perform detailed analyses on particle systems described in text files. Many users make use of this without requiring any detailed knowledge of the C++ code structure.
- Radical Voronoi tessellation (also referred to as the Laguerre tessellation) – for polydisperse particle systems it is often useful to consider the radical Voronoi tessellation, that weights the cell boundaries according to the relative radii of the particles.
- Neighbor list computation – Voro++ can optionally compute neighbor information, storing a list of neighboring particles that created each face of a Voronoi cell.
- Walls and complex boundary conditions – Voro++ supports both periodic and non-periodic boundary conditions. It also makes use of an extensible class system for handling boundary conditions due to walls. Plane, spherical, cylinder, and conical walls are supported, but further wall types can be added as derived C++ classes. Curved wall surfaces are approximated using planes.
- Customized output – the output files generated by Voro++ can be fully customized to contain a wide variety of different statistics about the computed Voronoi cells.
- C++ interface – Voro++ can be built as a static library and all of its functionality can be accessed through a C++ programming interface.
- Support for three-dimensional non-orthogonal periodic domains – In materials science, many chemical structures exist in non-orthogonal periodic domains given by three periodicity vectors that define a parallelepiped. The non-orthogonality significantly complicates the construction of Voronoi cells. Voro++ supports these calculations although this is currently a preliminary feature that is only accessible through the C++ interface and not through the command-line utility.
- Tolerant algorithms and degenerate vertex support – Carrying out accurate floating-point calculations is problematic on many systems, and on many popular processors, truncation errors can occur at any time, when numbers are moved from registers to memory. This makes it very hard to guarantee inequalities such as a<b as both a and b may change at any time. Voro++ takes the approach that if two numbers are within a small numerical tolerance, then those numbers are treated as being equal. In the cell-construction process, this can lead to the creation of vertices of arbitrary order, that Voro++ directly supports, allowing it to have perfect representations of shapes such as octahedrons, and icosahedrons.
- Extensive documentation and examples – Every routine in the source code is documented, and there are numerous examples provided online of how to use the code. A reference manual is automatically generated from the source code using the Doxygen system.
- Simple extension to parallel computation – Since each Voronoi cell is computed independently, it is straightforward to parallelize the code to a multicore architecture.
C++ code structure
The code is structured around several C++ classes. The
voronoicell class contains all of the routines for constructing a
single Voronoi cell. It represents the cells as a collection of vertices that
are connected by edges. To compute the Voronoi cell, it is first initialized as
a large rectangular box filling the domain, and is then repeatedly cut with
planes that correspond to the perpendicular bisectors between on point and its
neighbors. The plane function will recompute the cell after
cutting with a single plane. Once the cell is computed, it can be drawn using
functions such as draw_gnuplot and draw_pov. Numerous
routines exist for computing features of the cell, like its surface area,
volume, or centroid.
The container class represents a 3D rectangular box of
particles. The constructor for this class sets up the coordinate ranges, sets
whether each direction is periodic or not, and divides the box into a
rectangular grid of blocks. Particles can be added to the container using
the put function, that adds a particle's position and an integer
numerical ID label, to the container by adding it to the corresponding block.
The function import can be used to read in large numbers of
particles from a text file.
The Voronoi computations are carried out by the voro_compute
template. This class contains a function called compute_cell,
which can analyze the particles in an associated container class
to create a single Voronoi cell for a particle in the container. Various
functions utilize calls to compute_cell to carry out analyses of
the particle arrangement.
The radical Voronoi tessellation is handled by the
container_poly class, which is a variant of the
container class, where the put function accepts an
additional argument for the particle radius. Neighbor computations are carried
out using the voronoi_neighbor class, which is a variant of
voronoicell that has additional data structures for associating
the IDs of neighboring particles with each Voronoi cell face. These variants
are created by exploiting C++ templates.
Wall computations are handled by making use of a pure virtual
wall class. Specific wall types are derived from this class, and
have a routine called point_inside that tests to see if a point
is inside a wall or not, and a routine called cut_cell that cuts
a cell according to the wall's position. The walls can be added to the
container using the add_wall function, and these are called each
time a compute_cell function is carried out. The library contains
a number of other small helper classes, such as c_loop classes
that allow the computation routines to iterate over a specific subset of
particles within a container.
Development
Voro++ is written and maintained by Chris H. Rycroft, a visiting assistant professor in mathematics at UC Berkeley and the Lawrence Berkeley Laboratory. A preliminary version of the code was written at MIT during 2005–2006 to carry out local packing fraction computations during doctoral thesis work on flow in granular materials. After receiving feedback from a number of different research groups, the code was completely rewritten and extended during 2007–2008, to allow it to be publicly released during Summer 2008.