From 49a422ed91289a31142a8c0fb8b7030d2dea98a1 Mon Sep 17 00:00:00 2001
From: Dan Goodliffe <dan@randomdan.homeip.net>
Date: Sun, 29 Oct 2023 14:11:46 +0000
Subject: Initial commit of findPoint on terrain

2D navigate from a default/given starting point, possible scope for improvement, but it's
not exactly slow; <9ms
---
 game/terrain2.cpp     | 33 ++++++++++++++++++++++++++++++++-
 game/terrain2.h       |  4 ++++
 test/Jamfile.jam      |  4 +++-
 test/perf-terrain.cpp | 18 ++++++++++++++++++
 test/test-terrain.cpp | 19 +++++++++++++++++++
 5 files changed, 76 insertions(+), 2 deletions(-)
 create mode 100644 test/perf-terrain.cpp

diff --git a/game/terrain2.cpp b/game/terrain2.cpp
index 83df3fa..cc0bf90 100644
--- a/game/terrain2.cpp
+++ b/game/terrain2.cpp
@@ -48,6 +48,32 @@ TerrainMesh::TerrainMesh(const std::filesystem::path & input)
 	update_vertex_normals();
 };
 
+OpenMesh::FaceHandle
+TerrainMesh::findPoint(glm::vec2 p) const
+{
+	return findPoint(p, *faces_begin());
+}
+
+OpenMesh::FaceHandle
+TerrainMesh::findPoint(glm::vec2 p, OpenMesh::FaceHandle f) const
+{
+	ConstFaceVertexIter vertices;
+	while (f.is_valid() && !triangleContainsPoint(p, vertices = cfv_iter(f))) {
+		for (auto next = cfh_iter(f); next.is_valid(); ++next) {
+			f = opposite_face_handle(*next);
+			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)) {
+					break;
+				}
+			}
+			f.reset();
+		}
+	}
+	return f;
+}
+
 bool
 TerrainMesh::triangleContainsPoint(const glm::vec2 p, const glm::vec2 a, const glm::vec2 b, const glm::vec2 c)
 {
@@ -61,6 +87,11 @@ TerrainMesh::triangleContainsPoint(const glm::vec2 p, const glm::vec2 a, const g
 bool
 TerrainMesh::triangleContainsPoint(const glm::vec2 p, FaceHandle face) const
 {
-	auto vertices = cfv_iter(face);
+	return triangleContainsPoint(p, cfv_iter(face));
+}
+
+bool
+TerrainMesh::triangleContainsPoint(const glm::vec2 p, ConstFaceVertexIter vertices) const
+{
 	return triangleContainsPoint(p, point(*vertices++), point(*vertices++), point(*vertices++));
 }
diff --git a/game/terrain2.h b/game/terrain2.h
index d2da8d0..713fe23 100644
--- a/game/terrain2.h
+++ b/game/terrain2.h
@@ -18,7 +18,11 @@ class TerrainMesh : public OpenMesh::TriMesh_ArrayKernelT<TerrainTraits> {
 public:
 	explicit TerrainMesh(const std::filesystem::path &);
 
+	[[nodiscard]] FaceHandle findPoint(glm::vec2) const;
+	[[nodiscard]] FaceHandle findPoint(glm::vec2, FaceHandle start) 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;
+	[[nodiscard]] bool triangleContainsPoint(const glm::vec2, ConstFaceVertexIter) const;
 };
diff --git a/test/Jamfile.jam b/test/Jamfile.jam
index eab3996..7fa7bfc 100644
--- a/test/Jamfile.jam
+++ b/test/Jamfile.jam
@@ -61,9 +61,11 @@ run test-instancing.cpp : : : <library>test ;
 run test-glContainer.cpp : : : <library>test ;
 run test-pack.cpp : : : <library>test ;
 run test-terrain.cpp : : : <library>test <library>..//OpenMeshCore ;
+run perf-terrain.cpp : : : <library>test <library>..//OpenMeshCore <library>benchmark ;
 compile test-static-enumDetails.cpp ;
 compile test-static-stream_support.cpp ;
 explicit perf-assetFactory ;
 explicit perf-persistence ;
-alias perf : perf-assetFactory perf-persistence ;
+explicit perf-terrain ;
+alias perf : perf-assetFactory perf-persistence perf-terrain ;
 explicit perf ;
diff --git a/test/perf-terrain.cpp b/test/perf-terrain.cpp
new file mode 100644
index 0000000..e998f60
--- /dev/null
+++ b/test/perf-terrain.cpp
@@ -0,0 +1,18 @@
+#include <benchmark/benchmark.h>
+#include <game/terrain2.h>
+
+namespace {
+	const TerrainMesh tm {FIXTURESDIR "height/SD19.asc"};
+
+	void
+	terrain_findPoint(benchmark::State & state)
+	{
+		for (auto _ : state) {
+			benchmark::DoNotOptimize(tm.findPoint({315555, 495556}));
+		}
+	}
+}
+
+BENCHMARK(terrain_findPoint);
+
+BENCHMARK_MAIN();
diff --git a/test/test-terrain.cpp b/test/test-terrain.cpp
index b2358d6..d062853 100644
--- a/test/test-terrain.cpp
+++ b/test/test-terrain.cpp
@@ -1,4 +1,5 @@
 #define BOOST_TEST_MODULE terrain
+#include <boost/test/data/test_case.hpp>
 #include <boost/test/unit_test.hpp>
 #include <stream_support.h>
 
@@ -46,3 +47,21 @@ BOOST_AUTO_TEST_CASE(trianglesContainsPoints)
 }
 
 BOOST_AUTO_TEST_SUITE_END();
+
+using FindPointData = std::tuple<glm::vec2, int>;
+
+static const TestTerrainMesh fixedTerrtain;
+
+// No boundary cases as these can produce different valid results depending on starting point
+BOOST_DATA_TEST_CASE(findPointOnTerrain,
+		boost::unit_test::data::make<FindPointData>({
+				{{0, 0}, -1}, {{xllcorner, 0}, -1}, {{0, yllcorner}, -1}, {{xllcorner + 1, yllcorner + 2}, 0},
+				{{xllcorner + (cellsize * (nrows - 1)) - 2, yllcorner + (cellsize * (ncols - 1)) - 1}, 79200},
+				{{315555, 495556}, 44400}, // perf test target
+		})
+				* boost::unit_test::data::make<int>(
+						{0, 1, 2, 3, 4, 5, 6, 10, 100, 150, 200, 1000, 1234, 17439, 79201, 79200, 79199}),
+		p, fh, start)
+{
+	BOOST_CHECK_EQUAL(fh, fixedTerrtain.findPoint(p, TerrainMesh::FaceHandle(start)).idx());
+}
-- 
cgit v1.2.3