Logic of 2D midpoint subdivide

Question

I understand the concept but am having trouble implementing 2D subdivide. I have a 2D array representing a grid with the corners seeded. I believe I need 3 loops; 1 for the number of subdivide iterations, a second for each column in the row, and a third for each row.

This shows the results of the top-left square subdivide. That is why the row and column loops only once. If I get the basic logic the rest should be cake. However the loop does not work on the third iteration. I'm pretty sure the loop needs to be more complex.

Iterations is a manually set variable:

// iterate though subdivision levels
for(i = 1; i <= iterations; i++) {                  // iteration

    // iterate through each row
    for(row = 1; row <= 1; row += size / i ) {      // row

        // iterate through each column and subdivide
        for(col = 1; col <= 1; col += size / i) {   // column

            //*** ONLY SHOWING THE FIRST SUBDIVIDE OF EACH ITERATION ***//

            // Math.pow(2, iterations) / 2 / i = 1
            // i = 1, iteration = 1
            heightmap[0][1] = (heightmap[0][0] + heightmap[0][2]) / 2;

            // Math.pow(2, iterations) / 2 / i = 2
            // i = 1, iterations = 2
            heightmap[0][2] = (heightmap[0][0] + heightmap[0][4]) / 2;

            // Math.pow(2, iterations) / 2 / i = 4
            // i = 1, iterations = 3
            heightmap[0][4] = (heightmap[0][0] + heightmap[0][8]) / 2;

            // if iterations == 1, i != 2

            // Math.pow(2, iterations) / 2 / i = 1
            // i = 2, iterations = 2
            heightmap[0][1] = (heightmap[0][0] + heightmap[0][2]) / 2;

            // Math.pow(2, iterations) / 2 / i = 2
            // i = 2, iterations = 3
            heightmap[0][2] = (heightmap[0][0] + heightmap[0][4]) / 2;

            // if iterations == 1 or 2, i != 3

            // Math.pow(2, iterations) / 2 / i = 4/3 != 1
            // i = 3, iterations = 3
            heightmap[0][1] = (heightmap[0][0] + heightmap[0][2]) / 2;
        }
    }
}

1D subdivide:

// increase the number of segments
for(var i = 1; i < size; i *= 2){

    // iterate through each segment calculating the center point
    for(var j = (size / i) / 2; j < size; j += size / i){
        points[j] = ((points[j - (size / i) / 2] + points[j + (size / i) / 2]) / 2);
    }

}

Answer 1

It would be easier to subdivide one direction at the time:

var points = [[ 0,-1,-1,-1, 1],
              [-1,-1,-1,-1,-1],
              [-1,-1,-1,-1,-1],
              [-1,-1,-1,-1,-1],
              [ 2,-1,-1,-1, 0]];
var size = 4;

for (var iteration = 1; iteration < size; iteration *= 2) {
    var step = size / iteration;

    // * . * . *
    // x . x . x
    // * . * . *
    for (var row = step / 2; row < size; row += step) {
        for (var col = 0; col <= size; col += step) {
            points[row][col] = ((points[row - step / 2][col] + points[row + step / 2][col]) / 2);
        }
    }

    // * x * x *
    // * x * x *
    // * x * x *
    for (var row = 0; row <= size; row += step / 2) {
        for (var col = step / 2; col < size; col += step) {
            points[row][col] = ((points[row][col - step / 2] + points[row][col + step / 2]) / 2);
        }
    }
}

The result is:

[[ 0,   0.25,   0.5,   0.75,   1    ],
 [ 0.5, 0.5625, 0.625, 0.6875, 0.75 ],
 [ 1,   0.875,  0.75,  0.625,  0.5  ],
 [ 1.5, 1.1875, 0.875, 0.5625, 0.25 ],
 [ 2,   1.5,    1,     0.5,    0    ]]