Wang Tile Texture Stitcher

Computer Graphics

Overview

This project served as an experience into implementing a white paper on a computer graphics algorithm. My implementation is written in C++, which is what I was learning at the time. I thoroughly enjoyed the process of researching this algorithm and deconstructing the moving parts that needed to come together to put together this proof of concept. My implementation is far from perfect, but I am pleased with having put together a functioning prototype of the tiling algorithm. The paper I referenced is from SIGGRAPH 2003 - Michael Cohen et al "Wang Tiles for Image and Texture Generation."

You can see the project on Github here.

Algorithm Breakdown

The algorithm begins by deconstructing an input texture into 4 quadrants, and creates 8 tiles out of these by rearranging the 4 cut pieces into different configurations. The pieces are quilted together using an image quilting method. I followed the suggestion of the paper in my implementation and did this by slightly overlapping the images to be quilted together, and calculating a least-cost-boundary cut through the overlap region that minimized the total pixel error of the overlapping region. For the following input image (which is 256x256 resolution image):

The 8 quilted images that were generated are as follows (each 235x235 in resolution):

From each quilt, we pull a central diamond shape to be the actual tile that is to be in tileset. The technical explanations for this are discussed at length in the paper. Getting pixel information from an image rotated 45 degrees proved to be very tricky when I was implementing this. Here is the pulled tileset that will be used to infinitely tile a plane:

Conclusion

Finally, here is the tileset in action. Although the Wang Tile algorithm is meant to alleviate repetitive textures, the banding and repetition is pretty present still. The tile set generated seems very uniform which may be a part of the problem, although they are constructed from different parts of the source image. I think more variation could be achieved by splitting up the input source texture into more than 4 blocks, and building a larger tileset from that. A bit of refactoring of my implementation could make this scale very nicely. This image is 775x775 pixels in resolution.

With some modifications, this implementation could serve as a good tool for up-resing textures.