ReSTIR is built on a bunch of other technologies. Let's discuss them one-by-one.
Rejection Sampling
Rejection sampling isn't actually used in ReSTIR, but it's useful to cover it anyway. It is a technique to convert samples from one PDF (probability density function) to another PDF.
So, you start with the fact that you have 2 PDFs: a source PDF and a destination PDF. The first thing you do is you find a scalar "M" which, when scaling the source PDF, causes the source PDF to be strictly larger than the destination PDF, for all x coordinates. Then, for every sample in the source, accept that sample with a probability equal to destination PDF at the sample / (M * source PDF at the sample). You'll end up with fewer samples than you started with, but that's the price you pay. You can see how the scalar M is necessary to keep the probabilities between 0 and 1.
The larger the distance between the destination PDF and M * the source PDF, the fewer samples will be accepted. So, if you pick M very conservatively, you'll end up with almost no samples accepted. That's a downside to rejection sampling.
On the other hand, if the source PDF and the destination PDF are the same, then M = 1, and all the samples will be accepted. Which is good, because the input samples are exactly what should be produced by the algorithm.
Sequential Importance Resampling
This is another technique used to convert samples from one PDF to another PDF. Compared to rejection sampling, we don't reject samples as we encounter them; instead, we pick ahead of time how many samples we want to accept.
Again, you have a source PDF and a destination PDF. Go through all your samples, and compute a "score" which is the destination PDF at the sample / the source PDF at the sample. Now that you have all your scores, select N samples from them, with probabilities proportional to the scores. You might end up with duplicate samples; that's okay.
Compared to rejection sampling, this approach has a number of benefits. The first is that you don't have to pick that "M" value. The scores are allowed to be any (non-negative) value - not necessarily between 0 and 1. This means you don't have to have any global knowledge about the PDFs involved.
Another benefit is that you know how many samples you're going to get at the end - you can't end up in a situation where you accidentally don't end up with any samples.
The downside to this algorithm is that you have to pick N up front ahead of time. But, usually that's not actually a big deal.
The other really cool thing about SIR is that the source and destination PDFs don't actually have to be normalized. Because the scores can be arbitrary, it's okay if your destination PDF is actually just some arbitrary (non-normalized) function. This is super valuable, as we'll see later.
Monte Carlo Integration
The goal of Monte Carlo integration is to compute an integral of a function. You simply sample it at random locations, and average the results.
This assumes that the pdf you're using to generate random numbers is constant, from 0 - 1.
So, the formula is: 1/N * sum from 1 to N of f(x_i)
Importance Sampling
The idea here is to improve upon basic Monte Carlo integration as described above. Certain samples will contribute to the final result more than others. Instead of sampling from a constant PDF, if you instead sample using a PDF that approximates the function being integrated, you'll more quickly approach the final answer.
Doing so adds another term to the formula. It now is: 1/N * sum from 1 to N of f(x_i) / q(x_i), where q(x) is the PDF used to generate samples.
The best PDF, of course, is proportional the function being sampled - if you pick this, f(x_i) / q(x_i) will be a constant value for all i, which means you only need 1 term to calculate the final perfect answer. However, usually this is impractical - if you knew how to generate samples proportional to the function being integrated, you probably know enough to just integrate the function directly. For direct illumination, you can use things like the BRDF of the material, or the locations where the light sources are. Those will probably match the final answer pretty well.
Multiple Importance Sampling
So now the question becomes how to generate that approximating function. If you look at the above fomula, you'll notice that when f(x) is large, but q(x) is small, that leads to the worst possible situation - you are trying to compute an integral, but you're not generating any samples in an area that large contributes to it.
The other extreme - where f(x) is small but q(x) is big - isn't actually harmful, but it is wasteful. You're generating all these samples that don't actually contribute much to the final answer.
The idea behind MIS is that you can generate q(x) from multiple base formulas. For example, one of the base formulas might be the uniform distribution, and another might be proportional to the BRDF of the material you're shading, and another might be proportional to the direction of where the lights in the scene are. The idea is that, by linearly blending all these formulas, you can generate a better q(x) PDF.
Incorporating the uniform distribution is useful to make sure that q(x) never gets too small anywhere, thereby solving the problem where f(x) is large and q(x) is small.
Resampled Importance Sampling
RIS is what happens when you bring together importance sampling and SIR. You can use SIR to generate samples proportional to your approximating function. You can then use the importance sampling formula to compute the integral.
If, when using SIR, your approximating function isn't normalized, there's another term added into the formula to re-normalize the result, which allows the correct integral to be calculated.
This is really exciting, because it means that we can calculate integrals (like the rendering equation) by sampling in strategic places - and the pdf of those strategic places can be arbitrary (non-normalized) functions.
Reservoir Sampling
Reservoir Sampling is a reformulation of SIR, to make it streamable. Recall that, in SIR, you encounter samples, and each sample produces a weight, and then you select N samples proportional to each sample's weight. Reservoir sampling allows you to select the N samples without knowing the total number of samples there are. The idea is that you keep a "reservoir" of N samples, and each time you encounter a new sample, you update the contents of the reservoir depending on probabilities involved. The invariant is that the contents of the reservoir is proportional to the probabilities of all the samples encountered.
The other cool thing about reservoir sampling is that 2 reservoirs can be joined together into a single reservoir, via only looking at the contents of the reservoirs, without requiring another full pass over all the data.
Conclusion
So far, we've set ourselves up for success. We can calculate integrals, in a streamable way, by "resampling" our samples to approximate the final function being integrated. Being streamable is important, as we need to be able to update our results as we encounter new samples (perhaps across new frames, or across other pixels). The fact that you can merge reservoirs in constant time is super powerful, as it the merged result to behave as if it saw 2*N samples, while only running a constant-time algorithm. This can be done multiple times, thereby allowing for synthesis of an exponential number of samples, but each operation is constant time.
No comments:
Post a Comment