[&] Tokyo Demo Fest 2015 - Implementing a practical rendering system using GLSL

Implementing a practical rendering system using GLSL
Toshiya Hachisuka
http://www.ci.i.u-tokyo.ac.jp/~hachisuka

17年前から、CGを勉強していますが、
デモシーンに出会ったのがきっかけです。
ソフトウェアラスタライザを書いていました。。
なので、この場で発表するのはとても光栄です。

GLSL で実践的なレンダリングソフトウェアを書くとどうなるか？
GLSL はレイマーチングによって、RayTracing があたりまえになりました。
映画のレンダリングにも使われて初めています。
GPU デモの簡単なレイトレーシングはものは沢山のサンプルがあります。

映画のような物理的に正しいレンダリングをする知識はあまり共有されていない。
レンダリングの複雑性があがるにつれて、共有される知識が少ない。
この領域を考えると、実用的なレンダリングシステムを書くには重要な事柄が共有されていない。

こういうシーン、物理的に正しいシーンを三角形メッシュでテクスチャをはったようなものを 1分でレンダリングするには？

●まず、なんで GLSL なのか？
CUDA とか OpenCLの方がいいのじゃないか？

クロスプラットフォームであること、
Battle tested, 古いものなので、ドライバが良く成熟している。
簡単にシェーダーが書ける。
複数の GPU を使うおうとすると、結構面倒。でも GLSL を使うと、SLI, 複数のGPUでも高速化される。
でももっとも重要なのは「楽しい」から。

●二つの重要な機能
Bounding Vlume heierarchy (BVH)
CPUを使ったレンダリングシステムで使われているもの。
物理的に正しい計算をするために、光の計算をする必要がある。

●Bounding Volume Hierarchy
実用的なシーンをレンダリングするとなると 100M とかあるので、
ひとつ一つやっていると、実質レンダリング終わらない。
アイデアとしては、4つ三角形があったとすると、
2つのペアに対してバウンディングボックスを用意して、
その二つを囲むようなバウンディングボックスを作る。
そうすると階層構造ができる。
普通なら４つの三角形に対して衝突判定しなければいけませんが、
簡単にできるようになる。

●Stochastic PPM
蜂須賀手法；
３つの方法で光のシミュレーションをします。
フォトントレーシングという、光源から乱数を使ってレイトレーシングします。
フォトンという点群のが使いとして、格納します。
カメラからレイトレーシングして、どこに交差したのかみつけ、
交差した点で、密度推定します。
３つのステップで計算します。
全体として、CPUとして、BVH を使って、
それを使って高速なレイトレーシングを行います。
Photon Tracingy , Eye ray tracing, Density estimation
フォトンを累積して累積して計算します。

●Design Principles
並列な処理ができるような処理にすること
ひとつひとつの並列な処理を均質な処理になるようにすること。
ローカルメモリ, GPU のタスクごとに使われるメモリをなるべく使わない。

ここで使われるのは、趣味で書いたレベルなので、
実際の映画の製作に使うには無理があるかもしれません。
こういう風に作っていけばプロダクションレベルのレンダラーが作れるのではないか。

●挑戦
CPU を使ったレイトレーシングは、再帰を使う、スタックを使う、メモリが消費される。

スタックを使わない構造。
最近の GPU だとスタックが使えるし速い場合もある。
しかし、スタックのサイズで、どれくらい並列化されるか決まってしまう。
32kb/512 くらい、最高でも 64個のレイしか計算できない。
今後並列度があがっていった時に足りなくなるかもしれない。

スタックを使わない方が未来があると考える。
どうやってスタックを使わないで、木構造を探索するのか？

Threaded BVH
あらかじめ計算しておいてそれを利用する。
木構造の Hit link を計算しておく。
ヒットリンクは、トラバーサルする時にヒットすると、たどるリンク。
ミスリンクは、ヒットしなかったら辿るリンク。
最終的に、ターミナルに行き着いたら探索を終了。

木構造を計算してしまえば、木構造を保存しなくても、
探索ができます。

ヒットリンクの場合は、隣りにいき、
ミスリンクの場合も３つのルールにしたがって、自動的に計算できる。
変換するのは比較的簡単。
探索が非常に簡単になる。
バウンディングボックスに当たっているのか、当たっていないのかだけを判断するもの。
すごい簡単なループで探索計算ができます。

ヒットリンクとミスリンクは、トラバーサルの順番が固定になっています。
ヒットリンクとミスリンクで計算して、たまたま、トラバーサルすると、
最初のトライアングルにヒットすると、後ろにあるトライアングルは計算しない。
なるべく近いバウンディングボックスからトラバーサルしたいという基本。

+X,-X, +Y, -Y, +Z, -Z ６つの方向に対して、ヒットリンクとミスリンクを作る。

+X、Xがポジティブ方向にすすんで居るとして、
X = 6.0 と、X = 2.5 だと、順序を交換してあげて、
ヒットリンクとミスリンクを作る。
最終的にはデータは、バウンディングボックスのデータと、6つのヒットリンク、ミスリンクの構造になります。

ヒットリンク、ミスリンクは、
vec4 に格納できて、
小さくコンパクトにまとめられます。

トラバース自体のコードはほとんど変わらない。
レイの方向によって、どこからスタートするかを決める。
あとは全部同じ。
スタックは使わないし、まったく同じように動く。

レイトレをする時は、レイと三角形との交差判定を行います。
面白いことに、CPU でやる既存の方法は、CPUの SIMDとかで作られていて、
CPU上で速いとされているものが GPU で速いとは限りません。
CPU上で速い方法をやると、逆に遅くなったりします。
最終的に、おちついたのは、このコードです。

レイトレを書くと、レイと三角形の交差を書くと、分岐がたくさんありますが、
分岐を最後にまとめて、一回だけやると早くなります。
CPUだと分岐を早めにやるのが良い。
GPUだと実際はスキップされないので最後にやるのがいい。

前計算でやっておく方がいいと言われているが、効率が悪いので、
GPU の場合は、前計算しない方がいい。

位置を3つストアして、法線ベクトルが正規化されている前提でZは+-だけ。

NVIDIA の人がチューニングした方法とくらべて半分以上の値が出ている。
通常のBVH よりも3倍くらい速い。

Aila 09 は NVIDIA の GPU 用にチューニングされているものの半分くらいなら結構良いのではないか？

●もともとの６つのリンクを持つのでオーバーヘッドが多いのではないか？
他に比べて、実際リンクを持っても 1.5倍程度しか増えない。実験より。
そんなに悪くないんじゃないか。

この方法が唯一の方法ではなく、研究ではいろいろな方法があるのですが、
ほぼ全て実装して比較したところ、今回の方法が速いことがわかった。

ビット操作でトラバーサルする方法や結構遅い。

●ダイナミックなシーンは？
頑張れば GPU でも動く。

レイトレを高速化できたら、フォトントレーシングをどうするか？
それぞれのピクセルについて、光源からランダムにレイトレーシングしながら進める。
ここで難しいのは、それぞれのピクセルに対してランダムな光の経路がわりあてられるので、
反射回数がすごく多い場合と、凄く少ない場合があり、
計算負荷が一様でない。

乱数を使って計算するのですが、デモとかで使っている乱数を使うと酷いことになる。
統計的にいい乱数をつかわないといけない。

光源からレイを飛ばして、次にどうなるかを決めるとなると、
一つのピクセルについて、次にバウンスさせないという決定をしたときに、
他のピクセルの計算が終わるのを待たなければいけないので、計算効率が落ちる。
フォトンというのはヒットした点について生成するので、
フォトンが複数個生成されていまうと、
GPU でリストを作らなければならず、面倒なことになる。

最初の問題については、非同期にフォトンの計算をすることによって効率を上げることができる。
反射回数をピクセルで持って、0回反射している場合は、新しく光源から。
0の数を数えると新しくフォトンが発生したものがわかる。
計算が終わったピクセルは、他のピクセルを待たないで、新しい計算ができるように。

比較すると、反射回数を非同期にすると、反射回数をあげてもパフォーマンスが落ちない。

乱数について、Fract(sign(...)) は高速だが、乱数としての性質はあまり良くない。
本当にランダムな結果が欲しい。
結構難しい話しで、二つ問題があって、
ひとつは乱数の性質がいいものをつくらないといけない。
GLSL の整数演算をサポートしていない環境でできないといけない。
大抵の乱数発生アルゴリズムは整数前提。



GPGPUフォーラムがあって、そこに誰かが匿名でポストした方法があったのを
GPU に書いたもの。なぜこれがうまくいくのか全く解っていない。
基本的な演算は5行で、fract sig よりもかなりいい。
でも、なんで動いているのかわからないので、気持ち悪い気もする。

GPUを使った乱数生成はけっこう研究されていて、
複数の方法があるのですが、

LCG というスタンダードな方法、
実はあまりうまくいかないので、おすすめしない。
暗号化ハッシュを使う方法があって、それは結構うまくいく。
GPU Mersenne Twister は高品質なのですが、かなり遅い。
xorshift など。

●Eye ray tracing
フォトントレーシングを同じ、最後にヒットしたら、そこで計算がストップするので、
そこで計算をストップできる。どこに交点があるのかを見つけるだけ。
実際交点が見つかったあとは、密度推定を行う必要がある。

交点のまわりに球をつくり、その中に何個フォトンがあるのかを計算して、
密度計算をします。CPU上でやるのは簡単なのですが、
GPU 上でやると、問題がある。
フォトンはランダムに生成されるので、CPU上で作ってやればいいのか？
毎回転送すると、遅すぎて使えない。
GPU上でデータ構造を作りたい。

たまたまフォトンが大量に合った場合、計算がヘビーになる。

空間ハッシュを使うという方法。
フォトンが沢山あった場合、グリッドに切って、
グリッドの点に対して、それよりも少ないハッシュテーブルを作り、それを使う。
GPU 上でハッシュを作る方法はいろいろありますが、
1pixel ごとにテクスチャなどに格納する。

球に対して重なるグリッドにたいして、それぞれのグリッドに対してハッシュを計算して、
球の中にフォトンがあるかどうか計算してみつける。
これはすごく高速に動作します。

二つ問題があって、
ハッシュを作った時にリストを作らなければいけない。
ハッシュを使うので、リストが長くなったり、短くなったり、
長い場合に計算時間が長くなってしまう。

●Stochastic spatial hashing
蜂須賀手法。ランダムに一個のフォトンをキープする。
統計的に正しい結果が得られる。
普通だとリストを作らないといけないが、この方法では、どれが書き込まれたのは無視して、
最後に書き込まれたものをキープしている。
一応何個書き込まれたかというカウンターはあるが、
その分だけフォトンの明るさをスケールする。
これをやると実際のフォトンを探すのではなく、ハッシュテーブルに対して、一回だけ読み込めば良くなる。

実装が簡単で、
ハッシュを計算して、書き込んで、カウンターで数えるだけ。
実際に GPU を使って比較すると、
構築時間も速い。読む時間はほぼ同じか、若干速いくらい。

木構造で高速化する方法もありますが、
それと比べても 3倍から10倍。
CPU との比較。

密度推定、二つの問題を完璧に解決できる。
パーティクルの密度を計算する時などに使える。

テクスチャを持つ時に、なんとなく１つのテクスチャとして作りたくなりますが、
テクスチャの数が限られている。
違うテクスチャにアクセスすると条件分岐しなければならなくなる。

ボリュームテクスチャに全部突っ込んでおく。
アホな方法に見えますが、非常に速く動きます。

デモの人は CPU の利用率を気にしないかもしれませんが、
普通に GPU を使い切ると、CPU も 100%になってしまう。
これを回避する方法は、GPU上で処理が終わったか？をピクセル数を数える関数があって、
それを使うと、CPU 負荷が減ります。

面白い方法として、
普通 32bit の浮動小数点で計算する。
実は 16bit だけ持っていれば、結構なシーンが格納できて、速い。

GLSL はクロスプラットフォームですが、
これは理想的な話しで、OpenCL と比べるとかなりマシ。
NVIDIA, Intel, AMDどれでもちゃんと動く。

GLSL の mod はあるバージョンの NVIDIA ドライバでは変に動く場合がある。
Intel のドライバーの方がいい場合がある。
while ループを使うと NVIDIAのドライバでは動かない場合がある。
break を使うと動くようになる。

まとめ：
Multiple threaded BVH
Asynchronous path generation
PRNG usning only floating point numbers
Stochastic hashing