Syoyo Fujita's Blog

raytracing monte carlo

Month: April, 2006

Statistical Acceleration for Animated Global Illumination

Mark Meyer, John Anderson
Statistical Acceleration for Animated Global Illumination
SIGGRAPH 2006.
http://graphics.pixar.com/

It’s qute simple and easy to implement. So I started to implement this method.
For now, I could get basis vector images.

sequence of images(thumb)
The sequence of Noisy images

seq of images(thumb) 
Basis images(Eigen vectors) without scaling by eigenvalues.
Basis 0 gets smoother solution than noisy solution.

Next to do: Project noisy images to basis vector to get final result
Discussion: How about Using bilateral/trilateral filtering for spatio-temporal filtering?

時間軸でフィルタリングすることでノイズを減らす手法。
6 ページとシンプルで、実装も簡単です。

基本的なアルゴリズムは、
– 低サンプル数でレンダリングし、ノイズのある画像のシーケンスを得る
– PCA(主成分分析)により基底ベクトルを求める
– 基底ベクトルに、ノイズのある画像を射影して最終的にノイズの低減されたレンダリング結果を得る
を行います。

ビデオを見ると分かりますが、この手法の有益なところは、
空間的なノイズが消えるということよりも、
時間的なノイズフリッカーが消えるほうにあると言えると思います。

ということで、PCA を行って基底ベクトルの画像を得るところまで実装してみました。

http://lucille.atso-net.jp/svn/angelina/arch/statistial_filtering/

PCA のために、基底画像(固有ベクトル)を得るのには、
lapack の svd(特異値分解) を行う関数を利用しました。
基底画像の最初のものでは、すでにある程度平滑化されているのが見て取れます。

今回は光源もなにも変化していないので、基底 0(左上)で十分近似できるために、
基底 0 以外の基底画像はほとんどゼロに近くなっています。
(上記の基底画像は対応する固有値でスケーリングしていません。
基底 0(左上) 以外の固有値はほぼゼロなので、
実際にはスケーリングすると真っ黒の画像になります)

時間軸でフィルタリングというと、バイラテラルフィルタやトリラテラルフィルタも使えそうな感じですが、
これとの比較がどうなのかが気になるところです。

論文を見る限り、この手法は Pixar のカーズ(違うほうではありません)で使われた手法のようですね。

Abstract 日本語訳

大域照明(global illumination)は、アニメーションに非常に重要な視覚的効果を与えます。しかしその計算は高価なので、実際に利用するとなると制限がありました。

本論文では、アニメーションシーケンスにおいて、確率的レイトレーシングを用いた間接照明の計算を高速化する、実装が簡単な技法を提案します。

各サンプル点において、少数のサンプルレイを用いてすばやく計算するけれども、ノイズのかかった解を得ることからまず始めます。これらのノイズがかった解の時間軸での変化を利用して、スムースな基底を生成します。そして最後に、ノイズがかった解をこれらのスムースな基底に射影することで、最終的な解を得ます。

結果として得られるアニメーションでは、空間的および時間的なノイズを大きく減らすことができます。また計算コストは、元のノイズかがっていて低サンプルな計算のときとほとんど変わりません。

SIGGRAPH 2006 Paper list

本家の方で、SIGGRAPH 2006 採択論文のリストが公開されています。

http://www.siggraph.org/s2006/main.php?f=conference&p=papers

まだ論文が公開されていないもので、タイトルを見た限りで個人的に気になるのは、、、

o Guided Visibility Sampling
MLRTA のひとも絡んでいます。
o Fast Median and Bilateral Filtering
超高速なフィルタ
http://www.shellandslate.com/fastmedian.html
このグラフの提示方法はぜひ見習いたいところ。
o Perfect Spatial Hashing
完全ハッシュの空間データ版? ハッシュテーブルの作成と探索が高速ならすごい手法な気がします。
o Appearance  representation のセクション全部
o Precomputed Radiance  Transfer セクションの最後のひとつ以外全部
o Light Transport(!) セクション全部
o Locally Adapted Hierarchical Basis Preconditioning
なんかすごそう…
o Fast Proximity Computation Among Deformable Models using Discrete Voronoi Diagrams
変形物体間の高速な近接度計算。GJK みたいに最小距離と位置も出るようだとすごそう。
o Manga Colorization
このようなタイトルが通るくらいなら、○。○。シェーダや Gekiga シェーダも通りそうだなぁ

らへんです。ことしは豊作の気がします。GI や WSCG もまだ全部見ていないのに、この後に EG や EGSR も控えていますから、今年は読むべきレンダリング関連の論文は多くありそうですね。

Recursive Wang Tiles for Real-Time Blue Noise

Johannes Kopf, Daniel Cohen-Or, Oliver Deussen and Dani Lischinski,
Recursive Wang Tiles for Real-Time Blue Noise
SIGGRAPH 2006.
http://johanneskopf.de/publications/blue_noise

まだ abstract とムービーしか見ていませんが、これもすごいです。デモムービーを見るだけでも(サンプリング野郎からすると)すごいのが分かるかと思いますが、

– 任意の N(点の数)
– 決定的(deterministic)
– ブルーノイズ性質
– リアルタイム
– インポータンスサンプル可能
– プログレッシブかつ stratified

と、ほぼ最強の性質を持っています。私が長年求めていた究極のサンプルジェネレータかもしれません。
penrose tile sampler を Wang tile + 階層化へと拡張した手法のようですね。
実際にレンダラの light transport やアンチエイリアシングに実装してみたいところです。
今年の SIGGRAPH はすばらしい論文がいっぱいです。

Abstract 日本語訳

良質な分布を持つ点群は、コンピュータグラフィックスのいろいろな分野で重要な役割を演じています。
たとえば、アンチエイリアシング、大域照明(グローバルイルミネーション)、ハーフトーン処理、ノンフォトリアリスティックレンダリング、ポイントベースド・モデリング、ポイントベースド・レンダリング、ジオメトリ処理などが挙げられます。

本論文では、ブルーノイズ(blue noise)フーリエスペクトルおよび高い視覚的品質を保ちながら、非常に大量の点群を高速に生成する新しい手法を提案します。

本手法では、非周期的な点群を生成します。点群は任意の広い領域に対して分布させることが可能です。
点群の局所的密度は、最大密度の限度をあらかじめ設定することなく、任意のターゲット密度関数により指定することができます。

我々の手法は決定的(deterministic)であり、タイルベース(tile-based)です。
つまり、無限に広がる可能性のある点群であっても、その局所的な位置は必要に応じて一貫して再生成することができます。

本技法のメモリ使用量は一定であり、点群の局所的位置を生成するコストは、その(生成したい)局所的位置の領域に対応するターゲット密度の積分に比例します。

これらの性質により、本手法は各種リアルタイムなインタラクティブアプリケーションに非常に適しています(そのいくつかは本論文の中でデモします)。

我々の手法hは、注意深く構築されたプログレッシブで再帰的なブルーノイズワンタイル(blue noise Wang tiles)を利用しています。
ワンタイルを利用することで、無限の非周期的なタイリング(タイル張り)の生成を可能にしています。

各タイル内でプログレッシブな点群を生成することで、空間的に点密度を変化させることができます。再帰により、本手法は高密度が必要な部分のみに適応的なタイルの分割を行うことがが可能になっています。これにより、見かけ上は一定の密度を保ちつつも、点群内に任意にズームしていくことが可能です。

EUROGRAPHICS 2006 papers on the web

Ken-Sen Huang 先生が、EG 2006 の論文リストをまとめてくださっています。

http://myweb.hinet.net/home7/hks/Papers2006/eg2006Papers.htm

そろそろレンダリング関連の論文がいっぱい公開されて始めて、楽しくなってきました。

まだ読めていませんが、

Cache-Efficient Layouts of Bounding Volume Hierarchies

は、空間データ構造野郎とキャッシュ野郎でもある者としては要チェックです。ノードデータそのものには変更はなしで、メモリレイアウトのみの変更することで、最大 5 倍ほどまで効率アップが図れるようです。

Graphics Interface 2006 Papers

Ken-Sen Huang さんが GI 2006(グローバルイルミネーション 2006 ではない)の論文リンクをまとめてくださっています。

http://myweb.hinet.net/home7/hks/Papers2006/gi2006Papers.htm

Lighting のセクションが面白そうです。

Image Synthesis using Adjoint Photons
http://www.cs.utah.edu/~shirley/papers/

光源からフォトントレーシング(フォトンマッピングではない)ではなく、
視点からのフォトントレーシングをするというもの。
vray もちょっと昔に視点からのフォトンマッピングというのを発表していましたが、それに似た感じでしょうか(density estimation をしないという点が違う)。

光源から光を伝達し、センサー(つまり視点やカメラ)でその反応を受け取るのは、その役割を入れ替えても成り立つ、つまりセンサーからフォトンを放出し、光源でその反応を受け取るのと同じであるという、随伴性(adjoint)の理論を使ったレンダリング方法を提案しています。

視点からフォトントレーシングをしたり、随伴作用素(Adjoint Operator)の理論はすでに既存研究としてありましたが、あくまで理論から抜け出せていなかったと思います。本論文の趣旨は、視点からのフォトントレーシングを実際に実装してみたら、理解するのに複雑なモンテカルロ法の理論は必要なかったり、participating media の扱いが簡単だったり、パストレよりもコードがクリーンに書けたりするよ、というのがわかりました、という感じでしょうか。

SIGGRAPH 2005 の dual photography との関連があるそうですが、私はまだこの論文を読んでいないので、cite されている論文をもう少しじっくり読んでいろいろ判断する必要がありそうです。

あとは、視点からのトレーシングの場合は、コースティクスの表現が一番の問題だと思います。明示的にコースティクスの解決については書かれていないようですが、インポータンスの大きい部分に集中してサンプルレイが放たれるとあるので、基本的にはレイをいっぱい飛ばして力技で解決するということのようです。収束がどれくらいなものなのかについてもきちんと書いていないのでちょっとよくわかりません。
基本的には本手法を使ったとしても、それなりのレイトレの回数が必要です。論文では、終夜でレンダリングすれば今の CPU であれば一兆レイ飛ばせる(終夜を 12 時間とすると秒間約2300 万レイを飛ばせる計算。これは 1 CPU で実現できるなら、それなりにインタラクティブレイトレに近いパフォーマンスですね)ので、我々が扱うシーンのレンダリングでは問題ないとありますが…

とはいえ、大きな利点は、理論が簡潔で、実装も簡潔であるとのこと。最近のモンテカルロレイトレは複雑な方向に進みつつあると思うので、安い(?)、早い、うまい(?)なアルゴリズムというのは重要だと思います。
さらに、フォトンマッピングのように density estimation ではないので、その点では将来性のあるアルゴリズムであると思います

ただ、その割には擬似コードや背景知識の説明があまり親切でなかったり、我々の galileo レンダラに実装しましたとあるけどコードは公開されてない、みたいな所で損している感じがしてちょっと残念です。
(ここらへんはいずれ TR(テクニカルレポート) で詳細な解説付きなのが出そうですから、それを待つのもよさそうです)

SBR 2006

今年も、SBR 2006 を開催させていただきます。

http://lucille.atso-net.jp/sbr2006/

SBR 2006 とは?

SIGGRAPH 2006 採択論文が公開されると同時にスタートし、
ゴールをその実装とする人類史上初の公開論文実装レースであるッ!!!

今年はレンダリング関連の論文が多そうですので、盛り上がりそう!

Ray Tracing Animated Scenes using Coherent Grid Traversal

Ingo Wald, Thiago Ize, Andrew Kensler, Aaron Knoll, and Steven G Parker
Ray Tracing Animated Scenes using Coherent Grid Traversal
http://www.sci.utah.edu/~wald/Publications/

空間データ構造にグリッドを使った、動的シーンのリアルタイムレイトレです。
基本的な考えは coherent ray tracing や MLRTA と同じで、空間データ構造を kd-tree からグリッドに変えたという感じです。

動的シーンや軟体物体があるシーンでは、kd-tree の再構築がネックになるので、
再構築の高速なグリッドの方が好まれます。
現在の軟体シミュレーションの研究では、空間データ構造にグリッド(ハッシュ)を使っているものが
多いですしね。

しかし、グリッドでは、パフォーマンスアップのために複数のレイをまとめて飛ばそうとした場合、
通常グリッドのトラバースではレイごとに異なったセルをたどることが多いので、
コヒーレンシーをどう保つかが問題でした。

本論文では、これをボクセルをスライス(レイの進む方向の 2D 平面)ごとにステップしていくことで
解決する方法を提案しています。

さらに、mailboxing と MLRTA などでも用いられている SIMD frustum culling を用いて、
ポリゴンとの交差判定の数を極力減らすことで、レイを一本一本トラバースするのにくらべて、
10 – 20 倍ほどのパフォーマンスアップを実現しています。

基本的にはリアルタイムレンダリングでの利用が主のようですが、
オフラインレンダリングにも問題なくできそうなので、実装して試してみたいところです。
MLRTA も実装して試したことがあるのですが、明らかに MLRTA(kd-tree) よりは実装が楽でしょうし。
ただ、やはり二次レイ以降のランダムレイをどうするかが問題ですね。
これについては、WSCG 2006 の The hierarchical ray engine で提案されている
シンプルなレイのクラスタリングテクニックが有用そうな気がしています。

あとは、幅優先レイトレ(breadth-first raytraing)とうまく組み合わせられると、
より省メモリで大規模なシーンを効率的に処理できそうな感じがします。

SIGGRAPH 2006 paper list

Tim Rowley 大先生が、SIGGRAPH 2006 論文のリストをまとめてくださっています。

http://www.cs.brown.edu/~tor/sig2006.html

まだまだリストはこれから更新されていきますが、現在見た感じでは今年はレンダリング関連の論文が豊作な気がしています。

More SIGGRAPH 2006 papers found on the web

A Spatial Data Structure for Fast Poisson-Disk Sample Generation
http://www.cs.virginia.edu/~gfx/pubs/antimony/

これはすごいです。poisson-disk パターンをなんと O(N) で生成します。今までは、poisson-disk(ポワソンディスク) パターンの生成は O(N^2) or O(N log N) の計算量であることが良く知られていました。

poisson-disk パターンとは、基本的に N 個の点があったときに、お互いの点がある距離以上離れてるように点を配置したときに現れるパターンです。人間の視細胞分布がこれに従います。poisson-disk パターンはブルーノイズ性質を持つため(低周波成分を含まない)、サンプリングでは非常に重宝されるパターンのひとつです。

実は、任意の N や距離についてそのような配置を最適に見つけるのは、結構むずかしい問題です。

本論文は、SIGGRAPH 2005 の wavelet noise のように、SIGGRAPH 2006 でもっとも注目される論文のひとつとなるでしょう。アルゴリズムもそれほど複雑ではないとのこと。早速実装してテストしてみようかと思いましたが、コードがいずれ公開されるとのことです(いずれにせよ勉強のために自分でも実装しようかと思います)。

Two-scale Tone Management for Photographic Look
http://people.csail.mit.edu/sparis/

A Compact Factored Representation of Heterogeneous Subsurface Scattering
http://www.cs.princeton.edu/~jlawrenc/papers/bssrdf/

不均質媒体でのサブサーフェススキャタリングの取得とレンダリング。不均質の媒体だと、このようなモデルデータの生成も大変になりますね(論文では、カメラで実物を撮ってそのようなデータを取得するようです)。

Inverse Shade Trees for Non-Parametric Material Representation and Editing
http://www.cs.princeton.edu/~jlawrenc/papers/ist/

結果から、シェードツリーを逆に求めるらしい。つまりはシェーダ言語の逆コンパイル版?

SIGGRAPH 2006 論文決定?

SIGGRAPH 2006 論文の author notification がありました。
そろそろ採択された SIGGRAPH 2006 論文がネットで公開され始めますね。

なので今週末くらいにでも SBR 2006 のページを作成したいと思います。

とりあえず、みつけたもの。

http://www.cs.washington.edu/homes/aseem/supp/index.html

sumitted となっていますが、author のページでは appear になっているから採択されたのかな?