summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--game/terrain2.cpp55
-rw-r--r--game/terrain2.h3
-rw-r--r--test/test-terrain.cpp41
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());
+}