2010-04-30

A personal annotations of Veach's thesis (5)

Here is my Japanese translation, part 1/3.

Robust Monte Carlo Methods for Light Transport Simulation
光輸送シミュレーションのためのロバストなモンテカルロ法

著者(Author): Eric Veach
Translated by Lx=d HY

 本学位論文の目標は光輸送問題を解くための 1. 汎用,かつ 2. ロバストなアルゴリズムを開発することである.1 の汎用性という目標を達成するために,我々は Monte Carlo 法に注目した.なぜなら,現時点では Monte Carlo 法のみが,実世界にあるさまざまな表面幾何物体(surface geometry),反射モデル(reflection models), そして光学的効果を扱うことができるからである.2 のアルゴリズムがロバストとは,できる限り考えられるさまざまな入力に対して,破綻することなく,十分な精度の結果が得られるアルゴリズム,つまり入力に対して出力が頑健なアルゴリズムという意味でロバスト(頑健)という.本学位論文で,我々は本質的で重要な結果を得ることができた.すなわち,新しい理論モデルと統計モデルの構築を行い,新しいレンダリングアルゴリズムを開発することができたのである.一方で論文中で,本手法ではいったい何ができないのか --- 光輸送問題を解くための手法の持つ限界 --- に対する議論も行なっている.

これまでに光輸送問題に関して多数の研究がなされてきたが,現存する手法には,依然として大きな限界が存在している.現存の手法は,通常入力モデルに大きな制限を課しており,この制限が成立するとして最適化を行なっている.したがって,この制限から外れた入力を扱う際には膨大なリソースを必要とする傾向がある.たとえば,入力シーン中には間接照明があまりないと仮定していたり,シーン中に存在する面の多くが拡散面であるなどという仮定をしている.そのため,この仮定を満たさないシーンが入力される場合,たとえば,間接照明の効果が大きいシーンや,拡散面でない物体で構成されているシーンをレンダリングしようとすると,時間がかかりすぎたり,メモリ消費が大きすぎるということがしばしば起こる.しかし,間接照明があるというシーンは,日常でよく見られるものであり,特に異常な例というわけではない.実際にはこのような問題を解きたい(たとえば建築の分野など)ということはよくあることなので,このような制限は現実的ではない.

光輸送問題を解くアルゴリズムが広く利用されるためには,どんな入力が来ても破綻することがないような手法を開発することが重要である.レンダリングアルゴリズムは現実に存在する物体に近いモデルを扱う必要があり,かつ,アルゴリズムは許容できる時間内で解を出す必要がある.そして出力される画像は物理的に妥当で,視覚的にも見栄えの良いものでなくてはならない.また,これらのアルゴリズムは複雑な物体の形状,材質,照明を扱う必要がある.なぜならこれらは全て現実の環境において重要な要素であるからである.

我々は,現実世界の可能な限りの様々な状況に対して妥当に対応でき,どの位の時間でレンダリングが可能かということが予測できるようなアルゴリズムを開発することを目標とした.我々はモンテカルロ法に着目した.これは,この手法が比較的簡単に複雑な形状と材質を扱うことが可能だからである.ひとたび,モンテカルロ法を採用することを決定すると,この手法を適用することが難しそうな問題の部分,すなわち複雑な照明(illumination)問題,を解決することが可能なアルゴリズムの開発こそが,我々の主たる関心となった.たとえば,光沢のある(glossy)表面,密集した間接光,小さな物体,そしてコースティクス(caustics)といった,現存するレンダリングアルゴリズムがあまり上手く扱えない全ての現象を扱いたい.我々の目標はこれらの困難な問題を特殊な扱い無しに上手く処理できる汎用のアルゴリズムを見い出すことである.言いかえれば,ロバストな光輸送アルゴリズムの発見である.

続く節で我々は,まずは光輸送問題とはどのようなものかという概観を示し,光輸送問題がなぜ重要な問題なのかを論じる.また光輸送問題において我々が行なった仮定についても説明する.(これに関しては1.5 節にてより詳細を述べる.)簡潔な導入の後,本論文の独自の貢献に関して要約をおこない,論文がどのように構成されているかを述べる.

最後に,これらの結果がどのようにより大きな全体像におさまるのかを示す.1.4節では,グラフィクスで利用されている他の光輸送アルゴリズムを概観的にとらえ,unbias なモンテカルロアルゴリズムの利点を説明する.1.5節では,様々な実際の光学現象(拡散など)について考察を行い,それぞれの現象のシミュレーションがなぜ困難なのか,あるいかなぜ簡単なのか,の理由を説明する.最後に1.6 節にて物理学と光学という光輸送問題に密接に関係した分野から問題を見直す.これら他の分野からの視点はしばしば互いに異なっており,実際には似ている問題に対して,様々な種類の解法が適用されている.

A personal annotations of Veach's thesis (4)

Here is the (bijectional) Japanese translation, part 3.

Robust Monte Carlo Methods for Light Transport Simulation
光輸送シミュレーションのためのロバストなモンテカルロ法

著者(Author): Eric Veach
Translated by Lx=d HY

1.1.2 輸送モデルに関する仮定

光輸送アルゴリズムは全ての光の振舞いをシミュレートするのではない.なぜなら,ほとんどの応用でそれは必要でないからである.(脚注: 厳密に言えばそれは可能ですらない.なぜなら全ての物理学が知られているわけではないからだ.しかし,光と物体の相互作用は物理学が提供できるものとしては最上のものの一つである.そして実質的に全ての観測される現象はすばらしい精度で予測できる.[Feynman 1985] コンピュータグラフィックスの目的としては我々はこれらの法則が完全に理解されていると仮定してよい.) グラフィックスの立場に立つと,物理学の光学は一つの可能性のメニューとしてはもっとも良いものとして考えられる.各応用に対して,我々はどの光学的効果が重要かを決め,そしてそれをシミュレートできるアルゴリズムを選ぶ.

我々の論文においては,我々は一般的に幾何光学モデルを仮定する.光は表面からのみ放射され,拡散され,吸収される.そして,これらの面の間では光は直進する.したがって,雲や煙のような participate 物体(吸収・拡散を行う物体),あるいは屈折率が連続的に変化する物体(たとえば,熱せられた気体)は許可しない.我々はまた,波長や量子力学的効果に依存する(たとえば回折や蛍光)光学効果のほとんどを無視する.特に,我々は光線間の相互作用の可能性,すなわち,光は完全に非干渉であることを仮定する.

通常の環境では,我々が無視した効果はそんなに重要ではない.幾何光学は我々が目にする周辺のものをほとんど全て適切に,高い精度でモデル化する.このため,実質的に全てのグラフィックスでの光輸送アルゴリズムはここでの仮定と同様の仮定を行っている.この章の後ほどで,可能性のあった他の選択肢に関して調査することにする(1.5 と 1.6 節参照).

この後,より日本語としてこなれた訳文を掲載する予定である.

2010-04-29

A personal annotations of Veach's thesis (3)

Here is the (bijectional) Japanese translation, part 2.

Robust Monte Carlo Methods for Light Transport Simulation
光輸送シミュレーションのためのロバストなモンテカルロ法

著者(Author): Eric Veach
Translated by Lx=d HY


1.1 光輸送問題

コンピュータグラフィクスの世界においては光輸送シミュレーションは人工的な世界,かつ納得できる世界を作成することを助ける道具である.我々には形状や表面の散乱属性を含む環境についての記述が与えられている.また我々には光源の記述,どの画像が生成されるかというための視点も与えられている.光輸送アルゴリズムはその後,写実的で正確な画像を生成するためにこの世界の物理をシミュレートする.

1.1.1.なぜ光輸送は重要なのか

光輸送アルゴリズムの大きな目標の一つは,写実的な仮想環境モデルを人が効率的に生成することを助けることである.たとえば,コンピュータアニメーションでは現時点ではよりリアルな光源をデザインすることに多大な努力が払われている.主な問題は,プロダクションで利用されている(スキャンラインやレイトレーシングなど)のアルゴリズムは間接光をシミュレートする能力がない.つまりライトが置かれた時点で間接光が自動的に有効になることはない.そのかわり,それらの効果は注意深く置かれた光源によって模造されなくてはならない.もし,我々がロバストな光輸送アルゴリズムを自動で計算することができるなら,光源設置の仕事はより簡単になる.

光輸送シミュレーションのその他の応用は予測可能なモデリングである.つまり実際に製作する前に物体の外見を予測したいという欲求である.この考えは建築や,製品デザインの分野では明らかである.これらの応用では結果は客観的に正確であり,かつ,見た目も良いものであることが重要である.

最後にグラフィックスの分野での光輸送の技術の発展は,結局物理と工学に置いてもより広い手法の発展に寄与する可能性が高い.1.6節は,これらの可能性についてくわしく議論している.

もしロバストな光輸送アルゴリズムがみつかったならば,広く利用されることは確実である.これは一般にコンピュータソフトウェアの傾向として続くだろう.つまり,アルゴリズムがより簡単でより強力になることは,結局はいくつかの状況で効率なデザインよりも好まれるという傾向である.我々は正確な光輸送のシュミレーションのもたらす利益は,ある程度の計算コストをすぐに上まわることになると感じている.

2010-04-26

A personal annotations of Veach's thesis (2)

Here is the (bijectional) Japanese translation, part 1.

Robust Monte Carlo Methods for Light Transport Simulation
光輸送シミュレーションのためのロバストなモンテカルロ法

著者(Author): Eric Veach
Translated by Lx=d HY

Introduction

本学位論文の目標は光輸送問題を解くためのロバストで汎用のアルゴリズムを開発することである.汎用性という目的を達成するために,我々は Monte Carlo 法に着目した.現在の所,Monte Carlo 法を用いた方法のみが,実世界で起こる広範囲の表面幾何物体(surface geometry),反射モデル(reflection models), そして光学的効果を扱うことが可能なためである.ロバストなアルゴリズムという意味は,可能な限り広範囲の入力に対して十分許容できる精度での出力が得られるということである.本学位論文では,我々はこの目標に向かって本質的な進歩を得た.すなわち,新しい理論モデル,統計モデル,そして,レンダリングアルゴリズムを開発した.我々は本手法では何ができないのか --- 光輸送問題を解くためのそれぞれの手法の持つ限界 --- に対しても議論を行なった.


これまでに多数の研究がなされたにも関わらず,現存の光輸送問題の解法の能力には大きな限界が依然としてある.現存の手法は,入力モデルのクラスに対して大きな制限をしており,その制限の下での最適化を行なっている.この制限から外れた入力を扱う際には膨大なリソースを必要とする傾向がある.たとえば,間接照明に強く依存するシーンや,多くの表面が拡散面ではない(non-diffuse)シーンにおいて,しばしばこの問題が表面化する.しかしこのような例は特に異常な例というわけではない.実際にはこのような例を解きたい(たとえば建築の分野など)ということはよくあることである.

光輸送問題を解くアルゴリズムが広く利用されるためには,あまり壊れやすくない(less fragile)ような手法を開発することが重要である.レンダリングアルゴリズムは現実にあるものに近いモデルを用いて許容できる時間内で解を出す必要がある.そして出力される画像は物理的に妥当で,視覚的に満足できるものでなくてはならない.これらは複雑な物体の形状,材質,照明を扱う必要がある.なぜならこれらは全て現実の環境において重要な要素であるからである.


我々の研究では,実際のモデルのできるだけ広い範囲にわたって妥当な,そして予測可能な性能を達成することのできるアルゴリズムを開発することを目指した.我々がモンテカルロ法,この手法は比較的簡単に複雑な形状と材質を扱うことが可能である,に着目したため,我々の主たる関心は複雑な照明(illumination)を扱うことが可能なアルゴリズムの開発となった.これらは光沢のある(glossy)表面,密集した間接光,小さな物体,そしてコースティクス(caustics)といった,現存する様々なレンダリングアルゴリズムで問題となる全ての現象を含む.我々の目標はこれらの困難な状況を特殊な扱い無しに上手く処理できる汎用のアルゴリズムを見い出すことである.言いかえれば,ロバストな光輸送アルゴリズムの発見である.

続く節で我々は,皮切りに光輸送問題の概観をしめし,それがなぜ重要なのかを論じる.また輸送問題における我々の仮定も論じる.(1.5節にてより詳細を述べる.)この簡潔な導入の後,我々は本論文の独自の貢献に関して要約をおこない,構成の輪郭を述べる.

残りの章では,これらの結果がどのようにより大きな全体像におさまるのかを示す.1.4節では,グラフィクスで利用されている光輸送アルゴリズムの様々なタイプの高いレベルの様相を示し,unbias なモンテカルロアルゴリズムの利用法を説明する.1.5節では,様々な実際の光学現象(拡散など)を考察し,なぜこれらの現象をシミュレーションすることが簡単あるいは困難かの理由を説明する.最後に 1.6 節にて物理学と光学という光輸送問題に密接に関係した分野から問題を見直す.これら他の分野からの視点はしばしば互いに異なり,実際に似ている問題に対して様々な種類の解法を導くことになる.

A personal annotations of Veach's thesis (1)

Eric Veach's doctor dissertation -- Robust monte carlo methods for light transport simulation -- is famous of its great contents, its clarity, and its completeness. Some of my friends recommended me the paper and this time I decided to read it. Basically, it is not necessary to add any annotation to this paper, but, there are some difficult part for the person who is not a specialist of rendering technique, like myself. Therefore, I would put some notes for myself.


What is the Eric Veach's paper


Computer graphics less cares about the physically correctness since the computation cost is very high. They rather concentrated to generate nice images which looks like real for human perception, but, not necessary to physically correct. However, if you want to a reality, simulating it is the straghtforward way and no cheating. This paper explain a method that tries to achieve physical correctness and robustness. I think this is a great paper.


How to get the paper


Download it from http://graphics.stanford.edu/papers/veach_thesis/ .


Introduction of Veach's paper



I think the best method to introduce this paper is reading the paper's introduction. Here is a Japanese translation of Introduction of the paper. First, I will translate it one to one, sentence by sentence. If I felt that becomes difficult as Japanese, I will translate another version, more readable Japanese version. It should be readable and one to one translation, but, it might not possible to translate in that way because lack of my translation skill.

To be continued...

2010-04-19

Things like superficial and substantial

Long time, I thought an expression ``The last but not least'' was special, but recently, I finally connect this with a small cultural thing. In English, an important thing comes first. Therefore, it is 'not least'.

In Japanese, the last one could the most important thing. ``Tori'' is the last one and the most important one -- it is Shin'uchi. If you said, ``Zenza'' means one before, that is usually less important. I miss this assumption.

This is a kind of cultural thing, but this is a superficial thing for me. As far as I know, any culture prioritize the issues, and the first one or the last one is the most important. Some think this is big issue, but, I thought it was just picked one of them. For example, in Japanese grade system, five is the best if it is five degrees. If someone gets all one, that's bad. All five is the good one. This is not the case in Germany. Or in USA, if the grade is ABC, then A is better.

Mathematics usually didn't care a superficial thing and concentrate the substantial part. Finding minima of a function is exactly the same as finding maxima, just flip the sign. Maybe in this way, I think these are superficial. It's still interesting, but, not so important for me.


Today, I saw a movie from Rainer Werner Fassbinder, Angst essen Seele auf, http://www.imdb.com/title/tt0071141/ .

This is an interesting movie. I think individualism in Germany is stronger than Japan, but, in this movie, there is a lot of envy and bias for personal things like marriage. I thought these stuffs are strong in Japan and should be well described in Japanese movie. However, this movie shows me it is not.

An old woman falls in love, but it is not so easy. People reject something not familiar with or hard to understand. Foreign people is one of them. There is a shop that says ``I don't understand what you want. Your pronunciation is too bad.'' In my experience, it is not so bad as in the movie, but, there is. This is well done in the movie. It's not only in Germany, there is the same things in Japan. I found something substance human in this movie over the culture. Unfortunately, this movie is a bit dark. I feel it is honest. I can not say the woman, an usual old woman, becomes happy. I presume this movie is not so successful. Because many people just enjoy the fiction in the movie, I am also one of them. I understand: I don't need the reality in the movie since I have it already enough by myself.

As if one eats only sweet cakes, or if one sleep a month because it is just easy, they will be sick. There is necessary to eat some bitter things. I found this movie is such one.

When I see substance of human, I found at least German and Japanese have some common. This is a great hope. We could understand deep cultural part each other. It is interesting how Japanese and German are different, but, first, I always have a question, is it really substantial? This story reminds me some Dazai's (Dazai Osamu, a Japanese author) articles. As this movie showed me, I am interested in the deep similarity in German culture and Japanese culture. These have very different looks, however, when I found it actually they are just a superficial difference, like minima and maxima, it's fascinating. Actually, finding superficial differences are easy, we don't need to look in to German and Japan, just look Bayer and Berlin. It seems not so easy to find a substantial things in life even in a good movie.

2010-04-16

folllow up C++ riddle 2010-3-19

This is a follow up of the 3-19's C++ riddle.

Note: this article assumes the reader has some knowledge about C++ language.

There was a question about the last C++ riddle: Is this standard defined behaviour or depending on the environment? The last blog, I am a bit uncertain on the pitfall 4,

Pitfall 4. This pointer is implicitly converted to boolean type.

this is standard or not. So, I tried gcc4, icc9, and VisualStudio2008. If it is not a compiler bug, this is environment dependent.


Visual Studio 2008

a.obj : error LNK2019: unresolved external symbol "class std::basic_string>char, struct="" char_traits=""<>char<<,class std::allocator>char < __cdecl middle(void)" (?middle@@YA?AV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@XZ) refer
enced in function _main
a.exe : fatal error LNK1120: 1 unresolved externals

---
icc9

a.cc(6): remark #1419: external declaration in primary source file
std::string middle();

---
gcc4

a.cc: In function `int main()':
a.cc:6: warning: the address of `std::string middle()', will always evaluate as `true'



VisualStudio2008 casts a linker error. icc9 and gcc4 output warning if -Wall is specified, but both created an executable and output is 1.

Personally, the easiest behavior among three is VisualStudio2008. A function pointer's type depends on function arguments. This prevents specialization since we don't know what function will be written in the future. Then if we use void*, I believe that is not a good idea since
there is no meaning to use template in such a case.

Under this circumstances, I think the compiler writers can choose: 1. using implicit conversion from pointer to bool, 2. casts an error. Thanks to Peter.

Anyway, my point is C++ is difficult...

2010-04-08

How to write your name: Is capitalized family name recognized?

When I want to write my name in English/German document, there are several ways to do that, and it is confusing. For example, 村上春樹 can be written as

1. Murakami Haruki
2. Haruki Murakami
3. Haruki MURAKAMI
4. Murakami, Haruki.

For me, when I wrote my name in Latin characters, it has already been not quite my name (my mother can not read it) and the pronunciation has already been altered. (Usually people call me man-cow or something in Japanese. But, that's ok. I cannot pronounce others.) Therefore, I consider that it is just an approximation of my name, and I don't think further. Maybe one reason is that my name has different writing way, but the same pronunciation. (E.g., Japanese name Hiroshi is written in 宏,浩,弘, 洋.... These are all Hiroshi, but all have different meaning. When I wrote my name in Latin character, then it already lost some meanings. Maybe this is related I am not so eager to think how to write my name. A movie title 'Sen to Chihiro no Kamikakushi' (English title 'Sprited away') exploited that Japanese reading altered in a context. (Japanese reads the character '千' as 'Sen' or 'Chi'.) This kind of subtlety is unfortunately hard to translate.

Despite of these difficulty, I need to write my name in Latin character. In this case, I try to make one point clear, which is my family name. In default, case 2 is the common way, but this is actually not explicit.

2. Haruki Murakami

In European countries, the following writing can express which is the family name.

3. Haruki MURAKAMI
4. Murakami, Haruki.

However, case 3 is not always recognised. I recall a book from Honda, Katuichi who recommended this family name capitalisation. (Unfortunately, I don't have the book now and I could not verify it.) I followed the recommendation for a few years. However, as some of you know, this doesn't work in US. One day, at a computer graphics conference, I was asked why I capitalise a part of my name. On another conference, a professor made a joke on that, "Aha, your name is such an important as written in full CAPITAL letters!" It was a kind of bad timing and I was shamed. After that, I stoped to use this method 3. This writing can be recognised at least in France, Germany, and England.

The writing 4. is used in German official document. This is not valid only in European, but also valid in US. So, I use this writing time to time. However, one of my friend recommended to use 1. notation. Because this is a proper noun, then let's just try to write it as close as possible to the original. We usually need to explain this and this is a good clue to start a conversation. In any cases, this is just an approximation for some people who don't know the Japanese, so there is no exact answer.

In the German official documents, it is specified as

first name
family name,

then we can just follow the instruction.

I wrote this article, because I was surprised that this type 3. "Capitalising family name" is the most minor one, yet this is famous in Japan. I hope this was told more often in the school.


Acknowledgements

I had a long time question on this issue. Finally I got the
answer from native professional writers. Thanks to Mike, Rachael, and Kelly.

C++ riddle 2010-03-19 (solution)

This is the solution of the last blog.

Notice: You need C++ language knowledge to read this article.

First, I checked up that what does the string's default constructor do. But, it constructs a empty string instead of '1'.

Next, I put break points at all the constructors from my debugger. But, I cannot hit any breakpoint.

If I changed the middle()'s line as following,

std::string prefix("->"), middle(""), postfix("<-");

I got the expected result:

Hi:-><-


A hint is that the middle() is like this.

std::string middle();

Can you see now?

So what kind of C++ pitfall I jumped in?

1. This is not a definition of the string object middle, but, it is a declaration of a function middle that returns string.

2. Therefore, middle in the cout like is a function pointer.

3. When a function is declared, there should be a valid function pointer regardless the implementation. (Otherwise, linker failed and we can not have an executable.)

4. This pointer is implicitly converted to boolean type in this case.But, usually pointer will be printed out as hex number.

5. (C++ has no 'real' boolean, it is int.) Non NULL pointer implicitly becomes true.

6. (C++ has no 'real' boolean, it is int.) When true is outputted to the console out, it becomes 1.

This one line has this many pitfalls. Programming with C++ is hard.

Acknowledgements

Thanks to Peter of this nice C++ riddle.

2010-04-06

C++ riddle 2010-03-19

Notice: You need C++ language knowledge to read this article.

My colleague sometimes gives me a C++ quiz. This is one of such quiz by Peter. What is the output of the following C++ program.


#include <iostream>
#include <string>

int main()
{
std::string prefix("->"), middle(), postfix("<-");
std::cout << "Hi:" << prefix << middle << postfix << std::endl;
return 0;
}


The result is the following.

Hi:->1<-


There is '1' in the middle. Why this happens? Before I give you the
explanation, I will give you some time. Enjoy! To be continued.