Perlin Noise Generation

Perlin noise (named for its inventor, Ken Perlin) is very similar in appearance to interpolated noise. But in the code, it couldn't be more different. It is a lot more complicated; it has gradient maps, dot products, stuff that will make your head spin. So why not use interpolated noise, if it is so much easier? Speed. Perlin noise is a pretty good amount faster than interpolated noise. So strap on your mental seatbelts, because we're in for a wild ride.

If you get confused by some of the math in this section, that is OK. Just skip over sections that you are having a difficult time with and come back later. The algorithms still work even if you don't fully understand why they do.

The first step in generating Perlin noise is to generate a gradient map. A gradient map is simply a map where each grid point contains a unit line (length of one) pointing in a random direction. Visually it would look like this:

To generate one, we simply iterate through all possible points, pick a random angle θ between 0 and 2π, set the gradient's x value to cos(θ) and its y value to sin(θ).
(notice the original implementation by Ken Perlin used a lookup table to generate the values which is fast, but that is a bit harder to understand so we use a gradient map in this tutorial. If you are interested in the algorithm with a lookup table, refer to LookupPerlinNoise in the srcs)

The next step is similar to interpolated noise. Given the x and y periods, find the four nearest gradients.

Here is where we get chucked off the deep end. A value is calculated for each of the four corners, based on the following equation:
value = gradient · difference;

Let's explain this one piece at a time.
The · is the dot product. Here is what it means:

Given two points v1 and v2, the dot product of the two points is:
distance(v1 -> origin) * distance(v2 -> origin) * cos(θ)
In this case we know that the gradient's length is always one, so that term drops out and we are left with:
distance(v2 -> origin) * cos(θ)

Next the difference. This is easier, it is simply the distance from the current pixel we're evaluating to the base of the gradient, if things are scaled to the top of the current period is 1 and the bottom is 0. Here is what it is for the topX-botY gradient:


Whew, the worst of it is past. Next, you take these four values you have and interpolate between them. The values for mu that we are going to use is the x and y coords of the current pixel that we evaluated for the difference vector ^^^^ put into this equation:
6x^5 - 15x^4 + 10x^3
The reason for that equation is beyond the scope of this tutorial, but let's just say it involves the calculus, bump maps, and artifacts. If you want more information about that, refer to this link: http://http.developer.nvidia.com/GPUGems/gpugems_ch05.html
For all the rest of you, let's just say that it works, and looks good. After you have interpolated, you set the current pixel to that value, and you should get something like the image at the top.

The reason the Perlin noise algorithm works is more simple to explain. The interpolation part should be obvious, interpolate to smooth the transitions. The part with the dot product is a bit more tricky. Whenever θ in the cos is less than π (180°), the cosine function approximates a line function with 1 at 0 and 0 at π/2 (90°), ignoring direction of the lines involved. That boils down to "the angular "distance" from the gradient line".

So basically the value of each of the corners for any given pixel is the angular "distance" between the gradient and the line to it's base, times the distance to the base of the gradient. Hopefully this will clear up a bit of the confusion.

That's it. You made it. Go buy yourself a "I survived a Perlin Noise explanation" t-shirt. If you have questions or want more info, please feel free to email me at "thefatgamer99@yahoo.com".
As always, here is an applet for you:

Controls:
Q = increase x period
E = decrease x period
A = increase y period
D = decrease y period
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/