Jump to content
  • Advertisement
Sign in to follow this  
george7378

n-dimensional noise generation

This topic is 1329 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi everyone!

 

I'm trying to make a Perlin noise program but I'm having a bit of trouble coming up with a good noise function. I'm trying to create 2D noise to start with. I'm using the default_random_engine from <random.h> to fill a 2D array with noise, like so:

//Generate random floats between 0 and 1
default_random_engine gen(0);
uniform_real_distribution <float> line(0, 1);
 
//Fill the array image[][] using the random generator
void fill_noise()
{
    for (unsigned y = 0; y < yres; y++) 
    {
        for (unsigned x = 0; x < xres; x++)
        {
            float shade = line(gen);
            image[x][y] = Vec3(shade); //RGB are the same to give grayscale value
        }
    }
}

This works fine but I'd like to create a noise function which gives me the same result for a given x and y coordinate in the image every time I call it, i.e. something like this:

float noise_2d(int x, int y)
{
    //Generate a random number between 0 and 1 which is always the same for a given x, y
}

I hope that's clear enough! So how can I use <random.h> to create such a function? Thanks a lot smile.png

Edited by george7378

Share this post


Link to post
Share on other sites
Advertisement
What you need is a hash function.

float noise_2d(int x, int y) {
  unsigned s = x;
  s ^= 0x7e13c211;
  s *= 0x96c9618f;
  s = (s << 16) ^ (s >> 16);
  s += y;
  s ^= 0x1225e2b4;
  s *= 0x5cc656a5;
  s = (s << 16) ^ (s >> 16);
  s ^= 0xd5a9017e;
  s *= 0x8e28457f;
  return s / 4294967296.0f;
}
That's probably random enough but it might be too slow. Give it a try.

Share this post


Link to post
Share on other sites

You could also try to do it by setting the seed of the RNG. For example, you could use the hash function given by Alvaro to set the seed (the default_random_engine seems to have a method to set it)

 

Using something simple like x*width + y might work fine too. (you can combine this with another value which is the same for the entire map or texture, this would be the seed of your map/texture)

 

This means that after setting the seed, youll get the same exact sequence of numbers every time. This is useful if you need more than one random number per coordinate. So instead of a single random number that is the same every time, you can get as many as you want and theyll be the same every time.

 

Im not sure if this has performance implications or if it causes issues with the distribution of the random numbers generated.

 

Something like:

void genStuff(x,y)
{
    gen.seed(hash(x,y))
    for 1 to 100
    {
        float random=line(gen)
        *Do fancy generation logic using random*
    }
}
Edited by Waterlimon

Share this post


Link to post
Share on other sites

Thanks for the replies!

 

Alvaro: I tried that and it works fine. It's quicker than seeding the RNG every time I call it. What is the reasoning behind that function? Can you recommend somewhere I can learn more about how it works?

 

Thanks again!

Share this post


Link to post
Share on other sites
The function Álvaro describes is a hash function. A hash function maps one input value (or set of values) to a value within a fixed range; ie, mapping a set of 2D, 3D or other coordinates to a single 8-bit, 16-bit, or 32-bit value.

Many hashing functions operate on the same principle as a Linear Congruential Generator (LCG) pseudo-random generator. In the past, many built-in random number generators for various systems have been implemented using an LCG. The idea of an LCG is to take some starting value (in fixed-state systems, the seed) and multiply it by some special number, then add another special number. If the numbers are chosen correctly, the output sequence appears to be random. When using an LCG to hash a value instead of store a seed as internal state somewhere, you pass the value into the function and use that value where the seed is normally used. The function then becomes a hash that maps this input state (seed) to a seemingly-random output value.

If the input is more complicated than a single value (such as a set of input coordinates) then the input values are commonly folded together into a single value, then that value is hashed to an output value.

Another commonly used tool when hashing integral values is the XOR operator. When you XOR two integral values, wherever the corresponding bits in the operands are different, a 1 bit is generated in the output value; otherwise a 0 bit is generated. By XOR-ing a value with some number, the effect is to sort of 'mix' the bits up in a predictable and deterministic fashion, with the output result having a seemingly-random appearance. This is the trick that Álvaro uses in places in his hash function.

The problem with XOR-ing alone, though, is that while at first glance the output might seem random-enough, there are in truth patterns generated in the output, and when doing Perlin noise you really want to avoid patterns. So the above hash function doesn't rely on a single XOR, but rather mixes XOR with LCG-like behavior (multiplying by specially chosen numbers) as well as some bit-shifting. The whole point of all of this is to get a really good mix or churn on the input bit pattern, and to hopefully remove any semblance of a visual pattern when the hash is used to generate noise.

If you study the reference implementation for Perlin noise, you can see a different form of hashing at work, one which uses a look-up table. Essentially you use the input value to look up a value in a table; the table is shuffled, adding an element of randomness to the look-up. Since look-up tables take up memory, the reference implementation folds the input coordinate state down so that it falls in the range [0,511] and the output hash is an 8-bit value in the range [0,255].

There is no one way to implement a hash. But a good way of understanding hashes is to study pseudo-random generator functions which use many of the same techniques that make for good hashes. (For example, see the list of generators created by George Marsaglia). Also do google searches for hash functions, which might turn up things like the FNV hash.

Share this post


Link to post
Share on other sites
What JTippetts said is right, but I'll add a little more about the code I posted specifically.

If you consider the entire set of 32-bit numbers, the operations "XOR with a constant", "multiply by an odd constant" and "rotate bits" are all permutations. In other words, they don't lose information. "Add a constant" could also have been used, which is different than "XOR with a constant" in the treatment of carry. Composing several "XOR with a constant" in a row is equivalent to a single "XOR with a constant". Similarly, for all the other operations: Several of the same type in a row are equivalent to a single transformation of that type. By combining operations that treat the 32 bits as representing an integer modulo 2^32 (multiplication and addition) with operations that treat them as just 32-component vectors over the field with two elements (XOR and bit rotation) you can create mixing of bits that is unlikely to follow any visible pattern. The bit rotations are important to avoid having weak randomness in the lowest few bits (a common problem with LCG generators, which isn't helped much by just XORing).

You can probably write something better using 64-bit arithmetic, which is very fast on modern CPUs. But what I wrote is not bad for 5 minutes of work. smile.png

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!