Hi! In this video I am going to present our work on
efficiency-aware multiple importance sampling for bidirectional rendering algorithms.
When you're rendering an image of a virtual scene, one question you have to answer is:
"Which algorithm should you use?"
For example, vast exteriors are best handled by unidirectional path tracing
But interior scenes with caustics benefit from bidirectional methods like the VCM algorithm.
A more annoying decision you have to make is how to allocate your sample budget.
You could trace no bidirectional samples at all, so unidirectionally
you could trace a small number of light paths, a large number of light paths
You could trace a small number of shadow rays, or a large number of shadow rays.
You could enable photon mapping, or disable photon mapping.
And finding the right combination of all of these decisions can be very, very challenging
and also very frustrating, if you have to do it manually.
This is where our method comes in, because we propose a way to automatically optimize these sample parameters
for the scene that we are currently rendering. But first, we need to recap some background.
Our goal is to estimate some integral F of a function f(x)
We do that via Monte Carlo integration, which means we take n random samples x, with some PDF p(x)
And then we simply average the sample weights of those samples.
And if the pdf p(x) - illustrated in red down here - closely matches our integrand f(x) - the black line,
then we achieve a good estimator with low variance that needs only a low number n of samples
But, in practice, it's often very hard to find one such sample density that can achieve this.
That's where multiple importance sampling comes in, because MIS allows us to combine multiple densities,
for example the blue and yellow ones shown down here,
that each resemble the function we want to integrate better in different regions
or for different cases, like different types of illumination in rendering.
And then we simply sum over all those sampling techniques, take some number n_t of samples from them
and again compute our Monte Carlo estimate value, but additionally weighted by an MIS weighting function w.
This basic MIS estimator can be improved further, for example by
finding better PDFs, by finding better weighting functions
or, as we are doing, by finding better sample count allocations across the different techniques.
Previous work has already looked at those sample counts.
For example, the oldest approach proposed to use some domain-specific heuristics,
where, for example, in a direct illumination setting, you can look at the shininess of the surface
to decide if you want to use more BSDF samples or more shadow rays.
These are of course not general, and they are also not optimal. But they are simple and can be very effective.
An alternative is to base the sample counts on the second moments and/or variances of the different techniques.
There are multiple ways to do this. One is to set the sample counts n_t of technique t proportional to the efficiency,
which is the inverse of the product of cost and variance.
These decisions are also not optimal,
but they are still comparatively easy to do, although you now need to estimate second moments and variances.
A way to achieve something that is closer to the actual optimum is to use convex optimization.
If we approximate the variance by the second moment, and if we are using the classic balance heuristic,
then we actually have a convex function in the sample count that we can optimize
with either first order gradient descent, or some second order Newton optimizer.
and that achieves something that is much closer to the optimum. But we are very limited,
because we can't use arbitrary MIS weighting functions,
it's a continuous optimization so binary decisions aren't handled that nicely,
and all of these approaches ignore sample cost.
If we contrast this to the specific challenges of a bidirectional algorithm,
we see that none of the previous approaches will handle this very well.
For example, in a bidirectional algorithm, we have a large number of light paths.
But all of these paths are shared across all the pixels in our image.
So the cost to trace these millions of paths is ammortized over the pixel integrals.
If we ignore that cost, then we will get bad optimization results.
And, additionally, while this number of light paths is a global constant,
we have other sample counts, like the number of shadow rays that we can control, for example, on a pixel level
And we have seen in previous work that the classic balance heuristic
can perform quite poorly in a bidirectional setting, for some corner cases at least.
So we don't want to restrict ourselves to just the classic balance heuristic,
which rules out any convex optimization.
And, finally, we also don't want to have to explicitly work with the full product path PDFs.
Because, in a bidirectional algorithm, a single technique generates a full path from the camera to the light.
And those high-dimensional products of multiple PDFs might not even be representable in floating point.
and they will also definitely cause numerical problems if we, for example, add two PDF values onto each other.
So how do we overcome those challenges?
Our method is very simple. It's a brute-force search,
where we start with a set of fixed candidate sample counts for all the possible techniques.
And then we run a very quick pilot iteration - unidirectional path tracing in our case -
where we efficiently estimate the second moments of all of these candidates,
and then we combine that with a cost heuristic,
that predicts the number of ray-tracing and shading operations to approximate the render time.
And then we simply pick the best one.
This approach is inspired by the simplest, and possibly stupidest, way to achieve this optimization.
For example, if you wanted to find the best number of light paths,
what we could do is we could start with a bunch of sensible options
and then, with every single one of them, render an image
estimate the pixel variance
and measure the render time.
This will give us good estimates of the efficiency and tell us which one of those sample counts is the best.
But it also will require us to render dozens or hundreds of images
with a full-blown bidirectional algorithm.
so that's not at all practical.
But we can make this practical, by rendering only a single image,
with an arbitrary configuration
and, using the samples from that to efficiently estimate the second moments
as an approximation of the variance
of all of the candidates.
And then we can approximate the render time by a cost heuristic
where we have measured the number of ray-tracing and shading operations as a heuristic value,
and achieve a very similar optimization outcome as this simple and very slow approach,
but with just very, very low overhead.
The key to make our method work is to have an efficient estimation scheme for the second moment.
We start by rendering with a pilot strategy m that uses m_t samples from technique t.
The second moment of this pilot is trivial to estimate.
We simply square the sample weights of this pilot iteration.
But, of course, we don't want the pilot's second moment,
we want the second moments of all of our candidates n that use n_t samples from technique t.
We can get this equally easily and efficiently
by taking the squared sample weights of the pilot
and multiplying them by a correction factor.
And this correction factor we have designed in a way to make it both efficient to compute and numerically stable.
The numerical stability is achieved by basing it only on MIS weighting function values,
and never ever considering explicit PDF values.
The efficiency is achieved by introducing this proxy strategy a,
where we use some arbitrary sample count a_t from technique t
which we never actually use for sampling
but just as a mathematical trick to write this correction factor in terms of a single set of MIS weights.
That means that for every sample, we just need to compute
a few additional MIS weight terms
and then we can compute the correction factors
for every single candidate based on those few additional MIS weight terms.
So how does this work if we apply it to the full VCM algorithm?
First, we start rendering with a single sample per pixel with unidirectional path tracing.
We apply our moment estimation scheme to compute the second moments of all our candidate sample counts.
Then we optimize on the image-level the number of light paths n and the number of connections c.
If the outcome tells us that path tracing is the way to go,
we stick to unidirectional rendering forever, and just render until our budget is consumed.
Otherwise, we throw away this image from the unidirectional pilot
because it usually has a high amount of noise if the scene actually requires bidirectional samples.
Then we start over with another single sample per pixel rendering
Using VCM with our optimized number of light paths, number of connections
but also doing photon mapping in every single pixel.
We again estimate the second moments of all of our candidates.
From those, we now first optimize per pixel whether or not photon mapping would be useful in that pixel.
Of course, because we just have a single sample in each pixel,
we need to apply some aggressive filtering to make this work robustly.
And, with this per-pixel decision fixed,
we optimize on the image-level again the number of light paths and the number of shadow rays.
And those are the parameters we then use to render until we are done.
So what good is this if we apply it in practice?
Here you can see the statistics of our speed-up after 30s of equal-time rendering
of our method compared to unidirectional path tracing and standard VCM with fixed parameters.
Compared to unidirectional path tracing, in the worst-case scenario out of all of our 20 test scenes,
we are never slower than 2% less then unidirectional.
This is because of the additional overhead from our optimization.
If we take some more care at optimizing this, this can be reduced even further.
On the other hand, compared to standard VCM, even in the worst-case we are already 12% faster
because the full-blown VCM beast actually wastes a lot of samples
on sampling techniques that, for the one scene we are rendering right now, are not useful at all.
And, of course, in the best-case we are hundreds of times faster than path tracing
and 5 times faster than standard VCM.
So let's check out some results in a specific scene.
Here we see a diffuse - or mostly diffuse - interior scene with lots of indirect illumination
but also some glass bowl here that causes caustics and reflections of those caustics.
Our method reduces the number of light paths
because here most of the light paths actually find the visible region, so we don't need that many.
Instead, it increases the number of shadow rays used for connections
because of all the indirect, diffuse illumination
Also, we limit merging to mostly just the glass bowl
There are of course some regions from the blur and also from noise in the estimates,
where merging is turned on despite the fact that it is not actually beneficial there.
With this optimization, we achieve rendering performance that's
10 times faster than unidirectional path tracing
and almost 3 times faster than a standard VCM.
On the other hand, in this super simple diffuse exterior scene,
we achieve the same performance as a unidirectional path tracer,
because we never trace a single bidirectional sample.
Compared to bidirectional path tracing, which is 40% slower here
Or VCM, which is even 70% slower because all of those bidirectional samples are completely wasted.
Of course, our method is not perfect.
There is the overhead that we can reduce further by
either reducing the number of candidates
or adapting it to the scene
Or maybe applying some binary search instead of the brute-force search approach.
We can also improve our filtering
and, most importantly, what we could also do to improve the results further is to include the covariance.
Because currently we are only optimizing with the second moments
and the impact the covariance has is shown in this example down here.
Here we have rendered this simple diffuse kitchen scene
and we have optimized based on the second moments and full variances
from some very long prepass renderings
and we show the number of light paths, number of connections
the per-pixel merging decisions
and the corresponding speed-ups over unidirectional path tracing.
As we can see, the number of light paths and connections is exactly the same
if we optimize with the variance as if we optimize with the moments.
That's because those techniques do not have a lot of sample correlation.
But photon mapping does.
And that's why our per-pixel merge decision with just the second moments
in this example is severly off. We're doing way too much photon mapping.
And that's because in this scene, we have a lot of correlation
so the second moment severely underestimates the variance in photon mapping
and then our optimizer thinks that photon mapping is much better than it actually is.
If we had a way to efficiently estimate, or at least approximate, this covariance,
we could achieve another 10% increase in performance in this example.
But, in conclusion, the question we wanted to answer is:
"Can we automatically find the best, or at least good, parameters for a bidirectional algorithm?"
And the answer is: "Yes, we can."
With a very simple search-based optimization,
combined with an efficient scheme to estimate the second moments,
we can achieve consistent performance improvements over both, unidirectional path tracing
and a standard VCM approach with fixed parameters.
Our method never traces a single bidirectional sample in cases where bidirectional sampling is not beneficial.
And with that, I conclude my presentation and I thank you all for your attention and I am looking forward to some interesting discussions.