Importance Sampling of Many Lights with Adaptive Tree Splitting

(L) [2018/07/31] [tby cessen] [Importance Sampling of Many Lights with Adaptive Tree Splitting] Wayback!

I've skimmed the paper now, and they definitely have made some great contributions!  This really fleshes out the light tree method.  I'm especially pleased to see that they've accounted for non-omnidirectional lights.
I helped to mentor Petra Gospodnetić (who they also cited) when [LINK https://medium.com/@petragospodneti/gsoc-2017-with-appleseedhq-cc5f33d04170 she implemented light tree sampling in Appleseed] for last year's GSOC, and in the process we figured out a couple of additional things that I didn't see mentioned in this paper (at least in my skimming).
Shading points inside light tree nodes
The first is how to handle importance weighting when shading points fall inside the volume of a light tree node.  In the paper they appear to side-step this with their splitting approach, so that shading points are never inside nodes.  However, you can get significantly improved results in other ways too.
In both Psychopath and Appleseed we use the projected solid angle of the cluster X it's total power to determine the importance of the that node to the given shading point.  However, doing things that way leaves quite a bit of noise for scenes where the scene geometry is significantly intermixed with the lights of the scene.  This is because the nodes higher up in the tree then have spatial extents that encompass the shading points, in which case the importance then simply becomes the node's total power, since the projected solid angle is equal for all points inside it.  Rendering that way looks like this:
[IMG #1 Image]
However, Petra stumbled across something really interesting: if instead of using the (constant) projected solid angle for points inside a node, you transition to an inverse square equation from the node's center, you get this:
[IMG #2 Image]
Significantly reduced noise.  It also introduces some very bright fireflies, but if you clamp the inverse square factor so it doesn't approach infinity, that eliminates the fireflies while largely preserving the reduced noise:
[IMG #3 Image]
Neither of us are entirely sure why this works.  My theory is that it better approximates the fact that the lights under each node are generally more of a cloud than a surface.  I suspect that the clamped inverse square is accidentally approximating a different function that should actually be used.  But I haven't investigated what that function would be.
It's not clear to me how this would be incorporated in combination with how this paper accounts for light direction, but it would be interesting to investigate!
Tree arity
It turns out that tree arity makes a really big difference.  Compare the last image above with this:
[IMG #4 Image]
The only difference between the two images is that the previous one uses a binary tree whereas this image uses an 8-arity tree.  Although the higher arity does have some performance impact (61 vs 66 seconds in this case), the reduced noise due to better sampling more than makes up for it.  Increasing the arity further gives even further noise reduction.
This is also something that is somewhat addressed in the paper via their splitting method.  However, their splitting process actually samples additional lights (as I gathered from skimming, at least).  It would be interesting to explore using their splitting approach not for taking more samples, but instead as a kind of adaptive tree arity selection.  For clusters that are far away, using binary selection is almost certainly fine.  But for nearby clusters, switching to higher arity gives a much better approximation of the lights, and therefore results in better sampling.
I'm guessing (hoping?) that doing this adaptively based on the paper's splitting heuristic could give the benefits of a very high-arity tree with minimal performance impact.
One last note
In the paper, they said about my post (and other citations) "[...]though to our knowledge no publication discusses in detail their approach to tree construction or traversal."  While that is technically true, it feels a little misleading to me because [LINK https://github.com/cessen/psychopath Psychopath is open source and published on github] (and was at the time as well).  Anyone is free to examine the code to see how it works!  Granted, that isn't as convenient as a well-crafted explanation.  But I wasn't hiding any details. [SMILEY :-)]

[IMG #1]:

[IMG #2]:

[IMG #3]:

[IMG #4]:

(L) [2018/07/31] [tby fpsunflower] [Importance Sampling of Many Lights with Adaptive Tree Splitting] Wayback!

We certainly saw your post before getting into this topic (hence the citation [SMILEY :)]). I have to admit we didn't look at your code in detail though (or the appleseed gsoc project, which was started after we had been using ours in production for a while).
My colleague Alex did most of the work on this (he will give the presentation at HPG in a few weeks). He started from that basic idea (like several others have) and then tried to find the best possible way to assign the probabilities, build the tree, etc ... Hopefully the paper adds a few new ideas to the mix that are helpful and gives some kind of basis for comparison for future work. We definitely don't claim to have the found the most optimal formulas yet.
We observed the same effect with respect to tree-arity. Our implementation uses N=4 to fit nicely into SSE (which we allude to in the paper even though we describe most of it with N=2 for simplicity). Which tree-arity wins in practice probably is also related to implementation overheads which can be harder to compare fairly across systems.

(L) [2018/07/31] [tby cessen] [Importance Sampling of Many Lights with Adaptive Tree Splitting] Wayback!

Whoa!  I always forget how many researchers and paper authors frequent this forum.  Thanks for the reply, fpsunflower!
A note about my last note: re-reading it, I realize it may have come off as accusatory, which absolutely wasn't my intention.  I certainly didn't think you guys were intentionally misrepresenting anything.  I just meant it as an informative note for anyone else stumbling over here.
That's really cool that you guys saw my post!  And thanks so much for citing me.  That really means a lot.  Makes me feel like I've made a real contribution to graphics. [SMILEY :-)]
Your paper is really amazing, and does an excellent job laying out not just the basic technique, but also the details of your particular approach.  I really wish more papers were written so well!  I also think your original contributions are really significant, and didn't at all mean to downplay them.  I'm especially excited and impressed by your tree-building approach, taking into account light orientation.  I think that's huge, and is a significant improvement over the much more basic approach I've been using.
I hope my notes above might be useful to you guys as well.  I expect I'll also revisit my own code at some point (though I'm quite busy with other things at the moment), and see if I can get a best-of-both-worlds implementation going.
Regarding arity, I believe arity-4 is just a pure win, even without SIMD.  I wrote a post about tree arity for BVH's used for ray-tracing [LINK http://psychopath.io/bvh4-without-simd/ here], but it was actually originally due to me exploring tree arity for light trees.  The short version: you don't actually visit any more nodes when traversing arity-4 vs arity-2 (which was a weird thing to discover).
Also, here are the files relevant to my light tree implementation, if you guys want to take a look:
[LINK https://github.com/cessen/psychopath/blob/5c20fa3ea41e12fa7614fab26b1c37bf0cc8a3d9/src/accel/light_tree.rs light_tree.rs]
[LINK https://github.com/cessen/psychopath/blob/5c20fa3ea41e12fa7614fab26b1c37bf0cc8a3d9/src/shading/surface_closure.rs surface_closure.rs]
Most interesting to you guys would, I think, be the function used for node importance weighting, which is estimate_eval_over_sphere_light() [LINK https://github.com/cessen/psychopath/blob/5c20fa3ea41e12fa7614fab26b1c37bf0cc8a3d9/src/shading/surface_closure.rs#L299 here].  I actually use an analytic formula for lambert lighting from uniform spherical light sources, and then the hand-wavy inverse square trick noted in the post above if the points are inside the bounding sphere of the node.
I would be really curious if using this for the spatial-extent part of your weighting formula would improve things at all, especially when disabling splitting.

(L) [2018/08/01] [tby cessen] [Importance Sampling of Many Lights with Adaptive Tree Splitting] Wayback!

Couldn't help myself, and I did a quick test comparing the importance estimate currently in Psychopath to the left side of equation 3 in the paper (i.e. omitting the light orientation component):
Analytic Lambert over spherical cap solid angle & clamped inverse square hack (current Psychopath):
[IMG #1 Image]
Minimum incident angle Lambert / inverse square (from the paper):
[IMG #2 Image]
These are both rendered with tree arity = 2, and both rendered in almost the exact same render time. However, increasing tree arity starts to show a small performance difference (at arity = 8, the first is 23.5 seconds, the latter 22.4 seconds).
It's not clear to me that the implementation in the paper would actually benefit from this, as it likely has the most impact in the same cases where the paper's implementation would split. But it would be interesting to test out. [SMILEY :-)]

[IMG #1]:

[IMG #2]:

Importance Sampling of Many Lights with Adaptive Tree Splitting back

Board: Board index Raytracing Links & Papers