Syoyo Fujita's Blog

raytracing monte carlo

Month: August, 2006

外国人からのメール

サイトのコンテンツがら、外国人(結構各国)から英語でメールにて質問なりを受けることがときどきあります。メールの文面は、日本人同士がやりとりするのに比べて、各国ともかなり気さくです。

だいたいこんなメールをよくもらいます。


オッス (“オラ ○○”と名乗りすらしない)

MLT のコードほしい。くれ。
あと blog なんだけどさー、オレ日本語読めねーんだから英語で書いてくれよ!
じゃあな!

こんな感じです。

最初のころはカルチャーショックを受けましたが、けっこうこんな感じの文面のメールを受け取るのが続くので、あれ?これがもしかしてグローバルスタンダード?と思うようになりました。

特にエウロパ圏からのメールが多いです。メリケンは半々くらいでしょうか(半分はそれなりに礼儀正しい)。
エイジャ圏はそれなりに礼儀正しーメールがきたりするほうが多いです。
しかし見ず知らずの相手でも Dear なんてメールで始まることは一回しかありませんでした。
始まりはあるとするとだいたい Hi か Hello です。

まあそんな感じで、よく日本人同士が交わすような、


はじめまして ○○さん

私、○○で○○している○○と申します。

貴殿のサイトを拝啓し、○○について質問したく…

って感じのメールを送るのは、逆にグローバルスタンダードからしたら丁寧すぎなのかなーと思ったり。

そんなわけで最近は相手が Ph.D ホルダーだろうと Prof. だろうと誰だろうと、


オッス ○○

テメーの論文みたんだけどよー、そんでオレ実装しようとしたけどよくわかんねー、
あれってこーすればいいの?もしかしてちがう?
よかったら教えて。

じゃあね。

○○  (<- 自分の名前)

という文面でメールを送ることを心がけています。

英語で質問などを受け取ることがある皆さんはいかがでしょう?
やはり皆結構気さくにメールが来るものでしょうか?
そして皆さんも気さくにメールを送っていたりするでしょうか?
(もしかして私だけだったりしたら、日本を貶めていることになるので改めたいところですが…)

BVH-Median, BVH-SAH and BIH 2

BVH-Median, BVH-SAH and BIH

After I wrote above topic, I found still there is a room to optimize(reduce # of tris/ray and # of travs/ray) my BVH and BIH implementation.

BVH: Do packetize the ray traversal and do early hit test and early miss test.
BIH: Do refinement proposed by ompf.org forum members and Use BIH-SAH for the scene having large polygons.

I’ll report the improvement if I did it.

前回ひと段落、と書きましたが、その後もう少し BVH, BIH とも改善の余地があることがわかりました。

BVH: レイをパケット化し、early hit テスト、early miss テストを行う
BIH: BIH-SAH を実装したり、ompf.org で提案されている手法を使ってみる。

BIH については著者に質問してみましたが、そんなにトラバース回数は多くならねーっつの!
テメーの実装おかしいぜ、それ、と叱咤激励!? をいただきました。

たしかにもう少し改善の余地はありそうです。
トラバース回数は BVH に対して、現在の 10-20 倍から H-tree のように 3-4 倍までになるかどうかはわかりませんが、、、(少なくとも BIH は情報として持つ軸が BVH の 1/3 なので、理論的には BVH の三倍以上にはなる)
BIH-SAH を使ってみるのも手ですね。

というわけで、もう少し空間データ構造と付き合ってみたいと思います。

State of the Art in Interactive Ray Tracing

SIGGRAPH 2006 のリアルタイムレイトレのコースノートが公開されています。

http://www.cs.utah.edu/~shirley/irt/

Secondary Ray が新しいでしょうか。
このスライドのレイトレ画像がすごくて、え?まじでこれがリアルタイム?
とビビッたのですが、よくよく調べてみると、

Stoll, Gordon, William R. Mark, Peter Djeu, Rui Wang, and Ikrima Elhassan. “Razor: An Architecture for Dynamic Multiresolution Ray Tracing.” The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-06-21. April 26, 2006. 15 pages.
http://www.cs.utexas.edu/ftp/pub/techreports/index/html/Abstracts.2006.html

が元ネタのようです。

これには 1 フレーム 40-100 秒かかると書いてあります。
それなりにきちんと secondary ray してあのクオリティならやっぱそれくらいはかかるということでしょうか。

しかし SHexp が出た今、low frequency な secondary 効果であれば、
無理にレイトレでやる必要はなくてもう SHexp でいいんちゃう?と思っったりしています。
ただ、SHexp は sphere tree の construction 時間が問題ですね。
(ジオメトリが複雑でなければBVH とかで近似しちゃう手もありそう…)

高速かつ品質の高い(特に tight fit な)sphere tree の構築はまだまだ open な問題でしょうか。
http://lucille.sourceforge.net/blog/archives/000095.html (tight fit shpere tree)
http://lucille.sourceforge.net/blog/archives/000096.html (tight fit OBB)

BVH-Median, BVH-SAH and BIH

BVH を実装してみました。

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

BVH-Median は、spatial median で分割する
Bounding Volume Hierarchy です。いわゆる古典的なバウンディングボックス
階層ですね。BVH-SAH は Surface Area Heuristics を使った BVH です。

これらと、BIH との比較をしてみました。テストしたシーンは
大きなポリゴン(床とか壁とか)を含むシーンです。

buddha_bvh_rendered.png
(color shows object normal)

Happy buddha scene(10 K triangles)
BVH-Median : 4.38 tris/ray,  41 travs/ray
BVH-SAH: 4.37 tris/ray, 27.68 travs/ray
BIH: 2.58 tris/ray, 579.56 travs/ray(too much traversals…)

sponza_bvh_rendered.png

Sponza scene
BVH-Median : 32.18 tris/ray,  273.18 travs/ray
BVH-SAH: 31.48 tris/ray, 198.79 travs/ray
BIH: 25.65 tris/ray, 2416.52 travs/ray(too much traversals…)

tris/ray は一レイあたりの三角形との交差判定数、travs/ray は一レイあたりのノードのトラバース数です。
相変わらす BIH のトラバース量はちょっと多すぎです。

交差判定数は BIH のほうが少ないですが、BVH はまだあまりトラバースを最適化していないため、
最終的には BIH と同じくらいになるかと思います。

Havran の H-tree の paper を見ましたが、やはり巨大なポリゴンがある場合は、
H-tree は BVH に比べてトラバース数が 2-3 倍ほどになっています。

やはりここらへんはポリゴンを分割しないかぎりしょうがないようです。

というか、H-tree の paper の結果を見ると、
結局のところ古くからある古典的なバウンディングボックスが一番良い結果を出しています。
個人的にはバウンディングボックスはあまり効率的ではないと思っていたのですが、
この論文の結果や実際に自分で実装した結果を見ると、BVH が結構いい結果を出しているので以外でした。

下手に難しく考えずに、素直な方法が一番ということでしょうか。

とりあえずはオフラインレンダラに組み込む空間データ構造は、
一様グリッドで軽くボクセル化 + ボクセル内は BVH-SAH or BVH-Median というのが
個人的に一番の解です(実装も kd-tree よりも簡単ですし数値的にも robust ですし)。

これでひとまず空間データ構造については一通り調べて自分で納得のいく結果が出たので、
レイトレ用の空間データ構造の調査はこれで終わりにし、次なるレンダラの機能の調査に移りたいと思います。
Sequential Monte Carlo や Adaptive AntiAliasing、分光・偏光あたりをまずは埋めていきたいです。

the 2006 IEEE Symposium on Interactive Ray Tracing

http://www.sci.utah.edu/RT06/organization.html

世界初(?)のレイトレ学会の論文のリストが公開されています。

Kd-tree の構築方法がアツそうです。
importance sampling のセッションはタイトルだけみるとあまりインタラクティブレイトレと
関係ない気もしますが… オフラインにも使えるようだったら吸収していきたいところです。

リアルタイムレイトレ野郎同士は惹かれあうというのは本当だったんだ…

BIH の初期実装後、ompf.org の forum

http://ompf.org/

の BIH スレッドをよくよくしっかり読み始めたのですが、、、

あー、すげーなー、
アツい野郎どもばっかです、、、

やれ、
俺も BIH を実装したぞー, toxie!! とか、
どうやったら BIH のパフォーマンスアップするんだオラオラー、toxie!! とか、
ついに kd-tree の 97% まで追いついたぞー!! とか、
なんか論文のここがよーわからん、教えろ!! とか、
BIH の著者 toxie は toxie で、 SAH/kd-tree はその手法を使うヤツはそれを “聖杯” だと思っていやがる!
違うね! SAH/kd-tree はもう死んでいる! BIH サイコー!BIH 使わねーやつはアリーデ・ヴェルチ!(さよならだ)
とか言っていたり、、、、

うーむ、すごいなぁ…
あと自分の BIH の実装もまだまだ改善の余地があると思いました。
(large polygon 問題はそんなにとりあえげていないみたいですが…)

というか sunflow レンダラや pane レンダラのひとも参加しているのね。