2018-03-28Hashed-Octree(ハッシュ化八分木)による空間分割を実装したそろそろレイトレがしたい。具体的に言えばフォトンマッピングでGIを実装したい。フォトンマッピングを実装するには現状あまりにも足りないものが多すぎる。その最たるものが、高速な衝突判定アルゴリズムだ。シンプルに設計されたレイトレ専用のアプリケーションなら、レイの衝突判定は、シーン中の全てのオブジェクトに対して総当たり的にやってもいいだろう。メッシュも、プリミティブな形状に限定すれば、高速に処理できる。現在私が作ってるのは曲がりなりにもリアルタイムレンダリングエンジンだ。シーンの大きさや配置されるオブジェクトの数は固定ではない。現実的な処理時間で動作させなくてはならない。メッシュも多くのポリゴンを有する複雑なモデルが存在するかもしれない。そのためには、レイの衝突判定において、衝突しないことが自明なオブジェクトに対しては処理をスキップするような仕組みが必要である。このような仕組みで最も直感的なものは、ユニフォームグリッドによる空間分割だろう。シーン全体を一様なグリッドで分割し、所属するグリッド内のオブジェクトのみで衝突判定を行う。この分割法には多くの問題がある。グリッドの横断が想定されていない。空間の分割の粒度をどれくらいにするにせよ、位置、サイズによっては必ず複数のグリッドにまたがるオブジェクトが出現するはずである。基本的には一つのオブジェクトが複数のグリッドから参照される形になるだろう。一般に、空間というものは疎なもので、基本的には何もない。偏りがあるものである。空中にオブジェクトがあることはまれだが、あるテーブルに着目した時、そのテーブルの上には多くのオブジェクトがあることが期待される。このような分布の空間において、一様なグリッドで分割するのはあまりにも非効率である。このようなケースにおける最適な空間分割法として、八分木(Octree)がある。ルートの空間を定義する。次に、X-Y-Zについてそれぞれ2分割する。分割後の空間を空間レベル1(L=1)として、同様の操作を任意の空間レベルまで行う。ユニフォームグリッドとの大きな違いは、空間レベルという概念があること。「グリッドをまたぐ」というのは存在せず、仮にグリッドをまたぐ場合は、それは1ランク上の「親空間」と呼ばれる、より大きな分割単位の空間に所属する仕組みになる。グリッドの番号にはモートンオーダーを用いることで、ビット演算を駆使してあるオブジェクトの属するすべての空間レベルのグリッド番号を取得することも可能である。この辺の細かい説明は、すでに必要十分な説明を記載しているサイトがいくつもあるので省略することにする。4分木空間分割を最適化する!ちなみに、アルゴリズム的には木構造であるが、モートンオーダーに対して空間レベルの等比数列の総和のオフセットを付加することで、任意の空間レベルの任意のグリッドのオーダーをハッシュ化することができる。7)の要素数の配列の動的確保を要求していて効率が悪い。std::unordred_mapのようなハッシュマップを使えば、疎な空間における効率的なメモリ確保が実現できるだろう。実装にあたって、八分木分割後のビジュアライザーが必要だと感じたので、そちらもついでに作った。空間座標から所属するモートンオーダーの算出方法は上記サイト様に記載のある通りだが、モートンオーダーから空間座標を逆算する計算が不明だったので、ここに記しておく。boxSize.d));}これでハッシュ値から、所属するAABBを求めることができる。戦略的には3bitごとに区切られたX-Y-Zのビットに着目して、特定の次元について切り詰める。110111001というモートンオーダーをXについて切り詰めると、011だ。今回の場合は空間レベルは最大8に設定したので、24桁のビットがある。効率的な方法がある気もするが....実際に計算して可視化してみた。各オブジェクトが所属する最小八分木空間を計算した後は、それと同じサイズのボックスメッシュを生成し、ワイヤーフレーム描画してそれっぽく見せている。同じオブジェクトでも、位置によってはグリッドをまたいでしまうため、より大きなAABB(より高いレベルの空間)に所属している様子が分かる。これで空間内の衝突判定の準備は整った。次は、レイが空間を通過するときの衝突リストの作成だが...いまいち効率的な方法が思いついていない。Maps(分散シャドウマップ)を実装しようと思う。これはソフトシャドウの実装の一つで、シャドウのエッジをなんかいい感じにする技術だ。普通のシャドウマップの実装を再掲する。false;}まず、ライト視点のカメラを仮定してパースペクティブ・ビュー行列を作成し、シーンの深度を保存する。実際のレンダリングパスで対象の頂点を再度ライト視点に復元、格納済みの深度と比較してシャドウ判定を行う。格納された深度よりも描画対象の深度が低ければシャドウなし、高ければシャドウありだ。この2値的なアルゴリズムだと、どうしてもエッジが硬い違和感のあるシャドウになってしまう。これは、シャドウマップの解像度が低くなればよりジャギーが発生し違和感が顕著になる。リアルの世界のシャドウと言えば、硬いエッジものはそうは見かけない。光源が面積を持っていたり、あるいはシャドウに間接光が入射するなど、様々な影響が存在するからだ。残念ながら現在はそのどちらも実装できていないので、シャドウのエッジを”誤魔化す”ことにする。この手法は、物理的には正しくないが、それなりに見栄えの良いソフトシャドウを作ることができる。これの優れた点は、現状多く存在するシャドウの実装と容易に組み合わせることが可能な点だ。Maps(以下VSM)の実装に使われる、確率論分野のチェビシェフの不等式である。ここでtが確率論でいう標本、μが平均値、σが分散である。確率論の不等式をシャドウマップに適用というと突拍子もない話だが、この式によって得られる「0~1に正規化された確率」を「影の濃さとして適用する」と言えばなんとなく想像はつくだろうか。ここで、チェビシェフの不等式に使う平均値(期待値)、分散だが、これは局所平均値を用いることで計算できる。その計算方法とは、すなわちシャドウマップにぼかしフィルタを適用した後の値だ。移動平均フィルタのカーネルは一様分布であるので、そのフィルタを適用した後の各テクセルの値は局所平均値になることは自明であろう。(元論文)http://www.punkuser.net/vsm/vsm_paper.pdfでは、ガウシアンフィルタを使うようだ。シャドウマップには現状、深度ステンシルバッファを使っている。残念ながらこれは最も最適な手法だが融通が利かないので、深度バッファではなくレンダーターゲットに焼き付ける手法でシャドウマップを作成する。レンダーターゲットを使えば、1つのピクセルにつきrgbaの4つのスロットを使うことができる。E(x^2)を計算することができる。いうわけで、DirectXで実装してみよう。DirectXには、GPU上のリソースに手を加えるという軟弱な機能はないので(CPUにマップすれば可能だが無駄すぎる)、ガウスフィルタを適用したいテクスチャと同じサイズのビューポートを作り、そこに画面いっぱいに板ポリゴンを配置、ガウスフィルタを適用しながらその板ポリゴンを描画すると、レンダーターゲットにガウスフィルタの適用したテクスチャのできあがりだ。レンダーターゲットに深度を焼きこむピクセルシェーダは省略でいいだろう。zとz^2を出力するだけだ。ガウスフィルタは、X-PassとY-Passに分離できるので、2つのシェーダーを作り2パスに分けて描画することにする。1.0f);}フィルタの重みは以下のように計算できる。}ここでdisperisionパラメータは、シャドウの見栄えがよくなる適切なパラメータを指定する。このシェーダーで描画されたシャドウマップのrとbを使って、"影になる確率"を求める。t)を満たすときのみ}あとはこれで得られるファクターを、ライティング結果に掛けるだけだ。VSM実装前と実装後の比較画像を貼る。うん...(論文とちょっと違う感じになってるのが気になる。ソフトというより残像っぽい)今回はここまで。Reflectionを実装した。前回、スカイボックスを実装したが、そのスカイボックスのリソースであるキューブテクスチャを環境マップとして用いて、リフレクションを実装することにする。いっても、一応、拡張性を持たせるために、シーン内に複数の環境マップが存在し、最も近く、小さく精度が高いと期待できる環境マップをメッシュごとに探索し、レンダリング時のリフレクションリソースとして使用する、という仕組みを作った。Libraryにお世話になりオブジェクトのIDを一意に定められるようにした。std::size_tの変換を噛ませている。UUIDのフォーマットはXXXXX-XXXXXXX-XXXXXのような形式(桁数は適当)だが、これをそのまま使うにはC++はあまりにも文字列に対して無力なので、ハッシュ化することにする。(少なくともVC++はFNV-1アルゴリズムだった。)UUIDの一意性は失われ危険がある気はするが、まあ別にプロダクトを作っているわけではないのでこの辺はざっくり適当でいいだろう。問題が起こったらどうにかする。肝心のリフレクションだが、すでに実装しているスペキュラ反射の一部を流用しつつ実装する。これはSchlickの近似を使ったフレネルの公式である。垂直入射時の反射係数(物理的な正確さを求めるなら、RGBそれぞれの反射能の定数ベクトル)である。マテリアルのパラメータとして与える。cosθは正規化された法線・視線ベクトルの内積で求まる。ここでリフレクションが起きている頂点の色というのは、屈折方向の色と反射方向の色の合成で求まる。col;}このように求まる。ここで、etaというのは物質の屈折率だ。大気の屈折率は1として反射係数を計算している。これで求まる反射の色だが、これをどのようにPBRに当てはめるか?一応作っているのは、物理ベースであるので、レンダリング方程式に乗っ取って適用したい。結論から言うと、現時点での実装では物理的な正しさをこのリフレクションにもたせるのは不可能だ。基本的に現実の物質は多少なりとも光を拡散するからである。環境マップによるリフレクションとは何か?という定義から考えなくてはならない。反射が発生するとしている以上は、環境マップは光を放っているということにして、その光が物体に入射しているのだという前提で環境マップリフレクションは実装されている。環境マップは光源なのである。テクセル一つ一つが、光源として色をもって光を放っている。その数は横*縦*高さ。Lightingという。ここで一度原点に戻ってレンダリング方程式を掲載してみよう。ここで、右辺第一項は自身が光源として放つ光のことなので今回は無視してよい。右辺第二項は、(否透過材質であると仮定すれば)入射してくる光と、法線ベクトルと入射ベクトルの内積、そして反射を表すBSDF関数の積について、半球積分したものだ。半球上のあらゆる入射方向についての総和だ。この理論でいくならば、全テクセルを光源と定義した環境マップにおいては、その半球上に存在する全テクセルについて、ライティングの計算をしなくてはならない。喜ばしいことに、直接光だけの計算で考えるならば環境マップは離散データなので、モンテカルロ法とかそういう手法で頭を悩ませずとも数値積分することができる。