###### Variance Minimization Light Probe Sampling
SIGGRAPH 2009 Poster
##### Kuntee Viriyothai    Paul Debevec
USC Institute for Creative Technologies Figure 1: The Grace Cathedral light probe divided into 4, 16, 64, 256 regions using variance minimization light probe sampling algorithm.
Introduction

We present a technique for sampling light probe images using variance minimization. The technique modifies the median cut algorithm for light probe sampling [Debevec 2005] so that the variance within each region is minimized. Figure 1 shows 4, 16, 64 and 256 lights sampled from the Grace Cathedral lighting environment using the proposed variance minimization algorithm. The median cut algorithm tends to compute partitions which cut right through the brightest light sources, so these sampled lights are not placed in the optimal positions. Figure 2 shows a simple case highlighting how the variance minimization technique improves on the median cut approach. Figure 2: (a) and example region containing two light sources of different intensities. (b) Median Cut splits across the brighter light source, making final light placement (circular dots) suboptimal. (c) Variance Minimization places each light source into its own region, placing lights closer to original sources.
Algorithm

The algorithm recursively divides the entire light probe image into 2^n regions as follows:

• Add the entire light probe image to the region list as a single region.
• For each region in the list, subdivide such that the maximum of the two sub-regions' variances is minimized.
• If the number of iterations is less than n, return to step 2.
• Place a light source at the centroid of each region, and set the light source color to the sum of the pixel values within the region.

The variance of each region r can be calculated from the following equation: Where Lp is the light energy weighting factor of p, and dp is the distance from p to the centroid of r. The calculation of the variance of each region is accelerated using summed area tables.

Results

Figure 3 illustrates the differences in sample placement between the Median Cut algorithm and the proposed Variance Minimization algorithm. Figure 4 shows a scene rendered with 64 sampled lights from the Grace Cathedral light probe which is a close match to the ground truth Monte-Carlo solution. Figure 4: Rendering with Variance Minimization is a closer match to the Monte Carlo solution than the Median Cut result. Figure 3: Sample placement comparison of Median Cut versus Variance Minimization for 64 samples