技術

パケットトラバーサル

例のGPUレイキャストのコードをパケットトラバーサル化してみた。

ptimage
結果。といっても以前の結果と比べて見た目的には左右逆になってたのが治った以外の違いはない。

大きく分けて、BVHで分割したポリゴン(のAABB)をトラバーサルするトラバースフェイズと、トラバースにより暫定的に確定したポリゴンとレイの交差判定を行う交差判定フェーズの2つのフェーズから成っているが、今回変更したのはトラバースフェイズのほう。
レイごとに処理していたトラバースフェイズを、いくつかのレイをまとめて作成したフラスタムごとに行うようにした。
レイは64本ずつまとめるようにした。

変更前と変更後の速度差
Geforce 9400M(Mac) 約0.5秒 → 約0.17秒(約2.9倍高速化)
Geforce GTX 460(Ubuntu) 約0.027秒 → 0.009秒(約3.0倍高速化)

かなり速くなったけど、ほんとはもっと速くなると思ってた。
フラスタムは、法線と原点からの距離で表される平面4つ分(float4 4つ分)で表現してて(なのでフラスタムというよりは底面がない四角錐だけど)、その分のメモリアクセスが余分に発生してるのと、やはりフラスタムとAABBの交差判定がレイとAABBの交差判定より重いせいだと思う。
あと、フラスタム単位でトラバーサルしてるので余分なレイ-ポリゴンの交差判定が発生してるってのもあると思う。

この辺はパケットトラバーサルの宿命なので、劇的に改善する事は不可能だと思うけど、まだ実装が効率的じゃない部分があると思うのでそのあたりを修正すればまだ多少は速くなるはず。

ちなみに、まとめ具合は16, 32, 64本の3パターンで試したけど64本が一番はやく、小さい方から順に1.5倍ぐらいずつ速くなった。
64本より上に関しては、一箇所定数を書き換えるだけでは対応出来なかったので試してないけど、さらに速くなる可能性は高いと思う。
もちろんシーンの複雑さによって最適なまとめ具合は変わると思う。

今回はパケット化しやすい一次レイのみを扱った。
もっと汎用的に、位置や方向がバラバラなレイをパケット化するためには、レイをハッシュ化してソートしてコヒーレンシが高い物同士を自動でまとめる処理が必要となる。

コメントを残す

メールアドレスが公開されることはありません。



※画像をクリックして別の画像を表示

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください