Midpoint Displacement による地形生成

Midpoint Displacement による地形生成を実装していました。

Wikipedia (en): Midpoint displacement algorithm - Diamond-square algorithm

日本語では「中点変位法」と呼ぶようです。なお、Diamond-square algorithm については実装していません。

アルゴリズムについては、下記サイトの説明が分かりやすいと思います。

Generating Random Fractal Terrain: Midpoint Displacement in One Dimension
fractalterraingeneration: Midpoint Displacement

極めて簡単にアルゴリズムを説明すると、最初に height map の 4 隅に値を与え、2 点間の中点に対してそれら平均値 + 誤差 (乱数) を与えて決定し、この中点の決定を必要な所まで繰り返すというものです。

検索すると数多の公開コードがありましたが、サイト fractalterraingeneration で公開されているコードが最も綺麗に見えたので、これを元に実装しています。

なお、僕のコードでは、実行中に複数の height map を生成して並べたいため、シードを与えた後、(x, y) に対して一意に値が定まるような擬似乱数を用いています (ノイズの利用で行なっている事と同じ)。
見かけた公開コードの全ては (探せば別の物もあるでしょうが)、基点となる 4 隅の高さや中点の変位量を定める際に、C# ならば Random.NextDouble() に代表されるような擬似乱数生成器の値をそのまま利用していましたが、この方法では height map 間の境界上での高さを一致させることは困難です。

また、サイト fractalterraingeneration のコードでは、変位の際に与える誤差の重み付けが大雑把なため、サイト Generating Random Fractal Terrain の説明にあるようなパラメータ H による制御としています。なお、他のサイトでは、変位量の計算メソッドをオーバライド可にし、柔軟に実装を変更できるようにしているものもありました。

下図は、Midpoint displacement で height map を生成し、高度による色付けを行ってみた結果です。

下図は、「XNA Infinite Terrain アップ」で紹介したコードの Midpoint displacement 版を実行した結果です。

まぁ・・・ノイズ計算と重ね合わせを実行することに比べると、極めて高速です。見た目も十分に地形であり、今まで僕がノイズで作っていた地形よりも地形らしく見えるような気がしないでもありません。

ただし、多様な地形を表現できるかどうかについては、Midpoint displacement では厳しいであろうと考えています (特定の座標にある値を即座に得ることはできない仕組みであるため)。

また別の問題として、僕には今のところ解決の術が見つからないのですが、中点を選んでの変位を繰り返す処理ゆえに、綺麗に中点を選択できなくなる height map サイズを用いる場合、height map 同士の特定の位置にある高さを一致させることが難しくなります。
地形をポリゴンで描画する際、境界上にある頂点の法線を地形同士で一致させるために、僕は通常用いられる height map よりも 1 ピクセル分だけ余分に確保して法線の算出に用いていたのですが、Midpoint displacement ではこれを行うことができません。実行中の height map 生成でなければ、隣接する height map から情報を拝借して済む問題ではあるのですが。
このため、地形描画コードでは、height map 同士が隣接する境界での法線が不正となり、繋ぎ目が見える状態です。

下記にソースコードを置きました。

GitHub: TestXna (tag 20120727)

上記 Git プロジェクトのうち、下記の XNA プロジェクトが対象です (全てをダウンロードしなければコンパイルできません)。

• MidpointDisplacementDemo: デモ アプリケーションのソリューション
• DemoFramework: 基礎的なクラスを含むライブラリ
• Framework.Terrain: 地形描画の基礎となるクラスを含むライブラリ
• Framework.Terrain.CDLOD: CDLOD のためのライブラリ
• Framework.Landscape: 動的地形生成管理のためのライブラリ

また、MidpointDisplacementDemo ソリューションは、以下の 2 つのスタート アップ プロジェクトを持ちます。

• MidpointDisplacementDemo: 単に色付けしてテクスチャとして表示するデモ
• MDTerrainDemo: ポリゴンで実際に描画するデモ

なお、Midpoint displacement の実装そのものだけならば、以下のファイルとなります。

GitHub: MidpointDisplacement.cs