フレームごとにオクトリーを再構築する必要がありますか？

Question

ゲームで衝突検出にoctreeを使用する場合は、フレームごとにツリーを再構築するか、オブジェクトの半分がフレーム内を移動すると仮定した方が良いでしょうか？

Answer 1

フレームごとにシーンが変化する場合は、ツリーをやり直す必要があります。

Answer 2

シーンに静的ジオメトリがたくさんある場合は、別々のオクトツリーを作成することを検討してください。静的と非静的なジオメトリを区別するより複雑なリーフノードを持つことで、同じアイデアを表現することもできます。

ボトムライン：必要なものを再生します。

Answer 3

非常に動的なデータが1フレームごとに移動し、衝突検出を高速化する必要がある場合は、実際に固定3Dグリッドを使用することをお勧めします。 2次元の等価物は：

またようなので（同じグリッドセル内の次の要素へのインデックスのいずれかとしてnextインデックスを利用して、一定時間の削除を可能にするフリーリストとして上倍増できますそれが削除された場合には無料のスタックからオフにポップするか、次の空き要素）：

もう一つの例：

3次元では、爆発的なメモリが必要になるようです。しかし、このトリックは、各セルに32ビットのインデックスを配列に格納させるだけで、基本的には単一リンクインデックスリストとして機能します。これにより、各セルのサイズが32ビットに縮小されます。 100x100x100のグリッド（100万個のセル）を保存すると、4メガバイト未満になります。

要素が移動するときに、要素を占有しているセルから削除し、移動して新しいセルに挿入することができます。これを行うために必要なのは、ある種のセルから他のセルへ要素を転送するためのメモリ割り当て/割り当て解除なしの32ビットインデックスを操作することだけです。これはすべて一定の時間であり、あまりにも混雑したり、そのようなものになる木々の再平衡や分割を必要としません。

グリッドの階層を使用することもできます（これはオクトリーのように聞こえるかもしれませんが、異なる場合があります）。つまり、シーン内のメッシュオブジェクト全体に対して1つの粗いグリッドがあるかもしれません。次に、各メッシュオブジェクトは、その各部分に対して粗いグリッド、例えば、10x10x10を格納することができる。次に、各パーツはポリゴンごとに細かいグリッドまたはオクトリーを格納します。これは、例えばロボットのように回転している部品で剛体でない非メッシュを可能にし、ポリゴンの細かいグリッド/オクトリーを更新することを避け、それ自身の粗いグリッドのグリッドとワールドオブジェクトの粗いグリッドを更新するそれはその脚と腕を回転させ始める。オーガニックモデルのみが骨によって変形されると、細かいグリッドを更新する必要があります。

私はあなたの完全に静的な要素/フレームごとに更新する必要はありませんパーツと私は良い親和性のあるoctreeを使用したいと思います。おそらくキャッシュに優しいメモリアクセスのために後処理をします。一度構築されると、オクトリーが更新される必要がないと考えることができる場合、それらの検索を高速化し、メモリー使用を最小限に抑えるために、もう少し時間があります。