私は最近、バイナリ スペース パーティショニング ツリーと、その 3D グラフィックスおよび衝突検出への応用について学びました。また、四分木と八分木に関連する資料を簡単に調べました。bsp ツリーではなくクワッドツリーを使用するのはいつですか、またはその逆ですか? それらは交換可能ですか？次のような表に記入するのに十分な情報があれば満足です。
| BSP | Quadtree | Octree
------------+----------------+-------
Situation A | X | |
Situation B | | X |
Situation C | | | X
A、B、Cとは？
あなたの質問に対する明確な答えはありません。それは、データの編成方法に完全に依存します。
心に留めておくべきこと：
四分木は、ナビゲーション システムのマップ レンダリングのように、ほとんどが 2 次元のデータに最適です。この場合、ジオメトリによりよく適応し、ノード構造を小さく保つため、octree よりも高速です。
データが 3 次元の場合、オクトリーと BVH (バウンディング ボリューム階層) が役立ちます。また、ジオメトリ エンティティが 3D 空間でクラスタ化されている場合にも非常にうまく機能します。( Octree と BVHを参照) (からアーカイブオリジナル)
Oc および Quadtree の利点は、必要に応じていつでもツリーの生成を停止できることです。グラフィック アクセラレータを使用してグラフィックをレンダリングする場合は、オブジェクト レベルでツリーを生成し、各オブジェクトを 1 回の描画呼び出しでグラフィック API に送信するだけです。これは、個々の三角形を送信するよりもはるかに優れたパフォーマンスを発揮します (BSP ツリーを最大限に使用する場合は、これを行う必要があります)。
BSP ツリーは本当に特殊なケースです。それらは 2D および 3D で非常にうまく機能しますが、優れた BSP ツリーを生成することはそれ自体がアート フォームです。BSP ツリーには、ジオメトリを小さな断片に分割しなければならない場合があるという欠点があります。これにより、データセットの全体的なポリゴン数が増加する可能性があります。レンダリングには適していますが、衝突検出とレイ トレーシングにははるかに適しています。
BSP ツリーの優れた特性は、ポリゴン スープを、実際の並べ替えを行わなくても、任意のカメラ位置から完全に前後 (およびその逆) にレンダリングできる構造に分解することです。各視点からの順序はデータ構造の一部であり、BSP ツリーのコンパイル中に行われます。
ちなみに、それが10年前に人気だった理由です。Quake がこれらを使用したのは、グラフィック エンジン/ソフトウェア ラスタライザーがコストのかかる Z バッファーを使用しないようにするためです。
言及されているすべての木は、単なる木の家族です。ルーズ オクトリー、kd ツリー ハイブリッド ツリー、およびその他の関連する構造も多数あります。
BSP は都市環境に最適です。
Quadtree は、地形などに高さマップを使用する場合に最適です。
Octree は、太陽系などの 3D 空間にジオメトリの塊がある場合に最適です。
BSP は、使用するフレーバーに応じて、衝突検出を高速化するための適切なオプションです。それらは、点と線または光線のテストで特に高速ですが、ボリュームのあるものでは速度がやや遅くなり、少し複雑になります。
グラフィックでの使用に関しては、BSP はほとんど時代遅れです。オクトリーは、AABB ツリーと同様に、グロス ビジビリティ カリングなどに適しています。
私は BSP の経験はあまりありませんが、レンダリングするシーンが背の高い場合は、四分木ではなく八分木を使用する必要があると言えます。つまり、高さは幅と奥行きの半分以上です。大まかな目安です。一般に、八分木は四分木に比べて大きなコストをもたらすことはなく、かなり高速化する可能性があります。YMMV。
通常、これらのことには明確な答えがありません。A、B、および C は、スペースのサイズと区別するものの量の関数の結果であることをお勧めします。
BSP は、オクルージョンのみを行いたい、より小さくシンプルなスペースに適しています。特定の光線のすべての交差が必要な場合は、quad/octree にアップグレードする必要があります。
四分木と八分木については、いくつの次元を重視しますか? 2 次元は 4 分木、4 つは 8 分木を意味します。前述のように、四分木は 3 空間で機能しますが、各次元を適切に処理したい場合は、八分木が最適です。