超雑訳 Ray Classification for Accelerated BVH Traversal

Share

レイトレ合宿で使うので,必要なところだけ読むことにします。

いつも通り誤字・誤訳があることがあります。指摘して頂ける場合は,正しい翻訳と共にご指摘いただけると幸いです。

3. Efficient BVH Traversal

このセクションでは、BVHの標準的なトラバーサルがツリーをどのように進んでいくかを詳細に説明し、その弱点を特定します。 シャフトを使用してシーンジオメトリをカリングするというアイデアを簡単に紹介します。これにより、移動コストを大幅に削減できます。

3.1 Standard Traversal

シーンのジオメトリの上に空間インデックスを構築し、プライマリまたはセカンダリレイの最も近い交差点、またはサーフェスと光源の間の可視性をテストするシャドウレイの交差点を決定するために、トラバースする必要があります。これは通常、ツリーを下降させることによって行われます。 ルートノードIDをスタックにプッシュすることから始めます。 その後、最上位のスタックエントリが繰り返しポップされ、さらに処理されます。 リーフノードを表す場合、参照ジオメトリの交差がチェックされます。 内部ノードの場合、その子のバウンディングボックスは交差のためにチェックされます。レイ(該当する場合)にヒットした内部ノードのすべての子は、通常、効率のためにレイに沿って深度ソートした後、スタックにプッシュバックされます。 トラバース中、プライマリレイとセカンダリレイに対して、ジオメトリと実行中の最も近い交差が維持され、検索ツリーがさらに効果的に枝刈りされます。

大きく複雑なジオメトリを持つシーンでは、ルートからジオメトリ要素までのパスの長さは数十のトラバースステップになります。実際の走査は、多くの場合、検索の結果を早めない多くの側枝を訪問するため、さらに複雑です。 これは、階層インデックスが一般的な空間構造であり、シーンで追跡されているレイのプロパティに関する情報がないためです。 特定のレイにのみ関連するシーンの制限された部分は考慮されません。

3.2 Algorithm Overview

この方法は、シーンジオメトリを整理するBVHが既に構築されていることを前提としています。 凸状のフラスタムシャフトのセットを作成します。これは、シーンボクセルから(狭い)方向の間隔で延びています。 ボクセルは3Dの規則的なグリッドの要素であり、方向の間隔は方向の空間を細分化する規則的な2Dグリッド上に構築されます。 各シャフトについて、そのボリュームと交差するBVHの部分を特定し、それらのサブツリーをそれらのインデックスの短い配列(候補リスト)として表します。 図2に示すように、シャフトが関連付けられたソート済みリストは、BVHの階層的性質とシャフトの方向性の組み合わせを表します。

※図は,J.Hendrich, A.Pospíšil, D.Meister, J.Bittner, “Ray Classification for Accelerated BVH Traversal”, Eurographics Symposium on Rendering 2019, Volume 38 (2019), Number 4. より引用。

図2. 選択された1つのフラスタムシャフト(オレンジ色のボックスと破線)といくつかの交差した境界ボリューム(左)、およびベースBVHを参照する関連候補リスト(ノードIDのオレンジ色の配列)の対応する状況の単純なシーン。シャフトにはシーンジオメトリの小さなサブセットのみが含まれており、BVH内のいくつかのノードで表すことができます。 それらの上のノード(点線)およびシャフトと交差しない多くの並列分岐(灰色のサブツリー)のノードの走査は、すべてスキップできます。)

光線の追跡は、光線を含むシャフトを識別することから始まります。 トラバーサルアルゴリズムには、関連する候補リストのノードIDがシードされます。 これらのIDがスタックにプッシュされると、トラバーサルは通常どおり処理されます。 リストにはシーンジオメトリの非常に限られたサブセットのみが含まれているため、トラバースプロセスは通常の初期部分で不要な手順を実行する必要はありません。 最も重要なことは、多くのラテラルサブツリーをローミングする必要がないため、トラバーサルステップとメモリトラフィックの両方の面で多大な労力を節約できることです。

通常、シーン内の光の輸送は非常に不均一に分布しており、多数の光線を含まないシャフトが多数あります。 したがって、構築は、シーン内のレイ分布をサンプリングするオプションの前処理ステップの結果によって導かれます。 ほとんどの光線を保持するシャフトのみの候補リストを最後に作成します。

4. Shaft Culling in BVH Traversal

ここでは、基礎となるデータ構造とそのセットアップから始まり、次にレイトレーシングフェーズで使用する、提案された方法を詳細に説明し、議論します。

4.1. Collection of Shafts

シーンAABBを通常の3Dグリッドに細分化します。この3Dグリッドでは、すべてのボクセルが個々のフラスタムシャフトのベースを形成し、含まれる光線の起点をグループ化します(図3を参照)。 ボクセルごとに、光線の方向を標準的なキューブマッピングに対応する6つの主要な方向区間に分割します。 方向性キューブマップの各面は、通常の2Dグリッドにさらに細分されます。


※図は,J.Hendrich, A.Pospíšil, D.Meister, J.Bittner, “Ray Classification for Accelerated BVH Traversal”, Eurographics Symposium on Rendering 2019, Volume 38 (2019), Number 4. より引用。
図3:選択されたボクセルを起点とする錐台シャフトのサンプルを含む通常のグリッドを使用した空間の細分化。 ほとんどのシーンでは、立方体のようなボクセルを形成するために、3つの軸間でグリッド解像度が異なります。

空間解像度と方向解像度を設定するにはさまざまな方法があります。 3つの軸すべての単一の空間解像度は、特に立方体の比率が大きくないシーンでは特にうまく適合しないことがよくあります。 そのため、3つの軸すべてを異なる数の等間隔に分割できます。 一方、ほとんどのシーンでは、レイの実質的に支配的な方向は存在しないため(または、少なくとも事前に知られていないため)、方向の細分化には均一な解像度を使用します。

空間グリッド解像度を簡単に決定するための便利なオプションは、シャフトコレクションの許容メモリバジェットから自動的に導出することです(絶対量で、またはシーンジオメトリが占有するメモリを基準にして)。 ボクセルを可能な限り立方体の形状に近づけます。これは、立方体のようなノードのSAHプリファレンスとよく一致します。これらのソフト制約は、両側からの解像度の有用な値を制限しています。シャフトは広すぎてはいけません。その場合、シーンジオメトリの大部分をカットしないため、走査コストをあまり節約できません。 これらは、隣接するシャフト間のコンテンツの冗長性の増加と膨大な数のシャフト構造自体の両方によって引き起こされる高いメモリ消費を誘発するため、薄すぎるべきではありません。

コレクションは2つの部分で構成されます。すべての候補リストを連結したリスト領域と、各シャフトのIDをリスト領域の関連する候補リストの対応するオフセットにマップするシャフトルックアップテーブルです。 ノードIDは、メインBVHノード配列への4バイトのインデックスにすぎません。 シャフトコレクションを持つBVHの例を図4に示します。

シャフトIDは、シャフトのボクセルx / y / z座標とu / v方向座標の組み合わせとして計算されます。 このIDは、シャフトルックアップテーブルのキーとして機能します。


※図は,J.Hendrich, A.Pospíšil, D.Meister, J.Bittner, “Ray Classification for Accelerated BVH Traversal”, Eurographics Symposium on Rendering 2019, Volume 38 (2019), Number 4. より引用。
図4:BVHとシャフトコレクションの概略レイアウト。 シャフトルックアップテーブルは、シャフトIDを、候補リスト領域の関連する候補リストのオフセットにマッピングします。 リストには、ベースBVHのノードへの直接インデックスが含まれています。

4.2. Shaft Geometry

シャフトの幾何学的定義は、方向の部分区間を閉じるカリング平面を持つ3Dグリッドベースのボクセルによって完全に記述され,ArvoとKirk[AK87]が提案したものと非常に似ています。ボクセルはカリング平面に囲まれており,フラスタムシャフトのもう一方の端は開いたままになっています。

最大7つのカリングプレーンがシャフトの定義に使用されます:そのうちの4つはシャフトの方向範囲を囲み、最大3つのプレーンがシャフトのボクセルの外面を含みます。 シャフトジオメトリは候補リストの構築中にのみ使用されるため、そのステップ以降のデータ構造では保存されません。

4.3. Candidate List

シャフトの候補リストは、シャフトに囲まれたシーンジオメトリの完全なカバレッジを提供します。 その要素は、シャフトと交差する元のBVHのノードのIDです。 アルゴリズム1では、候補リストの構築を擬似コードで示します。

1: stack.push(bvh.root)
2: while !stack.empty() do
3:     node stack.top()
4:     stack.pop()
5:     if shaft.overlaps(node) then
6:         if node.isInner() then
7:             p ← shaft.getHitProbability(node, sampleRays)
8:             if p >= minHitProbability then
9:                 if shaft.centerRay.dir[node.splitAxis] > 0 then
10:                    stack.push(node.child)
11:                    stack.push(node.child+1)
12:                else
13:                    stack.push(node.child+1)
14:                    stack.push(node.child)
15:            else
16:                node ← shaft.cullNodeSubtree(node)
17:                if node.valid() then
18:                    shaft.candidateList.append(node)
19:        else {leaf}
20:            shaft.candidateList.append(node)

アルゴリズム1:バイナリBVHについてシャフト候補リストの構築

このメソッドの重要なコンポーネントはgetHitProbability()関数です。 この関数は、シャフト内の少数(20)の光線とノードのAABBとの交差をテストし、レンダリングフェーズでこのノードを通過する確率を推定します。これらの光線は、指定されたシャフト内の均一な分布を使用してランダムに生成され、標準のBVHを使用してキャストされ、シーンとの交差を確立します。 ヒット確率の推定では、これらの光線を使用して、ノードのAABBとの交点がサンプル光線とシーンの交点の前にあるかどうかを確認します。 したがって、推定ではオクルージョンも考慮されます。これにより、シーンのオクルージョン領域に候補リストエントリを作成できなくなります。 ヒット確率は、ノードを開いてその子と交換する価値があるかどうかを示す尺度として機能します。 ノードがこのチェックに合格した場合、その子は、シャフトの中心光線の方向に関してスタックにプッシュバックされます。つまり、レンダリングフェーズの後半で光線の早期終了の可能性を高めるために深度ソートされます。

最小ヒット確率のチェックに合格しないノードの場合、cullNodeSubtree()で、関連するすべてのジオメトリをまだ含む単一の子孫ノードを見つけようとします。これは、現在のノードを開いて、シャフトと交差する子の数を確認することにより行われます。 このプロパティを持つ単一の子孫が見つかった場合、候補リスト内の先祖ノードを置き換えます。 場合によっては、すべての子孫ノードがカリングされ、このサブツリー全体が候補リストの一部になるのを効果的に防ぎます。

場合によっては、アルゴリズムは、候補リストの最大サイズとして許可されているよりも多くのノードを生成します。 この問題に対処するために、minHitProbablityの閾値を徐々に増やし、アルゴリズムを再度呼び出します。これにより、候補リストに生成されるノードが少なくなります。

トラバーサルステップの数を確率的に削減するには、最小ヒット確率閾値をk-ary BVHの(k-1)/ kに設定する必要があることが示されます。この閾値が低い場合、アルゴリズムはツリー内でより深く下降し、候補リストが長くなります。 その結果、標準のトラバースよりもさらに多くのノードをトラバースする可能性があります。 逆に、閾値が大きければ、メソッドの可能性を利用せず、BVHルートに近づきすぎません。

候補リストとリスト内のノードから参照されるBVHサブツリーを使用して、ベースBVHよりも大幅に低い高さのサブBVHのセットを効果的に形成します(図1を参照)。 これらの小さなBVHは、シャフト内のコヒーレントレイのグループに関して、シーンジオメトリのビューに依存する事前ソート済みサブセットとして解釈できます。

4.4. Memory Optimizations

シャフトコレクションの構築時間の複雑さの上限は\(O(s^3 d^2 k \log n)\)であり、空間の複雑さは\(O(s^3 d^2 k)\)です。 ここで、\(s\)は3つの軸すべての単一の空間解像度、\(d\)は両方の座標の方向解像度、\(k\)は候補リストの最大長、\(n\)はシーンプリミティブの数を表します。

オプションの削減スキームを使用して、計算とストレージのコストを非常に効率的に制限できます。 アイデアは、最も多くの光線を占有しているシャフトのみが候補リストを作成できる場合の光線サンプリングに依存しています。 シャフト占有基準は、加速されたトラバーサルに使用する光線またはシャフトの割合によって指定できます。 サンプリング段階で収集されたシャフト統計データに基づいて動作し、最も使用されているシャフトから重要度の低いシャフトにソートされます。 レイサンプリングは、低い画像解像度で実行されるレンダリングフェーズであり、ピクセルあたりのサンプル数が少なくなります。 これらのサンプル光線によって収集された光輸送または潜在的な情報をレンダリング中に利用して、サンプリングのコストを償却できます。

レイサンプリングに代わる安価な方法は、シーンジオメトリが占めるボクセルに由来するシャフトのみの候補リストを作成することです。 このアプローチは、すべての二次光線と、表面から光源に向けて投射されるシャドウ光線も処理します。 ただし、処理からプライマリレイを除外します(カメラが空でないボクセルにない場合)。

多くの場合、隣接するシャフトの候補リスト(近くにベースボクセルと同様の光線方向を持つもの)は同一であるため、構築中にハッシュマップ内の候補リストにインデックスを付け、既に同一のコレクション中に候補リストが存在するかどうかをすばやく答えます。 その場合、新しいコピーを再度保存するのではなく、それぞれのシャフトが元のインスタンスを参照するようにします。 この非常に安価なチェックにより、シーンの候補リスト領域のメモリが10〜80%節約されます。

4.5. Traversal

光線のトラバーサルは、光線を分類し、対応する候補リストを検索することから始まります。 リストが正常に見つかった場合、そのすべてのノードがトラバーサルの新しいエントリポイントになり、BVHルートではなくトラバーサルスタックにプッシュされます。 それ以外の場合は、BVHルートをたどって通常の方法で続行します。

これは、行う必要がある標準のトラバーサルカーネルの唯一の変更です。異なる起動を除き、通常の方法でBVHをトラバースします。 したがって、トラバースパスの大部分を削除します。 スタックは候補リスト全体に加えて、リストから参照される個々のサブツリーのトラバーサル用の追加スペースを保持できる必要があるため、トラバーサルスタックの容量を増やす必要があります。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

日本語が含まれない投稿は無視されますのでご注意ください。(スパム対策)

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください