From 16bec12e3e75e95d251745f904ac4e15af9c9724 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 28 Oct 2023 02:34:45 +0100 Subject: Initial OpenMesh based terrain data and tests --- test/test-terrain.cpp | 48 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 48 insertions(+) create mode 100644 test/test-terrain.cpp (limited to 'test/test-terrain.cpp') diff --git a/test/test-terrain.cpp b/test/test-terrain.cpp new file mode 100644 index 0000000..b2358d6 --- /dev/null +++ b/test/test-terrain.cpp @@ -0,0 +1,48 @@ +#define BOOST_TEST_MODULE terrain +#include +#include + +#include + +class TestTerrainMesh : public TerrainMesh { +public: + TestTerrainMesh() : TerrainMesh {FIXTURESDIR "height/SD19.asc"} { } +}; + +constexpr size_t ncols = 200, nrows = 200, xllcorner = 310000, yllcorner = 490000, cellsize = 50; + +BOOST_FIXTURE_TEST_SUITE(ttm, TestTerrainMesh); + +BOOST_AUTO_TEST_CASE(loadSuccess) +{ + BOOST_CHECK_EQUAL(ncols * nrows, n_vertices()); + BOOST_CHECK_EQUAL(2 * (ncols - 1) * (nrows - 1), n_faces()); +} + +BOOST_AUTO_TEST_CASE(normalsAllPointUp) +{ + BOOST_CHECK(std::all_of(faces_begin(), faces_end(), [this](auto && vh) { + return normal(vh).z > 0; + })); + BOOST_CHECK(std::all_of(vertices_begin(), vertices_end(), [this](auto && vh) { + return normal(vh).z > 0; + })); +} + +BOOST_AUTO_TEST_CASE(trianglesContainsPoints) +{ + const auto face = face_handle(0); + auto vertices = cfv_iter(face); + + BOOST_TEST_CONTEXT(point(*vertices++) << point(*vertices++) << point(*vertices++)) { + BOOST_CHECK(triangleContainsPoint(glm::vec2 {xllcorner, yllcorner}, face)); + BOOST_CHECK(triangleContainsPoint(glm::vec2 {xllcorner + cellsize, yllcorner + cellsize}, face)); + BOOST_CHECK(triangleContainsPoint(glm::vec2 {xllcorner, yllcorner + cellsize}, face)); + BOOST_CHECK(triangleContainsPoint(glm::vec2 {xllcorner + 1, yllcorner + 1}, face)); + BOOST_CHECK(triangleContainsPoint(glm::vec2 {xllcorner + 1, yllcorner + 2}, face)); + BOOST_CHECK(!triangleContainsPoint(glm::vec2 {xllcorner + 3, yllcorner + 2}, face)); + BOOST_CHECK(!triangleContainsPoint(glm::vec2 {xllcorner + cellsize, yllcorner}, face)); + } +} + +BOOST_AUTO_TEST_SUITE_END(); -- cgit v1.2.3 From 49a422ed91289a31142a8c0fb8b7030d2dea98a1 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe 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 (limited to 'test/test-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 { 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 : : : test ; run test-glContainer.cpp : : : test ; run test-pack.cpp : : : test ; run test-terrain.cpp : : : test ..//OpenMeshCore ; +run perf-terrain.cpp : : : test ..//OpenMeshCore 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 +#include + +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 #include #include @@ -46,3 +47,21 @@ BOOST_AUTO_TEST_CASE(trianglesContainsPoints) } BOOST_AUTO_TEST_SUITE_END(); + +using FindPointData = std::tuple; + +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({ + {{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( + {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 From 583aa8eb078090fd48c6d6db8ee69da5ad8811fb Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Tue, 31 Oct 2023 00:29:35 +0000 Subject: Initial commit of walk/walkUtil terrain --- game/terrain2.cpp | 55 ++++++++++++++++++++++++++++++++++++++++++++++++++- game/terrain2.h | 3 +++ test/test-terrain.cpp | 41 ++++++++++++++++++++++++++++++++++++++ 3 files changed, 98 insertions(+), 1 deletion(-) (limited to 'test/test-terrain.cpp') 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 & 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 & 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 & op) const; + void walkUntil(const glm::vec2 from, const glm::vec2 to, const std::function & 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; diff --git a/test/test-terrain.cpp b/test/test-terrain.cpp index d062853..429207c 100644 --- a/test/test-terrain.cpp +++ b/test/test-terrain.cpp @@ -65,3 +65,44 @@ BOOST_DATA_TEST_CASE(findPointOnTerrain, { BOOST_CHECK_EQUAL(fh, fixedTerrtain.findPoint(p, TerrainMesh::FaceHandle(start)).idx()); } + +using WalkTerrainData = std::tuple>; + +BOOST_DATA_TEST_CASE(walkTerrain, + boost::unit_test::data::make({ + {{310002, 490003}, {310002, 490003}, {0}}, + {{310003, 490002}, {310003, 490002}, {1}}, + {{310002, 490003}, {310003, 490002}, {0, 1}}, + {{310003, 490002}, {310002, 490003}, {1, 0}}, + {{310002, 490003}, {310202, 490003}, {0, 1, 2, 3, 4, 5, 6, 7, 8}}, + {{310202, 490003}, {310002, 490003}, {8, 7, 6, 5, 4, 3, 2, 1, 0}}, + {{310002, 490003}, {310002, 490203}, {0, 399, 398, 797, 796, 1195, 1194, 1593, 1592}}, + }), + from, to, visits) +{ + std::vector visited; + BOOST_CHECK_NO_THROW(fixedTerrtain.walk(from, to, [&visited](auto fh) { + visited.emplace_back(fh.idx()); + })); + BOOST_CHECK_EQUAL_COLLECTIONS(visited.begin(), visited.end(), visits.begin(), visits.end()); +} + +BOOST_DATA_TEST_CASE(walkTerrainUntil, + boost::unit_test::data::make({ + {{310002, 490003}, {310002, 490003}, {0}}, + {{310003, 490002}, {310003, 490002}, {1}}, + {{310002, 490003}, {310003, 490002}, {0, 1}}, + {{310003, 490002}, {310002, 490003}, {1, 0}}, + {{310002, 490003}, {310202, 490003}, {0, 1, 2, 3, 4}}, + {{310202, 490003}, {310002, 490003}, {8, 7, 6, 5, 4}}, + {{310002, 490003}, {310002, 490203}, {0, 399, 398, 797, 796}}, + }), + from, to, visits) +{ + std::vector visited; + BOOST_CHECK_NO_THROW(fixedTerrtain.walkUntil(from, to, [&visited](auto fh) { + visited.emplace_back(fh.idx()); + return visited.size() >= 5; + })); + BOOST_CHECK_EQUAL_COLLECTIONS(visited.begin(), visited.end(), visits.begin(), visits.end()); +} -- cgit v1.2.3 From a0f1dc90aabd4cb5cfe2aef7116af170e6d0b953 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Tue, 31 Oct 2023 01:26:58 +0000 Subject: Helper type for storing/passing/returning a point and its containing face point is const as face is mutable as a cache of the face containing point. --- game/terrain2.cpp | 18 ++++++++++++++++++ game/terrain2.h | 10 ++++++++++ test/test-terrain.cpp | 9 +++++++++ 3 files changed, 37 insertions(+) (limited to 'test/test-terrain.cpp') diff --git a/game/terrain2.cpp b/game/terrain2.cpp index 3e24778..e98cebb 100644 --- a/game/terrain2.cpp +++ b/game/terrain2.cpp @@ -54,6 +54,24 @@ TerrainMesh::findPoint(glm::vec2 p) const return findPoint(p, *faces_begin()); } +bool +TerrainMesh::locate(const TerrainMesh::PointFace & pointFace, FaceHandle start) const +{ + if (pointFace.face.is_valid()) { + assert(triangleContainsPoint(pointFace.point, pointFace.face)); + return true; + } + else { + return (pointFace.face = findPoint(pointFace.point, start)).is_valid(); + } +} + +bool +TerrainMesh::locate(const TerrainMesh::PointFace & pointFace) const +{ + return locate(pointFace, *faces_begin()); +} + namespace { [[nodiscard]] constexpr inline bool pointLeftOfLine(const glm::vec2 p, const glm::vec2 e1, const glm::vec2 e2) diff --git a/game/terrain2.h b/game/terrain2.h index 848c36e..e516719 100644 --- a/game/terrain2.h +++ b/game/terrain2.h @@ -18,6 +18,13 @@ class TerrainMesh : public OpenMesh::TriMesh_ArrayKernelT { public: explicit TerrainMesh(const std::filesystem::path &); + struct PointFace { + PointFace(const glm::vec2 p) : point {p} { } + + const glm::vec2 point; + mutable FaceHandle face {}; + }; + [[nodiscard]] FaceHandle findPoint(glm::vec2) const; [[nodiscard]] FaceHandle findPoint(glm::vec2, FaceHandle start) const; @@ -28,4 +35,7 @@ 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; + + bool locate(const PointFace &) const; + bool locate(const PointFace &, FaceHandle start) const; }; diff --git a/test/test-terrain.cpp b/test/test-terrain.cpp index 429207c..f737f4f 100644 --- a/test/test-terrain.cpp +++ b/test/test-terrain.cpp @@ -46,6 +46,15 @@ BOOST_AUTO_TEST_CASE(trianglesContainsPoints) } } +BOOST_AUTO_TEST_CASE(locatePointFace) +{ + const PointFace pf {{310002, 490003}}; + BOOST_CHECK(!pf.face.is_valid()); + BOOST_CHECK(locate(pf)); + BOOST_CHECK(pf.face.is_valid()); + BOOST_CHECK_EQUAL(pf.face.idx(), 0); +} + BOOST_AUTO_TEST_SUITE_END(); using FindPointData = std::tuple; -- cgit v1.2.3 From a4f1c55ad34f6be9adc9573fd7f26507ae2c59b0 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Tue, 31 Oct 2023 02:40:03 +0000 Subject: Update walk/walkUntil to work on PointFace from parameter --- game/terrain2.cpp | 11 ++++++----- game/terrain2.h | 4 ++-- test/test-terrain.cpp | 14 ++++++++++++++ 3 files changed, 22 insertions(+), 7 deletions(-) (limited to 'test/test-terrain.cpp') diff --git a/game/terrain2.cpp b/game/terrain2.cpp index e98cebb..5d1c595 100644 --- a/game/terrain2.cpp +++ b/game/terrain2.cpp @@ -115,7 +115,7 @@ TerrainMesh::findPoint(glm::vec2 p, OpenMesh::FaceHandle f) const } void -TerrainMesh::walk(const glm::vec2 from, const glm::vec2 to, const std::function & op) const +TerrainMesh::walk(const PointFace & from, const glm::vec2 to, const std::function & op) const { walkUntil(from, to, [&op](const auto & fh) { op(fh); @@ -124,10 +124,11 @@ TerrainMesh::walk(const glm::vec2 from, const glm::vec2 to, const std::function< } void -TerrainMesh::walkUntil(const glm::vec2 from, const glm::vec2 to, const std::function & op) const +TerrainMesh::walkUntil(const PointFace & from, const glm::vec2 to, const std::function & op) const { - auto f = findPoint(from); - assert(f.is_valid()); // TODO replace with a boundary search + locate(from); + assert(from.face.is_valid()); // TODO replace with a boundary search + auto f = from.face; FaceHandle previousFace; while (f.is_valid() && !op(f)) { for (auto next = cfh_iter(f); next.is_valid(); ++next) { @@ -135,7 +136,7 @@ TerrainMesh::walkUntil(const glm::vec2 from, const glm::vec2 to, const std::func 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)) { + if (linesCross(from.point, to, e1, e2)) { previousFace = f; break; } diff --git a/game/terrain2.h b/game/terrain2.h index e516719..1a4e263 100644 --- a/game/terrain2.h +++ b/game/terrain2.h @@ -28,8 +28,8 @@ 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 & op) const; - void walkUntil(const glm::vec2 from, const glm::vec2 to, const std::function & op) const; + void walk(const PointFace & from, const glm::vec2 to, const std::function & op) const; + void walkUntil(const PointFace & from, const glm::vec2 to, const std::function & op) const; protected: [[nodiscard]] static bool triangleContainsPoint(const glm::vec2, const glm::vec2, const glm::vec2, const glm::vec2); diff --git a/test/test-terrain.cpp b/test/test-terrain.cpp index f737f4f..bf30179 100644 --- a/test/test-terrain.cpp +++ b/test/test-terrain.cpp @@ -96,6 +96,20 @@ BOOST_DATA_TEST_CASE(walkTerrain, BOOST_CHECK_EQUAL_COLLECTIONS(visited.begin(), visited.end(), visits.begin(), visits.end()); } +BOOST_DATA_TEST_CASE(walkTerrainSetsFromFace, + boost::unit_test::data::make({ + {{310002, 490003}, {310002, 490003}, {0}}, + {{310003, 490002}, {310003, 490002}, {1}}, + {{310002, 490003}, {310003, 490002}, {0, 1}}, + {{310003, 490002}, {310002, 490003}, {1, 0}}, + }), + from, to, visits) +{ + TerrainMesh::PointFace pf {from}; + BOOST_CHECK_NO_THROW(fixedTerrtain.walk(pf, to, [](auto) {})); + BOOST_CHECK_EQUAL(pf.face.idx(), visits.front()); +} + BOOST_DATA_TEST_CASE(walkTerrainUntil, boost::unit_test::data::make({ {{310002, 490003}, {310002, 490003}, {0}}, -- cgit v1.2.3 From b46cf55d66f262778bf0353650f00620c7740f2a Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Tue, 31 Oct 2023 19:36:16 +0000 Subject: Make PointFace harder to misuse --- game/terrain2.cpp | 33 +++++++++++++++++++++------------ game/terrain2.h | 21 +++++++++++++++++---- test/test-terrain.cpp | 16 +++++++++++----- 3 files changed, 49 insertions(+), 21 deletions(-) (limited to 'test/test-terrain.cpp') diff --git a/game/terrain2.cpp b/game/terrain2.cpp index 5d1c595..8d29143 100644 --- a/game/terrain2.cpp +++ b/game/terrain2.cpp @@ -54,22 +54,32 @@ TerrainMesh::findPoint(glm::vec2 p) const return findPoint(p, *faces_begin()); } -bool -TerrainMesh::locate(const TerrainMesh::PointFace & pointFace, FaceHandle start) const +TerrainMesh::PointFace::PointFace(const glm::vec2 p, const TerrainMesh * mesh) : + PointFace {p, mesh, *mesh->faces_begin()} +{ +} + +TerrainMesh::PointFace::PointFace(const glm::vec2 p, const TerrainMesh * mesh, FaceHandle start) : + PointFace {p, mesh->findPoint(p, start)} { - if (pointFace.face.is_valid()) { - assert(triangleContainsPoint(pointFace.point, pointFace.face)); - return true; +} + +TerrainMesh::FaceHandle +TerrainMesh::PointFace::face(const TerrainMesh * mesh, FaceHandle start) const +{ + if (_face.is_valid()) { + assert(mesh->triangleContainsPoint(point, _face)); + return _face; } else { - return (pointFace.face = findPoint(pointFace.point, start)).is_valid(); + return (_face = mesh->findPoint(point, start)); } } -bool -TerrainMesh::locate(const TerrainMesh::PointFace & pointFace) const +TerrainMesh::FaceHandle +TerrainMesh::PointFace::face(const TerrainMesh * mesh) const { - return locate(pointFace, *faces_begin()); + return face(mesh, *mesh->faces_begin()); } namespace { @@ -126,9 +136,8 @@ TerrainMesh::walk(const PointFace & from, const glm::vec2 to, const std::functio void TerrainMesh::walkUntil(const PointFace & from, const glm::vec2 to, const std::function & op) const { - locate(from); - assert(from.face.is_valid()); // TODO replace with a boundary search - auto f = from.face; + assert(from.face(this).is_valid()); // TODO replace with a boundary search + auto f = from.face(this); FaceHandle previousFace; while (f.is_valid() && !op(f)) { for (auto next = cfh_iter(f); next.is_valid(); ++next) { diff --git a/game/terrain2.h b/game/terrain2.h index 1a4e263..641d608 100644 --- a/game/terrain2.h +++ b/game/terrain2.h @@ -19,10 +19,26 @@ public: explicit TerrainMesh(const std::filesystem::path &); struct PointFace { + // NOLINTNEXTLINE(hicpp-explicit-conversions) PointFace(const glm::vec2 p) : point {p} { } + PointFace(const glm::vec2 p, FaceHandle face) : point {p}, _face {face} { } + + PointFace(const glm::vec2 p, const TerrainMesh *); + PointFace(const glm::vec2 p, const TerrainMesh *, FaceHandle start); + const glm::vec2 point; - mutable FaceHandle face {}; + [[nodiscard]] FaceHandle face(const TerrainMesh *) const; + [[nodiscard]] FaceHandle face(const TerrainMesh *, FaceHandle start) const; + + [[nodiscard]] bool + isLocated() const + { + return _face.is_valid(); + } + + private: + mutable FaceHandle _face {}; }; [[nodiscard]] FaceHandle findPoint(glm::vec2) const; @@ -35,7 +51,4 @@ 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; - - bool locate(const PointFace &) const; - bool locate(const PointFace &, FaceHandle start) const; }; diff --git a/test/test-terrain.cpp b/test/test-terrain.cpp index bf30179..bf73356 100644 --- a/test/test-terrain.cpp +++ b/test/test-terrain.cpp @@ -49,10 +49,16 @@ BOOST_AUTO_TEST_CASE(trianglesContainsPoints) BOOST_AUTO_TEST_CASE(locatePointFace) { const PointFace pf {{310002, 490003}}; - BOOST_CHECK(!pf.face.is_valid()); - BOOST_CHECK(locate(pf)); - BOOST_CHECK(pf.face.is_valid()); - BOOST_CHECK_EQUAL(pf.face.idx(), 0); + BOOST_CHECK(!pf.isLocated()); + BOOST_CHECK(pf.face(this).is_valid()); + BOOST_CHECK_EQUAL(pf.face(this).idx(), 0); +} + +BOOST_AUTO_TEST_CASE(preLocatePointFace) +{ + const PointFace pf {{310002, 490003}, this}; + BOOST_CHECK(pf.isLocated()); + BOOST_CHECK_EQUAL(pf.face(this).idx(), 0); } BOOST_AUTO_TEST_SUITE_END(); @@ -107,7 +113,7 @@ BOOST_DATA_TEST_CASE(walkTerrainSetsFromFace, { TerrainMesh::PointFace pf {from}; BOOST_CHECK_NO_THROW(fixedTerrtain.walk(pf, to, [](auto) {})); - BOOST_CHECK_EQUAL(pf.face.idx(), visits.front()); + BOOST_CHECK_EQUAL(pf.face(&fixedTerrtain).idx(), visits.front()); } BOOST_DATA_TEST_CASE(walkTerrainUntil, -- cgit v1.2.3 From 8a5d36623e4fa261aea16731954c9987dcbb1ef1 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Thu, 2 Nov 2023 20:38:10 +0000 Subject: Terrain mesh method for getting the height/position at a point on the surface --- game/terrain2.cpp | 11 +++++++++++ game/terrain2.h | 2 ++ test/test-terrain.cpp | 23 +++++++++++++++++++++++ 3 files changed, 36 insertions(+) (limited to 'test/test-terrain.cpp') diff --git a/game/terrain2.cpp b/game/terrain2.cpp index 8d29143..b129284 100644 --- a/game/terrain2.cpp +++ b/game/terrain2.cpp @@ -1,5 +1,7 @@ #include "terrain2.h" #include +#include +#include TerrainMesh::TerrainMesh(const std::filesystem::path & input) { @@ -124,6 +126,15 @@ TerrainMesh::findPoint(glm::vec2 p, OpenMesh::FaceHandle f) const return f; } +glm::vec3 +TerrainMesh::positionAt(const PointFace & p) const +{ + glm::vec3 out {}; + Triangle<3> t {this, fv_range(p.face(this))}; + glm::intersectLineTriangle(p.point ^ 0.F, up, t[0], t[1], t[2], out); + return p.point ^ out[0]; +} + void TerrainMesh::walk(const PointFace & from, const glm::vec2 to, const std::function & op) const { diff --git a/game/terrain2.h b/game/terrain2.h index c2c3d19..f1d288e 100644 --- a/game/terrain2.h +++ b/game/terrain2.h @@ -58,6 +58,8 @@ public: [[nodiscard]] FaceHandle findPoint(glm::vec2) const; [[nodiscard]] FaceHandle findPoint(glm::vec2, FaceHandle start) const; + [[nodiscard]] glm::vec3 positionAt(const PointFace &) const; + void walk(const PointFace & from, const glm::vec2 to, const std::function & op) const; void walkUntil(const PointFace & from, const glm::vec2 to, const std::function & op) const; diff --git a/test/test-terrain.cpp b/test/test-terrain.cpp index bf73356..38cb51f 100644 --- a/test/test-terrain.cpp +++ b/test/test-terrain.cpp @@ -1,4 +1,5 @@ #define BOOST_TEST_MODULE terrain +#include "testHelpers.h" #include #include #include @@ -81,6 +82,28 @@ BOOST_DATA_TEST_CASE(findPointOnTerrain, BOOST_CHECK_EQUAL(fh, fixedTerrtain.findPoint(p, TerrainMesh::FaceHandle(start)).idx()); } +using FindPositionData = std::tuple; + +BOOST_DATA_TEST_CASE(findPositionAt, + boost::unit_test::data::make({ + // corners + {{310000, 490000}, 32.8F}, + {{310050, 490050}, 33.0F}, + {{310000, 490050}, 32.7F}, + {{310050, 490000}, 33.2F}, + {{310750, 490150}, 58.4F}, + // midpoints + {{310025, 490025}, 32.9F}, + {{310025, 490050}, 32.85F}, + {{310000, 490025}, 32.75F}, + // other + {{310751, 490152}, 58.326F}, + }), + p, h) +{ + BOOST_CHECK_CLOSE_VEC(fixedTerrtain.positionAt(p), p ^ h); +} + using WalkTerrainData = std::tuple>; BOOST_DATA_TEST_CASE(walkTerrain, -- cgit v1.2.3 From 3931bda936aba6ddae26c1d9f1d450781df800e8 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Fri, 3 Nov 2023 20:12:03 +0000 Subject: Implement terrain intersect ray --- game/terrain2.cpp | 23 +++++++++++++++++++++++ game/terrain2.h | 4 ++++ test/test-terrain.cpp | 12 ++++++++++++ 3 files changed, 39 insertions(+) (limited to 'test/test-terrain.cpp') diff --git a/game/terrain2.cpp b/game/terrain2.cpp index b129284..d1af221 100644 --- a/game/terrain2.cpp +++ b/game/terrain2.cpp @@ -135,6 +135,29 @@ TerrainMesh::positionAt(const PointFace & p) const return p.point ^ out[0]; } +[[nodiscard]] std::optional +TerrainMesh::intersectRay(const Ray & ray) const +{ + return intersectRay(ray, findPoint(ray.start)); +} + +[[nodiscard]] std::optional +TerrainMesh::intersectRay(const Ray & ray, FaceHandle face) const +{ + std::optional out; + walkUntil(PointFace {ray.start, face}, ray.start + (ray.direction * 10000.F), [&out, &ray, this](FaceHandle face) { + glm::vec2 bari {}; + float dist {}; + Triangle<3> t {this, fv_range(face)}; + if (glm::intersectRayTriangle(ray.start, ray.direction, t[0], t[1], t[2], bari, dist)) { + out = t * bari; + return true; + } + return false; + }); + return out; +} + void TerrainMesh::walk(const PointFace & from, const glm::vec2 to, const std::function & op) const { diff --git a/game/terrain2.h b/game/terrain2.h index da9f823..5539a50 100644 --- a/game/terrain2.h +++ b/game/terrain2.h @@ -1,9 +1,11 @@ #pragma once #include "collections.h" // IWYU pragma: keep IterableCollection +#include "ray.h" #include #include #include +#include #include struct TerrainTraits : public OpenMesh::DefaultTraits { @@ -66,6 +68,8 @@ public: [[nodiscard]] FaceHandle findPoint(glm::vec2, FaceHandle start) const; [[nodiscard]] glm::vec3 positionAt(const PointFace &) const; + [[nodiscard]] std::optional intersectRay(const Ray &) const; + [[nodiscard]] std::optional intersectRay(const Ray &, FaceHandle start) const; void walk(const PointFace & from, const glm::vec2 to, const std::function & op) const; void walkUntil(const PointFace & from, const glm::vec2 to, const std::function & op) const; diff --git a/test/test-terrain.cpp b/test/test-terrain.cpp index 38cb51f..53eebfb 100644 --- a/test/test-terrain.cpp +++ b/test/test-terrain.cpp @@ -104,6 +104,18 @@ BOOST_DATA_TEST_CASE(findPositionAt, BOOST_CHECK_CLOSE_VEC(fixedTerrtain.positionAt(p), p ^ h); } +using FindRayIntersectData = std::tuple; + +BOOST_DATA_TEST_CASE(findRayIntersect, + boost::unit_test::data::make({ + {{310000, 490000, 50}, {1, 1, -2}, {310008.59, 490008.59, 32.834301}}, + {{310000, 490000, 50}, {1, 1, -1}, {310017.12, 490017.12, 32.868526}}, + }), + p, d, i) +{ + BOOST_CHECK_CLOSE_VEC(fixedTerrtain.intersectRay({p, d}).value(), i); +} + using WalkTerrainData = std::tuple>; BOOST_DATA_TEST_CASE(walkTerrain, -- cgit v1.2.3