Skip to content

noise() hash-function exhibits geometric self-similarity #7431

@cheind

Description

@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

cur

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

cur2

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

new

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()

Activity

limzykenneth

limzykenneth commented on Jan 20, 2025

@limzykenneth
Member

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

      Development

      No branches or pull requests

        Participants

        @cheind@limzykenneth

        Issue actions

          noise() hash-function exhibits geometric self-similarity · Issue #7431 · processing/p5.js