Wang Tile Tesselation based on Image Quilting

By Kennedy Owen

Summary
Rationale
Game Implementation
Terminology
Algorithm
Results
References

Summary

This project implements the Wang Tile tesselation algorithm. Given a set of Wang tiles formed from a quilted image, the tiles are placed aperiodically to form a background for a simple 3-match game implemented with HTML5, CSS and JavaScript using DOM development. The game is called Jewel Warrior, and is derived from Jacob Seidelin's book HTML5 Games: Creating Fun with HTML5, CSS3, and WebGL.

Rationale

So, why a game? The author is very interested in game development and wanted to learn how to create HTML5 games using CSS and JavaScript. Incorporating image texturing into the game was a way to integrate computer graphics into the process of learning game development for the web.
Part of the project was to incorporate image quilting translation to Wang tile creation. Unfortunately, due to time constraints only the tiling portion was implemented, and thus tiles are required input. The image quilts and Wang tiles are generated using Robert Burke's C# implementation.

Game Implementation

The game implementation with Wang tile backgrounds can be found and played here. It is set to a particular tile scheme and tiles according to the algorithm described below, but can be changed in scripts/game.js to tile with a different scheme as well as tiling randomly (look for commented out lines of code). Note: Make sure to play this game hosted online. If you play it locally (URL starts with file:// in the browser), the game will not work due to the way the game saving and loading works. A permanent hosted version of the game can be found here.

Terminology

Note: Please see the reference papers listed below for more detail and image examples of the following terms.

Image quilting

Image quilting is the process of acquiring samples from a basic image. Patch samples of a base image are compared side-by-side. A boundary cut is made inside the overlap of the two samples and stitched together based on specified color matching at any given pixel in the overlap. This process is repeated until enough patches are stitched together to form a natural quilt-like texture.

2. Wang tiles

Wang tiles or Wang dominoes are a property that consists of special labels to each of the 4 edges in a square image. They are used to create realistic-looking automatic, aperiodic texture backgrounds through the matching of edges on adjacent tiles. The idea behind matching two edges in adjacent tiles is that the image formed by those two tiles will look more realistic and natural, rather than choppy or full of seams. This seamless tiling provides a mechanism for forming endlessly large textures composed of few tiles drawn at the appropriate matching locations.
Wang tiles can be generated from quilted images. The process involves taking four sample diamond-shaped subimages from a quilted image, for each Wang tile to create. The four subimages are compared and stitched together in an "X" pattern to form a larger diamond-shaped image. A Wang tile is cut from a square formed by connecting the middle of each edge of the larger diamond image. It is not uncommon for the "X" pattern to be decently visible in any given resulting Wang tile. Below is an example of a set of 12 Wang tiles produced with this technique, from a quilt generated from a given patch (see the patch and quilt image here):

Algorithm

The Wang tiles algorithm consists of two phases: edge labeling and edge matching. This implementation uses 12 Wang tiles. For each tile, the four edges are labeled using four indices (e.g., the north edge could be 0, the east edge 3, the south edge 1 and the west edge 0). The labeling used for this implementation is as follows:

Tile #   NESW
-------------
Tile 1:  0312
Tile 2:  1302
Tile 3:  0203
Tile 4:  1013
Tile 5:  0310
Tile 6:  1200
Tile 7:  0012
Tile 8:  0002
Tile 9:  1003
Tile 10: 0213
Tile 11: 1210
Tile 12: 1300

The edge matching algorithm stores tile numbers (referred to as indices) into an array that represents which tile is drawn at any particular place in the image. It uses a class that represents the four labels of a given tile to compare the tiles based on the indices chosen. The algorithm is as follows:

1. Select a random index for the first tile spot in the first row, and store it in the index array.

2. Select a random index for the second tile spot in the first row. Compare the east label of the first tile in the row, to the west label of the second tile in the row. If they do not match, select a new random index for the second tile spot in the first row and compare again. When a match is found, the index is stored in the index array.

3. Repeat step 2 to tile the entire row, comparing the east labels of tile (x - 1) in the row, to the west labels of tile (x) in the row.

4. Select a random index for the first tile spot in the second row. Compare the south label of the first tile in the first row, to the north label of the first tile in the second row. If they do not match, select a new random index for the first tile spot in the second row and compare again. When a match is found, the index is stored in the index array.

5. Select a random index for the second tile spot in the second row. Compare the following:
    a. The south label of the second tile in the first row, to the north label of the second tile in the second row.
    b. The east label of the first tile in the second row, to the west label of the second tile in the second row.
If both do not match, select a new random index for the second tile spot in the second row and compare again. When a match is found, the index is stored in the index array.

6. Repeat steps 4 and 5 for additional rows, comparing the following for a given tile (x, y) in any given row:
First tile in the row:
    a. The south label of tile (x, y - 1), to the north label of tile (x, y).
Any other tile in the row:
    a. The south label of tile (x, y - 1), to the north label of tile (x, y).
    b. The east label of tile (x - 1, y), to the west label of tile (x, y).

NOTE: Additionally, for each tile spot in the texture, the algorithm prevents the adjacency of tiles chosen for the spot that are exactly the same as the tile(s) it is compared against.

Results

Brace for many pictures and explanations!

The first step is to produce image quilts from a sample patch. Below is a sample patch (left) used to create a larger image quilt (right):

The second step is to produce Wang tiles from the quilted image. Below is the set of 12 Wang tiles produced from stitching together four diamond samples and then cutting out Wang tiles from those shapes:

Note that the image quilting program I used to generate the quilts creates artifacts around the edges of the quilt, but this is sidestepped using the Wang tiler from the same source.

The final step is to tile the Wang tiles to create as large an image texture as desired. Below is the final result in the game, which tiles with 15 rows and 10 columns with each Wang tile being 32 pixels x 32 pixels:

Note that each time the game is loaded, the texture tiling is different due to pseudo-random tile selection.

Of course, a comparison between absolute random tile selection and Wang tile selection is inevitable, as seen below:

Ick. The fully randomized tile background is terrible, choppy, full of seams and just plain unappealing. Then again, the Wang tiles were designed specifically for Wang tile tesselation, and at least some of the tiles match up occasionally. Imagine how awful a texture with totally random tile samples (not Wang tiles cut from image stitching) would look like...

Other examples aside from flowers follow.

Gems (definitely more fitting than flowers for a game called Jewel Warrior)

Original image:

Patch:

Quilt:

Wang tiles:

Final result:

The program samples lots of blue for the Wang tiles. Unfortunately, the resulting pattern makes the game's blue jewels difficult to see.

Cyberworld

Original image:

Patch:

Quilt:

Wang tiles:

Final result:

Cyber (interesting fact about this one: two applications of quilting created a more aesthetically pleasing set of Wang tiles than the first application of quilting)

Original image: