Lx=d: SundayResearch

Overview idea of Bidirectional path tracing In forward path tracing method, we don't know where the light comes from, therefore, we sample them to find them. However, light comes from light sources. Therefore, it is natural to distribute light from the light source and then sample the environment to find where is bright. This could be more efficient. How this can be done without biasing is an issue and the paper described it. There are some cases that forward path tracer hardly handles some paths. For example, a projector projects an image to a wall. Forward path tracer creates paths from a view point and hits the wall, then samples the lens of the projector. Just looking up the light source (the projector) can be done, but, it is difficult to see the image on the wall since such a dense samples must be on the lens without a direct guidance. It's not impossible for forward path tracer, but practically it is hard and mostly we could not see an image. In this case, the proj...

Bidirectional path tracing Bidirectional path tracing connects vertices. The vertices are generated from 1. a light source, 2. an eye. My question is how these vertices are connected, this is rather an implementation question. If we connect all the generated vertices, this is combinatorial explosion and we can not handle this. Daniel answered me that 1. make two paths a pair (one comes from a light, the other comes from an eye), 2. connect vertices only from the paired paths. This is an efficient implementation. Figure 1. Connect vertices in Bidirectional path tracing The number of generated rays are the computation cost, but how many contributions we can get differs depends on how to connect them as shown in Figure 1. This figure is a simplified version (no occlusion at all). But, we could have many contribution by generating smaller number of rays. Overview idea of multiple importance sampling method This paper has a lot of interesting ideas. I will summariz...

p.310 Special cases for short subpaths There are zero subpaths vertices and one path vertices to generate subpaths. If I draw a picture, there is one line from the lens to the light source. So, I could not distinguish the difference. Again, I asked my friend/specialist. It is quite convenient to have such friends, but, I should study more, otherwise, these friends will be bothered by me. The correct picture is shown in Figure 1.      Figure 1. Short subpath The differences are: Zero subpath vertices: The sample is done from the lens only, the probability is only related with lens, and it coincidentally hit to a light source. One subpath vertices: The sample is done on the light source with sample density probability only. Then this vertex is connected to the lens. The path's generation probability is not the same, therefore, the contribution is also not the same. Acknowledgements Thanks to Leo and Carsten. p.321 Implementation It's a bit details, but I...

This is not a story about paper/mathematics/computer science, this is my story and I will be happy if you could find something interesting. Finally today (2010-9-15(Wed)), I finished the Veach's thesis. This is one of the best papers I've ever read. I have still many questions, but, I hope I got the main ideas. This is not exactly a paper of my area, but this is related with the basic technology I work on. My colleagues recommended me this paper. I partially read it last April and found it interesting, though, I did not continue until June. Our customers use our library, so our customers are developers. My task is helping them. When I joined the company, I worked as a developer for around two years. I was lucky to have a talented colleague and a great boss. It was fun to contribute a product. Our team had a success in 2008, for example, our optimizer made our other product more than 10 times faster. We had a demo in summer. But, at 2008 fall, the crisis came. My team just h...

p.272 Twice brighter sample There is an example of importance sampling based Light source and BRDF in p.270, Figure 9.6. Here is the figure. In this case, to avoid biasing, importance weight is compensated by probability. This leads the following interesting equation. where,  \hat{w_2} = p_2/(p_1 + p_2). Notice that the values of  p_1, p_2  here. When  p_1  is non-zero, usually  p_2  is smaller than p_1  (p_1 >> p_2). However, the Equation is the case of  p_2  sample happens in  p_1 's non-zero region as shown as a red line in Figure1. In general, since the region of p_2  is larger than  p_1, this usually doesn't happen. But if it happens, the condition is f/(p_1 + p_2) -> f/p_1, and this is almost equal to  p_1 's contribution because  p_1 >> p_2 . Veach explains this is seen as a bright spots in Figure 9.5(c). This is interesting. Of course this problem is when the number of sample is quite...

p.264 Balance heuristic 1 Equation 9.8's weight is quite similar to the weight used in my favorite operator, Laplacian operator. Here Veach said this is heuristic, but I see this condition is carefully chosen. There are positivity and partition of unity. Following these conditions, we can guarantee the solution's sup and inf can not be out of range of the value of the sampling values. It might be misleading, but, briefly speaking, this operator is an extension of averaging. One amazing property of average is the average never over the maximal value and never less than the minimal value. For example, the average of 5 and 10 is in-between 5 and 10, never larger than 10, never less than 10. You might hear I said something so simple in too complicated way. But, this property is still valid when these weights are applied in here. (9.8's weight gives us Affine combination of the samples.) If you think about the weights, you might need to think that these property can be kept or...

p.227 Probability density When I calculate the probability density p(\overline{x}) of given path \overline{x} , density is In p.228, the author said that it is also possible to directory compute the P . I thought this is just replace p with P and I fail to see how we could compute it. Here P is a density of samples, that I should decide it. This mean I could compute directory. For example, if I sample uniformly, then the density becomes uniform. In a sense, I need to decide it or if I choose a method, then it automatically chosen. Therefore, there is no more explanation here. But it is actually difficult part for me. p.232 BSDF's value is less than infinity BSDF is a sort of transfer function (signal processing sense), that is the ratio of input light and output light. Therefore, I thought why this can be infinity. I totally forgot this is a density function. In this case, total reflection gives you the Dirac delta, therefore, the value is infinite. There are some cas...

p.116 4.6 Adjoint operator I look back to the chapter 4.6 since adjoint operator is important topic now. This operator is written as Hermitian. This is a conjugate transpose, I just imagine what could be imaginary energy. There was a story about Hilbert space, so, maybe this is related with that. But until chapter 7, this operator indicates only real symmetry. In the light transport equation, the light emitted to a surface and reflected, then reaches to the camera. If the camera and the light exchanged, the equation should be the same. I think that is this adjoint operator about. Acknowledgements Carsten W. gives me a comment my understanding sounds OK. Thanks. p.122 particle tracing Equation 4.32's comment's comment My blog explain why the weight is there. But if you see p.226 Equation (8.9) explains brief and precise. Also it is general, since I only handled two cases, instead, Veach's form is an integral form and everything is there. How simple he explained t...

p.168 D3 and Equation 5.30 updated I got a comment about Equation 5.30 from my friend Daniel. However, Equation (1) has absolute value operator at |f'(x_0)|, I don't understand this yet. To see this Equation, we could think about this is a chain rule. If we write this in an integral form (as the substitution rule) as in the Equation (2). This is substantially equivalent with the chain rule. But still, the domain doesn't match with Equation 5.30. On the other hand, if we read the thesis until p.170, Equation 5.35 is a definition and this looks like showing a linearity. It is Equation (3). Maybe the question is, what is the linear coefficient a_{\beta}. That's my guess. What coefficient makes this equation consistent through the Dirac's \delta, that could be the definition of Equation 5.35. This has an advantage, if this can be, we don't need integrate every time, this \delta looks like just an ordinary function. This is convenient. (as the Veach said in ...

p.137 Shading normal The shading normal differs from the geometry normal. The shading normal has no physical meaning, therefore, this causes a trouble if we use it to compute physical energy. Indeed, if we use the bump mapping, then the energy computation for the geometry must be handled something special. p.140 Figure 5.1 The light energy inside of refraction object should be scaled. I never think about that. Indeed, water (refraction object) makes incoming light more dense inside the water. This means energy is concentrated inside. Therefore, we need to consider this. But the usual case, when light goes into the refraction object, then energy concentration happens, also when light goes out from the same refraction object, the inverse effect happens and the energy is un-concentrated. Therefore, I never think about that. In this figure, the algorithm need the energy of inside the water, this effect should be considered. For example, if a camera is inside the water, there could be...

p.88 Notation of Equation 3.6.3 In Equation 3.6.3, there is a d!, it looks like a operator. It is used as d! cos theta d phi. However, I could not find the definition of this (friends and web.) p.122 particle tracing Equation 4.32 In this Equation about alpha , there is a mysterious (for me) term 1/(q_{i+i}) . f is projected solid angle, p_{i+1} is approximation of BSDF, so no problem. But, what is this 1/(q_{i+i}) ? Figure 1: Sampling weight $\frac{1}{q_{i+1}}$. (1) terminate sampling by  probability $p$, (2) bounce probability is $(1-p)$. Because, the sample  value is better than nothing, the case (2) is respected by  $\frac{1}{1-p}$, that is $\frac{1}{q_{i+1}}$.} Figure 1 shows the alpha update. The sampling is done by the Russian roulette method, then, the termination of a ray is decided by a probability. Intuitively, when you continue to sample, it is natural to respect the sampled result more. Because a sample has more information than no sample. Ther...

2.8.2 Regression methods Section 2.8.2's Equation (2.33) was a mystery for me at first. I asked this to a few specialists, but they told me that is not so important, and I should go forward, the good ones are coming... Therefore, this annotation might not so helpful, but I like this straightforward idea. The hint of understanding of this Equation is in the paper: ``Equation (2.33) is the standard minimum variance unbiased linear estimator of desired mean I , ....'' This means he used Gauss's least square method. Most of the part of Veach's paper is self contained and easy to understand, but, personally I would like to have one more equation --- Equation (1) --- here.  This means each final estimation F is equal to the sample mean \hat{I} . Veach might think this is too obvious and he didn't feel to write it down. But it surely helps for dummies like me. We can derive Equation (2.33) from Equation (1), so let's try that. First of all, Equation (1) h...

2.7.2 Russian Roulette Russian roulette methods is one of sampling techniques. It selects sample path stochastically. This includes stochastic ray termination. The light transport equation is an integral and the equation has several terms. The magnitude of the term depends on the sample. If the term is quite small or the material's reflectance property said one direction is not so probable, sampling such term or direction has less effect, yet still costs the same. But, if we don't sample such term at all, the solution will be biased. Because it is always possible that the light comes from that direction. Figure 1. Russian Roulette: (a) non-Russian roulette (splitting) ray tracing, sample many directions when sampling a glossy surface, (b1)  Russian roulette sample, sampling only one direction depends on the probability, (b2) Russian roulette stochastic termination (c) a trace path is also chosen and terminated by specific probabilities. Figure1 (a) is an example of n...

Star discrepancy D_N^* I might say, the goal of Quasi-Monte Carlo method seems to have a sort of contradictory. It is: To minimize the irregularity of distribution Not using regular uniform samples to avoid aliasing  To minimize the irregularity of distribution, a straightforward answer is using regular distributed sampling. But, this causes aliasing that is the point to use the Monte-Carlo method (Note: not Quasi-Monte-Carlo). A discrepancy is a quantitative measure of irregularity of distribution. This measure tells us how much integration error occurs. The star discrepancy D_N^* is a discrepancy. When we sample many boxes that always includes the origin, it shows the maximum error of estimation of the area of these boxes. In the case of one dimension, boxes are lines. Therefore we estimate the length of line that includes the origin by sampling. If we sample N points, if we sample regular uniformly, we could not sample less than 1/(2N) length correctly. This is the...

Page 50: Stratified I was not familiar with the word `Stratified.' A Monte-Carlo method usually uses a pseudo random number sequence. A random number sequence usually should have a property, `unexpectedness,' this means a same number sequence like 1, 1, 1, 1, 1, ..., 1 could be also a part of random number sequence. This issue is well explained in Knuth's book (D.E.Knuth, The Art of Computer Programming, Vol.2 Random numbers). The sampling pattern could be the left of Figure 1.  Figure 1. Stratified example. Left example of random 12 samples (clumping problem), Right example of 2x2 stratified random 12 samples In Figure 1 left, some part is not well sampled, or some part is oversampled -- the sampling pattern is biased. This is clumping, a bad luck in a sense. Usually it is solved when the number of samples is increased, but, it computationally costs, means it takes more time to compute. To solve this clumping problem without losing performance, the sampling region is ...

Page 11: Light implementation In page 11, there is a paragraph about light implementation. Ideally, the performance of the light transport algorithm should depend only on what the scene represents, rather than the details of how it is represented. For example, consider a scene illuminated by a square area light source. If this light source is replaced with a 10 by 10 grid of point sources, then the visual results will be nearly identical. However, the performance of many light transport algorithms will be much worse in the second case. Why 10x10 points is more expensive? As an amateur, I think if the area light is sampled by 20x20, then it seems 10x10 points is cheaper. But this is just an example. It seems the author want to say if you tell the renderer more straight forward way, the rendere can usually optimize the process. It is better to say that an area light is an area light, not an area light is many points. (Thanks to D.S.) Page 14: unbias and consistent This page mentio...

Here is my Japanese translation, part 3/3. Robust Monte Carlo Methods for Light Transport Simulation 光輸送シミュレーションのためのロバストなモンテカルロ法 著者(Author): Eric Veach Translated by Lx=d HY 1.1.2 輸送モデルに関する仮定 光輸送アルゴリズムは全ての光の振舞いをシミュレートするのではない．なぜなら，ほとんどの応用でそれは必要でないからである．(脚注: 厳密に言えばそれは可能ですらない．なぜなら全ての物理学が知られているわけではないからである．しかし，光と物体の相互作用は物理学の中でも最もよく研究され，発展しているものの一つである．そして実質的に全ての観測される現象は，かなり高い精度で計算，予測できる．[Feynman 1985] したがって，コンピュータグラフィックスの目的としては我々はこれらの物理法則は，ほぼ完全に理解されていると仮定してよい．) グラフィックスの立場に立つと，物理学における光学の知識を使うことは，写実的な画像を生成する手法として，最も適していると考えられる．どのようなシーンを生成するかに対して，我々はどの光学的効果が重要なのかを判断し，そしてそれをシミュレートできるアルゴリズムを選ぶことになる． 我々の論文においては幾何光学モデルを基礎とする．このモデルでは，光は物体の表面からのみ放射，拡散，吸収される．そして，これらの面間では光は直進すると仮定する．したがって，雲や煙のような participate 物体(吸収・拡散を行う物体)や，あるいは屈折率が連続的に変化する物体(たとえば，熱せられた気体)は考慮しない．我々はまた，波長や量子力学的効果に依存する(たとえば回折や蛍光)光学効果のほとんどを無視する．特に，我々は光線間の相互作用の可能性を排除する．すなわち，光は完全に非干渉であることを仮定する． 通常のレンダリングでは，ここで我々が無視した効果はそれほど重要ではない．幾何光学は我々が日常で目にするものをほとんど全て，適切に高い精度でモデル化する．このため，実質的には，ほとんどのグラフィックスでの光輸送アルゴリズムはここで行なった仮定と同様の仮定を行っている．こ...

Here is my Japanese translation, part 2/3. Robust Monte Carlo Methods for Light Transport Simulation 光輸送シミュレーションのためのロバストなモンテカルロ法 著者(Author): Eric Veach Translated by Lx=d HY 1.1 光輸送問題 コンピュータグラフィクスの分野で光輸送シミュレーションは，現実のシーンと見紛うほどリアルな人工的な世界を作成する人々を助ける道具として利用されている．そのような道具には，物体の形状や表面の散乱属性などの仮想世界の環境の記述が入力されている．さらに，光源についての情報や，視点の情報も与えられている．これらの情報をもとに，光輸送アルゴリズムは現実の物理学に基いて光の振舞いをシミュレーションし，写実的で正確な画像を生成することを試みる． 1.1.1 なぜ光輸送は重要なのか 光輸送アルゴリズムの大きな目標の一つは，写実的な仮想環境モデルを人が効率的に生成することを助けることである．たとえば，現時点で，コンピュータアニメーションではよりリアルな光源をデザインすることに多大な努力が払われている．主な問題は，プロダクションで利用されている(スキャンラインやレイトレーシングなど)のアルゴリズムは通常間接光をシミュレートする能力がないか，限られた能力しかないことである．つまりライトが置かれた時点で通常は間接光が自動的に計算されることはほとんどない．そのかわり，それらの効果は人によって注意深く置かれた見えない光源によって模造されることがしばしばである．もし，我々がロバストな光輸送アルゴリズムによってこれらの間接光を自動で計算することができるなら，シーンのライティングを行う人の仕事はより簡単になる． 光輸送シミュレーションのその他の応用は予測可能なモデリングである．つまり実際に製作する前にこれから作成するものの外見を予測したいという欲求があり，これに応えようというものである．建築や製品デザインの分野ではこのような要求は明らかに必要とされている．これらの応用ではレンダリングの結果は客観的に正確であり，かつ，見た目も良いものであることが重要である． 最後にグラフィックスの分野での光輸送の技術を発...

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 のアルゴリズムがロバストとは，できる限り考えられるさまざまな入力に対して，破綻することなく，十分な精度の結果が得られるアルゴリズム，つまり入力に対して出力が頑健なアルゴリズムという意味でロバスト(頑健)という．本学位論文で，我々は本質的で重要な結果を得ることができた．すなわち，新しい理論モデルと統計モデルの構築を行い，新しいレンダリングアルゴリズムを開発することができたのである．一方で論文中で，本手法ではいったい何ができないのか --- 光輸送問題を解くための手法の持つ限界 --- に対する議論も行なっている． これまでに光輸送問題に関して多数の研究がなされてきたが，現存する手法には，依然として大きな限界が存在している．現存の手法は，通常入力モデルに大きな制限を課しており，この制限が成立するとして最適化を行なっている．したがって，この制限から外れた入力を扱う際には膨大なリソースを必要とする傾向がある．たとえば，入力シーン中には間接照明があまりないと仮定していたり，シーン中に存在する面の多くが拡散面であるなどという仮定をしている．そのため，この仮定を満たさないシーンが入力される場合，たとえば，間接照明の効果が大きいシーンや，拡散面でない物体で構成されているシーンをレンダリングしようとすると，時間がかかりすぎたり，メモリ消費が大きすぎるということがしばしば起こる．しかし，間接照明が...

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 節参照)． この後，より日本語と...