Syoyo Fujita's Blog

raytracing monte carlo

Month: June, 2006

Interactive Distribution Ray Tracing

Solomon Boulos, Dave Edwards, J. Dylan Lacewell, Joe Kniss, Jan Kautz, Peter Shirley, Ingo Wald
Interactive Distribution Ray Tracing,
Technical Report, SCI Institute, University of Utah, No UUSCI-2006-022, 2006

Although utilizing Sudoku for sampling pettern is something new,
1. Have Sudoku-tiling lower discrepancy for its sampling distribution?
I could see some sample points are too near around the tile border for fig 15.
2. The paper shold compare othor sampling methods such like AK’s paper or [2]. 

基本的にリアルタイムレイトレを拡張して、分散レイトレーシング [1] を行おうというもの。
16 コア相当の複数マシンでのレンダリングで、オリジナルの分散レイトレーシングの画像を
2-3 フレーム / 秒でレンダリングできるそうです。

この論文の一番の contribution は、サンプリングパターンにラテン超方挌法ではなく、
数独のパターンを利用した数独タイリングを用いたという点です。

発想は面白いのですが、よくよく論文の数独タイリングのパターン(fig 15)を見てみると、
タイルのボーダーあたりにあるサンプリング点が近接しあっていて、
少なくとも fig15 においては、discrepancy の観点からは最適ではないことが分かります。
(とはいえ、実際のレンダリングでは、理想的な discrepancy を持つ
サンプリングパターンよりも、数独タイリングのように、
すこしくらいずれているほうがよい結果を出すのかもしれません)
いずれにせよ、Hammersley パターン以外のサンプリングパターンとの
比較や収束はどれくらいなのか、きっちり計測してほしいところです。
(たとえば [2] との比較とか)

まあでも Recursive Wang tiling を Sudoku で置き換えた
Recursive Sudoku tiling とかできたらそれはそれで面白いかも。

ところで、分散レイトレでは基本的には N 次元サンプリング点が必要になります。
(本来であれば N 次元での数独タイリングを考案してほしかった)
これについては、最近、

F. Panneton and P. L’Ecuyer,
Infinite-Dimensional Highly-Uniform Point Sets Defined via Linear Recurrences in F_{2^w}
Monte Carlo and Quasi-Monte Carlo Methods 2004, H. Niederreiter and D. Talay eds., Springer-Verlag, 2006, 419-429.

という論文に注目しています。基本的には WELL のように、2^w の有限体上での線形再帰による手法なのですが、どれくらい無限次元でも一様に分布するのか気になります。Alexander Keller の提案する、
「(特に CG の世界において)良い discrepancy の定義は、各サンプリング点からのお互いの距離が一定かつ最小(最大でも同じことですが)であることである」
という感じなことを基準とした discrepany の定義に当てはめても、本手法はよい分布になるようです。
実装して試してみたいのですが、初期ベクトルの値がどれがよいか書いてないみたいなので、ちょっと pending 中です。

[1] 複数台のマシンで並列計算でレイトレーシングを行うのは distributed ray tracing と呼ばれます。
しかし Cook らのオリジナルの分散レイトレーシングの論文タイトルは distributed ray tracing であるので注意です(俗に、料理人・配送屋・大工連盟による論文と呼ばれる)。
[2] Samuli Laine and Timo Aila.
A Weighted Error Metric and Optimization Method for Antialiasing Patterns.
Computer Graphics Forum 25(1), 2006

SIGGRAPH Fastest forward paper preview

○○・○ー○も○○○○○ー○○も終わってしまって、これから○。○。以外になにを
糧にして生きていけばよいのか悶々としたので、
SIGGRAPH 開催前の 7 月くらいに、世界で最も早い? SIGGRAPH Fastest forward paper preview を開催したいと考えています。

SIGGRAPH 2006 に行けないひとは、これで行ったつもりになれるでしょう。
SIGGRAPH 2006 に行くひとは、本チャンでの Paper セッションのプレゼンが分かりまくりになるでしょう。

つまるところ、今年出た論文の有志による紹介です。
その道の専門のひとたちによる解説になる予定ですので、
日本(語)では最も信頼された解説になると思います。

ただ、場所(都内)の確保が調整中なのですが、最悪遂行不可になるかも。
そのときはごめんなさい。

詳細は SBR 2006 のページに告知してありますので、
そちらをご覧ください。

Adaptive Visibility-Driven View Cell Construction

Oliver Mattausch, Jiri Bittner, Michael Wimmer
Adaptive Visibility-Driven View Cell Construction
EGSR2006.

avdvc.jpg
2D で見た、生成された視野セル。
ビジビリティを考慮してうまくセルが構築されているらしい。

自動で PVS(portal) のセルを生成してくれる手法。
ゲームなどでは、この portal 用のセルの生成は
level editor などで手作業で行うことが多いかと思いますが、
これを自動でやってくれるというのは便利ではないでしょうか。
(とはいえある程度自動でやってくれるソフトもあった気がします)

既存手法ではあるセルから見える PVS(Potentially Visible Set, 見えちゃうかも集合)
を計算するのは多くあったが、セルそのものを見つけ出す手法については
ほとんど研究されてこなかったと論文では述べられています。

アルゴリズムとしては、

  1. ビジビリティのサンプリング
  2. 空間の分割
  3. 空間のマージ

となっています。ビジビリティのサンプリングに関しては、
基本的にはランダムな手法を用いていますが、
Guided Visibility Sampling と組み合わせるとよりロバストな
推定ができるのではと思います。

また、リアルタイムレイトレーシングにおいて、
シーン全体に kd-tree を構築するのではなくて、
このような手法を作って PVS + セル内部は kd-tree、
というような目的にも使えるかと思います。
特に本手法は前処理でビジビリティも計算するので、
そのようなビジビリティサンプリングの結果を利用した
kd-tree の分割面決定にも応用がありそうです。
(現在 kd-tree にて良く使われている SAH(surface area heuristic) による
分割面決定アルゴリズムは、ポリゴンの面積と tree node の
バウンディングボックスしか考慮していない) 

論文 abstract 日本語訳

視野空間を多重レベルの視野セル(view cell)へと自動で分割する新しい手法を提案します。

平均レンダリング時間を最小化するために、コストベースのモデルを利用します。
既存手法とは異なり、我々のモデルはシーン内の実際のビジビリティ(visibility, 可視情報)を考慮します。また、分割はシーンジオメトリの平面に制限されることはありません。

生成された視野セル階層が各種シーンでも問題なく動作し、また既存手法よりも低い平均レンダリング時間となることを示します。

Making Radiance and Irradiance Caching Practical: Adaptive Caching and Neighbor Clamping

Jaroslav Křivánek, Kadi Bouatouch, Sumanta Pattanaik, and Jiří Žára
Making Radiance and Irradiance Caching Practical: Adaptive Caching and Neighbor Clamping
EGSR 2006.
http://moon.felk.cvut.cz/~xkrivanj/

より実践的な放射照度キャッシュおよび放射輝度キャッシュ手法の提案です。

オリジナルの Ward の放射照度キャッシュ

http://radsite.lbl.gov/radiance/papers/sg88/paper.html

は、実際には実装してみると、photonmap 本のようにきれいにはいかず
壁のまわりでしみのようなアーティファクトが現れたり、
まず放射照度キャッシュを計算するパスと、その後の補間のパスへと 2 パスのアルゴリズムにしないと誤差が大きかったり、
それでもスキャンライン順でキャッシュ点を計算するのもよくないので production rendering ではある程度ランダムな順番で
キャッシュ点を選ぶのを提案しているなど、実際に実装する上ではいろいろと問題がありました。
(jensen も ward の式そのままではなく、エラー関数などにいろいろ修正を加えていたようです)

本論文では、キャッシュ点をアダプティブに挿入してき補間の誤差を少なくする方法と、
また壁などの部分で光のもれ(light leaking)によるアーティファクトを防ぐ
neighbor clamping という手法を提案しています。

特に neighbor clamping による壁のしみのようなアーティファクトが消えるという効果は
大きいと思いますが、全体的にはまだ irradiance cache らしいマッハバンドのような
低周波なアーティファクトが見受けられます。
(ここらへんはキャッシュ点を増やしたり、許容誤差をきつくすれば改善するのかな?)

あとは、キャッシュ系特有の問題として、並列計算に向かないので並列レンダリングするときに
ちょっと実装が面倒になるということですね。
画面分割(タイル分割)での並列レンダリングを行うとした場合、
タイル内だけでキャッシュの計算と evaluate をしてもよいのですが、タイル間の境界で
シェーディングの不連続性が生じ易そうです。