Saturday, March 1, 2014

Midpoint Displacement Noise Generation

If you have done anything with Fractal Noise, you know that while it produces some of the best quality noise, it is insanely slow compared to its base functions. This is because it has to calculate a base array for every single octave. But then comes Midpoint Displacement Noise. It gives the same general look but at lightning speeds. Here's a benchmarch table from my machine:

  • Fractal Interp Cubic: 670 ms
  • Fractal Interp Linear: 245 ms (unacceptible quality)
  • Fractal Perlin: 125 ms
  • Fractal Lookup Simplex: 100 ms
  • Midpoint Displacement: 24 ms

It is so fast, it is on par with the non-fractal noise functions. This is the holy grail of fractal look-alikes.


MidDis noise is not perfect though. Here is a list of its pros and cons:
Pros:
lightning fast
looks like fractal
can be seeded (as in you can force it to produces mountains and other features where you want them)
by nature tileable

Cons:
not nearly as many ways to customize the result
can not be easily generated Multi-Threadedly (so fractal lookup simplex overtakes its speed at >=4 cores)
by nature tileable (may be bad in some cases, can be corrected with specialized seeding)
resulting noise may be dominated by a large mountain or valley in the center (can also be corrected with seeding)

Overall the pros far outweigh the cons. We will discuss minimizing the cons in more detail at the end.

The general idea behind MidDis noise is to start with the four corner values, and then set each value to the average of the nearby points plus a small offset. First we will discuss the "nearby points" concept. The process looks like this:
There are two variations of the averaging of neighbors step. One is the square step where nearby points that are on the verticies of a square are averaged (step 3 and 5). The other is the diamond step where nearby points that are on the verticies of a diamond are averaged (step 4 and 6).

For the random displacement, we take a noise value from a noise generator and multiply it by the amplitude for the iteration. The amplitude starts a some starting value and is multiplied by the persistance after every set of square and diamond steps.

For the diamond step, sometimes there are no values in a direction for it to use. Instead of have a bunch special cases (which are generally a bad programming practice), we just wrap any values that are outside of the bounds of the noise function to the other side. This also helps with the size. Ordinarily, MidDis noise requires an array with dimensions "2^x + 1" square. With wrapping, we have a bit more freedom. The array doesn't have to be a square, and the sizes can be any size in the form "2^x".

The actual code looks like this:
private void calculate(NoiseArray noise)
{
    //get whatever value of 2^i is greater than or equal to the max dimension of the noise
    int totalSize = fixSize(Math.max(noise.getWidth(), noise.getHeight()));

    int halfSize = totalSize / 2;
    double amplitude = startingAmplitude * persistance;
    while(halfSize > 0)
    {
        //do square step
        for(int x = halfSize; x < totalSize; x += (halfSize * 2))
        {
            for(int y = halfSize; y < totalSize; y += (halfSize * 2))
            {
                squareStep(noise, x, y, halfSize, amplitude);
            }
        }
        //do diamond steps
        for(int x = halfSize; x < totalSize; x += (halfSize * 2))
        {
            for(int y = halfSize; y < totalSize; y += (halfSize * 2))
            {
                diamondStep(noise, x - halfSize, y, halfSize, amplitude);
                diamondStep(noise, x, y - halfSize, halfSize, amplitude);
            }
        }
        halfSize /= 2;
        amplitude *= persistance;
    }
}
 
private void squareStep(NoiseArray noise, int x, int y, int halfSize, double amplitude)
{
    //skip pre-seeded values
    if(seeded && noise.get(x, y) != SENTINEL)
    {
        return;
    }

    double value = 0;
    //no need to wrap, NoiseArray handles that for us
    value += noise.get(x - halfSize, y - halfSize);
    value += noise.get(x + halfSize, y - halfSize);
    value += noise.get(x - halfSize, y + halfSize);
    value += noise.get(x + halfSize, y + halfSize);
    value /= 4;
  
    noise.set(x, y, value + ((gen.noise_gen(seed, x, y) - .5) * 2 * amplitude));
}
 
private void diamondStep(NoiseArray noise, int x, int y, int halfSize, double amplitude)
{
    //skip pre-seeded values
    if(seeded && noise.get(x, y) != SENTINEL)
    {
        return;
    }

    double value = 0;
    //no need to wrap, NoiseArray handles that for us
    value += noise.get(x - halfSize, y);
    value += noise.get(x + halfSize, y);
    value += noise.get(x, y - halfSize);
    value += noise.get(x, y + halfSize);
    value /= 4;
  
    noise.set(x, y, value + ((gen.noise_gen(seed, x, y) - .5) * 2 * amplitude));
}
To start it all you have to do is pick a starting value (0-1 most likely) and set 0,0 to it. (because of wrapping all the corners are actually at 0,0)

Now to discuss seeding. There is not to much difficulting involved in setting it up. Just set certain points to values that you want (for example setting the center point to much higher than the corner point would result in a mountain), and before setting any values you check to see if it has been set previously (aka is not some sentinel values such as Double.POSITIVE_INFINITY).

The reason this type of noise cannot be MultiThreaded easily is that it cannot be divided up into many small tasks that are independent from each other. This is unfortunate, but it is not as if MidDis noise is hurting for speed.

The tilable nature of this type of noise can be bad if you want to seed it to create details for a section larger terrain noise map. Luckily if you seed all of the edge values and turn off wrapping, you can get acceptible results.

To correct occasional cases in which the noise if either too flat or dominated by one large feature, you can seed some of the values from a smaller noise map of another type of noise.

That is it. It is really a pretty simple type of noise.

Here is a applet for you:
Controls:
S = new random seed
Shift = toggle color mode
Enter (downloadable version only) = save screenshot


If the applet doesn't load, trying refreshing the webpage. May not work on mobiles.

Demos: https://drive.google.com/folderview?id=0B_jXYEquMamINGVGQTM0cTJzdmM&usp=sharing
Source Code: https://github.com/f4113nb34st/Println/

No comments:

Post a Comment