From dbd181a9e49b3b32400eb812ff224074413d2ef4 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Tue, 12 Nov 2024 20:19:03 +0000 Subject: Add linesIntersectAt function 2 dimensional line intersection point --- test/test-maths.cpp | 8 ++++++++ 1 file changed, 8 insertions(+) (limited to 'test') diff --git a/test/test-maths.cpp b/test/test-maths.cpp index f7f34b3..b9d08bb 100644 --- a/test/test-maths.cpp +++ b/test/test-maths.cpp @@ -333,3 +333,11 @@ BOOST_DATA_TEST_CASE(rayLineDistance, BOOST_CHECK_LE(Ray(c, direction).distanceToLine(n1, n2), 0.01F); } } + +static_assert(linesIntersectAt(glm::ivec2 {10, 10}, {40, 40}, {10, 80}, {20, 40}).value().x == 24); +static_assert(linesIntersectAt(glm::vec2 {10, 10}, {40, 40}, {10, 80}, {20, 40}).value().y == 24); +static_assert(linesIntersectAt(GlobalPosition2D {311000100, 491100100}, {311050000, 491150000}, {312000100, 491200100}, + {311000100, 491100100}) + .value() + == GlobalPosition2D {311000100, 491100100}); +static_assert(!linesIntersectAt(glm::dvec2 {0, 1}, {0, 4}, {1, 8}, {1, 4}).has_value()); -- cgit v1.2.3 From 2be260117a757288d419cf1564ccd6b91794399e Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 23 Nov 2024 14:18:56 +0000 Subject: Pass setHeights options as a struct with defaults --- game/geoData.cpp | 15 +++++++-------- game/geoData.h | 11 ++++++++++- test/test-geoData.cpp | 2 +- 3 files changed, 18 insertions(+), 10 deletions(-) (limited to 'test') diff --git a/game/geoData.cpp b/game/geoData.cpp index a63e03b..cc9a056 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -410,10 +410,8 @@ GeoData::triangleContainsTriangle(const Triangle<2> & a, const Triangle<2> & b) return triangleContainsPoint(a.x, b) && triangleContainsPoint(a.y, b) && triangleContainsPoint(a.z, b); } -static constexpr RelativeDistance MAX_SLOPE = .5F; - void -GeoData::setHeights(const std::span triangleStrip, const Surface &) +GeoData::setHeights(const std::span triangleStrip, const SetHeightsOpts & opts) { if (triangleStrip.size() < 3) { return; @@ -434,12 +432,12 @@ GeoData::setHeights(const std::span triangleStrip, const std::vector newVerts; newVerts.reserve(newVerts.size()); std::transform(triangleStrip.begin(), triangleStrip.end(), std::back_inserter(newVerts), - [this, &newVerts, &vertexDistFrom](const auto tsPoint) { + [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 < 500.F && !std::ranges::contains(newVerts, nearest.first)) { + nearest.second < opts.nearNodeTolerance && !std::ranges::contains(newVerts, nearest.first)) { point(nearest.first) = tsPoint; return nearest.first; } @@ -466,7 +464,7 @@ 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]( + auto doBoundaryPart = [this, &boundaryTriangles, &newVerts, &vertexDistFrom, &opts]( VertexHandle start, VertexHandle end, const Triangle<3> & triangle) { boundaryTriangles.emplace(start, &triangle); const auto endPoint = point(end); @@ -484,7 +482,8 @@ GeoData::setHeights(const std::span triangleStrip, const if (const auto nextDist = std::ranges::min(nexts | std::views::transform(vertexDistFrom(*intersection)), {}, &std::pair::second); - nextDist.second < 500.F && !boundaryTriangles.contains(nextDist.first) + nextDist.second < opts.nearNodeTolerance + && !boundaryTriangles.contains(nextDist.first) && !std::ranges::contains(newVerts, nextDist.first)) { start = nextDist.first; point(start) = positionOnTriangle(*intersection, triangle); @@ -534,7 +533,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(MAX_SLOPE * glm::length(difference(heh).xy())); + const auto maxOffset = static_cast(opts.maxSlope * glm::length(difference(heh).xy())); 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 5daa7a4..51bb28b 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -142,7 +142,16 @@ public: [[nodiscard]] HalfedgeHandle findEntry(const GlobalPosition2D from, const GlobalPosition2D to) const; - void setHeights(const std::span triangleStrip, const Surface &); + struct SetHeightsOpts { + static constexpr auto DEFAULT_NEAR_NODE_TOLERANACE = 500.F; + static constexpr auto DEFAULT_MAX_SLOPE = 0.5F; + + const Surface & surface; + RelativeDistance nearNodeTolerance = DEFAULT_NEAR_NODE_TOLERANACE; + RelativeDistance maxSlope = DEFAULT_MAX_SLOPE; + }; + + void setHeights(std::span triangleStrip, const SetHeightsOpts &); [[nodiscard]] auto getExtents() const diff --git a/test/test-geoData.cpp b/test/test-geoData.cpp index 35d6bae..17e1741 100644 --- a/test/test-geoData.cpp +++ b/test/test-geoData.cpp @@ -232,7 +232,7 @@ BOOST_DATA_TEST_CASE(deform, loadFixtureJson("geoData/deform/ Surface surface; surface.colorBias = RGB {0, 0, 1}; auto gd = std::make_shared(GeoData::createFlat({0, 0}, {1000000, 1000000}, 100)); - BOOST_CHECK_NO_THROW(gd->setHeights(points, surface)); + BOOST_CHECK_NO_THROW(gd->setHeights(points, {.surface = surface})); ApplicationBase ab; TestMainWindow tmw; -- cgit v1.2.3 From 2e1a91564c4765dbdc3f633ba0ff8a4af7164503 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Wed, 27 Nov 2024 02:50:06 +0000 Subject: Update new/moved vertex normals --- game/geoData.cpp | 43 ++++++++++++++++++++++++++++--------------- game/geoData.h | 5 +++-- test/test-geoData.cpp | 11 ++++++----- 3 files changed, 37 insertions(+), 22 deletions(-) (limited to 'test') diff --git a/game/geoData.cpp b/game/geoData.cpp index cd0be29..f43e231 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -66,7 +66,7 @@ GeoData::loadFromAsciiGrid(const std::filesystem::path & input) }); } } - mesh.update_vertex_normals_only(); + mesh.updateAllVertexNormals(); return mesh; }; @@ -105,7 +105,7 @@ GeoData::createFlat(GlobalPosition2D lower, GlobalPosition2D upper, GlobalDistan } } - mesh.update_vertex_normals_only(); + mesh.updateAllVertexNormals(); return mesh; } @@ -377,23 +377,28 @@ GeoData::centre(const HalfedgeHandle heh) const } void -GeoData::update_vertex_normals_only() +GeoData::updateAllVertexNormals() { - update_vertex_normals_only(vertices_sbegin()); + updateAllVertexNormals(vertices()); } +template void -GeoData::update_vertex_normals_only(VertexIter start) +GeoData::updateAllVertexNormals(const R & range) { - std::for_each(start, vertices_end(), [this](const auto vh) { - if (normal(vh) == Normal3D {}) { - Normal3D n; - calc_vertex_normal_correct(vh, n); - this->set_normal(vh, glm::normalize(n)); - } + std::ranges::for_each(range, [this](const auto vertex) { + updateVertexNormal(vertex); }); } +void +GeoData::updateVertexNormal(VertexHandle vertex) +{ + Normal3D n; + calc_vertex_normal_correct(vertex, n); + set_normal(vertex, glm::normalize(n)); +} + bool GeoData::triangleOverlapsTriangle(const Triangle<2> & a, const Triangle<2> & b) { @@ -420,14 +425,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 initialVertexCount = static_cast(n_vertices()); - const auto vertexDistFrom = [this](GlobalPosition2D p) { return [p, this](const VertexHandle v) { return std::make_pair(v, glm::length(difference(this->point(v).xy(), p))); }; }; + std::set newOrChangedVerts; + auto addVertexForNormalUpdate = [this, &newOrChangedVerts](const VertexHandle vertex) { + newOrChangedVerts.emplace(vertex); + std::ranges::copy(vv_range(vertex), std::inserter(newOrChangedVerts, newOrChangedVerts.end())); + }; + // New vertices for each vertex in triangleStrip std::vector newVerts; newVerts.reserve(newVerts.size()); @@ -443,6 +452,7 @@ GeoData::setHeights(const std::span triangleStrip, const } return split(face, tsPoint); }); + std::ranges::for_each(newVerts, addVertexForNormalUpdate); // Create temporary triangles from triangleStrip std::vector> strip; @@ -464,7 +474,7 @@ 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]( + auto doBoundaryPart = [this, &boundaryTriangles, &newVerts, &vertexDistFrom, &opts, &addVertexForNormalUpdate]( VertexHandle start, VertexHandle end, const Triangle<3> & triangle) { boundaryTriangles.emplace(start, &triangle); const auto endPoint = point(end); @@ -491,6 +501,7 @@ GeoData::setHeights(const std::span triangleStrip, const else { start = split(edge_handle(next), positionOnTriangle(*intersection, triangle)); } + addVertexForNormalUpdate(start); boundaryTriangles.emplace(start, &triangle); return true; } @@ -530,6 +541,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; + addVertexForNormalUpdate(toVertex); todoOutHalfEdges(toVertex); } else if (!toTriangle) { // point without the new strip, adjust vertically by limit @@ -537,6 +549,7 @@ GeoData::setHeights(const std::span triangleStrip, const 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)); @@ -559,5 +572,5 @@ GeoData::setHeights(const std::span triangleStrip, const }; surfaceStripWalk(surfaceStripWalk, findPoint(strip.front().centroid())); - update_vertex_normals_only(VertexIter {*this, vertex_handle(initialVertexCount), true}); + updateAllVertexNormals(newOrChangedVerts); } diff --git a/game/geoData.h b/game/geoData.h index c28dd14..71ec85f 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -200,8 +200,9 @@ protected: [[nodiscard]] RelativeDistance length(const HalfedgeHandle) const; [[nodiscard]] GlobalPosition3D centre(const HalfedgeHandle) const; - void update_vertex_normals_only(); - void update_vertex_normals_only(VertexIter start); + void updateAllVertexNormals(); + template void updateAllVertexNormals(const R &); + void updateVertexNormal(VertexHandle); private: GlobalPosition3D lowerExtent {}, upperExtent {}; diff --git a/test/test-geoData.cpp b/test/test-geoData.cpp index 17e1741..2f3d215 100644 --- a/test/test-geoData.cpp +++ b/test/test-geoData.cpp @@ -31,11 +31,9 @@ BOOST_AUTO_TEST_CASE(loadSuccess) BOOST_AUTO_TEST_CASE(normalsAllPointUp) { - BOOST_CHECK_EQUAL(std::count_if(vertices_begin(), vertices_end(), - [this](auto && vh) { - return normal(vh).z > 0; - }), - n_vertices()); + BOOST_CHECK(std::ranges::all_of(vertices(), [this](auto && vertex) { + return normal(vertex).z > 0; + })); } BOOST_AUTO_TEST_CASE(trianglesContainsPoints) @@ -233,6 +231,9 @@ BOOST_DATA_TEST_CASE(deform, loadFixtureJson("geoData/deform/ surface.colorBias = RGB {0, 0, 1}; auto gd = std::make_shared(GeoData::createFlat({0, 0}, {1000000, 1000000}, 100)); BOOST_CHECK_NO_THROW(gd->setHeights(points, {.surface = surface})); + BOOST_CHECK(std::ranges::all_of(gd->vertices(), [&gd](auto && vertex) { + return gd->normal(vertex).z > 0; + })); ApplicationBase ab; TestMainWindow tmw; -- cgit v1.2.3 From f9e6220bf8b17681cb2f395ab64851a72659a070 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 1 Dec 2024 16:56:14 +0000 Subject: Move GeoData::Triangle to global lib --- game/geoData.h | 89 ++++------------------------------------- lib/triangle.h | 108 ++++++++++++++++++++++++++++++++++++++++++++++++++ test/test-geoData.cpp | 2 +- 3 files changed, 117 insertions(+), 82 deletions(-) create mode 100644 lib/triangle.h (limited to 'test') diff --git a/game/geoData.h b/game/geoData.h index dcc28e0..79924d3 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -4,6 +4,7 @@ #include "config/types.h" #include "ray.h" #include "surface.h" +#include "triangle.h" #include #include #include @@ -52,85 +53,7 @@ public: mutable FaceHandle _face {}; }; - template struct Triangle : public glm::vec<3, glm::vec> { - using Point = glm::vec; - using base = glm::vec<3, Point>; - using base::base; - - template Triangle(const GeoData * m, Range range) - { - assert(std::distance(range.begin(), range.end()) == 3); - std::transform(range.begin(), range.end(), &base::operator[](0), [m](auto vh) { - return m->point(vh); - }); - } - - [[nodiscard]] Point - operator*(BaryPosition bari) const - { - return p(0) + (::difference(p(1), p(0)) * bari.x) + (::difference(p(2), p(0)) * bari.y); - } - - [[nodiscard]] Point - centroid() const - { - return [this](std::integer_sequence) { - return Point {(p(0)[axis] + p(1)[axis] + p(2)[axis]) / 3 ...}; - }(std::make_integer_sequence()); - } - - [[nodiscard]] auto - area() const - requires(Dim == 3) - { - return glm::length(crossProduct(::difference(p(1), p(0)), ::difference(p(2), p(0)))) / 2.F; - } - - [[nodiscard]] Normal3D - normal() const - requires(Dim == 3) - { - return crossProduct(::difference(p(1), p(0)), ::difference(p(2), p(0))); - } - - [[nodiscard]] Normal3D - nnormal() const - requires(Dim == 3) - { - return glm::normalize(normal()); - } - - [[nodiscard]] auto - angle(glm::length_t c) const - { - return Arc {P(c), P(c + 2), P(c + 1)}.length(); - } - - template - [[nodiscard]] auto - angleAt(const GlobalPosition pos) const - requires(D <= Dim) - { - for (glm::length_t i {}; i < 3; ++i) { - if (GlobalPosition {p(i)} == pos) { - return angle(i); - } - } - return 0.F; - } - - [[nodiscard]] inline auto - p(const glm::length_t i) const - { - return base::operator[](i); - } - - [[nodiscard]] inline auto - P(const glm::length_t i) const - { - return base::operator[](i % 3); - } - }; + template using Triangle = ::Triangle; [[nodiscard]] FaceHandle findPoint(GlobalPosition2D) const; [[nodiscard]] FaceHandle findPoint(GlobalPosition2D, FaceHandle start) const; @@ -178,9 +101,13 @@ public: protected: template [[nodiscard]] Triangle - triangle(FaceHandle f) const + triangle(FaceHandle face) const { - return {this, fv_range(f)}; + 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> &); diff --git a/lib/triangle.h b/lib/triangle.h new file mode 100644 index 0000000..812bfab --- /dev/null +++ b/lib/triangle.h @@ -0,0 +1,108 @@ +#pragma once + +#include "config/types.h" +#include "maths.h" +#include + +template +struct Triangle : public glm::vec<3, glm::vec> { + using Point = glm::vec; + using Base = glm::vec<3, glm::vec>; + using Base::Base; + + [[nodiscard]] constexpr Point + operator*(BaryPosition bari) const + { + return p(0) + (sideDifference(1) * bari.x) + (sideDifference(2) * bari.y); + } + + [[nodiscard]] constexpr Point + centroid() const + { + return [this](std::integer_sequence) { + return Point {(p(0)[Axis] + p(1)[Axis] + p(2)[Axis]) / 3 ...}; + }(std::make_integer_sequence()); + } + + [[nodiscard]] constexpr auto + area() const + requires(Dim == 3) + { + return glm::length(crossProduct(sideDifference(1), sideDifference(2))) / T {2}; + } + + [[nodiscard]] constexpr Normal3D + normal() const + requires(Dim == 3) + { + return crossProduct(sideDifference(1), sideDifference(2)); + } + + [[nodiscard]] constexpr Normal3D + nnormal() const + requires(Dim == 3) + { + return glm::normalize(normal()); + } + + [[nodiscard]] constexpr auto + sideDifference(glm::length_t side) const + { + return difference(p(side), p(0)); + } + + [[nodiscard]] constexpr auto + angle(glm::length_t corner) const + { + return Arc {P(corner), P(corner + 2), P(corner + 1)}.length(); + } + + template + [[nodiscard]] constexpr auto + angleAt(const glm::vec pos) const + requires(D <= Dim) + { + for (glm::length_t i {}; i < 3; ++i) { + if (glm::vec {p(i)} == pos) { + return angle(i); + } + } + return 0.F; + } + + [[nodiscard]] constexpr auto + p(const glm::length_t idx) const + { + return Base::operator[](idx); + } + + [[nodiscard]] constexpr auto + P(const glm::length_t idx) const + { + return Base::operator[](idx % 3); + } + + [[nodiscard]] constexpr Point * + begin() + { + return &(Base::x); + } + + [[nodiscard]] constexpr const Point * + begin() const + { + return &(Base::x); + } + + [[nodiscard]] constexpr Point * + end() + { + return begin() + 3; + } + + [[nodiscard]] constexpr const Point * + end() const + { + return begin() + 3; + } +}; diff --git a/test/test-geoData.cpp b/test/test-geoData.cpp index 2f3d215..bd1ff87 100644 --- a/test/test-geoData.cpp +++ b/test/test-geoData.cpp @@ -40,7 +40,7 @@ BOOST_AUTO_TEST_CASE(trianglesContainsPoints) { const auto face = face_handle(0); - BOOST_TEST_CONTEXT(GeoData::Triangle<2>(this, fv_range(face))) { + BOOST_TEST_CONTEXT(this->triangle<2>(face)) { BOOST_CHECK(triangleContainsPoint(GlobalPosition2D {xllcorner, yllcorner}, face)); BOOST_CHECK(triangleContainsPoint(GlobalPosition2D {xllcorner + cellsize, yllcorner + cellsize}, face)); BOOST_CHECK(triangleContainsPoint(GlobalPosition2D {xllcorner, yllcorner + cellsize}, face)); -- cgit v1.2.3