Ray Tracing In One Hour

KMC春合宿オンライン 2021夏で発表した内容です

レイトレーシングのチュートリアル"Ray Tracing In One Weekend"と続編の"Ray Tracing: The Next Week"の一部を元にしていますが、基礎的な部分の解説を入れたり、高速化についても取り扱っています

Transcript

1. Ray Tracing in One Hour KMC-ID: prime 2021/09/20 春合宿オンライン 2021夏
2. 2 今日の内容 レイトレーシングのチュートリアル Ray Tracing in One Weekend https://raytracing.github.io/books/RayTracingInOneWeekend.html を参考に、アルゴリズムと実装に触れる 最後の方は続編の Ray Tracing: The Next Week https://raytracing.github.io/books/RayTracingTheNextWeek.html の内容も一部取り扱ったり、これらの資料にないトピックも扱う
3. 3 自己紹介 KMC-id: prime (37 代 ) a.k.a.そすうぽよ 社会人 3 年目 Twitter: @_primenumber Web: https://poyo.me Mastodon: @prime@mstdn.poyo.me 計算機を作ったり壊したり、 使い倒したり
4. 5 自己紹介 (VRChat) 最近はバーチャルの世界で遊んでいます シェーダーを書いて、他プレイヤーの GPU で計算できる！ シェーダー : 3DCG で描画される内容を計算する、 GPU 上で動くプログラム 作例： ライフゲームのシミュレーション Brainf*ckインタプリタ 汎用並列計算機 GPU パーティクル ※ 用法容量を守ってお使いください
5. 6 レイトレーシングとは 光線の軌跡を追跡することで光のふるまいをシミュレートする手法、 あるいはそれを利用して 3DCG をレンダリング（描画）する手法
6. 7 レイトレーシングとは 光線の軌跡を追跡することで光のふるまいをシミュレートする手法、 あるいはそれを利用して 3DCG をレンダリング（描画）する手法 （光の挙動をもとにレンダリングするのは当たり前では…？ ） 🤔 → 光の軌跡を再現しない手法もある
7. 8 ラスタライズベースのレンダリング 計算負荷が低く、ほとんどの GPU でサポートされている手法 物体を多数の多角形（三角形や四角形がほとんど）に分割、これを 平面に投射するような形で描画する 物体の陰や写りこみ等は、このままでは実現できない 疑似的に実現する技法はあるが、正確性に劣る
8. 9 レイトレーシングの原理 視点からレイを飛ばし、光源に当たるまで反射・屈折を繰り返す （光源からレイを飛ばす方法や、両方から飛ばす方法もある）
9. 10 レイトレーシングのメリット・デメリット 光の屈折や反射を忠実に表現できるため、かなり正確な描画が可能 計算コストが非常に高い 散乱などについては、ある程度近似する必要がある
10. 11 レイトレーシングの実装
11. 12 描画結果の取得 描画した結果を目で確認したい（それはそう） 画像ファイルに保存できると楽 ppm(Portable Pixel Map) 形式なら、各ピクセルを文字列で格納で きるので、デバッグが楽 P3 画像格納形式 256 256 幅 / 高さ 255 最大輝度 0 255 63 赤 緑 青 1 255 63 赤 緑 青 ... PPM で保存した画像
12. 13 3 次元ベクトル (vec3) レイの方向等を表現するのに使う x,y,z の各次元に対応する実数値を持てばいい ここでは長さ 3 の配列で持つことにする struct vec3 { double e[3]; }; 座標 (x,y,z) や色 (R,G,B) も同様（流用してもよい） point3 , color としておく
13. 14 レイの実装 ある点から特定の方向に向かうレイを表現する 始点と方向を表すベクトルを持てばよい struct ray { point3 orig; vec3 dir; }; レイ上の点は orig + t * dir (tは実数 ) と書ける
14. 15 レイを飛ばす（飛ばすだけ）カメラ 原点から仮想的なスクリーンに向かってレイを飛ばす スクリーンの四隅との 相対座標 (u,v) からレイの 方向を計算できる
15. 16 レイをもとに描画する いまのところレイは飛ばしただけで何もしていない とりあえず Y 座標をもとにグラデーションを描画してみる 青から白へのグラデーション
16. 17 球を描画する Q: なんで球？ A: レイとの衝突判定が簡単等、実装が楽な点が多いから 球以外のオブジェクトの描画は、 続編の Ray Tracing: The Next Week で取り上げられている
17. 18 点と球の内外判定 レイ（半直線）と球の衝突判定の準備 点 P と球 S( 中心 C, 半径 r) の内外判定は、　　　　 でできる 引き算は、座標をベクトルとして演算、　　で v の長さを表す 三次元なので、 sqrt は重い計算なので、しばしば両辺二乗を取って 内積で書くと ‖P−C‖≤r ‖v‖ ‖v‖=√v x 2+v y 2 +v z 2 ‖P−C‖2≤r2 (P−C)⋅(P−C)≤r2
18. 19 レイと球の衝突判定 レイ上のある点が球の内側になるかどうかを判定すればよい レイ上の点をパラメータ t を用いて　　と書くと、 ある t について　　　　　　　　　　　となるかが知りたい レイの始点 A と方向 b を用いて、　　　　　と分解できるので、 内積は通常の積のように分配法則が成り立つので、 内積はスカラー値になるので、これは t の二次不等式になる 衝突判定だけでよければ、判別式の符号を見ればよい 衝突する点を求めたい場合は、二次方程式を解けばよい P(t) (P(t)−C)⋅(P(t)−C)≤r2 P(t)=A+t b (A+t b−C)⋅( A+t b−C)≤r2 t2 b⋅b+2t b⋅(A−C)+( A−C)⋅(A−C)≤r2
19. 20 ラスタライズ法との比較 ラスタライズベースのレンダリングでは、球のように曲面をもつ 物体は、多数の三角形等の組み合わせで近似することが多い
20. 21 スキャンライン法 ラスタライズベースのレンダリングでよく使われる手法 描画時に行 (line)単位で描画する 画面での線分に対応する点の集合は平面になる この平面と三角形の交わりは線分になる この線分を画面上の対応する区間に書き込めばよい
21. 22 球の描画
22. 23 … 球？ どう見てもただの丸です　ありがとうございました 単一色で塗りつぶしているので、立体感も何もない 現実では単一色でも、陰影により見え方が場所により変化する 球上の各点が各々「向いている向き」を持っている 球の中心の反対方向 法線という 光の反射を、法線とレイの向きをもとにシミュレートしていく
23. 24 法線とその計算 球の場合は簡単 その点から球の中心を引く 球の内側から入射した場合、 その反対向き
24. 25 法線の図示（陰影はまだ）
25. 26 複数の物体を描画する レイ上に複数の物体が現れることがある その場合、もっとも始点に近い衝突点が求める衝突点 単純には、全ての物体と衝突判定をすればよい より効率的な方法に BVH(Bounding Volume Hierarchy)などがある とりあえずここでは単純な方法を使う
26. 27 複数の物体の描画
27. 28 ジャギー 物体の端がギザギザしている 各ピクセルに対応するレイが、 その物体に当たるかどうかの境目で ギザギザしてしまう
28. 29 マルチサンプルによるアンチエイリアス 各ピクセルに対応するレイを複数投げる ピクセルに相当する矩形のなかで、ランダムに方向をずらす (px, py) (px+1, py) (px+1, py+1) (px, py+1)
29. 30 アンチエイリアス結果 アンチエイリアスをかける前後の比較 なし あり
30. 31 拡散反射 ここからレイトレーシングの核となるレイの追跡を実装していく まず拡散反射（乱反射）をシミュレートする ここでは拡散反射のモデルとしてランバート反射を実装する ランバート反射 (Lambert反射 ) 輝度はどの角度から見ても一定 輝度は光源の方向と法線の内積に比例する 滑らかな面を持つ物体の拡散反射をよく近似する ほかの拡散反射モデルもあるが、ここでは扱わない
31. 32 ランバート反射のシミュレート 今、視点から光源の方へ光を逆にたどっている レイは光源の方向を知らないため、このままでは計算できない 光源が複数あったり、広がりを持っている場合もある 輝度への寄与をもとに、適切な確率分布でレイを反射させることで シミュレートする
32. 33 ランバート反射 輝度が光源の方向に依存しないなら、 法線方向を向いた単位半球面から ランダムに選べばよい 要するに、光源としてあり得る方向から ランダムに選ぶ
33. 34 ランバート反射 実際には法線との内積に応じて分布が変わる 具体的には、法線と光源方向のなす角を θ として、　　　に応じて 分布が変化してほしい 実は簡単にこの分布を作ることができる 単位球面上から一様ランダムに取り、単位法線ベクトルと和を取ればよい 証明は、倍角の公式 と円周角の定理を使うとできる cos(θ) sin(θ)cos(θ)= 1 2 sin(2θ)
34. 35 ランバート反射の分布の図解
35. 36 球面上一様分布の作成 様々な方法があるが、簡単な方法として、 1.[-1,1]の一様乱数を 3 個生成する 2.これが半径 1 の単位球に収まっていないなら、 1 に戻る 3.収まっているなら、この 3 次元ベクトルを正規化する（自身の長 さで割る） ステップ 1,2 の繰り返しは十分少ない回数で終わることが期待でき る（ 1 回の試行で成功する確率は 1/2 より大きい）
36. 37 球面一様分布の他の作り方 xy-座標と z 座標に分けて考える z 座標で球を輪切りにするイメージ z 座標は実は [-1,1]上の一様分布になる xy-座標は半径　　　の円周上から一様に選べばよい 半径 r の円周上から一様に選ぶのは、 [0,1) 上の一様乱数 u から とすればよい √1−z2 x=r cos(2π u), y=rsin(2 π u)
37. 38 再帰的反射 拡散反射の分布に沿って、新しいレイができる これをレイが光源にぶつかるまで再帰的にくり返す 光源にぶつかったら、各物体における反射率を掛けて色を求める … 光源に永遠にぶつからなかったら？ スタックを食いつぶしてプログラムがクラッシュしたりしてしまう それは困るので、一定の回数反射したらそこで再帰をやめ、光源に 達しなかったとして黒（明るさ 0 ）とする とりあえず、光源は空の色とする
38. 39 ランバート反射のレンダリング
39. 40 ガンマ補正 人間の目は、輝度に対して対数的な挙動を示す 暗い場所の方が輝度の変化に気付きやすい ディスプレイは RGB の数値に対して非線形な変換をかけて表示する もともとはブラウン管ディスプレイの特性に由来する 人間の視覚の特性上都合が良いため、現代のディスプレイでもこの変換が 行われている レイトレーシングで得られた生の輝度をそのまま保存すると、 この変換により、暗い場所がさらに暗く表示されてしまう そこで保存時にこの変換を補正する変換を掛けてから保存する ガンマ補正という
40. 41 ガンマ補正後
41. 42 複数種類のマテリアルを扱う マテリアル “ 材質”を表すオブジェクト 反射の性質、色などを管理する 各物体に、対応するマテリアルへの参照を持たせておけば、 物体ごとにマテリアルを差し替えることができる 拡散反射する物体、鏡面反射する物体、透過・屈折する物体などを 同時に配置することができる
42. 43 鏡面反射 レイの衝突した点で、その面に対して反転した向きにレイが出る 新しいレイの方向は、レイの方向 v と、法線 N を用いて、 と書ける v−2(v⋅n)n v v N (v ･ N)N
43. 44 鏡面反射
44. 45 粗い面 つや消し加工のように、表面が粗い金属の反射をシミュレートする 反射角を乱数で少し乱してやる 乱し方はパラメータで調整できるようにしておくとよい Tips: 表面の粗い金属の反射と拡散反射では、反射スペクトルが異なる
45. 46 粗い面
46. 47 屈折 ガラス玉のような物体を描画したい ガラスの表面では、光は屈折を起こす 屈折による方向の変化は、スネルの法則に従って計算できる
47. 48 反射率の計算 入射角と屈折率の比によっては解けない この場合、全反射が起こる 全反射が起こらない角度でも、ある程度の反射が起こる 反射の割合はフレネルの式によって求められる しかし、偏光についても考える必要が出てくるなど面倒なため、 近似式として Schlickの近似がよく使われる 屈折率を　　　　入射角を α とすると、反射率 reflectanceは r 0 = |n 1 −n 2 n 1 +n 2 |2 reflectance≈r 0 +(1−r 0 )(1−cosα)5 n 1 ,n 2
48. 49 ガラスの描画
49. 50 中空ガラス 内側が空洞になっているガラス球をシミュレートしたい 「表裏が反対になった球面」があれば、普通の球と組み合わせて 中空ガラスを再現できる これは（実装によるが）「半径が負の球」にすることで実装可能
50. 51 中空ガラス
51. 52 カメラの移動 ここまで「カメラ」は完全に固定されていた 位置は座標系の原点 (0,0,0 ) にあった 視点の向きは z 軸負の方向 視野は上下方向が (x,1,-1) から (x,-1,-1) がぴったり見える範囲 せっかくなので動かせるようにする
52. 53 視野の調整 上下方向に見える角度（視野角）を与えられるようにする 対応する仮想的なスクリーンの高さは　　　で求められる tan( θ 2 )
53. 54 視点と向きを変える 視点の座標とカメラの向く方向を与えれば OK… ではない 「上」の向きも与える必要がある 目の位置と向いている方向を動かさずに、首を左右に倒すような動作を できるようになる 「上」と「前」が与えられたら、クロス積で「左右」の方向を求め ることができる
54. 55 斜め上から描画
55. 56 視点や向きを動かさずに、視野角を変更（ズーム）
56. 57 ボケのシミュレート 「ボケ (bokeh)」を実現する 焦点面（カメラから焦点距離だけ離れた面）から遠い物体の像は ぼやけて写る 遠方にある瓶がぼやけて写っている様子
57. 58 カメラとレンズ 焦点面上の点から発した光は、レンズにより屈折し、フィルム上の （理想的には）一点に集まる 現実のカメラでは多数のレンズの組み合わせで構成されているが、 それはおいておく
58. 59 ボケのシミュレート カメラの外側（レンズより外側）に着目する レンズには一定の大きさがあり、ここに入ってくる光を結像させて 画像を得る レイトレーシングでこれを実現するには、 レイの始点をレンズの面積分 ばらつかせればよい
59. 60 ボケのシミュレート
60. 61 ボケのシミュレート
61. 62 たくさん物を置いてみる Ray Tracing in One Weekend の内容はこれでおしまい たくさんの物体を、いろいろなマテリアルで配置してみる せっかくなので画像サイズを大きく、サンプリング数もたくさんに
62. 63 たくさん物を置いてみる
63. 64 おっっっっそ 35 分掛かった 実装による、にしても… せっかくなので頑張って速くしてみる とりあえずコンパイルオプションを最適化優先に -Og → -O3 -march =native 26 分になった
64. 65 並列化する 計算はピクセルごとに独立しているので、簡単に並列化できる C++ なら OpenMPで気軽に並列化できる が、単にピクセル単位で等分してもあまり効率が良くない 場所によってレイの反射回数（の平均値）が異なるため 動的にタスクを分割すると全コアを使い切れる ただし、余分なオーバーヘッドがかかる OpenMPなら schedule(guided) でやってくれる 1 タスク単位で分割する schedule(dynamic) もあるがオーバーヘッドが大きい 16 コア CPU で 11 倍速くらい ( 約 2 分 20 秒 ) になった
65. 66 Bounding Volume Hierarchy 計算時間のほとんどは、物体とレイの衝突判定 今はそれぞれのレイに対し、全ての物体との衝突判定をしている 当然物体の数に比例した時間がかかる なんとかならないだろうか…？ 解決策の一つが、 BVH(Bounding Volume Hierarchy)
66. 67 Bounding Volume Hierarchy 物体の集合を複数のグループに分割する 各グループに対し、グループ内の物体を包含する直方体を計算する 直方体以外もあり得るが、計算の単純さから直方体がよく使われる この直方体を Bounding boxという
67. 68 Bounding Volume Hierarchy レイの衝突判定では、まず bounding boxとの衝突判定を行う bounding boxと衝突しないなら、このレイはこのグループ内の 物体と衝突することはないため、個別の衝突判定をスキップできる グループ分割を再帰的に行うことで、劇的に計算量を削減できる
68. 69 Bounding Volume Hierarchy の実装 適当に分割すると、 bounding boxの重なりが増え、効率が悪い 上手い分割方法で論文や本が書けてしまうレベル https://shin jiogaki.github.io/b vh/ とかを眺めると面白い ここでは x/y/z 軸から一つ選んで座標でソートして分割する実装に
69. 70 BVH の効果 適当に実装したところ、 1 分半ほどに ( 約 1.5 倍速 ) bounding boxとの衝突判定が支配的なので、ここをチューニング グループ分割も多少工夫 これらの改善で、 33 秒ほどまで高速化した
70. 71 まとめ レイトレーシングをかなり簡略化した状態で実装した 物体は球面のみ、光源は環境光のみ、等 かなりリアルな描画が可能 一方で、計算負荷はとても高い 計算機のパワー、アルゴリズム、そしてチューニングで ある程度は頑張れる