From ba4b704ebf24952ab9a84c914b8ad6c45dabfaba Mon Sep 17 00:00:00 2001
From: Lars Hofhansl <larsh@apache.org>
Date: Mon, 27 Feb 2017 23:06:15 -0800
Subject: Allow server side occlusion culling.

---
 src/map.cpp | 66 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 66 insertions(+)

(limited to 'src/map.cpp')

diff --git a/src/map.cpp b/src/map.cpp
index a1502befa..43a49dc2f 100644
--- a/src/map.cpp
+++ b/src/map.cpp
@@ -1157,6 +1157,72 @@ void Map::removeNodeTimer(v3s16 p)
 	block->m_node_timers.remove(p_rel);
 }
 
+bool Map::isOccluded(v3s16 p0, v3s16 p1, float step, float stepfac,
+		float start_off, float end_off, u32 needed_count)
+{
+	float d0 = (float)BS * p0.getDistanceFrom(p1);
+	v3s16 u0 = p1 - p0;
+	v3f uf = v3f(u0.X, u0.Y, u0.Z) * BS;
+	uf.normalize();
+	v3f p0f = v3f(p0.X, p0.Y, p0.Z) * BS;
+	u32 count = 0;
+	for(float s=start_off; s<d0+end_off; s+=step){
+		v3f pf = p0f + uf * s;
+		v3s16 p = floatToInt(pf, BS);
+		MapNode n = getNodeNoEx(p);
+		const ContentFeatures &f = m_nodedef->get(n);
+		if(f.drawtype == NDT_NORMAL){
+			// not transparent, see ContentFeature::updateTextures
+			count++;
+			if(count >= needed_count)
+				return true;
+		}
+		step *= stepfac;
+	}
+	return false;
+}
+
+bool Map::isBlockOccluded(MapBlock *block, v3s16 cam_pos_nodes) {
+	v3s16 cpn = block->getPos() * MAP_BLOCKSIZE;
+	cpn += v3s16(MAP_BLOCKSIZE / 2, MAP_BLOCKSIZE / 2, MAP_BLOCKSIZE / 2);
+	float step = BS * 1;
+	float stepfac = 1.1;
+	float startoff = BS * 1;
+	// The occlusion search of 'isOccluded()' must stop short of the target
+	// point by distance 'endoff' (end offset) to not enter the target mapblock.
+	// For the 8 mapblock corners 'endoff' must therefore be the maximum diagonal
+	// of a mapblock, because we must consider all view angles.
+	// sqrt(1^2 + 1^2 + 1^2) = 1.732
+	float endoff = -BS * MAP_BLOCKSIZE * 1.732050807569;
+	v3s16 spn = cam_pos_nodes;
+	s16 bs2 = MAP_BLOCKSIZE / 2 + 1;
+	// to reduce the likelihood of falsely occluded blocks
+	// require at least two solid blocks
+	// this is a HACK, we should think of a more precise algorithm
+	u32 needed_count = 2;
+
+	return (
+		// For the central point of the mapblock 'endoff' can be halved
+		isOccluded(spn, cpn,
+			step, stepfac, startoff, endoff / 2.0f, needed_count) &&
+		isOccluded(spn, cpn + v3s16(bs2,bs2,bs2),
+			step, stepfac, startoff, endoff, needed_count) &&
+		isOccluded(spn, cpn + v3s16(bs2,bs2,-bs2),
+			step, stepfac, startoff, endoff, needed_count) &&
+		isOccluded(spn, cpn + v3s16(bs2,-bs2,bs2),
+			step, stepfac, startoff, endoff, needed_count) &&
+		isOccluded(spn, cpn + v3s16(bs2,-bs2,-bs2),
+			step, stepfac, startoff, endoff, needed_count) &&
+		isOccluded(spn, cpn + v3s16(-bs2,bs2,bs2),
+			step, stepfac, startoff, endoff, needed_count) &&
+		isOccluded(spn, cpn + v3s16(-bs2,bs2,-bs2),
+			step, stepfac, startoff, endoff, needed_count) &&
+		isOccluded(spn, cpn + v3s16(-bs2,-bs2,bs2),
+			step, stepfac, startoff, endoff, needed_count) &&
+		isOccluded(spn, cpn + v3s16(-bs2,-bs2,-bs2),
+			step, stepfac, startoff, endoff, needed_count));
+}
+
 /*
 	ServerMap
 */
-- 
cgit v1.2.3