<div dir="ltr"><div>Hi,</div><div><br></div><div>Thanks for the detailed analysis! I didn't have time yet to think though it all yet.</div><div><br></div><div>The HPG paper appears to be here, hopefully it has some answers:</div><a href="http://www.aconty.com/pdf/many-lights-hpg2018.pdf">http://www.aconty.com/pdf/many-lights-hpg2018.pdf</a><div><br></div><div>Regards,</div><div>Brecht.</div><div><br><div><br></div><div><br></div></div></div><br><div class="gmail_quote"><div dir="ltr">On Sat, Jul 7, 2018 at 8:25 AM Erik Englesson <<a href="mailto:erikenglesson@gmail.com">erikenglesson@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div>Hi all,</div><div><br></div><div>(Reposting this with a link to the figure instead.)</div><div><br></div><div>Here is my weekly report:</div><div><br></div><div><b>This week</b> 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.<br></div><div><br></div><div>Here is a summary of what I have done:<br>* Added a GUI for setting the splitting threshold<br>* Recursive split traversal<br> - A split heuristic based on the solid angle and the BSDF peak<br> - At leaves, the path radiance is accumulated<br> - Have created a simplified GGX evaluation that is not<br> currently being used.<br>* Refactored common code<br></div><div><br></div><div>This work can be found in this <a href="https://developer.blender.org/rB36cfc9e9fdc1" target="_blank">commit</a>.</div><div><br></div><div><b>Next week</b> 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.<br></div><div><br></div><div>Have a great weekend!<br></div><div><br></div><div>Thanks,</div><div>Erik<br></div><div><br></div><div><div><div>------------------------------------------------------------------------------------------------------------------------</div></div></div><div><br></div><div style="text-align:center"><b><font size="4"><u>Split Heuristic</u></font><br></b></div><div><br></div><div>This is how the authors describe the split heuristic on <a href="https://docs.google.com/viewer?a=v&pid=sites&srcid=ZGVmYXVsdGRvbWFpbnxja3VsbGF8Z3g6NWM0NmU2YWVlNjE3ODk1Yw" target="_blank">slide 20</a>:</div><div><div><br></div><div>"To make the split decision on a cluster we take into account its<b> </b>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."</div><div><br></div><div>where they describe the BSDF peak as:</div><div><br></div><div>"• BSDF peak is computed as follows:<br><div>1. Sample a random direction from the BSDF<br>2. Compute a conservative maximum cosine with the vector to the<br>cluster’s center<br>3. Evaluate a simple GGX model with the BSDF roughness"</div><div><br></div></div><div>My interpretation of the above, in pseudocode, looks like this:</div><div><i><br></i></div><div><i>bool split()</i></div><div><i>{<br></i></div><div><div><i> Compute solid angle<br></i></div><div><i><br></i></div><div><i> If BSDF is highly specular<br></i></div><div><i> Sample BSDF to get the direction of the BSDF peak</i></div><div><i> if BSDF peak points towards the cluster</i></div><div><i> Compute conservative cosine<br></i></div><div><i> Evaluate simplified GGX<br></i></div><div><i> Calculate the BSDF peak by combining the GGX evaluation and the conservative cosine</i></div><div><i> Calculate the split heuristic by combining the BSDF peak and solid angle</i></div><div><i> Normalize the split heuristic</i></div><div><i> Return true if the normalized split heuristic is less than split threshold else false</i></div><div><i><br></i></div><div><i> // No contribution from BSDF<br></i></div><div><i> Normalize the solid angle</i></div><div><i> Return true if the normalized solid angle is less than split threshold<br></i></div></div><div><i>}</i><br></div><div><br></div><div>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.<br><u><b><br></b></u></div><div><u><b>Solid Angle</b></u></div></div></div><div><div>The solid angle is probably the least unclear part. The notation in the figure below will be used in the rest of the email. <br></div><div><br></div></div><div><div><a href="https://wiki.blender.org/w/images/2/24/Splitting.png" target="_blank">https://wiki.blender.org/w/images/2/24/Splitting.png</a><br></div><br></div><div>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.<br></div><div><br></div><div>I currently approximate the solid angle of the bounding box of the cluster/node by the bounding sphere of the cluster/node:<br></div><div><br></div><div>cos(θmax) = sqrt( 1 - sin^2(θmax) ) // sin^2 + cos^2 = 1<br></div><div>solid_angle = 2π(1 - cos(θmax))<br></div><div><br></div><div>I might look into doing a more accurate solid angle calculation in a later iteration.</div><div><br></div><div><div><div><div><u><b>BSDF Peak</b></u><br></div><div><u><i>If BSDF is highly specular</i></u>: <br></div><div>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?<br></div><div><br></div><div>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().<br></div><div> </div><div><br></div><div><u><i>if BSDF peak points towards the cluster</i></u>: <br></div><div>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.</div><div><br></div><div><u><i>Compute conservative cosine</i></u>: <br></div><div><div><div>The conservative cosine is described like this:</div><div>"Compute a conservative maximum cosine with the vector to the cluster’s center"<br></div></div><div><br></div><div>Option 1<br></div><div>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:</div><div><br></div><div>NI = <span class="m_2936208689142307105m_4251927274730092731gmail-m_6400229614276737560m_905324366984257160gmail-gr_ m_2936208689142307105m_4251927274730092731gmail-m_6400229614276737560m_905324366984257160gmail-gr_1835 m_2936208689142307105m_4251927274730092731gmail-m_6400229614276737560m_905324366984257160gmail-gr-alert m_2936208689142307105m_4251927274730092731gmail-m_6400229614276737560m_905324366984257160gmail-gr_spell m_2936208689142307105m_4251927274730092731gmail-m_6400229614276737560m_905324366984257160gmail-gr_inline_cards m_2936208689142307105m_4251927274730092731gmail-m_6400229614276737560m_905324366984257160gmail-gr_disable_anim_appear m_2936208689142307105m_4251927274730092731gmail-m_6400229614276737560m_905324366984257160gmail-ContextualSpelling m_2936208689142307105m_4251927274730092731gmail-m_6400229614276737560m_905324366984257160gmail-ins-del m_2936208689142307105m_4251927274730092731gmail-m_6400229614276737560m_905324366984257160gmail-multiReplace" id="m_2936208689142307105m_4251927274730092731gmail-m_6400229614276737560m_905324366984257160gmail-1835">arccos</span>( dot( normalize( C-P), N) )<br></div><div>conservative_cosNI = cos( clamp( NI - θmax, 0.0, π/2 - θmax) )<br></div><div><br></div><div>See the figure above for what C<span class="m_2936208689142307105m_4251927274730092731gmail-m_6400229614276737560m_905324366984257160gmail-gr_ m_2936208689142307105m_4251927274730092731gmail-m_6400229614276737560m_905324366984257160gmail-gr_6390 m_2936208689142307105m_4251927274730092731gmail-m_6400229614276737560m_905324366984257160gmail-gr-alert m_2936208689142307105m_4251927274730092731gmail-m_6400229614276737560m_905324366984257160gmail-gr_gramm m_2936208689142307105m_4251927274730092731gmail-m_6400229614276737560m_905324366984257160gmail-gr_inline_cards m_2936208689142307105m_4251927274730092731gmail-m_6400229614276737560m_905324366984257160gmail-gr_run_anim m_2936208689142307105m_4251927274730092731gmail-m_6400229614276737560m_905324366984257160gmail-Style m_2936208689142307105m_4251927274730092731gmail-m_6400229614276737560m_905324366984257160gmail-replaceWithoutSep" id="m_2936208689142307105m_4251927274730092731gmail-m_6400229614276737560m_905324366984257160gmail-6390">, P</span>, N, <span class="m_2936208689142307105m_4251927274730092731gmail-m_6400229614276737560m_905324366984257160gmail-gr_ m_2936208689142307105m_4251927274730092731gmail-m_6400229614276737560m_905324366984257160gmail-gr_6405 m_2936208689142307105m_4251927274730092731gmail-m_6400229614276737560m_905324366984257160gmail-gr-alert m_2936208689142307105m_4251927274730092731gmail-m_6400229614276737560m_905324366984257160gmail-gr_gramm m_2936208689142307105m_4251927274730092731gmail-m_6400229614276737560m_905324366984257160gmail-gr_inline_cards m_2936208689142307105m_4251927274730092731gmail-m_6400229614276737560m_905324366984257160gmail-gr_run_anim m_2936208689142307105m_4251927274730092731gmail-m_6400229614276737560m_905324366984257160gmail-Punctuation m_2936208689142307105m_4251927274730092731gmail-m_6400229614276737560m_905324366984257160gmail-only-ins m_2936208689142307105m_4251927274730092731gmail-m_6400229614276737560m_905324366984257160gmail-replaceWithoutSep" id="m_2936208689142307105m_4251927274730092731gmail-m_6400229614276737560m_905324366984257160gmail-6405">and</span> θ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. <br></div><div><br></div><div>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:</div><div><br><div><div><div>if(NI < θmax)</div><div> NI = 0</div><div>else if(θ > π/2)</div><div> NI = π/2</div><div>else // NI ∈ [ θmax, π/2 ]<br></div><div> NI = π/2 * (NI - θmax) / (π/2 - θmax) // have to be careful if θmax=π/2</div></div></div><div><br></div><div>The else case essentially scales [ θmax, π/2 ] to [ 0, π/2 ].</div><div><br></div><div>Option 2</div><div>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:</div><div><br></div><div><div>conservative_cos = cos( clamp(θ - θmax, 0.0, π/2 - θmax) )</div>(see the figure)<br></div><div>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.</div><div><br></div></div></div><div><i><u>Evaluate simplified GGX</u>: <br></i></div><div>Which direction should be used as the light direction in the GGX evaluation?</div><div><br></div><div><div>Option 1: Direction to the center of the cluster</div><div>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.</div></div><div><br></div><div>Option 2: Direction from importance sampling of BSDF</div><div>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.<br></div><div><i><br></i></div><div><i><div><i><u>Calculate the BSDF peak by combining the GGX evaluation and the conservative cosine</u>:</i></div></i></div><div>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.<br></div><div><br></div></div></div></div><div><div><b><u>Solid Angle "times" BSDF Peak<br></u></b></div><div>On slide 20 again the authors write that the split heuristic should(?):</div><div>"Approximate solid angle times BSDF peak"</div><div><br></div><div><div><u><i>Calculate the split heuristic by combining the BSDF peak and solid angle</i></u></div></div><div></div><div>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. <br></div><div><br></div><div>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?<br></div></div><div><br></div><div><u><i>Normalize the split heuristic</i>:</u><br></div><div>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. <br></div><div><br></div><div>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?<br></div><div><br></div><div>I think the range of the conservative cosine is [cos(π/2 - θmax), 1] with the current implementation.<br></div><div><br></div><div>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?<br></div><div><br><div><div><div>In the abstract/paper the authors write:</div><div>"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 <b>give higher weight</b> to distant clusters that are likely to fall within the specular highlight."</div><div><br></div><div>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. <br></div><div><br></div><div>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.</div><div><br></div></div></div><div><div>------------------------------------------------------------------------------------------------------------------------</div></div><div><br></div><div>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.</div><div><br></div><div>Fun fact: I saw that the same authors will have a <a href="http://www.highperformancegraphics.org/2018/program/" target="_blank">presentation</a> 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?<br></div><div><br></div><div>Random idea: Would it make sense to have the throughput of the path affect the splitting heuristic too? Say times BSDF peak.</div><div><br></div><div>Thanks for your time.</div></div><br></div>
-- <br>
Soc-2018-dev mailing list<br>
<a href="mailto:Soc-2018-dev@blender.org" target="_blank">Soc-2018-dev@blender.org</a><br>
<a href="https://lists.blender.org/mailman/listinfo/soc-2018-dev" rel="noreferrer" target="_blank">https://lists.blender.org/mailman/listinfo/soc-2018-dev</a><br>
</blockquote></div>