# Perlin Noise

## Prerequisites

### Perlin Noise

#### Introduction

• Perlin noise is an algorithm for producing multi-dimensional noise
• Unlike the diamond-square algorithm, it does not suffer from severe axis-alignment

#### Interpolation

• Let's with an array of two height values:
• We can plot these on a graph:
• However if we want to get the height of a value between 0 and 1, for example: 0.5, then we have to interpolate.
• A simple linear interpolation would involve drawing a straight line between the two points:
• However this isn't very smooth
• Smoothness becomes very important when dealing with more than two values
• Perlin noise uses a function called 'smoother step' to smooth the values
• Smoother step is defined as:
• If we combine this with our linear interpolation:

##### For origins of 0
• If a line has an origin of 0 and a gradient of 0.5 then the equation for this line would be:
• At the origin, the values of x and y would be:
• But as we move further away from the origin:
• The important note here is that the further away from the origin we are, the more of an effect the gradient has on the height
• We are moving uphill from our origin
##### For origins of 1
• If a line has an origin of 1 and a gradient of 0.5 then the equation for this line would be:
• At the origin, the values of x and y would be:
• But as we move further away from the origin:
• Note that we end up with a negative number, as we are downhill from our origin
##### For origin x0 and gradient g
• To make the equations more generic, we can the line equation as:
• Where:
• g is the gradient of the line
• x0 is the origin

• In the above interpolation examples we used height values
• We defined the height that the line should be at the start and end
• We can define the gradient that the line the should be at the start and end:
• For a value x between 0 and 1 we can calculate its height relative to each gradient:
• Finally, we can interpolate between these two values to get our final value for y:
• If we do this for all x values between 0 and 1, we get:
• This is Perlin noise in 1 dimension

#### Extending to more than two points

• Our curve is great if you have a start and end point
• But we can also define a set of gradient vectors at the integers, and interpolate each segment individually:

#### Python Code

import numpy as np
import random

size = 5
gradients = [random.uniform(-1, 1) for t in range(size + 1)]

def smoother_step(x):
return x * x * x * (x * (x * 6 - 15) + 10)

def interpolate(x):
# the largest integer, that is smaller than x
x1 = x - (x % 1)

if x == x1:
return 0

# the smallest integer, that is larger than x
x2 = x1 + 1

# calculate the position vectors
p1 = x - x1
p2 = x - x2

# calculate the heights
y1 = g1 * p1
y2 = g2 * p2

# interpolate
return smoother_step(x - x1) * (y2 - y1) + y1

# generate a range of values from 0 to 'size - 1' with a step of 0.01
interpolated_x = np.arange(0, size, 0.01)

interpolated_y = [interpolate(x) for x in interpolated_x]

#### Perlin noise in 2 dimensions

• For 2d noise, we specify a gradient vector at each corner, each gradient vector has both an x and a y component:
• The gradients vectors are labelled as:
• g00 is the top-left gradient
• g10 is the top-right gradient
• g10 is the bottom-left gradient
• g11 is the bottom-right gradient
• each gradient has both an x and a y value:
• e.g. g00x and g00y
• We can't use y to represent height anymore, so instead we will use z

#### Interpolation

• For 1 dimensional noise, our equation for the height was:
• Where:
• g is the gradient of the line
• x0 is the origin
• However, for two or more dimensions, we have to use a dot product of the vectors
• Note that the dot product in one dimension is the same as multiplication
• So we aren't doing anything new, we've just changed the size of the vectors we are multiplying
• Our equations for the height values are:
• This simplifies to:
• Finally we interpolate
• However interpolation only works for two values
• So we will interpolate between z00 and z01
• And then between z10 and z11
• And finally between those two values
• We can also extend it to more than a single square by defining a 2d grid of gradients, and interpolating each segment individually:

#### Python Code

import random
from PIL import Image
import numpy as np

size = 5
gradients = np.zeros((size + 1, size + 1, 2))

for i in range(size + 1):
for j in range(size + 1):
gradient = (random.uniform(-1, 1), random.uniform(-1, 1))

def smoother_step(x):
return x * x * x * (x * (x * 6 - 15) + 10)

def interpolate(x, y):
# top left
x1 = x - (x % 1)
y1 = y - (y % 1)

if x == x1 and y == y1:
return 0

# bottom right
x2 = x1 + 1
y2 = y1 + 1

# and their corresponding gradient vectors

# calculate the position vectors
p00 = (x - x1, y - y1)
p10 = (x - x2, y - y1)
p01 = (x - x1, y - y2)
p11 = (x - x2, y - y2)

z00 = np.dot(p00, g00)
z10 = np.dot(p10, g10)
z01 = np.dot(p01, g01)
z11 = np.dot(p11, g11)

# interpolate
za = smoother_step(x - x1) * (z10 - z00) + z00
zb = smoother_step(x - x1) * (z11 - z01) + z01
z = smoother_step(y - y1) * (zb - za) + za

return z

img = Image.new('L', (size * 100, size * 100))

for i in range(size * 100):
for j in range(size * 100):
z = interpolate(i / 100, j / 100)
img.putpixel((i, j), int(128 * z + 128))

img.show()

• In the above example we chose random values for our gradient vectors and stored them in a 2d array
• Our only constraint was that the values should be in the -1, 1 range
• This is fine for 1 dimensional noise
• But for two or more dimensions, the gradient values should be clamped to either -1 or 1
##### Implementation:
• A simple approach would be something like:
gradient = -1 if random.uniform(0, 1) < 0.5 else 1
• But Ken Perlin created a more elegant and efficient solution
• Firstly:
• Instead of using a 2d array of gradients, of size (n, n)
• We can have an array that is fixed at size (256, 256)
• If we need a value that is outside of this range then we take its value mod 256
gradients = np.zeros((256, 256, 2))
for i in range(256):
for j in range(256):
gradients[i, j] = (-1 if random.uniform(0, 1) < 0.5 else 1, -1 if random.uniform(0, 1) < 0.5 else 1)

return gradients[x % 256, y % 256]
• But this still requires us to store two values at index
• an x and a y
• Instead of this, we can store a single random value and use it to generate both the x and y values:
• Due to the components of the gradient needing to be either -1 or 1, there are only 4 possible gradient vectors:
• (-1, -1)
• (-1, 1)
• (1, -1)
• (1, 1)
• Therefore we can check the random value mod 4, and return one of these vectors:
gradients = np.zeros((256, 256))
for i in range(256):
for j in range(256):

h = gradients[x % 256, y % 256] % 4
if h == 0:
return (-1, -1)
elif h == 1:
return (-1, 1)
elif h == 2:
return (1, -1)
else:
return (1, 1)
• But this still requires an array of 256x256 numbers
• Instead, we can use a single array of 256 numbers, and index the table twice:
gradients = np.zeros((256))
for i in range(256):

if h == 0:
return (-1, -1)
elif h == 1:
return (-1, 1)
elif h == 2:
return (1, -1)
else:
return (1, 1)
• Finally, we need to ensure that our array of gradients is uniform
• So that each value between 0 and 255 appears exactly once
• To do this, we fill it with the numbers in order, and then shuffle it
gradients = np.arange(256, dtype=int)

if h == 0:
return (-1, -1)
elif h == 1:
return (-1, 1)
elif h == 2:
return (1, -1)
else:
return (1, 1)

• We can describe its frequency as the number of line segemnts between each integer
• In the above case, it has a frequency of 1, as we have one line segment between 0 and 1, one line segment between 1 and 2, etc
• However if we double the frequency, we get:
• To do this we produce noise twice as long, and scale it in the x-dimension
• This results in a gradient vector not only at the integers, but also at 0.5, 1.5, etc
• We can plot these two lines together:
• A second property we can define is scale
• In the above lines, the scale is 1, e.g. unscaled
• However we can multiply the height of the line by a value
• If we multiply our blue line (with frequency 2) by a scale of 0.5 then we get:
• Finally, if we add these two lines together, we get a 3rd line:
• When increasing the frequency of a line, it produces more detail
• But it also creates larger swings in the gradient
• By scaling the result, it keeps the detail, and reduces the swings in the gradient
• Adding lines together with different frequencies and scales gives more detailed noise which is still smooth
• Each individual line is called an 'octave'