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