BKD tree and BIH

by syoyo

Graphics Hardware 2006 と Pacific Graphics 2006 の採択論文が公開され始めています。

http://www.cs.brown.edu/~tor/gh2006.html
(Graphics Hardware 2006)

http://myweb.hinet.net/home7/hks/Papers2006/pg2006Papers.htm
(Pacific Graphics 2006)

どちらもレンダリング関係で日本人の方の採択論文があります。
私もがんばらないと…

さて、GH06 では BKD tree、EGSR では BIH とよばれる、
注目すべきレンダリングのための空間データ構造手法が提案されています。

Sven Woop, Gerd Marmitt, Philipp Slusallek,
B-KD Trees for Hardware Accelerated Ray Tracing of Dynamic Scenes
Graphics Hardware 2006.
(SIGGRAPH 2005 の RPU のひと)

Carsten Wachter, Alexander Keller
Instant Ray Tracing: The Bounding Interval Hierarchy
Eurograpics Symposium on Rendering 2006.

どちらも、基本的にはバウンディングボックスと kd-tree を組み合わせた、
両方のいいとこどりの空間データ構造です。
主に動的シーンのレイトレーシングへの応用ですが、
オフラインレンダラの空間データ構造としても使えます。

BKD(BIH)の利点

  • シンプル
    少なくとも kd-tree に対して。kd-tree では分割面の扱い(共面ポリゴンや、分割面でポリゴンをクリップするかどうかなど)が複雑である。
  • 数値的にロバスト
    kd-tree では分割面で数値誤差が発生しやすいが、BKD ではそれが回避できる
  • 高速な構築
    kd-tree では分割面でポリゴンを分割することによりポリゴン数が増えたりしてしまうが、BKD ではそれがないので in-place なソートが使える
  • 決定的な上限
    BKD では、N 個のポリゴンがあったときに、 正確に N 個の葉ノード、N-1 個の中間ノードが生成される
    (葉ノードはポリゴン 1 個となる)

と、かなりいいこと尽くめです。もしかしたらこれは最強の空間データ構造かもしれません。

BKD の欠点

特に今のところ、既存の kd-tree やバウンディングボックスに対する決定的な欠点というのは私は思いつきません。

リアルタイムレイトレ野郎が集まる ompf.org

http://ompf.org/
http://ompf.org/forum/

では、すでに BKD を実装したひとがいるようですが、それによると、爆発などのポリゴンがばらばらの場合はあまり BKD の効果がないかもという発言もあります。

私も実装してみて試してみたいところです。

それにしても、instant ray tracing の boeing 777(3.5 億ポリゴン、12GB 相当)を 50 MB のメモリでレンダリングできるはすごいですね。1GB のフットプリントが与えられれば 1 時間以内でレンダリングとのこと(ディスク読み込み、空間データ構築時間含む。レンダリング自体は 1 次レイまでのようです)

Advertisements