ScratchAPixel : Understanding how to use Perlin's permutations hash table

Question

Consider this course : https://www.scratchapixel.com/lessons/procedural-generation-virtual-worlds/procedural-patterns-noise-part-1/creating-simple-2D-noise . In sub-part Introducing the Concept of Permutation (use CTRL||CMD + F), the author explains Ken Perlin uses the array containing noise values to be interpolated (denoted A) in conjunction with another array, which is the "permutation hash table" (denoted B).

The idea is : from any input (a point), we get its unique noise value in A, using B. A has always 256 cases (whatever the input point's dimension is) : it allows to gain in RAM consumption. B has 512 cases : the 255 first randomly contain numbers from {0...255}, idem for the last half part of B.

How to use the permutation table, according to ScratchAPixel ?

There are 2 things I didn't understand.

First, (1/2) I didn't understand how the hash table is actually used. The workflow I think I understood is the following :

1. For an input (coordinate), we find the both nearest pre-defined coordinates (i.e. : those present as indices in A). It's a multiple of 255.

2. The lower one is used to lookup in B

3. We get a number between [0;255] that we use to lookup in A

4. We get a number between [0;1] : the noise.

But where is the interpolation between the both pre-defined coordinates' noise values ?

In which way my understanding is wrong ? I believe you should really read this sub-part (Introducing the Concept of Permutation (use CTRL||CMD + F), https://www.scratchapixel.com/lessons/procedural-generation-virtual-worlds/procedural-patterns-noise-part-1/creating-simple-2D-noise), it's very short and maybe your answer would fit my question more than if you were giving me explanations that possibly would be out of the range of those provided by ScratchAPixel. Thus, I would understand your answer better.

By the way, (2/2) I didn't understand this paragraph neither :

You may wonder why the permutation array is twice the size of the function period (512 in size instead of 256). If we deal with a 2D noise, we will first do a lookup in the permutation table using the integer value for the x coordinate of our input point (as described). This will return an integer value in the range [0:255]. We will add the result of this lookup to the integer value for the input point y coordinate and use the sum of these two numbers as an index of the permutation table again. Since the result of the first permutation lookup is in the range [0:255] and that the integer value for the point's y coordinate is also in the range [0:255], it means that the range of possible index value for the permutation table is [0:511]. Hence the size of the permutation array (512).

I'm getting confused by all the different but likely terms ("integer value", "coordinate", ...).

Answer 1

First, (1/2) I didn't understand how the hash table is actually used. The workflow I think I understood is the following :

1. For an input (coordinate), we find the both nearest pre-defined coordinates (i.e. : those present as indices in A). It's a multiple of 255.

2. The lower one is used to lookup in B

3. We get a number between [0;255] that we use to lookup in A

4. We get a number between [0;1] : the noise.

But where is the interpolation between the both pre-defined coordinates' noise values ?

There are 4 of most of what you wrote here, then the interpolation. For example, if your 2D input is (2.7, 6.4):

1. You would truncate that to (2,6).
2. Then perform the permutation and noise lookup steps for (2,6), (3,6), (2,7), (3,7).
3. And finally perform a 2D interpolation (lerp) of the 4 lookups with the remainder of your input: (0.7, 0.4).

As for the second part of your question, the table is just a creative way to get a "(int, int) -> int" hashing function to go from input coordinates to an index to pick a value in the random data table. You could use any generic hash function instead. In fact, the method used is fairly obsolete for CPUs as it does not lend itself to SIMD implementation and has horrible memory dependencies. It might still have value for GPUs as they have different behavior. But it will have a visible period of 256 which can cause problems in images. So it is really a poor hash function but for the CPUs back then, it was fast and used little memory which is likely why it was picked.

Answer 2

I really haven't read the whole thing. But I think what the author means for the second part is that: The position or coordinate is in a continuous space i.e x = 1.2345 , y = 2.3455 (floating point) The integer value of this is just 1 and 2 respectively.

I hope this helps!