TU Wien Rendering #33 - Metropolis Light Transport

Okay, let's continue with even more good stuff. Metropolis Light Transport straight from 97. The key idea is to seek the light. This is the thing that I always hear from the artists who use the algorithm. What we are trying to do is sampling brighter light paths more often than darker light paths. That's it. That's the basic principle. That's what we're trying to do. And educated people would immediately say that, hey, but isn't this what we have been talking about at important sampling? Isn't this conflicting with important sampling? What is important sampling? Well, it means that if I have for instance, a glossy reflection, a glossy BRDF, which has a really high probability of sending rays out in the perfect reflection direction, so almost like a mirror with a high probability it would behave like a mirror, then I would like to have a high probability of actually sampling that light path proportional to the shape of the brdf. And this we can do through important sampling. Okay, but imagine a case where you would have a glossy reflection covered from almost every direction by black bodies. So it doesn't matter if I import and sample the BRDF correctly, because after I import and sample the BRDF and the light is coming to the next bounce, it's always going to hit the blackbody and it's going to be absorbed. I'm never going to continue my light path afterwards. So even though I would important sample this one bounce, I am not important sampling along the whole path, because I have important sampled this one bounds correctly. But I didn't know that globally I'm just heading to a region that's really dark. And what Metropolis Light Transport gives you is something that is not really referred to, but I like to call it multi bounds important sampling. So it may take suboptimal decisions and it may send out rays in a direction that is not so likely for your BRDF if it knows that it's going to end up being a bright light path. So for instance, if you have a glossy interreflection that would be mostly sending rays out in this direction, but there is complete darkness in there, then what it would do is it would actually send more rays towards the light source, which looks like a suboptimal decision in there in that brdf, but over the whole light path, that is actually going to be something bright. So this is the key idea behind Metropolis Light Transport, and I'd like to give you an intuitive example of that. So imagine that you have the camera in this room in the scene, and you have a light source only in the adjacent room in the Next room. And this next room is separated by a wall and the door that is slightly ajar. So it is just opened just a bit. And all the light that you see is coming through that door. And if you imagine, for now, naive path tracing, what am I doing? I am sending a ray through the first pixel and I'm going to bounce it around the scene. And it is very likely that I will never find the light source. And I cannot even connect to the light source. It's in the other room. I'm going to hit the wall or the door and imagine that I'm computing thousands and thousands of samples and I finally get to hit the light path that is actually connectable to a light source. If we are doing path tracing, you can imagine that I'm starting from here. If you take a look at the arrow in there, it gives you the intuition that maybe we are doing light tracing. We are shooting light rays of light from the light source and we finally get into this room and hit the camera. There's finally a good connection. After thousands and thousands of samples. I finally have one contribution before that.00000 and my CPU is basically dying on 100% load. Nothing gets out of there. Now imagine that I finally found a light path that makes sense, that has a contribution. And then I would suddenly forget about the whole thing and I would again start sampling completely random light paths and get the 000 again. Now it would be a crime to do that, wouldn't it? What Metropolis is doing is essentially trying to remember which are the paths that make sense. And if they find something like that, they are going to explore nearby. So they are not going to shoot out a completely random sample for the next sample. It's going to take this one sample that made sense. Finally a connection. And then it's going to add very small perturbations to this light path. What if I shoot this in an angle that's just a bit changed? And what you can expect is that most of the time it will give you again some amount of contribution and you don't have to start from scratch. So basically you can use all of these knowledge into your advantage. How does the difference look like? Well, this is the scene with bidirectional path tracing after 40 samples per pixel. And now if you look closely, you will see Metropolis after the very same number of samples per pixel. So this is bidirectional path tracing. And now Metropolis is the same number of samples. So if you take this knowledge into account, most of your samples are going to be Useful. Just another look. Bidirectional path tracing. Metropolis and bidirectional was already a good algorithm. It's not a naive path tracer, it's a good algorithm. A naive path tracer would be even worse. Another example, some nice volumetric caustics with naive path tracing and an equal time comparison with Metropolis light transport. How does it work exactly? Mathematical details, but just enough. Just enough to understand the intuition. What we are trying to do is important sampling. What does it mean? It means that I am computing discrete samples of F over P. F is the function that I would like to integrate. P is a sampling distribution. What I'm looking for is to match the blue lines with the green bars, if you remember. So it means that if the function is large somewhere, it means that the image is bright somewhere or the path space is bright somewhere. Then I would like to put more samples in there. So if F is large, then P should also be large. This is what I'm trying to achieve. Now how do I actually do this? I have some high dimensional function or if I'm doing local importance sampling, then I have a BRDF function. How do I important sample this? The trivial solution is called rejection sampling. Basically what it means is that I would like to compute. Samples from a sampling distribution. So here you see something that is like almost a Gaussian. But imagine that I cannot generate samples out of this function because what do I have in my C code? Well, I can generate uniform random numbers, but this function is not uniform random numbers. So what I can do is I can sample an arbitrary distribution function if I enclose it in a box and I throw completely uniform random samples on this box. So it is almost like drawing your function on a sheet of paper and throwing random samples at it. Now I cannot generate random samples out of this function, but I can generate random uniformly distributed samples. And the scheme is very simple if it is under the function. I am going to take this sample and pretend that I've generated that sample in the first place. And if it's out there, I'm just going to kick it out. So if I do this, I would have samples according to this almost Gaussian. This works well. But this is not what we are doing in practice. This is very inefficient and hopefully you can see from the image why this is an inefficient technique to do. So someone please raise your hand and help me out why this is not efficient. Okay, that's true. Thanks. So there's tons of rejected samples. Most of my uniformly Generated random numbers are completely wasted again. So there must be some technique that's better than this. Well, there is, but I guarantee that it's not going to make you any happier when you see how it is done. So there's lots of rejections. And this can be analytically. This problem can almost always be analytically solved by a technique called the inverse transform sampling or the Smirnoff transform. And this takes a bit of work, but I'll just briefly show you how it works. And if you are really interested in the details, then please take a look at this document. So I'll show you what you have to do. You have to do all of these calculations and then you will have your sampling distribution. What do we have at the end? Let's start with the intuition. We have uniformly generated random numbers. This is the xi1 and xi2 at the end. And I want to do some transform to these numbers in order to get an arbitrary sampling distribution. And what they are essentially doing is you have a probability distribution function, you want to sample from that. It can be like a Poisson distribution, an exponential distribution or some custom brdf. And if you integrate the PDF, you are going to have a cdf. So you integrate the probability distribution function, you will get a cumulative distribution function. And this can help you in this transformation from uniformly generated random numbers to the actual function. Now this is very intimidating, isn't it? Imagine that whenever you come up with a new BRDF or any kind of function that you would like to sample, you would have to compute all this. And not only that we were doing this for BRDFs. So I can import and sample 1 bounds. Again, I emphasize that it means that if I hit the table, I locally know what are the good outgoing directions because of the material model. But it doesn't mean that it's globally a good idea, because there may be this completely black curtain next to it, which I'm going to hit and all of the energy is going to be absorbed. What does Metropolis give us a solution to this? So it's important sampling not only for one BRDF, not only for all possible BRDFs, but an optimal important sampling along the whole path. So this means that it will know that if there is a path that is 15 bounds long, but it hits something that is really bright and it transfers a lot of energy. It will know that I will need to sample this light path and nearby, and it is not going to trace many rays towards the shadow regions. How does it work? Again, intuitively it runs a Markov chain process and there is, for Markov chains, there is a steady state distribution. This means that we have been running the Markov chain for a while. And if you do that, then it promises you optimal importance sampling for any kind of function without doing anything. And I hope that it is understandable. How really amazing this is because it is actually a simple sampling scheme that you can write down the pseudo code in five or six lines and it gives you optimal importance sampling. So this is really amazing. And I emphasize again that this is over multiple bounces, not important sampling one brdf, but over whole light paths. There are different variants of Metropolis Light Transport. The original is the Veatch type Metropolis. This is the one that was published in 97. It is a great algorithm. It has different mutation strategies. It means that it has different strategies of changing the current light path into a new one in a smart way and not randomly. The problem is that almost no one in the world can implement it correctly. So it was published in 97 and the first viable implementation that came out was in the Mitsuba Render implemented by Vento Ayako and it was around, I think 2010. So just a few years ago, the original Metropolis Light Transportation also attributed to Eric Veitch, no one in the world could implement it. I honestly don't know what was going on because he published it in 97 and it took the very least 13 years for the first super smart guy to implement correctly. I don't know what he was doing in the meantime. Maybe he was laughing on humanity that no one is smart enough to deal with this and maybe we don't deserve this algorithm. I don't know. It's not for the faint of the heart. It's a really difficult algorithm. Yes. He was working for Google. He's working for Google. That's true. After the PhD, did he go immediately to Google? So he's basically working on AdWords, how to get more money out of advertisements. It pays. It definitely pays well. And who knows, I mean, if Eric Veitch is working on it, there's gonna be some good stuff in there, I guarantee you. But I have to say that his face looked actually quite delighted when he got the Academy Award just recently for his work that was at the very least 15 years ago. It's still used all over the industry. Multiple important sampling, bi directional path tracing. Metropolis is all over the industry now. The Vich style Metropolis is really difficult. Fortunately, there are also smart people at my former university, namely Czobo Kelemen and Laszlo Silmaykolos. They came up with A simplified version of the algorithm which is almost as robust, but is actually quite trivial to implement. It is also implemented in small paint. It is called the primary sample space Metropolis. It is now implemented by one of my students from a previous year rendering course. And it is in small paint, so you can give it a try. Basically, it does complicated sounding, but otherwise simple mapping from an infinite dimensional cube where I can generate infinite dimensional cube means arbitrarily long vectors of independent randomly uniform random generated numbers. And these random numbers are somehow transformed into light paths. So what the algorithm does is there's a probability that I am computing a completely new light path. And if I don't have this probability, then I'm going to stay around this light path and and explore nearby. What does it mean? Practically if I find this super difficult light path from the other room to here, then I find a really bright light path. The algorithm will know that, okay, I'm just going to add slight perturbations to this light path. I'm going to stay around here. And sometimes it will start to look around for random samples. There's also a visualization video on YouTube. If you take a look, you will immediately understand what is going on and some literature about these algorithms. Now it is also a sampling scheme. So Metropolis you can implement together with path tracing or bidirectional path tracing. And therefore this is also an unbiased and consistent algorithm. And it is very robust. It is tailored for really difficult scenes. So if you have a scene with a lot of occlusions, difficult to sample light sources, difficult to reach light sources, use the Metropolis. But if you have an easy scene, this is not going to give you much because the Metropolis is a smart algorithm. It takes longer to compute one sample than a path tracer. And if this smart behavior of the algorithm, it does not pay off, then there may be scenes where the Metropolis is actually worse than a path tracer. So if you have an outdoor scene with large light sources and environment maps that you hit all the time, don't use Metropolis, it doesn't give you anything. Path tracing would give you better results because it can dish out more samples per pixel, because it's dumb and it parallelizes even better. And only the number of samples matter in this case. And there may be algorithms that take this into consideration. So what if we had an algorithm that could determine if we have an easy scene or a difficult scene? And it would use for easy scenes, easy naive path tracing, bidirectional path tracing, or if there is a difficult scene, then it would Use Metropolis Light Transport. Now, this would need an algorithm that can somehow determine whether the scene is easy or hard. And that's not trivial at all to do. But behind this link there is a work that deals with it. And I would also like to note that Metropolis Light Transport is unbiased, but it starts out biased. So what it means is that I'm running a Markov chain that will give me optimal importance sampling. But this Markov chain also evolves in time. So I have to wait and wait and wait and it will get better and better estimations on where the bright paths are and where the dark paths are. And this takes time. This effect is what we call startup bias. Now what do we get for it? We'll see plenty of examples. So for instance, on caustics, it's even better than bidirectional path tracing. For caustics, you will get almost immediate cost convergence. Now what about this scene? This scene was rendered with lux render. Here you have not glass spheres, but some kind of prism material spheres because you can see a pronounced effect of dispersion and you can see volumetric caustics. So there is a participating media that we are in and these caustics are going to be reflected more multiple times and refracted multiple times. Let's say that this is a disgustingly difficult scene. The only light source there is is actually this laser that comes in from the upper left. Let's try to render such a scene with the different algorithms that we have learned about. Now, if I start a path tracer, this is what I will get after 10 minutes. So the high scoring light paths, the bright light paths, are not the greatest probability light paths and therefore most of the connections will be also obstructed towards the light source. So it is very difficult to sample with path tracing. Bidirectional path tracing it's better. But I mean, if I get this after 10 minutes, I don't know how long it would take to render the actual scene. And if we run Metropolis, it will find the light paths that matter and find the ones that are actually needed to be sampled. And this is already the simplified version, pssmlt and the number next to it is just a ratio of these small perturbations to large perturbations. Sorry, the opposite. So a large number means that most of my light paths are going to be random. So most of with a 75% probability, I'm going to do bidirectional path tracing, 25% Metropolis. And if I pull down this probability 0.25, then most of the time I'm going to do Metropolis sampling. I'm going to explore nearby. And you can see that this renders the scene much, much faster. So this is definitely a very useful technique to have. Now I've done this animation just for fun. This is a primary sample space Metropolis light transport algorithm only with small mutations. So just very small adjustments to the light paths. And this is how an image would converge with these small steps. And. And you can see that the caustics converge ridiculously quickly. Let's take a look at one more example. Take a look at this. Most of the scene is still noisy, but the caustics are completely converged as we start out. Why? Because it is really bright. And this is exactly what the Metropolis is going to focus on. So. So it is even better on caustics. Something that takes a brutal amount of samples with a normal path tracer is going to be immediately converged with the Metropolis. So this is the first, I think 10, perhaps 10 minutes of rendering with the Metropolis on a not so powerful machine. So it seems that we have solved everything. We're looking good, we got this. But I will show you a failure case that we actually still have problems that we couldn't solve. This is a sophisticated scene that is for some reason even harder in some sense than the previous scenes. And it just doesn't want to converge with the primary sample space Metropolis. I'm just rendering and rendering and still fireflies. If I have really large, really bright noisy spots, then this means that I have light paths that have a ridiculously large low probability to be visited. And that means that my sampling strategies are not smart enough. And this is a classical long standing problem in global illumination. Metropolis is not a solution for this. It is still not good enough. But there are techniques that can give you a really smooth results on ridiculously difficult scenes. Scenes like this. And I will also explain you during the next lecture. Why is this essentially difficult? Because doesn't seem too intuitive, does it? But I will explain to you during the next lecture. Thank you very much.