バウンディングボリューム階層

バウンディングボリューム階層( BVH )は、ジオメトリオブジェクトのセットのツリー構造です。ツリーのリーフノードを形成するすべてのジオメトリオブジェクトは、バウンディングボリュームでラップされます。これらのノードは、小さなセットとしてグループ化され、より大きなバウンディングボリューム内に囲まれます。これらも、再帰的にグループ化され、他のより大きなバウンディングボリューム内に囲まれ、最終的にツリーの最上部に 1 つのバウンディングボリュームがあるツリー構造になります。バウンディングボリューム階層は、衝突検出やレイトレーシングなど、ジオメトリオブジェクトのセットに対するいくつかの操作を効率的にサポートするために使用されます。

オブジェクトを境界ボリュームにラップし、オブジェクトジオメトリ自体をテストする前にそれらの衝突テストを実行すると、テストが簡素化され、パフォーマンスが大幅に向上しますが、境界ボリューム間のペアワイズテストは同じ回数実行されます。境界ボリュームを境界ボリューム階層に配置すると、時間の複雑さ(実行されるテストの数) をオブジェクト数の対数に減らすことができます。このような階層を配置すると、衝突テスト中に、親ボリュームが交差していない場合は子ボリュームを調べる必要がありません (たとえば、2 つのバンパーカーの境界ボリュームが交差していない場合は、バンパー自体の境界ボリュームの衝突をチェックする必要はありません)。

BVH 設計の問題

境界ボリュームの選択は、2 つの目的のトレードオフによって決まります。一方では、非常に単純な形状の境界ボリュームを使用します。したがって、境界ボリュームの格納に必要なバイト数はわずかで、交差テストと距離の計算は単純かつ高速です。他方では、対応するデータオブジェクトに非常にぴったりとフィットする境界ボリュームが必要です。最も一般的に使用される境界ボリュームの 1 つは、軸に沿った最小境界ボックスです。特定のデータオブジェクトセットの軸に沿った最小境界ボックスは計算が簡単で、必要なストレージはわずか数バイトで、堅牢な交差テストは実装が簡単で非常に高速です。

特定の用途向けにBVHを設計する際には、考慮すべきいくつかの望ましい特性があります。^[1]

任意のサブツリーに含まれるノードは、互いに近い位置にある必要があります。ツリーが下に行くほど、ノードは互いに近くなります。
BVH 内の各ノードは最小のボリュームである必要があります。
すべての境界ボリュームの合計は最小である必要があります。
BVH のルートに近いノードには、より注意を払う必要があります。ツリーのルートに近いノードを剪定すると、さらに多くのオブジェクトが以降の検討対象から除外されます。
兄弟ノードの重複量は最小限に抑える必要があります。
BVH は、ノード構造とコンテンツの両方に関してバランスが取れている必要があります。バランスを取ることで、ブランチがトラバースされないときはいつでも、BVH の可能な限り多くの部分を刈り込むことができます。

BVH の構造に関しては、BVH を表すツリーで使用する次数 (子の数) と高さを決定する必要があります。次数の低いツリーは高さが高くなります。そのため、ルートからリーフまでのトラバーサル時間が長くなります。一方、各ノードを訪問して子の重複をチェックするのにかかる作業は少なくなります。次数の高いツリーの場合はその逆で、ツリーの高さは低くなりますが、各ノードでかかる作業は多くなります。実際には、二分木 (次数 = 2) が圧倒的に一般的です。主な理由の 1 つは、二分木の方が構築が簡単だからです。^[2]

工事

ツリー構築方法には、トップダウン、ボトムアップ、挿入の 3 つの主要なカテゴリがあります。

トップダウン方式では、入力セットを 2 つ (またはそれ以上) のサブセットに分割し、選択した境界ボリューム内でそれらを境界付け、各サブセットが 1 つのプリミティブのみで構成される (リーフノードに到達する) まで、再帰的に分割 (および境界付け) を続けます。トップダウン方式は実装が簡単で、構築が速く、最も人気がありますが、一般的には最良のツリーは生成されません。

ボトムアップ法は、入力セットをツリーの葉として開始し、そのうちの 2 つ (またはそれ以上) をグループ化して新しい (内部) ノードを形成し、すべてが 1 つのノード (ツリーのルート) の下にグループ化されるまで同じ方法を進めます。ボトムアップ法は実装がより困難ですが、一般的に優れたツリーが生成される可能性があります。最近のいくつかの研究^{[3]は、低次元空間では、}空間充填曲線を使用してオブジェクトをソートし、この順序に基づいて近似クラスタリングを適用することで、構築速度を大幅に向上できること (トップダウンアプローチと同等かそれ以上) を示しています。

トップダウン方式とボトムアップ方式は、どちらも構築を開始する前にすべてのプリミティブが利用可能である必要があるため、オフライン方式と見なされます。挿入方式は、空のツリーから始めて、一度に 1 つのオブジェクトを挿入することでツリーを構築します。挿入場所は、コストメトリックに従ってツリーができるだけ小さくなるように選択する必要があります。挿入方式は、構築を開始する前にすべてのプリミティブが利用可能である必要がないため、実行時に更新を実行できるため、 オンライン方式と見なされます。

使用法

レイトレーシング

BVHはレイトレーシングで、現在のレイと交差しない境界ボリュームにある幾何学的オブジェクトを省略することで、シーン内の潜在的な交差候補を排除するためによく使用されます。^[4]さらに、一般的なパフォーマンス最適化として、レイトレーシングのトラバーサルアルゴリズムはノードを降順で進み、複数の子ノードがレイと交差しているため、レイの最も近い交差のみが対象である場合、トラバーサルアルゴリズムは最初に近いボリュームを考慮し、そこで交差が見つかった場合、それが2番目（または他の）ボリュームの可能性のある交差よりも確実に近い場合（つまり、ボリュームが重複していない場合）、2番目のボリュームを安全に無視できます。BVHトラバーサル中の同様の最適化は、2番目のボリュームの子ボリュームに降順で進むときにも使用でき、それ以上の検索スペースを制限してトラバーサル時間を短縮できます。

さらに、BVH 用に多くの特殊な方法が開発されました。特にAABB (軸に沿った境界ボックス) に基づく方法、たとえば並列構築、SIMD加速トラバーサル、優れた分割ヒューリスティック (SAH -表面領域ヒューリスティックはレイトレーシングでよく使用されます)、ワイドツリー (4 項ツリーと 16 項ツリーは、実際のシーンの構築とクエリの両方のパフォーマンスで一定の利点を提供します)、および迅速な構造更新 (リアルタイムアプリケーションでは、オブジェクトが空間的に比較的ゆっくりと移動または変形したり、静止したりすることがあり、最初から完全に再構築しなくても、同じ BVH を更新して有効なままにすることができます) などが開発されました。

シーングラフ管理

BVH は、当然のことながら、完全な再構築を行わずにオブジェクトの挿入と削除もサポートしますが、結果として得られる BVH のクエリパフォーマンスは、完全な再構築に比べて通常低下します。これらの問題 (および迅速な構造更新が最適ではないこと) を解決するには、十分な変更 (リーフの重複が大きい、挿入と削除の数がしきい値を超えた、その他のより洗練されたヒューリスティック) が検出された後、新しい BVH を非同期的に並列に、または同期的に構築できます。

BVH は、シーングラフメソッドやジオメトリのインスタンス化と組み合わせて使用することもできます。これにより、メモリ使用量が削減され、構造の更新と完全な再構築のパフォーマンスが向上し、オブジェクトまたはプリミティブの分割が改善されます。

衝突検出

BVHは衝突検出の計算を高速化するためによく使用されます。布シミュレーションの文脈では、BVHは布と布自身、および他のオブジェクトとの衝突を計算するために使用されます。^[5]

オブジェクトセット間の距離計算

BVH のもう 1 つの強力な使用例は、ペアワイズ距離計算です。2 つのオブジェクトセット間の最小距離を見つける単純なアプローチでは、すべてのペアワイズ組み合わせ間の距離を計算します。BVH を使用すると、すべてのオブジェクト間の複雑な距離を計算することなく、多くの比較を効率的に削減できます。2 つのオブジェクトセット間のペアワイズ距離を計算する擬似コードと、距離計算に適した BVH を構築するためのアプローチについては、ここで説明されています^[6]

ハードウェア対応のBVHアクセラレーション

レイトレーシングの高速化

BVH は、レイサーフェス交差計算の数を減らすことで、レイトレーシングアプリケーションを大幅に高速化できます。トラバーサルなどの BVH 操作をハードウェアで実装すると、レイトレーシングをさらに高速化できます。現在、リアルタイムレイトレーシングは複数のプラットフォームで利用できます。BVH のハードウェア実装は、これを可能にする重要なイノベーションの 1 つです。

Nvidia RT コア

2018年、NvidiaはRTXプラットフォームの一部として、Turing GPUアーキテクチャを備えたRTコアを導入しました。RTコアは、BVHトラバーサルとレイトライアングル交差テストを高速化するように設計された特殊なハードウェアユニットです。 ^[7] これらの主要な機能の組み合わせにより、ビデオゲームに使用できるリアルタイムレイトレーシングが可能になります。^[8]および設計アプリケーション。

AMD RDNA 2/3

2019年に導入されたAMDのRDNA（Radeon DNA）アーキテクチャは、2番目のイテレーションであるRDNA 2以降、ハードウェアアクセラレーションによるレイトレーシングを組み込んでいます。このアーキテクチャは、レイアクセラレータと呼ばれる専用のハードウェアユニットを使用して、バウンディングボリューム階層（BVH）のトラバースに不可欠なレイボックスおよびレイトライアングルの交差テストを実行します。^[9] RDNA 2および3では、シェーダーがBVHのトラバースを担当し、レイアクセラレータがボックスノードとトライアングルノードの交差テストを処理します。^[10]

レイトレーシングを超えたHW対応BVHの使用

もともとレイトレーシングを高速化するために設計されたものですが、研究者たちは現在、高速なBVHトラバーサルを活用して他のアプリケーションを高速化する方法を検討しています。これには、ポイントの包含四面体の決定、^[11]、粒状物質シミュレーションの強化、^[12]、および最近傍計算の実行が含まれます。^[13]一部の方法では、これらのタスクをレイトレーシングの問題として再構成することで、NvidiaのRTコアコンポーネントを再利用しています。^[12]さまざまなアプリケーションでパフォーマンスが大幅に高速化されることが報告されているため、この方向性は有望と思われます。

参照

参考文献

^ Ericson, Christer (2005). 「§6.1 階層設計の問題」.リアルタイム衝突検出. Morgan Kaufmann インタラクティブ 3D テクノロジーシリーズ. Morgan Kaufmann. pp. 236–7. ISBN 1-55860-732-3。
^ エリックソン 2005、238 ページ
^ Gu, Yan; He, Yong; Fatahalian, Kayvon; Blelloch, Guy (2013). 「近似凝集クラスタリングによる効率的な BVH 構築」(PDF) . HPG '13: 第 5 回高性能グラフィックスカンファレンスの議事録. ACM. pp. 81–88. CiteSeerX 10.1.1.991.3441 . doi :10.1145/2492045.2492054. ISBN 9781450321358.S2CID 2585433 。
^ Günther, J.; Popov, S.; Seidel, H.-P.; Slusallek, P. (2007). 「BVH ベースのパケットトラバーサルによる GPU でのリアルタイムレイトレーシング」。2007 IEEEインタラクティブレイトレーシングシンポジウム。IEEE。pp. 113–8。CiteSeerX 10.1.1.137.6692。doi : 10.1109 / RT.2007.4342598。ISBN 978-1-4244-1629-5.S2CID 2840180 。
^ Bridson, Robert; Fedkiw, Ronald; Anderson, John (1997 年 6 月 25 日)。「布アニメーションの衝突、接触、摩擦の堅牢な処理」。ACM Trans. Graph . 21 (3)。ベルリン: Association for Computing Machinery: 594–603。doi : 10.1145 /566654.566623。
^ Ytterlid, Robin; Shellshear, Evan (2015年1月27日). 「高速距離クエリのためのBVH分割戦略」. Journal of Computer Graphics Techniques . 4 (1): 1–25. ISSN 2331-7418 . 2024年10月13日閲覧。
^ 「NVIDIA Turing GPU アーキテクチャ」(PDF) . NVIDIA . 2024 年 10 月 20 日閲覧。
^ 「NVIDIA Turing GPU アーキテクチャの詳細: GeForce RTX への序章」AnandTech 。2024年 10 月 20 日閲覧。
^ 「RDNA 2 ハードウェアレイトレーシング」。Interplay of Light 2020年12月27日。 2024年10月20日閲覧。
^ 「AMDのRDNA 2/3、およびNvidiaのTuringとPascalでのレイトレーシング」。Chips and Cheese。2023年3月22日。 2024年10月20日閲覧。
^ Wald, Ingo; Usher, Will; Morrical, Nathan; Lediaev, Laura; Pascucci, Valerio (2019)。「RTX Beyond Ray Tracing: Tet-Mesh Point Location のためのハードウェアレイトレーシングコアの使用の検討」。ハイパフォーマンスグラフィックス - ショートペーパー: 7 ページ。doi :10.2312/ HPG.20191189。ISBN 978-3-03868-092-5. ISSN 2079-8687.
^ ab Zhao, Shiwei; Zhao, Jidong (2023年11月1日). 「任意形状粒子に対する高性能レイトレーシング離散要素法による粒状物質シミュレーションの革新」.応用力学および工学におけるコンピューター手法. 416 : 116370. doi :10.1016/j.cma.2023.116370.
^ Zhu, Yuhao (2022-04-02). 「RTNN :ハードウェアレイトレーシングを使用した近傍検索の高速化」。並列プログラミングの原理と実践に関する第27回ACM SIGPLANシンポジウムの議事録。ACM。pp . 76–89。doi :10.1145/3503221.3508409。ISBN 978-1-4503-9204-4。

外部リンク

JavaScript での BVH。
C# での動的 BVH
Intel Embree オープンソース BVH ライブラリ
BVH の構築方法 - パート 1

[1] Ericson, Christer (2005). 「§6.1 階層設計の問題」.リアルタイム衝突検出. Morgan Kaufmann インタラクティブ 3D テクノロジーシリーズ. Morgan Kaufmann. pp. 236–7. ISBN 1-55860-732-3。

[2] エリックソン 2005、238 ページ

[AAC-3] Gu, Yan; He, Yong; Fatahalian, Kayvon; Blelloch, Guy (2013). 「近似凝集クラスタリングによる効率的な BVH 構築」(PDF) . HPG '13: 第 5 回高性能グラフィックスカンファレンスの議事録. ACM. pp. 81–88. CiteSeerX 10.1.1.991.3441 . doi :10.1145/2492045.2492054. ISBN 9781450321358.S2CID 2585433 。

[4] Günther, J.; Popov, S.; Seidel, H.-P.; Slusallek, P. (2007). 「BVH ベースのパケットトラバーサルによる GPU でのリアルタイムレイトレーシング」。2007 IEEEインタラクティブレイトレーシングシンポジウム。IEEE。pp. 113–8。CiteSeerX 10.1.1.137.6692。doi : 10.1109 / RT.2007.4342598。ISBN 978-1-4244-1629-5.S2CID 2840180 。

[5] Bridson, Robert; Fedkiw, Ronald; Anderson, John (1997 年 6 月 25 日)。「布アニメーションの衝突、接触、摩擦の堅牢な処理」。ACM Trans. Graph . 21 (3)。ベルリン: Association for Computing Machinery: 594–603。doi : 10.1145 /566654.566623。

[6] Ytterlid, Robin; Shellshear, Evan (2015年1月27日). 「高速距離クエリのためのBVH分割戦略」. Journal of Computer Graphics Techniques . 4 (1): 1–25. ISSN 2331-7418 . 2024年10月13日閲覧。

[nvidia-turing-7] 「NVIDIA Turing GPU アーキテクチャ」(PDF) . NVIDIA . 2024 年 10 月 20 日閲覧。

[anandtech-8] 「NVIDIA Turing GPU アーキテクチャの詳細: GeForce RTX への序章」AnandTech 。2024年 10 月 20 日閲覧。

[rdna2-9] 「RDNA 2 ハードウェアレイトレーシング」。Interplay of Light 2020年12月27日。 2024年10月20日閲覧。

[chipsandcheese-10] 「AMDのRDNA 2/3、およびNvidiaのTuringとPascalでのレイトレーシング」。Chips and Cheese。2023年3月22日。 2024年10月20日閲覧。

[11] Wald, Ingo; Usher, Will; Morrical, Nathan; Lediaev, Laura; Pascucci, Valerio (2019)。「RTX Beyond Ray Tracing: Tet-Mesh Point Location のためのハードウェアレイトレーシングコアの使用の検討」。ハイパフォーマンスグラフィックス - ショートペーパー: 7 ページ。doi :10.2312/ HPG.20191189。ISBN 978-3-03868-092-5. ISSN 2079-8687.

[:0-12] Zhao, Shiwei; Zhao, Jidong (2023年11月1日). 「任意形状粒子に対する高性能レイトレーシング離散要素法による粒状物質シミュレーションの革新」.応用力学および工学におけるコンピューター手法. 416 : 116370. doi :10.1016/j.cma.2023.116370.

[13] ^ Zhu, Yuhao (2022-04-02). 「RTNN :ハードウェアレイトレーシングを使用した近傍検索の高速化」。並列プログラミングの原理と実践に関する第27回ACM SIGPLANシンポジウムの議事録。ACM。pp . 76–89。doi :10.1145/3503221.3508409。ISBN 978-1-4503-9204-4。