From 950adaa5bdb9bf758400f2c00df623865b6bff1d Mon Sep 17 00:00:00 2001
From: Daniel Karbach <daniel.karbach@localhorst.tv>
Date: Fri, 13 Mar 2015 18:45:20 +0100
Subject: [PATCH] optimize chunk intersection tests a little

---
 src/chunk.cpp | 46 ++++++++++++++--------------------------------
 src/chunk.hpp | 14 +++++++++++---
 src/world.cpp | 31 +++++++++++++++++++++++++++----
 3 files changed, 52 insertions(+), 39 deletions(-)

diff --git a/src/chunk.cpp b/src/chunk.cpp
index f43f8fd..e61a3a7 100644
--- a/src/chunk.cpp
+++ b/src/chunk.cpp
@@ -56,24 +56,14 @@ void Chunk::Draw() {
 bool Chunk::Intersection(
 	const Ray &ray,
 	const glm::mat4 &M,
-	int *blkid,
-	float *dist,
-	glm::vec3 *normal) const {
-	{ // rough check
-		if (!blank::Intersection(ray, Bounds(), M)) {
-			return false;
-		}
-	}
-
-	if (!blkid && !dist && !normal) {
-		return true;
-	}
-
+	int &blkid,
+	float &dist,
+	glm::vec3 &normal
+) const {
 	// TODO: should be possible to heavily optimize this
 	int id = 0;
-	int closest_id = -1;
-	float closest_dist = std::numeric_limits<float>::infinity();
-	glm::vec3 closest_normal(0, 1, 0);
+	blkid = -1;
+	dist = std::numeric_limits<float>::infinity();
 	for (int z = 0; z < Depth(); ++z) {
 		for (int y = 0; y < Height(); ++y) {
 			for (int x = 0; x < Width(); ++x, ++id) {
@@ -83,30 +73,22 @@ bool Chunk::Intersection(
 				float cur_dist;
 				glm::vec3 cur_norm;
 				if (Type(blocks[id]).shape->Intersects(ray, M * ToTransform(id), cur_dist, cur_norm)) {
-					if (cur_dist < closest_dist) {
-						closest_id = id;
-						closest_dist = cur_dist;
-						closest_normal = cur_norm;
+					if (cur_dist < dist) {
+						blkid = id;
+						dist = cur_dist;
+						normal = cur_norm;
 					}
 				}
 			}
 		}
 	}
 
-	if (closest_id < 0) {
+	if (blkid < 0) {
 		return false;
+	} else {
+		normal = glm::vec3(BlockAt(blkid).Transform() * glm::vec4(normal, 0.0f));
+		return true;
 	}
-
-	if (blkid) {
-		*blkid = closest_id;
-	}
-	if (dist) {
-		*dist = closest_dist;
-	}
-	if (normal) {
-		*normal = glm::vec3(BlockAt(closest_id).Transform() * glm::vec4(closest_normal, 0.0f));
-	}
-	return true;
 }
 
 void Chunk::Position(const Pos &pos) {
diff --git a/src/chunk.hpp b/src/chunk.hpp
index 255d73b..19f5c07 100644
--- a/src/chunk.hpp
+++ b/src/chunk.hpp
@@ -74,12 +74,20 @@ public:
 
 	const BlockType &Type(const Block &b) const { return *types->Get(b.type); }
 
+	bool Intersection(
+		const Ray &ray,
+		const glm::mat4 &M,
+		float &dist
+	) const {
+		return blank::Intersection(ray, Bounds(), M, &dist);
+	}
+
 	bool Intersection(
 		const Ray &,
 		const glm::mat4 &M,
-		int *blkid = nullptr,
-		float *dist = nullptr,
-		glm::vec3 *normal = nullptr) const;
+		int &blkid,
+		float &dist,
+		glm::vec3 &normal) const;
 
 	void Position(const Pos &);
 	const Pos &Position() const { return position; }
diff --git a/src/world.cpp b/src/world.cpp
index 5244d15..675c29f 100644
--- a/src/world.cpp
+++ b/src/world.cpp
@@ -91,6 +91,17 @@ World::World()
 }
 
 
+namespace {
+
+struct Candidate {
+	Chunk *chunk;
+	float dist;
+};
+
+std::vector<Candidate> candidates;
+
+}
+
 bool World::Intersection(
 		const Ray &ray,
 		const glm::mat4 &M,
@@ -98,18 +109,30 @@ bool World::Intersection(
 		int *blkid,
 		float *dist,
 		glm::vec3 *normal) {
+	candidates.clear();
+
+	for (Chunk &cur_chunk : chunks.Loaded()) {
+		float cur_dist;
+		if (cur_chunk.Intersection(ray, M * cur_chunk.Transform(player.ChunkCoords()), cur_dist)) {
+			candidates.push_back({ &cur_chunk, cur_dist });
+		}
+	}
+
+	if (candidates.empty()) return false;
+
 	Chunk *closest_chunk = nullptr;
-	int closest_blkid = -1;
 	float closest_dist = std::numeric_limits<float>::infinity();
+	int closest_blkid = -1;
 	glm::vec3 closest_normal;
 
-	for (Chunk &cur_chunk : chunks.Loaded()) {
+	for (Candidate &cand : candidates) {
+		if (cand.dist > closest_dist) continue;
 		int cur_blkid;
 		float cur_dist;
 		glm::vec3 cur_normal;
-		if (cur_chunk.Intersection(ray, M * cur_chunk.Transform(player.ChunkCoords()), &cur_blkid, &cur_dist, &cur_normal)) {
+		if (cand.chunk->Intersection(ray, M * cand.chunk->Transform(player.ChunkCoords()), cur_blkid, cur_dist, cur_normal)) {
 			if (cur_dist < closest_dist) {
-				closest_chunk = &cur_chunk;
+				closest_chunk = cand.chunk;
 				closest_blkid = cur_blkid;
 				closest_dist = cur_dist;
 				closest_normal = cur_normal;
-- 
2.39.2