#### 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:

#### Gradients

##### 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 **x**_{0} and gradient **g**

_{0}

- To make the equations more generic, we can the line equation as:
- Where:
**g**is the gradient of the line**x**is the origin_{0}

#### Gradient vectors

- In the above interpolation examples we used height values
- We defined the height that the line should be at the start and end

- However, we could have used gradients instead
- 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
# and their corresponding gradients
g1 = gradients[int(x1)]
g2 = gradients[int(x2)]
# 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:
- g
_{00}is the top-left gradient - g
_{10}is the top-right gradient - g
_{10}is the bottom-left gradient - g
_{11}is the bottom-right gradient - each gradient has both an
**x**and a**y**value:- e.g. g
_{00x}and g_{00y}

- e.g. g
- We can't use
**y**to represent height anymore, so instead we will use**z**

- g

#### Interpolation

- For 1 dimensional noise, our equation for the height was:
- Where:
**g**is the gradient of the line**x**is the origin_{0}

- 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 z
_{00}and z_{01} - And then between z
_{10}and z_{11} - 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:

#### Image for a single 2d segment

#### Image for a 5x5 heightmap

#### 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))
gradient = gradient / np.linalg.norm(gradient)
gradients[i][j] = gradient
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
g00 = gradients[int(x1), int(y1)]
g10 = gradients[int(x2), int(y1)]
g01 = gradients[int(x1), int(y2)]
g11 = gradients[int(x2), int(y2)]
# 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()
```

#### Choosing gradient vectors

- 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) def get_gradient(x, y): return gradients[x % 256, y % 256]`

- But this still requires us to store two values at index
- an
**x**and a**y**

- an
- 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): gradients[i, j] = random.randint(0, 256) def get_gradient(x, y): 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): gradients[i] = random.randint(0, 256) def get_gradient(x, y): h = gradients[int(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)`

- 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) random.shuffle(gradients) def get_gradient(x, y): h = gradients[int(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)`

#### Adding multiple octaves

- If we start with our 1 dimensional noise:
- 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'

#### Persistence

- If we start with an octave with frequency=1 and scale=1
- Then we can add more octaves
- But how should the frequency and scale change for the additional octaves?
- This is defined with Persistance
- A persistance of 2 means:
- The frequency should double for each new octave
- The scale should half for each new octave

- By varying the persistance, and the number of octaves, you can produce noise with different properties