Highly Parallel Fast KD-tree Construction for Interactive Ray Tracing of Dynamic Scenes

by syoyo

Highly Parallel Fast KD-tree Construction for Interactive Ray Tracing of Dynamic Scenes,
Maxim Shevtsov, Alexei Soupikov and Alexander Kapustin.
EUROGRAPHICS 2007.

[En]

http://graphics.cs.uni-sb.de/Courses/ss07/sem/index.html

When I posted the article about “stackless kd-tree traversal” [1], I felt `kd-tree has no future’.
But I must take back what I have just felt and I have to say `kd-tree is still alive’.

The presented method in Intel’s kd-tree paper is mainly about fast SAH evalution,
thus it is not limited to kd-tree spatial data strucutre.

I think proposed method could be easily adapted to BVH or BIH method,
and more if it is combined with selective reconstruction [2], there might become
the fastest dynamic raytracer in the world(as of 2007).

[Ja]

kd-tree の構築が遅くて、kd-tree を動的シーンのレイトレに使えないのなら、
構築そのものを早くすればいいじゃない、というなんとも漢気な論文。

基本は SAH(Surface Area Heuristics) で分割面位置を求める計算を、
Havran の手法をベースに高速化して、並列化もしやすいようにしたよ、というもの。
近似手法なので、最適に構築された kd-tree に比べれば fps は 70% ほど落ちるものの、
構築時間は既存手法に比べて 100-300 倍を実現しています。

4 cores 使っているとはいえ、1000 万ポリゴンの Thai Statue の kd-tree 構築時間が
2.5 secs とはすごいなぁ…

タイトルでは kd-tree とありますが、提案している手法は SAH 計算の高速化なので、
これはそのまま SAH-BVH, SAH-BIH にも持っていけると思います。

提案手法によりこれだけ構築時間が高速されたとはいえ、やはり私としては kd-tree には未来を感じないので、
BVH ベースに本手法を適用したほうがよい結果を得られるような気がします。

Intel もそれなりにレイトレに投資しているようですね。

現状、GPU と比べてリアルタイムレイトレは destuctive innovation になりつつあるのかもしれません。
しばらくはまだまだ使いものにはならないでしょうが、ラスタライザでごにょごにょよりもリアルタイムレイトレの
ほうが将来性がありそうです。

[1] Stackless KD-Tree Traversal for High Performance GPU Ray Tracing
http://lucille.atso-net.jp/blog/?p=300

[2] Ray Tracing Dynamic Scenes using Selective Restructuring
http://lucille.atso-net.jp/blog/?p=298

Advertisements