A simple and fast algorithm for computing discrete Voronoi, Johnson-Mehl or Laguerre diagrams of points. (August 2022) - Moulinec, Hervé
Highlights: Generation of digital images of Voronoi, Laguerre and Johnson-Mehl tessellations. Microstructure simulation of polycrystalline materials for calculations using FFT-based homogenization methods. Microstructure generation with periodic boundary conditions. Abstract: This article presents an algorithm to compute digital images of Voronoi, Johnson-Mehl or Laguerre diagrams of a set of punctual sites, in a domain of a Euclidean space of any dimension. The principle of the algorithm is, in a first step, to investigate the voxels in balls centred around the sites, and, in a second step, to process the voxels remaining outside the balls. The optimal choice of ball radii can be determined analytically or numerically, which allows a performance of the algorithm in O ( N v ln N s ), where N v is the total number of voxels of the domain and N s the number of sites of the tessellation. Periodic and non-periodic boundary conditions are considered. A major advantage of the algorithm is its simplicity which makes it very easy to implement. This makes the algorithm suitable for creating high resolution images of microstructures containing a large number of cells, in particular when calculations using FFT-based homogenisation methods are then to be applied to the simulated materials.