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 ++++++++++++++++++++++++++++++-------------------------- 1 file changed, 35 insertions(+), 31 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; -- 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 ++++++++++ 1 file changed, 10 insertions(+) (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"); + } +} -- 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 +++++++++ 1 file changed, 9 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 -- 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 +- 1 file changed, 1 insertion(+), 1 deletion(-) (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())) { -- 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 ++++++++++++++++++++++++--------------------- 1 file changed, 24 insertions(+), 21 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)) { -- 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 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 44 insertions(+) (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 { -- 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 +- 1 file changed, 1 insertion(+), 1 deletion(-) (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; } } -- 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 ++---- 1 file changed, 2 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; } } -- 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 --- game/geoData.cpp | 5 ----- 1 file changed, 5 deletions(-) (limited to 'game/geoData.cpp') 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) { -- 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 +++++++--- 1 file changed, 7 insertions(+), 3 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 -- 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 +++++------ 1 file changed, 5 insertions(+), 6 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; } } -- 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 ++++--- 1 file changed, 4 insertions(+), 3 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; -- 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 +++++++++++++++++++++++++++++----- 1 file changed, 29 insertions(+), 5 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())); } } -- 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 ----------------------------------------- 1 file changed, 41 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) { -- 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 ++++--------------------------------------------------- 1 file changed, 9 insertions(+), 151 deletions(-) (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())); - } -} -- 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 +++------ 1 file changed, 3 insertions(+), 6 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; } -- 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 ++++++++++++++++++++------------------------------------ 1 file changed, 35 insertions(+), 63 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); -- 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 ++++------ 1 file changed, 4 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) { -- 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 ++-- 1 file changed, 2 insertions(+), 2 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, -- 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 ++++++++++++++++++++++++++++++++----------------------- 1 file changed, 204 insertions(+), 150 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 -- 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 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) (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 -- 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 +++++------------- 1 file changed, 5 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(); -- 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 ++++++------ 1 file changed, 6 insertions(+), 6 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); -- cgit v1.2.3