Fixing every other row is displaced in Value Noise algorithm implementation

Question

Below is my Value Noise implementation, which I'm using for terrain generation. It creates strange artifacts when the terrain's length (Y size) is longer than its width (X size), but not otherwise.

I've been staring at this for hours. Any idea what's causing this?

(Screenshots from the demo. You can mess with the code in your browser console and see the results immediately by putting THREE.Terrain.Value = ValueNoise; rebuild(); after the code below.)

1:1 Aspect Ratio:

1:1.1 Aspect Ratio:

/**
 * Generate a heightmap using white noise.
 *
 * @param {Vector3[]} g The terrain vertices.
 * @param {Object} options Settings
 * @param {Number} scale The resolution of the resulting heightmap.
 * @param {Number} segments The width of the target heightmap.
 * @param {Number} range The altitude of the noise.
 * @param {Number[]} data The target heightmap.
 */
function WhiteNoise(g, options, scale, segments, range, data) {
    if (scale > segments) return;
    var i = 0,
        j = 0,
        xl = segments,
        yl = segments,
        inc = Math.floor(segments / scale),
        k;
    // Walk over the target. For a target of size W and a resolution of N,
    // set every W/N points (in both directions).
    for (i = 0; i <= xl; i += inc) {
        for (j = 0; j <= yl; j += inc) {
            k = j * xl + i;
            data[k] = Math.random() * range;
            /* c b *
             * l t */
            var t = data[k],
                l = data[ j      * xl + (i-inc)] || t, // left
                b = data[(j-inc) * xl +  i     ] || t, // bottom
                c = data[(j-inc) * xl + (i-inc)] || t; // corner
            // Interpolate between adjacent points to set the height of
            // higher-resolution target data.
            for (var lastX = i-inc, x = lastX; x < i; x++) {
                for (var lastY = j-inc, y = lastY; y < j; y++) {
                    if (x === lastX && y === lastY) continue;
                    var px = ((x-lastX) / inc),
                        py = ((y-lastY) / inc),
                        r1 = px * b + (1-px) * c,
                        r2 = px * t + (1-px) * l;
                    data[y * xl + x] = py * r2 + (1-py) * r1;
                }
            }
        }
    }
    // Assign the temporary data back to the actual terrain heightmap.
    // Accumulate additively across multiple calls to WhiteNoise.
    for (i = 0, xl = options.xSegments + 1; i < xl; i++) {
        for (j = 0, yl = options.ySegments + 1; j < yl; j++) {
            k = j * xl + i;
            g[k].z += data[k] || 0;
        }
    }
}

/**
 * Generate random terrain using value noise.
 *
 * The basic approach of value noise is to generate white noise at a
 * smaller octave than the target and then interpolate to get a higher-
 * resolution result. This is then repeated at different resolutions.
 *
 * @param {Vector3[]} g The terrain vertices.
 * @param {Object} options Settings
 */
ValueNoise = function(g, options) {
    // Set the segment length to the smallest power of 2 that is greater
    // than the number of vertices in either dimension of the plane
    var segments = Math.max(options.xSegments, options.ySegments) + 1, n;
    for (n = 1; Math.pow(2, n) < segments; n++) {}
    segments = Math.pow(2, n);

    // Store the array of white noise outside of the WhiteNoise function to
    // avoid allocating a bunch of unnecessary arrays; we can just
    // overwrite old data each time WhiteNoise() is called.
    var data = new Array(segments*(segments+1));

    // Layer white noise at different resolutions.
    var range = options.maxHeight - options.minHeight;
    for (var i = 2; i < 7; i++) {
        WhiteNoise(g, options, Math.pow(2, i), segments, range * Math.pow(2, 2.4-i*1.2), data);
    }

    // Clamp and stretch the results
    THREE.Terrain.Clamp(g, {
        maxHeight: options.maxHeight,
        minHeight: options.minHeight,
        stretch: true,
    });
};

Answer 1

When you assign the height change of the temporary data field, you really have two different indices, because you have two different map sizes: the original map and the temporary map inflated to the next power of 2. So:

for (i = 0, xl = options.xSegments + 1; i < xl; i++) {
    for (j = 0, yl = options.ySegments + 1; j < yl; j++) {
        var kg = j * xl + i;
        var kd = j * segments + i;

        g[kg] += data[kd];
    }
}

I also think that you might have an off-by-one error in your data index. The size of data should be (segments + 1) * (segments + 1), because you need the outer cells in both dimensions and your xl and yl should be segments + 1.