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/geoDataMesh.cpp | 118 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 118 insertions(+) create mode 100644 game/geoDataMesh.cpp (limited to 'game/geoDataMesh.cpp') 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())); + } +} -- 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/geoDataMesh.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index e035a3c..dd7a3f8 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -291,6 +291,37 @@ GeoData::updateVertexNormal(VertexHandle vertex) set_normal(vertex, glm::normalize(n)); } +OpenMesh::VertexHandle +GeoData::setPoint(GlobalPosition3D tsPoint, const SetHeightsOpts & opts) +{ + const auto face = findPoint(tsPoint); + const auto distFromTsPoint = vertexDistanceFunction<2>(tsPoint); + // Check vertices + if (const auto nearest + = std::ranges::min(std::views::iota(fv_begin(face), fv_end(face)) | std::views::transform(distFromTsPoint), + {}, &std::pair::second); + nearest.second < opts.nearNodeTolerance) { + point(nearest.first).z = tsPoint.z; + return nearest.first; + } + // Check edges + if (const auto nearest + = std::ranges::min(std::views::iota(fh_begin(face), fh_end(face)) | std::views::transform(distFromTsPoint), + {}, &std::pair::second); + nearest.second < opts.nearNodeTolerance) { + const auto from = point(from_vertex_handle(nearest.first)).xy(); + const auto to = point(to_vertex_handle(nearest.first)).xy(); + const auto v = vector_normal(from - to); + const auto inter = linesIntersectAt(from, to, tsPoint.xy(), tsPoint.xy() + v); + if (!inter) { + throw std::runtime_error("Perpendicular lines do not cross"); + } + return split_copy(edge_handle(nearest.first), *inter || tsPoint.z); + } + // Nothing close, split face + return split_copy(face, tsPoint); +}; + std::vector GeoData::setHeights(const std::span triangleStrip, const SetHeightsOpts & opts) { @@ -301,57 +332,18 @@ GeoData::setHeights(const std::span triangleStrip, const lowerExtent.z = std::min(upperExtent.z, stripMinMax.min.z); upperExtent.z = std::max(upperExtent.z, stripMinMax.max.z); - const auto vertexDistFrom = [this](GlobalPosition2D p) { - return [p, this](const VertexHandle v) { - return std::make_pair(v, ::distance(p, this->point(v).xy())); - }; - }; - const auto vertexDistFromE = [this](GlobalPosition2D p) { - return [p, this](const HalfedgeHandle e) { - const auto fromPoint = point(from_vertex_handle(e)).xy(); - const auto toPoint = point(to_vertex_handle(e)).xy(); - return std::make_pair(e, Triangle<2> {fromPoint, toPoint, p}.height()); - }; - }; - std::set newOrChangedVerts; auto addVertexForNormalUpdate = [this, &newOrChangedVerts](const VertexHandle vertex) { newOrChangedVerts.emplace(vertex); std::ranges::copy(vv_range(vertex), std::inserter(newOrChangedVerts, newOrChangedVerts.end())); }; - auto newVertexOnFace = [this, &vertexDistFrom, &opts, &vertexDistFromE](GlobalPosition3D tsPoint) { - const auto face = findPoint(tsPoint); - // Check vertices - if (const auto nearest = std::ranges::min( - std::views::iota(fv_begin(face), fv_end(face)) | std::views::transform(vertexDistFrom(tsPoint)), {}, - &std::pair::second); - nearest.second < opts.nearNodeTolerance) { - point(nearest.first).z = tsPoint.z; - return nearest.first; - } - // Check edges - if (const auto nearest = std::ranges::min( - std::views::iota(fh_begin(face), fh_end(face)) | std::views::transform(vertexDistFromE(tsPoint)), - {}, &std::pair::second); - nearest.second < opts.nearNodeTolerance) { - const auto from = point(from_vertex_handle(nearest.first)).xy(); - const auto to = point(to_vertex_handle(nearest.first)).xy(); - const auto v = vector_normal(from - to); - const auto inter = linesIntersectAt(from, to, tsPoint.xy(), tsPoint.xy() + v); - if (!inter) { - throw std::runtime_error("Perpendicular lines do not cross"); - } - return split_copy(edge_handle(nearest.first), *inter || tsPoint.z); - } - // Nothing close, split face - return split_copy(face, tsPoint); - }; - // New vertices for each vertex in triangleStrip std::vector newVerts; newVerts.reserve(triangleStrip.size()); - std::transform(triangleStrip.begin(), triangleStrip.end(), std::back_inserter(newVerts), newVertexOnFace); + std::ranges::transform(triangleStrip, std::back_inserter(newVerts), [this, &opts](auto v) { + return setPoint(v, opts); + }); std::ranges::for_each(newVerts, addVertexForNormalUpdate); // Create temporary triangles from triangleStrip @@ -371,31 +363,11 @@ GeoData::setHeights(const std::span triangleStrip, const } return nullptr; }; - const auto canFlip = [this](const HalfedgeHandle edge) { - const auto opposite = opposite_halfedge_handle(edge); - const auto pointA = point(to_vertex_handle(edge)); - const auto pointB = point(to_vertex_handle(opposite)); - const auto pointC = point(to_vertex_handle(next_halfedge_handle(edge))); - const auto pointD = point(to_vertex_handle(next_halfedge_handle(opposite))); - - return Triangle<2> {pointC, pointB, pointD}.isUp() && Triangle<2> {pointA, pointC, pointD}.isUp(); - }; - const auto shouldFlip = [this, &canFlip](const HalfedgeHandle next, - const GlobalPosition2D startPoint) -> std::optional { - if (const auto nextEdge = edge_handle(next); is_flip_ok(nextEdge) && canFlip(next)) { - const auto opposite_point - = point(to_vertex_handle(next_halfedge_handle(opposite_halfedge_handle(next)))).xy(); - if (distance<2>(startPoint, opposite_point) < length<2>(next)) { - return nextEdge; - } - } - return std::nullopt; - }; sanityCheck(); // Cut along each edge of triangleStrip AB, AC, BC, BD, CD, CE etc std::map *> boundaryTriangles; - auto doBoundaryPart = [this, &boundaryTriangles, &opts, &addVertexForNormalUpdate, &shouldFlip]( + auto doBoundaryPart = [this, &boundaryTriangles, &opts, &addVertexForNormalUpdate]( VertexHandle start, VertexHandle end, const Triangle<3> & triangle) { boundaryTriangles.emplace(start, &triangle); const auto endPoint = point(end); diff --git a/game/geoData.h b/game/geoData.h index 3d5ea5d..1a93d03 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -73,6 +73,7 @@ public: } protected: + [[nodiscard]] VertexHandle setPoint(GlobalPosition3D point, const SetHeightsOpts &); void updateAllVertexNormals(); template void updateAllVertexNormals(const R &); void updateVertexNormal(VertexHandle); diff --git a/game/geoDataMesh.cpp b/game/geoDataMesh.cpp index aaa8c9c..687a025 100644 --- a/game/geoDataMesh.cpp +++ b/game/geoDataMesh.cpp @@ -116,3 +116,27 @@ GeoDataMesh::sanityCheck(const std::source_location & loc) const "{} upside down faces detected - checked from {}:{}", upSideDown, loc.function_name(), loc.line())); } } + +bool +GeoDataMesh::canFlip(const HalfedgeHandle edge) const +{ + const auto opposite = opposite_halfedge_handle(edge); + const auto pointA = point(to_vertex_handle(edge)); + const auto pointB = point(to_vertex_handle(opposite)); + const auto pointC = point(to_vertex_handle(next_halfedge_handle(edge))); + const auto pointD = point(to_vertex_handle(next_halfedge_handle(opposite))); + + return Triangle<2> {pointC, pointB, pointD}.isUp() && Triangle<2> {pointA, pointC, pointD}.isUp(); +}; + +std::optional +GeoDataMesh::shouldFlip(const HalfedgeHandle next, const GlobalPosition2D startPoint) const +{ + if (const auto nextEdge = edge_handle(next); is_flip_ok(nextEdge) && canFlip(next)) { + const auto oppositePoint = point(to_vertex_handle(next_halfedge_handle(opposite_halfedge_handle(next)))).xy(); + if (distance<2>(startPoint, oppositePoint) < length<2>(next)) { + return nextEdge; + } + } + return std::nullopt; +}; diff --git a/game/geoDataMesh.h b/game/geoDataMesh.h index 00db67c..5d0bade 100644 --- a/game/geoDataMesh.h +++ b/game/geoDataMesh.h @@ -1,7 +1,6 @@ #pragma once #include "config/types.h" -#include "ray.h" #include "triangle.h" #include #include @@ -60,6 +59,36 @@ protected: using HalfEdgePoints = std::pair; [[nodiscard]] HalfEdgePoints points(HalfEdgeVertices) const; + template + [[nodiscard]] auto + vertexDistanceFunction(GlobalPosition point) const + { + struct DistanceCalculator { + [[nodiscard]] std::pair + operator()(VertexHandle compVertex) const + { + return std::make_pair( + compVertex, ::distance(point, mesh->point(compVertex))); + } + + [[nodiscard]] + std::pair + operator()(const HalfedgeHandle compHalfedge) const + { + const auto edgePoints = mesh->points(mesh->toVertexHandles(compHalfedge)); + return std::make_pair(compHalfedge, Triangle<2> {edgePoints.second, edgePoints.first, point}.height()); + }; + + const GeoDataMesh * mesh; + GlobalPosition point; + }; + + return DistanceCalculator {this, point}; + } + + [[nodiscard]] bool canFlip(HalfedgeHandle edge) const; + [[nodiscard]] std::optional shouldFlip(HalfedgeHandle next, GlobalPosition2D startPoint) const; + template [[nodiscard]] RelativeDistance length(HalfedgeHandle heh) const -- cgit v1.2.3 From 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/geoDataMesh.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index 6052cd1..988b11c 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -350,7 +350,9 @@ GeoData::setHeights(const std::span triangleStrip, const std::ranges::for_each(newVerts, [this](auto vertex) { addVertexForNormalUpdate(vertex); }); +#ifndef NDEBUG geoData->sanityCheck(); +#endif return newVerts; } @@ -431,8 +433,8 @@ GeoData::setHeights(const std::span triangleStrip, const for (const auto v : geoData->vv_range(start)) { CLOG(geoData->point(v)); } -#endif geoData->sanityCheck(); +#endif throw std::runtime_error( std::format("Could not navigate to ({}, {}, {})", endPoint.x, endPoint.y, endPoint.z)); } @@ -499,7 +501,9 @@ GeoData::setHeights(const std::span triangleStrip, const addVertexForNormalUpdate(ends.first); addVertexForNormalUpdate(ends.second); }); +#ifndef NDEBUG geoData->sanityCheck(); +#endif } std::vector diff --git a/game/geoDataMesh.cpp b/game/geoDataMesh.cpp index 687a025..60af061 100644 --- a/game/geoDataMesh.cpp +++ b/game/geoDataMesh.cpp @@ -98,16 +98,15 @@ GeoDataMesh::centre(const HalfedgeHandle heh) const return midpoint(hehPoints.first, hehPoints.second); } +#ifndef NDEBUG void GeoDataMesh::sanityCheck(const std::source_location & loc) const { if (const auto upSideDown = std::ranges::count_if(faces(), [this](const auto face) { if (!triangle<2>(face).isUp()) { -#ifndef NDEBUG for (const auto vertex : fv_range(face)) { CLOG(point(vertex)); } -#endif return true; } return false; @@ -116,6 +115,7 @@ GeoDataMesh::sanityCheck(const std::source_location & loc) const "{} upside down faces detected - checked from {}:{}", upSideDown, loc.function_name(), loc.line())); } } +#endif bool GeoDataMesh::canFlip(const HalfedgeHandle edge) const diff --git a/game/geoDataMesh.h b/game/geoDataMesh.h index 5d0bade..befe9fe 100644 --- a/game/geoDataMesh.h +++ b/game/geoDataMesh.h @@ -49,7 +49,9 @@ public: [[nodiscard]] GlobalPosition3D positionAt(const PointFace &) const; protected: +#ifndef NDEBUG void sanityCheck(const std::source_location & = std::source_location::current()) const; +#endif [[nodiscard]] bool faceContainsPoint(GlobalPosition2D, FaceHandle) const; [[nodiscard]] HalfedgeHandle findBoundaryStart() const; -- cgit v1.2.3 From 9c4b26ce6781584ddcd60da8a013ac5757ec05b1 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Tue, 18 Feb 2025 19:25:34 +0000 Subject: Expand new verts collection once Before doing vertex normal recalc only, not on every insert --- game/geoData.cpp | 18 +++++------------- game/geoDataMesh.cpp | 8 ++++++++ game/geoDataMesh.h | 2 ++ 3 files changed, 15 insertions(+), 13 deletions(-) (limited to 'game/geoDataMesh.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index 988b11c..c472240 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -347,22 +347,13 @@ GeoData::setHeights(const std::span triangleStrip, const = materializeRange(triangleStrip | std::views::transform([this, nearNodeTolerance](auto v) { return geoData->setPoint(v, nearNodeTolerance); })); - std::ranges::for_each(newVerts, [this](auto vertex) { - addVertexForNormalUpdate(vertex); - }); + std::ranges::copy(newVerts, std::inserter(newOrChangedVerts, newOrChangedVerts.end())); #ifndef NDEBUG geoData->sanityCheck(); #endif return newVerts; } - void - addVertexForNormalUpdate(const VertexHandle vertex) - { - newOrChangedVerts.emplace(vertex); - std::ranges::copy(geoData->vv_range(vertex), std::inserter(newOrChangedVerts, newOrChangedVerts.end())); - } - const Triangle<3> * getTriangle(const GlobalPosition2D point) const { @@ -415,7 +406,7 @@ GeoData::setHeights(const std::span triangleStrip, const } start = geoData->split_copy( geoData->edge_handle(next), triangle.positionOnPlane(*intersection)); - addVertexForNormalUpdate(start); + newOrChangedVerts.emplace(start); boundaryTriangles.emplace(start, &triangle); return true; } @@ -498,8 +489,8 @@ GeoData::setHeights(const std::span triangleStrip, const } std::ranges::for_each(done, [this](const auto heh) { const auto ends = geoData->toVertexHandles(heh); - addVertexForNormalUpdate(ends.first); - addVertexForNormalUpdate(ends.second); + newOrChangedVerts.emplace(ends.first); + newOrChangedVerts.emplace(ends.second); }); #ifndef NDEBUG geoData->sanityCheck(); @@ -536,6 +527,7 @@ GeoData::setHeights(const std::span triangleStrip, const setHeights(newVerts, opts.maxSlope); const auto out = setSurface(opts.surface); + geoData->expandVerts(newOrChangedVerts); geoData->updateAllVertexNormals(newOrChangedVerts); geoData->afterChange(); diff --git a/game/geoDataMesh.cpp b/game/geoDataMesh.cpp index 60af061..8107a5e 100644 --- a/game/geoDataMesh.cpp +++ b/game/geoDataMesh.cpp @@ -140,3 +140,11 @@ GeoDataMesh::shouldFlip(const HalfedgeHandle next, const GlobalPosition2D startP } return std::nullopt; }; + +void +GeoDataMesh::expandVerts(std::set & verts) const +{ + std::ranges::for_each(std::vector(verts.begin(), verts.end()), [&verts, this](auto vertex) { + std::ranges::copy(vv_range(vertex), std::inserter(verts, verts.end())); + }); +} diff --git a/game/geoDataMesh.h b/game/geoDataMesh.h index befe9fe..72b069e 100644 --- a/game/geoDataMesh.h +++ b/game/geoDataMesh.h @@ -3,6 +3,7 @@ #include "config/types.h" #include "triangle.h" #include +#include #include #include #include @@ -90,6 +91,7 @@ protected: [[nodiscard]] bool canFlip(HalfedgeHandle edge) const; [[nodiscard]] std::optional shouldFlip(HalfedgeHandle next, GlobalPosition2D startPoint) const; + void expandVerts(std::set & verts) const; template [[nodiscard]] RelativeDistance -- cgit v1.2.3