Russian roulette termination in bi-dir path tracing back
(L) [2007/07/22] [Tecla] [Russian roulette termination in bi-dir path tracing] Wayback!I just finished implementing bidirectional path tracing in RenderSpud. I'm a little confused about how to apply russian roulette to the termination, though. In regular path tracing, it's easy to just pick a random number, compare it to the termination probability, and divide the next path vertex's contribution by the termination probability if we don't choose to terminate it.
In my bi-dir implementation, I choose whether or not to terminate it the same way, but I don't modify my vertex contributions. I figured that was still unbiased, because when we combine camera and light paths there is nothing random about how long the path is at that point. I'll bet my thinking is screwed up there, though.
If I am supposed to still apply that termination probability to my vertices, what is the correct way at each vertex (as I construct the combined path from the camera to the light)?
_________________
[LINK http://renderspud.blogspot.com/ RenderSpud development blog]
(L) [2007/07/22] [Lynx] [Russian roulette termination in bi-dir path tracing] Wayback!uhm i don't understand your argument...if your sub-path length is random, the sum obviously is too...
also, i'd say russian roulette doesn't modify the actual path contribution but the path probability. With path tracing there is always only one way to create a path, but with bidirectional path tracing it is important to distinguish this. Bidirectional path tracing lives from the fact that you can construct one path in multiple ways, and smart weighting makes the difference to path tracing really.
Veach says that you have to take russian roulette probabilities into account when computing the path probabilities, he explains it in his thesis.
However, i haven't implemented it yet, i still need to change some structural details in yafray before it will work properly...i should've read it before redesigning the core. And i have other changes going on, so i've delayed it a bit...so far it only works with one light, with at least two eye path vertices and fixed path lengths, the latter i could change of course, but what's the point when the important stuff isn't working yet.
(L) [2007/07/22] [necro] [Russian roulette termination in bi-dir path tracing] Wayback!I agree with Lynx, i don't understand your argument either [SMILEY Very Happy]
For unbiased BDPT the most important way of thinking is "each technique should be unbiased". By fixing s or t (lets say s) to a specific value and looking at all estimators with this value of s it becomes more clear that if we perform any kind of Russian roulette at this point the estimator stays unbiased. Same goes for all other values of s and t. In particular this is also valid if we do classical Russian roulette by the book while creating the paths, i.e. when creating the next vertex from the previous. I must admit this more a kind of combinatorical brainfuck, but in the end Russian roulette is applied for each technique with a certain probability that is the product of the probabilities encountered on creating the corresponding vertices.
So the solution is actually pretty simple (as long as anything in the context of BDPT can be called simple...):
It's completely the same as in path tracing, i.e. you construct both light and camera path just as in path tracing by continuing a path with probability p_rr and dividing the next vertex' energy by p_rr.
The only thing you need to care about is the change of the densities for multiple importance sampling (forgetting about this should not introduce bias but will certainly increase the variance):
if you sample vertex x_{i +1} from vertex x_i with density p(x_i -> x_{i + 1}) and apply Russian roulette termination with probability p_rr the new density is p_rr * p(x_i -> x_{i + 1})
I hope this helps!
(L) [2007/07/22] [Tecla] [Russian roulette termination in bi-dir path tracing] Wayback!Yeah, it does help. If you guys didn't understand my argument, then that means I was right that my thinking was screwed up. [SMILEY Very Happy]
So, if I understand correctly, the following process is still unbiased:
- Construct a camera path, and do russian roulette termination normally (dividing vertex energy by the continuation probability if we decide to continue)
- Construct a light path, and do the same thing (kick in russian roulette after a few bounces). The fact that we're going in reverse doesn't affect it (?)
- Combine variations of the two paths, leave the vertex energies as they are already stored (modified by russian roulette)
When I tried the above, rendering with more samples, it didn't seem to stop it from converging to a (seemingly) correct image. So I think I feel better about it now.
On another note, I discovered my specular surfaces in my bi-dir implementation are too dark, and when I include the light contribution at the very end of the path sometimes it gets completely blown out. I've got a few more issues to work out, it seems, but I'm getting pretty close.
_________________
[LINK http://renderspud.blogspot.com/ RenderSpud development blog]
(L) [2007/07/23] [bouliiii] [Russian roulette termination in bi-dir path tracing] Wayback!Super cool. A thread concerning MC rendering!
Just a remark concerning russian roulette. Russian roulette is a technique that given a random variable produces another one by combining it with a bernoulli RV. In other words, if X is a given RV, you build Y such that:
Y = 0 with proba 1 - P
Y = X / P with proba P.
Ok, if X is an unbiased estimator of mu then Y is also an unbiased estimator of mu.
How does it work in path tracing ?
Actually, take the rendering equation and expand it. You will have an infinite sum of integrals. The goal is to compute each of them (it is a bit different with the path integral formulation given by Veach where all paths are taken into account in one integral but it is off-topic here). All pqth tracing algorithms propose to evaluate ALL integrals at a time with correlated estimators: The path you use for length k is used for length k+1. As it is impossible to evaluate all integrals, the russian roulette is used to set that after some random rank, all contributions are supposed to be null.
How compute the density of a path? When you use path tracing, it is just the probability to reach this rank multiplied by the density of the sequence (density of the first point multiplied by the conditionnal densities of the succesive bounces). If you use bi-dir payh tracing, the light parts and the camera parts are independent: the density of a connected path is therefore the product of the densities of the two sub-paths.
these are very stupid remarks but it is important to formalize the problem to make it suitable to a MC renderer:
- specify the sampled space
- specify the integrand (a three point form as proposed by Veach is really easy to understand)
- specify the integrals --> what is the measure associated to our space ???
- specify the random variable families which are used --> the samplers and the densities
A little remark about multiple important sampling in bidir path tracing --> it is not really MIS since the samplers can build each path with many different manners. Therefore, the densities of a path is, *by definition*, the weighted sum of the densities. Therefore, if you have generated a path with p camera points and q light points, the SAME SAMPLING process could have generated it with another combination of camera and light points. By definition, you have to explicetely compute the density according to all manners. It is therefore a bit different of a simple estimator combination as it is done in the second step of the algo when you combine all paths (funny remark: the resulting density is the same as the one given by the balance heuristics!)
Everything may seem blurry but I will strongly advise to read Veach PhD. I also made in my PhD a chapter directly concerning sampling processes in MC rendering. I propose some inefficient path tracers which directly use the path integral formulation. You can for example easily design a bidir path tracer by connecting only the ending points of the light path and the camera path. It is not effective but may be used for example as an initial step of a Metropolis Light Transport or to generate VPL with a sampling / resampling method with a specific target density and so on.... Indeed some algorithns like Metropolis Light transport and its derivatives require to work directly in the whole path space (all paths no matter their length).
BEn
(L) [2007/07/23] [bouliiii] [Russian roulette termination in bi-dir path tracing] Wayback!Last thing, for MC rendering, I think a good thing while coding is to:
- read a bit about theory of measure and Lebesgues Integration
- learn some probability theory (at least, Kolgomorov axioms, definition of random variables, laws of large numbers, Central Limit Theorem ...)
- take some books about Monte-Carlo integration (basic results like importance sampling, stratified sampling ....)
- idem some statisitics (it is close) --> things like MCMC samplers, importance resampling, boot strap ...
- REad Veach PHD!!
I think this is a good way to learn and formalizing everything may really help ! [SMILEY Smile]
Ben
(L) [2007/07/23] [Tecla] [Russian roulette termination in bi-dir path tracing] Wayback!I have read parts of Veach's thesis, mostly because I wanted to understand MIS better and start to get my mind wrapped around MLT. I figured bi-dir path tracing would be a walk in the park compared to MLT, but it has plenty of nuances itself, I've discovered. I'll have to go dig in, because Veach seems to have quite a bit of detail on some of the more esoteric aspects of implementing all of the standard algorithms in there (minus photon mapping).
So, back to path termination, if I get the probabilities and energies at each vertex, and just keep the running weighted product from the camera all the way to the light, the final result still is correct when camera + light paths are combined because the densities multiply together along the way. Nice. Thanks for the theory refresher!
_________________
[LINK http://renderspud.blogspot.com/ RenderSpud development blog]
(L) [2007/07/23] [greenhybrid] [Russian roulette termination in bi-dir path tracing] Wayback!I recommend to read the *whole* Bible, not only the later chapters, it will help you a lot, and will also give you interesting glimpses at other disciplines outside CG, but which are still related. I think esp. the latter fact about watching to "the outside" brought us the great sabre from metropolis. I also recommend, if you do read it all, keep some math-resources in the range of your fingers (I failed to do that, and missed some neat detail in the consequence; it would also be helpful to understand the art of mathematical proof (a wizardry I am personally not familiar with, how bad...[SMILEY Sad] ) )
_________________
[LINK http://xitrace.org/ xitrace.org] | [LINK http://greenhybrid.net/ greenhybrid.net]
I love the smell of freshly cooked images in the morning....Yummy.
back