GPU向けのBVH構築の手法

次にこれを読んでいます。

Fast BVH Construction on GPUs, C. Lauterbach and M. Garland and S. Sengupta and D. Luebke and D. Manocha, EUROGRAPHICS 2009
http://luebke.us/publications/eg09.pdf

とりあえずSAHを利用する場合のみ読んでます。
主な並列化ポイントは２点あるようです。１つは、ノード分割を深さ優先ではなく幅優先でデータ並列処理すること。つまり並列可能なノード数は１、２、４、８、…と増えていきます。もう１つは、各ノード内でプリミティブを左右のノードに振り分ける際のSAH計算をデータ並列処理することです。ここでデータ並列に処理するのはプリミティブのほうではなくSAHの境界面です。つまり、SAHを評価する境界面がk個あるなら、k個スレッドを立てて１つずつ割り当てて、各スレッドで全プリミティブを処理します。
気になるのが、ルートノードにおける並列性です。最初の階層ではノード数は１つしかありませんから、並列化が期待できるのはk個のSAHを評価する境界面についてだけです。そしてスレッド数を増やすにつれて良くなるのは計算速度ではなくBVHの品質です。また、Waldの論文では「binの数はだいたい16程度で十分な品質が得られる」との説明があります。つまり「SAHを評価する境界面を16以上に増やしてもBVHの品質が良くなる可能性は低い」と推測されます。
階層ごとの処理時間のグラフでは、階層１、階層２と進むに従い半々に短縮されています。浅い階層のうちは階層が１つ増えたところで総プリミティブはほとんど減らないと思われるので(リーフノードが作られるまではプリミティブが減らないから)、並列可能なノード数が少ないことが結果に直結している形です。

ただ最後にも書いてありますが、このアプローチの場合はAABB-BVH木だけではなくOBBとかk-DOPのような構造に拡張することが容易です。高品質なBVHを作る代わりにレイの探索時間を削減できる可能性は期待できるかもしれませんね。(とはいえ結局シンプルなAABBが単純で速い、ということもあるのですが…)