Aperiodic Tiling

Unfortunately the eye is extremely critical in the recognition of repeating pat­terns. It will always realize the periodicity of simple tiling, in particular with flat viewing angles, as is evident in the sunflower field from Fig. 8.10b. Here a tile with 160 sunflowers was iterated over the plane. Despite the large number of plants per tile, the repetitions are clearly recognizable. Tiling, which does not form a periodic pattern, provides the solution for this problem.

The question of whether an aperiodic tiling of the plane with a finite number of square tiles could be produced using a deterministic tiling rule was disputed in mathematics for some time. A first result was achieved in 1966 by Berger [14]. He used 20,426 tiles and proved for this number the aperiodicity, which contradicted the converse assumption of Wang in 1961. Later he found a set of 104 tiles, and Culik and Kari, independently of each other, reduced this number to 13 tiles [99, 106]. Stam [206] was the first who applied this kind of tiling to simulate textures in computer graphics.

In connection with the positioning of plants it is of less interest, however, whether tiling results from a stochastic process or not; therefore we speak of of a nonperiodic tiling, in contrast to an aperiodic tiling that cannot tile the plane periodically. The corresponding production algorithms need a tile set with the attribute that in the process of tile arrangement always at least two tiles are selectable from the tile set in order to join them to the already-existing ones. If this selection is performed at random, usually no periodicity will appear.

Подпись: boundary conditionsIn principle, two tiles can be distributed randomly over the plane without any periodicity. However, problematic in this method are the boundary conditions at the tile edges: since, in the case of two tiles, the own opposite side as well as the respective border of the other tile could lie on all borders of each tile, we would have two conditions that need be fulfilled.

These conditions, in combination with only two options for the selection of the tiles themselves, lead to visible structures at the tile borders that can only be made invisible by adding more tiles.

Aperiodic Tiling

Aperiodic Tiling

Figure 8.10

(a) Small group of plants on two tiles; (b) plant positioning with a periodic repeated tile of 160 plants, and (c) with eight nonperiodic repeated tiles of 20 plants each

 

Aperiodic Tiling

(c)

However, in addition, with an increasing number of tiles and arbitrary combi­nations, the number of boundary conditions increases also, which in the end results in ever more restrictive patterns along the tile borders. Therefore, it is necessary to limit the combination of tiles. This can be done using a color cod­ing of the borders: only borders with the same color may be aligned. if a suitable set of tiles are used, and if the point production is adapted accord­ingly, then the repetition effects can be significantly decreased, as can be seen in Fig. 8.10. In part (c) a plant population on eight tiles was generated, which is repeated nonperiodically.

How does this method work? In the above case of two tiles that can be com­bined arbitrarily, this would correspond to a color coding with only one color for vertical and horizontal borders (see Fig. 8.11a).

(a)

 

(b)

 

(c)

 

Aperiodic Tiling

(d)

 

Aperiodic Tiling

Подпись: (f) Figure 8.11

Tile set with color coding of the borders: (a) two tiles; (b) set of eight tiles with two horizontal and two vertical colors; (c) 12 tiles with two horizontal and three vertical colors;

(b) 18 tiles with three horizontal and three vertical colors; (e) sample tiling for set of subimage (b); (f) color-coded tiles on the plane, no repetition patterns can be recognized

If two colors each for horizontal and vertical borders are used, then four possi­ble combinations of colors result for a corner to which a new tile is to be set. Therefore at least eight tiles must be present in the tile set in order to always have the selection possibility (see Fig. 8.11b). In the case of two horizontal and three vertical colors 12 tiles are needed; for three horizontal and three vertical colors 18 tiles.

A nonperiodic tiling is generated by the following algorithm. In the first step a line of tiles is generated by successively adding tiles to an initial tile:

1. Choose a random tile.

2. Select a tile from the tile set with its west color corresponding to the east color of the already-selected tile and place it on its east side.

Now the following lines are generated by successively adding new tiles to the already-existing line. [9]

2. Select successively tiles with a south color that matches the north side of the tile below, and a west color that matches the east color of the selected tile in the previous step

In Fig. 8.11e a nonperiodic tiling of the plane is shown; in Fig. 8.11f all the tiles from the tile set are colored individually – the border colors are removed here – so that we can visually analyze the generated patterns.