## Monday, June 4, 2007

### Fractal Tiles

Many game textures are designed to tile seamlessly. The left side matches the right and the top side matches the bottom:

Ye Olde Quintessential Brick Texture

What about more interesting ways of tiling? How about a texture that tiles with itself at different sizes on different sides? This could be used to generate a fractal so perhaps it should be called a fractile. Unfortunately it looks like that word's already in use.

I decided to try and make a texture that matches seamlessly with itself on the left and right; with quarter-size copies of itself along the top; and with a quadruple-size copy of itself along the bottom:

(When I'm doing texture mapping I like to use a texture with the letter R on it. It has no symmetries so it immediately tells me which way the surface is oriented.)

In the diagram above the boundary between tiles is a solid color, so they naturally match up seamlessly. Where's the fun in that, though?

This is more like what I had in mind:

Disc diameter and minimum disc spacing are functions of vertical position and vary by a factor of two from top to bottom.

This is how the texture tiles with itself:

I wrote a program to generate this texture. It first places as many discs as it can into the texture; then renders the discs to a bitmap. To place a disc, it picks a random spot, computes the radius based on the Y coordinate, and then checks the existing discs to see if there are any collisions. If not, it adds the new disc to the list. The loop stops after a few thousand tries.

There are a couple of keys to making sure the texture will tile.

1. When checking for collisions, make sure the proposed disc doesn't collide with any discs in neighboring tiles. These are just translated and possibly scaled copies of the central tile's discs. Note that the bottom edge must match against both the left and the right halves of the top edge, so the existing discs have to be transformed into both configurations.

2. Any discs crossing the top edge have to be duplicated in the left and right halves of the edge, since both halves have to match against the bottom edge. If a proposed disc's center is near the bottom edge, this will be taken care of by item #1; we check against the discs in the top left and top right. But if a disc overlaps the edge and has its center near the top, we need to generate a doppelgänger disc offset by half the texture width and test it for collisions as well. If there are no collisions, add both the disc and its doppelgänger to the list. You can see two discs that have doppelgängers in the example texture above.

To make a more interesting texture, I used the disc centers to generate a Voronoi diagram. Voronoi diagrams give a nice, cobblestony look, and everything connects together so the texture appears to be harder to create.

Obviously I've used much smaller discs in this case. Like everything else, the line width between Voronoi cells scales up by a factor of two from top to bottom. Here's how it tiles with itself:

The Voronoi-based texture was slightly trickier to produce. In particular, it's no longer sufficient to ensure that only discs crossing the top edge have doppelgängers, because there may be discs that don't cross whose Voronoi regions nevertheless do cross the edge. What we really need to ensure is that all the Voronoi edges crossing the top edge are identical in the left and right halves. To get around this, I used a bit of a hack: I generate disc doppelgängers whenever the disc center is in the upper quarter of the texture. This is overly conservative; you can see duplicate Voronoi regions that don't cross the top edge. It was very simple to implement, though, and the results don't look bad.

Here's the texture placed on a large disc:

The disc is built out of concentric rings. Each ring has twice as many copies of the texture as its inner neighbor:

I've purposely not shown the center of the disc. Things get screwy there. Ideally I'd probably want to co-generate another texture that was designed to fit into the center of the disc and match up with the other textures surrounding it.

The impetus for this is that I've been trying to figure out how to model and texture a 2D representation of a planet. Think of Lunar Lander and Moon Patrol combined together and placed on a disc instead of a flat world. Most of the action takes place on or above the surface of the planet, so you don't ever see the center of the disc unless you are zoomed out (as in the pictures above), and you need very fine detail at the surface.

It's been amusing to work this out. Now that I've seen it, I'll probably go in another direction, but who knows? You might find it useful or at least entertaining.

Have fun, and see you next week!