Scale culler steps proportionally to the mesh sizes (#13250)

1 files changed, 88 insertions, 22 deletions

diff --git a/src/client/clientmap.cpp b/src/client/clientmap.cpp
index d987a2ee3..62963f7a2 100644
--- a/src/client/clientmap.cpp
+++ b/src/client/clientmap.cpp
@@ -270,13 +270,19 @@ void ClientMap::updateDrawList()
 
 	// Number of blocks occlusion culled
 	u32 blocks_occlusion_culled = 0;
+	// Number of blocks frustum culled
+	u32 blocks_frustum_culled = 0;
 	// Blocks visited by the algorithm
 	u32 blocks_visited = 0;
 	// Block sides that were not traversed
 	u32 sides_skipped = 0;
 
+	MeshGrid mesh_grid = m_client->getMeshGrid();
+
 	// No occlusion culling when free_move is on and camera is inside ground
-	bool occlusion_culling_enabled = true;
+	// No occlusion culling for chunk sizes of 4 and above
+	//   because the current occlusion culling test is highly inefficient at these sizes
+	bool occlusion_culling_enabled = mesh_grid.cell_size < 4;
 	if (m_control.allow_noclip) {
 		MapNode n = getNode(cam_pos_nodes);
 		if (n.getContent() == CONTENT_IGNORE || m_nodedef->get(n).solidness == 2)
@@ -295,16 +301,18 @@ void ClientMap::updateDrawList()
 
 	std::queue<v3s16> blocks_to_consider;
 
+	v3s16 camera_mesh = mesh_grid.getMeshPos(camera_block);
+	v3s16 camera_cell = mesh_grid.getCellPos(camera_block);
+
 	// Bits per block:
 	// [ visited | 0 | 0 | 0 | 0 | Z visible | Y visible | X visible ]
-	MapBlockFlags blocks_seen(p_blocks_min, p_blocks_max);
+	MapBlockFlags meshes_seen(mesh_grid.getCellPos(p_blocks_min), mesh_grid.getCellPos(p_blocks_max) + 1);
 
 	// Start breadth-first search with the block the camera is in
-	blocks_to_consider.push(camera_block);
-	blocks_seen.getChunk(camera_block).getBits(camera_block) = 0x07; // mark all sides as visible
+	blocks_to_consider.push(camera_mesh);
+	meshes_seen.getChunk(camera_cell).getBits(camera_cell) = 0x07; // mark all sides as visible
 
 	std::set<v3s16> shortlist;
-	MeshGrid mesh_grid = m_client->getMeshGrid();
 
 	// Recursively walk the space and pick mapblocks for drawing
 	while (blocks_to_consider.size() > 0) {
@@ -312,7 +320,8 @@ void ClientMap::updateDrawList()
 		v3s16 block_coord = blocks_to_consider.front();
 		blocks_to_consider.pop();
 
-		auto &flags = blocks_seen.getChunk(block_coord).getBits(block_coord);
+		v3s16 cell_coord = mesh_grid.getCellPos(block_coord);
+		auto &flags = meshes_seen.getChunk(cell_coord).getBits(cell_coord);
 
 		// Only visit each block once (it may have been queued up to three times)
 		if ((flags & 0x80) == 0x80)
@@ -324,14 +333,11 @@ void ClientMap::updateDrawList()
 		// Get the sector, block and mesh
 		MapSector *sector = this->getSectorNoGenerate(v2s16(block_coord.X, block_coord.Z));
 
-		if (!sector)
-			continue;
-
-		MapBlock *block = sector->getBlockNoCreateNoEx(block_coord.Y);
+		MapBlock *block = sector ? sector->getBlockNoCreateNoEx(block_coord.Y) : nullptr;
 
 		MapBlockMesh *mesh = block ? block->mesh : nullptr;
 
-		// Calculate the coordinates for range and frutum culling
+		// Calculate the coordinates for range and frustum culling
 		v3f mesh_sphere_center;
 		f32 mesh_sphere_radius;
 
@@ -343,8 +349,8 @@ void ClientMap::updateDrawList()
 			mesh_sphere_radius = mesh->getBoundingRadius();
 		}
 		else {
-			mesh_sphere_center = intToFloat(block_pos_nodes, BS) + v3f((MAP_BLOCKSIZE * 0.5f - 0.5f) * BS);
-			mesh_sphere_radius = 0.0f;
+			mesh_sphere_center = intToFloat(block_pos_nodes, BS) + v3f((mesh_grid.cell_size * MAP_BLOCKSIZE * 0.5f - 0.5f) * BS);
+			mesh_sphere_radius = 0.87f * mesh_grid.cell_size * MAP_BLOCKSIZE * BS;
 		}
 
 		// First, perform a simple distance check.
@@ -358,12 +364,14 @@ void ClientMap::updateDrawList()
 		// This is needed because this function is not called every frame.
 		float frustum_cull_extra_radius = 300.0f;
 		if (is_frustum_culled(mesh_sphere_center,
-				mesh_sphere_radius + frustum_cull_extra_radius))
+				mesh_sphere_radius + frustum_cull_extra_radius)) {
+			blocks_frustum_culled++;
 			continue;
+		}
 
 		// Calculate the vector from the camera block to the current block
 		// We use it to determine through which sides of the current block we can continue the search
-		v3s16 look = block_coord - camera_block;
+		v3s16 look = block_coord - camera_mesh;
 
 		// Occluded near sides will further occlude the far sides
 		u8 visible_outer_sides = flags & 0x07;
@@ -371,7 +379,7 @@ void ClientMap::updateDrawList()
 		// Raytraced occlusion culling - send rays from the camera to the block's corners
 		if (occlusion_culling_enabled && m_enable_raytraced_culling &&
 				block && mesh &&
-				visible_outer_sides != 0x07 && isBlockOccluded(block, cam_pos_nodes)) {
+				visible_outer_sides != 0x07 && isMeshOccluded(block, mesh_grid.cell_size, cam_pos_nodes)) {
 			blocks_occlusion_culled++;
 			continue;
 		}
@@ -380,7 +388,7 @@ void ClientMap::updateDrawList()
 			// Block meshes are stored in the corner block of a chunk
 			// (where all coordinate are divisible by the chunk size)
 			// Add them to the de-dup set.
-			shortlist.emplace(mesh_grid.getMeshPos(block_coord.X), mesh_grid.getMeshPos(block_coord.Y), mesh_grid.getMeshPos(block_coord.Z));
+			shortlist.emplace(block_coord.X, block_coord.Y, block_coord.Z);
 			// All other blocks we can grab and add to the keeplist right away.
 			if (block) {
 				m_keeplist.push_back(block);
@@ -438,7 +446,7 @@ void ClientMap::updateDrawList()
 
 		// Calculate vector from camera to mapblock center. Because we only need relation between
 		// coordinates we scale by 2 to avoid precision loss.
-		v3s16 precise_look = 2 * (block_pos_nodes - cam_pos_nodes) + MAP_BLOCKSIZE - 1;
+		v3s16 precise_look = 2 * (block_pos_nodes - cam_pos_nodes) + mesh_grid.cell_size * MAP_BLOCKSIZE - 1;
 
 		// dominant axis flag
 		u8 dominant_axis = (abs(precise_look.X) > abs(precise_look.Y) && abs(precise_look.X) > abs(precise_look.Z)) |
@@ -467,9 +475,11 @@ void ClientMap::updateDrawList()
 				v3s16 next_pos = block_coord;
 				next_pos[axis] += next_pos_offset;
 
+				v3s16 next_cell = mesh_grid.getCellPos(next_pos);
+
 				// If a side is a see-through, mark the next block's side as visible, and queue
 				if (side_visible) {
-					auto &next_flags = blocks_seen.getChunk(next_pos).getBits(next_pos);
+					auto &next_flags = meshes_seen.getChunk(next_cell).getBits(next_cell);
 					next_flags |= my_side;
 					blocks_to_consider.push(next_pos);
 				}
@@ -481,13 +491,13 @@ void ClientMap::updateDrawList()
 
 			// Test the '-' direction of the axis
 			if (look[axis] <= 0 && block_coord[axis] > p_blocks_min[axis])
-				traverse_far_side(-1);
+				traverse_far_side(-mesh_grid.cell_size);
 
 			// Test the '+' direction of the axis
 			far_side_mask <<= 1;
 
 			if (look[axis] >= 0 && block_coord[axis] < p_blocks_max[axis])
-				traverse_far_side(+1);
+				traverse_far_side(+mesh_grid.cell_size);
 		}
 	}
 
@@ -503,6 +513,7 @@ void ClientMap::updateDrawList()
 	}
 
 	g_profiler->avg("MapBlocks occlusion culled [#]", blocks_occlusion_culled);
+	g_profiler->avg("MapBlocks frustum culled [#]", blocks_frustum_culled);
 	g_profiler->avg("MapBlocks sides skipped [#]", sides_skipped);
 	g_profiler->avg("MapBlocks examined [#]", blocks_visited);
 	g_profiler->avg("MapBlocks drawn [#]", m_drawlist.size());
@@ -521,6 +532,8 @@ void ClientMap::touchMapBlocks()
 	// Number of blocks with mesh in rendering range
 	u32 blocks_in_range_with_mesh = 0;
 
+	v3f cam_pos_f = intToFloat(cam_pos_nodes, BS);
+
 	for (const auto &sector_it : m_sectors) {
 		MapSector *sector = sector_it.second;
 		v2s16 sp = sector->getPos();
@@ -553,9 +566,10 @@ void ClientMap::touchMapBlocks()
 			v3f mesh_sphere_center = intToFloat(block->getPosRelative(), BS)
 					+ block->mesh->getBoundingSphereCenter();
 			f32 mesh_sphere_radius = block->mesh->getBoundingRadius();
+
 			// First, perform a simple distance check.
 			if (!m_control.range_all &&
-				mesh_sphere_center.getDistanceFrom(intToFloat(cam_pos_nodes, BS)) >
+				mesh_sphere_center.getDistanceFrom(cam_pos_f) >
 					m_control.wanted_range * BS + mesh_sphere_radius)
 				continue; // Out of range, skip.
 
@@ -564,6 +578,7 @@ void ClientMap::touchMapBlocks()
 			blocks_in_range_with_mesh++;
 		}
 	}
+
 	g_profiler->avg("MapBlock meshes in range [#]", blocks_in_range_with_mesh);
 	g_profiler->avg("MapBlocks loaded [#]", blocks_loaded);
 }
@@ -1239,3 +1254,54 @@ void ClientMap::DrawDescriptor::draw(video::IVideoDriver* driver)
 		driver->drawMeshBuffer(m_buffer);
 	}
 }
+
+bool ClientMap::isMeshOccluded(MapBlock *mesh_block, u16 mesh_size, v3s16 cam_pos_nodes)
+{
+	if (mesh_size == 1)
+		return isBlockOccluded(mesh_block, cam_pos_nodes);
+
+	v3s16 min_edge = mesh_block->getPosRelative();
+	v3s16 max_edge = min_edge + mesh_size * MAP_BLOCKSIZE -1;
+	bool check_axis[3] = { false, false, false };
+	u16 closest_side[3] = { 0, 0, 0 };
+
+	for (int axis = 0; axis < 3; axis++) {
+		if (cam_pos_nodes[axis] < min_edge[axis])
+			check_axis[axis] = true;
+		else if (cam_pos_nodes[axis] > max_edge[axis]) {
+			check_axis[axis] = true;
+			closest_side[axis] = mesh_size - 1;
+		}
+	}
+
+	std::vector<bool> processed_blocks(mesh_size * mesh_size * mesh_size);
+
+	// scan the side
+	for (u16 i = 0; i < mesh_size; i++)
+	for (u16 j = 0; j < mesh_size; j++) {
+		v3s16 offsets[3] = {
+			v3s16(closest_side[0], i, j),
+			v3s16(i, closest_side[1], j),
+			v3s16(i, j, closest_side[2])
+		};
+		for (int axis = 0; axis < 3; axis++) {
+			v3s16 offset = offsets[axis];
+			int block_index = offset.X + offset.Y * mesh_size + offset.Z * mesh_size * mesh_size;
+			if (check_axis[axis] && !processed_blocks[block_index]) {
+				processed_blocks[block_index] = true;
+				v3s16 block_pos = mesh_block->getPos() + offset;
+				MapBlock *block;
+
+				if (mesh_block->getPos() == block_pos)
+					block = mesh_block;
+				else
+					block = getBlockNoCreateNoEx(block_pos);
+
+				if (block && !isBlockOccluded(block, cam_pos_nodes))
+					return false;
+			}
+		}
+	}
+
+	return true;
+}