Acta Polytechnica CTU Proceedings doi:10.14311/APP.2017.13.0102 Acta Polytechnica CTU Proceedings 13:102–108, 2017 © Czech Technical University in Prague, 2017 available online at http://ojs.cvut.cz/ojs/index.php/app WANG TILE SIZE IN TERMS OF CIRCULAR PARTICLE DYNAMICS David Šedlbauer Czech Technical University in Prague, Faculty of Civil Engineering, Department of Mechanics, Thákurova 7, 166 29 Prague 6, Czech Republic correspondence: david.sedlbauer@fsv.cvut.cz Abstract. The main advantage of the Wang tiling concept for material engineering is ability to create large material domains with a relatively small set of tiles. Such idea allows both a reduction of computational demands and preserving heterogeneity of a reconstructed media in comparison with traditional cell concepts. This work is dealing with a random heterogeneous material composed of monodisperse circular hard particles within a matrix. The Wang tile sets are generated via algorithm with molecular dynamics and adaptive boundaries approach. Even though previous works proved usefulness of the Wang tiling for material reconstruction, still plenty of questions remain unanswered. In here we would like to provide simulations with emphasis on the overall particle distribution and the ratio of hard disc number to tile size. The results and discussion should followers help with settings of both tile generations and the tiling algorithms when creating samples of various degree of heterogeneity. Keywords: Wang tiling, random heterogeneous material, tile size, adaptive boundaries. 1. Introduction Despite the exponentially increasing computing power, simulations and modelling of random heterogeneous materials on microscale have been performed mostly using the periodical unit cells (PUCs) forming a rep- resentative sample. Unfortunately the nature of the PUC is in contradiction with the terms random and heterogeneity typicaly characterizing investigated ma- terial. The main idea of the Wang tiling [1] is to stack large (infinite) aperiodic plane via relatively small set of tiles. Within last few years a group of researches has been dealing with the Wang tiling approach as a tool for random heterogeneous material modelling. There is no need to stack strictly aperiodic tiling for usage in material engineering, therefore stochastic CSHD tiling algorithm has been utilized [2]. In general, algorithms for generation of the tile sets with circular particles can be divided into two groups based on the nature of a particle positioning. The pilot work [3] linking the Wang tile principles with material engineering, utilized static approach, whereas in this paper a process based on the molecular dynamics is utilized. The sets for tiling shown on the following Figure 1 were generated with the same algorithm. The first tiling is stacked of the set, where each tile includes only one particle. The second tiling is composed of the set, where size of each tile is twice bigger than in the first case. Therefore tile contains more particles, but the overall volume fraction remains the same for both tilings. The last tiling is made of the set with 36 particles per tile, but finial domain exhibits the same fraction as well. Figure 1. Examples of tilings with: 1 inclusion/tile (30×30 tiles), 4 inclusions/tile (15×15 tiles), 36 inclu- sions/tile (5×5 tiles); Wang tiling set of 8 tiles over 4 codes. 102 http://dx.doi.org/10.14311/APP.2017.13.0102 http://ojs.cvut.cz/ojs/index.php/app vol. 13/2017 Wang tile size in terms of circular particle dynamics It is obvious, that the first simulation represents S arrangement, whereas the second and the third tiling form rather R arrangement (particles randomly over whole area) [4]. One can also easily observe differences in the degree of heterogeneity, where in the first sam- ple there are visible interferences and the structure is closer to the ordered system in comparison with the last tiling with obvious particles clusters. There- fore the main goal of the presented contribution is to provide some simulations and build up recommenda- tions for particle-tile size relation with emphasis on overall arrangement and different states of heterogene- ity/ordering. These suggestions should help followers with the settings of a generation algorithm when tiling a material model with required geometrical properties. The contribution is organized as follows. The next chapter briefly presents algorithm for the Wang tile set generation. The beginning of the third part is devoted to tile size dimensions in terms of various packing states. The last but one subchapter presents simulations and include the discussion of obtained results. In the conclusion the summary of the paper with possible ways of the future work is presented. 2. Algorithm for tile generation The basis of the Wang tiling is represented by set of building blocks, Wang tiles. These can be seen origi- nally as squares with codes on edges, which enables to keep compatibility of neighbours in the final tiling. During years there were works attempting to find the minimal set of tiles for aperiodic tiling. The last known minimal aperiodic set of tiles consists of eleven pieces over four colours (codes) [5]. Since for material engineering there is no need to keep strictly aperiodic tiling, we utilize stochastic CSHD algorithm [2]. Con- sidering four different possible codes on edges, the minimal set consists of eight tiles. For the group of materials composed of circular hard particles within a matrix an algorithm inspired by molecular dynamics has been successfully uti- lized, where particles move and collide during re- construction process until the stopping criterion is reached. The similar principle (modified Lubachevsky- Stillinger [6]) utilizes the algorithm for tile set genera- tion. In the begging of the process, the particles zero initial radii are randomly thrown into each square tile and assigned with random velocity vectors. The par- ticles (inclusions) grow and collide with walls and with each other during the motion until they have reached desired diameter and arrangement. The de- scription of algorithm can be found in [7] together with recomanded optimized particle velocities. One of the main problems, the algorithm has to deal with, is the compatibility on tile edges/corners. If there is no trespassed particles, Wang tiles are re- duced only to separated systems with noticeable bor- ders in final tiling. In order to avoid such an artificial artefact a concept of adaptive boundaries was devel- oped [8]. In here the tile edges represents borders for Figure 2. Principle of adaptive boundaries. particles centres instead of particle surfaces. Thus in- clusions in the master tile are affected with a motion of particles in possible tile neighbours. Therefore the process leads on one hand to higher computational demands connected with higher number of collisions between particles, on the other hand there is a system with adaptive boundaries reducing unwanted artificial periodicity. An example of generated tile set with highlighted adaptive boundaries is in Figure 2. 3. Simulations and discussion In this chapter simulations are presented ilustrating the tile generation together with tiled samples, where we would like to point out the problems user has to deal with and discuss possible solutions. 3.1. Tile size and particle packing In the concept of the Wang tiling every tile used to be of unit size. But for modelling, the base block has to have a size of certain value or at least to be in the certain ratio with other structural dimensions. The determination of the tile size can be divided into two consecutive steps. In the first one there is need to define minimal geometry demands, in order to be able to reach various states of packings. Within the second step the size of tiles as well as tiling is compared to the characteristic structural sizes of a modelled sample or/and modified with emphasis on overall required material properties. This contribution deals mostly with the first condition. As mentioned in the problem definition, each Wang tile could have different number of particles. Such an assumption has to be taken into account for both full tiling and materials with lower packing density. The very first thing in a definition of the tile size should be identification of possible packing states. When the required material is fully packed or domain should have clusters of particles, it is necessary to cog- itate the close dense packing [9]. Since the dynamic algorithm involves adaptive boundaries, it is possi- ble to achieve the maximal hexagonal dense packing of equal-sized inclusions with the volume fraction of 0.9069. Nevertheless in order to be on the safe side with a definition of square tile dimensions, reader is referred to the densest packing of equal-sized disks in a 103 David Šedlbauer Acta Polytechnica CTU Proceedings case No. inclusions/tile tile size tiling 1 1 20 30×30 2 9 60 10×10 3 36 120 5×5 Table 1. Monodisperse tiling – settings. square volume [10, 11]. It has to be noticed that such an assembly leads to particle periodic artefacts and or- dered homogenized samples, which are far away from the term of random or heterogeneous. For the investi- gated materials more common are so-called jammed states (mechanical stable states). The most disordered jammed state used to be called maximally random jammed state, which can replace the term random close packing. For more information regarding densest packing states the reader is referred to [9, 12], since in our simulation we will focused on tiling with lower particle fraction and higher degree of freedom. 3.2. Tiles with the same number of equal-size inclusions In general it is better to have the same volume fraction in every tile. With this assumption the probability of accepting a next tile in tiling should be of value 0.5 in every step of the algorithm, assuring the material volume fraction. The term volume fraction, or in this case packing fraction, is defined as ratio of the sum of particle areas to overall space. The dimension of space is relative to tile size, therefore the number of particles within a tile defines (with respect to the required packing fraction) the size of each tile. In the following examples, where different number of particles in tiles are used, we will compare how this setting affects tiled model in terms of computer demands and simplified basic statistical description. For all analysed cases the packing fraction is 0.442. We want to show how different tiling could be pro- duced with various tile size, therefore the packing fraction is set well below the fraction for maximal random dense packing in order to preserve the degree of freedom for particles. For clarity the size of a final tiling is 600×600 pixels/microns. There are three examples where the tile size in- creases gradually. In the first case we have only one inclusion in every tile. Since the size of tile is 20 pixels, the final tiling consists of 30×30 tiles. In the Tab. 1 the summary of investigated cases with settings def- inition is presented. In the Figures 3 4 5 generated sets and examples of tilings with pore division and appropriate pore size distribution are shown [13]. (A). (B). (C). Figure 3. The first setings – (A) generated set, (B) tiling with pores, (C) pore size distribution. In the first case, the tiling exhibits similarity to the material with lattice. The particles in every tile have limited freedom given by the tile size-particle radius ratio which is 0.375. Thus the pore size histogram is quite narrow without existence of extra large or small pores. Such setting is valid only for a reconstruction of domain with high-ordered particle system or with periodic arrangement. In the second investigated case, the obviously dif- ferent arrangement of particles without large visible periodic artefacts is obtained. The diagram exhibits wide range of pore distribution, which was achieved due to more space for particle motion. Nevertheless there is still very predominate pore size indicating lower level of disordering. Despite the fact of wider pore distribution, the local particle clusters occured, caused by small number of particles within a tile and the nature of the stochastic tiling. 104 vol. 13/2017 Wang tile size in terms of circular particle dynamics Figure 4. The second setings – generated set, tiling with pores, pore size distribution. In the last tiling, where each tile includes 36 parti- cles, we gain the system with pore distribution near to the normal distribution. This confirms the claim that the larger Wang tile the more heterogenous is reconstructed material. Moreover, the results from the two point probability function [9] of tiling with 36 particles exhibit reduction of unwanted secondary peaks, which indicates the decrease of periodicity, es- pecially in comparison to the tiling composed with the PUC system 6. Please note that these figures were obtained as average from ten different tilings with the same size and the same number of tiles. The resolution (pixels/tile) was decreased to main- tain the clarity of figures. Nevertheless the defini- tion of maximal or sufficient tile size should be in accordance with required mechanical properties which needs further statistical description and investigation. But one has to have in mind the increasing computa- tional demands. Figure 5. The third setings – generated set, tiling with pores, pore size distribution. Figure 6. Two point probability function:36 inclu- sions/tile – top PUC tiling, bottom Wang tilling. 105 David Šedlbauer Acta Polytechnica CTU Proceedings incl. per tile frac. bound colli- sions particle colli- sions sum- mary colli- sions 1 0.049 39 4 43 2 0.098 72 29 101 3 0.147 96 78 174 4 0.196 128 137 265 5 0.245 151 248 399 6 0.295 180 441 621 7 0.344 212 574 786 8 0.393 243 829 1072 Table 2. Computer demands – number of collisions. inclusions per tile bound collisions particle collisions summary collisions 1 46 119 165 4 117 352 469 36 950 7683 8633 Table 3. Computer demands – number of collisions of representatives Despite the author’s best effort, the whole process definitely lacks internal optimization of the code to allow comparison in terms of the computer demands. Nevertheless, the computationally most demanding task is in a correlation with number of collisions. After collision of any particle with wall or another particle, velocity vectors have to be recalculated. The Table 2 presents summary of number of collisions for increas- ing number of particles within a tile of the same size. It has to be noted that these values are averaged over ten measurements. There is obvious interference be- tween number of wall rebounds and particle collisions. With packing fraction around 0.2 the number of both collision types is approximately equal. For lower frac- tion there is much more free space and particles do not colide so often. With higher fraction the situation is reversed. In Table 3 number of collisions are compared for the three representative cases. Since the packing fraction was 0.442, there is a higher probability of particle- particle collisions then for rebounds from walls. If we consider the first case as a reference one, then the performed representative results together with internal checks indicate following: The number of particle- particle collisions grow approximately with the same rate as tile size till the tiled area is ten times larger compared with the reference tile. The algorithm for particle motion begins with ran- domized velocity vectors. If we want to regulate com- puter demands, several possibilities exist. The easiest one is to generate Wang tiles of a small size, but with such settings the tiling exhibits periodicity artefacts. Moreover the final reconstructed material sample of the same size requires tiling with higher number of tiles. Therefore savings on tile generation can be con- sumed on tiling algorithm. Another possibility is to modify algorithm for tile generation, where velocity vectors will be optimized and more reduced. The sim- ilar approach has already been used in optimization of tiles with border areas [7]. There is also an option based on the semi-dynamic algorithm, where in the first step the particles are placed in a tile with certain initial radius. But in this process computer power will be used for initial arrangement of particles, thus savings are questionable. 3.3. Tiles with different number of equal-size inclusions The Wang tiling set, where each tile includes the same number of particles, fits either domains with lattices or materials with lower degree of heterogeneity [14]. If the reconstructed material sample should have some particle clusters or high degree of heterogeneity, the best way is to utilize the Wang tiling with different number of particles in tiles. Nevertheless with differ- ent tile particle packing other issues arise. The most critical one is dsign of tiling algorithm in terms of prescribed overall volume fraction. When the set in- cludes very varying tiles and tiling is made of relatively small number of tiles, the tiling algorithm cannot as- sure required volume fraction because of the uniform acceptance probability. This problem can be solved with observation of tiling process, where acceptance probability varies over tile set. After a certain part of the Wang tiling is complete, the temporary packing fraction can be recalculated and tiles will be assigned with an updated acceptance probability. Another so- lution might be to generate a new set with similar distribution of particles over tiles. The last but not least option is to transfer particles from tile to tile within the tiling algorithm. Following examples show tiling with very individual particle packing in each tile. It has to be noticed that these examples were made without any improvement in tiling algorithm. Thus the final pattern for each case exhibits different overall particle fraction. Obviously we gain in both cases samples with high degree of heterogeneity. This statement is verified us- ing visual check and the pore distribution histogram with representation of both small and large pores. Occurrence of the large pores is caused by tiles with minimal particle fraction and another phenomenon – empty tiles. Due to the usage of adaptive boundaries approach, empty tile should not be considered as a periodic cell. However such tile includes an area where any particle from tiling can never get to. One empty tile in the set is suitable for tiling diversity. More empty tiles result in redundancy of full basic Wang tile set. But existence of the same tiles in a set also of- fers an opportunity to increase acceptance probability 106 vol. 13/2017 Wang tile size in terms of circular particle dynamics Figure 7. Artifitial tiling 10×10 from basic set in- cluding 10, 8, 6, 4, 2, 1, 1, 0 equal-sized discs. of tiles without any intervention in tiling algorithm. The similar postulate is valid for expanded tile set as well as identical tiles with particles within. 4. Conclusions The concept of Wang tiling has already been rooted in the family of approaches, which are suitable for random heterogeneous material modelling. It brings possibilities of aperiodic tiling of large material do- mains with a relative small set of basic tiles. In this contribution we were dealing with a random hetero- geneous domain composed of equal-sized hard discs within a matrix. The basic set for tiling of such ar- tificial material sample was obtained via algorithm based on molecular dynamic and adaptive boundaries approaches. Even though this type of generation ex- hibits potential, there has been so far modelled only general samples without tile size investigation. There- fore we focused in this contribution on specific types Figure 8. Artifitial tiling 10×10 from basic set in- cluding 8, 8, 8, 8, 0, 0, 0, 0 equal-sized discs. of material domains with various particle configura- tions and volume fractions. The final tilings were constructed using the stochastic CSHD algorithm. In the first part of simulations, generated Wang tile set consists of tiles with the same particle frac- tion. The second part presented analysis of tiling with tiles of large differences in number of particles inside. Based on presented examples of illustrative tilings, one can show, how the size of tiles (and appropriate number of particles within) affects possibilities of par- ticle arrangement and ordering of the obtained sample. These tests proved the variability of Wang tiling in connection with the tile generator based on molecular dynamics. Concurrently the discussion over occurring arrangement could help followers with settings of both tiling algorithm and the generator. The investigated material contained only monodis- perse hard particles. But the Wang tile approach and the described generator are suitable for a wide range of 107 David Šedlbauer Acta Polytechnica CTU Proceedings material domains. Therefore future work will focus on other material models with various particle numbers and shapes. Within the next steps we will also inte- grate more statistical descriptions in order to quantify and compare material characteristics. Finally, whole process will be extended to 3D. Acknowledgements The financial support of the Grant Agency of the Czech Technical University in Prague, grant No. SGS17/042/OHK1/1T/11, is gratefully acknowledged. References [1] H. Wang. Proving theorems by pattern recognition ll. Bell Labs Technical Journal 40(1):1–40, 1961. doi:10.1002/j.1538-7305.1961.tb03975.x. [2] M. F. Cohen. Wang tiles for image and texture generation. Second printing. Association for Computing Machinery, 2003. [3] J. Novák. Microstructural enrichment functions based on stochastic wang tilings, 2013. [4] T. Müllner. Characterization of microscopic disorder in reconstructed porous materials and assessment of mass transport-relevant structural descriptors. New Journal of Chemistry 40(5):3993–4015, 2016. doi:10.1039/C5NJ03346B. [5] E. Jeandel. An aperiodic set of 11 wang tiles. arXiv preprint arXiv p. 1506.06492, 2015. [6] B. D. Lubachevsky. Geometric properties of random disk packings. Journal of Statistical Physics 60(5-6):561–583, 1990. doi:10.1007/BF01025983. [7] D. Šedlbauer. Optimized wang tiles generation for heterogeneous materials modelling. Applied Mechanics and Materials pp. 183–190, 2016. doi:10.4028/www.scientific.net/AMM.825.183. [8] D. Šedlbauer. Adaptive boundaries of wang tiles for heterogeneous material modelling. Advanced Materials Research pp. 159–166, 2017. doi:10.4028/www.scientific.net/AMR.1144.159. [9] S. Torquato. Random heterogeneous materials: microstructure and macroscopic properties. Springer Science & Business Mediat, 2013. [10] P. Szabó. Packing up to 200 equal circles in a square. Models and Algorithms for Global Optimization Optimization and Its Applications 2007. doi:10.1007/978-0-387-36721-7_9. [11] K. W. Desmond. Random close packing of disks and spheres in confined geometries. Physical Review E 80(5):051305, 2009. doi:10.1103/PhysRevE.80.051305. [12] Y. Jiao. Characterization of the structure of heterogeneous materials and particle packings. Princeton University, 2010. [13] A. Rabbani. An automated simple algorithm for realistic pore network extraction from micro-tomography images. Journal of Petroleum Science and Engineering 123:164–171, 2014. doi:10.1016/j.petrol.2014.08.020. [14] I. Schenker. Quantification of the heterogeneity of particle packings. Physical Review E 80(2):021302, 2009. doi:10.1103/PhysRevE.80.021302. 108 http://dx.doi.org/10.1002/j.1538-7305.1961.tb03975.x http://dx.doi.org/10.1039/C5NJ03346B http://dx.doi.org/10.1007/BF01025983 http://dx.doi.org/10.4028/www.scientific.net/AMM.825.183 http://dx.doi.org/10.4028/www.scientific.net/AMR.1144.159 http://dx.doi.org/10.1007/978-0-387-36721-7_9 http://dx.doi.org/10.1103/PhysRevE.80.051305 http://dx.doi.org/10.1016/j.petrol.2014.08.020 http://dx.doi.org/10.1103/PhysRevE.80.021302 Acta Polytechnica CTU Proceedings 13:103–109, 2017 1 Introduction 2 Algorithm for tile generation 3 Simulations and discussion 3.1 Tile size and particle packing 3.2 Tiles with the same number of equal-size inclusions 3.3 Tiles with different number of equal-size inclusions 4 Conclusions Acknowledgements References