Syoyo Fujita's Blog

raytracing monte carlo

Month: April, 2007

物語で読み解くデリバティブ入門

物語で読み解くデリバティブ入門
http://www.amazon.co.jp/dp/4532352509/

本書では、一本一億円のソフトウェア [1] も取りあげています。
が、その取り上げかたには問題となる記述があります。
本書では、それはでたらめな乱数を収録したものであると記述してあるのです。

1995 年 9 月、日本とアメリカの IBM は重大な発表をしました。
まったくランダムな数値 200 万個を一億円で販売する、と発表したのです。

えっと、これって [1] でも取り上げているように、
手塚先生の LDS(Low Discrepancy Sequence) のことじゃないんですか?

[1] のときは確証がありませんでしたが、この本で年月が指定されていたので調べたところ、
たしかに手塚先生の LDS が 1995 年 9 月 27 日に Deterministic Simulation Blaster
という名前で発表されています [2]。
さらに [2] では確かにこの Deterministic Simulation Blaster の中身は実際には数列のテーブルだと記述されています。

たしかに、1990 年代は LDS だけでなく、
Mersenne Twister などの疑似乱数もファイナンスの分野で再度注目されはじめていたようですが、
この LDS の発表と同じくらいインパクトがあって IBM から発表されて、一億円の値がつくような、
(疑似)乱数がらみの発表はあったのでしょうか?たぶん無いでしょう。

LDS は(疑似)乱数ではありません。つまりでたらめな数字ではないのです。
LDS は積分の収束を早めるためにデザインされた数列であり、
でたらめさというのはまったくもって要求されていません

私も最初は LDS は疑似乱数よりもよりよいでたらめさを持つような数だと誤解していました。
「計算統計 I」の手塚先生の article を見て、LDS はでたらめな数字ではないんだ、と理解しました [3]。

この本は入門書という位置づけであり、
それほど突っ込んだ話というのは求められていません。

しかし入門書である以上、たとえばこの本を呼んでファイナンスを目指す学生も多くいるはずです。
すくなくとも著者はその道の専門家のようですから、
間違った道を教えてしまわないように、内容は正確に記述しておくべきです。
(まぁ単純に著者が LDS と(疑似)乱数の区別が分かっていないのでは、ということもあり得ますが)

そうしないと私のようにずっと LDS について誤解したままという状況になってしまいかねませんからね。

[1] http://lucille.atso-net.jp/blog/?p=258
[2] Monte Carlo loses out to IBM’s Blaster
http://www.cargonewsasia.com/timesnet/data/ab/docs/ab0916.html
[3] http://lucille.sourceforge.net/blog/archives/000336.html

[4] FlexViewディスプレイとドットパターン技術
http://www.trl.ibm.com/people/ide/dotpattern.htm
「ウォール街を動かすソフトウェア」についての記述がある。
[5] 準モンテカルロ法を利用したデリバティブ価格付け
http://www.research.ibm.com/trl/projects/optsim/riskmng/LDS/lds.htm

Metropolis Instant Radiosity

Benjamin Segovia, Jean-Claude Iehl and Bernard Péroche
Metropolis Instant Radiosity
Proceedings of Eurographics 2007, to appear
http://bat710.univ-lyon1.fr/~bsegovia/papers/mir.html

[En]

I just have granted the paper and found MIR(Metropolis Instant Radiosity) would be one of the best method to compute diffuse illumination contribution.

MIR possibly efficiently handles illumination for scenes with complex visibility and they say MIR can be easily pluggable to existing renderer. Fantastic!

Specular or caustics path cannot be handled yet, but they list it in the future work.

[Ja]

まだ軽く読んだだけですが、これはなかなか良さそうな手法です。

また、論文では Multiple-Try Metropils-Hasting 法というのを取り込んで
さらに MIR の計算の効率化を図っています。

Metropolis-Hasting 法による VPL(Virtual Point Lightsorce) の選択は、
Kollig and Keller の Instant Global Illumination にもそのままつかえんじゃね、
と思いますがどうなのでしょう。論文ではちらっと cite しているだけですが、
そちらに適用したほうがよりよい結果が得られそうな気が素人考えではするところです。

もう少し詳しく読んでみて,できれば実装してみてテストしてみたいところです。

ところで、diffuse 照明の計算はまだまだ研究すべき領域ですが、
radiosity という用語はそろそろ使わないほうがよさそうな気がします。
今の世の中

radiosity is dead.
photon mapping is obsolete.
MC-based ray tracing is cutting edge

な雰囲気だと思いますので。
(正確に言うなら mesh-based radiosity is dead というところでしょうか)

earliest record of packet tracing discovered

http://ompf.org/forum/viewtopic.php?t=345

すごい!、やっぱりパケットベースレイトレは本当にあったんだ!

「40秒でレンダリングしな!!」

Nonlinear Beam Tracing on a GPU

http://research.microsoft.com/research/pubs/view.aspx?0rc=p&type=technical+report&id=1276

タイトルは非常に興味深かったので読んでみたのですが、
やっていることはかなり brute-force だったので残念。

というか beam を作るところは CPU でやっているし、
GPU 処理部ではラスタライザを使うという手法はスケーラブルにならないとおもうので、
あまり GPU 化の意味がないように思います。
(MSRA はアレなんですかね、論文には必ず GPU という用語をいれろ、
とでも言われているのでしょうか)

ちなみに、ラスタライザは基本的に並列化処理が困難なので、
これからの GPU の進化においては、ラスタライザによるネックが大きくなってくると思います。
# DirectX 10 や OpenGL 2.0 のパイプライン図を見ても、
# ラスタライザの部分だけが相変わらず古臭いアーキティクチャのように
# 鎮座しているのが残念でなりません。

黄金四角形

https://i0.wp.com/upload.wikimedia.org/wikipedia/commons/2/2f/FakeRealLogSpiral.png

http://ja.wikipedia.org/wiki/黄金四角形

from Wikipedia.

黄金四角形の中に正方形を作ると、残った四角形がまた黄金四角形の比率に自然になる。残った長方形に正方形を作っていくと、永遠に図形を作ることができる。作られた正方形の中点を結んでいくと、渦が作れる

永遠に渦が作れる、球、回転 -> 無限!!!

ちなみに、最近ケプラー予想という本を読みました。

http://www.amazon.co.jp/dp/4105454013

これも「球」本です。sphere packing と「球」に人生を託したひとたちのお話です。
いやーアツいです。

ケプラー予想の証明に、シンプレックス法による線形計画法が使われたというのもなんとも興味深いです。

http://www.geocities.jp/ikuro_kotaro/koramu/290_kepler.htm

なんだか無性に Conway & Sloane の Sphere Packing, Lattices and Groups を
しっかりと読みたくなりました。

http://www.research.att.com/~njas/doc/splag.html

やっぱ球ネタで SIGGRAPH に一本論文出せそうだよなぁ… いや、
出来るわけがない!!!

SFMT : SIMD-oriented Fast Mersenne Twister

SIMD-oriented Fast Mersenne Twister
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html

[En]

SFMT is SIMD-oriented derivative of MT(Mersenne Twister) and there are some improvements over MT.
SIMD-optimized SFMT runs twice faster than SIMD-optimized version of MT.

[Ja]

SFMT は SIMD 最適化された MT(Mersenne Twister) で、オリジナルの SIMD 最適化された MT に
比べてもさらに 2 倍の速度で疑似乱数を生成できるそうです。また、SFMT ではオリジナルの MT の問題も改善され、
さらに周期も長くなっています。す、すばらしい、、、

論文は MCQMC2006 で発表されていたのですね。レンダリング系しか見ていなかったので気づきませんでした…

これはもう、 WELL を使うこともなく、SFMT でぜんぶ事足りそうです。

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

参考のために、Core2 2.16 GHz での non-SIMD な SFMT と SIMD 最適化な SFMT の速度結果です。


mbp: $ ./test-std-M19937 -s
32 bit BLOCK:1050ms for 100000000 randoms generation
32 bit SEQUE:1290ms for 100000000 randoms generation
64 bit BLOCK:1070ms for 50000000 randoms generation
64 bit SEQUE:1220ms for 50000000 randoms generation

mbp: $ ./test-sse2-M19937 -s
32 bit BLOCK:90ms for 100000000 randoms generation
32 bit SEQUE:420ms for 100000000 randoms generation
64 bit BLOCK:90ms for 50000000 randoms generation
64 bit SEQUE:260ms for 50000000 randoms generation