Client map: do frustum culling via planes (#12710)

8 files changed, 113 insertions, 42 deletions

diff --git a/src/client/camera.cpp b/src/client/camera.cpp
index 994497224..e2f50e4a6 100644
--- a/src/client/camera.cpp
+++ b/src/client/camera.cpp
@@ -38,6 +38,7 @@ with this program; if not, write to the Free Software Foundation, Inc.,
 #include "fontengine.h"
 #include "script/scripting_client.h"
 #include "gettext.h"
+#include <SViewFrustum.h>
 
 #define CAMERA_OFFSET_STEP 200
 #define WIELDMESH_OFFSET_X 55.0f
@@ -318,6 +319,9 @@ void Camera::update(LocalPlayer* player, f32 frametime, f32 tool_reload_ratio)
 	v3f old_player_position = m_playernode->getPosition();
 	v3f player_position = player->getPosition();
 
+	f32 yaw = player->getYaw();
+	f32 pitch = player->getPitch();
+
 	// This is worse than `LocalPlayer::getPosition()` but
 	// mods expect the player head to be at the parent's position
 	// plus eye height.
@@ -342,7 +346,7 @@ void Camera::update(LocalPlayer* player, f32 frametime, f32 tool_reload_ratio)
 
 	// Set player node transformation
 	m_playernode->setPosition(player_position);
-	m_playernode->setRotation(v3f(0, -1 * player->getYaw(), 0));
+	m_playernode->setRotation(v3f(0, -1 * yaw, 0));
 	m_playernode->updateAbsolutePosition();
 
 	// Get camera tilt timer (hurt animation)
@@ -379,7 +383,7 @@ void Camera::update(LocalPlayer* player, f32 frametime, f32 tool_reload_ratio)
 		// Set head node transformation
 		eye_offset.Y += cameratilt * -player->hurt_tilt_strength + fall_bobbing;
 		m_headnode->setPosition(eye_offset);
-		m_headnode->setRotation(v3f(player->getPitch(), 0,
+		m_headnode->setRotation(v3f(pitch, 0,
 			cameratilt * player->hurt_tilt_strength));
 		m_headnode->updateAbsolutePosition();
 	}
@@ -463,6 +467,7 @@ void Camera::update(LocalPlayer* player, f32 frametime, f32 tool_reload_ratio)
 
 	// Set camera node transformation
 	m_cameranode->setPosition(my_cp-intToFloat(m_camera_offset, BS));
+	m_cameranode->updateAbsolutePosition();
 	m_cameranode->setUpVector(abs_cam_up);
 	// *100.0 helps in large map coordinates
 	m_cameranode->setTarget(my_cp-intToFloat(m_camera_offset, BS) + 100 * m_camera_direction);
@@ -511,8 +516,11 @@ void Camera::update(LocalPlayer* player, f32 frametime, f32 tool_reload_ratio)
 	m_cameranode->setAspectRatio(m_aspect);
 	m_cameranode->setFOV(m_fov_y);
 
+	// Make new matrices and frustum
+	m_cameranode->updateMatrices();
+
 	if (m_arm_inertia)
-		addArmInertia(player->getYaw());
+		addArmInertia(yaw);
 
 	// Position the wielded item
 	//v3f wield_position = v3f(45, -35, 65);
@@ -643,6 +651,7 @@ void Camera::drawWieldedTool(irr::core::matrix4* translation)
 		irr::core::vector3df camera_pos =
 				(startMatrix * *translation).getTranslation();
 		cam->setPosition(camera_pos);
+		cam->updateAbsolutePosition();
 		cam->setTarget(focusPoint);
 	}
 	m_wieldmgr->drawAll();
@@ -704,3 +713,15 @@ void Camera::removeNametag(Nametag *nametag)
 	m_nametags.remove(nametag);
 	delete nametag;
 }
+
+std::array<core::plane3d<f32>, 4> Camera::getFrustumCullPlanes() const
+{
+	using irr::scene::SViewFrustum;
+	const auto &frustum_planes = m_cameranode->getViewFrustum()->planes;
+	return {
+		frustum_planes[SViewFrustum::VF_LEFT_PLANE],
+		frustum_planes[SViewFrustum::VF_RIGHT_PLANE],
+		frustum_planes[SViewFrustum::VF_BOTTOM_PLANE],
+		frustum_planes[SViewFrustum::VF_TOP_PLANE],
+	};
+}
diff --git a/src/client/camera.h b/src/client/camera.h
index cbf248d97..1018af55a 100644
--- a/src/client/camera.h
+++ b/src/client/camera.h
@@ -24,6 +24,8 @@ with this program; if not, write to the Free Software Foundation, Inc.,
 #include "client/tile.h"
 #include <ICameraSceneNode.h>
 #include <ISceneNode.h>
+#include <plane3d.h>
+#include <array>
 #include <list>
 #include "util/Optional.h"
 
@@ -133,6 +135,23 @@ public:
 		return MYMAX(m_fov_x, m_fov_y);
 	}
 
+	// Returns a lambda that when called with an object's position and bounding-sphere
+	// radius (both in BS space) returns true if, and only if the object should be
+	// frustum-culled.
+	auto getFrustumCuller() const
+	{
+		return [planes = getFrustumCullPlanes(),
+				camera_offset = intToFloat(m_camera_offset, BS)
+				](v3f position, f32 radius) {
+			v3f pos_camspace = position - camera_offset;
+			for (auto &plane : planes) {
+				if (plane.getDistanceTo(pos_camspace) > radius)
+					return true;
+			}
+			return false;
+		};
+	}
+
 	// Notify about new server-sent FOV and initialize smooth FOV transition
 	void notifyFovChange();
 
@@ -190,6 +209,10 @@ public:
 	inline void addArmInertia(f32 player_yaw);
 
 private:
+	// Use getFrustumCuller().
+	// This helper just exists to decrease the header's number of includes.
+	std::array<core::plane3d<f32>, 4> getFrustumCullPlanes() const;
+
 	// Nodes
 	scene::ISceneNode *m_playernode = nullptr;
 	scene::ISceneNode *m_headnode = nullptr;
diff --git a/src/client/clientmap.cpp b/src/client/clientmap.cpp
index 669c673aa..23234c365 100644
--- a/src/client/clientmap.cpp
+++ b/src/client/clientmap.cpp
@@ -196,22 +196,12 @@ void ClientMap::updateDrawList()
 	}
 	m_drawlist.clear();
 
-	const v3f camera_position = m_camera_position;
-	const v3f camera_direction = m_camera_direction;
-
-	// Use a higher fov to accomodate faster camera movements.
-	// Blocks are cropped better when they are drawn.
-	const f32 camera_fov = m_camera_fov * 1.1f;
-
-	v3s16 cam_pos_nodes = floatToInt(camera_position, BS);
+	v3s16 cam_pos_nodes = floatToInt(m_camera_position, BS);
 
 	v3s16 p_blocks_min;
 	v3s16 p_blocks_max;
 	getBlocksInViewRange(cam_pos_nodes, &p_blocks_min, &p_blocks_max);
 
-	// Read the vision range, unless unlimited range is enabled.
-	float range = m_control.range_all ? 1e7 : m_control.wanted_range;
-
 	// Number of blocks currently loaded by the client
 	u32 blocks_loaded = 0;
 	// Number of blocks with mesh in rendering range
@@ -230,6 +220,8 @@ void ClientMap::updateDrawList()
 	v3s16 camera_block = getContainerPos(cam_pos_nodes, MAP_BLOCKSIZE);
 	m_drawlist = std::map<v3s16, MapBlock*, MapBlockComparer>(MapBlockComparer(camera_block));
 
+	auto is_frustum_culled = m_client->getCamera()->getFrustumCuller();
+
 	// Uncomment to debug occluded blocks in the wireframe mode
 	// TODO: Include this as a flag for an extended debugging setting
 	//if (occlusion_culling_enabled && m_control.show_wireframe)
@@ -271,7 +263,7 @@ void ClientMap::updateDrawList()
 
 			// First, perform a simple distance check, with a padding of one extra block.
 			if (!m_control.range_all &&
-					block_position.getDistanceFrom(cam_pos_nodes) > range + MAP_BLOCKSIZE)
+					block_position.getDistanceFrom(cam_pos_nodes) > m_control.wanted_range)
 				continue; // Out of range, skip.
 
 			// Keep the block alive as long as it is in range.
@@ -279,14 +271,18 @@ void ClientMap::updateDrawList()
 			blocks_in_range_with_mesh++;
 
 			// Frustum culling
-			float d = 0.0;
-			if (!isBlockInSight(block_coord, camera_position,
-					camera_direction, camera_fov, range * BS, &d))
+			// Only do coarse culling here, to account for fast camera movement.
+			// This is needed because this function is not called every frame.
+			constexpr float frustum_cull_extra_radius = 300.0f;
+			v3f mesh_sphere_center = intToFloat(block->getPosRelative(), BS)
+					+ block->mesh->getBoundingSphereCenter();
+			f32 mesh_sphere_radius = block->mesh->getBoundingRadius();
+			if (is_frustum_culled(mesh_sphere_center,
+					mesh_sphere_radius + frustum_cull_extra_radius))
 				continue;
 
 			// Occlusion culling
-			if ((!m_control.range_all && d > m_control.wanted_range * BS) ||
-					(occlusion_culling_enabled && isBlockOccluded(block, cam_pos_nodes))) {
+			if (occlusion_culling_enabled && isBlockOccluded(block, cam_pos_nodes)) {
 				blocks_occlusion_culled++;
 				continue;
 			}
@@ -358,33 +354,43 @@ void ClientMap::renderMap(video::IVideoDriver* driver, s32 pass)
 	std::vector<DrawDescriptor> draw_order;
 	video::SMaterial previous_material;
 
+	auto is_frustum_culled = m_client->getCamera()->getFrustumCuller();
+
 	for (auto &i : m_drawlist) {
 		v3s16 block_pos = i.first;
 		MapBlock *block = i.second;
+		MapBlockMesh *block_mesh = block->mesh;
 
 		// If the mesh of the block happened to get deleted, ignore it
-		if (!block->mesh)
+		if (!block_mesh)
+			continue;
+
+		// Do exact frustum culling
+		// (The one in updateDrawList is only coarse.)
+		v3f mesh_sphere_center = intToFloat(block->getPosRelative(), BS)
+				+ block_mesh->getBoundingSphereCenter();
+		f32 mesh_sphere_radius = block_mesh->getBoundingRadius();
+		if (is_frustum_culled(mesh_sphere_center, mesh_sphere_radius))
 			continue;
 
 		v3f block_pos_r = intToFloat(block->getPosRelative() + MAP_BLOCKSIZE / 2, BS);
+
 		float d = camera_position.getDistanceFrom(block_pos_r);
 		d = MYMAX(0,d - BLOCK_MAX_RADIUS);
 
 		// Mesh animation
 		if (pass == scene::ESNRP_SOLID) {
-			MapBlockMesh *mapBlockMesh = block->mesh;
-			assert(mapBlockMesh);
 			// Pretty random but this should work somewhat nicely
 			bool faraway = d >= BS * 50;
-			if (mapBlockMesh->isAnimationForced() || !faraway ||
+			if (block_mesh->isAnimationForced() || !faraway ||
 					mesh_animate_count < (m_control.range_all ? 200 : 50)) {
 
-				bool animated = mapBlockMesh->animate(faraway, animation_time,
+				bool animated = block_mesh->animate(faraway, animation_time,
 					crack, daynight_ratio);
 				if (animated)
 					mesh_animate_count++;
 			} else {
-				mapBlockMesh->decreaseAnimationForceTimer();
+				block_mesh->decreaseAnimationForceTimer();
 			}
 		}
 
@@ -394,17 +400,14 @@ void ClientMap::renderMap(video::IVideoDriver* driver, s32 pass)
 		if (is_transparent_pass) {
 			// In transparent pass, the mesh will give us
 			// the partial buffers in the correct order
-			for (auto &buffer : block->mesh->getTransparentBuffers())
+			for (auto &buffer : block_mesh->getTransparentBuffers())
 				draw_order.emplace_back(block_pos, &buffer);
 		}
 		else {
 			// otherwise, group buffers across meshes
 			// using MeshBufListList
-			MapBlockMesh *mapBlockMesh = block->mesh;
-			assert(mapBlockMesh);
-
 			for (int layer = 0; layer < MAX_TILE_LAYERS; layer++) {
-				scene::IMesh *mesh = mapBlockMesh->getMesh(layer);
+				scene::IMesh *mesh = block_mesh->getMesh(layer);
 				assert(mesh);
 
 				u32 c = mesh->getMeshBufferCount();
@@ -772,9 +775,9 @@ void ClientMap::renderMapShadows(video::IVideoDriver *driver,
 	for (auto &lists : grouped_buffers.lists)
 		for (MeshBufList &list : lists)
 			buffer_count += list.bufs.size();
-	
+
 	draw_order.reserve(draw_order.size() + buffer_count);
-	
+
 	// Capture draw order for all solid meshes
 	for (auto &lists : grouped_buffers.lists) {
 		for (MeshBufList &list : lists) {
@@ -908,8 +911,8 @@ void ClientMap::updateTransparentMeshBuffers()
 		MapBlock* block = it->second;
 		if (!block->mesh)
 			continue;
-		
-		if (m_needs_update_transparent_meshes || 
+
+		if (m_needs_update_transparent_meshes ||
 				block->mesh->getTransparentBuffers().size() == 0) {
 
 			v3s16 block_pos = block->getPos();
diff --git a/src/client/mapblock_mesh.cpp b/src/client/mapblock_mesh.cpp
index c730b9bf9..d05a786a6 100644
--- a/src/client/mapblock_mesh.cpp
+++ b/src/client/mapblock_mesh.cpp
@@ -1031,9 +1031,9 @@ void MapBlockBspTree::buildTree(const std::vector<MeshTriangle> *triangles)
 
 /**
  * @brief Find a candidate plane to split a set of triangles in two
- * 
+ *
  * The candidate plane is represented by one of the triangles from the set.
- * 
+ *
  * @param list Vector of indexes of the triangles in the set
  * @param triangles Vector of all triangles in the BSP tree
  * @return Address of the triangle that represents the proposed split plane
@@ -1225,7 +1225,7 @@ MapBlockMesh::MapBlockMesh(MeshMakeData *data, v3s16 camera_offset):
 		Convert FastFaces to MeshCollector
 	*/
 
-	MeshCollector collector;
+	MeshCollector collector(m_bounding_sphere_center);
 
 	{
 		// avg 0ms (100ms spikes when loading textures the first time)
@@ -1261,6 +1261,8 @@ MapBlockMesh::MapBlockMesh(MeshMakeData *data, v3s16 camera_offset):
 	const bool desync_animations = g_settings->getBool(
 		"desynchronize_mapblock_texture_animation");
 
+	m_bounding_radius = std::sqrt(collector.m_bounding_radius_sq);
+
 	for (int layer = 0; layer < MAX_TILE_LAYERS; layer++) {
 		for(u32 i = 0; i < collector.prebuffers[layer].size(); i++)
 		{
diff --git a/src/client/mapblock_mesh.h b/src/client/mapblock_mesh.h
index 169b3a8c1..f22dd68bd 100644
--- a/src/client/mapblock_mesh.h
+++ b/src/client/mapblock_mesh.h
@@ -100,7 +100,7 @@ public:
 };
 
 /**
- * Implements a binary space partitioning tree 
+ * Implements a binary space partitioning tree
  * See also: https://en.wikipedia.org/wiki/Binary_space_partitioning
  */
 class MapBlockBspTree
@@ -221,6 +221,12 @@ public:
 			m_animation_force_timer--;
 	}
 
+	/// Radius of the bounding-sphere, in BS-space.
+	f32 getBoundingRadius() const { return m_bounding_radius; }
+
+	/// Center of the bounding-sphere, in BS-space, relative to block pos.
+	v3f getBoundingSphereCenter() const { return m_bounding_sphere_center; }
+
 	/// update transparent buffers to render towards the camera
 	void updateTransparentBuffers(v3f camera_pos, v3s16 block_pos);
 	void consolidateTransparentBuffers();
@@ -243,6 +249,10 @@ private:
 	ITextureSource *m_tsrc;
 	IShaderSource *m_shdrsrc;
 
+	f32 m_bounding_radius;
+	// MapblockMeshGenerator uses the same as mapblock center
+	v3f m_bounding_sphere_center = v3f((MAP_BLOCKSIZE * 0.5f - 0.5f) * BS);
+
 	bool m_enable_shaders;
 	bool m_enable_vbo;
 
diff --git a/src/client/meshgen/collector.cpp b/src/client/meshgen/collector.cpp
index 25457c868..c5f4eb976 100644
--- a/src/client/meshgen/collector.cpp
+++ b/src/client/meshgen/collector.cpp
@@ -45,9 +45,12 @@ void MeshCollector::append(const TileLayer &layer, const video::S3DVertex *verti
 		scale = 1.0f / layer.scale;
 
 	u32 vertex_count = p.vertices.size();
-	for (u32 i = 0; i < numVertices; i++)
+	for (u32 i = 0; i < numVertices; i++) {
 		p.vertices.emplace_back(vertices[i].Pos, vertices[i].Normal,
 				vertices[i].Color, scale * vertices[i].TCoords);
+		m_bounding_radius_sq = std::max(m_bounding_radius_sq,
+				(vertices[i].Pos - m_center_pos).getLengthSQ());
+	}
 
 	for (u32 i = 0; i < numIndices; i++)
 		p.indices.push_back(indices[i] + vertex_count);
@@ -81,8 +84,11 @@ void MeshCollector::append(const TileLayer &layer, const video::S3DVertex *verti
 		video::SColor color = c;
 		if (!light_source)
 			applyFacesShading(color, vertices[i].Normal);
-		p.vertices.emplace_back(vertices[i].Pos + pos, vertices[i].Normal, color,
+		auto vpos = vertices[i].Pos + pos;
+		p.vertices.emplace_back(vpos, vertices[i].Normal, color,
 				scale * vertices[i].TCoords);
+		m_bounding_radius_sq = std::max(m_bounding_radius_sq,
+				(vpos - m_center_pos).getLengthSQ());
 	}
 
 	for (u32 i = 0; i < numIndices; i++)
diff --git a/src/client/meshgen/collector.h b/src/client/meshgen/collector.h
index e4189088e..c390c53e7 100644
--- a/src/client/meshgen/collector.h
+++ b/src/client/meshgen/collector.h
@@ -37,6 +37,12 @@ struct PreMeshBuffer
 struct MeshCollector
 {
 	std::array<std::vector<PreMeshBuffer>, MAX_TILE_LAYERS> prebuffers;
+	// bounding sphere radius and center
+	f32 m_bounding_radius_sq = 0.0f;
+	v3f m_center_pos;
+
+	// center_pos: pos to use for bounding-sphere, in BS-space
+	MeshCollector(const v3f center_pos) : m_center_pos(center_pos) {}
 
 	// clang-format off
 	void append(const TileSpec &material,
diff --git a/src/client/wieldmesh.cpp b/src/client/wieldmesh.cpp
index 0a89e2aa2..d546d52ff 100644
--- a/src/client/wieldmesh.cpp
+++ b/src/client/wieldmesh.cpp
@@ -313,7 +313,7 @@ static scene::SMesh *createSpecialNodeMesh(Client *client, MapNode n,
 	std::vector<ItemPartColor> *colors, const ContentFeatures &f)
 {
 	MeshMakeData mesh_make_data(client, false);
-	MeshCollector collector;
+	MeshCollector collector(v3f(0.0f * BS));
 	mesh_make_data.setSmoothLighting(false);
 	MapblockMeshGenerator gen(&mesh_make_data, &collector,
 		client->getSceneManager()->getMeshManipulator());