Decima Engine: Visibility in Horizon Zero Dawn

はじめに（INTRODUCTION）

背景（BACKGROUND）

既存のシステム --- モデル（Existing system - Models）

• 我々のモデルデータはMeshResourceによって表現される
  • 実際には他のMeshResourceの｜任意のツリー《arbitrary tree》
  • LOD切り替えとマルチメッシュの内部ノード
  • プリミティブデータを持つ静的、および、スキンメッシュのリーフノード

ゲームで見られるような3Dモデルは任意に複雑にできるMeshResourceのツリーである。異なるブランチの間を選択するLODメッシュ、ルートを基準にブランチを配置するためのマルチメッシュを持つ。そして、リーフには、ジオメトリを含む静的メッシュを持つ。他のリーフノードタイプもあるが、このトークと関係はない。

これは、様々なコンテンツワークフローを構築するのに効果的である、とても柔軟なシステムだが、最適化するときに一般的な挙動を見極め、抽出することをより難しくしている。

既存のシステム --- インスタンス（Existing system - Instances）

• メッシュはDrawableObjectとしてワールドに配置される
  • 各々は自身のMeshInstanceTreeを持つ
  • 効率の良い平坦な形式でリソースツリーをエンコードする
• MeshInstanceTreeリーフノードはDrawableSetupを含む
  • プリミティブジオメトリ（頂点＆インデックス配列）
  • シェーダとレンダリングオプション
  • ローカルからワールドへの変換
• DrawableObjectのKdツリーは空間的な階層を提供する

DrawableObjectとしてワールドにメッシュリソースのインスタンスを配置する。これらはランタイムで使われるMeshResourceツリーのより効率的なエンコーディングを持つ。

ある特有の問題はメッシュリソースがツリーのルートであるかを認識していないことであり、これはDrawableObjectによって配置されるときのみ明確になる。

このツリーのリーフノードはDrawableSetupを含み、これをレンダラに食わせる。各々はレンダリングするのに必要なシェーダを持つジオメトリのチャンクである。これらはコンテンツの残りからレンダラを隔離する。

既存のシステム --- クエリ（Existing system - Queries）

• ｜可視《visible》のDrawableObjectを見つける
  • Kdツリーを歩く
  • 各DrawableObjectを錐台カリングする
• 可視のDrawableSetupを見つける
  • それぞれの可視DrawableObjectのMeshInstanceTreeを歩く
  • 関連するLODに｜降りる《descend》
  • 各DrawableSetupを錐台カリングする
• 可視DrawableSetupのリストをレンダラに出力する

KZ3では、PS3のSPUでソフトウェアオクルージョンカリングを用いて各オブジェクトとセットアップをカリングしていた。

KZ4では、静的コンテンツには遮蔽を含めたすべての可視性を扱うミドルウェアを用いた。

既存のシステム --- クエリ（Existing system - Queries）

• すべてのジオメトリに対して同じシステム
  • 静的も動的も同じ方法で取り扱う
• フレームごとに2つ以上のクエリを実行する
  • プレイヤーカメラ（｜透視投影《perspective》）
  • 太陽光シャドウマップ（｜正投影《orthographic》）
  • 他のシャドウマップ（透視投影、小さめの錐台）

クエリはCPUジョブであり、これは一般的なレンダリングジョブグラフの一部である。CPUには柔軟なジョブアーキテクチャがある --- ほとんどのコード（とすべてのレンダリングコード）はジョブで実行する。

既存のシステム --- 問題（Existing system - Problems）

• いくつかのスケーリングの問題が存在することが分かった
  • Kdツリーの再構築は高コスト
  • MeshInstanceTreeのクエリは高コスト
    • 並列ジョブにも関わらず
    • 大きかったり小さかったりするツリーが混ざりあったアンバランスなジョブ
    • それでも、Kdツリーのクエリは比較的高速
  • APIは少なく大きなオブジェクトに狙いを付けていた
    • ｜構成要素《building blocks》には大量の小さなオブジェクトがある
    • インターフェースのオーバーヘッド（主にロック処理による）

このシステムはHorizonのワールドサイズにはあまり良いとは言えず、しばしばコンテンツがストリーミングされるたびにKdツリーを再構築していたので、その複雑さを減らす必要があり、また、MeshInstanceTreeクエリが高価だったので、それをより少なくしたかった。

シーンAPIが実際には少なく大きなオブジェクトに狙いを定めており、Horizonのワールドを生成する構成要素には大量の極小オブジェクトがある、という問題もあった。

新システム（NEW SYSTEM）

基本的な目標（Basic goals）

• オフライン事前計算なし
  • マジで、なし
• 既存のコンテンツをサポートする
• KZ4よりはるかに多くのコンテンツを扱う
• KZ4よりクエリ時間を短縮する
  • クエリはすべてのレンダリングでクリティカルパスである

KZ4には可視性ミドルウェアがあったが、これは可視性データを事前計算する必要があり、単に我々がやっていた方法に合わなかったため、ワークフローの問題を引き起こした。変更を適切にテストするのに必要な時間が増加した --- それなしにゲームを始めることもできたが、アーティストは、あるべき姿としてモノを確認できるようになるまで、ベイク処理がバックグラウンドで終了するのを待たなければならなかった。我々は依然としてこれでゲームを出荷していたが、Horizonにそれを合わせられるとは考えなかった。

事前計算のアイデアを諦めることはとても難しいと分かっていたが、それは自由をもたらす --- もしベイク処理を待たなくて良いとしたら、同じくらい素早くコードの変更をテストできる。

明らかに、新しいコンテンツを、より高速に扱う必要があった。

新システム --- StaticScene（New system - StaticScene）

• 静的データのみを扱う
  • 動的データより静的データのほうがはるかに多い
  • 既存のシステムは動的データでうまく動作する
  • 物事を過度に複雑にしない
  • 並列に両方のジョブを動作させる
• 非同期コンピュートハードウェアを使う
  • レンダリングではなくCPUと同期する
  • 我々が熟知し愛好した、PS3のSPU同期のようなもの

既存の多目的システムの負荷を軽減するために単目的システムを構築した。StaticSceneは、それが大量にあるということから、静的なジオメトリのみを扱う。

既存のシステムは残りの動的なジオメトリを扱うために使用でき、そのジョブは並列に実行することができた。

コンテンツの量をより上手に扱えたり、CPUと同期するのが比較的簡単になったりするだろうと考えたので、PS4の非同期コンピュート能力を使うことも目標とした。

入力の制約（Input constraints）

• ほとんどの静的リソースツリーはこのようになっている
  • 高LOD: 構成要素のリスト、アーティストによって配置される
  • 低LOD: 構成要素からツールが生成した｜潰れた《collapsed》ジオメトリ

（画像）

計算を行うために比較的平坦なデータを送り込みたかったので、我々は複雑なMeshResourceツリーに制約を課さねばならなかった。

静的なリソースの多くは、1つ以上の構成要素のLODとエクスポートツールによって生成された潰れたジオメトリのLODとの間を選択するトップレベルのLodMeshResourceを持っている、ように見えたことが判明している。構成要素それ自体はLODノードを持つが、潰れたジオメトリでは、これは単純化されている。

入力の制約（Input constraints）

• このツリーをより均一な何かに平坦化したい
  • コンピュートに食わせるために
• 2つのLODレベルとして完全に表現できる
  • これらを親と子と呼ぶ
  • バウンディングボックスとLOD距離の$[\min, \max)$
  • リーフは親と子の両方のLODが選択された場合のみ可視である
  • ツリーが2つのLODレベルを持っていない場合、“｜常に有効《always on》”なレベルで｜埋める《pad》
    • ｜特例《special cases》はない
• ｜はずれ値《outlier》コンテンツは動的の方に移される
  • 古いシステム内でうまく動作する
  • アーティストは時間をかけてそれを取り除くためにワークフローを調整した

重要な所見は、LODレベルが2つあればこれらのツリーを表現するのに十分であることだった。これらは親や子と呼ばれ、LodMeshResourceの境界とブランチのひとつに対するLOD｜区間《bracket》を持つ。

リーフは親と子のLOD両方が選択された場合に限り可視である。

特殊なケースを避けるため、“空”のLODレベルを追加する。なので、すべてが2つ持つことになる。

これに合わないコンテンツは動的システムに移され、アーティストは時間をかけてそれを取り除いた。

高レベル構造: StaticTile（High level structure: StaticTile）

• ワールドをタイルに分割する
  • 空間的にではなく、ストリーミンググループによって定義される
  • いくつかのグループは本当に空間的なタイルである
  • その他は｜村落《settlements》や｜遭遇《encounters》のようなモノをグループ化する
• 一度生成されれば、タイルは不変である
  • 動的な更新は物事を複雑化するだろう
  • 変更するには破棄して再生成する

このすべてのデータを選別するため、空間的な構造を必要とした。トップレベルでは、ワールドをStaticTileに分割する。これは時に真の空間的なタイルであり、時に｜人が住む場所《settlements》や｜敵と戦う場所《encounters》のような他のものである。これらはストリーミングシステムによって定義され、StaticSceneを選ばせない。

タイルは不変として生成され、物事を単純化するために、更新できないようになっている。

高レベルデータ: タイルコンテンツ（High level data: Tile contents）

• GPUバッファ
  • QueryObject （DrawableObjectを表現）
  • QuerySetup （DrawableSetupを表現）
  • QueryInstance （QueryObjectひとつとQuerySetupひとつを接続する）
    • コンピュートスレッドに一対一対応する
    • 行列＆バウンディングボックス
      • インスタンスから間接的に読み出される
• CPUクラスタ
  • 境界とLODを持つインスタンスの空間的に一貫性のある範囲

タイルはほぼ平坦なGPUデータのバッファであり、第一パスのカリングのためにCPU上で使われるクラスタのリストを持つ。

低レベルデータ: QueryInstance（Low level data: QueryInstance）

: QueryInstance

• ほぼ数値データ
  • 従って、積極的なパッキング
• フィルタはインスタンスの高速な排除ができる
  • 例えば、シャドウキャスターだけを選択するために
  • または、可視メッシュだけ
  • これ以上のデータを読み込む必要はない
• 間接読み込みのために使われるインデックス
  • 行列（48バイト、floatの4x3行列）
  • 境界（12バイト、half精度のAABB）

Horizonを出荷して以来、バッチレンダリングをサポートするための変更を作っていた。これについては後に話したい。新旧両方を網羅する時間があるとは思えなかったので、ここに記述するデータフォーマットは新しい方のものである。手短に言えば、以前は、各DrawableSetupがそれ自身のローカルからオブジェクトへの空間の変換を持っていたので、より小さなQueryInstanceとより大きなQuerySetupを使っていた。バッチ処理のために、DrawableSetupから変換を取り除き、代わりにMeshResourceTreeにあるDrawableSetupの位置を使って、ローカルからオブジェクトへの変換を定義する。

スペースを節約するため、QueryInstance以外のすべての要素はハッシュ化され、インデックスで検索されるインスタンスと一緒に、1タイルあたり厳密に一度だけ格納される。繰り返すが、これは出荷後の変更である。

データは、ほとんどがインデックスで、可視メッシュや様々なシャドウキャスターの種類を示すフィルタビットや、インスタンスが入っているリーフのための親と子のLOD範囲がある。

｜現状では《as it stands now》、成長の余地は残っていない！

低レベルデータ: QuerySetup/QueryObject（Low level data: QuerySetup/QueryObject）

: QueryObject

: QuerySetup

• 両方が1タイルあたり厳密に一度だけ格納される
  • パッキングはそれほど重要じゃない
• レンダラはカメラに関連する｜浮動空間《floating space》を用いる
  • ｜スナップされた《snapped》オブジェクトの整数位置を格納する
  • それに関するobject-to-snappedの行列
  • object-to-floatingを構築して出力する
    • 原点から遠い所の精度を維持する
• Setupはジオメトリの正確な頂点境界を持つ
  • LOD境界は常に｜過推定《overestimate》である
  • LODをまたいで集められ、オブジェクト空間で格納される

各々のユニークなQuerySetupとQueryObjectは1タイル当たり一度だけ格納される。なので、これらの構造をパッキングすることは重要ではない。

ゲームワールドは高精度な座標系を使い、原点から離れるほど浮動小数点の精度が欠落することで引き起こされる問題を回避する。そして、そのレンダラはカメラに従う浮動空間で動作する。1m整数グリッドに基づく高精度のオブジェクト変換処理を通過し、クエリシェーダはスナップされたカメラ原点を減算して、レンダラへ浮動空間の変換を出力する。

QuerySetupは錐台カリングで用いる正確なローカル境界情報を持つ。LOD境界を用いることもできるが、これらは常に過推定である。

タイル構築: 読み込み（Building tiles: Loading）

• ストリーミングスレッドでは、
  • 変更が大きい場合、複数のStaticTileへ分けて追加する
  • 変更が小さい場合、“｜孤児《orphan》”タイルへオブジェクトを追加する
  • 一連の追加/除去を一致させるので、タイル全体を除去する（孤児を除く）
  • 負荷バランシング＆スケーリングのために｜矛盾のない《consistent》タイルサイズを得ることを目指す
  • 空間的な分割を生成し、バッファを埋める
• メインスレッドでは、
  • 単に準備のできたタイルをアクティブにする
  • ｜困難な仕事《heavy lifting》なし --- ストリーミングヒッチを回避する

我々のストリーミングシステムは、ローティングが数フレームをかけて起こる可能性があるので、バックグラウンドスレッドでオブジェクトをロードおよびアンロードする。StaticSceneは追加されるオブジェクトと除去されるオブジェクトのセットを受け取り、部分アンロードを扱わなくて良いように追加と除去が一致していることを保証した。

一般には、追加されるオブジェクトのグループは単一のStaticTileを生成するが、タイルは大量のQueryInstance（24K以上）を持つかもしれないなら、それを分割する。同様に、非常に少ない（1K以下）場合、これらを特別な”孤児”タイルに追加する。

すべての困難な仕事（空間分割、メモリ割り当て、など）はストリーミングスレッドで発生し、メインスレッドは単にタイルが利用可能になるときにそれをアクティブにすればいいだけである。

タイル構築: 空間分割（Building tiles: Spatial partition）

• 分割の第一レベルとしてタイルを使う
  • 一般的にはすでに空間的に一貫性がある
• 各タイル内に｜更なる空間分割《spatial+ partition》を生成する
  • フィルタ、LOD範囲、｜モートン数《Morton number》でインスタンスをソートする
  • フィルタはCPUでクラスタ全体のリジェクションを可能にする
  • LOD範囲は、例えば｜詳細で密な領域《detailed dense area》に対して、同じことを行う
  • モートン数は合理的な空間的一貫性を与える
• ソートキーはクラスタを定義する
  • 最小サイズと一緒に
  • クラスタはコンピュートジョブと1対1対応する

データを分解するために空間分割が必要であり、このための｜いくつかのレベル《a couple of levels》がある。StaticTileは、一般的にはすでに一貫性があるので、第一レベルを提供する。そして、クラスタを定義するためにタイル内に部分的に空間分割を生成する。

フィルタビット、最大LOD範囲、モートン数を用いて各QueryInstanceごとにソートキーを生成する。フィルタはクエリに関係のないクラスタを素早く破棄することができ、LOD範囲はコンテンツの｜密な領域《dense area》に対して似たようなことを行う。これの下に、モートン数は｜ある程度《a degree of》の空間的一貫性を与える。

ソート後、負荷バランシングの役に立つよう再び4K個のインスタンスの最小サイズでクラスタを定義するためにソートキーを変更する。各クラスタは潜在的にコンピュートジョブである。

余談: モートン数¹（Aside: Morton numbers）

• 単純だが役に立つ概念
  • 位置を整数に量子化する
  • ビットバイビットで要素をインターリーブする
  • N次元の点から1DのZ階数曲線を生成する
  • 3Dでは、八分木を構築するのと等価である
• モートン数は近い？
  • 位置は（ほぼ）近い
  • ｜逆もまた然り《vice-versa》
• ビットトリックでかなり素早く計算できる
  • 各成分のビットを2ビット間隔でバラして配置する《Spread bits of each component by two》
• 素早く汚い空間的構造に対して役立つ
  • Hilbert曲線はより良い局所性を持つが、計算コストがより高い

Guy Macdonald Mortonにより導入されたモートン数はN次元の座標と1次元の数値とをマッピングする方法である。

位置をいくつかの整数グリッドに量子化することに始まり、単一の数値を生み出すためにビットバイビットで要素をインターリーブする。3Dにおいて、これは八分木を構成するのと似ており、モートン数の増加は図のひとつのようなZ階数曲線に従う。

これらはビットトリックによりとても計算しやすく、モートン数同士が近ければ、位置同士も一般的に近い。そのため、素早く汚い空間的構造に対して役立つ。使える曲線には、Hilbert曲線のような、より良いがより高価なものがある。

クエリのためのCPUジョブ（CPU job for query）

• 静的クエリあたりひとつのCPUジョブを実行する
  • ジョブグラフ全体の可視性クエリに対する部分
  • 動的クエリに対する既存のCPUジョブと一緒に並列に
• CPUでタイルとクラスタの可視性をテストする
• 可視クラスタごとにひとつのコンピュートジョブをキックする
• CPUジョブはGPUジョブを待つ

データを構築したら、クエリを実行したいので、古いシステムのようにレンダジョブグラフ内でこれを行うためのCPUジョブを生成する。これは動的クエリジョブをと一緒に並列に実行できるので、レイテンシーは増加しない。

できるだけ多くのクラスタをスキップするためにタイルとクラスタの階層を用いて、可視クラスタごとにひとつのコンピュートジョブをディスパッチする。そして、CPUジョブはコンピュートの終了を待つ。これは素晴らしく、単純であり、CPUジョブスケジューラに混在するジョブタイプを同期させることを回避する。

通常、このように結果を待つとき、｜空回り《idling》を避けるためにスケジューラからより多くの処理を選び取っていたが、この待機は一般に長くないし、何よりレイテンシーを最小にするのが大事なので、今回のケースではしないことにした。

クラスタのGPUコンピュートジョブ（GPU compute job for cluster）

• いくつかのコンパイル時特殊化を伴うuberシェーダ
  • シャドウクエリと可視クエリは様々なオプションを持つ
  • コードサイズを減らした”｜ファストパス《fast path》”シェーダをいくつかコンパイルする
  • ファストパスから外れていないことを確実にする…

ディスパッチするGPUジョブは少量《a handful of》のコンパイル時バリエーションへ特殊化される単一のuberシェーダを使う。これらすべては汎用シェーダと比べて命令数やレジスタ数を削減してあり、GPUコンピュート単位が一度により多くのwavefrontを実行するのに役立つ。

クエリオプションがデフォルト設定から切り替えられているとき、汎用シェーダのみを使う。これはデバッグ専用のものである。

このシェーダはとても長く、最長の場合で約1500命令ある。

GPUコンピュートスレッド: 入力とテスト（GPU compute thread: Input and tests）

• QueryInstanceを読み込み、フィルタをテストする
  • 選択されていなければ、早期に脱出する
• コンテンツ（行列、境界、など）を読み込む
• 親のワールド境界を計算して、LODをテストする
  • 選択されていなければ、可視性テストをスキップする
• 子のワールド境界を計算して、LODをテストする
• 正確なローカル境界を読み込んで、可視性をテストする
  • 錐台
  • サイズのしきい値
  • オクルージョンカリング

コンピュートジョブ内では、各スレッドはQueryInstanceを読み込み、すべての処理をスキップできるかどうかを確認するためにフィルタビットをテストする。

そうでなければ先に進み、LODと可視性のテストを行うために境界と行列を間接的に読み込む。少なくとも親のLODテストが合格すれば、子のLODテストと正確な可視性テストの両方を行う。これらの結果はLODフェード状態を更新するのに必要となる。

この時点でメッシュストリーミングの利用可能性もチェックする --- 頂点およびインデックスのデータが｜流出《streamed out》²していれば、オブジェクトを描画できない。

GPUコンピュートスレッド: 出力（GPU compute thread: Output）

• LODフェード状態を読み込み、更新し、格納する
  • プレイヤーカメラクエリに対してのみ
  • 更新するためにLODと錐台の可視性を必要とする
• フェードアウトした（または、見えない、シャドウ用の）場合、スキップする
• 出力バッファにスペースを割り当てる
  • ひとつのクエリに対してすべてのスレッド/ジョブで共有する
  • ｜集約的アトミック《aggregated atomics》とグローバルカウンタを用いる
• DrawableSetupのポインタと変換を書き込む

一度テストが完了すれば、その結果と以前のフレームの値を用いてLODフェード状態を更新できる。これは現時点ではプレイヤーカメラクエリでしか起こらない。

インスタンスが見えない場合は取りやめ、そうでなければ、出力バッファにスペースを割り当てる。これはそのクエリ内ですべてのジョブやスレッドによって共有されるので、アトミックに更新されるグローバルカウンタを用いてアクセスを同期しなければならない。

アドレスがあれば、各スレッドはDrawableSetupと変換を出力バッファに書き込むことができる。

余談: 抜粋コンピュート用語（Aside: Some compute terminology）

• Wavefront
  • ｜足並みをそろえて《lock-step》実行するスレッドの不可視ブロック（PS4では64スレッド）
• LDS
  • Local Data Store --- wavefrontのスレッドで共有される高速なメモリ
• VGPR
  • Vector General Purpose Registerの略で、wavefrontでスレッドあたりひとつの値を持つ
• SGPR
  • Scalar General Purpose Registerの略で、wavefront全体でひとつの値を持つ
• ｜ベクタレーン《vector lane》
  • ベクタレジスタの一要素
• Ballot（述語）
  • （述語）が真であるアクティブスレッドのビットマスク（PS4では64ビット）
• ｜アトミック《atomic》
  • 他のスレッドに割り込まれないメモリ処理

余談: Aggregated atomics（Aside: Aggregated atomics）

• コンピュートスレッドはしばしばグローバルなアトミックを使いたくなる
  • 例えば、バッファに追記したり、モノを数えたりするため
• wavefrontをまたいでこれらを集計するのが便利
  • スレッドあたりひとつではなくwavefrontあたりひとつのアトミック
  • メモリトラフィックを節約する
  • 加えて、wavefront内に固定されたアペンド順を与える
• 既存のアトミックに対する｜差し込み式《drop-in》置き換え
• さらなる情報は、Adinets2014を参照

アトミック処理はwavefrontのスレッドをまたいで集計される。これはスレッドあたりひとつのアトミックを使うのではなくwavefrontあたりひとつを使うことを意味する。

これは大量のメモリトラフィックを節約する。そして、標準のアトミックに対する｜差し込み式《drop-in》の置き換えである。

余談: Aggregated atomics（Aside: Aggregated atomics）

（画像）

• アクティブスレッドはそれぞれ、追加するためのカウンタを用いて、共有された出力へアイテムを書き込みたい
• アクティブスレッドのビットマスク（スカラ）
• アクティブビットのprefix sum $n$（ベクトル）
• アクティブスレッドのビットマスク数（スカラ）
• 第1アクティブスレッドはグローバルアトミックを処理する
• 以前のカウンタの値$m$をすべてのスレッドに頒布する
• 各スレッドはアドレス$m + n$に書き込む

このダイアグラムでは、箱の行は単一の単純化された8スレッドのwavefront内のスレッドを示しており、コンテンツは処理の特定の段階でスレッドが見ているものを示している。そして、各列は単一のスレッドでの値を表す。これは、各スレッドがここに示された行ごとにひとつではなく、いつでも生きているレジスタをいくつか持っているので、明らかに単純化されている。

右側の角の丸い箱はGPUメモリ中の他の場所にあるグローバルバッファを示す。これはこのwavefrontやその他で同時に処理される。

出力バッファに書き込みたいアクティブスレッド（色付きの箱）から始まる。

ballot()を用いてアクティブスレッドのビッドマスクを生成する。これはスカラ値、すなわち、各スレッドで同じ値である。

すべてのビット値を問題のスレッドの左側へ足し合わせることで、ビットマスク上のprefix sumを生成する。これはご覧の通り各スレッドで異なる。

最後に、ビットマスク内のビットを合計する。これは再びスカラである。

第1スレッドを選択し、グローバルアトミックを処理させ、グローバルカウンタの値へビットの合計を足す。

もとの値を取り戻し、各スレッドに頒布する。そして、各スレッドはprefix sumを足し、そのアドレスに書き込む。ご覧の通り書き込みはコンパクトであり、prefix sumで順番付けされている。

余談: Aggregated atomics（Aside: Aggregated atomics）

// 現在どのスレッドがアクティブか？これはスカラ、すなわち、wavefront全体で同じである
ulong active_mask = ballot(true);

// このスレッドのIDが一番小さいアクティブIDであるなら、これは第1アクティブスレッドである
uint wavefront_old_value;
if (ReadFirstLane(thread_id_in_wavefront) == thread_id_in_wavefront) {
    // wavefrontに対するトータルの増分を得るためにスカラマスク内のビットを数える
    uint increment = popcnt(active_mask);

    // グローバルアトミック加算を処理して、もとの値を回収する
    OutputBuffer.AtomicAdd(address, increment, wavefrint_old_value);
}

// 第1アクティブスレッドから初めにアクティブだったスレッドへもとの値を頒布する
wavefrint_old_value = ReadFirstLane(wavefrint_old_value);

// 各スレッドの値を得るために、prefix sumを加える。これは書き込み先アドレスとして通常使われる
uint thread_value = wavefront_old_value + MaskBitCnt(active_mask);

そして、ここにそのためのコードがある。ballot(true)はアクティブスレッドのマスクを得る。

現在のスレッドのIDとそのIDに対する第1アクティブスレッドの値とを比較することで第1アクティブスレッドを選択する。

第1スレッドはマスク中のビットを数え、グローバルカウンタに加える。

その後、各スレッドは第1アクティブスレッドの結果を回収して、最後に、自身のカウンターの値を得るためにprefix sumを加える。

最近の仕事（LATEST WORK）

クエリ中のバッチ処理（Batching during query）

• Horizon Zero Dawnのレンダラでは、
  • ジオメトリとシェーダでDrawableSetupをソートする（深度なども同様に）
  • CPUレンダパイプラインの終わりの近くで一緒にバッチ処理する
  • DrawableSetupのリストにとして完全なバッチ処理が使える
  • パイプライン中のDrawableeSetupごとにCPUコストを払う
  • 重要なパスでのみこれをサポートする（ディファードジオメトリ、シャドウマップ）
• 最近の仕事
  • 可視性クエリからバッチを生成して出力する
  • レンダラはバッチのみを見ており、CPU時間を節約する
  • GPUは一度にひとつのクラスタのみ見ているので、不完全なバッチ処理である
  • 現在では、同時に両方のシステムを使う :)

Horizonのレンダラでは、クエリの完了後に、可視DrawableSetupをジオメトリとシェーダでソートする（深度のような通常のソート基準も同様に）。

レンダラのバックエンドでは、矛盾のないジオメトリとシェーダを持つバッチを収集して、単一のドローコールとしてこれらを描画する。これはすべてのDrawableSetupを見れるので良いバッチ処理をもたらすが、レンダパイプライン中のすべての不可視DrawableSetupに対してCPUコストを支払うことを意味する。

バックエンドにさらなる｜機構《machinery》を必要としたので、ディファードジオメトリやシャドウマップレンダリングのような重要なパスでのみこれをサポートする。

代わりにパイプラインの最序盤でクエリ中にバッチ処理することでこの余分なCPUコストとスクラッチメモリコストを取り除きたかった。GPUは一度にひとつのクラスタだけしか見れないのでバッチクオリティは下がるが、依然としてかなり良好である。現在では、両方のシステムを使っているが、将来的に最後のバッチ処理をやめられることを願っている。

GPUコンピュートスレッド: バッチ化された出力（GPU compute thread: Batched output）

• 2つのバッファを書き込む。DrawableSetupBatchに対してひとつ
  • バッチのヘッダ
• そして、DrawableSetupInstanceに対してひとつ
  • Local to Floating空間変換と状態
  • 以前のの変換（動的ジオメトリのみ）

: DrawableSetupBatch

: DrawableSetupInstance

上手にバッチ処理を行うため、全体的にDrawableSetupからの変換を取り除いたので、インスタンスとリソースの間をより効率的に共有できた。これなしには十分な共有率にならなかった。

DrawableSetupと変換を書き込む代わりに、実質的にDrawableSetupInstanceのバッチリストに対する先頭であるDrawableSetupBatchを書き込む。バッチはすべてのインスタンスに対する境界、バッチの長さ、などを持ち、インスタンスは変換といくつかのその他のレンダステートを持つ。

これらはスクラッチメモリ中を進み、見えているもののみを書き込む。繰り返すが、密なパッキングはそれほど重要ではない。

GPUコンピュートスレッド: バッチ化された出力（GPU compute thread: Batched output）

• CPUでは、
  • DrawableSetupインデックスをQueryInstanceの更に空間的なソートキーに追加する
  • なので、QueryInstanceはDrawableSetupでもソートされる
  • DrawableSetupが変化するとき、ビットでQueryInstanceをマークする
• シェーダでは、
  • DrawableSetupでスレッドをグループ化するためにこれらのビットを使う
  • （各スレッドで可視性テストを行う）
  • 各アクティブスレッドはDrawableSeputInstanceを出力へ追加する
  • 各スレッドグループはDrawableSetupBatchをLDSへ｜累計《accumulate》する
    • 例えば、全体の境界、バッチの長さ
  • 各グループの第1アクティブスレッドはDrawableSetupBatchを出力へ追加する

CPUでは、DrawableSetupでソートするためにQueryInstanceのソートキーを拡張し、これが変化するとき、QueryInstanceをビットでフラグ立てする。

GPUでは、DrawableSetupでグループ化するためにこのビットを使い、通常の可視性テストを行い、各アクティブスレッドにDrawableSetupInstanceを書き込ませ、各グループの第一アクティブスレッドに出力へDrawableSetupBatchについてを書き込ませる。

GPUコンピュートスレッド: バッチ処理（GPU compute thread: Batching）

（画像）

• wavefrontはDrawableSetupでソートされる
  • （色は同じSetupのグループを示す）
• CPUからの｜グループ終端ビット《group end bit》
  • （4つのスレッドグループ）
• グループインデックス（終端ビット上のprefix sum）
• 可視性テストを行う。アクティブスレッドは可視である
• アクティブスレッドはインスタンスを追加する
• そして、グループインデックスを用いてLDSに集める
  • （ここでバッチの長さを示す）
• グループごとの第1アクティブスレッドはバッチを出力バッファに追加する

再び、ここでは単純化されたwavefrontを見ている。文字は各スレッドで処理されるQueryInstanceを、色はDrawableSetupのグループを示す。

QueryInstanceからグループ終端ビットを読み込むことに始まり、グループインデックスを得るためにこれのprefix sumを取る。それぞれ色付けされたグループが矛盾のないインデックスで識別されたことを確認できる。

通常の可視性テストを行い、最終的に可視インスタンスを表すアクティブスレッドのサブセットとなる。

アクティブスレッドは以前のようにaggregated atomicsを用いて最初の出力バッファにインスタンスを書き込む。

これらはwavefront全体で共有されるLDS配列にバッチ特性を｜収集《collate》することも行う。これらは円で表され、ここでは、バッチの長さを生成するために各スレッドがグループの配列スロットに1を加えることを示している。本当のシェーダでは、境界と他のバッチ単位の情報も収集する。

各グループの第1アクティブスレッドはバッチデータを読み戻し、バッチを出力バッファに書き込む。バッチ中の最初のインスタンスを書き込んだスレッドであるので、正しいインスタンスを指す方法を知っている。

これはすこし紛らわしいと思う。ここには助けになるかもしれないさらなるいくつかの例がある。

GPUコンピュートスレッド: ひとつの大きなバッチ（GPU compute thread: One big batch）

（画像）

この例はひとつの大きなバッチがある場合に起こることを示している。すべては0番のグループインデックスに集められ、wavefront全体でひとつのバッチを出力する。

これらはすべて同じグループにあるため、グループインデックスは各スレッドで0となる。

書き込まれるインスタンスは同一である。

すべてのスレッドはグループ0のエンティティに集まり、バッチ内のインスタンス数4を得る。

そして、最後にはひとつのグループがあり、4つのインスタンスのリストの開始位置を指すひとつのエンティティのみをバッチバッファに書き込む。

GPUコンピュートスレッド: ひとつずつのバッチ（GPU compute thread: Batches of one）

（画像）

そして、これはすべてのDrawableSetupが異なるときである。ここではグループインデックスがスレッドインデックスと同じである。これは基本的にはシェーダでのバッチ処理を持つ前のセットアップである。

ここで、すべてのグループ終端ビットがセットされ、各スレッドは異なるグループインデックスを得る。

以前と同様に同じインスタンスリストを書き込む。

収集時、各スレッドは自身のグループを持ち、バッチの長さを1とする。

そして、各アクティブスレッドはそのバッチを書き出し、インスタンス1つそれぞれのバッチ4つを得る。

やれやれ。

GPUコンピュートスレッド: バッチ処理（GPU compute thread: Batching）

• ｜長所《advantage》
  • 出力バッファに直接書き込むため、余計なストレージを必要としない
  • wavefront内の書き込みの安定した並べ替え
  • 単一のシェーダを通した単一のパス
• ｜短所《disadvantage》
  • CPUでのいくつかの追加のセットアップ
  • ある大きさへの空間的ソートの衝突
  • 最大バッチサイズがwavefrontサイズに制限される
  • 約2KBのLDSを使う
  • より大きなQueryInstanceを伴う新しいデータフォーマット

このスキームはとてもシンプルであり、いくつかの大きなアドバンテージを得る --- いかなる追加の機構も、ストレージも、パスも必要ない。例えば、各バッチにSetupの連結リストを生成した場合、レンダラが消費できる何かにこれらを平坦化するための別のパスを必要とするだろう。これはいけない。

初めにSetupでソートしなければならないので、空間的一貫性のいくつかを失うが、レンダラではなくカリング階層の効率に影響を与えるだけである。

本当は最大バッチサイズがwavefrontサイズに制限されるという欠点があるが、これは実践ではそれほど痛手にならない --- 依然として｜64倍《64-fold》節約である。

LDSのチャンクを使っているが、シェーダが大量のレジスタを使うので、LDSは占有を害しない --- 多くのwavefrontとして実行できる。

要約（SUMMING UP）

統計（Statistics）

• 一般的にはStaticInstanceを500K-1.5M持つ
• StaticSceneのGPUデータは最大10-30MB使う
• 主な静的クエリ時間は最大1-2msかかる
  • この時間の内いくつかはGPUに対するCPUのビジーウェイトである
  • シャドウクエリ時間は一般的に小さい
• バッチ処理の変更は価値がある
  • レンダパイプラインでのアイテムが最大60-70%削減される
  • クエリ時間には意味のある変化はない

静的なシーンは大量のデータを扱う --- 通常は500Kから最大1.5Mのインスタンスがあり、単一のカメラ位置へ潜在的に可視である可能性がある。

これを表現するGPUデータはそれほど大きくないが、いつもどおりに小さくあることを好む。

クエリ時間は非常に首尾一貫しており、シャドウクエリは、異なる錐台や幾分緩やかなLOD基準を持つので、通常更に速い。

バッチ処理のために作った変更はとても価値があり、クエリ時間をそれほど変えずにレンダパイプラインからだいたい処理の2/3を取り除く。

今後の課題（Future work）

• もとの設計はコンピュートに保守的であった
  • PS4のコンピュートはとても速く、とても柔軟性がある
• CPUからもっと処理を移動する
  • タイル/クラスタカリングをコンピュートに移動する
  • コンピュートにシェーダ定数を直接生成させる
• 動的なコンテンツを（Static）Sceneに移動する
  • オブジェクトの追加削除をより速くする必要がある
  • 空間構造をより速く（および/または簡単に）する必要がある
  • プレースメント（ベジテーションなどの）メッシュのためにとりわけ必要とされる

終わりに（Conclusion）

• PS4のコンピュートは素晴らしい :)
• 単純な解決策は素晴らしい
  • 思い切った試行錯誤を沢山しよう、それも超超速で《Do dumb stuff, lots of it, but really really fast》
• 既存のワークフロー内で動作する
• スケールするように作る
  • コンテンツはプロジェクト終盤に向けて劇的に成長する
  • クラスタのサイズと分布は調整される
  • 新しいシステムは｜かねがね上手くやってくれている《generally coped》

ボーナススライド: オクルージョンカリング（Bonus slides: Occlusion culling）

• 前フレームの深度バッファに対するテスト
  • PS4では、圧縮された深度タイルを読み込む
  • 保守的MIPチェーンを生成する
• 単純で驚くほど効果的
  • ひとつのMIPに対してバウンディングボックスを再投影してテストする
    • 小さなオブジェクトに対する4テクセルの定数時間テスト
    • 大きなオブジェクトに対するテクセルのボックスをスキャンする
  • GPUレンダリングと一緒にスケジュールするのはトリッキー
  • 完璧ではないが、十分良い

ボーナススライド: オクルージョンカリング（Bonus slides: Occlusion culling）

• 錐台カリングするところならどこでもオクルージョンカリングする
  • すべての動的Kdツリーノード、DrawableObject、DrawableSetupに対して
  • すべての静的QueryInstanceに対して
  • CPUとGPUで同じデータと同じアルゴリズム
  • シャドウマップクエリではなくプレイヤーカメラクエリで使う
• 素直なコンピュート実装
  • CPUではもっと込み入ったSIMD実装になる