From Checkerboard to Cloverfield: Using Wang Tiles in Seamless Non-Periodic Patterns

Year: 2016 Authors: Tuomas Nurmi

Core claim

A novel 30-tile Wang tileset with colored corners is the smallest known set that enforces both corner continuity and aperiodicity.

Topics

Wang tiles, aperiodic tilings, seamless patterns, corner continuity

Domains

tiling theory, aperiodic sets, domino problem, pattern design, computer graphics, texture generation, visual arts

Methods

tileset design, exhaustive search, edge matching, decorative overloading

Media

unit square tiles, parallelogrammatic frames, colored edges, colored corners

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

From Checkerboard to Cloverfield: Using Wang Tiles in Seamless Non-Periodic Patterns

Tuomas Nurmi

Abstract

This article discusses Wang tiles from an artistic point of view. Mathematically Wang tiles are unit squares with colored edges and a local rule saying that two edges may only be adjacent, if they have the same color. We will present some known methods to use and abuse this concept, ultimately to force aperiodic tilings of arbitrary size, optionally containing irregular tiles and continuity at the tile corners. This paper also introduces a previously unpublished aperiodic set of 30 Wang tiles with colored corners. This is the smallest such set known today.

Introduction

The concept of Wang tiles was introduced by Hao Wang in 1961*[7]*. They are used in computer graphics for tile based texture and pattern generation. This article introduces some methods to use them for artistic purposes even outside their usual field. Topics covered include altering the geometric shape of tiles, “over-loading” tile textures, tilesets that force non-periodic patterns, and tilesets ensuring any texture continues smoothly also across the corners, not just the edges.

Our ultimate goal is to introduce a novel 30 tile tileset that forces both continuity across the corners and aperiodicity over arbitrarily large areas, and to show a cloverfield texture generated with that set.

Mathematically, Wang tiles are topological disks, unit squares with labels – called colors – on their edges. A tile may also have decoration on its surface. A Wang tileset has a finite number of prototiles, but an infinite number of copies of any of the prototiles may be used in a tiling. A tiling is called valid if the following simple rules apply everywhere:

• Tiles placed next to each other have the the same color on their adjacent edges (like dominoes).
• Tiles are not rotated or mirrored.

A tileset is called valid, if the entire infinite Euclidian plane has a valid tiling.

For enhancing the readability in gray-scale media, the edge colors in undecorated tiles are marked with butterfly and flower shapes. For clarity most of the presented tiles are square.

Careful with the Corners!

We asked our topologist on duty if we could have some artistic license with the tile shape. He told that as long as a few conditions were met, he really couldn’t tell a difference from the unit square:

• Each tile has four edges and the edges only touch at the four corners, two at each corner.
• At each corner four tiles meet.
• Edges with matching colors have shapes that conform to each other seamlessly.

For generality, instead of unit squares, we’ll consider parallelograms (quadrilaterals that have their opposing sides parallel and equally long). More precisely, the corners of the parallelograms define a frame for our tiles

– the edges themselves don’t have to be straight lines. While a casual observer might not notice the similarity between some apparently hexagonal tiles and Wang tiles (see Figure 7), under this lisence it is possible to reshape the tiles extensively, maintaining the tiling and aperiodicity properties unaffected.

While at it, let’s toss out the colors. They are just a boring way to say that two tiles fit together like pieces in a jigsaw puzzle. So why not make them look like pieces of a puzzle? (Figure 2) Edge shape can effectively implement the color matching rule: Two edges have the same “color” if their shapes conform without gaps or overlays. Another common way to enforce the rule is to require continuous decoration across the edge. These methods can be combined so that the shape of the edge and any continuous decoration together define the edge color. However, regardless of how we actually implement the matching rule, we generally still talk about “colors”.

The length of an edge is a property of its shape. Under some conditions (e.g. Figure 7) this allows tiles with different sized parallelogrammatic frames in the same tiling. These sizes are row specific or column specific – they need not have the same dimensions everywhere, only for the subset of tiles that appears in that particular row or column. As long as we can find a way to match the corners of our tiles with such parallelogrammatic lattice, we are good to go.

Finally, it might get a bit boring to just repeat the same few tiles over and over again. The human visual system is an expert at spotting repetition, and with a finite number of tiles you are bound to have some. A simple solution is to overload some tiles: i.e. include two or more tiles with exactly the same edge colors, but different decoration. While tiling you may carry out your creative vision, or just pick in random.

A sample workflow for tileset design:

1. Decide what kind of properties you want from the tiling and color the edges accordingly. While at it, pick sizes for the frames.
2. Treat each color as an area extending to both directions from a frame edge, and design its decoration.
3. Cut the edges along any non-intesecting curve from frame corner to frame corner within the design area. You may think of the results as pairs of colors and anti-colors.
4. Combine the designed colors into your tiles and design tile decorations that blend smoothly with those made for the edges. You may alter any already made decorations, just stay off the edgeline.

Let’s look at some examples. In Figure 1 we see the simplest possible tileset: a single tile with a single color. It implements the P1 wallpaper symmetry group – a good start. The checkerboard in Figure 2 demonstrates two important points: 1) Colors are dimension specific. 2) Shape is a very effective way to enforce also the no-rotation no-mirror rule.

The tileset in Figure 3 is more interesting. First, it is not valid: No tile fits under tile A, but it can’t be left out either, because it is required to the left of B or C. Thus the plane cannot be tiled with this tileset. However, you may find it useful for making one-dimensional friezes. Second, it is overloaded: tiles B and C have identical edge colors, but different decoration. Next to the tiles with the simple colors are examples decorated with clovers. Note how tile C is used as a drop-in replacement for B to spice up the frieze.

In Figure 4 we have a non-trivial tileset that can tile the plane. This set will force a checkerboard pattern of As and Bs, but with an interesting property: they have alternating colors, forcing a brickwall pattern. Tile B has been overloaded, with a noteworthy side-effect: while the edges match perfectly everywhere, the petal formation at the corner of the tiles breaks at tile C.

Figure 5 presents a comprehensive set over two colors. These will not force any configuration, quite the opposite: you can always find a fitting tile for any spot. It may be useful in some texture generation tasks, where you have a simple binary condition for the edges, like in maze design.

From Checkerboard to Cloverfield: Using Wang Tiles in Seamless Non-Periodic Patterns

Figure 1: P1 - tile. Many pattern artists seem to find this type of tiling very fascinating.

Figure 2: Checkerboard: two topological disks with four corners, one black, one white, colors can only alternate in the rows and columns.

Figure 3: A set of frieze tiles.

Figure 4: Clovers in a brick-wall pattern.

Aperiodic Tilesets

When Hao Wang first devised his tiles, he asked a very simple question: Given a set of tiles, is there a way to tell whether it can tile the plane? This became known as the domino problem. As often happens, simple questions turn into difficult research questions. His student Berger was able to answer to the question – in the negative*[1]*. The naive algorithm is to keep building ever growing areas until you either find an area with no valid tilings, meaning that the tileset is invalid, or the pattern starts repeating, meaning that it’s periodic. Berger was able to show that there is a third option: there are tilesets that admit a valid tiling of the plane, but ensure that no P1 symmentry groups appear. Because they only allow non-periodic tilings, they are called aperiodic tilesets.

The first such tileset had 20426 tiles*[1]. The number has been cut down several times. The latest development from 2015 is a set of 11 tiles over four colors, which was shown to be minimal both in terms of tiles and colors[3]*, so the search for the smallest aperiodic Wang tileset is over.

There are some important things artists should know about these tilesets.

1. They are sets of Wang tiles, so the methods presented above for manipulating the shape of the tile may be used. Overloading tiles in an aperiodic tileset will not make it periodic. Adding a tile with a new color combination on the edges might.
2. It is guaranteed that it is possible to tile an area of any size or shape with these tiles. Exactly how to do that depends on the tileset. In some cases it can be tricky. In some cases some tiles may have a very limited set of possible neighbours. Removing tiles from a set will most likely lead to an invalid tileset.
3. It is guaranteed that the tiling will be aperiodic. However, this is different from the tiling looking “random”, “organic” or “chaotic”. Tilings may have patterns that keep repeating infinitely many times, perhaps even periodically, but all of the patterns will never have a common period.

If you are simply interested in using Wang tiles to make patterns that do not repeat too soon, you might be better off with some periodic tileset, possibly overloaded, and a proper stochastic algorithm, as suggested by [2]. If you are interested in designing a repeating pattern (P1 symmetry), the aperiodic sets are not for you. However, if you settle for nothing less than pure aperiodicity, look no further.

Let’s look at one such set in more detail. According to our computer simulations the small 14 tile set by Kari*[4]* in Figure 6 admits significantly more patterns than the other small aperiodic sets, even at small patch sizes. This means more room for artistic expression, while not sacrificing the aperiodicity.

This tileset is split into two classes based on the colors on their vertical edges: Tiles A-D can only appear on the same row, no other tile can appear on that row. We will “abuse” that property in the decorated version (Figure 7) to construct a hexagonal Wang tile. Please note:

• The color represented by a empty horizontal edge (like the top edge of tile A) has empty decoration.
• The hexagonal shape of tile C is forced by the flower pattern. It cannot be cut straight from corner to corner. However, the extra “corners” are not topological corners, but in the middle of edges.
• Tiles A–D have different a grid on their row than the rest of the tiles.
• Tiles A, D, H and I all have the same color on their south edge, originally designed as an area. Tile D demonstrates that at the end of the day the edges are just lines.
• It is possible to generate an arbitrarily large field covered with these clovers, but only aperiodically.
• For cosmetic purposes the entire tileset could be rotated by rotating each tile individually.

From Checkerboard to Cloverfield: Using Wang Tiles in Seamless Non-Periodic Patterns

Figure 5: Comprehensive set of Wang tiles over 2 colors.

Figure 6: The 14 tile aperiodic set by Kari.

Figure 7: Decorated aperiodic set. Order of tiles same as in Figure 6.

Fuzzy with the Corners

Our quest for non-periodic seamless tiles is not yet over. We still have some glitches:

• While we may be able to take care that individual tiles do not appear too regularly, in each row or column we are bound to have the tile frame corners at regular intervals. If we leave them empty, they may form a visual pattern the eye will eventually notice – even if we use the tricks introduced so far.
• While the tiles are guaranteed to be seamless at the edges, we have little control over what will happen around the corner. Consider the glitch introduced by the replacement tile in Figure 4.

These problems arise from a common source: the tile corner is a singular point. Let’s remove that condition. Lagae*[6]* suggested a variant of Wang tiles with colored corners instead edges. The respective local rule is that tiles touching each other at any corner must have the same color where they touch. These new tiles are a subset of common Wang tiles: on every horizontal (or vertical) edge we have an ordered pair of corner colors, and when we replace that with a single color, we have ordinary Wang tiles. Thus we have the same freedom with their shape, but the edges between the same corner colors must always have the same shape. If edge colors are independent of the corner colors, we have a new Wang tile variant, a hybrid of edge and corner variants with properties from each. To our knowledge such variant has not yet been formally defined, but see [2] for related work.

The fundamental difference between tiles with colored edges or colored corners is that the edge color is essentially a line with two sides that match each other snugly, but are not the same, while the corner color is an area where the decoration is the same in all four tiles. It doesn’t matter where you cut the edge within that area. You can even implement the corner colors by geometry: cut the edges inside the area defined by a given corner color in a way that is unique to that color.

Let’s look at a design example. Figure 8 shows a sample grid of 9 tiles. Clearly distinguishable symbols A, B, X and 5 decorate the corner areas. Note that the grid is parallelogrammatic, with some tiles having irregular edges. The eastern edges of tiles 1 and 3 are required to be identical. Actual tiles are on the right. When decorating the tiles, it is forbidden to modify the contents in the corner color areas.

Wang tilesets with colored corners are Wang tilesets, so we may pose the domino problem. Starting from existing aperiodic tilesets, aperiodic tilesets with colored corners have been constructed, the smallest of them with 44 tiles*[5]*. Using exhaustive search in that tileset we were able to identify and remove tiles that cannot appear inside even small valid patches, reducing it to the 30 tiles in Figure 9. Figure 10 shows a decorated version of the tileset, and Figure 11 our ultimate goal, the aperiodic cloverfield with seamless corners.

Conclusion

Wang tiles are a versatile tool for designing repetitive patterns, both periodic and aperiodic. Their usefulness arises from their ability to define locally which tiles may be next to each other, and from their ability to be shaped in many forms. It is possible to ensure that decorations flow smoothly across corners as well as over edges. This paper describes several ways to use them effectively and creatively for tiling-based pattern and texture design, and presents two tilesets that can be used to design only aperiodic patterns.

Presented aperiodic 30 tile tileset with colored corners is novel, and to our knowledge the smallest one known to date.

From Checkerboard to Cloverfield: Using Wang Tiles in Seamless Non-Periodic Patterns

Figure 8: Constructing a Wang tileset with colored corners.

Figure 9: 30 tile aperiodic Wang tile set with colored corners over 6 colors.

Figure 10: Decorated set of aperiodic corner tiles. Order the same as in Figure 9.

Nurmi

Figure 11: Cloverfield. Sample tiling by the set in Figure 10.

References

[1] R Berger. The undecidability of the domino problem. 1966. (document) [2] Michael F. Cohen, Jonathan Shade, Stefan Hiller, and Oliver Deussen. Wang Tiles for Image and Texture Generation, 2003. (document) [3] Emmanuel Jeandel and Michael Rao. An aperiodic set of 11 Wang tiles. CoRR, abs/1506.0, 2015. (document) [4] Jarkko Kari. A small aperiodic set of Wang tiles. Discrete Mathematics, 160(1-3):259-264, 1996. (document) [5] A Lagae, J Kari, and P Dutre. Aperiodic sets of square tiles with colored corners. Report CW, 2006. (document) [6] Ares Lagae and Philip Dutre. An alternative for Wang tiles: colored edges versus colored corners. ACM Transactions on Graphics (TOG), 25(4):1442-1459, 2006. (document) [7] Hao Wang. Proving theorems by Pattern Recognition II. Bell Systems technical journal, (40):1-41, 1961. (document)