Syoyo Fujita's Blog

raytracing monte carlo

Month: July, 2006

Efficient Selective Rendering of Participating Media

Oscar Anson, Veronica Sunstedt, Diego Gutierrez, Alan Chalmers
Efficient Selective Rendering of Participating Media
Symposium on Applied Perception in Graphics and Visualization 2006
http://www.cs.bris.ac.uk/home/veronica/research.html

selective_participating.png
(ちなみにこれは写真です。participating media の効果を示しています)

XS-map というマップを利用して、participating media のサンプリングがより必要な部分を選択的にサンプルすることで、最大 10 倍高速に participating media をレンダリングするという手法。

しかしより注目すべきは、興味深い participating media の知覚解析が行われている点です。
近似のレンダリング画像が、リファレンスのレンダリング画像に対してたとえ 1% の誤差であっても、
それらはほとんど区別が付かないというとそうではなく、知覚的な観点からは十分区別できうることを
報告しています。

これにはちょっと驚きです。論文が行った知覚テストがどれだけ reliable なのかはさておき、
仮に 1 % の誤差でも十分知覚的に異なるということは、きちんとしたレンダラにとっては
テキトーに participating media を処理するするわけにはいかなくなるということです。

映画などでの volumetric 効果を見ていると、特に霧みたいに low frequency な効果では
結構 CG っぽさを感じるときが、思い起こしてみるとあったりしたような気がするのですが、
それはこの論文が指摘することが一因として関与しているからなのかもしれませんね。

lucille では今のところ volume 効果はサポートしていませんが、将来的には組み込みたいと
考えています。volume のレンダリング品質をしっかりしたものにしようとなると、
きちんと処理しないといけなくなるようです。

Advertisements

My initial BIH implementation

This is my initial BIH implemetation.
BIH を実装してみました。

http://lucille.atso-net.jp/svn/angelina/spatial/bih/

今回はトラバーサルも込みです。BIH の欠点を見つけました。
それは、大きなポリゴン(1 枚のポリゴンでできた床とか)があると、
トラバーサルのコストが wost case の O(N) になってしまうことです。

いくつかのシーンでテストしましたが、ここでは 1 万ポリゴンの happy buddha のシーンを取り上げます。

BIH ツリーの統計は以下の通り。

=== BIH tree statistics ============================
nNonEmptyLeaves : 7377
nEmptyLeaves    : 0
nBifurcations   : 7376
maxDepth        : 19
nTriangles      : 10002
maxTris/leaf    : 26
aveTris/leaf    : 1.355836

床なし版 

bih_noplane.png
 
 nRays            = 65536
 nCandidateTrianglesToTest = 5173440 (78.940430 tris/ray)
 nActuallyTestedIsectTris = 181236 (2.765442 tris/ray)
 nFailedIsectTris = 5153594 (78.637604 tris/ray)
 nTraversals      = 12986098 (198.152130 trav/ray)

スクリーンショットはレンダリング結果です。色は法線を出しているだけなので、特に意味はありません。
実際にテストした三角形の数は 2.7 tris/ray と、交差判定数ではかなり理想値に近いです。
(背景では 0 tris/ray なので、実際の可視部分ではもう少し増えますので 5 tris/ray くらいでしょうか)

トラバースの回数は結構多いです。しかしパケットトラバースなどすれば、実際には 1/4 – 1/10 には減るでしょうか。

床(2 polygon で構成)あり版

bih_show_split.pngbih_with_plane.png
 nRays            = 65536
 nCandidateTrianglesToTest = 444096622 (6776.376678 tris/ray)
 nActuallyTestedIsectTris = 1539230 (23.486786 tris/ray)
 nFailedIsectTris = 444042139 (6775.545334 tris/ray)
 nTraversals      = 656813420 (10022.177429 trav/ray)

はっきり言ってありえません。ほぼ全レイが worst case のトラバース量になっています。
レンダリング時間もアホみたいに遅くなりました。
(あと、床なし版は 90 度回転しているので、法線色が床あり版と異なっています)

ある意味これはしょうがないことで、巨大なポリゴンがあると、
シーンのバウンディングボックスのインターバル区間 = そのポリゴンのインターバル区間
となり、いくら細分割したところでインターバルが狭くならず、ほぼすべてのツリーをトラバース
しなければならなくなってしまうためです。
また今回さらに悪いのは、ツリーの最初の分割面が床に垂直になっていますが、
ここで切ると、床ポリゴンの一枚は手前に、もう一枚は奥に割り振られてしまい、どのレイもルートの両方の子ノードをたどらなければならなくなってしまうことです。

論文では、このような巨大なポリゴン問題があることを認めていますが、

「我々の手法はプロダクション向けを考えている。プロダクションでは、そんなローポリなシーンなんてつかわねーんだよ。バリバリディスプレースメントマップ使うから、そんなケース(一枚の大きな床ポリゴン)なんて生じねー。だから問題ないね。」

と説明しています。これは正直賛同しかねます。オフラインやプロダクションでしたら、どのような入力シーンにも対応できるべきですから。
(少なくとも mental images の技術顧問?っぽいことをしている Alexander Keller が言う言葉ではないと思うのですが、、、それとも mental ray 使いは皆、バリバリディスプレースメントマップ使ったハイポリシーンを使うのがデフォルトなのでしょうか?)
あと、この問題が実は wost case のトラバーサルコストになることも書かれていないのも問題です。

デザイナやプログラムがあらかじめポリゴン分割をするという前提では、BIH はよさそうです。
リアルタイムレイトレでは、うまくツリーが構築できるように結局シーンをいじるでしょうし。

しかしオフライン用途では、シーンの構成によっては worst case のトラバースがほとんどになってしまうという状況はちょっと使い物になりません。BKD も同じ問題を抱えていますが、こちらは分割面の選択により自由度があるため、もう少し問題は緩和されそうです。
(BIH では単純に最も長い軸を二分、としていますが、これが今回のような条件では問題になる)

うーん、やっぱりまずは軽く一様グリッドで切りボクセルトラバースを行い、各グリッドセルでは BKD or BIH を使うという手法がやっぱり一番よさそうでしょうか。

それとも H-tree ならなんとかしてくれるでしょうか。こちらも実装してみたいですね。

V. Havran, R. Herzog, H.-P. Seidel: “On Fast Construction of Spatial Hierarchies for Ray Tracing”,
http://www.cgg.cvut.cz/~havran/

10 月 26 日

発売日: 10 月 26 日(木)
プラットフォーム: PS2
ジャンル: 波紋疾走(オーバードライブ)アクション

ゴゴゴ… ゴゴゴ… ゴ…ゴゴ…
うぉおおおおおおおおおおおお!!!
ついに発売日が決定!!!

10 月まではがんばろうと思いました。

My initial BKD tree implementation

bkd_test.png

BKD ツリーを実装してみました。まだ構築だけできたというレベルで、実際にレイをトラバースしてうまく動くかはこれからです。
Here is my initial BKD tree implementation.

 

http://lucille.atso-net.jp/svn/angelina/spatial/bkd/

http://lucille.atso-net.jp/svn/angelina/spatial/bkd/bkd.exe
http://lucille.atso-net.jp/svn/angelina/spatial/bkd/cornellbox.obj
(demo binary + scene file. put them in same directory to run the demo)

オリジナルでは SAH(surface area heuristic) を使っているようですが、
とりあえずは簡潔のために object median で分割するようにしました。
アルゴリズムはこんな感じです。
I use object median for simplicity. the following is the algorithm.

1. バウンディングボックスが 2D なら、(3) に進むが、そのときテストする軸は他の 2 軸(幅のある軸)のみとする。
2. 軸並行(x, y, z)なポリゴンがあれば、その位置で分割を試みる(3 軸すべてをテスト)
2.1. 軸並行なポリゴンの位置と分割面が同一であるので、軸並行なポリゴンをどちらに分けるかが問題となる。今回はノードのバウンディングボックス(bmin, bmax)とポリゴンの位置を比較し、距離が近いほうにポリゴンを振り分けました。
2.2 どちらかの子ノードに振り分けられるポリゴンの数がゼロなら、分割失敗。三軸テストしてすべてダメなら、次のテストに進む
3. object median で分割を試みる(三軸テスト)
4. すべてでダメなら、あきらめて葉ノードをつくって終了(1 葉ノード 1 三角形にはならない)
5. 子ノードを 1 から繰り返す。

こんな感じです。

あと、実装していく過程で、いくつかうまくいかない(分割が難しい)ケースを見つけました。

split_bbox.png
この左のような二つの三角形。三角形の bounding box(中央や右) を分割面の候補にしたり、spatial median で分割しようとすると分割できない。
For such two triangles(left), it couldn’t split with spatial median using triangle’s bounding box.

split_objmedian.png
ポリゴンの重心を使えば、object median を分割面とし、ポリゴンの重心で左右どちらかに振り分けることが可能。
Using object median, it could be splittable.

ただ、object median だけだと、これまたうまくいかないケースがあり、

same_center.png
このように重心が重なっていると、分割面と物体の重心が重なってしまうので object median だけでは分割できません。このときは spatial median のときのように、
In such a case, object median == center of triangle. it can’t splittable.

split_aabb.png

分割面をポリゴンの bounding box + ポリゴンの重心で振り分け、もしくは
分割面はポリゴンの重心 + ポリゴンの bounding box で振り分け、とすることができるでしょう。
Use object median for split candidate and triangle’s bounding box to classify.

まずはポリゴンの bounding box を分割面の候補としてテスト、だめなら object median を分割面の候補にしてテスト、とするとよさそうです。

また、軸並行なポリゴンは最初にそのようなポリゴンが見つかったときに、そこで分割するようにしていますが、
複数の軸並行なポリゴンがある場合、なるべく断面積が大きくものや、ノードの bounding box の端に近い
ものを優先的に選ぶなどするとより高品質なツリーが構築できると思います。

さて、BKD ツリーは構築が高速であるというのがとりえだったような気がしますが、
なんか結構普通の kd-tree のようにめんどうな手続きになってしまいました。
オンラインの場合はある程度シーンを作るときに変な形状を取り除くでしょうから上記のような
特殊なケースを考えなくともよいかもしれませんが、
オフラインレンダラでの利用となると任意のポリゴンシーンでも安定して構築できなければならなくなりますので、
いろいろ特殊なケースに対応できるようにしないといけません。

それでも、kd-tree に比べて、bkd tree は数値的にロバストであったり、構築が高速になるなら、
利用してみる意義はあると思います。

BKD tree and BIH

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 次レイまでのようです)