Generating a pseudo-random 2d noise texture

Let's imagine an infinite 2d grid (or more realistically, a very large grid, larger than what I can reasonnably keep in memory), and to each node of that grid, we associate an integer value. Every time we look at one particular node of the grid, we want the same value associated to that node. The values of the grid's nodes should follow a random distribution. At least, it should look random to the naked eye : pseudo-random. Let's call this function GridNoise.

When working with procedural content generation, say, procedural textures, GridNoise is an essential building block. The integer associated to one grid node can be used to generate information. Then, between the nodes of the grid, one can interpolate those informations. This is how value noise and Perlin noise works, for instance. Indeed, pretty much all procedural textures uses GridNoise at their core. However, I never seen a clear, consistent method to build something like GridNoise. Since GridNoise is a low-level, essential building block, one might want something without obvious defects. I introduce here my recipe to build such a GridNoise function.

The idea is use the coordinates of a node to build a key, and to hash that key with a hash function to get our integer. A good hash function will give us the pseudo-random distribution for the integer values. Or will it ? Let's take a look. I use Pearson hashing : it's a very simple hash function, fast to compute, it have good properties, and it's dead simple to code. Pearson hashing works on array of 8 bits integers. Here it is my implementation of Pearson hashing in Python, as a functor.

import random

class PearsonHash:
  def __init__(self, rnd=random.Random()):
    self.permut = range(256)
    rnd.shuffle(self.permut)
    self.seed = rnd.choice(self.permut)

  def __call__(self, array):
    h = self.seed
    for value in array:
      h = self.permut[h ^ value]
    return h

As you can see, because Pearson hash relies on a permutation table, it's not one single function, but a whole familly of functions ! So you can define plenty variant of it, you are not stuck with one single hash function. It's nice, we will be able to define different varieties of GridNoise.

Now, how to build a key from 2d integer coordinates ? Let's assume 16 bits coordinates (thus defining a 65536x65536 noise texture) for this example, it would be same with 32 bits. We can take the 16 bits of the X coordinate, the 16 bits of the Y coordinates, put them one after each other into a 32 bits value. 32 bits value, same as an array of 4x8 bytes values. If we have X=1011 and Y=0100, then the resulting 1d coordinate would be Z=10110100.

Let's try this ! Here it is an implementation in Python, assuming you have a Picture object

import array

phash = PearsonHash()
pic = Picture(512, 512)

tmp = array.array('B', [0] * 4)
for i in xrange(pic.h):
  for k in xrange(2):
    tmp[k+2] = ((i >> (8 * k)) & 255)
  for j in xrange(pic.w):
    for k in xrange(2):
      tmp[k] = (j >> (8 * k)) & 255
    pic.pixel(j, i) = phash(tmp)

Hum... It looks like white noise, but we can see some really nasty artifacts. You don't see it ? Let me show you that !

We can see vertical bands, 256 pixels wide. Each band looks noisy, but not so random, the bands have a distinct character. Not so random indeed... We can confirm what is just a visual test by something a bit more rigorous. If we try to compress this picture, throwing lot's of CPU time at this, we find out if there is some obvious repeating pattern. I used optipng for this : it reduced the picture data size by 90%... So our random data are not very random. Random data are data which most compact description are themselves. We did something wrong, but what ? Pearson hashing is innocent, it's a know, well-test hashing function. So the problem is with the way we built our key from node's coordinate. If we reverse X and Y in the 4 bytes array, it just turns the vertical bands into horizontal bands. It does not compress very well... Rotate this by 90 degrees, and suddenly, it become very easily compressible, also around 90% size reduction with optipng.

So we have to built our key completly differently. Struck by an Eureka instant, I got this intuition : use the Z curve ! The Z what ?!

The Z-curve is a space-filling curve, defining a map between 2d coordinates and 1d coordinates. The 2d coordinates are n n bits numbers. The 1d coordinate is a 2n 2n bits number, built by interleaving the bits of the 2d coordinates. If we have X=1011 and Y=0100, then the resulting 1d coordinate would be Z=10011010. The curve shown above is built linking the nodes by increasing Z. Here it is a naive implementation of the 2d to 1d conversion for the Z curve, assuming 16 bits per coordinates.

def mix(x, y):
  i = 0
  for j in xrange(16):
    i |= (x & 1) << (2 * j)
    x >>= 1
    i |= (y & 1) << (2 * j + 1)
    y >>= 1
  return i

Because of its shape, I believed that the Z curve would scramble those nasty patterns we got. It would give something that looks and feel much more like actual noise. The code to generate the picture becomes

import array

phash = PearsonHash()
pic = Picture(512, 512)

tmp = array.array('B', [0] * 4)
for i in xrange(pic.h):
  for j in xrange(pic.w):
    z = mix(j, i)
    for k in xrange(4):
      tmp[k] = (z >> (8 * k)) & 255
    pic.pixel(j, i) = phash(tmp)

And here it is a sample of what we get from this

No visible artifacts ! Using a clever & expensive compresser does not reduce the size at all ! We did it, we have a very good GridNoise function. For demonstration purpose, I used 16 bits coordinates for the grid nodes, thus GridNoise is a procedure 65536x65536 noise texture. If we use 32 bits, or even 64 bits coordinates, then we got a Universe-scale noise texture to work with. I might have overlooked some awfull flaw, I would be glad to know it if anybody notice that.

The approach generalize well to N dimensions. Z-order is defined in N dimensions : just interleave bits as we did for 2 dimensions. You might have a look here to see how to interleave bits efficiently. The Z curve can be replaced by any decent space-filling curve. However, the Z curve is maybe the cheapest to compute I know, while being close to the best ones I know, the Hilbert curve and the Peano curve.