From 582ac127f763f512c45f35e17b768487e3b51796 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 4 Nov 2023 17:07:58 +0000 Subject: Rename TerrainMesh to GeoData to drop inplace --- test/test-geoData.cpp | 175 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 175 insertions(+) create mode 100644 test/test-geoData.cpp (limited to 'test/test-geoData.cpp') diff --git a/test/test-geoData.cpp b/test/test-geoData.cpp new file mode 100644 index 0000000..d79f5b8 --- /dev/null +++ b/test/test-geoData.cpp @@ -0,0 +1,175 @@ +#define BOOST_TEST_MODULE terrain +#include "testHelpers.h" +#include +#include +#include + +#include + +class TestTerrainMesh : public GeoData { +public: + TestTerrainMesh() : GeoData {GeoData::loadFromAsciiGrid(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()); + const auto [lower, upper] = getExtents(); + BOOST_CHECK_EQUAL(lower, glm::vec3(310000, 490000, -2.6)); + BOOST_CHECK_EQUAL(upper, glm::vec3(320000, 500000, 571.6)); +} + +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_CASE(locatePointFace) +{ + const PointFace pf {{310002, 490003}}; + 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(); + +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, GeoData::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 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, + 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(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) +{ + GeoData::PointFace pf {from}; + BOOST_CHECK_NO_THROW(fixedTerrtain.walk(pf, to, [](auto) {})); + BOOST_CHECK_EQUAL(pf.face(&fixedTerrtain).idx(), visits.front()); +} + +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 5ed36466b48aa347277c70422eb00bee264a5c8b Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 4 Nov 2023 17:07:58 +0000 Subject: Simplify some logic with the triangle construct --- game/geoData.cpp | 26 ++++++++++---------------- game/geoData.h | 10 ++++++++-- test/test-geoData.cpp | 3 +-- 3 files changed, 19 insertions(+), 20 deletions(-) (limited to 'test/test-geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index d32bf8c..5e49c94 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -135,8 +135,7 @@ namespace { OpenMesh::FaceHandle GeoData::findPoint(glm::vec2 p, OpenMesh::FaceHandle f) const { - ConstFaceVertexIter vertices; - while (f.is_valid() && !triangleContainsPoint(p, vertices = cfv_iter(f))) { + while (f.is_valid() && !triangleContainsPoint(p, triangle<2>(f))) { for (auto next = cfh_iter(f); next.is_valid(); ++next) { f = opposite_face_handle(*next); if (f.is_valid()) { @@ -156,7 +155,7 @@ glm::vec3 GeoData::positionAt(const PointFace & p) const { glm::vec3 out {}; - Triangle<3> t {this, fv_range(p.face(this))}; + const auto t = triangle<3>(p.face(this)); glm::intersectLineTriangle(p.point ^ 0.F, up, t[0], t[1], t[2], out); return p.point ^ out[0]; } @@ -174,7 +173,7 @@ GeoData::intersectRay(const Ray & ray, FaceHandle face) const 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)}; + const auto t = triangle<3>(face); if (glm::intersectRayTriangle(ray.start, ray.direction, t[0], t[1], t[2], bari, dist)) { out = t * bari; return true; @@ -216,23 +215,18 @@ GeoData::walkUntil(const PointFace & from, const glm::vec2 to, const std::functi } bool -GeoData::triangleContainsPoint(const glm::vec2 p, const glm::vec2 a, const glm::vec2 b, const glm::vec2 c) +GeoData::triangleContainsPoint(const glm::vec2 p, const Triangle<2> & t) { - const auto det = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); + const auto mul = [](const glm::vec2 a, const glm::vec2 b, const glm::vec2 c) { + return (a.x - b.x) * (c.y - b.y) - (a.y - b.y) * (c.x - b.x); + }; + const auto det = mul(t[1], t[0], t[2]); - 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; + return det * mul(t[1], t[0], p) >= 0 && det * mul(t[2], t[1], p) >= 0 && det * mul(t[0], t[2], p) >= 0; } bool GeoData::triangleContainsPoint(const glm::vec2 p, FaceHandle face) const { - return triangleContainsPoint(p, cfv_iter(face)); -} - -bool -GeoData::triangleContainsPoint(const glm::vec2 p, ConstFaceVertexIter vertices) const -{ - return triangleContainsPoint(p, point(*vertices++), point(*vertices++), point(*vertices++)); + return triangleContainsPoint(p, triangle<2>(face)); } diff --git a/game/geoData.h b/game/geoData.h index 3a4f98e..b8561d0 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -85,9 +85,15 @@ public: } protected: - [[nodiscard]] static bool triangleContainsPoint(const glm::vec2, const glm::vec2, const glm::vec2, const glm::vec2); + template + [[nodiscard]] Triangle + triangle(FaceHandle f) const + { + return {this, fv_range(f)}; + } + + [[nodiscard]] static bool triangleContainsPoint(const glm::vec2, const Triangle<2> &); [[nodiscard]] bool triangleContainsPoint(const glm::vec2, FaceHandle) const; - [[nodiscard]] bool triangleContainsPoint(const glm::vec2, ConstFaceVertexIter) const; private: glm::vec3 lowerExtent {}, upperExtent {}; diff --git a/test/test-geoData.cpp b/test/test-geoData.cpp index d79f5b8..b33c61e 100644 --- a/test/test-geoData.cpp +++ b/test/test-geoData.cpp @@ -37,9 +37,8 @@ BOOST_AUTO_TEST_CASE(normalsAllPointUp) 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_TEST_CONTEXT(GeoData::Triangle<2>(this, fv_range(face))) { 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)); -- cgit v1.2.3 From 9ab1214aca7d77e1083476b05c6ddc2bb351bbac Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 4 Nov 2023 19:09:58 +0000 Subject: More tests can just use the global fixed data --- test/test-geoData.cpp | 18 +++++++++--------- 1 file changed, 9 insertions(+), 9 deletions(-) (limited to 'test/test-geoData.cpp') diff --git a/test/test-geoData.cpp b/test/test-geoData.cpp index b33c61e..258bd9c 100644 --- a/test/test-geoData.cpp +++ b/test/test-geoData.cpp @@ -49,27 +49,27 @@ BOOST_AUTO_TEST_CASE(trianglesContainsPoints) } } +BOOST_AUTO_TEST_SUITE_END(); + +static const TestTerrainMesh fixedTerrtain; + BOOST_AUTO_TEST_CASE(locatePointFace) { - const PointFace pf {{310002, 490003}}; + const GeoData::PointFace pf {{310002, 490003}}; BOOST_CHECK(!pf.isLocated()); - BOOST_CHECK(pf.face(this).is_valid()); - BOOST_CHECK_EQUAL(pf.face(this).idx(), 0); + BOOST_CHECK(pf.face(&fixedTerrtain).is_valid()); + BOOST_CHECK_EQUAL(pf.face(&fixedTerrtain).idx(), 0); } BOOST_AUTO_TEST_CASE(preLocatePointFace) { - const PointFace pf {{310002, 490003}, this}; + const GeoData::PointFace pf {{310002, 490003}, &fixedTerrtain}; BOOST_CHECK(pf.isLocated()); - BOOST_CHECK_EQUAL(pf.face(this).idx(), 0); + BOOST_CHECK_EQUAL(pf.face(&fixedTerrtain).idx(), 0); } -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({ -- cgit v1.2.3 From 04078dbb3fe4acd09d150e016c2b2e0d5d036950 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 5 Nov 2023 13:07:32 +0000 Subject: Add methods to walk the boundary of the terrain mesh --- game/geoData.cpp | 45 +++++++++++++++++++++++++++++++++++++++++++++ game/geoData.h | 6 ++++++ test/perf-geoData.cpp | 11 +++++++++++ test/test-geoData.cpp | 10 ++++++++++ 4 files changed, 72 insertions(+) (limited to 'test/test-geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index c58658a..f9c11bf 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -218,6 +218,43 @@ GeoData::walkUntil(const PointFace & from, const glm::vec2 to, const std::functi } } +void +GeoData::boundaryWalk(const std::function & op) const +{ + boundaryWalk(op, findBoundaryStart()); +} + +void +GeoData::boundaryWalk(const std::function & op, HalfedgeHandle start) const +{ + assert(is_boundary(start)); + boundaryWalkUntil( + [&op](auto heh) { + op(heh); + return false; + }, + start); +} + +void +GeoData::boundaryWalkUntil(const std::function & op) const +{ + boundaryWalkUntil(op, findBoundaryStart()); +} + +void +GeoData::boundaryWalkUntil(const std::function & op, HalfedgeHandle start) const +{ + assert(is_boundary(start)); + if (!op(start)) { + for (auto heh = next_halfedge_handle(start); heh != start; heh = next_halfedge_handle(heh)) { + if (op(heh)) { + break; + } + } + } +} + bool GeoData::triangleContainsPoint(const glm::vec2 p, const Triangle<2> & t) { @@ -230,3 +267,11 @@ GeoData::triangleContainsPoint(const glm::vec2 p, FaceHandle face) const { return triangleContainsPoint(p, triangle<2>(face)); } + +GeoData::HalfedgeHandle +GeoData::findBoundaryStart() const +{ + return *std::find_if(halfedges_begin(), halfedges_end(), [this](const auto heh) { + return is_boundary(heh); + }); +} diff --git a/game/geoData.h b/game/geoData.h index b8561d0..15d7e24 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -78,6 +78,11 @@ public: 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; + void boundaryWalk(const std::function &) const; + void boundaryWalk(const std::function &, HalfedgeHandle start) const; + void boundaryWalkUntil(const std::function &) const; + void boundaryWalkUntil(const std::function &, HalfedgeHandle start) const; + [[nodiscard]] auto getExtents() const { @@ -94,6 +99,7 @@ protected: [[nodiscard]] static bool triangleContainsPoint(const glm::vec2, const Triangle<2> &); [[nodiscard]] bool triangleContainsPoint(const glm::vec2, FaceHandle) const; + [[nodiscard]] HalfedgeHandle findBoundaryStart() const; private: glm::vec3 lowerExtent {}, upperExtent {}; diff --git a/test/perf-geoData.cpp b/test/perf-geoData.cpp index 2d79a90..4fed632 100644 --- a/test/perf-geoData.cpp +++ b/test/perf-geoData.cpp @@ -23,9 +23,20 @@ namespace { }); } } + + void + terrain_walkBoundary(benchmark::State & state) + { + for (auto _ : state) { + tm.boundaryWalk([](auto heh) { + benchmark::DoNotOptimize(heh); + }); + } + } } BENCHMARK(terrain_findPoint); BENCHMARK(terrain_walk); +BENCHMARK(terrain_walkBoundary); BENCHMARK_MAIN(); diff --git a/test/test-geoData.cpp b/test/test-geoData.cpp index 258bd9c..34c9cb6 100644 --- a/test/test-geoData.cpp +++ b/test/test-geoData.cpp @@ -118,6 +118,16 @@ BOOST_DATA_TEST_CASE(findRayIntersect, BOOST_CHECK_CLOSE_VEC(fixedTerrtain.intersectRay({p, d}).value(), i); } +BOOST_AUTO_TEST_CASE(boundaryWalk) +{ + size_t count {}; + fixedTerrtain.boundaryWalk([&count](auto heh) { + BOOST_CHECK(fixedTerrtain.is_boundary(heh)); + count++; + }); + BOOST_CHECK_EQUAL(count, 2 * (ncols + nrows - 2)); +} + using WalkTerrainData = std::tuple>; BOOST_DATA_TEST_CASE(walkTerrain, -- cgit v1.2.3 From acca54f3a12225454633dca2d56506c0dcebb653 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 5 Nov 2023 15:37:13 +0000 Subject: Fix calculating extents --- game/geoData.cpp | 4 ++-- test/test-geoData.cpp | 2 +- 2 files changed, 3 insertions(+), 3 deletions(-) (limited to 'test/test-geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index 78f753f..781b41e 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -25,8 +25,8 @@ GeoData::loadFromAsciiGrid(const std::filesystem::path & input) vertices.reserve(ncols * nrows); GeoData mesh; mesh.lowerExtent = {xllcorner, yllcorner, std::numeric_limits::max()}; - mesh.upperExtent - = {xllcorner + (cellsize * ncols), yllcorner + (cellsize * nrows), std::numeric_limits::min()}; + mesh.upperExtent = {xllcorner + (cellsize * (ncols - 1)), yllcorner + (cellsize * (nrows - 1)), + std::numeric_limits::min()}; for (size_t row = 0; row < nrows; ++row) { for (size_t col = 0; col < ncols; ++col) { float height = 0; diff --git a/test/test-geoData.cpp b/test/test-geoData.cpp index 34c9cb6..2ea9b26 100644 --- a/test/test-geoData.cpp +++ b/test/test-geoData.cpp @@ -21,7 +21,7 @@ BOOST_AUTO_TEST_CASE(loadSuccess) BOOST_CHECK_EQUAL(2 * (ncols - 1) * (nrows - 1), n_faces()); const auto [lower, upper] = getExtents(); BOOST_CHECK_EQUAL(lower, glm::vec3(310000, 490000, -2.6)); - BOOST_CHECK_EQUAL(upper, glm::vec3(320000, 500000, 571.6)); + BOOST_CHECK_EQUAL(upper, glm::vec3(319950, 499950, 571.6)); } BOOST_AUTO_TEST_CASE(normalsAllPointUp) -- cgit v1.2.3 From 58402765133fab24d08b64f3752553bd2b8393b9 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 5 Nov 2023 15:52:02 +0000 Subject: Fix todo for handling a terrain walk from outside the mesh --- game/geoData.cpp | 22 ++++++++++++++++++++-- game/geoData.h | 2 ++ test/test-geoData.cpp | 5 +++++ 3 files changed, 27 insertions(+), 2 deletions(-) (limited to 'test/test-geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index 781b41e..61dedda 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -210,8 +210,10 @@ GeoData::walk(const PointFace & from, const glm::vec2 to, const std::function & op) const { - assert(from.face(this).is_valid()); // TODO replace with a boundary search auto f = from.face(this); + if (!f.is_valid()) { + f = opposite_face_handle(findEntry(from.point, to)); + } FaceHandle previousFace; while (f.is_valid() && !op(f)) { for (auto next = cfh_iter(f); next.is_valid(); ++next) { @@ -241,7 +243,7 @@ GeoData::boundaryWalk(const std::function & op, HalfedgeHa assert(is_boundary(start)); boundaryWalkUntil( [&op](auto heh) { - op(heh); + op(heh); return false; }, start); @@ -266,6 +268,22 @@ GeoData::boundaryWalkUntil(const std::function & op, Halfe } } +GeoData::HalfedgeHandle +GeoData::findEntry(const glm::vec2 from, const glm::vec2 to) const +{ + HalfedgeHandle entry; + boundaryWalkUntil([this, from, to, &entry](auto he) { + const auto e1 = point(to_vertex_handle(he)); + const auto e2 = point(to_vertex_handle(opposite_halfedge_handle(he))); + if (linesCrossLtR(from, to, e1, e2)) { + entry = he; + return true; + } + return false; + }); + return entry; +} + bool GeoData::triangleContainsPoint(const glm::vec2 p, const Triangle<2> & t) { diff --git a/game/geoData.h b/game/geoData.h index 15d7e24..474731b 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -83,6 +83,8 @@ public: void boundaryWalkUntil(const std::function &) const; void boundaryWalkUntil(const std::function &, HalfedgeHandle start) const; + [[nodiscard]] HalfedgeHandle findEntry(const glm::vec2 from, const glm::vec2 to) const; + [[nodiscard]] auto getExtents() const { diff --git a/test/test-geoData.cpp b/test/test-geoData.cpp index 2ea9b26..447ab37 100644 --- a/test/test-geoData.cpp +++ b/test/test-geoData.cpp @@ -139,6 +139,11 @@ BOOST_DATA_TEST_CASE(walkTerrain, {{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}}, + {{310002, 490003}, {309999, 489999}, {0}}, + {{309999, 489999}, {310002, 490003}, {0}}, + {{320002, 500003}, {319949, 499948}, {79201}}, + {{309999, 490003}, {310004, 489997}, {0, 1}}, + {{310004, 489997}, {309999, 490003}, {1, 0}}, }), from, to, visits) { -- cgit v1.2.3 From 3abe940a22d99939b666bd806214c8b986cb3ed9 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 26 Nov 2023 14:20:28 +0000 Subject: Calculate vertex normals only Doesn't require half edge normals or face normals, which uses Newell's method, which results in integer overflow... Not to mention we don't need all the other normals. --- game/geoData.cpp | 16 ++++++++++++---- game/geoData.h | 6 ++++-- test/test-geoData.cpp | 5 ----- 3 files changed, 16 insertions(+), 11 deletions(-) (limited to 'test/test-geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index 7710efe..70133a9 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -57,8 +57,7 @@ GeoData::loadFromAsciiGrid(const std::filesystem::path & input) }); } } - mesh.update_face_normals(); - mesh.update_vertex_normals(); + mesh.update_vertex_normals_only(); return mesh; }; @@ -77,8 +76,7 @@ GeoData::createFlat(GlobalPosition2D lower, GlobalPosition2D upper, GlobalDistan mesh.add_face(ll, uu, lu); mesh.add_face(ll, ul, uu); - mesh.update_face_normals(); - mesh.update_vertex_normals(); + mesh.update_vertex_normals_only(); return mesh; } @@ -317,3 +315,13 @@ GeoData::findBoundaryStart() const return is_boundary(heh); }); } + +void +GeoData::update_vertex_normals_only() +{ + for (auto vh : all_vertices()) { + Normal3D n; + calc_vertex_normal_correct(vh, n); + this->set_normal(vh, glm::normalize(n)); + } +} diff --git a/game/geoData.h b/game/geoData.h index 3141dbe..d4d0fb3 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -10,10 +10,10 @@ #include struct GeoDataTraits : public OpenMesh::DefaultTraits { - FaceAttributes(OpenMesh::Attributes::Normal | OpenMesh::Attributes::Status); + FaceAttributes(OpenMesh::Attributes::Status); EdgeAttributes(OpenMesh::Attributes::Status); VertexAttributes(OpenMesh::Attributes::Normal | OpenMesh::Attributes::Status); - HalfedgeAttributes(OpenMesh::Attributes::Normal | OpenMesh::Attributes::Status); + HalfedgeAttributes(OpenMesh::Attributes::Status); using Point = GlobalPosition3D; using Normal = Normal3D; }; @@ -105,6 +105,8 @@ protected: [[nodiscard]] bool triangleContainsPoint(const GlobalPosition2D, FaceHandle) const; [[nodiscard]] HalfedgeHandle findBoundaryStart() const; + void update_vertex_normals_only(); + private: GlobalPosition3D lowerExtent {}, upperExtent {}; }; diff --git a/test/test-geoData.cpp b/test/test-geoData.cpp index 4e85f73..cb0466e 100644 --- a/test/test-geoData.cpp +++ b/test/test-geoData.cpp @@ -26,11 +26,6 @@ BOOST_AUTO_TEST_CASE(loadSuccess) BOOST_AUTO_TEST_CASE(normalsAllPointUp) { - BOOST_CHECK_EQUAL(std::count_if(faces_begin(), faces_end(), - [this](auto && vh) { - return normal(vh).z > 0; - }), - n_faces()); BOOST_CHECK_EQUAL(std::count_if(vertices_begin(), vertices_end(), [this](auto && vh) { return normal(vh).z > 0; -- cgit v1.2.3 From 0f56b13766fc6d8b45dabc4febf378756620ab32 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 2 Dec 2023 12:26:36 +0000 Subject: Replace positionAt with pure integer version --- game/geoData.cpp | 15 +++++++++++---- test/test-geoData.cpp | 2 +- 2 files changed, 12 insertions(+), 5 deletions(-) (limited to 'test/test-geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index 70133a9..d092d00 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -155,6 +155,16 @@ namespace { static_assert(linesCrossLtR({1, 1}, {2, 2}, {1, 2}, {2, 1})); static_assert(!linesCrossLtR({2, 2}, {1, 1}, {1, 2}, {2, 1})); + + constexpr GlobalPosition3D + positionOnTriangle(const GlobalPosition2D point, const GeoData::Triangle<3> & t) + { + const glm::vec<3, int64_t> a = t[1] - t[0], b = t[2] - t[0]; + const auto n = crossInt(a, b); + return {point, ((n.x * t[0].x) + (n.y * t[0].y) + (n.z * t[0].z) - (n.x * point.x) - (n.y * point.y)) / n.z}; + } + + static_assert(positionOnTriangle({7, -2}, {{1, 2, 3}, {1, 0, 1}, {-2, 1, 0}}) == GlobalPosition3D {7, -2, 3}); } OpenMesh::FaceHandle @@ -179,10 +189,7 @@ GeoData::findPoint(GlobalPosition2D p, OpenMesh::FaceHandle f) const GlobalPosition3D GeoData::positionAt(const PointFace & p) const { - RelativePosition3D out {}; - const auto t = triangle<3>(p.face(this)); - glm::intersectLineTriangle({p.point, 0}, up, t[0], t[1], t[2], out); - return {p.point, out[0]}; + return positionOnTriangle(p.point, triangle<3>(p.face(this))); } [[nodiscard]] std::optional diff --git a/test/test-geoData.cpp b/test/test-geoData.cpp index cb0466e..164a6a5 100644 --- a/test/test-geoData.cpp +++ b/test/test-geoData.cpp @@ -92,7 +92,7 @@ BOOST_DATA_TEST_CASE(findPositionAt, {{310050000, 490050000}, 33000}, {{310000000, 490050000}, 32700}, {{310050000, 490000000}, 33200}, - {{310750000, 490150000}, 58399}, + {{310750000, 490150000}, 58400}, // midpoints {{310025000, 490025000}, 32900}, {{310025000, 490050000}, 32850}, -- cgit v1.2.3 From 9ae29335b72b6db037a78428ff8493d1fb587103 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 2 Dec 2023 16:38:12 +0000 Subject: Test case for finding ray entry points --- test/test-geoData.cpp | 13 +++++++++++++ 1 file changed, 13 insertions(+) (limited to 'test/test-geoData.cpp') diff --git a/test/test-geoData.cpp b/test/test-geoData.cpp index 164a6a5..d1c6b8b 100644 --- a/test/test-geoData.cpp +++ b/test/test-geoData.cpp @@ -186,3 +186,16 @@ BOOST_DATA_TEST_CASE(walkTerrainUntil, })); BOOST_CHECK_EQUAL_COLLECTIONS(visited.begin(), visited.end(), visits.begin(), visits.end()); } + +using FindEntiesData = std::tuple; + +BOOST_DATA_TEST_CASE(findEntries, + boost::unit_test::data::make({ + {{307739360, 494851616}, {314056992, 500079744}, 160667}, + {{308597952, 498417056}, {315154144, 504671456}, 233623}, + {{302690592, 502270912}, {311585184, 497868064}, 207311}, + }), + from, to, heh) +{ + BOOST_CHECK_EQUAL(fixedTerrtain.findEntry(from, to).idx(), heh); +} -- cgit v1.2.3