Allow cheaper culling checks at a distance

[lhofhansl]

Server side occlusion culling is extremely valuable, even in an open air scene it can often save upwards of 90% of
the blocks to be sent to the client.

It does, however, come at a price. For each block it sends 5 rays (plus an extra check for tunnels) to see of a block is occluded. At viewing_ranges of 1000 my server easily spends the majority of its time doing occlusion checks.

This PR even benefits the normal case as it sends an extra ray to a random position inside the target block, so over time (i.e. subsequent map-send-cycles) it would improve the culling.

Most folks would not be affected by the default setting of 20 blocks (i.e. 320 nodes).

• Goal of the PR
  Reduce CPU spent in server occlusion culling

• How does the PR work?
  Send a single ray to a random position inside the, improving accuracy over time.
  At large (configurable) distances only send this one ray on each iteration.

• Does it resolve any reported issue?
  Not that I am aware

• Does this relate to a goal in the roadmap?
  Nope.

• If not a bug fix, why is this PR needed? What usecases does it solve?
  Reduce per-player server CPU.

To do

This PR is Ready for Review.

How to test

Set viewing_range (and related server settings such as max_block_send_distance and max_block_generate_distance) to a large value.

Say:
viewing_range = 1000
max_block_send_distance = 64
max_block_generate_distance = 64

And look for rendering glitches past 400 nodes. Also note the reduction of server CPU time.
On my machine it reduced CPU time spent on occlusion culling by 70% without any immediately noticeable rendering glitches.

[lhofhansl]

Added some randomness, instead of the center ray, pick a random ray. So at a distance blocks that were erroneously declared as non-visible will be filled in in subsequent sweeps.

[sfan5]

Suggested change

	# Stated in mapblocks (16 nodes).
	block_cull_optimize_distance (Block cull optimize distance) int 20 2 32767
	# Stated in MapBlocks (16 nodes).
	block_cull_optimize_distance (Block cull optimize distance) int 20 2 2047

[lhofhansl]

I had copied from block_send_optimizer distance above. Should I fix those as well while I'm here?

[sfan5]

Sure.

[lhofhansl]

WDYT @sfan5?

Personally I like the true random sampling that this is doing over time, it will lead to fewer blocks incorrectly occluded, and at a distance it will improve over time.

[sfan5]

I like it in principle but still trying to warm up to adding yet another (expensive?) check to culling.

[lhofhansl]

Fair enough.

The culling is especially expensive with many blocks being far away - each ray will cost more even though we reduce the sampling rate the farther we go, and at a distance we'll have mnay blocks to check.

So the closer blocks are less of a problem (there are comparatively fewer, and they are close so rays to send are short).

I like the increased accuracy over time.

Lemme think on that a bit.
I'm happy to remove that extra check from the normal case.
Maybe we can bring some randomness into the short range checks as well in other ways.
Could also remove the check for the center ray, i.e. replace that with the random ray.

[lhofhansl]

Could go as "extreme" as this:

	u32 needed_count = 1;

	if (simple_check)
		return isOccluded(cam_pos_nodes, pos_blockcenter + v3s16(myrand_range(-bs2, bs2), myrand_range(-bs2, bs2), myrand_range(-bs2, bs2)), step, stepfac,
				start_offset, end_offset, needed_count);

	// Additional occlusion check, see comments in that function
	v3s16 check;
	if (determineAdditionalOcclusionCheck(cam_pos_nodes, block->getBox(), check)) {
		// node is always on a side facing the camera, end_offset can be lower
		if (!isOccluded(cam_pos_nodes, check, step, stepfac, start_offset,
				-1.0f, needed_count))
			return false;
	}

	for (int i=0; i<5; i++) {
		if (!isOccluded(cam_pos_nodes, pos_blockcenter + v3s16(myrand_range(-bs2, bs2), myrand_range(-bs2, bs2), myrand_range(-bs2, bs2)), step, stepfac,
				start_offset, end_offset, needed_count))
			return false;
	}
	return true;

This is surprisingly accurate. Even though it sends less than 1/2 of the rays. And we can get rid of that needed_count nonsense. Any blocks wrongfully occluded in one run will likely show in the next run.

[lhofhansl]

Or:

	// passing d instead of a flag..

	u32 needed_count = 1;

	s16 rounds = MYMAX(1, 8-d/4);

	if (rounds > 1) {
		// Additional occlusion check, see comments in that function
		v3s16 check;
		if (determineAdditionalOcclusionCheck(cam_pos_nodes, block->getBox(), check)) {
			// node is always on a side facing the camera, end_offset can be lower
			if (!isOccluded(cam_pos_nodes, check, step, stepfac, start_offset,
					-1.0f, needed_count))
				return false;
		}
	}

	for (int i=0; i<rounds; i++) {
		if (!isOccluded(cam_pos_nodes, pos_blockcenter + v3s16(myrand_range(-bs2, bs2), myrand_range(-bs2, bs2), myrand_range(-bs2, bs2)), step, stepfac,
				start_offset, end_offset, needed_count))
			return false;
	}
	return true;

So this will gracefully fall off at a distance. Reaching 1 at a distance of 28 block. 2 at 24 blocks, a.s.o.
No config needed, and good results in my tests, always cheaper than it is now.

I'll stop now :)

[sfan5]

Radical idea but very interesting IMO.
I guess we should merge this first and see about the rest in a second PR.

[sfan5]

(still needs the settingtypes.txt fix)

[lhofhansl]

Fixed settingtypes.txt