独立して動く小さなオブジェクトの大集団をリアルタイムでレンダリングできるようにしたいのですが、群れのように動く可能性がありますが、それらの相対的な位置は一貫していません-それらの位置は群れの中で任意に変化する可能性があり、群れはいつでも崩壊して再形成する可能性があります。
バウンディングボリューム階層を構築するためのどのアプローチがこの状況に最も適していますか？各フレームの部分的な更新のみが必要な、最適ではないが十分に優れた階層を維持する方法ですか？それとも、スムーズなアニメーションに十分な速度で各フレームの階層を最初から構築する方法はありますか？
オブジェクトの数が多すぎて階層なしでレンダリングできませんが、同じ理由で、階層の構築には時間がかかると思います。
John Calsbeekからのコメントに従って、バウンディングボリューム階層に焦点を合わせるのは誤った方向に進んでおり、この状況にはより良いスペース分割アプローチがあります。それに応じて答えてください。思いもよらなかったことも含めて、自分の説明に対応できるものを探しています。
コメント
- 意図的に制限していますかバウンディングボリューム階層への質問、または他の形式の空間分割を受け入れていますか？
- @JohnCalsbeek I '明確にするために編集しました-指摘してくれてありがとう不注意による制限。
- 群れが合流する場合は、"群れ"を単一のユニットとして扱うことを検討してください。それらを1つの群れにマージし、孤独な人が遠くまでさまようとき、それは1つの"群れ"になります。これは、群れがまとまりがあり、孤独がまれである傾向がある場合に最適に機能します。 "群れは単一のユニット"で遊ぶには、多くの巧妙な方法があります。たとえば、メンバーが群れを切り替えられるのは、互いに接触していると、リストはどんどん増えていきます。
回答
特に空間ハッシュの使用を検討してください。オブジェクトのサイズが同じである場合。
基本的に、世界を均一なサイズのグリッドセルに分割します（垂直方向の動きの量に応じて、2Dと3Dの両方が有効な可能性です）。更新のたびに、オブジェクトをオーバーラップする各ビンに割り当てます。セルがオブジェクトに対して適切なサイズである場合、ほとんどのオブジェクトは1つのビンになります。
各ビンはハッシュテーブルに挿入されます。キーはビンの座標です。 （同じキーに複数の値があり、重複するセルごとに1回オブジェクトを挿入するハッシュテーブルと考えることもできます。）
このスキームでは、再構築する階層はありません。これにより、動的なシーンに最適です。錐台または粗いレベルのオクルーダーに対してセルの寸法をテストし、一度に多くのオブジェクトを破棄することができます。また、この構造を段階的に管理する方が簡単です。フレーム間でハッシュテーブルを同じに保ち、オブジェクトがセルの境界を越えたときにのみ、オブジェクトをあるビンから別のビンに移動できます。
回答
オブジェクトが移動のたびに境界を越えないように、バウンディングボリュームを必要以上に大きくすることもできますが、とにかく、時々構造を再構築する必要があります。
または、これに正確に対処しようとする境界間隔階層があります。
または、Ingo Wald、Solomon Boulos、PeterShirleyによる動的バウンディングボリューム階層を使用したレイトレーシング変形可能シーンというタイトルの論文は興味があります。
回答
これに実用的な視点を追加したいと思います。
私はここで限られた情報を操作していることを前置きします：
- どのようにmかわかりません扱っているオブジェクト。
- 加速構造が正確に何に使用されているのかわかりません。錐台カリング？レイトレーシング？ BVH内のオブジェクト間の衝突検出？
今後は、数千のオブジェクトをカリングするフラスタムについて話していると仮定します。
オブジェクトの数が多すぎて階層なしでレンダリングできませんが、同じ理由で、階層の構築には時間がかかると思います。
BVHを計算するためにフレームごとにすべてのオブジェクトにアクセスする必要がある場合は、BVHなしで直接カリングする方が実際には高速であると主張します。もちろん、これは錐台カリングの実装によって異なります。すべてのオブジェクトのバウンディングボリュームは、メモリに連続して保存する必要があります。これにより、CPUキャッシュの使用率が向上し、SIMD命令を使用してさらに最適化できます。 DICEには、このテーマに関する全体的なプレゼンテーションがあります：戦場のカリング：データ指向の設計の実践
プレゼンテーションでは、単純なグリッドを使用して、カリングをさらに高速化することについても言及しています。
ほとんどの3D /シミュレーション/ゲームコードベースには、すでに何らかの種類があると想定しているためです。 BVHクラスと私は、最高のカリングパフォーマンスを得ることがどれほど重要かわかりません。BVHに固執するためのいくつかの議論を提示したいと思います。
使用するメソッドに応じて、構築するBVHは高速でシンプルです。
現在のバイナリBVHの実装（各ノードは0個または2個の子のみを持つことができ、各リーフノードは1つのアイテムのみを格納します）は、迅速な i7-5960X @ 3.89GHz のシングルスレッドで、1137個のオブジェクトの構築に約0.18msかかります。 「もっと速くできると確信しています。構築はプロセスでメモリを再割り当てせずに実行されます（これにより構築パフォーマンスが2倍になります）。
SAHは最高のBVHを生成する可能性がありますが、時間がかかります。SAHは優れています。衝突メッシュなど、事前に計算できるものについては、実行時に、リアルタイム構築により適したBVHに衝突メッシュを配置できます。
高速でシンプルなBVH構築アプローチ（I 「musingcurrently）は、軸（たとえば、親AABBの最長軸）上のすべてのオブジェクトを並べ替え、コレクションを中央で分割することです。
さらに高速化するには、ノードAABBを計算します。ツリーを構築した後、親ノードの2つの子ノードAABBを組み合わせます。これにより、すべてのオブジェクトの反復が回避されます（さらに2倍のスピードアップ）。ただし、これは、分割基準が親のAABBに依存しない場合にのみ可能です。