1. Deterministic Continuous Random Functions</h1>
To procedurally generate textures, we generally need a source of randomness. Libraries often offer this functionality in the form of a function that returns a new value each time it’s called.
A problem with these random number generators is that they are "too random" for our purposes. Consider the graphs below:
Perlin noise is in essence a random number generator that guarantees a certain smoothness.
Concretely, what we want is some function double random(double x)
that satisfies the following conditions:
-
random
must be deterministic:random(x)
must return the same result when given the samex
. -
random
must be continuous:random(x)
andrandom(x + 0.00001)
should be close to each other, i.e. no sudden jumps.
Perlin noise satisfies these criteria.
The function double random(double x)
is one-dimensional: it associates a value with each double
.
We can lift this to higher dimensions:
-
double random(const Point2D&)
is a two dimensional variant: it associates a value with eachPoint2D
. -
double random(const Point3D&)
is three dimensional: each point in 3D space is mapped to a value.
2. Perlin Noise
Perlin noise is such a deterministic continuous function. For the remainder of this page, we will work in 2D, i.e.
we will build a function double perlin(const Point2D&)
.
Perlin noise works as follows: take a 2D grid of 1 × 1 cells and associate a unit vector with every intersection.
![grid vectors](grid-vectors.png)
In order to determine the value associated with a point \(P(x, y)\), you need to find out in which grid cell it resides. Its corners are
where \(\lfloor x \rfloor\) corresponds to rounding \(x\) down and \(\lceil x \rceil\) to rounding \(x\) up. Each corner has a unit vector associated with it. We denote the vector corresponding to \(Q_i\) with \(\vec v_i\).</p>
Next, take the dot product of each \(Q_iP\) and \(v_i\):
![computation](computation.png)
Now we have associated a \(z\)-value with each corner. As last step, we need to determine which \(z\)-value to assign to \(P\) itself using interpolation.
![interpolation](interpolation.png)
Interpolation goes in three steps:
-
Find a function \(f\) with \(f(0) = z_1\) and \(f(1) = z_4\). Compute \(f(x)\).
-
Find a function \(g\) with \(g(0) = z_2\) and \(g(1) = z_3\). Compute \(g(x)\).
-
Find a function \(h\) with \(h(0) = f(x)\) and \(h(1) = g(x)\). Compute \(h(y)\).
The functions \(f\), \(g\) and \(h\) can be linear or, for better results, an easing functions.