Ray Trace cursor clicks to terrain surface

4 files changed, 121 insertions, 9 deletions

diff --git a/game/geoData.cpp b/game/geoData.cpp
index 32ec55e..c9e909b 100644
--- a/game/geoData.cpp
+++ b/game/geoData.cpp
@@ -4,8 +4,10 @@
 #include <array>
 #include <cmath>
 #include <cstddef>
+#include <glm/gtx/intersect.hpp>
 #include <maths.h>
 #include <random>
+#include <ray.hpp>
 #include <stb/stb_image.h>
 #include <stdexcept>
 #include <util.h>
@@ -132,6 +134,38 @@ GeoData::RayTracer::next()
 	return cur;
 }
 
+std::optional<glm::vec3>
+GeoData::intersectRay(const Ray & ray) const
+{
+	if (glm::length(!ray.direction) <= 0) {
+		return {};
+	}
+	RayTracer rt {ray.start / scale, ray.direction};
+	while (true) {
+		const auto n {rt.next() * scale};
+		try {
+			const auto point = quad(n);
+			for (auto offset : {0U, 1U}) {
+				glm::vec2 bary;
+				float distance;
+				if (glm::intersectRayTriangle(ray.start, ray.direction, point[offset], point[offset + 1],
+							point[offset + 2], bary, distance)) {
+					return point[offset] + ((point[offset + 1] - point[offset]) * bary[0])
+							+ ((point[offset + 2] - point[offset]) * bary[1]);
+				}
+			}
+		}
+		catch (std::range_error &) {
+			const auto rel = n / !ray.direction;
+			if (rel.x > 0 && rel.y > 0) {
+				return {};
+			}
+		}
+	}
+
+	return {};
+}
+
 unsigned int
 GeoData::at(glm::ivec2 coord) const
 {
diff --git a/game/geoData.h b/game/geoData.h
index a296205..42c2d9d 100644
--- a/game/geoData.h
+++ b/game/geoData.h
@@ -2,10 +2,13 @@
 
 #include <filesystem>
 #include <glm/glm.hpp>
+#include <optional>
 #include <span>
 #include <utility>
 #include <vector>
 
+class Ray;
+
 class GeoData {
 public:
 	struct Node {
@@ -22,6 +25,7 @@ public:
 	void loadFromImages(const std::filesystem::path &, float scale);
 
 	[[nodiscard]] glm::vec3 positionAt(glm::vec2) const;
+	[[nodiscard]] std::optional<glm::vec3> intersectRay(const Ray &) const;
 
 	[[nodiscard]] unsigned int at(glm::ivec2) const;
 	[[nodiscard]] unsigned int at(int x, int y) const;
diff --git a/test/test-geo.cpp b/test/test-geo.cpp
index 07e3bd1..7f072bc 100644
--- a/test/test-geo.cpp
+++ b/test/test-geo.cpp
@@ -6,11 +6,20 @@
 #include <stream_support.hpp>
 
 #include <game/geoData.h>
+#include <lib/ray.hpp>
 
 struct TestGeoData : public GeoData {
 	TestGeoData() : GeoData {{{-10, -5}, {30, 40}}, 5.F} { }
 };
 
+namespace std {
+	std::ostream &
+	operator<<(std::ostream & s, const Ray & r)
+	{
+		return (s << r.start << "->" << r.direction);
+	}
+}
+
 BOOST_FIXTURE_TEST_SUITE(tgd, TestGeoData)
 
 BOOST_AUTO_TEST_CASE(initialize)
@@ -134,4 +143,74 @@ BOOST_DATA_TEST_CASE(raytracer,
 	}
 }
 
+using TestRayData = std::tuple<glm::vec3, glm::vec3, glm::vec3>;
+BOOST_TEST_DECORATOR(*boost::unit_test::timeout(1))
+BOOST_DATA_TEST_CASE(intersect_ray,
+		boost::unit_test::data::make<TestRayData>({
+				{{-1, -1, 1.0}, {1, 1, 0}, {0, 0, 1}},
+				{{-1, -1, 2.5}, {1, 1, 0}, {2.5F, 2.5F, 2.5F}},
+				{{-20, -20, 2.5}, {1, 1, 0}, {2.5F, 2.5F, 2.5F}},
+				// outside the map looking in
+				{{-205, -205, 4}, {1, 1, 0}, {5, 5, 4}},
+				{{-205, 5, 4}, {1, 0, 0}, {5, 5, 4}},
+				{{-205, 215, 4}, {1, -1, 0}, {5, 5, 4}},
+				{{215, -205, 4}, {-1, 1, 0}, {5, 5, 4}},
+				{{215, 5, 4}, {-1, 0, 0}, {5, 5, 4}},
+				{{215, 215, 4}, {-1, -1, 0}, {5, 5, 4}},
+				{{5, 215, 4}, {0, -1, 0}, {5, 5, 4}},
+				{{5, -205, 4}, {0, 1, 0}, {5, 5, 4}},
+		}),
+		start, dir, pos)
+{
+	// at(x,y) is index based
+	nodes[at(0, 0)].height = 1;
+	nodes[at(1, 0)].height = 2;
+	nodes[at(0, 1)].height = 3;
+	nodes[at(1, 1)].height = 4;
+
+	const auto intersect = intersectRay({start, glm::normalize(dir)});
+	BOOST_REQUIRE(intersect);
+	BOOST_CHECK_CLOSE_VEC(*intersect, pos);
+}
+
+auto xs = boost::unit_test::data::xrange(-20.F, 0.F, 0.6F), ys = boost::unit_test::data::xrange(-20.F, 0.F, 0.7F);
+auto targetsx = boost::unit_test::data::xrange(0.2F, 4.9F, 1.3F),
+	 targetsy = boost::unit_test::data::xrange(0.3F, 4.9F, 1.3F);
+BOOST_TEST_DECORATOR(*boost::unit_test::timeout(1))
+BOOST_DATA_TEST_CASE(intersect_ray_many, xs * ys * targetsx * targetsy, x, y, targetx, targety)
+{
+	// at(x,y) is index based
+	nodes[at(0, 0)].height = 1;
+	nodes[at(1, 0)].height = 2;
+	nodes[at(0, 1)].height = 3;
+	nodes[at(1, 1)].height = 4;
+
+	glm::vec3 start {x, y, 10};
+	const auto target {this->positionAt({targetx, targety})};
+	Ray ray {start, glm::normalize(target - start)};
+	BOOST_TEST_CONTEXT(ray) {
+		const auto intersect = intersectRay(ray);
+		BOOST_REQUIRE(intersect);
+		BOOST_CHECK_CLOSE_VEC(*intersect, target);
+	}
+}
+
+BOOST_TEST_DECORATOR(*boost::unit_test::timeout(1))
+BOOST_DATA_TEST_CASE(intersect_ray_miss,
+		boost::unit_test::data::make<Ray>({
+				{{3, 3, 5}, {-1, -1, 0}},
+				{{0, 0, 5}, {0, 0, 1}},
+				{{0, 0, 5}, {0, 0, -1}},
+		}),
+		ray)
+{
+	// at(x,y) is index based
+	nodes[at(0, 0)].height = 1;
+	nodes[at(1, 0)].height = 2;
+	nodes[at(0, 1)].height = 3;
+	nodes[at(1, 1)].height = 4;
+
+	BOOST_REQUIRE(!intersectRay(ray));
+}
+
 BOOST_AUTO_TEST_SUITE_END()
diff --git a/ui/gameMainWindow.cpp b/ui/gameMainWindow.cpp
index d53db4b..1724927 100644
--- a/ui/gameMainWindow.cpp
+++ b/ui/gameMainWindow.cpp
@@ -70,16 +70,11 @@ public:
 						const auto & ref = *selected.base()->get();
 						clicked = typeid(ref).name();
 					}
+					else if (const auto pos = gameState->geoData->intersectRay(ray)) {
+						clicked = streamed_string(*pos);
+					}
 					else {
-						try {
-							const auto dist = camera->pos.z / -ray.direction.z;
-							const auto pos = !camera->pos + (!ray.direction * dist);
-
-							clicked = streamed_string(gameState->geoData->positionAt(pos));
-						}
-						catch (std::range_error &) {
-							clicked.clear();
-						}
+						clicked.clear();
 					}
 				}
 		}