LightSlice: matrix slice sampling for the many-lights problem

Recent work has shown that complex lighting effects can be well approximated by gathering the contribution of hundreds of thousands of virtual point lights (VPLs). This final gathering step is known as the many-lights problem. Due to the large number of VPLs, computing all the VPLs' contribution is not feasible. This paper presents LightSlice, an algorithm that efficiently solves the many-lights problem for large environments with complex lighting. As in prior work, we derive our algorithm from a matrix formulation of the many-lights problem, where the contribution of each VPL corresponds to a column, and computing the final image amounts to computing the sum of all matrix columns. We make the observation that if we cluster similar surface samples together, the slice of the matrix corresponding to these surface samples has significantly lower rank than the original matrix. We exploit this observation by deriving a two-step algorithm where we first globally cluster all lights, to capture the global structure of the matrix, and then locally refine these clusters to determine the most important lights for each slice. We then reconstruct a final image from only these locally-important lights. Compared to prior work, our algorithm has the advantage of discovering and exploiting the global as well as local matrix structure, giving us a speedup of between three and six times compared to state-of-the-art algorithms.