为什么 Perlin 噪声使用哈希函数而不是计算随机值?
Why does Perlin noise use a hash function rather than computing random values?
我正在通读 this explanation of Perlin noise,它描述了一个哈希函数,该函数计算所有 x、y 坐标的随机点。
如果 x、y 坐标散列是随机生成的,最终用于计算梯度等,为什么我不能即时生成随机数?
我们在哈希图上使用排列来找到我们的随机值,这仅仅是一个优化问题吗?我能想到的唯一原因是通过我们的哈希映射的排列有些如何产生平滑效果,但我看不出如何。
为了澄清起见,我指的是代码中的这一部分:
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)
// ...
Perlin 噪声生成背后的关键思想是创建一个点网格,为每个点分配一些向量值,然后以特定方式在这些点之间进行插值。
我查看了 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 噪声的生成要求 space 中不同点的梯度函数在算法的 运行 过程中多次重新计算。因此,您可以
- 有一些公式,给定 space 中的一个点,计算梯度,或
- 显式创建一个 table 并存储您需要的所有随机值。
选项 (1) 是 Ken Perlin 提出的。这种方法的优点是存储梯度所需的内存使用量最小;你只需要使用哈希函数。
选项 (2) 是您所提议的。这工作得很好,但它使用大量内存(你需要为你正在使用的整数格中的每个点存储多个值)。请记住,Perlin 的论文是在 1985 年 (!) 写的,当时记忆力比今天少得多。
我怀疑这两种方法都可以逃脱,但考虑到您不需要真正的随机性,一个好的哈希函数提供的伪随机性应该足够了。
不过,我无法解释为什么您阅读的那篇文章的作者选择使用他们所做的特定哈希函数。我的猜测是它“足够随机”并且足够快,以至于它最终不会成为计算中的瓶颈;请记住,哈希函数在噪声生成代码中被多次调用。这似乎是实现 Perlin 噪声的标准方法;甚至 Ken Perlin mentions using this hash function on his site.
您不能做的是您提议的方法,即只让变量 aaa
、aab
、aba
等是随机的。原因是 Perlin 噪声算法要求您多次重新评估给定点的噪声项,并期望它每次都会返回相同的值。如果你想计算真正的随机值,你可以这样做,但你需要缓存你的结果,以便你在每个点返回一致的噪声项答案。
我正在通读 this explanation of Perlin noise,它描述了一个哈希函数,该函数计算所有 x、y 坐标的随机点。
如果 x、y 坐标散列是随机生成的,最终用于计算梯度等,为什么我不能即时生成随机数?
我们在哈希图上使用排列来找到我们的随机值,这仅仅是一个优化问题吗?我能想到的唯一原因是通过我们的哈希映射的排列有些如何产生平滑效果,但我看不出如何。
为了澄清起见,我指的是代码中的这一部分:
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)
// ...
Perlin 噪声生成背后的关键思想是创建一个点网格,为每个点分配一些向量值,然后以特定方式在这些点之间进行插值。
我查看了 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 噪声的生成要求 space 中不同点的梯度函数在算法的 运行 过程中多次重新计算。因此,您可以
- 有一些公式,给定 space 中的一个点,计算梯度,或
- 显式创建一个 table 并存储您需要的所有随机值。
选项 (1) 是 Ken Perlin 提出的。这种方法的优点是存储梯度所需的内存使用量最小;你只需要使用哈希函数。
选项 (2) 是您所提议的。这工作得很好,但它使用大量内存(你需要为你正在使用的整数格中的每个点存储多个值)。请记住,Perlin 的论文是在 1985 年 (!) 写的,当时记忆力比今天少得多。
我怀疑这两种方法都可以逃脱,但考虑到您不需要真正的随机性,一个好的哈希函数提供的伪随机性应该足够了。
不过,我无法解释为什么您阅读的那篇文章的作者选择使用他们所做的特定哈希函数。我的猜测是它“足够随机”并且足够快,以至于它最终不会成为计算中的瓶颈;请记住,哈希函数在噪声生成代码中被多次调用。这似乎是实现 Perlin 噪声的标准方法;甚至 Ken Perlin mentions using this hash function on his site.
您不能做的是您提议的方法,即只让变量 aaa
、aab
、aba
等是随机的。原因是 Perlin 噪声算法要求您多次重新评估给定点的噪声项,并期望它每次都会返回相同的值。如果你想计算真正的随机值,你可以这样做,但你需要缓存你的结果,以便你在每个点返回一致的噪声项答案。