A personal annotations of Veach's thesis (22)

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 projector projects an image to the wall and sample the wall would be more efficient. This is my understanding of the basic idea of bidirectional path tracing.

Overview idea of Metropolis sampling algorithm

There is a case that bidirectional path tracer also has problems to find some kind of paths. Veach's paper's example is that: ``there are two rooms, one room has a light source, other is dark room that doesn't have any light source. There is a door in-between the rooms, that is almost closed. The camera is in the dark room.'' The light only passes through the gap of the door. To avoid bias, we could not sample the door's gap only. (Is we do that, then there will be a path that can not be detected.) If we can find a nice path once, we should exploit something similar path, but not the same ones. This is the Metropolis method. (Metropolis is a person's name who proposed this method.)

Veach proposed the initial guess is done by a bidirectional path tracer. If we could find a path that can reach to any light source, we perturbate the path and exploit more paths exist or not.

By the way, I used some kind of variational method for geometry processing. A problem is interpreted to some kind of potential energy problem and is applied a variational method. But the energy design is the problem. Once you have a nice energy, then perturbate your solution and get the better solution. For the light transport problem, it seems difficult to find a derivative, but, the basic idea of Metropolis algorithm looks surprisingly similar.

I enjoyed the Veach's paper. This paper uses a kind of basic and orthodox methods. Basic and orthodox are well established and so many times challenged, therefore I like them.

My personal annotations of Veach's paper ends now. Thanks a lot. So, what will be the next?

A personal annotations of Veach's thesis (21)

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 summarize them after Chapter 9.

If we could sample infinitely in all the directions in the environment, but our computational resource is usually limited. Therefore, we use several different sampling methods. Each sampling method has advantages and disadvantages. Multiple importance sampling method is: how to combine them and exploit all the benefits. After the combination, Veach showed it is possible to stay unbias. This is great. Also this is not only for the light transport method, but this is general.

The proposed sampling methods are: sampling method that awares the light source direction, sampling method based on BRDF. If we know where the light comes from, or which direction has no light, we could sample them more efficiently. For example, it is useless to sample the direction that has no light. These sample doesn't affect the result. BRDF gives us a hint, most of the light comes in a specific direction. Another possibility is visibility.

Thanks to Daniel, Leo, and Carsten.


A personal annotations of Veach's thesis (20) pp.310-321

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.

Thanks to Leo and Carsten.

p.321 Implementation

It's a bit details, but I have a question in the following equation.

I computed this as follows.

I may have a mistake. Actually, today I write 3 - 4 = 1 and my matrix becomes unsolvable when I try to get a row reduced echelon form. I was astonished when I compare my calculation and the output of the octave. But, still where is N_0?


Why I wrote a blog of ``A personal annotations of Veach's thesis.''

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 had a product, therefore, no customer yet. The company decided that no customers, no department. I was a bit sad, but also understandable. We built a new department that concentrate to care the customers and I was assigned to that department. First I even could not speak customers directory. But, now my responsibility becomes larger and I assign some tasks to others and talk with the customers. In one project, I had a full responsibility and I even managed our managers. It turns out I could do this well. But, I realized that I hardly solved technical problems.

I like to solve technical problems. Actually, that was the reason I chose this company. When I realized it, I was not happy anymore. This is a problem. That's my area -- solving a problem. I made a plan to solve the problem, and started to execute it. First I talked with my boss, my current boss is also a nice boss and he understands the situation. Then, I asked a meeting with the upper management. I made a presentation and asked development tasks. I asked a few possibilities to join one of our development teams. One of the answers is that I am not good enough to join the team. It is true, I have not so much experience yet, but I want to have a new challenge. I said I tried to learn, though they think that I might achieve nothing in five to ten years. That sounds an interesting challenge. I like challenges. Now you see, why I read the Veach's paper as my first project. This is one of the projects to make me more useful for the company. Here we have many specialists, I just ask them questions and I can easily get the answers as you have seen in my blog. This environment is great for learning. I also study some more topics now.

Veach's paper is comprehensive and complete. It is fun to read such paper. Some of the mathematics are familiar with me, and some I learned. Today, I am happy that I can keep my word.


I thank all my friends who answered my stupid questions. I also thank their great patience. Some of them I recorded in this blog, as ``A personal annotations of Veach's thesis''. I will continue to write some more summary about the paper.


Bookstore and me

This article is neither about a computer nor mathematics, but bookstore.

When my friends visit me from Japan, I always ask some books. I even asked books when one of my friend's sister comes from Japan. I also order books via Amazon.co.jp, but delivery cost is significant, so I could not do it so often. I am not sure nowadays Japan's bookstore. I like the bookstore concentrate the books, but, Internet bookstore also has the same books. Then, the small shops becomes obsolete.

Here in Germany, many of the bookstore has a cafe, also put sofas, sometimes playground for children. When I was a kid, my parents put me a bookstore in a department store, I was quite happy. Though, I once kicked out the bookstore since I read whole books in one shelf without buying.

In Muenchen, Marienplaz, there is a bookstore that has a cafe. From the cafe, you can see the famous clockworks. I visited the bookstore because of this cafe.

I think next generation bookstore needs this atmosphere in Japan. The concept is a young couple come to a date, parents and children comes to stay some time at a bookstore. Yet, if I come to a bookstore, there would be Google or Amazon interface, and I can directory links to the physical position. Or I can use my smart phone to find the book. Though, I don't have any smart phone.

For me, a bookstore is a place to go journey. I sometimes just visit to bookstore. Just to see any books. Therefore, I sometimes don't want to search a book. In Shimada Kazuhiko's ''Moeyo Pen'', a cartoonist visits to a bookstore and see the pictures in a book and imagines that he is in New York, sitting on top of the statue of liberty. Cool. That is same for me. A bookstore is the place where my imagination unleash. I don't feel in the net bookstore, I think it could be, but not yet so far.


A personal annotations of Veach's thesis (19) pp.272-282

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 low and this kind of bad luck is visible.

When the number of samples increases, this kind of bad luck situation becomes less effect since the difference of density distribution  p_1 and  p_2 . This is an example the variance is large when there are less samples.

p.282 Figure 9.12(a)

Figure 9.12(a) shows the dark and noisy region near the light source. But this method is light source sampling, therefore, the darkness isn't caused by sampling miss. So why is neat the light region dark?

The reason is sample points, that is perpendicular to the area light, are too close to the light source. In this setting, the cos term becomes almost zero.

Also if the sample point is too close to the area light source, geometry term is unstable shown in Figure 2. If there are some distance between sample point and an area light, when the sample happens at upper region and lower region in the light source, the distance is rather stable. On the other hand, the sample point is too close to the light source, the distance can be almost zero to the other side of the light source. This causes high variance. This is a kind of paradoxical situation, near the light source points becomes dark and noisy.

Thanks to Matthias, Carsten, Daniel.

A personal annotations of Veach's thesis (18) pp.264-267

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 not. This is kind of natural that when we combine several solutions, this is great of this paper.

p.267 Balance heuristic 2

Figure 9.3 is the pseudo code of balance heuristic estimator.

I would like to add some annotation of this pseudo code since I think this code is important.

  •  i means i-th sampling technique. k is also used as k-th sampling technique, but this is used to distinguish different iteration.
  •  n is number of sampling techniques. Therefore, i = 1, 2, ..., n. k is also the same.
  •  n_i is the number of samples of i-th sampling techniques. Therefore, the line 2's N is total number of samples. For example, technique 1 samples 5, technique 2 samples 3, then n_1 = 5, n_2 = 3, N = 8.
  • p_i is the probability function of i-th sampling technique.
  • X is a sampling point.
As usual, thanks to Leo.


A personal annotations of Veach's thesis (17) pp.227-240

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 cases the value becomes more than 1. But in any cases, if we integrate in some domain, this should be equal or less than 1.

p.236 Scattering events at Psi_L and Psi_W

This is a cool idea. We consider the light source is a reflector that its light source is infinitely close. If we think as like this, every scene element can be a reflection surface. No need to think the light source is a special case. For example, a object emits light case is not the special case anymore.

One of the Feynman's books (I think it is Surely You're Joking, Mr. Feynman!) has an episode. Feynman tried to model an electron as self affecting particle. Since the center of the electron seems singular point of the electro magnetic field. He tried to get rid of this singularity. I think he wrote the idea doesn't work unfortunately, but, this Veach's idea just reminded me this story.

p.240 Chains

I think the chain here explained is
But he did not write this in his notation. I just wonder why he did not write that in this way. Or I might be wrong.

Thanks to Leo and Daniel to give me the answer regarding with my questions of these pages.