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):
And this is what it looks like at the same sampling rate with the method I’m presenting:
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: 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) / p2In 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.
