algorithm - 为什么 Perlin 噪声使用哈希函数而不是计算随机值？

Question

我正在通读 this explanation of Perlin noise它描述了一个哈希函数，该函数计算所有 x、y 坐标的随机点。

如果 x、y 坐标散列是随机生成的，最终用于计算梯度等，为什么我不能即时生成随机数？

我们在 HashMap 上使用排列来找到我们的随机值，这仅仅是一个优化问题吗？我能想到的唯一原因是通过我们的 HashMap 的排列有些如何产生平滑效果，但我看不出如何。

为了澄清起见，我指的是代码中的这一部分:

private static readonly int[] p = { 151,160,137,91,90,15,                 // Hash lookup table as defined by Ken Perlin.  This is a randomly
    131,13,201,95,96,53,194,233,7,225,140,36,103,30,69,142,8,99,37,240,21,10,23,    // arranged array of all numbers from 0-255 inclusive.
    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
};

int aaa, aba, aab, abb, baa, bba, bab, bbb;
        aaa = p[p[p[    xi ]+    yi ]+    zi ];
        aba = p[p[p[    xi ]+inc(yi)]+    zi ];
        aab = p[p[p[    xi ]+    yi ]+inc(zi)];
        abb = p[p[p[    xi ]+inc(yi)]+inc(zi)];
        baa = p[p[p[inc(xi)]+    yi ]+    zi ];
        bba = p[p[p[inc(xi)]+inc(yi)]+    zi ];
        bab = p[p[p[inc(xi)]+    yi ]+inc(zi)];
        bbb = p[p[p[inc(xi)]+inc(yi)]+inc(zi)];

为什么我们不按如下方式初始化值？

aaa = random(255)
aab = random(255)
// ...

Answer 1

Perlin 噪声生成背后的关键思想是创建一个点网格，每个点都被分配了一些矢量值，然后以特定方式在这些点之间进行插值。

我 checkout Ken Perlin's original paper on Perlin noise似乎早在他推荐使用散列函数来执行此操作的原始论文中:

Associate with each point in the integer lattice a pseudorandom value and x, y, and z gradient values. More precisely, map each ordered sequence of three integers into an uncorrelated ordered sequence of four real numbers [a,b,c,d] = H([x,y,z]), where [a,b,e,d] define a linear equation with gradient [a,b,c] and value d at [x,y,z]. H is best implemented as a hash function.

(强调我的)。

我怀疑这样做的原因与内存问题有关。 Perlin 噪声的生成要求在算法运行过程中多次重新评估空间中不同点的梯度函数。因此，您可以

1. 有一些公式，给定空间中的一个点，计算梯度，或者
2. 显式创建一个表并存储您需要的所有随机值。

选项 (1) 是 Ken Perlin 提出的。这种方法的优点是存储梯度所需的内存使用量最小；你只需要使用哈希函数。

选项 (2) 是您的提议。这工作得很好，但它使用大量内存(你需要为你正在使用的整数格中的每个点存储多个值)。请记住，Perlin 的论文写于 1985 年(!)，当时内存力比今天稀缺得多。

我怀疑这两种方法都可以逃脱，但考虑到您不需要真正的随机性，一个好的哈希函数提供的伪随机性应该足够了。

不过，我无法解释为什么您阅读的那篇文章的作者选择使用他们使用的特定哈希函数。我的猜测是它“足够随机”并且足够快，以至于它最终不会成为计算中的瓶颈；请记住，哈希函数在噪声生成代码中被多次调用。这似乎是实现 Perlin 噪声的标准方法；甚至 Ken Perlin mentions using this hash function on his site .

您不能做的是您提议的方法，即只让变量aaa、aab、aba 等是随机的。原因是 Perlin 噪声算法要求您多次重新评估给定点的噪声项，并期望它每次都会返回相同的值。如果您想计算真正的随机值，您可以这样做，但您需要缓存您的结果，以便在每个点返回一致的噪声项答案。