Monte Carlo Integration: Correctness, Convergence, and Application in Rendering Equation

Correctness of Monte Carlo Integration

Given a probability density function $p(x)$ over the interval $[a, b]$, we sample a dataset $\{X_1, X_2, \dots, X_N\}$.

Define $F_N$:

$$F_N = \frac{1}{N} \sum_{i=1}^N \frac{f(X_i)}{p(X_i)}$$

Expected value of $F_N$:

$$\begin{aligned} E[F_N] &= E\left[\frac{1}{N} \sum_{i=1}^N \frac{f(X_i)}{p(X_i)}\right] \\ &= \frac{1}{N} \sum_{i=1}^N E\left[\frac{f(X_i)}{p(X_i)}\right] \\ &= \frac{1}{N} \sum_{i=1}^N \int_a^b \frac{f(x)}{p(x)} p(x) dx \\ &= \int_a^b f(x) dx. \end{aligned}$$

Thus, Monte Carlo integration converges to the true integral as $N \to \infty$:

$$\int_D f(x) dx = \lim_{N \to \infty} \frac{1}{N} \sum_{i=1}^N \frac{f(X_i)}{p(X_i)}.$$

Convergence and Variance Analysis

Let $Y = \frac{f(X)}{p(X)}$. The variance of $F_N$ is derived as:

$$\begin{aligned} \sigma^2(F_N) &= \sigma^2\left[\frac{1}{N} \sum_{i=1}^N Y_i\right] \\ &= \frac{1}{N^2} \sum_{i=1}^N \sigma^2[Y_i] \\ &= \frac{1}{N^2}(N \cdot \sigma^2[Y]) \\ &= \frac{1}{N} \sigma^2[Y]. \end{aligned}$$

Hence, the standard deviation:

$$\sigma(F_N) = \frac{\sigma[Y]}{\sqrt{N}}.$$

As $N \to \infty$, $\sigma(F_N) \to 0$, proving convergence.

Impact of variance ($\sigma^2[Y]$):

Smoothness of $Y$: If $Y$ has large variations, $\sigma^2[Y]$ increases, slowing convergence.
Choice of $p(x)$: If $p(x) \propto f(x)$, $\sigma^2[Y] \to 0$, and convergence is optimal.

Monte Carlo Integration for the Rendering Equation

Rendering equation:

$$L_o(x, \omega_o) = L_e(x, \omega_o) + \int_{\Omega} L_i(x, \omega_i) f(x, \omega_i, \omega_o) \cos \theta_i \, \mathrm{d}\omega_i$$

Monte Carlo approximation:

$$L_o(x, \omega_o) = L_e(x, \omega_o) + \frac{1}{N} \sum_{j=1}^N \frac{L_i(x, \omega_i) f(x, \omega_i, \omega_o) \cos \theta_i}{\text{pdf}(\omega_i)}$$

Key Insights

Variance reduction:
- If $\text{pdf}(\omega_i)$ is chosen to closely match the product $L_i(x, \omega_i) f(x, \omega_i, \omega_o) \cos \theta_i$, variance is minimized.
Importance sampling:
- Select $\text{pdf}(\omega_i) \propto L_i(x, \omega_i) f(x, \omega_i, \omega_o) \cos \theta_i$ for optimal convergence and stability.

Importance Sampling

Principle:
Importance sampling selects a probability density function $p(x)$ that closely resembles or is proportional to the integrand $f(x)$. This reduces variance and improves convergence speed.
Monte Carlo Approximation with Importance Sampling:
$$I = \int f(x) \, dx \approx \frac{1}{N} \sum_{i=1}^{N} \frac{f(x_i)}{p(x_i)} \quad \text{where } x_i \sim p(x)$$
- A good choice of $p(x)$ minimizes variance.
- Optimal case: $p(x) \propto f(x)$, which results in zero variance.

Multiple Importance Sampling Estimator

The estimator is defined as:

$$ \text{estimator} = \sum_{i=1}^{n} \left[ \frac{1}{\text{num\_samples\_strategy}_i} \sum_{j=1}^{\text{num\_samples\_strategy}_i} \left( \frac{\text{weight\_function}(i, X_{i,j}) \cdot \text{target\_function}(X_{i,j})}{\text{probability\_density}(i, X_{i,j})} \right) \right] $$

Where:

$ n $: Total number of sampling strategies
$ \text{num\_samples\_strategy}_i $: Number of samples taken using strategy $ i $
$ X_{i,j} $: The $ j $-th sample generated by strategy $ i $
$ \text{weight\_function}(i, X_{i,j}) $: Weight function for strategy $ i $ and sample $ X_{i,j} $
$ \text{target\_function}(X_{i,j}) $: The target function we aim to estimate
$ \text{probability\_density}(i, X_{i,j}) $: Probability density function of strategy $ i $ at $ X_{i,j} $

Conditions for Unbiasedness

To ensure that the estimator is unbiased, the following two conditions must be satisfied:

Condition 1

$$ \sum_{i=1}^{n} \text{weight\_function}(i, x) = 1 \quad \text{for all} \, \text{target\_function}(x) \neq 0 $$

Condition 2

$$ \text{weight\_function}(i, x) = 0 \quad \text{if and only if} \, \text{probability\_density}(i, x) = 0 $$

Common Choices for the Weight Function

Uniform Weights

$$ \text{weight\_function}(i, x) = \frac{1}{n} $$

Binary Weights

$$ \text{weight\_function}(i, x) = \begin{cases} 1 & \text{if certain condition is met} \\ 0 & \text{otherwise} \end{cases} $$

Balance Heuristic

$$ \text{weight\_function}(i, x) = \frac{\text{probability\_density}(i, x)}{\sum_{k=1}^{n} \text{probability\_density}(k, x)} $$

Power Heuristic

$$ \text{weight\_function}(i, x) = \frac{\text{probability\_density}(i, x)^\beta}{\sum_{k=1}^{n} \text{probability\_density}(k, x)^\beta} $$

Balance Heuristic Explained

The balance heuristic ensures the weights are normalized based on the relative importance of each sampling strategy. The formula is:

$$ \text{weight\_function}(i, x) = \frac{\text{probability\_density}(i, x)}{\sum_{k=1}^{n} \text{probability\_density}(k, x)} $$

Where:

$ \text{probability\_density}(i, x) $: Probability density of strategy $ i $ at sample $ x $.
$ \sum_{k=1}^{n} \text{probability\_density}(k, x) $: Sum of all strategies’ probability densities at $ x $.

Explanation:

Numerator: The contribution of strategy $ i $ to the sample $ x $, based on its probability density.
Denominator: The total contribution of all strategies at $ x $, ensuring the weights are normalized across all strategies.

This approach balances the influence of each strategy on the final estimate, depending on the relative density contributions.

Sampling Strategy Coverage and Unbiasedness

Condition: $\text{weight\_function}(i, x) = 0 \iff \text{probability\_density}(i, x) = 0$
- This condition states that:
  - If a particular sampling strategy $i$ cannot generate a sample point $x$ (i.e., $\text{probability\_density}(i, x) = 0$),
  - Then the weight assigned to $x$ by that strategy must also be zero (i.e., $\text{weight\_function}(i, x) = 0$).
- In simpler terms: Only strategies capable of generating a sample point $x$ contribute to its weight.
Do All Paths Need to Be Covered by All Strategies?
- The idea that all possible paths (samples) must be covered by every sampling strategy to ensure unbiasedness seems overly strict.
- In reality:
  - Unbiasedness only requires that every path $x$ can be generated by at least one sampling strategy, not necessarily by all strategies.
Using Partially Covering Strategies
- “Can we use sampling strategies that do not cover all possible paths?”
  - The answer is yes, as long as the following condition for unbiasedness is satisfied:
    - Every path $x$ must be generable by at least one sampling strategy.
    - For strategies unable to generate certain paths, their probability density and corresponding weights must be zero.

Next Event Estimation (NEE)

The Fundamental Problem

Light source sampling works well for direct lighting.
However, path tracing primarily deals with indirect lighting.
Indirect lighting means every surface could act as an indirect light source.
This makes it challenging to apply light source sampling directly, as there are infinitely many potential light sources.

NEE’s Solution

At each shading point, use two strategies together:
1. BRDF Sampling: To find directions for indirect lighting.
2. Light Source Sampling: To directly sample known light sources at each hit point.
The essence is to separate direct lighting and indirect lighting.
Key insight: Indirect lighting is essentially future direct lighting from other bounces.

Workflow Example (Single Area Light Scene)

After a view ray hits a point P:

Compute Direct Lighting:
- Directly sample the light source.
- Calculate the contribution from the light source to point P.
Compute Indirect Lighting:
- Use BRDF sampling to select a new direction.
- Repeat the NEE process (recursively) at the new hit point.
Final Result:
- Direct lighting contribution + Indirect lighting contribution.

Optimization of Hemisphere Sampling

Light source sampling handles the part of the hemisphere corresponding to the light source projection.
BRDF sampling handles other directions that may contribute to indirect lighting.
This division makes sampling more efficient.

Implementation Highlights

Recursively apply NEE in path tracing.
Perform light source sampling at each hit point.
Add the results of light source sampling and recursive hemisphere sampling.
Use BRDF importance sampling to select directions for indirect lighting.

Advantages

This method effectively combines the strengths of BRDF sampling and light source sampling, enhancing rendering efficiency and accuracy.

Efficient Path Tracing (NEE) with the Balance Heuristic

Core Idea

Consider both light sampling methods in every bounce.
Weight on first intersection must still be 1 for BRDF sampling.
Compute probabilities for selected sample with both techniques, use the balance heuristic to compute adequate MIS weights.

The Role of the Balance Heuristic

Compute probabilities for samples chosen by both techniques.
Use the balance heuristic to assign proper multiple importance sampling (MIS) weights to each contribution.
Ensures a fair balance between the contributions of light source sampling and BRDF sampling.

Challenges and Solutions

Different sampling methods are evaluated at different times.
- BRDF sample contributions are calculated when hitting an emitting surface.
- Light source sampling contributions are computed one bounce earlier.