Saturday 10 February 2018

Randomness and Perlin Noise

In the book we explore randomness as an important tool for creating algorithmic art. We later show how pure randomness sometimes isn't what we want, and introduce Perlin noise. We explore several ways Perlin noise can be used, but we don't dig into how it is actually created.

In this post we'll look briefly at how such useful noise is created.


Randomness v Noise


This is pure randomness.


The heights of the lines are completely random between a lower and upper limit. If we wanted to simulate a landscape of hills and valleys, peaks and troughs, then this clearly doesn't work. It doesn't look natural at all. The main reason is that the jump up or drop down from any given point is unnaturally large in too many cases.

What we want is for nearby points to have similar heights so that the transition is fairly smooth. From a distance, the heights can be random, in the sense that they are hard to predict. But close up, a height value and the one next to it need to be similar. This relationship between consecutive values means the values aren't totally random, because total randomness means no relationship at all between values.

What we've just described is often called noise - to signal that, unlike pure randomness, the values conform to some kind of rule.


As a landscape this looks much more realistic. At larger scales, the heights are not predictable. But at small scales, consecutive values are similar, so the heights change more smoothly.

Noise isn't restricted to one dimension, algorithms exist for noise in 2, 3 and even more dimensions. Here's the kind of image you can create with two-dimensional noise.


How is this really useful noise created?


Value Noise

Thinking about how there is a smooth transition between consecutive noise values immediately suggests a simple method for creating noise.


The idea is that we do use pure randomness to create values that are spaced apart at regular intervals. These random values are shown as red dots in the picture above, placed at every whole number. If we want a noise value at x, we interpolate between the random value just above and below x, unless x falls exactly on a whole number.

This approach gives us what is called value noise. It does solve the problem of making sure that nearby noise values are similar.

But there are two things about this kind of noise that can be undesirable:

  • There are sharp changes at the regularly spaced points where the purely random values are placed. In the picture above, noise values will increase up to x=2 but then suddenly change direction just after x=2. This discontinuity isn't always desirable.

  • Because the red dots are truly random, it is entirely possible that we get a group of them with similar values, all high, medium or low, which would result in interpolated noise which didn't change much at all. We could also have a series of alternating very low and very high values, with would result in noise values changing very rapidly. What we're saying is that the frequencies in this kind of noise can vary a lot. We might prefer noise with a narrower band of frequencies - so that the shapes in it are roughly of the same kind of size.


A common way to alleviate the first problem is to change those straight green lines so that they join at the red dots in a smooth continuous way - with no abrupt changes. This is called smoothing, or blending.


We can use any mathematical function that maps a regular linear sequence into an s-shaped curve. Some people use variants of the cosine function. Others use polynomials.

Smoothed value noise can be useful, but not if the frequency content needs to be more constrained - as it is in many natural phenomenon. If you looked at the frequency content of the patterns made by wood textures, turbulent water, rocky landscapes, fluffy clouds, you'd see the distribution was mostly constrained into limited ranges.

So another method is needed to fix the frequency issue.


Gradient Noise

Instead of having a single random value at equally spaced intervals, another approach is to use a vector pointing in a random direction. The following picture shows this idea. Those random directions are actually one unit in length - they're unit vectors.


Just like before, we find which two regularly spaced points a given x sits between. Then instead of interpolating between the random values at the those two points, we take the dot product between the random vector and the vector from the interval point to x, shown as a blue arrow above. We do this for both unit vectors on either side of x.

A dot product is simple to calculate, and is:
  • maximally positive when the two vectors are facing in exactly the same direction
  • maximally negative when the two vectors are facing the exact opposite direction
  • zero when then two vectors are perpendicular

The dot product of two vectors a and b is a.b.cos(angle) where a and b are the lengths of the vectors, and angle is the angle between them. Because our random vectors are unit vectors, and the blue vectors to x are never longer than 1, the dot products also cannot be less than -1 or larger than +1.

It's worth noting that when x is on top of the interval points, the blue vector is of zero length, so the dot product is zero. This is important because it forces the noise to be zero at every interval point. In effect it is pinned down at these regular points, and so the noise is forced into a narrow frequency band.

Finally, all we have to do is combine the dot products by interpolating them. Using a linear interpolation with smoothed distances is still effective. Ken Perlin himself recommended a smoothing function 6x5-15x4+10x3, which has a zero derivative at 0 and 1 which means any discontinuities are smoothed off. Even better, it has a second derivative of zero at 0 and 1 which makes the noise even smoother.


And that interpolation of dot products is the Perlin gradient noise.

A Python notebook demonstrating this idea is online at GitHub.  Here's an example output. The green circles mark the regular intervals at which the random vector were placed, in this case at every whole number.


Some observations:
  • The noise is smooth, which is what we intended. 
  • The absolute magnitude (heights and depths) are also limited to a range because the dot product is limited by the magnitude of the unit and blue vectors. In this example, the blue vectors are never longer than 1, so the overall noise limits are [-1, +1].
  • The frequency is also limited to a small range, sometimes called bandwidth-limited. This means the shapes in the noise aren't too big or too small. This is enforced by the zeros in the noise, marked by the green circles. 

That last point is really important. The highest frequency can only happen when the value changes sign between the regular intervals marked by green circles - and this can only happen once, never more than once. For that to happen more than once, we'd need more interval points. Similarly the lowest frequency happens when the value has the same sign between consecutive green dots. For it to be lower, the interval would have to widen to further separate the green circles.


Combining Noise Octaves

When Perlin noise is used in the real world, it is often a combination of several noise signals, each one with different frequencies. This gives the resulting noise a nice global slow-changing structure, as well as smaller localised details.

The idea is easiest to see when adding simple functions like sine waves. The following picture shows two sine waves. The red one is larger vertically and also slower to change - it has a low frequency. The blue one is smaller vertically and changes more rapidly - it has a higher frequency.


Adding them together gives us the larger sine wave with the roughness of the small one.


If you're familiar with music, you'll see why people call this adding octaves of noise.

And that's how Perlin noise can create interesting landscapes with both larger scale structure as well as smaller scale noise, like the following.



References