ITエンジニア勉強ブログ

自分が学んだことを共有していきます。

Diamond-Squareアルゴリズムの高度マップをThree.jsで描画

Diamond-Squareアルゴリズムで生成した高度マップをThree.jsで描画してみました。


See the Pen
Untitled
by Imai (@imai1)
on CodePen.


Diamond-Squareアルゴリズムの解説

高度マップ風のノイズを生成するアルゴリズムです。

en.wikipedia.org

DiamondステップとSquareステップを繰り返すイテレーション型のアルゴリズムです。1回分のイテレーション3x3の二次元配列で説明します。

  • [初期化:最初のイテレーションでのみ実行]:座標(0, 0), (2, 0), (0, 2), (2, 2)をランダムに初期化。
  • [Diamondステップ]:座標(0, 0), (2, 0), (0, 2), (2, 2)の平均値に乱数を加えた値を座標(1, 1)にセット。
  • [Squareステップ]:座標(0, 0), (2, 0), (1, 1)の平均値に乱数を加えた値を座標(1, 0)にセット。同様に、座標(0, 1), (1, 2), (2, 1)に値をセット。

3x3の二次元配列を4つの2x2の二次元配列に分けて(例えば(0, 0), (1, 0), (0, 1), (1, 1)が一つの2x2の二次元配列になります)、小さい二次元配列の各々にDiamondステップとSquareステップを再帰的に適用していきます。

乱数はイテレーション毎に×0.5倍にしていくなどで調整すると、それらしい結果になります。

実装

Diamond-Squareアルゴリズム

前述の擬似コードを真面目にプログラミングすると、やや長くなりますが下記のようになります。

/**
 * @param {number} exponent - exponent of width and height of map.
 * @param {number} amplitude - amplitude for the initialization.
 * @param {Array} - result.
 */
function runDiamondSquareAlgorithm(exponent, amplitude = 5.0) {
  const length = Math.pow(2, exponent) + 1;

  // Allocate map.
  const map = allocateMap(length, length);

  // Initialize.
  map[0][0] = randM1P1() * amplitude;
  map[0][length - 1] = randM1P1() * amplitude;
  map[length - 1][0] = randM1P1() * amplitude;
  map[length - 1][length - 1] = randM1P1() * amplitude;

  let size = length - 1;
  amplitude *= 0.5;
  while (size > 1) {
    // Run diamond step.
    for (let y = 0; y < length - 1; y += size) {
      for (let x = 0; x < length - 1; x += size) {
        const average = (
          map[y][x] +
          map[y][x + size] +
          map[y + size][x] +
          map[y + size][x + size]) / 4.0;
        const mx = x + size / 2;
        const my = y + size / 2;
        map[my][mx] = average + randM1P1() * amplitude;
      }
    }

    // Run square step.
    for (let y = 0; y < length; y += size) {
      for (let x = 0; x < length - 1; x += size) {
        const mx = x + size / 2;
        map[y][mx] = map[y][x] + map[y][x + size];
        let added = 2;
        if (y > 0) {
          map[y][mx] += map[y - size / 2][mx];
          added += 1;
        } else if (y < length - 1) {
          map[y][mx] += map[y + size / 2][mx];
          added += 1;
        }
        map[y][mx] = map[y][mx] / added + randM1P1() * amplitude;
      }
    }
    for (let x = 0; x < length; x += size) {
      for (let y = 0; y < length - 1; y += size) {
        const my = y + size / 2;
        map[my][x] = map[y][x] + map[y + size][x];
        let added = 2;
        if (x > 0) {
          map[my][x] += map[my][x - size / 2];
          added += 1;
        } else if (x < length - 1) {
          map[my][x] += map[my][x + size / 2];
          added += 1;
        }
        map[my][x] = map[my][x] / added + randM1P1() * amplitude;
      }
    }

    // Update parameters.
    size /= 2;
    amplitude *= 0.5;
  }

  return map;
}

2回目以降のSquareステップでは座標によって3つの値の平均値になったり4つの値の平均値になったりしてやや面倒です。シンプルに、常に3つの値の平均を取り、新しい値で上書きするやり方でも結果はそれほど変わらない気もします。

Three.jsによる描画

描画にはThree.jsを利用しました。

まずは、HTML側で以下のスクリプトを読み込みます。

<script src="https://unpkg.com/three@0.142.0/build/three.min.js"></script>
<script src="https://unpkg.com/three@0.142.0/examples/js/utils/BufferGeometryUtils.js"></script>

BufferGeometryUtils.jsは高速化のための追加ライブラリです。複数のMeshを描画するのを避けて、全てのMeshを一つに合体させるために使用します。CodePenのスクリプトを少しいじればロジック的にはthree.min.jsだけでも動作可能ですが速度差は結構大きいです。

高度マップの生成および全体の描画は以下のコードです。

function main() {
  const WIDTH = window.innerWidth;
  const HEIGHT = window.innerHeight;

  const renderer = new THREE.WebGLRenderer({antialias:true});
  renderer.setSize(WIDTH, HEIGHT);
  renderer.setClearColor(0xDDDDDD, 1);
  document.body.appendChild(renderer.domElement);

  const scene = new THREE.Scene();

  const camera = new THREE.OrthographicCamera(-48, +48, 27, -27, 1, 1000);
  camera.position.set(-90, -90, 60);
  //camera.rotation.set(Math.PI / 4, 0, -Math.PI / 4);
  camera.up.set(1, 1, 1);
  camera.lookAt(new THREE.Vector3(0, 0, 0));
  scene.add(camera);
  
  const light = new THREE.PointLight(0xFFFFFF);
  light.position.set(-10, 15, 50);
  scene.add(light);

  const ambientLight = new THREE.AmbientLight(0xffffff, 0.5)
  scene.add(ambientLight);

  const boxGeometries = [];
  function addBoxGeometry(x, y, z) {
    const boxGeometry = new THREE.BoxGeometry(1, 1, 1);
    const geometryTranslated = boxGeometry.translate(x, y, z);
    boxGeometries.push(geometryTranslated);
  }

  const exponent = 6;
  const amplitude = 10.0;
  const length = Math.pow(2, 5) + 1;
  const map = runDiamondSquareAlgorithm(exponent, amplitude);
  for (let y = 0; y < map.length; ++y) {
    for (let x = 0; x < map[y].length; ++x) {
      const height = Math.floor(map[y][x] + amplitude);
      for (let z = 0; z < height; ++z) {
        addBoxGeometry(x - length / 2, y - length / 2, z);
      }
    }
  }

  const combinedGeometry = THREE.BufferGeometryUtils.mergeBufferGeometries(boxGeometries);
  const lambertMaterial = new THREE.MeshLambertMaterial({color: 0xEAEFF2});
  const mesh = new THREE.Mesh(combinedGeometry, lambertMaterial);
  scene.add(mesh);

  /*
  function render() {
    requestAnimationFrame(render);
    renderer.render(scene, camera);
  }
  render();
  */
  renderer.render(scene, camera);
}

カメラ、ライト、メッシュetcを初期化して描画処理に紐づけて実行、という3DCGプログラミングのお馴染みの流れです。

高度マップを生成してメッシュを追加する処理は以下の部分です。x,y座標毎に、高度の個数だけ1x1x1のBoxを積み重ねていきます。

  const exponent = 6;
  const amplitude = 10.0;
  const length = Math.pow(2, 5) + 1;
  const map = runDiamondSquareAlgorithm(exponent, amplitude);
  for (let y = 0; y < map.length; ++y) {
    for (let x = 0; x < map[y].length; ++x) {
      const height = Math.floor(map[y][x] + amplitude);
      for (let z = 0; z < height; ++z) {
        addBoxGeometry(x - length / 2, y - length / 2, z);
      }
    }
  }