From b4576e3a40d0416dea4e82042905598680fba3ee Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 15 Dec 2024 15:00:08 +0000 Subject: Reuse close edges when adding new vertices for surface --- game/geoData.cpp | 50 +++++++++++++++++++++++++++++++++++++------------- 1 file changed, 37 insertions(+), 13 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index a5fc4ef..d3b5485 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -430,6 +430,19 @@ GeoData::setHeights(const std::span triangleStrip, const return std::make_pair(v, glm::length(::difference(p, this->point(v).xy()))); }; }; + const auto vertexDistFromE = [this](GlobalPosition2D p) { + return [p, this](const HalfedgeHandle e) { + const auto fromPoint = point(from_vertex_handle(e)).xy(); + const auto toPoint = point(to_vertex_handle(e)).xy(); + return std::make_pair(e, Triangle<2> {fromPoint, toPoint, p}.height()); + }; + }; + const auto notBoundary = std::views::filter([this](auto handleItr) { + return !is_boundary(*handleItr); + }); + const auto notEdgeBoundary = std::views::filter([this](auto handleItr) { + return !is_boundary(edge_handle(*handleItr)); + }); std::set newOrChangedVerts; auto addVertexForNormalUpdate = [this, &newOrChangedVerts](const VertexHandle vertex) { @@ -437,21 +450,32 @@ GeoData::setHeights(const std::span triangleStrip, const std::ranges::copy(vv_range(vertex), std::inserter(newOrChangedVerts, newOrChangedVerts.end())); }; - // New vertices for each vertex in triangleStrip std::vector newVerts; + auto newVertexOnFace = [this, &vertexDistFrom, &opts, &vertexDistFromE, &newVerts, ¬Boundary, ¬EdgeBoundary]( + GlobalPosition3D tsPoint) { + const auto face = findPoint(tsPoint); + // Check vertices + if (const auto nearest = std::ranges::min(std::views::iota(fv_begin(face), fv_end(face)) | notBoundary + | std::views::transform(vertexDistFrom(tsPoint)), + {}, &std::pair::second); + nearest.second < opts.nearNodeTolerance && !std::ranges::contains(newVerts, nearest.first)) { + point(nearest.first) = tsPoint; + return nearest.first; + } + // Check edges + if (const auto nearest = std::ranges::min(std::views::iota(fh_begin(face), fh_end(face)) | notEdgeBoundary + | std::views::transform(vertexDistFromE(tsPoint)), + {}, &std::pair::second); + nearest.second < opts.nearNodeTolerance) { + return split(edge_handle(nearest.first), tsPoint); + } + // Nothing close, split face + return split(face, tsPoint); + }; + + // New vertices for each vertex in triangleStrip newVerts.reserve(newVerts.size()); - std::transform(triangleStrip.begin(), triangleStrip.end(), std::back_inserter(newVerts), - [this, &newVerts, &vertexDistFrom, &opts](const auto tsPoint) { - const auto face = findPoint(tsPoint); - if (const auto nearest = std::ranges::min(std::views::iota(fv_begin(face), fv_end(face)) - | std::views::transform(vertexDistFrom(tsPoint)), - {}, &std::pair::second); - nearest.second < opts.nearNodeTolerance && !std::ranges::contains(newVerts, nearest.first)) { - point(nearest.first) = tsPoint; - return nearest.first; - } - return split(face, tsPoint); - }); + std::transform(triangleStrip.begin(), triangleStrip.end(), std::back_inserter(newVerts), newVertexOnFace); std::ranges::for_each(newVerts, addVertexForNormalUpdate); // Create temporary triangles from triangleStrip -- cgit v1.2.3 From c54004cc4003698cd4583ea49e50f8993a9f953b Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Wed, 18 Dec 2024 14:55:33 +0000 Subject: Don't make arbitrary changes to mesh for triangle corners Making these arbitrary changes can lead to inverted adjacent faces, instead just: a) use the near node where it is, or b) create the edge split along its length without lateral movement Removes the check that these are already used and/or boundaries as they're not being changed now anyway. --- game/geoData.cpp | 35 +++++++++++++++++------------------ 1 file changed, 17 insertions(+), 18 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index d3b5485..8d7e18a 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -437,12 +437,6 @@ GeoData::setHeights(const std::span triangleStrip, const return std::make_pair(e, Triangle<2> {fromPoint, toPoint, p}.height()); }; }; - const auto notBoundary = std::views::filter([this](auto handleItr) { - return !is_boundary(*handleItr); - }); - const auto notEdgeBoundary = std::views::filter([this](auto handleItr) { - return !is_boundary(edge_handle(*handleItr)); - }); std::set newOrChangedVerts; auto addVertexForNormalUpdate = [this, &newOrChangedVerts](const VertexHandle vertex) { @@ -450,31 +444,36 @@ GeoData::setHeights(const std::span triangleStrip, const std::ranges::copy(vv_range(vertex), std::inserter(newOrChangedVerts, newOrChangedVerts.end())); }; - std::vector newVerts; - auto newVertexOnFace = [this, &vertexDistFrom, &opts, &vertexDistFromE, &newVerts, ¬Boundary, ¬EdgeBoundary]( - GlobalPosition3D tsPoint) { + auto newVertexOnFace = [this, &vertexDistFrom, &opts, &vertexDistFromE](GlobalPosition3D tsPoint) { const auto face = findPoint(tsPoint); // Check vertices - if (const auto nearest = std::ranges::min(std::views::iota(fv_begin(face), fv_end(face)) | notBoundary - | std::views::transform(vertexDistFrom(tsPoint)), - {}, &std::pair::second); - nearest.second < opts.nearNodeTolerance && !std::ranges::contains(newVerts, nearest.first)) { - point(nearest.first) = tsPoint; + if (const auto nearest = std::ranges::min( + std::views::iota(fv_begin(face), fv_end(face)) | std::views::transform(vertexDistFrom(tsPoint)), {}, + &std::pair::second); + nearest.second < opts.nearNodeTolerance) { return nearest.first; } // Check edges - if (const auto nearest = std::ranges::min(std::views::iota(fh_begin(face), fh_end(face)) | notEdgeBoundary - | std::views::transform(vertexDistFromE(tsPoint)), + if (const auto nearest = std::ranges::min( + std::views::iota(fh_begin(face), fh_end(face)) | std::views::transform(vertexDistFromE(tsPoint)), {}, &std::pair::second); nearest.second < opts.nearNodeTolerance) { - return split(edge_handle(nearest.first), tsPoint); + const auto from = point(from_vertex_handle(nearest.first)).xy(); + const auto to = point(to_vertex_handle(nearest.first)).xy(); + const auto v = vector_normal(from - to); + const auto inter = linesIntersectAt(from, to, tsPoint.xy(), tsPoint.xy() + v); + if (!inter) { + throw std::runtime_error("Perpendicular lines do not cross"); + } + return split(edge_handle(nearest.first), *inter || tsPoint.z); } // Nothing close, split face return split(face, tsPoint); }; // New vertices for each vertex in triangleStrip - newVerts.reserve(newVerts.size()); + std::vector newVerts; + newVerts.reserve(triangleStrip.size()); std::transform(triangleStrip.begin(), triangleStrip.end(), std::back_inserter(newVerts), newVertexOnFace); std::ranges::for_each(newVerts, addVertexForNormalUpdate); -- cgit v1.2.3 From 9f80b4b9ed43db91035ed3ddbf9bad4c40c9cf9d Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Wed, 18 Dec 2024 14:55:33 +0000 Subject: Don't make arbitrary changes to mesh for triangle boundaries Making these arbitrary changes can lead to inverted adjacent faces, instead just: a) use the near node where it is, or b) create the edge split along its length without lateral movement Same principal as previous commit, addresses issues where tracing would fail seemingly at random and throws on error now. --- game/geoData.cpp | 66 +++++++++++++++++++++++++++------------------------ test/test-geoData.cpp | 2 +- 2 files changed, 36 insertions(+), 32 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index 8d7e18a..643b24b 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -497,40 +497,44 @@ GeoData::setHeights(const std::span triangleStrip, const // Cut along each edge of triangleStrip AB, AC, BC, BD, CD, CE etc std::map *> boundaryTriangles; - auto doBoundaryPart = [this, &boundaryTriangles, &newVerts, &vertexDistFrom, &opts, &addVertexForNormalUpdate]( + auto doBoundaryPart = [this, &boundaryTriangles, &vertexDistFrom, &opts, &addVertexForNormalUpdate]( VertexHandle start, VertexHandle end, const Triangle<3> & triangle) { boundaryTriangles.emplace(start, &triangle); const auto endPoint = point(end); - while (!std::ranges::contains(vv_range(start), end) - && std::ranges::any_of(voh_range(start), [&](const auto & outHalf) { - const auto next = next_halfedge_handle(outHalf); - const auto startPoint = point(start); - const auto nexts = std::array {from_vertex_handle(next), to_vertex_handle(next)}; - const auto nextPoints = nexts | std::views::transform([this](const auto v) { - return std::make_pair(v, this->point(v)); - }); - if (linesCross(startPoint, endPoint, nextPoints.front().second, nextPoints.back().second)) { - if (const auto intersection = linesIntersectAt(startPoint.xy(), endPoint.xy(), - nextPoints.front().second.xy(), nextPoints.back().second.xy())) { - if (const auto nextDist - = std::ranges::min(nexts | std::views::transform(vertexDistFrom(*intersection)), - {}, &std::pair::second); - nextDist.second < opts.nearNodeTolerance - && !boundaryTriangles.contains(nextDist.first) - && !std::ranges::contains(newVerts, nextDist.first)) { - start = nextDist.first; - point(start) = positionOnTriangle(*intersection, triangle); - } - else { - start = split(edge_handle(next), positionOnTriangle(*intersection, triangle)); - } - addVertexForNormalUpdate(start); - boundaryTriangles.emplace(start, &triangle); - return true; - } - } - return false; - })) { } + while (!std::ranges::contains(vv_range(start), end)) { + const auto startPoint = point(start); + if (std::ranges::none_of(voh_range(start), [&](const auto & outHalf) { + const auto next = next_halfedge_handle(outHalf); + const auto nexts = std::array {from_vertex_handle(next), to_vertex_handle(next)}; + const auto nextPoints = nexts | std::views::transform([this](const auto v) { + return std::make_pair(v, this->point(v)); + }); + if (linesCross(startPoint, endPoint, nextPoints.front().second, nextPoints.back().second)) { + if (const auto intersection = linesIntersectAt(startPoint.xy(), endPoint.xy(), + nextPoints.front().second.xy(), nextPoints.back().second.xy())) { + const auto newPosition = positionOnTriangle(*intersection, triangle); + if (const auto nextDist + = std::ranges::min(nexts | std::views::transform(vertexDistFrom(*intersection)), {}, + &std::pair::second); + nextDist.second < opts.nearNodeTolerance) { + start = nextDist.first; + return true; + } + else { + start = split(edge_handle(next), newPosition); + } + addVertexForNormalUpdate(start); + boundaryTriangles.emplace(start, &triangle); + return true; + } + throw std::runtime_error("Crossing lines don't intersect"); + } + return false; + })) { + throw std::runtime_error( + std::format("Could not navigate to ({}, {}, {})", endPoint.x, endPoint.y, endPoint.z)); + } + } }; auto doBoundary = [&doBoundaryPart, triangle = strip.begin()](const auto & verts) mutable { const auto & [a, b, c] = verts; diff --git a/test/test-geoData.cpp b/test/test-geoData.cpp index 1ca050d..5998789 100644 --- a/test/test-geoData.cpp +++ b/test/test-geoData.cpp @@ -269,6 +269,6 @@ BOOST_DATA_TEST_CASE( auto gd = std::make_shared(GeoData::createFlat({0, 0}, {1000000, 1000000}, 100)); for (const auto & strip : points) { BOOST_REQUIRE_GE(strip.size(), 3); - BOOST_CHECK_NO_THROW(gd->setHeights(strip, {.surface = surface})); + BOOST_CHECK_NO_THROW(gd->setHeights(strip, {.surface = surface, .nearNodeTolerance = 50})); } } -- cgit v1.2.3 From 8185a79abb71aa6ad0d3ca3719047372440291c4 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Wed, 18 Dec 2024 16:03:47 +0000 Subject: Don't cut internal boundaries Existing terrain contains enough nodes, assumes input surface is flat. For non-flat requires, submit several surfaces. --- game/geoData.cpp | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index 643b24b..8e662b3 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -537,12 +537,12 @@ GeoData::setHeights(const std::span triangleStrip, const } }; auto doBoundary = [&doBoundaryPart, triangle = strip.begin()](const auto & verts) mutable { - const auto & [a, b, c] = verts; - doBoundaryPart(a, b, *triangle); + const auto & [a, _, c] = verts; doBoundaryPart(a, c, *triangle); triangle++; }; std::ranges::for_each(newVerts | std::views::adjacent<3>, doBoundary); + doBoundaryPart(*++newVerts.begin(), newVerts.front(), *strip.rbegin()); doBoundaryPart(*++newVerts.rbegin(), newVerts.back(), *strip.rbegin()); std::set done; -- cgit v1.2.3 From a007ffeed3cfa6af2cbe1053c330ad11927d58de Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Wed, 18 Dec 2024 17:24:02 +0000 Subject: Add sanity checking logic to GeoData --- game/geoData.cpp | 10 ++++++++++ game/geoData.h | 2 ++ lib/triangle.h | 8 ++++++++ test/test-geoData.cpp | 10 +++------- 4 files changed, 23 insertions(+), 7 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index 8e662b3..eef5dc7 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -601,3 +601,13 @@ GeoData::setHeights(const std::span triangleStrip, const updateAllVertexNormals(newOrChangedVerts); } + +void +GeoData::sanityCheck() const +{ + if (!std::ranges::all_of(faces(), [this](const auto face) { + return triangle<2>(face).isUp(); + })) { + throw std::logic_error("Upside down faces detected"); + } +} diff --git a/game/geoData.h b/game/geoData.h index 79924d3..01582a6 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -98,6 +98,8 @@ public: return property(surface, h); } + void sanityCheck() const; + protected: template [[nodiscard]] Triangle diff --git a/lib/triangle.h b/lib/triangle.h index 888481d..d5547ab 100644 --- a/lib/triangle.h +++ b/lib/triangle.h @@ -83,6 +83,14 @@ struct Triangle : public glm::vec<3, glm::vec> { return 0.F; } + [[nodiscard]] constexpr auto + isUp() const + { + const auto edgeAB = sideDifference(1); + const auto edgeAC = sideDifference(2); + return edgeAB.x * edgeAC.y >= edgeAB.y * edgeAC.x; + } + [[nodiscard]] constexpr auto p(const glm::length_t idx) const { diff --git a/test/test-geoData.cpp b/test/test-geoData.cpp index 5998789..9ec4656 100644 --- a/test/test-geoData.cpp +++ b/test/test-geoData.cpp @@ -29,11 +29,9 @@ BOOST_AUTO_TEST_CASE(loadSuccess) BOOST_CHECK_EQUAL(upper, GlobalPosition3D(319950000, 499950000, 571600)); } -BOOST_AUTO_TEST_CASE(normalsAllPointUp) +BOOST_AUTO_TEST_CASE(sanityCheck) { - BOOST_CHECK(std::ranges::all_of(vertices(), [this](auto && vertex) { - return normal(vertex).z > 0; - })); + BOOST_CHECK_NO_THROW(sanityCheck()); } BOOST_AUTO_TEST_CASE(trianglesContainsPoints) @@ -214,9 +212,7 @@ BOOST_DATA_TEST_CASE(deform, loadFixtureJson("geoData/deform/ surface.colorBias = RGB {0, 0, 1}; auto gd = std::make_shared(GeoData::createFlat({0, 0}, {1000000, 1000000}, 100)); BOOST_CHECK_NO_THROW(gd->setHeights(points, {.surface = surface})); - BOOST_CHECK(std::ranges::all_of(gd->vertices(), [&gd](auto && vertex) { - return gd->normal(vertex).z > 0; - })); + BOOST_CHECK_NO_THROW(gd->sanityCheck()); ApplicationBase ab; TestMainWindow tmw; -- cgit v1.2.3 From c99b75bc628469c860970ffdc8268a438740190e Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 21 Dec 2024 13:38:51 +0000 Subject: Set height when reusing vertices during setHeights --- game/geoData.cpp | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index eef5dc7..d15a51b 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -451,6 +451,7 @@ GeoData::setHeights(const std::span triangleStrip, const std::views::iota(fv_begin(face), fv_end(face)) | std::views::transform(vertexDistFrom(tsPoint)), {}, &std::pair::second); nearest.second < opts.nearNodeTolerance) { + point(nearest.first).z = tsPoint.z; return nearest.first; } // Check edges @@ -512,16 +513,16 @@ GeoData::setHeights(const std::span triangleStrip, const if (linesCross(startPoint, endPoint, nextPoints.front().second, nextPoints.back().second)) { if (const auto intersection = linesIntersectAt(startPoint.xy(), endPoint.xy(), nextPoints.front().second.xy(), nextPoints.back().second.xy())) { - const auto newPosition = positionOnTriangle(*intersection, triangle); if (const auto nextDist = std::ranges::min(nexts | std::views::transform(vertexDistFrom(*intersection)), {}, &std::pair::second); nextDist.second < opts.nearNodeTolerance) { + point(nextDist.first).z = positionOnTriangle(point(nextDist.first), triangle).z; start = nextDist.first; return true; } else { - start = split(edge_handle(next), newPosition); + start = split(edge_handle(next), positionOnTriangle(*intersection, triangle)); } addVertexForNormalUpdate(start); boundaryTriangles.emplace(start, &triangle); -- cgit v1.2.3 From 20308e0a8d62e575237310b7de919e9c7410a9d7 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 22 Dec 2024 12:41:37 +0000 Subject: Store a generation number for GeoData --- game/geoData.cpp | 9 +++++++++ game/geoData.h | 2 ++ 2 files changed, 11 insertions(+) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index d15a51b..5771a2f 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -66,6 +66,7 @@ GeoData::loadFromAsciiGrid(const std::filesystem::path & input) }); } } + mesh.generation++; mesh.updateAllVertexNormals(); return mesh; @@ -106,6 +107,7 @@ GeoData::createFlat(GlobalPosition2D lower, GlobalPosition2D upper, GlobalDistan } mesh.updateAllVertexNormals(); + mesh.generation++; return mesh; } @@ -601,6 +603,13 @@ GeoData::setHeights(const std::span triangleStrip, const surfaceStripWalk(surfaceStripWalk, findPoint(strip.front().centroid())); updateAllVertexNormals(newOrChangedVerts); + generation++; +} + +size_t +GeoData::getGeneration() const +{ + return generation; } void diff --git a/game/geoData.h b/game/geoData.h index 01582a6..8eda99a 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -84,6 +84,7 @@ public: }; void setHeights(std::span triangleStrip, const SetHeightsOpts &); + [[nodiscard]] size_t getGeneration() const; [[nodiscard]] auto getExtents() const @@ -128,4 +129,5 @@ protected: private: GlobalPosition3D lowerExtent {}, upperExtent {}; + size_t generation {}; }; -- cgit v1.2.3 From 7a0121a612e901585fef39c1b599d53a21cb0afe Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 22 Dec 2024 12:58:57 +0000 Subject: SetHeightOptions surface changed to defaulted pointer --- game/geoData.cpp | 2 +- game/geoData.h | 2 +- test/test-geoData.cpp | 4 ++-- 3 files changed, 4 insertions(+), 4 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index 5771a2f..d8caff7 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -591,7 +591,7 @@ GeoData::setHeights(const std::span triangleStrip, const auto surfaceStripWalk = [this, &getTriangle, &opts](const auto & surfaceStripWalk, const auto & face) -> void { if (!property(surface, face)) { - property(surface, face) = &opts.surface; + property(surface, face) = opts.surface; std::ranges::for_each( ff_range(face), [this, &getTriangle, &surfaceStripWalk](const auto & adjacentFaceHandle) { if (getTriangle(this->triangle<2>(adjacentFaceHandle).centroid())) { diff --git a/game/geoData.h b/game/geoData.h index 8eda99a..92b9b75 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -78,7 +78,7 @@ public: static constexpr auto DEFAULT_NEAR_NODE_TOLERANACE = 500.F; static constexpr auto DEFAULT_MAX_SLOPE = 0.5F; - const Surface & surface; + const Surface * surface = nullptr; RelativeDistance nearNodeTolerance = DEFAULT_NEAR_NODE_TOLERANACE; RelativeDistance maxSlope = DEFAULT_MAX_SLOPE; }; diff --git a/test/test-geoData.cpp b/test/test-geoData.cpp index 9ec4656..589f675 100644 --- a/test/test-geoData.cpp +++ b/test/test-geoData.cpp @@ -211,7 +211,7 @@ BOOST_DATA_TEST_CASE(deform, loadFixtureJson("geoData/deform/ Surface surface; surface.colorBias = RGB {0, 0, 1}; auto gd = std::make_shared(GeoData::createFlat({0, 0}, {1000000, 1000000}, 100)); - BOOST_CHECK_NO_THROW(gd->setHeights(points, {.surface = surface})); + BOOST_CHECK_NO_THROW(gd->setHeights(points, {.surface = &surface})); BOOST_CHECK_NO_THROW(gd->sanityCheck()); ApplicationBase ab; @@ -265,6 +265,6 @@ BOOST_DATA_TEST_CASE( auto gd = std::make_shared(GeoData::createFlat({0, 0}, {1000000, 1000000}, 100)); for (const auto & strip : points) { BOOST_REQUIRE_GE(strip.size(), 3); - BOOST_CHECK_NO_THROW(gd->setHeights(strip, {.surface = surface, .nearNodeTolerance = 50})); + BOOST_CHECK_NO_THROW(gd->setHeights(strip, {.surface = &surface, .nearNodeTolerance = 50})); } } -- cgit v1.2.3 From d65bec3667e0344d71223c581ce09e8573191294 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Mon, 23 Dec 2024 13:26:18 +0000 Subject: Use correct triangle when creating surface boundary ends --- game/geoData.cpp | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index d8caff7..9516a95 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -545,8 +545,8 @@ GeoData::setHeights(const std::span triangleStrip, const triangle++; }; std::ranges::for_each(newVerts | std::views::adjacent<3>, doBoundary); - doBoundaryPart(*++newVerts.begin(), newVerts.front(), *strip.rbegin()); - doBoundaryPart(*++newVerts.rbegin(), newVerts.back(), *strip.rbegin()); + doBoundaryPart(*++newVerts.begin(), newVerts.front(), strip.front()); + doBoundaryPart(*++newVerts.rbegin(), newVerts.back(), strip.back()); std::set done; std::set todo; -- cgit v1.2.3 From 9310329401d47de713f19aa3dcc5f6f12f22ea59 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Mon, 23 Dec 2024 13:42:39 +0000 Subject: Copy properties when split faces and edges --- game/geoData.cpp | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index 9516a95..d01b4d5 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -468,10 +468,10 @@ GeoData::setHeights(const std::span triangleStrip, const if (!inter) { throw std::runtime_error("Perpendicular lines do not cross"); } - return split(edge_handle(nearest.first), *inter || tsPoint.z); + return split_copy(edge_handle(nearest.first), *inter || tsPoint.z); } // Nothing close, split face - return split(face, tsPoint); + return split_copy(face, tsPoint); }; // New vertices for each vertex in triangleStrip @@ -524,7 +524,7 @@ GeoData::setHeights(const std::span triangleStrip, const return true; } else { - start = split(edge_handle(next), positionOnTriangle(*intersection, triangle)); + start = split_copy(edge_handle(next), positionOnTriangle(*intersection, triangle)); } addVertexForNormalUpdate(start); boundaryTriangles.emplace(start, &triangle); -- cgit v1.2.3 From b410b2e37b91d9bb39eeb98af45d603b74281be2 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Mon, 23 Dec 2024 13:55:29 +0000 Subject: Set surface from all triangles, not just the first First may already have a surface in the case of a join --- game/geoData.cpp | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index d01b4d5..fb3cb15 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -600,7 +600,9 @@ GeoData::setHeights(const std::span triangleStrip, const }); } }; - surfaceStripWalk(surfaceStripWalk, findPoint(strip.front().centroid())); + for (const auto & triangle : strip) { + surfaceStripWalk(surfaceStripWalk, findPoint(triangle.centroid())); + } updateAllVertexNormals(newOrChangedVerts); generation++; -- cgit v1.2.3 From 89068c56f3236b65e392cdc8794c5bc1977e5556 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Mon, 30 Dec 2024 17:18:26 +0000 Subject: Pass lots more information during GeoData::walk --- game/geoData.cpp | 45 ++++++++++++++++++++++++--------------------- game/geoData.h | 22 ++++++++++++++++------ test/test-geoData.cpp | 11 +++++++---- 3 files changed, 47 insertions(+), 31 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index fb3cb15..ce88e5b 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -236,12 +236,12 @@ GeoData::intersectRay(const Ray & ray, FaceHandle face) const GeoData::IntersectionResult out; walkUntil(PointFace {ray.start, face}, ray.start.xy() + (ray.direction.xy() * RelativePosition2D(upperExtent.xy() - lowerExtent.xy())), - [&out, &ray, this](FaceHandle face) { + [&out, &ray, this](const auto & step) { BaryPosition bari {}; RelativeDistance dist {}; - const auto t = triangle<3>(face); + const auto t = triangle<3>(step.current); if (ray.intersectTriangle(t.x, t.y, t.z, bari, dist)) { - out.emplace(t * bari, face); + out.emplace(t * bari, step.current); return true; } return false; @@ -250,7 +250,7 @@ GeoData::intersectRay(const Ray & ray, FaceHandle face) const } void -GeoData::walk(const PointFace & from, const GlobalPosition2D to, const std::function & op) const +GeoData::walk(const PointFace & from, const GlobalPosition2D to, Consumer op) const { walkUntil(from, to, [&op](const auto & fh) { op(fh); @@ -259,41 +259,44 @@ GeoData::walk(const PointFace & from, const GlobalPosition2D to, const std::func } void -GeoData::walkUntil(const PointFace & from, const GlobalPosition2D to, const std::function & op) const +GeoData::walkUntil(const PointFace & from, const GlobalPosition2D to, Tester op) const { - auto f = from.face(this); - if (!f.is_valid()) { + WalkStep step { + .current = from.face(this), + }; + if (!step.current.is_valid()) { const auto entryEdge = findEntry(from.point, to); if (!entryEdge.is_valid()) { return; } - f = opposite_face_handle(entryEdge); + step.current = opposite_face_handle(entryEdge); } - 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))); + while (step.current.is_valid() && !op(step)) { + step.previous = step.current; + for (const auto next : fh_range(step.current)) { + step.current = opposite_face_handle(next); + if (step.current.is_valid() && step.current != step.previous) { + const auto e1 = point(to_vertex_handle(next)); + const auto e2 = point(to_vertex_handle(opposite_halfedge_handle(next))); if (linesCrossLtR(from.point, to, e1, e2)) { - previousFace = f; + step.exitHalfedge = next; + step.exitPosition = linesIntersectAt(from.point.xy(), to.xy(), e1.xy(), e2.xy()).value(); break; } } - f.reset(); + step.current.reset(); } } } void -GeoData::boundaryWalk(const std::function & op) const +GeoData::boundaryWalk(Consumer op) const { boundaryWalk(op, findBoundaryStart()); } void -GeoData::boundaryWalk(const std::function & op, HalfedgeHandle start) const +GeoData::boundaryWalk(Consumer op, HalfedgeHandle start) const { assert(is_boundary(start)); boundaryWalkUntil( @@ -305,13 +308,13 @@ GeoData::boundaryWalk(const std::function & op, HalfedgeHa } void -GeoData::boundaryWalkUntil(const std::function & op) const +GeoData::boundaryWalkUntil(Tester op) const { boundaryWalkUntil(op, findBoundaryStart()); } void -GeoData::boundaryWalkUntil(const std::function & op, HalfedgeHandle start) const +GeoData::boundaryWalkUntil(Tester op, HalfedgeHandle start) const { assert(is_boundary(start)); if (!op(start)) { diff --git a/game/geoData.h b/game/geoData.h index b3ef22a..68ce9a2 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -64,13 +64,23 @@ public: [[nodiscard]] IntersectionResult intersectRay(const Ray &) const; [[nodiscard]] IntersectionResult intersectRay(const Ray &, FaceHandle start) const; - void walk(const PointFace & from, const GlobalPosition2D to, const std::function & op) const; - void walkUntil(const PointFace & from, const GlobalPosition2D to, const std::function & op) const; + struct WalkStep { + FaceHandle current; + FaceHandle previous {}; + HalfedgeHandle exitHalfedge {}; + GlobalPosition2D exitPosition {}; + }; + + template using Consumer = const std::function &; + template using Tester = const std::function &; + + void walk(const PointFace & from, const GlobalPosition2D to, Consumer op) const; + void walkUntil(const PointFace & from, const GlobalPosition2D to, Tester 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; + void boundaryWalk(Consumer) const; + void boundaryWalk(Consumer, HalfedgeHandle start) const; + void boundaryWalkUntil(Tester) const; + void boundaryWalkUntil(Tester, HalfedgeHandle start) const; [[nodiscard]] HalfedgeHandle findEntry(const GlobalPosition2D from, const GlobalPosition2D to) const; diff --git a/test/test-geoData.cpp b/test/test-geoData.cpp index 589f675..dd68375 100644 --- a/test/test-geoData.cpp +++ b/test/test-geoData.cpp @@ -148,8 +148,11 @@ BOOST_DATA_TEST_CASE(walkTerrain, from, to, visits) { std::vector visited; - BOOST_CHECK_NO_THROW(fixedTerrtain.walk(from, to, [&visited](auto fh) { - visited.emplace_back(fh.idx()); + BOOST_CHECK_NO_THROW(fixedTerrtain.walk(from, to, [&visited](auto step) { + if (!visited.empty()) { + BOOST_CHECK_EQUAL(step.previous.idx(), visited.back()); + } + visited.emplace_back(step.current.idx()); })); BOOST_CHECK_EQUAL_COLLECTIONS(visited.begin(), visited.end(), visits.begin(), visits.end()); } @@ -181,8 +184,8 @@ BOOST_DATA_TEST_CASE(walkTerrainUntil, from, to, visits) { std::vector visited; - BOOST_CHECK_NO_THROW(fixedTerrtain.walkUntil(from, to, [&visited](auto fh) { - visited.emplace_back(fh.idx()); + BOOST_CHECK_NO_THROW(fixedTerrtain.walkUntil(from, to, [&visited](const auto & step) { + visited.emplace_back(step.current.idx()); return visited.size() >= 5; })); BOOST_CHECK_EQUAL_COLLECTIONS(visited.begin(), visited.end(), visits.begin(), visits.end()); -- cgit v1.2.3 From ca3736b3a896557536c0aa4c0cee1f156e118b54 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Wed, 1 Jan 2025 12:53:43 +0000 Subject: Walk terrain along a curve - edge cases exist --- game/geoData.cpp | 44 ++++++++++++++++++++++++++++++++++++++++++++ game/geoData.h | 6 ++++-- test/test-geoData.cpp | 40 ++++++++++++++++++++++++++++++++++++++++ 3 files changed, 88 insertions(+), 2 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index ce88e5b..37abc4c 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -289,6 +289,50 @@ GeoData::walkUntil(const PointFace & from, const GlobalPosition2D to, Tester op) const +{ + walkUntil(from, to, centre, [&op](const auto & fh) { + op(fh); + return false; + }); +} + +void +GeoData::walkUntil(const PointFace & from, GlobalPosition2D to, GlobalPosition2D centre, Tester op) const +{ + WalkStep step { + .current = from.face(this), + }; + if (!step.current.is_valid()) { + const auto entryEdge = findEntry(from.point, to); + if (!entryEdge.is_valid()) { + return; + } + step.current = opposite_face_handle(entryEdge); + } + ArcSegment arc {centre, from.point, to}; + while (step.current.is_valid() && !op(step)) { + step.previous = step.current; + for (const auto next : fh_range(step.current)) { + if (opposite_halfedge_handle(next) == step.exitHalfedge) { + continue; + } + step.current = opposite_face_handle(next); + if (step.current.is_valid()) { + const auto e1 = point(to_vertex_handle(next)); + const auto e2 = point(to_vertex_handle(opposite_halfedge_handle(next))); + if (const auto intersect = arc.crossesLineAt(e1, e2)) { + step.exitHalfedge = next; + step.exitPosition = intersect.value(); + break; + } + } + step.current.reset(); + } + } +} + void GeoData::boundaryWalk(Consumer op) const { diff --git a/game/geoData.h b/game/geoData.h index 68ce9a2..e3fc313 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -74,8 +74,10 @@ public: template using Consumer = const std::function &; template using Tester = const std::function &; - void walk(const PointFace & from, const GlobalPosition2D to, Consumer op) const; - void walkUntil(const PointFace & from, const GlobalPosition2D to, Tester op) const; + void walk(const PointFace & from, GlobalPosition2D to, Consumer op) const; + void walkUntil(const PointFace & from, GlobalPosition2D to, Tester op) const; + void walk(const PointFace & from, GlobalPosition2D to, GlobalPosition2D centre, Consumer op) const; + void walkUntil(const PointFace & from, GlobalPosition2D to, GlobalPosition2D centre, Tester op) const; void boundaryWalk(Consumer) const; void boundaryWalk(Consumer, HalfedgeHandle start) const; diff --git a/test/test-geoData.cpp b/test/test-geoData.cpp index dd68375..049d896 100644 --- a/test/test-geoData.cpp +++ b/test/test-geoData.cpp @@ -191,6 +191,46 @@ BOOST_DATA_TEST_CASE(walkTerrainUntil, BOOST_CHECK_EQUAL_COLLECTIONS(visited.begin(), visited.end(), visits.begin(), visits.end()); } +using WalkTerrainCurveData = std::tuple, + std::vector>; + +BOOST_TEST_DECORATOR(*boost::unit_test::timeout(1)) + +BOOST_DATA_TEST_CASE(walkTerrainCurveSetsFromFace, + boost::unit_test::data::make({ + {{310002000, 490003000}, {310002000, 490003000}, {310002000, 490003000}, {0}, {}}, + {{310003000, 490002000}, {310003000, 490002000}, {310003000, 490002000}, {1}, {}}, + {{310202000, 490203000}, {310002000, 490003000}, {310002000, 490203000}, + {1600, 1601, 1202, 1201, 802, 803, 404, 403, 4, 3, 2, 1, 0}, + { + {310201997, 490201997}, + {310201977, 490200000}, + {310200000, 490174787}, + {310194850, 490150000}, + {310192690, 490142690}, + {310173438, 490100000}, + {310150000, 490068479}, + {310130806, 490050000}, + {310100000, 490028656}, + {310062310, 490012310}, + {310050000, 490008845}, + {310003003, 490003003}, + }}, + }), + from, to, centre, visits, exits) +{ + BOOST_REQUIRE_EQUAL(visits.size(), exits.size() + 1); + + std::vector visited; + std::vector exited; + BOOST_CHECK_NO_THROW(fixedTerrtain.walk(from, to, centre, [&](const auto & step) { + visited.emplace_back(step.current.idx()); + exited.emplace_back(step.exitPosition); + })); + BOOST_CHECK_EQUAL_COLLECTIONS(visited.begin(), visited.end(), visits.begin(), visits.end()); + BOOST_CHECK_EQUAL_COLLECTIONS(exited.begin() + 1, exited.end(), exits.begin(), exits.end()); +} + using FindEntiesData = std::tuple; BOOST_DATA_TEST_CASE(findEntries, -- cgit v1.2.3 From c0d05b1ad0f2d82f9ce94437370648e7dfdd994e Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Wed, 1 Jan 2025 16:00:35 +0000 Subject: Return angle of intersection of arc with line --- game/geoData.cpp | 2 +- lib/maths.h | 30 +++++++++++++++--------------- test/test-maths.cpp | 32 +++++++++++++++++++------------- 3 files changed, 35 insertions(+), 29 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index 37abc4c..45e6590 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -324,7 +324,7 @@ GeoData::walkUntil(const PointFace & from, GlobalPosition2D to, GlobalPosition2D const auto e2 = point(to_vertex_handle(opposite_halfedge_handle(next))); if (const auto intersect = arc.crossesLineAt(e1, e2)) { step.exitHalfedge = next; - step.exitPosition = intersect.value(); + step.exitPosition = intersect.value().first; break; } } diff --git a/lib/maths.h b/lib/maths.h index f43321a..671313d 100644 --- a/lib/maths.h +++ b/lib/maths.h @@ -48,7 +48,7 @@ template struct ArcSegment : publi PointType ep1; RelativeDistance radius; - [[nodiscard]] constexpr std::optional> crossesLineAt( + [[nodiscard]] constexpr std::optional, Angle>> crossesLineAt( const glm::vec<2, T, Q> & lineStart, const glm::vec<2, T, Q> & lineEnd) const; [[nodiscard]] constexpr bool @@ -502,7 +502,7 @@ constexpr ArcSegment::ArcSegment(PointType centre, PointType ep0, PointTyp } template -[[nodiscard]] constexpr std::optional> +[[nodiscard]] constexpr std::optional, Angle>> ArcSegment::crossesLineAt(const glm::vec<2, T, Q> & lineStart, const glm::vec<2, T, Q> & lineEnd) const { // Based on formulas from https://mathworld.wolfram.com/Circle-LineIntersection.html @@ -519,23 +519,23 @@ ArcSegment::crossesLineAt(const glm::vec<2, T, Q> & lineStart, const glm:: const auto rootDiscriminant = std::sqrt(discriminant); const auto drdr = lineLen * lineLen; const RelativeDistance sgn = (lineDiff.y < 0 ? -1 : 1); - std::array points { - RelativePosition2D {((determinant * lineDiff.y) + sgn * lineDiff.x * rootDiscriminant), - ((-determinant * lineDiff.x) + std::abs(lineDiff.y) * rootDiscriminant)} - / drdr, - RelativePosition2D {((determinant * lineDiff.y) - sgn * lineDiff.x * rootDiscriminant), - ((-determinant * lineDiff.x) - std::abs(lineDiff.y) * rootDiscriminant)} - / drdr, - }; + std::array, 2> points; + std::ranges::transform(std::initializer_list {1, -1}, points.begin(), [&](RelativeDistance N) { + const auto point = RelativePosition2D {((determinant * lineDiff.y) + sgn * lineDiff.x * rootDiscriminant * N), + ((-determinant * lineDiff.x) + std::abs(lineDiff.y) * rootDiscriminant * N)} + / drdr; + return std::make_pair(point, vector_yaw(point)); + }); const auto end = std::remove_if(points.begin(), points.end(), [this, lineRelStart, lineDiff, drdr](const auto point) { - const auto dot = glm::dot(lineDiff, point - lineRelStart); - return !angleWithinArc(vector_yaw(point)) || dot < 0 || dot > drdr; - }); + const auto dot = glm::dot(lineDiff, point.first - lineRelStart); + return !angleWithinArc(point.second) || dot < 0 || dot > drdr; + }); if (points.begin() == end) { return std::nullopt; } - return centre + *std::ranges::min_element(points.begin(), end, {}, [lineRelStart](const auto point) { - return glm::distance(lineRelStart, point); + const auto first = *std::ranges::min_element(points.begin(), end, {}, [lineRelStart](const auto point) { + return glm::distance(lineRelStart, point.first); }); + return std::make_pair(centre + first.first, first.second); } diff --git a/test/test-maths.cpp b/test/test-maths.cpp index aa2b9c8..5906757 100644 --- a/test/test-maths.cpp +++ b/test/test-maths.cpp @@ -376,33 +376,39 @@ BOOST_AUTO_TEST_CASE(triangle3d_helpers) BOOST_CHECK_CLOSE(t.area(), 12.5F, 0.01F); } +using ArcLineIntersectExp = std::pair; using ArcLineIntersectData = std::tuple>; + GlobalPosition2D, std::optional>; BOOST_DATA_TEST_CASE(arcline_intersection, boost::unit_test::data::make({ {{0, 0}, {0, 100}, {100, 0}, {200, 0}, {0, 200}, std::nullopt}, {{0, 0}, {0, 100}, {100, 0}, {0, 0}, {10, 10}, std::nullopt}, - {{0, 0}, {0, 100}, {100, 0}, {0, 0}, {100, 100}, GlobalPosition2D {71, 71}}, - {{15, 27}, {15, 127}, {115, 27}, {15, 27}, {115, 127}, GlobalPosition2D {86, 98}}, + {{0, 0}, {0, 100}, {100, 0}, {0, 0}, {100, 100}, ArcLineIntersectExp {{71, 71}, quarter_pi}}, + {{15, 27}, {15, 127}, {115, 27}, {15, 27}, {115, 127}, ArcLineIntersectExp {{86, 98}, quarter_pi}}, {{0, 0}, {0, 100}, {100, 0}, {0, 0}, {-100, -100}, std::nullopt}, - {{0, 0}, {0, 100}, {100, 0}, {-10, 125}, {125, -10}, GlobalPosition2D {16, 99}}, - {{0, 0}, {0, 100}, {100, 0}, {125, -10}, {-10, 125}, GlobalPosition2D {99, 16}}, - {{0, 0}, {0, 100}, {100, 0}, {10, 125}, {125, -10}, GlobalPosition2D {38, 93}}, - {{0, 0}, {0, 100}, {100, 0}, {12, 80}, {125, -10}, GlobalPosition2D {99, 10}}, - {{0, 0}, {0, 100}, {100, 0}, {40, 80}, {125, -10}, GlobalPosition2D {98, 18}}, + {{0, 0}, {0, 100}, {100, 0}, {-10, 125}, {125, -10}, ArcLineIntersectExp {{16, 99}, 0.164F}}, + {{0, 0}, {0, 100}, {100, 0}, {125, -10}, {-10, 125}, ArcLineIntersectExp {{99, 16}, 1.407F}}, + {{0, 0}, {0, 100}, {100, 0}, {10, 125}, {125, -10}, ArcLineIntersectExp {{38, 93}, 0.385F}}, + {{0, 0}, {0, 100}, {100, 0}, {12, 80}, {125, -10}, ArcLineIntersectExp {{99, 10}, 1.467F}}, + {{0, 0}, {0, 100}, {100, 0}, {40, 80}, {125, -10}, ArcLineIntersectExp {{98, 18}, 1.387F}}, {{0, 0}, {0, 100}, {100, 0}, {40, 80}, {80, 20}, std::nullopt}, - {{0, 0}, {0, 100}, {100, 0}, {40, 80}, {80, 80}, GlobalPosition2D {60, 80}}, - {{0, 0}, {0, 100}, {100, 0}, {80, 40}, {80, 80}, GlobalPosition2D {80, 60}}, + {{0, 0}, {0, 100}, {100, 0}, {40, 80}, {80, 80}, ArcLineIntersectExp {{60, 80}, 0.6435F}}, + {{0, 0}, {0, 100}, {100, 0}, {80, 40}, {80, 80}, ArcLineIntersectExp {{80, 60}, 0.9273F}}, {{310002000, 490203000}, {310202000, 490203000}, {310002000, 490003000}, {310200000, 490150000}, - {310150000, 490150000}, GlobalPosition2D {310194850, 490150000}}, + {310150000, 490150000}, ArcLineIntersectExp {{310194850, 490150000}, 1.839F}}, }), - centre, arcStart, arcEnd, lineStart, lineEnd, intersection) + centre, arcStart, arcEnd, lineStart, lineEnd, expected) { const ArcSegment arc {centre, arcStart, arcEnd}; BOOST_TEST_INFO(arc.first); BOOST_TEST_INFO(arc.second); BOOST_TEST_INFO(arc.length()); - BOOST_CHECK_EQUAL(arc.crossesLineAt(lineStart, lineEnd), intersection); + const auto intersection = arc.crossesLineAt(lineStart, lineEnd); + BOOST_REQUIRE_EQUAL(expected.has_value(), intersection.has_value()); + if (expected.has_value()) { + BOOST_CHECK_EQUAL(expected->first, intersection->first); + BOOST_CHECK_CLOSE(expected->second, intersection->second, 1.F); + } } -- cgit v1.2.3 From 02c37c477099f69d1468a51ab66d05f3e7bf35fd Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Thu, 2 Jan 2025 17:29:09 +0000 Subject: Fix curve walk edge case where the curve legitimately returns to the previous face --- game/geoData.cpp | 6 ++---- test/test-geoData.cpp | 6 ++++++ 2 files changed, 8 insertions(+), 4 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index 45e6590..f0e38d0 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -315,16 +315,14 @@ GeoData::walkUntil(const PointFace & from, GlobalPosition2D to, GlobalPosition2D while (step.current.is_valid() && !op(step)) { step.previous = step.current; for (const auto next : fh_range(step.current)) { - if (opposite_halfedge_handle(next) == step.exitHalfedge) { - continue; - } step.current = opposite_face_handle(next); if (step.current.is_valid()) { const auto e1 = point(to_vertex_handle(next)); const auto e2 = point(to_vertex_handle(opposite_halfedge_handle(next))); if (const auto intersect = arc.crossesLineAt(e1, e2)) { step.exitHalfedge = next; - step.exitPosition = intersect.value().first; + arc.ep0 = step.exitPosition = intersect.value().first; + arc.first = std::nextafter(intersect.value().second, INFINITY); break; } } diff --git a/test/test-geoData.cpp b/test/test-geoData.cpp index 049d896..8e5ef2d 100644 --- a/test/test-geoData.cpp +++ b/test/test-geoData.cpp @@ -216,6 +216,11 @@ BOOST_DATA_TEST_CASE(walkTerrainCurveSetsFromFace, {310050000, 490008845}, {310003003, 490003003}, }}, + {{310999999, 490205000}, {310999999, 490203000}, {310999000, 490204000}, {1631, 1632, 1631}, + { + {311000000, 490204999}, + {311000000, 490203001}, + }}, }), from, to, centre, visits, exits) { @@ -225,6 +230,7 @@ BOOST_DATA_TEST_CASE(walkTerrainCurveSetsFromFace, std::vector exited; BOOST_CHECK_NO_THROW(fixedTerrtain.walk(from, to, centre, [&](const auto & step) { visited.emplace_back(step.current.idx()); + BOOST_REQUIRE(!std::ranges::contains(exited, step.exitPosition)); exited.emplace_back(step.exitPosition); })); BOOST_CHECK_EQUAL_COLLECTIONS(visited.begin(), visited.end(), visits.begin(), visits.end()); -- cgit v1.2.3 From 917c081ddc1651381f83d8a9b0e095440419814a Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 5 Jan 2025 01:09:01 +0000 Subject: Helper to declare and add OpenMesh property declaratively --- assetFactory/modelFactoryMesh.cpp | 8 -------- assetFactory/modelFactoryMesh.h | 11 +++++------ game/geoData.cpp | 5 ----- game/geoData.h | 5 ++--- thirdparty/openmesh/helpers.h | 11 +++++++++++ 5 files changed, 18 insertions(+), 22 deletions(-) create mode 100644 thirdparty/openmesh/helpers.h (limited to 'game/geoData.cpp') diff --git a/assetFactory/modelFactoryMesh.cpp b/assetFactory/modelFactoryMesh.cpp index 3d4b5f3..3660fb7 100644 --- a/assetFactory/modelFactoryMesh.cpp +++ b/assetFactory/modelFactoryMesh.cpp @@ -1,13 +1,5 @@ #include "modelFactoryMesh.h" -ModelFactoryMesh::ModelFactoryMesh() -{ - add_property(smoothFaceProperty); - add_property(materialFaceProperty); - add_property(nameFaceProperty); - add_property(nameAdjFaceProperty); -} - void ModelFactoryMesh::configNamedFace(const std::string & name, OpenMesh::FaceHandle handle) { diff --git a/assetFactory/modelFactoryMesh.h b/assetFactory/modelFactoryMesh.h index 299986e..6a18155 100644 --- a/assetFactory/modelFactoryMesh.h +++ b/assetFactory/modelFactoryMesh.h @@ -8,6 +8,7 @@ #include #include #include +#include struct ModelFactoryTraits : public OpenMesh::DefaultTraits { FaceAttributes(OpenMesh::Attributes::Normal | OpenMesh::Attributes::Status | OpenMesh::Attributes::Color); @@ -21,13 +22,11 @@ struct ModelFactoryTraits : public OpenMesh::DefaultTraits { }; struct ModelFactoryMesh : public OpenMesh::PolyMesh_ArrayKernelT { - ModelFactoryMesh(); - bool normalsProvidedProperty {}; - OpenMesh::FPropHandleT smoothFaceProperty; - OpenMesh::FPropHandleT materialFaceProperty; - OpenMesh::FPropHandleT nameFaceProperty; - OpenMesh::HPropHandleT nameAdjFaceProperty; + const OpenMesh::Helpers::Property smoothFaceProperty {this}; + const OpenMesh::Helpers::Property materialFaceProperty {this}; + const OpenMesh::Helpers::Property nameFaceProperty {this}; + const OpenMesh::Helpers::Property nameAdjFaceProperty {this}; template std::pair diff --git a/game/geoData.cpp b/game/geoData.cpp index f0e38d0..950fb73 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -7,11 +7,6 @@ #include #include -GeoData::GeoData() -{ - add_property(surface); -} - GeoData GeoData::loadFromAsciiGrid(const std::filesystem::path & input) { diff --git a/game/geoData.h b/game/geoData.h index e3fc313..11ba568 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -10,6 +10,7 @@ #include #include #include +#include struct GeoDataTraits : public OpenMesh::DefaultTraits { FaceAttributes(OpenMesh::Attributes::Status); @@ -22,9 +23,7 @@ struct GeoDataTraits : public OpenMesh::DefaultTraits { class GeoData : public OpenMesh::TriMesh_ArrayKernelT { private: - GeoData(); - - OpenMesh::FPropHandleT surface; + const OpenMesh::Helpers::Property surface {this}; public: static GeoData loadFromAsciiGrid(const std::filesystem::path &); diff --git a/thirdparty/openmesh/helpers.h b/thirdparty/openmesh/helpers.h new file mode 100644 index 0000000..bed885c --- /dev/null +++ b/thirdparty/openmesh/helpers.h @@ -0,0 +1,11 @@ +#pragma once +#include + +namespace OpenMesh::Helpers { + template typename PropertyT> struct Property : public PropertyT { + template explicit Property(OpenMesh::BaseKernel * kernel, Params &&... params) + { + kernel->add_property(*this, std::forward(params)...); + } + }; +} -- cgit v1.2.3 From ee636e6c5da87e52e1d40e97ce95ed0765f9e819 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 5 Jan 2025 11:59:24 +0000 Subject: Return surface face list from setHeights --- game/geoData.cpp | 10 +++++++--- game/geoData.h | 2 +- 2 files changed, 8 insertions(+), 4 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index 950fb73..03bf85f 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -457,11 +457,11 @@ GeoData::triangleContainsTriangle(const Triangle<2> & a, const Triangle<2> & b) return triangleContainsPoint(a.x, b) && triangleContainsPoint(a.y, b) && triangleContainsPoint(a.z, b); } -void +std::vector GeoData::setHeights(const std::span triangleStrip, const SetHeightsOpts & opts) { if (triangleStrip.size() < 3) { - return; + return {}; } const auto stripMinMax = std::ranges::minmax(triangleStrip, {}, &GlobalPosition3D::z); lowerExtent.z = std::min(upperExtent.z, stripMinMax.min.z); @@ -629,9 +629,12 @@ GeoData::setHeights(const std::span triangleStrip, const done.insert(heh); } - auto surfaceStripWalk = [this, &getTriangle, &opts](const auto & surfaceStripWalk, const auto & face) -> void { + std::vector out; + auto surfaceStripWalk + = [this, &getTriangle, &opts, &out](const auto & surfaceStripWalk, const auto & face) -> void { if (!property(surface, face)) { property(surface, face) = opts.surface; + out.emplace_back(face); std::ranges::for_each( ff_range(face), [this, &getTriangle, &surfaceStripWalk](const auto & adjacentFaceHandle) { if (getTriangle(this->triangle<2>(adjacentFaceHandle).centroid())) { @@ -646,6 +649,7 @@ GeoData::setHeights(const std::span triangleStrip, const updateAllVertexNormals(newOrChangedVerts); generation++; + return out; } size_t diff --git a/game/geoData.h b/game/geoData.h index 11ba568..2bdc60d 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -94,7 +94,7 @@ public: RelativeDistance maxSlope = DEFAULT_MAX_SLOPE; }; - void setHeights(std::span triangleStrip, const SetHeightsOpts &); + std::vector setHeights(std::span triangleStrip, const SetHeightsOpts &); [[nodiscard]] size_t getGeneration() const; [[nodiscard]] auto -- cgit v1.2.3 From b5899aae753287805967ec5241bc0063f5c95a4d Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 5 Jan 2025 12:25:16 +0000 Subject: Include arc angle in curved terrain walk --- game/geoData.cpp | 11 +++++------ game/geoData.h | 9 +++++++-- 2 files changed, 12 insertions(+), 8 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index 03bf85f..1a4cd3b 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -285,7 +285,7 @@ GeoData::walkUntil(const PointFace & from, const GlobalPosition2D to, Tester op) const +GeoData::walk(const PointFace & from, GlobalPosition2D to, GlobalPosition2D centre, Consumer op) const { walkUntil(from, to, centre, [&op](const auto & fh) { op(fh); @@ -294,11 +294,9 @@ GeoData::walk(const PointFace & from, GlobalPosition2D to, GlobalPosition2D cent } void -GeoData::walkUntil(const PointFace & from, GlobalPosition2D to, GlobalPosition2D centre, Tester op) const +GeoData::walkUntil(const PointFace & from, GlobalPosition2D to, GlobalPosition2D centre, Tester op) const { - WalkStep step { - .current = from.face(this), - }; + WalkStepCurve step {WalkStep {.current = from.face(this)}}; if (!step.current.is_valid()) { const auto entryEdge = findEntry(from.point, to); if (!entryEdge.is_valid()) { @@ -307,6 +305,7 @@ GeoData::walkUntil(const PointFace & from, GlobalPosition2D to, GlobalPosition2D step.current = opposite_face_handle(entryEdge); } ArcSegment arc {centre, from.point, to}; + step.angle = arc.first; while (step.current.is_valid() && !op(step)) { step.previous = step.current; for (const auto next : fh_range(step.current)) { @@ -317,7 +316,7 @@ GeoData::walkUntil(const PointFace & from, GlobalPosition2D to, GlobalPosition2D if (const auto intersect = arc.crossesLineAt(e1, e2)) { step.exitHalfedge = next; arc.ep0 = step.exitPosition = intersect.value().first; - arc.first = std::nextafter(intersect.value().second, INFINITY); + arc.first = std::nextafter(step.angle = intersect.value().second, INFINITY); break; } } diff --git a/game/geoData.h b/game/geoData.h index 2bdc60d..7e4c28f 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -70,13 +70,18 @@ public: GlobalPosition2D exitPosition {}; }; + struct WalkStepCurve : public WalkStep { + Angle angle {}; + }; + template using Consumer = const std::function &; template using Tester = const std::function &; void walk(const PointFace & from, GlobalPosition2D to, Consumer op) const; void walkUntil(const PointFace & from, GlobalPosition2D to, Tester op) const; - void walk(const PointFace & from, GlobalPosition2D to, GlobalPosition2D centre, Consumer op) const; - void walkUntil(const PointFace & from, GlobalPosition2D to, GlobalPosition2D centre, Tester op) const; + void walk(const PointFace & from, GlobalPosition2D to, GlobalPosition2D centre, Consumer op) const; + void walkUntil( + const PointFace & from, GlobalPosition2D to, GlobalPosition2D centre, Tester op) const; void boundaryWalk(Consumer) const; void boundaryWalk(Consumer, HalfedgeHandle start) const; -- cgit v1.2.3 From 1aba027462a861f2c1155672792dbbe555d7dc0a Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Mon, 13 Jan 2025 01:45:43 +0000 Subject: Add distance helper Works with integer positions, first template param allows forcing to N dimensions --- game/geoData.cpp | 7 ++++--- game/geoData.h | 2 +- game/network/network.cpp | 4 ++-- game/network/network.impl.h | 4 ++-- game/network/rail.cpp | 6 +++--- lib/maths.h | 9 ++++++++- lib/ray.h | 3 +-- lib/triangle.h | 2 +- test/test-network.cpp | 6 +++--- 9 files changed, 25 insertions(+), 18 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index 1a4cd3b..448ff67 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -405,10 +405,11 @@ GeoData::difference(const HalfedgeHandle heh) const return ::difference(point(to_vertex_handle(heh)), point(from_vertex_handle(heh))); } +template [[nodiscard]] RelativeDistance GeoData::length(const HalfedgeHandle heh) const { - return glm::length(difference(heh)); + return ::distance(point(to_vertex_handle(heh)), point(from_vertex_handle(heh))); } [[nodiscard]] GlobalPosition3D @@ -468,7 +469,7 @@ GeoData::setHeights(const std::span triangleStrip, const const auto vertexDistFrom = [this](GlobalPosition2D p) { return [p, this](const VertexHandle v) { - return std::make_pair(v, glm::length(::difference(p, this->point(v).xy()))); + return std::make_pair(v, ::distance(p, this->point(v).xy())); }; }; const auto vertexDistFromE = [this](GlobalPosition2D p) { @@ -614,7 +615,7 @@ GeoData::setHeights(const std::span triangleStrip, const todoOutHalfEdges(toVertex); } else if (!toTriangle) { // point without the new strip, adjust vertically by limit - const auto maxOffset = static_cast(opts.maxSlope * glm::length(difference(heh).xy())); + const auto maxOffset = static_cast(opts.maxSlope * length<2>(heh)); const auto newHeight = std::clamp(toPoint.z, fromPoint.z - maxOffset, fromPoint.z + maxOffset); if (newHeight != toPoint.z) { toPoint.z = newHeight; diff --git a/game/geoData.h b/game/geoData.h index 7e4c28f..390a443 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -136,7 +136,7 @@ protected: [[nodiscard]] HalfedgeHandle findBoundaryStart() const; [[nodiscard]] RelativePosition3D difference(const HalfedgeHandle) const; - [[nodiscard]] RelativeDistance length(const HalfedgeHandle) const; + template [[nodiscard]] RelativeDistance length(const HalfedgeHandle) const; [[nodiscard]] GlobalPosition3D centre(const HalfedgeHandle) const; void updateAllVertexNormals(); diff --git a/game/network/network.cpp b/game/network/network.cpp index 1666c4d..e67942f 100644 --- a/game/network/network.cpp +++ b/game/network/network.cpp @@ -121,8 +121,8 @@ Network::genCurveDef(const GlobalPosition3D & start, const GlobalPosition3D & en endDir += pi; const auto flatStart {start.xy()}, flatEnd {end.xy()}; auto midheight = [&](auto mid) { - const auto sm = glm::length(RelativePosition2D(flatStart - mid)), - em = glm::length(RelativePosition2D(flatEnd - mid)); + const auto sm = ::distance<2>(flatStart, mid); + const auto em = ::distance<2>(flatEnd, mid); return start.z + GlobalDistance(RelativeDistance(end.z - start.z) * (sm / (sm + em))); }; if (const auto radii = find_arcs_radius(flatStart, startDir, flatEnd, endDir); radii.first < radii.second) { diff --git a/game/network/network.impl.h b/game/network/network.impl.h index ff29088..33b0a86 100644 --- a/game/network/network.impl.h +++ b/game/network/network.impl.h @@ -52,7 +52,7 @@ template Link::CCollection NetworkOf::candidateJoins(GlobalPosition3D start, GlobalPosition3D end) { - if (glm::length(RelativePosition3D(start - end)) < 2000.F) { + if (::distance(start, end) < 2000.F) { return {}; } const auto defs = genCurveDef( @@ -81,7 +81,7 @@ template Link::CCollection NetworkOf::addJoins(GlobalPosition3D start, GlobalPosition3D end) { - if (glm::length(RelativePosition3D(start - end)) < 2000.F) { + if (::distance(start, end) < 2000.F) { return {}; } const auto defs = genCurveDef(start, end, findNodeDirection(nodeAt(start)), findNodeDirection(nodeAt(end))); diff --git a/game/network/rail.cpp b/game/network/rail.cpp index 2820cca..d7de231 100644 --- a/game/network/rail.cpp +++ b/game/network/rail.cpp @@ -40,8 +40,8 @@ RailLinks::addLinksBetween(GlobalPosition3D start, GlobalPosition3D end) const auto flatStart {start.xy()}, flatEnd {end.xy()}; if (node2ins.second == NodeIs::InNetwork) { auto midheight = [&](auto mid) { - const auto sm = glm::length(RelativePosition2D(flatStart - mid)), - em = glm::length(RelativePosition2D(flatEnd - mid)); + const auto sm = ::distance<2>(flatStart, mid); + const auto em = ::distance<2>(flatEnd, mid); return start.z + GlobalDistance(RelativeDistance(end.z - start.z) * (sm / (sm + em))); }; const float dir2 = pi + findNodeDirection(node2ins.first); @@ -117,7 +117,7 @@ RailLinkStraight::RailLinkStraight( RailLinkCurve::RailLinkCurve( NetworkLinkHolder & instances, const Node::Ptr & a, const Node::Ptr & b, GlobalPosition2D c) : - RailLinkCurve(instances, a, b, c || a->pos.z, glm::length(difference(a->pos.xy(), c)), {c, a->pos, b->pos}) + RailLinkCurve(instances, a, b, c || a->pos.z, ::distance<2>(a->pos.xy(), c), {c, a->pos, b->pos}) { } diff --git a/lib/maths.h b/lib/maths.h index 17ca795..3d4f440 100644 --- a/lib/maths.h +++ b/lib/maths.h @@ -111,6 +111,13 @@ difference(const glm::vec & globalA, const glm::vec & globalB) return globalA - globalB; } +template +constexpr auto +distance(const glm::vec & pointA, const glm::vec & pointB) +{ + return glm::length(difference(pointA, pointB)); +} + glm::mat4 flat_orientation(const Rotation3D & diff); namespace { @@ -498,7 +505,7 @@ operator"" _degrees(long double degrees) // Late implementations due to dependencies template constexpr ArcSegment::ArcSegment(PointType centre, PointType ep0, PointType ep1) : - Arc {centre, ep0, ep1}, centre {centre}, ep0 {ep0}, ep1 {ep1}, radius {glm::length(difference(centre, ep0))} + Arc {centre, ep0, ep1}, centre {centre}, ep0 {ep0}, ep1 {ep1}, radius {::distance(centre, ep0)} { } diff --git a/lib/ray.h b/lib/ray.h index a831270..793e21e 100644 --- a/lib/ray.h +++ b/lib/ray.h @@ -27,8 +27,7 @@ public: const auto n2 = crossProduct(direction, n); const auto c1 = p1 + PositionType((glm::dot(RelativePosition3D(start - p1), n2) / glm::dot(d1, n2)) * d1); const auto difflength = glm::length(diff); - if (glm::length(RelativePosition3D(c1 - p1)) > difflength - || glm::length(RelativePosition3D(c1 - e1)) > difflength) { + if (::distance(c1, p1) > difflength || ::distance(c1, e1) > difflength) { return std::numeric_limits::infinity(); } return static_cast(glm::abs(glm::dot(n, RelativePosition3D(p1 - start)))); diff --git a/lib/triangle.h b/lib/triangle.h index d5547ab..e430653 100644 --- a/lib/triangle.h +++ b/lib/triangle.h @@ -48,7 +48,7 @@ struct Triangle : public glm::vec<3, glm::vec> { [[nodiscard]] constexpr auto height() { - return (area() * 2) / glm::length(difference(p(0), p(1))); + return (area() * 2) / ::distance(p(0), p(1)); } [[nodiscard]] constexpr Normal3D diff --git a/test/test-network.cpp b/test/test-network.cpp index 5373dd5..e7419b5 100644 --- a/test/test-network.cpp +++ b/test/test-network.cpp @@ -241,7 +241,7 @@ BOOST_FIXTURE_TEST_CASE(test_rail_network, RailLinks) // -------- auto l0 = addLinksBetween(p000, p100); BOOST_CHECK(dynamic_cast(l0.get())); - BOOST_CHECK_EQUAL(l0->length, glm::length(difference(p000, p100))); + BOOST_CHECK_EQUAL(l0->length, ::distance(p000, p100)); BOOST_CHECK_CLOSE(l0->ends[0].dir, half_pi, 0.1F); BOOST_CHECK_CLOSE(l0->ends[1].dir, -half_pi, 0.1F); BOOST_CHECK(l0->ends[0].nexts.empty()); @@ -249,7 +249,7 @@ BOOST_FIXTURE_TEST_CASE(test_rail_network, RailLinks) auto l1 = addLinksBetween(p200, p100); BOOST_CHECK(dynamic_cast(l1.get())); - BOOST_CHECK_EQUAL(l1->length, glm::length(difference(p200, p100))); + BOOST_CHECK_EQUAL(l1->length, ::distance(p200, p100)); BOOST_CHECK_CLOSE(l1->ends[0].dir, half_pi, 0.1F); BOOST_CHECK_CLOSE(l1->ends[1].dir, -half_pi, 0.1F); BOOST_CHECK(l0->ends[0].nexts.empty()); @@ -261,7 +261,7 @@ BOOST_FIXTURE_TEST_CASE(test_rail_network, RailLinks) auto l2 = addLinksBetween(p200, p300); BOOST_CHECK(dynamic_cast(l2.get())); - BOOST_CHECK_EQUAL(l2->length, glm::length(difference(p200, p300))); + BOOST_CHECK_EQUAL(l2->length, ::distance(p200, p300)); BOOST_CHECK_CLOSE(l2->ends[0].dir, half_pi, 0.1F); BOOST_CHECK_CLOSE(l2->ends[1].dir, -half_pi, 0.1F); BOOST_CHECK(l0->ends[0].nexts.empty()); -- cgit v1.2.3 From dddc07f0189d722fc07f70ae0c1308dcc4fd0978 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 2 Feb 2025 03:18:43 +0000 Subject: Flip edges if better instead of splitting them when cutting triangle strip edge --- game/geoData.cpp | 19 ++++++++++++++++--- 1 file changed, 16 insertions(+), 3 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index 448ff67..1430cb6 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -537,10 +537,21 @@ GeoData::setHeights(const std::span triangleStrip, const } return nullptr; }; + const auto shouldFlip + = [this](const HalfedgeHandle next, const GlobalPosition2D startPoint) -> std::optional { + if (const auto nextEdge = edge_handle(next); is_flip_ok(nextEdge)) { + const auto opposite_point + = point(to_vertex_handle(next_halfedge_handle(opposite_halfedge_handle(next)))).xy(); + if (distance<2>(startPoint, opposite_point) < length<2>(next)) { + return nextEdge; + } + } + return std::nullopt; + }; // Cut along each edge of triangleStrip AB, AC, BC, BD, CD, CE etc std::map *> boundaryTriangles; - auto doBoundaryPart = [this, &boundaryTriangles, &vertexDistFrom, &opts, &addVertexForNormalUpdate]( + auto doBoundaryPart = [this, &boundaryTriangles, &vertexDistFrom, &opts, &addVertexForNormalUpdate, &shouldFlip]( VertexHandle start, VertexHandle end, const Triangle<3> & triangle) { boundaryTriangles.emplace(start, &triangle); const auto endPoint = point(end); @@ -563,9 +574,11 @@ GeoData::setHeights(const std::span triangleStrip, const start = nextDist.first; return true; } - else { - start = split_copy(edge_handle(next), positionOnTriangle(*intersection, triangle)); + else if (const auto nextEdge = shouldFlip(next, startPoint)) { + flip(*nextEdge); + return true; } + start = split_copy(edge_handle(next), positionOnTriangle(*intersection, triangle)); addVertexForNormalUpdate(start); boundaryTriangles.emplace(start, &triangle); return true; -- cgit v1.2.3 From 750d483af501a9b89dffb1e60ff97ca9a5fa2e44 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Mon, 3 Feb 2025 02:35:54 +0000 Subject: Check all adjacent vertex before edges when cutting triangle strip edge --- game/geoData.cpp | 33 ++++++++++++++++++++------------- 1 file changed, 20 insertions(+), 13 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index 1430cb6..22f8682 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -551,13 +551,27 @@ GeoData::setHeights(const std::span triangleStrip, const // Cut along each edge of triangleStrip AB, AC, BC, BD, CD, CE etc std::map *> boundaryTriangles; - auto doBoundaryPart = [this, &boundaryTriangles, &vertexDistFrom, &opts, &addVertexForNormalUpdate, &shouldFlip]( + auto doBoundaryPart = [this, &boundaryTriangles, &opts, &addVertexForNormalUpdate, &shouldFlip]( VertexHandle start, VertexHandle end, const Triangle<3> & triangle) { boundaryTriangles.emplace(start, &triangle); const auto endPoint = point(end); while (!std::ranges::contains(vv_range(start), end)) { const auto startPoint = point(start); - if (std::ranges::none_of(voh_range(start), [&](const auto & outHalf) { + const auto distanceToEndPoint = distance(startPoint.xy(), endPoint.xy()); + if (std::ranges::any_of(vv_range(start), [&](const auto & adjVertex) { + const auto adjPoint = point(adjVertex); + if (distance(adjPoint.xy(), endPoint.xy()) < distanceToEndPoint + && (Triangle<2> {startPoint, endPoint, adjPoint}.area() + / distance(startPoint.xy(), endPoint.xy())) + < opts.nearNodeTolerance) { + start = adjVertex; + return true; + } + return false; + })) { + continue; + } + if (std::ranges::any_of(voh_range(start), [&](const auto & outHalf) { const auto next = next_halfedge_handle(outHalf); const auto nexts = std::array {from_vertex_handle(next), to_vertex_handle(next)}; const auto nextPoints = nexts | std::views::transform([this](const auto v) { @@ -566,15 +580,7 @@ GeoData::setHeights(const std::span triangleStrip, const if (linesCross(startPoint, endPoint, nextPoints.front().second, nextPoints.back().second)) { if (const auto intersection = linesIntersectAt(startPoint.xy(), endPoint.xy(), nextPoints.front().second.xy(), nextPoints.back().second.xy())) { - if (const auto nextDist - = std::ranges::min(nexts | std::views::transform(vertexDistFrom(*intersection)), {}, - &std::pair::second); - nextDist.second < opts.nearNodeTolerance) { - point(nextDist.first).z = positionOnTriangle(point(nextDist.first), triangle).z; - start = nextDist.first; - return true; - } - else if (const auto nextEdge = shouldFlip(next, startPoint)) { + if (const auto nextEdge = shouldFlip(next, startPoint)) { flip(*nextEdge); return true; } @@ -587,9 +593,10 @@ GeoData::setHeights(const std::span triangleStrip, const } return false; })) { - throw std::runtime_error( - std::format("Could not navigate to ({}, {}, {})", endPoint.x, endPoint.y, endPoint.z)); + continue; } + throw std::runtime_error( + std::format("Could not navigate to ({}, {}, {})", endPoint.x, endPoint.y, endPoint.z)); } }; auto doBoundary = [&doBoundaryPart, triangle = strip.begin()](const auto & verts) mutable { -- cgit v1.2.3 From 4667af751eb33edfd88204da8353ba4cf76592a8 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Thu, 6 Feb 2025 19:11:49 +0000 Subject: Update PointFace _face cache as required instead of erroring --- game/geoData.cpp | 7 ++----- 1 file changed, 2 insertions(+), 5 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index 22f8682..5f098e4 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -126,13 +126,10 @@ GeoData::PointFace::PointFace(const GlobalPosition2D p, const GeoData * mesh, Fa GeoData::FaceHandle GeoData::PointFace::face(const GeoData * mesh, FaceHandle start) const { - if (_face.is_valid()) { - assert(mesh->triangleContainsPoint(point, _face)); + if (_face.is_valid() && mesh->triangleContainsPoint(point, _face)) { return _face; } - else { - return (_face = mesh->findPoint(point, start)); - } + return (_face = mesh->findPoint(point, start)); } GeoData::FaceHandle -- cgit v1.2.3 From 87b2d80aabb6b4e6effc423a350963395f528f3c Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Thu, 6 Feb 2025 19:38:20 +0000 Subject: Verify an edge can be flipped Asserts the resulting triangle pair would be both still face up, not the case if the original triangles do not form a convex polygon --- game/geoData.cpp | 15 ++++++++++++--- 1 file changed, 12 insertions(+), 3 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index 5f098e4..74ededa 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -534,9 +534,18 @@ GeoData::setHeights(const std::span triangleStrip, const } return nullptr; }; - const auto shouldFlip - = [this](const HalfedgeHandle next, const GlobalPosition2D startPoint) -> std::optional { - if (const auto nextEdge = edge_handle(next); is_flip_ok(nextEdge)) { + const auto canFlip = [this](const HalfedgeHandle edge) { + const auto opposite = opposite_halfedge_handle(edge); + const auto pointA = point(to_vertex_handle(edge)); + const auto pointB = point(to_vertex_handle(opposite)); + const auto pointC = point(to_vertex_handle(next_halfedge_handle(edge))); + const auto pointD = point(to_vertex_handle(next_halfedge_handle(opposite))); + + return Triangle<2> {pointC, pointB, pointD}.isUp() && Triangle<2> {pointA, pointC, pointD}.isUp(); + }; + const auto shouldFlip = [this, &canFlip](const HalfedgeHandle next, + const GlobalPosition2D startPoint) -> std::optional { + if (const auto nextEdge = edge_handle(next); is_flip_ok(nextEdge) && canFlip(next)) { const auto opposite_point = point(to_vertex_handle(next_halfedge_handle(opposite_halfedge_handle(next)))).xy(); if (distance<2>(startPoint, opposite_point) < length<2>(next)) { -- cgit v1.2.3 From 5f427be93108795ce85d1567ab90ef37fd5e8f11 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 8 Feb 2025 12:53:17 +0000 Subject: Set height when reusing adjacent vertices --- game/geoData.cpp | 1 + 1 file changed, 1 insertion(+) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index 74ededa..4cfcf6d 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -571,6 +571,7 @@ GeoData::setHeights(const std::span triangleStrip, const / distance(startPoint.xy(), endPoint.xy())) < opts.nearNodeTolerance) { start = adjVertex; + point(start).z = positionOnTriangle(adjPoint, triangle).z; return true; } return false; -- cgit v1.2.3 From ca1a83e21d0cdb4b3443252b11789bd8ecff3c86 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 8 Feb 2025 18:11:23 +0000 Subject: Improve logging and fault detection during mesh mutation --- game/geoData.cpp | 34 +++++++++++++++++++++++++++++----- game/geoData.h | 3 ++- 2 files changed, 31 insertions(+), 6 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index 4cfcf6d..816ce03 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -6,6 +6,9 @@ #include #include #include +#ifndef NDEBUG +# include +#endif GeoData GeoData::loadFromAsciiGrid(const std::filesystem::path & input) @@ -554,6 +557,7 @@ GeoData::setHeights(const std::span triangleStrip, const } return std::nullopt; }; + sanityCheck(); // Cut along each edge of triangleStrip AB, AC, BC, BD, CD, CE etc std::map *> boundaryTriangles; @@ -602,6 +606,16 @@ GeoData::setHeights(const std::span triangleStrip, const })) { continue; } +#ifndef NDEBUG + CLOG(start); + CLOG(startPoint); + CLOG(end); + CLOG(endPoint); + for (const auto v : vv_range(start)) { + CLOG(point(v)); + } +#endif + sanityCheck(); throw std::runtime_error( std::format("Could not navigate to ({}, {}, {})", endPoint.x, endPoint.y, endPoint.z)); } @@ -655,6 +669,7 @@ GeoData::setHeights(const std::span triangleStrip, const } done.insert(heh); } + sanityCheck(); std::vector out; auto surfaceStripWalk @@ -686,11 +701,20 @@ GeoData::getGeneration() const } void -GeoData::sanityCheck() const +GeoData::sanityCheck(const std::source_location & loc) const { - if (!std::ranges::all_of(faces(), [this](const auto face) { - return triangle<2>(face).isUp(); - })) { - throw std::logic_error("Upside down faces detected"); + if (const auto upSideDown = std::ranges::count_if(faces(), [this](const auto face) { + if (!triangle<2>(face).isUp()) { +#ifndef NDEBUG + for (const auto v : fv_range(face)) { + CLOG(point(v)); + } +#endif + return true; + } + return false; + }) > 0) { + throw std::logic_error(std::format( + "{} upside down faces detected - checked from {}:{}", upSideDown, loc.function_name(), loc.line())); } } diff --git a/game/geoData.h b/game/geoData.h index 390a443..7c11b07 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -9,6 +9,7 @@ #include #include #include +#include #include #include @@ -115,7 +116,7 @@ public: return property(surface, handle); } - void sanityCheck() const; + void sanityCheck(const std::source_location & = std::source_location::current()) const; protected: template -- cgit v1.2.3 From ecbb621171af0f20751bbc590453d00a7bd38320 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 9 Feb 2025 15:18:35 +0000 Subject: Move lots of geoData helpers into lib --- game/geoData.cpp | 41 ----------------------------------------- lib/maths.h | 46 +++++++++++++++++++++++++++++++++++++++++++--- lib/triangle.h | 27 +++++++++++++++++++++++++++ test/test-maths.cpp | 25 +++++++++++++++++++++++++ 4 files changed, 95 insertions(+), 44 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index 816ce03..3b94564 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -142,47 +142,6 @@ GeoData::PointFace::face(const GeoData * mesh) const } namespace { - template typename Op> - [[nodiscard]] constexpr inline auto - pointLineOp(const GlobalPosition2D p, const GlobalPosition2D e1, const GlobalPosition2D e2) - { - return Op {}(CalcDistance(e2.x - e1.x) * CalcDistance(p.y - e1.y), - CalcDistance(e2.y - e1.y) * CalcDistance(p.x - e1.x)); - } - - constexpr auto pointLeftOfLine = pointLineOp; - constexpr auto pointLeftOfOrOnLine = pointLineOp; - - 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})); - static_assert(pointLeftOfOrOnLine({310000000, 490000000}, {310000000, 490000000}, {310050000, 490050000})); - static_assert(pointLeftOfOrOnLine({310000000, 490000000}, {310050000, 490050000}, {310000000, 490050000})); - static_assert(pointLeftOfOrOnLine({310000000, 490000000}, {310000000, 490050000}, {310000000, 490000000})); - - [[nodiscard]] constexpr inline bool - linesCross( - const GlobalPosition2D a1, const GlobalPosition2D a2, const GlobalPosition2D b1, const GlobalPosition2D 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})); - static_assert(linesCross({2, 2}, {1, 1}, {1, 2}, {2, 1})); - - [[nodiscard]] constexpr inline bool - linesCrossLtR( - const GlobalPosition2D a1, const GlobalPosition2D a2, const GlobalPosition2D b1, const GlobalPosition2D b2) - { - return pointLeftOfLine(a2, b1, b2) && pointLeftOfLine(a1, b2, b1) && pointLeftOfLine(b1, a1, a2) - && pointLeftOfLine(b2, a2, a1); - } - - 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) { diff --git a/lib/maths.h b/lib/maths.h index 3d4f440..2049c78 100644 --- a/lib/maths.h +++ b/lib/maths.h @@ -14,6 +14,9 @@ template concept Arithmetic = std::is_arithmetic_v; +template using CalcType = std::conditional_t, T, int64_t>; +template using DifferenceType = std::conditional_t, T, float>; + struct Arc : public std::pair { template requires(Lc >= 2, Le >= 2) @@ -102,7 +105,7 @@ operator-(const GlobalPosition & global, const CalcPosition & relative) } template -using DifferenceVector = glm::vec, T, float>, Q>; +using DifferenceVector = glm::vec, Q>; template constexpr DifferenceVector @@ -111,6 +114,16 @@ difference(const glm::vec & globalA, const glm::vec & globalB) return globalA - globalB; } +template +using CalcVector = glm::vec, Q>; + +template +constexpr CalcVector +calcDifference(const glm::vec & globalA, const glm::vec & globalB) +{ + return globalA - globalB; +} + template constexpr auto distance(const glm::vec & pointA, const glm::vec & pointB) @@ -364,8 +377,6 @@ normalize(T ang) return ang; } -template using CalcType = std::conditional_t, T, int64_t>; - template [[nodiscard]] constexpr std::optional> linesIntersectAt(const glm::vec<2, T, Q> Aabs, const glm::vec<2, T, Q> Babs, const glm::vec<2, T, Q> Cabs, @@ -547,3 +558,32 @@ ArcSegment::crossesLineAt(const glm::vec<2, T, Q> & lineStart, const glm:: }); return std::make_pair(centre + first.first, first.second); } + +namespace { + template typename Op> + [[nodiscard]] constexpr auto + pointLineOp(const GlobalPosition2D point, const GlobalPosition2D end1, const GlobalPosition2D end2) + { + return Op {}(CalcDistance(end2.x - end1.x) * CalcDistance(point.y - end1.y), + CalcDistance(end2.y - end1.y) * CalcDistance(point.x - end1.x)); + } +} + +constexpr auto pointLeftOfLine = pointLineOp; +constexpr auto pointLeftOfOrOnLine = pointLineOp; + +[[nodiscard]] constexpr bool +linesCross(const GlobalPosition2D lineAend1, const GlobalPosition2D lineAend2, const GlobalPosition2D lineBend1, + const GlobalPosition2D lineBend2) +{ + return (pointLeftOfLine(lineAend2, lineBend1, lineBend2) == pointLeftOfLine(lineAend1, lineBend2, lineBend1)) + && (pointLeftOfLine(lineBend1, lineAend1, lineAend2) == pointLeftOfLine(lineBend2, lineAend2, lineAend1)); +} + +[[nodiscard]] constexpr bool +linesCrossLtR(const GlobalPosition2D lineAend1, const GlobalPosition2D lineAend2, const GlobalPosition2D lineBend1, + const GlobalPosition2D lineBend2) +{ + return pointLeftOfLine(lineAend2, lineBend1, lineBend2) && pointLeftOfLine(lineAend1, lineBend2, lineBend1) + && pointLeftOfLine(lineBend1, lineAend1, lineAend2) && pointLeftOfLine(lineBend2, lineAend2, lineAend1); +} diff --git a/lib/triangle.h b/lib/triangle.h index e430653..abd697c 100644 --- a/lib/triangle.h +++ b/lib/triangle.h @@ -64,6 +64,12 @@ struct Triangle : public glm::vec<3, glm::vec> { return difference(p(side), p(0)); } + [[nodiscard]] constexpr auto + calcSideDifference(glm::length_t side) const + { + return calcDifference(p(side), p(0)); + } + [[nodiscard]] constexpr auto angle(glm::length_t corner) const { @@ -126,4 +132,25 @@ struct Triangle : public glm::vec<3, glm::vec> { { return begin() + 3; } + + [[nodiscard]] + constexpr auto + positionOnPlane(const glm::vec<2, T, Q> coord2d) const + requires(Dim == 3) + { + const auto edgeCrossProduct = crossProduct(calcSideDifference(1), calcSideDifference(2)); + return coord2d + || static_cast( + ((edgeCrossProduct.x * p(0).x) + (edgeCrossProduct.y * p(0).y) + (edgeCrossProduct.z * p(0).z) + - (edgeCrossProduct.x * coord2d.x) - (edgeCrossProduct.y * coord2d.y)) + / edgeCrossProduct.z); + } + + [[nodiscard]] + constexpr bool + containsPoint(const GlobalPosition2D coord) const + { + return pointLeftOfOrOnLine(coord, p(0), p(1)) && pointLeftOfOrOnLine(coord, p(1), p(2)) + && pointLeftOfOrOnLine(coord, p(2), p(0)); + } }; diff --git a/test/test-maths.cpp b/test/test-maths.cpp index 5906757..a6b780a 100644 --- a/test/test-maths.cpp +++ b/test/test-maths.cpp @@ -412,3 +412,28 @@ BOOST_DATA_TEST_CASE(arcline_intersection, BOOST_CHECK_CLOSE(expected->second, intersection->second, 1.F); } } + +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})); +static_assert(pointLeftOfOrOnLine({310000000, 490000000}, {310000000, 490000000}, {310050000, 490050000})); +static_assert(pointLeftOfOrOnLine({310000000, 490000000}, {310050000, 490050000}, {310000000, 490050000})); +static_assert(pointLeftOfOrOnLine({310000000, 490000000}, {310000000, 490050000}, {310000000, 490000000})); + +static_assert(linesCross({1, 1}, {2, 2}, {1, 2}, {2, 1})); +static_assert(linesCross({2, 2}, {1, 1}, {1, 2}, {2, 1})); + +static_assert(linesCrossLtR({1, 1}, {2, 2}, {1, 2}, {2, 1})); +static_assert(!linesCrossLtR({2, 2}, {1, 1}, {1, 2}, {2, 1})); + +static_assert(Triangle<3, GlobalDistance> {{1, 2, 3}, {1, 0, 1}, {-2, 1, 0}}.positionOnPlane({7, -2}) + == GlobalPosition3D {7, -2, 3}); +static_assert(Triangle<3, GlobalDistance> { + {310000000, 490000000, 32800}, {310050000, 490050000, 33000}, {310000000, 490050000, 32700}} + .positionOnPlane({310000000, 490000000}) + == GlobalPosition3D {310000000, 490000000, 32800}); +static_assert(Triangle<3, GlobalDistance> { + {310750000, 490150000, 58400}, {310800000, 490200000, 55500}, {310750000, 490200000, 57600}} + .positionOnPlane({310751000, 490152000}) + == GlobalPosition3D {310751000, 490152000, 58326}); -- cgit v1.2.3 From ec29d7bb5e786549eaa960016ddf511fad010cc5 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 9 Feb 2025 15:23:15 +0000 Subject: Split GeoData mesh basics into a subclass Declutters the class for terrain related things --- game/geoData.cpp | 160 +++---------------------------------------- game/geoData.h | 74 +------------------- game/geoDataMesh.cpp | 118 +++++++++++++++++++++++++++++++ game/geoDataMesh.h | 83 ++++++++++++++++++++++ test/test-geoData-counts.cpp | 1 - test/test-geoData.cpp | 18 +---- 6 files changed, 214 insertions(+), 240 deletions(-) create mode 100644 game/geoDataMesh.cpp create mode 100644 game/geoDataMesh.h (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index 3b94564..a1d9762 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -110,74 +110,6 @@ GeoData::createFlat(GlobalPosition2D lower, GlobalPosition2D upper, GlobalDistan return mesh; } -OpenMesh::FaceHandle -GeoData::findPoint(GlobalPosition2D p) const -{ - return findPoint(p, *faces_sbegin()); -} - -GeoData::PointFace::PointFace(const GlobalPosition2D p, const GeoData * mesh) : - PointFace {p, mesh, *mesh->faces_sbegin()} -{ -} - -GeoData::PointFace::PointFace(const GlobalPosition2D p, const GeoData * mesh, FaceHandle start) : - PointFace {p, mesh->findPoint(p, start)} -{ -} - -GeoData::FaceHandle -GeoData::PointFace::face(const GeoData * mesh, FaceHandle start) const -{ - if (_face.is_valid() && mesh->triangleContainsPoint(point, _face)) { - return _face; - } - return (_face = mesh->findPoint(point, start)); -} - -GeoData::FaceHandle -GeoData::PointFace::face(const GeoData * mesh) const -{ - return face(mesh, *mesh->faces_sbegin()); -} - -namespace { - constexpr GlobalPosition3D - positionOnTriangle(const GlobalPosition2D point, const GeoData::Triangle<3> & t) - { - const CalcPosition3D a = t[1] - t[0], b = t[2] - t[0]; - const auto n = crossProduct(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 -GeoData::findPoint(GlobalPosition2D p, OpenMesh::FaceHandle f) const -{ - 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()) { - const auto e1 = point(to_vertex_handle(*next)); - const auto e2 = point(to_vertex_handle(opposite_halfedge_handle(*next))); - if (pointLeftOfLine(p, e1, e2)) { - break; - } - } - f.reset(); - } - } - return f; -} - -GlobalPosition3D -GeoData::positionAt(const PointFace & p) const -{ - return positionOnTriangle(p.point, triangle<3>(p.face(this))); -} - [[nodiscard]] GeoData::IntersectionResult GeoData::intersectRay(const Ray & ray) const { @@ -230,11 +162,12 @@ GeoData::walkUntil(const PointFace & from, const GlobalPosition2D to, Tester & t) -{ - return pointLeftOfOrOnLine(p, t[0], t[1]) && pointLeftOfOrOnLine(p, t[1], t[2]) - && pointLeftOfOrOnLine(p, t[2], t[0]); -} - -bool -GeoData::triangleContainsPoint(const GlobalPosition2D p, FaceHandle face) const -{ - return triangleContainsPoint(p, triangle<2>(face)); -} - -GeoData::HalfedgeHandle -GeoData::findBoundaryStart() const -{ - return *std::find_if(halfedges_sbegin(), halfedges_end(), [this](const auto heh) { - return is_boundary(heh); - }); -} - -[[nodiscard]] RelativePosition3D -GeoData::difference(const HalfedgeHandle heh) const -{ - return ::difference(point(to_vertex_handle(heh)), point(from_vertex_handle(heh))); -} - -template -[[nodiscard]] RelativeDistance -GeoData::length(const HalfedgeHandle heh) const -{ - return ::distance(point(to_vertex_handle(heh)), point(from_vertex_handle(heh))); -} - -[[nodiscard]] GlobalPosition3D -GeoData::centre(const HalfedgeHandle heh) const -{ - return point(from_vertex_handle(heh)) + (difference(heh) / 2.F); -} - void GeoData::updateAllVertexNormals() { @@ -400,22 +293,6 @@ GeoData::updateVertexNormal(VertexHandle vertex) set_normal(vertex, glm::normalize(n)); } -bool -GeoData::triangleOverlapsTriangle(const Triangle<2> & a, const Triangle<2> & b) -{ - return triangleContainsPoint(a.x, b) || triangleContainsPoint(a.y, b) || triangleContainsPoint(a.z, b) - || triangleContainsPoint(b.x, a) || triangleContainsPoint(b.y, a) || triangleContainsPoint(b.z, a) - || linesCross(a.x, a.y, b.x, b.y) || linesCross(a.x, a.y, b.y, b.z) || linesCross(a.x, a.y, b.z, b.x) - || linesCross(a.y, a.z, b.x, b.y) || linesCross(a.y, a.z, b.y, b.z) || linesCross(a.y, a.z, b.z, b.x) - || linesCross(a.z, a.x, b.x, b.y) || linesCross(a.z, a.x, b.y, b.z) || linesCross(a.z, a.x, b.z, b.x); -} - -bool -GeoData::triangleContainsTriangle(const Triangle<2> & a, const Triangle<2> & b) -{ - return triangleContainsPoint(a.x, b) && triangleContainsPoint(a.y, b) && triangleContainsPoint(a.z, b); -} - std::vector GeoData::setHeights(const std::span triangleStrip, const SetHeightsOpts & opts) { @@ -489,7 +366,7 @@ GeoData::setHeights(const std::span triangleStrip, const auto getTriangle = [&strip](const auto point) -> const Triangle<3> * { if (const auto t = std::ranges::find_if(strip, [point](const auto & triangle) { - return triangleContainsPoint(point, triangle); + return triangle.containsPoint(point); }); t != strip.end()) { return &*t; @@ -534,7 +411,7 @@ GeoData::setHeights(const std::span triangleStrip, const / distance(startPoint.xy(), endPoint.xy())) < opts.nearNodeTolerance) { start = adjVertex; - point(start).z = positionOnTriangle(adjPoint, triangle).z; + point(start).z = triangle.positionOnPlane(adjPoint).z; return true; } return false; @@ -554,7 +431,7 @@ GeoData::setHeights(const std::span triangleStrip, const flip(*nextEdge); return true; } - start = split_copy(edge_handle(next), positionOnTriangle(*intersection, triangle)); + start = split_copy(edge_handle(next), triangle.positionOnPlane(*intersection)); addVertexForNormalUpdate(start); boundaryTriangles.emplace(start, &triangle); return true; @@ -610,7 +487,7 @@ GeoData::setHeights(const std::span triangleStrip, const } } if (toTriangle) { // point within the new strip, adjust vertically by triangle - toPoint.z = positionOnTriangle(toPoint, *toTriangle).z; + toPoint.z = toTriangle->positionOnPlane(toPoint).z; addVertexForNormalUpdate(toVertex); todoOutHalfEdges(toVertex); } @@ -658,22 +535,3 @@ GeoData::getGeneration() const { return generation; } - -void -GeoData::sanityCheck(const std::source_location & loc) const -{ - if (const auto upSideDown = std::ranges::count_if(faces(), [this](const auto face) { - if (!triangle<2>(face).isUp()) { -#ifndef NDEBUG - for (const auto v : fv_range(face)) { - CLOG(point(v)); - } -#endif - return true; - } - return false; - }) > 0) { - throw std::logic_error(std::format( - "{} upside down faces detected - checked from {}:{}", upSideDown, loc.function_name(), loc.line())); - } -} diff --git a/game/geoData.h b/game/geoData.h index 03a2b3a..d486f22 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -1,28 +1,12 @@ #pragma once #include "collections.h" // IWYU pragma: keep IterableCollection -#include "config/types.h" -#include "ray.h" +#include "geoDataMesh.h" #include "surface.h" -#include "triangle.h" -#include #include #include -#include -#include -#include -#include - -struct GeoDataTraits : public OpenMesh::DefaultTraits { - FaceAttributes(OpenMesh::Attributes::Status); - EdgeAttributes(OpenMesh::Attributes::Status); - VertexAttributes(OpenMesh::Attributes::Normal | OpenMesh::Attributes::Status); - HalfedgeAttributes(OpenMesh::Attributes::Status); - using Point = GlobalPosition3D; - using Normal = Normal3D; -}; -class GeoData : public OpenMesh::TriMesh_ArrayKernelT { +class GeoData : public GeoDataMesh { private: const OpenMesh::Helpers::Property surface {this}; @@ -30,35 +14,6 @@ public: static GeoData loadFromAsciiGrid(const std::filesystem::path &); static GeoData createFlat(GlobalPosition2D lower, GlobalPosition2D upper, GlobalDistance h); - struct PointFace { - // NOLINTNEXTLINE(hicpp-explicit-conversions) - PointFace(const GlobalPosition2D p) : point {p} { } - - PointFace(const GlobalPosition2D p, FaceHandle face) : point {p}, _face {face} { } - - PointFace(const GlobalPosition2D p, const GeoData *); - PointFace(const GlobalPosition2D p, const GeoData *, FaceHandle start); - - const GlobalPosition2D point; - [[nodiscard]] FaceHandle face(const GeoData *) const; - [[nodiscard]] FaceHandle face(const GeoData *, FaceHandle start) const; - - [[nodiscard]] bool - isLocated() const - { - return _face.is_valid(); - } - - private: - mutable FaceHandle _face {}; - }; - - template using Triangle = ::Triangle; - - [[nodiscard]] FaceHandle findPoint(GlobalPosition2D) const; - [[nodiscard]] FaceHandle findPoint(GlobalPosition2D, FaceHandle start) const; - - [[nodiscard]] GlobalPosition3D positionAt(const PointFace &) const; using IntersectionLocation = std::pair; using IntersectionResult = std::optional; [[nodiscard]] IntersectionResult intersectRay(const Ray &) const; @@ -89,7 +44,7 @@ public: void boundaryWalkUntil(Tester) const; void boundaryWalkUntil(Tester, HalfedgeHandle start) const; - [[nodiscard]] HalfedgeHandle findEntry(const GlobalPosition2D from, const GlobalPosition2D to) const; + [[nodiscard]] HalfedgeHandle findEntry(GlobalPosition2D from, GlobalPosition2D to) const; struct SetHeightsOpts { static constexpr auto DEFAULT_NEAR_NODE_TOLERANACE = 500.F; @@ -118,30 +73,7 @@ public: return property(surface, handle); } - void sanityCheck(const std::source_location & = std::source_location::current()) const; - protected: - template - [[nodiscard]] Triangle - triangle(FaceHandle face) const - { - Triangle triangle; - std::ranges::transform(fv_range(face), triangle.begin(), [this](auto vertex) { - return point(vertex); - }); - return triangle; - } - - [[nodiscard]] static bool triangleContainsPoint(const GlobalPosition2D, const Triangle<2> &); - [[nodiscard]] bool triangleContainsPoint(const GlobalPosition2D, FaceHandle) const; - [[nodiscard]] static bool triangleOverlapsTriangle(const Triangle<2> &, const Triangle<2> &); - [[nodiscard]] static bool triangleContainsTriangle(const Triangle<2> &, const Triangle<2> &); - [[nodiscard]] HalfedgeHandle findBoundaryStart() const; - [[nodiscard]] RelativePosition3D difference(const HalfedgeHandle) const; - - template [[nodiscard]] RelativeDistance length(const HalfedgeHandle) const; - [[nodiscard]] GlobalPosition3D centre(const HalfedgeHandle) const; - void updateAllVertexNormals(); template void updateAllVertexNormals(const R &); void updateVertexNormal(VertexHandle); diff --git a/game/geoDataMesh.cpp b/game/geoDataMesh.cpp new file mode 100644 index 0000000..aaa8c9c --- /dev/null +++ b/game/geoDataMesh.cpp @@ -0,0 +1,118 @@ +#include "geoDataMesh.h" +#include +#ifndef NDEBUG +# include +#endif + +OpenMesh::FaceHandle +GeoDataMesh::findPoint(GlobalPosition2D coord) const +{ + return findPoint(coord, *faces_sbegin()); +} + +GeoDataMesh::PointFace::PointFace(const GlobalPosition2D coord, const GeoDataMesh * mesh) : + PointFace {coord, mesh, *mesh->faces_sbegin()} +{ +} + +GeoDataMesh::PointFace::PointFace(const GlobalPosition2D coord, const GeoDataMesh * mesh, FaceHandle start) : + PointFace {coord, mesh->findPoint(coord, start)} +{ +} + +OpenMesh::FaceHandle +GeoDataMesh::PointFace::face(const GeoDataMesh * mesh, FaceHandle start) const +{ + if (faceCache.is_valid() && mesh->faceContainsPoint(point, faceCache)) { + return faceCache; + } + return (faceCache = mesh->findPoint(point, start)); +} + +OpenMesh::FaceHandle +GeoDataMesh::PointFace::face(const GeoDataMesh * mesh) const +{ + return face(mesh, *mesh->faces_sbegin()); +} + +GeoDataMesh::HalfEdgeVertices +GeoDataMesh::toVertexHandles(HalfedgeHandle halfEdge) const +{ + return {from_vertex_handle(halfEdge), to_vertex_handle(halfEdge)}; +} + +GeoDataMesh::HalfEdgePoints +GeoDataMesh::points(HalfEdgeVertices vertices) const +{ + return {point(vertices.first), point(vertices.second)}; +} + +OpenMesh::FaceHandle +GeoDataMesh::findPoint(const GlobalPosition2D coord, OpenMesh::FaceHandle face) const +{ + while (face.is_valid() && !triangle<2>(face).containsPoint(coord)) { + for (auto next = cfh_iter(face); next.is_valid(); ++next) { + face = opposite_face_handle(*next); + if (face.is_valid()) { + const auto nextPoints = points(toVertexHandles(*next)); + if (pointLeftOfLine(coord, nextPoints.second, nextPoints.first)) { + break; + } + } + face.reset(); + } + } + return face; +} + +GlobalPosition3D +GeoDataMesh::positionAt(const PointFace & coord) const +{ + return triangle<3>(coord.face(this)).positionOnPlane(coord.point); +} + +bool +GeoDataMesh::faceContainsPoint(const GlobalPosition2D coord, FaceHandle face) const +{ + return triangle<2>(face).containsPoint(coord); +} + +OpenMesh::HalfedgeHandle +GeoDataMesh::findBoundaryStart() const +{ + return *std::find_if(halfedges_sbegin(), halfedges_end(), [this](const auto heh) { + return is_boundary(heh); + }); +} + +[[nodiscard]] RelativePosition3D +GeoDataMesh::difference(const HalfedgeHandle heh) const +{ + return ::difference(point(to_vertex_handle(heh)), point(from_vertex_handle(heh))); +} + +[[nodiscard]] GlobalPosition3D +GeoDataMesh::centre(const HalfedgeHandle heh) const +{ + const auto hehPoints = points(toVertexHandles(heh)); + return midpoint(hehPoints.first, hehPoints.second); +} + +void +GeoDataMesh::sanityCheck(const std::source_location & loc) const +{ + if (const auto upSideDown = std::ranges::count_if(faces(), [this](const auto face) { + if (!triangle<2>(face).isUp()) { +#ifndef NDEBUG + for (const auto vertex : fv_range(face)) { + CLOG(point(vertex)); + } +#endif + return true; + } + return false; + }) > 0) { + throw std::logic_error(std::format( + "{} upside down faces detected - checked from {}:{}", upSideDown, loc.function_name(), loc.line())); + } +} diff --git a/game/geoDataMesh.h b/game/geoDataMesh.h new file mode 100644 index 0000000..00db67c --- /dev/null +++ b/game/geoDataMesh.h @@ -0,0 +1,83 @@ +#pragma once + +#include "config/types.h" +#include "ray.h" +#include "triangle.h" +#include +#include +#include +#include + +struct GeoDataTraits : public OpenMesh::DefaultTraits { + FaceAttributes(OpenMesh::Attributes::Status); + EdgeAttributes(OpenMesh::Attributes::Status); + VertexAttributes(OpenMesh::Attributes::Normal | OpenMesh::Attributes::Status); + HalfedgeAttributes(OpenMesh::Attributes::Status); + using Point = GlobalPosition3D; + using Normal = Normal3D; +}; + +class GeoDataMesh : public OpenMesh::TriMesh_ArrayKernelT { +public: + struct PointFace { + // NOLINTNEXTLINE(hicpp-explicit-conversions) + PointFace(GlobalPosition2D coord) : point {coord} { } + + PointFace(GlobalPosition2D coord, FaceHandle face) : point {coord}, faceCache {face} { } + + PointFace(GlobalPosition2D coord, const GeoDataMesh *); + PointFace(GlobalPosition2D coord, GeoDataMesh const *, FaceHandle start); + + const GlobalPosition2D point; + [[nodiscard]] FaceHandle face(const GeoDataMesh *) const; + [[nodiscard]] FaceHandle face(const GeoDataMesh *, FaceHandle start) const; + + [[nodiscard]] bool + isLocated() const + { + return faceCache.is_valid(); + } + + private: + mutable FaceHandle faceCache; + }; + + template using Triangle = ::Triangle; + + [[nodiscard]] FaceHandle findPoint(GlobalPosition2D) const; + [[nodiscard]] FaceHandle findPoint(GlobalPosition2D, FaceHandle) const; + + [[nodiscard]] GlobalPosition3D positionAt(const PointFace &) const; + +protected: + void sanityCheck(const std::source_location & = std::source_location::current()) const; + + [[nodiscard]] bool faceContainsPoint(GlobalPosition2D, FaceHandle) const; + [[nodiscard]] HalfedgeHandle findBoundaryStart() const; + [[nodiscard]] RelativePosition3D difference(HalfedgeHandle) const; + using HalfEdgeVertices = std::pair; + [[nodiscard]] HalfEdgeVertices toVertexHandles(HalfedgeHandle) const; + using HalfEdgePoints = std::pair; + [[nodiscard]] HalfEdgePoints points(HalfEdgeVertices) const; + + template + [[nodiscard]] RelativeDistance + length(HalfedgeHandle heh) const + { + return ::distance( + point(to_vertex_handle(heh)), point(from_vertex_handle(heh))); + } + + [[nodiscard]] GlobalPosition3D centre(HalfedgeHandle) const; + + template + [[nodiscard]] Triangle + triangle(FaceHandle face) const + { + Triangle triangle; + std::ranges::transform(fv_range(face), triangle.begin(), [this](auto vertex) { + return point(vertex); + }); + return triangle; + } +}; diff --git a/test/test-geoData-counts.cpp b/test/test-geoData-counts.cpp index cad078d..bb43fdb 100644 --- a/test/test-geoData-counts.cpp +++ b/test/test-geoData-counts.cpp @@ -60,5 +60,4 @@ BOOST_DATA_TEST_CASE(deformLogical, BOOST_CHECK_EQUAL(geoData.n_vertices(), expVertices); BOOST_CHECK_EQUAL(geoData.n_edges(), expEdges); BOOST_CHECK_EQUAL(geoData.n_faces(), expFaces); - BOOST_CHECK_NO_THROW(geoData.sanityCheck()); } diff --git a/test/test-geoData.cpp b/test/test-geoData.cpp index 8e5ef2d..dbf5f29 100644 --- a/test/test-geoData.cpp +++ b/test/test-geoData.cpp @@ -34,21 +34,6 @@ BOOST_AUTO_TEST_CASE(sanityCheck) BOOST_CHECK_NO_THROW(sanityCheck()); } -BOOST_AUTO_TEST_CASE(trianglesContainsPoints) -{ - const auto face = face_handle(0); - - BOOST_TEST_CONTEXT(this->triangle<2>(face)) { - BOOST_CHECK(triangleContainsPoint(GlobalPosition2D {xllcorner, yllcorner}, face)); - BOOST_CHECK(triangleContainsPoint(GlobalPosition2D {xllcorner + cellsize, yllcorner + cellsize}, face)); - BOOST_CHECK(triangleContainsPoint(GlobalPosition2D {xllcorner, yllcorner + cellsize}, face)); - BOOST_CHECK(triangleContainsPoint(GlobalPosition2D {xllcorner + 1, yllcorner + 1}, face)); - BOOST_CHECK(triangleContainsPoint(GlobalPosition2D {xllcorner + 1, yllcorner + 2}, face)); - BOOST_CHECK(!triangleContainsPoint(GlobalPosition2D {xllcorner + 3, yllcorner + 2}, face)); - BOOST_CHECK(!triangleContainsPoint(GlobalPosition2D {xllcorner + cellsize, yllcorner}, face)); - } -} - BOOST_AUTO_TEST_SUITE_END(); static const TestTerrainMesh fixedTerrtain; @@ -103,7 +88,7 @@ BOOST_DATA_TEST_CASE(findPositionAt, }), p, h) { - BOOST_CHECK_EQUAL(fixedTerrtain.positionAt(p), GlobalPosition3D(p, h)); + BOOST_CHECK_EQUAL(fixedTerrtain.positionAt(p), p || h); } using FindRayIntersectData = std::tuple; @@ -261,7 +246,6 @@ BOOST_DATA_TEST_CASE(deform, loadFixtureJson("geoData/deform/ surface.colorBias = RGB {0, 0, 1}; auto gd = std::make_shared(GeoData::createFlat({0, 0}, {1000000, 1000000}, 100)); BOOST_CHECK_NO_THROW(gd->setHeights(points, {.surface = &surface})); - BOOST_CHECK_NO_THROW(gd->sanityCheck()); ApplicationBase ab; TestMainWindow tmw; -- cgit v1.2.3 From c9d9aedb9f29725e1106ce1f7ddbc1707400d105 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Mon, 10 Feb 2025 20:07:46 +0000 Subject: Replace mesh generation counter with afterChange event --- game/geoData.cpp | 9 +++------ game/geoData.h | 3 +-- game/terrain.cpp | 8 +++++--- game/terrain.h | 1 + 4 files changed, 10 insertions(+), 11 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index a1d9762..e035a3c 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -64,7 +64,6 @@ GeoData::loadFromAsciiGrid(const std::filesystem::path & input) }); } } - mesh.generation++; mesh.updateAllVertexNormals(); return mesh; @@ -105,7 +104,6 @@ GeoData::createFlat(GlobalPosition2D lower, GlobalPosition2D upper, GlobalDistan } mesh.updateAllVertexNormals(); - mesh.generation++; return mesh; } @@ -526,12 +524,11 @@ GeoData::setHeights(const std::span triangleStrip, const } updateAllVertexNormals(newOrChangedVerts); - generation++; + afterChange(); return out; } -size_t -GeoData::getGeneration() const +void +GeoData::afterChange() { - return generation; } diff --git a/game/geoData.h b/game/geoData.h index d486f22..3d5ea5d 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -56,7 +56,6 @@ public: }; std::vector setHeights(std::span triangleStrip, const SetHeightsOpts &); - [[nodiscard]] size_t getGeneration() const; [[nodiscard]] auto getExtents() const @@ -77,8 +76,8 @@ protected: void updateAllVertexNormals(); template void updateAllVertexNormals(const R &); void updateVertexNormal(VertexHandle); + virtual void afterChange(); private: GlobalPosition3D lowerExtent {}, upperExtent {}; - size_t generation {}; }; diff --git a/game/terrain.cpp b/game/terrain.cpp index 786b9b0..01af163 100644 --- a/game/terrain.cpp +++ b/game/terrain.cpp @@ -56,10 +56,12 @@ Terrain::generateMeshes() void Terrain::tick(TickDuration) { - if (const auto newGeneration = getGeneration(); newGeneration != geoGeneration) { +} + +void +Terrain::afterChange() +{ generateMeshes(); - geoGeneration = newGeneration; - } } void diff --git a/game/terrain.h b/game/terrain.h index 7464bdd..f0f9621 100644 --- a/game/terrain.h +++ b/game/terrain.h @@ -30,6 +30,7 @@ public: }; private: + void afterChange() override; void generateMeshes(); Collection, false> meshes; -- cgit v1.2.3 From 4b175adffdf68f35589ed48c82baa15723a9af0a Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Thu, 13 Feb 2025 19:57:41 +0000 Subject: Move basic setHeights lambdas into proper helper functions --- game/geoData.cpp | 98 +++++++++++++++++++--------------------------------- game/geoData.h | 1 + game/geoDataMesh.cpp | 24 +++++++++++++ game/geoDataMesh.h | 31 ++++++++++++++++- 4 files changed, 90 insertions(+), 64 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index e035a3c..dd7a3f8 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -291,6 +291,37 @@ GeoData::updateVertexNormal(VertexHandle vertex) set_normal(vertex, glm::normalize(n)); } +OpenMesh::VertexHandle +GeoData::setPoint(GlobalPosition3D tsPoint, const SetHeightsOpts & opts) +{ + const auto face = findPoint(tsPoint); + const auto distFromTsPoint = vertexDistanceFunction<2>(tsPoint); + // Check vertices + if (const auto nearest + = std::ranges::min(std::views::iota(fv_begin(face), fv_end(face)) | std::views::transform(distFromTsPoint), + {}, &std::pair::second); + nearest.second < opts.nearNodeTolerance) { + point(nearest.first).z = tsPoint.z; + return nearest.first; + } + // Check edges + if (const auto nearest + = std::ranges::min(std::views::iota(fh_begin(face), fh_end(face)) | std::views::transform(distFromTsPoint), + {}, &std::pair::second); + nearest.second < opts.nearNodeTolerance) { + const auto from = point(from_vertex_handle(nearest.first)).xy(); + const auto to = point(to_vertex_handle(nearest.first)).xy(); + const auto v = vector_normal(from - to); + const auto inter = linesIntersectAt(from, to, tsPoint.xy(), tsPoint.xy() + v); + if (!inter) { + throw std::runtime_error("Perpendicular lines do not cross"); + } + return split_copy(edge_handle(nearest.first), *inter || tsPoint.z); + } + // Nothing close, split face + return split_copy(face, tsPoint); +}; + std::vector GeoData::setHeights(const std::span triangleStrip, const SetHeightsOpts & opts) { @@ -301,57 +332,18 @@ GeoData::setHeights(const std::span triangleStrip, const lowerExtent.z = std::min(upperExtent.z, stripMinMax.min.z); upperExtent.z = std::max(upperExtent.z, stripMinMax.max.z); - const auto vertexDistFrom = [this](GlobalPosition2D p) { - return [p, this](const VertexHandle v) { - return std::make_pair(v, ::distance(p, this->point(v).xy())); - }; - }; - const auto vertexDistFromE = [this](GlobalPosition2D p) { - return [p, this](const HalfedgeHandle e) { - const auto fromPoint = point(from_vertex_handle(e)).xy(); - const auto toPoint = point(to_vertex_handle(e)).xy(); - return std::make_pair(e, Triangle<2> {fromPoint, toPoint, p}.height()); - }; - }; - std::set newOrChangedVerts; auto addVertexForNormalUpdate = [this, &newOrChangedVerts](const VertexHandle vertex) { newOrChangedVerts.emplace(vertex); std::ranges::copy(vv_range(vertex), std::inserter(newOrChangedVerts, newOrChangedVerts.end())); }; - auto newVertexOnFace = [this, &vertexDistFrom, &opts, &vertexDistFromE](GlobalPosition3D tsPoint) { - const auto face = findPoint(tsPoint); - // Check vertices - if (const auto nearest = std::ranges::min( - std::views::iota(fv_begin(face), fv_end(face)) | std::views::transform(vertexDistFrom(tsPoint)), {}, - &std::pair::second); - nearest.second < opts.nearNodeTolerance) { - point(nearest.first).z = tsPoint.z; - return nearest.first; - } - // Check edges - if (const auto nearest = std::ranges::min( - std::views::iota(fh_begin(face), fh_end(face)) | std::views::transform(vertexDistFromE(tsPoint)), - {}, &std::pair::second); - nearest.second < opts.nearNodeTolerance) { - const auto from = point(from_vertex_handle(nearest.first)).xy(); - const auto to = point(to_vertex_handle(nearest.first)).xy(); - const auto v = vector_normal(from - to); - const auto inter = linesIntersectAt(from, to, tsPoint.xy(), tsPoint.xy() + v); - if (!inter) { - throw std::runtime_error("Perpendicular lines do not cross"); - } - return split_copy(edge_handle(nearest.first), *inter || tsPoint.z); - } - // Nothing close, split face - return split_copy(face, tsPoint); - }; - // New vertices for each vertex in triangleStrip std::vector newVerts; newVerts.reserve(triangleStrip.size()); - std::transform(triangleStrip.begin(), triangleStrip.end(), std::back_inserter(newVerts), newVertexOnFace); + std::ranges::transform(triangleStrip, std::back_inserter(newVerts), [this, &opts](auto v) { + return setPoint(v, opts); + }); std::ranges::for_each(newVerts, addVertexForNormalUpdate); // Create temporary triangles from triangleStrip @@ -371,31 +363,11 @@ GeoData::setHeights(const std::span triangleStrip, const } return nullptr; }; - const auto canFlip = [this](const HalfedgeHandle edge) { - const auto opposite = opposite_halfedge_handle(edge); - const auto pointA = point(to_vertex_handle(edge)); - const auto pointB = point(to_vertex_handle(opposite)); - const auto pointC = point(to_vertex_handle(next_halfedge_handle(edge))); - const auto pointD = point(to_vertex_handle(next_halfedge_handle(opposite))); - - return Triangle<2> {pointC, pointB, pointD}.isUp() && Triangle<2> {pointA, pointC, pointD}.isUp(); - }; - const auto shouldFlip = [this, &canFlip](const HalfedgeHandle next, - const GlobalPosition2D startPoint) -> std::optional { - if (const auto nextEdge = edge_handle(next); is_flip_ok(nextEdge) && canFlip(next)) { - const auto opposite_point - = point(to_vertex_handle(next_halfedge_handle(opposite_halfedge_handle(next)))).xy(); - if (distance<2>(startPoint, opposite_point) < length<2>(next)) { - return nextEdge; - } - } - return std::nullopt; - }; sanityCheck(); // Cut along each edge of triangleStrip AB, AC, BC, BD, CD, CE etc std::map *> boundaryTriangles; - auto doBoundaryPart = [this, &boundaryTriangles, &opts, &addVertexForNormalUpdate, &shouldFlip]( + auto doBoundaryPart = [this, &boundaryTriangles, &opts, &addVertexForNormalUpdate]( VertexHandle start, VertexHandle end, const Triangle<3> & triangle) { boundaryTriangles.emplace(start, &triangle); const auto endPoint = point(end); diff --git a/game/geoData.h b/game/geoData.h index 3d5ea5d..1a93d03 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -73,6 +73,7 @@ public: } protected: + [[nodiscard]] VertexHandle setPoint(GlobalPosition3D point, const SetHeightsOpts &); void updateAllVertexNormals(); template void updateAllVertexNormals(const R &); void updateVertexNormal(VertexHandle); diff --git a/game/geoDataMesh.cpp b/game/geoDataMesh.cpp index aaa8c9c..687a025 100644 --- a/game/geoDataMesh.cpp +++ b/game/geoDataMesh.cpp @@ -116,3 +116,27 @@ GeoDataMesh::sanityCheck(const std::source_location & loc) const "{} upside down faces detected - checked from {}:{}", upSideDown, loc.function_name(), loc.line())); } } + +bool +GeoDataMesh::canFlip(const HalfedgeHandle edge) const +{ + const auto opposite = opposite_halfedge_handle(edge); + const auto pointA = point(to_vertex_handle(edge)); + const auto pointB = point(to_vertex_handle(opposite)); + const auto pointC = point(to_vertex_handle(next_halfedge_handle(edge))); + const auto pointD = point(to_vertex_handle(next_halfedge_handle(opposite))); + + return Triangle<2> {pointC, pointB, pointD}.isUp() && Triangle<2> {pointA, pointC, pointD}.isUp(); +}; + +std::optional +GeoDataMesh::shouldFlip(const HalfedgeHandle next, const GlobalPosition2D startPoint) const +{ + if (const auto nextEdge = edge_handle(next); is_flip_ok(nextEdge) && canFlip(next)) { + const auto oppositePoint = point(to_vertex_handle(next_halfedge_handle(opposite_halfedge_handle(next)))).xy(); + if (distance<2>(startPoint, oppositePoint) < length<2>(next)) { + return nextEdge; + } + } + return std::nullopt; +}; diff --git a/game/geoDataMesh.h b/game/geoDataMesh.h index 00db67c..5d0bade 100644 --- a/game/geoDataMesh.h +++ b/game/geoDataMesh.h @@ -1,7 +1,6 @@ #pragma once #include "config/types.h" -#include "ray.h" #include "triangle.h" #include #include @@ -60,6 +59,36 @@ protected: using HalfEdgePoints = std::pair; [[nodiscard]] HalfEdgePoints points(HalfEdgeVertices) const; + template + [[nodiscard]] auto + vertexDistanceFunction(GlobalPosition point) const + { + struct DistanceCalculator { + [[nodiscard]] std::pair + operator()(VertexHandle compVertex) const + { + return std::make_pair( + compVertex, ::distance(point, mesh->point(compVertex))); + } + + [[nodiscard]] + std::pair + operator()(const HalfedgeHandle compHalfedge) const + { + const auto edgePoints = mesh->points(mesh->toVertexHandles(compHalfedge)); + return std::make_pair(compHalfedge, Triangle<2> {edgePoints.second, edgePoints.first, point}.height()); + }; + + const GeoDataMesh * mesh; + GlobalPosition point; + }; + + return DistanceCalculator {this, point}; + } + + [[nodiscard]] bool canFlip(HalfedgeHandle edge) const; + [[nodiscard]] std::optional shouldFlip(HalfedgeHandle next, GlobalPosition2D startPoint) const; + template [[nodiscard]] RelativeDistance length(HalfedgeHandle heh) const -- cgit v1.2.3 From fe58d2e6e20c2fc21b3bfd37f9f78736bb28a6ea Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Fri, 14 Feb 2025 02:36:45 +0000 Subject: Use new helpers to simplify close entity search in GeoData::setPoint --- game/geoData.cpp | 11 ++++------- 1 file changed, 4 insertions(+), 7 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index dd7a3f8..552d2ba 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -1,6 +1,7 @@ #include "geoData.h" #include "collections.h" #include "geometricPlane.h" +#include "util.h" #include #include #include @@ -297,23 +298,19 @@ GeoData::setPoint(GlobalPosition3D tsPoint, const SetHeightsOpts & opts) const auto face = findPoint(tsPoint); const auto distFromTsPoint = vertexDistanceFunction<2>(tsPoint); // Check vertices - if (const auto nearest - = std::ranges::min(std::views::iota(fv_begin(face), fv_end(face)) | std::views::transform(distFromTsPoint), - {}, &std::pair::second); + if (const auto nearest = std::ranges::min(fv_range(face) | std::views::transform(distFromTsPoint), {}, GetSecond); nearest.second < opts.nearNodeTolerance) { point(nearest.first).z = tsPoint.z; return nearest.first; } // Check edges - if (const auto nearest - = std::ranges::min(std::views::iota(fh_begin(face), fh_end(face)) | std::views::transform(distFromTsPoint), - {}, &std::pair::second); + if (const auto nearest = std::ranges::min(fh_range(face) | std::views::transform(distFromTsPoint), {}, GetSecond); nearest.second < opts.nearNodeTolerance) { const auto from = point(from_vertex_handle(nearest.first)).xy(); const auto to = point(to_vertex_handle(nearest.first)).xy(); const auto v = vector_normal(from - to); const auto inter = linesIntersectAt(from, to, tsPoint.xy(), tsPoint.xy() + v); - if (!inter) { + if (!inter) [[unlikely]] { throw std::runtime_error("Perpendicular lines do not cross"); } return split_copy(edge_handle(nearest.first), *inter || tsPoint.z); -- cgit v1.2.3 From f26559dcd25b649d37a1a30e087b70b95f530954 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Fri, 14 Feb 2025 23:53:46 +0000 Subject: Range adaptor to make triangle strip triples --- game/geoData.cpp | 10 ++++------ lib/collections.h | 26 ++++++++++++++++++++++++++ 2 files changed, 30 insertions(+), 6 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index 552d2ba..cfaf44b 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -344,12 +344,10 @@ GeoData::setHeights(const std::span triangleStrip, const std::ranges::for_each(newVerts, addVertexForNormalUpdate); // Create temporary triangles from triangleStrip - std::vector> strip; - std::transform( - strip_begin(triangleStrip), strip_end(triangleStrip), std::back_inserter(strip), [](const auto & newVert) { - const auto [a, b, c] = newVert; - return Triangle<3> {a, b, c}; - }); + const auto strip + = materializeRange(triangleStrip | TriangleTriples | std::views::transform([](const auto & newVert) { + return std::make_from_tuple>(*newVert); + })); auto getTriangle = [&strip](const auto point) -> const Triangle<3> * { if (const auto t = std::ranges::find_if(strip, [point](const auto & triangle) { diff --git a/lib/collections.h b/lib/collections.h index fcd65d3..c81bede 100644 --- a/lib/collections.h +++ b/lib/collections.h @@ -197,6 +197,14 @@ template struct stripiter { return *this; } + constexpr stripiter + operator++(int) + { + auto out {*this}; + ++*this; + return out; + } + constexpr stripiter & operator--() { @@ -205,6 +213,14 @@ template struct stripiter { return *this; } + constexpr stripiter + operator--(int) + { + auto out {*this}; + --*this; + return out; + } + constexpr auto operator-(const stripiter & other) const { @@ -235,6 +251,16 @@ strip_end(IterableCollection auto & cont) return stripiter {cont.end()}; } +struct TriangleTriplesImpl : public std::ranges::range_adaptor_closure { + decltype(auto) + operator()(const auto & triangleStrip) const + { + return std::views::iota(strip_begin(triangleStrip), strip_end(triangleStrip)); + } +}; + +constexpr TriangleTriplesImpl TriangleTriples; + template void mergeClose(std::vector & range, const Dist & dist, const Merger & merger, -- cgit v1.2.3 From 619983e949fde226cc7a3de0bc198fdcee3fe3b4 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 15 Feb 2025 14:46:48 +0000 Subject: Fixes and tests to new range helpers --- game/geoData.cpp | 4 ++-- lib/collections.h | 10 +++++++--- lib/util.h | 8 ++++---- test/test-lib.cpp | 15 ++++++++++++--- 4 files changed, 25 insertions(+), 12 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index cfaf44b..fa96a33 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -345,8 +345,8 @@ GeoData::setHeights(const std::span triangleStrip, const // Create temporary triangles from triangleStrip const auto strip - = materializeRange(triangleStrip | TriangleTriples | std::views::transform([](const auto & newVert) { - return std::make_from_tuple>(*newVert); + = materializeRange(triangleStrip | triangleTriples | std::views::transform([](const auto & newVert) { + return std::make_from_tuple>(newVert); })); auto getTriangle = [&strip](const auto point) -> const Triangle<3> * { if (const auto t = std::ranges::find_if(strip, diff --git a/lib/collections.h b/lib/collections.h index c81bede..27eff0a 100644 --- a/lib/collections.h +++ b/lib/collections.h @@ -251,15 +251,19 @@ strip_end(IterableCollection auto & cont) return stripiter {cont.end()}; } -struct TriangleTriplesImpl : public std::ranges::range_adaptor_closure { +inline constexpr auto dereference = std::views::transform([](const auto & iter) -> decltype(auto) { + return *iter; +}); + +struct TriangleTriples : public std::ranges::range_adaptor_closure { decltype(auto) operator()(const auto & triangleStrip) const { - return std::views::iota(strip_begin(triangleStrip), strip_end(triangleStrip)); + return std::views::iota(strip_begin(triangleStrip), strip_end(triangleStrip)) | dereference; } }; -constexpr TriangleTriplesImpl TriangleTriples; +inline constexpr TriangleTriples triangleTriples; template void diff --git a/lib/util.h b/lib/util.h index 2674eaf..cd7971b 100644 --- a/lib/util.h +++ b/lib/util.h @@ -29,7 +29,7 @@ namespace { }; } -template constexpr auto Nth = GetNth {}; -constexpr auto GetFirst = Nth<0>; -constexpr auto GetSecond = Nth<1>; -constexpr auto GetSwapped = Nth<0, 1>; +template inline constexpr auto Nth = GetNth {}; +inline constexpr auto GetFirst = Nth<0>; +inline constexpr auto GetSecond = Nth<1>; +inline constexpr auto GetSwapped = Nth<0, 1>; diff --git a/test/test-lib.cpp b/test/test-lib.cpp index 7672acc..17c0f63 100644 --- a/test/test-lib.cpp +++ b/test/test-lib.cpp @@ -1,5 +1,6 @@ #define BOOST_TEST_MODULE test_lib +#include "testHelpers.h" #include #include #include @@ -66,8 +67,16 @@ BOOST_AUTO_TEST_CASE(triangle_strip_iter) out.push_back(c); }); BOOST_REQUIRE_EQUAL(out.size(), (TRIANGLE_STRIP_IN.size() - 2) * 3); - BOOST_CHECK_EQUAL_COLLECTIONS( - out.begin(), out.end(), TRIANGLE_STRIP_EXPECTED.begin(), TRIANGLE_STRIP_EXPECTED.end()); + BOOST_CHECK_EQUAL_COLCOL(out, TRIANGLE_STRIP_EXPECTED); +} + +BOOST_AUTO_TEST_CASE(triangle_strip_range_adapter) +{ + using TriTuple = std::tuple; + std::vector outRange; + std::ranges::copy(TRIANGLE_STRIP_IN | triangleTriples, std::back_inserter(outRange)); + constexpr std::array TRIANGLE_STRIP_EXPECTED_TUPLES {{{0, 1, 2}, {2, 1, 3}, {2, 3, 4}, {4, 3, 5}}}; + BOOST_CHECK_EQUAL_COLCOL(outRange, TRIANGLE_STRIP_EXPECTED_TUPLES); } using MergeCloseData = std::tuple, int, std::vector>; @@ -99,5 +108,5 @@ BOOST_DATA_TEST_CASE(mergeCloseInts, return (left + right) / 2; }, tolerance))); - BOOST_CHECK_EQUAL_COLLECTIONS(mutableCollection.begin(), mutableCollection.end(), expected.begin(), expected.end()); + BOOST_CHECK_EQUAL_COLCOL(mutableCollection, expected); } -- cgit v1.2.3 From f3aa7850519bf022689192e7d52ff380daa9f2d1 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Mon, 17 Feb 2025 18:45:30 +0000 Subject: Refactor GeoData::setHeights until a struct made of a logical breakdown of the process --- game/geoData.cpp | 354 ++++++++++++++++++++++++++++++++----------------------- game/geoData.h | 2 +- 2 files changed, 205 insertions(+), 151 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index fa96a33..6052cd1 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -293,19 +293,19 @@ GeoData::updateVertexNormal(VertexHandle vertex) } OpenMesh::VertexHandle -GeoData::setPoint(GlobalPosition3D tsPoint, const SetHeightsOpts & opts) +GeoData::setPoint(GlobalPosition3D tsPoint, const RelativeDistance nearNodeTolerance) { const auto face = findPoint(tsPoint); const auto distFromTsPoint = vertexDistanceFunction<2>(tsPoint); // Check vertices if (const auto nearest = std::ranges::min(fv_range(face) | std::views::transform(distFromTsPoint), {}, GetSecond); - nearest.second < opts.nearNodeTolerance) { + nearest.second < nearNodeTolerance) { point(nearest.first).z = tsPoint.z; return nearest.first; } // Check edges if (const auto nearest = std::ranges::min(fh_range(face) | std::views::transform(distFromTsPoint), {}, GetSecond); - nearest.second < opts.nearNodeTolerance) { + nearest.second < nearNodeTolerance) { const auto from = point(from_vertex_handle(nearest.first)).xy(); const auto to = point(to_vertex_handle(nearest.first)).xy(); const auto v = vector_normal(from - to); @@ -329,170 +329,224 @@ GeoData::setHeights(const std::span triangleStrip, const lowerExtent.z = std::min(upperExtent.z, stripMinMax.min.z); upperExtent.z = std::max(upperExtent.z, stripMinMax.max.z); - std::set newOrChangedVerts; - auto addVertexForNormalUpdate = [this, &newOrChangedVerts](const VertexHandle vertex) { - newOrChangedVerts.emplace(vertex); - std::ranges::copy(vv_range(vertex), std::inserter(newOrChangedVerts, newOrChangedVerts.end())); - }; + class SetHeights { + public: + SetHeights(GeoData * geoData, const std::span triangleStrip) : + geoData(geoData), triangleStrip {triangleStrip}, + strip {materializeRange(triangleStrip | triangleTriples | std::views::transform([](const auto & newVert) { + return std::make_from_tuple>(newVert); + }))} + { + } - // New vertices for each vertex in triangleStrip - std::vector newVerts; - newVerts.reserve(triangleStrip.size()); - std::ranges::transform(triangleStrip, std::back_inserter(newVerts), [this, &opts](auto v) { - return setPoint(v, opts); - }); - std::ranges::for_each(newVerts, addVertexForNormalUpdate); - - // Create temporary triangles from triangleStrip - const auto strip - = materializeRange(triangleStrip | triangleTriples | std::views::transform([](const auto & newVert) { - return std::make_from_tuple>(newVert); - })); - auto getTriangle = [&strip](const auto point) -> const Triangle<3> * { - if (const auto t = std::ranges::find_if(strip, - [point](const auto & triangle) { - return triangle.containsPoint(point); - }); - t != strip.end()) { - return &*t; + std::vector + createVerticesForStrip(RelativeDistance nearNodeTolerance) + { + // New vertices for each vertex in triangleStrip + const auto newVerts + = materializeRange(triangleStrip | std::views::transform([this, nearNodeTolerance](auto v) { + return geoData->setPoint(v, nearNodeTolerance); + })); + std::ranges::for_each(newVerts, [this](auto vertex) { + addVertexForNormalUpdate(vertex); + }); + geoData->sanityCheck(); + return newVerts; } - return nullptr; - }; - sanityCheck(); - - // Cut along each edge of triangleStrip AB, AC, BC, BD, CD, CE etc - std::map *> boundaryTriangles; - auto doBoundaryPart = [this, &boundaryTriangles, &opts, &addVertexForNormalUpdate]( - VertexHandle start, VertexHandle end, const Triangle<3> & triangle) { - boundaryTriangles.emplace(start, &triangle); - const auto endPoint = point(end); - while (!std::ranges::contains(vv_range(start), end)) { - const auto startPoint = point(start); - const auto distanceToEndPoint = distance(startPoint.xy(), endPoint.xy()); - if (std::ranges::any_of(vv_range(start), [&](const auto & adjVertex) { - const auto adjPoint = point(adjVertex); - if (distance(adjPoint.xy(), endPoint.xy()) < distanceToEndPoint - && (Triangle<2> {startPoint, endPoint, adjPoint}.area() - / distance(startPoint.xy(), endPoint.xy())) - < opts.nearNodeTolerance) { - start = adjVertex; - point(start).z = triangle.positionOnPlane(adjPoint).z; - return true; - } - return false; - })) { - continue; + + void + addVertexForNormalUpdate(const VertexHandle vertex) + { + newOrChangedVerts.emplace(vertex); + std::ranges::copy(geoData->vv_range(vertex), std::inserter(newOrChangedVerts, newOrChangedVerts.end())); + } + + const Triangle<3> * + getTriangle(const GlobalPosition2D point) const + { + if (const auto t = std::ranges::find_if(strip, + [point](const auto & triangle) { + return triangle.containsPoint(point); + }); + t != strip.end()) { + return &*t; } - if (std::ranges::any_of(voh_range(start), [&](const auto & outHalf) { - const auto next = next_halfedge_handle(outHalf); - const auto nexts = std::array {from_vertex_handle(next), to_vertex_handle(next)}; - const auto nextPoints = nexts | std::views::transform([this](const auto v) { - return std::make_pair(v, this->point(v)); - }); - if (linesCross(startPoint, endPoint, nextPoints.front().second, nextPoints.back().second)) { - if (const auto intersection = linesIntersectAt(startPoint.xy(), endPoint.xy(), - nextPoints.front().second.xy(), nextPoints.back().second.xy())) { - if (const auto nextEdge = shouldFlip(next, startPoint)) { - flip(*nextEdge); + return nullptr; + } + + void + doBoundaryPart(VertexHandle start, VertexHandle end, const Triangle<3> & triangle, + const RelativeDistance nearNodeTolerance) + { + boundaryTriangles.emplace(start, &triangle); + const auto endPoint = geoData->point(end); + while (!std::ranges::contains(geoData->vv_range(start), end)) { + const auto startPoint = geoData->point(start); + const auto distanceToEndPoint = distance(startPoint.xy(), endPoint.xy()); + if (std::ranges::any_of(geoData->vv_range(start), [&](const auto & adjVertex) { + const auto adjPoint = geoData->point(adjVertex); + if (distance(adjPoint.xy(), endPoint.xy()) < distanceToEndPoint + && (Triangle<2> {startPoint, endPoint, adjPoint}.area() + / distance(startPoint.xy(), endPoint.xy())) + < nearNodeTolerance) { + start = adjVertex; + geoData->point(start).z = triangle.positionOnPlane(adjPoint).z; + return true; + } + return false; + })) { + continue; + } + if (std::ranges::any_of(geoData->voh_range(start), [&](const auto & outHalf) { + const auto next = geoData->next_halfedge_handle(outHalf); + const auto nexts + = std::array {geoData->from_vertex_handle(next), geoData->to_vertex_handle(next)}; + const auto nextPoints = nexts | std::views::transform([this](const auto v) { + return std::make_pair(v, geoData->point(v)); + }); + if (linesCross(startPoint, endPoint, nextPoints.front().second, nextPoints.back().second)) { + if (const auto intersection = linesIntersectAt(startPoint.xy(), endPoint.xy(), + nextPoints.front().second.xy(), nextPoints.back().second.xy())) { + if (const auto nextEdge = geoData->shouldFlip(next, startPoint)) { + geoData->flip(*nextEdge); + return true; + } + start = geoData->split_copy( + geoData->edge_handle(next), triangle.positionOnPlane(*intersection)); + addVertexForNormalUpdate(start); + boundaryTriangles.emplace(start, &triangle); return true; } - start = split_copy(edge_handle(next), triangle.positionOnPlane(*intersection)); - addVertexForNormalUpdate(start); - boundaryTriangles.emplace(start, &triangle); - return true; + throw std::runtime_error("Crossing lines don't intersect"); } - throw std::runtime_error("Crossing lines don't intersect"); - } - return false; - })) { - continue; - } + return false; + })) { + continue; + } #ifndef NDEBUG - CLOG(start); - CLOG(startPoint); - CLOG(end); - CLOG(endPoint); - for (const auto v : vv_range(start)) { - CLOG(point(v)); - } + CLOG(start); + CLOG(startPoint); + CLOG(end); + CLOG(endPoint); + for (const auto v : geoData->vv_range(start)) { + CLOG(geoData->point(v)); + } #endif - sanityCheck(); - throw std::runtime_error( - std::format("Could not navigate to ({}, {}, {})", endPoint.x, endPoint.y, endPoint.z)); - } - }; - auto doBoundary = [&doBoundaryPart, triangle = strip.begin()](const auto & verts) mutable { - const auto & [a, _, c] = verts; - doBoundaryPart(a, c, *triangle); - triangle++; - }; - std::ranges::for_each(newVerts | std::views::adjacent<3>, doBoundary); - doBoundaryPart(*++newVerts.begin(), newVerts.front(), strip.front()); - doBoundaryPart(*++newVerts.rbegin(), newVerts.back(), strip.back()); - - std::set done; - std::set todo; - auto todoOutHalfEdges = [&todo, &done, this](const VertexHandle v) { - std::copy_if(voh_begin(v), voh_end(v), std::inserter(todo, todo.end()), [&done](const auto & h) { - return !done.contains(h); - }); - }; - std::ranges::for_each(newVerts, todoOutHalfEdges); - while (!todo.empty()) { - const auto heh = todo.extract(todo.begin()).value(); - const auto fromVertex = from_vertex_handle(heh); - const auto toVertex = to_vertex_handle(heh); - const auto & fromPoint = point(fromVertex); - auto & toPoint = point(toVertex); - auto toTriangle = getTriangle(toPoint); - if (!toTriangle) { - if (const auto boundaryVertex = boundaryTriangles.find(toVertex); - boundaryVertex != boundaryTriangles.end()) { - toTriangle = boundaryVertex->second; + geoData->sanityCheck(); + throw std::runtime_error( + std::format("Could not navigate to ({}, {}, {})", endPoint.x, endPoint.y, endPoint.z)); } } - if (toTriangle) { // point within the new strip, adjust vertically by triangle - toPoint.z = toTriangle->positionOnPlane(toPoint).z; - addVertexForNormalUpdate(toVertex); - todoOutHalfEdges(toVertex); + + void + cutBoundary(const std::vector & newVerts, RelativeDistance nearNodeTolerance) + { + // Cut along each edge of triangleStrip AB, AC, BC, BD, CD, CE etc + std::ranges::for_each(newVerts | std::views::adjacent<3>, + [this, nearNodeTolerance, triangle = strip.begin()](const auto & verts) mutable { + const auto & [a, _, c] = verts; + doBoundaryPart(a, c, *triangle, nearNodeTolerance); + triangle++; + }); + doBoundaryPart(*++newVerts.begin(), newVerts.front(), strip.front(), nearNodeTolerance); + doBoundaryPart(*++newVerts.rbegin(), newVerts.back(), strip.back(), nearNodeTolerance); } - else if (!toTriangle) { // point without the new strip, adjust vertically by limit - const auto maxOffset = static_cast(opts.maxSlope * length<2>(heh)); - const auto newHeight = std::clamp(toPoint.z, fromPoint.z - maxOffset, fromPoint.z + maxOffset); - if (newHeight != toPoint.z) { - toPoint.z = newHeight; - addVertexForNormalUpdate(toVertex); - std::copy_if(voh_begin(toVertex), voh_end(toVertex), std::inserter(todo, todo.end()), - [this, &boundaryTriangles](const auto & heh) { - return !boundaryTriangles.contains(to_vertex_handle(heh)); + + void + setHeights(const std::vector & newVerts, RelativeDistance maxSlope) + { + std::set done; + std::set todo; + auto todoOutHalfEdges = [&todo, &done, this](const VertexHandle v) { + std::ranges::copy_if(geoData->voh_range(v), std::inserter(todo, todo.end()), [&done](const auto & h) { + return !done.contains(h); + }); + }; + std::ranges::for_each(newVerts, todoOutHalfEdges); + auto setHalfedgeToHeight = [this, &todoOutHalfEdges, maxSlope, &done]( + const auto & setHalfedgeToHeight, const HalfedgeHandle heh) -> void { + const auto [fromVertex, toVertex] = geoData->toVertexHandles(heh); + auto & toPoint = geoData->point(toVertex); + auto toTriangle = getTriangle(toPoint); + if (!toTriangle) { + if (const auto boundaryVertex = boundaryTriangles.find(toVertex); + boundaryVertex != boundaryTriangles.end()) { + toTriangle = boundaryVertex->second; + } + } + if (toTriangle) { // point within the new strip, adjust vertically by triangle + toPoint.z = toTriangle->positionOnPlane(toPoint).z; + todoOutHalfEdges(toVertex); + } + else { // point without the new strip, adjust vertically by limit + const auto maxOffset = static_cast(maxSlope * geoData->length<2>(heh)); + const auto fromHeight = geoData->point(fromVertex).z; + const auto newHeight = std::clamp(toPoint.z, fromHeight - maxOffset, fromHeight + maxOffset); + if (newHeight != toPoint.z) { + toPoint.z = newHeight; + std::ranges::for_each(geoData->voh_range(toVertex), [&setHalfedgeToHeight](const auto heh) { + setHalfedgeToHeight(setHalfedgeToHeight, heh); }); + } + } + done.insert(heh); + }; + while (!todo.empty()) { + setHalfedgeToHeight(setHalfedgeToHeight, todo.extract(todo.begin()).value()); } + std::ranges::for_each(done, [this](const auto heh) { + const auto ends = geoData->toVertexHandles(heh); + addVertexForNormalUpdate(ends.first); + addVertexForNormalUpdate(ends.second); + }); + geoData->sanityCheck(); } - done.insert(heh); - } - sanityCheck(); - - std::vector out; - auto surfaceStripWalk - = [this, &getTriangle, &opts, &out](const auto & surfaceStripWalk, const auto & face) -> void { - if (!property(surface, face)) { - property(surface, face) = opts.surface; - out.emplace_back(face); - std::ranges::for_each( - ff_range(face), [this, &getTriangle, &surfaceStripWalk](const auto & adjacentFaceHandle) { - if (getTriangle(this->triangle<2>(adjacentFaceHandle).centroid())) { - surfaceStripWalk(surfaceStripWalk, adjacentFaceHandle); - } - }); + + std::vector + setSurface(const Surface * surface) + { + std::vector out; + auto surfaceStripWalk = [this, surface, &out](const auto & surfaceStripWalk, const auto & face) -> void { + if (!geoData->property(geoData->surface, face)) { + geoData->property(geoData->surface, face) = surface; + out.emplace_back(face); + std::ranges::for_each( + geoData->ff_range(face), [this, &surfaceStripWalk](const auto & adjacentFaceHandle) { + if (getTriangle(geoData->triangle<2>(adjacentFaceHandle).centroid())) { + surfaceStripWalk(surfaceStripWalk, adjacentFaceHandle); + } + }); + } + }; + for (const auto & triangle : strip) { + surfaceStripWalk(surfaceStripWalk, geoData->findPoint(triangle.centroid())); + } + return out; + } + + std::vector + run(const SetHeightsOpts & opts) + { + const std::vector newVerts = createVerticesForStrip(opts.nearNodeTolerance); + cutBoundary(newVerts, opts.nearNodeTolerance); + setHeights(newVerts, opts.maxSlope); + const auto out = setSurface(opts.surface); + + geoData->updateAllVertexNormals(newOrChangedVerts); + geoData->afterChange(); + + return out; } + + private: + GeoData * geoData; + const std::span triangleStrip; + const std::vector> strip; + std::set newOrChangedVerts; + std::map *> boundaryTriangles; }; - for (const auto & triangle : strip) { - surfaceStripWalk(surfaceStripWalk, findPoint(triangle.centroid())); - } - updateAllVertexNormals(newOrChangedVerts); - afterChange(); - return out; + return SetHeights {this, triangleStrip}.run(opts); } void diff --git a/game/geoData.h b/game/geoData.h index 1a93d03..586b48d 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -73,7 +73,7 @@ public: } protected: - [[nodiscard]] VertexHandle setPoint(GlobalPosition3D point, const SetHeightsOpts &); + [[nodiscard]] VertexHandle setPoint(GlobalPosition3D point, RelativeDistance nearNodeTolerance); void updateAllVertexNormals(); template void updateAllVertexNormals(const R &); void updateVertexNormal(VertexHandle); -- cgit v1.2.3 From f36a3c4b51b1305548e3f645d645b20f1a192f1d Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Mon, 17 Feb 2025 18:50:30 +0000 Subject: Only build/run GeoDataMesh::sanityCheck for debug --- game/geoData.cpp | 6 +++++- game/geoDataMesh.cpp | 4 ++-- game/geoDataMesh.h | 2 ++ 3 files changed, 9 insertions(+), 3 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index 6052cd1..988b11c 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -350,7 +350,9 @@ GeoData::setHeights(const std::span triangleStrip, const std::ranges::for_each(newVerts, [this](auto vertex) { addVertexForNormalUpdate(vertex); }); +#ifndef NDEBUG geoData->sanityCheck(); +#endif return newVerts; } @@ -431,8 +433,8 @@ GeoData::setHeights(const std::span triangleStrip, const for (const auto v : geoData->vv_range(start)) { CLOG(geoData->point(v)); } -#endif geoData->sanityCheck(); +#endif throw std::runtime_error( std::format("Could not navigate to ({}, {}, {})", endPoint.x, endPoint.y, endPoint.z)); } @@ -499,7 +501,9 @@ GeoData::setHeights(const std::span triangleStrip, const addVertexForNormalUpdate(ends.first); addVertexForNormalUpdate(ends.second); }); +#ifndef NDEBUG geoData->sanityCheck(); +#endif } std::vector diff --git a/game/geoDataMesh.cpp b/game/geoDataMesh.cpp index 687a025..60af061 100644 --- a/game/geoDataMesh.cpp +++ b/game/geoDataMesh.cpp @@ -98,16 +98,15 @@ GeoDataMesh::centre(const HalfedgeHandle heh) const return midpoint(hehPoints.first, hehPoints.second); } +#ifndef NDEBUG void GeoDataMesh::sanityCheck(const std::source_location & loc) const { if (const auto upSideDown = std::ranges::count_if(faces(), [this](const auto face) { if (!triangle<2>(face).isUp()) { -#ifndef NDEBUG for (const auto vertex : fv_range(face)) { CLOG(point(vertex)); } -#endif return true; } return false; @@ -116,6 +115,7 @@ GeoDataMesh::sanityCheck(const std::source_location & loc) const "{} upside down faces detected - checked from {}:{}", upSideDown, loc.function_name(), loc.line())); } } +#endif bool GeoDataMesh::canFlip(const HalfedgeHandle edge) const diff --git a/game/geoDataMesh.h b/game/geoDataMesh.h index 5d0bade..befe9fe 100644 --- a/game/geoDataMesh.h +++ b/game/geoDataMesh.h @@ -49,7 +49,9 @@ public: [[nodiscard]] GlobalPosition3D positionAt(const PointFace &) const; protected: +#ifndef NDEBUG void sanityCheck(const std::source_location & = std::source_location::current()) const; +#endif [[nodiscard]] bool faceContainsPoint(GlobalPosition2D, FaceHandle) const; [[nodiscard]] HalfedgeHandle findBoundaryStart() const; -- cgit v1.2.3 From 9c4b26ce6781584ddcd60da8a013ac5757ec05b1 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Tue, 18 Feb 2025 19:25:34 +0000 Subject: Expand new verts collection once Before doing vertex normal recalc only, not on every insert --- game/geoData.cpp | 18 +++++------------- game/geoDataMesh.cpp | 8 ++++++++ game/geoDataMesh.h | 2 ++ 3 files changed, 15 insertions(+), 13 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index 988b11c..c472240 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -347,22 +347,13 @@ GeoData::setHeights(const std::span triangleStrip, const = materializeRange(triangleStrip | std::views::transform([this, nearNodeTolerance](auto v) { return geoData->setPoint(v, nearNodeTolerance); })); - std::ranges::for_each(newVerts, [this](auto vertex) { - addVertexForNormalUpdate(vertex); - }); + std::ranges::copy(newVerts, std::inserter(newOrChangedVerts, newOrChangedVerts.end())); #ifndef NDEBUG geoData->sanityCheck(); #endif return newVerts; } - void - addVertexForNormalUpdate(const VertexHandle vertex) - { - newOrChangedVerts.emplace(vertex); - std::ranges::copy(geoData->vv_range(vertex), std::inserter(newOrChangedVerts, newOrChangedVerts.end())); - } - const Triangle<3> * getTriangle(const GlobalPosition2D point) const { @@ -415,7 +406,7 @@ GeoData::setHeights(const std::span triangleStrip, const } start = geoData->split_copy( geoData->edge_handle(next), triangle.positionOnPlane(*intersection)); - addVertexForNormalUpdate(start); + newOrChangedVerts.emplace(start); boundaryTriangles.emplace(start, &triangle); return true; } @@ -498,8 +489,8 @@ GeoData::setHeights(const std::span triangleStrip, const } std::ranges::for_each(done, [this](const auto heh) { const auto ends = geoData->toVertexHandles(heh); - addVertexForNormalUpdate(ends.first); - addVertexForNormalUpdate(ends.second); + newOrChangedVerts.emplace(ends.first); + newOrChangedVerts.emplace(ends.second); }); #ifndef NDEBUG geoData->sanityCheck(); @@ -536,6 +527,7 @@ GeoData::setHeights(const std::span triangleStrip, const setHeights(newVerts, opts.maxSlope); const auto out = setSurface(opts.surface); + geoData->expandVerts(newOrChangedVerts); geoData->updateAllVertexNormals(newOrChangedVerts); geoData->afterChange(); diff --git a/game/geoDataMesh.cpp b/game/geoDataMesh.cpp index 60af061..8107a5e 100644 --- a/game/geoDataMesh.cpp +++ b/game/geoDataMesh.cpp @@ -140,3 +140,11 @@ GeoDataMesh::shouldFlip(const HalfedgeHandle next, const GlobalPosition2D startP } return std::nullopt; }; + +void +GeoDataMesh::expandVerts(std::set & verts) const +{ + std::ranges::for_each(std::vector(verts.begin(), verts.end()), [&verts, this](auto vertex) { + std::ranges::copy(vv_range(vertex), std::inserter(verts, verts.end())); + }); +} diff --git a/game/geoDataMesh.h b/game/geoDataMesh.h index befe9fe..72b069e 100644 --- a/game/geoDataMesh.h +++ b/game/geoDataMesh.h @@ -3,6 +3,7 @@ #include "config/types.h" #include "triangle.h" #include +#include #include #include #include @@ -90,6 +91,7 @@ protected: [[nodiscard]] bool canFlip(HalfedgeHandle edge) const; [[nodiscard]] std::optional shouldFlip(HalfedgeHandle next, GlobalPosition2D startPoint) const; + void expandVerts(std::set & verts) const; template [[nodiscard]] RelativeDistance -- cgit v1.2.3 From b86883a943b35aa9c2a50cf54f544807adfe4e55 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 23 Feb 2025 13:28:36 +0000 Subject: Add adjusted boundary vertices to new/changes/boundary lists --- game/geoData.cpp | 2 ++ 1 file changed, 2 insertions(+) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index c472240..cf61f20 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -383,6 +383,8 @@ GeoData::setHeights(const std::span triangleStrip, const / distance(startPoint.xy(), endPoint.xy())) < nearNodeTolerance) { start = adjVertex; + newOrChangedVerts.emplace(start); + boundaryTriangles.emplace(start, &triangle); geoData->point(start).z = triangle.positionOnPlane(adjPoint).z; return true; } -- cgit v1.2.3 From 6a1bd528719d19c24f9c4a1fb9e10c6481105556 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 23 Feb 2025 14:55:31 +0000 Subject: Less allocy/work set based surface/recursive height setting --- game/geoData.cpp | 101 ++++++++++++++++++++++++++++++++----------------------- 1 file changed, 59 insertions(+), 42 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index cf61f20..bdd1a9b 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -447,56 +447,72 @@ GeoData::setHeights(const std::span triangleStrip, const doBoundaryPart(*++newVerts.rbegin(), newVerts.back(), strip.back(), nearNodeTolerance); } - void - setHeights(const std::vector & newVerts, RelativeDistance maxSlope) + using HeightSetTodo = std::multimap; + + HeightSetTodo + setSurfaceHeights(const std::span newVerts) { - std::set done; - std::set todo; - auto todoOutHalfEdges = [&todo, &done, this](const VertexHandle v) { - std::ranges::copy_if(geoData->voh_range(v), std::inserter(todo, todo.end()), [&done](const auto & h) { - return !done.contains(h); - }); - }; - std::ranges::for_each(newVerts, todoOutHalfEdges); - auto setHalfedgeToHeight = [this, &todoOutHalfEdges, maxSlope, &done]( - const auto & setHalfedgeToHeight, const HalfedgeHandle heh) -> void { - const auto [fromVertex, toVertex] = geoData->toVertexHandles(heh); - auto & toPoint = geoData->point(toVertex); - auto toTriangle = getTriangle(toPoint); - if (!toTriangle) { - if (const auto boundaryVertex = boundaryTriangles.find(toVertex); + HeightSetTodo out; + auto setSurfaceVertexHeight = [this, &out](const auto & setSurfaceVertexHeight, const VertexHandle vertex, + const VertexHandle previousVertex) -> void { + if (surfaceVerts.contains(vertex)) { + return; + } + auto & point = geoData->point(vertex); + auto triangle = getTriangle(point); + if (!triangle) { + if (const auto boundaryVertex = boundaryTriangles.find(vertex); boundaryVertex != boundaryTriangles.end()) { - toTriangle = boundaryVertex->second; + triangle = boundaryVertex->second; } } - if (toTriangle) { // point within the new strip, adjust vertically by triangle - toPoint.z = toTriangle->positionOnPlane(toPoint).z; - todoOutHalfEdges(toVertex); + if (triangle) { // point within the new strip, adjust vertically by triangle + point.z = triangle->positionOnPlane(point).z; + newOrChangedVerts.emplace(vertex); + surfaceVerts.emplace(vertex); + for (const auto nextVertex : geoData->vv_range(vertex)) { + setSurfaceVertexHeight(setSurfaceVertexHeight, nextVertex, vertex); + } } - else { // point without the new strip, adjust vertically by limit - const auto maxOffset = static_cast(maxSlope * geoData->length<2>(heh)); - const auto fromHeight = geoData->point(fromVertex).z; - const auto newHeight = std::clamp(toPoint.z, fromHeight - maxOffset, fromHeight + maxOffset); - if (newHeight != toPoint.z) { - toPoint.z = newHeight; - std::ranges::for_each(geoData->voh_range(toVertex), [&setHalfedgeToHeight](const auto heh) { - setHalfedgeToHeight(setHalfedgeToHeight, heh); - }); + else if (previousVertex.is_valid()) { + out.emplace(vertex, previousVertex); + } + }; + for (const auto vertex : newVerts) { + setSurfaceVertexHeight(setSurfaceVertexHeight, vertex, VertexHandle {}); + } + return out; + } + + void + setHeightsAsRequired(HeightSetTodo starts, RelativeDistance maxSlope) + { + auto setHalfedgeToHeight = [this, maxSlope](HeightSetTodo & nexts, const VertexHandle vertex, + const VertexHandle previousVertex) -> void { + const auto & fromPoint = geoData->point(previousVertex); + auto & point = geoData->point(vertex); + const auto maxOffset + = static_cast(std::round(maxSlope * ::distance<2>(fromPoint.xy(), point.xy()))); + const auto newHeight = std::clamp(point.z, fromPoint.z - maxOffset, fromPoint.z + maxOffset); + if (newHeight != point.z) { + point.z = newHeight; + newOrChangedVerts.emplace(vertex); + for (const auto nextVertex : geoData->vv_range(vertex)) { + if (nextVertex != previousVertex && !boundaryTriangles.contains(nextVertex)) { + nexts.emplace(nextVertex, vertex); + } } } - done.insert(heh); }; - while (!todo.empty()) { - setHalfedgeToHeight(setHalfedgeToHeight, todo.extract(todo.begin()).value()); + while (!starts.empty()) { + HeightSetTodo nexts; + + for (const auto & start : starts) { + const auto & [toVertex, previousVertex] = start; + setHalfedgeToHeight(nexts, toVertex, previousVertex); + } + starts = std::move(nexts); } - std::ranges::for_each(done, [this](const auto heh) { - const auto ends = geoData->toVertexHandles(heh); - newOrChangedVerts.emplace(ends.first); - newOrChangedVerts.emplace(ends.second); - }); -#ifndef NDEBUG - geoData->sanityCheck(); -#endif } std::vector @@ -526,7 +542,7 @@ GeoData::setHeights(const std::span triangleStrip, const { const std::vector newVerts = createVerticesForStrip(opts.nearNodeTolerance); cutBoundary(newVerts, opts.nearNodeTolerance); - setHeights(newVerts, opts.maxSlope); + setHeightsAsRequired(setSurfaceHeights(newVerts), opts.maxSlope); const auto out = setSurface(opts.surface); geoData->expandVerts(newOrChangedVerts); @@ -541,6 +557,7 @@ GeoData::setHeights(const std::span triangleStrip, const const std::span triangleStrip; const std::vector> strip; std::set newOrChangedVerts; + std::set surfaceVerts; std::map *> boundaryTriangles; }; -- cgit v1.2.3 From fffd56b621a6cf96b2c72221d0a09a736055311a Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 23 Feb 2025 20:02:06 +0000 Subject: Process set height as required in chunks of target vertex --- game/geoData.cpp | 55 ++++++++++++++++++++++++++++++++++++------------------- 1 file changed, 36 insertions(+), 19 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index bdd1a9b..d577392 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -485,31 +485,48 @@ GeoData::setHeights(const std::span triangleStrip, const } void - setHeightsAsRequired(HeightSetTodo starts, RelativeDistance maxSlope) + setHalfedgeToHeight(HeightSetTodo & nexts, HeightSetTodo::const_iterator verticesBegin, + HeightSetTodo::const_iterator verticesEnd, const RelativeDistance maxSlope) { - auto setHalfedgeToHeight = [this, maxSlope](HeightSetTodo & nexts, const VertexHandle vertex, - const VertexHandle previousVertex) -> void { - const auto & fromPoint = geoData->point(previousVertex); - auto & point = geoData->point(vertex); - const auto maxOffset - = static_cast(std::round(maxSlope * ::distance<2>(fromPoint.xy(), point.xy()))); - const auto newHeight = std::clamp(point.z, fromPoint.z - maxOffset, fromPoint.z + maxOffset); - if (newHeight != point.z) { - point.z = newHeight; - newOrChangedVerts.emplace(vertex); - for (const auto nextVertex : geoData->vv_range(vertex)) { - if (nextVertex != previousVertex && !boundaryTriangles.contains(nextVertex)) { - nexts.emplace(nextVertex, vertex); - } + const auto vertex = verticesBegin->first; + auto & point = geoData->point(vertex); + const auto minMaxHeight = std::accumulate(verticesBegin, verticesEnd, + std::pair { + std::numeric_limits::min(), + std::numeric_limits::max(), + }, + [this, maxSlope, point](auto limit, auto previousVertexItr) { + const auto & fromPoint = geoData->point(previousVertexItr.second); + const auto maxOffset = static_cast( + std::round(maxSlope * ::distance<2>(fromPoint.xy(), point.xy()))); + limit.first = std::max(limit.first, fromPoint.z - maxOffset); + limit.second = std::min(limit.second, fromPoint.z + maxOffset); + return limit; + }); + + const auto newHeight = std::clamp(point.z, minMaxHeight.first, minMaxHeight.second); + if (newHeight != point.z) { + point.z = newHeight; + newOrChangedVerts.emplace(vertex); + for (const auto nextVertex : geoData->vv_range(vertex)) { + if (!std::ranges::contains(verticesBegin, verticesEnd, nextVertex, GetSecond) + && !boundaryTriangles.contains(nextVertex)) { + nexts.emplace(nextVertex, vertex); } } - }; + } + } + + void + setHeightsAsRequired(HeightSetTodo starts, RelativeDistance maxSlope) + { while (!starts.empty()) { HeightSetTodo nexts; - for (const auto & start : starts) { - const auto & [toVertex, previousVertex] = start; - setHalfedgeToHeight(nexts, toVertex, previousVertex); + for (const auto chunk : starts | std::views::chunk_by([](const auto a, const auto b) { + return a.first == b.first; + })) { + setHalfedgeToHeight(nexts, chunk.begin(), chunk.end(), maxSlope); } starts = std::move(nexts); } -- cgit v1.2.3 From 7c04c368fe0694b38e2ab46aca078d921c7d44b1 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Mon, 24 Feb 2025 00:10:07 +0000 Subject: Don't rely on triangle centroid not already having a surface --- game/geoData.cpp | 12 ++++++------ game/geoData.h | 2 +- 2 files changed, 7 insertions(+), 7 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index d577392..4291a64 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -319,7 +319,7 @@ GeoData::setPoint(GlobalPosition3D tsPoint, const RelativeDistance nearNodeToler return split_copy(face, tsPoint); }; -std::vector +std::set GeoData::setHeights(const std::span triangleStrip, const SetHeightsOpts & opts) { if (triangleStrip.size() < 3) { @@ -532,14 +532,14 @@ GeoData::setHeights(const std::span triangleStrip, const } } - std::vector + std::set setSurface(const Surface * surface) { - std::vector out; + std::set out; auto surfaceStripWalk = [this, surface, &out](const auto & surfaceStripWalk, const auto & face) -> void { - if (!geoData->property(geoData->surface, face)) { + if (!out.contains(face)) { geoData->property(geoData->surface, face) = surface; - out.emplace_back(face); + out.emplace(face); std::ranges::for_each( geoData->ff_range(face), [this, &surfaceStripWalk](const auto & adjacentFaceHandle) { if (getTriangle(geoData->triangle<2>(adjacentFaceHandle).centroid())) { @@ -554,7 +554,7 @@ GeoData::setHeights(const std::span triangleStrip, const return out; } - std::vector + std::set run(const SetHeightsOpts & opts) { const std::vector newVerts = createVerticesForStrip(opts.nearNodeTolerance); diff --git a/game/geoData.h b/game/geoData.h index 586b48d..b2a75bd 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -55,7 +55,7 @@ public: RelativeDistance maxSlope = DEFAULT_MAX_SLOPE; }; - std::vector setHeights(std::span triangleStrip, const SetHeightsOpts &); + std::set setHeights(std::span triangleStrip, const SetHeightsOpts &); [[nodiscard]] auto getExtents() const -- cgit v1.2.3