noise() hash-function exhibits geometric self-similarity

[cheind]

noise() hash-function exhibits geometric self-similarity

I did a quick analysis of the hash function used in noise() that is used to map from 3D integer coordinates to 1D indices. In essence this is

let of = (xi + (yi << PERLIN_YWRAPB) + (zi << PERLIN_ZWRAPB)) & PERLIN_SIZE

According to quick analysis it distributes input locations uniformly to PERLIN_SIZE which is a good thing :), but when I colored a 2048x2048 image according to the resulting hashed indices I get

where same colors mean same hash values. Here is a top-left zoom of the same image.

What does this mean? For input locations that obey a geometric pattern, the randomness of the noise might be reduced.
If instead, one changes the hash-function to something along the following lines

let of = p[(p[(p[xi & PERLIN_SIZE] + yi) & PERLIN_SIZE] +zi) & PERLIN_SIZE]

where p is permutation table of size PERLIN_SIZE, one gets

Note, I'm unsure if this problem is only of theoretical nature or has been observed practically as well. In case you revise your algorithm anyway, you might want to reconsider the hash function as well. I'm attaching my Python test script for reference.

# Christoph Heindl, https://github.com/cheind/, 2024
import numpy as np
import matplotlib.pyplot as plt

PERLIN_YWRAPB = 7
PERLIN_ZWRAPB = 8
PERLIN_SIZE = 4095
P = np.random.permutation(PERLIN_SIZE)

# Current hash
# def hash_fn(x: np.ndarray):
#     return (
#         x[..., 0]
#         + np.left_shift(x[..., 1], PERLIN_YWRAPB)
#         + np.left_shift(x[..., 2], PERLIN_ZWRAPB)
#     ) & PERLIN_SIZE


# Proposed hash
def hash_fn(x: np.ndarray):
    u = P[x[..., 0] % PERLIN_SIZE]
    v = P[(u + x[..., 1]) % PERLIN_SIZE]
    w = P[(v + x[..., 2]) % PERLIN_SIZE]
    return w


n = 2048
grid = np.stack(np.meshgrid(np.arange(n), np.arange(n)), -1)
grid = np.concatenate((grid, np.zeros((n, n, 1))), -1).astype(int)
h = hash_fn(grid).reshape(-1)

# Check for uniformity
values, counts = np.unique(h, return_counts=True)
plt.vlines(values, 0, counts, color="C0", lw=4)
plt.show()

# Colorize based on hash value to detect geometric similarities
plt.imshow(h.reshape(n, n) / (PERLIN_SIZE - 1))
plt.show()

[limzykenneth]

This is a bit over my head actually. My thinking is that if it does not affect the quality of the noise output it probably is not a problem.