Why do all Simplex Noise algorithms have a Permutation & Gradient table?

Question

I've been trying to implement Simplex Noise for about a month now, and I do understand the idea of working with Simplices to reduce the amount of calculations needed and also safe power on the gradient side. Implementing this into any language though, seems like Mission Impossible.

In every, every, every, code I find, resource I read, everywhere, the code seems to be having a G and a P table. From some Googling and asking around I learnt they are a Permutation and a Gradients table. What do they do? Why do we need them?

My current thought is that the permutation table just contains random values so they don't have to be calculated at runtime.

Examples:

• http://cabbynode.net/2012/06/10/perlin-simplex-noise-for-c-and-xna/
• http://www.6by9.net/simplex-noise-for-c-and-python/
• http://webstaff.itn.liu.se/~stegu/simplexnoise/simplexnoise.pdf
• http://www.csee.umbc.edu/~olano/s2002c36/ch02.pdf

Answer 1

The confusion between simplex, perlin noise and a hybrid of these two are very prevelent throughout the internet at this point. The most famous and cited paper I know of is Stefan Gustavson's. In it Mr. Gustavson says the following

I will use a hybrid approach for clarity, using the gradient hash method from classic noise but the simplex grid and straight summation of noise contributions of simplex noise

The result is thus not simplex noise nor Perlin noise but rather a mishmash or hybrid noise algorithm which has some features of both.'

Perlin noise is the classic noise and it uses predefined (generated somehow) gradient vectors and a permutation table (which hold indices to the gradient table). So in order to get a gradient from a coordinate (x, y, z) you apply some kind of hash function, classical Perlin noise simply uses modulo, and then you grab a index from the permutation table which in turn gives you another index which you use to grab a gradient from the table. Using the modulo operation as a hashing function instantly gives you the repeatable nature of Perlin noise.

The permutation table looks something like this; [0, 1, 2, ..., sizeof(gradient_table) - 1].

Simplex noise is patented (atleast for texture generation in 3D and up) and its algorithm is described here. Simplex noise uses two unique inventions in order to differentiate it from Perlin noise.

1) No gradient table nor permutation table. Instead the gradients are generated on-the-fly with a bitmanipulation algorithm.

2) Instead of a coordinate grid consisting of square (in 2D) it is made up of the simpliest geometric form which tiles the plane. In 2D this is the triangle, in 3D the tetrahedron. This coordinate grid reduces the visible artifacts of grid.

There are also some minor but still very important features of simplex noise that makes it a much more elegant algorithm. For instance there are not inner products made since all the contributions from the vertices are made using a spherical kernel. Even the transformation between the simpletic coordinate grid and the cartesian (or normal one) is optimized into a single multiplication which makes it super cheap to transform.

As a shameless selfpromotion I will provide a link to my repository of noise function in which I try to implement everything as correctly as possible. The goal is to provide some kind of standard cross-platform implementation a bunch of noise functions.

Answer 2

Essentially yes, the P table is used to select a random gradient from the G table. However, the important thing is that it needs to be repeatable. That is, in the 3D case, for a given (i,j,k) triple you need to be able to always produce the same "random" gradient. This is what makes the noise function coherent. So the whole point of the formula where it does a few lookups in the P table is that the result comes out looking random, but it's deterministic for a given input.

If you weren't concerned about performance, you could just as easily use (i,j,k) to seed a pseudorandom number generator, and then use that to pick a gradient from the G table.