c++ - 如何创建用于噪声生成的哈希函数

Question

我最近在研究噪声函数，即 perlin 噪声和单纯形噪声。我对噪声算法没有任何疑问，因为我已经启动并运行了它们，但我对 ken perlin 使用的散列方法有一些疑问:

一些上下文:

因此，在这些噪声函数中，每个坐标都需要一个(伪)随机值。在 Ken Perlins 的实现中，他使用查找表来获取这些值:

static const U8 perlin_hash_values[] = {
151,160,137, 91, 90, 15,131, 13,201, 95, 96, 53,194,233,  7,225,
140, 36,103, 30, 69,142,  8, 99, 37,240, 21, 10, 23,190,  6,148,
247,120,234, 75,  0, 26,197, 62, 94,252,219,203,117, 35, 11, 32,
57,177, 33, 88,237,149, 56, 87,174, 20,125,136,171,168, 68,175,
74,165, 71,134,139, 48, 27,166, 77,146,158,231, 83,111,229,122,
60,211,133,230,220,105, 92, 41, 55, 46,245, 40,244,102,143, 54,
65, 25, 63,161,  1,216, 80, 73,209, 76,132,187,208, 89, 18,169,
200,196,135,130,116,188,159, 86,164,100,109,198,173,186,  3, 64,
52,217,226,250,124,123,  5,202, 38,147,118,126,255, 82, 85,212,
207,206, 59,227, 47, 16, 58, 17,182,189, 28, 42,223,183,170,213,
119,248,152,  2, 44,154,163, 70,221,153,101,155,167, 43,172,  9,
129, 22, 39,253, 19, 98,108,110, 79,113,224,232,178,185,112,104,
218,246, 97,228,251, 34,242,193,238,210,144, 12,191,179,162,241,
81, 51,145,235,249, 14,239,107, 49,192,214, 31,181,199,106,157,
184, 84,204,176,115,121, 50, 45,127,  4,150,254,138,236,205, 93,
222,114, 67, 29, 24, 72,243,141,128,195, 78, 66,215, 61,156,180,

151,160,137, 91, 90, 15,131, 13,201, 95, 96, 53,194,233,  7,225,
140, 36,103, 30, 69,142,  8, 99, 37,240, 21, 10, 23,190,  6,148,
247,120,234, 75,  0, 26,197, 62, 94,252,219,203,117, 35, 11, 32,
57,177, 33, 88,237,149, 56, 87,174, 20,125,136,171,168, 68,175,
74,165, 71,134,139, 48, 27,166, 77,146,158,231, 83,111,229,122,
60,211,133,230,220,105, 92, 41, 55, 46,245, 40,244,102,143, 54,
65, 25, 63,161,  1,216, 80, 73,209, 76,132,187,208, 89, 18,169,
200,196,135,130,116,188,159, 86,164,100,109,198,173,186,  3, 64,
52,217,226,250,124,123,  5,202, 38,147,118,126,255, 82, 85,212,
207,206, 59,227, 47, 16, 58, 17,182,189, 28, 42,223,183,170,213,
119,248,152,  2, 44,154,163, 70,221,153,101,155,167, 43,172,  9,
129, 22, 39,253, 19, 98,108,110, 79,113,224,232,178,185,112,104,
218,246, 97,228,251, 34,242,193,238,210,144, 12,191,179,162,241,
81, 51,145,235,249, 14,239,107, 49,192,214, 31,181,199,106,157,
184, 84,204,176,115,121, 50, 45,127,  4,150,254,138,236,205, 93,
222,114, 67, 29, 24, 72,243,141,128,195, 78, 66,215, 61,156,180};

坐标映射到这样的值:

return perlin_hash_values[perlin_hash_values[y & 255] + x & 255];

我对此有一些问题:它占用内存，重复速度非常快，而且不可播种(至少引用实现是这样。我猜你可以只使用 3D Perlin 噪声，z 值用作种子)和我想知道是否可以走得更快。 (可能不是，因为数组很可能在缓存中，而且很难击败 2 次内存读取和 3 条指令)。我这样做主要是为了好玩和学习一些东西。

我的问题是:

用算法替换此方法的好方法是什么？理想的属性可能是它速度快，不会导致视觉伪影并且不会像这个数组一样快速重复。

我首先想到使用标准散列函数，但我发现它们有 2 个并不真正需要的属性:散列函数通常采用任意长输入，此处不需要。他们还试图避免冲突(不同输入的相同输出)，这在此处也不是必需的。至少如果我认为视觉伪影和碰撞之间可能没有很强的相关性是正确的。这两个因素使标准哈希函数看起来不必要地复杂。所需要的只是从 N 维到看起来随机的 1 维的映射。

到目前为止我尝试了什么:

---

采用 xorshift* 伪随机数生成器:我将内部 64 位状态设置为 x 和 y 连接的值。

F32 xor_shift_star_adaption(S32 x, S32 y, U32 seed) {
    union concat_S32
    {
        S32 s[2];
        U64 u;
    };
    concat_S32 temp;
    temp.s[0] = x;
    temp.s[1] = y;
    xorshift_star_64 xor;
    xor.state = temp.u;
    return xor.get_random_number();
}

It produces a LOT of artifacts我没有足够的声誉来发布图片:/。我怀疑伪随机数生成器不太适合这项任务，因为我听说它们通常需要一些时间来“预热”。内部状态会 self 提升，时间越长，随机数的质量就越高。通过这种方法，我可以防止 prng “预热”。另一方面:状态可以被认为是数字的线性序列。如果我用一个在这个线性序列中很长一段距离的数字初始化 prng，我不应该立即得到“高质量”的数字吗？

---

使用有人建议的这个 super 简单的单线(现在不再是单线):

F32 internet_oneliner(S32 x, S32 y, U32 seed){
    F32 xf = x;
    F32 yf = y;

    F32 dot = xf * 12.9898 + yf * 78.233;
    F32 sin = sinf(dot)  * 43758.5453;
    F32 fract = sin - floorf(sin);
    return fract;
}

它performs pretty well ，但其中有一些昂贵的操作。

---

使用 Murmur 3 哈希函数，它似乎是(？)我能找到的最好的“普通”哈希函数。 (我不会在这里发布代码，它很大)。它的性能也非常好，但也需要很长时间才能完成工作。

---

尝试用质数做一些异或和移位的东西，因为我认为这就是 prngs 的工作方式:D。可以想象，它看起来很可怕(比随机噪音更接近抽象艺术)。如果不了解它们，创建 prng 似乎是不可能的。

---

那么，您对下一步尝试什么有什么建议吗？我认为一般来说我更希望寻找哈希函数而不是 prng，因为它更符合我在这里试图实现的目标。

(很抱歉缺少链接和图片，信誉系统真的把我搞砸了)

Answer 1

两种可能的解决方案:

a) 使用二维随机表。如果它适合 L1 缓存，它会很快。

b) 使用整数散列:http://burtleburtle.net/bob/hash/integer.html

例如，这个:

uint32_t hash( uint32_t a)
    a = (a ^ 61) ^ (a >> 16);
    a = a + (a << 3);
    a = a ^ (a >> 4);
    a = a * 0x27d4eb2d;
    a = a ^ (a >> 15);
    return a;
}

使用 (hash((y<<8)+x)&0xff)。

甚至，由于它是一个完整的 32 位哈希，而您只需要 8 位输出，您可以找到更快的变体。也许只是从这个哈希函数中删除一些操作:)(你不仅可以尝试最低的 8 位，还可以尝试最高的 8 位，也许它有更好的属性)