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 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 cle not so clear where you first see the algorithm now mathematical details again will be omitted mostly and 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 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 part 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 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 samples in order to hit these caustics many times in order to clean them up clear them up onwards 1993 bi-directional path racing 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 the 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 you won't continue your light path now you would start a part racer what do you start tracing the race 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 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 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 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 bi-directional path tracing what happens here is that i'm 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 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 bi-directional 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 diffuser 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 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 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 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 part racing 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 veach in his landmark thesis of beautiful works bi-directional path racing 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 that daddy do people actually read this huge tone 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 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 veg pyramid this is created with bi-directional 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 second bounce third image would be the third bounce for bi-directional path tracing you have a pyramid like that because you subdivide them to the first bounds from the eye and the sun 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 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 there and if this is a low probability event then 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 one t equals five you can see that we have caustics in there and the caustics is almost com 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 zero t equals six 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 want to what i would want to do is give a large weight to s equals one t equals five 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 a really good and super simple technique on how to do that and now look closely to the image this is without naive bi-directional path 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 five t equals one it seems to have been even better at sampling caustics because this s equals one t equals five 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 is implemented on shader toy the nice classical v 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 small paint 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 bi-directional path tracing definitely better converge 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 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 racing and even better there is a nice comparison coded 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