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:

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₀ and gradient g

• To make the equations more generic, we can the line equation as:
• Where:
  • g is the gradient of the line
  • x₀ is the origin

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₀₀ is the top-left gradient
  • g₁₀ is the top-right gradient
  • g₁₀ is the bottom-left gradient
  • g₁₁ is the bottom-right gradient
  • each gradient has both an x and a y value:
    • e.g. g_00x and g_00y
  • 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
  • x₀ 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 z₀₀ and z₀₁
  • And then between z₁₀ and z₁₁
  • 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
• 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