6
私は、単純な細長い3dメッシュを含む3d空間に何千ものOOBB（オブジェクト指向バウンディングボックス）を持っています。彼らはしっかりと一緒に詰め込まれています。緊密なOOBBグループに対してレイ交差を迅速にテストするにはどうすればよいですか？
私はそれらに光線を吹き込み、どのOOBBがヒットするのか把握したいと思います。私が実行する必要のあるレイ交差テストの数（数百万）のために、すべてのOOBBに対するブルートフォースアプローチでは十分ではありません。
元来、ある種の空間分割システムを使用して潜在的な結果を素早く絞り込むことは簡単だと思っていましたが、BVHsやKDTreesのようなシステムはAABB（軸合わせバウンディングボックス） （私のしっかりと詰め込まれたOOBBの多くが、それらが網羅するメッシュの対角線の性質のため、おおよそ同じAABBを有するので、非常に非効率的である）。
RAPIDライブラリのOBBTreesについては読んでいますが、上から下に向かって構築されているようです（ポリゴンスープで始まり、徐々に小さなOOBBグループに細分されています）。たくさんのOOBBがあり、そこから木をつくる）。
交差テストの高速化に使用できる他のデータ構造はありますか？
ここに私のOOBBの写真があります。あなたが見ることができるように、彼らはしっかりと詰め込まれていて、AABBの外観を想像することができれば、AABBベースのツリーが実際にパフォーマンスを向上させない点に重なることが分かります（なぜなら、グループの中心を通る射撃によって打撃を受けるだろう）。
最初の/最も近いものだけでなく、レイでヒットしたすべてのOOBBを照会する必要があることは注目に値します。
ほとんどのbbsがaabbsに近く、その新しい空間で何らかの種類の空間分割アルゴリズムを使用するいくつかの領域に光線を回転させてみてください。線形変換を除いてオブジェクトがレイからレイトに変化しない場合に適用される別のソリューション：各セルが三角形/楕円形の交点のリストを持つ3D配列を生成し、その3Dアレイ。 – programmerjake
シーンはどのようにダイナミックですか？つまり、OOBBが変更されるまでどのくらい光線を投射し、どれほど大幅に変化するでしょうか？ – Angew
@programmerjake残念ながら、最初の提案は機能しません。OOBBが私のサンプルイメージのようにうまく整列されないからです。 2番目のオプションはもっと近くにあるかもしれませんが、メモリのフットプリントと前処理の必要性は問題になる可能性があります...私は3Dアレイが実現できない非常に大きな3D環境で作業するためのソリューションが必要です（合理的な粒度を維持しながらすべてを含めるには何十億ものセルが必要です）。しかし、提案に感謝します。 – Tyson