超雑訳 CHC++ : Coherent Hierarchical Culling Revisited

こんばんわ。
Pocolです。
とあるサイトを見て,温めているネタの温度が一気に下がりそうな予感がしたので,温度が下がる前に放出します。

会社でシャドウマップが重い!重い!と文句をつけられるので,カリングに効きそうな手法を探してみました。昔実装した,オクルージョンカリング関係でググったら,CHCが出てきたので,読んでみました。
いつもながら,適当に訳しているので,誤字・誤訳が多々あると思います。ご指摘いただける場合は,正しい翻訳例と共に指摘していただけると幸いです。

Abstract

ハードウェアオクルージョンクエリを用いた効率的なオクルージョンカリングのための新しいアルゴリズムを提案します。アルゴリズムは視認性の時間的および空間的な一貫性をよりよく利用することによって,従来の技術を大幅に改善します。これは適応型の視認性予測とクエリのバッチ処理を用いることによって達成されます。新しい最適化の結果として,発行されたクエリの数とレンダリングステートの変更数が大幅に削減されます。また,オクルージョンクエリに対してタイトなバウンディングボリュームを決定するためのシンプルな方法も提案し,さらにパイプラインのストールを減らします。提案された方法は,従来の最先端技術に比べて1桁までのスピードアップを提供します。新しいテクニックは実装が簡単で,ハードウェアのキャリブレーションに依存せず,現代のゲームエンジンにうまく統合できます。

1. Introduction

オクルージョンカリングは複雑なシーンのレンダリング時間を減らすために重要なテクニックです。ハードウェアオクルージョンクエリの可用性により,ランタイムの可視性の決定が良くなりました。ハードウェアオクルージョンクエリはグラフィックスハードウェアがシンプルなプロキシジオメトリの可視性状態を素早く報告できるメカニズムです。しかしながら,それは時間的な一貫性を利用することのみで,例えば,例えばコヒーレント階層カリング(CHC)アルゴリズム[BWPP04]においては,CPUストールとGPUスタベーションを避けるために実行可能となるハードウェアオクルージョンクエリを使用しています。

CHCアルゴリズムは密集した遮蔽されるシーンではうまく機能しますが,ハードウェアオクルージョンクエリのオーバーヘッドによって,一部のシーンではシンプルな視錘台カリング(VFC)にまで処理が落ちます。これはGutheら[GBK06]によってわかり,彼らはNear Optimal Hierachical Culling(NOHC)と呼ばれるアルゴリズムを提供し,オクルージョンの巧みな統計学モデルとハードウェアキャリブレーションステップに基づいてクエリの数を減らしました。しかし,Gutheらによって定義された最適化さえも,さらなるソースの単純化を利用することによって改善できることが分かっている。

この論文では,以前のオンラインオクルージョンカリング手法上で著しく向上するCHC++を提案します(図1参照)。

※図は,Oliver Mattausch, Jiří Bittner, Michael Wimmer, “CHC++: Coherent Hierarchical Culling Revisited”, Eurographics 2008, Vol.27 (2008), No.2 より引用

アルゴリズムのコアはシンプルなままで,キャリブレーションを必要とせず,容易にゲームエンジンに組み込むことができます。この手法の主な貢献は次のようになります:

  • Reduction of state changes.
  • その重要性にも関わらず,状態変化の削減は以前のオクルージョンカリング手法では明示的に解決されていませんでした。我々の手法はクエリのバッチ処理を用いることによって状態変化の数を最小化するためのパワフルなメカニズムを提供します。その結果,状態変化の数は一桁以上減少します(図2参照)。

    ※図は,Oliver Mattausch, Jiří Bittner, Michael Wimmer, “CHC++: Coherent Hierarchical Culling Revisited”, Eurographics 2008, Vol.27 (2008), No.2 より引用

  • Reduction of number of queries.
  • クエリの数を減らすことは,ハードウェアベースのオクルージョンカリングに基づく以前の研究の主要な目的でした。例えば,Gutheら[GBK06]によって提案されたNOHCアルゴリズムは低オクルージョンでビューに対するクエリの数を減らすことで非常に成功しています。我々はクエリの数をさらに減らすため新たに2つの手法を提案します。最初の手法は,単一クエリによって階層における多くのノードの可視性を解決し,2つ目の手法は指向性バウンディングボックスやk-dopsのような任意の補助データ構造体を必要とせずに,よりタイトなバウンディングボリュームを利用します。その結果,我々はGutheら[GBK06]によって定義された”最適な”アルゴリズムよりもかなり少ないクエリの数を達成しました(図2参照)。

  • Reduction of CPU stalls.
  • CHCアルゴリズムはCPUストールを減らす点において良い仕事をしますが,あるシナリオにおいてはストールがまだ発生し,パフォーマンスペナルティを被ります。状態変更を減らすために我々の手法と一緒にうまく組み込める,待機時間の削減をもたらすシンプルな変更を提案します。

  • Reduction of rendered geometry.
  • タイトなバウンディングボリュームはバウンディングボリュームによって引き起こされる視認性の過剰推定を減らし,よって視認できると分類されたジオメトリの量が減ります。

  • Integration with game engines.

ほとんどのゲームエンジンはレンダリング状態の変化を最小限に抑えるためにマテリアルとシェーダによりソートを行う高度に最適化されたレンダリングループを組み込んでいます。我々の手法はレンダリングエンジンがレンダーキューに格納されるプリミティブバッチに対してそのようなソートを行うことを可能としています。提案されたテクニックを追加することで,著しくエンジン呼び出しの回数を減らします。

2. Related Work

和訳省略。

3. Overview

このセクションでは,CHCアルゴリズムとNOHCアルゴリズムについて簡単にレビューし,いくつかのそれらの問題について説明します。次に,新しいCHC++アルゴリズムの主要なコンポーネントについて説明します。

3.1. CHC and its problem

コヒーレント階層カリング[BWPP04]は,時間的および空間的コヒーレンスを利用し,ハードウェアオクルージョンクリエのオーバーヘッドとレイテンシーを削減します。前から後ろへ順序で階層をトラバースし,以前に視認できるリーフと以前に視認できない境界のノードについてクエリを発行します。前に表示されたリーフは現在フレームにおいても表示されたままであるとみなされ,直ちに描画されます。これらのノードのについてクエリの結果は次のフレームについての分類のみを更新します。非表示ノードは見えないままであると想定されますが,アルゴリズムは可視性の変化を発見するために現在フレームにおけるクエリ結果を取り出します。元のCHCアルゴリズムの疑似コードについては図6を参照してください(マークされていない部分)。

※図は,Oliver Mattausch, Jiří Bittner, Michael Wimmer, “CHC++: Coherent Hierarchical Culling Revisited”, Eurographics 2008, Vol.27 (2008), No.2 より引用

クエリ数の減少(クエリは以前に可視性がある内部ノード上で発行されない)し,巧みなインターリービングは許容可能な量にオクルージョンクエリのオーバーヘッドを減らします。アルゴリズムは多くの遮蔽を持つシナリオでは非常にうまく動作します。しかし,描画するジオメトリがクエリに比べて安価となる新しいハードウェア上や,シーンの多くが視認できるビューポイントでは,この手法は従来の視錘台カリングよりもさらに遅くなる可能性があります。これは無駄なクエリと不要な状態変更の結果となります。この問題は,視錘台カリングよりも信頼性の高いアルゴリズムを必要とするゲーム開発者に対してCHCアルゴリズムを魅力的ではないものにします。CHCの別の問題は,高度に最適化されたゲームエンジンのレンダリングループへの手法の統合が複雑なことです。CHCは空間階層の各ノードの描画とクエリをインタリーブし,マテリアルのソートを実行できず,より多くのエンジンAPIの呼び出し数を招きます。

3.2. NOHC and its problem

Gutheら[GBK06]によって提案されたNear Optimal Hierarchical Cullingアルゴリズムは無駄なクエリの問題に取り組んでいます。この方法では,クエリのコストと描画コストを推測するためにグラフィックスハードウェアのキャリブレーションされたモデルを使用します。単純なスクリーンカバレッジモデルとテンポラルコヒーレンスを想定したさらなる補正を用いてノードのオクルージョンを推定します。現在処理されているノードにオクルージョンクエリを適用するかどうかを決定するオクルージョン推定とハードウェアモデルはコスト/利益ヒューリスティックで使用されます。このヒューリスティックは2つのルールを持ち,クリエに対して洗練された妥当性テストを使用します。

このアルゴリズムは特に可視ノード上に適用されるかなりの数のクエリを保存します。これはCHCについて提案された可視性最適化が使用されない場合に,CHCアルゴリズムを超える大幅な向上になる可能性があります。

NOHCについての結果は適切なハードウェアキャリブレーションを持つ手法は常に視錘台カリングよりも良いことを示しています。彼らの論文では,Gutheら[GBK06]もまたオクルージョンクエリに基づく最適なカリングアルゴリズムを定義しています。最適なアルゴリズムは,オクルージョンクエリによって検証される必要がある各呼び出されたノードの状態の想定かで導出されます。NOHC手法は最適なアルゴリズムに近いアプローチです。我々の論文では,Gutheら[GBK06]によって使用された最適性の定義がまだ改善のための余地が残っているということを示します。実際に,CHC++アルゴリズムはGutheらによって定義された最適性を常にはっきりと下回ります。

NOHCは人工的なレンダリングシナリオを用いてハードウェアパラメータを事前処理計測するハードウェアキャリブレーションステップを必要とします。モデルの正確なパラメータを計測するには,以上に慎重な実装が必要です。しかし,正確に実装されていも,これらの計測はウォークスルー間の状態変化やパイプライン化,インタリービングレンダリングやオクルージョンクエリなどの複雑な過程を反映する必要がありません。我々の新しい手法は,ハードウェアキャリブレーションに依存せず,外部パラメータへの依存を最小化することを目的としています。実際に,影響がうまく予測できる緩やかなパラメータ設定の余地がユーザーに残されています。

3.3. Building blocks of CHC++

新しいCHC++アルゴリズム手法は,前述のすべての問題に対処し,次の新しいコンポーネントを含むことによってCHCを拡張します:
Queues for batching of queries.
ノードがクエリされる前に,キューに追加します。別々キューは以前に見えたノードと以前に見えないノードを蓄積するために使われます。個々のクエリの代わりにクエリのバッチを発行するためにキューを使用します。これにより,1桁から2桁のオーダーで状態変化を減らします。クエリのバッチはセクション4で説明します。
Multiqueries.
シングルのオクルージョンクエリでより多くのノードをカバーすることができるマルチクエリ(セクション5.1)をコンパイルします。これは前の視認できないノードについてのクエリの数を1桁まで減らします。
Randomized sampling pattern for visible nodes.
前の視認できるノードについてクエリをスケジューリングするために,テンポラリーなジッターされたサンプリングパターン(セクション5.2)を適用します。これは視認できるノードについてのクエリの数を減らし,ウォークスルーのフレームにわたって均等に分散します。
Tight bounding volumes.
明示的な構築の必要がないタイトなバウンディングボリュームを使用します(セクション6)。これは,クエリの数の減少だけでなく,描画される三角形の数の減少をもたらします。

この論文中の提示されテストのすべてについて,サーフェイスエリアヒューリスティック[MB90]に従って構築された軸平行バウンディングボリュームヒエラルキーを使用することに注意してください。しかしながら,BVHの性質を明示的に利用するタイトなバウンディングボリュームの最適化を除いて,提案された手法は他の離散的な階層構造[MBM*01]と両立できます。

4. Reducing state changes

レンダリングパイプライン中においてレンダリングステートの変化は重要なコストの構成要素となります。以前のオクルージョンカリング手法は見方によれば全体的なクエリの数を減らすことと同様にGPUの占有保持とレイテンシーを隠すクエリのスケジューリングにフォーカスしていました。しかし,クエリの数が減っても,少なくともカラーと深度バッファへの書き込みが無効化され,クエリ後に再度有効化されて,残りの各クエリが状態変化につながる可能性が残っています。複雑なシェーダが使用されている場合,このとき,この状態変化もまたシェーダのオン/オフの切り替えを含みます。

これらのレンダリングステートの変更は,クエリ自体よりも大きなオーバーヘッドを引き起こすことが分かります。オーバーヘッドはハードウェア側かもしれないし(キャッシュフラッシュなど),ドライバー側やアプリケーション側かもしれません。したがって,状態変化の数を許容可能な数に減らすことが高く望まれます:現在のハードウェア上では許容可能な数としてフレームあたりに約200回の状態変化であるとゲーム開発者は述べています。

Query batching.
この問題に対する我々の解決策はアルゴリズムによって要求された際にすぐにクエリを発行する代わりにオクルージョンクエリをバッチ処理することに基づきます。レンダリングステートはバッチごとに一度だけ変更されるので,状態変更の削減は発行するクエリバッチのサイズに直接一致します。バッチ処理アルゴリズムは以下のセクションで説明するように可視ノードと不可視ノードを別々に処理します。

4.1. Batching previously invisible queries

クエリされる視認できないノードは我々が i-キューと呼ぶキューに追加されます。iキュー内のノード数がユーザー定義のバッチサイズ\(b\)に達すると,クエリするためにレンダリングステートを変更し,iキュー内の各ノードに対してオクルージョンクエリを発行します(セクション5.1で,クエリの数を減らすために1つのオクルージョンクエリ上に結合することが可能ないくつかのノードについてを示します)。

バッチサイズ\(b\)はレンダリングステートの変更の削減と密接に関係し,CHCアルゴリズムのよりもおおよそ\(b\)倍少ない変更になります。一方で,効果的にバッチを遅らせると,視認できないノードに対してクエリの結果の有効性は,あとで特定可能な視認性の変化を意味し,代わりの動作(例えば,視認できるノードを描画すること)を十分に残さない場合に,それらを導入することによって補足のクエリが生成され,更なるレイテンシーを招きます。

\(b\)の最適値はシーンジオメトリ,マテリアルシェーダそして,マテリアルソートに関係するレンダリングエンジンの機能に依存します。我々のシーンとレンダリングエンジンでは,このパラメータの正確なチューニングは必要ではなく,この手法への追加のレイテンシーを導入することなく20から80の間の値でレンダリングステートの変化を大幅に減らすことができました。

4.2. Batching previously visible queries

CHCアルゴリズムは前に視認できたノードに対してクエリを発行し,クエリの結果を待たずにノードのジオメトリを描画するということを思い出してください。CHCと同様に,我々の提案した手法は階層のトラバーサルの間,前に視認できたノードのジオメトリを描画します。しかし,クエリはすぐに発行されません。代わりに,vキューと呼ばれるキューに対応するノードを格納します。

重要なのは,これらのノードについてのクエリは,次のフレームで結果が使われるので現在のフレームについては重要ではないということです。待ち時間を埋めるためにvキューからのノードを用いることによってこの観測を利用します:トラバーサルキューが空で,未処理のクエリ結果が利用できないときはいつでも,vキューからのノードを処理します。

結果として,未処理のクエリのレイテンシーによって引き起こされる前に視認できるノードについてのクエリの適用的バッチ処理を行います。フレームの終わりに,前に見えなかったノードに対するクエリのすべてが処理され,メソッドは単にvキューから処理されてないノードについて単一の大きなバッチを適用するだけです。

vキューからノードを処理をする前に,レンダーステートの変更が必要とされるかどうかの確認もします。ほとんどの場合,視認されないノードについて前に発行されたクエリバッチにより既に変更されるのでレンダーステートの変更の必要が全くありません。

有益な副作用として,vキューはオリジナルのCHCアルゴリズムによって行われる前から後ろへの順序の違反効果を減らします。特に,現在のフレームにおいて前に隠されたノードが視認できるノードを遮蔽する場合,前に視認できないノードが描画される前に前フレームで視認できるノードはクエリされます。この問題は,多くの可視性の変化が同時に起こる状況において明らかになってきます。vキューを使用してクエリを遅らせると,検出するための可視性の変化がより起こる可能性があります。

4.3. Game engine integration

CHC++手法の組み込みを容易にするために既存のゲームエンジンにレンダーキューと呼ばれる追加のキューを使用することを提案します。このキューはレンダリングについてスケジュールされたすべてのノードを蓄積し,クエリのバッチが発行されたときに処理します。レンダーキューを処理するときに,エンジンは内部のマテリアルシェーダソートを適用し,新しい順序でキューに格納されたオブジェクトを描画します。レンダーキューの別の有益な効果は,エンジンAPIの呼び出し削減です。これらの呼び出しが非常にコストがかかる可能性があり,それらの削減は,例えば人気のあるOGREゲームエンジンで経験したように,大幅な高速化をもたらします。

CHC++アルゴリズムで使用される異なるキューの概要を図3に示します。クエリキュー内にオーバーレイされたノードはセクション5.1で説明するマルチクエリに一致することに注意してください。

※図は,Oliver Mattausch, Jiří Bittner, Michael Wimmer, “CHC++: Coherent Hierarchical Culling Revisited”, Eurographics 2008, Vol.27 (2008), No.2 より引用

5. Reducing the number of queries

最近のオンラインオクルージョンクエリ手法はオーバーヘッドを減らすためにオクルージョンクエリの数を減らすことに焦点を当てています。特に,Gutheら[GBK06]の方法は,コスト/利益ヒューリスティックとグラフィックスハードウェアのキャリブレーションされたモデルに基づいてクエリを排除する洗練されたアプローチを提案しています。このセクションでは,Gutheらによって最適であると以前に定義された仮想的アルゴリズムを下回るクエリ数の削減を可能にする新しい2つの手法を提案します。

5.1. Multiqueries for invisible nodes

これまでの技術は(階層におけるノード,グリッドにおけるバウンディングボリュームは)判定するために前のフレームで視認できないプリミティブごとに1つのオクルージョンクエリを使用していました。これらのノードのオクルージョンクエリは減らせないものと考えられていました。しかし,以下の考察では前に視認できないノードであってもクエリ数を減らすことができます:前に視認できないシーンのある一部が現在フレームにおいても視認できないままである場合,可視状態を確認するためにはパーツ全体の1つのオクルージョンクエリで十分です。そのようなクエリはこのシーン部分のすべてのバウンディングボックスプリミティブを描画し,すべのプリミティブが遮蔽されたままの場合にゼロを返します。例えば,静的シーンや静的な視点の極端な場合には,シーンの視認できない部分すべてについて単一のオクルージョンクエリを使用することができます。

ある可視性のコヒーレンスを想定すると,我々の新しい技法は同じように視認できないままになる可能性がある前フレームで視認できないノードのグループを形成することによってそのようなシーン部分を特定することを目的とする。そのような各グループに対しては単一のオクルージョンクエリが発行され,これをマルチクエリと呼びます。マルチクエリがゼロを返す場合,グループ内のすべての非常のままで,それらの状態はシングルクエリによって更新されます。それ以外の場合は,このグループの一貫性が失われ,すべてのノードに対してiキュー中にノードを再挿入し,個々のクエリを発行します。最初のケースでは,クエリ数はグループ内のプリミティブ数分減少します。しかし,2番目のケースでは,バッチに対するマルチクエリは無駄となります。

適切なノードグループを見つけるために,コスト/利益ヒューリスティックに基づく適応的メカニズムを使用します。評価の重要な部分は,次のセクションで説明するノードの可視性の分類における一貫性の推定です。実際のヒューリスティックはセクション5.1.2で説明します。

5.1.1. Estimating coherence of visibility

大部分のケースでは,階層内のほとんどのノードについて強い可視性の一貫性があります。我々の目的は,この一貫性を定量化することです。特に,与えられたノードの可視性の分類を知ることで,次のフレームにおける可視性の分類をが保たれる確率を推定することを目的とします。我々の実験は,ノードの「履歴」と強い相関があります。すなわち,フレーム数とともに,ノードは同じ分類分けを維持します(この値を可視性持続性と呼びます)。非常に長い時間見えなかったノードは見えないままになる可能性があります。例えば,車のエンジンブロックとなるノードは車のエンジン内部をカメラが移動しない限り,決して見えません。逆に,動きの遅いシナリオであっても,頻繁に分類が変化する視認できる境界上にいくつかのノードが常に存在します。したがって,最近で見えなくなったノードがすぐに表示される可能性はきわめて非常に高いです。

可視性の持続性\(i\)の関数として所望される確率を定義し,前のノード履歴に基づいて近似します:

\begin{eqnarray}
p_{keep}(i) \approx \frac{ n_i^{keep} }{ n_i^{all} } \tag{1}
\end{eqnarray}

ここで,\(n_i^{keep}\)は\(i\)フレームと,\(i+1\)番目のフレームにおける状態が同じ状態で維持される既に判定されたノードの数で,\(n_i^{all}\)は\(i\)フレームについて同じ状となる既に判定されたノードの総数です。図4は可視の持続性\(i\)に対する確率\(p_{keep}\)のプロットを示します。カウンタ\(n_i^{keep}\)と\(n_i^{all}\)はウォークするの以前のフレームすべてについての蓄積されたものです。最初の数フレームでは,特に\(i\)の値が大きい場合,\(p_{keep}(i)\)の正確な計算の測定は十分ではありません。この問題は,\(p_{keep}(i)\)のより高い値へと既に計算された値を区分的に伝搬することによって解決されます。

測定により\(p_{keep}(i)\)を評価する代わりに,我々のシーンとウォークスルーについて計測した関数と合理的に一致する解析的な式を提案します:

\begin{eqnarray}
p_{keep}(i) \approx 0.99 – 0.7e^{-i} \tag{2}
\end{eqnarray}

この関数を使用すると,測定された関数と正確な\(p_{keep}\)の推定値は得られませんが,測定された関数の評価を実装することを避けるために使用することが可能です。図4は2つの異なるシーンについて解析的関数と測定関数を図示しています。

※図は,Oliver Mattausch, Jiří Bittner, Michael Wimmer, “CHC++: Coherent Hierarchical Culling Revisited”, Eurographics 2008, Vol.27 (2008), No.2 より引用

5.1.2. Cost/benefit model for multiqueries

与えられたバッチ中(すなわち,iキュー)の前に非常されないノードについてのマルチクエリの最適なサイズを決定することは,考えられるバッチのパーティションをすべてをマルチクエリへと評価するグローバルな最適化問題です。代わりに,我々は各マルチクエリについて利益/コスト比を最大化する欲張りモデルを使用します。これは次のように表されます:

\begin{eqnarray}
C(M) = 1 + p_{fail}(M) * |M|, \tag{3}
\end{eqnarray}

ここで,\(p_{fail}(M)\)はマルチクエリが失敗する確率(ノードの全てが個別にテストされる場合において visibleを返します)で,\(|M|\)はマルチクエリ中のノードの数です。定数1はマルチクエリ自身のコストを表します。一方,\(p_{fail}(M) * |M|\)は個々のノードについての付加的に発行されることが予想されるクエリの数を表します。確率\(p_{fail}\)はマルチクエリ中のノードの可視性持続値\(i_N\)から計算されます:

\begin{eqnarray}
p_{fail}(M) = 1 – {\displaystyle \prod_{\forall N \in M}}{p_{keep}(i_N)}, \tag{4}
\end{eqnarray}

マルチクエリの利点はマルチクエリ中のノードの数が分かりやすくなることです。すなわち,\(B(M) = |M|\)です。iキュー内のノードが与えられると,欲張り最適化アルゴリズムは与えられたコストで利益を最大化します。まず,視認できないままになる確率\(p_{keep}(i_N)\)に基づいて降順でノードをソートします。次に,キュー内の最初のノードから初めて,マルチキューにノードを追加し,各ステップにおいて利益/コスト比としてマルチクエリの値\(V\)を評価します:

\begin{eqnarray}
V(M_j) = \frac{ B(M_j}{ C(M_j) } \tag{5}
\end{eqnarray}

特定の\(M_j\)について\(V\)が最大に達することが分かり,\(j\)はiキューのフロントにおけるノードについてのマルチクエリの最適なサイズに一致する。この最大値に達すると,対応するノードのマルチクエリを発行し,iキューが使い尽くされるまで処理を繰り返します。結果として,視認できないままで高い確率を持つノードについて大きなマルチクエリをコンパイルし,表示に切り替わる可能性があるノードについては小さなマルチクエリをコンパイルします。

5.2. Skipping tests of visible nodes

オリジナルのCHCアルゴリズムは前に視認できたノード上のクエリ数を減らすために重要な最適化を導入しました。視認できるノードは\(n_{av}\)フレームについては表示されたままであるとみなされ,\(n_{av}+1\)フレームでのみテストされます。この最適化により,以前に表示されたリーフの平均クエリ数が\(n_{av} + 1\)倍に減少します。

しかしながら,この単純な方法はクエリを時間的に整列させることができるという問題があります。このクエリアライメントは同一フレーム内でノードが表示される傾向がある状況では問題になります。例えば,典型的な都市のシーンで,視点が地上レベルから屋根レベルを超えて移動する際に,多くのノードが同一フレームで視認できるようになります。その後,それらのノードのクエリは,\(n_{av} + 1\)番目のフレームに対してスケジュールされ,ほとんどのクエリは再度整列されます。1フレームあたりの平均クエリ数は減りますが,アライメントは観測可能なフレームレートの減少を引き起こす可能性があります。小さなランダム値\(-r_{max} < r < r_{max}\)による\(n_{av} + 1\)のランダム化が満足のいく方法で問題を解決しないということに気づきました。問題はランダム化が小さい場合に,まだクエリがきちんと整列している可能性があることです。一方で,ランダム化が大きい場合,クエリの一部の処理が遅すぎるため,可視状態から不可視状態への変更が遅すぎるためキャプチャされます。 最も満足のいく解決策は,オクルージョンクエリの最初の呼び出しをランダム化することによって達成されるということが分かりました。ノードが可視になった後で,クエリが発行される際に次のフレームを決定するために\(0 < r < n_{av}\)の乱数値を使用します。その後,前のテストにおいてノードが既に表示されていた場合,\(n_{av}\)によって与えれるレギュラーサンプリングインターバルを使用します。 我々は,様々な\(n_{av}\)の値を試しました。最適な値はシーン自体,県産の一貫性,ハードウェアパラメータ,レンダリングエンジンのパラメータに依存します。幸いにも,我々のテストでは依存性がそれほど強くないことが示されており,5-10という値はすべてのテストで安全で頑健な選択となりました。

6. Tighter bounding volumes

オクルージョンクエリによって導入されたオーバーヘッドとは別に,カリングアルゴリズムの成功は空間階層のバウンディングボリュームが包含するジオメトリがどのぐらいタイトであるかに強く依存します。フィットが十分にタイトでない場合には,たとえジオメトリが含まれなくても視認できるものとして分類されます。タイトなバウンディングボックスを得るためにいくつかのテクニックが存在し,多くはより複雑な形状を軸平行バウンディングボックスに置き換えるものです。これらの方法はほとんどのオクルージョンカリングアルゴリズムに直接適用できますが,これらのボリュームを維持し,計算することはオーバーヘッドの構成要素にもなります。これは特に動的なシーンについてコストとなります。

我々は任意の階層バウンディングボリュームに適用されるハードウェアオクルージョンクエリのコンテキストにおいて内部ノードに対してよりタイトな領域を決定するための簡単な手法を提案します。特定のノードに対して,特定の深度における子供のバウンディングボリュームのコレクションとしてタイトなバウンディングボリュームを決定します(図5参照)。

※図は,Oliver Mattausch, Jiří Bittner, Michael Wimmer, “CHC++: Coherent Hierarchical Culling Revisited”, Eurographics 2008, Vol.27 (2008), No.2 より引用

バウンディングボリュームジオメトリ(例えば,OpenGL頂点バッファオブジェクト)を描画するために最新のAPIを使用する場合,オクルージョンクエリについて若干複雑なジオメトリはオーバーヘッドを増加がないこと分かります。しかし,スクリーン空間上で小さなバウンディングプリミティブの一部が重なっている場合にタイトなバウンディングボリュームをラスタライズすることはペナルティになる可能性があります,したがってノードのオリジナルのバウンディングボリュームを射影することと比べてフィルレートが増加します。このようなケースを避けるために,よりタイトな領域の有用性を保証するために簡単なテストを使用します。タイトなバウンディングボリュームについてのチャイルドノードを集める際に,子供のバウンディングボリュームの表面積の合計が\(s_{max}\)×親ノードの表面積よりも大きくならないということをテストします(これは特定のビューポイントに依存しないことに注意してください)。この場合に,トラバーサルを終了し,更なる バウンディングの描画を改善しません。ノードからの深度が指定された最大深度\(d_{max}\)よりも大きくなった場合に,バウンディングボリュームの探索を終了します。我々のテストでは次の値が良い結果を与えました:\(d_{max} = 3, s_{max} = 1.4\)。

階層のリーフについてもタイトなバウンディングボリュームを決定することは有益であることに留意してください。これはわずかに深い階層を構築することによって容易達成でき,このとき仮想的なリーフ,つまり内部ノードはトラバーサル中にリーフとして考慮されるリーフとして指定された三角形の数よりも少なくなるように階層の内部ノードを作成します。

結果として,タイトなバウンディングボリュームはほぼノーコストでいくつかの利点をもたらします:(1)階層の内部のノードの早期カリング,(2)視認できるものとして分類されない場合にリーフをカリングする,(3)内部ノードの可視性分類のコヒーレンス増加。最初の特性はクエリの数の減少につながります。2番目の性質は描画された三角形の数を減らします。最後に,3つ目の利点は複数回の視認性の引き上げと引き下げによる内部ノードの視認性の分類の変化を回避します。

7. Putting it all together

CHC++アルゴリズムは,いくつか重要なアドオンで,CHCアルゴリズムの単純さを保持することを目的としています。このセクションでは,完全なCHC++アルゴリズムをまとめ,CHCアルゴリズムとの主な違いを強調します。CHC++アルゴリズムの疑似コードを図6に示します。

CHCのように,階層のトラバースについて優先度付きキューを使用します。このキューは処理されるノードの前から後ろへの順番を提供します。CHCとは異なり,新しいアルゴリズムはクエリされノードを格納するために2つの新しいキューを使用します(vキューとiキュー)。これらの2つのキューはレンダリングステートの変更を減らし,マルチクエリをコンパイルするための鍵となります。直前に表示されたノードは,CHCと同様に直ちに描画されます。現在フレームにおいてテストのためにスケジュールされている場合,それらはvキュー内に配置されます。クエリをスケジューリングするためのアルゴリズムはクエリの数を減らすため説明した時間的にジッタされたサンプリングパターンを使用し,フレームにわたってそれらを均等に配分します。vキューに格納されたノードについてのクエリは発生する必要がある場合に待機時間を無くすために使用されます。フレームの最後にvキュー内にの残りのノードはクエリの単一バッチとなります。

iキューは,前のフレームで不可視だった処理済みノードを蓄積します。キュー内に十分な数のノードがある場合に,マルチクエリにコンパイルしながらiキュー内のノードについてのおくるーじょんクエリのバッチを適用します。この方法をゲームエンジンに統合する場合,視認できるノードは最初にレンダーキューに蓄積されます。レンダーキューはiキューからのバッチが発行される前にエンジンによって処理されます。

8. Results

和訳省略。

9. Conclusion

我々はCHCアルゴリズム[BWPP04]へのいくつかの変更を提案しました。これらの変更により,状態の変更,レンダリングされた三角形の数とクエリの数,そして,パイプラインのストールがさらに減少します。これらの利点はオクルージョンクエリのバッチング,シングルクエリで複数のノードをカバーするマルチクエリ,クエリについてのランダムにジッタされるテンポラルサンプリングパターン,そしてタイトなバウンディングボリュームにより達成されます。

結果は,以前の方法と比較して新しい手法は状態変更の数を最大で2桁減少させ,クエリの数を1桁減少を与えることを示しています。これらの省力化は,CHCに比べて2倍の高速化になり,NOHC[GBK06]と比べて約1.5倍の高速化になります。提案した手法は,ほとんどの場合事前に可視性の分類を知っており「理想的な」方法の数パーセント以内となり,任意のオクルージョンクエリを仕様ぜずに視認できるジオメトリを描画します。新しいアルゴリズムは安定しており,実装が簡単で,ゲームエンジンにうまく組み込めるので,ゲームプログラマーにとって有用になると考えています。

将来的に,総フレームで発行されたクエリ数と描画された三角形の数に依存することを利用してウォークスルー中の自動パラメータの適用の可能性を研究したいです。

コメントを残す

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

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