j3259の日記： 地形 (terrain) のレンダリング

地形のデータの読み込みはただの標高データなんで、誰でもできる。何が面白いかっていうと、百万とかそれ以上の高さのデータからリアルタイムで地形をレンダリングするのにアルゴリズムを使わなきゃいけない。

とりあえず、
- Virtual Terrain Project
- ROAM
- SOAR
- terra
- scape

その前に、地形(terrain) とは何ぞや。地形データは大きく分けて二つ。
- 標高、地勢
- 属性: 建物、植物、道、色その他

地形データのネタ
- 自動生成されたもの
- 物理ベースのもの （GIS, 標高データなど）

地形エンジン(terrain engine)の役割
- データ構造の管理
- リアルタイムでの描画
- 問題の解決
-- データ構造
-- リアルタイム描画での LOD（Level of detail; 詳細の段階、遠くのものや、平坦なものを適当に描画しちゃうこと）
-- 効率的で正確なデータ問い合わせと LOD の両立
-- メモリ管理

完全な地形データはデータ構造がデカくなるので、適当に近似した情報で代用する。
viewer dependent（VD; 視点依存）のアプローチと viewer independent（VI; 視点独立）のアプローチがある。
描画に関してはそれっぽく見えてれば一応問題は起きないけど、物理シミュレーションでボールが山を転がってるとかいう事になるとある程度正確さが求められる。あと、描画の場合は基本的にはカメラの後ろはどうでもいい。物理はカメラ関係なし。

標高図 (Elevation Map; EM)
標高値は
- 規則的(regular)な長方形のグリッド
- 規則的(regular)/不規則的(irregular)に三角化されたメッシュ
にサンプルする事ができる

長方形標高図 (Rectangular elevation map; REM)
標高値は規則的(regular)な長方形のグリッドにサンプルされる。
保存されるのは、グリッドの間隔、縦横のサイズ、ならびに標高値(EV)
隣接の値同士が近いことを利用して基点と差分だけ保存する方法もある

三角化標高図 (Triangulated elevation map; TEM)
メッシュ化されている。三角化(triangulate)する必要がある。
三角化っていうのは多角形のポリゴンを三角形に分割すること。
- 規則的(regular) 三角化メッシュ
-- 例、ROAM、quadtree（四分木)、triangle bintree（三角形二分木）。binary tree search（二分木検索）を応用できる。
- 不規則的(irregular) 三角化メッシュ
-- 例、Triangulated Irregular Networks (TIN; 三角化不規則ネットワーク)。GIS でよく使われる。

アルゴリズム
- Garland and Heckbert "Fast Polygonal Approximation of Terrains and Height Fields", 1995
-- 通常視点非依存、TIN ベース。動的LOD は複数の TINをキャッシュすることで実現可能だが高価。
- Duchaineau ROAM, 1997
- Lindstrom et al "Real-Time, Continuous Level of Detail Rendering of Height Fields", 1996
-- 視点依存、LOD あり、規則的な三角形二分木ベース
- Hoppe "Smooth View-Dependent Level-of-Detail Control and Its Application to Terrain Rendering", 1998
-- 視点依存、スムーズな LOD、progressive（漸進的な）メッシュ

方針
- 標高図/地形メッシュを適当な "fit"（ぴったり感）を満たす簡略化されたメッシュで近似する
- Hierarchical （階層化された）データ構造を使い、状況によって適当なレベルを描画する
-- 視点非依存
-- 視点依存
- progressive（漸進的）メッシュを使う。プログレッシブ jpeg のように最初は荒いメッシュで、段階的に細かいメッシュになっていくこと。

視点非依存的近似メッシュ
- Garland and Heckbert "Fast Polygonal Approximation of Terrains and Height Fields", 1995
-- 通常視点非依存、TIN ベース。動的LOD は複数の TINをキャッシュすることで実現可能だが高価。
- Greedy アルゴリズム。Greedy っていうのはがつがつしてて欲張りなこと。後のことは考えずに一番おいしそうなものからがつがつ食べていく方法論。これでうまくいく問題もあれば、うまくいかない問題もあります。素直に理詰めで計算すると面倒な問題でもこれでそれらしい解がでるので便利。問題を複数のステップに分割して、ステップごとの部分解を合わせると問題の解になると望む。うまくいかない例は、迷路で出口に近い方向へ欲張り法で進んでいくとして、行き止まりに当たった場合。参考: 焼きなまし法。
- 低解像度の近似メッシュに標高図から重要な点を足していく
- 重要度の尺度
- 三角化
-- 二次元の範囲では Delaunay 三角化
-- 三次元ではデータを利用

レベル 0 のメッシュ M₀ は四隅を頂点にした四角形とする。
レベル k のメッシュ M_k から M_k+1 を作る。
M_k のを標高値 (x, y, z(x, y)) の集合として、三角化されたメッシュは τ(M_k) とする。
(x, y) におけるメッシュ上の点を τ(M_k)(x, y) とする。
重要度 I(x, y) は |τ(M_k)(x, y) - z(x, y)| とすることが出来る。
この重要度は曲率の低いおおざっぱな地形をサンプルすることができるが、細かい上下は得意ではない。

三角化の方法
他の頂点を中に含まない三角形のみを有効とする
- 方法1 Delaunay 三角化（ドロネー三角形分割と訳すらしい）
- 方法2 3D のデータ駆動の方法

Delaunay法は実際は三次元の地形をみなすため、一方方向に曲率が高く、他方向に曲率が低い地形ではうまくいかない。
ハーフパイプなんかがいい例。