狠狠撸

E?cient Virtual Shadow
Maps for Many Lights
Ola Olsson*, Erik Sintorn*, Viktor K?mpe*, Markus Billeter*, Ulf Assarsson*
Chalmers University of Technology
お
!
2014年10月作成
2015年4月加筆
1

Abstract
? I3D 2014 で発表された Shadow Map の論文

? 動画: https://www.youtube.com/watch?v=jjAE0h5VNT0

? 目的: 数百のライトによる影をリアルタイムで出す

? 特徴的な点

- Clustered Deferred Shading [Olsson+, 2012] を利用

- Virtual Cube Map を利用

- レイトレーシングを併用したハイブリッド方式
2

目次
? Introduction and Previous Work

? Basic Algorithm

? Algorithm Extensions

? Implementation

? Results and Discussion

? Conclusion and Future Work
3

Introduction
? 目的: リアルタイムゲームで大量の光源を出し、それらの光源による
影も計算したい

? Clustered Deferred Shading をベースとした手法を提案

? Contributions

? Cube Map, Cluster を利用した shadow-caster の効率的なカリング

? 数百オーダーのライトがあるシーンのレンダリングを、影含めリア
ルタイム（～30, 40 ms/frame）で描画可能

? Virtual Shadow Map を利用した、メモリ効率が良くかつ品質を
保った影のレンダリング

? レイトレーシングとのハイブリッド手法（LoD に用いられる）
4

Previous Work
? Many light shadows

? Imperfect Shadow Map [Ritschel+, 2008]

? Many-LODs [Hollander+, 2011]

? これらの手法は「大量の光源によって近似誤差を打ち消す」という考
え方 => 正確じゃない

? Virtual Shadow Map

? Software based virtual shadow map [Fernando+, 2001; Lefohn+, 2007]

? => Software-based で Virtual Texture を実現。本手法は Hardware の機
能を利用
5

目次

? Basic Algorithm


? Implementation


6

Basic Algorithm - Flow
1.Render scene to G-Bu?ers

2.Cluster assignment - calculating the cluster keys of each view sample

3.Find unique clusters - ?nding the compact list of unique cluster keys

4.Assign lights to clusters - creating a list of in?uencing lights for each cluster.

5.Select shadow map resolution for each light.

6.Allocate shadow maps.

7.Cull shadow casting geometry for each light.

8.Rasterize shadow maps.

9.Shade samples.
7









9.Shade samples.
Clustered Deferred Shading のプロセス
8

Clustered Shading
1.スクリーンスペースを 32x32 pixels のグリッドに分割

2.Depth 方向を、区切り幅を指数的変化させながら分割（図の黄色い区切り）

3.Visible なジオメトリが存在するクラスタを見つける（C0～C3)

4.各光源（L0, L1) が交差しているクラスタを見つけ、ペアを作る（Cluster/Light
Pairs)

? Cluster 内のジオメトリが shadow receiver になりうる

5.このペアのリストに基づいて Shading
9









9.Shade samples.
Shadow Map のプロセス
10

Shadow Map Resolution
Selection
? Resolution Matched Shadow Maps (RMSM) [Lefohn+, 2007] をベースにする

? 性能はいいけど expensive

? 完璧な alias-free を狙うのではなく、そこそこ良くてそこそこの軽さにしたい

? Cluster/Light Pair 毎に (1) で計算

!
!
!
!
? S: Cluster が占めるピクセル数

? α: 光源に対する、Cluster の Bounding Sphere の立体角
11

Shadow Map Allocation
? 各光源ごとに Cube Map で Shadow Map を確保

? 解像度は式（１）で求めたもの

!
!
!
!
!
!
? 図の場合、Shadow Map の一部しか使われない

? しかもCluster がスクリーンに占める割合が大きいとCube Mapはかな
り大きくなってメモリに乗り切らなくなる

? => Virtual Cube Map を用いる
Light Source
Cluster Shadow map
12

Shadow Map Allocation -
Virtual Cube Map
? Virtual Texture

? 仮想メモリのようなテクスチャ

? テクスチャの全ての領域がメモ
リ上にのらず、Commit した領
域だけが利用される

? 各領域は「ページ」と呼ぶ

? OpenGL 4.4 extension を利用

? ARB_sparse_texture
Committ
ed
Not
Commite
d
1024Texels
1024
256
256
13

Shadow Map Allocation -
Virtual Page Mask
? Virtual Cube Map

? Commit / Uncommit が必要

? どのページをCommitすべきかを把握する必要がある

? Virtual Cube Map とは別に、Commit すべきかどうかのフ
ラグを保持するCube Map (Virtual Page Mask) を作る
Com
Not
Com
0 0
0 0
0 0 0
0 0 0
1
1 1
1
1
0Virtual Cube Map Virtual Page Mask
フラグを参照して
Commit/Uncommit
14









9.Shade samples.
ここまでやった
15

Culling Shadow-Casting
Geometry
? Batch (適当なポリゴンの集合) 単位でのカリング

? Cluster とは関係なく、全てのポリゴンに対しての処理

? Batch を BVH (Bounding Volume Hierarchy) で格納

? BVH をトラバースすることでライトとの交差判定を行う

? Batch の AABB が、ライトのどの方向と交差したかを格納する

? Cube-face mask (CFM)
Cube Culling?
Planes
Light Sphere
16

Rasterize Shadow Maps
? 各ライト毎に通常の Shadow Map のプロセスを走らせる

? ここ自体は既存手法と大差ない

? Shadow Map を使うときに、Virtual Cube Map の使用する領
域をCommitする必要がある、という点のみ
17

Basic Algorithm
? 基本的な流れはこれで終わり

? しかし、この基本的なアルゴリズムだけではカリング等の高速化
が不十分なので、さらに機能を付け足していく
18

目次

? Basic Algorithm


? Implementation


19

Projection Maps
? 可視領域に shadow receiver が存在しない shadow-caster
=> 計算するだけ無駄

? うまくカリングしたい
Eye/Camera
Shadow casters
20

Projection Maps
? 可視領域に shadow receiver が存在しない shadow-caster
=> 計算するだけ無駄

? うまくカリングしたい
Eye/Camera
Shadow casters
無駄な shadow-caster
21

? どうやって無駄なshadow-casterを判別するか

1. ライトに紐づいたshadow-caster をマッピング
(shadow mapとは別の、各面32x32bitのフラグ用cube
mapへ書き込む)
Projection Maps
Eye/Camera
※shadow-caster は Cluster に含ま
れていないが、Batch カリングの際
に発見しているのでマッピンが可能
22



2. ライトに紐づいた Cluster 内の Batches をマッピング
Projection Maps
Eye/Camera
23



2. ライトに紐づいた Cluster 内の Batches をマッピング

3. オーバーラップが無い場合 => カリング
Projection Maps
Eye/Camera
Projection overlaps:

Draw shadow caster
No overlap:

Cull shadow caster
24

? 同じライトでもClusterによって要求されるshadow mapの
解像度が異なる
Non-uniform Light Sizes
? ライト毎に最大で16個のshadow
mapを作る

? 要求された解像度のうち、解
像度が高いものを最大16個使
う

? 今回の実装では 4 SM/light
25

? 視点から遠くにある Light/Cluster Pair についての処理

? Shadow Map の解像度が 96x96 以下の場合、Ray Tracing
を用いて LoD (Level of Detail) を行う

? Shadow receiver からライトに ray を飛ばし、間に
shadow caster があるかどうか判断

? ポリゴンそのままではなく Voxel 表現を使う[K?mpe+, 2013]

? Occlusion を事前計算しておいて高速化 (詳細不明)
Level of Detail
26

? Cluster の AABB の表現を工夫したというお話

? 各軸を10分割してグリッドを作成

? AABB がそのグリッドのどこからどこまで存在するかを
ビットで表現 (各軸10bit × 3軸 = 30bit)
Explicit Cluster Bounds
Cluster
００１１１１
０
０
１
１
１
０
ビット表現: 001111
ビット表現: 001110
? AABBの統合、Overlap の判定等が高速
にできるようになる
27

目次
? Introduction

? Basic Algorithm


? Implementation


28

? OpenGL と CUDA で実装

? Computationally intense な計算にCPUは使わない。全部
GPU
Implementation
読む気が失せる処理全体のフロー
29

? 基本的には最初に説明した Basic Algorithm のフロー通り

? 各フローを細かく分解して並べただけ

? カリングの際に Projection Map を並列で動かす部分だけ
追加されている

!
Implementation
30

Shadow Map Resolution
Selection
? CUDA を利用して並列計算

? Cluster/Light pair 毎に CUDA の kernel を走らせて計算
31

Culling Shadow-Casting
Geometry
? Batch Hierarchy Construction

? Batchの作り方: Transform を共有し、近くに存在する triangles で構成 (事
前計算)。今回は最大 128 triangles/batch

? Batch の AABB は毎フレーム計算

? BVHの作り方 left balanced 32-way BVH [Olsson+, 2012]

? Hierarchy Traversal

? SM 毎に CUDA block を立ち上げて traverse (32-way BVH にする理由)

? 2pass で traverse を行う

? 1pass: batch の counting と traverse 結果のための storage allocate

? 2pass: 描画する batch の indices やCMF等を出力
32

? Virtual Cube Shadow Map

? OpenGL 4.4 ARG extension

? 16-bit depth texture

? ページサイズ: 256x256 texels

? 解像度: 最大 8Kx8K

? Virtual Page Masks: 最大 32x32 bits
Commit
ted
…
Not
Commit
ed
…
… … …
8K Texels
8K
256
256
33

? 実際のところ、現在のGPUだと Virtual Texture の Commit はとん
でもなく遅い

? 全部 Virtual Texture でまかなうのは無理

? 通常の Cube Map を、事前にある程度解像度別にプールして
おき、それが足りなくなったら Virtual Texture を使う

? Game Console だとそこまで遅くはならない、という主張

? Direct API でリソース管理が行えるから

? AMD_texture_tile_pool [Sellers+, 2013] 等
34

? 特殊な事はせずに straight forward に描画

? Shadow Map 毎に glMultiDrawElementsIndirect

!
? その他いくつかの工夫

? 色々あるけど細かい事なので割愛 (§5.4)
Rasterizing Shadow Caster
Geometry
35

目次
? Introduction

? Basic Algorithm


? Implementation


36

? NECROPOLIS でのパフォーマンス
Results - Performance
Ray Tracing だけ
Ray Tracing 含めた全ての手法詰め
Ray Tracing 除いた全ての手法
ピーク時はこっちの方が悪い
37

? HOUSES でのパフォーマンス

? PMCD-EB-LOD がパフォーマンスいい

? PMCD-EB-LOD: レイトレ以外入れたもの＋従来のポリゴンベースのLOD

? Hybrid: レイトレ入り全部
Results - Performance
38

? 描画された triangles の数の変化 (NECROPOLIS)

? Hybrid (レイトレによるLODが入ったフル機能) が効率良い！
Results - Culling E?ciency
39

? Allocate された shadow map の texels 数 (NECROPOLIS)

? PMCD-EB-1SM/4SM: 1つのライトあたりSMが1つ/4つ

? PMCD-EB-U2/U4: Undersampling x2/x4
Results - Memory Usage
? SM1つだと頻繁に確保し
直しが発生する

? SMのサイズが小さく、ラ
イトの密度が高いときに
Memory Usage が大きく
なる
40

? 上: (1)式で解像度を決め
た事によって発生したアー
ティファクト

? 下: 上の絵にテクスチャを
付けてPCF (Percentage-
Closer Filter) を効かせた

!
? 結果的にアーティファク
トはあまり目立たない
Results - Quality
41

目次
? Introduction

? Basic Algorithm


? Implementation


42

? Conclusion

? Cluster Shading を利用して効率的なカリングが出来た

? Virtual Cube Map を利用して、メモリ利用量、さらなるカ
リングの効率化を行った

? Ray Tracing との Hybrid な手法を提案

? Future Work

? さらにアグレッシブなカリング手法 (max-depth culling 等)

? ライトの事前分布を利用した効率的な手法の提案
Conclusion and Future Work
43

論文について
? Ola Olsson, Erik Sintorn, Viktor K?mpe, Markus Billeter and Ulf
Assarsson, E?cient Virtual Shadow Maps for Many Lights,
Proceedings of the ACM SIGGRAPH Symposium on Interactive
3D Graphics and Games, 2014.

!
? 本資料の図、グラフ等は、論文中から一部引用して使わて頂いて
います
44

狠狠撸

輪読発表資料: Efficient Virtual Shadow Maps for Many Lights

Recommended

More Related Content

What's hot (20)

Similar to 輪読発表資料: Efficient Virtual Shadow Maps for Many Lights (20)

Recently uploaded (15)

輪読発表資料: Efficient Virtual Shadow Maps for Many Lights