Differential for Many Lights Sampling applied on top of rB50df9caef01a
ArchivedPublic
Actions

Authored by Alaska (Alaska) on Sep 25 2022, 11:01 AM.

Tags

None

Subscribers

None

	diff --git a/intern/cycles/blender/addon/presets.py b/intern/cycles/blender/addon/presets.py
	index e1f08c07eaf..a2c43126f15 100644
	--- a/intern/cycles/blender/addon/presets.py
	+++ b/intern/cycles/blender/addon/presets.py
	@@ -49,6 +49,8 @@ class AddPresetSampling(AddPresetBase, Operator):
	"cycles.samples",
	"cycles.adaptive_threshold",
	"cycles.adaptive_min_samples",
	+ "cycles.use_light_tree",
	+ "cycles.splitting_threshold",
	"cycles.time_limit",
	"cycles.use_denoising",
	"cycles.denoiser",
	diff --git a/intern/cycles/blender/addon/properties.py b/intern/cycles/blender/addon/properties.py
	index a9954016829..f42a2de0c9d 100644
	--- a/intern/cycles/blender/addon/properties.py
	+++ b/intern/cycles/blender/addon/properties.py
	@@ -473,6 +473,20 @@ class CyclesRenderSettings(bpy.types.PropertyGroup):
	default='MULTIPLE_IMPORTANCE_SAMPLING',
	)

	+ use_light_tree: BoolProperty(
	+ name="Light Tree",
	+ description="Samples many lights more efficiently",
	+ default=False,
	+ )
	+
	+ splitting_threshold: FloatProperty(
	+ name="Splitting",
	+ description="Amount of light tree emitters to consider at a time, from one light at 0.0, "
	+ "to adaptively more lights as needed, to all branches at 1.0",
	+ min=0.0, max=1.0,
	+ default=0.85,
	+ )
	+
	min_light_bounces: IntProperty(
	name="Min Light Bounces",
	description="Minimum number of light bounces. Setting this higher reduces noise in the first bounces, "
	diff --git a/intern/cycles/blender/addon/ui.py b/intern/cycles/blender/addon/ui.py
	index eb89e76dc75..436597bdcfb 100644
	--- a/intern/cycles/blender/addon/ui.py
	+++ b/intern/cycles/blender/addon/ui.py
	@@ -323,6 +323,34 @@ class CYCLES_RENDER_PT_sampling_advanced(CyclesButtonsPanel, Panel):
	layout.row().prop(cscene, "use_layer_samples")
	break

	+class CYCLES_RENDER_PT_sampling_light_tree(CyclesButtonsPanel, Panel):
	+ bl_label = "Many Lights Sampling"
	+ bl_parent_id = "CYCLES_RENDER_PT_sampling"
	+ bl_options = {'DEFAULT_CLOSED'}
	+
	+ @classmethod
	+ def poll(cls, context):
	+ return (context.scene.cycles.feature_set == 'EXPERIMENTAL')
	+
	+ def draw_header(self, context):
	+ layout = self.layout
	+ scene = context.scene
	+ cscene = scene.cycles
	+
	+ layout.prop(cscene, "use_light_tree", text="")
	+
	+ def draw(self, context):
	+ layout = self.layout
	+ layout.use_property_split = True
	+ layout.use_property_decorate = False
	+
	+ scene = context.scene
	+ cscene = scene.cycles
	+
	+ layout.active = cscene.use_light_tree
	+ col = layout.column(align=True)
	+ col.prop(cscene, "splitting_threshold", text="Split Threshold")
	+

	class CYCLES_RENDER_PT_subdivision(CyclesButtonsPanel, Panel):
	bl_label = "Subdivision"
	@@ -2288,6 +2316,7 @@ classes = (
	CYCLES_RENDER_PT_sampling_render,
	CYCLES_RENDER_PT_sampling_render_denoise,
	CYCLES_RENDER_PT_sampling_advanced,
	+ CYCLES_RENDER_PT_sampling_light_tree,
	CYCLES_RENDER_PT_light_paths,
	CYCLES_RENDER_PT_light_paths_max_bounces,
	CYCLES_RENDER_PT_light_paths_clamping,
	diff --git a/intern/cycles/blender/sync.cpp b/intern/cycles/blender/sync.cpp
	index 3808cbf1459..548617f9284 100644
	--- a/intern/cycles/blender/sync.cpp
	+++ b/intern/cycles/blender/sync.cpp
	@@ -342,6 +342,13 @@ void BlenderSync::sync_integrator(BL::ViewLayer &b_view_layer, bool background)

	integrator->set_light_sampling_threshold(get_float(cscene, "light_sampling_threshold"));

	+ integrator->set_use_light_tree(get_boolean(cscene, "use_light_tree"));
	+ integrator->set_splitting_threshold(get_float(cscene, "splitting_threshold"));
	+
	+ if (integrator->use_light_tree_is_modified()) {
	+ scene->light_manager->tag_update(scene, LightManager::UPDATE_ALL);
	+ }
	+
	SamplingPattern sampling_pattern = (SamplingPattern)get_enum(
	cscene, "sampling_pattern", SAMPLING_NUM_PATTERNS, SAMPLING_PATTERN_SOBOL);
	integrator->set_sampling_pattern(sampling_pattern);
	diff --git a/intern/cycles/kernel/CMakeLists.txt b/intern/cycles/kernel/CMakeLists.txt
	index f32a810786d..10f68559f7f 100644
	--- a/intern/cycles/kernel/CMakeLists.txt
	+++ b/intern/cycles/kernel/CMakeLists.txt
	@@ -263,6 +263,7 @@ set(SRC_KERNEL_INTEGRATOR_HEADERS

	set(SRC_KERNEL_LIGHT_HEADERS
	light/light.h
	+ light/light_tree.h
	light/background.h
	light/common.h
	light/sample.h
	diff --git a/intern/cycles/kernel/data_arrays.h b/intern/cycles/kernel/data_arrays.h
	index 7205f728088..28fcfb4a2cf 100644
	--- a/intern/cycles/kernel/data_arrays.h
	+++ b/intern/cycles/kernel/data_arrays.h
	@@ -60,6 +60,14 @@ KERNEL_DATA_ARRAY(KernelLight, lights)
	KERNEL_DATA_ARRAY(float2, light_background_marginal_cdf)
	KERNEL_DATA_ARRAY(float2, light_background_conditional_cdf)

	+/* light tree */
	+KERNEL_DATA_ARRAY(KernelLightTreeNode, light_tree_nodes)
	+KERNEL_DATA_ARRAY(KernelLightTreeEmitter, light_tree_emitters)
	+KERNEL_DATA_ARRAY(KernelLightTreeDistantEmitter, light_tree_distant_group)
	+KERNEL_DATA_ARRAY(uint, light_to_tree)
	+KERNEL_DATA_ARRAY(uint, object_lookup_offset)
	+KERNEL_DATA_ARRAY(uint, triangle_to_tree)
	+
	/* particles */
	KERNEL_DATA_ARRAY(KernelParticle, particles)

	diff --git a/intern/cycles/kernel/data_template.h b/intern/cycles/kernel/data_template.h
	index 807d0650fc3..8b480db895c 100644
	--- a/intern/cycles/kernel/data_template.h
	+++ b/intern/cycles/kernel/data_template.h
	@@ -37,10 +37,11 @@ KERNEL_STRUCT_MEMBER(background, int, map_res_y)
	KERNEL_STRUCT_MEMBER(background, int, use_mis)
	/* Lightgroup. */
	KERNEL_STRUCT_MEMBER(background, int, lightgroup)
	+/* Light Index. */
	+KERNEL_STRUCT_MEMBER(background, int, light_index)
	/* Padding. */
	KERNEL_STRUCT_MEMBER(background, int, pad1)
	KERNEL_STRUCT_MEMBER(background, int, pad2)
	-KERNEL_STRUCT_MEMBER(background, int, pad3)
	KERNEL_STRUCT_END(KernelBackground)

	/* BVH: own BVH2 if no native device acceleration struct used. */
	@@ -144,6 +145,7 @@ KERNEL_STRUCT_BEGIN(KernelIntegrator, integrator)
	/* Emission. */
	KERNEL_STRUCT_MEMBER(integrator, int, use_direct_light)
	KERNEL_STRUCT_MEMBER(integrator, int, num_distribution)
	+KERNEL_STRUCT_MEMBER(integrator, int, num_distant_lights)
	KERNEL_STRUCT_MEMBER(integrator, int, num_all_lights)
	KERNEL_STRUCT_MEMBER(integrator, float, pdf_triangles)
	KERNEL_STRUCT_MEMBER(integrator, float, pdf_lights)
	@@ -190,8 +192,12 @@ KERNEL_STRUCT_MEMBER(integrator, int, has_shadow_catcher)
	KERNEL_STRUCT_MEMBER(integrator, int, filter_closures)
	/* MIS debugging. */
	KERNEL_STRUCT_MEMBER(integrator, int, direct_light_sampling_type)
	+/* Light tree. */
	+KERNEL_STRUCT_MEMBER(integrator, int, use_light_tree)
	+KERNEL_STRUCT_MEMBER(integrator, float, splitting_threshold)
	/* Padding */
	KERNEL_STRUCT_MEMBER(integrator, int, pad1)
	+KERNEL_STRUCT_MEMBER(integrator, int, pad2)
	KERNEL_STRUCT_END(KernelIntegrator)

	/* SVM. For shader specialization. */
	diff --git a/intern/cycles/kernel/integrator/shade_background.h b/intern/cycles/kernel/integrator/shade_background.h
	index 57d060d58df..c5beda0a5ec 100644
	--- a/intern/cycles/kernel/integrator/shade_background.h
	+++ b/intern/cycles/kernel/integrator/shade_background.h
	@@ -6,6 +6,7 @@
	#include "kernel/film/accumulate.h"
	#include "kernel/integrator/shader_eval.h"
	#include "kernel/light/light.h"
	+#include "kernel/light/light_tree.h"
	#include "kernel/light/sample.h"

	CCL_NAMESPACE_BEGIN
	@@ -65,7 +66,11 @@ ccl_device Spectrum integrator_eval_background_shader(KernelGlobals kg,

	/* multiple importance sampling, get background light pdf for ray
	* direction, and compute weight with respect to BSDF pdf */
	- const float pdf = background_light_pdf(kg, ray_P, ray_D);
	+ float pdf = background_light_pdf(kg, ray_P, ray_D);
	+ if (kernel_data.integrator.use_light_tree) {
	+ const float3 N = INTEGRATOR_STATE(state, path, mis_origin_n);
	+ pdf *= distant_lights_pdf(kg, ray_P, N, kernel_data.background.light_index);
	+ }
	const float mis_weight = light_sample_mis_weight_forward(kg, mis_ray_pdf, pdf);
	L *= mis_weight;
	}
	@@ -179,6 +184,11 @@ ccl_device_inline void integrate_distant_lights(KernelGlobals kg,
	/* multiple importance sampling, get regular light pdf,
	* and compute weight with respect to BSDF pdf */
	const float mis_ray_pdf = INTEGRATOR_STATE(state, path, mis_ray_pdf);
	+ if (kernel_data.integrator.use_light_tree) {
	+ const float3 ray_P = INTEGRATOR_STATE(state, ray, P);
	+ const float3 N = INTEGRATOR_STATE(state, path, mis_origin_n);
	+ ls.pdf *= distant_lights_pdf(kg, ray_P, N, lamp);
	+ }
	const float mis_weight = light_sample_mis_weight_forward(kg, mis_ray_pdf, ls.pdf);
	light_eval *= mis_weight;
	}
	diff --git a/intern/cycles/kernel/integrator/shade_light.h b/intern/cycles/kernel/integrator/shade_light.h
	index ac9d1415abb..0857463ba53 100644
	--- a/intern/cycles/kernel/integrator/shade_light.h
	+++ b/intern/cycles/kernel/integrator/shade_light.h
	@@ -61,6 +61,10 @@ ccl_device_inline void integrate_light(KernelGlobals kg,
	/* multiple importance sampling, get regular light pdf,
	* and compute weight with respect to BSDF pdf */
	const float mis_ray_pdf = INTEGRATOR_STATE(state, path, mis_ray_pdf);
	+ if (kernel_data.integrator.use_light_tree) {
	+ const float3 N = INTEGRATOR_STATE(state, path, mis_origin_n);
	+ ls.pdf *= light_tree_pdf(kg, state, ray_P, N, ~ls.lamp);
	+ }
	const float mis_weight = light_sample_mis_weight_forward(kg, mis_ray_pdf, ls.pdf);
	light_eval *= mis_weight;
	}
	diff --git a/intern/cycles/kernel/integrator/shade_surface.h b/intern/cycles/kernel/integrator/shade_surface.h
	index f42e2979b3b..a036d4565ae 100644
	--- a/intern/cycles/kernel/integrator/shade_surface.h
	+++ b/intern/cycles/kernel/integrator/shade_surface.h
	@@ -14,6 +14,7 @@
	#include "kernel/integrator/volume_stack.h"

	#include "kernel/light/light.h"
	+#include "kernel/light/light_tree.h"
	#include "kernel/light/sample.h"

	CCL_NAMESPACE_BEGIN
	@@ -126,6 +127,14 @@ ccl_device_forceinline void integrate_surface_emission(KernelGlobals kg,
	/* Multiple importance sampling, get triangle light pdf,
	* and compute weight with respect to BSDF pdf. */
	float pdf = triangle_light_pdf(kg, sd, t);
	+ if (kernel_data.integrator.use_light_tree) {
	+ float3 ray_P = INTEGRATOR_STATE(state, ray, P);
	+ const float3 ray_D = INTEGRATOR_STATE(state, ray, D);
	+ const float3 N = INTEGRATOR_STATE(state, path, mis_origin_n);
	+ uint lookup_offset = kernel_data_fetch(object_lookup_offset, sd->object);
	+ uint prim_offset = kernel_data_fetch(object_prim_offset, sd->object);
	+ pdf *= light_tree_pdf(kg, state, ray_P, N, sd->prim - prim_offset + lookup_offset);
	+ }
	float mis_weight = light_sample_mis_weight_forward(kg, bsdf_pdf, pdf);
	L *= mis_weight;
	}
	@@ -158,9 +167,17 @@ ccl_device_forceinline void integrate_surface_direct_light(KernelGlobals kg,
	float light_u, light_v;
	path_state_rng_2D(kg, rng_state, PRNG_LIGHT_U, &light_u, &light_v);

	- if (!light_distribution_sample_from_position(
	- kg, light_u, light_v, sd->time, sd->P, bounce, path_flag, &ls)) {
	- return;
	+ if (kernel_data.integrator.use_light_tree) {
	+ if (!light_tree_sample_from_position(
	+ kg, rng_state, light_u, light_v, sd->time, sd->P, sd->N, bounce, path_flag, &ls)) {
	+ return;
	+ }
	+ }
	+ else {
	+ if (!light_distribution_sample_from_position(
	+ kg, light_u, light_v, sd->time, sd->P, bounce, path_flag, &ls)) {
	+ return;
	+ }
	}
	}

	@@ -404,6 +421,7 @@ ccl_device_forceinline int integrate_surface_bsdf_bssrdf_bounce(
	/* Update path state */
	if (!(label & LABEL_TRANSPARENT)) {
	INTEGRATOR_STATE_WRITE(state, path, mis_ray_pdf) = bsdf_pdf;
	+ INTEGRATOR_STATE_WRITE(state, path, mis_origin_n) = sd->N;
	INTEGRATOR_STATE_WRITE(state, path, min_ray_pdf) = fminf(
	bsdf_pdf, INTEGRATOR_STATE(state, path, min_ray_pdf));
	}
	diff --git a/intern/cycles/kernel/integrator/state_template.h b/intern/cycles/kernel/integrator/state_template.h
	index f4e280e4cb2..38fd5b752e0 100644
	--- a/intern/cycles/kernel/integrator/state_template.h
	+++ b/intern/cycles/kernel/integrator/state_template.h
	@@ -41,6 +41,7 @@ KERNEL_STRUCT_MEMBER(path, uint8_t, mnee, KERNEL_FEATURE_PATH_TRACING)
	* zero and distance. Note that transparency and volume attenuation increase
	* the ray tmin but keep P unmodified so that this works. */
	KERNEL_STRUCT_MEMBER(path, float, mis_ray_pdf, KERNEL_FEATURE_PATH_TRACING)
	+KERNEL_STRUCT_MEMBER(path, packed_float3, mis_origin_n, KERNEL_FEATURE_PATH_TRACING)
	/* Filter glossy. */
	KERNEL_STRUCT_MEMBER(path, float, min_ray_pdf, KERNEL_FEATURE_PATH_TRACING)
	/* Continuation probability for path termination. */
	diff --git a/intern/cycles/kernel/light/light.h b/intern/cycles/kernel/light/light.h
	index b939489bb18..4816bfa98ce 100644
	--- a/intern/cycles/kernel/light/light.h
	+++ b/intern/cycles/kernel/light/light.h
	@@ -649,32 +649,43 @@ ccl_device_forceinline float triangle_light_pdf(KernelGlobals kg,
	}
	else {
	float area = 1.0f;
	- if (has_motion) {
	- /* get the center frame vertices, this is what the PDF was calculated from */
	- triangle_world_space_vertices(kg, sd->object, sd->prim, -1.0f, V);
	- area = triangle_area(V[0], V[1], V[2]);
	- }
	- else {
	- area = 0.5f * len(N);
	+ if (!kernel_data.integrator.use_light_tree) {
	+ if (has_motion) {
	+ /* get the center frame vertices, this is what the PDF was calculated from */
	+ triangle_world_space_vertices(kg, sd->object, sd->prim, -1.0f, V);
	+ area = triangle_area(V[0], V[1], V[2]);
	+ }
	+ else {
	+ area = 0.5f * len(N);
	+ }
	}
	- const float pdf = area * kernel_data.integrator.pdf_triangles;
	+ float pdf = area * kernel_data.integrator.pdf_triangles;
	return pdf / solid_angle;
	}
	}
	else {
	float pdf = triangle_light_pdf_area(kg, sd->Ng, sd->I, t);
	- if (has_motion) {
	- const float area = 0.5f * len(N);
	- if (UNLIKELY(area == 0.0f)) {
	- return 0.0f;
	- }
	+ const float area = 0.5f * len(N);
	+ if (UNLIKELY(area == 0.0f)) {
	+ return 0.0f;
	+ }
	+
	+ if (area != 0.0f) {
	/* scale the PDF.
	* area = the area the sample was taken from
	* area_pre = the are from which pdf_triangles was calculated from */
	- triangle_world_space_vertices(kg, sd->object, sd->prim, -1.0f, V);
	- const float area_pre = triangle_area(V[0], V[1], V[2]);
	- pdf = pdf * area_pre / area;
	+ if (has_motion) {
	+ triangle_world_space_vertices(kg, sd->object, sd->prim, sd->time, V);
	+ const float area_pre = (kernel_data.integrator.use_light_tree) ?
	+ 1.0f :
	+ triangle_area(V[0], V[1], V[2]);
	+ pdf *= area_pre / area;
	+ }
	+ else if (kernel_data.integrator.use_light_tree) {
	+ pdf /= area;
	+ }
	}
	+
	return pdf;
	}
	}
	@@ -801,6 +812,10 @@ ccl_device_forceinline void triangle_light_sample(KernelGlobals kg,
	triangle_world_space_vertices(kg, object, prim, -1.0f, V);
	area = triangle_area(V[0], V[1], V[2]);
	}
	+
	+ if (kernel_data.integrator.use_light_tree) {
	+ area = 1.0f;
	+ }
	const float pdf = area * kernel_data.integrator.pdf_triangles;
	ls->pdf = pdf / solid_angle;
	}
	@@ -824,13 +839,20 @@ ccl_device_forceinline void triangle_light_sample(KernelGlobals kg,
	/* compute incoming direction, distance and pdf */
	ls->D = normalize_len(ls->P - P, &ls->t);
	ls->pdf = triangle_light_pdf_area(kg, ls->Ng, -ls->D, ls->t);
	- if (has_motion && area != 0.0f) {
	+ if (area != 0.0f) {
	/* scale the PDF.
	* area = the area the sample was taken from
	* area_pre = the are from which pdf_triangles was calculated from */
	- triangle_world_space_vertices(kg, object, prim, -1.0f, V);
	- const float area_pre = triangle_area(V[0], V[1], V[2]);
	- ls->pdf = ls->pdf * area_pre / area;
	+ if (has_motion) {
	+ triangle_world_space_vertices(kg, object, prim, -1.0f, V);
	+ const float area_pre = (kernel_data.integrator.use_light_tree) ?
	+ 1.0f :
	+ triangle_area(V[0], V[1], V[2]);
	+ ls->pdf = ls->pdf * area_pre / area;
	+ }
	+ else if (kernel_data.integrator.use_light_tree) {
	+ ls->pdf = ls->pdf / area;
	+ }
	}
	ls->u = u;
	ls->v = v;
	diff --git a/intern/cycles/kernel/light/light_tree.h b/intern/cycles/kernel/light/light_tree.h
	new file mode 100644
	index 00000000000..ab366cfe8a3
	--- /dev/null
	+++ b/intern/cycles/kernel/light/light_tree.h
	@@ -0,0 +1,727 @@
	+#pragma once
	+
	+#include "kernel/light/light.h"
	+
	+CCL_NAMESPACE_BEGIN
	+
	+/* to-do: this seems like a relative expensive computation, and we can make it a lot cheaper
	+ * by using a bounding sphere instead of a bounding box. This will be more inaccurate, but it
	+ * might be fine when used along with the adaptive splitting. */
	+ccl_device float light_tree_bounding_box_angle(const float3 bbox_min,
	+ const float3 bbox_max,
	+ const float3 P,
	+ const float3 point_to_centroid)
	+{
	+ /* Iterate through all 8 possible points of the bounding box. */
	+ float theta_u = 0;
	+ float3 corners[8];
	+ corners[0] = bbox_min;
	+ corners[1] = make_float3(bbox_min.x, bbox_min.y, bbox_max.z);
	+ corners[2] = make_float3(bbox_min.x, bbox_max.y, bbox_min.z);
	+ corners[3] = make_float3(bbox_min.x, bbox_max.y, bbox_max.z);
	+ corners[4] = make_float3(bbox_max.x, bbox_min.y, bbox_min.z);
	+ corners[5] = make_float3(bbox_max.x, bbox_min.y, bbox_max.z);
	+ corners[6] = make_float3(bbox_max.x, bbox_max.y, bbox_min.z);
	+ corners[7] = bbox_max;
	+ for (int i = 0; i < 8; ++i) {
	+ float3 point_to_corner = normalize(corners[i] - P);
	+ const float cos_theta_u = dot(point_to_centroid, point_to_corner);
	+ theta_u = fmaxf(fast_acosf(cos_theta_u), theta_u);
	+ }
	+ return theta_u;
	+}
	+
	+/* This is the general function for calculating the importance of either a cluster or an emitter.
	+ * Both of the specialized functions obtain the necessary data before calling this function. */
	+ccl_device float light_tree_node_importance(const float3 P,
	+ const float3 N,
	+ const float3 bbox_min,
	+ const float3 bbox_max,
	+ const float3 bcone_axis,
	+ const float theta_o,
	+ const float theta_e,
	+ const float energy)
	+{
	+ const float3 centroid = 0.5f * bbox_min + 0.5f * bbox_max;
	+ const float3 point_to_centroid = normalize(centroid - P);
	+
	+ /* Since we're not using the splitting heuristic, we clamp
	+ * the distance to half the radius of the cluster. */
	+ const float distance_squared = fmaxf(0.25f * len_squared(centroid - bbox_max),
	+ len_squared(centroid - P));
	+
	+ /* to-do: should there be a different importance calculations for different surfaces?
	+ * opaque surfaces could just return 0 importance in this case. */
	+ const float theta = fast_acosf(dot(bcone_axis, -point_to_centroid));
	+ float theta_i = fast_acosf(dot(point_to_centroid, N));
	+ if (theta_i > M_PI_2_F) {
	+ theta_i = M_PI_F - theta_i;
	+ }
	+ const float theta_u = light_tree_bounding_box_angle(bbox_min, bbox_max, P, point_to_centroid);
	+
	+ /* Avoid using cosine until needed. */
	+ const float theta_prime = fmaxf(theta - theta_o - theta_u, 0.0f);
	+ if (theta_prime >= theta_e) {
	+ return 0.0f;
	+ }
	+ const float cos_theta_prime = fast_cosf(theta_prime);
	+
	+ float cos_theta_i_prime = 1.0f;
	+ if (theta_i - theta_u > 0.0f) {
	+ cos_theta_i_prime = fabsf(fast_cosf(theta_i - theta_u));
	+ }
	+
	+ /* to-do: find a good approximation for this value. */
	+ const float f_a = 1.0f;
	+ float importance = f_a * cos_theta_i_prime * energy / distance_squared * cos_theta_prime;
	+ return importance;
	+}
	+
	+/* This is uniformly sampling the reservoir for now. */
	+ccl_device float light_tree_emitter_reservoir_weight(KernelGlobals kg,
	+ const float3 P,
	+ const float3 N,
	+ int emitter_index)
	+{
	+ if (emitter_index < 0) {
	+ return 0.0f;
	+ }
	+
	+ ccl_global const KernelLightTreeEmitter *kemitter = &kernel_data_fetch(light_tree_emitters,
	+ emitter_index);
	+ const int prim = kemitter->prim_id;
	+
	+ /* Triangles are handled normally for now. */
	+ if (prim < 0) {
	+ const int lamp = -prim - 1;
	+
	+ const ccl_global KernelLight *klight = &kernel_data_fetch(lights, lamp);
	+ float3 light_P = make_float3(klight->co[0], klight->co[1], klight->co[2]);
	+
	+ /* We use a special calculation to check if a light is
	+ * within the bounds of a spot or area light. */
	+ if (klight->type == LIGHT_SPOT) {
	+ const float radius = klight->spot.radius;
	+ const float cos_theta = klight->spot.spot_angle;
	+ const float theta = fast_acosf(cos_theta);
	+ const float3 light_P = make_float3(klight->co[0], klight->co[1], klight->co[2]);
	+ const float3 light_dir = make_float3(
	+ klight->spot.dir[0], klight->spot.dir[1], klight->spot.dir[2]);
	+
	+ const float h1 = radius * fast_sinf(theta);
	+ const float d1 = radius * cos_theta;
	+ const float h2 = d1 / fast_tanf(theta);
	+
	+ const float3 apex = light_P - (h1 + h2) * light_dir;
	+ const float3 apex_to_point = normalize(P - apex);
	+ if (dot(apex_to_point, light_dir) < cos_theta) {
	+ return 0.0f;
	+ }
	+ }
	+ else if (klight->type == LIGHT_AREA) {
	+ float3 axisu = make_float3(
	+ klight->area.axisu[0], klight->area.axisu[1], klight->area.axisu[2]);
	+ float3 axisv = make_float3(
	+ klight->area.axisv[0], klight->area.axisv[1], klight->area.axisv[2]);
	+ float3 Ng = make_float3(klight->area.dir[0], klight->area.dir[1], klight->area.dir[2]);
	+ bool is_round = (klight->area.invarea < 0.0f);
	+
	+ if (dot(light_P - P, Ng) > 0.0f) {
	+ return 0.0f;
	+ }
	+
	+ if (!is_round) {
	+ if (klight->area.tan_spread > 0.0f) {
	+ if (!light_spread_clamp_area_light(
	+ P, Ng, &light_P, &axisu, &axisv, klight->area.tan_spread)) {
	+ return 0.0f;
	+ }
	+ }
	+ }
	+ }
	+ }
	+
	+ return 1.0f;
	+}
	+
	+ccl_device float light_tree_emitter_importance(KernelGlobals kg,
	+ const float3 P,
	+ const float3 N,
	+ int emitter_index)
	+{
	+ ccl_global const KernelLightTreeEmitter *kemitter = &kernel_data_fetch(light_tree_emitters,
	+ emitter_index);
	+
	+ const float3 bbox_min = make_float3(kemitter->bounding_box_min[0],
	+ kemitter->bounding_box_min[1],
	+ kemitter->bounding_box_min[2]);
	+ const float3 bbox_max = make_float3(kemitter->bounding_box_max[0],
	+ kemitter->bounding_box_max[1],
	+ kemitter->bounding_box_max[2]);
	+ const float3 bcone_axis = make_float3(kemitter->bounding_cone_axis[0],
	+ kemitter->bounding_cone_axis[1],
	+ kemitter->bounding_cone_axis[2]);
	+
	+ return light_tree_node_importance(
	+ P, N, bbox_min, bbox_max, bcone_axis, kemitter->theta_o, kemitter->theta_e, kemitter->energy);
	+}
	+
	+ccl_device bool light_tree_should_split(KernelGlobals kg,
	+ const float3 P,
	+ const ccl_global KernelLightTreeNode *knode)
	+{
	+ const float splitting_threshold = kernel_data.integrator.splitting_threshold;
	+ if (splitting_threshold == 0.0f) {
	+ return false;
	+ }
	+ else if (splitting_threshold == 1.0f) {
	+ return true;
	+ }
	+
	+ const float3 bbox_min = make_float3(
	+ knode->bounding_box_min[0], knode->bounding_box_min[1], knode->bounding_box_min[2]);
	+ const float3 bbox_max = make_float3(
	+ knode->bounding_box_max[0], knode->bounding_box_max[1], knode->bounding_box_max[2]);
	+ const float3 centroid = 0.5f * bbox_min + 0.5f * bbox_max;
	+
	+ const float radius = len(bbox_max - centroid);
	+ const float distance = len(P - centroid);
	+
	+ if (distance < radius) {
	+ return true;
	+ }
	+
	+ const float a = distance - radius;
	+ const float b = distance + radius;
	+
	+ const float E_g = 1.0f / (a * b);
	+ const float E_e = knode->energy;
	+
	+ /* This is a simplified version of the expression given in the paper. */
	+ const float V_g = (b - a) * (b - a) * E_g * E_g * E_g / 3.0f;
	+ const float V_e = knode->energy_variance;
	+
	+ const float total_variance = V_e * V_g + V_e * E_g * E_g + E_e * E_e * V_g;
	+ const float normalized_variance = sqrt(sqrt(1.0f / (1.0f + sqrt(total_variance))));
	+ return (normalized_variance < splitting_threshold);
	+}
	+
	+ccl_device float light_tree_cluster_importance(KernelGlobals kg,
	+ const float3 P,
	+ const float3 N,
	+ const ccl_global KernelLightTreeNode *knode)
	+{
	+ const float3 bbox_min = make_float3(
	+ knode->bounding_box_min[0], knode->bounding_box_min[1], knode->bounding_box_min[2]);
	+ const float3 bbox_max = make_float3(
	+ knode->bounding_box_max[0], knode->bounding_box_max[1], knode->bounding_box_max[2]);
	+ const float3 bcone_axis = make_float3(
	+ knode->bounding_cone_axis[0], knode->bounding_cone_axis[1], knode->bounding_cone_axis[2]);
	+
	+ return light_tree_node_importance(
	+ P, N, bbox_min, bbox_max, bcone_axis, knode->theta_o, knode->theta_e, knode->energy);
	+}
	+
	+ccl_device int light_tree_cluster_select_emitter(KernelGlobals kg,
	+ ccl_private float *randu,
	+ const float3 P,
	+ const float3 N,
	+ const ccl_global KernelLightTreeNode *knode,
	+ ccl_private float *pdf_factor)
	+{
	+ float total_emitter_importance = 0.0f;
	+ for (int i = 0; i < knode->num_prims; i++) {
	+ const int prim_index = -knode->child_index + i;
	+ total_emitter_importance += light_tree_emitter_importance(kg, P, N, prim_index);
	+ }
	+
	+ /* to-do: need to handle a case when total importance is 0. */
	+ if (total_emitter_importance == 0.0f) {
	+ return -1;
	+ }
	+
	+ /* Once we have the total importance, we can normalize the CDF and sample it. */
	+ const float inv_total_importance = 1.0f / total_emitter_importance;
	+ float emitter_cdf = 0.0f;
	+ for (int i = 0; i < knode->num_prims; i++) {
	+ const int prim_index = -knode->child_index + i;
	+ /* to-do: is there any way to cache these values, so that recalculation isn't needed? */
	+ const float emitter_pdf = light_tree_emitter_importance(kg, P, N, prim_index) *
	+ inv_total_importance;
	+ if (*randu < emitter_cdf + emitter_pdf) {
	+ randu = (randu - emitter_cdf) / emitter_pdf;
	+ pdf_factor = emitter_pdf;
	+ return prim_index;
	+ }
	+ emitter_cdf += emitter_pdf;
	+ }
	+
	+ /* This point should never be reached. */
	+ assert(false);
	+ return -1;
	+}
	+
	+/* to-do: for now, we're not going to worry about being in a volume,
	+ * but this is how the other function determines whether we're in a volume or not. */
	+template<bool in_volume_segment>
	+ccl_device bool light_tree_sample(KernelGlobals kg,
	+ ccl_private const RNGState *rng_state,
	+ ccl_private float *randu,
	+ const float randv,
	+ const float time,
	+ const float3 N,
	+ const float3 P,
	+ const int bounce,
	+ const uint32_t path_flag,
	+ ccl_private LightSample *ls,
	+ ccl_private float *pdf_factor)
	+{
	+ /* We keep track of the currently selected primitive and its weight,
	+ * as well as the total weight as part of the weighted reservoir sampling. */
	+ int current_light = -1;
	+ float current_weight = -1.0f;
	+ float total_weight = 0.0f;
	+ float current_pdf = 1.0f;
	+
	+ /* We need a stack to substitute for recursion. */
	+ const int stack_size = 32;
	+ int stack[stack_size];
	+ float pdfs[stack_size];
	+ int stack_index = 0;
	+ stack[0] = 0;
	+ pdfs[0] = 1.0f;
	+
	+ /* For now, we arbitrarily limit splitting to 8 so that it doesn't continuously split. */
	+ int split_count = 0;
	+
	+ /* First traverse the light tree until a leaf node is reached.
	+ * Also keep track of the probability of traversing to a given node,
	+ * so that we can scale our PDF accordingly later. */
	+ while (stack_index >= 0) {
	+ const float pdf = pdfs[stack_index];
	+ const int index = stack[stack_index];
	+ const ccl_global KernelLightTreeNode *knode = &kernel_data_fetch(light_tree_nodes, index);
	+
	+ /* If we're at a leaf node, we choose a primitive. Otherwise, we check if we should split
	+ * or traverse down the light tree. */
	+ if (knode->child_index <= 0) {
	+ float light_probability = 1.0f;
	+ const int selected_light = light_tree_cluster_select_emitter(kg, randu, P, N, knode, &light_probability);
	+
	+ if (selected_light < 0) {
	+ stack_index--;
	+ continue;
	+ }
	+
	+ const float light_weight = light_tree_emitter_reservoir_weight(
	+ kg, P, N, selected_light);
	+ if (light_weight == 0.0f) {
	+ stack_index--;
	+ continue;
	+ }
	+ total_weight += light_weight;
	+
	+ /* We compute the probability of switching to the new candidate sample,
	+ * otherwise we stick with the old one. */
	+ const float selection_probability = light_weight / total_weight;
	+ if (*randu < selection_probability) {
	+ randu = randu / selection_probability;
	+ current_light = selected_light;
	+ current_weight = light_weight;
	+ current_pdf = pdf * light_probability;
	+ }
	+ else {
	+ randu = (randu - selection_probability) / (1.0f - selection_probability);
	+ }
	+
	+ stack_index--;
	+ continue;
	+ }
	+
	+ /* At an interior node, the left child is directly after the parent,
	+ * while the right child is stored as the child index.
	+ * We adaptively split if the variance is high enough. */
	+ const int left_index = index + 1;
	+ const int right_index = knode->child_index;
	+ if (light_tree_should_split(kg, P, knode) &&
	+ split_count < 8 &&
	+ stack_index < stack_size - 1) {
	+ stack[stack_index] = left_index;
	+ pdfs[stack_index] = pdf;
	+ stack[stack_index + 1] = right_index;
	+ pdfs[stack_index + 1] = pdf;
	+ stack_index++;
	+ split_count++;
	+ continue;
	+ }
	+
	+ /* If we don't split, then we need to choose sampling between the left or right child. */
	+ const ccl_global KernelLightTreeNode *left = &kernel_data_fetch(light_tree_nodes, left_index);
	+ const ccl_global KernelLightTreeNode *right = &kernel_data_fetch(light_tree_nodes, right_index);
	+
	+ const float left_importance = light_tree_cluster_importance(kg, P, N, left);
	+ const float right_importance = light_tree_cluster_importance(kg, P, N, right);
	+ const float total_importance = left_importance + right_importance;
	+
	+ if (total_importance == 0.0f) {
	+ stack_index--;
	+ continue;
	+ }
	+ float left_probability = left_importance / (left_importance + right_importance);
	+
	+ if (*randu < left_probability) {
	+ stack[stack_index] = left_index;
	+ randu = randu / left_probability;
	+ pdfs[stack_index] = pdf * left_probability;
	+ }
	+ else {
	+ stack[stack_index] = right_index;
	+ randu = (randu - left_probability) / (1.0f - left_probability);
	+ pdfs[stack_index] = pdf * (1.0f - left_probability);
	+ }
	+ }
	+
	+ if (total_weight == 0.0f) {
	+ return false;
	+ }
	+
	+ pdf_factor = current_pdf * current_weight / total_weight;
	+
	+ ccl_global const KernelLightTreeEmitter *kemitter = &kernel_data_fetch(light_tree_emitters,
	+ current_light);
	+
	+ /* to-do: this is the same code as light_distribution_sample, except the index is determined
	+ * differently. Would it be better to refactor this into a separate function? */
	+ const int prim = kemitter->prim_id;
	+ if (prim >= 0) {
	+ /* Mesh light. */
	+ const int object = kemitter->mesh_light.object_id;
	+
	+ /* Exclude synthetic meshes from shadow catcher pass. */
	+ if ((path_flag & PATH_RAY_SHADOW_CATCHER_PASS) &&
	+ !(kernel_data_fetch(object_flag, object) & SD_OBJECT_SHADOW_CATCHER)) {
	+ return false;
	+ }
	+
	+ const int shader_flag = kemitter->mesh_light.shader_flag;
	+ triangle_light_sample<in_volume_segment>(kg, prim, object, *randu, randv, time, ls, P);
	+ ls->shader \|= shader_flag;
	+
	+ return (ls->pdf > 0.0f);
	+ }
	+
	+ const int lamp = -prim - 1;
	+
	+ if (UNLIKELY(light_select_reached_max_bounces(kg, lamp, bounce))) {
	+ return false;
	+ }
	+
	+ return light_sample<in_volume_segment>(kg, lamp, *randu, randv, P, path_flag, ls);
	+}
	+
	+ccl_device float light_tree_distant_light_importance(KernelGlobals kg,
	+ const float3 P,
	+ const float3 N,
	+ const int index)
	+{
	+ ccl_global const KernelLightTreeDistantEmitter *kdistant = &kernel_data_fetch(
	+ light_tree_distant_group, index);
	+
	+ if (kdistant->energy == 0.0f) {
	+ return 0.0f;
	+ }
	+
	+ const float3 light_axis = make_float3(
	+ kdistant->direction[0], kdistant->direction[1], kdistant->direction[2]);
	+ const float theta = fast_acosf(dot(N, light_axis));
	+ const float theta_i_prime = theta - kdistant->bounding_radius;
	+
	+ float cos_theta_i_prime = 1.0f;
	+ if (theta_i_prime > M_PI_2_F) {
	+ return 0.0f;
	+ } else if (theta - kdistant->bounding_radius > 0.0f) {
	+ cos_theta_i_prime = fast_cosf(theta - kdistant->bounding_radius);
	+ }
	+
	+ /* to-do: find a good value for this. */
	+ const float f_a = 1.0f;
	+ float importance = f_a * cos_theta_i_prime * kdistant->energy;
	+ return importance;
	+}
	+
	+template<bool in_volume_segment>
	+ccl_device bool light_tree_sample_distant_lights(KernelGlobals kg,
	+ ccl_private const RNGState *rng_state,
	+ ccl_private float *randu,
	+ const float randv,
	+ const float time,
	+ const float3 N,
	+ const float3 P,
	+ const int bounce,
	+ const uint32_t path_flag,
	+ ccl_private LightSample *ls,
	+ ccl_private float *pdf_factor)
	+{
	+ const int num_distant_lights = kernel_data.integrator.num_distant_lights;
	+ float total_importance = 0.0f;
	+ for (int i = 0; i < num_distant_lights; i++) {
	+ total_importance += light_tree_distant_light_importance(kg, P, N, i);
	+ }
	+ const float inv_total_importance = 1.0f / total_importance;
	+
	+ float light_cdf = 0.0f;
	+ for (int i = 0; i < num_distant_lights; i++) {
	+ const float light_pdf = light_tree_distant_light_importance(kg, P, N, i) *
	+ inv_total_importance;
	+ if (*randu < light_cdf + light_pdf) {
	+ randu = (randu - light_cdf) / light_pdf;
	+ pdf_factor = light_pdf;
	+ ccl_global const KernelLightTreeDistantEmitter *kdistant = &kernel_data_fetch(
	+ light_tree_distant_group, i);
	+
	+ const int lamp = kdistant->prim_id;
	+
	+ if (UNLIKELY(light_select_reached_max_bounces(kg, lamp, bounce))) {
	+ return false;
	+ }
	+
	+ return light_sample<in_volume_segment>(kg, lamp, *randu, randv, P, path_flag, ls);
	+ }
	+ light_cdf += light_pdf;
	+ }
	+
	+ /* We should never reach this point. */
	+ assert(false);
	+ return -1;
	+}
	+
	+/* We need to be able to find the probability of selecting a given light for MIS. */
	+ccl_device float light_tree_pdf(KernelGlobals kg,
	+ ConstIntegratorState state,
	+ const float3 P,
	+ const float3 N,
	+ const int prim)
	+{
	+ float distant_light_importance = light_tree_distant_light_importance(
	+ kg, P, N, kernel_data.integrator.num_distant_lights);
	+ float light_tree_importance = 0.0f;
	+ if (kernel_data.integrator.num_distribution > kernel_data.integrator.num_distant_lights) {
	+ const ccl_global KernelLightTreeNode *kroot = &kernel_data_fetch(light_tree_nodes, 0);
	+ light_tree_importance = light_tree_cluster_importance(kg, P, N, kroot);
	+ }
	+ const float total_group_importance = light_tree_importance + distant_light_importance;
	+ assert(total_group_importance != 0.0f);
	+ float pdf = light_tree_importance / total_group_importance;
	+
	+ const int emitter = (prim >= 0) ? kernel_data_fetch(triangle_to_tree, prim) :
	+ kernel_data_fetch(light_to_tree, ~prim);
	+ ccl_global const KernelLightTreeEmitter *kemitter = &kernel_data_fetch(light_tree_emitters,
	+ emitter);
	+ const int target_leaf = kemitter->parent_index;
	+ ccl_global const KernelLightTreeNode *kleaf = &kernel_data_fetch(light_tree_nodes, target_leaf);
	+
	+ /* We generate a random number to use for selecting a light. */
	+ RNGState rng_state;
	+ path_state_rng_load(state, &rng_state);
	+ float randu = path_state_rng_1D_hash(kg, &rng_state, 0x6a21694c);
	+
	+ /* We traverse to the leaf node and
	+ * find the probability of selecting the target light. */
	+ const int stack_size = 32;
	+ int stack[stack_size];
	+ float pdfs[stack_size];
	+ int stack_index = 0;
	+ stack[0] = 0;
	+ pdfs[0] = 1.0f;
	+
	+ int split_count = 0;
	+
	+ float light_tree_pdf = 0.0f;
	+ float light_leaf_pdf = 0.0f;
	+ float total_weight = 0.0f;
	+ float target_weight = 0.0f;
	+
	+ uint bit_trail = kleaf->bit_trail;
	+ while (stack_index >= 0) {
	+ const float pdf = pdfs[stack_index];
	+ const int index = stack[stack_index];
	+ const ccl_global KernelLightTreeNode *knode = &kernel_data_fetch(light_tree_nodes, index);
	+
	+ if (knode->child_index <= 0) {
	+ int selected_light = -1;
	+ float light_weight = 0.0f;
	+
	+ /* If we're at the leaf node containing the light we need,
	+ * then we iterate through the lights to find the target emitter.
	+ * Otherwise, we randomly select one. */
	+ if (index == target_leaf) {
	+ light_tree_pdf = pdf;
	+
	+ float target_emitter_importance = 0.0f;
	+ float total_emitter_importance = 0.0f;
	+ for (int i = 0; i < knode->num_prims; i++) {
	+ const int prim_index = -knode->child_index + i;
	+ float light_importance = light_tree_emitter_importance(kg, P, N, prim_index);
	+ if (prim_index == prim) {
	+ selected_light = prim_index;
	+ light_weight = light_tree_emitter_reservoir_weight(kg, P, N, selected_light);
	+ target_weight = light_weight;
	+ target_emitter_importance = light_importance;
	+ }
	+ total_emitter_importance += light_importance;
	+ }
	+
	+ light_leaf_pdf = target_emitter_importance / total_emitter_importance;
	+ }
	+ else {
	+ float light_probability = 1.0f;
	+ selected_light = light_tree_cluster_select_emitter(
	+ kg, &randu, P, N, knode, &light_probability);
	+ light_weight = light_tree_emitter_reservoir_weight(kg, P, N, selected_light);
	+ }
	+
	+ if (selected_light < 0) {
	+ stack_index--;
	+ continue;
	+ }
	+
	+ if (light_weight == 0.0f) {
	+ stack_index--;
	+ continue;
	+ }
	+ total_weight += light_weight;
	+
	+ stack_index--;
	+ continue;
	+ }
	+
	+ /* At an interior node, the left child is directly after the parent,
	+ * while the right child is stored as the child index.
	+ * We adaptively split if the variance is high enough. */
	+ const int left_index = index + 1;
	+ const int right_index = knode->child_index;
	+ if (light_tree_should_split(kg, P, knode) &&
	+ split_count < 8 &&
	+ stack_index < stack_size - 1) {
	+ stack[stack_index] = left_index;
	+ pdfs[stack_index] = pdf;
	+ stack[stack_index + 1] = right_index;
	+ pdfs[stack_index + 1] = pdf;
	+ stack_index++;
	+ split_count++;
	+ continue;
	+ }
	+
	+ /* If we don't split, the bit trail determines whether we go left or right. */
	+ const ccl_global KernelLightTreeNode *left = &kernel_data_fetch(light_tree_nodes, left_index);
	+ const ccl_global KernelLightTreeNode *right = &kernel_data_fetch(light_tree_nodes,
	+ right_index);
	+
	+ const float left_importance = light_tree_cluster_importance(kg, P, N, left);
	+ const float right_importance = light_tree_cluster_importance(kg, P, N, right);
	+ const float total_importance = left_importance + right_importance;
	+
	+ if (total_importance == 0.0f) {
	+ stack_index--;
	+ continue;
	+ }
	+ float left_probability = left_importance / (left_importance + right_importance);
	+
	+ if (bit_trail & 1) {
	+ stack[stack_index] = right_index;
	+ pdfs[stack_index] = pdf * (1.0f - left_probability);
	+ }
	+ else {
	+ stack[stack_index] = left_index;
	+ pdfs[stack_index] = pdf * left_probability;
	+ }
	+ bit_trail = bit_trail >> 1;
	+ }
	+
	+ pdf = light_leaf_pdf light_tree_pdf * target_weight / total_weight;
	+ return pdf;
	+}
	+
	+ccl_device float distant_lights_pdf(KernelGlobals kg,
	+ const float3 P,
	+ const float3 N,
	+ const int prim)
	+{
	+ float distant_light_importance = light_tree_distant_light_importance(
	+ kg, P, N, kernel_data.integrator.num_distant_lights);
	+ float light_tree_importance = 0.0f;
	+ if (kernel_data.integrator.num_distribution > kernel_data.integrator.num_distant_lights) {
	+ const ccl_global KernelLightTreeNode *kroot = &kernel_data_fetch(light_tree_nodes, 0);
	+ light_tree_importance = light_tree_cluster_importance(kg, P, N, kroot);
	+ }
	+ const float total_group_importance = light_tree_importance + distant_light_importance;
	+ assert(total_group_importance != 0.0f);
	+ float pdf = distant_light_importance / total_group_importance;
	+
	+ /* The light_to_tree array doubles as a lookup table for
	+ * both the light tree as well as the distant lights group.*/
	+ const int distant_light = kernel_data_fetch(light_to_tree, prim);
	+ const int num_distant_lights = kernel_data.integrator.num_distant_lights;
	+
	+ float emitter_importance = 0.0f;
	+ float total_importance = 0.0f;
	+ for (int i = 0; i < num_distant_lights; i++) {
	+ float importance = light_tree_distant_light_importance(kg, P, N, i);
	+ if (i == distant_light) {
	+ emitter_importance = importance;
	+ }
	+ total_importance += importance;
	+ }
	+
	+ pdf *= emitter_importance / total_importance;
	+ return pdf;
	+}
	+
	+ccl_device bool light_tree_sample_from_position(KernelGlobals kg,
	+ ccl_private const RNGState *rng_state,
	+ float randu,
	+ const float randv,
	+ const float time,
	+ const float3 P,
	+ const float3 N,
	+ const int bounce,
	+ const uint32_t path_flag,
	+ ccl_private LightSample *ls)
	+{
	+ /* to-do: with weighted reservoir sampling, we can also try picking a sample from the distant light group
	+ * and compare it to the sample from the light tree. */
	+ float distant_light_importance = light_tree_distant_light_importance(
	+ kg, P, N, kernel_data.integrator.num_distant_lights);
	+ float light_tree_importance = 0.0f;
	+ if (kernel_data.integrator.num_distribution > kernel_data.integrator.num_distant_lights) {
	+ const ccl_global KernelLightTreeNode *kroot = &kernel_data_fetch(light_tree_nodes, 0);
	+ light_tree_importance = light_tree_cluster_importance(kg, P, N, kroot);
	+ }
	+ const float total_importance = light_tree_importance + distant_light_importance;
	+
	+ if (total_importance == 0.0f) {
	+ return false;
	+ }
	+
	+ const float light_tree_probability = light_tree_importance / total_importance;
	+
	+ float pdf_factor = 1.0f;
	+ bool ret;
	+ if (randu < light_tree_probability) {
	+ randu = randu / light_tree_probability;
	+ pdf_factor *= light_tree_probability;
	+ ret = light_tree_sample<false>(
	+ kg, rng_state, &randu, randv, time, N, P, bounce, path_flag, ls, &pdf_factor);
	+ }
	+ else {
	+ randu = (randu - light_tree_probability) / (1.0f - light_tree_probability);
	+ pdf_factor *= (1.0f - light_tree_probability);
	+ ret = light_tree_sample_distant_lights<false>(
	+ kg, rng_state, &randu, randv, time, N, P, bounce, path_flag, ls, &pdf_factor);
	+ }
	+
	+ ls->pdf *= pdf_factor;
	+ return ret;
	+}
	+
	+CCL_NAMESPACE_END
	diff --git a/intern/cycles/kernel/types.h b/intern/cycles/kernel/types.h
	index f55ace1a227..d104a4eb37a 100644
	--- a/intern/cycles/kernel/types.h
	+++ b/intern/cycles/kernel/types.h
	@@ -1302,6 +1302,85 @@ typedef struct KernelLightDistribution {
	} KernelLightDistribution;
	static_assert_align(KernelLightDistribution, 16);

	+typedef struct KernelLightTreeNode {
	+ /* Bounding box. */
	+ float bounding_box_min[3];
	+ float bounding_box_max[3];
	+
	+ /* Bounding cone. */
	+ float bounding_cone_axis[3];
	+ float theta_o;
	+ float theta_e;
	+
	+ /* Energy. */
	+ float energy;
	+
	+ /* If this is 0 or less, we're at a leaf node
	+ * and the negative value indexes into the first child of the light array.
	+ * Otherwise, it's an index to the node's second child. */
	+ int child_index;
	+ union {
	+ int num_prims; /* leaf nodes need to know the number of primitives stored. */
	+ float energy_variance; /* interior nodes use the energy variance for the splitting heuristic. */
	+ };
	+
	+ /* Bit trail. */
	+ uint bit_trail;
	+
	+ /* Padding. */
	+ int pad1;
	+} KernelLightTreeNode;
	+static_assert_align(KernelLightTreeNode, 16);
	+
	+typedef struct KernelLightTreeEmitter {
	+ /* Bounding box. */
	+ float bounding_box_min[3];
	+ float bounding_box_max[3];
	+
	+ /* Bounding cone. */
	+ float bounding_cone_axis[3];
	+ float theta_o;
	+ float theta_e;
	+
	+ /* Energy. */
	+ float energy;
	+
	+ /* prim_id denotes the location in the lights or triangles array. */
	+ int prim_id;
	+ union {
	+ struct {
	+ int shader_flag;
	+ int object_id;
	+ } mesh_light;
	+ struct {
	+ float pad;
	+ float size;
	+ } lamp;
	+ };
	+
	+ /* Parent. */
	+ int parent_index;
	+} KernelLightTreeEmitter;
	+static_assert_align(KernelLightTreeEmitter, 16);
	+
	+typedef struct KernelLightTreeDistantEmitter {
	+ /* Direction from world to light. */
	+ float direction[3];
	+
	+ /* Size of light (in radians). */
	+ float bounding_radius;
	+
	+ /* Energy. */
	+ float energy;
	+
	+ /* Prim ID. */
	+ int prim_id;
	+
	+ /* Padding. */
	+ int pad1, pad2;
	+} KernelLightTreeDistantEmitter;
	+static_assert_align(KernelLightTreeDistantEmitter, 16);
	+
	typedef struct KernelParticle {
	int index;
	float age;
	diff --git a/intern/cycles/scene/CMakeLists.txt b/intern/cycles/scene/CMakeLists.txt
	index a30f408f207..f0922fe8c44 100644
	--- a/intern/cycles/scene/CMakeLists.txt
	+++ b/intern/cycles/scene/CMakeLists.txt
	@@ -25,6 +25,7 @@ set(SRC
	integrator.cpp
	jitter.cpp
	light.cpp
	+ light_tree.cpp
	mesh.cpp
	mesh_displace.cpp
	mesh_subdivision.cpp
	@@ -64,6 +65,7 @@ set(SRC_HEADERS
	image_vdb.h
	integrator.h
	light.h
	+ light_tree.h
	jitter.h
	mesh.h
	object.h
	diff --git a/intern/cycles/scene/background.cpp b/intern/cycles/scene/background.cpp
	index bffc8895bfd..0779313e5ba 100644
	--- a/intern/cycles/scene/background.cpp
	+++ b/intern/cycles/scene/background.cpp
	@@ -4,6 +4,7 @@
	#include "scene/background.h"
	#include "device/device.h"
	#include "scene/integrator.h"
	+#include "scene/light.h"
	#include "scene/scene.h"
	#include "scene/shader.h"
	#include "scene/shader_graph.h"
	@@ -103,6 +104,19 @@ void Background::device_update(Device device, DeviceScene dscene, Scene *scene
	kbackground->surface_shader \|= SHADER_EXCLUDE_CAMERA;
	}

	+ /* Find background index in lights. */
	+ int device_light_index = 0;
	+ int background_light_index = -1;
	+ foreach (Light *light, scene->lights) {
	+ if (light->get_is_enabled()) {
	+ if (light->get_light_type() == LIGHT_BACKGROUND) {
	+ background_light_index = device_light_index;
	+ }
	+ device_light_index++;
	+ }
	+ }
	+ kbackground->light_index = background_light_index;
	+
	/* Light group. */
	auto it = scene->lightgroups.find(lightgroup);
	if (it != scene->lightgroups.end()) {
	diff --git a/intern/cycles/scene/integrator.cpp b/intern/cycles/scene/integrator.cpp
	index 58daf417ab0..0ff6e32ca66 100644
	--- a/intern/cycles/scene/integrator.cpp
	+++ b/intern/cycles/scene/integrator.cpp
	@@ -86,6 +86,9 @@ NODE_DEFINE(Integrator)

	SOCKET_FLOAT(light_sampling_threshold, "Light Sampling Threshold", 0.01f);

	+ SOCKET_BOOLEAN(use_light_tree, "Use light tree to optimize many light sampling", false);
	+ SOCKET_FLOAT(splitting_threshold, "Splitting threshold", 0.85f);
	+
	static NodeEnum sampling_pattern_enum;
	sampling_pattern_enum.insert("sobol", SAMPLING_PATTERN_SOBOL);
	sampling_pattern_enum.insert("pmj", SAMPLING_PATTERN_PMJ);
	@@ -181,6 +184,9 @@ void Integrator::device_update(Device device, DeviceScene dscene, Scene *scene
	kintegrator->direct_light_sampling_type = DIRECT_LIGHT_SAMPLING_MIS;
	#endif

	+ kintegrator->use_light_tree = scene->integrator->use_light_tree;
	+ kintegrator->splitting_threshold = scene->integrator->splitting_threshold;
	+
	/* Transparent Shadows
	* We only need to enable transparent shadows, if we actually have
	* transparent shaders in the scene. Otherwise we can disable it
	diff --git a/intern/cycles/scene/integrator.h b/intern/cycles/scene/integrator.h
	index d54a44b6177..1d9604d58f1 100644
	--- a/intern/cycles/scene/integrator.h
	+++ b/intern/cycles/scene/integrator.h
	@@ -68,6 +68,8 @@ class Integrator : public Node {
	NODE_SOCKET_API(int, start_sample)

	NODE_SOCKET_API(float, light_sampling_threshold)
	+ NODE_SOCKET_API(bool, use_light_tree)
	+ NODE_SOCKET_API(float, splitting_threshold)

	NODE_SOCKET_API(bool, use_adaptive_sampling)
	NODE_SOCKET_API(int, adaptive_min_samples)
	diff --git a/intern/cycles/scene/light.cpp b/intern/cycles/scene/light.cpp
	index ea1f45793fa..b4c86c39a0e 100644
	--- a/intern/cycles/scene/light.cpp
	+++ b/intern/cycles/scene/light.cpp
	@@ -80,6 +80,35 @@ static void shade_background_pixels(Device *device,
	});
	}

	+static float average_background_energy(Device *device,
	+ DeviceScene *dscene,
	+ Progress &progress,
	+ Scene *scene,
	+ Light *light)
	+{
	+ if (light->get_light_type() != LIGHT_BACKGROUND) {
	+ assert(false);
	+ }
	+
	+ /* get the resolution from the light's size (we stuff it in there) */
	+ int2 res = make_int2(light->get_map_resolution(), light->get_map_resolution() / 2);
	+ /* If it's still unknown, just use the default. */
	+ if (res.x == 0 \|\| res.y == 0) {
	+ res = make_int2(1024, 512);
	+ VLOG_INFO << "Setting World MIS resolution to default\n";
	+ }
	+
	+ vector<float3> pixels;
	+ shade_background_pixels(device, dscene, res.x, res.y, pixels, progress);
	+
	+ float total_energy = 0.0f;
	+ for (int i = 0; i < pixels.size(); i++) {
	+ total_energy += scene->shader_manager->linear_rgb_to_gray(pixels[i]);
	+ }
	+
	+ return total_energy / pixels.size();
	+}
	+
	/* Light */

	NODE_DEFINE(Light)
	@@ -263,7 +292,7 @@ bool LightManager::object_usable_as_light(Object *object)
	return false;
	}

	-void LightManager::device_update_distribution(Device *,
	+void LightManager::device_update_distribution(Device *device,
	DeviceScene *dscene,
	Scene *scene,
	Progress &progress)
	@@ -274,30 +303,70 @@ void LightManager::device_update_distribution(Device *,
	size_t num_lights = 0;
	size_t num_portals = 0;
	size_t num_background_lights = 0;
	+ size_t num_distant_lights = 0;
	size_t num_triangles = 0;
	+ size_t total_triangles = 0;

	bool background_mis = false;

	+ /* We want to add both lights and emissive triangles to this vector for light tree construction. */
	+ bool light_tree_enabled = scene->integrator->get_use_light_tree();
	+ vector<LightTreePrimitive> light_prims;
	+ vector<LightTreePrimitive> distant_lights;
	+ vector<uint> object_lookup_offsets(scene->objects.size());
	+
	+ /* When we keep track of the light index, only contributing lights will be added to the device.
	+ * Therefore, we want to keep track of the light's index on the device.
	+ * However, we also need the light's index in the scene when we're constructing the tree. */
	+ int device_light_index = 0;
	+ int scene_light_index = 0;
	foreach (Light *light, scene->lights) {
	if (light->is_enabled) {
	+ if (light_tree_enabled) {
	+ LightTreePrimitive light_prim;
	+ light_prim.prim_id = ~device_light_index; /* -prim_id - 1 is a light source index. */
	+ light_prim.lamp_id = scene_light_index;
	+
	+ /* Distant lights get added to a separate vector. */
	+ if (light->light_type == LIGHT_DISTANT \|\| light->light_type == LIGHT_BACKGROUND) {
	+ distant_lights.push_back(light_prim);
	+ num_distant_lights++;
	+ }
	+ else {
	+ light_prims.push_back(light_prim);
	+ }
	+
	+ device_light_index++;
	+ }
	+
	num_lights++;
	}
	if (light->is_portal) {
	num_portals++;
	}
	+
	+ scene_light_index++;
	}

	+ /* Similarly, we also want to keep track of the index of triangles that are emissive. */
	+ int object_id = 0;
	foreach (Object *object, scene->objects) {
	if (progress.get_cancel())
	return;

	if (!object_usable_as_light(object)) {
	+ object_id++;
	continue;
	}

	- /* Count triangles. */
	+ if (light_tree_enabled) {
	+ object_lookup_offsets[object_id] = total_triangles;
	+ }
	+
	+ /* Count emissive triangles. */
	Mesh mesh = static_cast<Mesh >(object->get_geometry());
	size_t mesh_num_triangles = mesh->num_triangles();
	+
	for (size_t i = 0; i < mesh_num_triangles; i++) {
	int shader_index = mesh->get_shader()[i];
	Shader *shader = (shader_index < mesh->get_used_shaders().size()) ?
	@@ -305,14 +374,204 @@ void LightManager::device_update_distribution(Device *,
	scene->default_surface;

	if (shader->get_use_mis() && shader->has_surface_emission) {
	+ /* to-do: for the light tree implementation, we eventually want to include emissive
	+ * triangles. Right now, point lights are the main concern. */
	+ if (light_tree_enabled) {
	+ LightTreePrimitive light_prim;
	+ light_prim.prim_id = i;
	+ light_prim.object_id = object_id;
	+ light_prims.push_back(light_prim);
	+ }
	+
	num_triangles++;
	}
	}
	+
	+ total_triangles += mesh_num_triangles;
	+ object_id++;
	}

	size_t num_distribution = num_triangles + num_lights;
	VLOG_INFO << "Total " << num_distribution << " of light distribution primitives.";

	+ if (light_tree_enabled && num_distribution > 0) {
	+ /* For now, we'll start with a smaller number of max lights in a node.
	+ * More benchmarking is needed to determine what number works best. */
	+ LightTree light_tree(light_prims, scene, 8);
	+ light_prims = light_tree.get_prims();
	+
	+ /* We want to create separate arrays corresponding to triangles and lights,
	+ * which will be used to index back into the light tree for PDF calculations. */
	+ uint *light_array = dscene->light_to_tree.alloc(num_lights);
	+ uint *object_offsets = dscene->object_lookup_offset.alloc(object_lookup_offsets.size());
	+ uint *triangle_array = dscene->triangle_to_tree.alloc(total_triangles);
	+
	+ for (int i = 0; i < object_lookup_offsets.size(); i++) {
	+ object_offsets[i] = object_lookup_offsets[i];
	+ }
	+
	+ /* First initialize the light tree's nodes. */
	+ const vector<PackedLightTreeNode> &linearized_bvh = light_tree.get_nodes();
	+ KernelLightTreeNode *light_tree_nodes = dscene->light_tree_nodes.alloc(linearized_bvh.size());
	+ KernelLightTreeEmitter *light_tree_emitters = dscene->light_tree_emitters.alloc(light_prims.size());
	+ float max_light_tree_energy = 0.0f;
	+ for (int index = 0; index < linearized_bvh.size(); index++) {
	+ const PackedLightTreeNode &node = linearized_bvh[index];
	+
	+ light_tree_nodes[index].energy = node.energy;
	+
	+ for (int i = 0; i < 3; i++) {
	+ light_tree_nodes[index].bounding_box_min[i] = node.bbox.min[i];
	+ light_tree_nodes[index].bounding_box_max[i] = node.bbox.max[i];
	+ light_tree_nodes[index].bounding_cone_axis[i] = node.bcone.axis[i];
	+ }
	+ light_tree_nodes[index].theta_o = node.bcone.theta_o;
	+ light_tree_nodes[index].theta_e = node.bcone.theta_e;
	+
	+ light_tree_nodes[index].bit_trail = node.bit_trail;
	+
	+ /* Here we need to make a distinction between interior and leaf nodes. */
	+ if (node.is_leaf_node) {
	+ light_tree_nodes[index].num_prims = node.num_lights;
	+ light_tree_nodes[index].child_index = -node.first_prim_index;
	+
	+ for (int i = 0; i < node.num_lights; i++) {
	+ int emitter_index = i + node.first_prim_index;
	+ LightTreePrimitive &prim = light_prims[emitter_index];
	+ BoundBox bbox = prim.calculate_bbox(scene);
	+ OrientationBounds bcone = prim.calculate_bcone(scene);
	+ float energy = prim.calculate_energy(scene);
	+
	+ light_tree_emitters[emitter_index].energy = energy;
	+ if (energy > max_light_tree_energy) {
	+ max_light_tree_energy = energy;
	+ }
	+
	+ for (int i = 0; i < 3; i++) {
	+ light_tree_emitters[emitter_index].bounding_box_min[i] = bbox.min[i];
	+ light_tree_emitters[emitter_index].bounding_box_max[i] = bbox.max[i];
	+ light_tree_emitters[emitter_index].bounding_cone_axis[i] = bcone.axis[i];
	+ }
	+ light_tree_emitters[emitter_index].theta_o = bcone.theta_o;
	+ light_tree_emitters[emitter_index].theta_e = bcone.theta_e;
	+
	+ if (prim.prim_id >= 0) {
	+ light_tree_emitters[emitter_index].mesh_light.object_id = prim.object_id;
	+
	+ int shader_flag = 0;
	+ Object *object = scene->objects[prim.object_id];
	+ Mesh mesh = static_cast<Mesh >(object->get_geometry());
	+ if (!(object->get_visibility() & PATH_RAY_CAMERA)) {
	+ shader_flag \|= SHADER_EXCLUDE_CAMERA;
	+ }
	+ if (!(object->get_visibility() & PATH_RAY_DIFFUSE)) {
	+ shader_flag \|= SHADER_EXCLUDE_DIFFUSE;
	+ }
	+ if (!(object->get_visibility() & PATH_RAY_GLOSSY)) {
	+ shader_flag \|= SHADER_EXCLUDE_GLOSSY;
	+ }
	+ if (!(object->get_visibility() & PATH_RAY_TRANSMIT)) {
	+ shader_flag \|= SHADER_EXCLUDE_TRANSMIT;
	+ }
	+ if (!(object->get_visibility() & PATH_RAY_VOLUME_SCATTER)) {
	+ shader_flag \|= SHADER_EXCLUDE_SCATTER;
	+ }
	+ if (!(object->get_is_shadow_catcher())) {
	+ shader_flag \|= SHADER_EXCLUDE_SHADOW_CATCHER;
	+ }
	+
	+ light_tree_emitters[emitter_index].prim_id = prim.prim_id + mesh->prim_offset;
	+ light_tree_emitters[emitter_index].mesh_light.shader_flag = shader_flag;
	+ triangle_array[prim.prim_id + object_lookup_offsets[prim.object_id]] = emitter_index;
	+ }
	+ else {
	+ Light *lamp = scene->lights[prim.lamp_id];
	+ light_tree_emitters[emitter_index].prim_id = prim.prim_id;
	+ light_tree_emitters[emitter_index].lamp.size = lamp->size;
	+ light_tree_emitters[emitter_index].lamp.pad = 1.0f;
	+ light_array[~prim.prim_id] = emitter_index;
	+ }
	+
	+ light_tree_emitters[emitter_index].parent_index = index;
	+ }
	+ }
	+ else {
	+ light_tree_nodes[index].energy_variance = node.energy_variance;
	+ light_tree_nodes[index].child_index = node.second_child_index;
	+ }
	+ }
	+
	+ /* We set the parent node's energy to be the average energy,
	+ * which is used for deciding between the tree and distant lights. */
	+ if (max_light_tree_energy > 0.0f) {
	+ light_tree_nodes[0].energy = max_light_tree_energy;
	+ }
	+
	+ /* We also add distant lights to a separate group. */
	+ KernelLightTreeDistantEmitter *light_tree_distant_group =
	+ dscene->light_tree_distant_group.alloc(num_distant_lights + 1);
	+
	+ /* We use OrientationBounds here to */
	+ OrientationBounds distant_light_bounds = OrientationBounds::empty;
	+ float max_distant_light_energy = 0.0f;
	+ for (int index = 0; index < num_distant_lights; index++) {
	+ LightTreePrimitive prim = distant_lights[index];
	+ Light *light = scene->lights[prim.lamp_id];
	+ OrientationBounds light_bounds;
	+
	+ /* Lights in this group are either a background or distant light. */
	+ light_tree_distant_group[index].prim_id = ~prim.prim_id;
	+
	+ float energy = 0.0f;
	+ if (light->light_type == LIGHT_BACKGROUND) {
	+ energy = average_background_energy(device, dscene, progress, scene, light);
	+
	+ /* We can set an arbitrary direction for the background light. */
	+ light_bounds.axis[0] = 0.0f;
	+ light_bounds.axis[1] = 0.0f;
	+ light_bounds.axis[2] = 1.0f;
	+
	+ /* to-do: this may depend on portal lights as well. */
	+ light_bounds.theta_o = M_PI_F;
	+ }
	+ else {
	+ energy = prim.calculate_energy(scene);
	+ for (int i = 0; i < 3; i++) {
	+ light_bounds.axis[i] = -light->dir[i];
	+ }
	+ light_bounds.theta_o = tanf(light->angle * 0.5f);
	+ }
	+
	+ distant_light_bounds = merge(distant_light_bounds, light_bounds);
	+ for (int i = 0; i < 3; i++) {
	+ light_tree_distant_group[index].direction[i] = light_bounds.axis[i];
	+ }
	+ light_tree_distant_group[index].bounding_radius = light_bounds.theta_o;
	+
	+ light_tree_distant_group[index].energy = energy;
	+ light_array[~prim.prim_id] = index;
	+
	+ if (energy > max_distant_light_energy) {
	+ max_distant_light_energy = energy;
	+ }
	+ }
	+
	+ /* The net OrientationBounds contain bounding information about all the distant lights. */
	+ light_tree_distant_group[num_distant_lights].prim_id = -1;
	+ light_tree_distant_group[num_distant_lights].energy = max_distant_light_energy;
	+ for (int i = 0; i < 3; i++) {
	+ light_tree_distant_group[num_distant_lights].direction[i] = distant_light_bounds.axis[i];
	+ }
	+ light_tree_distant_group[num_distant_lights].bounding_radius = distant_light_bounds.theta_o;
	+
	+ dscene->light_tree_nodes.copy_to_device();
	+ dscene->light_tree_emitters.copy_to_device();
	+ dscene->light_tree_distant_group.copy_to_device();
	+ dscene->light_to_tree.copy_to_device();
	+ dscene->object_lookup_offset.copy_to_device();
	+ dscene->triangle_to_tree.copy_to_device();
	+ }
	+
	/* emission area */
	KernelLightDistribution *distribution = dscene->light_distribution.alloc(num_distribution + 1);
	float totarea = 0.0f;
	@@ -456,18 +715,29 @@ void LightManager::device_update_distribution(Device *,
	kintegrator->pdf_lights = 0.0f;

	/* sample one, with 0.5 probability of light or triangle */
	+ /* to-do: this pdf is probably going to need adjustment if a light tree is used. */
	kintegrator->num_all_lights = num_lights;
	-
	- if (trianglearea > 0.0f) {
	- kintegrator->pdf_triangles = 1.0f / trianglearea;
	- if (num_lights)
	- kintegrator->pdf_triangles *= 0.5f;
	+ kintegrator->num_distant_lights = num_distant_lights;
	+
	+ /* pdf_lights is used when sampling lights, and assumes that
	+ * the light has been sampled through the light distribution.
	+ * Therefore, we override it for now and adjust the pdf manually in the light tree.*/
	+ if (light_tree_enabled) {
	+ kintegrator->pdf_triangles = 1.0f;
	+ kintegrator->pdf_lights = 1.0f;
	}
	+ else {
	+ if (trianglearea > 0.0f) {
	+ kintegrator->pdf_triangles = 1.0f / trianglearea;
	+ if (num_lights)
	+ kintegrator->pdf_triangles *= 0.5f;
	+ }

	- if (num_lights) {
	- kintegrator->pdf_lights = 1.0f / num_lights;
	- if (trianglearea > 0.0f)
	- kintegrator->pdf_lights *= 0.5f;
	+ if (num_lights) {
	+ kintegrator->pdf_lights = 1.0f / num_lights;
	+ if (trianglearea > 0.0f)
	+ kintegrator->pdf_lights *= 0.5f;
	+ }
	}

	kintegrator->use_lamp_mis = use_lamp_mis;
	@@ -501,6 +771,14 @@ void LightManager::device_update_distribution(Device *,
	kbackground->map_weight = background_mis ? 1.0f : 0.0f;
	}
	else {
	+ if (light_tree_enabled) {
	+ dscene->light_tree_nodes.free();
	+ dscene->light_tree_emitters.free();
	+ dscene->light_tree_distant_group.free();
	+ dscene->light_to_tree.free();
	+ dscene->object_lookup_offset.free();
	+ dscene->triangle_to_tree.free();
	+ }
	dscene->light_distribution.free();

	kintegrator->num_distribution = 0;
	@@ -1010,6 +1288,13 @@ void LightManager::device_update(Device *device,

	void LightManager::device_free(Device , DeviceScene dscene, const bool free_background)
	{
	+ /* to-do: check if the light tree member variables need to be wrapped in a conditional too*/
	+ dscene->light_tree_nodes.free();
	+ dscene->light_tree_emitters.free();
	+ dscene->light_tree_distant_group.free();
	+ dscene->light_to_tree.free();
	+ dscene->triangle_to_tree.free();
	+
	dscene->light_distribution.free();
	dscene->lights.free();
	if (free_background) {
	diff --git a/intern/cycles/scene/light.h b/intern/cycles/scene/light.h
	index 5b852f210fc..4db4de10ec6 100644
	--- a/intern/cycles/scene/light.h
	+++ b/intern/cycles/scene/light.h
	@@ -10,6 +10,7 @@

	/* included as Light::set_shader defined through NODE_SOCKET_API does not select
	* the right Node::set overload as it does not know that Shader is a Node */
	+#include "scene/light_tree.h"
	#include "scene/shader.h"

	#include "util/ies.h"
	diff --git a/intern/cycles/scene/light_tree.cpp b/intern/cycles/scene/light_tree.cpp
	new file mode 100644
	index 00000000000..69f626d879f
	--- /dev/null
	+++ b/intern/cycles/scene/light_tree.cpp
	@@ -0,0 +1,515 @@
	+/* SPDX-License-Identifier: Apache-2.0
	+ * Copyright 2011-2022 Blender Foundation */
	+
	+#include "scene/mesh.h"
	+#include "scene/object.h"
	+#include "scene/light_tree.h"
	+
	+CCL_NAMESPACE_BEGIN
	+
	+float OrientationBounds::calculate_measure() const
	+{
	+ float theta_w = fminf(M_PI_F, theta_o + theta_e);
	+ float cos_theta_o = cosf(theta_o);
	+ float sin_theta_o = sinf(theta_o);
	+
	+ return M_2PI_F * (1 - cos_theta_o) +
	+ M_PI_2_F * (2 * theta_w * sin_theta_o - cosf(theta_o - 2 * theta_w) -
	+ 2 * theta_o * sin_theta_o + cos_theta_o);
	+}
	+
	+OrientationBounds merge(const OrientationBounds& cone_a,
	+ const OrientationBounds& cone_b)
	+{
	+ if (is_zero(cone_a.axis)) {
	+ return cone_b;
	+ }
	+ else if (is_zero(cone_b.axis)) {
	+ return cone_a;
	+ }
	+
	+ /* Set cone a to always have the greater theta_o. */
	+ const OrientationBounds *a = &cone_a;
	+ const OrientationBounds *b = &cone_b;
	+ if (cone_b.theta_o > cone_a.theta_o) {
	+ a = &cone_b;
	+ b = &cone_a;
	+ }
	+
	+ float theta_d = safe_acosf(dot(a->axis, b->axis));
	+ float theta_e = fmaxf(a->theta_e, b->theta_e);
	+
	+ /* Return axis and theta_o of a if it already contains b. */
	+ /* This should also be called when b is empty. */
	+ if (a->theta_o >= fminf(M_PI_F, theta_d + b->theta_o)) {
	+ return OrientationBounds({a->axis, a->theta_o, theta_e});
	+ }
	+ else {
	+ /* Compute new theta_o that contains both a and b. */
	+ float theta_o = (theta_d + a->theta_o + b->theta_o) * 0.5f;
	+
	+ if (theta_o >= M_PI_F) {
	+ return OrientationBounds({a->axis, M_PI_F, theta_e});
	+ }
	+
	+ /* Rotate new axis to be between a and b. */
	+ float theta_r = theta_o - a->theta_o;
	+ float3 new_axis = rotate_around_axis(a->axis, cross(a->axis, b->axis), theta_r);
	+ new_axis = normalize(new_axis);
	+
	+ return OrientationBounds({new_axis, theta_o, theta_e});
	+ }
	+}
	+
	+BoundBox LightTreePrimitive::calculate_bbox(Scene *scene) const
	+{
	+ BoundBox bbox = BoundBox::empty;
	+
	+ if (prim_id >= 0) {
	+ Object *object = scene->objects[object_id];
	+ Mesh mesh = static_cast<Mesh>(object->get_geometry());
	+ Mesh::Triangle triangle = mesh->get_triangle(prim_id);
	+
	+ float3 p[3] = {mesh->get_verts()[triangle.v[0]],
	+ mesh->get_verts()[triangle.v[1]],
	+ mesh->get_verts()[triangle.v[2]]};
	+
	+ /* instanced mesh lights have not applied their transform at this point.
	+ * in this case, these points have to be transformed to get the proper
	+ * spatial bound. */
	+ if (!mesh->transform_applied) {
	+ const Transform &tfm = object->get_tfm();
	+ for (int i = 0; i < 3; i++) {
	+ p[i] = transform_point(&tfm, p[i]);
	+ }
	+ }
	+
	+ for (int i = 0; i < 3; i++) {
	+ bbox.grow(p[i]);
	+ }
	+ }
	+ else {
	+ Light *lamp = scene->lights[lamp_id];
	+ LightType type = lamp->get_light_type();
	+ const float3 center = lamp->get_co();
	+ const float size = lamp->get_size();
	+
	+ if (type == LIGHT_POINT \|\| type == LIGHT_SPOT) {
	+ /* Point and spot lights can emit light from any point within its radius. */
	+ const float3 radius = make_float3(size);
	+ bbox.grow(center - radius);
	+ bbox.grow(center + radius);
	+ }
	+ else if (type == LIGHT_AREA) {
	+ /* For an area light, sizeu and sizev determine the 2 dimensions of the area light,
	+ * while axisu and axisv determine the orientation of the 2 dimensions.
	+ * We want to add all 4 corners to our bounding box. */
	+ const float3 half_extentu = 0.5 * lamp->get_sizeu() * lamp->get_axisu() * size;
	+ const float3 half_extentv = 0.5 * lamp->get_sizev() * lamp->get_axisv() * size;
	+
	+ bbox.grow(center + half_extentu + half_extentv);
	+ bbox.grow(center + half_extentu - half_extentv);
	+ bbox.grow(center - half_extentu + half_extentv);
	+ bbox.grow(center - half_extentu - half_extentv);
	+ }
	+ else {
	+ /* This should never be reached during construction. */
	+ assert(false);
	+ }
	+ }
	+
	+ return bbox;
	+}
	+
	+OrientationBounds LightTreePrimitive::calculate_bcone(Scene *scene) const
	+{
	+ OrientationBounds bcone = OrientationBounds::empty;
	+
	+ if (prim_id >= 0) {
	+ Object *object = scene->objects[object_id];
	+ Mesh mesh = static_cast<Mesh >(object->get_geometry());
	+ Mesh::Triangle triangle = mesh->get_triangle(prim_id);
	+
	+ float3 p[3] = {mesh->get_verts()[triangle.v[0]],
	+ mesh->get_verts()[triangle.v[1]],
	+ mesh->get_verts()[triangle.v[2]]};
	+
	+ /* instanced mesh lights have not applied their transform at this point.
	+ * in this case, these points have to be transformed to get the proper
	+ * spatial bound. */
	+ if (!mesh->transform_applied) {
	+ const Transform &tfm = object->get_tfm();
	+ for (int i = 0; i < 3; i++) {
	+ p[i] = transform_point(&tfm, p[i]);
	+ }
	+ }
	+
	+ float3 normal = cross(p[1] - p[0], p[2] - p[0]);
	+ const float normlen = len(normal);
	+ if (normlen == 0.0f) {
	+ normal = make_float3(1.0f, 0.0f, 0.0f);
	+ }
	+ normal = normal / normlen;
	+
	+ bcone.axis = normal;
	+
	+ /* to-do: is there a better way to handle this case where both sides of the triangle are visible?
	+ * Right now, we assume that the normal axis is within pi radians of the triangle normal. */
	+ bcone.theta_o = M_PI_F;
	+ bcone.theta_e = M_PI_2_F;
	+ }
	+ else {
	+ Light *lamp = scene->lights[lamp_id];
	+ LightType type = lamp->get_light_type();
	+
	+ bcone.axis = normalize(lamp->get_dir());
	+
	+ if (type == LIGHT_POINT) {
	+ bcone.theta_o = M_PI_F;
	+ bcone.theta_e = M_PI_2_F;
	+ }
	+ else if (type == LIGHT_SPOT) {
	+ bcone.theta_o = 0;
	+ bcone.theta_e = lamp->get_spot_angle() * 0.5f;
	+ }
	+ else if (type == LIGHT_AREA) {
	+ bcone.theta_o = 0;
	+ bcone.theta_e = lamp->get_spread() * 0.5f;
	+ }
	+ else {
	+ /* This should never be reached during construction. */
	+ assert(false);
	+ }
	+ }
	+
	+ return bcone;
	+}
	+
	+float LightTreePrimitive::calculate_energy(Scene *scene) const
	+{
	+ float3 strength = make_float3(0.0f);
	+
	+ if (prim_id >= 0) {
	+ Object *object = scene->objects[object_id];
	+ Mesh mesh = static_cast<Mesh >(object->get_geometry());
	+ Mesh::Triangle triangle = mesh->get_triangle(prim_id);
	+ Shader shader = static_cast<Shader>(mesh->get_used_shaders()[mesh->get_shader()[prim_id]]);
	+
	+ /* to-do: need a better way to handle this when textures are used. */
	+ if (!shader->is_constant_emission(&strength)) {
	+ strength = make_float3(1.0f);
	+ }
	+
	+ float3 p[3] = {mesh->get_verts()[triangle.v[0]],
	+ mesh->get_verts()[triangle.v[1]],
	+ mesh->get_verts()[triangle.v[2]]};
	+
	+ /* instanced mesh lights have not applied their transform at this point.
	+ * in this case, these points have to be transformed to get the proper
	+ * spatial bound. */
	+ if (!mesh->transform_applied) {
	+ const Transform &tfm = object->get_tfm();
	+ for (int i = 0; i < 3; i++) {
	+ p[i] = transform_point(&tfm, p[i]);
	+ }
	+ }
	+
	+ float area = triangle_area(p[0], p[1], p[2]);
	+ strength *= area;
	+ }
	+ else {
	+ Light *lamp = scene->lights[lamp_id];
	+ strength = lamp->get_strength();
	+ }
	+
	+ return fabsf(scene->shader_manager->linear_rgb_to_gray(strength));
	+}
	+
	+void LightTreeBuildNode::init_leaf(
	+ uint offset, uint n, const BoundBox &b, const OrientationBounds &c, float e, float e_var, uint bits)
	+{
	+ bbox = b;
	+ bcone = c;
	+ energy = e;
	+ energy_variance = e_var;
	+ first_prim_index = offset;
	+ num_lights = n;
	+
	+ children[0] = children[1] = nullptr;
	+ bit_trail = bits;
	+ is_leaf = true;
	+}
	+
	+void LightTreeBuildNode::init_interior(LightTreeBuildNode c0, LightTreeBuildNode c1)
	+{
	+ bbox = merge(c0->bbox, c1->bbox);
	+ bcone = merge(c0->bcone, c1->bcone);
	+ energy = c0->energy + c1->energy;
	+ energy_variance = c0->energy_variance + c1->energy_variance;
	+ first_prim_index = 0;
	+ num_lights = 0;
	+
	+ children[0] = c0;
	+ children[1] = c1;
	+ is_leaf = false;
	+}
	+
	+LightTree::LightTree(const vector<LightTreePrimitive> &prims, Scene *scene, uint max_lights_in_leaf)
	+{
	+ if (prims.size() == 0) {
	+ return;
	+ }
	+
	+ prims_ = prims;
	+ scene_ = scene;
	+ max_lights_in_leaf_ = max_lights_in_leaf;
	+
	+ vector<LightTreePrimitiveInfo> build_data;
	+ for (int i = 0; i < prims.size(); i++) {
	+ LightTreePrimitiveInfo prim_info;
	+ prim_info.bbox = prims[i].calculate_bbox(scene);
	+ prim_info.bcone = prims[i].calculate_bcone(scene);
	+ prim_info.energy = prims[i].calculate_energy(scene);
	+ prim_info.centroid = prim_info.bbox.center();
	+ prim_info.prim_num = i;
	+ build_data.push_back(prim_info);
	+ }
	+
	+ int total_nodes = 0;
	+ vector<LightTreePrimitive> ordered_prims;
	+ LightTreeBuildNode *root = recursive_build(build_data, 0, prims.size(), total_nodes, ordered_prims, 0, 0);
	+ prims_ = ordered_prims;
	+
	+ int offset = 0;
	+ nodes_.resize(total_nodes);
	+ flatten_tree(root, offset, -1);
	+}
	+
	+const vector<LightTreePrimitive> &LightTree::get_prims() const
	+{
	+ return prims_;
	+}
	+
	+const vector<PackedLightTreeNode> &LightTree::get_nodes() const
	+{
	+ return nodes_;
	+}
	+
	+LightTreeBuildNode *LightTree::recursive_build(vector<LightTreePrimitiveInfo> &primitive_info,
	+ int start,
	+ int end,
	+ int &total_nodes,
	+ vector<LightTreePrimitive> &ordered_prims,
	+ uint bit_trail,
	+ int depth)
	+{
	+ LightTreeBuildNode *node = new LightTreeBuildNode();
	+ total_nodes++;
	+ BoundBox node_bbox = BoundBox::empty;
	+ OrientationBounds node_bcone = OrientationBounds::empty;
	+ BoundBox centroid_bounds = BoundBox::empty;
	+ float energy_total = 0.0;
	+ float energy_squared_total = 0.0;
	+ int num_prims = end - start;
	+
	+ for (int i = start; i < end; i++) {
	+ const LightTreePrimitiveInfo &prim = primitive_info.at(i);
	+ node_bbox.grow(prim.bbox);
	+ node_bcone = merge(node_bcone, prim.bcone);
	+ centroid_bounds.grow(prim.centroid);
	+
	+ energy_total += prim.energy;
	+ energy_squared_total += prim.energy * prim.energy;
	+ }
	+
	+ /* Var(X) = E[X^2] - E[X]^2 */
	+ float energy_variance = (energy_squared_total / num_prims) - (energy_total / num_prims) * (energy_total / num_prims);
	+ if (num_prims == 1 \|\| len(centroid_bounds.size()) == 0.0f) {
	+ int first_prim_offset = ordered_prims.size();
	+ for (int i = start; i < end; i++) {
	+ int prim_num = primitive_info[i].prim_num;
	+ ordered_prims.push_back(prims_[prim_num]);
	+ }
	+ node->init_leaf(first_prim_offset, num_prims, node_bbox, node_bcone, energy_total, energy_variance, bit_trail);
	+ }
	+ else {
	+ /* Find the best place to split the primitives into 2 nodes.
	+ * If the best split cost is no better than making a leaf node, make a leaf instead.*/
	+ float min_cost;
	+ int min_dim, min_bucket;
	+ split_saoh(centroid_bounds,
	+ primitive_info,
	+ start,
	+ end,
	+ node_bbox,
	+ node_bcone,
	+ min_cost,
	+ min_dim,
	+ min_bucket);
	+ if (num_prims > max_lights_in_leaf_ \|\| min_cost < energy_total) {
	+ /* Partition the primitives between start and end into the appropriate split,
	+ * based on the minimum dimension and minimum bucket returned from split_saoh.
	+ * This is an O(n) algorithm where we iterate from the left and right side,
	+ * and swaps the appropriate left and right elements until complete. */
	+ int left = start, right = end - 1;
	+ float bounding_dimension = (min_bucket + 1) * (centroid_bounds.size()[min_dim] /
	+ LightTreeBucketInfo::num_buckets) +
	+ centroid_bounds.min[min_dim];
	+ while (left < right) {
	+ while (primitive_info[left].centroid[min_dim] <= bounding_dimension && left < end) {
	+ left++;
	+ }
	+
	+ while (primitive_info[right].centroid[min_dim] > bounding_dimension && right >= start) {
	+ right--;
	+ }
	+
	+ if (left < right) {
	+ LightTreePrimitiveInfo temp = primitive_info[left];
	+ primitive_info[left] = primitive_info[right];
	+ primitive_info[right] = temp;
	+ }
	+ }
	+
	+ /* At this point, we should expect right to be just past left,
	+ * where left points to the first element that belongs to the right node. */
	+ LightTreeBuildNode *left_node = recursive_build(
	+ primitive_info, start, left, total_nodes, ordered_prims, bit_trail, depth + 1);
	+ LightTreeBuildNode *right_node = recursive_build(
	+ primitive_info, left, end, total_nodes, ordered_prims, bit_trail \| (1u << depth), depth + 1);
	+ node->init_interior(left_node, right_node);
	+ }
	+ else {
	+ int first_prim_offset = ordered_prims.size();
	+ for (int i = start; i < end; i++) {
	+ int prim_num = primitive_info[i].prim_num;
	+ ordered_prims.push_back(prims_[prim_num]);
	+ }
	+ node->init_leaf(first_prim_offset, num_prims, node_bbox, node_bcone, energy_total, energy_variance, bit_trail);
	+ }
	+ }
	+
	+ return node;
	+}
	+
	+void LightTree::split_saoh(const BoundBox &centroid_bbox,
	+ const vector<LightTreePrimitiveInfo> &primitive_info,
	+ int start,
	+ int end,
	+ const BoundBox &bbox,
	+ const OrientationBounds &bcone,
	+ float& min_cost,
	+ int& min_dim,
	+ int& min_bucket)
	+{
	+ /* Even though this factor is used for every bucket, we use it to compare
	+ * the min_cost and total_energy (when deciding between creating a leaf or interior node. */
	+ const float inv_total_cost = 1 / (bbox.area() * bcone.calculate_measure());
	+ const float3 extent = centroid_bbox.size();
	+ const float max_extent = max4(extent.x, extent.y, extent.z, 0.0f);
	+
	+ /* Check each dimension to find the minimum splitting cost. */
	+ min_cost = FLT_MAX;
	+ for (int dim = 0; dim < 3; dim++) {
	+ /* If the centroid bounding box is 0 along a given dimension, skip it. */
	+ if (centroid_bbox.size()[dim] == 0.0f) {
	+ continue;
	+ }
	+
	+ const float inv_extent = 1 / (centroid_bbox.size()[dim]);
	+
	+ /* Fill in buckets with primitives. */
	+ vector<LightTreeBucketInfo> buckets(LightTreeBucketInfo::num_buckets);
	+ for (int i = start; i < end; i++) {
	+ const LightTreePrimitiveInfo &primitive = primitive_info[i];
	+
	+ /* Place primitive into the appropriate bucket,
	+ * where the centroid box is split into equal partitions. */
	+ int bucket_idx = LightTreeBucketInfo::num_buckets *
	+ (primitive.centroid[dim] - centroid_bbox.min[dim]) * inv_extent;
	+ if (bucket_idx == LightTreeBucketInfo::num_buckets)
	+ {
	+ bucket_idx = LightTreeBucketInfo::num_buckets - 1;
	+ }
	+
	+ buckets[bucket_idx].count++;
	+ buckets[bucket_idx].energy += primitive.energy;
	+ buckets[bucket_idx].bbox.grow(primitive.bbox);
	+ buckets[bucket_idx].bcone = merge(buckets[bucket_idx].bcone, primitive.bcone);
	+ }
	+
	+ /* Calculate the cost of splitting at each point between partitions. */
	+ vector<float> bucket_costs(LightTreeBucketInfo::num_buckets - 1);
	+ float energy_L, energy_R;
	+ BoundBox bbox_L, bbox_R;
	+ OrientationBounds bcone_L, bcone_R;
	+ for (int split = 0; split < LightTreeBucketInfo::num_buckets - 1; split++) {
	+ energy_L = 0;
	+ energy_R = 0;
	+ bbox_L = BoundBox::empty;
	+ bbox_R = BoundBox::empty;
	+ bcone_L = OrientationBounds::empty;
	+ bcone_R = OrientationBounds::empty;
	+
	+ for (int left = 0; left <= split; left++) {
	+ if (buckets[left].bbox.valid()) {
	+ energy_L += buckets[left].energy;
	+ bbox_L.grow(buckets[left].bbox);
	+ bcone_L = merge(bcone_L, buckets[left].bcone);
	+ }
	+ }
	+
	+ for (int right = split + 1; right < LightTreeBucketInfo::num_buckets; right++) {
	+ if (buckets[right].bbox.valid()) {
	+ energy_R += buckets[right].energy;
	+ bbox_R.grow(buckets[right].bbox);
	+ bcone_R = merge(bcone_R, buckets[right].bcone);
	+ }
	+ }
	+
	+ /* Calculate the cost of splitting using the heuristic as described in the paper. */
	+ float left = (bbox_L.valid()) ? energy_L * bbox_L.area() * bcone_L.calculate_measure() : 0.0f;
	+ float right = (bbox_R.valid()) ? energy_R * bbox_R.area() * bcone_R.calculate_measure() : 0.0f;
	+ float regularization = max_extent * inv_extent;
	+ bucket_costs[split] = regularization * (left + right) * inv_total_cost;
	+
	+ if (bucket_costs[split] < min_cost) {
	+ min_cost = bucket_costs[split];
	+ min_dim = dim;
	+ min_bucket = split;
	+ }
	+ }
	+ }
	+}
	+
	+int LightTree::flatten_tree(const LightTreeBuildNode *node, int &offset, int parent)
	+{
	+ PackedLightTreeNode *current_node = &nodes_[offset];
	+ current_node->bbox = node->bbox;
	+ current_node->bcone = node->bcone;
	+ current_node->energy = node->energy;
	+ current_node->energy_variance = node->energy_variance;
	+ int current_index = offset;
	+ offset++;
	+
	+ /* If current node contains lights, then it is a leaf node.
	+ * Otherwise, create interior node and children recursively. */
	+ if (node->num_lights > 0) {
	+ current_node->first_prim_index = node->first_prim_index;
	+ current_node->num_lights = node->num_lights;
	+ current_node->bit_trail = node->bit_trail;
	+ current_node->is_leaf_node = true;
	+ }
	+ else {
	+ current_node->num_lights = 0;
	+ current_node->is_leaf_node = false;
	+
	+ /* The first child is located directly to the right of the parent. */
	+ flatten_tree(node->children[0], offset, current_index);
	+ current_node->second_child_index = flatten_tree(node->children[1], offset, current_index);
	+ }
	+
	+ return current_index;
	+}
	+
	+CCL_NAMESPACE_END
	\ No newline at end of file
	diff --git a/intern/cycles/scene/light_tree.h b/intern/cycles/scene/light_tree.h
	new file mode 100644
	index 00000000000..4417d0efd9a
	--- /dev/null
	+++ b/intern/cycles/scene/light_tree.h
	@@ -0,0 +1,163 @@
	+/* SPDX-License-Identifier: Apache-2.0
	+ * Copyright 2011-2022 Blender Foundation */
	+
	+#ifndef __LIGHT_TREE_H__
	+#define __LIGHT_TREE_H__
	+
	+#include "scene/light.h"
	+#include "scene/scene.h"
	+
	+#include "util/boundbox.h"
	+#include "util/types.h"
	+#include "util/vector.h"
	+
	+CCL_NAMESPACE_BEGIN
	+
	+/* Orientation Bounds
	+ *
	+ * Bounds the normal axis of the lights,
	+ * along with their emission profiles */
	+struct OrientationBounds {
	+ float3 axis; /* normal axis of the light */
	+ float theta_o; /* angle bounding the normals */
	+ float theta_e; /* angle bounding the light emissions */
	+
	+ __forceinline OrientationBounds()
	+ {
	+ }
	+
	+ __forceinline OrientationBounds(const float3 &axis_, float theta_o_, float theta_e_)
	+ : axis(axis_), theta_o(theta_o_), theta_e(theta_e_)
	+ {
	+ }
	+
	+ enum empty_t { empty = 0 };
	+
	+ /* If the orientation bound is set to empty, the values are set to minumums
	+ * so that merging it with another non-empty orientation bound guarantees that
	+ * the return value is equal to non-empty orientation bound. */
	+ __forceinline OrientationBounds(empty_t)
	+ : axis(make_float3(0, 0, 0)), theta_o(FLT_MIN), theta_e(FLT_MIN)
	+ {
	+ }
	+
	+ float calculate_measure() const;
	+};
	+
	+OrientationBounds merge(const OrientationBounds &cone_a, const OrientationBounds &cone_b);
	+
	+/* --------------------------------------------------------------------
	+ * Light Tree Construction
	+ *
	+ * The light tree construction is based off PBRT's BVH construction,
	+ * which first uses build nodes before converting to a more compact structure.
	+ */
	+
	+/* Light Tree Primitive Info
	+ * Struct to keep track of primitives in a vector of primitives,
	+ * which is used when reordering the vector. */
	+struct LightTreePrimitiveInfo {
	+ BoundBox bbox;
	+ OrientationBounds bcone;
	+ float3 centroid;
	+ float energy;
	+ int prim_num;
	+};
	+
	+/* Light Tree Primitive
	+ * Struct that indexes into the scene's triangle and light arrays. */
	+struct LightTreePrimitive {
	+ /* prim_id >= 0 is an index into an object's local triangle index,
	+ * otherwise -prim_id-1 is an index into device lights array. */
	+ int prim_id;
	+
	+ /* The primitive is either a light or an emissive triangle. */
	+ union {
	+ int object_id;
	+ int lamp_id;
	+ };
	+
	+ BoundBox calculate_bbox(Scene *scene) const;
	+ OrientationBounds calculate_bcone(Scene *scene) const;
	+ float calculate_energy(Scene *scene) const;
	+};
	+
	+/* Light Tree Bucket Info
	+ * Struct used to determine splitting costs in the light BVH. */
	+struct LightTreeBucketInfo {
	+ LightTreeBucketInfo()
	+ : energy(0.0f), bbox(BoundBox::empty), bcone(OrientationBounds::empty), count(0)
	+ {}
	+
	+ float energy; /* Total energy in the partition */
	+ BoundBox bbox;
	+ OrientationBounds bcone;
	+ int count;
	+
	+ static const int num_buckets = 12;
	+};
	+
	+/* Light Tree Build Node
	+ * Temporary build node when constructing light tree,
	+ * and is later converted into a more compact representation for device. */
	+struct LightTreeBuildNode {
	+ BoundBox bbox;
	+ OrientationBounds bcone;
	+ float energy;
	+ float energy_variance;
	+ LightTreeBuildNode *children[2];
	+ uint first_prim_index;
	+ uint num_lights;
	+ uint bit_trail;
	+ bool is_leaf;
	+
	+ void init_leaf(uint offset, uint n, const BoundBox& b, const OrientationBounds& c, float e, float e_var, uint bits);
	+ void init_interior(LightTreeBuildNode* c0, LightTreeBuildNode* c1);
	+};
	+
	+/* Packed Light Tree Node
	+ * Compact representation of light tree node
	+ * that's actually used in the device */
	+struct PackedLightTreeNode {
	+ BoundBox bbox;
	+ OrientationBounds bcone;
	+ float energy;
	+ float energy_variance;
	+ union {
	+ int first_prim_index; /* leaf nodes contain an index to first primitive. */
	+ int second_child_index; /* interior nodes contain an index to second child. */
	+ };
	+ int num_lights;
	+ bool is_leaf_node;
	+
	+ /* The bit trail traces the traversal from the root to a leaf node.
	+ * A value of 0 denotes traversing left while a value of 1 denotes traversing right. */
	+ uint bit_trail;
	+};
	+
	+/* Light BVH
	+ *
	+ * BVH-like data structure that keeps track of lights
	+ * and considers additional orientation and energy information */
	+class LightTree {
	+ vector<LightTreePrimitive> prims_;
	+ vector<PackedLightTreeNode> nodes_;
	+ Scene *scene_;
	+ uint max_lights_in_leaf_;
	+
	+public:
	+ LightTree(const vector<LightTreePrimitive> &prims, Scene *scene, uint max_lights_in_leaf);
	+
	+ const vector<LightTreePrimitive> &get_prims() const;
	+ const vector<PackedLightTreeNode> &get_nodes() const;
	+
	+private:
	+ LightTreeBuildNode* recursive_build(vector<LightTreePrimitiveInfo> &primitive_info, int start, int end, int &total_nodes, vector<LightTreePrimitive> &ordered_prims, uint bit_trail, int depth);
	+ void split_saoh(const BoundBox &centroid_bounds,
	+ const vector<LightTreePrimitiveInfo> &primitive_info, int start, int end, const BoundBox &bbox, const OrientationBounds &bcone, float& min_cost, int& min_dim, int& min_bucket);
	+ int flatten_tree(const LightTreeBuildNode *node, int &offset, int parent);
	+};
	+
	+CCL_NAMESPACE_END
	+
	+#endif /* __LIGHT_TREE_H__ */
	diff --git a/intern/cycles/scene/object.cpp b/intern/cycles/scene/object.cpp
	index 2126b23d82e..b3848c58501 100644
	--- a/intern/cycles/scene/object.cpp
	+++ b/intern/cycles/scene/object.cpp
	@@ -558,10 +558,12 @@ void ObjectManager::device_update_object_transform(UpdateObjectTransformState *s

	void ObjectManager::device_update_prim_offsets(Device device, DeviceScene dscene, Scene *scene)
	{
	- BVHLayoutMask layout_mask = device->get_bvh_layout_mask();
	- if (layout_mask != BVH_LAYOUT_METAL && layout_mask != BVH_LAYOUT_MULTI_METAL &&
	- layout_mask != BVH_LAYOUT_MULTI_METAL_EMBREE) {
	- return;
	+ if (!scene->integrator->get_use_light_tree()) {
	+ BVHLayoutMask layout_mask = device->get_bvh_layout_mask();
	+ if (layout_mask != BVH_LAYOUT_METAL && layout_mask != BVH_LAYOUT_MULTI_METAL &&
	+ layout_mask != BVH_LAYOUT_MULTI_METAL_EMBREE) {
	+ return;
	+ }
	}

	/* On MetalRT, primitive / curve segment offsets can't be baked at BVH build time. Intersection
	diff --git a/intern/cycles/scene/scene.cpp b/intern/cycles/scene/scene.cpp
	index 18cd665ac74..2718501ddba 100644
	--- a/intern/cycles/scene/scene.cpp
	+++ b/intern/cycles/scene/scene.cpp
	@@ -71,6 +71,12 @@ DeviceScene::DeviceScene(Device *device)
	lights(device, "lights", MEM_GLOBAL),
	light_background_marginal_cdf(device, "light_background_marginal_cdf", MEM_GLOBAL),
	light_background_conditional_cdf(device, "light_background_conditional_cdf", MEM_GLOBAL),
	+ light_tree_nodes(device, "light_tree_nodes", MEM_GLOBAL),
	+ light_tree_emitters(device, "light_tree_emitters", MEM_GLOBAL),
	+ light_tree_distant_group(device, "light_tree_distant_group", MEM_GLOBAL),
	+ light_to_tree(device, "light_to_tree", MEM_GLOBAL),
	+ object_lookup_offset(device, "object_lookup_offset", MEM_GLOBAL),
	+ triangle_to_tree(device, "triangle_to_tree", MEM_GLOBAL),
	particles(device, "particles", MEM_GLOBAL),
	svm_nodes(device, "svm_nodes", MEM_GLOBAL),
	shaders(device, "shaders", MEM_GLOBAL),
	diff --git a/intern/cycles/scene/scene.h b/intern/cycles/scene/scene.h
	index d1004bb7b66..d50666da316 100644
	--- a/intern/cycles/scene/scene.h
	+++ b/intern/cycles/scene/scene.h
	@@ -111,6 +111,14 @@ class DeviceScene {
	device_vector<float2> light_background_marginal_cdf;
	device_vector<float2> light_background_conditional_cdf;

	+ /* light tree */
	+ device_vector<KernelLightTreeNode> light_tree_nodes;
	+ device_vector<KernelLightTreeEmitter> light_tree_emitters;
	+ device_vector<KernelLightTreeDistantEmitter> light_tree_distant_group;
	+ device_vector<uint> light_to_tree;
	+ device_vector<uint> object_lookup_offset;
	+ device_vector<uint> triangle_to_tree;
	+
	/* particles */
	device_vector<KernelParticle> particles;

Event Timeline

Alaska (Alaska) created this paste.Sep 25 2022, 11:01 AM

Alaska (Alaska) mentioned this in T101356: New PMJ does not converge to the same result as Sobol-Burley.Sep 25 2022, 11:04 AM

Alaska (Alaska) archived this paste.Dec 17 2022, 4:45 AM

Differential for Many Lights Sampling applied on top of rB50df9caef01aArchivedPublicActions

Event Timeline

Differential for Many Lights Sampling applied on top of rB50df9caef01a
ArchivedPublic
Actions