Hydraulic erosion について色々と調べていました・・・と言うか、幾つかの実装を終えました。その内の 1 つが、F.Kenton Musgrave、Craig E. Kolb、Robert S. Mace による『The Synthesis and Rendering of Eroded Fractal Terrains』で述べられているアルゴリズムによるものです。
で、そのうち調べたことを忘れ、その時に再度英語で論文を読み返すのも疲れると考え、備忘のために自分の解釈でまとめてみることにしました。なお、図解はしませんし、専門家ではないので言い回しの問題はご容赦ください。また、原文の訳を載せているわけではないので注意してください。
Musgrave らの論文の PDF は以下から得られますが・・・これは大丈夫なんでしょうか？
ebookbrowse.com: The Synthesis and Rendering of Eroded Fractal Terrains pdf
日本語で hydraulic erosion を何と言えば良いのか分かりませんが、大雑把には、
- 雨が降り、
- 雨により土が削られて土砂が生まれ、
- 土砂が水に混じり、
- 水の流れと共に土砂が移動し、
- 時に土砂が堆積する、
という現象のシミュレートと言えば良いでしょうか。
なお、水の流れと言っても、河川のような複雑な水の流れを考えるのではありません。
アルゴリズム
※原文は時間 $t$ から $t + 1$ への変化で説明していますが、なんだか式が見づらくなるので表記を省き、数式をプログラミング言語としての式へ変えています。
Height map 上のセルについて、$a$ (altitude: 地形の高さ)、$w$ (water: 雨による水の量)、$s$ (sediment: 水に混じっている土砂の量) を考えます。
このアルゴリズムの上では、雨による $w$ の定め方については触れません。シンプルな雨の実装としては、各ループの最初に一律で $w$ へ値を加える方法がありますし、少しランダムな状態としたければノイズ関数で値を加えるなどの方法もあります。いずれにせよ、何らかの形で $w$ を与える必要はあります。
なお、シミュレーションの最初のループでは $s = 0$ であり、処理の過程において水が土を削ることで土砂が生まれる点に注意が必要です (最初から土砂があると考えてアルゴリズムを見ると混乱します)。
また、実装では height map 上の全セルについて水の移動を処理する必要がありますが、ここではセル $v$ について、隣接するセル $u$ への移動を説明している点に注意が必要です。
セル $v$ から $u$ へ流れ出る水の量 $\Delta w$ は次式となります。
\[
\Delta w = min(w_{v}, (w_{v} + a_{v}) - (w_{u} + a_{u}))
\]
まず、$\Delta w \leq 0$ は、「$v$ には水がない」あるいは「$v$ から $u$ へは水は流れ出ることができない」ことを表しているため、水の移動を考えず、土砂の堆積のみを考えます。
ここで、堆積の割合を定数 $K_{d}$ (deposition constant) で定義し、堆積する量を $K_{d} s_{v}$ として堆積を処理します。
\begin{eqnarray}
a_{v} &=& a_{v} + K_{d} s_{v} \\
s_{v} &=& s_{v} - K_{d} s_{v} = (1 - K_{d}) s_{v}
\end{eqnarray}
一方、$0 < \Delta w$ では水が移動できるため、土砂の移動についても考えます。まず、水の移動は単純に次式で表せます。
\begin{eqnarray}
w_{v} &=& w_{v} - \Delta w \\
w_{u} &=& w_{u} + \Delta w
\end{eqnarray}
次に、水と共に移動する土砂の量ですが、水が全ての土砂を運べるとは限らず、その能力には限界があります。そこで、水が運べる土砂の割合を定数 $K_{c}$ (sediment capacity constant) で定義し、$\Delta w$ について共に移動する土砂の量 $c$ (sediment capacity) を次式で定めます。
\[
c = K_{c} \Delta w
\]
ここで、$c$ と $s_{v}$ の比較で処理が分岐します。
まず、$s_{v} \geq c$ では $c$ 分を移動させるだけの $s_{v}$ があるため、そのまま移動させます。そして、移動後の残りの分 $s_{v} - c$ について堆積を考えます。
\begin{eqnarray}
s_{u} &=& s_{u} + c \\
a_{v} &=& a_{v} + K_{d} (s_{v} - c) \\
s_{v} &=& s_{v} - c - K_{d}(s_{v} - c) = (1 - K_{d})(s_{v} - c)
\end{eqnarray}
一方、$s_{v} < c$ では、$c$ 分の移動には $s_{v}$ が不足していますが、この状態は、「更に土が水に混じる余地のある状態」と考えることができるため、土を削って土砂を生み出すこととします。
なお、シミュレーションの最初の段階では $s = 0$ であり、必ずこの処理に入ります。そして、この処理で土砂が生まれ、$s$ が増加するということになります。
ここで、土砂として水に混じることのできる量に対して、実際に土砂として削る割合を定数 $K_{s}$ (soil softness constant) で定義し、$K_{s} (c - s_{v})$ だけ地形を削り新たな土砂とし、次式で水と土砂の移動と堆積を考えます。
\begin{eqnarray}
s_{u} &=& s_{u} + s_{v} + K_{s} (c - s_{v}) \\
a_{v} &=& a_{v} - K_{s} (c - s_{v}) \\
s_{v} &=& 0
\end{eqnarray}
・・・と、以上のようなアルゴリズムを考えるそうです。そして、ここまでの処理を $n$ 回繰り返してシミュレーションとします。
