Thursday, January 3, 2013

Introduction to Wang Tiles

This is guaranteed to be a very colorful post.

Since the early days of computer graphics, texturing has been the favorite method to bring detail into 3D surfaces.

The problem with textures is they take a lot of memory. While there are some attempts to have 3D worlds uniquely textured, like Id's Rage, the traditional approach remains to tile a smaller rectangle of texture across a much larger 3D surface.

This certainly does the job, but it also brings out these repeating patterns we dislike so much. There are a number of ways to mask the repetition, sometimes by blending more than one texture, or by adding splats of unique detail in strategic places.

Another approach is to use Wang tiles. If they are new to you, once you are done reading this you should Google them up and get soaked on what they are and how they work. You will love learning about this. It will expand the way you look at problems in the future. Wang tiles are much more than just a method to avoid repeating textures. You could use them to generate terrain, geometry, architecture. If you get carried away, you'd see they are actually full fledged computing devices on their own.

You could say we have used them already without knowing, as the traditional way we tile textures is one specific case of Wang tiles.

But forget Wang tiles for a moment. The way you would normally texture a brick wall is to use a 2D image and let the GPU do the tiling. If you just take a picture of a brick wall in real life and use it, you would see there are very noticeable discontinuities where the edges meet. The colors on the North edge of the image do not connect properly to the colors in the South edge, and the same happens with East and West.

This is very noticeable in the following polka dots texture:


This is easily solved by making the texture "seamless". What it involves is to make sure the West and North edges match the East and South edges respectively. In most cases this is done manually, using a tool like Photoshop.

Here you see the fixed texture:


Problem solved. But this texture still has very noticeable repeating patterns. If you tile it long enough they are hard to miss.

Here comes the twist. We made this texture work by making sure edges connected properly. We have one edge that is shared horizontally, and another one that is shared vertically:

So what is inside the tile does not matter as long as the edges connect properly. Instead of just one texture we could use several, all sharing the same edges. Here is an example:


We could pick which tile to use randomly. This will eliminate the repeating patterns coming from the center area of the tiles. But we would still have some repetition coming from the edges.

Here enters Mr Hao Wang. He predicted what we are about to do was not possible, and for being wrong this method bears his name. In reality he did all the heavy work so it is more than deserved. Here is a picture of Hao Wang winning the 20 Km men's race in Chihuahua:


Actually that is not Wang, but it is the spirit what counts.

Wang tiles allow us to have more than just one vertical and one horizontal border. You can choose to have as many as you want. As soon as you know how many different borders there are, the method tells you how many tiles you need so you can tile them all you want without leaving any holes.

Let's say you choose to have two horizontal borders, blue and yellow, and two vertical borders, red and green. Here is a resulting set of 16 tiles:


This is what the tiling authorities call a "complete set", meaning it has all the possible tiles. It contains every combination of every combination of colors. This is how you would compute the number of tiles in a complete set:

Where N is the number of horizontal borders and M is the number of vertical ones. Hence 2 horizontal and 2 vertical make a set of 16 tiles. Now these numbers explode quickly. For 3 colors in each direction you now have 81 tiles. For 4 colors it would be 256 tiles. Four colors do not provide too much variation along the edges, still the number of tiles is huge. If you had to store this info in video memory it would be a problem.

Thankfully the math guys proved you do not need a complete set to achieve full tiling. A much more smaller set exists which can be created in the following way: For each combination of North and West colors, you need at least two tiles. Now the tile count becomes:

This is a lot more manageable. Two borders on each direction requires eight tiles. Four borders, 32.

Once you have your tile set, you can use it in different ways. When time comes to place them, there are a few simple rules to follow. You start from the top-left corner, North-West. At this point you can place any tile from the set, picking one at random will do.


The next tile you place must match the existing one. You can still pick a random tile, but its West side must match the East side of the previous tile. You can continue to do so for the first row:


When starting the second row, you will have to match the South border of the tile on top, in this case you can pick any tile in the set that has a green North.


And then for the rest of the row, you will find tiles that match both the North and West color requirements:


At this point you are ready to go on tiling forever:


While all this seems great and guaranteed to make you interesting at parties, the difficulties with Wang tiling are not in picking edge colors and using the sets. The real challenge is to come up with content for the tiles. In my case I had to resort to genetic algorithms running many instances over a LAN.

I will cover this in my next post.



13 comments:

  1. While Wang-Tiles are indeed quite beautiful, it is still not that easy to prevent recognizable patterns.

    One common problem of Wang-Tiles is visible in the example tiling of the Wikipedia article: http://en.wikipedia.org/wiki/Wang_tile
    In the image you see long "chains" of repeating color patterns. While the overall tiling is indeed irregular, the human eye nevertheless perceives a lot of repetitions.
    A good example to underline this point is the Penrose tiling: http://en.wikipedia.org/wiki/Penrose_tiling
    This is an aperiodic tiling but (at least to me) seems to contain a lot of repetitions.

    Furthermore, the horizontal and vertical lines that you highlighted in your second image tend to repeat themselves (possibly with holes), independent of the number of tiles you use.
    You would need to increase the N and M, but being realistic, N and M can be at most 5.

    The previously mentioned long chains of repeating pattern in the "2NM" Wang Tiling (which can be seen in the paper http://research.microsoft.com/en-us/um/people/cohen/WangFinal.pdf Figure 2d )
    can be solved by using the N^2 M^2 approach and choosing the tile in a stochastic manner.

    As we also considered using Wang Tiles, we are uncertain if they really provide an advantage. In order to realize the full potential, you need a lot of Tiles, which use memory that you could otherwise use for the actual texture. (Of course, Wang tiling is asymptotically better, but real applications need a realistic perspective ;)

    ReplyDelete
    Replies
    1. Yes, my next post in the Wang series is about dealing with these limitations and whether it is worth all the trouble at the end.

      I have seen some successful applications to texturing, but in every case a very skilled artist was involved. This is no different than creating good seamless textures.

      Check out this one made for Path of Exile: http://www.pathofexile.com/forum/view-thread/55091

      Your assumption that the tileset wastes memory that could be used by a larger texture is partially correct. Note that only the borders have repetition. The inside of the tiles can be unique. If the artist manages to minimize the border cuts into the tile centers there is not so much waste, and the decrease in periodicity is well worth the trade off.

      In the tutorial I linked before you can see the extent of the edges here: http://www.pathofexile.com/image/devdiary5/step8a.png

      It is not much. I think this game looks great thanks to these textures.

      Delete
  2. Nice article. I actually made a map generator using Wang tiles before I even knew they were called Wang tiles. :)

    I took a more declarative approach to making sure the sides match though. Here's my write-up: http://rcfox.ca/declarative-content-generation/

    ReplyDelete
  3. This could actually be really useful for when I start a new project, thanks!

    ReplyDelete
  4. You certainly know how to leave your audience wanting for more :)

    Yet another excellent article, I await the next one.

    ReplyDelete
    Replies
    1. I thought I remembered something related to this and have looked it up: The Cicada Principle (http://designfestival.com/the-cicada-principle-and-why-it-matters-to-web-designers/ ). It can also be used to generate tiles that appear to be non-repeating (in reality they repeat, just not very often).

      It boils down to the fact that using prime numbers for coordinates in textures can generate variance very cheaply. It requires multiple textures with alphas on top of each other, not a single-layer one, but it seems another viable option.

      You can see some very simple textures on the Cicada Project page: http://designfestival.com/cicada/

      Delete
    2. Very cool stuff, thanks for the link.

      Delete
  5. That's rather amusing. I read Miguel's post, and went, "Oh, I better be sure to comment and tell him about the Cicada Project."

    Good to know I wasn't the only one who's seen that. I think it needs to get more use in procedurally generated content contexts.

    ReplyDelete
  6. I think I could actually feel your excitement while writing this post. I'm anxious to hear more! Don't leave us hanging for another 3 weeks though! ;)

    ReplyDelete
    Replies
    1. I second that! ;D

      Checking the blog several times a day for updates... ;)

      Always feels like xmas if there is one haha.

      Delete
  7. This might be a good source for ideas as well...
    [url]http://udn.epicgames.com/Three/TerrainAdvancedTextures.html[/url]

    ReplyDelete
  8. I suppose you already know about the "corners" extension to Wang tiles, right ?

    Just mentioning it in case you'd not have seen it...
    http://graphics.cs.kuleuven.be/publications/LD06AWTCECC/

    ReplyDelete
    Replies
    1. Yes thanks. I actually use them.

      The absence of links in this post is no accident. I did not want point to any specific solution yet, as this was more of an introduction.

      Delete