初めまして
こんにちは、この記事はFogrexのアドベントカレンダー 36日目兼ハッカソンの報告記事になる予定でしたが、気が付いたら日付超えてました。
ハッカソンのチームは、「ディケイド」で、メンバーは @Fogrex @kegra @0214sh7 です。今回私たちが制作したのは「WebPathTracer」という名前のライブラリです(いい感じの名前が思いつかなかった)。以降はこれについて紹介していきます。アドベントカレンダーも兼ねているので、主に技術について話をしようと思います。
WebPathTracerとは
Fogrexon(アクセスするたびにカメラの位置が変わります、かなり動作が重いうえに画像出力まで結構かかるので注意)
Web上でパストレーサーができるようになるライブラリです。上のリンクはそのデモページですね。特徴としては
- Webで動く
- 簡易的ではあるもののglTFローダーとBVHの当たり判定を備えているので、ユーザーの定義したモデルの読み込みができる
- ↑に加えて、テクスチャ読み込みにも対応している
- ライブラリとしての体裁が整っているので、モデルやカメラの拡縮、移動、配置がわかりやすいインターフェースで提供されている。
- 完全拡散面のモデルでパストレースできる
となっています。
パストレーサーって何
という話なんですが、要はレイトレーシングの一種で、光の経路を逆算することで従来のレンダリング(ポリゴンを代数的に変形する方式、いわゆるラスタライズ法)では表現できない、正確な表現が可能になります。
例えば↑のデモシーンだと部屋の隅のあたりが暗くなっているのがわかると思います。これはアンビエントオクルージョンといって、周りに壁があるおかげで光(環境光)があまり到達しないことによるものです。現実でも起こっていることですが、これをラスタライズ法で数学的に正しく計算することはほぼできないといってよいです(疑似的に表現はできます)
アンビエントオクルージョンぐらいなら疑似的な表現でも気にならないですが、例えばガラスの屈折や反射、オブジェクト自体の発光などはレイトレーシングしないと真に正確な表現はできません。
詳しくは先輩が昔に書いた記事を参考にしてください
sobaya007
基本的には上の記事にあるようなレンダリングのプログラムを実装しています。
レンダリングについて
さて、今回の制作物(Webで使えるパストレーサー)でのレンダリングにはいくつかのハードルが存在します
- モデルをどう読み込むのか問題
- モデルの当たり判定をどうするのか問題
- パストレースの実行時間が長すぎる問題
ひとつずつ見ていきましょう
モデルをどう読み込むのか問題
先述のそばやさんの記事では、基本的な物体(平面、球体、直方体)を使ってレンダリングをしていました。まぁそれでもきれいな画像は出力できるんですが、やはり自作モデルを読み込めたほうがいいに決まってるじゃないですか。それに単に立方体や球体だけだと、やっぱ「テスト」感が強い。「ライブラリ」としての体裁を保つ以上モデル読み込みは絶対条件でした。モデル読み込みができるライブラリがないか探したのですが、この分野に関してはThree.jsが一強ですね。Three.jsのローダーを使った話しか出てきません。モデル読み込みするためだけにThree.jsを読み込むのは負けた気がしたので、自前で作ることにしました。
さて、モデルといっても、この世の中にはいろいろ形式があります。.fbx, .obj, .3ds, .blend ...どれがよいでしょうか？
開発期間が一週間しかない以上、①仕様がわかりやすい、②Webで読み込みやすい の二つを満たす形式がいいです。結局、glTFのjson形式を採用することにしました。この形式はチートシートが用意されていて読みやすく、中身がjsonなのでファイルの操作も楽にできました。
mebiusboxとはいえとりあえずモデル読み込みできるようにした、程度の出来なので、制約はめちゃめちゃあります。
モデルの当たり判定をどうするのか問題
パストレは光の経路を逆算するといいました。なので光の経路と物体との衝突判定を実装する必要があります。直方体や平面、球体などの基本的な図形であれば解析的に衝突判定を作ることができますが、複雑なポリゴンを持つ物体との衝突判定は簡単には作れません。ポリゴン自体は平面なので、全ポリゴンとの衝突判定を作れば理論上はうまくいきます。しかし重すぎて実用的ではありません。
そこで、BVH(Bounding Volume Hierarchy)というものを作ります。これは簡単に言えば、ポリゴンを木(tree)に分割して各節のバウンディングボックス(ポリゴンを囲む軸に平行な最小の直方体)を作り、バウンディングボックスとの判定を繰り返しながら木を探索するという方法です。こうすることで判定回数をだいたいO(logN)回に抑えることができます。この辺はすくくんが競プロパワーで実装してくれました。
ついでにBVHの返り値でその地点の法線情報やテクスチャ座標を返却できるようにしたことで、レンダリングの計算がめちゃめちゃ楽になりました。
パストレースの時間が長すぎる問題
パストレは各ピクセルごとに光の反射を計算していきます。デモだと最大数十回の反射があり、さらにデノイズのために複数回のサンプリングをした後平均化するといった処理を行うので、明らかにJSでの実行では遅すぎます。またパストレ自体の収束性も改善したいです。そのため以下の工夫をしました。
まずはWebAssemblyを使った高速化です。Webでアセンブリコードを実行するWasmなら、3~4倍の速度で計算可能(らしい、測ってない)です。必須の高速化です。今回BVHの構築やパストレース処理はすべてC++で書かれており、EmscriptenによってWasmファイルに書き出しています。その辺の処理をうまくやるようにJSのインターフェースも考えたつもりです。
次にNEE(Next Event Estimation)です。パストレースは、複数回の反射を経てどこかしらの光源に戻って初めて色がわかります。しかし物体表面が拡散反射だと、ランダムに光が飛んでいくことになり、必ずしも狙ったとおりに光源に戻るとは限りません。特に光源がかなり小さい場合、ほとんど衝突することはないでしょう。これは実行時間の伸びにつながりますし、計算を途中で打ち切る場合、ノイズの原因にもなります。NEEは物体表面での光の反射を計算する場合に、強引に光源からの光も計算してしまうという手法です。これにより計算を途中で打ち切る場合でも光源からの光の影響を計算できていることになり、モンテカルロ積分の収束がかなり早くなります。
今後
まぁどう考えても不完全燃焼なので、今後も開発を継続してライブラリとして見れるものを出したいですよね。
実装予定の機能は以下
- WebWorkerをつかってパストレースをバックグラウンド処理
- モデル読み込みを丁寧に作る
- ガラスの実装と物理ベースのマテリアル追加
- C++側で並列処理
うまくできたらnpmとかで公開したいですね。
コメント
チームメンバーからのひとこと 時間経過で追加されていくかも。
Fogrex
今回パストレやりたかったのでできてうれしいです。モデル読み込みとかライブラリないかなって結構探したんだけど読み込むだけのライブラリって無いもんですね。自作する羽目になりました。悲しい。
kegra
0214sh7
青コーダーの†データ構造フォース†でBVHを書きました。他にも法線計算やテクスチャのUV座標計算などバックエンドな部分も書きました。競プロはハッカソンの役に立つ
余談ですが今回BVHでポリゴンの集合を2つに分けるパートはポリゴンの数を半分に分けることを基準にしました。さらなる改善ができるようですが今回は省略しました。
完成しなかったのはディケイドのせいです。
おわりに
明日(今日)のアドベントカレンダーはiroriさんです。お楽しみに！
また、うちのチーム以外のハッカソンの記事が明日までに出そろうと思うんで、そちらも見てみてください。よろしくお願いします。
