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

Code before:
									switch (light_type) {
										case RS::LIGHT_OMNI: {
											if (omni_count < max_lights_per_mesh) {
												// 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_lights_per_mesh) {
												// 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 {
												if (spot_needs_heap) {
													// We need to make this a heap one time.
													heapify.make_heap(0, spot_count, &spot_score_idx[0]);
													spot_needs_heap = false;
												}
												if (light_inst_score < spot_score_idx[0].first) {
													uint32_t replace_index = spot_score_idx[0].second;
													geom->geometry_instance->pair_light_instance(light->instance, light_type, replace_index);
													heapify.adjust_heap(0, 0, spot_count, Pair(light_inst_score, replace_index), &spot_score_idx[0]);
												}
											}
										} break;
										default:
											break;
									}
								}
							}
						}
						idata.flags &= ~InstanceData::FLAG_GEOM_LIGHTING_DIRTY;
					}

					if (idata.flags & InstanceData::FLAG_GEOM_PROJECTOR_SOFTSHADOW_DIRTY) {
						InstanceGeometryData *geom = static_cast<InstanceGeometryData *>(idata.instance->base_data);

						ERR_FAIL_NULL(geom->geometry_instance);
						cull_data.cull->lock.lock();

Review comment (bug):
Finally got around to doing a bunch of testing @jon1solution. Played around a bit with the test projects.

First there does seem to be a bug. `heapify.adjust_heap` nicely inserts the new entry but it doesn't actually end up sorting the `LocalVector`, so the more lights it evaluates, the more likely you get the wrong lights.

Actually testing more, even after `make_heap` is called the sorting can be off:
<img width="1003" height="367" alt="Image" src="https://github.com/user-attachments/assets/bbe3ae67-7ee8-4c8a-a838-82d279555196" />
So it might even be a bug in the sort logic itself, or we're making an assumption here on what 'make_heap' and 'adjust_heap' supposedly do.

Testing in OpenGL with only 2 lights, it masks the issue, but testing in the mobile renderer with 8 lights you do end up with the wrong lights.

Second, and I can't put my finger on it completely, `geom->lights` seems to always contain all lights that are in range of the mesh regardless of whether the light itself is being culled. Or maybe there is some other criteria for what gets added here. As a result, this code path is skipped with the previous results reused until `FLAG_GEOM_LIGHTING_DIRTY` gets set. I can pass several lights and have them out of range behind the camera before the light pairing is updated and even then it seems to still process all lights.

Third, we're sorting by distance to the mesh. This solution is perfect for your use case (in which the second point is also mute), with many objects potentially being effected by many lights, sorting the lights and having those closest to the object win is perfect.

But the other sample from @Calinou 's comment, here all 3 points mentioned effect the outcome.
The sorting would mean that only the lights closest to the center of the mesh would be applied, regardless of the camera position. This use case would work better if we'd prioritise lights based on distance to the camera, but that would break your use case. 

I don't think the distance fade is taken into account here either, you'd expect it to adjust the content of `geom->lights` but it didn't seem to do so for me.

--

Anyway, to make a long story short. My recommendation is to figure out what is going on with the sorting and fix that issue. Then this PR solves your use case, which IMHO is all we can fix with this optimisation.

For the issues with the test project @Calinou was referring too, I think that requires an entirely different approach. We'd need to look into why `geom->lights` includes lights that should be culled because they shouldn't effect anything on screen.

Neither fixes the issue where there are more then 8 lights (2 for GLES3) that effect one mesh and where we'd like them sorted based on distance to camera instead of distance to mesh.
I think those requirements are mutually exclusive. Personally I believe distance wins out because you can solve the other use case by simply breaking your mesh up into smaller meshes. 



Code after:
									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) {
												// 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) {
#if VERIFY_RELEVANT_LIGHT_HEAP
													// The [0] element should have the max score.
													for (uint32_t vi = 1; vi < max_lights_per_mesh; ++vi) {
														if (omni_score_idx[vi].first > omni_score_idx[0].first) {
															ERR_PRINT_ONCE("Relevant Omni Light Heap Error");
														}
													}
#endif
													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_lights_per_mesh) {
												// 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 {
												if (spot_needs_heap) {
													// We need to make this a heap one time.
													heapify.make_heap(0, spot_count, &spot_score_idx[0]);
													spot_needs_heap = false;
												}