Ratio tracking, intuitively


Recently, I've been toying around with volumetric path tracing, and along the way I had to learn some new math, which was actually pretty exciting. Today, I want to tell you about some of this math, in a way that feels like we've derived it ourselves from scratch.

Contents

Monte Carlo recap

First, let's recap the usual Monte Carlo method. Say, we want to compute the integral of some function

\[ I = \int\limits_0^L f(x)dx \]

We do this by generating \(N\) samples \(X_i\) according to some probability distribution \(p(x)\) that satisfies \(f(x) \neq 0 \Rightarrow p(x) > 0\), compute the single-sample estimators \(\frac{f(X_i)}{p(X_i)}\), and average them out, producing our final estimate

\[ \frac{1}{N}\sum\limits_i \frac{f(X_i)}{p(X_i)} \]

The output is random, but on average it equals our desired integral. And, as we get more samples, we get a better estimate – that is, the variance (the noise) of the estimator goes to zero.

Now, this is all good, but what if our task is a bit more complicated than just a single integral? What if we want to compute some function of the integral?

Integral, squared

Consider the simplest possible way we could make our lives harder (which will turn out to be useful later): what if instead of an integral, we need to compute the square of an integral?

\[ I^2 = \left(\int\limits_0^L f(x)dx\right)^2 \]

That sounds silly at first: if you want the integral squared, just compute the integral, then take the square! For example, using the same Monte Carlo method as before:

\[ \left(\frac{1}{N}\sum\limits_i \frac{f(X_i)}{p(X_i)}\right)^2 \]

This certainly works, and in fact if your end goal is to compute this squared integral, this is the way to go.

The problem is when this squared integral is only a part of something bigger. Maybe it is multiplied by some other expression, or maybe it is itself inside another integral? In cases like this, we might want to apply Monte Carlo to the whole expression of which the squared integral might only be a small part.

For this to work with Monte Carlo, we need an estimate of the squared integral, not the integral itself. I.e. we need some random variable \(Y\) such that its expected value \(\mathbb E[Y]\) equals the squared integral. Basic Monte Carlo cannot do that!

You might think that we just need to square the samples we generate, – e.g. instead of returning \(\frac{f(X)}{p(X)}\) we'd return \(\frac{f(X)^2}{p(X)}\), – but that would compute the integral of a square

\[ \int\limits_0^L f(x)^2dx \quad{\color{red}\neq}\quad I^2 \]

and not the squared integral. For all but the simplest choices of \(f(x)\) these are not the same!

We can somewhat solve it by e.g. approximating the integral using other methods, like discretization, but that would introduce aliasing (unless we jitter the samples) and bias (i.e. the result will not be equal the the desired integral on average, it will only approximate it). For real-time applications, this might be fine, but for something like path-tracing aiming at generating the true solution of the light transport equations, this is not acceptable.

So, what do we do? There's a fun trick that relies on the fact that for independent random variables \(Y_1\) and \(Y_2\), the expected value of their product is the product of expected values:

\[ \mathbb E[Y_1Y_2] = \mathbb E[Y_1]\mathbb E[Y_2] \]

(in general, these two differ by their covariance).

So, take both \(Y_1\) and \(Y_2\) to be two independent Monte Carlo estimates of the original integral \(I = \int\limits_0^L f(x)dx\), i.e. generate two independent samples \(X_1\) and \(X_2\), compute \(Y_i = \frac{f(X_i)}{p(X_i)}\), so that \(\mathbb E[Y_i] = I\), and set

\[ Y = Y_1Y_2 = \frac{f(X_1)f(X_2)}{p(X_1)p(X_2)} \]

This \(Y\) will be a Monte Carlo estimate of the squared integral, meaning that its expectation value is equal to the squared integral:

\[ \mathbb E[Y] = \mathbb E[Y_1Y_2] = \mathbb E[Y_1]\mathbb E[Y_2] = I^2 \]

The \(X_i\) don't even have to use the same distribution \(p(x)\), the important thing is that they are independent.

More generally, if we want to compute the \(k\)-th power of the integral,

\[ I^k = \left(\int\limits_0^L f(x)dx\right)^k \]

you simply generate \(k\) independent samples to estimate the integral itself, and take their product – this will be a Monte Carlo sample for the \(I^k\). It does force us to take more samples and compute more evaluations of \(f(x)\), but as a reward we get a true Monte Carlo sample for something that is more complicated than just a single integral.

Volumetric light transport

Unfortunately, in volumetric rendering we need something even more complicated than an integral taken to some power. Ignoring scattering (which complicates things even further), a typical volumetric integral looks like

\[ \int\limits_0^L g(x) \exp\left(-\int\limits_0^x f(t)dt \right)dx \]

Yep, this is an integral of an exponential of an integral.

Wtf man, I just wanted to make videogames.

This apparent monstrosity of a formula is actually surprisingly easy to interpret: \(g(x)\) is how much light is emitted by the 3D medium at the point \(x\) along the camera ray, and we simply add (i.e. integrate) all the emitted light together. However, this light might be scattered away or absorbed along the path towards the camera by the same medium, so we multiply it be the mysterious exponential factor (called transmittance) which tells us how much light actually survives and reaches the camera.

(The reason transmittance takes the form of an exponential of an integral aren't too complicated, but they are irrelevant to this post.)

If we want to use Monte Carlo to compute this formula, we can generate a random sample \(X\in [0, L]\) using some distribution \(p(x)\), but then we need to compute the exponential, which is generally impossible to do precisely. Thankfully, because we're doing Monte Carlo, we can replace the exponential with some random variable \(Y\) that has this exponential as its expectation value, making the final estimator \(\frac{g(X)\cdot Y}{p(X)}\) converge to the desired integral.

All we need to do is find such a random variable \(Y\), and the method to do that is called

Ratio tracking

As you might've guessed by this point, ratio tracking is precisely that: a method of Monte Carlo estimating an exponential of an integral. In other words, it's a method for constructing a random variable with its expectation value equal to an exponential of an integral.

Our target formula will be of the form

\[ T = \exp\left(-\int\limits_0^L f(x)dx\right) = \exp(-I) \]

and we'll construct a random variable \(Y\) such that

\[ \mathbb E[Y] = \exp(-I) = T \]

I want to note that in most applications it happens that \(f(x)\geq 0\), so that the integral is also \(I \geq 0\), the exponentiated expression is \(-I \leq 0\), and thus the exponent itself \(T\) is always in the \([0, 1]\) range. We'll see why this is important in the next section. From now on, we'll assume that \(f(x) \geq 0\).

\(f(x)\) is usually something like the probability of a ray hitting some particle or being absorbed by some particle, thus it is nonnegative. Technically, \(f(x)\) is defined per unit distance in the limit of infinitely small distances.

So, how does this method work? Instead of simply presenting it to you, I'll try to motivate its construction in such a way that it feels like we've derived it ourselves (which we technically will).

Step 1: Infinite series

We don't know how to estimate the exponential directly, but we do know how to turn in into an infinite series of simpler expressions:

\[ T = \exp(-I) = \sum\limits_{k=0}^\infty (-1)^k\frac{I^k}{k!} \]

Now, how do we Monte Carlo a sum of several values? We have essentially two main methods:

  1. Estimate each term of the sum separately \(Y_k\), and return the sum \(Y=\sum Y_k\) as the total estimate, or
  2. Pick a random term \(k\) of the sum with probability \(p_k\), estimate it as \(Y_k\), and return \(Y=\frac{Y_k}{p_k}\) as the total estimate.

The first method generally has lower variance, but it gets less attractive as the number of terms in the sum grows. In our case we have an infinite number of terms, thus this method isn't really applicable at all (you'd need an infinite for loop just to produce a single estimate of the whole sum).

Thus, we have to use the second method. Which is actually really, really bad news. You see, our series is alternating in signs (because of the \((-1)^k\) factor), and in the previous post we've derived that when estimating sign-alternating series like these, we have really big problems with variance (aka noise). Specifically, when computing an infinite sum \(\sum A_k\) using this method, the lowest variance we can get is

\left(\sum |A_k|\right)^2 - \left(\sum A_k\right)^2

Applying this to our series for \(T=\exp(-I)\), we get

\[ \left(\sum \left|(-1)^k\frac{I^k}{k!}\right|\right)^2 - \left(\sum (-1)^k\frac{I^k}{k!}\right)^2 = \exp(2I) - \exp(-2I) \]

(Here, the absolute value killed the \((-1)^k\) factor, and I've moved squaring inside the exponential as a factor of 2.)

Now, if \(I\) is close to zero, this minimal variance is roughly equal to

\[ \exp(2I) - \exp(-2I) \approx (1+2I) - (1-2I) = 4I \]

meaning that the typical error (the standard deviation) would be something like \(2\sqrt I\), which for small \(I\) is much larger than \(I\) itself. For example, we would estimate the value of \(T\) as \(0.01\pm 0.2\), which is borderline useless.

Now, for large \(I\), things are even worse. In this case the \(\exp(-2I)\) term is negligible, and the variance is approximately \(\exp(2I)\), thus the standard deviation is about \(\exp(I)\), which is equal to \(\frac{1}{T}\). This time, we would estimate \(T\) as \(0.01\pm 100\), which is far beyond being staggeringly useless.

So, we either have to give up entirely, or proceed to

Step 2: Control variates, aka the majorant

The main problem is that we're exponentiating something negative. There's a stupidly simple way of turning this into a problem of exponentiating something positive! Find any value \(A\) which is guaranteed to be not less than \(I\), then \(A-I\geq 0\), and \(\exp(A-I)\) is an exponent of something nonnegative! Wait, but this isn't what we were trying to compute...

The fix is using the properties of exponentials:

\[ \exp(-I) = \exp(-A)\exp(A-I) \]

Now, this only works if \(\exp(-A)\) itself is easier to compute that \(\exp(-I)\), otherwise we've just made a circle. One particularly easy way is find some upper bound \(M\) for our function \(f(x)\), meaning that \(\forall x\in [0, L] \quad f(x)\leq M\). (In practice, the values of f(x) might come from a 3D texture or some noise, and the upper bound can be easily estimated or precomputed.) Then

\[ I = \int\limits_0^L f(x)dx \leq \int\limits_0^L Mdx = M\cdot L \]

Thus, we can rewrite \(\exp(-I)\) as

\[ \exp(-I) = \exp(-ML)\exp(ML-I) \]

Here, \(\exp(-ML)\) is just some constant, and the \(\exp(ML-I)\) is the exponent of something nonnegative! That's a win.

We can now express it via an infinite sum again:

\[ \exp(-I) = \exp(-ML)\sum\limits_{k=0}^\infty \frac{(ML-I)^k}{k!} \]

And we just need to sample random terms from this sum, using

Step 3: Poisson distribution

We know that for a good sampling strategy, the probability of picking the \(k\)-th term of the sum must be proportional to the value of this term. Unfortunately, we don't know the values of the terms (otherwise there wouldn't be anything left to compute), but we can try to bound them somehow.

Look at the \(k\)-th term of the sum again:

\[ \frac{(ML-I)^k}{k!} = \frac{(ML)^k}{k!}\left(1-\frac{I}{ML}\right)^k \]

I've rewritten it a bit to separate the constants \(ML\) and the term number \(k\) from the unknown integral value \(I\). The \(\left(1-\frac{I}{ML}\right)\) term is a bit scary, but notice that \(I\leq ML\), thus this term is always somewhere in the \([0, 1]\) range (at it remains there when we take the \(k\)-th power).

The remaining factors look pretty okay, so let's find a probability distribution which is proportional to their value

\[ p_k \sim \frac{(ML)^k}{k!} \]

We just need to compute the proportionality constant. To do this, sum all these terms:

\[ C = \sum\limits_{k=0}^\infty \frac{(ML)^k}{k!} = \exp(ML) \]

So, to turn this into a probability distribution, we need to divide \(\frac{(ML)^k}{k!}\) by \(\exp(ML)\), which is the same as multiply by a factor of \(\exp(-ML)\). The final probabilities now look like

\[ p_k = \exp(-ML) \frac{(ML)^k}{k!} \]

This is a well-known distribution called the Poisson distribution, and is one of the most important probability distributions across all math. The fact that it appeared out of nowewhere isn't a coincidence, although it does look somewhat fishy.

But wait, \(\exp(-ML)\) is exactly the factor we already had in front of our infinite sum! Recall:

\[ \exp(-I) = \exp(-ML)\sum\limits_{k=0}^\infty \frac{(ML-I)^k}{k!} \]

We can now rewrite it as

\[ \exp(-I) = \sum\limits_{k=0}^\infty p_k \left(1-\frac{I}{ML}\right)^k \]

Which literally has the form of an expectation value! How very convenient. So, here's our new algorithm:

  1. Select a random \(k\) with probability distribution \(p_k\),
  2. Return a random estimate of \(\left(1-\frac{I}{ML}\right)^k\) as the answer.

On average, this will converge to \(T=\exp(-I)\). The only thing that remains is

Step 4: Sampling the k-th power

How on Earth do we Monte Carlo estimate \(\left(1-\frac{I}{ML}\right)^k\)? We've already talked about it in the beginning of the post: take \(k\) independent estimates of \(\left(1-\frac{I}{ML}\right)\) and multiply them all!

Okay, how do I Monte Carlo estimate \(\left(1-\frac{I}{ML}\right)\) itself? Rewrite it:

\[ 1-\frac{I}{ML} = \frac{1}{ML}(ML-I) = \frac{1}{ML}\int\limits_0^L (M - f(x))dx = \] \[ = \int\limits_0^L \frac{1}{L} \left(1-\frac{f(x)}{M}\right)dx \]

This looks suspiciosly familiar: \(\frac{1}{L}\) is just the probability of selecting a point \(X\in[0,L]\) uniformly, and the expression as a whole is just the expected value of the resulting random variable \(1-\frac{f(X)}{M}\)!

So, here's the recipe for estimating \(\left(1-\frac{I}{ML}\right)^k\):

  1. Generate \(k\) independent points \(X_i\in[0,L]\) using uniform distribution
  2. Compute the product \(\prod\limits_{i=1}^k \left(1-\frac{f(X_i)}{M}\right)\) – this is the desired estimate

Notice that we don't divide by the probabilities of \(X_i\) (which are all equal to \(\frac{1}{L}\)) – it is already included in our formula, and it relies on the \(X_i\) being uniformly distributed.

We could stop here, – after all, we have all the algorithm pieces worked out, – but that's not how ratio tracking is usually presented. There are many reasons for that, one being that sampling \(k\) using the probabilities \(p_k\) we've derived earlier isn't actually that straightforward.

Instead, it uses something called

Step 5: Poisson process

Poisson process is something very closely related to the Poisson distribution. It is often described as the bus arrival distribution. The idea is that, in theory, buses should arrive at regular time intervals, but because of random traffic delays, varying bus speeds, and the drivers' aim of sticking to the timetable at least somewhat, the time intervals are stable only on average.

The Poisson process describes exactly what happens in this case: if we only know that certain events happen once every \(T\) seconds on average, what can we say about the exact distribution? How many events will happen during some time period, how long will we have to wait for the next event, for the second-to-next event, and so on.

The Poisson process with parameter \(\lambda\) defines an increasing sequence of random positive numbers (or points, or events) \(X_i\), and the difference between any two neighbouring points follows the exponential distribution \(\lambda \exp(-\lambda x)\). By the way, it is convenient to define \(X_{0}=0\) without considering \(X_{0}\) to be part of the sequence.

The connection between Poisson processes and volumetric rendering is extremely deep, and it's something that I'm still learning about, and something I'll hopefully share in a later post. For now, all we need can be boiled down to the following 3 standard facts about Poisson processes:

  1. For a Poisson process with parameter \(\lambda=M\), the number of events \(k\) in the interval \([0,L]\) follows the probability distribution \(p_k = \exp(-ML)\frac{(ML)^k}{k!}\).
  2. If the number of events \(k\) is fixed, the events themselves \(X_i\) turn out to be uniformly distributed.
  3. There is an easy algorithm for sampling the Poisson process.

So, the idea is that we use the Poisson process to generate a sequence of points \(X_i\). We're only interested in points in the interval \([0, L]\), so we can simply stop when a new sample is outside that range (\(X_i>L\)). Then we simply compute \(\prod\limits_{i=1}^k\left(1-\frac{f(X_i)}{M}\right)\) as our estimate of \(T=\exp(-I)\).

A lot of things work out automatically here:

What's left is actually sampling the Poisson process, which is done using

Step 6: CDF inversion

Recall that the Poisson process is defined like that:

  1. Start with \(X_{0}=0\), which isn't part of the sequence.
  2. For each \(i\in\{1,2,\dots\}\), generate \(X_i\) as \(X_{i-1}\) plus an exponentially-distributed step size.

So it boils down to generating exponentially-distributed values. This is where CDF inversion enters the stage. Recall that the probability distribution for the step size is \(p(x) = \lambda\exp(-\lambda x)\). Integrating, we get the CDF equal to \(F(x) = 1-\exp(-\lambda x)\).

Now apply CDF inversion: to generate samples according to \(p(x)\), generate a sample \(u\) uniformly distributed on \([0, 1]\), and compute \(F^{-1}(u)\) – it will have the desired distribution.

In our case, \(F^{-1}\) is easy to find:

\[ u = F(x) = 1 - \exp(-\lambda x) \] \[ \exp(-\lambda x) = 1 - u \] \[ -\lambda x = \log(1 - u) \] \[ x = F^{-1}(u) = -\frac{\log(1 - u)}{\lambda} \]

Recall that in the case of ratio tracking, we set \(\lambda=M\), where \(M\) is the upper bound for our function \(f(x)\).

So, we generate uniform values \(u_i \in [0,1]\), generate \(X_i\) sequentually using steps of \(-\frac{\log(1 - u)}{M}\), compute the product of \(\left(1-\frac{f(X_i)}{M}\right)\) terms, and stop when \(X_i > L\). This is ratio tracking!

The complete algorithm

It is very easy to get lost in all the formulas and terminology above, so let me once again describe the algorithm from start to end.

What we want to do is find a random variable \(Y\) which will be a Monte Carlo estimate of an exponential of minus the integral of a nonnegative function \(f(x)\):

\[ T = \exp\left(-\int\limits_0^L f(x)dx\right) = \exp(-I) \]

That is, we want the expectation value of \(Y\) to be equal to this exponential:

\[ \mathbb E[Y] = \exp(-I) = T \]

We do this by finding an upper bound \(M\) for our integrated function \(f(x)\), meaning that \(f(x) \leq M\) always holds.

Then, we generate a sequence of numbers \(X_i\), and compute the running product of \(\left(1-\frac{f(X_i)}{M}\right)\). Note that we don't need to store all the numbers, just the last one (in order to generate the next one).

And the numbers themselves are generated as incremental steps following the exponential distribution, starting with \(X_0=0\) (which is just the starting value, and not part of the sequence).

I'm sure that, for a lot of my audience, code is easier to read than literally everything I've said above, so here's the code:

// f(x) is the function under the integral
// L is the length of the interval
// M is the upper bound for f(x)

float x = 0;
float result = 1;
while (true) {
    float u = rand01();
    float step = - log(1 - u) / M;
    x += step;
    if (x >= L) break;
    result *= 1 - f(x) / M;
}

// result holds the desired random estimate of the exponential

Ta-daaaaa! Less than 10 lines, this one. So much for all the yapping.