lucille 開発日記: スフィアツリー

スフィアツリー 物理シミュレーションの衝突判定には、よくバウンディングボックスやバウンディング球が使われます。 レンダリングではレイとの交差判定のときに使うことがあるでしょう。 多分 lucille ではここらへんのアルゴリズムは使う事はないでしょうが、その昔階層バウンディング球、スフィアツリー(Sphere tree)と呼ばれる、について調べたことがあったので、思い出して書き留めておくことにします。 バウンディング球 バウンディング球は、その判定の演算がもっとも単純なので、よく用いられているとおもいます。 オブジェクトのバウンディング球を作成するのは、効率や最適な解を考えなければそれほど難しくありません。 しかし、実際の利用では、点群(コンピュータグラフィックスの場合ではポリゴンの頂点のリストがこれに当たる)に対して、なるべくタイトフィット(tight fit)、つまり最適で隙間が最小に