Repository: godotengine/godot
File: servers/rendering/renderer_scene_cull.cpp (C++)

Code before:
							LocalVector<Pair<float, uint32_t>> omni_score_idx, spot_score_idx; //	score, index into the light array
							SortArray<Pair<float, uint32_t>> heapify; //	SortArray has heap functionality in it
							bool omni_needs_heap = true, spot_needs_heap = true;
							Vector3 mesh_center = idata.instance->transformed_aabb.get_center();
							//	Run through all lights in the scene (there might be more than max_renderable_lights)
							uint32_t total_omni_count = 0, total_spot_count = 0;
							for (const Instance *E : geom->lights) {
								RS::LightType light_type = RSG::light_storage->light_get_type(E->base);
								if (((RS::LIGHT_OMNI == light_type) && (total_omni_count++ < max_per_mesh_total.second)) ||
										((RS::LIGHT_SPOT == light_type) && (total_spot_count++ < max_per_mesh_total.second))) {
									//	Cull
									if (!(RSG::light_storage->light_get_cull_mask(E->base) & idata.layer_mask)) {
										continue;
									}
									if ((RSG::light_storage->light_get_bake_mode(E->base) == RS::LIGHT_BAKE_STATIC) && idata.instance->lightmap) {
										continue;
									}

									InstanceLightData *light = static_cast<InstanceLightData *>(E->base_data);
									//	Large scores are worse, so linear with distance, inverse with energy and range
									Vector3 light_center = E->transformed_aabb.get_center();
									float light_range_energy =
											RSG::light_storage->light_get_param(E->base, RS::LightParam::LIGHT_PARAM_RANGE) *
											RSG::light_storage->light_get_param(E->base, RS::LightParam::LIGHT_PARAM_ENERGY);
									float light_inst_score = mesh_center.distance_to(light_center) / MAX(0.01f, light_range_energy);
									//	Keep the best per-light-type
									switch (light_type) {
										case RS::LIGHT_OMNI: {
											if (omni_count < max_per_mesh_total.first) {
												//	We have room to just add it, and track the score and where it goes
												omni_score_idx.push_back(Pair(light_inst_score, omni_count));
												geom->geometry_instance->pair_light_instance(light->instance, light_type, omni_count++);
											} else {
												if (omni_needs_heap) {
													//	We need to make this a heap one time
													heapify.make_heap(0, omni_count, &omni_score_idx[0]);
													omni_needs_heap = false;
												}
												if (light_inst_score < omni_score_idx[0].first) {
													uint32_t replace_index = omni_score_idx[0].second;
													geom->geometry_instance->pair_light_instance(light->instance, light_type, replace_index);
													heapify.adjust_heap(0, 0, omni_count, Pair(light_inst_score, replace_index), &omni_score_idx[0]);
												}
											}
										} break;
										case RS::LIGHT_SPOT: {
											if (spot_count < max_per_mesh_total.first) {
												//	We have room to just add it, and track the score and where it goes
												spot_score_idx.push_back(Pair(light_inst_score, spot_count));
												geom->geometry_instance->pair_light_instance(light->instance, light_type, spot_count++);
											} else {

Review comment (suggestion):
```suggestion
									// Keep the "best" lights on a per-light-type basis.
```

Code after:
					}

					if (geometry_instance_pair_mask & (1 << RS::INSTANCE_LIGHT) && (idata.flags & InstanceData::FLAG_GEOM_LIGHTING_DIRTY)) {
						InstanceGeometryData *geom = static_cast<InstanceGeometryData *>(idata.instance->base_data);
						ERR_FAIL_NULL(geom->geometry_instance);
						// Clear any existing light instances for this mesh and find the max count per-mesh, and total (per-scene).
						geom->geometry_instance->clear_light_instances();
						if ((max_lights_per_mesh > 0) && (max_lights_total > 0)) {
							// For the top N lights, track the score and the index into the internal light storage array.
							uint32_t total_omni_count = 0, total_spot_count = 0;
							bool omni_needs_heap = true, spot_needs_heap = true;
							uint32_t omni_count = 0, spot_count = 0;
							omni_score_idx.clear();
							spot_score_idx.clear();
							SortArray<Pair<float, uint32_t>> heapify; // SortArray has heap functions, but no local storage.
							// Iterate over the lights (possibly > max_renderable_lights), keeping the closest to the mesh center.
							Vector3 mesh_center = idata.instance->transformed_aabb.get_center();
							for (const Instance *E : geom->lights) {
								RS::LightType light_type = RSG::light_storage->light_get_type(E->base);
								if (((RS::LIGHT_OMNI == light_type) && (total_omni_count++ < max_lights_total)) ||
										((RS::LIGHT_SPOT == light_type) && (total_spot_count++ < max_lights_total))) {
									// Perform culling.
									if (!(RSG::light_storage->light_get_cull_mask(E->base) & idata.layer_mask)) {
										continue;
									}
									if ((RSG::light_storage->light_get_bake_mode(E->base) == RS::LIGHT_BAKE_STATIC) && idata.instance->lightmap) {
										continue;
									}

									InstanceLightData *light = static_cast<InstanceLightData *>(E->base_data);
									// Large scores are worse, so linear with distance, inverse with energy and range.
									Vector3 light_center = E->transformed_aabb.get_center();
									float light_range_energy =
											RSG::light_storage->light_get_param(E->base, RS::LightParam::LIGHT_PARAM_RANGE) *
											RSG::light_storage->light_get_param(E->base, RS::LightParam::LIGHT_PARAM_ENERGY);
									float light_inst_score = mesh_center.distance_to(light_center) / MAX(0.01f, light_range_energy);
									// Of the N lights (on a per-light-type basis, Omni or Spot) keep only the M "best" lights.
									// If N <= M, we can simply store the lights, but once we exceed M, we need check each new
									// light and see if it's score is better than the worst light stored to date.  If the new
									// light is better, we can replace the current worst light with the new one.  In order to
									// efficiently track our currently worst light we use a "max heap".  This loosely orders
									// the elements in an array as a binary-tree structure, and has the properties that finding
									// the worst score element is O(1) (it will always be stored in element [0]), and removing
									// the old max and inserting a new value is O(log M).
#define VERIFY_RELEVANT_LIGHT_HEAP 0
#if VERIFY_RELEVANT_LIGHT_HEAP
									WARN_PRINT_ONCE("VERIFY_RELEVANT_LIGHT_HEAP is True");
#endif
									switch (light_type) {
										case RS::LIGHT_OMNI: {
											if (omni_count < max_lights_per_mesh) {