Syoyo Fujita's Blog

raytracing monte carlo

Month: March, 2006

CiteULike その後

http://jp.citeulike.org/

CiteULike、使っていくと結構よさげな感じになってきました。

CiteULike が対応している citeseer のページから論文登録をすると、
自動で情報を取得してくれますし、他人がすでに登録してくれていると、
クリックひとつで自分のライブラリに論文を追加することが出来て便利です。

pdf アップロードはイケナイ感じを受けるのでやりませんが、まあタイトルがわかればあとは scholar.google.com に聞いたり、 acm dl や ieee exploerer に繋げばだいたいは pdf がゲットできますので、それほど不便さを感じません。
(siteseer の該当論文のページにリンク先がつながっていればすぐオンラインで pdf がゲットできますし)

とりあえず CiteULike に登録しておき(忘れてしまわないように)、後日検索をかけて面白そうな論文をピックアップしたりすると、素敵な論文ライフが送れそうな気がしてきました。

それにしても、やっぱり CG 関連の論文はぜんぜんまだまだ登録されていませんね。物理やバイオ系が多いみたいです。

おまけ。現在の私のライブラリは以下のようになっています。

http://jp.citeulike.org/user/syoyo

うーん、まだまだライブラリのリストが足りないので、どんどん追加していかないとですね。

Advertisements

docutils

http://docutils.sourceforge.net/

物理のかぎしっぽ という 、非常によくできたサイトがあります。
(ときどき、rot 神拳の出し方を忘れたときなどに復習させていただいています)

このサイトでは、HTML と PDF の両方でコンテンツを提供しており、
LaTeX 数式もページに含まれています。

LaTeX 数式をサポートした何かツールを使っているのかな?
と調べたところ、上記の docutils というツールを使用していることを
知りました。

docutils では、基本は wiki のような感じの reST(reStrucured Text)
という形式でコンテンツを記述します。

個人的には、xml のようなタグ形式ではなくて、
このようになるべく人間が自然と解釈できるテキスト形式のほうが好きです。

ソースコードコメントツールも doxygen よりも naturaldocs のほうが好きですし。

docutils は LaTeX 数式もサポートしており、ひとつのコンテンツから、

o HTML + 画像による数式 (ただし imgmathhack 拡張を利用)
o PDF(latex に変換してから pdf を作成)

ということができます。 HTML + MathML というのもできますが、
ブラウザによる MathML のサポートはまだまだでしょうから、
画像化するほうが現実的でしょう。

さて、数式の画像変換ツールでは dviselect を使っているのですが、
Mac の ptex には dviselect が無くて(そもそも dviselect 自体もう古くて
使われていないようです)、ちょっと修正が必要になります。
とりあえずちょっと修正 & 簡単なテストをし、
数式を画像として HTML に出力できるとこまで確認したので、
あとは微調整すれば使い物になりそうです。

数式の入った文章を HTML と PDF の両方に出力できるソフトとしては、
docutils は自分の目的に一番マッチしたものになりそうです。

これのおかげでグローバルイルミネーション入門の執筆が加速するといいな…

WSCG 2006 Papers

WSCG 2006 の論文がオンラインで閲覧可能になっています。

http://wscg.zcu.cz/WSCG2006/wscg_program.htm

個人的に興味があるのは、、

o Dual Subdivison
新しいサブディビジョンサーフェスのフレームワークらしい

o The Hierarchical Ray Engine
“The Ray Engine” を階層化して高速化した版かな。

o Density estimation optimizations for global illumination

o A new model for 3D graphical rendering

o Efficient Occlusion Culling using Solid Occluders
前計算とかいらないので動的シーンに適しているらしい

o Light Field Rendering using Matrix Optics
交点を求める方法ではなく行列計算でライトフィールドのレンダリングを行うらしい。

oImproved Illumination Estimation for Photon Maps in Architectural Scenes
フォトンマップ使っていて、コーネルボックスの壁のかどの変なしみを消したいと思う人に最適?

o Real Time Rendering of Atmospheric Scattering and Volumetric Shadows

らへんです。 今年は大域照明関連の論文はあまりないようですね。

On the Halton sequence and its scramblings

Bart Vandewoestyne and Ronald Cools
On the Halton sequence and its scramblings
http://www.cs.kuleuven.ac.be/~bartv/downloads/iccam2004_bart_vandewoestyne.pdf

Halton 列の permutation のやり方についての新しい提案。
Halton 列については、高次元になるほど correlation が出てきて、
サンプル点の分布が悪くなることが知られています。

この問題を解決するために、スクランブルをかけて分布
を良くさせます。このときスクランブルに使われる permutation テーブルの
生成のやり方はいろいろと提案されていますが、この文献では、

(0, 1)
(0, 2, 1)
(0, 3, 2, 1)
(0, b – 1, b – 2, …, 1)

という 0 以外は単純に順番を反転させる方法(reverse permutation)を提案しています。

すっげー簡単な方法なのですが、実際これを使うと、今まで提案された
手法よりもなぜか star discrepancy が小さくなって良い分布が
生成されるようです。

lucille では、Alexander Keller の Strictly Deterministic Sampling
にあるように、 Faure の permutation 実装してありますが、
( faure_permutation() )

http://lucille.atso-net.jp/svn/lucille/src/qmc.c

この reverse permutation も試してみたいですね(すごい実装簡単だし)。

グラフィックスの学会

CG レンダリングやレンダラをこれからやりたいんだけど、
いまの CG 研究のギョーカイってどうなってんの?
どんな研究がいま流行ってんの?などと思うのは、
これからその分野を学ばんとするひとがよく感じることだと思います。
(これはちろん他の研究分野にも当てはまると思います)

そこで、今回は CG 研究(とくに大域照明研究)の海図となるようなものの
ひとつとして、主な CG 学会はどんなものがあるか取り上げてみました。
これらの学会で発表される論文が、現在の超最先端の CG 研究であるといっても
過言ではないでしょう。

個人的な観点から、各学会のレンダリング関連の論文を見た感じで、
学会(の論文)の特色はどんなものかというのコメントもつけてみました。
(本来であれば、すべての学会に論文を通した上で物申す、であるべきですが、、、)

SIGGRAPH(シーグラフ)

幼稚園児でも知っている、世界最高峰のコンピュータグラフィックスの学会。
メリケン国で開催されます。
これに論文が通るようであれば、世界の CG 研究者の仲間入りです。
ただ、最近は一発ネタやあんま CG と関係のなさそうな研究の論文も通っていたりして、
よくも悪くもエンターテイメント的な論文が良く採択されている感じを受けます。
(ある意味論文捏造みたいなことをしても OK?)

EUROGRAPHICS(ユーログラフィックス)

SIGGRAPH に次ぐ、世界第二位と言える学会です。ヨーロッパで開催されます。
ヨーロッパらしく(?)、学会らしい学会です。
理論がしっかりしていて、数学的裏づけもちゃんとしているような
論文が採択されます。

EGSR(Eurographics Symposium on Rendering)

ユーログラフィックスの血を引く、レンダリングに特化した学会です。
グローバルイルミネーションやらのレンダリング手法に関する研究では、
実はこの EGSR が一番レベルが高いといっても過言ではないでしょう。

Pacific Graphics(パシフィックグラフィックス)

太平洋の周りの国々で開催される学会です。
だいたいアジアで開催されますが、たまにカナダなときもあります。
SIGGRAPH, EUROGRAPHICS に次ぐ世界第三位の学会と言えます。
論文の傾向ですが、、、実は昔は SIGGRAPH で落とされたやつが
ここに流れ着いたりしていたので、あまり特徴となるようなものを感じなかったり、、、

Graphics Interface(グラフィックスインターフェイス)

結構昔からある学会のようです。グラフィックスに限らず、インターフェイス系も扱っている
ようです。レンダリングに関する論文ですと、人間の知覚と絡ませたやつとかが
よく取り上げられています。

Graphics Hardware(グラフィックスハードウェア)

名前の通り、グラフィックスのハードウェアに関連した論文が取り上げられます。
自前でハードウェアを設計しないと駄目というわけではなく、
GPU を活用したものや、ハードウェアでの実行に適したアルゴリズムの提案なども
採択されています。
参加者がとーっても少ない(と思う)ので、SIGGRAPH と EUROGRAPHICS とに、
毎年交互にくっついて開催されるコバンザメ学会です。

WSCG(Winter School of Computer Graphics)

ヨーロッパのどこかで開催されているという…
グローバルイルミネーションの研究に熱心な、ブタペスト工科大学からの論文が
よく採択されています。ときどきすごい論文があったりするので、目が離せません。

jgt(Journal of Graphics Tools)

かつて大人気を誇った(?) Graphics Gems の血を引くジャーナルです。
ちょっと地味だけど、キラリと光る職人的な研究が取り上げられます。

実際にレンダラを書くなどの現場や実装のレベルで、
皆が突き当たるような問題を解決するような役に立つ実用手法が多いため、
とても重宝します。

まとめ

メジャーなところはこんなところでしょうか。

ちなみに、これら学会すべてに論文を通して制覇することを、グランドスラムと言います。

上記学会のいくつかについては、Tim Rowley 大先生がまとめのページを作成しています。
非常に役に立ちますので、参考にしてみてください。

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

LaTeXiT, A LaTeX equation editor

http://www.apple.com/downloads/macosx/math_science/latexit.html

すでに LatexEquationEditor という同等の機能のソフトがありますが、こちらはサービスなどにも対応しているとのこと。日記なり文章なりでは、内容柄、数式を書くことが多いので、このようなソフトは重宝します。

なので、だいたい数式の入る文章はいつも Mac で行っています。
Mac だと OS レベルで PDF や eps のサポートがされていますから、このようなソフトが生まれやすいのでしょうかね。

test rendering

chrysler_sunsky_thumb.png
Rendered with Physical Sky(sunsky).

Stratification by Rank-1 Lattices

Alexander Keller,
Stratification by Rank-1 Lattices
Monte Carlo and Quasi-Monte Carlo Methods 2002.

I implemented “stratification by rank-1 lattices” sampling method,
which generates sample points in 2D domain.

http://lucille.atso-net.jp/svn/angelina/sampling/rank1lattice/

Alexander Keller 博士の “Stratification by Rank-1 Lattices”
を実装してみました。

ランク-1 格子(Rank-1 Lattice)とは、

lattice_eq

のような形式により生成される格子点のことです[1]。
ここで、N は生成するサンプルの数、z は s 次元のベクトルであり、
その要素はどれも N と互いに素(N との最大公約数が 1)であるような
ベクトルになります。{}は値の小数部のみを取り出すことを意味します
(つまり値が [0, 1)^s の単位超立方体に収まる)。

特に、この格子点が低食い違い量列の性質を満たすときは、
良い格子(good lattice)と呼ばれています。
ランク-1 格子の代表的なものに、フィボナッチ格子や
コロボフ型(Korobov form)の格子があります。


フィボナッチ格子

フィボナッチ格子点は、以下のような式で定義されます。

fibo_lattice
こで、Fk は k 番目のフィボナッチ数になります。
ここで、Fk は k 番目のフィボナッチ数になります。
k=9(Fk=34)のときのフィボナッチ格子をプロットすると以下のようになります。

rank1_fib1.png


コロボフ型の格子点

コロボフ型の格子点は、以下のように定義されます。

z = (1, a, a*a, a*a*a, … , a^s)

このベクトル z を使って s 次元空間に n 個の格子点を生成します。
省略して (n, a) と書かれたりします。もちろん、任意の n と a が
ランク-1 格子を満たすわけではありません。
ランク-1 格子を満たすような n と a の取り方にはいろいろあるようですが、
有名なものに (2^m, 17797), (2^m, 203) があるようです。 

Cranley-Patterson rotation

ここで、 Alexander Keller 博士お得意の、Cranley-Patterson rotation
を格子点に追加することを考えます。格子点は deterministic な点列であるため、
そのままでは相関(correlation)によりレンダリング結果にエイリアシングなど
が出たりしてしまいます。Cranley-Patterson rotation は、
サンプル点に一様乱数を加えることで、この相関を取り除きます。
式としては、ランク-1 格子に単純に一様乱数 ζ ( [0,1) ) によりオフセットを追加するだけです。

{j/N z + ζ}

Cranley-Patterson rotation を各フィボナッチ格子点に 15 点づつ適用
(上記と同じ k=9 のとき。全部で 34 * 15 点)したもののプロット図は以下のようになります。

rank1_rand

Reduced Cranley-Patterson rotation

さて、Cranely-Patterson rotation(CP 回転)を追加してみましたが、
あまりランダム性がありつつも一様に点群が分布していませんので、
少し分布の性質が悪いですね。
これはつまり、乱数を [0,1) の区間で生成しているので、うまく層別化が行われていない
というのがあります。ここで、フィボナッチ格子を良く見ると、格子点という名前の通り、
サンプル点を結ぶと格子模様が現れることがわかります。

rank1_fib_basis

ここで、格子の線が囲む各ひし形の領域内で一様乱数を生成すると、
一様乱数のオフセットが sweep する領域が狭くなり、
よりよく層別化が行われるのがわかると思います。

格子が囲むひし形の領域を定義する基底ベクトル(青色、ただし必ずしも直交にはならない)は、
以下のような 2×2 の基底行列で求まります。

bmat_eq

ここで、
j1_eq
j2_eq
となります。

基底行列を B とすると、

{j/N z + B ζ}

として CP rotation を行うのを、論文では reduced Cranley-Patterson rotation と
呼んでいます。

相関サンプリング

ここで、いままでは各フィボナッチ点に対して、毎度ランダムな一様乱数を CP rotation として与えてサンプル点を生成してきましたが、ループを逆にしても数学的には積分の結果には影響がありません。つまり CP rotation によるオフセットは一度だけ計算し、それをすべてのフィボナッチ格子点に適用するということです。
これは相関サンプリングと呼ばれています。

こうすることで、かなり相関性(フィボナッチ格子のかたち)を保ったまま一様なサンプル点を生成することができます(ただ、CG の場合はこれはエイリアシングを引き起こしやくなるので、このような相関サンプリングを使う場合は注意が必要です)。

rank1_reduced_random
相関サンプリングによる reduced RP rotation。(34 * 15 samples)

rank1_reduced_stratified
相関サンプリングによる reduced RP rotation。
ランダム値は 3×5 の層別サンプリングで生成(34 * (3*5) samples)。
一様度が上がっていますが、論文ほどきれいに層別化はされていないですね

ここで、さらに論文では、RP rotation のオフセットに、(8, 3) のコロボフ格子の
次元 3 と 4 を用いた場合も示しています。

rank1_correlated
34 fibonacchi lattice points * 8 samples( (8, 3) Korobov lattices)

なんでここでいきなりコロボフ格子(のしかも次元 3 と 4)をオフセットに使う
のかどうかはよくわかりませんが、
見た目的によい結果が得られたからでしょうか。

まとめ

次は実際にこの手法をレンダラに組み込んでみて、テストしてみたいと思います。
ところで、この手法(ランク-1 格子)もまだサンプル数 N はあらかじめ既知で
すから、適応サンプリングに使うには向かないかもしれないですね。

次は実際にこの手法をレンダラに組み込んでみて、テストしてみたいと思います。
ところで、この手法(ランク-1 格子)もまだサンプル数 N はあらかじめ既知ですから、
適応サンプリングに使うには向かないかもしれないですね。

適応サンプリングに適した、
N -1 の時のサンプル位置を変えずに、N 番目の点を
プログレッシブかつ常に statified に高速に生成する
サンプリング法を求める旅は続く…

参考文献

[1] I.H. Sloan and S. Joe. Lattice methods for multiple integration. Oxford Science Publications. Oxford: Clarendon Press., 1994.
[2] http://lucille.sourceforge.net/blog/archives/000199.html 

CiteULike

http://jp.citeulike.org

takiuchi さんから教えていただきました。
論文をメインとしたブックマークサービスです。

当たり前ですが基本的にはタイトルなどの bibtex 相当の
情報などで、 権利関係のある論文の PDF とかは public に
閲覧可能な状態でのアップロードはできません。

ローカルコピーの PDF を自分のアカウント内からだけアップして、
自分だけ見れるという機能はあるようですが、これってゼミとかの
グループ用に一個アカウント作って皆で使いまわすみたいなこともできる
ので、結構危険な香りがします…

論文タイトルの検索や管理をメインとして使用するのがよさそうです。
今日読んだ論文とか読む予定の論文とかリストアップするのにもよさそうかも。

分光画像処理入門

三宅洋一 編
分光画像処理入門
http://www.utp.or.jp/shelf/200602/062141.html

レンダラ王 shinji さんに教えていただきましたので購入してみました。
スペクトルレンダリングの基礎としての参考になりそうです。