diff options
| -rw-r--r-- | game/terrain2.cpp | 55 | ||||
| -rw-r--r-- | game/terrain2.h | 3 | ||||
| -rw-r--r-- | test/test-terrain.cpp | 41 |
3 files changed, 98 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; 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<glm::vec2, glm::vec2, std::vector<int>>; + +BOOST_DATA_TEST_CASE(walkTerrain, + boost::unit_test::data::make<WalkTerrainData>({ + {{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<int> 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<WalkTerrainData>({ + {{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<int> 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()); +} |