diff options
Diffstat (limited to 'servers/rendering')
| -rw-r--r-- | servers/rendering/renderer_scene_cull.cpp | 82 | ||||
| -rw-r--r-- | servers/rendering/renderer_scene_cull.h | 53 | ||||
| -rw-r--r-- | servers/rendering/rendering_light_culler.cpp | 1125 | ||||
| -rw-r--r-- | servers/rendering/rendering_light_culler.h | 248 |
4 files changed, 1495 insertions, 13 deletions
diff --git a/servers/rendering/renderer_scene_cull.cpp b/servers/rendering/renderer_scene_cull.cpp index 2f7e4fef06..b8f14bb611 100644 --- a/servers/rendering/renderer_scene_cull.cpp +++ b/servers/rendering/renderer_scene_cull.cpp @@ -33,6 +33,7 @@ #include "core/config/project_settings.h" #include "core/object/worker_thread_pool.h" #include "core/os/os.h" +#include "rendering_light_culler.h" #include "rendering_server_default.h" #include <new> @@ -158,7 +159,7 @@ void RendererSceneCull::_instance_pair(Instance *p_A, Instance *p_B) { light->geometries.insert(A); if (geom->can_cast_shadows) { - light->shadow_dirty = true; + light->make_shadow_dirty(); } if (A->scenario && A->array_index >= 0) { @@ -265,7 +266,7 @@ void RendererSceneCull::_instance_unpair(Instance *p_A, Instance *p_B) { light->geometries.erase(A); if (geom->can_cast_shadows) { - light->shadow_dirty = true; + light->make_shadow_dirty(); } if (A->scenario && A->array_index >= 0) { @@ -871,7 +872,7 @@ void RendererSceneCull::instance_set_layer_mask(RID p_instance, uint32_t p_mask) if (geom->can_cast_shadows) { for (HashSet<RendererSceneCull::Instance *>::Iterator I = geom->lights.begin(); I != geom->lights.end(); ++I) { InstanceLightData *light = static_cast<InstanceLightData *>((*I)->base_data); - light->shadow_dirty = true; + light->make_shadow_dirty(); } } } @@ -1565,7 +1566,7 @@ void RendererSceneCull::_update_instance(Instance *p_instance) { RSG::light_storage->light_instance_set_transform(light->instance, p_instance->transform); RSG::light_storage->light_instance_set_aabb(light->instance, p_instance->transform.xform(p_instance->aabb)); - light->shadow_dirty = true; + light->make_shadow_dirty(); RS::LightBakeMode bake_mode = RSG::light_storage->light_get_bake_mode(p_instance->base); if (RSG::light_storage->light_get_type(p_instance->base) != RS::LIGHT_DIRECTIONAL && bake_mode != light->bake_mode) { @@ -1650,7 +1651,7 @@ void RendererSceneCull::_update_instance(Instance *p_instance) { if (geom->can_cast_shadows) { for (const Instance *E : geom->lights) { InstanceLightData *light = static_cast<InstanceLightData *>(E->base_data); - light->shadow_dirty = true; + light->make_shadow_dirty(); } } @@ -2075,6 +2076,9 @@ void RendererSceneCull::_update_instance_lightmap_captures(Instance *p_instance) } void RendererSceneCull::_light_instance_setup_directional_shadow(int p_shadow_index, Instance *p_instance, const Transform3D p_cam_transform, const Projection &p_cam_projection, bool p_cam_orthogonal, bool p_cam_vaspect) { + // For later tight culling, the light culler needs to know the details of the directional light. + light_culler->prepare_directional_light(p_instance, p_shadow_index); + InstanceLightData *light = static_cast<InstanceLightData *>(p_instance->base_data); Transform3D light_transform = p_instance->transform; @@ -2345,6 +2349,10 @@ bool RendererSceneCull::_light_instance_update_shadow(Instance *p_instance, cons RendererSceneRender::RenderShadowData &shadow_data = render_shadow_data[max_shadows_used++]; + if (!light->is_shadow_update_full()) { + light_culler->cull_regular_light(instance_shadow_cull_result); + } + for (int j = 0; j < (int)instance_shadow_cull_result.size(); j++) { Instance *instance = instance_shadow_cull_result[j]; if (!instance->visible || !((1 << instance->base_type) & RS::INSTANCE_GEOMETRY_MASK) || !static_cast<InstanceGeometryData *>(instance->base_data)->can_cast_shadows || !(p_visible_layers & instance->layer_mask)) { @@ -2423,6 +2431,10 @@ bool RendererSceneCull::_light_instance_update_shadow(Instance *p_instance, cons RendererSceneRender::RenderShadowData &shadow_data = render_shadow_data[max_shadows_used++]; + if (!light->is_shadow_update_full()) { + light_culler->cull_regular_light(instance_shadow_cull_result); + } + for (int j = 0; j < (int)instance_shadow_cull_result.size(); j++) { Instance *instance = instance_shadow_cull_result[j]; if (!instance->visible || !((1 << instance->base_type) & RS::INSTANCE_GEOMETRY_MASK) || !static_cast<InstanceGeometryData *>(instance->base_data)->can_cast_shadows || !(p_visible_layers & instance->layer_mask)) { @@ -2486,6 +2498,10 @@ bool RendererSceneCull::_light_instance_update_shadow(Instance *p_instance, cons RendererSceneRender::RenderShadowData &shadow_data = render_shadow_data[max_shadows_used++]; + if (!light->is_shadow_update_full()) { + light_culler->cull_regular_light(instance_shadow_cull_result); + } + for (int j = 0; j < (int)instance_shadow_cull_result.size(); j++) { Instance *instance = instance_shadow_cull_result[j]; if (!instance->visible || !((1 << instance->base_type) & RS::INSTANCE_GEOMETRY_MASK) || !static_cast<InstanceGeometryData *>(instance->base_data)->can_cast_shadows || !(p_visible_layers & instance->layer_mask)) { @@ -2940,6 +2956,9 @@ void RendererSceneCull::_scene_cull(CullData &cull_data, InstanceCullResult &cul } for (uint32_t j = 0; j < cull_data.cull->shadow_count; j++) { + if (!light_culler->cull_directional_light(cull_data.scenario->instance_aabbs[i], j)) { + continue; + } for (uint32_t k = 0; k < cull_data.cull->shadows[j].cascade_count; k++) { if (IN_FRUSTUM(cull_data.cull->shadows[j].cascades[k].frustum) && VIS_CHECK) { uint32_t base_type = idata.flags & InstanceData::FLAG_BASE_TYPE_MASK; @@ -2992,6 +3011,9 @@ void RendererSceneCull::_scene_cull(CullData &cull_data, InstanceCullResult &cul void RendererSceneCull::_render_scene(const RendererSceneRender::CameraData *p_camera_data, const Ref<RenderSceneBuffers> &p_render_buffers, RID p_environment, RID p_force_camera_attributes, uint32_t p_visible_layers, RID p_scenario, RID p_viewport, RID p_shadow_atlas, RID p_reflection_probe, int p_reflection_probe_pass, float p_screen_mesh_lod_threshold, bool p_using_shadows, RenderingMethod::RenderInfo *r_render_info) { Instance *render_reflection_probe = instance_owner.get_or_null(p_reflection_probe); //if null, not rendering to it + // Prepare the light - camera volume culling system. + light_culler->prepare_camera(p_camera_data->main_transform, p_camera_data->main_projection); + Scenario *scenario = scenario_owner.get_or_null(p_scenario); ERR_FAIL_COND(p_render_buffers.is_null()); @@ -3126,6 +3148,7 @@ void RendererSceneCull::_render_scene(const RendererSceneRender::CameraData *p_c #ifdef DEBUG_CULL_TIME uint64_t time_from = OS::get_singleton()->get_ticks_usec(); #endif + if (cull_to > thread_cull_threshold) { //multiple threads for (InstanceCullResult &thread : scene_cull_result_threads) { @@ -3263,9 +3286,31 @@ void RendererSceneCull::_render_scene(const RendererSceneRender::CameraData *p_c } } - if (light->shadow_dirty) { - light->last_version++; - light->shadow_dirty = false; + // We can detect whether multiple cameras are hitting this light, whether or not the shadow is dirty, + // so that we can turn off tighter caster culling. + light->detect_light_intersects_multiple_cameras(Engine::get_singleton()->get_frames_drawn()); + + if (light->is_shadow_dirty()) { + // Dirty shadows have no need to be drawn if + // the light volume doesn't intersect the camera frustum. + + // Returns false if the entire light can be culled. + bool allow_redraw = light_culler->prepare_regular_light(*ins); + + // Directional lights aren't handled here, _light_instance_update_shadow is called from elsewhere. + // Checking for this in case this changes, as this is assumed. + DEV_CHECK_ONCE(RSG::light_storage->light_get_type(ins->base) != RS::LIGHT_DIRECTIONAL); + + // Tighter caster culling to the camera frustum should work correctly with multiple viewports + cameras. + // The first camera will cull tightly, but if the light is present on more than 1 camera, the second will + // do a full render, and mark the light as non-dirty. + // There is however a cost to tighter shadow culling in this situation (2 shadow updates in 1 frame), + // so we should detect this and switch off tighter caster culling automatically. + // This is done in the logic for `decrement_shadow_dirty()`. + if (allow_redraw) { + light->last_version++; + light->decrement_shadow_dirty(); + } } bool redraw = RSG::light_storage->shadow_atlas_update_light(p_shadow_atlas, light->instance, coverage, light->last_version); @@ -3273,10 +3318,14 @@ void RendererSceneCull::_render_scene(const RendererSceneRender::CameraData *p_c if (redraw && max_shadows_used < MAX_UPDATE_SHADOWS) { //must redraw! RENDER_TIMESTAMP("> Render Light3D " + itos(i)); - light->shadow_dirty = _light_instance_update_shadow(ins, p_camera_data->main_transform, p_camera_data->main_projection, p_camera_data->is_orthogonal, p_camera_data->vaspect, p_shadow_atlas, scenario, p_screen_mesh_lod_threshold, p_visible_layers); + if (_light_instance_update_shadow(ins, p_camera_data->main_transform, p_camera_data->main_projection, p_camera_data->is_orthogonal, p_camera_data->vaspect, p_shadow_atlas, scenario, p_screen_mesh_lod_threshold, p_visible_layers)) { + light->make_shadow_dirty(); + } RENDER_TIMESTAMP("< Render Light3D " + itos(i)); } else { - light->shadow_dirty = redraw; + if (redraw) { + light->make_shadow_dirty(); + } } } } @@ -3953,7 +4002,7 @@ void RendererSceneCull::_update_dirty_instance(Instance *p_instance) { //ability to cast shadows change, let lights now for (const Instance *E : geom->lights) { InstanceLightData *light = static_cast<InstanceLightData *>(E->base_data); - light->shadow_dirty = true; + light->make_shadow_dirty(); } geom->can_cast_shadows = can_cast_shadows; @@ -4165,6 +4214,12 @@ RendererSceneCull::RendererSceneCull() { thread_cull_threshold = MAX(thread_cull_threshold, (uint32_t)WorkerThreadPool::get_singleton()->get_thread_count()); //make sure there is at least one thread per CPU dummy_occlusion_culling = memnew(RendererSceneOcclusionCull); + + light_culler = memnew(RenderingLightCuller); + + bool tighter_caster_culling = GLOBAL_DEF("rendering/lights_and_shadows/tighter_shadow_caster_culling", true); + light_culler->set_caster_culling_active(tighter_caster_culling); + light_culler->set_light_culling_active(tighter_caster_culling); } RendererSceneCull::~RendererSceneCull() { @@ -4187,4 +4242,9 @@ RendererSceneCull::~RendererSceneCull() { if (dummy_occlusion_culling) { memdelete(dummy_occlusion_culling); } + + if (light_culler) { + memdelete(light_culler); + light_culler = nullptr; + } } diff --git a/servers/rendering/renderer_scene_cull.h b/servers/rendering/renderer_scene_cull.h index e3e20b8502..a09823b008 100644 --- a/servers/rendering/renderer_scene_cull.h +++ b/servers/rendering/renderer_scene_cull.h @@ -46,6 +46,8 @@ #include "servers/rendering/storage/utilities.h" #include "servers/xr/xr_interface.h" +class RenderingLightCuller; + class RendererSceneCull : public RenderingMethod { public: RendererSceneRender *scene_render = nullptr; @@ -679,7 +681,6 @@ public: uint64_t last_version; List<Instance *>::Element *D; // directional light in scenario - bool shadow_dirty; bool uses_projector = false; bool uses_softshadow = false; @@ -690,12 +691,59 @@ public: RS::LightBakeMode bake_mode; uint32_t max_sdfgi_cascade = 2; + private: + // Instead of a single dirty flag, we maintain a count + // so that we can detect lights that are being made dirty + // each frame, and switch on tighter caster culling. + int32_t shadow_dirty_count; + + uint32_t light_update_frame_id; + bool light_intersects_multiple_cameras; + uint32_t light_intersects_multiple_cameras_timeout_frame_id; + + public: + bool is_shadow_dirty() const { return shadow_dirty_count != 0; } + void make_shadow_dirty() { shadow_dirty_count = light_intersects_multiple_cameras ? 1 : 2; } + void detect_light_intersects_multiple_cameras(uint32_t p_frame_id) { + // We need to detect the case where shadow updates are occurring + // more than once per frame. In this case, we need to turn off + // tighter caster culling, so situation reverts to one full shadow update + // per frame (light_intersects_multiple_cameras is set). + if (p_frame_id == light_update_frame_id) { + light_intersects_multiple_cameras = true; + light_intersects_multiple_cameras_timeout_frame_id = p_frame_id + 60; + } else { + // When shadow_volume_intersects_multiple_cameras is set, we + // want to detect the situation this is no longer the case, via a timeout. + // The system can go back to tighter caster culling in this situation. + // Having a long-ish timeout prevents rapid cycling. + if (light_intersects_multiple_cameras && (p_frame_id >= light_intersects_multiple_cameras_timeout_frame_id)) { + light_intersects_multiple_cameras = false; + light_intersects_multiple_cameras_timeout_frame_id = UINT32_MAX; + } + } + light_update_frame_id = p_frame_id; + } + + void decrement_shadow_dirty() { + shadow_dirty_count--; + DEV_ASSERT(shadow_dirty_count >= 0); + } + + // Shadow updates can either full (everything in the shadow volume) + // or closely culled to the camera frustum. + bool is_shadow_update_full() const { return shadow_dirty_count == 0; } + InstanceLightData() { bake_mode = RS::LIGHT_BAKE_DISABLED; - shadow_dirty = true; D = nullptr; last_version = 0; baked_light = nullptr; + + shadow_dirty_count = 1; + light_update_frame_id = UINT32_MAX; + light_intersects_multiple_cameras_timeout_frame_id = UINT32_MAX; + light_intersects_multiple_cameras = false; } }; @@ -955,6 +1003,7 @@ public: uint32_t geometry_instance_pair_mask = 0; // used in traditional forward, unnecessary on clustered LocalVector<Vector2> camera_jitter_array; + RenderingLightCuller *light_culler = nullptr; virtual RID instance_allocate(); virtual void instance_initialize(RID p_rid); diff --git a/servers/rendering/rendering_light_culler.cpp b/servers/rendering/rendering_light_culler.cpp new file mode 100644 index 0000000000..0d704c85de --- /dev/null +++ b/servers/rendering/rendering_light_culler.cpp @@ -0,0 +1,1125 @@ +/**************************************************************************/ +/* rendering_light_culler.cpp */ +/**************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/**************************************************************************/ +/* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */ +/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. */ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/**************************************************************************/ + +#include "rendering_light_culler.h" + +#include "core/math/plane.h" +#include "core/math/projection.h" +#include "rendering_server_globals.h" +#include "scene/3d/camera_3d.h" + +#ifdef RENDERING_LIGHT_CULLER_DEBUG_STRINGS +const char *RenderingLightCuller::Data::string_planes[] = { + "NEAR", + "FAR", + "LEFT", + "TOP", + "RIGHT", + "BOTTOM", +}; +const char *RenderingLightCuller::Data::string_points[] = { + "FAR_LEFT_TOP", + "FAR_LEFT_BOTTOM", + "FAR_RIGHT_TOP", + "FAR_RIGHT_BOTTOM", + "NEAR_LEFT_TOP", + "NEAR_LEFT_BOTTOM", + "NEAR_RIGHT_TOP", + "NEAR_RIGHT_BOTTOM", +}; + +String RenderingLightCuller::Data::plane_bitfield_to_string(unsigned int BF) { + String sz; + + for (int n = 0; n < 6; n++) { + unsigned int bit = 1 << n; + if (BF & bit) { + sz += String(string_planes[n]) + ", "; + } + } + + return sz; +} +#endif + +void RenderingLightCuller::prepare_directional_light(const RendererSceneCull::Instance *p_instance, int32_t p_directional_light_id) { + //data.directional_light = p_instance; + // Something is probably going wrong, we shouldn't have this many directional lights... + ERR_FAIL_COND(p_directional_light_id > 512); + DEV_ASSERT(p_directional_light_id >= 0); + + // First make sure we have enough directional lights to hold this one. + if (p_directional_light_id >= (int32_t)data.directional_cull_planes.size()) { + data.directional_cull_planes.resize(p_directional_light_id + 1); + } + + _prepare_light(*p_instance, p_directional_light_id); +} + +bool RenderingLightCuller::_prepare_light(const RendererSceneCull::Instance &p_instance, int32_t p_directional_light_id) { + if (!data.is_active()) { + return true; + } + + LightSource lsource; + switch (RSG::light_storage->light_get_type(p_instance.base)) { + case RS::LIGHT_SPOT: + lsource.type = LightSource::ST_SPOTLIGHT; + lsource.angle = RSG::light_storage->light_get_param(p_instance.base, RS::LIGHT_PARAM_SPOT_ANGLE); + lsource.range = RSG::light_storage->light_get_param(p_instance.base, RS::LIGHT_PARAM_RANGE); + break; + case RS::LIGHT_OMNI: + lsource.type = LightSource::ST_OMNI; + lsource.range = RSG::light_storage->light_get_param(p_instance.base, RS::LIGHT_PARAM_RANGE); + break; + case RS::LIGHT_DIRECTIONAL: + lsource.type = LightSource::ST_DIRECTIONAL; + // Could deal with a max directional shadow range here? NYI + // LIGHT_PARAM_SHADOW_MAX_DISTANCE + break; + } + + lsource.pos = p_instance.transform.origin; + lsource.dir = -p_instance.transform.basis.get_column(2); + lsource.dir.normalize(); + + bool visible; + if (p_directional_light_id == -1) { + visible = _add_light_camera_planes(data.regular_cull_planes, lsource); + } else { + visible = _add_light_camera_planes(data.directional_cull_planes[p_directional_light_id], lsource); + } + + if (data.light_culling_active) { + return visible; + } + return true; +} + +bool RenderingLightCuller::cull_directional_light(const RendererSceneCull::InstanceBounds &p_bound, int32_t p_directional_light_id) { + if (!data.is_active() || !is_caster_culling_active()) { + return true; + } + + ERR_FAIL_INDEX_V(p_directional_light_id, (int32_t)data.directional_cull_planes.size(), true); + + LightCullPlanes &cull_planes = data.directional_cull_planes[p_directional_light_id]; + + Vector3 mins = Vector3(p_bound.bounds[0], p_bound.bounds[1], p_bound.bounds[2]); + Vector3 maxs = Vector3(p_bound.bounds[3], p_bound.bounds[4], p_bound.bounds[5]); + AABB bb(mins, maxs - mins); + + real_t r_min, r_max; + for (int p = 0; p < cull_planes.num_cull_planes; p++) { + bb.project_range_in_plane(cull_planes.cull_planes[p], r_min, r_max); + if (r_min > 0.0f) { +#ifdef LIGHT_CULLER_DEBUG_DIRECTIONAL_LIGHT + cull_planes.rejected_count++; +#endif + + return false; + } + } + + return true; +} + +void RenderingLightCuller::cull_regular_light(PagedArray<RendererSceneCull::Instance *> &r_instance_shadow_cull_result) { + if (!data.is_active() || !is_caster_culling_active()) { + return; + } + + // If the light is out of range, no need to check anything, just return 0 casters. + // Ideally an out of range light should not even be drawn AT ALL (no shadow map, no PCF etc). + if (data.out_of_range) { + return; + } + + // Shorter local alias. + PagedArray<RendererSceneCull::Instance *> &list = r_instance_shadow_cull_result; + +#ifdef LIGHT_CULLER_DEBUG_LOGGING + uint32_t count_before = r_instance_shadow_cull_result.size(); +#endif + + // Go through all the casters in the list (the list will hopefully shrink as we go). + for (int n = 0; n < (int)list.size(); n++) { + // World space aabb. + const AABB &bb = list[n]->transformed_aabb; + +#ifdef LIGHT_CULLER_DEBUG_LOGGING + if (is_logging()) { + print_line("bb : " + String(bb)); + } +#endif + + real_t r_min, r_max; + bool show = true; + + for (int p = 0; p < data.regular_cull_planes.num_cull_planes; p++) { + // As we only need r_min, could this be optimized? + bb.project_range_in_plane(data.regular_cull_planes.cull_planes[p], r_min, r_max); + +#ifdef LIGHT_CULLER_DEBUG_LOGGING + if (is_logging()) { + print_line("\tplane " + itos(p) + " : " + String(data.regular_cull_planes.cull_planes[p]) + " r_min " + String(Variant(r_min)) + " r_max " + String(Variant(r_max))); + } +#endif + + if (r_min > 0.0f) { + show = false; + break; + } + } + + // Remove. + if (!show) { + list.remove_at_unordered(n); + + // Repeat this element next iteration of the loop as it has been removed and replaced by the last. + n--; + +#ifdef LIGHT_CULLER_DEBUG_REGULAR_LIGHT + data.regular_rejected_count++; +#endif + } + } + +#ifdef LIGHT_CULLER_DEBUG_LOGGING + uint32_t removed = r_instance_shadow_cull_result.size() - count_before; + if (removed) { + if (((data.debug_count) % 60) == 0) { + print_line("[" + itos(data.debug_count) + "] linear cull before " + itos(count_before) + " after " + itos(r_instance_shadow_cull_result.size())); + } + } +#endif +} + +void RenderingLightCuller::LightCullPlanes::add_cull_plane(const Plane &p) { + ERR_FAIL_COND(num_cull_planes >= MAX_CULL_PLANES); + cull_planes[num_cull_planes++] = p; +} + +// Directional lights are different to points, as the origin is infinitely in the distance, so the plane third +// points are derived differently. +bool RenderingLightCuller::add_light_camera_planes_directional(LightCullPlanes &r_cull_planes, const LightSource &p_light_source) { + uint32_t lookup = 0; + r_cull_planes.num_cull_planes = 0; + + // Directional light, we will use dot against the light direction to determine back facing planes. + for (int n = 0; n < 6; n++) { + float dot = data.frustum_planes[n].normal.dot(p_light_source.dir); + if (dot > 0.0f) { + lookup |= 1 << n; + + // Add backfacing camera frustum planes. + r_cull_planes.add_cull_plane(data.frustum_planes[n]); + } + } + + ERR_FAIL_COND_V(lookup >= LUT_SIZE, true); + + // Deal with special case... if the light is INSIDE the view frustum (i.e. all planes face away) + // then we will add the camera frustum planes to clip the light volume .. there is no need to + // render shadow casters outside the frustum as shadows can never re-enter the frustum. + + // Should never happen with directional light?? This may be able to be removed. + if (lookup == 63) { + r_cull_planes.num_cull_planes = 0; + for (int n = 0; n < data.frustum_planes.size(); n++) { + r_cull_planes.add_cull_plane(data.frustum_planes[n]); + } + + return true; + } + +// Each edge forms a plane. +#ifdef RENDERING_LIGHT_CULLER_CALCULATE_LUT + const LocalVector<uint8_t> &entry = _calculated_LUT[lookup]; + + // each edge forms a plane + int n_edges = entry.size() - 1; +#else + uint8_t *entry = &data.LUT_entries[lookup][0]; + int n_edges = data.LUT_entry_sizes[lookup] - 1; +#endif + + for (int e = 0; e < n_edges; e++) { + int i0 = entry[e]; + int i1 = entry[e + 1]; + const Vector3 &pt0 = data.frustum_points[i0]; + const Vector3 &pt1 = data.frustum_points[i1]; + + // Create a third point from the light direction. + Vector3 pt2 = pt0 - p_light_source.dir; + + // Create plane from 3 points. + Plane p(pt0, pt1, pt2); + r_cull_planes.add_cull_plane(p); + } + + // Last to 0 edge. + if (n_edges) { + int i0 = entry[n_edges]; // Last. + int i1 = entry[0]; // First. + + const Vector3 &pt0 = data.frustum_points[i0]; + const Vector3 &pt1 = data.frustum_points[i1]; + + // Create a third point from the light direction. + Vector3 pt2 = pt0 - p_light_source.dir; + + // Create plane from 3 points. + Plane p(pt0, pt1, pt2); + r_cull_planes.add_cull_plane(p); + } + +#ifdef LIGHT_CULLER_DEBUG_LOGGING + if (is_logging()) { + print_line("lcam.pos is " + String(p_light_source.pos)); + } +#endif + + return true; +} + +bool RenderingLightCuller::_add_light_camera_planes(LightCullPlanes &r_cull_planes, const LightSource &p_light_source) { + if (!data.is_active()) { + return true; + } + + // We should have called prepare_camera before this. + ERR_FAIL_COND_V(data.frustum_planes.size() != 6, true); + + switch (p_light_source.type) { + case LightSource::ST_SPOTLIGHT: + case LightSource::ST_OMNI: + break; + case LightSource::ST_DIRECTIONAL: + return add_light_camera_planes_directional(r_cull_planes, p_light_source); + break; + default: + return false; // not yet supported + break; + } + + // Start with 0 cull planes. + r_cull_planes.num_cull_planes = 0; + data.out_of_range = false; + uint32_t lookup = 0; + + // Find which of the camera planes are facing away from the light. + // We can also test for the situation where the light max range means it cannot + // affect the camera frustum. This is absolutely worth doing because it is relatively + // cheap, and if the entire light can be culled this can vastly improve performance + // (much more than just culling casters). + + // POINT LIGHT (spotlight, omni) + // Instead of using dot product to compare light direction to plane, we can simply + // find out which side of the plane the camera is on. By definition this marks the point at which the plane + // becomes invisible. + + // OMNIS + if (p_light_source.type == LightSource::ST_OMNI) { + for (int n = 0; n < 6; n++) { + float dist = data.frustum_planes[n].distance_to(p_light_source.pos); + if (dist < 0.0f) { + lookup |= 1 << n; + + // Add backfacing camera frustum planes. + r_cull_planes.add_cull_plane(data.frustum_planes[n]); + } else { + // Is the light out of range? + // This is one of the tests. If the point source is more than range distance from a frustum plane, it can't + // be seen. + if (dist >= p_light_source.range) { + // If the light is out of range, no need to do anything else, everything will be culled. + data.out_of_range = true; + return false; + } + } + } + } else { + // SPOTLIGHTs, more complex to cull. + Vector3 pos_end = p_light_source.pos + (p_light_source.dir * p_light_source.range); + + // This is the radius of the cone at distance 1. + float radius_at_dist_one = Math::tan(Math::deg_to_rad(p_light_source.angle)); + + // The worst case radius of the cone at the end point can be calculated + // (the radius will scale linearly with length along the cone). + float end_cone_radius = radius_at_dist_one * p_light_source.range; + + for (int n = 0; n < 6; n++) { + float dist = data.frustum_planes[n].distance_to(p_light_source.pos); + if (dist < 0.0f) { + // Either the plane is backfacing or we are inside the frustum. + lookup |= 1 << n; + + // Add backfacing camera frustum planes. + r_cull_planes.add_cull_plane(data.frustum_planes[n]); + } else { + // The light is in front of the plane. + + // Is the light out of range? + if (dist >= p_light_source.range) { + data.out_of_range = true; + return false; + } + + // For a spotlight, we can use an extra test + // at this point the cone start is in front of the plane... + // If the cone end point is further than the maximum possible distance to the plane + // we can guarantee that the cone does not cross the plane, and hence the cone + // is outside the frustum. + float dist_end = data.frustum_planes[n].distance_to(pos_end); + + if (dist_end >= end_cone_radius) { + data.out_of_range = true; + return false; + } + } + } + } + + // The lookup should be within the LUT, logic should prevent this. + ERR_FAIL_COND_V(lookup >= LUT_SIZE, true); + + // Deal with special case... if the light is INSIDE the view frustum (i.e. all planes face away) + // then we will add the camera frustum planes to clip the light volume .. there is no need to + // render shadow casters outside the frustum as shadows can never re-enter the frustum. + if (lookup == 63) { + r_cull_planes.num_cull_planes = 0; + for (int n = 0; n < data.frustum_planes.size(); n++) { + r_cull_planes.add_cull_plane(data.frustum_planes[n]); + } + + return true; + } + + // Each edge forms a plane. + uint8_t *entry = &data.LUT_entries[lookup][0]; + int n_edges = data.LUT_entry_sizes[lookup] - 1; + + for (int e = 0; e < n_edges; e++) { + int i0 = entry[e]; + int i1 = entry[e + 1]; + const Vector3 &pt0 = data.frustum_points[i0]; + const Vector3 &pt1 = data.frustum_points[i1]; + + // Create plane from 3 points. + Plane p(pt0, pt1, p_light_source.pos); + r_cull_planes.add_cull_plane(p); + } + + // Last to 0 edge. + if (n_edges) { + int i0 = entry[n_edges]; // Last. + int i1 = entry[0]; // First. + + const Vector3 &pt0 = data.frustum_points[i0]; + const Vector3 &pt1 = data.frustum_points[i1]; + + // Create plane from 3 points. + Plane p(pt0, pt1, p_light_source.pos); + r_cull_planes.add_cull_plane(p); + } + +#ifdef LIGHT_CULLER_DEBUG_LOGGING + if (is_logging()) { + print_line("lsource.pos is " + String(p_light_source.pos)); + } +#endif + + return true; +} + +bool RenderingLightCuller::prepare_camera(const Transform3D &p_cam_transform, const Projection &p_cam_matrix) { + data.debug_count++; + if (data.debug_count >= 120) { + data.debug_count = 0; + } + + // For debug flash off and on. +#ifdef LIGHT_CULLER_DEBUG_FLASH + if (!Engine::get_singleton()->is_editor_hint()) { + int dc = Engine::get_singleton()->get_process_frames() / LIGHT_CULLER_DEBUG_FLASH_FREQUENCY; + bool bnew_active; + bnew_active = (dc % 2) == 0; + + if (bnew_active != data.light_culling_active) { + data.light_culling_active = bnew_active; + print_line("switching light culler " + String(Variant(data.light_culling_active))); + } + } +#endif + + if (!data.is_active()) { + return false; + } + + // Get the camera frustum planes in world space. + data.frustum_planes = p_cam_matrix.get_projection_planes(p_cam_transform); + DEV_CHECK_ONCE(data.frustum_planes.size() == 6); + + data.regular_cull_planes.num_cull_planes = 0; + +#ifdef LIGHT_CULLER_DEBUG_DIRECTIONAL_LIGHT + if (is_logging()) { + for (uint32_t n = 0; n < data.directional_cull_planes.size(); n++) { + print_line("LightCuller directional light " + itos(n) + " rejected " + itos(data.directional_cull_planes[n].rejected_count) + " instances."); + } + } +#endif +#ifdef LIGHT_CULLER_DEBUG_REGULAR_LIGHT + if (data.regular_rejected_count) { + print_line("LightCuller regular lights rejected " + itos(data.regular_rejected_count) + " instances."); + } + data.regular_rejected_count = 0; +#endif + + data.directional_cull_planes.resize(0); + +#ifdef LIGHT_CULLER_DEBUG_LOGGING + if (is_logging()) { + for (int p = 0; p < 6; p++) { + print_line("plane " + itos(p) + " : " + String(data.frustum_planes[p])); + } + } +#endif + + // We want to calculate the frustum corners in a specific order. + const Projection::Planes intersections[8][3] = { + { Projection::PLANE_FAR, Projection::PLANE_LEFT, Projection::PLANE_TOP }, + { Projection::PLANE_FAR, Projection::PLANE_LEFT, Projection::PLANE_BOTTOM }, + { Projection::PLANE_FAR, Projection::PLANE_RIGHT, Projection::PLANE_TOP }, + { Projection::PLANE_FAR, Projection::PLANE_RIGHT, Projection::PLANE_BOTTOM }, + { Projection::PLANE_NEAR, Projection::PLANE_LEFT, Projection::PLANE_TOP }, + { Projection::PLANE_NEAR, Projection::PLANE_LEFT, Projection::PLANE_BOTTOM }, + { Projection::PLANE_NEAR, Projection::PLANE_RIGHT, Projection::PLANE_TOP }, + { Projection::PLANE_NEAR, Projection::PLANE_RIGHT, Projection::PLANE_BOTTOM }, + }; + + for (int i = 0; i < 8; i++) { + // 3 plane intersection, gives us a point. + bool res = data.frustum_planes[intersections[i][0]].intersect_3(data.frustum_planes[intersections[i][1]], data.frustum_planes[intersections[i][2]], &data.frustum_points[i]); + + // What happens with a zero frustum? NYI - deal with this. + ERR_FAIL_COND_V(!res, false); + +#ifdef LIGHT_CULLER_DEBUG_LOGGING + if (is_logging()) { + print_line("point " + itos(i) + " -> " + String(data.frustum_points[i])); + } +#endif + } + + return true; +} + +RenderingLightCuller::RenderingLightCuller() { + // Used to determine which frame to give debug output. + data.debug_count = -1; + + // Uncomment below to switch off light culler in the editor. + // data.caster_culling_active = Engine::get_singleton()->is_editor_hint() == false; + +#ifdef RENDERING_LIGHT_CULLER_CALCULATE_LUT + create_LUT(); +#endif +} + +/* clang-format off */ +uint8_t RenderingLightCuller::Data::LUT_entry_sizes[LUT_SIZE] = {0, 4, 4, 0, 4, 6, 6, 8, 4, 6, 6, 8, 6, 6, 6, 6, 4, 6, 6, 8, 0, 8, 8, 0, 6, 6, 6, 6, 8, 6, 6, 4, 4, 6, 6, 8, 6, 6, 6, 6, 0, 8, 8, 0, 8, 6, 6, 4, 6, 6, 6, 6, 8, 6, 6, 4, 8, 6, 6, 4, 0, 4, 4, 0, }; + +// The lookup table used to determine which edges form the silhouette of the camera frustum, +// depending on the viewing angle (defined by which camera planes are backward facing). +uint8_t RenderingLightCuller::Data::LUT_entries[LUT_SIZE][8] = { +{0, 0, 0, 0, 0, 0, 0, 0, }, +{7, 6, 4, 5, 0, 0, 0, 0, }, +{1, 0, 2, 3, 0, 0, 0, 0, }, +{0, 0, 0, 0, 0, 0, 0, 0, }, +{1, 5, 4, 0, 0, 0, 0, 0, }, +{1, 5, 7, 6, 4, 0, 0, 0, }, +{4, 0, 2, 3, 1, 5, 0, 0, }, +{5, 7, 6, 4, 0, 2, 3, 1, }, +{0, 4, 6, 2, 0, 0, 0, 0, }, +{0, 4, 5, 7, 6, 2, 0, 0, }, +{6, 2, 3, 1, 0, 4, 0, 0, }, +{2, 3, 1, 0, 4, 5, 7, 6, }, +{0, 1, 5, 4, 6, 2, 0, 0, }, +{0, 1, 5, 7, 6, 2, 0, 0, }, +{6, 2, 3, 1, 5, 4, 0, 0, }, +{2, 3, 1, 5, 7, 6, 0, 0, }, +{2, 6, 7, 3, 0, 0, 0, 0, }, +{2, 6, 4, 5, 7, 3, 0, 0, }, +{7, 3, 1, 0, 2, 6, 0, 0, }, +{3, 1, 0, 2, 6, 4, 5, 7, }, +{0, 0, 0, 0, 0, 0, 0, 0, }, +{2, 6, 4, 0, 1, 5, 7, 3, }, +{7, 3, 1, 5, 4, 0, 2, 6, }, +{0, 0, 0, 0, 0, 0, 0, 0, }, +{2, 0, 4, 6, 7, 3, 0, 0, }, +{2, 0, 4, 5, 7, 3, 0, 0, }, +{7, 3, 1, 0, 4, 6, 0, 0, }, +{3, 1, 0, 4, 5, 7, 0, 0, }, +{2, 0, 1, 5, 4, 6, 7, 3, }, +{2, 0, 1, 5, 7, 3, 0, 0, }, +{7, 3, 1, 5, 4, 6, 0, 0, }, +{3, 1, 5, 7, 0, 0, 0, 0, }, +{3, 7, 5, 1, 0, 0, 0, 0, }, +{3, 7, 6, 4, 5, 1, 0, 0, }, +{5, 1, 0, 2, 3, 7, 0, 0, }, +{7, 6, 4, 5, 1, 0, 2, 3, }, +{3, 7, 5, 4, 0, 1, 0, 0, }, +{3, 7, 6, 4, 0, 1, 0, 0, }, +{5, 4, 0, 2, 3, 7, 0, 0, }, +{7, 6, 4, 0, 2, 3, 0, 0, }, +{0, 0, 0, 0, 0, 0, 0, 0, }, +{3, 7, 6, 2, 0, 4, 5, 1, }, +{5, 1, 0, 4, 6, 2, 3, 7, }, +{0, 0, 0, 0, 0, 0, 0, 0, }, +{3, 7, 5, 4, 6, 2, 0, 1, }, +{3, 7, 6, 2, 0, 1, 0, 0, }, +{5, 4, 6, 2, 3, 7, 0, 0, }, +{7, 6, 2, 3, 0, 0, 0, 0, }, +{3, 2, 6, 7, 5, 1, 0, 0, }, +{3, 2, 6, 4, 5, 1, 0, 0, }, +{5, 1, 0, 2, 6, 7, 0, 0, }, +{1, 0, 2, 6, 4, 5, 0, 0, }, +{3, 2, 6, 7, 5, 4, 0, 1, }, +{3, 2, 6, 4, 0, 1, 0, 0, }, +{5, 4, 0, 2, 6, 7, 0, 0, }, +{6, 4, 0, 2, 0, 0, 0, 0, }, +{3, 2, 0, 4, 6, 7, 5, 1, }, +{3, 2, 0, 4, 5, 1, 0, 0, }, +{5, 1, 0, 4, 6, 7, 0, 0, }, +{1, 0, 4, 5, 0, 0, 0, 0, }, +{0, 0, 0, 0, 0, 0, 0, 0, }, +{3, 2, 0, 1, 0, 0, 0, 0, }, +{5, 4, 6, 7, 0, 0, 0, 0, }, +{0, 0, 0, 0, 0, 0, 0, 0, }, +}; + +/* clang-format on */ + +#ifdef RENDERING_LIGHT_CULLER_CALCULATE_LUT + +// See e.g. http://lspiroengine.com/?p=153 for reference. +// Principles are the same, but differences to the article: +// * Order of planes / points is different in Godot. +// * We use a lookup table at runtime. +void RenderingLightCuller::create_LUT() { + // Each pair of planes that are opposite can have an edge. + for (int plane_0 = 0; plane_0 < PLANE_TOTAL; plane_0++) { + // For each neighbour of the plane. + PlaneOrder neighs[4]; + get_neighbouring_planes((PlaneOrder)plane_0, neighs); + + for (int n = 0; n < 4; n++) { + int plane_1 = neighs[n]; + + // If these are opposite we need to add the 2 points they share. + PointOrder pts[2]; + get_corners_of_planes((PlaneOrder)plane_0, (PlaneOrder)plane_1, pts); + + add_LUT(plane_0, plane_1, pts); + } + } + + for (uint32_t n = 0; n < LUT_SIZE; n++) { + compact_LUT_entry(n); + } + + debug_print_LUT(); + debug_print_LUT_as_table(); +} + +// we can pre-create the entire LUT and store it hard coded as a static inside the executable! +// it is only small in size, 64 entries with max 8 bytes per entry +void RenderingLightCuller::debug_print_LUT_as_table() { + print_line("\nLIGHT VOLUME TABLE BEGIN\n"); + + print_line("Copy this to LUT_entry_sizes:\n"); + String sz = "{"; + for (int n = 0; n < LUT_SIZE; n++) { + const LocalVector<uint8_t> &entry = _calculated_LUT[n]; + + sz += itos(entry.size()) + ", "; + } + sz += "}"; + print_line(sz); + print_line("\nCopy this to LUT_entries:\n"); + + for (int n = 0; n < LUT_SIZE; n++) { + const LocalVector<uint8_t> &entry = _calculated_LUT[n]; + + String sz = "{"; + + // First is the number of points in the entry. + int s = entry.size(); + + for (int p = 0; p < 8; p++) { + if (p < s) + sz += itos(entry[p]); + else + sz += "0"; // just a spacer + + sz += ", "; + } + + sz += "},"; + print_line(sz); + } + + print_line("\nLIGHT VOLUME TABLE END\n"); +} + +void RenderingLightCuller::debug_print_LUT() { + for (int n = 0; n < LUT_SIZE; n++) { + String sz; + sz = "LUT" + itos(n) + ":\t"; + + sz += Data::plane_bitfield_to_string(n); + print_line(sz); + + const LocalVector<uint8_t> &entry = _calculated_LUT[n]; + + sz = "\t" + string_LUT_entry(entry); + + print_line(sz); + } +} + +String RenderingLightCuller::string_LUT_entry(const LocalVector<uint8_t> &p_entry) { + String string; + + for (uint32_t n = 0; n < p_entry.size(); n++) { + uint8_t val = p_entry[n]; + DEV_ASSERT(val < 8); + const char *sz_point = Data::string_points[val]; + string += sz_point; + string += ", "; + } + + return string; +} + +String RenderingLightCuller::debug_string_LUT_entry(const LocalVector<uint8_t> &p_entry, bool p_pair) { + String string; + + for (uint32_t i = 0; i < p_entry.size(); i++) { + int pt_order = p_entry[i]; + if (p_pair && ((i % 2) == 0)) { + string += itos(pt_order) + "-"; + } else { + string += itos(pt_order) + ", "; + } + } + + return string; +} + +void RenderingLightCuller::add_LUT(int p_plane_0, int p_plane_1, PointOrder p_pts[2]) { + // Note that some entries to the LUT will be "impossible" situations, + // because it contains all combinations of plane flips. + uint32_t bit0 = 1 << p_plane_0; + uint32_t bit1 = 1 << p_plane_1; + + // All entries of the LUT that have plane 0 set and plane 1 not set. + for (uint32_t n = 0; n < 64; n++) { + // If bit0 not set... + if (!(n & bit0)) + continue; + + // If bit1 set... + if (n & bit1) + continue; + + // Meets criteria. + add_LUT_entry(n, p_pts); + } +} + +void RenderingLightCuller::add_LUT_entry(uint32_t p_entry_id, PointOrder p_pts[2]) { + DEV_ASSERT(p_entry_id < LUT_SIZE); + LocalVector<uint8_t> &entry = _calculated_LUT[p_entry_id]; + + entry.push_back(p_pts[0]); + entry.push_back(p_pts[1]); +} + +void RenderingLightCuller::compact_LUT_entry(uint32_t p_entry_id) { + DEV_ASSERT(p_entry_id < LUT_SIZE); + LocalVector<uint8_t> &entry = _calculated_LUT[p_entry_id]; + + int num_pairs = entry.size() / 2; + + if (num_pairs == 0) + return; + + LocalVector<uint8_t> temp; + + String string; + string = "Compact LUT" + itos(p_entry_id) + ":\t"; + string += debug_string_LUT_entry(entry, true); + print_line(string); + + // Add first pair. + temp.push_back(entry[0]); + temp.push_back(entry[1]); + unsigned int BFpairs = 1; + + string = debug_string_LUT_entry(temp) + " -> "; + print_line(string); + + // Attempt to add a pair each time. + for (int done = 1; done < num_pairs; done++) { + string = "done " + itos(done) + ": "; + // Find a free pair. + for (int p = 1; p < num_pairs; p++) { + unsigned int bit = 1 << p; + // Is it done already? + if (BFpairs & bit) + continue; + + // There must be at least 1 free pair. + // Attempt to add. + int a = entry[p * 2]; + int b = entry[(p * 2) + 1]; + + string += "[" + itos(a) + "-" + itos(b) + "], "; + + int found_a = temp.find(a); + int found_b = temp.find(b); + + // Special case, if they are both already in the list, no need to add + // as this is a link from the tail to the head of the list. + if ((found_a != -1) && (found_b != -1)) { + string += "foundAB link " + itos(found_a) + ", " + itos(found_b) + " "; + BFpairs |= bit; + goto found; + } + + // Find a. + if (found_a != -1) { + string += "foundA " + itos(found_a) + " "; + temp.insert(found_a + 1, b); + BFpairs |= bit; + goto found; + } + + // Find b. + if (found_b != -1) { + string += "foundB " + itos(found_b) + " "; + temp.insert(found_b, a); + BFpairs |= bit; + goto found; + } + + } // Check each pair for adding. + + // If we got here before finding a link, the whole set of planes is INVALID + // e.g. far and near plane only, does not create continuous sillouhette of edges. + print_line("\tINVALID"); + entry.clear(); + return; + + found:; + print_line(string); + string = "\ttemp now : " + debug_string_LUT_entry(temp); + print_line(string); + } + + // temp should now be the sorted entry .. delete the old one and replace by temp. + entry.clear(); + entry = temp; +} + +void RenderingLightCuller::get_neighbouring_planes(PlaneOrder p_plane, PlaneOrder r_neigh_planes[4]) const { + // Table of neighbouring planes to each. + static const PlaneOrder neigh_table[PLANE_TOTAL][4] = { + { // LSM_FP_NEAR + PLANE_LEFT, + PLANE_RIGHT, + PLANE_TOP, + PLANE_BOTTOM }, + { // LSM_FP_FAR + PLANE_LEFT, + PLANE_RIGHT, + PLANE_TOP, + PLANE_BOTTOM }, + { // LSM_FP_LEFT + PLANE_TOP, + PLANE_BOTTOM, + PLANE_NEAR, + PLANE_FAR }, + { // LSM_FP_TOP + PLANE_LEFT, + PLANE_RIGHT, + PLANE_NEAR, + PLANE_FAR }, + { // LSM_FP_RIGHT + PLANE_TOP, + PLANE_BOTTOM, + PLANE_NEAR, + PLANE_FAR }, + { // LSM_FP_BOTTOM + PLANE_LEFT, + PLANE_RIGHT, + PLANE_NEAR, + PLANE_FAR }, + }; + + for (int n = 0; n < 4; n++) { + r_neigh_planes[n] = neigh_table[p_plane][n]; + } +} + +// Given two planes, returns the two points shared by those planes. The points are always +// returned in counter-clockwise order, assuming the first input plane is facing towards +// the viewer. + +// param p_plane_a The plane facing towards the viewer. +// param p_plane_b A plane neighboring p_plane_a. +// param r_points An array of exactly two elements to be filled with the indices of the points +// on return. + +void RenderingLightCuller::get_corners_of_planes(PlaneOrder p_plane_a, PlaneOrder p_plane_b, PointOrder r_points[2]) const { + static const PointOrder fp_table[PLANE_TOTAL][PLANE_TOTAL][2] = { + { + // LSM_FP_NEAR + { + // LSM_FP_NEAR + PT_NEAR_LEFT_TOP, PT_NEAR_RIGHT_TOP, // Invalid combination. + }, + { + // LSM_FP_FAR + PT_FAR_RIGHT_TOP, PT_FAR_LEFT_TOP, // Invalid combination. + }, + { + // LSM_FP_LEFT + PT_NEAR_LEFT_TOP, + PT_NEAR_LEFT_BOTTOM, + }, + { + // LSM_FP_TOP + PT_NEAR_RIGHT_TOP, + PT_NEAR_LEFT_TOP, + }, + { + // LSM_FP_RIGHT + PT_NEAR_RIGHT_BOTTOM, + PT_NEAR_RIGHT_TOP, + }, + { + // LSM_FP_BOTTOM + PT_NEAR_LEFT_BOTTOM, + PT_NEAR_RIGHT_BOTTOM, + }, + }, + + { + // LSM_FP_FAR + { + // LSM_FP_NEAR + PT_FAR_LEFT_TOP, PT_FAR_RIGHT_TOP, // Invalid combination. + }, + { + // LSM_FP_FAR + PT_FAR_RIGHT_TOP, PT_FAR_LEFT_TOP, // Invalid combination. + }, + { + // LSM_FP_LEFT + PT_FAR_LEFT_BOTTOM, + PT_FAR_LEFT_TOP, + }, + { + // LSM_FP_TOP + PT_FAR_LEFT_TOP, + PT_FAR_RIGHT_TOP, + }, + { + // LSM_FP_RIGHT + PT_FAR_RIGHT_TOP, + PT_FAR_RIGHT_BOTTOM, + }, + { + // LSM_FP_BOTTOM + PT_FAR_RIGHT_BOTTOM, + PT_FAR_LEFT_BOTTOM, + }, + }, + + { + // LSM_FP_LEFT + { + // LSM_FP_NEAR + PT_NEAR_LEFT_BOTTOM, + PT_NEAR_LEFT_TOP, + }, + { + // LSM_FP_FAR + PT_FAR_LEFT_TOP, + PT_FAR_LEFT_BOTTOM, + }, + { + // LSM_FP_LEFT + PT_FAR_LEFT_BOTTOM, PT_FAR_LEFT_BOTTOM, // Invalid combination. + }, + { + // LSM_FP_TOP + PT_NEAR_LEFT_TOP, + PT_FAR_LEFT_TOP, + }, + { + // LSM_FP_RIGHT + PT_FAR_LEFT_BOTTOM, PT_FAR_LEFT_BOTTOM, // Invalid combination. + }, + { + // LSM_FP_BOTTOM + PT_FAR_LEFT_BOTTOM, + PT_NEAR_LEFT_BOTTOM, + }, + }, + + { + // LSM_FP_TOP + { + // LSM_FP_NEAR + PT_NEAR_LEFT_TOP, + PT_NEAR_RIGHT_TOP, + }, + { + // LSM_FP_FAR + PT_FAR_RIGHT_TOP, + PT_FAR_LEFT_TOP, + }, + { + // LSM_FP_LEFT + PT_FAR_LEFT_TOP, + PT_NEAR_LEFT_TOP, + }, + { + // LSM_FP_TOP + PT_NEAR_LEFT_TOP, PT_FAR_LEFT_TOP, // Invalid combination. + }, + { + // LSM_FP_RIGHT + PT_NEAR_RIGHT_TOP, + PT_FAR_RIGHT_TOP, + }, + { + // LSM_FP_BOTTOM + PT_FAR_LEFT_BOTTOM, PT_NEAR_LEFT_BOTTOM, // Invalid combination. + }, + }, + + { + // LSM_FP_RIGHT + { + // LSM_FP_NEAR + PT_NEAR_RIGHT_TOP, + PT_NEAR_RIGHT_BOTTOM, + }, + { + // LSM_FP_FAR + PT_FAR_RIGHT_BOTTOM, + PT_FAR_RIGHT_TOP, + }, + { + // LSM_FP_LEFT + PT_FAR_RIGHT_BOTTOM, PT_FAR_RIGHT_BOTTOM, // Invalid combination. + }, + { + // LSM_FP_TOP + PT_FAR_RIGHT_TOP, + PT_NEAR_RIGHT_TOP, + }, + { + // LSM_FP_RIGHT + PT_FAR_RIGHT_BOTTOM, PT_FAR_RIGHT_BOTTOM, // Invalid combination. + }, + { + // LSM_FP_BOTTOM + PT_NEAR_RIGHT_BOTTOM, + PT_FAR_RIGHT_BOTTOM, + }, + }, + + // == + + // P_NEAR, + // P_FAR, + // P_LEFT, + // P_TOP, + // P_RIGHT, + // P_BOTTOM, + + { + // LSM_FP_BOTTOM + { + // LSM_FP_NEAR + PT_NEAR_RIGHT_BOTTOM, + PT_NEAR_LEFT_BOTTOM, + }, + { + // LSM_FP_FAR + PT_FAR_LEFT_BOTTOM, + PT_FAR_RIGHT_BOTTOM, + }, + { + // LSM_FP_LEFT + PT_NEAR_LEFT_BOTTOM, + PT_FAR_LEFT_BOTTOM, + }, + { + // LSM_FP_TOP + PT_NEAR_LEFT_BOTTOM, PT_FAR_LEFT_BOTTOM, // Invalid combination. + }, + { + // LSM_FP_RIGHT + PT_FAR_RIGHT_BOTTOM, + PT_NEAR_RIGHT_BOTTOM, + }, + { + // LSM_FP_BOTTOM + PT_FAR_LEFT_BOTTOM, PT_NEAR_LEFT_BOTTOM, // Invalid combination. + }, + }, + + // == + + }; + r_points[0] = fp_table[p_plane_a][p_plane_b][0]; + r_points[1] = fp_table[p_plane_a][p_plane_b][1]; +} + +#endif diff --git a/servers/rendering/rendering_light_culler.h b/servers/rendering/rendering_light_culler.h new file mode 100644 index 0000000000..602543850a --- /dev/null +++ b/servers/rendering/rendering_light_culler.h @@ -0,0 +1,248 @@ +/**************************************************************************/ +/* rendering_light_culler.h */ +/**************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/**************************************************************************/ +/* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */ +/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. */ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/**************************************************************************/ + +#ifndef RENDERING_LIGHT_CULLER_H +#define RENDERING_LIGHT_CULLER_H + +#include "core/math/plane.h" +#include "core/math/vector3.h" +#include "renderer_scene_cull.h" + +struct Projection; +struct Transform3D; + +// For testing performance improvements from the LightCuller: +// Uncomment LIGHT_CULLER_DEBUG_FLASH and it will turn the culler +// on and off every LIGHT_CULLER_DEBUG_FLASH_FREQUENCY camera prepares. +// Uncomment LIGHT_CULLER_DEBUG_LOGGING to get periodic print of the number of casters culled before / after. +// Uncomment LIGHT_CULLER_DEBUG_DIRECTIONAL_LIGHT to get periodic print of the number of casters culled for the directional light.. + +// #define LIGHT_CULLER_DEBUG_LOGGING +// #define LIGHT_CULLER_DEBUG_DIRECTIONAL_LIGHT +// #define LIGHT_CULLER_DEBUG_REGULAR_LIGHT +// #define LIGHT_CULLER_DEBUG_FLASH +#define LIGHT_CULLER_DEBUG_FLASH_FREQUENCY 1024 +//////////////////////////////////////////////////////////////////////////////////////////////// + +// The code to generate the lookup table is included but commented out. +// This may be useful for debugging / regenerating the LUT in the future, +// especially if the order of planes changes. +// When this define is set, the generated lookup table will be printed to debug output. +// The generated lookup table can be copy pasted +// straight to LUT_entry_sizes and LUT_entries. +// See the referenced article for explanation. +// #define RENDERING_LIGHT_CULLER_CALCULATE_LUT + +//////////////////////////////////////////////////////////////////////////////////////////////// +// This define will be set automatically depending on earlier defines, you can leave this as is. +#if defined(LIGHT_CULLER_DEBUG_LOGGING) || defined(RENDERING_LIGHT_CULLER_CALCULATE_LUT) +#define RENDERING_LIGHT_CULLER_DEBUG_STRINGS +#endif + +// Culls shadow casters that can't cast shadows into the camera frustum. +class RenderingLightCuller { +public: + RenderingLightCuller(); + +private: + class LightSource { + public: + enum SourceType { + ST_UNKNOWN, + ST_DIRECTIONAL, + ST_SPOTLIGHT, + ST_OMNI, + }; + + LightSource() { + type = ST_UNKNOWN; + angle = 0.0f; + range = FLT_MAX; + } + + // All in world space, culling done in world space. + Vector3 pos; + Vector3 dir; + SourceType type; + + float angle; // For spotlight. + float range; + }; + + // Same order as godot. + enum PlaneOrder { + PLANE_NEAR, + PLANE_FAR, + PLANE_LEFT, + PLANE_TOP, + PLANE_RIGHT, + PLANE_BOTTOM, + PLANE_TOTAL, + }; + + // Same order as godot. + enum PointOrder { + PT_FAR_LEFT_TOP, + PT_FAR_LEFT_BOTTOM, + PT_FAR_RIGHT_TOP, + PT_FAR_RIGHT_BOTTOM, + PT_NEAR_LEFT_TOP, + PT_NEAR_LEFT_BOTTOM, + PT_NEAR_RIGHT_TOP, + PT_NEAR_RIGHT_BOTTOM, + }; + + // 6 bits, 6 planes. + enum { + NUM_CAM_PLANES = 6, + NUM_CAM_POINTS = 8, + MAX_CULL_PLANES = 17, + LUT_SIZE = 64, + }; + +public: + // Before each pass with a different camera, you must call this so the culler can pre-create + // the camera frustum planes and corner points in world space which are used for the culling. + bool prepare_camera(const Transform3D &p_cam_transform, const Projection &p_cam_matrix); + + // REGULAR LIGHTS (SPOT, OMNI). + // These are prepared then used for culling one by one, single threaded. + // prepare_regular_light() returns false if the entire light is culled (i.e. there is no intersection between the light and the view frustum). + bool prepare_regular_light(const RendererSceneCull::Instance &p_instance) { return _prepare_light(p_instance, -1); } + + // Cull according to the regular light planes that were setup in the previous call to prepare_regular_light. + void cull_regular_light(PagedArray<RendererSceneCull::Instance *> &r_instance_shadow_cull_result); + + // Directional lights are prepared in advance, and can be culled multithreaded chopping and changing between + // different directional_light_id. + void prepare_directional_light(const RendererSceneCull::Instance *p_instance, int32_t p_directional_light_id); + + // Return false if the instance is to be culled. + bool cull_directional_light(const RendererSceneCull::InstanceBounds &p_bound, int32_t p_directional_light_id); + + // Can turn on and off from the engine if desired. + void set_caster_culling_active(bool p_active) { data.caster_culling_active = p_active; } + void set_light_culling_active(bool p_active) { data.light_culling_active = p_active; } + +private: + struct LightCullPlanes { + void add_cull_plane(const Plane &p); + Plane cull_planes[MAX_CULL_PLANES]; + int num_cull_planes = 0; +#ifdef LIGHT_CULLER_DEBUG_DIRECTIONAL_LIGHT + uint32_t rejected_count = 0; +#endif + }; + + bool _prepare_light(const RendererSceneCull::Instance &p_instance, int32_t p_directional_light_id = -1); + + // Internal version uses LightSource. + bool _add_light_camera_planes(LightCullPlanes &r_cull_planes, const LightSource &p_light_source); + + // Directional light gives parallel culling planes (as opposed to point lights). + bool add_light_camera_planes_directional(LightCullPlanes &r_cull_planes, const LightSource &p_light_source); + + // Is the light culler active? maybe not in the editor... + bool is_caster_culling_active() const { return data.caster_culling_active; } + bool is_light_culling_active() const { return data.light_culling_active; } + + // Do we want to log some debug output? + bool is_logging() const { return data.debug_count == 0; } + + struct Data { + // Camera frustum planes (world space) - order ePlane. + Vector<Plane> frustum_planes; + + // Camera frustum corners (world space) - order ePoint. + Vector3 frustum_points[NUM_CAM_POINTS]; + + // Master can have multiple directional lights. + // These need to store their own cull planes individually, as master + // chops and changes between culling different lights + // instead of doing one by one, and we don't want to prepare + // lights multiple times per frame. + LocalVector<LightCullPlanes> directional_cull_planes; + + // Single threaded cull planes for regular lights + // (OMNI, SPOT). These lights reuse the same set of cull plane data. + LightCullPlanes regular_cull_planes; + +#ifdef LIGHT_CULLER_DEBUG_REGULAR_LIGHT + uint32_t regular_rejected_count = 0; +#endif + // The whole regular light can be out of range of the view frustum, in which case all casters should be culled. + bool out_of_range = false; + +#ifdef RENDERING_LIGHT_CULLER_DEBUG_STRINGS + static String plane_bitfield_to_string(unsigned int BF); + // Names of the plane and point enums, useful for debugging. + static const char *string_planes[]; + static const char *string_points[]; +#endif + + // Precalculated look up table. + static uint8_t LUT_entry_sizes[LUT_SIZE]; + static uint8_t LUT_entries[LUT_SIZE][8]; + + bool caster_culling_active = true; + bool light_culling_active = true; + + // Light culling is a basic on / off switch. + // Caster culling only works if light culling is also on. + bool is_active() const { return light_culling_active; } + + // Ideally a frame counter, but for ease of implementation + // this is just incremented on each prepare_camera. + // used to turn on and off debugging features. + int debug_count = -1; + } data; + + // This functionality is not required in general use (and is compiled out), + // as the lookup table can normally be hard coded + // (provided order of planes etc does not change). + // It is provided for debugging / future maintenance. +#ifdef RENDERING_LIGHT_CULLER_CALCULATE_LUT + void get_neighbouring_planes(PlaneOrder p_plane, PlaneOrder r_neigh_planes[4]) const; + void get_corners_of_planes(PlaneOrder p_plane_a, PlaneOrder p_plane_b, PointOrder r_points[2]) const; + void create_LUT(); + void compact_LUT_entry(uint32_t p_entry_id); + void debug_print_LUT(); + void debug_print_LUT_as_table(); + void add_LUT(int p_plane_0, int p_plane_1, PointOrder p_pts[2]); + void add_LUT_entry(uint32_t p_entry_id, PointOrder p_pts[2]); + String debug_string_LUT_entry(const LocalVector<uint8_t> &p_entry, bool p_pair = false); + String string_LUT_entry(const LocalVector<uint8_t> &p_entry); + + // Contains a list of points for each combination of plane facing directions. + LocalVector<uint8_t> _calculated_LUT[LUT_SIZE]; +#endif +}; + +#endif // RENDERING_LIGHT_CULLER_H |