TU Wien Rendering #32 - Bidirectional Path Tracing, Multiple Importance Sampling

Now, before we start the algorithms, one more time, a disclaimer. These results are coming from scientific papers. And if you come up with a new method, you want to show that this method outperforms existing methods in the scenes or in the setups that you have tried. And some people are very open about the limitations of the techniques. Because if I have a technique that's better than the best technique out there on this scene, then that's great, but it doesn't mean that it will be better on all possible scenes. And some people are very candid about the limitations of the algorithms, and some of them are not so candid about this. But with time, as people start to use the algorithm, these possible corner cases or just simply difficult cases come up. So what do I mean by this? What I mean is that if you see great results, that there's an algorithm, wonderful results, it's the best thing ever. Okay, but always have a slight doubt whether this algorithm would be robust enough. Would it always work? When would it not work? Because don't just extrapolate from one case. There may be drawbacks that are maybe not so clear where you first see the algorithm. Now, mathematical details again will be omitted mostly. But what we are interested in, the motivation for each algorithm. What is the key idea? What are the advantages, disadvantages, how do the results look like? Where can you access implementations? Where can you try these? And for most of them, some additional literature. If you think that, wow, this is a really great algorithm, I would like to know more. Then, then there will be links. You click them and then you can read either the paper or some writings about them. So let's get started. Path tracing from 1986. Super old stuff. But this is the very first and the easiest way to wrap your head around global illumination. You start your rays from the eye or the camera, you bounce them around the scene. If you would like to earn some style points, then after every bounce, you would also trace shadow rays towards the light source. This is next, event estimation. This usually lowers your variance and then you end up somewhere. You compute all these light paths and jolly good, you don't do any simplifications to the integrand. You exhaustively sample all possible light paths. There's no interpolation, no tricks, no magic. So this should be an unbiased and consistent algorithm. Unbiased, the error is predictable. I know that if I add more samples, there's going to be less error. And I know that sooner or later the image is going to converge because I am sampling all possible light paths There are. It is impossible that I would miss something now. There may be corner cases, but they are really difficult, but fortunately well understood corner cases where there are contributions that you may miss. I will discuss this during the next lecture. What are the advantages? It's simple. It's also very easy to implement. I didn't write it there. But it also parallelizes well. Why? Because it's a dumb algorithm. It doesn't do anything tricky. It doesn't build super difficult and super complicated data structures. You just put it on the GPU and you just cram out as many. And you just dish out as many light paths per second as possible. What is a common problem that people encounter with this? Well, for instance, caustics converge very slowly because caustics are usually light paths that are extremely improbable to be sampled. And you would need to compute many, many samples in order to hit these caustics many times, in order to clean them up, clear them up onwards. 1993 bidirectional path tracing what is the motivation behind this guy? Well, imagine a scene that this is your camera on the left and you have a light source, for instance, enclosed in this object, which is for now, for the sake of experiment, a black body. So if you hit it from anywhere, it's not a glass light bulb or anything like that, it's a black body. So whichever part of the container you hit the you won't continue your light path. Now you would start a path tracer. What do you do? You start tracing the rays from the camera. And it is not too likely to hit the light source, is it? So it's not a point light source, it's an area light source. It is possible to hit it, but it's not very likely. Now, after the previous lecture, you would say no problem, next event estimation, what do I do? I don't wait until I hit the light source. I would send out shadow rays after every bounce and I would get some of the energy of the light source, the direct contribution of the light source. Great. But the problem is that this also doesn't work because most of the connections would be obstructed because if I hit this very first bounce, I cannot hit the light source because there is the black body that contains it. After the second bounce, I also cannot connect to the light source. It's again, even with next event estimation, we most of my samples are wasted. We are tracing random rays. It is very unlikely to hit the light source. And even if I connect to the light source, it is very unlikely that I will See an obstructed connection. What is the solution? Bidirectional path tracing. What happens here is that I am not starting only one light path from the eye. I start two light paths, one from the eye, as with regular path tracing. And I also start light paths starting out from the light sources. This is called light tracing. And I tried to combine these two techniques into one framework. So what it means is that I start one or a given number of bounces from the eye, I start a given number of bounces from the light source, and then I connect these light paths together and I pretend that I just built this light path instead. And now with this, I have a much better chance to sample these light sources because I would have the opportunity to get out of that small zone that is otherwise difficult to hit from the eye. Now let's see the difference between the two techniques. These are taken after 10 seconds for the very same scene. And you could say that there's a huge difference for this indoor scene between the two. So it's definitely worth looking into. Now, what is actually difficult about bidirectional path tracing is that theoretically it's very simple. There is not one light path, there are two. And I connect them in all possible different ways. Now, what you should take into consideration is that this is actually two Monte Carlo processes. One Monte Carlo process is when you start out from the eye and you hit a diffuse or a glossy object, then you would start to important sample it important sample the vrdf. This means that I would take the likely paths more often. Now, if you start a light path from the light source, then what you would be sampling is actually the distribution of the light source itself, because regions that are visible from the light source would be sampled extensively with light tracing, because you're always hitting them, they are in front of you. And that's a completely different sampling distribution. So you can imagine as if you had two different Monte Carlo processes that sample the very same integrand. And one Monte Carlo process would have some variants and the other would have some other variants. So different regions of the of the path space, different and also different regions of the image would converge quicker with light tracing, and different images would converge quicker with standard path tracing. And I would like to combine these two techniques together. And this is entirely not trivial. Variance. I've written noise in there to be more intuitive, but we're talking about variance. Noise comes from variance. Variance is an additive quantity. So this means that if I have two Monte Carlo estimators of given variance, and if I would just add them together and average these samples, then I would also average the error of the two. And that doesn't give me a great result, because there are some regions that are sampled by light tracing well. And there are regions that are sampled by path tracing well. And I cannot just cut out the good parts from each sampling technique because the error would be averaged. And this can be solved in a meaningful way in a way that is actually proven to be optimal in some sense. And this technique is called multiple important sampling. Now, multiple important sampling was brought to us by a person called Eric Veitch in his landmark thesis of beautiful, beautiful works. Bi directional path tracing is one of them. And he, if I remember correctly, last year he got an Academy Award for his work. This is basically gone. This is basically the technical Oscar award, if you will. And in his acceptance speech, it was really funny because he has a daughter and his daughter had taken a look at his thesis, which is hundreds of pages of heavy integral calculus. And she asked daddy, do people actually read this huge tome of knowledge? And he finally can say that, yes, people actually do read that. We read it like the holy Bible. Multiple important sampling is among one of his discoveries. And it is maybe it's a bit subjective, maybe the most powerful technique in there in all rendering. And I will show you plenty of examples to convince you that this is so. So on the left, let's forget about the middle example for now. Let's just compare the left and the right. You can see that there are many artifacts and many of these fireflies that can be suppressed by this technique. So I can unify multiple sampling techniques in a way that wherever they do really bad, I can just forget that. And I would take only the best samples for each region. Let's take another look, which is maybe even better. This is called, at least this is what we call a vege pyramid. This is created with bidirectional path tracing and the code below Each image means that we have taken a different number of steps from the light source and from the eye. So in every image, you see one given number of bounces. So if you would have path tracing, you would get like 10 or something images not in a pyramid. One image would be the first bounce. Second image would be the second bounce. Third image would be the third bounce. For bidirectional path tracing, you have a pyramid like that because you subdivide them to the first bounce from the eye and the sum bounce from the light source. So this is now a two dimensional thing. And you can see that some of the effects are Captured really well in some of these images. And there are some other images which are absolutely, absolutely terrible and really noisy. So for instance, if you take a look at the two sides, these two sides mean that I am hitting either the camera or the light source by accident. And if you have a small light source, which we actually do look here, then this is a relatively low probability event. And if this is a low probability event, then most of my samples are going to be wasted and I'm going to have a noisy image, not a well converged image. So on the sides I have really low probability events. And these are samples that I really don't want to use. Imagine that I would add all of these images together, average them. I would have plenty of noise from the noisy ones. Now what if I could say that if you take a look at s equals 1t equals 5, you can see that we have caustics in there. And the caustics is almost immediately converged in there. It is definitely good in a sense that I would for caustics, I definitely would want to use these samples and not the ones for instance in S equals 0, T equals 6 because there's also caustics. But it's really noisy. It is not systematically looking for caustics. It just happened to hit it. But it's not good at sampling it. And I don't want to average these guys together. What I would want to do is I would want to give a large weight to s equals 1, t equals 5 on caustics and I would just grab it in there in my image and I would just forget about the other contributions. And this is mathematically doing this in a mathematically sound way is, is not easy. But Eric has proven a really good and super simple technique on how to do that. And now look closely to the image. This is without naive bidirectional path tracing, without multiple important sampling. And now what you will see is if we add multiple important sampling. So look closely, see the difference. There are many noisy images that were completely shut down because they were not really good at sampling different parts of the space of light paths. Some images are not good at anything at all. Take a look at the two sides. And there are images where I can take caustics from. For instance, like the S equals 5T1. It seems to have been even better at sampling caustics because this s equals 1 t equals 5 was also pretty good, but it was shut down by the other technique that was even better. So this is an amazingly powerful technique in order to create even more Converged images. If you have multiple sampling strategies now, you can also play with it. It is implemented on shadertoy, the nice classical Veatch scene where there is light source sampling and BSDF BRDF sampling. And it doesn't matter if you say VSDF or BRDF in this case, by the way, but you remember, so you can play with it and I encourage you to do so. It is lots of fun and you will see what kind of light transport situations are captured well with which sampling technique and how to unify them in a way that everything looks converged almost immediately. And also, what does a good engineer do? Well, a good engineer obviously is interested in the problem. So I just sat down and also implemented the same thing in a simple example in 1D to make sure that everyone really understands what is going on. So this is a simple Monte Carlo sampling problem in 1D. I have a function that I would want to integrate. If I remember correctly, I'm integrating a Gaussian and I would like to sample it with two different techniques. So this is two different Monte Carlo sampling processes. And I would want to take only the best samples in order to get an approximation which has the least variance. And there are multiple ways of combining them together. And there's also naive averaging which just averages the error. So it would give you back all of these images from the side. And I write out what are the exact Monte Carlo estimators for different multiple important sampling estimators as well. So take a look. It is now part of smallpaint and you can run it super simple and hopefully super understandable. I think it is less than 100 lines of code. Okay, so what we now know, bidirectional path tracing, definitely better convergence speed, especially in scenes where you are not that likely to hit light sources, so especially in indoor scenes. And you will also get quicker convergence for caustics because you will have sampling strategies that are very efficient in that. So caustics are usually visible from light sources and you will sample them very often. So there's going to be at least one estimator that captures it well. So. So if you use MIS multiple important sampling, you're going to have caustics covered very quickly. Now, it is definitely not easy to grasp and it is definitely not easy to implement. So it requires quite a bit of an effort, even if it sounds very intuitive. It is, but it is not easy. This is also a brute force method. This also samples all possible light sources, and therefore this is also unbiased and consistent. Some more literature on bidirectional path tracing. And even better, there is a nice comparison coded up also on Shadertoy. So when you are at home, just fire it up and you will see the difference evolving in real time on your GPU on an indoor scene.