如何创建一个用于噪声生成的哈希函数

Question

如何创建一个用于噪声生成的哈希函数

5

我最近一直在研究噪声函数，特别是柏林噪声和simplex噪声。我对噪声算法没有任何问题，因为我已经将它们运行起来了，但是我对Ken Perlins使用的哈希方法有些疑问：

一些背景信息：

因此，在这些噪声函数中，您需要为每个坐标获取一个（伪）随机值。在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个指令）。我主要是出于兴趣和学习一些东西。

我的问题是：

用算法替换这种方法的好方法是什么？期望的特性可能是它快速，不会导致视觉伪影，并且不会像这个数组那样重复得快。

我最初想到使用标准哈希函数，但我发现它们有两个不真正需要的属性：哈希函数通常需要任意长的输入，这里并不需要。它们还尝试避免冲突（不同输入的相同输出），这也不是这里所需的。至少如果我正确地认为视觉伪影和冲突之间可能没有强相关性。这两个因素使标准哈希函数看起来不必要地复杂。所需的只是从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();
}

它会产生很多伪影我没有足够的声望来发布图片：/。我怀疑伪随机数生成器不适合这个任务，因为我听说它们通常需要一些时间来“热身”。内部状态会自行推进，它有更长的时间来做这件事，随机数的质量就会更高。通过这种方法，我防止了伪随机数生成器“热身”。另一方面：状态可以被视为一个线性序列的数字。如果我用在这个线性序列中远远的一个数字初始化伪随机数生成器，我不应该立即得到“高质量”的数字吗？

使用这个超级简单的一行代码，有人建议（现在不再是一行代码了）：

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;
}

它表现相当不错，但其中有一些昂贵的操作。

使用Murmur 3哈希函数，它似乎是我能找到的最好的“普通”哈希函数。（我不会在这里发布代码，因为它很大）。它的性能也非常出色，但完成任务需要很长时间。

我正在尝试使用质数进行异或和位移操作，因为我认为这就是伪随机数生成器的工作原理 :D。正如你所想象的那样，它看起来很糟糕（更像抽象艺术而不是随机噪声）。没有关于伪随机数生成器的知识，创建一个伪随机数生成器似乎相当困难。

那么，你有什么建议可以尝试下一步？我认为总的来说，我更想寻找一个哈希函数而不是伪随机数生成器，因为它更符合我在这里尝试实现的目标。

（很抱歉缺少链接和图片，声望系统在这里真的让我很困扰）

- pulp_user

因为那样只会变成一个随机数生成器。噪声函数的优点是对于给定的坐标，你会得到相同的值。如果我只使用伪随机数生成器给出的数字序列，一个点的值将不取决于该点本身，而是取决于它之前的点的序列。 - pulp_user

像 std::linear_congruential_engine 这样的东西怎么样？您可以"预热"它，然后在其"预热"状态下获取引擎的副本（而不是对其进行种子处理）？复制应该很便宜。 - Galik

抱歉，我好像没明白重点。复制一个预热的PRNG会如何帮助我？你是说我应该为每个坐标复制一个吗？如果我这样做，它们都将具有相同的内部状态，因此我将在每个坐标上获得相同的值。 - pulp_user

你在问题中提到你觉得prng需要预热才能产生合理的结果。是的，获得具有相同内部状态的副本将成为种子的替代品，因此关键是以一种方式使用每个坐标，使得prng生成一个数字。例如，让prng生成0和您的坐标之间的数字，然后让prng在正确的范围内生成您的值？ - Galik

当从普通 PRNG 初始化它时，除非更改维度，否则每次都会是相同的。这不够好吗？或者您可以尝试一些其他哈希函数。 - harold

显示剩余8条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- geza · Accepted Answer

两种可能的解决方案：

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位，也许它具有更好的性质)。