Procedural Generation and Simulation

Prof. Dr. Lena Gieseke | l.gieseke@filmuniversitaet.de | Film University Babelsberg KONRAD WOLF

Chapter 06 - Noise

Procedural Generation and Simulation
Chapter 06 - Noise

Try to identify the aspect of noise in the following examples.

noise_01
noise_05
noise_02 noise_04
noise_06
noise_03 noise_12 noise_10

noise_07 noise_08
noise_09 noise_11

Image references (top-bottom, left-right): [hornet], [scratchapixel], [myNoise], [draxe], [Schwarm by A. N. Fischer], [Planeta by M. Kanzler], [Eve by D. Ladopoulos], [Noise landscapes by D. Ladopoulos], [imgur], [moonlightrainbow], [Noise landscapes by D. Ladopoulos]

Learning Objectives

With this chapter you will gain

an understanding of what a procedural noise function is and the requirements for it,
an understanding of the different types of noise, and
knowledge on how to use noise.

Applications for Noise

Noise is an essential component in various applications.

Textures and Materials

For Textures and Materials, we map the output of a noise function to color, gradients and such.

noise_13
[Perlin, K. (1985). An Image Synthesizer.]

noise_14
[thebookofshaders]

Height Fields

With height fields, we use for example, a noise function value as a displacement along normals to make terrain.

noise_15
[wiki]

noise_17

Houdini has also a special height field functionality, for which a volume on a 2D grid represents the distance of the terrain at each point on the map from the ground plane (the values can be negative).

noise_18
[planetside]

Or simply use the noise as z-value for a geometry node in Houdini, for example.

noise_16

On a side note: Do you remember the difference between displacement vs. bump in a 3D package such as Houdini?

Working with a displacement map will add actual new geometry based on the provided displacement map at render time. For this, the renderer subdivides the existing geometry and moves it according to the noise values.

When working with a normal or bump map (different names for the same thing), only the appearance of additional surface detail is created by changing the surface’s normals at render time, without actually creating additional geometry. This approach is much faster and use less memory.

bump_displace_01
[talkgraphics]

bump_displace_02
[photigy]

Stylization

Classic stylization algorithms offset regularly spaced coordinates (e.g. from images or texture accesses) with noise to create a turbulent effect.

noise_19
[Perlin, K. (1985). An Image Synthesizer.]

Stylistic Element

As already seen in the intro example, noise itself can be used as visual and auditive element.

noise_20
[Beautiful Noise]

noise_21
[datalize]

noise_22
[H. Lippmann]

noise_23
[Jackson Pollock - Number 14 gray (1948)]

Animation

In animation, we use noise as a velocity or offset vector for natural movements.

bounce
[processing]

Or map noise to a time parameter to create waves or ripples.

wave
[processing]

Dynamics

For dynamic simulations noise is used to animate or offset particle properties, e.g. their position.

fire
[astarobynski]

Faking Complex Systems

The above examples already touched on a crucial application of noise.

Almost all natural systems appear to combine structure with randomness even though they in fact follow complex creation rules on different scales. As proper simulations of the underlying rules are usually quite expensive to compute, a simple addition of noise is used fake natural systems.

Noise adds variation for designed systems to look natural and for an aesthetic appeal.

mush
[thisiscolossal] The mushrooms appear to us to grow pretty random even though their growth is greatly controlled by factors such as light and foil properties.

Procedural Noise

Procedural noise engineers the appearance of randomness.

How could we do this?

When thinking about a practical usable random noise function, we probably think about something like this:

noise_24
[scratchapixel]

However, true random values look like the following:

noise_25
[scratchapixel]

What are the differences?

With true random values there is no coherency or relationship between adjacent points. Also, computing these values would not guarantee the same results each time.

Here, random is too random! 🤯

So, what is it that we want? Have a look at the blurred version of the true random numbers rendering to get an intuition for what we are looking for:

noise_26
[scratchapixel]

Hence, we want small variations locally and large variations globally!

Naive Smooth Randomness

For example, a naive approach to creating a noise function is to

assign random values at fixed position on a grid (lattice),
- using a random number generator (RNG)
blur these values, e.g. with a gaussian blur
- this is similar to bilinear interpolation

To mimic this behavior, we could for example build the following smooth 1D pseudo-random function, which is put together by the different function blocks from the last chapter:

prn_09

In the following, I walk you through how to build the above pseudo-random function from scratch. Feel free to follow along with these steps with graphtoy. graphtoy is a great tool to quickly put together and test functions. The tool is once again, by our - or at least my 😁 - great idol Inigo Quilez.

Pseudo random generator

We want new random values at the integer values. For that as a base, we sample sin() function at the integers:

step_random(x) = sin(floor(x))

prn_01

The frac value of f1 gives us positive 0..1 ranges:

step_random(x) = fract(sin(floor(x)))

prn_02

This looks far too regular though. By scaling up sin() we can get a noisier value distribution:

step_random(x) = fract(sin(floor(x)) * 9999)

prn_03

Smooth interpolation

Instead of stepping between values, we want to smoothly interpolate between values. We can use two smoothstep() versions of the step_random(x), one for each “side” of the integer.

For sampling with a smooth step, we take:

smooth_saw(x) = smoothstep(0, 1, fract(x))

prn_04

and multiply that with our step_random():

left_side(x) = smooth_saw(x) * step_random(x)

prn_05

For the right side, we use a flipped and shifted version of the above. First the flip:

right_side(x) = smooth_saw(x) * (step_random(x) * -1)

prn_06

…then a shift up:

right_side(x) = smooth_saw(x) * (step_random(x) * -1 + 1)

prn_07

…and right:

right_side(x) = smooth_saw(x - 1) * (step_random(x - 1) * -1 + 1)

prn_08

Now adding both sides together, gives the final smooth pseudo random function:

smooth_pseudo_noise(x) = left_side(x) + right_side(x)

prn_09

Of course, in graphtoy (and most environments) you also could have simply used the given noise function noise() 🙃

prn_10

Requirements For Procedural Noise

For good noise functions there are overall the following requirements.

Spatial correlation

Minimal location shifts should not result in huge value differences, creating a smooth behavior. This means that local value changes are gradual, while global changes can be large.
No Periodicity

At least, we do not want to see it.

[Visible periodicity]
Rotational and Translational Invariance

Following the same creation principles everywhere.
A Defined Distribution

We want some control over the function, e.g. how smooth it is.
Reproducibility

The noise should look the same every time we compute is, e.g. in every frame we render unless we explicitly want a change e.g. for an animation.
Band Limited Frequency Content

This means frequencies should not get too high, otherwise we might get aliasing.

[scratchapixel]
Continuity and Differentiability

Often the derivates of noise functions are needed.

Non-differential or non-continues function examples.

Noise Function Designs

noise_29
[scratchapixel]

Back to the original question, how do we go from random numbers (left example, image above) to a well behaved noise function, which fullfills the requirements of the last section (right example, image above)?

Random Number Generator (RNG)

At the core of all noise functions is a seeded random number generator, which takes some input parameters, e.g. a point coordinate and returns a random (looking) number. Seeded means that the same input parameters will always produce the same output for the same seed (usually a number) and if you change the seed there will be a different distribution of random numbers.

y = rng(x)

There are many, many random number generation methods… (for example the method we used above with sin()) it is almost a science in itself. If you are interested, you can start with this Introduction to Randomness and Random Numbers.

You will often see so-called hash functions for the generation of random numbers. A hash function is any function that can be used to map data of arbitrary size to data of fixed size. [1]

Hence, what the hash function in the context of RNGs does is to transform input with math operations into output a that looks random. These function actually do repeat after a long period but usually non-noticable for our applications.

To generate a random looking output, typically bitwise operations and/or large prime numbers are used. These function are n-dimensional, meaning they can be setup for any number of input parameters and produce any number of random values for the input. The demo scene has spent a lot of time and effort to optimize these. See Inigo Quilez’s blog for some optimization tips.

When using any kind of RNG it is important that you pay attention to its output range and wether that fits to your needs. Usually you can assume a range from [-1, 1].

In the following some example hash functions, from Hash without Sine (you don’t have to understand the code!). Not using any trigonometric functions in the generation of random numbers has the advantage that how trigonometric functions are executed still highly depends on the graphics card and on certain systems (mine for example) will lead to visible periodicity:

//  1 out, 1 in...
float hash11(float p)
{
    p = fract(p * .1031);
    p *= p + 33.33;
    p *= p + p;
    return fract(p);
}

//  1 out, 2 in...
float hash12(vec2 p)
{
    vec3 p3  = fract(vec3(p.xyx) * .1031);
    p3 += dot(p3, p3.yzx + 33.33);
    return fract((p3.x + p3.y) * p3.z);
}

///  2 out, 2 in...
vec2 hash22(vec2 p)
{
    vec3 p3 = fract(vec3(p.xyx) * vec3(.1031, .1030, .0973));
    p3 += dot(p3, p3.yzx+33.33);
    return fract((p3.xx+p3.yz)*p3.zy);
}

...

(Lattice) Value Noise

The principle of a value noise is simple:

A fixed grid (the lattice)
- Relates the noise to space
- Defines the basic scale
A random number for each grid point
Interpolate in-between
- Again, many interpolation algorithms available… we have already talked about these
- Ensures spatial correlation

noise_30

(Lattice) Gradient Noise

Ken Perlin was commissioned to generate more realistic textures for the movie Tron in the early 1980s. He task was to break with the solid shaded look that have been used so far. The idea was to add to the solid colors a noise texture. For that he came up with an elegant noise algorithm, the Perlin noise. In 1997 he won the Academy Award for Technical Achievement from the Academy of Motion Picture Arts.

tron [3]

Perlin published is results in the seminal publication

Ken Perlin. 1985. An image synthesizer. In Proceedings of the 12th annual conference on Computer graphics and interactive techniques (SIGGRAPH ’85). Association for Computing Machinery, New York, NY, USA, 287–296. DOI:https://doi.org/10.1145/325334.325247

perlin

And in 2002 to follow-up (a Siggraph paper with only two pages!)

Ken Perlin. 2002. Improving noise. In Proceedings of the 29th annual conference on Computer graphics and interactive techniques (SIGGRAPH ’02). Association for Computing Machinery, New York, NY, USA, 681–682. DOI:https://doi.org/10.1145/566570.566636

The Perlin noise function got further improved and extended over the years primarily by Ken Perlin himself but also by others.

So what did Perlin invent? Instead of values, Perlin uses random normalized gradients on a grid for each sample point. But let’s go step by step to understand this.

We want a smooth noise, meaning regular in frequency such as

perlin_01
[scratchapixel] Even changes

When choosing random values the distribution of frequencies might lead to an irregular interpolation of values such as

perlin_02
[scratchapixel] Uneven changes

To get the uneven frequency changes under control, we can define random normalized gradients, meaning random vectors, on a grid for each sample point instead of simply using values. Then, we interpolate a smooth function between those vectors.

perlin_03
[scratchapixel]

This causes the curve to go up on one side of the lattice point and down on the other side of that same point such as

perlin_04
[scratchapixel]

The worst case in regard to a uneven frequency distribution happens when two successive lattice points have gradients that aim at opposite directions (one points up and the other points down). Then the noise function will have a “S” like shape between the two points.

perlin_05
[scratchapixel]

Through the use of random vectors, the distribution of frequencies in the Perlin noise is more regular than the value noise’s frequency spectrum. As Perlin notes in his paper:

The above texture has a band-limited character to it; there is no detail outside of a certain range of size.

perlin_06
[scratchapixel]

In 2D, at each grid point a pseudo-random 2D gradient is picked such as

perlin_07
[webstaff.itn.liu.se]

But how to go from vectors to random numbers, which we ultimately want? We apply the dot product between the gradient at the corner of a cell and the vector from that corner to the point such as

perlin_08
[scratchapixel]

For an arbitrary point the noise value is computed from the four closest grid points.

perlin_09
[webstaff.itn.liu.se]

To interpolate between n₀₀, n₁₀, n₀₁, n₁₁ rather than just using linear interpolation, Perlin uses as a fade function the Hermit blending function, which we already know from smoothstep()

f(t) = 3t² - 2t³

Perlin later changed that to a fifth degree polynomial f(t) = 6t5 - 15t4 + 10t3

f(t) = 6t⁵ - 15t⁴ + 10t³

perlin_10
[webstaff.itn.liu.se]

The difference vector is (0,0,0) (and the dot product 0) when P lies exactly on the grid such as

perlin_11
[wiki]

Here, an overall comparison of the gradient noise to a simple value noise

perlin_12
[iquilezles]

Changing the interpolation also leads to visible differences

perlin_13
[[2]]

Simplex Noise

Perlin was still not satisfied with his gradient noise and presented 2001 the simplex noise. For the simplex noise Perlin replaced a grid tiling of a space with a triangular tiling such as

simplex_01
[webstaff.itn.liu.se]

Perlin correctly argues that a square has more corners than necessary. The simplest and most compact shape that can be repeated to fill a space is an equilateral triangle. For more details about the simplex noise, please refer to this detailed explanation.

simplex_02
[iquilezles]

`noise()`

As mentioned before, almost in all environments we are using you have pre-defined noise functions such as

// 1D
noise(x); 

//2D
noise(x, y);

For full control over your results, check which algorithm the noise() function is based and whether the noise creates the distribution you want. If not you can always go back to defining your own noise function. An excellent resource for different noise functions is this State of the Art Report.

Using Noise Functions

Noise functions are usually used as

value = amplitude * noise(frequency * x + offset);

Amplitude

The amplitude controls the maximum absolute value that a specific noise function can output. For example, for a 1D y = noise(x) this would mean the range the noise can spread in y:

amplitude

Frequency

The frequency parameter can be understood as the density of the noise, or its bumpiness.

frequency

frequency_01 frequency_02
[2]

Offset

The offset selects different locations of the noise function. Hence, the offset enables you to use the same noise function multiple times, each version looking differently.

noise-curve-offset

Component Frequencies

Which characteristic feature of noise do you see here, which we haven’t discussed yet?

noise_14
[thebookofshaders]

In the above example we can observe well that organic patterns have multiple levels of detail with self-similar structures.

The represent this, we remember the insights we gained from Fourier transformations and that any function, or signal, can be decomposed into simple component signals at different frequencies.

turbulence_02
[pgfplots]

To represent this, we can sum up multiple noise functions (so-called octaves) at different frequencies and amplitudes.

1D:

turbulence_03
[2]

2D:

turbulence_01
[hugo.elias]

There are several techniques for computing such multi-level noises and all follow the same principle of defining a relationship between frequency and amplitude and successive octaves.

Such noises are for example Turbulent noise, Fractal Brownian Motion (fBM), Fractal noise or Multi-Octave noise.

Turbulence Noise

The generalized formula for turbulence is

turbulence_04

with

Number of octaves n
Lacunarity L
- Multiplier to determine how quickly the frequency increases for each successive octave
- The frequency of each successive octave is equal to the product of the previous octave’s frequency and the lacunarity value
Amount of fractal noise H (weighting the octaves)

This function adds details proportional to the size of the noise in each octave and creates self-similar structures.

[4]

On a side note: Turbulent noise is often considered as Perlin noise. This is not true. Perlin’s main contribution is the noise function itself. He used in his paper a specific turbulent noise setup as an example application for his noise function. But the internet doesn’t understand this.

Perlin’s specific turbulence noise uses H = 1, L = 2

turbulence_05

Hence, the levels are

turbulence_07

turbulence_06
[2]

This type of turbulence noise is also known as Fractal Brownian Motion (fBM) or Fractal Noise.

For example, Inigo Quiles applied fbm noise to wrap the space of a fbm noise again with the following results:

fbm_fbm
[Warping by Iq]

If you want to understand this better, Inigo also wrote an article about it.

Multi-Octave Noise

A similar property to lacunarity is persistence. Again, this is a multiplier to determine how quickly the amplitudes diminish for each successive octave.

Here, the amplitude of each successive octave is equal to the product of the previous octave’s amplitude and the persistence value, meaning

frequency = 2ⁱ
amplitude = persistenceⁱ

This means that increasing the persistence produces rougher noise.

mon_01
[libnoise]

mon_02
[hugo.elias]

// Pseudo Code

function MultiOctaveNoise2D(float x, float y)

      total = 0
      n = Number_Of_Octaves - 1

      loop i from 0 to n

          frequency = 2^i
          amplitude = persistence^i

          total += noise(x * frequency, y * frequency) * amplitude

      return total

end function

Cellular Noise

Cellular noise describes random variability in quantities arising in cellular biology [5]. Steven Worley adapted cellular noise principles for computer graphics in:

Steven Worley. 1996. A cellular texture basis function. In Proceedings of the 23rd annual conference on Computer graphics and interactive techniques (SIGGRAPH ‘96). ACM, New York, NY, USA, 291-294.

cellular_01
[wiki]

Worley Noise

Worley noise is based on a distance field, for which you compute for each pixel the distance to a set of points. This set of points are often randomly distributed feature points. Then, we take the closest distance to all points found and use that as color information, e.g. black and white.

cellular_02

// Iterate through the points positions
float minimum_dist = 1.;

for (int i = 0; i < TOTAL_POINTS; i++) 
{
   float dist = distance(pix, point[i]);

  // Keep the closer distance
  minimum_dist = min(minimum_dist, dist);
}

pix.color = minimum_dist;

To check all points for all pixels is costly and the algorithms becomes with the naive implementation as shown above, almost non-usable. As optimization we rather divide the space into tiles and have one point per tile. Then you only need to check a pixel’s tile and the neighboring ones for the closes distance. For a detailled explanations, please see [The Book of Shaders] (highly recommended).

cellular_03
[thebookofshaders]

worley
[thebookofshaders]

This algorithm gives many design options, e.g. inverting the colors or by setting thresholds and clamping the last quarter of the distance.

cellular_04
[thebookofshaders]

You could also understand the algorithm from the perspective of the points (not the pixels). This would mean that each point grows its area until it finds the growing area from another point. This mirrors some of the growth rules in nature.

voronoi_growth_euclidean
[wiki]

Living forms are shaped by this tension between an inner force to expand and grow, and limitations by outside forces.

Voronoi Algorithm

A Voronoi diagram is a slight variation from the Worley noise in the sense that is doesn’t save the closest distance for each pixel to a feature point, but it saves for each pixel the feature point itself, e.g. by assigning the color of the closest point, disregarding the actual distance.

voronoi_01
[wiki]

// Iterate through the points positions
float minimum_dist = 1.;
vec2 closest_point;

for (int i = 0; i < TOTAL_POINTS; i++) 
{
    float dist = distance(pix, point[i]);

    if ( dist < minimum_dist )
    {
        // Keep the closer distance
        minimum_dist = dist;

        // Also keep the position of the closer point
        closest_point = point[i];
    }
}
pix.color = closest_point.color;

A Voronoi diagram has the following characteristics:

Partitioning of a plane into n convex polygons (aka cells or regions).
Each point in a region is guaranteed to be closer to the region’s generating point than any of the other n possible generating points.
Line segments are equidistant to two points. Nodes (corners) are equidistant to three (or more) points.

This concept can be extended to higher dimensions.

voronoi_08
[thebookofshaders]Extended Voronoi - Leo Solaas (2011)

voronoi_animated
[thebookofshaders]

voronoi_09
[iquilezles]Using a bitmap as cell color

voronoi_10
[thebookofshaders] Cloud Cities - Tomás Saraceno (2011)

voronoi_11
[thebookofshaders] Accretion Disc Series - Clint Fulkerson

Deluanay Triangulation

Deluanay Triangulation is a technique for creating a mesh of contiguous, non-overlapping triangles from a set of points.

delaunay_01
[samuelp]

There are three possible triangulations for this set of points.

Which one do we want?

delaunay_02
[samuelp]

Deluanay Triangulation is a triangulation such that no point is inside the circumcircle of any triangle.

delaunay_03
[samuelp]

If you are interested in the computation of the delaunay trinagulation, refere e.g. to this explanation.

Delaunay triangulation is related with Voronoi diagrams in that the circumcircle centers of the triangulation are voronoi cell corner points!

delaunay_04
[wiki]

Hence, Delaunay triangulation is one method to compute voronoi diagrams. There are furthermore

[jakerice]

Distances

We are free to define any kind of distance. So far we have used the most common one, the Euclidian distance.

Note: Euclidean distance, Manhattan distance and Chebyshev distance are all distance metrics which compute a number based on two data points. All the three metrics are useful in various use cases and differ in some aspects.

voronoi_02
[wiki]

Different distance might look as

voronoi_03
[wiki]

Manhattan distance with the taxicab metric vs. Euclidean distance

voronoi_04
[improvedoutcomes]

with

voronoi_05
[wiki]

voronoi_06
[iquilezles]

Dual Graph

A variation to Voronoi diagrams is the dual graph. For the dual graph imagine we have two triangles, that share one complete edge. Now for every shared edge, you would remove that shared edge, and connect the centers of the two triangles, passing through the position where the old edge was.

dual [jakerice]