レイトレを幅優先探索でGPUで処理するっていう論文
読み終えたので、忘れないようにメモ書きしておきます。GPUによる、高い並列性を持つレイトレーシングの手法の一つです。
Fast Ray Sorting and Breadth-First Packet Traversal for GPU Ray Tracing, Kirill Garanzha and Charles Loop
http://research.microsoft.com/en-us/um/people/cloop/garanzhaloop2010.pdf
レイのソート
このステージでは、メモリのコヒーレンシーだとか探索における分枝を減らすために、入力された大量のレイをソートします。
レイの原点と方向について仮想グリッドで離散化してハッシュ値を求め、ハッシュ値でソートします。このとき、ハッシュ値配列をソートする前後にランレングス圧縮と展開を導入します。もともとハッシュ値配列はほぼ整列されていますので、予めランレングス圧縮をかけてからソートしたほうが高速であるようです。とはいえ圧縮展開も無コストではないので、ここにも並列化向けの工夫がされているようです(SENGUPTA S., HARRIS M., GARLAND M.: Efficient parallel scan algorithms for GPUs 参照)
フラスタムの構築
このステージでは、ソートされたレイのリストから、コヒーレントなものを束ねて、フラスタムのリストを作ります。
フラスタム1つが含むレイの数は、だいたい128〜512といったところであるようです。当然、シーンにより最適値は変わります。
BVH幅優先フラスタム探索
「大量のフラスタム vs 大量のノード」という処理を、階層0、階層1、階層2、…とどんどん深く処理していき、最後の層になるまで続けるようです。
- フラスタムがあるだけ、(フラスタム,ルートノード) のペアの配列を作ります。(なので、かなりの数のペアが作られます)
- 全てのペアについて、フラスタム vs ノードの子供のAABB で衝突判定し、衝突した（フラスタム,子供ノード）のペアの配列を出力します。
- 最下層でないなら、次の階層へ行くために、出力された配列を元にして2へ戻ります。
- 最下層であるなら、出力された配列は（フラスタム,葉ノード）のペアの配列ですので、そこで終わります。
局所衝突判定
ここでフラスタムを展開して、レイと三角形の衝突判定を行います。
