ak備忘録

レガシーブログ

空間分割のまとめ的なもの

f:id:Keiro:20140710172020p:plain

ここのところ空間分割について勉強していたので、備忘録的な意味でまとめておこうと思う。

そもそも空間分割をなぜやるのか?というところだが処理の高速化のためにやる。

自分の近くにあるものに高速にアクセスする手段を、
自分から遠くにあるものに可能な限りアクセスしない手段を手に入れることで
判定処理などの回数を減らす。

種類は豊富にあるが、いくつか取り上げてみる。
ちなみに僕が作ったことがあるのは8分木のみ。

●BSPツリー
この辺が分かりやすい。
http://blogai.igda.jp/article/29853941.html

ゲームではDOOMで使われていた空間分割技術。
「見えない敵は描画しない!」といった極一般的な高速化を実現できる。

理論的には空間を左右に分割することを繰り返すだけだが、
難しいのはどのように分割するか、というアルゴリズムである。

一般的にツリーを構築するのに時間がかかる。
また、分割平面情報を保持しなければいけない。

●kdツリー
おそらくWikiが一番分かりやすい。
http://ja.wikipedia.org/wiki/Kd%E6%9C%A8

BSPツリーでもあるが、kdツリーは任意の平面で区切るのではなく
XYZ軸に平行に区切るのが特徴。

軸に平行なので平面情報などがいらないのと、
入っているかどうか判定が比較的簡単になる。

kdツリーは最近点を求めるのに向いていると思う。
だが、最悪のパターンになると計算量が線形とあまり変わらない場合もある。

●LSH
ハッシュ値を求め、近似で最近点を求める。
重要なのは最近点が確実に求まるわけではなく、近似だということ。
確率論なのだ。

詳しくはここが分かりやすい。
http://kusamochi.blog.shinobi.jp/%E7%A0%94%E7%A9%B6%E3%81%AE%E9%80%B2%E6%8D%97/lsh%E3%81%BE%E3%81%A8%E3%82%81-1-

ちなみにLSHに使用するハッシュ関数は色々とあるので、
それを選定するのも難しい。

●4分木、8分木
問答無用でここが一番分かりやすい。
http://marupeke296.com/COL_2D_No8_QuadTree.html
http://marupeke296.com/COL_3D_No15_Octree.html

最適化するとかなり高速にアクセスすることが可能。
当たり判定などの物理シミュレーションとの相性が抜群だと感じる。

ただし、最近点を求める系で言えば若干劣る。
というのも最近点を求める場合は分割した1つのボックス内だけの話では
完結しないことが多くあるため、どうしても検索範囲が広くなる。

あとメモリの問題も大きい。
ボックスを小さくすればそれだけ高速になるが、管理用メモリが爆発的に増える。

そこで僕が考えたのが、他のアルゴリズムとの併用である。

たとえば、空間を木綿豆腐のように縦横に適当に切り、
その適当に切ったおおざっぱな空間で8分木を構築する。

そのとき密度に応じて分割レベルを可変にすれば、
空間の最適化とメモリの効率化の両方が実現できてよいと思う。

ただし、この方法は最近点を求める系とは非常に相性が悪いので注意。
というか、そのボックス内だけでは完結しない問題系には弱い。

弱いというと若干言いすぎだが、最高のパフォーマンスは引き出せない。

ゲームプログラミングのためのリアルタイム衝突判定

ゲームプログラミングのためのリアルタイム衝突判定