Acta Polytechnica CTU Proceedings doi:10.14311/APP.2017.13.0162 Acta Polytechnica CTU Proceedings 13:162–165, 2017 © Czech Technical University in Prague, 2017 available online at http://ojs.cvut.cz/ojs/index.php/app WANG TILES LOCAL TILINGS CREATED BY MERGING EDGE-COMPATIBLE FINITE ELEMENT MESHES Lukáš Zrůbek∗, Anna Kučerová, Martin Doškář Department of Mechanics, Faculty of Civil Engineering, Czech Technical University in Prague, Thákurova 7, 166 29 Prague 6, Czech Republic ∗ corresponding author: lukas.zrubek@fsv.cvut.cz Abstract. In this contribution, we present the concept of Wang Tiles as a surrogate of the periodic unit cell method (PUC) for modelling of materials with heterogeneous microstructures and for synthesis of micro-mechanical fields. The concept is based on a set of specifically designed cells that compresses the stochastic mi- crostructure into a small set of statistical volume elements – tiles. Tiles are placed side by side according to matching edges like in a game of domino. Opposite to the repeating pattern of PUC the Wang Tiles method with the stochastic tiling algorithm preserves the randomness for reconstructed microstructures. The same process is applied to obtain the micro-mechanical response of domains where the evaluation as one piece would be time consuming. Therefore the micro-mechanical quantities are evaluated only on tiles (with surrounding layers of tiles of each addressed tile included into the evaluation) and then synthesized to the micro-mechanical field of whole domain. Keywords: Heterogeneous microstructures, Wang tiles, micro-mechanical fields, local tiling, finite element method. 1. Introduction The heavily increasing pressure to the materials ut- most performance leads to necessity of excellent under- standing of characteristic mechanical processes taking place at a microstructural level of materials. Therefore the numerical material models needs to incorporate also the micro-scale level. However, even though the materials may look like homogeneous from macro-scale view, the majority of materials used in engineering applications are heterogeneous with a stochastic mi- crostructure layout (Fig.1). For modelling of heterogeneous materials many methods exists, but the most widely used one is the numerical homogenization method [1]. Heterogeneous materials are modelled using the concept of periodic unit cell (PUC) or statistically equivalent periodic unit cell (SEPUC). The PUC approach is used for material with periodic patterns, where the modelled microstruc- ture is produced by duplication of a representative part of the original microstructure in cardinal direc- tions (see Fig.2). On the contrary the stochastic microstructures are modelled using the concept of SEPUC. In this case the unit cell representing the original microstructure holds the same properties given by statistical descriptors as the source one [2]. Nevertheless, this approach uses only a single cell to describe the whole material and the stochastic heterogeneous material is transformed into unwanted periodic pattern of the same cells. And to be able to study micro-mechanical quantities (e.g. stresses, strains or displacements) at micro-scale level we need to preserve not only its properties but also the stochastic layout. (a) (b) Figure 1. The appearance of the structure at different scales, a) homogeneous at macro-scale, b) heteroge- neous at micro-scale. (a) (b) (c) Figure 2. Modelling of periodic microstructure, a) periodic microstructure, b) PUC, c) reconstructed microstructure. 162 http://dx.doi.org/10.14311/APP.2017.13.0162 http://ojs.cvut.cz/ojs/index.php/app vol. 13/2017 Local Tilings from Merged Edge-compatible FE Meshes (a) (b) 1 3 5 7 8 Figure 3. Principle of Wang Tiles method, a) domino game, b) Wang Tiles. Preserving the randomness of the recreated material cannot be achieved with single cell. Hence the method utilizing the set of representative cells must be used. To be able to place these cells side by side, they must be specifically designed so they are mutually compati- ble on the edges. If this criterion is met the infinitely large material microstructure can be created with the use of simple algorithm. The resulting microstructure preserves stochastic distribution and the statistical description of the source media. The above described method is called method of Wang tiles. 2. Wang Tiles Method The basic principle of Wang tiles method was intro- duced by Mr. Hao Wang [3, 4] in the early sixties of the 20th century. The concept is very similar to the domino game. The objective is to construct a straight or zigzag line series of game pieces with a match- ing number of dots on the adjacent sides of touching stones (Fig. 3a). The Wang tiles method works nearly the same with only few differences. Instead of dou- ble coded rectangular domino pieces, the tiles are squares with four edge codes, colours in this case (Fig. 2b). And contrary of creating a linear series of game pieces the tiles are placed into four cardinal directions (north – N, south – S, east – E, west – W) and the two-dimensional area covered with tiles is produced. The tiles cannot be rotated or mirrored through the process of laying tiles as any of these two actions would create a new type of tile. The tiles are placed side- by-side according to matching edge codes until the desired size of area is completely created. The result is called tiling and if there are no missing tiles or unequal edge codes, the tiling is valid. 2.1. CSHD algorithm Except the condition that the tiling must be valid we also need it to be stochastic. That can be achieved by utilization of Cohen-Shade-Hiller-Deussen (CSHD) tiling algorithm [5]. If the creation of tiling is per- formed row by row, the most difficult position to place a new tile would be the corner position like in Figure 4. In this picture is shown the corner position where the north (N) and western (W) edges of new tiles must N W 1 3 4 8 2 6 2or ? Figure 4. Tiling process and valid tiles for the corner position. 1 2 3 4 5 6 7 8 Figure 5. Smallest Wang tiles set called W8/2-2. correspond with already placed tiles. Among other rules of the CSHD algorithm, the most important one is that it there must be at least two valid tiles (like tiles number 8 or 2 in the Fig. 4) for this kind of corner position. Then the new tile is randomly selected from these valid tiles and placed in the tiling. This creates another corner position and the process is repeated until the tiling of required size is created. The smallest set that complies the requirements of CSHD algorithm and has at least two distinct vertical edge codes and two distinct horizontal edge codes is set consisting of 8 tiles. We call this set W8/2-2 (Fig. 5) and we use it as a representative set in all further explanations in the following paper. 2.2. Design of Tiles When designing the set of tiles the process must ensure that the resulting tiles will satisfy the requirement of the CSHD algorithm and of course the tiles must hold the properties of the original microstructure. Couple of methods to design tiles can be used and one of them is based on multicriterial optimization of tile morphology according to statistical descriptors. The goal is to create tiles such as the recreated mi- crostructure share the same statistical properties as the original microstructure. However this process is extremely time and computationally consuming (days to weeks). Moreover as presented in the paper [6] with increasing pressure on optimizations all the tiles tend to become identical and the reconstructed mi- crostructure became visibly periodical. Another method called Automatic Tile Design [5] creates each tile by stapling four small samples (Fig. 5) cut out of the original microstructure in different combination. In addition is almost instantaneous if compared with first method. Completely different approach based on particles dynamics, movement and collisions inside of the in- terconnected tiles bounding boxes are using methods described in [7, 8]. These method can be used only for microstructures with distinguishable particles that can be described by simple geometrical shapes. 163 L. Zrůbek, A. Kučerová, M. Doškář Acta Polytechnica CTU Proceedings 1 3 2 4 1 2 3 4 a) b) c) Figure 6. Automatic Tile Design [5], a) cut-outs for stapling, b) stapling, c) new tile. 3. Micro-mechanical quantities The Wang tiles method can be used in many different fields like modelling of quasi-crystals and generating naturally looking textures for computer graphic [5]. Or as a substitution for the unit cell concepts (PUC and SEPUC) in material modelling. Or to obtain the micro-mechanical response for enrichment functions in numerous generalized finite element methods, e.g. [9, 10]. In our work, the following (numerical homogeniza- tion like) decomposition of a sought macroscopic field u(x) is assumed u(x) = uE (x) + u∗(x) (1) where u∗(x) is the microscopic fluctuation field syn- thesized by means of Wang tiles method and uE (x) is the macroscopic part solved by finite element method (FEM) with a sparse grid. 3.1. Simple synthesis The whole microscopic domain can of course be dis- cretized by very fine FEM mesh and evaluated to obtain demanded micro-mechanical fields like stresses, strains and displacements. But according to the fine- ness of the mesh and size of the domain, the evaluation time is rapidly increasing. The computational requirements can be diminished with the Wang tiles method as the process of mi- crostructure reconstruction can be applied to the micro-mechanical field. The micro-scale quantities are evaluated on individual tiles and then synthesized back according to the same tiling as the microstructure. However, as presented in the paper [11] the non-local character of mechanical quantities is causing disconti- nuities on tile edges and therefore the underlying grid of tiles is recognizable. That is because of the me- chanical response of each tile is affected by a different combination of surrounding tiles (Fig. 7). 3.2. Finite element meshes Furthermore, to be able to use the finite element method (FEM) as a solver brings another difficulty. Because the domain is represented by the tiles which are mutually compatible on the edges, the finite el- ement meshes created on the individual tiles has to fulfil the exactly same compatibility. Example of arti- ficially created edge-compatible finite element meshes on tiles are shows in the figure 8. 2 1 6 62 6 3 4 8 3 6 4 5 8 7 1 8 5 4 511 1 1 1 1 12 2 2 2 2 2 2 2 2 2224 4 4 4 4 4 4 8 8 8 88 8 8 3 3 33 3 3 5 5 5 5 55 5 7 7 7 7 7 7 77 7 6 6 6 6 1 6 m=3 Figure 7. Single layer of surrounding tiles (dashed squares) for different tiles with No. 1. 1 2 3 4 5 6 7 8 Figure 8. Mutually edge-compatible finite element meshes on tiles. 3.3. Local tiling Our attempt to solve this problem is to include these surrounding tiles into the evaluation of the mechanical response for each tile [12]. Therefore for every tile Ti (grey square in the in figure 9) from the macro tiling we create so called local tiling. This local tiling is rep- resented by the center tile Ti and the arbitrary number of surrounding layers of tiles taken from the macro tiling. Then the local local FE mesh is synthesized (see section 3.4) and the micro-mechanical quantity is evaluated. Because we need only the results for the centre tile Ti we crop the results of all surrounding tiles and save the results under label T285416148. This procedure is repeated for every tile Ti in macro- tiling and because these processes are not dependent, they can be solved using parallel computation. After results of all tiles are obtained, the micro-mechanical field is synthesized. 3.4. FE meshes merging tool As mentioned in section 3.2 the FE meshes on tiles must be mutually edge-compatible so they can be merged together into single FE mesh (e.g. local tiling FE mesh). To create the edge-compatible meshes 164 vol. 13/2017 Local Tilings from Merged Edge-compatible FE Meshes evaluated mechanical response 2 8 5 4 81 4 6 1 2 8 4 4 8 5 6 1 7 1 8 5 4 51 1 1 1 2 2 2 22 4 4 4 4 8 88 3 3 5 5 7 7 7 7 77 6 6 6 1 812 2 2 57 2 2 4 5 7 6 11 2854 61481 Figure 9. Local tiling process: macro tiling ⇒ local tiling ⇒ local FE mesh ⇒ evaluation ⇒ cropping results ⇒ results for tile Ti. Figure 10. Real adaptive mesh of tile. the software called T3D is used. Next the output from T3D must be loaded, sorted, renumbered, etc. For these purposes we are working on robust tool implemented in C++ language. In addition to above mentioned operations, the tool can already merge arbitrary number of tile meshes (without duplicate nodes or gaps in node numbering). Any created mesh can be saved to a file or loaded from file (once saved) and especially visualized using the VTK visualization tool-kit as an unstructured grid. The tool is capable to process any finite element mesh from simple (Fig. 8) to quite complex like on Fig. 10. The entire current work is devoted to implement the process described on figure 9 and on the effective storing and working with big volume of data results. 3.5. Future work Once the implementation of the local tiling process (see 3.3) is completed and we will be able to quickly generate results we are planning to implement some statistical descriptors, automatized call of T3D soft- ware or even tile design methods. Our main goal is to run sensitive analysis and determine the influence of characteristic microstructural lengths, tile size and number of necessary included layers in local tilings on the overall error of synthesized micro-mechanical fields. Acknowledgements The authors gratefully acknowledge the financial support from the Grant Agency of the Czech Technical Univer- sity in Prague, the grant No. SGS17/042/OHK1/1T/11 (Numerical Methods for Modelling Uncertainties in Civil Engineering) (L. Zrůbek, A. Kučerová and M. Doškář). References [1] F. Fritzen. Microstructural modeling and computational homogenization of the physically linear and nonlinear constitutive behavior of micro-heterogeneous materials, vol. 1. KIT Scientific Publishing, 2011. [2] H. Lee, M. Brandyberry, A. Tudor, K. Matouš. Three-dimensional reconstruction of statistically optimal unit cells of polydisperse particulate composites from microtomography. Phys Rev E 80:061301, 2009. doi:10.1103/PhysRevE.80.061301. [3] H. Wang. Proving theorems by pattern recognition–II. Bell System Technical Journal 40(1):1–41, 1961. doi:10.1002/j.1538-7305.1961.tb03975.x. [4] H. Wang. Games, logic and computers. Scientific American 213(5):98–106, 1965. [5] M. F. Cohen, J. Shade, S. Hiller, O. Deussen. Wang tiles for image and texture generation. ACM Trans Graph 22(3):287–294, 2003. doi:10.1145/882262.882265. [6] J. Novák, A. Kučerová, J. Zeman. Compressing random microstructures via stochastic wang tilings. Phys Rev E 86:040–104, 2012. doi:10.1103/PhysRevE.86.040104. [7] D. Šedlbauer, M. Lepš. Dynamic packing of stochastic wang tiling for heterogeneous material modelling. In Proceedings of the 20th International Conference on Computer Methods in Mechanics, pp. 447–448. 2013. [8] J. Stránský, M. Doškář. Stochastic wang tiles generation using the discrete element method. In Engineering Mechanics 2015, vol. 821 of Applied Mechanics and Materials, pp. 392–398. Trans Tech Publications, 2016. doi:10.4028/www.scientific.net/AMM.821.392. [9] J. M. Melenk, I. Babuška. The partition of unity finite element method: Basic theory and applications. Computer Methods in Applied Mechanics and Engineering 139(1):289–314, 1996. doi:10.1016/S0045-7825(96)01087-0. [10] T. de Freitas J.A. Formulation of elastostatic hybrid-trefftz stress elements. Computer Methods in Applied Mechanics and Engineering 153(1):127–151, 1998. doi:10.1016/S0045-7825(97)00042-X. [11] J. Novák, A. Kučerová, J. Zeman. Microstructural enrichment functions based on stochastic wang tilings. Modelling and Simulation in Materials Science and Engineering 21(2):025–014, 2013. doi:10.1088/0965-0393/21/2/025014. [12] L. Zrůbek, A. Kučerová, J. Novák. Synthesized fields fluctuations by means of wang tiles and local tilings. In Modern Methods of Experimental and Computational Investigations in Area of Construction II, vol. 1144 of Advanced Materials Research, pp. 178–183. Trans Tech Publications, 2017. doi:10.4028/www.scientific.net/AMR.1144.178. 165 http://dx.doi.org/10.1103/PhysRevE.80.061301 http://dx.doi.org/10.1002/j.1538-7305.1961.tb03975.x http://dx.doi.org/10.1145/882262.882265 http://dx.doi.org/10.1103/PhysRevE.86.040104 http://dx.doi.org/10.4028/www.scientific.net/AMM.821.392 http://dx.doi.org/10.1016/S0045-7825(96)01087-0 http://dx.doi.org/10.1016/S0045-7825(97)00042-X http://dx.doi.org/10.1088/0965-0393/21/2/025014 http://dx.doi.org/10.4028/www.scientific.net/AMR.1144.178 Acta Polytechnica CTU Proceedings 13:161–164, 2017 1 Introduction 2 Wang Tiles Method 2.1 CSHD algorithm 2.2 Design of Tiles 3 Micro-mechanical quantities 3.1 Simple synthesis 3.2 Finite element meshes 3.3 Local tiling 3.4 FE meshes merging tool 3.5 Future work Acknowledgements References