バイナリ空間分割、四分木、八分木をいつ使用するか?
https://stackoverflow.com/questions/99796
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
私は最近、バイナリ空間分割ツリーと、3D グラフィックスおよび衝突検出へのその応用について学びました。また、4 分木と 8 分木に関する資料も簡単に読んでみました。BSP ツリーではなくクオッドツリーを使用する場合、またはその逆を使用するのはどのような場合ですか?交換可能ですか?次のような表に記入するのに十分な情報があれば満足です。
| BSP | Quadtree | Octree
------------+----------------+-------
Situation A | X | |
Situation B | | X |
Situation C | | | X
A、B、Cとは何ですか?
解決
あなたの質問に対する明確な答えはありません。それはデータがどのように編成されているかに完全に依存します。
注意すべき点:
クアッドツリーは、ナビゲーション システムのマップ レンダリングのように、ほとんどが 2 次元のデータに最適です。この場合、ジオメトリへの適応性が高く、ノード構造を小さく保つことができるため、オクツリーよりも高速です。
データが 3 次元の場合、オクツリーと BVH (境界ボリューム階層) が役立ちます。また、幾何学的エンティティが 3D 空間にクラスタリングされている場合にも非常にうまく機能します。（見る オクツリー vs BVH)
Oct ツリーと Quadtree の利点は、いつでも必要に応じてツリーの生成を停止できることです。グラフィック アクセラレータを使用してグラフィックをレンダリングする場合、オブジェクト レベルでツリーを生成し、各オブジェクトを 1 回の描画呼び出しでグラフィック API に送信できます。これにより実行されます 多くの 個々の三角形を送信するよりも優れています (BSP ツリーを最大限に使用する場合はこれを行う必要があります)。
BSP ツリーは実際には特殊なケースです。これらは 2D と 3D で非常にうまく機能しますが、優れた BSP ツリーを生成すること自体が芸術形式です。BSP ツリーには、ジオメトリをより小さな部分に分割しなければならない可能性があるという欠点があります。これにより、データセット全体のポリゴン数が増加する可能性があります。これらはレンダリングには適していますが、衝突検出やレイ トレーシングにははるかに優れています。
BSP ツリーの優れた特性は、実際の並べ替えを行わずに、どのカメラ位置からでも後ろから前へ (またはその逆に) 完全にレンダリングできる構造にポリゴン スープを分解することです。各視点からの順序はデータ構造の一部であり、BSP ツリーのコンパイル中に行われます。
ちなみに、それが10年前に人気があった理由です。Quake がこれらを使用したのは、グラフィック エンジン/ソフトウェア ラスタライザーが高価な Z バッファを使用しなくても済むためです。
ここで挙げた木はすべて、木の仲間にすぎません。緩いオクツリー、kd ツリー、ハイブリッド ツリー、その他多くの関連構造もあります。
他のヒント
BSP ツリーと他の種類の 3D ツリーの実質的な最大の違いは、BSP ツリーはより最適化できるものの、機能するのは 静的 幾何学。これは、BSP ツリーの構築が一般的に非常に遅く、典型的な静的な都市ゲーム レベルでは数時間から数日かかることが多いためです。
BSP ツリーの構築に時間がかかる 2 つの主な理由は、(a) 軸が整列していない分割平面を使用するため、最適な検出に時間がかかること、(b) 分割平面を横切るオブジェクトが存在しないことを保証するために、軸の境界でジオメトリを細分化することです。
他のタイプの 3D ツリー (八分木、四分木、kd ツリー、境界ボリューム階層) は軸に合わせた境界ボリュームを使用し、ボリュームは (オプションで) オーバーラップできるため、含まれるオブジェクトをボリューム上でカットする必要はありません。境界線。これらにより、ツリーは BSP ツリーよりも最適ではなくなりますが、構築が速くなり、動的オブジェクトの変更が容易になります。
これらの要因を状況に当てはめると...
屋外エリアでは通常、単純なハイトマップまたは ROAM などのより複雑なジオミップ マッピング技術のいずれかである、ハイト フィールド ベースの地面表現が使用されます。地面自体は 3D 空間の分割に関与せず、地面に配置されたオブジェクトのみが関与します。
より単純で類似したジオメトリのインスタンスが多数ある世界 (家、木、小惑星など) では、非 BSP ツリー (BVH など) がよく使用されます。これは、ジオメトリを BSP ツリーに入れることは、オブジェクトを複製して分割することを意味するためです。すべてのインスタンスの詳細なジオメトリ。
逆に、都市部のシーンや複雑な屋内環境など、インスタンス化のない大規模なカスタム静的メッシュでは、通常、実行時のパフォーマンスを向上させるために BSP ツリーが使用されます。BSP ノードは事前に編成された三角形のレンダリング バッチとして使用できるため、BSP ツリーがノード境界でジオメトリを分割するという事実は、レンダリングのパフォーマンスに役立ちます。BSP ツリーはオクルージョンに対して最適化することもできるため、他のジオメトリの背後にあることがわかっている BSP ツリーの部分を描画する必要がなくなります。
以下も参照してください。 オクツリー vs BVH, バウンディングボリューム階層のチュートリアル, BSP チュートリアル.
BSP は都市環境に最適です。
クアッドツリーは、地形などに高さマップを使用する場合に最適です。
オクツリーは、太陽系などの 3D 空間にジオメトリの塊がある場合に最適です。
BSP は、使用するフレーバーに応じて、衝突検出を高速化するための優れたオプションです。点と線または光線のテストでは特に高速ですが、ボリュームのあるものの場合は速度が若干遅くなり、少し複雑になります。
グラフィックスでの BSP の使用に関して言えば、BSP はほとんど時代遅れです。オクツリーは、AABB ツリーと同様に、全体的な可視性のカリングなどに適しています。
私には BSP の経験があまりありませんが、レンダリングしているシーンの高さが高い場合は、4 分木ではなく 8 分木を使用する必要があると言えます。つまり、高さは幅と奥行きの半分以上です。経験則はほとんどありません。一般に、オクツリーはクアッドツリーに比べて大きなコストがかからず、処理をかなり高速化する可能性があります。YMMV。
通常、これらのことには明確な答えがありません。A、B、C は、空間のサイズと区別する物の量の関数の結果であると私は提案します。
BSP は、オクルージョンのみを行う、より小さく単純なスペースに適しています。特定の光線のすべての交差が必要な場合は、クアッド/オクツリーにアップグレードする必要があります。
クアッドツリー vs.octree - どのくらいの次元を重視しますか?2 次元とは 4 つ木、4 つは 8 つ木を意味します。前述したように、4 分木は 3 空間でも機能しますが、各次元に適切な処理を施したい場合は、8 分木が最適です。
