Syoyo Fujita's Blog

raytracing monte carlo

Month: December, 2005

RainbowMaker

スペクトルを知るに当たって、
理論 G.I. 屋ではまずいと思い立ち、
real world での物理現象の振舞いを観察すべく、
分光の実験をしてみました。

David Dear,
“RainbowMaker”
Kikkerland Design,
http://www.kikkerland.com/HO/1588.htm

太陽発電で下に付いているクリスタルが回る仕組みになっているので、
太陽の光が当たる窓などに貼り付けます。


(こんな感じ)

すると…


(白い背景は壁です)

おぉ、部屋中に虹が! 光の波動性を感じるひと時です。


くるくる~ (クリスタルが回転するとミラーボールみたいに虹も回転します)


くるくる~

有意義な実験でした。

スペクトルレンダリング(Spectral Rendering)

最近は Maxwellrender
がやっていることくらいはできなきゃまずいでしょ、
ということで、スペクトルレンダリングについて勉強しています。

スペクトルレンダリングについては、Sun
氏による博士論文が概観をつかむ
導入としてよいでしょう。

Yoilong Sun,
Ph.D. thesis in computer
science:
“A Spectrum-Based Framework for
Realistic Image
Synthesis”


http://www.cs.purdue.edu/homes/sun/

同氏は、composite model
と呼ばれるスペクトルの表現方法を提案しています。

通常スペクトルを表現する場合に考えられるアプローチとしては、

WinOSi
のように波長をある区間で一様に区切ってサンプルすることです。

たとえば 380 – 780 nm
の範囲の波長(だいたい人間の可視領域はここらへんにある)
を現したいときに、サンプル数を 10 としたら
(780 – 380) / 10
の区間ごとに区切って波長をサンプルします。

しかし、これだと実装は楽ですが、データサイズが冗長になってしまいますし、

シェーディングの計算量も分割数に応じて増えてしまいます。
また特定の波長に偏っている材質がある場合などに、
十分な精度を確保できないことがあります。

composite model では、
スペクトルをスパイク状のスペクトル分布となだらかなスペクトル分布に
分け、スパイク状はデルタ関数で、
なだらかな部分はフーリエ展開で表現することにより、
データサイズをコンパクトにしつつも精度を保つということを実現しています。

個人的には、フーリエ変換よりもやはり時代はウェーブレットなので、
ウェーブレットで
スペクトルを展開するのがよさそうだし、
実装も簡単になりそうな感じを受けています。

RGB ->
スペクトル変換

通常テクスチャなどは RGB
のフォーマットのほうが指定しやすいですから、レンダラ内部で
RGB からスペクトルへデータを変換しなくてはなりません。ある特定の
RGB 色を表現する
スペクトル分布はいろいろな組み合わせがあるため、一意には決定できません。

そのため何らかの近似手法が必要になります。

以下は RGB から スペクトルへ変換する手法で有名そうなものです。

Brian.Smits.: “An RGB-to-Spectrum
Conversion for Reflectance.”
Jouranal of Graphics Tools
4(4):11-22(1999).

http://www.cs.utah.edu/~bes/papers/color/

芳信孝宏,真鍋知久,金田和文,
山下英生
RGB画像からのスペクトル変換手法
Visual Computing / グラフィクスと CAD
合同シンポジウム 2003


http://www.eml.hiroshima-u.ac.jp/member/person/Yoshinobu.t/cgsinpojium2003.pdf

後者のほうがよりよい近似を生成するようです。

アートディレクション

G.I.
レンダラは物理的に正確であるべき、というレンダリストの観点からは、

スペクトルでレンダリングするのが自然ではありますが、
アーティストの観点からは RGB
ではなくてスペクトル空間で色調整
するのは直感的でないし、調整も困難な気がします。
そのため、レンダラをスペクトルに対応しても
そんな(調整が難しい)レンダラを使ってくれるのかなぁと思ってしまいます。

ジョージ(George Lucas) が、
「いやこれからはスペクトルだ、500 ± 10 nm
のスペクトル帯
が美しく表現できないようじゃないとオレはスペクタクルを感じない」

とか言ってくれるとスペクトル世代へのシフトが起きるとは思うのですが…

A quasi-Monte Carlo Metropolis algorithm

乱列化準モンテカルロ(RQMC)で有名な Art B. Owen
氏による、
メトロポリス(・ヘイスティング)サンプリングへの RQMC
の応用についての論文です。

Owen, A.B. and Tribble, S.D “A
quasi-Monte Carlo Metropolis
algorithm”

http://www.pnas.org/cgi/reprint/102/25/8844


http://www-stat.stanford.edu/~owen/reports/

論文は結構小難しく書かれていますが(というか予備知識がないと全然わかんないべ?)、

言わんとすることは、 RQMC をメトロポリス法のような MCMC
系(マルコフ連鎖モンテカルロ法)
に適用しても問題ないよね、ということの数学的裏づけが述べられています。

(いままでは QMC や RQMC を MCMC
に使ってちゃんと収束すると言えるかが数学的に疑わしかった。
と思う)

RQMC を用いることにより、通常の MC(モンテカルロ法)に比べて、

10 – 100 倍ほど収束が早くなっています。
(論文のテスト対象は単純なガウス分布関数などなので、
実際のレンダリング処理に適用した場合は
そこまで収束の効率はよくならないかと思います)

論文がやっていることは単純で、
メトロポリス法で通常擬似乱数を使う部分を
RQMC のサンプルで置き換えるだけです。
本論文では、サンプルの生成には Entacher et al の
LCG(Linear Congruential Generators)
[1] を使っています。
各サンプルには、Strictly Deterministic
Sampling [2] にもあるように、
Cranley-Patterson
回転を使ってランダムネスを付加しています。

つまり、 LCG で得られた i 番目のサンプルが x_i としたとき、
 

x’_i = frac(x_i + u)

として実際に用いるサンプル点 x’_i を生成します。
u は [0, 1) の一様分布乱数(Mersenne
Twister や WELL などの
擬似乱数
 でよい)、
frac(x) は x の小数部を取り出す関数(つまり結果は [0,
1) の範囲になる)です。

サンプルは二つのペアにまとめ、最初のほうを関数の評価に使い、
二つ目のほうを
accept/reject のために使っています。

ちなみに、双方向パストレに RQMC を使うのは Alexander
Keller 博士がもうやっていますね。

http://lucille.sourceforge.net/blog/archives/000142.html

RQMC は vray も導入しているようですし(Owen’s
scrambling らしい。 [3] が参考文献)、


http://www.oakcorp.net/chaos/sigg15.shtml

maxwell
もレンダリングのプロセスを見ているとランダムさがありつつも規則的なパターンが出ていることから
QMC(RQMC ではなさそう?) を使っているようです。

レンダラも、もう MC ではなく QMC or
RQMC を使うように着実に遷移しつつあるようです。

References

[1] K. Entacher, P. Hellekalek, and
P. L’Ecuyer, “Quasi-Monte Carlo
Node Sets from Linear Congruential
Generators”, Monte Carlo and
Quasi-Monte Carlo methods 1998, H.
Niederreiter and J. Spanier Eds.,
Springer, Berlin, 2000,
188–198.

http://www.iro.umontreal.ca/~lecuyer/papers.html

[2] Strictly Deterministic Sampling
Methods in Computer Graphics
(mental images technical report,
2001) in “Monte Carlo Ray Tracing”,
SIGGRAPH’2003 Course #44, San
Diego, July 2003.
http://graphics.uni-ulm.de/

[3] Owen, A.B. “Quasi-Monte Carlo
Sampling” PDF A Chapter on QMC for
a SIGGRAPH 2003 course

http://www-stat.stanford.edu/~owen/reports/

計算統計II

本を買いました。
なんだろう?….


ゴゴゴゴ…..  
ゴゴゴゴ…..
近づいてみよう….


ゴゴゴ… ゴゴゴゴ…  
ゴゴゴゴ…


ドォ~~~~~~~~~~~~~~ン


バァ~~~~~~~~~~ン


http://www.amazon.co.jp/exec/obidos/ASIN/4000068520

逐次モンテカルロ法を取り上げている貴重な邦書が
ついに発売になりました。

これからの GI
アルゴリズムでは逐次モンテカルロ法を扱うものが
多く提案されてきそうですので、今のうちに学ぶのに最適だと思います。

(MLT などのモンテカルロ系 GI
を実装するのにも役立つでしょう)

Pane: Kevin Beason’s renderer

最近の Kevn Beason 先生。ソース公開の GI
レンダラ Pane で有名です。


http://www.csit.fsu.edu/~beason/pane/

ちょっと見ていない間に、いつの間にか Work Log
なるものがッ!?
元から引き離されていましたが、さらに引き離されてしまいました。

やべぇ、勝てる気がしない…

こちらもがんばらないといけませんね。
1 月くらいに lucille 0.2
がリリースできるようにがんばってみたいと思います。

自動微分を援用した適応的オーバーサンプリング

牧野光則, 井下雅美,柏木雅英,大石進一
自動微分を援用した適応的オーバーサンプリング

http://www2.tamacc.chuo-u.ac.jp/tise/pub/journal07/

レイ微分を調べているときに見つけた論文。
自動微分とありますが、
やっていることはつまりレイ微分とおなじで
連鎖律(chain rule)で関数を微分するというやつです。

この自動微分(automatic
differentiaton)というのは、もともとは
mathematica
のようにプログラムがシンボリックに関数の微分式を求めてくれるしくみのようです。

A Collection of Automatic
Differentiation Tools

http://www-unix.mcs.anl.gov/autodiff/AD_Tools/

本論文では、重心座標パラメータの微分値を利用することで、
三角形と交差する可能性のある部分(スクリーン座標での物体のふちなど)を
適応的にサンプリングできることを示しています。

レイトレでの適応的サンプリングは、Glassner
 を見る限り、
輝度や深度の差、ピクセル内の三角形の数などから求めるのが一般的ですが、

本論文のように微分量も加味できると、
よりロバストな推定をすることができるようになりますね。

とはいえ、実際に実装するとなると問題もあります。

論文では述べられていませんが、
空間データ構造をトラバースしているときに、
直接レイとは交差しないが、
すこしレイの方向がずれれば交差する可能性のある
ポリゴンも見つける必要があります。

ちょっと考えてみた解は、

o 入力の三角形をちょっと大きくして(fat triangle)、
空間データ構造を構築する。
スクリーンに射影したときに大きくした分がだいたい 1
ピクセル程度になる必要があります。
あまり遠くにある三角形だと失敗するかもしれないし、
それを回避するために構築時に視点からの
距離に応じて大きくする幅を変えたとしても、
今度は反射屈折があったときにうまくいかなくなります。

o ビームやコーンのように、
ある程度レイに幅を持たせて空間データ構造をトラバースする。
もちろんどれくらいのビーム幅で探索するかにはレイ微分が使えます。

いくつか無駄にトラバースする回数が増えるかもしれませんが、
三角形を大きくするよりは
こちらのほうが反射屈折などがあっても問題がありません。空間データ構造が
kd 木であれば、
ビームでのトラバースは今年の SIGGRAPH 2005
論文である
MLRTA(Multi-Level Ray Tracing
Algorithm) も使えますので、
レイを一緒にまとめて飛ばすこともできて効率的にできそうです。

物体のふちなどの部分への適応的サンプリングは通常のレイトレでは難しいので、

一次レイ程度はジオメトリックアンチエイリアシングのやりやすい
スキャンラインのほうがいいかなーと思っていましたが、
これを使えばなんかいけそうですね。