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

Question

I’ve been trying to implement Simplex Noise for about a month, and I understand the idea of ​​working with Simplices to reduce the amount of computation needed, as well as the safe power on the gradient side. Introducing it into any language, it seems that Mission Impossible.

In every, every, every code that I find, the resource I read is everywhere, the code seems to have a table G and P. From some Googling and asking, I found out that this is a table of permutations and gradients. What are they doing? What are they needed for?

My current thought is that the permutation table contains only random values, so they do not need to be computed 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, perlinsky noise and a hybrid of these two is very common throughout the Internet at this moment. The most famous and quoted article I know is Stefan Gustavson's . In it, Mr. Gustavson says the following

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

Thus, the result is not simplex noise, but Perlin noise, but rather an algorithm of useless or hybrid noise, which has some features of both. ''

Noise Perlin is a classic noise, and it uses predefined (somehow generated) gradient vectors and a permutation table (which contain indices in the gradient table). Therefore, to get the gradient from the coordinate (x, y, z), you use some kind of hash function, the classic Perlin noise just uses modulo, and then you grab the index from the permutation table, which in turn gives you another The index that you use to grab the gradient from the table. Using modular operation as a hash function instantly gives you the repetitive nature of Perlin noise.

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

Simplex noise is patented (at least for texture generation in 3D and higher), and its algorithm is described here. Simplex noise uses two unique inventions to distinguish it from Perlin noise.

1) There is no gradient table or permutation table. Instead, gradients are generated "on the fly" with a bitmanipulation algorithm.

2) Instead of a grid consisting of a square (in 2D), it consists of the simplest geometric shape that divides the plane, in 2D it is a triangle, in 3D it is a tetrahedron. This grid reduces the visible grid artifacts.

There are also some minor, but still very important features of simplex noise that make it a more elegant algorithm. For example, there are no internal products, since all contributions from the vertices are made using a spherical core. Even the conversion between a simple grid of coordinates and a Cartesian (or normal) is optimized in one multiplication, which makes it superfast for conversion.

As a shameless self-promotion, I provided a link to my noise function repository , in which I try to implement everything as best as possible. The goal is to provide some standard cross-platform implementation with a bunch of noise features.

Answer 2

Essentially yes, table P is used to select a random gradient from table G. However, it is important that it be repeatable. That is, in the three-dimensional case for a given triple (i,j,k) you always need to have the same “random” gradient. This is what makes the noise function coherent. Thus, the whole point of the formula in which he performs several searches in table P is that the result is random, but it is determined for a given input.

If you weren't concerned about performance, you could just as easily use (i,j,k) to seed a pseudo-random number generator, and then use this to select a gradient from Table G.