Sphere packing algorithm for the generation of digital models of polycrystalline microstructures with heterogeneous grain sizes

Lucyna Hajder, Lukasz Madej

AGH University of Science and Technology, Mickiewicza av. 30, 30-059 Krakow, Poland.




Development of the cellular automata (CA) sphere packing algorithm dedicated to the generation of two- and three-dimensional digital, synthetic microstructure models with heterogenous grain size distribution is presented within the paper. The synthetic microstructure model is generated in four major steps: generation of 2D/3D cellular automata computational domain, generation of circles/spheres with a required size distribution, close-packed filling of the computational domain with generated circles/spheres, growth of the circles/spheres according to the unconstrained CA growth algorithm. As a result, synthetic microstructure models with specific, required grain size distribution described by e.g. uni- or bimodal one are obtained. To reduce computational complexity and decrease execution time, the rotation of the circles/spheres during the packing stage is based on the vector accounting for the distance from computational domain borders and other spheres. The CA grain growth algorithm is also implemented using threads mechanism allowing parallel execution of computations to increase its efficiency. The developed algorithm with the implementation details as well as a set of examples of obtained results are presented within the paper.

Cite as:

Hajder, L., & Madej, L. (2020). Sphere packing algorithm for the generation of digital models of polycrystalline microstructures with heterogeneous grain sizes. Computer Methods in Materials Science, 20, 24-32. https://doi.org/10.7494/cmms.2020.1.0652

Article (PDF):


Digital Material Representation, Sphere Packing Algorithm, Cellular Automata


Banhart, J., 2008, Advanced tomographic methods in material research and engineering, Oxford University Press.

Baranau, V., Tallarek, U., 2014, Random-close packing limits for monodisperse and polydisperse hard spheres, Soft Matter, 10(21), 3826-3841.

Clarke, A.S., Wiley, J.D., 1987. Numerical simulation of the dense random packing of a binary mixture of hard spheres: Amorphous metals, Physical Review B, 35(14), 7350-7356.

Cui, L., O’Sullivan, C., 2003, Analysis of a triangulation based approach for specimen generation for discrete element simulations, Granul. Matter, 5, 135-145.

Burnett, T.L., Polonsky A.T., Pollock, T.M., Withers P.J., 2020, Serial sectioning in the SEM for three dimensional materials science, Current Opinion in Solid State and Materials Science, 24(2), 100817.

Evans, J.W., 1993, Random and cooperative sequential adsorption, Reviews of Modern Physics, 65, 1281-1304.

Gawad, J., Madej, L., Szeliga, D., Pietrzyk, M., 2005, Cellular automaton technique as a tool for a complex analysis of the microstructure evolution and rheological behavior, Acta Metallurgica Slovaka, 11, 45-53.

He, K., Ye, H., Wang, Z., Liu, J., 2018, An efficient quasiphysical quasi-human algorithm for packing equal circles in a circular container, Computers and Operations Research, 92, 26 -36.

Hitti, K., Bernacki, M., 2013, Optimized dropping and rolling (ODR) method for packing of poly-disperse spheres, Applied Mathematical Modelling, 37(8), 5715-5722.

Hoffpauir, B.K., Pope, B.A., Spirou, G.A., 2007, Serial sectioning and electron microscopy of large tissue volumes for 3D analysis and reconstruction: a case study of the calyx of held, Nature Protocols, 2(1), 9-22.

Ilina, D.N., Bernacki, M., 2016, A new algorithm for dense ellipse packing and polygonal structures generation in context of FEM or DEM, MATEC Web of Conferences, vol. 80, doi.org/10.1051/matecconf/20168002004.

Jodrey, W.S., Tory, E.M., 1979, Simulation of random packing of spheres, Simulation, 32(1), 1-12.

Kazakov, A.L., Lempert, A.A., Ta, T.T., 2018, The sphere packing problem into bounded containers in threedimension non-Euclidean space, IFAC-PapersOnLine, 51(32), 782 -787.

Khirevich, S., Höltzel, A., Tallarek, U., 2013, Validation of pore-scale simulations of hydrodynamic dispersion in random sphere packings, Communications in Computational Physics, 13(3), 801-822.

Madej, L., 2017, Digital virtual microstructures in application to metals engineering – a review, Archives of Civil and Mechanical Engineering, 17, 839-854.

Madej, L., Pasternak, K., Szyndler, J., Wajda, W., 2014. Development of the modified cellular automata sphere growth model for creation of the digital material representations,. Key Engineering Materials, 611, 489-496.

Orick, G.L., Stephenson, K., Collins, C., 2017, A linearized circle packing algorithm, Computational Geometry: Theory and Applications, 64, 13-29.

Pietrzyk, M., Madej, L., Rauch, L., Szeliga, D., 2015, Computational materials engineering: achieving high accurancy and efficiency in metals processing simulations, Butterworth- Heinimann, Elsevier.

Raabe, D., Becker, R., 2000, Coupling of a crystal plasticity finitelement model with a probabilistic cellular automaton for simulating primary static recrystallization in aluminium, Modelling and Simulation in Materials Science and Engineering, 8, 445-462.

Romanova, T., Litvinchev, I., Pankratov, A., 2020, Packing ellipsoids in an optimized cylinder, European Journal of Operational Research, 285(2), 429 – 443.

Sahu, K., 2009, Gravity packing of same size spheres and investigation of wall ordering, International Journal of Chemical Reactor Engineering, 7(1), doi:10.2202/1542-6580.1932

Shi, Y., Zhang, Y., 2008, simulation of random packing of spherical particles with different size distributions, Applied Physics A, 92(3), 621-626.

Sitko, M., Mojzeszko, M., Rychlowski, L., Cios, G., Bala, P., Muszka, K., Madej, L., 2020. Numerical procedure of three-dimensional reconstruction of ferrite-pearlite microstructure data from SEM/EBSD serial sectioning, Procedia Manufacturing, 47, 1217 – 1222.

Sohn, H.Y., Sridhar, S., 2005. Description of high-temperature metallurgical processes, in: Fundamentals of metallurgy, Padstow: Woodhead Publishing Limited, 3-38.

Torquato, S., Jiao, Y., 2010, Robust algorithm to generate a diverse class of dense disordered and ordered sphere packings via linear programming, Physical Review E, 82(6), 061302.

Jodrey, W.S., Tory, E.M., 1986, Computer simulation of close random packing of equal spheres, Physical Review A, 32(4), 2347-2351.

Totten, G., Pye, D., 2004, Heat-treating process design. in: handbook of metallurgical process design, CRC Press, New York, 453 – 506.

Vásárhelyi, L., Kónya, Z., Kukovecz, Á., Vajtai, R., 2020, Microcomputed tomography–based characterization of advanced materials: a review, Materials Today Advances, 8, 100084, doi.org/10.1016/j.mtadv.2020.100084.

Visscher, W.M., Bolsterli, M., 1972, Random packing of equal and unequal spheres in two and three dimensions, Nature, 239, 504-507.

Von Neumann, J., 1966, Theory of self-reproducing automata, ed.., Burks, A.W., University of Illinois Press, Urbana,