[Soc-2018-dev] Weekly Report #08 - Many Light Sampling

[Brecht Van Lommel]

Sure, it's fine to continue based on this paper.

On Mon, Jul 9, 2018 at 8:45 AM Erik Englesson <erikenglesson at gmail.com>
wrote:

> Hi,
>
> Thanks for finding the paper! This is great news! Having looked through it
> quickly, it looks like they have a completely different splitting heuristic
> now:
> "The decision to split traversal into both branches is based on the
> estimated variance of the lighting within it. We consider two sources of
> variance: the energy differences between the emitters in the tree and the
> geometric term 1/d^2"
>
> They also explain some other things that were unclear before, e.g. how
> they aggregate bounding cones, their regularization factor that penalizes
> thin bounding boxes in the tree construction, how they traverse the tree
> "bottom-up" for a specific light when MIS is used, etc. This is great! I am
> really happy about this.
>
> Is it OK if I continue my work based on this paper instead of the
> abstract/slides from 2017?
>
> Thanks,
> Erik
>
> On 8 July 2018 at 23:31, Brecht Van Lommel <brechtvanlommel at gmail.com>
> wrote:
>
>> Hi,
>>
>> Thanks for the detailed analysis! I didn't have time yet to think though
>> it all yet.
>>
>> The HPG paper appears to be here, hopefully it has some answers:
>> http://www.aconty.com/pdf/many-lights-hpg2018.pdf
>>
>> Regards,
>> Brecht.
>>
>>
>>
>>
>> On Sat, Jul 7, 2018 at 8:25 AM Erik Englesson <erikenglesson at gmail.com>
>> wrote:
>>
>>> Hi all,
>>>
>>> (Reposting this with a link to the figure instead.)
>>>
>>> Here is my weekly report:
>>>
>>> *This week* I have started the implementation of the split traversal
>>> method. When traversing the tree, instead of always choosing between going
>>> down the left or the right child, it is now also possible to go down both.
>>> If a certain split heuristic is smaller than a user parameter then the
>>> traversal goes down both children otherwise it chooses one of them. This
>>> results in several lights being sampled at the same time instead of one.
>>>
>>> Here is a summary of what I have done:
>>> * Added a GUI for setting the splitting threshold
>>> * Recursive split traversal
>>>       - A split heuristic based on the solid angle and the BSDF peak
>>>       - At leaves, the path radiance is accumulated
>>>       - Have created a simplified GGX evaluation that is not
>>>         currently being used.
>>> * Refactored common code
>>>
>>> This work can be found in this commit
>>> <https://developer.blender.org/rB36cfc9e9fdc1>.
>>>
>>> *Next week* I plan to continue working on the split traversal. There
>>> are still a lot of things that are unclear to me in the split heuristic. A
>>> more detailed description of the split heuristic, what I have done and what
>>> I find unclear can be found at the end of this email.
>>>
>>> Have a great weekend!
>>>
>>> Thanks,
>>> Erik
>>>
>>>
>>> ------------------------------------------------------------------------------------------------------------------------
>>>
>>>
>>> *Split Heuristic*
>>>
>>> This is how the authors describe the split heuristic on slide 20
>>> <https://docs.google.com/viewer?a=v&pid=sites&srcid=ZGVmYXVsdGRvbWFpbnxja3VsbGF8Z3g6NWM0NmU2YWVlNjE3ODk1Yw>
>>> :
>>>
>>> "To make the split decision on a cluster we take into account its subtended
>>> solid angle from the shading point. Also the BSDF peak in case it is highly
>>> specular pointing to the cluster. All together it gives us a number, easy
>>> to normalize from zero to one."
>>>
>>> where they describe the BSDF peak as:
>>>
>>> "• BSDF peak is computed as follows:
>>> 1. Sample a random direction from the BSDF
>>> 2. Compute a conservative maximum cosine with the vector to the
>>> cluster’s center
>>> 3. Evaluate a simple GGX model with the BSDF roughness"
>>>
>>> My interpretation of the above, in pseudocode, looks like this:
>>>
>>> *bool split()*
>>>
>>> *{*
>>>
>>> *   Compute solid angle*
>>>
>>>
>>> *   If BSDF is highly specular*
>>> *      Sample BSDF to get the direction of the BSDF peak*
>>> *      if BSDF peak points towards the cluster*
>>>
>>> *         Compute conservative cosine*
>>>
>>> *         Evaluate simplified GGX*
>>> *         Calculate the BSDF peak by combining the GGX evaluation and
>>> the conservative cosine*
>>> *         Calculate the split heuristic by combining the BSDF peak and
>>> solid angle*
>>> *         Normalize the split heuristic*
>>> *         Return true if the normalized split heuristic is less than
>>> split threshold else false*
>>>
>>>
>>> *    // No contribution from BSDF*
>>> *   Normalize the solid angle*
>>>
>>> *   Return true if the normalized solid angle is less than split
>>> threshold*
>>> *}*
>>>
>>> This could be way off and if you think it should be some other way then
>>> please let me know. This applies to anything written below too. Assuming my
>>> interpretation is correct, there are still a lot of things that are
>>> unclear. Let us go over what I have done this week and be more precise
>>> about what I find unclear.
>>>
>>> *Solid Angle*
>>> The solid angle is probably the least unclear part. The notation in the
>>> figure below will be used in the rest of the email.
>>>
>>> https://wiki.blender.org/w/images/2/24/Splitting.png
>>>
>>> C is the center of the cluster, P is the shading point, N is the normal
>>> at the shading point, d is the distance between C and P, r is the radius of
>>> the bounding sphere, θmax is the maximum angle from the vector C-P that is
>>> still inside the bounding sphere, and "BSDF direction" is the importance
>>> sampled BSDF direction.
>>>
>>> I currently approximate the solid angle of the bounding box of the
>>> cluster/node by the bounding sphere of the cluster/node:
>>>
>>> cos(θmax) = sqrt( 1 - sin^2(θmax) ) // sin^2 + cos^2 = 1
>>> solid_angle = 2π(1 - cos(θmax))
>>>
>>> I might look into doing a more accurate solid angle calculation in a
>>> later iteration.
>>>
>>> *BSDF Peak*
>>> *If BSDF is highly specular*:
>>> This is a bit simplified. What if the shading point has several BSDFs?
>>> Maybe the best thing to do would be to loop over them and see if any of
>>> them are highly specular. If so, choose one of these. How do you know if a
>>> shader is highly specular?
>>>
>>> Currently, I use shader_bsdf_pick() to just randomly choose one of the
>>> BSDFs. However, I think it could pick a diffuse BSDF even if there are
>>> highly specular ones. Once a BSDF has been picked, I decide if it is highly
>>> specular or not by looking at its roughness using
>>> bsdf_get_roughness_squared().
>>>
>>> *if BSDF peak points towards the cluster*:
>>> I sample a random direction from the BSDF with bsdf_sample() and
>>> calculate θ and check if it is smaller or equal to θmax. See the figure
>>> above. I might look into doing a more accurate intersection test in a later
>>> iteration.
>>>
>>> *Compute conservative cosine*:
>>> The conservative cosine is described like this:
>>> "Compute a conservative maximum cosine with the vector to the cluster’s
>>> center"
>>>
>>> Option 1
>>> My current best guess is that they refer to a conservative cosine for
>>> the angle between the cluster's center and the normal N. Something like
>>> this:
>>>
>>> NI = arccos( dot( normalize( C-P), N) )
>>> conservative_cosNI = cos( clamp( NI - θmax, 0.0, π/2 - θmax) )
>>>
>>> See the figure above for what C, P, N, and θmax are referring to. This
>>> is similar to what they did for the "conservative cosine factor to the
>>> orientation bounds". The conservative angle essentially becomes the
>>> smallest possible angle between any light in the node and the normal.
>>>
>>> Sidenote: A small issue with this is that the conservative angle will be
>>> between 0 and π/2 - θmax, which means the conservative cosine will never be
>>> less than cos(π/2 - θmax). This is something I will look at in the next
>>> iteration. It would be nicer to have the conservative cosine be 1 for all
>>> angles less than θmax and a cosine falloff from 1 to 0 between θmax and π/2
>>> and 0 otherwise. Maybe something like this:
>>>
>>> if(NI < θmax)
>>>   NI = 0
>>> else if(θ > π/2)
>>>   NI = π/2
>>> else // NI ∈ [ θmax, π/2 ]
>>>   NI = π/2  *  (NI - θmax) / (π/2 - θmax) // have to be careful if
>>> θmax=π/2
>>>
>>> The else case essentially scales [ θmax, π/2 ] to [ 0, π/2 ].
>>>
>>> Option 2
>>> Another interpretation of the "Also the BSDF peak in case it is highly
>>> specular pointing to the cluster." could be that it is up to the
>>> conservative cosine to scale directions not pointing to the cluster. That
>>> is, to not do the if-check described in "if BSDF peak points towards the
>>> cluster" and instead have the conservative cosine be for the angle between
>>> the cluster's center and the sampled direction. Multiplication with the
>>> conservative cosine then acts like a more forgiving if-check. Something
>>> like this:
>>>
>>> conservative_cos = cos( clamp(θ - θmax, 0.0, π/2 - θmax) )
>>> (see the figure)
>>> If the BSDF direction is inside the bounding sphere then the cosine term
>>> will be 1 otherwise there will be a cosine falloff with the same issue as
>>> mentioned in the sidenote above. It is a bit strange for a highly specular
>>> BSDF to have a non-zero contribution for all directions, or even for all
>>> directions in the hemisphere if something like the sidenote is done. This
>>> makes me think this option is less likely, but I am not sure.
>>>
>>>
>>> *Evaluate simplified GGX: *
>>> Which direction should be used as the light direction in the GGX
>>> evaluation?
>>>
>>> Option 1: Direction to the center of the cluster
>>> The BSDF is highly specular so there is a high risk of this direction to
>>> evaluate to zero? Even if there are other directions within the cluster
>>> that are non-zero. Makes me think this option is unlikely.
>>>
>>> Option 2: Direction from importance sampling of BSDF
>>> We know this direction is pointing towards the cluster, so it is not
>>> unreasonable to me to consider it as a light direction. This is the
>>> direction I currently use. However, since I use bsdf_sample() to get the
>>> direction I get the evaluation of it at the same time. This means that I do
>>> not do any GGX evaluations currently. However, I think it is more efficient
>>> to only sample a random direction without evaluation first and only if this
>>> direction points towards the cluster then a simplified GGX is evaluated.
>>>
>>> *Calculate the BSDF peak by combining the GGX evaluation and the
>>> conservative cosine:*
>>> The computation of the BSDF peak was described as three different steps,
>>> but it is unclear to me how these should be combined. Currently, I just
>>> multiply the conservative cosine with the BSDF evaluation.
>>>
>>>
>>> *Solid Angle "times" BSDF Peak*
>>> On slide 20 again the authors write that the split heuristic should(?):
>>> "Approximate solid angle times BSDF peak"
>>>
>>> *Calculate the split heuristic by combining the BSDF peak and solid
>>> angle*
>>> The BSDF peak is a float3 with the current way of generating it(BSDF
>>> evaluation returns a float3) and the solid angle is just a float value,
>>> while the split heuristic is supposed to be a number. We need some way of
>>> combining the BSDF peak and the solid angle into a number.
>>>
>>> I do not know how to do this and the way I do it now is just by
>>> multiplying the BSDF peak and the solid angle and take the maximum
>>> component. Is there a standard way of doing this?
>>>
>>> *Normalize the split heuristic:*
>>> The splitting heuristic should be normalized between zero and one. To be
>>> able to do this, we need to know the bounds of the BSDF, the conservative
>>> cosine, and the solid angle.
>>>
>>> The bounds of a general BSDF does not necessarily have to be within
>>> [0,1]^3, right? It is probably hard to have an upper bound for a general
>>> BSDF, but maybe that is one of the reasons they evaluate a simplified GGX
>>> which they know how to bound?
>>>
>>> I think the range of the conservative cosine is [cos(π/2 - θmax), 1]
>>> with the current implementation.
>>>
>>> The absolute maximum for the solid angle is 4π (area of the entire unit
>>> sphere). However, since P cannot be inside the bounding box(then always
>>> split) I think the upper bound for the solid angle actually is 2π, i.e.
>>> entire hemisphere?
>>>
>>> In the abstract/paper the authors write:
>>> "We drive this scoring process by both the bounding box of the cluster
>>> (clusters that contain the shading point are always split) but also by an
>>> approximation of the BRDF’s cone of influence to *give higher weight*
>>> to distant clusters that are likely to fall within the specular highlight."
>>>
>>> So, the combination of the BSDF peak and the solid angle should make it
>>> more likely for it to split than if it is only based on the solid angle.
>>>
>>> The first thing I thought of was to normalize the solid angle and the
>>> BSDF peak separately and then combine them by multiplying them. However, if
>>> both these are numbers between zero and one then their combination will be
>>> smaller or equal to the normalized solid angle. This is not what we want,
>>> but it is what I currently do.
>>>
>>>
>>> ------------------------------------------------------------------------------------------------------------------------
>>>
>>> As we have seen above. There are a lot of things that need to be
>>> clarified and fixed next week. Please let me know if there is anything that
>>> you think is strange/unclear/wrong above, then it most probably is.
>>>
>>> Fun fact: I saw that the same authors will have a presentation
>>> <http://www.highperformancegraphics.org/2018/program/> with the same
>>> name(Importance Sampling of Many Lights With Adaptive Tree Splitting) at
>>> the High-Performance Graphics conference on August 10th. Maybe they plan to
>>> clarify their method or have improved it or both?
>>>
>>> Random idea: Would it make sense to have the throughput of the path
>>> affect the splitting heuristic too? Say times BSDF peak.
>>>
>>> Thanks for your time.
>>>
>>> --
>>> Soc-2018-dev mailing list
>>> Soc-2018-dev at blender.org
>>> https://lists.blender.org/mailman/listinfo/soc-2018-dev
>>>
>>
>> --
>> Soc-2018-dev mailing list
>> Soc-2018-dev at blender.org
>> https://lists.blender.org/mailman/listinfo/soc-2018-dev
>>
>>
> --
> Soc-2018-dev mailing list
> Soc-2018-dev at blender.org
> https://lists.blender.org/mailman/listinfo/soc-2018-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.blender.org/pipermail/soc-2018-dev/attachments/20180709/c9ea38a7/attachment-0001.html>