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 --- game/terrain2.cpp | 66 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 66 insertions(+) create mode 100644 game/terrain2.cpp (limited to 'game/terrain2.cpp') diff --git a/game/terrain2.cpp b/game/terrain2.cpp new file mode 100644 index 0000000..83df3fa --- /dev/null +++ b/game/terrain2.cpp @@ -0,0 +1,66 @@ +#include "terrain2.h" +#include + +TerrainMesh::TerrainMesh(const std::filesystem::path & input) +{ + size_t ncols = 0, nrows = 0, xllcorner = 0, yllcorner = 0, cellsize = 0; + std::map properties { + {"ncols", &ncols}, + {"nrows", &nrows}, + {"xllcorner", &xllcorner}, + {"yllcorner", &yllcorner}, + {"cellsize", &cellsize}, + }; + std::ifstream f {input}; + while (!properties.empty()) { + std::string property; + f >> property; + f >> *properties.at(property); + properties.erase(property); + } + std::vector vertices; + vertices.reserve(ncols * nrows); + for (size_t row = 0; row < nrows; ++row) { + for (size_t col = 0; col < ncols; ++col) { + float height = 0; + f >> height; + vertices.push_back(add_vertex({xllcorner + (col * cellsize), yllcorner + (row * cellsize), height})); + } + } + if (!f.good()) { + throw std::runtime_error("Couldn't read terrain file"); + } + for (size_t row = 1; row < nrows; ++row) { + for (size_t col = 1; col < ncols; ++col) { + add_face({ + vertices[ncols * (row - 1) + (col - 1)], + vertices[ncols * (row - 0) + (col - 0)], + vertices[ncols * (row - 0) + (col - 1)], + }); + add_face({ + vertices[ncols * (row - 1) + (col - 1)], + vertices[ncols * (row - 1) + (col - 0)], + vertices[ncols * (row - 0) + (col - 0)], + }); + } + } + update_face_normals(); + update_vertex_normals(); +}; + +bool +TerrainMesh::triangleContainsPoint(const glm::vec2 p, const glm::vec2 a, const glm::vec2 b, const glm::vec2 c) +{ + const auto det = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); + + return det * ((b.x - a.x) * (p.y - a.y) - (b.y - a.y) * (p.x - a.x)) >= 0 + && det * ((c.x - b.x) * (p.y - b.y) - (c.y - b.y) * (p.x - b.x)) >= 0 + && det * ((a.x - c.x) * (p.y - c.y) - (a.y - c.y) * (p.x - c.x)) >= 0; +} + +bool +TerrainMesh::triangleContainsPoint(const glm::vec2 p, FaceHandle face) const +{ + auto vertices = cfv_iter(face); + return triangleContainsPoint(p, point(*vertices++), point(*vertices++), point(*vertices++)); +} -- 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 ++++++++++++++++++++++++++++++++- 1 file changed, 32 insertions(+), 1 deletion(-) (limited to 'game/terrain2.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++)); } -- 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 ++++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 54 insertions(+), 1 deletion(-) (limited to 'game/terrain2.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) { -- 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 ++++++++++++++++++ 1 file changed, 18 insertions(+) (limited to 'game/terrain2.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) -- 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 ++++++----- 1 file changed, 6 insertions(+), 5 deletions(-) (limited to 'game/terrain2.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; } -- 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 +++++++++++++++++++++------------ 1 file changed, 21 insertions(+), 12 deletions(-) (limited to 'game/terrain2.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) { -- 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 +++++++++++ 1 file changed, 11 insertions(+) (limited to 'game/terrain2.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 { -- 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 +++++++++++++++++++++++ 1 file changed, 23 insertions(+) (limited to 'game/terrain2.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 { -- cgit v1.2.3