3
\$\begingroup\$

I wrote a small JavaScript implementation of the Diamond-Square height map/texture algorithm and the result is much more industrial-looking than I expected. I can trace a diamond pattern throughout (maybe I should have expected that given the name? 😉 ).

Any idea what I could be doing wrong?

A screenshot of my result

Here's the code I'm using:

const textureCanvas = document.getElementById('texture');
const ctx = textureCanvas.getContext('2d');

const levelInput = document.getElementById('level');
const topLeftHeightInput = document.getElementById('tl');
const topRightHeightInput = document.getElementById('tr');
const bottomLeftHeightInput = document.getElementById('bl');
const bottomRightHeightInput = document.getElementById('br');

levelInput.addEventListener('input', render);
topLeftHeightInput.addEventListener('input', render);
topRightHeightInput.addEventListener('input', render);
bottomLeftHeightInput.addEventListener('input', render);
bottomRightHeightInput.addEventListener('input', render);


render();

function render () {
  const level = Number(levelInput.value);
  const span = Math.pow(2,level) + 1;
  textureCanvas.width = span;
  textureCanvas.height = span;

  // initialize height data container
  const heightData = Array(span);
  for (let x = 0; x < span; x++) {
    heightData[x] = Array(span);
  }

  // compute heights via Diamond Square algorithm
  heightData[0][0] = Number(topLeftHeightInput.value);
  heightData[span - 1][0] = Number(topRightHeightInput.value);
  heightData[0][span - 1] = Number(bottomLeftHeightInput.value);
  heightData[span - 1][span - 1] = Number(bottomRightHeightInput.value);
  const maxHeight = Math.max(
    heightData[0][0],
    heightData[span - 1][0],
    heightData[0][span - 1],
    heightData[span - 1][span - 1],
    diamondSquare(heightData, level) // performs diamond square algorithm
  );

  // convert heights to image data for canvas
  const imageData = ctx.createImageData(span, span);
  const { data } = imageData;
  for (let y = 0; y < span; y++) {
    for (let x = 0; x < span; x++) {
      const brightness = Math.round(heightData[x][y] / maxHeight * 255);
      data[y * span * 4 + x * 4 + 0] = brightness; // r
      data[y * span * 4 + x * 4 + 1] = brightness; // g
      data[y * span * 4 + x * 4 + 2] = brightness; // b
      data[y * span * 4 + x * 4 + 3] = 255;        // a
    }
  }

  ctx.putImageData(imageData, 0, 0);
}


// implementation based on visual description at:
// https://en.wikipedia.org/wiki/Diamond-square_algorithm#Visualization
// NOTE: mutates heightData.
function diamondSquare (heightData, level) {
  let maxHeight = 0;

  if (level < 1) {
    return maxHeight;
  }

  const interval = Math.pow(2, level);
  const half = Math.pow(2, level - 1);

  // diamond step
  for (let yOffset = 0; yOffset + 1 < heightData.length; yOffset += interval) {
    for (let xOffset = 0; xOffset + 1 < heightData.length; xOffset += interval) {
      heightData[xOffset + half][yOffset + half] = (
        heightData[xOffset + 0][yOffset + 0] +
        heightData[xOffset + half * 2][yOffset + 0] +
        heightData[xOffset + 0][yOffset + half * 2] +
        heightData[xOffset + half * 2][yOffset + half * 2]
      ) / 4 + Math.random() * interval;

      maxHeight = Math.max(
        maxHeight,
        heightData[xOffset + half][yOffset + half]
      );
    }
  }

  // square step
  for (let yOffset = 0; yOffset + 1 < heightData.length; yOffset += interval) {
    for (let xOffset = 0; xOffset + 1 < heightData.length; xOffset += interval) {
      const noTopCorner = yOffset <= 0;
      heightData[xOffset + half][yOffset + 0] = (
        (noTopCorner ? 0 : heightData[xOffset + half][yOffset - half]) +
        heightData[xOffset + half][yOffset + half] +
        heightData[xOffset + 0][yOffset + 0] +
        heightData[xOffset + half * 2][yOffset + 0]
      ) / (noTopCorner ? 3 : 4) + Math.random() * interval;
      const noBottomCorner = yOffset + half * 2 + 1 >= heightData.length;
      heightData[xOffset + half][yOffset + half * 2] = (
        heightData[xOffset + half][yOffset + half] +
        (noBottomCorner ? 0 : heightData[xOffset + half][yOffset + half * 3]) +
        heightData[xOffset + 0][yOffset + half * 2] +
        heightData[xOffset + half * 2][yOffset + half * 2]
      ) / (noBottomCorner ? 3 : 4) + Math.random() * interval;
      const noLeftCorner = xOffset <= 0;
      heightData[xOffset + 0][yOffset + half] = (
        heightData[xOffset + 0][yOffset + 0] +
        heightData[xOffset + 0][yOffset + half * 2] +
        (noLeftCorner ? 0 : heightData[xOffset - half][yOffset + half]) +
        heightData[xOffset + half][yOffset + half]
      ) / (noLeftCorner ? 3 : 4) + Math.random() * interval;
      const noRightCorner = xOffset + half * 2 + 1 >= heightData.length;
      heightData[xOffset + half * 2][yOffset + half] = (
        heightData[xOffset + half * 2][yOffset + 0] +
        heightData[xOffset + half * 2][yOffset + half * 2] +
        heightData[xOffset + half][yOffset + half] +
        (noRightCorner ? 0 : heightData[xOffset + half * 3][yOffset + half])
      ) / (noRightCorner ? 3 : 4) + Math.random() * interval;

      maxHeight = Math.max(
        maxHeight,
        heightData[xOffset + half][yOffset + half],
        heightData[xOffset + half][yOffset + 0],
        heightData[xOffset + half][yOffset + half * 2],
        heightData[xOffset + 0][yOffset + half],
        heightData[xOffset + half * 2][yOffset + half]
      );
    }
  }

  return Math.max(maxHeight, diamondSquare(heightData, level - 1));
}
  <h1>Diamond Square texturing</h1>
  <div id="inputs">
    <label>
      Level <input id="level" type="number" step="1" min="1" max="20" value="8">
    </label>
    <br/>
    <label>
      Top-left-height
      <input id="tl" type="number" step="0.1" min="0" max="20" value="2">
    </label>
    <br/>
    <label>
      Top-right-height
      <input id="tr" type="number" step="0.1" min="0" max="20" value="17">
    </label>
    <br/>
    <label>
      Bottom-left-height
      <input id="bl" type="number" step="0.1" min="0" max="20" value="4">
    </label>
    <br/>
    <label>
      Bottom-right-height
      <input id="br" type="number" step="0.1" min="0" max="20" value="9">
    </label>
  </div>
  <canvas id="texture"></canvas>
  

\$\endgroup\$

2 Answers 2

2
\$\begingroup\$

Your code cites the Wikipedia article, which in turn has a section called "Artifacts and Extensions" that observes a potential problem:

The diamond-square algorithm was analyzed by Gavin S. P. Miller in SIGGRAPH 1986 who described it as flawed because the algorithm produces noticeable vertical and horizontal "creases" due to the most significant perturbation taking place in a rectangular grid.

And a solution:

The grid artifacts were addressed in a generalized algorithm introduced by J.P. Lewis. In this variant the weights on the neighboring points are obtained by solving a small linear system motivated by estimation theory, rather than being fixed.

Some of these artifacts are present in the example image on Wikipedia. Here's the original image & a copy where I've flagged some of the artifacts. I marked 'high artifacts' in yellow & 'low artifacts' in pink:

enter image description here enter image description here

I did the flagging by free hand, so they might be off by a few pixels here & there, but we can noticed some trends: the artifacts tend to manifest as horizontal & vertical lines & the lines tend to align with each in a grid pattern. Your are also grid aligned, but tend to show up as lines cutting at 45 degrees. So I think there's something else going on here. If I understand your code correctly, it looks like you're doing a diamond step & a square step for each level - my understanding is that the diamond and square steps are supposed to be performed alternately.

\$\endgroup\$
3
  • \$\begingroup\$ note: at the moment I can't add illustrations describing the problem or solution. Assuming no one else adds them for me, I'll try to add them in later today. \$\endgroup\$
    – Pikalek
    Commented Nov 20, 2017 at 16:14
  • \$\begingroup\$ Are you sure I even implemented the wikipedia version correctly? None of the images I google for diamond square texture resemble my result very closely. And thanks for the help! If you're able to add illustrations I'd appreciate it. \$\endgroup\$
    – Ben Wiley
    Commented Nov 20, 2017 at 19:12
  • \$\begingroup\$ I've revised my answer to include some illustrations, and some conjecture about your problem. I also removed some stuff that didn't apply to this problem - I had some info that applied to certain implementation of value noise, but not diamond-square - sorry for the confusion. \$\endgroup\$
    – Pikalek
    Commented Nov 20, 2017 at 23:46
2
\$\begingroup\$

While this is an old question, it still ranks on google and the marked answer does not explain the artefacts seen in the output.

I have just implemented this algorithm (for fun) in c# using linqpad and had what seems to be exactly the same problem. I managed to figure out that the pattern appears due to the way one calculates the random values that are always added to the pixels. If you only allow positive random numbers, it seems the original corners are "left behind" and remain low throught the process. These then cause the repeating pattern seen throughout. If you ensure the random number generated for each pixel is in the range -1 -> +1 before any other calculations then the pattern is eliminated.

There may be other ways to accomplish the same outcome, but I found this the easiest way (other attempts failed), I then normalise my data to the range 0->1 before rendering. Performance is not a consideration for me.

TLDR - make your random numbers go from -1 to +1

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .