拙訳「Efficient Shadows from Many Lights」

概要#

• 問題定義
• 動的シーン
  • シャドウマップ
• 静的シーンの要素
  • 他の手法(も)

何が問題？#

• “多数のライトに対するシャドウ”
  • 多種多様なことを意味し得る！
  • それぞれに多数の解法がある

何が問題？#

• 我々の問題ではない:
  • 非常に小さい多数のライト
    • シャドウを必要としない

• 例:
  • Photon Splatting [Stürzlinger and Bastos 1997Stürzlinger, W. and Bastos, R. 1997. Interactive Rendering of Globally Illuminated Glossy Scenes. Rendering Techniques ’97 93–102.; Dachsbacher and Stamminger 2006Dachsbacher, C. and Stamminger, M. 2006. Splatting indirect illumination. Proceedings of the 2006 symposium on interactive 3D graphics and games 93–100. 10.1145/1111411.1111428.]
    • オクルージョンがすでに計算されている

何が問題？#

• 我々の問題ではない:
  • 非常に小さい多数のライト
    • シャドウを必要としない
  • 多くの重なりを持つ大きなライト
    • 可視性を近似できる

• 例:
  • Imperfect Shadow Maps [Ritschel et al. 2008Ritschel, T., Grosch, T., Kim, M. H., Seidel, H.-P., Dachsbacher, C. and Kautz, J. 2008. Imperfect shadow maps for efficient computation of indirect illumination. ACM SIGGRAPH asia 2008 papers. 10.1145/1457515.1409082. https://jankautz.com/publications/ISM_SIGAsia08.pdf.]
  • ManyLoDs [Hollander et al. 2011Hollander, M., Ritschel, T., Eisemann, E. and Boubekeur, T. 2011. ManyLoDs: Parallel Many-View Level-of-Detail Selection for Real-Time Global Illumination. Computer Graphics Forum 30, 4, 1233–1240. 10.1111/j.1467-8659.2011.01982.x. https://perso.telecom-paristech.fr/boubek/papers/ManyLoDs/ManyLoDs.pdf.]

何が問題？#

• 我々の問題: その中間
  • 現在/将来のゲーム
  • 動的なライトおよびシーン
  • 数百個の全方向性《omnidirectional》ライト
    • ビューあたりわずか数十個のライトがサンプルされる
  • 高品質なシャドウ
    • 誤差の”平均化《average out》”を行わない
  • リアルタイム
    • 少なくとも”研究的実時間《research real time》”である

UKD Necropolis#

• 約300〜400個のライト
  • 大きさが変化する
• 2.6M個のトライアングル
• 最小でだいたい30FPS
• Geforce Titan

いったいどうしてシャドウマップなのか？#

• デファクトスタンダード
  • ｜いろいろあったけど《despite everything》…
• シャドウが高い一貫性を持つ
• ハードウェア/APIにおける柔軟性が増す
• スケーリングが他のテクニックほど酷くない
• キューブシャドウマップが利用可能
• レイトレーシング/シャドウボリューム/など？
  • 動的でない
  • 遅すぎる
  • フィルタ不可能

解法の内訳《breakdown》#

• どのライトがシャドウをキャストするか？
• シャドウマップごとに必要な解像度は？
• シャドウマップのメモリを管理する
• シャドウをキャストするジオメトリをカリングする
• シャドウマップを描画する
• シーンをシェーディングする

多数のライトに対するシャドウ#

• I3D 2014とTVCG 2015による論文 [Olsson et al. 2015Olsson, O., Billeter, M., Sintorn, E., Kämpe, V. and Assarsson, U. 2015. More efficient virtual shadow maps for many lights. IEEE Transactions on Visualization and Computer Graphics 21, 6, 701–713. 10.1109/TVCG.2015.2418772. https://www.cse.chalmers.se/~d00sint/more_efficient/clustered_shadows_tvcg.pdf.]
  • “(More) Efficient Virtual Shadow Maps for Many Lights”
• Clustered Shadingの上に構築する
• シャドウのサポートを追加する
  • 何百個、リアルタイム
    • もちろん、少なくとも研究的実時間
  • 高く一貫性のある品質
  • 効率的なカリング
  • Virtual/Sparseテクスチャのユースケース

解法の内訳#

• どのライトがシャドウをキャストするか？

Clustered Shadingの重要な特徴#

• クラスタ
  • 可視ジオメトリに対するプロキシ
    • ビューサンプルの境界となる
      • 3Dボックス
    • ｜何桁も少ない《orders of magnitudes fewer》
  • クラスタ/ライトのペア
    • クラスタとライトを接続する

解法の内訳#

• シャドウマップごとに必要な解像度は？

シャドウマップの解像度#

• 一定の解像度を選び出す
  • アンダーおよびオーバーサンプリング
  • 不十分な品質
• サンプル密度に対応させる
  • スクリーン空間
  • シャドウマップ空間

シャドウマップの解像度#

ある一般的なアプローチ(例えば[King and Newhall 2004King, G. and Newhall, W. 2004. Efficient Omnidirectional Shadow Maps. ShaderX3. http://www.shaderx3.com/index.htm.])はライトの境界球の投影から必要なシャドウマップの解像度を推定する。

その他のアプローチはより良い推定を行うためにシャドウレシーバーの位置を用いる方法を提案した。

例えば、シャドウレシーバーの境界ボックスをライトへ投影する手法[Forsyth 2004Forsyth, T. 2004. Multiple Shadow frustra. https://web.archive.org/web/20151004100242/http://home.comcast.net/~tom_forsyth/papers/shadowbuffer_pseudocode.html.]

または、個々のサンプルをライトへ投影する手法[Lefohn et al. 2007Lefohn, A. E., Sengupta, S. and Owens, J. D. 2007. Resolution-matched shadow maps. ACM Trans. Graph. 26, 4, 20–es. 10.1145/1289603.1289611.]

各クラスタは固定のスクリーン空間フットプリントを持つ。

クラスタはシャドウマップ上にフットプリントを持つ。これにより、その立体角に比例した必要な解像度を計算できるようになる。

より遠方のシャドウマップ（または、シャドウマップに近いクラスタ）について考えると、クラスタはより大きな立体角をなし、それ故に、シャドウマップの解像度は小さくなる。

解像度の計算#

• ライト球上の立体角
• すべてのクラスタ/ライトのペアで並列に
  • ライトごとに一番高い値を保持する
    • atomicMax
• $Res = \sqrt{\frac{S/(\alpha/4\pi)}{6}}$
  • $\alpha$ = 立体角
  • $S$ = スクリーン空間フットプリント(例、32x32)

解法の内訳#

• シャドウマップのメモリを管理する

シャドウマップのストレージ#

• シャドウマップは前もって必要とされる
  • 効率的なストレージが最重要《paramount》である
  • 理想的には: 不必要なサンプルを一切格納しない
    • 実践では幾らか｜やりにくい《tricky》
    • (シャドウボリューム、レイトレーシング、エイリアスフリーなシャドウマップ)

どれだけ大きく不規則な範囲が未使用であるかに注目して欲しい。

シャドウマップのこの部分に描かれるいずれも可視シャドウを生成しないだろう。

明らかにこの領域に対するメモリの割り当てを回避すべきであるが、どうやって？

ハードウェア仮想テクスチャ*#

• 仮想テクスチャストレージを割り当てる
  • 仮想メモリのようなもの
  • 低オーバーヘッド
• タイル(ページ)状の物理的配置《physical backing》
  • 例、256x256テクセル
• 最新API
  • OpenGL 4.4の拡張 [OpenGL14]
    • ARB_sparse_texture
  • DirectX 11.2
    • Tiled Resources [Cebenoyan 2014Cebenoyan, C. 2014. Real Virtual Texturing - Taking Advantage of DirectX 11.2 Tiled Resources. Game Developers Conference. https://gdcvault.com/play/1020621/Advanced-Visual-Effects-with-DirectX.]
  • Vulkanは？DX12は？コンソールは？(GCN)

* Sparse Textures、Partially Resident Texturesとも

使用されるページの決定#

• シャドウマップにクラスタを投影する
  • クラスタのワールド空間のAABB
  • ワールド空間におけるシャドウマップ
  • 単純な計算

キューブ面 +X#

float rdMin = 1.0f / max(Epsilon, aabb.min.x);
float rdMax = 1.0f / max(Epsilon, aabb.max.x);

float sMin = min(-aabb.max.z * rdMin, -aabb.max.z * rdMax);
float sMax = max(-aabb.min.z * rdMin, -aabb.min.z * rdMax);

float tMin = min(-aabb.max.y * rdMin, -aabb.max.y * rdMax);
float tMax = max(-aabb.min.y * rdMin, -aabb.min.y * rdMax);Copy

• キューブ面上の境界矩形
• 若干異なるものを、6回繰り返す

処理#

• 並列に、クラスタ/ライトのペアごとに
  • クラスタのAABBをライトのシャドウマップに投影する
  • ライトごとにビットマスクを更新する
    • 物理ページあたりに1つのビット
    • 32x32x6ビット = ライトあたり768バイト
  • atomicOrのアトミックreduction
  • 180Kのクラスタ/ライトのペアで0.25ms以下
• ホストにマスクをコピーし戻す
• 物理ページをコミットする(ホスト)
  • glTexPageCommitmentARB

仮想シャドウマップ --- 結果#

: Necropolisのピーク時シャドウマップ使用率

品質 対 メモリ使用量#

• 極めて一様な品質
• 減らすのが簡単
  • アンダーサンプリングパラメータ
• メモリ使用量を制御する
• 動的に行うことができる
  • ピーク時メモリ使用量を保証する？

ここにそれを示すスクショ《shot》があり、シャドウマップにおける2倍または4倍のグローバルな削減を伴う。

シャドウマップのメモリ使用量における対応するピークが示されている。

品質削減を行わないとピークは322MBである。

拡大してみると、シャドウエイリアシングが画像中においてエッジエイリアシングと比較しておおよそ期待されるレベルであることを確認できる。

これは必要解像度の計算のための我々の単純なスキームが理にかなう結果を生み出していることを示している。

フィルタリングがあれば、特に不均等に割り当てられるシャドウマップではなく一様な品質を可能にするので、これは許容できる。

メモリ使用量は大幅に削減される。

解法の内訳#

• シャドウをキャストするジオメトリをカリングする

基本的なカリング#

• 視錐台カリングと同じこと
  • ジオメトリのチャンクをカリングする
  • 境界ボックスを用いて

• VFCと違うこと
  • 数百のライト
  • ほとんどのビューボリュームが短い
    • ライト範囲が制限される
  • 全方向性ライト
    • 6つの隣接する錐台
    • 平面を共有している

int getCubeFaceMask(float3 cubeMapPos, Aabb aabb) {
    float3 planeNormals[] = {{-1, 1, 0}, {1, 1, 0}, {1, 0, 1}, {1, 0, -1}, {0, 1, 1}, {0, -1, 1}};
    float3 absPlaneNormals[] = {{1, 1, 0}, {1, 1, 0}, {1, 0, 1}, {1, 0, 1}, {0, 1, 1}, {0, 1, 1}};

    float3 center = aabb.getCentre() - cubeMapPos;
    float3 extents = aabb.getHalfSize();

    bool rp[6];
    bool rn[6];

    for (int i = 0; i < 6; ++i) {
        float dist = dot3(center, planeNormals[i]);
        float radius = dot3(extents, absPlaneNormals[i]);
        rp[i] = dist > -radius;
        rn[i] = dist < radius;
    }

    int fpx = rn[0] && rn[1] && rn[2] && rn[3] && aabb.max.x > cubeMapPos.x;
    // …他の面で同様に…
    return fpx | (fnx << 1) | (fpy << 2) | (fny << 3) | (fpz << 4) | (fnz << 5);
}Copy

これは、6つの錐台に対して6つの平面のみをテストするので、非常に効率的である。

特に、平面の方程式はすべて1か0であるので、

このループがアンロールされれば、このコードのほとんどはなくなることを意味している。

基本的なカリング#

• 細かな粒度(バッチ)
  • 小さくしなければならない
  • ライトのサイズに合わせる

バッチが大きすぎると、ほとんどのキューブ面にトライアングルが複製されてしまう。

カリングがより精密であれば、描画されるトライアングルが少なくなる。

なので、描画されるトライアングルの減少とカリング処理の増加をトレードする。

トライアングルの描画は最も大きなボトルネックであり、それ故に、これが調節可能であることは重要である。

バッチ#

• 約100個のトライアングルをバッチする
  • AABB
  • 変換へのインデックス、トライアングル
• オフラインで構築される
  • 一貫性のあるトライアングルをグループ化する
    • 同じ変換
  • 平坦な配列

バッチのBVH#

• オンラインで構築される
  • 各フレーム
  • 頂点によって更新されるAABBをバッチする
  • 単純な32ウェイの完全なBVH
• ライトごとに並列に横断する

より良いカリング#

この領域を格納するだけでなく、そこになんでも描画するのはちょっと馬鹿げてもいる。

バッチの剪定#

• ライトに対する投影マップを計算する
• 基本のカリングの結果の上でループする
  • バッチマスクを計算する
  • 投影マップと比較する
    • ビットAND
  • 重ならないなら破棄する

解法の内訳#

• シャドウマップを描画する

描画#

• GPUでカリングする
• 描画コマンドを作る
  • GPUバッファ
• ライトあたり1つのドローコール
  • glMultiDrawElementsIndirect(...);

結果#

• ピーク時に約250Kのバッチ

: Necropolis、ピーク時のフレームあたりのトライアングル数

• 最適化メモ:
  • 達成されたトライアングルレート: 約800M Tris/s
  • GeForce Titanのピーク: 約4.2G Tris/s
  • 差: 約5倍

解法の内訳#

• シーンをシェーディングする

シェーディング(2015年版)#

• ライトでループする
  • ライトインデックス ⇔ シャドウマップインデックス
• 方向からキューブ面のインデックスを計算する
  • GCN: cubeFaceIndexAMD [OpenGL14]
• 方向からキューブ面の座標を計算する
• シャドウマップにおける2Dレイヤをサンプルする
• 注意:
  • バインドレステクスチャを使っていない(I3Dの論文に反して)
  • 理由:
    • ARB仕様への適合
    • シェーディングにおける2倍のパフォーマンス増加(NVIDIAのハードウェア)

ライトインデックスはシャドウマップを参照《look up》するのに単に使われる。

解法の内訳#

• 完了！

静的なシーン要素#

• 静的なライトとシャドウキャスタ
  • シャドウを事前計算する[Kämpe et al. 2015Kämpe, V., Sintorn, E. and Assarsson, U. 2015. Fast, memory-efficient construction of voxelized shadows. Proceedings of the 19th symposium on interactive 3D graphics and games 25–30. 10.1145/2699276.2699284. https://www.cse.chalmers.se/~uffe/Fast%20memory%20efficient%20construction%20of%20voxelized%20shadows%20TVCG.pdf.]
    • ボクセル化されたシャドウ
    • 高品質なフィルタリング
  • シャドウプロキシ[Valient 2014Valient, M. 2014. Reflections and Volumetrics of Killzone Shadow Fall. Advances in Real-Time Rendering in Games course. ACM SIGGRAPH. https://advances.realtimerendering.com/s2014/.]
    • 静的ライト用の静的ジオメトリを事前計算する
    • 実行時にプロキシ＋動的物体をレンダリングする
• 静的シャドウキャスタ
  • レイトレーシング[Olsson et al. 2015Olsson, O., Billeter, M., Sintorn, E., Kämpe, V. and Assarsson, U. 2015. More efficient virtual shadow maps for many lights. IEEE Transactions on Visualization and Computer Graphics 21, 6, 701–713. 10.1109/TVCG.2015.2418772. https://www.cse.chalmers.se/~d00sint/more_efficient/clustered_shadows_tvcg.pdf.; Harada et al. 2013Harada, T., McKee, J. and Yang, J. C. 2013. Forward+: A Step Toward Film-Style Shading in Real Time. GPU Pro 4 277–298.]
  • 符号付き距離フィールド？
• 問題: 時々シャドウキャスタが動くとしたら？

アルゴリズムの拡張#

• シャドウマップを維持する
  • 簡単！
  • すべてのSMが前もって割り当てられる
• 変化しない部分を再描画しない
  • それほど簡単ではない…
  • だけど、試してみよう！

もっと効率的なカリング#

• 以下ならばバッチを破棄する:
  • そのライトが静的である
  • そのバッチが静的である
  • そのバッチが最後のフレームで描画された
  • そのバッチが前のフレームで描画された動的バッチのいずれとも重ならない
  • そのバッチの投影がこのフレームでコミットされる仮想ページのいずれとも重ならない
  • そのシャドウマップの解像度が変化しない

新しい問題#

• ライト/バッチが静的？
  • アニメーションなどに基づいてこれらをフラグ立てするだけ
• 最後のフレームで描画されたバッチ？
  • フラグ？ --- は多すぎる…
  • 前のフレームの投影マップをテストする！
• 動的のものと重なる？
  • 新しい投影マップに動的バッチを記録する
• 新たにコミットされる？
  • 仮想ページマスクに対してテストする
• 動的バッチ後に’trace’をクリアする
  • クリアするためにポイントスプライトを描画する

カリング#

改善されたカリングのロジックを再掲、今回は1D。

我々はライトの投影マップを持つ。

バッチ用のマップを作り、それとテストする。

いずれかの交差があるとき、そのバッチを描画する。

次のフレームでは、変化がないとしよう。

前のフレームからのライトの投影マップを使う。

これは、前と同様に、バッチ投影に対してテストされる。だがしかし！

重なりがある場合、最後のフレームで描画されているはずなので、そのバッチを破棄する。

ライトとバッチの両方は静的であり、両方とも動くことができなかったことを思い出して欲しい。

２つ目のバッチは動的であり、左に動くとしよう。

我々はカリングしつつ動的バッチの投影マップを作る。これは描画されるいずれの動的バッチも記録する。

次のフレームで、このマップをバッチの投影マップと交差させる。

重なりがないので、静的バッチを依然として破棄できる。

ただし、どのように動的バッチが静的バッチと実際に重なるかに注意する…

すなわち、これは次のフレームで再描画しなければならないことを意味する。

これは、前のフレームの動的投影マップを比較することで発見される。

動的投影マップはクリアし再描画すべき部分を教えてくれる。

ページのコミットは同様の効果を持ち、本質的に、同様に扱われる。

これは我々が非常に小さな追加の処理およびオーバーヘッドでシャドウマップへの最小の変更を作ることができることを意味する。

つまり、極端な話、何も動かなければ、何も描画されない。

今後の仕事#

• 我々の設計では忘れやすすぎる！
  • できるだけすぐにページを｜捨てて《drop》しまう
  • 解像度の変更が再描画を引き起こす
• 代わりに
  • できるだけ長くページを維持する
  • 固定サイズのメモリプール
    • 再利用のためのLRUポリシー？
  • (静的ならば)より長く解像度を維持する？
  • より高解像度をリサンプリングする？

問題その1 --- 遅いコミット#

• ページのコミット
  • フレームあたり最大で約2500コミット
  • 平均: コミットあたり約7us
    • → フレームあたり17ms
  • ピーク: コミットあたり約40us
    • → フレームあたり約100ms
  • ｜ばらつきが大きい《high variability》
• より良くする
• バッチAPIを必要とする
  • DX11のような

問題その2 --- 大きな配列のテクスチャのクリア#

• 仮想ストレージ
  • 2048 * 8K2 = 128Gテクセル
• クリアはすべてのレイヤに影響を与える
• ワークアラウンド #1
  • テクスチャビューで6レイヤをクリアする
  • 依然として非常に低速(NVIDIAのハードウェア)
    • フレームあたり約90ms
  • ピーク時の物理ストレージ: 161Mテクセル
• ワークアラウンド:
  • コミットされるページごとにポイントスプライトを描画する
  • フレームあたり約1ms