TU Wien Rendering #27 - Russian Roulette Path Termination
Russian roulette path termination uses a continuation probability at each bounce to randomly kill rays while keeping the estimator unbiased. Instead of a hard bounce limit that loses energy, you weight surviving paths by 1/Pi to preserve the expected value. Set higher probabilities for bright surfaces and lower for dark ones to reduce variance.
Chapters
Quick question, we will discuss the rationale and then we're done. When do we start tracing the rate? Well, what we did so far is really the cutoff. So we said that there's a maximum number of bounces that I'm going to compute, and the rest of it I'm not interested in. The problem is that this is a biased solution and we are missing some energy in the image. Because if I would compute many more subsequent bounces, I would accumulate more radiance. So I would get perhaps a brighter but a more faithful image to reality. And we can do much better than that. What's more, there is a technique that can compute an infinite amount of samples, an infinite amount of depth, and that boggles the mind a bit, because what is really happening, if I would need to compute physical reality, I would need to have a maximum depth of infinity. I couldn't even compute one sample per pixel because I would have to bounce the array indefinitely. But there's a mathematical technique that can give you the results as if you computed an infinite number of bounces. And this is against statistics and statistics and probability, usually very difficult to wrap one's mind around what is happening. But we can actually solve this problem. So how can we overcome this? What we're looking for is an estimator that converges to the expected value of the integral. Okay, that's fine, that's fine. I'm looking for the expected value. But having the expected value of, or looking for the expected value of something is one thing. But there's not only expected value, there is variance. So I may have multiple estimators. And what I'm looking for is one that has the lowest possible variance. What I can do here is after each, step, by step, I mean each bounds, I decide whether I will terminate the path. So, so I would stop this light path or I would continue. But if I continue, I multiply the collected radians with some. And the question is, what should this sum mean? Now, this I would like to relate to, for instance, Fresnel's law. In Fresnel's law, we could compute what is the probability of reflection? What is the probability of reflection? I hit that last window, and with some probability, I will continue my ray through the window. And with some other probability, I will get the ray reflector. Now, what I could do is I could run many samples and add them together. Or what I could also do is that I don't run many samples. I enter the window and I compute that there is an 80% chance of reflection and 20% for refraction. And I will send out only one ray in each direction. But I would multiply these by the relative probability of the event. So I'm not tracing 10,000 rays. I would send out one and I would multiply it by 0.8 in one direction and 0.2 in another direction. And then if I would do this, yes, I will compute more and more samples. But statistically this is sound. So what this means is that this converges to the expected value of the integral. And Russian roulette does the exact same thing, but it gives you an infinite number of boxes. So with a given probability I stop, and with a given probability I continue. But I will multiply the collected gradients with a factor. And this factor, for the Fresnels example, could be the probability of reflection algorithm. What does the algorithm look like? I choose a random variable, let's call it Xi on 01. And with the given probability, that's PI. I continue the light path after hitting something. Every bounce I throw a dice. And if I have this probability, I will continue my light path. But I will multiply the connected radians with something. I won't give you the end results as what you would see in the textbook. I'll try to show you the thought process on how someone can put together a technique. I will need to multiply it by something. I don't know what this something should be. We will find out together. And if I don't hit this probability, then I will terminate the light path. So we could imagine this as if I continue the light path, but I multiply all the subsequent gradients by zero. I spoiled the zero for the second question mark, so. Dammit. But you would have found this out in a second anyway. Okay, so I'm looking for the expected value of something Li. The hat means an estimation. And on the right side this is the actual Li. So whatever happens in the middle is some magic. But the constraint is that the expected value of the estimator should be the same as the original quantity that I'm looking for. There is a probability of continuation. And if I don't hit this probability, then I will stop. The stopping part is trivial. If I stop, then I will multiply this term with zero. So imagine that I continue my life path. I won't, because it's wasted time until infinity. But it multiplied with zero. Now the question is, what is the other question mark? What I know is that on the right side I would want to get Li. So forget this right term. What do I need to do with this expression on the left in order to get li on the right side. Raise your hand if you know the answer. I want you to take a few seconds and think about it. What do I need to do to get li from this expression? The rest is multiplied by zero, so this doesn't matter. Bayesiana. Okay, maybe. Maybe. Okay, yes, please. May I ask your name first? Okay. I think li divided by PI. Yes. Simple as that. Okay, so I kill the PI, because I don't see any PI here. So there's going to be a fraction and the denominator is going to be PI. So I killed this guy, but there's no one in there, and I want someone in there, and that someone is the li. So I killed the PI with my fraction and in the numerator there's going to be li. So if I do this, then what I am doing is going to be statistically solved. I'll try to give you the intuition again. This takes time to wrap your head around. It is almost like in the Freddy equation, that what you could do is you could send out one ray in one direction. Sorry, you could send out 800 rays in one direction and sum them up. Or what you could do is that I send out only one ray and I multiply it with 800. And no, I would not get the same result, but I would get the same expected value. And over time, the variance around this expected would shrink. If I do this many times. So this is the intuition behind the whole thing. What is a good choice for the PI? Because this has been a parameter so far. What should I put in there? Well, with a little scratch I could say, it doesn't matter. You could put many sensible choices in there and it would work. But quickly, let's review the cases where it would not work. Well, obviously there are two very stupid options. If you put PI equals zero, then this would mean that you would never continue your path. You would always stop. So this is obviously incorrect. What if I say PI equals one? Well, this means that I would always continue. I would never stop. Well, you could say, mathematically this is sound, but you could never compute one sample per pixel. If you're a mathematician, you would say, I have a Turing machine that would never stop. It doesn't make too much sense. If you're looking for a practical solution now, anything in between the two is completely fine. The only difference is because I've showed you that the expected value is the same as the actual quantity. Done. That I'm looking for. But the variance is different. So it is oscillating around the very same number. But the magnitude of the oscillation depends on this choice and what you can prove. But it is actually very easy to visualize that a good choice for the PI would usually be something that would sample brighter paths, longer and darker paths. I would want to terminate faster because this is the same as matching the green function with the blue function with the green bars. And we want to reconstruct the brighter regions more faithfully than darker regions, because this is what gives me the smaller error. So what you can plug in in there is for instance, the albedo of the material. So if you have a really bright white wall, then you would, with a super high probability, you would want to continue your path. But if you have really, if you encounter a really dark object, like the curtains on the other side of the room, you would want to stop with a much larger probability. So this is how Russian roulette works. We will also code this in the next lecture. You will see the whole thing that we've studied in code.
