logo标签列表

从梅森旋转生成器切换到其他伪随机数生成器为何在渐变噪声生成器中会产生不良结果？

c++randomnoiseperlin-noiseprocedural-generation
6
我一直在尝试创建一个通用的渐变噪声生成器（不使用哈希方法获取渐变）。以下是代码：
class GradientNoise {
    std::uint64_t m_seed;
    std::uniform_int_distribution<std::uint8_t> distribution;
    const std::array<glm::vec2, 4> vector_choice = {glm::vec2(1.0, 1.0), glm::vec2(-1.0, 1.0), glm::vec2(1.0, -1.0),
                                                    glm::vec2(-1.0, -1.0)};

public:
    GradientNoise(uint64_t seed) {
        m_seed = seed;
        distribution = std::uniform_int_distribution<std::uint8_t>(0, 3);
    }

    // 0 -> 1
    // just passes the value through, origionally was perlin noise activation
    double nonLinearActivationFunction(double value) {
        //return value * value * value * (value * (value * 6.0 - 15.0) + 10.0);
        return value;
    }

    // 0 -> 1
    //cosine interpolation
    double interpolate(double a, double b, double t) {
        double mu2 = (1 - cos(t * M_PI)) / 2;
        return (a * (1 - mu2) + b * mu2);
    }

    double noise(double x, double y) {
        std::mt19937_64 rng;
        //first get the bottom left corner associated
        // with these coordinates
        int corner_x = std::floor(x);
        int corner_y = std::floor(y);

        // then get the respective distance from that corner
        double dist_x = x - corner_x;
        double dist_y = y - corner_y;

        double corner_0_contrib; // bottom left
        double corner_1_contrib; // top left
        double corner_2_contrib; // top right
        double corner_3_contrib; // bottom right

        std::uint64_t s1 = ((std::uint64_t(corner_x) << 32) + std::uint64_t(corner_y) + m_seed);
        std::uint64_t s2 = ((std::uint64_t(corner_x) << 32) + std::uint64_t(corner_y + 1) + m_seed);
        std::uint64_t s3 = ((std::uint64_t(corner_x + 1) << 32) + std::uint64_t(corner_y + 1) + m_seed);
        std::uint64_t s4 = ((std::uint64_t(corner_x + 1) << 32) + std::uint64_t(corner_y) + m_seed);


        // each xy pair turns into distance vector from respective corner, corner zero is our starting corner (bottom
        // left)
        rng.seed(s1);
        corner_0_contrib = glm::dot(vector_choice[distribution(rng)], {dist_x, dist_y});

        rng.seed(s2);
        corner_1_contrib = glm::dot(vector_choice[distribution(rng)], {dist_x, dist_y - 1});


        rng.seed(s3);
        corner_2_contrib = glm::dot(vector_choice[distribution(rng)], {dist_x - 1, dist_y - 1});


        rng.seed(s4);
        corner_3_contrib = glm::dot(vector_choice[distribution(rng)], {dist_x - 1, dist_y});


        double u = nonLinearActivationFunction(dist_x);
        double v = nonLinearActivationFunction(dist_y);


        double x_bottom = interpolate(corner_0_contrib, corner_3_contrib, u);
        double x_top = interpolate(corner_1_contrib, corner_2_contrib, u);
        double total_xy = interpolate(x_bottom, x_top, v);
        return total_xy;
    }
};

我会生成一个OpenGL纹理来展示它，就像这样：
int width = 1024;
int height = 1024;
unsigned char *temp_texture = new unsigned char[width*height * 4];
double octaves[5] = {2,4,8,16,32};

for( int i = 0; i < height; i++){
    for(int j = 0; j < width; j++){
        double d_noise = 0;
        d_noise += temp_1.noise(j/octaves[0], i/octaves[0]);
        d_noise += temp_1.noise(j/octaves[1], i/octaves[1]);
        d_noise += temp_1.noise(j/octaves[2], i/octaves[2]);
        d_noise += temp_1.noise(j/octaves[3], i/octaves[3]);
        d_noise += temp_1.noise(j/octaves[4], i/octaves[4]);
        d_noise/=5;
        uint8_t noise = static_cast<uint8_t>(((d_noise * 128.0) + 128.0));
        temp_texture[j*4 + (i * width * 4) + 0] = (noise);
        temp_texture[j*4 + (i * width * 4) + 1] = (noise);
        temp_texture[j*4 + (i * width * 4) + 2] = (noise);
        temp_texture[j*4 + (i * width * 4) + 3] = (255);
    }
}

哪些能够得到好的结果：

enter image description here

但是 gprof 告诉我 Mersenne twister 占用了 62.4% 的时间，并且随着纹理的增大而增长。没有其他单独的部分需要花费那么多时间。虽然 Mersenne twister 在初始化后很快，但每次使用它时都要初始化它，这似乎使它变得相当慢。
这种初始化对于确保相同的 x 和 y 在每个整数点生成相同的渐变是 100% 必需的（因此您需要哈希函数或每次播种 RNG）。
我尝试将 PRNG 更改为线性同余发生器和 Xorshiftplus，虽然两者运行速度都快了几个数量级，但结果很奇怪：
LCG（一次，然后在使用之前运行 5 次） enter image description here

enter image description here

Xorshiftplus

一次迭代后enter image description here

经过10000次迭代后enter image description here

我已尝试：

在使用输出之前多次运行生成器，结果执行速度较慢或不同的工件。

使用初始种子后两个连续运行的输出来重新播种PRNG并在此后使用该值。结果没有差异。

发生了什么？如何获得与mersenne twister相同质量的更快结果？

大更新：

我不知道为什么这样可以运行，我知道它与使用的质数有关，但是经过一些尝试，似乎以下方法有效：

第一步，将x和y值分别作为种子合并（并与它们结合一些其他偏移值或附加种子值，这个数应该是质数/非平凡因子）

第二步，将这两个种子结果再次用于生成器的种子中，然后再次进入函数（就像geza所说，所做的种子很糟糕）

第三步，在获取结果时，不要使用模数项数（4）尝试获取，或者& 3，首先将结果模以质数，然后应用& 3。我不确定梅森质数是否重要。

以下是使用prime = 257和xorshiftplus的结果！（请注意，我在这个示例中使用了2048 x 2048，而其他示例则为256 x 256）

enter image description here

1
顺便问一下，为什么rng是类成员而不是自动变量？ - Deduplicator
1
你正在使用PRNG作为一个非常昂贵的哈希函数。尝试使用实际的（加密的？）哈希函数来替代。 - yuri kilochek
@snb：这是哪个xorshift随机数生成器？也许你发现了一些东西，创造者们可能会感兴趣。新的xorshift生成器被认为非常好。 - geza
@snb：嗯，实际上我更担心随机数生成器而不是哈希函数。你说你比理解哈希更了解MT？ :) 我会建议你尝试基于哈希的噪声生成。随机生成器在这种情况下表现不佳。 - geza
@snb：好的，我不想和你争论:)但事实上，理解一个好的随机生成器的工作原理，以及为什么它好，是困难的。实际上，我认为没有人确切知道为什么随机生成器是好的。我们所拥有的只是测试，用来测试生成器。PRNG是黑魔法。你应该查看Bob Jenkins integer hash page。你可以在Bob的网站上找到如何设计哈希函数的信息。 - geza
显示剩余9条评论
5个回答
4
LCG已知对您的目的不足。
Xorshift128+的结果很糟糕，因为它需要良好的种子。而提供良好的种子会破坏使用它的全部目的。我不推荐使用这个。
然而，我建议使用整数哈希。例如，来自Bob's page的哈希之一。
这是那个页面第一个哈希的结果，看起来还不错，而且速度很快（我认为比Mersenne Twister快得多）：enter image description here 这是我编写的生成此代码：
#include <cmath>
#include <stdio.h>

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

unsigned int ivalue(int x, int y) {
    return hash(y<<16|x)&0xff;
}

float smooth(float x) {
    return 6*x*x*x*x*x - 15*x*x*x*x + 10*x*x*x;
}

float value(float x, float y) {
    int ix = floor(x);
    int iy = floor(y);
    float fx = smooth(x-ix);
    float fy = smooth(y-iy);

    int v00 = ivalue(iy+0, ix+0);
    int v01 = ivalue(iy+0, ix+1);
    int v10 = ivalue(iy+1, ix+0);
    int v11 = ivalue(iy+1, ix+1);
    float v0 = v00*(1-fx) + v01*fx;
    float v1 = v10*(1-fx) + v11*fx;
    return v0*(1-fy) + v1*fy;
}

unsigned char pic[1024*1024];

int main() {
    for (int y=0; y<1024; y++) {
        for (int x=0; x<1024; x++) {
            float v = 0;

            for (int o=0; o<=9; o++) {
                v += value(x/64.0f*(1<<o), y/64.0f*(1<<o))/(1<<o);
            }

            int r = rint(v*0.5f);

            pic[y*1024+x] = r;
        }
    }

    FILE *f = fopen("x.pnm", "wb");
    fprintf(f, "P5\n1024 1024\n255\n");
    fwrite(pic, 1, 1024*1024, f);
    fclose(f);
}

如果您想了解哈希函数是如何工作的（或者更好的是，一个好的哈希函数具有哪些属性），可以查看Bob的网页，例如this。
我不想让这段代码变得更加复杂。它只有八度求和。为了检查哈希质量，这已经足够了。 - geza
我有点困惑，这是你用来创建上面那张图片的确切代码吗？我不明白它是如何在没有渐变的情况下工作的:/ - Krupip
我以为你需要渐变色；那么渐变色实际上有什么用呢？看起来这个结果很好。代码让它看起来像随机值噪声。 - Krupip
@snb：我认为这是一种创建噪声纹理的不同方法。结果看起来相似。但是Perlin噪声（以及这种噪声）之所以大多数看起来像这样，是因为八度求和。如果您删除求和，则噪声变得更加“简单”。 - geza
我花了一些时间，但你是100％正确的，那些随机数生成器的性质使得连续输入难以使用并生成均匀的随机结果，它们不是为此目的而制作的，它们的雪崩效应很糟糕，因此连续种子通常会共享一些相关性，除非您应用单独的操作（即Mersenne质数或重新利用x和y的输出值作为种子来“随机化”它）。哈希数字是这个应用程序的用例，我们正在尝试从不同的数字中获得非常不同的结果，而不是生成没有输入的新数字。 - Krupip
显示剩余2条评论
2

您（是否无意中）实现了一个伪随机数生成器的可视化非随机模式。这看起来非常酷！

除梅森旋转法之外，您测试的所有伪随机数生成器都似乎不适合您的目的。由于我自己没有进行进一步的测试，我只能建议尝试并测量更多的伪随机数生成器。

看到我的更新帖子，显然它们确实满足要求，只是需要对质数进行一些调整，我不明白为什么！ - Krupip
1

众所周知，线性同余生成器的随机性对其参数的选择非常敏感。特别是，LCG的周期相对于m参数而言——最多为m（您的质因数），对于许多值，它可能会更少。

同样地，需要仔细选择参数才能从Xorshift PRNG中获得长周期。

你已经注意到某些PRNG产生了良好的过程式生成结果，而其他一些则没有。为了分离出原因，我建议将过程式生成部分剥离出去，直接检查PRNG的输出。一种可视化数据的简单方法是构建一个灰度图像，其中每个像素值都是一个（可能经过缩放的）随机值。对于基于图像的内容，我发现这是一种易于发现可能导致视觉瑕疵的方法。如果你在这里看到任何瑕疵，它们很可能会影响你的过程式生成输出。

另一个选择是尝试类似于Diehard tests这样的东西。如果上述图像测试未能揭示任何问题，我可能会使用它来确保我的伪随机数生成技术是可信的。

1
请注意，您的代码会初始化伪随机数生成器（PRNG），之后从 PRNG 生成一个伪随机数。你发现 xorshift128+ 不随机的原因是在改变状态之前，xorshift128+ 简单地将种子的两个半部分相加（并使用结果 mod 264 作为生成的数字）。这使得该 PRNG 与哈希函数有很大的不同（请查看其 源代码）。
0

您所看到的是PRNG质量的实际演示。Mersenne Twister是性能良好的最佳PRNG之一，它通过了DIEHARD测试。应该知道，生成随机数并不是一项简单的计算任务，因此寻求更好的性能必然会导致较差的质量。LCG被认为是设计得最简单且最糟糕的PRNG，并且如您的图片所示，它清楚地展示了二维相关性。Xorshift产生器的质量在很大程度上取决于位数和参数。它们绝对比Mersenne Twister差，但某些（例如xorshift128+）可能足够好以通过BigCrush和TestU01测试。

换句话说，如果您正在进行重要的物理建模数值实验，则最好继续使用Mersenne Twister，因为它是速度和质量之间的良好折衷方案，并且可以在许多标准库中找到。对于不太重要的情况，您可以尝试使用xorshift128+生成器。对于最终结果，您需要使用具有密码学质量的PRNG（这里提到的任何一种都不能用于密码学目的）。

3
不要夸大其词，LCG并不是有史以来设计最简单且最糟糕的伪随机数生成器。冯·诺依曼使用的“中位平方方法”真的让他陷入了困境，因为它存在某些种子值的固定点行为和非常短的周期。 - pjs
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接