A simple and fast algorithm for computing discrete Voronoi, Johnson-Mehl or Laguerre diagrams of points. (August 2022)

• Record Type: Journal Article
• Authors: Moulinec, Hervé
• Is Part Of: Advances in engineering software. Volume 170(2022)
• Publication Date: 2022-08
• Subjects: Voronoi diagram -- Johnson-Mehl tessellation -- Laguerre tessellation -- micromechanics; Computer-aided engineering -- Periodicals; Engineering -- Computer programs -- Periodicals; Engineering -- Software -- Periodicals; Periodicals; 620.0028553
• DOI: 10.1016/j.advengsoft.2022.103150
• Languages: English
• ISSNs: 0965-9978

Abstract

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.