 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, 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? But 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? The 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 than there will be links. You click them and then you can read either the paper or some writing about them. So let's get started. Park 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 race from the eye or the camera. You bounce them around the scene if you would like to earn some style points. And 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 dishought as many light paths per second as possible. What is a common problem that people encounter with this? 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. Onwards 1993 by directional 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. 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 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. So it's not a point light source, it's an aerial 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 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? By direction of 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 try 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 is a huge difference for this indoor scene between the two. So it's definitely worth looking into. Now what is actually difficult about biorectional 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 sampled the very same integrand. And one Monte Carlo process would have some variance and the other would have some other variance. So different regions of the path space, 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 Weach in his landmark thesis of beautiful, beautiful works by direction of path tracing is one of them. And 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 that that he do people actually read this huge poem 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 will 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 Veech 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 some 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 and most of my samples are going to be wasted and I'm going to be 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 1, t equals 5, you can see that we have caustics in there. And the caustics is almost 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 is also caustics but it is really noisy. It is not systematically looking for caustics, it just happened to hit it but it is 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 not easy but Eric has proven really good and super simple technique on how to do that. And now look closely to the image. This is without naive biorectional power pressing, 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 5, t equals 1, 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 in shader toy, the nice classical V-Sync where there is light source sampling and BSDF, DRDF sampling. And it doesn't matter if you sell BSDF or DRDF 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 set 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 am 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 small paint. And you can run it super simple and hopefully super understandable. I think it is less than 100 lines of code. So what we now know, bi-directional 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 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 bi-directional path tracing and even better, there is a nice comparison quoted up also on shader toy. 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.