1 of 26

Noise Algorithms and their applications

by Andreas Sepp

for the Computer Graphics Seminar 16/17 fall

2 of 26

The plan for today

  • Noise algorithms
    • White noise
    • Value noise
    • Perlin noise
    • Simplex noise
  • Noise algorithm applications
  • Some exercises
  • Noise algorithms in popular games (if we have time)

3 of 26

What is noise?

4 of 26

Formally...

  • An n-dimensional function f: ℝn → ℝ that projects every n-dimensional vector to a (pseudo)random number

​

    • Usually the projected number is confined to the range [0, 1] or [-1, 1]

​

    • Can be deterministic or nondeterministic

5 of 26

White noise

for each(x,y):

var color = random(0, 256);

Image.pixel[x,y]

= (color, color, color);

6 of 26

White Noise as a post-effect

White Noise: Online

7 of 26

Value noise

  • We want our noise to be deterministic
  • First, we define a function fhash that converts any n-dimensional integer vector to a pseudorandom number in some fixed range.
  • For example, in 2d:

fhash = ℤ2 → [0, 1]

For this, we can generate some numbers in the desired range at some fixed interval m (= 0.05):

perm = {0.00, 0.05, 0.10, 0.15, …, 0.95, 1.00}

And then randomize it into some random permutation:

perm = { 0.15, 1.00, 0.35, 0.00, …, 0.50, 0.20 }

8 of 26

Value noise

Now we can find a pseudorandom value for every 2D vector (x,y) from the perm array like this:

Let k = 1 + 1/m = perm.length()

fhash = perm[ (perm[x mod k] * (1/m +1) + y) mod k]

​

9 of 26

Value noise

  • So far we have a function that finds values for integer coordinates.
  • What about the rest, for example (0.5, 0.2)?
  • We interpolate the values from nearest integer coordinate point values.
  • Let's go back to 1D: we have a function fhash: ℤ → [0, 1].

​

10 of 26

Value noise interpolation

  • In 1D: for our point P, we find the distance to the closest points with integer coordinates and use a blending function.

​

  • In 1D: for our point P, we find the distance to the closest points with integer coordinates and use a blending function.
  • In 2d: we find the 4 closest points and apply bilinear interpolation with a blending function.

11 of 26

Blending functions comparison

C0 smooth C1 smooth C2 smooth

f(x) = x f(x) = 3x2 - 2x3 f(x) = 6x5 - 15x4 + 10x3

12 of 26

Value noise

  • So we can generate such layers now but they don't look that great
  • The idea: let's add multiple layers with different scales together.
  • We have:
    • Number of layers
    • Scaling factor (frequency) for each layer
    • Gain factor(which layers are more prominent?)
      • For example gain factor 0.5 and 3 layers means that each layer gets the following weight in the combined result:

13 of 26

Value noise

  • 6 layers with frequencies 1/32, 1/16, ⅛, ¼, ½, 1 and gain 0,5.
  • Noticeable horizontal and vertical artifacts :(

14 of 26

Gradient noise

  • Gradient is a generalization of the derivative of a function concept
  • Formally: Gradient is a n-dimensional vector whose components are the n partial derivatives of a function.
  • In current case: in n-dimensional place fhash generates a n-dimensional vector of some fixed length k.
  • In 2D, we can pick 8 or 16 vectors at even intervals on an unit circle.
  • In 3D, we can pick vectors from the (0,0,0) origin to the midpoints of an unit cube's edges.

15 of 26

Perlin noise

  • First we define a new ghash function that converts our integer coordinates to one of the possible gradient vectors.
  • Once again we can first define the possible gradient vectors, randomly permute them and then hash the input integer coordinates and pick the one from the array.
    • For example, in 3D the possible gradients could be:

16 of 26

Perlin noise

  • Finding the noise value of point P:
  • Find the relevant points with integer coordinates surrounding P and their gradients (red).
  • Construct the vectors v from each corner point to P (green).
  • For each corner find the scalar value n = g * v. (red gradient * green vector)
  • Bilinearly interpolate the value at P using n and a blending function.

17 of 26

Perlin noise

  • 6 layers with frequencies 1/64, 1/32, 1/16, ⅛, ¼, ½ and gain 0,5.
  • Perlin noise sometimes, albeit rarely, generates some artifacts
  • Calculating Perlin noise takes O(2n) time (n is the dimension)
  • Can we do better?

18 of 26

Simplex noise

  • Complexity of O(n2)
  • No noticeable artificial lines
  • Works based on simplex shapes:
    • In n-dimensional space, a simplex is a n-dimensional object that has the minimal number of edges but is still able to fill the whole space without intersecting with each other.

19 of 26

Simplex noise

  • Instead of defining a function for integer coordinates, we tessellate the n-dimensional space into n-dimensional simplices.
  • For example, in 2D:
  • Next, a function is defined to convert the tessellation space into regular space, where each simplex corner has integer coordinates:

20 of 26

Simplex noise

  • Now we can also convert any point coordinates from simplex space to normal space and see inside which simplex our point is.
  • Next, we find the gradient values for the simplex corners which now have integer coordinates.
  • Lastly, we interpolate the value at our point of interest using a radial weight function:

21 of 26

Simplex noise

  • 6 layers with frequencies 1/64, 1/32, 1/16, ⅛, ¼, ½ and gain 0,5.

22 of 26

Noise applications

​

​

23 of 26

Noise applications

24 of 26

Noise algorithms in games: Minecraft

  • Started as a relatively simple algorithm using Perlin noise
  • Has evolved to use a lot more complicated algorithms
  • Used to use "Perlin worms" algorithm for cave generation
  • A big problem: world generated while coming from any side must be the same

25 of 26

Noise algorithms in games: Terraria

  • Finite size explorable 2D world with a lot of caves and structures

26 of 26

Thanks for listening and participating!

Some links of interest:

Value noise and Perlin noise implementation as a tutorial: http://catlikecoding.com/unity/tutorials/noise/

Simplex noise explained more thoroughly: http://webstaff.itn.liu.se/~stegu/simplexnoise/simplexnoise.pdf

Simplex noise with actually easy to follow code: http://catlikecoding.com/unity/tutorials/simplex-noise/

My BSc thesis about procedural infinite terrain generation, also explains the noise algorithms in more detail (in estonian): https://comserv.cs.ut.ee/home/files/sepp_informaatika_2016.pdf?study=ATILoputoo&reference=DD8A7D42D542D38F624F67AA83B6CB1108696588

​

​