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

[Erik Englesson]

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.blender.org/pipermail/soc-2018-dev/attachments/20180707/8355aa3a/attachment-0001.html>