Syoyo Fujita's Blog

raytracing monte carlo

Month: March, 2007

Uncrustify : Source Code Beautifier for C, C++, C#, D, Java, and Pawn

[En]

I found good code beautifier. I like it.

http://uncrustify.sourceforge.net/

[Ja]

lucille のソースコードを書き直し & リファクタリングし始めてようとしています。

私の場合コードを書き足していくとどんどんダメでいい加減なコード記述になっていくので、
ちょうどよい機会なのでソースコード整形ツールでコードを機械的に統一的に整形
できる仕組みにしておきたいと考えました。

ソースコード整形ツールでは、GNU indent や Astyle が有名かと思います。
このふたつを試してみましたが、どうも出力が自分の求めるものに合いませんでした。

そこでさらによいソースコード整形ツールはないかと探してみて、見つけたのが uncrustify。

かなり細かく整形ルールを指定できますので、自分好みの結果を得やすくなっています。

出力例はこんな感じです。

整形前のコード(Before beautify)


typedef struct _ri_ray_t
{
        ri_vector_t org;                /* Position                     */
        ri_vector_t dir;                /* Direction                    */
        int         nbound_diffuse;     /* number of diffuse bounds     */
        int         nbound_specular;    /* number of specular bounds    */
        float    *isectt;               /* dist from nearest hit pos    */
        float       weight;             /* weight                       */
        char        prev_hit;           /* 'E','S','D',or 'L'           */

        /* quasi-Monte Carlo related variables. */
        int  d;                 /* current dimension            */
        int    i;                       /* instance number              */

        /* multi-thread variables */
        int         thread_num;         /* thread number.
                                         * If multi-threading feature
                                         * is turned on this value
                                         * should be set                */

#if 0
        /* Ray differentials for better texture mapping, etc.
         * TODO: This feature is not yet implemented.
         */
        ri_vector_t dPdx;               /* Partial derivative, dP / dx  */
        ri_vector_t dPdy;               /* Partial derivative, dP / dy  */
        ri_vector_t dDdx;               /* Partial derivative, dD / dx  */
        ri_vector_t dDdy;               /* Partial derivative, dD / dy  */
#endif
} ri_ray_t;

extern void ri_ray_copy(
        ri_ray_t *dst,
        const ri_ray_t *src);

extern void ri_ray_perturb(
        ri_ray_t *ray);

整形後のコード(After beautify)


typedef struct _ri_ray_t {
        ri_vector_t org;                /* Position                     */
        ri_vector_t dir;                /* Direction                    */
        int         nbound_diffuse;     /* number of diffuse bounds     */
        int         nbound_specular;    /* number of specular bounds    */
        float      *isectt;             /* dist from nearest hit pos    */
        float       weight;             /* weight                       */
        char        prev_hit;           /* 'E','S','D',or 'L'           */

        /* quasi-Monte Carlo related variables. */
        int         d;                  /* current dimension            */
        int         i;                  /* instance number              */

        /* multi-thread variables */
        int         thread_num;         /* thread number.
                                         * If multi-threading feature
                                         * is turned on this value
                                         * should be set                */

#if 0
        /* Ray differentials for better texture mapping, etc.
         * TODO: This feature is not yet implemented.
         */
        ri_vector_t dPdx;               /* Partial derivative, dP / dx  */
        ri_vector_t dPdy;               /* Partial derivative, dP / dy  */
        ri_vector_t dDdx;               /* Partial derivative, dD / dx  */
        ri_vector_t dDdy;               /* Partial derivative, dD / dy  */
#endif
} ri_ray_t;

extern void ri_ray_copy(
        ri_ray_t       *dst,
        const ri_ray_t *src );

extern void ri_ray_perturb(
        ri_ray_t *ray );

Computational Statistics researchers has interest on GI reseach field?

[En]

Arnaud Doucet, the “GURU” of SMC(Sequential Monte Carlo method) has interest on MLT.
http://www.cs.ubc.ca/~arnaud/CS535D_2007.html

[Ja]

逐次モンテカルロ法(SMC) で有名な Arnaud Doucet 先生が、MLT に(本格的に?)興味をもたれているようです。
すでに Doucet 先生は W. Heidrich らと組んで EGSR2006 にて SMC を GI へ応用した論文を発表しています。

Sequential Sampling for Dynamic Environment Map illumination

これを皮切りに、計算統計や統計物理の研究者が、本格的に GI の世界に入ってくると、
いまの GI 研究者はひとたまりもないかも。なにせ彼らにとってみれば、
GI の研究領域などセリエ∀(ターンエー)みたいなものでしょうから。

さらに一方では、モンテカルロ系の生物学者が GI に興味を持っているのを伝え聞いています。

この先 2,3 年ほどは、GI 研究界には大きな激動が起こるかも。
まさに GI の巨塔になるか?…

Black and Scholes option pricing model

[En]

I’m getting interest to financial engineering because there are a lot of
similarity against (MC-based) global illumination.
For example, massive monte carlo simulation, probability theory, statistics and
low discrepancy sequences.

Thus I’m scrating the surface of financial enginnering field by
starting reading 2 famos papers in classic finantial engineering,
i.e. the paper of Black-Scholes option pricing theorem.

Black, F. and M. Scholes,
“The Pricing of Options and Corporate Liabilities,”
Journal of Political Economy, Vol. 81, pp. 637-654. 1973.

Merton. R. C.,
“Theory of Rational Option Pricing,”
Bell Journal of Economics and Management Science, Vol. 4, pp. 141-183. 1973.

Though I’m a newbie of the financial engineering, I couldn’t understand these yet.
B&S 1973 was written simply(Black said so) but needs to read a lot of citation to understand the background, while Merton 1973 is too complexed!(a lot of equations).

I can say B&S 1973 is similar to Kajiya’s the rendering equation paper and
Merton 1973 is like Veach’s Ph.D thesis.

And more, I couldn’t find the Name of Kiyoshi Ito in the References,
who established the stocastic calclus and his Ito’s lennma heavily affects Black
to derive the Black-Scholes equation(its story is well known in many FE books).

http://www.siam.org/pdf/news/1059.pdf
http://www.nikkei.co.jp/topic3/kinyu/20001222a63cm001_22.html
http://en.wikipedia.org/wiki/Kiyoshi_Ito

Option pricing theorem, including this Black-Scholes equation, would be
applicable to (theoretical) global illumination problem.
For example optimal stopping in adaptive sampling,
but I have no concrete idea of appliyng financial engineering technique to
computer graphics for now … 🙂

[Ja]

金融工学の論文で最も著名なものということで、上記二つの
ブラック•ショールズ式の元論文を軽く読んでみました。

金融工学系の論文は、量は CG 系よりも多いようなのですが、
最近のものでもあまり web では公開されていないようです。
(non random walker として知られる? MIT の Andrew Lo 教授とかは
公開しているようですが)
まあ論文自体古いこともあり web では上記論文は入手できなかったので、
図書館に行って複写してくることになりました。

Black & Scholes 1973 は、オリジナルのブラック•ショールズ方程式について、
Merton 1973 はその式の数学的な証明を与える、という感じです。

CG の世界で言えば、Black & Scholes 1973 は Kajiya の the rendering equation,
Merton 1973 は Veach の Ph.D thesis, という位置づけな感じです。

Black & Scholes 1973 は Black 先生自身も言うように、
読み手が理解しやすいように簡潔に書かれてあるとのことでした。
たしかに簡潔に書かれてあることはよくわかるのですが、
分野が違うからというのもあり、それだけ読んでもいまいちよくわかりません。

というか多くが … については … を参照、なんて書かれてあるので、
cite されている論文も読み込んでいかないとなぜここでこんな理論や式になるの?
というのがまったく見えないわけです。まあこれは the rendering equation にも言えることですね。

Merton 1973 は、これはもう数式のオンパレードです。
私のような異分野の人間がこれをいきなりよんでも、まったくちんぷんかんぷんでした。
(ベル研ジャーナルはみんなこんなにすごいのだろうか?…)
下手な理論 GI 論文よりもまっとうに数学的です。金融工学なんて所詮
金儲けのための実務的な学問だと思っていた私が浅はかでした。ごめんなさい。
Merton 先生にはひれ伏します。
(今は GI のほうが金融工学よりも浅はかだなぁという感じです)

GI のために確率論や統計を学ばんとするならば、実際の金融市場で実践のできる
金融工学から入るのがよさそうです。
(身銭を切って実践すれば、なかなか本気に勉強できるでしょうし)

さて、二つの論文でもっとも気になったのは、
References に我らが憧れの伊藤先生の文字がどちらの論文にも現れていないこと。
(ついでにいうと Bachelier 1900 も)
えっと、B&S equation を導出するのに伊藤の lenma が多大なる貢献を
したんじゃなかったんでしょうか?それを cite しないとはなにごとぞ?
それとも cite されている論文には含まれているのかな?

…しばらくは論文の孫引きのために、図書館へ通う日々になりそうです。

ちなみに、ブラック•ショールズ方程式を含め、
オプション理論や金融の理論は CG への応用が多くありそうです。
たとえば適応的サンプリングの最適な打ち切り回数などです。

Accurate direct illumination using iterative adaptive sampling.

ias.png
(left: ordinary method. middle: the method. right: reference)

Michael Donikian, Bruce Walter, Kavita Bala, Sebastian Fernandez, and Donald P. Greenberg.
Accurate direct illumination using iterative adaptive sampling.
IEEE Transactions on Visualization and Computer Graphics, 12(3):353–364, 2006.
http://www.graphics.cornell.edu/pubs/2006/DWB+06.html

[En]
Hmm… The method is simple and result is good.
I think this is the best method for direct illumination in the many-light source situation
(incluing IBL).

And the method can also be applied to Kollig and Keller’s Instant Global Illumination method.

Illumination in the Presence of Weak Singularities

[Ja]

複数光源環境における、直接光の効率的な計算方法です。

処理をピクセルブロック単位(8×8)にし、
ピクセルごとにどの光源をサンプルするかの PDF(確率分布関数) を構築するだけでなく、
ブロック単位でも PDF を構築して、その複合 PDF から光源をサンプルします。
これにより、ピクセル単位ではサンプル不足でうまく PDF が構築できなくても、
ブロック単位での PDF でカバーするということができます。

また、PDF は適応サンプリングによりじょじょにアップデートしていくことで、
ターゲット分布を収束させていきます。

アルゴリズムも簡単に見えますし、
unbiased かどうかは不明ですが結果を見るとほぼ MC ノイズが消えているので、
なかなかよさそうな手法です。

分布をじょじょにアップデートしていくのは、SMC(Sequential monte carlo)に
似た感じを受けますね。PDF を複合するのは、交換モンテカルロ法(Replica monte carlo)っぽい。
数学的にきちっと記述したら、SMC や RMC の一解釈という位置づけになったりして。

あと、本手法は直接光に限定していまが、
同じ複数光源に対するサンプルということで、本手法は
Illumination in the Presence of Weak Singularities
のインスタント GI にも使えそうです。
これで間接光も取り込むことができそうです。

Eq 10 in ERPT paper.

[En]

Recently I’m carefully reading BPT, MLT and ERPT papers.
A couple of days ago I read ERPT paper intensively.

I noticed that there is a division by PI in eq. 10. I wondered why.
I checked the eq. 10 with Eric Veach’s thesis, but I coudn’t find the reason
why div by PI is needed.

Then I downloaded the ERPT paper pdf from BYU page, from which the div by
PI is disappeared in Eq. 10.

SIGGRAPH 2005 Proceedings or pdf from ACM DL has div by PI in Eq. 10.
It seems that I had been reading ERPT paper downloaded from ACM DL.

Div by PI in Eq. 10 might be mistake, but I’m wonder why the SIGGRAPH reviwer
can’t find that?…

[Ja]
ここ最近は数学的基礎からしっかりと今一度 PT, BPT, MLT, ERPT を勉強しようとしていて、
この前は ERPT 論文、

David Cline, Justin Talbot and Parris K. Egbert, “Energy Redistribution Path Tracing” ACM Transactions on Graphics 24:3 (Proceedings of ACM SIGGRAPH 2005), July 2005.
http://rivit.cs.byu.edu/a3dg/publications.php

を精読していたのですが、どうにも 式 10 の pi 割りの理由が分からない。
Eric Veach の博士論文も引っ張り出して検算したのですが、やっぱり pi がどこから来るのか
不明とうんうんと 2,3 時間うなっていました。

しょうがないのでこりゃ author にでもメールしてみっかな、と思っていたのですが、
今一度 BYU のページで落とせる pdf をチェックしたら、
式 10 から pi 割りが消えているではないですか。

SIGGRAPH 2005 の Proceedings や ACM DL から落とせるものでは、
式 10 に pi 割りがありますので、どうも(印刷して)見ていた論文は ACM DL からのものだったようです。
(興味あるレンダラ野郎はチェックしてみてください)

なぜ当時に読んだときにこの間違いに気づかなかったのだろう、というのもありますが
(単に私がまともに精読していなかっただけ…)
もう1つ疑問なのは、Proceeding に収録されるまで reviewer はこの式の間違いに
気づかなかったのかなぁ、ということ。

まあここ最近のモンテカルロベースの GI 技法は、そんなのきちんと理解できるやつは
CG 研究者でも世界ではそんなにいないんじゃないかと思うので、
そもそも reviewer がその分野に未知だったらもうどうしようもないのかもしれません。
(私も Eric Veach の博士論文というロゼッタ・ストーンがないと解読できません 🙂 )

株価大暴落で資産 500 倍!?

さて、ここほんの数日のうちに、米国のサブプライムローンのクレジットバブル崩壊と
円キャリートレード巻き戻しが原因と見られる、世界的な株価暴落(+円高)が起きています。

そんな株価大暴落の中、面白い現象として(?)、500 倍に値上がりしたものがあります。
それは日経 255 オプションの 3 月限 プット 17,000 円です。

nk225_op_03_05_thumb.png

2/27 の最安値は 1 円でしたが、3/5 には 480 円の値段がついています。
3/5 日の取引時間内では、560 円の値段がついています。
わずか 1 週間のうちに 500 倍もの値上がりです。
競艇で言えば、万舟券を当てたようなものです。

1 円とありますが、取引単位は x1000 なので、1000 円でこのプットオプションを買っていたら、
50 万円になるということです。また、もし 3/8 までに日経平均が 16,000 円まで値下がりすると、
オプション価格は 1,000 になるので、実に 1,000 倍ものリターンを得ることができます。

オプションを取り上げるからには、オプション価格のプライシング理論を導出した、
我らが憧れのブラック先生を紹介しなければなりませんが、それはまた別の機会にでも。

オプションは、プットのオプション(株価が下がるほうに賭ける)は数年に何回か、
株価暴落により価格が 100 倍になることがよくあります。
(株価暴騰で 100 倍になることもないことはありませんが、
株価は基本的に大きく下げることはあっても大きく上げることはない)

毎月宝くじを買う気持ちで 1,000 ほどを bet していると、2, 3 年に一回は 10 万円に
なる機会があります。
下手に宝くじを買うよりも、プットオプションを買うほうが期待値は高いです。

まあとはいえ、オプション取引については、株価暴落でなければ、
90 %以上はオプションの売り手に回るほうが利益を得る機会が多い世界ではあります。

ハーバード大学の資産運用

今回のような暴落により資産がもし 500 倍にでもなるようだったら、
レンダラ財団を立ち上げて、年利 10 % 以上で資産運用して
どーらくでレンダラを書きつつ、レンダラ野郎の育成をしていきたいです。

と思う理由は、ハーバード大学では、二兆円を超える資産を年利 10 % 以上で運用して、
なんと毎年 2000 億以上資産を増やしている現実があるからです。

世界の大学のファイナンス力格差
http://www.tez.com/blog/archives/000645.html

ハーバード大の教育改革:日本の大学改革とどこが違うのか
http://www.redcruise.com/nakaoka/?p=188

授業料収入よりも資産運用益のほうが大きいって、、、
なんじゃそりゃと思いつつも、よい大学サービスを提供できるのは、
資産運用によるところが大きいということでしょうか。
金融って大事ですね。

# しかし世の中どこかにはレンダラ財団がありそうな気がしますが、やっぱり無いものなのかなぁ。
# MSR がある意味グラフィックス財団のような感じがしますけどね。

Automatic Creation of Object Hierarchies for Ray Tracing of Dynamic Scenes

Eisemann,M., Grosch,T., Magnor,M., Müller,M.
Automatic Creation of Object Hierarchies for Ray Tracing Dynamic Scenes
WSCG 2007.
http://wscg.zcu.cz/wscg2007/wscg_program.htm

良さげな論文を見過ごしていました。

効率的な動的 BVH の構築手法について提案している論文です。

3 個のテストシーンに対してしかテストしていませんが、
平均的に 10 倍ほどの構築時間の短縮を実現しています。

各フレームの動的 bvh の構築時間は本手法を使用すると 0.1 ~ 1.0 sec と、
リアルタイムで行うには難しいですが、対するレイトレ時間が
各フレーム 10 sec ですので、動的 bvh の構築コストはレイトレに比べれば
かなり小さくなっています。

もしレイトレ部分がカリカリチューンされてリアルタイムレイトレになり、
本手法の動的 bvh 構築処理も SIMD などでカリカリチューンすれば、
動的リアルタイムレイトレもかなり実用的になってくると思います。

リアルタイムレイトレ向けの空間データ構造アルゴリズムはホント,
ここ 2, 3 年の間に大きな進歩がありますね。

そろそろ本格的なリアルタイムレイトレの幕開けを感じます。

真の仮想世界

リアルタイムレイトレが現実のものになるにつれて、
いずれ将来はその発展版のリアルタイム GI による、
真の仮想世界の実現が現実のものになるだろうと感じています。

ここ最近は second life の仮想世界が流行りつつあるようですが、
あのような visual quality を見ると、
やはりポリゴンレンダラでは真の仮想世界を実現するには無理があると感じています。

仮想世界とは、Kengo Hanazawa 教授が提唱し描いている、
unreal ワールドのことであるべきです。

unreal ワールドは、現実世界と同じ視覚的リアリティが実現されており、
また、たとえば現実世界で雨が降っていれば、仮想世界(unreal ワールド)でも雨がふります。

それだけのリアリティを実現するには、maxwell render レベル以上の品質を実現する
リアルタイム GI 技術が必須となると感じています。
(それが MC ベースになるかは分かりませんが)

今はまだリアルタイムレイトレが限界ですが、
10, 20 年のうちにはリアルタイム GI 技術により
unreal ワールドも現実のものになるでしょう。

まあそんなわけで、きっと unreal ワールドのような仮想世界は現実のものになるけれども、
それには GI 技術の発展が不可欠です。
まだまだレイトレ野郎、GI レンダラ野郎がやるべきことは多いのではないかと思います。
(そして 10 年後, 20 年後には GI レンダラのマーケットは大きいと期待し、
今のうちにレンダラ野郎たちの兄貴となるようなポジションを確立しておくと、
将来はうはうはに暮らせる… かも…)