レイトレ合宿7 徒競走でやったこと

はじめに

今回のレイトレ合宿では、イベントの一環として BVH の構築/交差判定を高速化する徒競走というイベントが行われました。今いる会社的なあれで高速化に詳しくなりたいというのもありましたが、やってみるとこれがかなり楽しくて、 本題の CG 作品の提出を忘れて 取り組んでいました。そこそこ勉強込で時間をかけたので、何とか忘れないようにやったことを記したいと思います。

実際のソースコードこちら になります。
ソースコードの規約が統一されていなかったり、部分的におかしなコードがあったりしますが、昔書いたコードを必要最低限の改変で持ってきたりしてたので、許して下さい。

ルールは、BVH の構築 + 交差判定の時間が短い人の勝ちです。

とりあえず、効果が 0 でなさそうな、やったことの概要を記すと以下のようになります。
抜け漏れはあるかもしれません。あと、どうやらどこかがバグっているらしいのですが、特定できていません…

やったこと

3次元ベクトルを Expression Template 化

ソースコード

最初、SIMD 化もされていないコードだったので、BVH 構築/交差判定両方で一時オブジェクト作成を削減するためにやりました。最終的に、交差判定ではどのみち一時オブジェクトは作成されないので、最終的な貢献度は薄かったかもしれません。今見ると、きちんと作ろうとして途中で投げ出した後があって面白い。

ポリゴンの当たり判定を正規化した空間でやる(名前がわからない)

ソースコード

Polygon の当たり判定も、もっと速い方法絶対あるだろーと思って色々ググった結果、この記事 に行き当たりました。仕組みは割と簡単で、三角形を (0, 1, 0), (0, 0, 0), (1, 0, 0) の空間に写してから当たり判定するというものです。手元では、そこそこ効果があったように見えたので、採用しました。

三角形をなさない polygon の除去

ソースコード

本来は高速化の意図ではありませんでしたが、上記のポリゴン当たり判定方法を採用すると、obj の一部で nan を吐きまくったため、抑制のために入れました。誤差とはいえ、多少は影響あったかもしれません。

Top Down な SAH ベースの BVH の並列構築

ソースコード

この記事 を色々眺めた結果、とりあえず知ってるやつをやろうということでこうなりました。構築は Task Queue を使って並列化しました。詳細はアドベントカレンダーの記事 に書いたので、興味があれば見てもらえると嬉しいです。

std::stable_partition を使った O( n log n ) 構築(nはポリゴン数)

ソースコード

この内容は、 Bonsai の論文 で知りました。

TopDown SAH ベースの構築をする時、(僕の理解が間違っていなければ) polygon id を管理する配列を x / y / z 軸の3つ分用意し、 x / y / z 軸のそれぞれで sort した状態を保持します。 node を left / right で分けた時、この polygon id の配列を left / right の子ノードの分に分離しつつ、それぞれの子ノードの中では x / y / z 軸で sort されている状態を保ちたいです。
例えば x 軸で bounding box を 2分割したとすると、x 軸分の polygon id の分割は容易です(あるしきい値より左が left, 右が right なので)が、y / z 軸については left / right にいるべき polygon id がごちゃごちゃしているので、これを std::stable_partition を使って分離します。x 軸の polygon id list を見れば、「特定の polygon id が left / right にいるべき」というのは容易にわかるので、各 polygon が left / right のどちらにいるべきかフラグを持たせておき、 y / z 軸の polygon id を std::stable_partition で振り分けます。この時、stable 付きのものを呼ぶと、「 left どうし、right どうしの polygon ID の順番は元の配列のソート順を保つ」という性質があるので、y / z 軸で sort された状態も保つことが出来ます。

8分木の構築 + Node の当たり判定 8並列

ソースコード(2分木の展開)
ソースコード(8 並列 intersect)

定石がよくわからなかったので、2分木を作ってから展開して8分木にしました。
node の当たり判定については、reference 実装のものをそのまま SIMD に描き起こした感じなので、もうちょっと工夫が出来たかもしれません。

8 並列当たり判定で交差した node を効率的に抜き出す

ソースコード

この技術的課題は、この論文で知りました。

8 並列で node の当たり判定をした後、距離順に sort して 子ノードの traverse 順序を決めたいのですが、8要素のソートは重いので、交差した個数に応じて sort を分けるのがいいと記載がありました。これを実現するためには、交差した部分の index はどれかを高速に特定する必要があります。
ここで、「子ノードの bounding box との距離が INF でない bitmask を作成して、bitmask の位置にある index を 右詰めして抜き出す」という処理だと思うと、 pdep / pext 命令が使えることに気づきます。ざっくり書くと、

  1. 入力:1bit x 8 の bitmask当たり判定結果
  2. 8bit x 8 の bitmask を作成する
    • pdep で 8bit おきに bit を配置するように設定し、0xFF をかけて作る
    • avx512 でも大体似たような感じでいける
  3. 0x0706050403020100 は、64bit の数字に index を埋め込んだもので、ここから ↑の bitmask に被るところを pext で右詰めして保存
  4. 3.で作られた整数は実質 8bit integer なので、32bit interger に拡張して store
  5. 何個当たり判定したかは、入力の popcount を数える

みたいな感じになっています。この処理も参考にしたブログがあったのですが、メモに残っていませんでした。
なお、肝心のソート用関数を個数に応じて使い分けるのは、あんまり速くならなかったので、詰めた後は std::sort してます。

Polygon の当たり判定 8並列

ソースコード

これは本当に 1行ずつ SIMD にするだけ。

Polygon の(メモリ配置的な)並び替え

ソースコード

index の間接参照みたいなのを減らすためにやりました。バグらせるのが怖かったので愚直に配列作る + copy をしました。
こういうのが他にも複数あるので、多分構築は遅かったと思います。

(補足)やったけど、効果がなかったやつ(上2つはバグってた可能性大)

Bonsai

構築が明らかに遅かった+改善の余地があったので、とりあえず Bonsai しておけばいいだろうと思って実装したのですが、部分的に手抜きして作ったせいかめちゃくちゃ交差判定が遅くなり、時間切れで諦めました。今回唯一悔やまれる点があるとすると、これのきちんとした実装が出来なかったことだと思います。

insertion based optimization

論文

見た瞬間、これはやりてぇと思って実装しました。が、何か思うように速くならず…かつ、論文とか見ると結構構築が重そうで、終了判定タイミングも結構難しいなと思ったので、優先度をそこそこ落としてしまいました。

AVX512 化(16分木 + ポリゴン 16並列当たり判定)

ほとんど AVX2 の命令を移植するだけでしたが、AVX512 では bitmask が一部 __mmask16 のように圧縮されている形式だったので、その扱いを少し変える必要がありました。手元では全然速くならなかったので、結局諦めました。

SIMD の bitonic sort

ソートが遅いということで、子ノードの交差個数が多かったらこっちの方が速いかもなーと思って実装はしてみました。やっぱり交差するノード数の期待値の問題なのか、多少調整しても速くなったか微妙だったので、やめてしまいました。

intersectAny で leaf node を優先して当たり判定

シャドウレイを飛ばす場合などでは、 polygon に 1つでも当たったら終わりなので、距離よりも当たりやすさを優先すべきだよなぁと思っていました。というわけで、Leaf Node に当たったらそっちを優先的に調べることにしていたんですが、比較条件が複雑な割に改善ケースが少ないせいか、遅くなってしまいました。

開発過程でやったこと

visual studio のプロファイラを眺める

大体ボトルネックは全てこれで把握していました。途中 inline 展開された部分の把握が不可能だったので、もうちょっと何とかならなかったものか。

途中まで SIMD 化して残りを愚直に実装する

SIMD の処理を最初から最後まで書くと大抵 100% バグっていたので、「途中まで SIMD で書いて残りは愚直に書く」をして、愚直をどんどん減らすような方針で書いていきました。

intel intrinsics guide をざっくり眺める

https://software.intel.com/sites/landingpage/IntrinsicsGuide/

そもそも自明じゃないテーマで本格的に SIMD 高速化をするのが初めてだったので、とりあえず何ができるのかをざっくり把握することをやりました。1個ずつというのは到底出来ないので、カテゴリごとに似たような命令はすっ飛ばして、雰囲気を感じていました。

BVH の validator をたくさん書く

ソースコード

BVH の構築後に色々データをいじりまくっていたので、一度バグりだすと何が原因なのか特定するのは難しいです。この時、処理における事前条件/事後条件を書き出して、処理する度にチェックするコード debug build で入れてました。かなり役立ち度は高かったように思います。

開発過程でやらなかったこと

cache miss のプロファイルをとる

これは本当はやりたかったのですが、 VS 2019 でやる方法がわからず。わかる人がいたらぜひ教えて欲しいです。

BVH の visualizer とか評価尺度を見て考察する

割と定数倍高速化をしてたら終わってしまったので、BVH の構築は top-down SAH のものからほとんど進歩していませんでした。もうちょい構築の工夫を入れてたら、 SAH とか体積とか当たり判定の分布とかを真面目にとっても良かった気がします。

UT を書く

reference 実装がきっちり与えられていたので、あまり必要ではありませんでした。今回は validator があれば大体問題なかったような気がします。

最終的な速度

正確に計測するのは大変なので諦めましたが、本番環境(CUI 版) + 本番データセットの hairball で 3回計測したときの中央値を取ると、最初と最後でこれ位の差がありました。あと、embree みたいな現状最強格のやつとも比較したかったのですが、使い方がよくわからなかったので諦めました。まぁこれだけ速度差があるといっても、バグを修正しないと何とも言えないよなぁという気持ちはあります。

build(ms) intersect(ms)
reference 9,491 202,253
最終版 7,660 9,500
速度比(ref / 最終版) 1.24 21.29

終わりに

振り返ってみると、これは本当にレイトレ合宿の参加記なのかという気持ちになってきました。とはいえ、こうしてまとめてみると、意外と頑張ったなという気持ちになってきたので、とりあえずは良かったかなと思います。初めてガチで最適化を頑張ってみましたが、同じ言語でも、これだけ違うんだなぁみたいな感慨深さはあります。

来年こそは、綺麗な絵+CUDA を頑張りたい気持ちです。