Tech Feature: Noise and Fractals

Introduction
Now that I have a working algorithm for terrain rendering, I wanted to try making some of it procedurally. This would not be used in order to generate levels, but instead to help artists add some extra detail and perhaps for some effects. The natural world is very noisy and fractal place, so in order a to get a nice looking environment, these two features are crucial.

Noise
When doing noise for natural phenomena, one normally wants some kind of coherent noise. Normal white noise, when nearby pixels are not correlated in any way, looks like this:

This is no good when one wants generate terrain and the like. Instead the noise should have a more smooth feel to it. To get achieve this, one fades between different random values, creating smooth gradients. A way to do this is to generate a pseudo-random number (pseudo because a certain coordinate, will always return the same random value) for whole number points, and then let the fractional parts between these be interpolations. For example, consider the 1D point 5.5. To get the value for this coordinate the pseudo-random values for 5 and 6 are gotten. Lets say they are 10 and 15. These are then interpolated and since 5.5 lies right between them, it is given the value 12.5 ( (10+15)/2 ). This technique is actually very similar to image magnification, where the whole numbers represent the original pixels.

Generating random numbers this way, something like this is gotten:


This looks okay, but the interpolations are not very smooth and looks quite ugly. This can be fixed by using a better kind of interpolation. One way to to do this is using cosine-interpolation, which smoothen the transition a bit.

This looks a lot better, but the height map image still looks a bit angular, and not that smooth. However, we can smooth it even further by using cubic interpolation. This ties nicely into the image magnification analogy I made early as cubic is a common type of filter for that. It works by not only taking into account the two points to blend between, but the points next to them as well. In our above example this would be the points 4 and 7 (which are next to 5 and 6). It looks like this:


This gives a much smoother appearance, but it (as well as the other algorithms above) has some other problems. Because the height values for each whole pixel are completely random, it is gives a very chaotic impression. Many times one wants a more uniform look instead. To fix this something called Perlin noise is used. What makes this algorithm extra nice is that it based on gradients instead of absolute values for each pixel. Each whole pixel is assumed to have the value 0, and then a gradient determines how the value changes between it and a neighboring pixel. This allows it to be much more uniform look:


Because of it is based on gradients, it also makes it possible to take the derivative of it, which can be used to generate normal maps (something I am not using though). It is also quite fast, pretty much identical to the cosine interpolation. The cubic interpolation, which requires more random samples, is almost twice as slow.


Fractals
Now that a coherent noise function is implemented it can be used to generate some terrain. The screens above does not look that realistic though and to improve the look something called Fractal Brownian Motion can be used. This is a really simple technique and works, like all fractals, by iterating an algorithm over and over. What is iterated is the noise function, starting off with a large distance between the whole pixel inputs (low frequency) and then using smaller and smaller distances (higher frequency) for each iteration. The higher the frequency the smaller the influence, resulting in the low frequency noise creating the large scale features and the high frequency creating the details.

The result of doing so can produce something like this:


Suddenly we get something that looks a lot more like real terrain!

There is lots of stuff that can be done with this and often very simple alteration can lead to interesting results. Here is some iterated fractal noise that as been combined with a sine-function afterwards:


End notes
There is a lot more fun stuff that can be done using noise and I have just scratched the surface with this. It is a really versatile method with tons of usages for graphics. The problem is that that it can be quite slow though and my implementation will not be used for any real-time effects. However, Perlin noise can be simulated on the GPU, allowing it for realtime usage, and this is something I might look into later.

Next up is the hardest part of the terrain rendering - texturing! I am actually still not sure how to do it, but have tons of ideas. Can never get enough of info though, so if anybody know any good papers on terrain texturing, please share!