From 4ef5c934aacbfce6b3c5502425975edcf61cf0e8 Mon Sep 17 00:00:00 2001
From: Dan Goodliffe <dan@randomdan.homeip.net>
Date: Fri, 7 Jan 2022 18:57:08 +0000
Subject: Initial commit GeoData ray tracer

---
 game/geoData.cpp  | 39 +++++++++++++++++++++++++++++++++++++++
 game/geoData.h    | 13 +++++++++++++
 test/test-geo.cpp | 40 ++++++++++++++++++++++++++++++++++++++++
 3 files changed, 92 insertions(+)

diff --git a/game/geoData.cpp b/game/geoData.cpp
index c3fb5dc..4537026 100644
--- a/game/geoData.cpp
+++ b/game/geoData.cpp
@@ -95,6 +95,45 @@ GeoData::positionAt(const glm::vec2 wcoord) const
 	return wcoord || heightMid;
 }
 
+GeoData::RayTracer::RayTracer(glm::vec2 p0, glm::vec2 p1, float scale) : p {glm::floor(p0)}, d {glm::abs(p1 - p0)}
+{
+	using Limits = std::numeric_limits<typename glm::vec2::value_type>;
+	static_assert(Limits::has_infinity);
+	static constexpr const glm::vec2 inf {Limits::infinity(), -Limits::infinity()};
+
+	auto byAxis = [this, p0, p1, scale](auto axis) {
+		if (d[axis] == 0) {
+			inc[axis] = 0;
+			return inf[axis];
+		}
+		else if (p1[axis] > p0[axis]) {
+			inc[axis] = scale;
+			return (std::floor(p0[axis]) + 1 - p0[axis]) * d[1 - axis];
+		}
+		else {
+			inc[axis] = -scale;
+			return (p0[axis] - std::floor(p0[axis])) * d[1 - axis];
+		}
+	};
+
+	error = byAxis(0);
+	error -= byAxis(1);
+	inc.z = scale;
+}
+
+glm::vec2
+GeoData::RayTracer::next()
+{
+	glm::vec2 cur {p};
+
+	static constexpr const glm::vec2 m {1, -1};
+	const int axis = (error > 0) ? 1 : 0;
+	p[axis] += inc[axis];
+	error += d[1 - axis] * m[axis] * inc.z;
+
+	return cur;
+}
+
 unsigned int
 GeoData::at(glm::ivec2 coord) const
 {
diff --git a/game/geoData.h b/game/geoData.h
index ffb7d64..7bd6ae5 100644
--- a/game/geoData.h
+++ b/game/geoData.h
@@ -32,6 +32,19 @@ public:
 	[[nodiscard]] float getScale() const;
 	[[nodiscard]] std::span<const Node> getNodes() const;
 
+	class RayTracer {
+	public:
+		RayTracer(glm::vec2 p0, glm::vec2 p1, float scale);
+
+		glm::vec2 next();
+
+	private:
+		glm::vec2 p;
+		const glm::vec2 d;
+		float error;
+		glm::vec3 inc;
+	};
+
 protected:
 	Limits limit {}; // Base grid limits first(x,y) -> second(x,y)
 	glm::uvec2 size {};
diff --git a/test/test-geo.cpp b/test/test-geo.cpp
index 63f192b..f0ed693 100644
--- a/test/test-geo.cpp
+++ b/test/test-geo.cpp
@@ -97,4 +97,44 @@ BOOST_AUTO_TEST_CASE(get_height_at)
 	BOOST_CHECK_EQUAL(positionAt({2.5F, 2.5F}), glm::vec3(2.5F, 2.5F, 2.5F));
 }
 
+using TestRayTracerData = std::tuple<glm::vec2, glm::vec2, float, std::vector<glm::vec2>>;
+BOOST_DATA_TEST_CASE(raytracer,
+		boost::unit_test::data::make<TestRayTracerData>({
+				{{0, 0}, {0, 0}, 3,
+						{
+								{0, 0},
+						}},
+				{{0, 0}, {4, 5}, 4,
+						{
+								{0, 0},
+								{0, 4},
+								{4, 4},
+								{4, 8},
+								{8, 8},
+								{8, 12},
+								{12, 12},
+								{12, 16},
+								{16, 16},
+								{16, 20},
+						}},
+				{{-1, -1}, {-4, -5}, 5,
+						{
+								{-1, -1},
+								{-6, -1},
+								{-6, -6},
+								{-6, -11},
+								{-11, -11},
+								{-11, -16},
+								{-16, -16},
+								{-16, -21},
+						}},
+		}),
+		start, end, scale, points)
+{
+	GeoData::RayTracer rt {start, end, scale};
+	for (const auto & point : points) {
+		BOOST_CHECK_CLOSE_VEC(point, rt.next());
+	}
+}
+
 BOOST_AUTO_TEST_SUITE_END()
-- 
cgit v1.2.3