LightSlice: Matrix Slice Sampling for the Many-Lights Problem

晃晃

LightSlice: Matrix Slice Sampling for the Many-Lights Problem

Jiawei Ou Fabio Pellacini

Dartmouth College Dartmouth College







Abstract

Recent work has shown that complex lighting effects can be well

approximated by gathering the contribution of hundreds of thou-

sands 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 light-

ing. 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 ob-

servation 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 algo-

rithm 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.

CR Categories: I.3.7 [Computer Graphics]: Three-Dimensional

Graphics and Realism—Color, shading, shadowing, and texture

Keywords: many light, global illumination, matrix sampling



1 Introduction

Realistic Rendering as Many-Lights. Fast computation of global

illumination in large scenes with a complex lighting configuration

is still a challenging problem in computer graphics. Many methods

have been proposed to compute fast global illumination solutions,

e.g. bidirectional path tracing and photon mapping. (see [Pharr

and Humphreys 2010] for a recent review). In this paper, we focus

on computing images using a variant of instant global illumination

[Keller 1997], where direct and indirect illumination are approxi-

mated by converting the original light sources into a large number

of virtual point lights (VPLs) distributed across the entire scene.

In this model, computing a global illumination solution is equiva-

lent to computing an image lit solely by a large number of point

light sources, i.e. the many-lights problem. Prior work in offline,

high-fidelity rendering [Haˇ san et al. 2007; Walter et al. 2005] has

shown that for scenes with diffuse and low gloss materials, hun-

dreds or thousands of VPLs effectively approximate complex di-

rect and indirect illumination effects, while having the advantage of

treating both equally within the same algorithm framework. VPLs

have also been used in real-time applications, where they handle a

smaller number of lights at the price of the accuracy of approxi-

mation [Ritschel et al. 2009]. VPLs have also found much use in

feature film production [Christensen 2008]. In this paper, we fo-

cus on high-fidelity rendering in complex environments rather than

interactive applications.

Matrix Intepretation of Many-Lights. It is useful to consider an

alternative interpretation of the many-lights problem as a matrix

sampling problem. Let us arrange all pixels of an image as a long

column vector. We can then arrange all columns corresponding to

each VPL as a large unknown matrix. Computing the final image

amounts to computing the sum of each row in the matrix. Figure

1 shows an example of such matrix. While many-lights algorithms

handle all lights equally, it is useful to note that the lights have

two common behaviors. Ignoring shadows, some lights have strong

contributions to all pixels; these VPLs typically correspond to di

rect illumination, e.g., the sun. We term these global lights. When

unshadowed, these appear as bright matrix columns. When shad

owed, these appear as columns with bright and black sections o

an entirely black column. Other lights have more local behavio

affecting only a few pixels; typically, these are VPLs derived by

sampling indirect lighting, and thus have lower intensity and an r

squared falloff. We term these local lights. In the matrix, these

lights appear mostly as black columns with a small, low intensity

section.

For hundreds of thousands of lights, a brute force solution tha

computes all columns of the many-lights problem is prohibitively

expensive. Many methods have been proposed to reduce the com

putation complexity of the many-lights problem to be sublinear in

the number of VPLs. The two main observations that allow this

is that the elements of the matrix have repeating patterns and tha

large areas of low contributions are present (see Fig. 1). All scalable

many-lights algorithms exploit these two observations by clustering

groups of similar VPLs and approximating their contribution using

a single representative. In other words, all these methods subsam

ple the matrix by approximating blocks of similar elements as con

stant values computed from only one element. The size and shape

of these blocks changes for different algorithms. We compare ou

work with two main prior algorithms.



全文请下载附件：

tc

真不错,全存下来了.

C.R.CAN

百度的叫度娘，网易的叫易娘，新浪内部还在为是叫新娘还是浪娘而争论不休！……不管你们是企鹅的额娘，豆瓣的伴娘，还是华为的伪娘，都要记得，淘宝才是你们的亲娘啊！亲！！

tc

我就看看，我不说话

晃晃

读铁系缘分，顶铁系友情

C.R.CAN

不错 非常经典  实用

C.R.CAN

凡系斑竹滴话要听；凡系朋友滴帖要顶

奇

谢谢楼主，真是太实用了