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') 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') 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') 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') diff --git a/game/geoData.cpp b/game/geoData.cpp index 643b24b..8e662b3 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -537,12 +537,12 @@ GeoData::setHeights(const std::span triangleStrip, const } }; auto doBoundary = [&doBoundaryPart, triangle = strip.begin()](const auto & verts) mutable { - const auto & [a, b, c] = verts; - doBoundaryPart(a, b, *triangle); + const auto & [a, _, c] = verts; doBoundaryPart(a, c, *triangle); triangle++; }; std::ranges::for_each(newVerts | std::views::adjacent<3>, doBoundary); + doBoundaryPart(*++newVerts.begin(), newVerts.front(), *strip.rbegin()); doBoundaryPart(*++newVerts.rbegin(), newVerts.back(), *strip.rbegin()); std::set done; -- cgit v1.2.3 From a007ffeed3cfa6af2cbe1053c330ad11927d58de Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Wed, 18 Dec 2024 17:24:02 +0000 Subject: Add sanity checking logic to GeoData --- game/geoData.cpp | 10 ++++++++++ game/geoData.h | 2 ++ 2 files changed, 12 insertions(+) (limited to 'game') diff --git a/game/geoData.cpp b/game/geoData.cpp index 8e662b3..eef5dc7 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -601,3 +601,13 @@ GeoData::setHeights(const std::span triangleStrip, const updateAllVertexNormals(newOrChangedVerts); } + +void +GeoData::sanityCheck() const +{ + if (!std::ranges::all_of(faces(), [this](const auto face) { + return triangle<2>(face).isUp(); + })) { + throw std::logic_error("Upside down faces detected"); + } +} diff --git a/game/geoData.h b/game/geoData.h index 79924d3..01582a6 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -98,6 +98,8 @@ public: return property(surface, h); } + void sanityCheck() const; + protected: template [[nodiscard]] Triangle -- cgit v1.2.3 From d8ee91b44e31cf1500926d37b7391e8c94bbf14a Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 21 Dec 2024 03:30:18 +0000 Subject: Fix calculating radius and length of curved links --- game/network/link.h | 6 +++--- game/network/rail.cpp | 11 ++++++----- game/network/rail.h | 4 ++-- 3 files changed, 11 insertions(+), 10 deletions(-) (limited to 'game') diff --git a/game/network/link.h b/game/network/link.h index 725e023..4cca52c 100644 --- a/game/network/link.h +++ b/game/network/link.h @@ -16,7 +16,7 @@ template class Ray; // it has location class Node : public StdTypeDefs { public: - explicit Node(GlobalPosition3D p) noexcept : pos(p) {}; + explicit Node(GlobalPosition3D p) noexcept : pos(p) { }; virtual ~Node() noexcept = default; NO_COPY(Node); NO_MOVE(Node); @@ -38,7 +38,7 @@ public: Nexts nexts {}; }; - Link(End, End, float); + Link(End, End, RelativeDistance length); virtual ~Link() = default; NO_COPY(Link); NO_MOVE(Link); @@ -76,7 +76,7 @@ LinkStraight::~LinkStraight() = default; class LinkCurve : public virtual Link { public: inline ~LinkCurve() override = 0; - LinkCurve(GlobalPosition3D, RelativeDistance, Arc); + LinkCurve(GlobalPosition3D centreBase, RelativeDistance radius, Arc); NO_COPY(LinkCurve); NO_MOVE(LinkCurve); diff --git a/game/network/rail.cpp b/game/network/rail.cpp index 6f04070..69422aa 100644 --- a/game/network/rail.cpp +++ b/game/network/rail.cpp @@ -108,16 +108,17 @@ RailLinkStraight::RailLinkStraight( { } -RailLinkCurve::RailLinkCurve(NetworkLinkHolder & instances, const Node::Ptr & a, const Node::Ptr & b, - GlobalPosition2D c) : RailLinkCurve(instances, a, b, c || a->pos.z, {c, a->pos, b->pos}) +RailLinkCurve::RailLinkCurve( + NetworkLinkHolder & instances, const Node::Ptr & a, const Node::Ptr & b, GlobalPosition2D c) : + RailLinkCurve(instances, a, b, c || a->pos.z, glm::length(difference(a->pos.xy(), c)), {c, a->pos, b->pos}) { } RailLinkCurve::RailLinkCurve(NetworkLinkHolder & instances, const Node::Ptr & a, const Node::Ptr & b, - GlobalPosition3D c, const Arc arc) : + GlobalPosition3D c, RelativeDistance radius, const Arc arc) : Link({a, normalize(arc.first + half_pi)}, {b, normalize(arc.second - half_pi)}, - glm::length(RelativePosition3D(a->pos - c)) * arc.length()), - LinkCurve {c, glm::length(RelativePosition3D(ends[0].node->pos - c)), arc}, + glm::length(RelativePosition2D {radius * arc.length(), difference(a->pos, b->pos).z})), + LinkCurve {c, radius, arc}, instance {instances.vertices.acquire(ends[0].node->pos, ends[1].node->pos, c, round_sleepers(length / 2000.F), half_pi - arc.first, half_pi - arc.second, radius)} { diff --git a/game/network/rail.h b/game/network/rail.h index c8effef..0aae718 100644 --- a/game/network/rail.h +++ b/game/network/rail.h @@ -62,8 +62,8 @@ public: }; private: - RailLinkCurve( - NetworkLinkHolder &, const Node::Ptr &, const Node::Ptr &, GlobalPosition3D, const Arc); + RailLinkCurve(NetworkLinkHolder &, const Node::Ptr &, const Node::Ptr &, GlobalPosition3D centreBase, + RelativeDistance radius, Arc); InstanceVertices::InstanceProxy instance; }; -- 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') 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 2e66a686cd6cf589c583060921430a94b2849e83 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 21 Dec 2024 14:10:01 +0000 Subject: Expose network link interface to define a base area of the link --- game/network/link.cpp | 35 +++++++++++++++++++++++++++++++++++ game/network/link.h | 3 +++ 2 files changed, 38 insertions(+) (limited to 'game') diff --git a/game/network/link.cpp b/game/network/link.cpp index 79af92a..61e8771 100644 --- a/game/network/link.cpp +++ b/game/network/link.cpp @@ -38,6 +38,20 @@ LinkStraight::intersectRay(const Ray & ray) const std::array {GlobalPosition3D {ends.front().node->pos}, GlobalPosition3D {ends.back().node->pos}}, 1000); } +std::vector +LinkStraight::getBase(RelativeDistance width) const +{ + const auto start = ends.front().node->pos; + const auto end = ends.back().node->pos; + const auto direction = (vector_normal(normalize(::difference(start, end).xy())) * width / 2.F) || 0.F; + return { + start - direction, + start + direction, + end - direction, + end + direction, + }; +} + Location LinkCurve::positionAt(float dist, unsigned char start) const { @@ -73,3 +87,24 @@ LinkCurve::intersectRay(const Ray & ray) const } return ray.passesCloseToEdges(points, 1.F); } + +std::vector +LinkCurve::getBase(RelativeDistance width) const +{ + const auto start = ends.front().node->pos; + const auto end = ends.back().node->pos; + const auto segs = std::ceil(15.F * arc.length()); + const auto step {glm::vec<2, RelativeDistance> {arc.length(), end.z - start.z} / segs}; + + auto segCount = static_cast(segs) + 1; + std::vector out; + out.reserve(segCount); + for (RelativePosition2D swing = {arc.first, centreBase.z - start.z}; segCount != 0U; swing += step, --segCount) { + const auto direction = sincos(swing.x); + const auto linkCentre = centreBase + ((direction * radius) || swing.y); + const auto toEdge = (direction * width / 2.F) || 0.F; + out.emplace_back(linkCentre + toEdge); + out.emplace_back(linkCentre - toEdge); + } + return out; +} diff --git a/game/network/link.h b/game/network/link.h index 4cca52c..59bbb65 100644 --- a/game/network/link.h +++ b/game/network/link.h @@ -45,6 +45,7 @@ public: [[nodiscard]] virtual Location positionAt(RelativeDistance dist, unsigned char start) const = 0; [[nodiscard]] virtual bool intersectRay(const Ray &) const = 0; + [[nodiscard]] virtual std::vector getBase(RelativeDistance width) const = 0; std::array ends; float length; @@ -69,6 +70,7 @@ public: [[nodiscard]] Location positionAt(RelativeDistance dist, unsigned char start) const override; [[nodiscard]] bool intersectRay(const Ray &) const override; + [[nodiscard]] std::vector getBase(RelativeDistance width) const override; }; LinkStraight::~LinkStraight() = default; @@ -82,6 +84,7 @@ public: [[nodiscard]] Location positionAt(RelativeDistance dist, unsigned char start) const override; [[nodiscard]] bool intersectRay(const Ray &) const override; + [[nodiscard]] std::vector getBase(RelativeDistance width) const override; GlobalPosition3D centreBase; RelativeDistance radius; -- cgit v1.2.3 From 4481f97f2114d07d999744224e53039b85b04553 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 21 Dec 2024 19:13:20 +0000 Subject: Adjust track height to blend into terrain --- game/network/rail.cpp | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'game') diff --git a/game/network/rail.cpp b/game/network/rail.cpp index 69422aa..f226327 100644 --- a/game/network/rail.cpp +++ b/game/network/rail.cpp @@ -8,7 +8,7 @@ template class NetworkOf; constexpr auto RAIL_CROSSSECTION_VERTICES {5U}; -constexpr Size3D RAIL_HEIGHT {0, 0, 250.F}; +constexpr Size3D RAIL_HEIGHT {0, 0, 50.F}; RailLinks::RailLinks() : NetworkOf {"rails.jpg"} { } @@ -74,11 +74,11 @@ RailLinks::addLinksBetween(GlobalPosition3D start, GlobalPosition3D end) } constexpr const std::array railCrossSection {{ - {-1900.F, 0.F, 0.F}, + {-1900.F, 0.F, -RAIL_HEIGHT.z * 2}, {-608.F, 0.F, RAIL_HEIGHT.z}, - {0, 0.F, RAIL_HEIGHT.z * .7F}, + {0, 0.F, RAIL_HEIGHT.z / 2}, {608.F, 0.F, RAIL_HEIGHT.z}, - {1900.F, 0.F, 0.F}, + {1900.F, 0.F, -RAIL_HEIGHT.z * 2}, }}; constexpr const std::array railTexturePos { 0.F, -- cgit v1.2.3 From 20308e0a8d62e575237310b7de919e9c7410a9d7 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 22 Dec 2024 12:41:37 +0000 Subject: Store a generation number for GeoData --- game/geoData.cpp | 9 +++++++++ game/geoData.h | 2 ++ 2 files changed, 11 insertions(+) (limited to 'game') diff --git a/game/geoData.cpp b/game/geoData.cpp index d15a51b..5771a2f 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -66,6 +66,7 @@ GeoData::loadFromAsciiGrid(const std::filesystem::path & input) }); } } + mesh.generation++; mesh.updateAllVertexNormals(); return mesh; @@ -106,6 +107,7 @@ GeoData::createFlat(GlobalPosition2D lower, GlobalPosition2D upper, GlobalDistan } mesh.updateAllVertexNormals(); + mesh.generation++; return mesh; } @@ -601,6 +603,13 @@ GeoData::setHeights(const std::span triangleStrip, const surfaceStripWalk(surfaceStripWalk, findPoint(strip.front().centroid())); updateAllVertexNormals(newOrChangedVerts); + generation++; +} + +size_t +GeoData::getGeneration() const +{ + return generation; } void diff --git a/game/geoData.h b/game/geoData.h index 01582a6..8eda99a 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -84,6 +84,7 @@ public: }; void setHeights(std::span triangleStrip, const SetHeightsOpts &); + [[nodiscard]] size_t getGeneration() const; [[nodiscard]] auto getExtents() const @@ -128,4 +129,5 @@ protected: private: GlobalPosition3D lowerExtent {}, upperExtent {}; + size_t generation {}; }; -- cgit v1.2.3 From c5f1f0b1b82b0672768992fd324adce9f379f9a7 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 22 Dec 2024 12:43:31 +0000 Subject: Update terrain meshes as required --- game/terrain.cpp | 4 ++++ game/terrain.h | 3 ++- 2 files changed, 6 insertions(+), 1 deletion(-) (limited to 'game') diff --git a/game/terrain.cpp b/game/terrain.cpp index bb8e3ce..e7508d0 100644 --- a/game/terrain.cpp +++ b/game/terrain.cpp @@ -66,6 +66,10 @@ Terrain::generateMeshes() void Terrain::tick(TickDuration) { + if (const auto newGeneration = geoData->getGeneration(); newGeneration != geoGeneration) { + generateMeshes(); + geoGeneration = newGeneration; + } } void diff --git a/game/terrain.h b/game/terrain.h index 7d074cf..c9d09fe 100644 --- a/game/terrain.h +++ b/game/terrain.h @@ -27,10 +27,11 @@ public: RGB colourBias; }; +private: void generateMeshes(); -private: std::shared_ptr geoData; Collection, false> meshes; Texture::Ptr grass; + size_t geoGeneration {}; }; -- cgit v1.2.3 From 7a0121a612e901585fef39c1b599d53a21cb0afe Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 22 Dec 2024 12:58:57 +0000 Subject: SetHeightOptions surface changed to defaulted pointer --- game/geoData.cpp | 2 +- game/geoData.h | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-) (limited to 'game') diff --git a/game/geoData.cpp b/game/geoData.cpp index 5771a2f..d8caff7 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -591,7 +591,7 @@ GeoData::setHeights(const std::span triangleStrip, const auto surfaceStripWalk = [this, &getTriangle, &opts](const auto & surfaceStripWalk, const auto & face) -> void { if (!property(surface, face)) { - property(surface, face) = &opts.surface; + property(surface, face) = opts.surface; std::ranges::for_each( ff_range(face), [this, &getTriangle, &surfaceStripWalk](const auto & adjacentFaceHandle) { if (getTriangle(this->triangle<2>(adjacentFaceHandle).centroid())) { diff --git a/game/geoData.h b/game/geoData.h index 8eda99a..92b9b75 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -78,7 +78,7 @@ public: static constexpr auto DEFAULT_NEAR_NODE_TOLERANACE = 500.F; static constexpr auto DEFAULT_MAX_SLOPE = 0.5F; - const Surface & surface; + const Surface * surface = nullptr; RelativeDistance nearNodeTolerance = DEFAULT_NEAR_NODE_TOLERANACE; RelativeDistance maxSlope = DEFAULT_MAX_SLOPE; }; -- cgit v1.2.3 From 8b388c4ee59961f4d307c7f9f87641beffb76a53 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 22 Dec 2024 13:29:15 +0000 Subject: Expose network base width and surface --- game/network/network.h | 4 ++++ game/network/rail.cpp | 14 ++++++++++++++ game/network/rail.h | 3 +++ 3 files changed, 21 insertions(+) (limited to 'game') diff --git a/game/network/network.h b/game/network/network.h index be0900b..f8739b8 100644 --- a/game/network/network.h +++ b/game/network/network.h @@ -14,6 +14,7 @@ #include class SceneShader; +class Surface; template class Ray; template using GenDef = std::tuple...>; @@ -47,6 +48,9 @@ public: [[nodiscard]] virtual float findNodeDirection(Node::AnyCPtr) const = 0; + [[nodiscard]] virtual const Surface * getBaseSurface() const = 0; + [[nodiscard]] virtual RelativeDistance getBaseWidth() const = 0; + protected: static void joinLinks(const Link::Ptr & l, const Link::Ptr & ol); static GenCurveDef genCurveDef(const GlobalPosition3D & start, const GlobalPosition3D & end, float startDir); diff --git a/game/network/rail.cpp b/game/network/rail.cpp index f226327..dc62cf3 100644 --- a/game/network/rail.cpp +++ b/game/network/rail.cpp @@ -1,4 +1,6 @@ #include "rail.h" +#include "game/gamestate.h" +#include "game/geoData.h" #include "network.h" #include // IWYU pragma: keep #include @@ -169,3 +171,15 @@ RailLinks::render(const SceneShader & shader) const glBindVertexArray(0); } } + +const Surface * +RailLinks::getBaseSurface() const +{ + return std::dynamic_pointer_cast(gameState->assets.at("terrain.surface.gravel")).get(); +} + +RelativeDistance +RailLinks::getBaseWidth() const +{ + return 5'700; +} diff --git a/game/network/rail.h b/game/network/rail.h index 0aae718..fa64eda 100644 --- a/game/network/rail.h +++ b/game/network/rail.h @@ -77,6 +77,9 @@ public: std::shared_ptr addLinksBetween(GlobalPosition3D start, GlobalPosition3D end); void render(const SceneShader &) const override; + [[nodiscard]] const Surface * getBaseSurface() const override; + [[nodiscard]] RelativeDistance getBaseWidth() const override; + private: void tick(TickDuration elapsed) override; }; -- 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') 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') 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') 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 485143ae90aa692aef47c1c7aba8775818a026aa Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Tue, 24 Dec 2024 15:02:10 +0000 Subject: Fix calculations for sleeper texture coords --- game/network/rail.cpp | 22 ++++++++++++++-------- 1 file changed, 14 insertions(+), 8 deletions(-) (limited to 'game') diff --git a/game/network/rail.cpp b/game/network/rail.cpp index dc62cf3..baf48f3 100644 --- a/game/network/rail.cpp +++ b/game/network/rail.cpp @@ -91,10 +91,17 @@ constexpr const std::array railTexturePos { }; constexpr auto sleepers {5.F}; // There are 5 repetitions of sleepers in the texture -inline auto -round_sleepers(const float v) -{ - return round_frac(v, sleepers); +namespace { + template constexpr T SLEEPERS_PER_TEXTURE {5}; + template constexpr T TEXTURE_LENGTH {2'000}; + template constexpr T SLEEPER_LENGTH {T {1} / SLEEPERS_PER_TEXTURE}; + + template + constexpr auto + roundSleepers(const T length) + { + return round_frac(length / TEXTURE_LENGTH, SLEEPER_LENGTH); + } } RailLinkStraight::RailLinkStraight(NetworkLinkHolder & instances, const Node::Ptr & a, @@ -106,7 +113,7 @@ RailLinkStraight::RailLinkStraight( NetworkLinkHolder & instances, Node::Ptr a, Node::Ptr b, const RelativePosition3D & diff) : Link({std::move(a), vector_yaw(diff)}, {std::move(b), vector_yaw(-diff)}, glm::length(diff)), instance {instances.vertices.acquire( - ends[0].node->pos, ends[1].node->pos, flat_orientation(diff), round_sleepers(length / 2000.F))} + ends[0].node->pos, ends[1].node->pos, flat_orientation(diff), roundSleepers(length))} { } @@ -120,9 +127,8 @@ RailLinkCurve::RailLinkCurve(NetworkLinkHolder & instances, const GlobalPosition3D c, RelativeDistance radius, const Arc arc) : Link({a, normalize(arc.first + half_pi)}, {b, normalize(arc.second - half_pi)}, glm::length(RelativePosition2D {radius * arc.length(), difference(a->pos, b->pos).z})), - LinkCurve {c, radius, arc}, - instance {instances.vertices.acquire(ends[0].node->pos, ends[1].node->pos, c, round_sleepers(length / 2000.F), - half_pi - arc.first, half_pi - arc.second, radius)} + LinkCurve {c, radius, arc}, instance {instances.vertices.acquire(ends[0].node->pos, ends[1].node->pos, c, + roundSleepers(length), half_pi - arc.first, half_pi - arc.second, radius)} { } -- cgit v1.2.3 From 6ad6d935d8a601908d49a82fb56f1f2c14871573 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Tue, 24 Dec 2024 15:07:32 +0000 Subject: Enable min mipmap on network texture --- game/network/network.cpp | 8 +++++++- 1 file changed, 7 insertions(+), 1 deletion(-) (limited to 'game') diff --git a/game/network/network.cpp b/game/network/network.cpp index 6ba3ed6..1666c4d 100644 --- a/game/network/network.cpp +++ b/game/network/network.cpp @@ -8,7 +8,13 @@ #include #include -Network::Network(const std::string & tn) : texture {std::make_shared(tn)} { } +Network::Network(const std::string & tn) : + texture {std::make_shared(tn, + TextureOptions { + .minFilter = GL_NEAREST_MIPMAP_LINEAR, + })} +{ +} Node::Ptr Network::nodeAt(GlobalPosition3D pos) -- cgit v1.2.3 From 4e6539a9cfb4fa19c87ac23b929a8bd2683c5626 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Tue, 24 Dec 2024 15:29:57 +0000 Subject: Update rails render for being atop a surface --- game/network/rail.cpp | 35 ++++++++++++++++++----------------- 1 file changed, 18 insertions(+), 17 deletions(-) (limited to 'game') diff --git a/game/network/rail.cpp b/game/network/rail.cpp index baf48f3..2820cca 100644 --- a/game/network/rail.cpp +++ b/game/network/rail.cpp @@ -75,23 +75,21 @@ RailLinks::addLinksBetween(GlobalPosition3D start, GlobalPosition3D end) return addLink(start, end, centre.first); } -constexpr const std::array railCrossSection {{ - {-1900.F, 0.F, -RAIL_HEIGHT.z * 2}, - {-608.F, 0.F, RAIL_HEIGHT.z}, - {0, 0.F, RAIL_HEIGHT.z / 2}, - {608.F, 0.F, RAIL_HEIGHT.z}, - {1900.F, 0.F, -RAIL_HEIGHT.z * 2}, -}}; -constexpr const std::array railTexturePos { - 0.F, - .34F, - .5F, - .66F, - 1.F, -}; -constexpr auto sleepers {5.F}; // There are 5 repetitions of sleepers in the texture - namespace { + constexpr const std::array RAIL_CROSS_SECTION {{ + {-1330.F, 0.F, 0}, + {-608.F, 0.F, RAIL_HEIGHT.z}, + {0, 0.F, RAIL_HEIGHT.z / 2}, + {608.F, 0.F, RAIL_HEIGHT.z}, + {1330.F, 0.F, 0}, + }}; + constexpr const std::array RAIL_TEXTURE_POS { + 0.15F, + .34F, + .5F, + .66F, + 0.85F, + }; template constexpr T SLEEPERS_PER_TEXTURE {5}; template constexpr T TEXTURE_LENGTH {2'000}; template constexpr T SLEEPER_LENGTH {T {1} / SLEEPERS_PER_TEXTURE}; @@ -160,7 +158,7 @@ namespace { renderType(const NetworkLinkHolder & n, auto & s) { if (auto count = n.vertices.size()) { - s.use(railCrossSection, railTexturePos); + s.use(RAIL_CROSS_SECTION, RAIL_TEXTURE_POS); glBindVertexArray(n.vao); glDrawArrays(GL_POINTS, 0, static_cast(count)); } @@ -172,8 +170,11 @@ RailLinks::render(const SceneShader & shader) const { if (!links.objects.empty()) { texture->bind(); + glEnable(GL_POLYGON_OFFSET_FILL); + glPolygonOffset(-1, 0); renderType(*this, shader.networkStraight); renderType(*this, shader.networkCurve); + glDisable(GL_POLYGON_OFFSET_FILL); glBindVertexArray(0); } } -- cgit v1.2.3 From eb4b851381453c1f60ccb56e966ca4e7b8e80b97 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Mon, 30 Dec 2024 13:30:48 +0000 Subject: Fix naming style of getSurface --- game/geoData.h | 4 ++-- game/terrain.cpp | 4 ++-- 2 files changed, 4 insertions(+), 4 deletions(-) (limited to 'game') diff --git a/game/geoData.h b/game/geoData.h index 92b9b75..b3ef22a 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -94,9 +94,9 @@ public: template [[nodiscard]] auto - get_surface(const HandleT h) + getSurface(const HandleT handle) const { - return property(surface, h); + return property(surface, handle); } void sanityCheck() const; diff --git a/game/terrain.cpp b/game/terrain.cpp index e7508d0..39aa99a 100644 --- a/game/terrain.cpp +++ b/game/terrain.cpp @@ -43,7 +43,7 @@ Terrain::generateMeshes() [this, &vertexIndex, &vertices](const GeoData::VertexHandle v) { std::for_each(geoData->vf_begin(v), geoData->vf_end(v), [&vertexIndex, v, this, &vertices](const GeoData::FaceHandle f) { - const auto surface = geoData->get_surface(f); + const auto surface = geoData->getSurface(f); if (const auto vertexIndexRef = vertexIndex.emplace(std::make_pair(v, surface), 0); vertexIndexRef.second) { vertexIndexRef.first->second = vertices.size(); @@ -57,7 +57,7 @@ Terrain::generateMeshes() geoData->faces_sbegin(), geoData->faces_end(), [this, &vertexIndex, &indices](const GeoData::FaceHandle f) { std::transform(geoData->fv_begin(f), geoData->fv_end(f), std::back_inserter(indices), [&vertexIndex, f, this](const GeoData::VertexHandle v) { - return vertexIndex[std::make_pair(v, geoData->get_surface(f))]; + return vertexIndex[std::make_pair(v, geoData->getSurface(f))]; }); }); meshes.create>(vertices, indices); -- cgit v1.2.3 From 89068c56f3236b65e392cdc8794c5bc1977e5556 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Mon, 30 Dec 2024 17:18:26 +0000 Subject: Pass lots more information during GeoData::walk --- game/geoData.cpp | 45 ++++++++++++++++++++++++--------------------- game/geoData.h | 22 ++++++++++++++++------ 2 files changed, 40 insertions(+), 27 deletions(-) (limited to 'game') diff --git a/game/geoData.cpp b/game/geoData.cpp index fb3cb15..ce88e5b 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -236,12 +236,12 @@ GeoData::intersectRay(const Ray & ray, FaceHandle face) const GeoData::IntersectionResult out; walkUntil(PointFace {ray.start, face}, ray.start.xy() + (ray.direction.xy() * RelativePosition2D(upperExtent.xy() - lowerExtent.xy())), - [&out, &ray, this](FaceHandle face) { + [&out, &ray, this](const auto & step) { BaryPosition bari {}; RelativeDistance dist {}; - const auto t = triangle<3>(face); + const auto t = triangle<3>(step.current); if (ray.intersectTriangle(t.x, t.y, t.z, bari, dist)) { - out.emplace(t * bari, face); + out.emplace(t * bari, step.current); return true; } return false; @@ -250,7 +250,7 @@ GeoData::intersectRay(const Ray & ray, FaceHandle face) const } void -GeoData::walk(const PointFace & from, const GlobalPosition2D to, const std::function & op) const +GeoData::walk(const PointFace & from, const GlobalPosition2D to, Consumer op) const { walkUntil(from, to, [&op](const auto & fh) { op(fh); @@ -259,41 +259,44 @@ GeoData::walk(const PointFace & from, const GlobalPosition2D to, const std::func } void -GeoData::walkUntil(const PointFace & from, const GlobalPosition2D to, const std::function & op) const +GeoData::walkUntil(const PointFace & from, const GlobalPosition2D to, Tester op) const { - auto f = from.face(this); - if (!f.is_valid()) { + WalkStep step { + .current = from.face(this), + }; + if (!step.current.is_valid()) { const auto entryEdge = findEntry(from.point, to); if (!entryEdge.is_valid()) { return; } - f = opposite_face_handle(entryEdge); + step.current = opposite_face_handle(entryEdge); } - FaceHandle previousFace; - while (f.is_valid() && !op(f)) { - for (auto next = cfh_iter(f); next.is_valid(); ++next) { - f = opposite_face_handle(*next); - if (f.is_valid() && f != previousFace) { - const auto e1 = point(to_vertex_handle(*next)); - const auto e2 = point(to_vertex_handle(opposite_halfedge_handle(*next))); + while (step.current.is_valid() && !op(step)) { + step.previous = step.current; + for (const auto next : fh_range(step.current)) { + step.current = opposite_face_handle(next); + if (step.current.is_valid() && step.current != step.previous) { + const auto e1 = point(to_vertex_handle(next)); + const auto e2 = point(to_vertex_handle(opposite_halfedge_handle(next))); if (linesCrossLtR(from.point, to, e1, e2)) { - previousFace = f; + step.exitHalfedge = next; + step.exitPosition = linesIntersectAt(from.point.xy(), to.xy(), e1.xy(), e2.xy()).value(); break; } } - f.reset(); + step.current.reset(); } } } void -GeoData::boundaryWalk(const std::function & op) const +GeoData::boundaryWalk(Consumer op) const { boundaryWalk(op, findBoundaryStart()); } void -GeoData::boundaryWalk(const std::function & op, HalfedgeHandle start) const +GeoData::boundaryWalk(Consumer op, HalfedgeHandle start) const { assert(is_boundary(start)); boundaryWalkUntil( @@ -305,13 +308,13 @@ GeoData::boundaryWalk(const std::function & op, HalfedgeHa } void -GeoData::boundaryWalkUntil(const std::function & op) const +GeoData::boundaryWalkUntil(Tester op) const { boundaryWalkUntil(op, findBoundaryStart()); } void -GeoData::boundaryWalkUntil(const std::function & op, HalfedgeHandle start) const +GeoData::boundaryWalkUntil(Tester op, HalfedgeHandle start) const { assert(is_boundary(start)); if (!op(start)) { diff --git a/game/geoData.h b/game/geoData.h index b3ef22a..68ce9a2 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -64,13 +64,23 @@ public: [[nodiscard]] IntersectionResult intersectRay(const Ray &) const; [[nodiscard]] IntersectionResult intersectRay(const Ray &, FaceHandle start) const; - void walk(const PointFace & from, const GlobalPosition2D to, const std::function & op) const; - void walkUntil(const PointFace & from, const GlobalPosition2D to, const std::function & op) const; + struct WalkStep { + FaceHandle current; + FaceHandle previous {}; + HalfedgeHandle exitHalfedge {}; + GlobalPosition2D exitPosition {}; + }; + + template using Consumer = const std::function &; + template using Tester = const std::function &; + + void walk(const PointFace & from, const GlobalPosition2D to, Consumer op) const; + void walkUntil(const PointFace & from, const GlobalPosition2D to, Tester op) const; - void boundaryWalk(const std::function &) const; - void boundaryWalk(const std::function &, HalfedgeHandle start) const; - void boundaryWalkUntil(const std::function &) const; - void boundaryWalkUntil(const std::function &, HalfedgeHandle start) const; + void boundaryWalk(Consumer) const; + void boundaryWalk(Consumer, HalfedgeHandle start) const; + void boundaryWalkUntil(Tester) const; + void boundaryWalkUntil(Tester, HalfedgeHandle start) const; [[nodiscard]] HalfedgeHandle findEntry(const GlobalPosition2D from, const GlobalPosition2D to) const; -- cgit v1.2.3 From ca3736b3a896557536c0aa4c0cee1f156e118b54 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Wed, 1 Jan 2025 12:53:43 +0000 Subject: Walk terrain along a curve - edge cases exist --- game/geoData.cpp | 44 ++++++++++++++++++++++++++++++++++++++++++++ game/geoData.h | 6 ++++-- 2 files changed, 48 insertions(+), 2 deletions(-) (limited to 'game') diff --git a/game/geoData.cpp b/game/geoData.cpp index ce88e5b..37abc4c 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -289,6 +289,50 @@ GeoData::walkUntil(const PointFace & from, const GlobalPosition2D to, Tester op) const +{ + walkUntil(from, to, centre, [&op](const auto & fh) { + op(fh); + return false; + }); +} + +void +GeoData::walkUntil(const PointFace & from, GlobalPosition2D to, GlobalPosition2D centre, Tester op) const +{ + WalkStep step { + .current = from.face(this), + }; + if (!step.current.is_valid()) { + const auto entryEdge = findEntry(from.point, to); + if (!entryEdge.is_valid()) { + return; + } + step.current = opposite_face_handle(entryEdge); + } + ArcSegment arc {centre, from.point, to}; + while (step.current.is_valid() && !op(step)) { + step.previous = step.current; + for (const auto next : fh_range(step.current)) { + if (opposite_halfedge_handle(next) == step.exitHalfedge) { + continue; + } + step.current = opposite_face_handle(next); + if (step.current.is_valid()) { + const auto e1 = point(to_vertex_handle(next)); + const auto e2 = point(to_vertex_handle(opposite_halfedge_handle(next))); + if (const auto intersect = arc.crossesLineAt(e1, e2)) { + step.exitHalfedge = next; + step.exitPosition = intersect.value(); + break; + } + } + step.current.reset(); + } + } +} + void GeoData::boundaryWalk(Consumer op) const { diff --git a/game/geoData.h b/game/geoData.h index 68ce9a2..e3fc313 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -74,8 +74,10 @@ public: template using Consumer = const std::function &; template using Tester = const std::function &; - void walk(const PointFace & from, const GlobalPosition2D to, Consumer op) const; - void walkUntil(const PointFace & from, const GlobalPosition2D to, Tester op) const; + void walk(const PointFace & from, GlobalPosition2D to, Consumer op) const; + void walkUntil(const PointFace & from, GlobalPosition2D to, Tester op) const; + void walk(const PointFace & from, GlobalPosition2D to, GlobalPosition2D centre, Consumer op) const; + void walkUntil(const PointFace & from, GlobalPosition2D to, GlobalPosition2D centre, Tester op) const; void boundaryWalk(Consumer) const; void boundaryWalk(Consumer, HalfedgeHandle start) const; -- 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') 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') 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 ----- game/geoData.h | 5 ++--- 2 files changed, 2 insertions(+), 8 deletions(-) (limited to 'game') diff --git a/game/geoData.cpp b/game/geoData.cpp index f0e38d0..950fb73 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -7,11 +7,6 @@ #include #include -GeoData::GeoData() -{ - add_property(surface); -} - GeoData GeoData::loadFromAsciiGrid(const std::filesystem::path & input) { diff --git a/game/geoData.h b/game/geoData.h index e3fc313..11ba568 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -10,6 +10,7 @@ #include #include #include +#include struct GeoDataTraits : public OpenMesh::DefaultTraits { FaceAttributes(OpenMesh::Attributes::Status); @@ -22,9 +23,7 @@ struct GeoDataTraits : public OpenMesh::DefaultTraits { class GeoData : public OpenMesh::TriMesh_ArrayKernelT { private: - GeoData(); - - OpenMesh::FPropHandleT surface; + const OpenMesh::Helpers::Property surface {this}; public: static GeoData loadFromAsciiGrid(const std::filesystem::path &); -- cgit v1.2.3 From ee636e6c5da87e52e1d40e97ce95ed0765f9e819 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 5 Jan 2025 11:59:24 +0000 Subject: Return surface face list from setHeights --- game/geoData.cpp | 10 +++++++--- game/geoData.h | 2 +- 2 files changed, 8 insertions(+), 4 deletions(-) (limited to 'game') diff --git a/game/geoData.cpp b/game/geoData.cpp index 950fb73..03bf85f 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -457,11 +457,11 @@ GeoData::triangleContainsTriangle(const Triangle<2> & a, const Triangle<2> & b) return triangleContainsPoint(a.x, b) && triangleContainsPoint(a.y, b) && triangleContainsPoint(a.z, b); } -void +std::vector GeoData::setHeights(const std::span triangleStrip, const SetHeightsOpts & opts) { if (triangleStrip.size() < 3) { - return; + return {}; } const auto stripMinMax = std::ranges::minmax(triangleStrip, {}, &GlobalPosition3D::z); lowerExtent.z = std::min(upperExtent.z, stripMinMax.min.z); @@ -629,9 +629,12 @@ GeoData::setHeights(const std::span triangleStrip, const done.insert(heh); } - auto surfaceStripWalk = [this, &getTriangle, &opts](const auto & surfaceStripWalk, const auto & face) -> void { + std::vector out; + auto surfaceStripWalk + = [this, &getTriangle, &opts, &out](const auto & surfaceStripWalk, const auto & face) -> void { if (!property(surface, face)) { property(surface, face) = opts.surface; + out.emplace_back(face); std::ranges::for_each( ff_range(face), [this, &getTriangle, &surfaceStripWalk](const auto & adjacentFaceHandle) { if (getTriangle(this->triangle<2>(adjacentFaceHandle).centroid())) { @@ -646,6 +649,7 @@ GeoData::setHeights(const std::span triangleStrip, const updateAllVertexNormals(newOrChangedVerts); generation++; + return out; } size_t diff --git a/game/geoData.h b/game/geoData.h index 11ba568..2bdc60d 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -94,7 +94,7 @@ public: RelativeDistance maxSlope = DEFAULT_MAX_SLOPE; }; - void setHeights(std::span triangleStrip, const SetHeightsOpts &); + std::vector setHeights(std::span triangleStrip, const SetHeightsOpts &); [[nodiscard]] size_t getGeneration() const; [[nodiscard]] auto -- cgit v1.2.3 From b5899aae753287805967ec5241bc0063f5c95a4d Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 5 Jan 2025 12:25:16 +0000 Subject: Include arc angle in curved terrain walk --- game/geoData.cpp | 11 +++++------ game/geoData.h | 9 +++++++-- 2 files changed, 12 insertions(+), 8 deletions(-) (limited to 'game') diff --git a/game/geoData.cpp b/game/geoData.cpp index 03bf85f..1a4cd3b 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -285,7 +285,7 @@ GeoData::walkUntil(const PointFace & from, const GlobalPosition2D to, Tester op) const +GeoData::walk(const PointFace & from, GlobalPosition2D to, GlobalPosition2D centre, Consumer op) const { walkUntil(from, to, centre, [&op](const auto & fh) { op(fh); @@ -294,11 +294,9 @@ GeoData::walk(const PointFace & from, GlobalPosition2D to, GlobalPosition2D cent } void -GeoData::walkUntil(const PointFace & from, GlobalPosition2D to, GlobalPosition2D centre, Tester op) const +GeoData::walkUntil(const PointFace & from, GlobalPosition2D to, GlobalPosition2D centre, Tester op) const { - WalkStep step { - .current = from.face(this), - }; + WalkStepCurve step {WalkStep {.current = from.face(this)}}; if (!step.current.is_valid()) { const auto entryEdge = findEntry(from.point, to); if (!entryEdge.is_valid()) { @@ -307,6 +305,7 @@ GeoData::walkUntil(const PointFace & from, GlobalPosition2D to, GlobalPosition2D step.current = opposite_face_handle(entryEdge); } ArcSegment arc {centre, from.point, to}; + step.angle = arc.first; while (step.current.is_valid() && !op(step)) { step.previous = step.current; for (const auto next : fh_range(step.current)) { @@ -317,7 +316,7 @@ GeoData::walkUntil(const PointFace & from, GlobalPosition2D to, GlobalPosition2D if (const auto intersect = arc.crossesLineAt(e1, e2)) { step.exitHalfedge = next; arc.ep0 = step.exitPosition = intersect.value().first; - arc.first = std::nextafter(intersect.value().second, INFINITY); + arc.first = std::nextafter(step.angle = intersect.value().second, INFINITY); break; } } diff --git a/game/geoData.h b/game/geoData.h index 2bdc60d..7e4c28f 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -70,13 +70,18 @@ public: GlobalPosition2D exitPosition {}; }; + struct WalkStepCurve : public WalkStep { + Angle angle {}; + }; + template using Consumer = const std::function &; template using Tester = const std::function &; void walk(const PointFace & from, GlobalPosition2D to, Consumer op) const; void walkUntil(const PointFace & from, GlobalPosition2D to, Tester op) const; - void walk(const PointFace & from, GlobalPosition2D to, GlobalPosition2D centre, Consumer op) const; - void walkUntil(const PointFace & from, GlobalPosition2D to, GlobalPosition2D centre, Tester op) const; + void walk(const PointFace & from, GlobalPosition2D to, GlobalPosition2D centre, Consumer op) const; + void walkUntil( + const PointFace & from, GlobalPosition2D to, GlobalPosition2D centre, Tester op) const; void boundaryWalk(Consumer) const; void boundaryWalk(Consumer, HalfedgeHandle start) const; -- cgit v1.2.3 From 1aba027462a861f2c1155672792dbbe555d7dc0a Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Mon, 13 Jan 2025 01:45:43 +0000 Subject: Add distance helper Works with integer positions, first template param allows forcing to N dimensions --- game/geoData.cpp | 7 ++++--- game/geoData.h | 2 +- game/network/network.cpp | 4 ++-- game/network/network.impl.h | 4 ++-- game/network/rail.cpp | 6 +++--- 5 files changed, 12 insertions(+), 11 deletions(-) (limited to 'game') diff --git a/game/geoData.cpp b/game/geoData.cpp index 1a4cd3b..448ff67 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -405,10 +405,11 @@ GeoData::difference(const HalfedgeHandle heh) const return ::difference(point(to_vertex_handle(heh)), point(from_vertex_handle(heh))); } +template [[nodiscard]] RelativeDistance GeoData::length(const HalfedgeHandle heh) const { - return glm::length(difference(heh)); + return ::distance(point(to_vertex_handle(heh)), point(from_vertex_handle(heh))); } [[nodiscard]] GlobalPosition3D @@ -468,7 +469,7 @@ GeoData::setHeights(const std::span triangleStrip, const const auto vertexDistFrom = [this](GlobalPosition2D p) { return [p, this](const VertexHandle v) { - return std::make_pair(v, glm::length(::difference(p, this->point(v).xy()))); + return std::make_pair(v, ::distance(p, this->point(v).xy())); }; }; const auto vertexDistFromE = [this](GlobalPosition2D p) { @@ -614,7 +615,7 @@ GeoData::setHeights(const std::span triangleStrip, const todoOutHalfEdges(toVertex); } else if (!toTriangle) { // point without the new strip, adjust vertically by limit - const auto maxOffset = static_cast(opts.maxSlope * glm::length(difference(heh).xy())); + const auto maxOffset = static_cast(opts.maxSlope * length<2>(heh)); const auto newHeight = std::clamp(toPoint.z, fromPoint.z - maxOffset, fromPoint.z + maxOffset); if (newHeight != toPoint.z) { toPoint.z = newHeight; diff --git a/game/geoData.h b/game/geoData.h index 7e4c28f..390a443 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -136,7 +136,7 @@ protected: [[nodiscard]] HalfedgeHandle findBoundaryStart() const; [[nodiscard]] RelativePosition3D difference(const HalfedgeHandle) const; - [[nodiscard]] RelativeDistance length(const HalfedgeHandle) const; + template [[nodiscard]] RelativeDistance length(const HalfedgeHandle) const; [[nodiscard]] GlobalPosition3D centre(const HalfedgeHandle) const; void updateAllVertexNormals(); diff --git a/game/network/network.cpp b/game/network/network.cpp index 1666c4d..e67942f 100644 --- a/game/network/network.cpp +++ b/game/network/network.cpp @@ -121,8 +121,8 @@ Network::genCurveDef(const GlobalPosition3D & start, const GlobalPosition3D & en endDir += pi; const auto flatStart {start.xy()}, flatEnd {end.xy()}; auto midheight = [&](auto mid) { - const auto sm = glm::length(RelativePosition2D(flatStart - mid)), - em = glm::length(RelativePosition2D(flatEnd - mid)); + const auto sm = ::distance<2>(flatStart, mid); + const auto em = ::distance<2>(flatEnd, mid); return start.z + GlobalDistance(RelativeDistance(end.z - start.z) * (sm / (sm + em))); }; if (const auto radii = find_arcs_radius(flatStart, startDir, flatEnd, endDir); radii.first < radii.second) { diff --git a/game/network/network.impl.h b/game/network/network.impl.h index ff29088..33b0a86 100644 --- a/game/network/network.impl.h +++ b/game/network/network.impl.h @@ -52,7 +52,7 @@ template Link::CCollection NetworkOf::candidateJoins(GlobalPosition3D start, GlobalPosition3D end) { - if (glm::length(RelativePosition3D(start - end)) < 2000.F) { + if (::distance(start, end) < 2000.F) { return {}; } const auto defs = genCurveDef( @@ -81,7 +81,7 @@ template Link::CCollection NetworkOf::addJoins(GlobalPosition3D start, GlobalPosition3D end) { - if (glm::length(RelativePosition3D(start - end)) < 2000.F) { + if (::distance(start, end) < 2000.F) { return {}; } const auto defs = genCurveDef(start, end, findNodeDirection(nodeAt(start)), findNodeDirection(nodeAt(end))); diff --git a/game/network/rail.cpp b/game/network/rail.cpp index 2820cca..d7de231 100644 --- a/game/network/rail.cpp +++ b/game/network/rail.cpp @@ -40,8 +40,8 @@ RailLinks::addLinksBetween(GlobalPosition3D start, GlobalPosition3D end) const auto flatStart {start.xy()}, flatEnd {end.xy()}; if (node2ins.second == NodeIs::InNetwork) { auto midheight = [&](auto mid) { - const auto sm = glm::length(RelativePosition2D(flatStart - mid)), - em = glm::length(RelativePosition2D(flatEnd - mid)); + const auto sm = ::distance<2>(flatStart, mid); + const auto em = ::distance<2>(flatEnd, mid); return start.z + GlobalDistance(RelativeDistance(end.z - start.z) * (sm / (sm + em))); }; const float dir2 = pi + findNodeDirection(node2ins.first); @@ -117,7 +117,7 @@ RailLinkStraight::RailLinkStraight( RailLinkCurve::RailLinkCurve( NetworkLinkHolder & instances, const Node::Ptr & a, const Node::Ptr & b, GlobalPosition2D c) : - RailLinkCurve(instances, a, b, c || a->pos.z, glm::length(difference(a->pos.xy(), c)), {c, a->pos, b->pos}) + RailLinkCurve(instances, a, b, c || a->pos.z, ::distance<2>(a->pos.xy(), c), {c, a->pos, b->pos}) { } -- 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') 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') 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') 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') 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') diff --git a/game/geoData.cpp b/game/geoData.cpp index 74ededa..4cfcf6d 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -571,6 +571,7 @@ GeoData::setHeights(const std::span triangleStrip, const / distance(startPoint.xy(), endPoint.xy())) < opts.nearNodeTolerance) { start = adjVertex; + point(start).z = positionOnTriangle(adjPoint, triangle).z; return true; } return false; -- cgit v1.2.3 From ca1a83e21d0cdb4b3443252b11789bd8ecff3c86 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 8 Feb 2025 18:11:23 +0000 Subject: Improve logging and fault detection during mesh mutation --- game/geoData.cpp | 34 +++++++++++++++++++++++++++++----- game/geoData.h | 3 ++- 2 files changed, 31 insertions(+), 6 deletions(-) (limited to 'game') diff --git a/game/geoData.cpp b/game/geoData.cpp index 4cfcf6d..816ce03 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -6,6 +6,9 @@ #include #include #include +#ifndef NDEBUG +# include +#endif GeoData GeoData::loadFromAsciiGrid(const std::filesystem::path & input) @@ -554,6 +557,7 @@ GeoData::setHeights(const std::span triangleStrip, const } return std::nullopt; }; + sanityCheck(); // Cut along each edge of triangleStrip AB, AC, BC, BD, CD, CE etc std::map *> boundaryTriangles; @@ -602,6 +606,16 @@ GeoData::setHeights(const std::span triangleStrip, const })) { continue; } +#ifndef NDEBUG + CLOG(start); + CLOG(startPoint); + CLOG(end); + CLOG(endPoint); + for (const auto v : vv_range(start)) { + CLOG(point(v)); + } +#endif + sanityCheck(); throw std::runtime_error( std::format("Could not navigate to ({}, {}, {})", endPoint.x, endPoint.y, endPoint.z)); } @@ -655,6 +669,7 @@ GeoData::setHeights(const std::span triangleStrip, const } done.insert(heh); } + sanityCheck(); std::vector out; auto surfaceStripWalk @@ -686,11 +701,20 @@ GeoData::getGeneration() const } void -GeoData::sanityCheck() const +GeoData::sanityCheck(const std::source_location & loc) const { - if (!std::ranges::all_of(faces(), [this](const auto face) { - return triangle<2>(face).isUp(); - })) { - throw std::logic_error("Upside down faces detected"); + if (const auto upSideDown = std::ranges::count_if(faces(), [this](const auto face) { + if (!triangle<2>(face).isUp()) { +#ifndef NDEBUG + for (const auto v : fv_range(face)) { + CLOG(point(v)); + } +#endif + return true; + } + return false; + }) > 0) { + throw std::logic_error(std::format( + "{} upside down faces detected - checked from {}:{}", upSideDown, loc.function_name(), loc.line())); } } diff --git a/game/geoData.h b/game/geoData.h index 390a443..7c11b07 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -9,6 +9,7 @@ #include #include #include +#include #include #include @@ -115,7 +116,7 @@ public: return property(surface, handle); } - void sanityCheck() const; + void sanityCheck(const std::source_location & = std::source_location::current()) const; protected: template -- cgit v1.2.3 From e608c8644bb9573c2e36a18a3f0404d6a284cfee Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 9 Feb 2025 12:52:37 +0000 Subject: Big of validation on getSurface --- game/geoData.h | 2 ++ 1 file changed, 2 insertions(+) (limited to 'game') diff --git a/game/geoData.h b/game/geoData.h index 7c11b07..03a2b3a 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -110,9 +110,11 @@ public: } template + requires(std::derived_from) [[nodiscard]] auto getSurface(const HandleT handle) const { + assert(handle.is_valid()); return property(surface, handle); } -- cgit v1.2.3 From 62fd9391bbfde47177fb36434d9664e47f4cf656 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 9 Feb 2025 13:02:09 +0000 Subject: Initial commit setting terrain during network construction This is all in the wrong place, it shouldn't be part of the network interface. --- game/network/network.h | 17 +++++++------ game/network/network.impl.h | 61 ++++++++++++++++++++++++++++++++++++++------- game/terrain.cpp | 2 ++ 3 files changed, 63 insertions(+), 17 deletions(-) (limited to 'game') diff --git a/game/network/network.h b/game/network/network.h index f8739b8..291c4ec 100644 --- a/game/network/network.h +++ b/game/network/network.h @@ -14,7 +14,8 @@ #include class SceneShader; -class Surface; +struct Surface; +class GeoData; template class Ray; template using GenDef = std::tuple...>; @@ -42,9 +43,9 @@ public: virtual Link::CCollection candidateStraight(GlobalPosition3D, GlobalPosition3D) = 0; virtual Link::CCollection candidateJoins(GlobalPosition3D, GlobalPosition3D) = 0; virtual Link::CCollection candidateExtend(GlobalPosition3D, GlobalPosition3D) = 0; - virtual Link::CCollection addStraight(GlobalPosition3D, GlobalPosition3D) = 0; - virtual Link::CCollection addJoins(GlobalPosition3D, GlobalPosition3D) = 0; - virtual Link::CCollection addExtend(GlobalPosition3D, GlobalPosition3D) = 0; + virtual Link::CCollection addStraight(const GeoData *, GlobalPosition3D, GlobalPosition3D) = 0; + virtual Link::CCollection addJoins(const GeoData *, GlobalPosition3D, GlobalPosition3D) = 0; + virtual Link::CCollection addExtend(const GeoData *, GlobalPosition3D, GlobalPosition3D) = 0; [[nodiscard]] virtual float findNodeDirection(Node::AnyCPtr) const = 0; @@ -106,12 +107,12 @@ public: Link::CCollection candidateStraight(GlobalPosition3D n1, GlobalPosition3D n2) override; Link::CCollection candidateJoins(GlobalPosition3D, GlobalPosition3D) override; Link::CCollection candidateExtend(GlobalPosition3D, GlobalPosition3D) override; - Link::CCollection addStraight(GlobalPosition3D n1, GlobalPosition3D n2) override; - Link::CCollection addJoins(GlobalPosition3D, GlobalPosition3D) override; - Link::CCollection addExtend(GlobalPosition3D, GlobalPosition3D) override; + Link::CCollection addStraight(const GeoData *, GlobalPosition3D n1, GlobalPosition3D n2) override; + Link::CCollection addJoins(const GeoData *, GlobalPosition3D, GlobalPosition3D) override; + Link::CCollection addExtend(const GeoData *, GlobalPosition3D, GlobalPosition3D) override; [[nodiscard]] float findNodeDirection(Node::AnyCPtr) const override; protected: - Link::CCollection addJoins(); + Link::CCollection addCurve(const GeoData *, const GenCurveDef &); }; diff --git a/game/network/network.impl.h b/game/network/network.impl.h index 33b0a86..c683378 100644 --- a/game/network/network.impl.h +++ b/game/network/network.impl.h @@ -1,4 +1,6 @@ +#include "collections.h" #include "network.h" +#include #include #include @@ -72,28 +74,69 @@ NetworkOf::candidateExtend(GlobalPosition3D start, GlobalPosition3D template Link::CCollection -NetworkOf::addStraight(GlobalPosition3D n1, GlobalPosition3D n2) +NetworkOf::addStraight(const GeoData * geoData, GlobalPosition3D n1, GlobalPosition3D n2) { - return {addLink(n1, n2)}; + Link::CCollection out; + geoData->walk(n1.xy(), n2, [geoData, &out, this, &n1](const GeoData::WalkStep & step) { + if (step.previous.is_valid() && geoData->getSurface(step.current) != geoData->getSurface(step.previous)) { + const auto surfaceEdgePosition = geoData->positionAt(GeoData::PointFace(step.exitPosition, step.current)); + out.emplace_back(addLink(n1, surfaceEdgePosition)); + n1 = surfaceEdgePosition; + } + }); + out.emplace_back(addLink(n1, n2)); + return out; +} + +template +Link::CCollection +NetworkOf::addCurve(const GeoData * geoData, const GenCurveDef & curve) +{ + auto [cstart, cend, centre] = curve; + Link::CCollection out; + std::set> breaks; + const auto radiusMid = ::distance(cstart.xy(), centre); + for (const auto radiusOffset : {-getBaseWidth() / 2.F, 0.F, getBaseWidth() / 2.F}) { + const auto radius = radiusOffset + radiusMid; + const auto start = centre + (difference(cstart.xy(), centre) * radius) / radiusMid; + const auto end = centre + (difference(cend.xy(), centre) * radius) / radiusMid; + geoData->walk(start, end, centre, [geoData, &breaks](const GeoData::WalkStepCurve & step) { + if (step.previous.is_valid() && geoData->getSurface(step.current) != geoData->getSurface(step.previous)) { + breaks.insert(step); + } + }); + } + std::vector points; + points.reserve(breaks.size() + 2); + points.push_back(cstart); + std::ranges::transform( + breaks, std::back_inserter(points), [geoData, centre, radiusMid](const GeoData::WalkStepCurve & step) { + return (centre + (sincos(step.angle) * radiusMid)) + || geoData->positionAt(GeoData::PointFace(step.exitPosition, step.current)).z; + }); + points.push_back(cend); + mergeClose(points, ::distance<3, GlobalDistance>, ::midpoint<3, GlobalDistance>, 2'000.F); + std::ranges::transform(points | std::views::pairwise, std::back_inserter(out), [this, centre](const auto pair) { + const auto [a, b] = pair; + return addLink(a, b, centre); + }); + return out; } template Link::CCollection -NetworkOf::addJoins(GlobalPosition3D start, GlobalPosition3D end) +NetworkOf::addJoins(const GeoData * geoData, GlobalPosition3D start, GlobalPosition3D end) { if (::distance(start, end) < 2000.F) { return {}; } const auto defs = genCurveDef(start, end, findNodeDirection(nodeAt(start)), findNodeDirection(nodeAt(end))); - const auto & [c1s, c1e, c1c] = defs.first; - const auto & [c2s, c2e, c2c] = defs.second; - return {addLink(c1s, c1e, c1c), addLink(c2s, c2e, c2c)}; + return addCurve(geoData, defs.first) + addCurve(geoData, defs.second); } template Link::CCollection -NetworkOf::addExtend(GlobalPosition3D start, GlobalPosition3D end) +NetworkOf::addExtend(const GeoData * geoData, GlobalPosition3D start, GlobalPosition3D end) { - const auto [cstart, cend, centre] = genCurveDef(start, end, findNodeDirection(nodeAt(start))); - return {addLink(cstart, cend, centre)}; + return addCurve(geoData, genCurveDef(start, end, findNodeDirection(nodeAt(start)))); } diff --git a/game/terrain.cpp b/game/terrain.cpp index 39aa99a..c834379 100644 --- a/game/terrain.cpp +++ b/game/terrain.cpp @@ -77,7 +77,9 @@ Terrain::render(const SceneShader & shader) const { shader.landmass.use(); grass->bind(); + // glPolygonMode(GL_FRONT_AND_BACK, GL_LINE); meshes.apply(&Mesh::Draw); + // glPolygonMode(GL_FRONT_AND_BACK, GL_FILL); } void -- 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') 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 +++------------------------------------------------ game/geoData.h | 74 +----------------------- game/geoDataMesh.cpp | 118 +++++++++++++++++++++++++++++++++++++ game/geoDataMesh.h | 83 ++++++++++++++++++++++++++ 4 files changed, 213 insertions(+), 222 deletions(-) create mode 100644 game/geoDataMesh.cpp create mode 100644 game/geoDataMesh.h (limited to 'game') diff --git a/game/geoData.cpp b/game/geoData.cpp index 3b94564..a1d9762 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -110,74 +110,6 @@ GeoData::createFlat(GlobalPosition2D lower, GlobalPosition2D upper, GlobalDistan return mesh; } -OpenMesh::FaceHandle -GeoData::findPoint(GlobalPosition2D p) const -{ - return findPoint(p, *faces_sbegin()); -} - -GeoData::PointFace::PointFace(const GlobalPosition2D p, const GeoData * mesh) : - PointFace {p, mesh, *mesh->faces_sbegin()} -{ -} - -GeoData::PointFace::PointFace(const GlobalPosition2D p, const GeoData * mesh, FaceHandle start) : - PointFace {p, mesh->findPoint(p, start)} -{ -} - -GeoData::FaceHandle -GeoData::PointFace::face(const GeoData * mesh, FaceHandle start) const -{ - if (_face.is_valid() && mesh->triangleContainsPoint(point, _face)) { - return _face; - } - return (_face = mesh->findPoint(point, start)); -} - -GeoData::FaceHandle -GeoData::PointFace::face(const GeoData * mesh) const -{ - return face(mesh, *mesh->faces_sbegin()); -} - -namespace { - constexpr GlobalPosition3D - positionOnTriangle(const GlobalPosition2D point, const GeoData::Triangle<3> & t) - { - const CalcPosition3D a = t[1] - t[0], b = t[2] - t[0]; - const auto n = crossProduct(a, b); - return {point, ((n.x * t[0].x) + (n.y * t[0].y) + (n.z * t[0].z) - (n.x * point.x) - (n.y * point.y)) / n.z}; - } - - static_assert(positionOnTriangle({7, -2}, {{1, 2, 3}, {1, 0, 1}, {-2, 1, 0}}) == GlobalPosition3D {7, -2, 3}); -} - -OpenMesh::FaceHandle -GeoData::findPoint(GlobalPosition2D p, OpenMesh::FaceHandle f) const -{ - while (f.is_valid() && !triangleContainsPoint(p, triangle<2>(f))) { - for (auto next = cfh_iter(f); next.is_valid(); ++next) { - f = opposite_face_handle(*next); - if (f.is_valid()) { - const auto e1 = point(to_vertex_handle(*next)); - const auto e2 = point(to_vertex_handle(opposite_halfedge_handle(*next))); - if (pointLeftOfLine(p, e1, e2)) { - break; - } - } - f.reset(); - } - } - return f; -} - -GlobalPosition3D -GeoData::positionAt(const PointFace & p) const -{ - return positionOnTriangle(p.point, triangle<3>(p.face(this))); -} - [[nodiscard]] GeoData::IntersectionResult GeoData::intersectRay(const Ray & ray) const { @@ -230,11 +162,12 @@ GeoData::walkUntil(const PointFace & from, const GlobalPosition2D to, Tester & t) -{ - return pointLeftOfOrOnLine(p, t[0], t[1]) && pointLeftOfOrOnLine(p, t[1], t[2]) - && pointLeftOfOrOnLine(p, t[2], t[0]); -} - -bool -GeoData::triangleContainsPoint(const GlobalPosition2D p, FaceHandle face) const -{ - return triangleContainsPoint(p, triangle<2>(face)); -} - -GeoData::HalfedgeHandle -GeoData::findBoundaryStart() const -{ - return *std::find_if(halfedges_sbegin(), halfedges_end(), [this](const auto heh) { - return is_boundary(heh); - }); -} - -[[nodiscard]] RelativePosition3D -GeoData::difference(const HalfedgeHandle heh) const -{ - return ::difference(point(to_vertex_handle(heh)), point(from_vertex_handle(heh))); -} - -template -[[nodiscard]] RelativeDistance -GeoData::length(const HalfedgeHandle heh) const -{ - return ::distance(point(to_vertex_handle(heh)), point(from_vertex_handle(heh))); -} - -[[nodiscard]] GlobalPosition3D -GeoData::centre(const HalfedgeHandle heh) const -{ - return point(from_vertex_handle(heh)) + (difference(heh) / 2.F); -} - void GeoData::updateAllVertexNormals() { @@ -400,22 +293,6 @@ GeoData::updateVertexNormal(VertexHandle vertex) set_normal(vertex, glm::normalize(n)); } -bool -GeoData::triangleOverlapsTriangle(const Triangle<2> & a, const Triangle<2> & b) -{ - return triangleContainsPoint(a.x, b) || triangleContainsPoint(a.y, b) || triangleContainsPoint(a.z, b) - || triangleContainsPoint(b.x, a) || triangleContainsPoint(b.y, a) || triangleContainsPoint(b.z, a) - || linesCross(a.x, a.y, b.x, b.y) || linesCross(a.x, a.y, b.y, b.z) || linesCross(a.x, a.y, b.z, b.x) - || linesCross(a.y, a.z, b.x, b.y) || linesCross(a.y, a.z, b.y, b.z) || linesCross(a.y, a.z, b.z, b.x) - || linesCross(a.z, a.x, b.x, b.y) || linesCross(a.z, a.x, b.y, b.z) || linesCross(a.z, a.x, b.z, b.x); -} - -bool -GeoData::triangleContainsTriangle(const Triangle<2> & a, const Triangle<2> & b) -{ - return triangleContainsPoint(a.x, b) && triangleContainsPoint(a.y, b) && triangleContainsPoint(a.z, b); -} - std::vector GeoData::setHeights(const std::span triangleStrip, const SetHeightsOpts & opts) { @@ -489,7 +366,7 @@ GeoData::setHeights(const std::span triangleStrip, const auto getTriangle = [&strip](const auto point) -> const Triangle<3> * { if (const auto t = std::ranges::find_if(strip, [point](const auto & triangle) { - return triangleContainsPoint(point, triangle); + return triangle.containsPoint(point); }); t != strip.end()) { return &*t; @@ -534,7 +411,7 @@ GeoData::setHeights(const std::span triangleStrip, const / distance(startPoint.xy(), endPoint.xy())) < opts.nearNodeTolerance) { start = adjVertex; - point(start).z = positionOnTriangle(adjPoint, triangle).z; + point(start).z = triangle.positionOnPlane(adjPoint).z; return true; } return false; @@ -554,7 +431,7 @@ GeoData::setHeights(const std::span triangleStrip, const flip(*nextEdge); return true; } - start = split_copy(edge_handle(next), positionOnTriangle(*intersection, triangle)); + start = split_copy(edge_handle(next), triangle.positionOnPlane(*intersection)); addVertexForNormalUpdate(start); boundaryTriangles.emplace(start, &triangle); return true; @@ -610,7 +487,7 @@ GeoData::setHeights(const std::span triangleStrip, const } } if (toTriangle) { // point within the new strip, adjust vertically by triangle - toPoint.z = positionOnTriangle(toPoint, *toTriangle).z; + toPoint.z = toTriangle->positionOnPlane(toPoint).z; addVertexForNormalUpdate(toVertex); todoOutHalfEdges(toVertex); } @@ -658,22 +535,3 @@ GeoData::getGeneration() const { return generation; } - -void -GeoData::sanityCheck(const std::source_location & loc) const -{ - if (const auto upSideDown = std::ranges::count_if(faces(), [this](const auto face) { - if (!triangle<2>(face).isUp()) { -#ifndef NDEBUG - for (const auto v : fv_range(face)) { - CLOG(point(v)); - } -#endif - return true; - } - return false; - }) > 0) { - throw std::logic_error(std::format( - "{} upside down faces detected - checked from {}:{}", upSideDown, loc.function_name(), loc.line())); - } -} diff --git a/game/geoData.h b/game/geoData.h index 03a2b3a..d486f22 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -1,28 +1,12 @@ #pragma once #include "collections.h" // IWYU pragma: keep IterableCollection -#include "config/types.h" -#include "ray.h" +#include "geoDataMesh.h" #include "surface.h" -#include "triangle.h" -#include #include #include -#include -#include -#include -#include - -struct GeoDataTraits : public OpenMesh::DefaultTraits { - FaceAttributes(OpenMesh::Attributes::Status); - EdgeAttributes(OpenMesh::Attributes::Status); - VertexAttributes(OpenMesh::Attributes::Normal | OpenMesh::Attributes::Status); - HalfedgeAttributes(OpenMesh::Attributes::Status); - using Point = GlobalPosition3D; - using Normal = Normal3D; -}; -class GeoData : public OpenMesh::TriMesh_ArrayKernelT { +class GeoData : public GeoDataMesh { private: const OpenMesh::Helpers::Property surface {this}; @@ -30,35 +14,6 @@ public: static GeoData loadFromAsciiGrid(const std::filesystem::path &); static GeoData createFlat(GlobalPosition2D lower, GlobalPosition2D upper, GlobalDistance h); - struct PointFace { - // NOLINTNEXTLINE(hicpp-explicit-conversions) - PointFace(const GlobalPosition2D p) : point {p} { } - - PointFace(const GlobalPosition2D p, FaceHandle face) : point {p}, _face {face} { } - - PointFace(const GlobalPosition2D p, const GeoData *); - PointFace(const GlobalPosition2D p, const GeoData *, FaceHandle start); - - const GlobalPosition2D point; - [[nodiscard]] FaceHandle face(const GeoData *) const; - [[nodiscard]] FaceHandle face(const GeoData *, FaceHandle start) const; - - [[nodiscard]] bool - isLocated() const - { - return _face.is_valid(); - } - - private: - mutable FaceHandle _face {}; - }; - - template using Triangle = ::Triangle; - - [[nodiscard]] FaceHandle findPoint(GlobalPosition2D) const; - [[nodiscard]] FaceHandle findPoint(GlobalPosition2D, FaceHandle start) const; - - [[nodiscard]] GlobalPosition3D positionAt(const PointFace &) const; using IntersectionLocation = std::pair; using IntersectionResult = std::optional; [[nodiscard]] IntersectionResult intersectRay(const Ray &) const; @@ -89,7 +44,7 @@ public: void boundaryWalkUntil(Tester) const; void boundaryWalkUntil(Tester, HalfedgeHandle start) const; - [[nodiscard]] HalfedgeHandle findEntry(const GlobalPosition2D from, const GlobalPosition2D to) const; + [[nodiscard]] HalfedgeHandle findEntry(GlobalPosition2D from, GlobalPosition2D to) const; struct SetHeightsOpts { static constexpr auto DEFAULT_NEAR_NODE_TOLERANACE = 500.F; @@ -118,30 +73,7 @@ public: return property(surface, handle); } - void sanityCheck(const std::source_location & = std::source_location::current()) const; - protected: - template - [[nodiscard]] Triangle - triangle(FaceHandle face) const - { - Triangle triangle; - std::ranges::transform(fv_range(face), triangle.begin(), [this](auto vertex) { - return point(vertex); - }); - return triangle; - } - - [[nodiscard]] static bool triangleContainsPoint(const GlobalPosition2D, const Triangle<2> &); - [[nodiscard]] bool triangleContainsPoint(const GlobalPosition2D, FaceHandle) const; - [[nodiscard]] static bool triangleOverlapsTriangle(const Triangle<2> &, const Triangle<2> &); - [[nodiscard]] static bool triangleContainsTriangle(const Triangle<2> &, const Triangle<2> &); - [[nodiscard]] HalfedgeHandle findBoundaryStart() const; - [[nodiscard]] RelativePosition3D difference(const HalfedgeHandle) const; - - template [[nodiscard]] RelativeDistance length(const HalfedgeHandle) const; - [[nodiscard]] GlobalPosition3D centre(const HalfedgeHandle) const; - void updateAllVertexNormals(); template void updateAllVertexNormals(const R &); void updateVertexNormal(VertexHandle); diff --git a/game/geoDataMesh.cpp b/game/geoDataMesh.cpp new file mode 100644 index 0000000..aaa8c9c --- /dev/null +++ b/game/geoDataMesh.cpp @@ -0,0 +1,118 @@ +#include "geoDataMesh.h" +#include +#ifndef NDEBUG +# include +#endif + +OpenMesh::FaceHandle +GeoDataMesh::findPoint(GlobalPosition2D coord) const +{ + return findPoint(coord, *faces_sbegin()); +} + +GeoDataMesh::PointFace::PointFace(const GlobalPosition2D coord, const GeoDataMesh * mesh) : + PointFace {coord, mesh, *mesh->faces_sbegin()} +{ +} + +GeoDataMesh::PointFace::PointFace(const GlobalPosition2D coord, const GeoDataMesh * mesh, FaceHandle start) : + PointFace {coord, mesh->findPoint(coord, start)} +{ +} + +OpenMesh::FaceHandle +GeoDataMesh::PointFace::face(const GeoDataMesh * mesh, FaceHandle start) const +{ + if (faceCache.is_valid() && mesh->faceContainsPoint(point, faceCache)) { + return faceCache; + } + return (faceCache = mesh->findPoint(point, start)); +} + +OpenMesh::FaceHandle +GeoDataMesh::PointFace::face(const GeoDataMesh * mesh) const +{ + return face(mesh, *mesh->faces_sbegin()); +} + +GeoDataMesh::HalfEdgeVertices +GeoDataMesh::toVertexHandles(HalfedgeHandle halfEdge) const +{ + return {from_vertex_handle(halfEdge), to_vertex_handle(halfEdge)}; +} + +GeoDataMesh::HalfEdgePoints +GeoDataMesh::points(HalfEdgeVertices vertices) const +{ + return {point(vertices.first), point(vertices.second)}; +} + +OpenMesh::FaceHandle +GeoDataMesh::findPoint(const GlobalPosition2D coord, OpenMesh::FaceHandle face) const +{ + while (face.is_valid() && !triangle<2>(face).containsPoint(coord)) { + for (auto next = cfh_iter(face); next.is_valid(); ++next) { + face = opposite_face_handle(*next); + if (face.is_valid()) { + const auto nextPoints = points(toVertexHandles(*next)); + if (pointLeftOfLine(coord, nextPoints.second, nextPoints.first)) { + break; + } + } + face.reset(); + } + } + return face; +} + +GlobalPosition3D +GeoDataMesh::positionAt(const PointFace & coord) const +{ + return triangle<3>(coord.face(this)).positionOnPlane(coord.point); +} + +bool +GeoDataMesh::faceContainsPoint(const GlobalPosition2D coord, FaceHandle face) const +{ + return triangle<2>(face).containsPoint(coord); +} + +OpenMesh::HalfedgeHandle +GeoDataMesh::findBoundaryStart() const +{ + return *std::find_if(halfedges_sbegin(), halfedges_end(), [this](const auto heh) { + return is_boundary(heh); + }); +} + +[[nodiscard]] RelativePosition3D +GeoDataMesh::difference(const HalfedgeHandle heh) const +{ + return ::difference(point(to_vertex_handle(heh)), point(from_vertex_handle(heh))); +} + +[[nodiscard]] GlobalPosition3D +GeoDataMesh::centre(const HalfedgeHandle heh) const +{ + const auto hehPoints = points(toVertexHandles(heh)); + return midpoint(hehPoints.first, hehPoints.second); +} + +void +GeoDataMesh::sanityCheck(const std::source_location & loc) const +{ + if (const auto upSideDown = std::ranges::count_if(faces(), [this](const auto face) { + if (!triangle<2>(face).isUp()) { +#ifndef NDEBUG + for (const auto vertex : fv_range(face)) { + CLOG(point(vertex)); + } +#endif + return true; + } + return false; + }) > 0) { + throw std::logic_error(std::format( + "{} upside down faces detected - checked from {}:{}", upSideDown, loc.function_name(), loc.line())); + } +} diff --git a/game/geoDataMesh.h b/game/geoDataMesh.h new file mode 100644 index 0000000..00db67c --- /dev/null +++ b/game/geoDataMesh.h @@ -0,0 +1,83 @@ +#pragma once + +#include "config/types.h" +#include "ray.h" +#include "triangle.h" +#include +#include +#include +#include + +struct GeoDataTraits : public OpenMesh::DefaultTraits { + FaceAttributes(OpenMesh::Attributes::Status); + EdgeAttributes(OpenMesh::Attributes::Status); + VertexAttributes(OpenMesh::Attributes::Normal | OpenMesh::Attributes::Status); + HalfedgeAttributes(OpenMesh::Attributes::Status); + using Point = GlobalPosition3D; + using Normal = Normal3D; +}; + +class GeoDataMesh : public OpenMesh::TriMesh_ArrayKernelT { +public: + struct PointFace { + // NOLINTNEXTLINE(hicpp-explicit-conversions) + PointFace(GlobalPosition2D coord) : point {coord} { } + + PointFace(GlobalPosition2D coord, FaceHandle face) : point {coord}, faceCache {face} { } + + PointFace(GlobalPosition2D coord, const GeoDataMesh *); + PointFace(GlobalPosition2D coord, GeoDataMesh const *, FaceHandle start); + + const GlobalPosition2D point; + [[nodiscard]] FaceHandle face(const GeoDataMesh *) const; + [[nodiscard]] FaceHandle face(const GeoDataMesh *, FaceHandle start) const; + + [[nodiscard]] bool + isLocated() const + { + return faceCache.is_valid(); + } + + private: + mutable FaceHandle faceCache; + }; + + template using Triangle = ::Triangle; + + [[nodiscard]] FaceHandle findPoint(GlobalPosition2D) const; + [[nodiscard]] FaceHandle findPoint(GlobalPosition2D, FaceHandle) const; + + [[nodiscard]] GlobalPosition3D positionAt(const PointFace &) const; + +protected: + void sanityCheck(const std::source_location & = std::source_location::current()) const; + + [[nodiscard]] bool faceContainsPoint(GlobalPosition2D, FaceHandle) const; + [[nodiscard]] HalfedgeHandle findBoundaryStart() const; + [[nodiscard]] RelativePosition3D difference(HalfedgeHandle) const; + using HalfEdgeVertices = std::pair; + [[nodiscard]] HalfEdgeVertices toVertexHandles(HalfedgeHandle) const; + using HalfEdgePoints = std::pair; + [[nodiscard]] HalfEdgePoints points(HalfEdgeVertices) const; + + template + [[nodiscard]] RelativeDistance + length(HalfedgeHandle heh) const + { + return ::distance( + point(to_vertex_handle(heh)), point(from_vertex_handle(heh))); + } + + [[nodiscard]] GlobalPosition3D centre(HalfedgeHandle) const; + + template + [[nodiscard]] Triangle + triangle(FaceHandle face) const + { + Triangle triangle; + std::ranges::transform(fv_range(face), triangle.begin(), [this](auto vertex) { + return point(vertex); + }); + return triangle; + } +}; -- cgit v1.2.3 From 42e16ad8ad853c6e97d7eb6718ee0f78b868be30 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 9 Feb 2025 20:14:51 +0000 Subject: Combine GeoData and Terrain class hierarchies --- game/gamestate.h | 4 ++-- game/terrain.cpp | 54 +++++++++++++++++++++--------------------------------- game/terrain.h | 13 +++++++------ 3 files changed, 30 insertions(+), 41 deletions(-) (limited to 'game') diff --git a/game/gamestate.h b/game/gamestate.h index 892aa69..189417d 100644 --- a/game/gamestate.h +++ b/game/gamestate.h @@ -6,7 +6,7 @@ #include class WorldObject; -class GeoData; +class Terrain; class Environment; class GameState { @@ -17,7 +17,7 @@ public: NO_COPY(GameState); Collection world; - std::shared_ptr geoData; + std::shared_ptr terrain; std::shared_ptr environment; AssetFactory::Assets assets; }; diff --git a/game/terrain.cpp b/game/terrain.cpp index c834379..786b9b0 100644 --- a/game/terrain.cpp +++ b/game/terrain.cpp @@ -1,6 +1,5 @@ #include "terrain.h" #include "game/geoData.h" -#include "gfx/models/texture.h" #include #include #include @@ -15,12 +14,7 @@ #include #include -static constexpr RGB openSurface {-1}; - -Terrain::Terrain(std::shared_ptr tm) : geoData {std::move(tm)}, grass {std::make_shared("grass.png")} -{ - generateMeshes(); -} +static constexpr RGB OPEN_SURFACE {-1}; template<> VertexArrayObject & @@ -35,38 +29,34 @@ Terrain::generateMeshes() { meshes.removeAll(); std::vector indices; - indices.reserve(geoData->n_faces() * 3); + indices.reserve(n_faces() * 3); std::vector vertices; - vertices.reserve(geoData->n_vertices()); - std::map, size_t> vertexIndex; - std::for_each(geoData->vertices_sbegin(), geoData->vertices_end(), - [this, &vertexIndex, &vertices](const GeoData::VertexHandle v) { - std::for_each(geoData->vf_begin(v), geoData->vf_end(v), - [&vertexIndex, v, this, &vertices](const GeoData::FaceHandle f) { - const auto surface = geoData->getSurface(f); - if (const auto vertexIndexRef = vertexIndex.emplace(std::make_pair(v, surface), 0); - vertexIndexRef.second) { - vertexIndexRef.first->second = vertices.size(); + vertices.reserve(n_vertices()); + std::map, size_t> vertexIndex; + std::ranges::for_each(this->vertices(), [this, &vertexIndex, &vertices](const auto vertex) { + std::ranges::for_each(vf_range(vertex), [&vertexIndex, vertex, this, &vertices](const auto face) { + const auto * const surface = getSurface(face); + if (const auto vertexIndexRef = vertexIndex.emplace(std::make_pair(vertex, surface), 0); + vertexIndexRef.second) { + vertexIndexRef.first->second = vertices.size(); - vertices.emplace_back(geoData->point(v), geoData->normal(v), - surface ? surface->colorBias : openSurface); - } - }); - }); - std::for_each( - geoData->faces_sbegin(), geoData->faces_end(), [this, &vertexIndex, &indices](const GeoData::FaceHandle f) { - std::transform(geoData->fv_begin(f), geoData->fv_end(f), std::back_inserter(indices), - [&vertexIndex, f, this](const GeoData::VertexHandle v) { - return vertexIndex[std::make_pair(v, geoData->getSurface(f))]; - }); - }); + vertices.emplace_back(point(vertex), normal(vertex), surface ? surface->colorBias : OPEN_SURFACE); + } + }); + }); + std::ranges::for_each(faces(), [this, &vertexIndex, &indices](const auto face) { + std::ranges::transform( + fv_range(face), std::back_inserter(indices), [&vertexIndex, face, this](const auto vertex) { + return vertexIndex[std::make_pair(vertex, getSurface(face))]; + }); + }); meshes.create>(vertices, indices); } void Terrain::tick(TickDuration) { - if (const auto newGeneration = geoData->getGeneration(); newGeneration != geoGeneration) { + if (const auto newGeneration = getGeneration(); newGeneration != geoGeneration) { generateMeshes(); geoGeneration = newGeneration; } @@ -77,9 +67,7 @@ Terrain::render(const SceneShader & shader) const { shader.landmass.use(); grass->bind(); - // glPolygonMode(GL_FRONT_AND_BACK, GL_LINE); meshes.apply(&Mesh::Draw); - // glPolygonMode(GL_FRONT_AND_BACK, GL_FILL); } void diff --git a/game/terrain.h b/game/terrain.h index c9d09fe..7464bdd 100644 --- a/game/terrain.h +++ b/game/terrain.h @@ -4,17 +4,19 @@ #include "collection.h" #include "config/types.h" #include "game/worldobject.h" +#include "geoData.h" #include "gfx/models/mesh.h" #include "gfx/models/texture.h" #include "gfx/renderable.h" -#include class SceneShader; -class GeoData; -class Terrain : public WorldObject, public Renderable { +class Terrain : public GeoData, public WorldObject, public Renderable { public: - explicit Terrain(std::shared_ptr); + template explicit Terrain(P &&... params) : GeoData {std::forward

(params)...} + { + generateMeshes(); + } void render(const SceneShader & shader) const override; void shadows(const ShadowMapper &) const override; @@ -30,8 +32,7 @@ public: private: void generateMeshes(); - std::shared_ptr geoData; Collection, false> meshes; - Texture::Ptr grass; + Texture::Ptr grass = std::make_shared("grass.png"); size_t geoGeneration {}; }; -- cgit v1.2.3 From c9d9aedb9f29725e1106ce1f7ddbc1707400d105 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Mon, 10 Feb 2025 20:07:46 +0000 Subject: Replace mesh generation counter with afterChange event --- game/geoData.cpp | 9 +++------ game/geoData.h | 3 +-- game/terrain.cpp | 8 +++++--- game/terrain.h | 1 + 4 files changed, 10 insertions(+), 11 deletions(-) (limited to 'game') diff --git a/game/geoData.cpp b/game/geoData.cpp index a1d9762..e035a3c 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -64,7 +64,6 @@ GeoData::loadFromAsciiGrid(const std::filesystem::path & input) }); } } - mesh.generation++; mesh.updateAllVertexNormals(); return mesh; @@ -105,7 +104,6 @@ GeoData::createFlat(GlobalPosition2D lower, GlobalPosition2D upper, GlobalDistan } mesh.updateAllVertexNormals(); - mesh.generation++; return mesh; } @@ -526,12 +524,11 @@ GeoData::setHeights(const std::span triangleStrip, const } updateAllVertexNormals(newOrChangedVerts); - generation++; + afterChange(); return out; } -size_t -GeoData::getGeneration() const +void +GeoData::afterChange() { - return generation; } diff --git a/game/geoData.h b/game/geoData.h index d486f22..3d5ea5d 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -56,7 +56,6 @@ public: }; std::vector setHeights(std::span triangleStrip, const SetHeightsOpts &); - [[nodiscard]] size_t getGeneration() const; [[nodiscard]] auto getExtents() const @@ -77,8 +76,8 @@ protected: void updateAllVertexNormals(); template void updateAllVertexNormals(const R &); void updateVertexNormal(VertexHandle); + virtual void afterChange(); private: GlobalPosition3D lowerExtent {}, upperExtent {}; - size_t generation {}; }; diff --git a/game/terrain.cpp b/game/terrain.cpp index 786b9b0..01af163 100644 --- a/game/terrain.cpp +++ b/game/terrain.cpp @@ -56,10 +56,12 @@ Terrain::generateMeshes() void Terrain::tick(TickDuration) { - if (const auto newGeneration = getGeneration(); newGeneration != geoGeneration) { +} + +void +Terrain::afterChange() +{ generateMeshes(); - geoGeneration = newGeneration; - } } void diff --git a/game/terrain.h b/game/terrain.h index 7464bdd..f0f9621 100644 --- a/game/terrain.h +++ b/game/terrain.h @@ -30,6 +30,7 @@ public: }; private: + void afterChange() override; void generateMeshes(); Collection, false> meshes; -- cgit v1.2.3 From 4b175adffdf68f35589ed48c82baa15723a9af0a Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Thu, 13 Feb 2025 19:57:41 +0000 Subject: Move basic setHeights lambdas into proper helper functions --- game/geoData.cpp | 98 +++++++++++++++++++--------------------------------- game/geoData.h | 1 + game/geoDataMesh.cpp | 24 +++++++++++++ game/geoDataMesh.h | 31 ++++++++++++++++- 4 files changed, 90 insertions(+), 64 deletions(-) (limited to 'game') diff --git a/game/geoData.cpp b/game/geoData.cpp index e035a3c..dd7a3f8 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -291,6 +291,37 @@ GeoData::updateVertexNormal(VertexHandle vertex) set_normal(vertex, glm::normalize(n)); } +OpenMesh::VertexHandle +GeoData::setPoint(GlobalPosition3D tsPoint, const SetHeightsOpts & opts) +{ + const auto face = findPoint(tsPoint); + const auto distFromTsPoint = vertexDistanceFunction<2>(tsPoint); + // Check vertices + if (const auto nearest + = std::ranges::min(std::views::iota(fv_begin(face), fv_end(face)) | std::views::transform(distFromTsPoint), + {}, &std::pair::second); + nearest.second < opts.nearNodeTolerance) { + point(nearest.first).z = tsPoint.z; + return nearest.first; + } + // Check edges + if (const auto nearest + = std::ranges::min(std::views::iota(fh_begin(face), fh_end(face)) | std::views::transform(distFromTsPoint), + {}, &std::pair::second); + nearest.second < opts.nearNodeTolerance) { + const auto from = point(from_vertex_handle(nearest.first)).xy(); + const auto to = point(to_vertex_handle(nearest.first)).xy(); + const auto v = vector_normal(from - to); + const auto inter = linesIntersectAt(from, to, tsPoint.xy(), tsPoint.xy() + v); + if (!inter) { + throw std::runtime_error("Perpendicular lines do not cross"); + } + return split_copy(edge_handle(nearest.first), *inter || tsPoint.z); + } + // Nothing close, split face + return split_copy(face, tsPoint); +}; + std::vector GeoData::setHeights(const std::span triangleStrip, const SetHeightsOpts & opts) { @@ -301,57 +332,18 @@ GeoData::setHeights(const std::span triangleStrip, const lowerExtent.z = std::min(upperExtent.z, stripMinMax.min.z); upperExtent.z = std::max(upperExtent.z, stripMinMax.max.z); - const auto vertexDistFrom = [this](GlobalPosition2D p) { - return [p, this](const VertexHandle v) { - return std::make_pair(v, ::distance(p, this->point(v).xy())); - }; - }; - const auto vertexDistFromE = [this](GlobalPosition2D p) { - return [p, this](const HalfedgeHandle e) { - const auto fromPoint = point(from_vertex_handle(e)).xy(); - const auto toPoint = point(to_vertex_handle(e)).xy(); - return std::make_pair(e, Triangle<2> {fromPoint, toPoint, p}.height()); - }; - }; - std::set newOrChangedVerts; auto addVertexForNormalUpdate = [this, &newOrChangedVerts](const VertexHandle vertex) { newOrChangedVerts.emplace(vertex); std::ranges::copy(vv_range(vertex), std::inserter(newOrChangedVerts, newOrChangedVerts.end())); }; - auto newVertexOnFace = [this, &vertexDistFrom, &opts, &vertexDistFromE](GlobalPosition3D tsPoint) { - const auto face = findPoint(tsPoint); - // Check vertices - if (const auto nearest = std::ranges::min( - std::views::iota(fv_begin(face), fv_end(face)) | std::views::transform(vertexDistFrom(tsPoint)), {}, - &std::pair::second); - nearest.second < opts.nearNodeTolerance) { - point(nearest.first).z = tsPoint.z; - return nearest.first; - } - // Check edges - if (const auto nearest = std::ranges::min( - std::views::iota(fh_begin(face), fh_end(face)) | std::views::transform(vertexDistFromE(tsPoint)), - {}, &std::pair::second); - nearest.second < opts.nearNodeTolerance) { - const auto from = point(from_vertex_handle(nearest.first)).xy(); - const auto to = point(to_vertex_handle(nearest.first)).xy(); - const auto v = vector_normal(from - to); - const auto inter = linesIntersectAt(from, to, tsPoint.xy(), tsPoint.xy() + v); - if (!inter) { - throw std::runtime_error("Perpendicular lines do not cross"); - } - return split_copy(edge_handle(nearest.first), *inter || tsPoint.z); - } - // Nothing close, split face - return split_copy(face, tsPoint); - }; - // New vertices for each vertex in triangleStrip std::vector newVerts; newVerts.reserve(triangleStrip.size()); - std::transform(triangleStrip.begin(), triangleStrip.end(), std::back_inserter(newVerts), newVertexOnFace); + std::ranges::transform(triangleStrip, std::back_inserter(newVerts), [this, &opts](auto v) { + return setPoint(v, opts); + }); std::ranges::for_each(newVerts, addVertexForNormalUpdate); // Create temporary triangles from triangleStrip @@ -371,31 +363,11 @@ GeoData::setHeights(const std::span triangleStrip, const } return nullptr; }; - const auto canFlip = [this](const HalfedgeHandle edge) { - const auto opposite = opposite_halfedge_handle(edge); - const auto pointA = point(to_vertex_handle(edge)); - const auto pointB = point(to_vertex_handle(opposite)); - const auto pointC = point(to_vertex_handle(next_halfedge_handle(edge))); - const auto pointD = point(to_vertex_handle(next_halfedge_handle(opposite))); - - return Triangle<2> {pointC, pointB, pointD}.isUp() && Triangle<2> {pointA, pointC, pointD}.isUp(); - }; - const auto shouldFlip = [this, &canFlip](const HalfedgeHandle next, - const GlobalPosition2D startPoint) -> std::optional { - if (const auto nextEdge = edge_handle(next); is_flip_ok(nextEdge) && canFlip(next)) { - const auto opposite_point - = point(to_vertex_handle(next_halfedge_handle(opposite_halfedge_handle(next)))).xy(); - if (distance<2>(startPoint, opposite_point) < length<2>(next)) { - return nextEdge; - } - } - return std::nullopt; - }; sanityCheck(); // Cut along each edge of triangleStrip AB, AC, BC, BD, CD, CE etc std::map *> boundaryTriangles; - auto doBoundaryPart = [this, &boundaryTriangles, &opts, &addVertexForNormalUpdate, &shouldFlip]( + auto doBoundaryPart = [this, &boundaryTriangles, &opts, &addVertexForNormalUpdate]( VertexHandle start, VertexHandle end, const Triangle<3> & triangle) { boundaryTriangles.emplace(start, &triangle); const auto endPoint = point(end); diff --git a/game/geoData.h b/game/geoData.h index 3d5ea5d..1a93d03 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -73,6 +73,7 @@ public: } protected: + [[nodiscard]] VertexHandle setPoint(GlobalPosition3D point, const SetHeightsOpts &); void updateAllVertexNormals(); template void updateAllVertexNormals(const R &); void updateVertexNormal(VertexHandle); diff --git a/game/geoDataMesh.cpp b/game/geoDataMesh.cpp index aaa8c9c..687a025 100644 --- a/game/geoDataMesh.cpp +++ b/game/geoDataMesh.cpp @@ -116,3 +116,27 @@ GeoDataMesh::sanityCheck(const std::source_location & loc) const "{} upside down faces detected - checked from {}:{}", upSideDown, loc.function_name(), loc.line())); } } + +bool +GeoDataMesh::canFlip(const HalfedgeHandle edge) const +{ + const auto opposite = opposite_halfedge_handle(edge); + const auto pointA = point(to_vertex_handle(edge)); + const auto pointB = point(to_vertex_handle(opposite)); + const auto pointC = point(to_vertex_handle(next_halfedge_handle(edge))); + const auto pointD = point(to_vertex_handle(next_halfedge_handle(opposite))); + + return Triangle<2> {pointC, pointB, pointD}.isUp() && Triangle<2> {pointA, pointC, pointD}.isUp(); +}; + +std::optional +GeoDataMesh::shouldFlip(const HalfedgeHandle next, const GlobalPosition2D startPoint) const +{ + if (const auto nextEdge = edge_handle(next); is_flip_ok(nextEdge) && canFlip(next)) { + const auto oppositePoint = point(to_vertex_handle(next_halfedge_handle(opposite_halfedge_handle(next)))).xy(); + if (distance<2>(startPoint, oppositePoint) < length<2>(next)) { + return nextEdge; + } + } + return std::nullopt; +}; diff --git a/game/geoDataMesh.h b/game/geoDataMesh.h index 00db67c..5d0bade 100644 --- a/game/geoDataMesh.h +++ b/game/geoDataMesh.h @@ -1,7 +1,6 @@ #pragma once #include "config/types.h" -#include "ray.h" #include "triangle.h" #include #include @@ -60,6 +59,36 @@ protected: using HalfEdgePoints = std::pair; [[nodiscard]] HalfEdgePoints points(HalfEdgeVertices) const; + template + [[nodiscard]] auto + vertexDistanceFunction(GlobalPosition point) const + { + struct DistanceCalculator { + [[nodiscard]] std::pair + operator()(VertexHandle compVertex) const + { + return std::make_pair( + compVertex, ::distance(point, mesh->point(compVertex))); + } + + [[nodiscard]] + std::pair + operator()(const HalfedgeHandle compHalfedge) const + { + const auto edgePoints = mesh->points(mesh->toVertexHandles(compHalfedge)); + return std::make_pair(compHalfedge, Triangle<2> {edgePoints.second, edgePoints.first, point}.height()); + }; + + const GeoDataMesh * mesh; + GlobalPosition point; + }; + + return DistanceCalculator {this, point}; + } + + [[nodiscard]] bool canFlip(HalfedgeHandle edge) const; + [[nodiscard]] std::optional shouldFlip(HalfedgeHandle next, GlobalPosition2D startPoint) const; + template [[nodiscard]] RelativeDistance length(HalfedgeHandle heh) const -- cgit v1.2.3 From fe58d2e6e20c2fc21b3bfd37f9f78736bb28a6ea Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Fri, 14 Feb 2025 02:36:45 +0000 Subject: Use new helpers to simplify close entity search in GeoData::setPoint --- game/geoData.cpp | 11 ++++------- 1 file changed, 4 insertions(+), 7 deletions(-) (limited to 'game') 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') 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') 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 ++++++++++++++++++++++++++++++++----------------------- game/geoData.h | 2 +- 2 files changed, 205 insertions(+), 151 deletions(-) (limited to 'game') diff --git a/game/geoData.cpp b/game/geoData.cpp index fa96a33..6052cd1 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -293,19 +293,19 @@ GeoData::updateVertexNormal(VertexHandle vertex) } OpenMesh::VertexHandle -GeoData::setPoint(GlobalPosition3D tsPoint, const SetHeightsOpts & opts) +GeoData::setPoint(GlobalPosition3D tsPoint, const RelativeDistance nearNodeTolerance) { const auto face = findPoint(tsPoint); const auto distFromTsPoint = vertexDistanceFunction<2>(tsPoint); // Check vertices if (const auto nearest = std::ranges::min(fv_range(face) | std::views::transform(distFromTsPoint), {}, GetSecond); - nearest.second < opts.nearNodeTolerance) { + nearest.second < nearNodeTolerance) { point(nearest.first).z = tsPoint.z; return nearest.first; } // Check edges if (const auto nearest = std::ranges::min(fh_range(face) | std::views::transform(distFromTsPoint), {}, GetSecond); - nearest.second < opts.nearNodeTolerance) { + nearest.second < nearNodeTolerance) { const auto from = point(from_vertex_handle(nearest.first)).xy(); const auto to = point(to_vertex_handle(nearest.first)).xy(); const auto v = vector_normal(from - to); @@ -329,170 +329,224 @@ GeoData::setHeights(const std::span triangleStrip, const lowerExtent.z = std::min(upperExtent.z, stripMinMax.min.z); upperExtent.z = std::max(upperExtent.z, stripMinMax.max.z); - std::set newOrChangedVerts; - auto addVertexForNormalUpdate = [this, &newOrChangedVerts](const VertexHandle vertex) { - newOrChangedVerts.emplace(vertex); - std::ranges::copy(vv_range(vertex), std::inserter(newOrChangedVerts, newOrChangedVerts.end())); - }; + class SetHeights { + public: + SetHeights(GeoData * geoData, const std::span triangleStrip) : + geoData(geoData), triangleStrip {triangleStrip}, + strip {materializeRange(triangleStrip | triangleTriples | std::views::transform([](const auto & newVert) { + return std::make_from_tuple>(newVert); + }))} + { + } - // New vertices for each vertex in triangleStrip - std::vector newVerts; - newVerts.reserve(triangleStrip.size()); - std::ranges::transform(triangleStrip, std::back_inserter(newVerts), [this, &opts](auto v) { - return setPoint(v, opts); - }); - std::ranges::for_each(newVerts, addVertexForNormalUpdate); - - // Create temporary triangles from triangleStrip - const auto strip - = materializeRange(triangleStrip | triangleTriples | std::views::transform([](const auto & newVert) { - return std::make_from_tuple>(newVert); - })); - auto getTriangle = [&strip](const auto point) -> const Triangle<3> * { - if (const auto t = std::ranges::find_if(strip, - [point](const auto & triangle) { - return triangle.containsPoint(point); - }); - t != strip.end()) { - return &*t; + std::vector + createVerticesForStrip(RelativeDistance nearNodeTolerance) + { + // New vertices for each vertex in triangleStrip + const auto newVerts + = materializeRange(triangleStrip | std::views::transform([this, nearNodeTolerance](auto v) { + return geoData->setPoint(v, nearNodeTolerance); + })); + std::ranges::for_each(newVerts, [this](auto vertex) { + addVertexForNormalUpdate(vertex); + }); + geoData->sanityCheck(); + return newVerts; } - return nullptr; - }; - sanityCheck(); - - // Cut along each edge of triangleStrip AB, AC, BC, BD, CD, CE etc - std::map *> boundaryTriangles; - auto doBoundaryPart = [this, &boundaryTriangles, &opts, &addVertexForNormalUpdate]( - VertexHandle start, VertexHandle end, const Triangle<3> & triangle) { - boundaryTriangles.emplace(start, &triangle); - const auto endPoint = point(end); - while (!std::ranges::contains(vv_range(start), end)) { - const auto startPoint = point(start); - const auto distanceToEndPoint = distance(startPoint.xy(), endPoint.xy()); - if (std::ranges::any_of(vv_range(start), [&](const auto & adjVertex) { - const auto adjPoint = point(adjVertex); - if (distance(adjPoint.xy(), endPoint.xy()) < distanceToEndPoint - && (Triangle<2> {startPoint, endPoint, adjPoint}.area() - / distance(startPoint.xy(), endPoint.xy())) - < opts.nearNodeTolerance) { - start = adjVertex; - point(start).z = triangle.positionOnPlane(adjPoint).z; - return true; - } - return false; - })) { - continue; + + void + addVertexForNormalUpdate(const VertexHandle vertex) + { + newOrChangedVerts.emplace(vertex); + std::ranges::copy(geoData->vv_range(vertex), std::inserter(newOrChangedVerts, newOrChangedVerts.end())); + } + + const Triangle<3> * + getTriangle(const GlobalPosition2D point) const + { + if (const auto t = std::ranges::find_if(strip, + [point](const auto & triangle) { + return triangle.containsPoint(point); + }); + t != strip.end()) { + return &*t; } - if (std::ranges::any_of(voh_range(start), [&](const auto & outHalf) { - const auto next = next_halfedge_handle(outHalf); - const auto nexts = std::array {from_vertex_handle(next), to_vertex_handle(next)}; - const auto nextPoints = nexts | std::views::transform([this](const auto v) { - return std::make_pair(v, this->point(v)); - }); - if (linesCross(startPoint, endPoint, nextPoints.front().second, nextPoints.back().second)) { - if (const auto intersection = linesIntersectAt(startPoint.xy(), endPoint.xy(), - nextPoints.front().second.xy(), nextPoints.back().second.xy())) { - if (const auto nextEdge = shouldFlip(next, startPoint)) { - flip(*nextEdge); + return nullptr; + } + + void + doBoundaryPart(VertexHandle start, VertexHandle end, const Triangle<3> & triangle, + const RelativeDistance nearNodeTolerance) + { + boundaryTriangles.emplace(start, &triangle); + const auto endPoint = geoData->point(end); + while (!std::ranges::contains(geoData->vv_range(start), end)) { + const auto startPoint = geoData->point(start); + const auto distanceToEndPoint = distance(startPoint.xy(), endPoint.xy()); + if (std::ranges::any_of(geoData->vv_range(start), [&](const auto & adjVertex) { + const auto adjPoint = geoData->point(adjVertex); + if (distance(adjPoint.xy(), endPoint.xy()) < distanceToEndPoint + && (Triangle<2> {startPoint, endPoint, adjPoint}.area() + / distance(startPoint.xy(), endPoint.xy())) + < nearNodeTolerance) { + start = adjVertex; + geoData->point(start).z = triangle.positionOnPlane(adjPoint).z; + return true; + } + return false; + })) { + continue; + } + if (std::ranges::any_of(geoData->voh_range(start), [&](const auto & outHalf) { + const auto next = geoData->next_halfedge_handle(outHalf); + const auto nexts + = std::array {geoData->from_vertex_handle(next), geoData->to_vertex_handle(next)}; + const auto nextPoints = nexts | std::views::transform([this](const auto v) { + return std::make_pair(v, geoData->point(v)); + }); + if (linesCross(startPoint, endPoint, nextPoints.front().second, nextPoints.back().second)) { + if (const auto intersection = linesIntersectAt(startPoint.xy(), endPoint.xy(), + nextPoints.front().second.xy(), nextPoints.back().second.xy())) { + if (const auto nextEdge = geoData->shouldFlip(next, startPoint)) { + geoData->flip(*nextEdge); + return true; + } + start = geoData->split_copy( + geoData->edge_handle(next), triangle.positionOnPlane(*intersection)); + addVertexForNormalUpdate(start); + boundaryTriangles.emplace(start, &triangle); return true; } - start = split_copy(edge_handle(next), triangle.positionOnPlane(*intersection)); - addVertexForNormalUpdate(start); - boundaryTriangles.emplace(start, &triangle); - return true; + throw std::runtime_error("Crossing lines don't intersect"); } - throw std::runtime_error("Crossing lines don't intersect"); - } - return false; - })) { - continue; - } + return false; + })) { + continue; + } #ifndef NDEBUG - CLOG(start); - CLOG(startPoint); - CLOG(end); - CLOG(endPoint); - for (const auto v : vv_range(start)) { - CLOG(point(v)); - } + CLOG(start); + CLOG(startPoint); + CLOG(end); + CLOG(endPoint); + for (const auto v : geoData->vv_range(start)) { + CLOG(geoData->point(v)); + } #endif - sanityCheck(); - throw std::runtime_error( - std::format("Could not navigate to ({}, {}, {})", endPoint.x, endPoint.y, endPoint.z)); - } - }; - auto doBoundary = [&doBoundaryPart, triangle = strip.begin()](const auto & verts) mutable { - const auto & [a, _, c] = verts; - doBoundaryPart(a, c, *triangle); - triangle++; - }; - std::ranges::for_each(newVerts | std::views::adjacent<3>, doBoundary); - doBoundaryPart(*++newVerts.begin(), newVerts.front(), strip.front()); - doBoundaryPart(*++newVerts.rbegin(), newVerts.back(), strip.back()); - - std::set done; - std::set todo; - auto todoOutHalfEdges = [&todo, &done, this](const VertexHandle v) { - std::copy_if(voh_begin(v), voh_end(v), std::inserter(todo, todo.end()), [&done](const auto & h) { - return !done.contains(h); - }); - }; - std::ranges::for_each(newVerts, todoOutHalfEdges); - while (!todo.empty()) { - const auto heh = todo.extract(todo.begin()).value(); - const auto fromVertex = from_vertex_handle(heh); - const auto toVertex = to_vertex_handle(heh); - const auto & fromPoint = point(fromVertex); - auto & toPoint = point(toVertex); - auto toTriangle = getTriangle(toPoint); - if (!toTriangle) { - if (const auto boundaryVertex = boundaryTriangles.find(toVertex); - boundaryVertex != boundaryTriangles.end()) { - toTriangle = boundaryVertex->second; + geoData->sanityCheck(); + throw std::runtime_error( + std::format("Could not navigate to ({}, {}, {})", endPoint.x, endPoint.y, endPoint.z)); } } - if (toTriangle) { // point within the new strip, adjust vertically by triangle - toPoint.z = toTriangle->positionOnPlane(toPoint).z; - addVertexForNormalUpdate(toVertex); - todoOutHalfEdges(toVertex); + + void + cutBoundary(const std::vector & newVerts, RelativeDistance nearNodeTolerance) + { + // Cut along each edge of triangleStrip AB, AC, BC, BD, CD, CE etc + std::ranges::for_each(newVerts | std::views::adjacent<3>, + [this, nearNodeTolerance, triangle = strip.begin()](const auto & verts) mutable { + const auto & [a, _, c] = verts; + doBoundaryPart(a, c, *triangle, nearNodeTolerance); + triangle++; + }); + doBoundaryPart(*++newVerts.begin(), newVerts.front(), strip.front(), nearNodeTolerance); + doBoundaryPart(*++newVerts.rbegin(), newVerts.back(), strip.back(), nearNodeTolerance); } - else if (!toTriangle) { // point without the new strip, adjust vertically by limit - const auto maxOffset = static_cast(opts.maxSlope * length<2>(heh)); - const auto newHeight = std::clamp(toPoint.z, fromPoint.z - maxOffset, fromPoint.z + maxOffset); - if (newHeight != toPoint.z) { - toPoint.z = newHeight; - addVertexForNormalUpdate(toVertex); - std::copy_if(voh_begin(toVertex), voh_end(toVertex), std::inserter(todo, todo.end()), - [this, &boundaryTriangles](const auto & heh) { - return !boundaryTriangles.contains(to_vertex_handle(heh)); + + void + setHeights(const std::vector & newVerts, RelativeDistance maxSlope) + { + std::set done; + std::set todo; + auto todoOutHalfEdges = [&todo, &done, this](const VertexHandle v) { + std::ranges::copy_if(geoData->voh_range(v), std::inserter(todo, todo.end()), [&done](const auto & h) { + return !done.contains(h); + }); + }; + std::ranges::for_each(newVerts, todoOutHalfEdges); + auto setHalfedgeToHeight = [this, &todoOutHalfEdges, maxSlope, &done]( + const auto & setHalfedgeToHeight, const HalfedgeHandle heh) -> void { + const auto [fromVertex, toVertex] = geoData->toVertexHandles(heh); + auto & toPoint = geoData->point(toVertex); + auto toTriangle = getTriangle(toPoint); + if (!toTriangle) { + if (const auto boundaryVertex = boundaryTriangles.find(toVertex); + boundaryVertex != boundaryTriangles.end()) { + toTriangle = boundaryVertex->second; + } + } + if (toTriangle) { // point within the new strip, adjust vertically by triangle + toPoint.z = toTriangle->positionOnPlane(toPoint).z; + todoOutHalfEdges(toVertex); + } + else { // point without the new strip, adjust vertically by limit + const auto maxOffset = static_cast(maxSlope * geoData->length<2>(heh)); + const auto fromHeight = geoData->point(fromVertex).z; + const auto newHeight = std::clamp(toPoint.z, fromHeight - maxOffset, fromHeight + maxOffset); + if (newHeight != toPoint.z) { + toPoint.z = newHeight; + std::ranges::for_each(geoData->voh_range(toVertex), [&setHalfedgeToHeight](const auto heh) { + setHalfedgeToHeight(setHalfedgeToHeight, heh); }); + } + } + done.insert(heh); + }; + while (!todo.empty()) { + setHalfedgeToHeight(setHalfedgeToHeight, todo.extract(todo.begin()).value()); } + std::ranges::for_each(done, [this](const auto heh) { + const auto ends = geoData->toVertexHandles(heh); + addVertexForNormalUpdate(ends.first); + addVertexForNormalUpdate(ends.second); + }); + geoData->sanityCheck(); } - done.insert(heh); - } - sanityCheck(); - - std::vector out; - auto surfaceStripWalk - = [this, &getTriangle, &opts, &out](const auto & surfaceStripWalk, const auto & face) -> void { - if (!property(surface, face)) { - property(surface, face) = opts.surface; - out.emplace_back(face); - std::ranges::for_each( - ff_range(face), [this, &getTriangle, &surfaceStripWalk](const auto & adjacentFaceHandle) { - if (getTriangle(this->triangle<2>(adjacentFaceHandle).centroid())) { - surfaceStripWalk(surfaceStripWalk, adjacentFaceHandle); - } - }); + + std::vector + setSurface(const Surface * surface) + { + std::vector out; + auto surfaceStripWalk = [this, surface, &out](const auto & surfaceStripWalk, const auto & face) -> void { + if (!geoData->property(geoData->surface, face)) { + geoData->property(geoData->surface, face) = surface; + out.emplace_back(face); + std::ranges::for_each( + geoData->ff_range(face), [this, &surfaceStripWalk](const auto & adjacentFaceHandle) { + if (getTriangle(geoData->triangle<2>(adjacentFaceHandle).centroid())) { + surfaceStripWalk(surfaceStripWalk, adjacentFaceHandle); + } + }); + } + }; + for (const auto & triangle : strip) { + surfaceStripWalk(surfaceStripWalk, geoData->findPoint(triangle.centroid())); + } + return out; + } + + std::vector + run(const SetHeightsOpts & opts) + { + const std::vector newVerts = createVerticesForStrip(opts.nearNodeTolerance); + cutBoundary(newVerts, opts.nearNodeTolerance); + setHeights(newVerts, opts.maxSlope); + const auto out = setSurface(opts.surface); + + geoData->updateAllVertexNormals(newOrChangedVerts); + geoData->afterChange(); + + return out; } + + private: + GeoData * geoData; + const std::span triangleStrip; + const std::vector> strip; + std::set newOrChangedVerts; + std::map *> boundaryTriangles; }; - for (const auto & triangle : strip) { - surfaceStripWalk(surfaceStripWalk, findPoint(triangle.centroid())); - } - updateAllVertexNormals(newOrChangedVerts); - afterChange(); - return out; + return SetHeights {this, triangleStrip}.run(opts); } void diff --git a/game/geoData.h b/game/geoData.h index 1a93d03..586b48d 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -73,7 +73,7 @@ public: } protected: - [[nodiscard]] VertexHandle setPoint(GlobalPosition3D point, const SetHeightsOpts &); + [[nodiscard]] VertexHandle setPoint(GlobalPosition3D point, RelativeDistance nearNodeTolerance); void updateAllVertexNormals(); template void updateAllVertexNormals(const R &); void updateVertexNormal(VertexHandle); -- cgit v1.2.3 From f36a3c4b51b1305548e3f645d645b20f1a192f1d Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Mon, 17 Feb 2025 18:50:30 +0000 Subject: Only build/run GeoDataMesh::sanityCheck for debug --- game/geoData.cpp | 6 +++++- game/geoDataMesh.cpp | 4 ++-- game/geoDataMesh.h | 2 ++ 3 files changed, 9 insertions(+), 3 deletions(-) (limited to 'game') diff --git a/game/geoData.cpp b/game/geoData.cpp index 6052cd1..988b11c 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -350,7 +350,9 @@ GeoData::setHeights(const std::span triangleStrip, const std::ranges::for_each(newVerts, [this](auto vertex) { addVertexForNormalUpdate(vertex); }); +#ifndef NDEBUG geoData->sanityCheck(); +#endif return newVerts; } @@ -431,8 +433,8 @@ GeoData::setHeights(const std::span triangleStrip, const for (const auto v : geoData->vv_range(start)) { CLOG(geoData->point(v)); } -#endif geoData->sanityCheck(); +#endif throw std::runtime_error( std::format("Could not navigate to ({}, {}, {})", endPoint.x, endPoint.y, endPoint.z)); } @@ -499,7 +501,9 @@ GeoData::setHeights(const std::span triangleStrip, const addVertexForNormalUpdate(ends.first); addVertexForNormalUpdate(ends.second); }); +#ifndef NDEBUG geoData->sanityCheck(); +#endif } std::vector diff --git a/game/geoDataMesh.cpp b/game/geoDataMesh.cpp index 687a025..60af061 100644 --- a/game/geoDataMesh.cpp +++ b/game/geoDataMesh.cpp @@ -98,16 +98,15 @@ GeoDataMesh::centre(const HalfedgeHandle heh) const return midpoint(hehPoints.first, hehPoints.second); } +#ifndef NDEBUG void GeoDataMesh::sanityCheck(const std::source_location & loc) const { if (const auto upSideDown = std::ranges::count_if(faces(), [this](const auto face) { if (!triangle<2>(face).isUp()) { -#ifndef NDEBUG for (const auto vertex : fv_range(face)) { CLOG(point(vertex)); } -#endif return true; } return false; @@ -116,6 +115,7 @@ GeoDataMesh::sanityCheck(const std::source_location & loc) const "{} upside down faces detected - checked from {}:{}", upSideDown, loc.function_name(), loc.line())); } } +#endif bool GeoDataMesh::canFlip(const HalfedgeHandle edge) const diff --git a/game/geoDataMesh.h b/game/geoDataMesh.h index 5d0bade..befe9fe 100644 --- a/game/geoDataMesh.h +++ b/game/geoDataMesh.h @@ -49,7 +49,9 @@ public: [[nodiscard]] GlobalPosition3D positionAt(const PointFace &) const; protected: +#ifndef NDEBUG void sanityCheck(const std::source_location & = std::source_location::current()) const; +#endif [[nodiscard]] bool faceContainsPoint(GlobalPosition2D, FaceHandle) const; [[nodiscard]] HalfedgeHandle findBoundaryStart() const; -- cgit v1.2.3 From 9c4b26ce6781584ddcd60da8a013ac5757ec05b1 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Tue, 18 Feb 2025 19:25:34 +0000 Subject: Expand new verts collection once Before doing vertex normal recalc only, not on every insert --- game/geoData.cpp | 18 +++++------------- game/geoDataMesh.cpp | 8 ++++++++ game/geoDataMesh.h | 2 ++ 3 files changed, 15 insertions(+), 13 deletions(-) (limited to 'game') diff --git a/game/geoData.cpp b/game/geoData.cpp index 988b11c..c472240 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -347,22 +347,13 @@ GeoData::setHeights(const std::span triangleStrip, const = materializeRange(triangleStrip | std::views::transform([this, nearNodeTolerance](auto v) { return geoData->setPoint(v, nearNodeTolerance); })); - std::ranges::for_each(newVerts, [this](auto vertex) { - addVertexForNormalUpdate(vertex); - }); + std::ranges::copy(newVerts, std::inserter(newOrChangedVerts, newOrChangedVerts.end())); #ifndef NDEBUG geoData->sanityCheck(); #endif return newVerts; } - void - addVertexForNormalUpdate(const VertexHandle vertex) - { - newOrChangedVerts.emplace(vertex); - std::ranges::copy(geoData->vv_range(vertex), std::inserter(newOrChangedVerts, newOrChangedVerts.end())); - } - const Triangle<3> * getTriangle(const GlobalPosition2D point) const { @@ -415,7 +406,7 @@ GeoData::setHeights(const std::span triangleStrip, const } start = geoData->split_copy( geoData->edge_handle(next), triangle.positionOnPlane(*intersection)); - addVertexForNormalUpdate(start); + newOrChangedVerts.emplace(start); boundaryTriangles.emplace(start, &triangle); return true; } @@ -498,8 +489,8 @@ GeoData::setHeights(const std::span triangleStrip, const } std::ranges::for_each(done, [this](const auto heh) { const auto ends = geoData->toVertexHandles(heh); - addVertexForNormalUpdate(ends.first); - addVertexForNormalUpdate(ends.second); + newOrChangedVerts.emplace(ends.first); + newOrChangedVerts.emplace(ends.second); }); #ifndef NDEBUG geoData->sanityCheck(); @@ -536,6 +527,7 @@ GeoData::setHeights(const std::span triangleStrip, const setHeights(newVerts, opts.maxSlope); const auto out = setSurface(opts.surface); + geoData->expandVerts(newOrChangedVerts); geoData->updateAllVertexNormals(newOrChangedVerts); geoData->afterChange(); diff --git a/game/geoDataMesh.cpp b/game/geoDataMesh.cpp index 60af061..8107a5e 100644 --- a/game/geoDataMesh.cpp +++ b/game/geoDataMesh.cpp @@ -140,3 +140,11 @@ GeoDataMesh::shouldFlip(const HalfedgeHandle next, const GlobalPosition2D startP } return std::nullopt; }; + +void +GeoDataMesh::expandVerts(std::set & verts) const +{ + std::ranges::for_each(std::vector(verts.begin(), verts.end()), [&verts, this](auto vertex) { + std::ranges::copy(vv_range(vertex), std::inserter(verts, verts.end())); + }); +} diff --git a/game/geoDataMesh.h b/game/geoDataMesh.h index befe9fe..72b069e 100644 --- a/game/geoDataMesh.h +++ b/game/geoDataMesh.h @@ -3,6 +3,7 @@ #include "config/types.h" #include "triangle.h" #include +#include #include #include #include @@ -90,6 +91,7 @@ protected: [[nodiscard]] bool canFlip(HalfedgeHandle edge) const; [[nodiscard]] std::optional shouldFlip(HalfedgeHandle next, GlobalPosition2D startPoint) const; + void expandVerts(std::set & verts) const; template [[nodiscard]] RelativeDistance -- cgit v1.2.3 From b86883a943b35aa9c2a50cf54f544807adfe4e55 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 23 Feb 2025 13:28:36 +0000 Subject: Add adjusted boundary vertices to new/changes/boundary lists --- game/geoData.cpp | 2 ++ 1 file changed, 2 insertions(+) (limited to 'game') 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') 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') 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 27e1da72e5ff30d4e5b94bd1d8a674bf1e645222 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 23 Feb 2025 23:58:56 +0000 Subject: Improve number of segments in LinkCurve bases --- game/network/link.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'game') diff --git a/game/network/link.cpp b/game/network/link.cpp index 61e8771..c84524c 100644 --- a/game/network/link.cpp +++ b/game/network/link.cpp @@ -93,7 +93,7 @@ LinkCurve::getBase(RelativeDistance width) const { const auto start = ends.front().node->pos; const auto end = ends.back().node->pos; - const auto segs = std::ceil(15.F * arc.length()); + const auto segs = std::ceil(std::sqrt(radius) * 0.02F * arc.length()); const auto step {glm::vec<2, RelativeDistance> {arc.length(), end.z - start.z} / segs}; auto segCount = static_cast(segs) + 1; -- cgit v1.2.3 From 7c04c368fe0694b38e2ab46aca078d921c7d44b1 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Mon, 24 Feb 2025 00:10:07 +0000 Subject: Don't rely on triangle centroid not already having a surface --- game/geoData.cpp | 12 ++++++------ game/geoData.h | 2 +- 2 files changed, 7 insertions(+), 7 deletions(-) (limited to 'game') diff --git a/game/geoData.cpp b/game/geoData.cpp index d577392..4291a64 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -319,7 +319,7 @@ GeoData::setPoint(GlobalPosition3D tsPoint, const RelativeDistance nearNodeToler return split_copy(face, tsPoint); }; -std::vector +std::set GeoData::setHeights(const std::span triangleStrip, const SetHeightsOpts & opts) { if (triangleStrip.size() < 3) { @@ -532,14 +532,14 @@ GeoData::setHeights(const std::span triangleStrip, const } } - std::vector + std::set setSurface(const Surface * surface) { - std::vector out; + std::set out; auto surfaceStripWalk = [this, surface, &out](const auto & surfaceStripWalk, const auto & face) -> void { - if (!geoData->property(geoData->surface, face)) { + if (!out.contains(face)) { geoData->property(geoData->surface, face) = surface; - out.emplace_back(face); + out.emplace(face); std::ranges::for_each( geoData->ff_range(face), [this, &surfaceStripWalk](const auto & adjacentFaceHandle) { if (getTriangle(geoData->triangle<2>(adjacentFaceHandle).centroid())) { @@ -554,7 +554,7 @@ GeoData::setHeights(const std::span triangleStrip, const return out; } - std::vector + std::set run(const SetHeightsOpts & opts) { const std::vector newVerts = createVerticesForStrip(opts.nearNodeTolerance); diff --git a/game/geoData.h b/game/geoData.h index 586b48d..b2a75bd 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -55,7 +55,7 @@ public: RelativeDistance maxSlope = DEFAULT_MAX_SLOPE; }; - std::vector setHeights(std::span triangleStrip, const SetHeightsOpts &); + std::set setHeights(std::span triangleStrip, const SetHeightsOpts &); [[nodiscard]] auto getExtents() const -- cgit v1.2.3