Efficient sampling of many lights

(L) [2014/03/20] [tby cessen] [Efficient sampling of many lights] Wayback!

I've come up with a method for efficiently sampling large numbers of lights in an unbiased way.  I don't know if it's actually original or not (a quick perusal of google didn't turn anything up), but in case it is I thought I'd present it briefly here so that other smarter people can sink their teeth into it.  If it’s not original, then no worries.  Just reinventing the wheel. [SMILEY :-)]
The basic problem is how to choose a light to sample in a scene that has many light sources (e.g. thousands or millions).  Typical methods I’m familiar with include just randomly picking one, and weighted-randomly picking one based on emitted energy.  Neither of these methods work well, however, in cases such as a city-scape with many many small lights that mostly only contribute to their local area.
As a test case, I have created such a scene.  It’s composed of fairly simple geometry and over 8000 light sources.  This is what it looks like when rendered by just randomly picking a single light to sample (at 16spp):
[IMG #1 Image]
And this is what it looks like at the same sampling rate with the method I’m presenting:
[IMG #2 Image]
The basic idea is to organize the lights into a tree, quite similar to how lightcuts does.  But instead of using that tree to approximate lighting, you use it to do a kind of importance sampling.  In my implementation, I record the spatial bounds and total energy of the lights under each node of the tree.
When you need to choose a light to sample, you then walk the tree choosing which branch to take based on the approximate contribution of the node to the point being lit.  While traversing down the tree you also keep track of the total probability of taking that path.  When you finally reach a leaf node, you then have a light to sample and the chances of that light having been selected.  Pseudo-code for such a choice function might look like this:
Code: [LINK # Select all]func choose_light(n):
choice_probability = 1.0
node = root
loop:
if node is leaf:
return (get_light(node), choice_probability)
p1 = weight(child1)
p2 = weight(child2)
p1 /= p1 + p2
p2 /= p1 + p2
if n < p1:
node = child1
choice_probability *= p1
n /= p1
else:
node = child2
choice_probability *= p2
n = (n - p1) / p2
The function takes a single parameter for choosing amongst all the lights in the scene (it can be random, or QMC, or whatever), and uses an arbitrary “weight” function to determine the importance of a node to the point being lit.
In my implementation, that weight function uses the position and surface normal of the point being lit, and then approximates the node as a sphere light source with the combined energy of all of its children.  There are some subtle details to get right, but it’s not terribly difficult.
And the result is what you see above.
Essentially, this allows you to do a kind of importance sampling across all the light sources of the scene in O(log(N)) time, where N is the number of lights.  And it allows you to take into account any factors that can be conservatively approximated in a hierarchical way.  I’ve chosen distance and angle from surface normal, but any arbitrary criteria could be used for weighting, so there’s a lot of room for playing with different schemes and improving things even further.

[IMG #1]:

[IMG #2]:

(L) [2014/03/20] [tby cessen] [Efficient sampling of many lights] Wayback!

>> Aw man, I had the same idea.
Yeah, can't say that I'm surprised.  Honestly, I was surprised when I searched around the internet and couldn't seem to find it already floating around out there.  It seems like a pretty straight-forward combination of various techniques already out there.  I guess this is just one of those low-hanging fruit that no one has picked yet. [SMILEY :-)]
>> Would be great for a small paper.
Yeah, I've been thinking about writing a paper about it, and maybe submitting it to [LINK http://jcgt.org/ jcgt].  The last time I wrote anything resembling an academic paper was back in college, though, so I'm a bit rusty.  I'd also like to investigate the technique more, and have more solid test-cases and benchmarks if I'm going to publish.  Which means, for one thing, that I'll need to add a shading system to Psychopath so I can test and improve it in more complex shading environments than just grey lambert surfaces.
>> When you traverse the acc struc for the lights, you can do a bit better than just choosing weight based on surface normal and position
I should have been more specific.  When I said "position" I meant position of the point being lit, relative to the light source.  In other words, I did indeed mean taking into account light falloff.  Specifically, I'm calculating the projected solid angle of the sphere onto the point being lit, which is the correct way to calculate light attenuation from a spherical light source.  And the total energy emitted from the sphere is the sum of the energy emitted by the lights under it, so it is taking into account light power.
When taking into account the surface normal, I'm doing a hand-wavy conservative lambert-esk falloff, so kind-of-sort-of taking into account the BSDF given that the entire scene is lambert.
I'm definitely curious how the weighting functions can be improved further.  I'm also curious to see how the tree and internal node representation can be improved/generalized.  For example, it would be interesting to include spot lights, distant lights, world background, etc., taking into account things like the direction of the light.  As you say, spatial extent doesn't have to be the only criteria for building the tree. [SMILEY :-)]

(L) [2014/03/20] [tby cessen] [Efficient sampling of many lights] Wayback!

Here's another before/after, from earlier in the development process:
[LINK http://perm.cessen.com/2014/psychopath/renders/many_lights_16spp_before.png]
[LINK http://perm.cessen.com/2014/psychopath/renders/many_lights_16spp_after.png]
The implementation was more primitive when I rendered this (used point lights for node approximation, didn't account for surface normal, etc). It performs even better now. But it shows that even in relatively simple scenes (in this case, only 16 light sources) there can be a big improvement. Render times for both images were pretty much identical (I don't recall off the top of my head what they were). I'll see if I can get some more up-to-date images soon.
If anyone is curious, the relevant code is here:
[LINK https://github.com/cessen/psychopath/blob/54334c7e6d5a7bfc12db26d08a239e5c82a88926/accel/light_tree.hpp light_tree.hpp]

(L) [2014/03/21] [tby ingenious] [Efficient sampling of many lights] Wayback!

Nice improvement indeed! It is almost a must to have some sort of adaptive clustering/sampling to handle thousands of lights.
But, believe it or not, this is quite similar to what lightcuts does, which is also unbiased! Lightcuts is an adaptive stratified sampling method: for each shading point it partitions the (point-sampled) light sources into a number of strata and then selects a random light inside each stratum with probability proportional to its energy. One interesting property of the stratification is that whichever light you choose from each stratum, the total error in the estimate will be below a perceivable threshold. Strictly speaking, the statement in the previous sentence is not 100% correct; there are some assumptions involved, as a strict guarantee for the error would be too conservative (details in the paper). But the important thing is that lightcuts is unbiased, which is something that seems to elude many people. The random choice of a representative light for each cluster is shared for all pixels, so the variance does not manifest itself as high frequency noise but as structures noise (like in traditional instant radiosity).

(L) [2014/03/21] [tby bachi] [Efficient sampling of many lights] Wayback!

Just to add one thing to ingenious' comment: the correlated error in lightcuts can be reduced by using multiple representatives. See, for example, multi-dimensional lightcuts.
I think essentially most many-lights clustering algorithms(e.g. matrix row-colum sampling, lightslice) can be viewed as a stratified or importance sampling scheme. What is confusing is that many of them share the sampling choice across pixels and can introduce correlated/structured noise, but it does not necessarily mean that they are biased, as what is said in ingenious' post.
Here are a few related papers on many lights importance sampling in case you are interested:
- Wang et al., Bidirectional Importance Sampling for Unstructured Direct Illumination
[LINK http://onlinelibrary.wiley.com/doi/10.1111/j.1467-8659.2009.01366.x/abstract]
- Georgiev et al., Importance Caching for Complex Illumination (ingenious' paper : p)
[LINK https://graphics.cg.uni-saarland.de/2012/importance-caching-for-complex-illumination/]
- Wu and Chuang, VisibilityCluster: Average Directional Visibility for Many-Light Rendering
[LINK http://www.cmlab.csie.ntu.edu.tw/~kevincosner/publications/2013/tvcg_vc/]

(L) [2014/03/21] [tby cessen] [Efficient sampling of many lights] Wayback!

>> But the important thing is that lightcuts is unbiased, which is something that seems to elude many people. The random choice of a representative light for each cluster is shared for all pixels, so the variance does not manifest itself as high frequency noise but as structures noise (like in traditional instant radiosity).
From my own reading of the paper, the choice of representative light, while random, is fixed during the tree construction stage.  So while repeated renderings, with different fixed trees, may eventually average to the correct solution, the technique will never converge to the correct solution within a single rendering.  Perhaps my understanding of the term "unbiased" is not entirely correct, but for practical purposes I don't think lightcuts has the properties I would want from a sampling algorithm (i.e. it can eventually converge to the correct solution within a single rendering session).
It's also worth noting that lightcuts, as originally presented, approximates light sources with many point lights before proceeding to rendering.  So e.g. area lights are clearly not sampled in an unbiased way due to that pre-processing.
>> Here are a few related papers on many lights importance sampling in case you are interested:
Awesome!  Thanks for the links.  I'll take a look when I get a chance.  This is exactly the kind of feedback I was hoping for when I posted this. [SMILEY :-)]

(L) [2014/03/21] [tby friedlinguini] [Efficient sampling of many lights] Wayback!

>> cessen wrote:From my own reading of the paper, the choice of representative light, while random, is fixed during the tree construction stage. So while repeated renderings, with different fixed trees, may eventually average to the correct solution, the technique will never converge to the correct solution within a single rendering. Perhaps my understanding of the term "unbiased" is not entirely correct, but for practical purposes I don't think lightcuts has the properties I would want from a sampling algorithm (i.e. it can eventually converge to the correct solution within a single rendering session).
The fact that you don't like it doesn't make it biased. [SMILEY :-)]
If you define a "rendering session" such that you put VPL generation and eye path processing inside a loop, then you will get convergence (modulo caustics from perfect reflectors/refractors, which lightcuts doesn't support).
>> It's also worth noting that lightcuts, as originally presented, approximates light sources with many point lights before proceeding to rendering. So e.g. area lights are clearly not sampled in an unbiased way due to that pre-processing.
The point lights can be sampled from the area lights in an unbiased way, just like they are for bidirectional path tracing.

Efficient sampling of many lights back

Board: Home Board index Raytracing General Development