ボロノイ分割による地形生成

複数の height map を並べる処理をしている間、ボロノイ分割による地形生成も実装していました。

Wikipedia: ボロノイ図

ソースコードは、前回の XNA Infinite Terrain のコードと同じですが、修正を加えた状態が以下となります。

GitHub: TestXna / TiledTerrainDemo (tag 20120722)
(TiledTerrainDemo.Noise.Voronoi クラス周辺)

実行例は、以下のようになります。

距離メソッド = Squred, 選択方法 = Distance0, Frequency = 1

ロジック

簡単に説明すると次のようになります (実際には 3 次元で値を生成しますが 2 次元で考えます)。

まず、float 値の (x, y) について周辺のセル (int) を特定し、それらセルに含まれる母点を乱数で定めます (乱数といっても同じセルなら必ず同じ母点)。
続いて、周辺の各セルについて (x, y) から母点までの距離を測定し、最も近い母点を選択します。
最後に、選択された最も近い母点について乱数を生成し、これを (x, y) の高さの値とします。
結果として、ある母点に近いところにある (x, y) の高さが母点の高さと同一となります。

なお、Wikipedia では分割された領域に色を設定している説明ですが、ここでは地形生成に用いるため、乱数で生成した高さを設定しています。

参考にしたソース コードは以下の通りです。

libnoise: http://libnoise.sourceforge.net/
(module にある voronoi.h/voronoi.cpp)
Blender: http://www.blender.org/
(blenlib にある BLI_noise.h/noise.c)

各種パラメータによる変化を 2D テクスチャで見たい場合には、以下のサイトが分かりやすいです (ソースコードも公開していますが、Blender とほぼ同一です)。

The Nugget Mines: Voronoi Noise

距離メソッド

僕のコードの基本形は libnoise に類似していますが、libnoise の Voronoi クラスでは、Blender にあるような距離の測定方法の変更が行えません (ユークリッド距離^2 で固定)。僕のコードでは Blender にならい、複数の距離メソッドを用意し、delegate で変更できるようにしています。
実装してある距離メソッドは以下の通りです。

• Squared: ユークリッド距離^2 (XNA での Vector3.DistanceSquared() に相当)
• Real: ユークリッド距離 (XNA での Vector3.Distance() に相当)
• Manhattan: マンハッタン距離
• Chebychev: チェビシェフ距離
• Minkowski: ミンコフスキー距離

各距離の意味は、以下がまとめられていて分かりやすいと思います。

CatTail Wiki: 類似度と距離

なお、上記は統計解析で用いられる SAS というアプリケーションのための Wiki です (関係する人で知らない人はいないのでは？)。実用経験はないですが、僕も訳があり多少かじっていたりします。

以下、距離メソッドを変更した場合での地形の雰囲気を画像で並べます。後述する母点選択方法は Distance0、Frequency は 1 で固定。また、Real は除外。

Squred

Manhattan

Chebychev

Minkowski (p = 0.5)

Minkowski (p = 4)

以上、違いを認識しづらい画像になってしまいましたが、Squared を基本に比較すると、Manhattan や Chebychev はより矩形に近い分割に見える気がします。Minkowski だと領域がより複雑な形状となるのでしょうか。

母点選択方法

libnoise の Voronoi クラスでは、Blender にあるような母点の選択方法の変更が行えません (常に最も近い母点を選択する)。僕のコードでは Blender にならい、母点の選択方法を変更できるようにしています。Blender では距離の選択方法と呼ぶのが正しいですが、僕のコードでは母点の選択方法です。

実装してある母点選択方法は以下の通りです。

• Distance0: 最も近い母点を選択
• Distance1: 2 番目に近い母点を選択
• Distance2: 3 番目に近い母点を選択
• Distance3: 4 番目に近い母点を選択
• Difference21: Distance1 と Distance2 が示す各母点の中間点を母点に選択
• Difference32: Distance2 と Distance3 が示す各母点の中間点を母点に選択
• Crackle: よく分からずに実装

Difference21 と Difference32 については、Blender では距離の算出のみで、そこから高さを乱数で算出するようなことをしていないため、自分で勝手に中間点を選択するようにアレンジしました。

以下、母点選択方法を変更した場合での地形の雰囲気を画像で並べます。距離メソッドは Squared、後述する Frequency は 1 で固定。



Distance0

Distance1

Distance2

Disntance3

Difference21

Difference32

Crackle

より遠い母点を選ぶことで、より粗い分割が行われるように見えます。Difference21、Difference32 については、勝手なアレンジをしたので何とも言えません。Crackle は理解していないので更に何とも言えません。

Frequency による調整

Voronoi クラスの Frequency プロパティは、Voronoi 分割を行うまえに、指定した (x, y, z) に対して乗算されます。上手く表現する方法が分からないのですが、名前の通り、生成する値の幅を調整する役目を果たします・・・と言えば良いのでしょうか・・・。

以下、Frequency を変更した場合での地形の雰囲気を画像で並べます。距離メソッドは Squared、母点選択方法は Distance0 で固定。

Frequency = 1

Frequency = 4

Frequency 値を大きくすると、より狭い範囲で分割を行うことになります。

距離を高さに足す

Voronoi クラスの DistanceEnabled プロパティを true にすると、算出した高さに対し、その算出の元となった距離を足します。
つまり、母点に近い位置では算出した高さのままであり、母点から遠のく程に (領域の境界へ近づく程に) 高さが上がる状態となります。

以下、DistanceEnabled を変更した場合での地形の雰囲気を画像で並べます。距離メソッドは Squred、母点選択方法は Distance0、Frequency は 1 で固定。

DistanceEnabled = false

DistanceEnabled = true

距離を高さに足すことで、クレータのような部分が作られます。