2 files changed, 57 insertions, 1 deletions

diff --git a/game/terrain2.cpp b/game/terrain2.cpp
index cc0bf90..3e24778 100644
--- a/game/terrain2.cpp
+++ b/game/terrain2.cpp
@@ -54,6 +54,28 @@ TerrainMesh::findPoint(glm::vec2 p) const
 	return findPoint(p, *faces_begin());
 }
 
+namespace {
+	[[nodiscard]] constexpr inline bool
+	pointLeftOfLine(const glm::vec2 p, const glm::vec2 e1, const glm::vec2 e2)
+	{
+		return (e2.x - e1.x) * (p.y - e1.y) > (e2.y - e1.y) * (p.x - e1.x);
+	}
+
+	static_assert(pointLeftOfLine({1, 2}, {1, 1}, {2, 2}));
+	static_assert(pointLeftOfLine({2, 1}, {2, 2}, {1, 1}));
+	static_assert(pointLeftOfLine({2, 2}, {1, 2}, {2, 1}));
+	static_assert(pointLeftOfLine({1, 1}, {2, 1}, {1, 2}));
+
+	[[nodiscard]] constexpr inline bool
+	linesCross(const glm::vec2 a1, const glm::vec2 a2, const glm::vec2 b1, const glm::vec2 b2)
+	{
+		return pointLeftOfLine(a2, b1, b2) && pointLeftOfLine(a1, b2, b1) && pointLeftOfLine(b1, a1, a2)
+				&& pointLeftOfLine(b2, a2, a1);
+	}
+
+	static_assert(linesCross({1, 1}, {2, 2}, {1, 2}, {2, 1}));
+}
+
 OpenMesh::FaceHandle
 TerrainMesh::findPoint(glm::vec2 p, OpenMesh::FaceHandle f) const
 {
@@ -64,7 +86,7 @@ TerrainMesh::findPoint(glm::vec2 p, OpenMesh::FaceHandle f) const
 			if (f.is_valid()) {
 				const auto e1 = point(to_vertex_handle(*next));
 				const auto e2 = point(to_vertex_handle(opposite_halfedge_handle(*next)));
-				if ((e2.x - e1.x) * (p.y - e1.y) > (e2.y - e1.y) * (p.x - e1.x)) {
+				if (pointLeftOfLine(p, e1, e2)) {
 					break;
 				}
 			}
@@ -74,6 +96,37 @@ TerrainMesh::findPoint(glm::vec2 p, OpenMesh::FaceHandle f) const
 	return f;
 }
 
+void
+TerrainMesh::walk(const glm::vec2 from, const glm::vec2 to, const std::function<void(FaceHandle)> & op) const
+{
+	walkUntil(from, to, [&op](const auto & fh) {
+		op(fh);
+		return false;
+	});
+}
+
+void
+TerrainMesh::walkUntil(const glm::vec2 from, const glm::vec2 to, const std::function<bool(FaceHandle)> & op) const
+{
+	auto f = findPoint(from);
+	assert(f.is_valid()); // TODO replace with a boundary search
+	FaceHandle previousFace;
+	while (f.is_valid() && !op(f)) {
+		for (auto next = cfh_iter(f); next.is_valid(); ++next) {
+			f = opposite_face_handle(*next);
+			if (f.is_valid() && f != previousFace) {
+				const auto e1 = point(to_vertex_handle(*next));
+				const auto e2 = point(to_vertex_handle(opposite_halfedge_handle(*next)));
+				if (linesCross(from, to, e1, e2)) {
+					previousFace = f;
+					break;
+				}
+			}
+			f.reset();
+		}
+	}
+}
+
 bool
 TerrainMesh::triangleContainsPoint(const glm::vec2 p, const glm::vec2 a, const glm::vec2 b, const glm::vec2 c)
 {
diff --git a/game/terrain2.h b/game/terrain2.h
index 713fe23..848c36e 100644
--- a/game/terrain2.h
+++ b/game/terrain2.h
@@ -21,6 +21,9 @@ public:
 	[[nodiscard]] FaceHandle findPoint(glm::vec2) const;
 	[[nodiscard]] FaceHandle findPoint(glm::vec2, FaceHandle start) const;
 
+	void walk(const glm::vec2 from, const glm::vec2 to, const std::function<void(FaceHandle)> & op) const;
+	void walkUntil(const glm::vec2 from, const glm::vec2 to, const std::function<bool(FaceHandle)> & op) const;
+
 protected:
 	[[nodiscard]] static bool triangleContainsPoint(const glm::vec2, const glm::vec2, const glm::vec2, const glm::vec2);
 	[[nodiscard]] bool triangleContainsPoint(const glm::vec2, FaceHandle) const;