javascript - 钻石方形算法固定大小

Question

我正在尝试找出一种方法来为以下对象设置固定比例:

https://en.wikipedia.org/wiki/Diamond-square_algorithm

我看到该算法需要数组大小的 2 (+1) 次幂。

我遇到的问题是无论分辨率如何，我都希望生成相同的高度图。因此，如果我的分辨率为 512，它看起来与分辨率 256 相同，但细节较少。我只是想不通如何做到这一点。

我最初的想法是始终在某个维度上创建高度图，例如1024 并下采样到我想要的分辨率。问题是我希望较高的分辨率非常高(例如 4096)，这会严重降低较低分辨率下的性能，因为我们必须以尽可能高的分辨率运行算法。

目前算法在 javascript 中，这里是一个片段:

function Advanced() {
    var adv = {},
    res, max, heightmap, roughness;

    adv.heightmap = function() {
        // heightmap has one extra pixel this is ot remove it.
        var hm = create2DArray(res-1, res-1);
        for(var x = 0;x< res-1;x++) {
            for(var y = 0;y< res-1;y++) {
                hm[x][y] = heightmap[x][y];
            }
        }
        return hm;
    }

    adv.get = function(x,y) {
        if (x < 0 || x > max || y < 0 || y > max) return -1;
        return heightmap[x][y];
    }

    adv.set = function(x,y,val) {
        if(val < 0) {
            val = 0;
        }

        heightmap[x][y] = val;

    }

    adv.divide = function(size) {
        var x, y, half = size / 2;
        var scale = roughness * size;
        if (half < 1) return;

        for (y = half; y < max; y += size) {
            for (x = half; x < max; x += size) {
                adv.square(x, y, half, Math.random() * scale * 2 - scale);
            }
        }
        for (y = 0; y <= max; y += half) {
            for (x = (y + half) % size; x <= max; x += size) {
                adv.diamond(x, y, half, Math.random() * scale * 2 - scale);
            }
        }
        adv.divide(size / 2);
    }

    adv.average = function(values) {
        var valid = values.filter(function(val) {
            return val !== -1;
        });
        var total = valid.reduce(function(sum, val) {
            return sum + val;
        }, 0);
        return total / valid.length;
    }

    adv.square = function(x, y, size, offset) {
        var ave = adv.average([
            adv.get(x - size, y - size), // upper left
            adv.get(x + size, y - size), // upper right
            adv.get(x + size, y + size), // lower right
            adv.get(x - size, y + size) // lower left
        ]);
        adv.set(x, y, ave + offset);
    }

    adv.diamond = function(x, y, size, offset) {

        var ave = adv.average([
            adv.get(x, y - size), // top
            adv.get(x + size, y), // right
            adv.get(x, y + size), // bottom
            adv.get(x - size, y) // left
        ]);

        adv.set(x, y, Math.abs(ave + offset));
    }

    adv.generate = function(properties, resolution) {
        Math.seedrandom(properties.seed);

        res = resolution + 1;
        max = res - 1;
        heightmap = create2DArray(res, res);

        roughness = properties.roughness;

        adv.set(0, 0, max);
        adv.set(max, 0, max / 2);
        adv.set(max, max, 0);
        adv.set(0, max, max / 2);

        adv.divide(max);
    }

    function create2DArray(d1, d2) {
        var x = new Array(d1),
        i = 0,
        j = 0;

        for (i = 0; i < d1; i += 1) {
            x[i] = new Array(d2);
        }

        for (i=0; i < d1; i += 1) {
            for (j = 0; j < d2; j += 1) {
                x[i][j] = 0;
            }
        }

        return x;
    }

    return adv;
}

以前有人做过吗？

Answer 1

不太确定我是否理解您的问题，但如果可以的话，我会提供进一步的说明。

您描述了一种情况，您希望在不放大的情况下以 512 的大小使用分辨率为 256 的菱形正方形高度图。我将通过一个使用 2x2 高度图到 4x4“大小”的示例。

菱形方形高度图实际上是一组顶点而不是瓦片或正方形，因此大小为 2x2 的高度图实际上是一组 3x3 顶点，如下所示:

您可以使用 Angular 的高度来渲染它，或者您可以通过取周围四个点的平均值将它变成一组 2x2 的正方形 - 实际上这只是算法的“正方形”步骤，没有位移步骤。

因此在这种情况下，左上角正方形的“高度”将是 (0, 0)、(0, 1)、(1, 1) 和 (1, 0) 点的平均值。

如果您想以更高的分辨率绘制它，您可以将每个正方形分成一组较小的 4 个正方形，根据它与每个点的接近程度调整平均值。

所以现在最左上角的正方形的值将是它周围的 4 个子点的样本或其相对于它周围的点的位置的样本。但实际上这只是在没有任何位移(没有粗糙度)的情况下再次应用菱形方形算法，因此您不妨再次应用该算法并转到更大的尺寸。

您已经说过，达到您希望达到的大小会让处理器无法处理，因此您可能希望在较小的大小上采用这种采样方法。一种有效的方法是将高度图渲染为纹理并从中采样以及所需的位置。