拙訳「CHC++: Coherent hierarchical culling revisited」

1. はじめに（Introduction）#

オクルージョンクエリは複合的なシーンをレンダリングするのにかかる時間を減らすために重要な技術である。いわゆるハードウェアオクルージョンクエリの可用性は可視性の実行時測定《runtime determination》を魅力的にしてきた。ハードウェアオクルージョンクエリはグラフィクスハードウェアが単純なプロキシオブジェクトの可視性状態を素早く報告できるメカニズムである。しかしながら、ハードウェアオクルージョンクエリが使用できるようになるのは、例えばCoherent Hierarchical Culling (CHC)アルゴリズム[Bittner et al. 2004Bittner, J., Wimmer, M., Piringer, H. and Purgathofer, W. 2004. Coherent hierarchical culling: Hardware occlusion queries made useful. Computer Graphics Forum 23, 3, 615–624. 10.1111/j.1467-8659.2004.00793.x. https://www.cg.tuwien.ac.at/research/vr/chcull/bittner-eg04-chcull.pdf.]にあるような、時間的一貫性《temporal coherence》を活用することによってのみである。なぜなら、これはCPUをストールしたりGPUを飢餓状態《starvation》にしたりすること回避するためである。

CHCアルゴリズムは｜密に遮蔽された《densely occluded》シーンで上手く機能するが、ハードウェアオクルージョンクエリのオーバーヘッドはいくつかの状況において単純な視錐台カリング(VFC)にさえ｜後れを取る《fall behind》ようにしてしまう。これは、オクルージョンの賢い統計モデルとハードウェア較正《calibration》ステップに基づいてクエリ数を減少させるNear Optimal Hierarchical Culling (NOHC)と呼ばれるアルゴリズムを提供する、 Guthe et al. [2006Guthe, M., Balázs, Á. and Klein, R. 2006. Near optimal hierarchical culling: Performance driven use of hardware occlusion queries. Symposium on rendering. 10.2312/EGWR/EGSR06/207-214. https://cg.cs.uni-bonn.de/backend/v1/files/publications/guthe-2006-neal-optimal.pdf.] によって認知された。しかしながら、Guthe et al.によって定義された最適条件でさえ更なる単純化の情報源《sources》を活用することによって依然として改善できることが分かっている。

（図1：視錐台カリング(VFC)、Coherent Hierarchical Culling (CHC)、Near Optimal Hierarchical Culling (NOHC)、我々の新しいアルゴリズム(CHC++)に対する発電所モデルのウォークスルーのフレーム時間の比較。）

本論において、我々は以前のオンラインのオクルージョンカリング手法に大幅な改良を加える手法であるCHC++を提案する(図1を参照)。そのアルゴリズムの核は単純なままであり、較正をまったく必要とせず、ゲームエンジンへと簡単に統合することができる。その手法の主要な貢献は以下である。

｜ステート変更《state changes》の削減。その重要性に関わらず、ステート変更の削減は以前のオクルージョンカリング手法によって明示的に扱われなかった。我々の手法はクエリのバッチ処理を用いることによってステート変更の数を最小化するための強力なメカニズムを提供する。結果として、ステート変更の総数は｜1桁以上《more than an order of magnitude》削減される。
クエリ数の削減。クエリ数の削減はハードウェアベースのオクルージョンカリングにおける以前の研究の主要な目標であった。例えば、 Guthe et al. [2006Guthe, M., Balázs, Á. and Klein, R. 2006. Near optimal hierarchical culling: Performance driven use of hardware occlusion queries. Symposium on rendering. 10.2312/EGWR/EGSR06/207-214. https://cg.cs.uni-bonn.de/backend/v1/files/publications/guthe-2006-neal-optimal.pdf.] によって提案されるNOHCアルゴリズムは低い遮蔽率を持つビューに対するクエリ数の削減では非常に成功している。我々はクエリ数の更なる削減のための2つの新しい手法を提案する。1つ目の手法は単一のクエリによって階層において多くのノードの可視性を解決し、2つ目の手法はOriented Bounding Boxやk-DOPのような補助データ構造を必要としないクエリに対するよりタイトな境界ボリュームを活用する。結果として、我々は Guthe et al. [2006Guthe, M., Balázs, Á. and Klein, R. 2006. Near optimal hierarchical culling: Performance driven use of hardware occlusion queries. Symposium on rendering. 10.2312/EGWR/EGSR06/207-214. https://cg.cs.uni-bonn.de/backend/v1/files/publications/guthe-2006-neal-optimal.pdf.] によって定義される”最適”なアルゴリズムより大幅に少ないクエリ数を達成する(図2を参照)。
CPUストールの削減。CHCアルゴリズムはCPUストールの削減では良い働きをするが、あるシナリオにおいて、ストールは依然として発生し、パフォーマンス上のペナルティを引き起こす。我々は待ち時間のさらなる削減をもたらし、それと同時にステート変更の削減に対する我々の手法と上手く統合する単純な修正を提案する。
レンダリングされるジオメトリの削減。よりタイトな境界ボリュームは境界ボリュームによって引き起こされる可視性の過剰推定を削減し、それ故に、可視として分類されるジオメトリ量を削減するだろう。
ゲームエンジンとの統合。ほとんどのゲームエンジンはマテリアルによってソートされている高度に最適化されたレンダリングループを｜組み入れ《incorporate》、シェーダはレンダリングステートの変更を最小化する順番で処理される。我々の手法はレンダリングエンジンがレンダキューに格納されるプリミティブのバッチ上でそのようなソートを処理できるようにする。加えて、提案される技術はエンジン呼び出し数を大幅に削減する。

（図2：左上:街のシーンにおけるサンプル視点。右上:CHCアルゴリズムによって必要とされるステート変更(ステート変更の数 = 階層ノードの異なる色の数)。左下:CHC++アルゴリズムによって必要とされるステート変更。右下:マルチクエリ:すべての可視ノードがたった2つのオクルージョンクエリによって網羅される(異なる色で示される)。）

2. 関連研究（Related Work）#

こんにちの急速に進化するグラフィクスハードウェアでしばしば発生する｜CPUに制約された《CPU-limited》アプリケーションでさえ、可視性カリングはグラフィクスドライバやレンダリングAPIにかかる時間を大幅に削減でき、グラフィクスハードウェアをより良く使うことができる。可視性カリングの一般的な概要については、 Cohen-Or et al. [2003Cohen-Or, D., Chrysanthou, Y.L., Silva, C.T. and Durand, F. 2003. A survey of visibility for walkthrough applications. IEEE Transactions on Visualization and Computer Graphics 9, 3, 412–431. 10.1109/TVCG.2003.1207447. https://people.csail.mit.edu/fredo/PUBLI/surveyTVCG.pdf.] や Bittner and Wonka [2003Bittner, J. and Wonka, P. 2003. Visibility in computer graphics. Environment and Planning B: Planning and Design 30, 5, 729–755. 10.1068/b2957. http://www.casa.ucl.ac.uk/mike-michigan-april1/mike%27s%20stuff/attach/bittner_wonka.pdf.] の｜精緻な調査《thorough surveys》を参照していただきたい。

可視性アルゴリズムは事前処理の工程として処理するものと実行時に処理するものに大まかに分類することができる。事前処理のアルゴリズムは実行時のオーバーヘッドを一切持たないが、その一方で、しばしば実装し辛く、静的なシーンに対してのみ正常に動作する。一方のオンラインのオクルージョンカリングは長々しい事前処理の工程に頼らず、点からの可視性を計算するためにより正確となる可能性があり、また、完全に動的なシーンに対して行うことが可能となる。ほとんどのオンラインのカリングアルゴリズムはイメージ空間で動作するため、ラスタライゼーションを用いて自動的なオクルーダーの融合を可能にする。専用のハードウェアサポートが存在する前は、オンラインのオクルージョンカリングは、 Zhang et al. [1997Zhang, H., Manocha, D., Hudson, T. and Hoff, K. E. 1997. Visibility culling using hierarchical occlusion maps. Proceedings of the 24th annual conference on computer graphics and interactive techniques 77–88. 10.1145/258734.258781. https://gamma.cs.unc.edu/papers/documents/technicalreports/tr97004.pdf.] によるHierarchical Occlusion Mapsや Aila and Miettinen [2004Aila, T. and Miettinen, V. 2004. dPVS: an occlusion culling system for massive dynamic environments. IEEE Computer Graphics and Applications 24, 2, 86–97. 10.1109/MCG.2004.1274066. https://articles.tomasparks.name/publications/Aila2004.pdf.] によるdPVSシステムのようないくつかの有名な例外を除いて、実践で用いるにはコストが高すぎるとおおよそ考えられていた。

｜ハードウェアで高速化された《hardware accelerated》オクルージョンクエリの導入に伴い、オンラインのオクルージョンカリングは多くの人気を獲得した。ハードウェアオクルージョンクエリはフレームバッファを読み戻す必要なしにプロキシジオメトリの可視ピクセル数を返す比較的軽量な命令である。これらは多種多様なアルゴリズム[Klosowski and Silva 2001Klosowski, J.T. and Silva, C.T. 2001. Efficient conservative visibility culling using the prioritized-layered projection algorithm. IEEE Transactions on Visualization and Computer Graphics 7, 4, 365–379. 10.1109/2945.965350. https://www.sci.utah.edu/~csilva/papers/tvcg2001cr.pdf.; Hillesland et al. 2002Hillesland, K., Salomon, B., Lastra, A. and Manocha, D. 2002. Fast and Simple Occlusion Culling using Hardware-Based Depth Queries.; Govindaraju et al. 2003Govindaraju, N. K., Sud, A., Yoon, S.-E. and Manocha, D. 2003. Interactive visibility culling in complex environments using occlusion-switches. Proceedings of the 2003 symposium on interactive 3D graphics 103–112. 10.1145/641480.641501. https://gamma.cs.unc.edu/SWITCH/Paper/i3d03.pdf.; Staneker et al. 2004Staneker, D., Bartz, D. and Straßer, W. 2004. Occlusion culling in OpenSG PLUS. Computers & Graphics 28, 1, 87–92. 10.1016/j.cag.2003.10.008.; Kovalčík and Sochor 2005Kovalčík, V. and Sochor, J. 2005. Occlusion Culling with Statistically Optimized Occlusion Queries. WSCG '2005: Short Papers: The 13-th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision 2005 in co-operation with EUROGRAPHICS 109--112. https://dspace.zcu.cz/items/df24ceaa-74af-4219-958b-c8e0ee549a35.]に対する分野を切り開いたが、そのクエリはコストを伴うため、｜愚直な《naive》実装ではクエリが戻るのを待つことによって引き起こされるGPUおよびCPUのアイドル時間により非常に遅くなる可能性がある。

Coherent Hierarchical Culling [Bittner et al. 2004Bittner, J., Wimmer, M., Piringer, H. and Purgathofer, W. 2004. Coherent hierarchical culling: Hardware occlusion queries made useful. Computer Graphics Forum 23, 3, 615–624. 10.1111/j.1467-8659.2004.00793.x. https://www.cg.tuwien.ac.at/research/vr/chcull/bittner-eg04-chcull.pdf.]や後のNear Optimal Hierarchical Culling [Guthe et al. 2006Guthe, M., Balázs, Á. and Klein, R. 2006. Near optimal hierarchical culling: Performance driven use of hardware occlusion queries. Symposium on rendering. 10.2312/EGWR/EGSR06/207-214. https://cg.cs.uni-bonn.de/backend/v1/files/publications/guthe-2006-neal-optimal.pdf.]は時間的一貫性を利用することでアイドル時間を回避する。これらは次節にてその詳細を論じたい。

3. 概要（Overview）#

この節では、CHCおよびNOHCアルゴリズムを｜手短に評し《briefly review》、これらの問題のいくつかを論ずる。その後、我々は新しいCHC++アルゴリズムの主要な構成要素を述べる。

3.1. CHCとその問題（CHC and its problems）#

Coherent Hierarchical Cullingアルゴリズム[Bittner et al. 2004Bittner, J., Wimmer, M., Piringer, H. and Purgathofer, W. 2004. Coherent hierarchical culling: Hardware occlusion queries made useful. Computer Graphics Forum 23, 3, 615–624. 10.1111/j.1467-8659.2004.00793.x. https://www.cg.tuwien.ac.at/research/vr/chcull/bittner-eg04-chcull.pdf.]はハードウェアオクルージョンクエリのオーバーヘッドおよびレイテンシを減らすために時間的および空間的一貫性を利用する。前から後ろへの順に階層を横断し、｜以前に可視であった《previously visible》｜リーフ《leaves》¹と｜以前に不可視であった境界《previously invisible boundary》のノードに対してのみクエリを発行する。以前に可視であったリーフは現在のフレームにおいて可視のままであると仮定され、故にこれらは即座にレンダリングされる。これらのノードに対するクエリの結果は次のフレームに対するこれらの分類を更新するのみである。不可視であるノードは不可視のままであると仮定されるが、そのアルゴリズムは可視性の変化を発見するために現在のフレームにおけるクエリ結果を｜検索する《retrieve》。オリジナルのCHCアルゴリズムの擬似コードに対する図6を参照のこと(｜印のない部分《unmarked parts》)。

クエリ数の削減(クエリは以前に可視であった内側《interior》ノードに関して発行されない)と賢いインターリービングは許容できる量にまでオクルージョンクエリのオーバーヘッドを削減した。そのアルゴリズムは大量の遮蔽を持つシナリオに対して非常に上手く機能する。しかし、ジオメトリのレンダリングが｜問い合わせ《querying》と比べて安価となるより新しいハードウェアやシーンの多くが可視となる視点では、その手法は伝統的な視錐台カリングより低速にさえなる可能性がある。これは無駄なクエリや不必要なステート変更の結果である。この問題は視錐台カリングより確実に高速であるアルゴリズムを求めているゲーム開発者に対してCHCアルゴリズムを魅力的でなくしている。CHCのもうひとつの問題は高度に最適化されたゲームエンジンのレンダリングループへのその手法の複雑な統合にある。CHCは空間的階層の個々のノードのレンダリングと問い合わせを｜互い違いにする《interleave》。これはエンジンがマテリアルでのソートを処理することを不可能にし、より多数のエンジンAPI呼び出しを引き起こす。

3.2. NOHCとその問題（NOHC and its problems）#

Guthe et al. [2006Guthe, M., Balázs, Á. and Klein, R. 2006. Near optimal hierarchical culling: Performance driven use of hardware occlusion queries. Symposium on rendering. 10.2312/EGWR/EGSR06/207-214. https://cg.cs.uni-bonn.de/backend/v1/files/publications/guthe-2006-neal-optimal.pdf.] によって提案されるNear Optimal Hierarchical Cullingアルゴリズムは無駄なクエリの問題に取り組む。その手法はクエリコストとレンダリングコストを推定するためにグラフィクスハードウェアの較正されたモデルを用いる。単純なスクリーンカバレッジモデルと時間的一貫性を仮定する更なる補正を用いることによってノードの遮蔽を推定する。その遮蔽推定とハードウェアモデルは現時点で処理されているノードに関してオクルージョンクエリを適用するかどうかを決める費用便益《cost/benefit》のヒューリスティクスに用いられる。このヒューリスティックは2、3の規則を伴うクエリに対する洗練された妥当性テストを用いる。

そのアルゴリズムは、かなりのクエリ数を、特に可視ノード上に適用されるであろうクエリを節約する。これはCHCで提案される仮定された可視性の最適化が用いられない場合にCHCアルゴリズム全体に大幅な改善をもたらし得る。

NOHCに対する結果は、適切なハードウェア較正により、その手法が視錐台カリングより上手に常に処理されることを示している。彼らの論文において、 Guthe et al. [2006Guthe, M., Balázs, Á. and Klein, R. 2006. Near optimal hierarchical culling: Performance driven use of hardware occlusion queries. Symposium on rendering. 10.2312/EGWR/EGSR06/207-214. https://cg.cs.uni-bonn.de/backend/v1/files/publications/guthe-2006-neal-optimal.pdf.] はオクルージョンクエリに基づいた最適なカリングアルゴリズムも定義した。その最適なアルゴリズムはすべてのカリングされるノードの状態がオクルージョンクエリによって検証されなければならないという前提の下で導出される。そうして、NOHC手法は最適なアルゴリズムに近づく。

我々の論文では、我々は Guthe et al. [2006Guthe, M., Balázs, Á. and Klein, R. 2006. Near optimal hierarchical culling: Performance driven use of hardware occlusion queries. Symposium on rendering. 10.2312/EGWR/EGSR06/207-214. https://cg.cs.uni-bonn.de/backend/v1/files/publications/guthe-2006-neal-optimal.pdf.] によって用いられる最適性の定義が依然として｜多大な改善の余地を残している《leaves significant room for improvement》ことを示す。実際に、CHC++アルゴリズムはGuthe et al.によって定義される最適条件《optimum》を常に明らかに下回っている。

NOHCはハードウェアパラメータが人為的なレンダリングシナリオを用いる事前処理において測定されるハードウェア較正の工程を必要とする。モデルの正確なパラメータの測定は非常に｜慎重な《careful》実装を必要とする。しかし、｜精密に《precisely》実装したとしても、これらの測定はステート変更、パイプライン処理、実際のウォークスルー中のレンダリングとオクルージョンクエリのインターリービングの複合的な処理を反映する必要がないことが判明している。我々の新しい手法はハードウェア較正に頼らず、外部パラメータへの依存度を最小化することを目的とする。実際に、ユーザにはその影響度が十分に予測可能であるいくつかのパラメータを大まかに設定できるようにしてある。

3.3. CHC++の構成要素（Building blocks of CHC++）#

新しいCHC++アルゴリズム手法は以前に言及したすべての問題に取り組み、以下の新しい構成要素を含めることによってCHCを拡張する。

クエリの｜バッチ処理《batching》のためのキュー。ノードはクエリされる前に、キューへ追加される。以前に可視であったノードと以前に不可視であったノードを累積するために別々のキューが用いられる。我々は個別のキューではなくクエリのバッチを発行するためにキューを用いる。これはステート変更を1桁から2桁ほど削減する。クエリのバッチ処理は節4で述べたい。

マルチクエリ。我々は単一のオクルージョンクエリによってより多くのノードをカバーすることができるマルチキューをコンパイルする(節5.1)。これは以前に不可視であったノードに対するクエリ数を1桁台にまで削減する。

タイトな境界ボリューム。我々は明示的な構築を必要とせずにタイトな境界ボリュームを用いる(節6)。これはクエリ数の削減と共にレンダリングされるトライアングル数の削減をもたらす。

本論に示されるすべてのテストに対して、我々は表面積のヒューリスティクス[MacDonald and Booth 1990MacDonald, J. D. and Booth, K. S. 1990. Heuristics for ray tracing using space subdivision. The Visual Computer 6, 3, 153–166. 10.1007/BF01911006. https://www.rose-hulman.edu/class/csse/csse451/Papers-hierarchy/MacDonald-Heuristics%20for%20ray%20tracing%20using%20space%20subdivision.pdf.]に従って構築される軸並行な境界ボリューム階層(BVH)を用いたことに注意する。しかし、その示される手法は、BVHの特性を明示的に活用するタイトな境界ボリューム最適化を除いて、他の種類の空間的階層[Meißner et al. 2001Meißner, M., Bartz, D., Müller, G., Hüttner, T. and Einighammer, J. 2001. Generation of decomposition hierarchies for efficient occlusion culling of large polygonal models. Proceedings of the vision modeling and visualization conference 2001 225–232.]と互換性がある。

4. ステート変更の削減（Reducing state changes）#

レンダリングステートの変更はレンダリングパイプラインにおいてかなりのコストを｜占める《constitute》。以前のオクルージョンカリング手法は、クエリの全体数を削減するだけでなく、主にレイテンシを隠蔽しつつGPUを占有し続ける方法においてクエリをスケジューリングすることに焦点を当てていた。しかし、クエリ数が削減されるとしても、残りのクエリのすべては、少なくとも色や深度バッファへの書き込みが無効化され、そして、クエリの後に再び有効化されるようなステート変更を潜在的に引き起こす。複合的なシェーダが用いられる場合、このステート変更もまたシェーダのオンオフの切り替えを伴う。

これらのレンダリングステートの変更はクエリそれ自体よりずっと大きなオーバーヘッドを引き起こす。そのオーバーヘッドはハードウェア側(例えば、キャッシュのフラッシュ)にあるかもしれないし、ドライバ側にあるかもしれないし、アプリケーション側にさえあるかもしれない。よって、ステート変更の数を許容できる量にまで削減することは非常に望ましい。ゲーム開発者は現在のハードウェア上で許容できる値の参考としてフレームあたりのステート変更数を約200としている《refer to》。

クエリのバッチ処理。この問題への我々の解法は、アルゴリズムによって要求されたときに即座にクエリを発行するのではなく、オクルージョンクエリをバッチ処理することに基づいている。レンダリングステートはバッチあたりに一度だけ変更されるため、ステート変更の削減は我々が発行するクエリのバッチサイズに直接的に対応する。そのバッチ処理のアルゴリズムは以下の節にて述べられるように個別に可視および不可視ノードを扱う。

4.1. 以前に不可視であったクエリのバッチ処理（Batching previously invisible queries）#

クエリされた不可視ノードは我々が ｜iキュー《i-queue》 と呼ぶキューに追加される。iキューの中のノードの数がユーザ定義のバッチサイズbに達したとき、我々はクエリのためにレンダリングステートを変更し、iキューの中のノードごとにオクルージョンクエリを発行する。(節5.1では、いくつかのノードがクエリ数を削減するために1つのオクルージョンクエリに組み合わせることができる方法を見ていこうと思う。)

バッチサイズbはレンダステートの変更の削減に｜強く結び付き《tightly connected》、CHCアルゴリズムよりおよそb倍少ないステート変更をもたらす。一方で、バッチ処理は不可視ノードに対するクエリ結果の可用性を実質的に遅延させている。これは可視性の変化が後に検出される可能性があり、十分な量の代替処理(例えば、可視ノードのレンダリング)が残されていない場合、それらによって｜生成された《spawned》追跡調査《follow-up》クエリが更なるレイテンシをもたらすだろう。

bに対する最適値はシーンのジオメトリ、マテリアルシェーダ、マテリアルソートに関するレンダリングエンジンの能力に依存する。我々のシーンおよびレンダリングエンジンでは、我々は、このパラメータの精密な調整が必要なく、20から80までの値がその手法に追加のレイテンシをもたらすことなくレンダステートの変更のほぼ十分な削減量をもたらすことに気がついた。

4.2. 以前に可視であったクエリのバッチ処理（Batching previously visible queries）#

CHCアルゴリズムは以前に可視であったノードに対するクエリを発行し、クエリの結果を待たずにノードのジオメトリをレンダリングすること｜思い出してほしい《recall》。CHCと同様に、我々の提案する手法はその階層を横断している間に以前に可視であったノードのジオメトリをレンダリングする。しかし、クエリは即座には発行されない。代わりに、対応するノードは我々が ｜vキュー《v-queue》 と呼ぶキューに格納される。

重要な所見《observation》は、これらの結果が次のフレームで使われるのみであろうという理由により、これらのノードに対するクエリが現在のフレームに不可欠《critical》ではない、ということである。我々は待ち時間を穴埋めするためにvキューからのノードを用いることによってこの所見を活用する。すなわち、横断キューが空であり、未解決クエリの結果が利用できないときはいつでも、我々はvキューからのノードを処理する。

結果として、我々は、未解決クエリのレイテンシによって駆動する、以前に可視であったノードに対するクエリの適応的バッチ処理を実行する。フレームの終わりに、以前に不可視であったノードに対するすべてのクエリが処理され終わったとき、その手法はvキューからのすべての処理されていないノードに対する単一の大きなバッチを適用するだけである。

vキューからのノードを処理する前に、我々はレンダステートの変更が必要とされているかどうかの確認も行うことに注意する。以前に発行された不可視ノードに対するクエリのバッチによってすでに変更されているために、ほとんどの場合でレンダリングステートを変更する必要は一切ないことが判明している。故に、我々は以前に可視であったノードに対するステート変更を基本的に取り除いた。

有益な副次的効果として、vキューは元のCHCアルゴリズムによって作られた前から後への順序の違反《violations》の効果を削減する。具体的には、以前に隠れていたノードが現在のフレームにおいて以前に可視であったノードを遮蔽する場合、以前に可視であったノードは以前に不可視であったノードがレンダリングされる前にしばしばクエリされるであろうために、この効果は次のフレームで捕捉されるのみだろう。この問題は多くの可視性の変化が同時に発生するような状況で明らかになる。vキューを用いてクエリを遅延させることはそのような可視性変化を検出され易くするだろう。

4.3. ゲームエンジン統合（Game engine integration）#

CHC++手法の既存のゲームエンジンへの簡単な統合のために、我々が レンダキュー《render queue》 と呼ぶ追加のキューをアルゴリズムで使用することを提案する。このキューはレンダリングのためにスケジューリングされたすべてのノードを累積し、クエリのバッチが発行される間近となるときに処理される。レンダキューを処理するとき、エンジンは内部のマテリアルシェーダソートを適用でき、そして、新しい順序でキューに格納されたオブジェクトをレンダリングする。レンダキューのもうひとつの有益な効果はエンジンAPI呼び出しの削減である。これらの呼び出しは非常にコストが高く、故に、これらの削減は、例えば、有名なOGREゲームエンジンで体験したような、大幅な高速化をもたらす。

（図3：CHC++アルゴリズムによって用いられる様々なキュー。CHCアルゴリズムによって用いられなかったキューは青色で強調される。）

CHC++アルゴリズムによって用いられる様々なキューの概要は図3に示される。クエリキューにおける｜重なり合った《overlaid》ノードは節5.1で述べられるであろうマルチクエリに対応する。

5. クエリ数の削減（Reducing the number of queries）#

最近のオンラインのオクルージョンカリング手法はそのオーバーヘッドを減らすためにオクルージョンクエリの数を削減することに焦点を当てていた。具体的に、 Guthe et al. [2006Guthe, M., Balázs, Á. and Klein, R. 2006. Near optimal hierarchical culling: Performance driven use of hardware occlusion queries. Symposium on rendering. 10.2312/EGWR/EGSR06/207-214. https://cg.cs.uni-bonn.de/backend/v1/files/publications/guthe-2006-neal-optimal.pdf.] の手法は費用便益のヒューリスティクスに基づくクエリの除去やグラフィクスハードウェアの較正されたモデルに対する洗練されたアプローチを提案した。この節では、我々はGuthe et al.によって最適であると以前に定義された仮説のアルゴリズム 以下《below》 にさえクエリ数を削減することができる2つの新しい手法を提案する。

5.1. 不可視ノードのためのマルチキュー（ Multiqueries for invisible nodes）#

過去の技術のすべてはテストされる以前に不可視であったプリミティブあたり1つのオクルージョンクエリを用いる(階層内のノード、境界ボリューム、グリッド内のセル)。これらのノードに対するオクルージョンクエリは削減できないと見なされた。

しかし、以下の所見は我々が以前に不可視であったノードに対してさえもクエリ数を削減することを可能にする。いくつかの以前に不可視であったシーンの部分が現在のフレームにおいて不可視のままである場合、その部分全体に対する単一のオクルージョンクエリはそれの可視性の状態を検証するのに十分である。そのようなクエリはこのシーンの部分にあるプリミティブのすべての境界ボックスをレンダリングし、プリミティブが遮蔽されたままであれば0を返すだろう。例えば、静的なシーンと静的な視点の極端なケースでは、単一のオクルージョンクエリがシーンのすべての不可視部分で用いられることができるかもしれない。

特定の可視性の一貫性を仮定すれば、我々の新しい技術は不可視のままである可能性が同等に高い以前に不可視であったノードのグループを形成することによってそのようなシーンの部分を識別することを目的としている。我々が マルチクエリ《multiquery》 と呼ぶ単一のオクルージョンクエリはそのようなグループごとに発行される。マルチクエリが0を返すならば、グループ中のすべてのノードは不可視のままであり、これらの状態は単一のクエリによって更新され続ける。そうでなければ、一貫性はこのグループに対して破壊されてしまい、我々はiキューにそれらを再挿入することですべてのノードに対する個々のクエリを発行する。最初のケースではクエリ数はグループ内のプリミティブ数によって削減されることに注意する。しかし、次のケースではバッチに対するマルチクエリが無駄になってしまう。

我々は適切なノードのグルーピングを見つけるために費用便益のヒューリスティクスに基づいた適応的メカニズムを用いる。計算の｜極めて重要な《crucial》部分は、次節で述べられる、ノードの可視性分類における一貫性の推定である。実際のヒューリスティクスは節5.1.2で述べたい。

5.1.1. 可視性の一貫性の推定（Estimating coherence of visibility）#

大多数の場合において、階層内のほとんどのノードに対する可視性には強い一貫性がある。我々の目的はこの一貫性を定量化することである。具体的には、与えられたノードの可視性の分類を知ることで、我々はこのノードが次のフレームにおいてその可視性の分類を維持するであろう確率を推定することを目指す。我々の実験はノードの”履歴《history》”、すなわち、ノードが同じ可視性の分類を維持したフレーム数とこの値に強い相関があることを示している(我々はこの値を 可視性持続度《visibility persistence》 と呼ぶ)。非常に長い時間の間に不可視であったノードは不可視であり続ける可能性が高い。そのようなノードは、例えば、カメラが車のエンジンの内部に移動しない限り見えることが一切ないであろう車のエンジンブロックであるかもしれない。それどころか《on the contrary》、低速移動のシナリオでさえ、分類を定期的に変化させる可視境界《visible border》上のいくつかのノードが常にある。それ故に、最近不可視になったノードがまもなく可視になる可能性は極めて高い。

我々は可視性持続度 $i$ の関数として望ましい確率を定義し、以前のノードの履歴に基づいてそれを近似する。

P_{keep}(i) \approx \frac{n_{i}^{keep}}{n_{i}^{all}} \tag{1}

ここで、 $n_{i}^{keep}$ は、 $i$ フレームの間に同じ状態にあり続け、 $i+1$ 番目のフレームでこれらの状態を維持する、すでにテストされたノード数であり、 $n_{i}^{all}$ は、 $i$ フレームの間同じ状態にあり続けた、すでにテストされたノードの総数である。図4は可視性持続度 $i$ に対する確率 $p_{keep}$ のプロットを示す。計数《counters》 $n_{i}^{keep}$ と $n_{i}^{all}$ はウォークスルーのすべての前のフレーム上で累積される。

最初の数フレームでは、 $i$ の値が大きいと特に、 $p_{keep}(i)$ の正確な計算のための計測値が足りない。我々は $p_{keep}(i)$ のより高い値へのすでに計算された値の区分定数伝播《piecewise constant propagation》によってこの問題を解決する。

計測によって $p_{keep}(i)$ を計算するより単純な代替法として、我々は我々のシーンやウォークスルーで計測した関数にかなり《reasonably》上手く対応する解析的な式を提案する。

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

この関数の使用は計測された関数と同様に正確な $p_{keep}$ の推定値をもたらさないが、測定された関数の計算を実装することを回避するのに使うことができる。図4は2つの異なるシーンに対する解析的な関数と計測された関数を図示する。

（図4：可視性持続度 $i$ に依存する $p_{keep}(i)$ 。式2からの解析的な関数はPowerplantとViennaのシーンで計測した関数とほぼ一致することに注意する。）

5.1.2. マルチクエリに対する費用便益モデル（Cost/benefit model for multiqueries）#

与えられたバッチ(すなわち、iキュー)における以前に不可視であったノードに対するマルチクエリの最適なサイズを定めることは、マルチクエリへのバッチ分割の取り得るすべてを計算する必要がある、大局的な最適化問題である。代わりに、我々はマルチクエリごとに費用便益の比を最大化する貪欲なモデルを用いる。

そのコストはマルチクエリ1つあたりに発行されるクエリ数の期待値であり、以下で表される。

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

ここで、 $p_{fail}(M)$ はマルチクエリが失敗する確率であり(可視を返し、この場合、すべてのノードが個々にテストされなければならない)、 $|M|$ はマルチクエリ内のノード数である。定数 $1$ はマルチクエリそれ自体のコストを表しているのに対し、 $p_{fail}(M) * |M|$ は個々のノードに対して追加で発行されるクエリ数の期待値を説明していることに注意する。確率 $p_{fail}$ は以下のようにマルチクエリにおけるノードの可視性持続度の値 $i_N$ から計算される。

p_{fail}(M) = 1 - \prod_{\forall N \in M} p_{keep}(i_N) \tag{4}

マルチクエリの利点は単純にマルチクエリにおけるノード数、すなわち、 $B(M) = |M|$ である。

iキューにおけるノードを仮定するならば、貪欲な最適化アルゴリズムは与えられたコストでの利益を最大化する。我々はまず不可視であり続ける確率、すなわち、 $p_{keep}(i_N)$ に基づいて降順にノードをソートする。その後、キューにおける最初のノードを皮切りに、我々はマルチクエリにノードを追加し、各工程で、費用便益の比としてマルチクエリの値 $V$ を計算する。

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

$V$ は特定の $M_j$ に対して最大値に達し、故に、 $j$ はiキューの先頭にあるノードに対するマルチクエリの最適なサイズに対応することが判明している。ひとたびこの最大値を発見すれば、我々は対応するノードに対するマルチクエリを発行し、iキューが使い果たされるまでその処理を繰り返す。結果として、我々は不可視であり続ける確率の高いノードに対するマルチクエリをより大きく、可視に転ずる可能性の高いノードに対するマルチクエリをより小さくコンパイルする。

5.2. 可視ノードのテストの省略（Skipping tests of visible nodes）#

元のCHCアルゴリズムは以前に可視であったノード上のクエリ数を削減するための重要な最適化を導入した。可視ノードは $n_{av}$ フレームの間に可視であり続けると仮定され、フレーム $n_{av}+1$ においてテストされるのみであろう。この最適化は以前に可視であったリーフに対する平均クエリ数を $n_{av}+1$ 倍に実質的に削減する。

しかし、この単純な手法はクエリが｜時間的に整列し得る《can be temporally aligned》という問題を持つ。このクエリの整列《alignment》はノードが同じフレームにおいて可視になりがちな状況において問題となる。例えば、多くのノードを同じフレームで可視にしてしまうような、典型的な街のシーンにおいて｜地面の高さ《ground level》から｜屋根の高さ《roof level》以上に視点が移動する場合が考えられる。その後、これらのノードのクエリは $n_{av}+1$ 番目のフレームでスケジューリングされ、故に、クエリのほとんどは再び整列するだろう。フレームあたりの平均クエリ数は依然として削減されるだろうが、その整列は｜目に付く《observable》フレームレートドロップを引き起こし得る。

我々は小さな乱数 $-r_{max} < r < r_{max}$ による $n_{av}+1$ の無作為化が満足のいくやり方で問題を解決しないことに気付いた。その問題は、無作為化が小さい場合、クエリが依然として｜非常に《very much》整列しているかもしれない、ということである。対して、無作為化が大きい場合、クエリの幾つかを処理するのが遅すぎてしまい、故に、可視状態から不可視状態への変化を捕捉するのが遅すぎてしまうだろう。

我々は最も満足のいく解法がオクルージョンクエリの ｜初回の呼び出し《first invocation》 を無作為化することで達成されることを発見した。ノードが可視に転じた後、我々はクエリが発行されるであろう次のフレームを決定するために乱数 $0 < r < n_{av}$ を用いる。続けて、そのノードが以前のテストですでに可視であった場合、我々は $n_{av}$ によって与えられる通常のサンプリング間隔《interval》を用いる。

我々は様々な $n_{av}$ の値で実験を行った。その最適値はシーンそれ自体、｜検査の一貫性《inspection coherence》、ハードウェアのパラメータ、および、レンダリングエンジンのパラメータに依存する。幸いにも、我々のテストはその依存性がそれほど強くなく、5から10の値がすべてのテストで安全かつ堅牢な選択であったことを示している。

6. よりタイトな境界ボリューム（Tighter bounding volumes）#

オクルージョンクエリによってもたらされるオーバーヘッドとは別に、カリングアルゴリズムの成功は空間的階層における境界ボリュームがどれだけタイトに含まれるジオメトリを近似するかに強く依存する。その合致《fit》が十分にタイトでないならば、多くのノードはたとえ含まれるジオメトリが可視でないとしても可視として分類されるだろう。タイトな境界ボリュームを得るための技術はいくつかあり、ほとんどはより複合的な形状で軸並行な境界ボックスを置き換えることによってなされる。これらの手法はほとんどのオクルージョンカリングアルゴリズムに直接的に適用できるだろうが、一方で、これらもまたボリュームの計算と維持のオーバーヘッドを｜成す《constitute》。これは特に動的なシーンで高価となり得る。

我々は任意の境界ボリューム階層に適用されるハードウェアオクルージョンクエリの観点において ｜内部ノード《inner nodes》 に対するタイトな境界を定める単純な手法を提案する。特定のノードに対して、我々は特定の深さでのその子供の境界ボリュームの集まりとしてその ｜タイトな境界ボリューム《tight bounding volume》 を定める(図5を参照)。

（図5：球として示されるオブジェクトをより｜ピッタリと《closely》表現するBVHのノードに対するタイトな境界ボリューム。タイトな境界ボリュームは親のボックス(白)ではなく子供の境界ボックス(赤)から成る。）

境界ボリュームのジオメトリをレンダリングするための最新のAPIを用いるとき(例えば、OpenGLのVertex Buffer Objects)、オクルージョンクエリに対するよりわずかに複合的なジオメトリは実践的にそのオーバーヘッドを増加させないことが判明している。しかし、より小さな境界プリミティブがスクリーン空間において重なるときにタイトな境界ボリュームをラスタライズするためのペナルティがあるかもしれず、故に、オリジナルのノードの境界ボリュームの投影と比べてフィルレートを増加させる。そのようなケースを回避するため、我々はよりタイトな境界の有用性を保証するための単純なテストを用いる。タイトな境界ボリュームのために子ノードを集めるとき、我々は子供の境界ボリュームの表面積の合計が $s_{max}$ ×親ノードの表面積より大きくないかどうかをテストする(これは特定の視点に依存しないことに注意)。これが正しいならば、我々は横断を終了し、境界表現をこれ以上に精錬しない。我々はノードからの深さが指定された最大の深さ $d_{max}$ より大きいかどうかによって境界ボリュームの探索を終了する。以下の値は我々のテストにおいて良い結果をもたらした: $d_{max} = 3, s_{max} = 1.4$ 。

タイトな境界ボリュームを定めることは階層のリーフに対しても有利であることに注意する。これはよりわずかに深い階層を構築し、｜仮想リーフ《virtual leaves》 として指定された数より少ないトライアングルを含む階層の内部ノード、すなわち、横断中にリーフと見なされる内部ノードを作ることによって容易に達成できる。

結果として、タイトな境界ボリュームはほぼコストなしでいくつかの利点をもたらす。(1)階層の内部ノードの早期《earlier》カリング、(2)可視として｜別途分類される《otherwise be classified》であろうリーフのカリング、(3)内部ノードの可視性分類の一貫性の増加。第1の特性はクエリ数の削減を引き起こす。第2の特性はレンダリングされるトライアングル数の削減をもたらす。最後に、第3の利点は繰り返される可視性の｜引き上げ《pull-up》と｜引き下げ《pull-down》によって引き起こされる内部ノードに対する可視性分類における変化を回避する。

7. まとめ上げ（utting it all together）#

CHC++アルゴリズムは、いくつかの重要な追加要素《add-ons》を含めて、CHCアルゴリズムの単純さを維持することを目的としている。この節では、我々は完全なCHC++アルゴリズムを要約し、CHCアルゴリズムとのその主な差異を強調する。CHC++アルゴリズムの擬似コードは図6に示される。

（図6：CHC++の主な横断ループの擬似コードと抜粋された重要な関数。オリジナルのCHCとの差異は青色で印を付けている。）

CHCにあるように、我々は階層を横断するために｜優先度付きキュー《priority queue》を用いる。このキューは処理されるノードの前から後への順序をもたらす。CHCと異なり、新しいアルゴリズムはクエリされるべきノードを格納するための2つの新しいキューを用いる(vキューとiキュー)。これらの2つのキューはレンダリングステートの変更を削減したりマルチクエリをコンパイルしたりするための鍵である。

以前に可視であったノードはCHCの場合と同様に即座にレンダリングされる。これらは現在のフレームにおけるテストのためにスケジューリングされる場合、vキューに配置される。クエリをスケジューリングするためのアルゴリズムは、クエリ数を削減し、フレーム全体で均等に分布させるため、すでに｜論じた《discussed》時間的にジッタリングされたサンプリングパターンを用いる。vキューに格納されるノードに対するクエリはそれが発生する必要がある場合に待ち時間を埋めるために用いられる。フレームの終わりで、vキューにある残りのノードはクエリの単一バッチを形成する。

iキューは前のフレームにおいて不可視であり続けている処理されたノードを累積する。そのキューの中に十分な数のノードがあるとき、我々は、それらをマルチクエリにコンパイルしつつ、iキューにあるノードに対するオクルージョンクエリのバッチを適用する。

ゲームエンジンにその手法を統合するとき、可視ノードはまずレンダキューに累積される。そして、レンダキューは、iキューからのクエリのバッチがまさに発行されるようとする前に、エンジンによって処理される。