Return 'loops' occlusion culler under a setting (#13352)

* Add occlusion_culler setting to minetest.conf.example
* Add raytraced occlusion culling to 'loops' algorithm

---------

Co-authored-by: sfan5 <sfan5@live.de>

5 files changed, 30 insertions, 2 deletions

diff --git a/builtin/settingtypes.txt b/builtin/settingtypes.txt
index 14d4df179..ea90c30d0 100644
--- a/builtin/settingtypes.txt
+++ b/builtin/settingtypes.txt
@@ -629,6 +629,11 @@ update_last_checked (Last update check) string
 #    Ex: 5.5.0 is 005005000
 update_last_known (Last known version update) int 0
 
+#    Type of occlusion_culler
+#    "loops" is the legacy algorithm with nested loops and O(N^3) complexity
+#    "bfs" is the new algorithm based on breadth-first-search and side culling
+occlusion_culler (Occlusion Culler) enum bfs bfs,loops
+
 #    Use raytraced occlusion culling in the new culler.
 #	 This flag enables use of raytraced occlusion culling test for
 #    client mesh sizes smaller than 4x4x4 map blocks.
diff --git a/minetest.conf.example b/minetest.conf.example
index b69d7764e..7f79ca493 100644
--- a/minetest.conf.example
+++ b/minetest.conf.example
@@ -695,6 +695,12 @@
 #    type: int
 # update_last_known = 0
 
+#    Type of occlusion_culler
+#    "loops" is the legacy algorithm with nested loops and O(N^3) complexity
+#    "bfs" is the new algorithm based on breadth-first-search and side culling
+#    type: enum values: bfs, loops
+# occlusion_culler = bfs
+
 #    Use raytraced occlusion culling in the new culler.
 #    This flag enables use of raytraced occlusion culling test
 #    type: bool
diff --git a/src/client/clientmap.cpp b/src/client/clientmap.cpp
index e19ef0f53..e876c9efc 100644
--- a/src/client/clientmap.cpp
+++ b/src/client/clientmap.cpp
@@ -103,18 +103,23 @@ ClientMap::ClientMap(
 	m_cache_bilinear_filter   = g_settings->getBool("bilinear_filter");
 	m_cache_anistropic_filter = g_settings->getBool("anisotropic_filter");
 	m_cache_transparency_sorting_distance = g_settings->getU16("transparency_sorting_distance");
+	m_loops_occlusion_culler = g_settings->get("occlusion_culler") == "loops";
+	g_settings->registerChangedCallback("occlusion_culler", on_settings_changed, this);
 	m_enable_raytraced_culling = g_settings->getBool("enable_raytraced_culling");
 	g_settings->registerChangedCallback("enable_raytraced_culling", on_settings_changed, this);
 }
 
 void ClientMap::onSettingChanged(const std::string &name)
 {
+	if (name == "occlusion_culler")
+		m_loops_occlusion_culler = g_settings->get("occlusion_culler") == "loops";
 	if (name == "enable_raytraced_culling")
 		m_enable_raytraced_culling = g_settings->getBool("enable_raytraced_culling");
 }
 
 ClientMap::~ClientMap()
 {
+	g_settings->deregisterChangedCallback("occlusion_culler", on_settings_changed, this);
 	g_settings->deregisterChangedCallback("enable_raytraced_culling", on_settings_changed, this);
 }
 
@@ -298,7 +303,7 @@ void ClientMap::updateDrawList()
 	 When range_all is enabled, enumerate all blocks visible in the
 	 frustum and display them.
 	 */
-	if (m_control.range_all) {
+	if (m_control.range_all || m_loops_occlusion_culler) {
 		MapBlockVect sectorblocks;
 
 		for (auto &sector_it : m_sectors) {
@@ -339,6 +344,14 @@ void ClientMap::updateDrawList()
 					continue;
 				}
 
+				// Raytraced occlusion culling - send rays from the camera to the block's corners
+				if (occlusion_culling_enabled && m_enable_raytraced_culling &&
+						mesh &&
+						isMeshOccluded(block, mesh_grid.cell_size, cam_pos_nodes)) {
+					blocks_occlusion_culled++;
+					continue;
+				}
+
 				if (mesh_grid.cell_size > 1) {
 					// Block meshes are stored in the corner block of a chunk
 					// (where all coordinate are divisible by the chunk size)
@@ -582,6 +595,9 @@ void ClientMap::updateDrawList()
 
 void ClientMap::touchMapBlocks()
 {
+	if (!m_loops_occlusion_culler)
+		return;
+
 	v3s16 cam_pos_nodes = floatToInt(m_camera_position, BS);
 
 	v3s16 p_blocks_min;
diff --git a/src/client/clientmap.h b/src/client/clientmap.h
index b9f7b4dfa..4d565ec9f 100644
--- a/src/client/clientmap.h
+++ b/src/client/clientmap.h
@@ -215,6 +215,6 @@ private:
 	bool m_cache_anistropic_filter;
 	u16 m_cache_transparency_sorting_distance;
 
-	bool m_new_occlusion_culler;
+	bool m_loops_occlusion_culler;
 	bool m_enable_raytraced_culling;
 };
diff --git a/src/defaultsettings.cpp b/src/defaultsettings.cpp
index e2457ce78..01ee1a8a1 100644
--- a/src/defaultsettings.cpp
+++ b/src/defaultsettings.cpp
@@ -65,6 +65,7 @@ void set_default_settings()
 	settings->setDefault("max_out_chat_queue_size", "20");
 	settings->setDefault("pause_on_lost_focus", "false");
 	settings->setDefault("enable_split_login_register", "true");
+	settings->setDefault("occlusion_culler", "bfs");
 	settings->setDefault("enable_raytraced_culling", "true");
 	settings->setDefault("chat_weblink_color", "#8888FF");