feature image

2021年12月19日 | ブログ記事

Webでパストレできるライブラリ作った話 (ハッカソン21冬 10班)

初めまして

こんにちは、この記事はFogrexのアドベントカレンダー 36日目兼ハッカソンの報告記事になる予定でしたが、気が付いたら日付超えてました。

ハッカソンのチームは、「ディケイド」で、メンバーは @Fogrex @kegra @0214sh7 です。今回私たちが制作したのは「WebPathTracer」という名前のライブラリです(いい感じの名前が思いつかなかった)。以降はこれについて紹介していきます。アドベントカレンダーも兼ねているので、主に技術について話をしようと思います。

WebPathTracerとは

GitHub - Fogrexon/WebPathtracer
Contribute to Fogrexon/WebPathtracer development by creating an account on GitHub.

デモ

(アクセスするたびにカメラの位置が変わります、かなり動作が重いうえに画像出力まで結構かかるので注意)

 Web上でパストレーサーができるようになるライブラリです。上のリンクはそのデモページですね。特徴としては

となっています。

パストレーサーって何

 という話なんですが、要はレイトレーシングの一種で、光の経路を逆算することで従来のレンダリング(ポリゴンを代数的に変形する方式、いわゆるラスタライズ法)では表現できない、正確な表現が可能になります。

 例えば↑のデモシーンだと部屋の隅のあたりが暗くなっているのがわかると思います。これはアンビエントオクルージョンといって、周りに壁があるおかげで光(環境光)があまり到達しないことによるものです。現実でも起こっていることですが、これをラスタライズ法で数学的に正しく計算することはほぼできないといってよいです(疑似的に表現はできます)

 アンビエントオクルージョンぐらいなら疑似的な表現でも気にならないですが、例えばガラスの屈折や反射、オブジェクト自体の発光などはレイトレーシングしないと真に正確な表現はできません。

 詳しくは先輩が昔に書いた記事を参考にしてください

そばやのウキ☆ウキ物理ベースレンダリング〜パストレ編〜
どうも、そばやです 大学生活がスタートすると、一度は「レイトレしてみたいなぁ」と思うこともあるでしょう。 そこで、そんな新入生の皆様のために人肌脱いでやってみました。 さっそくですが、パストレーシングとは何なのかをご紹介。 する前に、まずレイトレーシングというのをご紹介。 レイトレーシングとは? レイトレーシング(ray tracing)とは3DのCGを作るときの技法で、カメラから仮想的な光線(ray)を飛ばして、その光線と物体が当たっているかどうかを調べることで少しずつ画面に出す色を決定するものです。 じゃあパストレーシングとは? パストレーシング(path tracing)とは…

 基本的には上の記事にあるようなレンダリングのプログラムを実装しています。

レンダリングについて

 さて、今回の制作物(Webで使えるパストレーサー)でのレンダリングにはいくつかのハードルが存在します

  1. モデルをどう読み込むのか問題
  2. モデルの当たり判定をどうするのか問題
  3. パストレースの実行時間が長すぎる問題

 ひとつずつ見ていきましょう

モデルをどう読み込むのか問題

 先述のそばやさんの記事では、基本的な物体(平面、球体、直方体)を使ってレンダリングをしていました。まぁそれでもきれいな画像は出力できるんですが、やはり自作モデルを読み込めたほうがいいに決まってるじゃないですか。それに単に立方体や球体だけだと、やっぱ「テスト」感が強い。「ライブラリ」としての体裁を保つ以上モデル読み込みは絶対条件でした。モデル読み込みができるライブラリがないか探したのですが、この分野に関してはThree.jsが一強ですね。Three.jsのローダーを使った話しか出てきません。モデル読み込みするためだけにThree.jsを読み込むのは負けた気がしたので、自前で作ることにしました。

 さて、モデルといっても、この世の中にはいろいろ形式があります。.fbx, .obj, .3ds, .blend ...どれがよいでしょうか?

 開発期間が一週間しかない以上、①仕様がわかりやすい、②Webで読み込みやすい の二つを満たす形式がいいです。結局、glTFのjson形式を採用することにしました。この形式はチートシートが用意されていて読みやすく、中身がjsonなのでファイルの操作も楽にできました。

gltf/glTF2_QuickRef_jp.pdf at master · mebiusbox/gltf
Contribute to mebiusbox/gltf development by creating an account on GitHub.
有志が作った日本語版チートシート

 とはいえとりあえずモデル読み込みできるようにした、程度の出来なので、制約はめちゃめちゃあります。

モデルの当たり判定をどうするのか問題

 パストレは光の経路を逆算するといいました。なので光の経路と物体との衝突判定を実装する必要があります。直方体や平面、球体などの基本的な図形であれば解析的に衝突判定を作ることができますが、複雑なポリゴンを持つ物体との衝突判定は簡単には作れません。ポリゴン自体は平面なので、全ポリゴンとの衝突判定を作れば理論上はうまくいきます。しかし重すぎて実用的ではありません。

 そこで、BVH(Bounding Volume Hierarchy)というものを作ります。これは簡単に言えば、ポリゴンを木(tree)に分割して各節のバウンディングボックス(ポリゴンを囲む軸に平行な最小の直方体)を作り、バウンディングボックスとの判定を繰り返しながら木を探索するという方法です。こうすることで判定回数をだいたいO(logN)回に抑えることができます。この辺はすくくんが競プロパワーで実装してくれました。

 ついでにBVHの返り値でその地点の法線情報やテクスチャ座標を返却できるようにしたことで、レンダリングの計算がめちゃめちゃ楽になりました。

パストレースの時間が長すぎる問題

 パストレは各ピクセルごとに光の反射を計算していきます。デモだと最大数十回の反射があり、さらにデノイズのために複数回のサンプリングをした後平均化するといった処理を行うので、明らかにJSでの実行では遅すぎます。またパストレ自体の収束性も改善したいです。そのため以下の工夫をしました。

 まずはWebAssemblyを使った高速化です。Webでアセンブリコードを実行するWasmなら、3~4倍の速度で計算可能(らしい、測ってない)です。必須の高速化です。今回BVHの構築やパストレース処理はすべてC++で書かれており、EmscriptenによってWasmファイルに書き出しています。その辺の処理をうまくやるようにJSのインターフェースも考えたつもりです。

 次にNEE(Next Event Estimation)です。パストレースは、複数回の反射を経てどこかしらの光源に戻って初めて色がわかります。しかし物体表面が拡散反射だと、ランダムに光が飛んでいくことになり、必ずしも狙ったとおりに光源に戻るとは限りません。特に光源がかなり小さい場合、ほとんど衝突することはないでしょう。これは実行時間の伸びにつながりますし、計算を途中で打ち切る場合、ノイズの原因にもなります。NEEは物体表面での光の反射を計算する場合に、強引に光源からの光も計算してしまうという手法です。これにより計算を途中で打ち切る場合でも光源からの光の影響を計算できていることになり、モンテカルロ積分の収束がかなり早くなります。

今後

 まぁどう考えても不完全燃焼なので、今後も開発を継続してライブラリとして見れるものを出したいですよね。

実装予定の機能は以下

うまくできたらnpmとかで公開したいですね。

コメント

チームメンバーからのひとこと 時間経過で追加されていくかも。

Fogrex

今回パストレやりたかったのでできてうれしいです。モデル読み込みとかライブラリないかなって結構探したんだけど読み込むだけのライブラリって無いもんですね。自作する羽目になりました。悲しい。

kegra

0214sh7

青コーダーの†データ構造フォース†でBVHを書きました。他にも法線計算やテクスチャのUV座標計算などバックエンドな部分も書きました。競プロはハッカソンの役に立つ
余談ですが今回BVHでポリゴンの集合を2つに分けるパートはポリゴンの数を半分に分けることを基準にしました。さらなる改善ができるようですが今回は省略しました。
完成しなかったのはディケイドのせいです。

おわりに

明日(今日)のアドベントカレンダーはiroriさんです。お楽しみに!

また、うちのチーム以外のハッカソンの記事が明日までに出そろうと思うんで、そちらも見てみてください。よろしくお願いします。

Fogrex icon
この記事を書いた人
Fogrex

シェーダーとVRやってます レイマーチ楽しい(゚∀。)

kegra icon
この記事を書いた人
kegra

レトロゲームとかが好き

0214sh7 icon
この記事を書いた人
0214sh7

きいろこーだー アルゴリズム班の元班長さんです

この記事をシェア

このエントリーをはてなブックマークに追加
共有

関連する記事

2023年12月11日
DIGI-CON HACKATHON 2023『Mikage』
toshi00 icon toshi00
2024年6月21日
ハッカソン参加記 4班"Slide Center"
Alt--er icon Alt--er
2023年7月15日
2023 春ハッカソン 06班 stamProlog
H1rono_K icon H1rono_K
2024年5月8日
2023 春ハッカソン 10班 『「」か』
Kasyu icon Kasyu
2024年1月16日
2023年冬ハッカソン参加記 チーム2 20%電電 "Orbit"
onkyi icon onkyi
2023年6月23日
2023 春ハッカソン 26班 『traP Mission』
Ras icon Ras
記事一覧 タグ一覧 Google アナリティクスについて 特定商取引法に基づく表記