1 files changed, 140 insertions, 65 deletions

diff --git a/servers/rendering/renderer_scene_cull.h b/servers/rendering/renderer_scene_cull.h
index 051919314e..8bf262d7c0 100644
--- a/servers/rendering/renderer_scene_cull.h
+++ b/servers/rendering/renderer_scene_cull.h
@@ -34,30 +34,25 @@
 #include "core/templates/pass_func.h"
 #include "servers/rendering/renderer_compositor.h"
 
+#include "core/math/dynamic_bvh.h"
 #include "core/math/geometry_3d.h"
 #include "core/math/octree.h"
 #include "core/os/semaphore.h"
 #include "core/os/thread.h"
 #include "core/templates/local_vector.h"
+#include "core/templates/paged_allocator.h"
+#include "core/templates/paged_array.h"
 #include "core/templates/rid_owner.h"
 #include "core/templates/self_list.h"
 #include "servers/rendering/renderer_scene.h"
 #include "servers/rendering/renderer_scene_render.h"
 #include "servers/xr/xr_interface.h"
-
 class RendererSceneCull : public RendererScene {
 public:
 	RendererSceneRender *scene_render;
 
 	enum {
-		MAX_INSTANCE_CULL = 65536,
-		MAX_LIGHTS_CULLED = 4096,
-		MAX_REFLECTION_PROBES_CULLED = 4096,
-		MAX_DECALS_CULLED = 4096,
-		MAX_GI_PROBES_CULLED = 4096,
-		MAX_ROOM_CULL = 32,
-		MAX_LIGHTMAPS_CULLED = 4096,
-		MAX_EXTERIOR_PORTALS = 128,
+		SDFGI_MAX_CASCADES = 8
 	};
 
 	uint64_t render_pass;
@@ -114,11 +109,17 @@ public:
 	struct Instance;
 
 	struct Scenario {
+		enum IndexerType {
+			INDEXER_GEOMETRY, //for geometry
+			INDEXER_VOLUMES, //for everything else
+			INDEXER_MAX
+		};
+
+		DynamicBVH indexers[INDEXER_MAX];
+
 		RS::ScenarioDebugMode debug;
 		RID self;
 
-		Octree<Instance, true> octree;
-
 		List<Instance *> directional_lights;
 		RID environment;
 		RID fallback_environment;
@@ -130,13 +131,19 @@ public:
 
 		LocalVector<RID> dynamic_lights;
 
-		Scenario() { debug = RS::SCENARIO_DEBUG_DISABLED; }
+		Scenario() {
+			indexers[INDEXER_GEOMETRY].set_index(INDEXER_GEOMETRY);
+			indexers[INDEXER_VOLUMES].set_index(INDEXER_VOLUMES);
+			debug = RS::SCENARIO_DEBUG_DISABLED;
+		}
 	};
 
+	int indexer_update_iterations = 0;
+
 	mutable RID_PtrOwner<Scenario> scenario_owner;
 
-	static void *_instance_pair(void *p_self, OctreeElementID, Instance *p_A, int, OctreeElementID, Instance *p_B, int);
-	static void _instance_unpair(void *p_self, OctreeElementID, Instance *p_A, int, OctreeElementID, Instance *p_B, int, void *);
+	static void _instance_pair(Instance *p_A, Instance *p_B);
+	static void _instance_unpair(Instance *p_A, Instance *p_B);
 
 	static void _instance_update_mesh_instance(Instance *p_instance);
 
@@ -152,6 +159,17 @@ public:
 
 	/* INSTANCING API */
 
+	struct InstancePair {
+		Instance *a;
+		Instance *b;
+		SelfList<InstancePair> list_a;
+		SelfList<InstancePair> list_b;
+		InstancePair() :
+				list_a(this), list_b(this) {}
+	};
+
+	PagedAllocator<InstancePair> pair_allocator;
+
 	struct InstanceBaseData {
 		virtual ~InstanceBaseData() {}
 	};
@@ -159,7 +177,7 @@ public:
 	struct Instance : RendererSceneRender::InstanceBase {
 		RID self;
 		//scenario stuff
-		OctreeElementID octree_id;
+		DynamicBVH::ID indexer_id;
 		Scenario *scenario;
 		SelfList<Instance> scenario_item;
 
@@ -188,6 +206,9 @@ public:
 
 		InstanceBaseData *base_data;
 
+		SelfList<InstancePair>::List pairs;
+		uint64_t pair_check;
+
 		virtual void dependency_deleted(RID p_dependency) {
 			if (p_dependency == base) {
 				singleton->instance_set_base(self, RID());
@@ -205,7 +226,6 @@ public:
 		Instance() :
 				scenario_item(this),
 				update_item(this) {
-			octree_id = 0;
 			scenario = nullptr;
 
 			update_aabb = false;
@@ -226,6 +246,8 @@ public:
 			base_data = nullptr;
 
 			custom_aabb = nullptr;
+
+			pair_check = 0;
 		}
 
 		~Instance() {
@@ -242,21 +264,21 @@ public:
 	void _instance_queue_update(Instance *p_instance, bool p_update_aabb, bool p_update_dependencies = false);
 
 	struct InstanceGeometryData : public InstanceBaseData {
-		List<Instance *> lighting;
+		Set<Instance *> lights;
 		bool lighting_dirty;
 		bool can_cast_shadows;
 		bool material_is_animated;
 
-		List<Instance *> decals;
+		Set<Instance *> decals;
 		bool decal_dirty;
 
-		List<Instance *> reflection_probes;
+		Set<Instance *> reflection_probes;
 		bool reflection_dirty;
 
-		List<Instance *> gi_probes;
+		Set<Instance *> gi_probes;
 		bool gi_probes_dirty;
 
-		List<Instance *> lightmap_captures;
+		Set<Instance *> lightmap_captures;
 
 		InstanceGeometryData() {
 			lighting_dirty = false;
@@ -271,11 +293,7 @@ public:
 	struct InstanceReflectionProbeData : public InstanceBaseData {
 		Instance *owner;
 
-		struct PairInfo {
-			List<Instance *>::Element *L; //reflection iterator in geometry
-			Instance *geometry;
-		};
-		List<PairInfo> geometries;
+		Set<Instance *> geometries;
 
 		RID instance;
 		bool reflection_dirty;
@@ -294,11 +312,7 @@ public:
 		Instance *owner;
 		RID instance;
 
-		struct PairInfo {
-			List<Instance *>::Element *L; //reflection iterator in geometry
-			Instance *geometry;
-		};
-		List<PairInfo> geometries;
+		Set<Instance *> geometries;
 
 		InstanceDecalData() {
 		}
@@ -307,18 +321,13 @@ public:
 	SelfList<InstanceReflectionProbeData>::List reflection_probe_render_list;
 
 	struct InstanceLightData : public InstanceBaseData {
-		struct PairInfo {
-			List<Instance *>::Element *L; //light iterator in geometry
-			Instance *geometry;
-		};
-
 		RID instance;
 		uint64_t last_version;
 		List<Instance *>::Element *D; // directional light in scenario
 
 		bool shadow_dirty;
 
-		List<PairInfo> geometries;
+		Set<Instance *> geometries;
 
 		Instance *baked_light;
 
@@ -339,13 +348,8 @@ public:
 	struct InstanceGIProbeData : public InstanceBaseData {
 		Instance *owner;
 
-		struct PairInfo {
-			List<Instance *>::Element *L; //gi probe iterator in geometry
-			Instance *geometry;
-		};
-
-		List<PairInfo> geometries;
-		List<PairInfo> dynamic_geometries;
+		Set<Instance *> geometries;
+		Set<Instance *> dynamic_geometries;
 
 		Set<Instance *> lights;
 
@@ -383,40 +387,110 @@ public:
 	SelfList<InstanceGIProbeData>::List gi_probe_update_list;
 
 	struct InstanceLightmapData : public InstanceBaseData {
-		struct PairInfo {
-			List<Instance *>::Element *L; //iterator in geometry
-			Instance *geometry;
-		};
-		List<PairInfo> geometries;
-
+		Set<Instance *> geometries;
 		Set<Instance *> users;
 
 		InstanceLightmapData() {
 		}
 	};
 
+	uint64_t pair_pass = 1;
+
+	struct PairInstances {
+		Instance *instance = nullptr;
+		PagedAllocator<InstancePair> *pair_allocator = nullptr;
+		SelfList<InstancePair>::List pairs_found;
+		DynamicBVH *bvh = nullptr;
+		DynamicBVH *bvh2 = nullptr; //some may need to cull in two
+		uint32_t pair_mask;
+		uint64_t pair_pass;
+
+		_FORCE_INLINE_ bool operator()(void *p_data) {
+			Instance *p_instance = (Instance *)p_data;
+			if (instance != p_instance && instance->transformed_aabb.intersects(p_instance->transformed_aabb) && (pair_mask & (1 << p_instance->base_type))) {
+				//test is more coarse in indexer
+				p_instance->pair_check = pair_pass;
+				InstancePair *pair = pair_allocator->alloc();
+				pair->a = instance;
+				pair->b = p_instance;
+				pairs_found.add(&pair->list_a);
+			}
+			return false;
+		}
+
+		void pair() {
+			if (bvh) {
+				bvh->aabb_query(instance->transformed_aabb, *this);
+			}
+			if (bvh2) {
+				bvh2->aabb_query(instance->transformed_aabb, *this);
+			}
+			while (instance->pairs.first()) {
+				InstancePair *pair = instance->pairs.first()->self();
+				Instance *other_instance = instance == pair->a ? pair->b : pair->a;
+				if (other_instance->pair_check != pair_pass) {
+					//unpaired
+					_instance_unpair(instance, other_instance);
+				} else {
+					//kept
+					other_instance->pair_check = 0; // if kept, then put pair check to zero, so we can distinguish with the newly added ones
+				}
+
+				pair_allocator->free(pair);
+			}
+			while (pairs_found.first()) {
+				InstancePair *pair = pairs_found.first()->self();
+				pairs_found.remove(pairs_found.first());
+
+				if (pair->b->pair_check == pair_pass) {
+					//paired
+					_instance_pair(instance, pair->b);
+				}
+				pair->a->pairs.add(&pair->list_a);
+				pair->b->pairs.add(&pair->list_b);
+			}
+		}
+	};
+
+	struct CullResult {
+		PagedArray<Instance *> *result;
+		_FORCE_INLINE_ bool operator()(void *p_data) {
+			Instance *p_instance = (Instance *)p_data;
+			result->push_back(p_instance);
+			return false;
+		}
+	};
+
 	Set<Instance *> heightfield_particle_colliders_update_list;
 
-	int instance_cull_count;
-	Instance *instance_cull_result[MAX_INSTANCE_CULL];
-	Instance *instance_shadow_cull_result[MAX_INSTANCE_CULL]; //used for generating shadowmaps
-	Instance *light_cull_result[MAX_LIGHTS_CULLED];
-	RID sdfgi_light_cull_result[MAX_LIGHTS_CULLED];
-	RID light_instance_cull_result[MAX_LIGHTS_CULLED];
+	PagedArrayPool<Instance *> instance_cull_page_pool;
+	PagedArrayPool<RendererSceneRender::InstanceBase *> base_instance_cull_page_pool;
+	PagedArrayPool<RID> rid_cull_page_pool;
+
+	PagedArray<Instance *> instance_cull_result;
+	PagedArray<RendererSceneRender::InstanceBase *> geometry_instances_to_render;
+	PagedArray<Instance *> instance_shadow_cull_result;
+	PagedArray<RendererSceneRender::InstanceBase *> geometry_instances_to_shadow_render;
+	PagedArray<Instance *> instance_sdfgi_cull_result;
+	PagedArray<RendererSceneRender::InstanceBase *> geometry_instances_to_sdfgi_render;
+	PagedArray<Instance *> light_cull_result;
+	PagedArray<RendererSceneRender::InstanceBase *> lightmap_cull_result;
+	PagedArray<Instance *> directional_shadow_cull_result;
+	PagedArray<RID> reflection_probe_instance_cull_result;
+	PagedArray<RID> light_instance_cull_result;
+	PagedArray<RID> directional_light_cull_result;
+	PagedArray<RID> gi_probe_instance_cull_result;
+	PagedArray<RID> decal_instance_cull_result;
+
+	PagedArray<RID> sdfgi_cascade_lights[SDFGI_MAX_CASCADES];
+
 	uint64_t sdfgi_light_cull_pass = 0;
-	int light_cull_count;
 	int directional_light_count;
-	RID reflection_probe_instance_cull_result[MAX_REFLECTION_PROBES_CULLED];
-	RID decal_instance_cull_result[MAX_DECALS_CULLED];
-	int reflection_probe_cull_count;
-	int decal_cull_count;
-	RID gi_probe_instance_cull_result[MAX_GI_PROBES_CULLED];
-	int gi_probe_cull_count;
-	Instance *lightmap_cull_result[MAX_LIGHTS_CULLED];
-	int lightmap_cull_count;
 
 	RID_PtrOwner<Instance> instance_owner;
 
+	bool pair_volumes_to_mesh; // used in traditional forward, unnecesary on clustered
+
 	virtual RID instance_create();
 
 	virtual void instance_set_base(RID p_instance, RID p_base);
@@ -460,6 +534,7 @@ public:
 	_FORCE_INLINE_ void _update_instance_aabb(Instance *p_instance);
 	_FORCE_INLINE_ void _update_dirty_instance(Instance *p_instance);
 	_FORCE_INLINE_ void _update_instance_lightmap_captures(Instance *p_instance);
+	void _unpair_instance(Instance *p_instance);
 
 	_FORCE_INLINE_ bool _light_instance_update_shadow(Instance *p_instance, const Transform p_cam_transform, const CameraMatrix &p_cam_projection, bool p_cam_orthogonal, bool p_cam_vaspect, RID p_shadow_atlas, Scenario *p_scenario, float p_scren_lod_threshold);