From ca276ca5471a4e7a137f68a81feb150282eae62f Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Wed, 7 Feb 2024 23:50:50 +0000 Subject: Add stripiter A generic iterator wrapper returning a tuple of 3 references to the original values, as processed in the fashion of an OpenGL triangle strip. --- lib/collections.h | 60 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ test/test-lib.cpp | 20 +++++++++++++++++++ 2 files changed, 80 insertions(+) diff --git a/lib/collections.h b/lib/collections.h index 943b986..6cee10c 100644 --- a/lib/collections.h +++ b/lib/collections.h @@ -2,6 +2,7 @@ #include #include +#include #include #include #include @@ -160,3 +161,62 @@ template struct pair_range { }; template pair_range(std::pair) -> pair_range; + +template struct stripiter { + [[nodiscard]] constexpr bool + operator!=(const stripiter & other) const + { + return current != other.current; + } + + [[nodiscard]] constexpr bool + operator==(const stripiter & other) const + { + return current == other.current; + } + + constexpr stripiter & + operator++() + { + ++current; + off = 1 - off; + return *this; + } + + constexpr stripiter & + operator--() + { + --current; + off = 1 - off; + return *this; + } + + constexpr auto + operator-(const stripiter & other) const + { + return current - other.current; + } + + constexpr auto + operator*() const + { + return std::tie(*(current - (2 - off)), *(current - off - 1), *current); + } + + iter current; + uint8_t off {}; +}; + +template struct std::iterator_traits> : std::iterator_traits { }; + +constexpr auto +strip_begin(IterableCollection auto & cont) +{ + return stripiter {cont.begin() + 2}; +} + +constexpr auto +strip_end(IterableCollection auto & cont) +{ + return stripiter {cont.end()}; +} diff --git a/test/test-lib.cpp b/test/test-lib.cpp index 58b769a..5f0b5e5 100644 --- a/test/test-lib.cpp +++ b/test/test-lib.cpp @@ -4,6 +4,7 @@ #include #include +#include #include #include #include @@ -49,3 +50,22 @@ BOOST_AUTO_TEST_CASE(generate_move_and_delete) } BOOST_CHECK(active.empty()); } + +constexpr std::array TRIANGLE_STRIP_IN {0, 1, 2, 3, 4, 5}; +static_assert(std::distance(strip_begin(TRIANGLE_STRIP_IN), strip_end(TRIANGLE_STRIP_IN)) == 4); + +BOOST_AUTO_TEST_CASE(triangle_strip_iter) +{ + constexpr std::array TRIANGLE_STRIP_EXPECTED {0, 1, 2, 2, 1, 3, 2, 3, 4, 4, 3, 5}; + + std::vector out; + std::for_each(strip_begin(TRIANGLE_STRIP_IN), strip_end(TRIANGLE_STRIP_IN), [&out](const auto & t) { + const auto [a, b, c] = t; + out.push_back(a); + out.push_back(b); + out.push_back(c); + }); + BOOST_REQUIRE_EQUAL(out.size(), (TRIANGLE_STRIP_IN.size() - 2) * 3); + BOOST_CHECK_EQUAL_COLLECTIONS( + out.begin(), out.end(), TRIANGLE_STRIP_EXPECTED.begin(), TRIANGLE_STRIP_EXPECTED.end()); +} -- cgit v1.2.3 From fa48542d7387ba376b56dc4f60f90fccbd037f92 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Mon, 12 Feb 2024 20:28:50 +0000 Subject: Cast relative position accordingly in geometric plane --- lib/geometricPlane.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/lib/geometricPlane.h b/lib/geometricPlane.h index 3f95d3c..3b1a0e4 100644 --- a/lib/geometricPlane.h +++ b/lib/geometricPlane.h @@ -27,7 +27,7 @@ public: [[nodiscard]] inline PlaneRelation getRelation(PositionType point) const { - const auto d = glm::dot(normal, point - origin); + const auto d = glm::dot(normal, RelativePosition3D(point - origin)); return d < 0.F ? PlaneRelation::Below : d > 0.F ? PlaneRelation::Above : PlaneRelation::On; } -- cgit v1.2.3 From 40f5a59dba7d5061821e143cebcfa30f6faa9464 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Mon, 12 Feb 2024 20:32:01 +0000 Subject: Add materializeRange override for naked iterator pair --- lib/collections.h | 13 ++++++++++--- 1 file changed, 10 insertions(+), 3 deletions(-) diff --git a/lib/collections.h b/lib/collections.h index 6cee10c..dd603be 100644 --- a/lib/collections.h +++ b/lib/collections.h @@ -130,18 +130,25 @@ vectorOfN(std::integral auto N, T start = {}, T step = 1) return v; } +template typename Rtn = std::vector, typename In> +[[nodiscard]] auto +materializeRange(const In begin, const In end) +{ + return Rtn(begin, end); +} + template typename Rtn = std::vector, IterableCollection In> [[nodiscard]] auto -materializeRange(In && in) +materializeRange(const In & in) { - return Rtn(in.begin(), in.end()); + return materializeRange(in.begin(), in.end()); } template typename Rtn = std::vector, typename In> [[nodiscard]] auto materializeRange(const std::pair & in) { - return Rtn(in.first, in.second); + return materializeRange(in.first, in.second); } template struct pair_range { -- cgit v1.2.3 From e0c5affab138cdc35074d66d641dae2dba1ab3f1 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Mon, 12 Feb 2024 20:40:20 +0000 Subject: Create flat GeoData as 10m squares instead of one big square --- game/geoData.cpp | 28 ++++++++++++++++++++++++---- 1 file changed, 24 insertions(+), 4 deletions(-) diff --git a/game/geoData.cpp b/game/geoData.cpp index b30a35b..49cf892 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -62,6 +62,8 @@ GeoData::loadFromAsciiGrid(const std::filesystem::path & input) return mesh; }; +template constexpr static T GRID_SIZE = 10'000; + GeoData GeoData::createFlat(GlobalPosition2D lower, GlobalPosition2D upper, GlobalDistance h) { @@ -70,11 +72,29 @@ GeoData::createFlat(GlobalPosition2D lower, GlobalPosition2D upper, GlobalDistan mesh.lowerExtent = {lower, h}; mesh.upperExtent = {upper, h}; - const auto ll = mesh.add_vertex({lower.x, lower.y, h}), lu = mesh.add_vertex({lower.x, upper.y, h}), - ul = mesh.add_vertex({upper.x, lower.y, h}), uu = mesh.add_vertex({upper.x, upper.y, h}); + std::vector vertices; + for (GlobalDistance row = lower.x; row < upper.x; row += GRID_SIZE) { + for (GlobalDistance col = lower.y; col < upper.y; col += GRID_SIZE) { + vertices.push_back(mesh.add_vertex({col, row, h})); + } + } - mesh.add_face(ll, uu, lu); - mesh.add_face(ll, ul, uu); + const auto nrows = static_cast(std::ceil(float(upper.x - lower.x) / GRID_SIZE)); + const auto ncols = static_cast(std::ceil(float(upper.y - lower.y) / GRID_SIZE)); + for (size_t row = 1; row < nrows; ++row) { + for (size_t col = 1; col < ncols; ++col) { + mesh.add_face({ + vertices[ncols * (row - 1) + (col - 1)], + vertices[ncols * (row - 0) + (col - 0)], + vertices[ncols * (row - 0) + (col - 1)], + }); + mesh.add_face({ + vertices[ncols * (row - 1) + (col - 1)], + vertices[ncols * (row - 1) + (col - 0)], + vertices[ncols * (row - 0) + (col - 0)], + }); + } + } mesh.update_vertex_normals_only(); -- cgit v1.2.3 From 68a23b27925142fed3b1e53b2f17ad2c90878e21 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Mon, 12 Feb 2024 23:25:00 +0000 Subject: Add helpers for testing for triangle overlap/containedness --- game/geoData.cpp | 16 ++++++++++++++++ game/geoData.h | 2 ++ 2 files changed, 18 insertions(+) diff --git a/game/geoData.cpp b/game/geoData.cpp index 49cf892..ae43f3f 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -359,3 +359,19 @@ GeoData::update_vertex_normals_only() this->set_normal(vh, 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); +} diff --git a/game/geoData.h b/game/geoData.h index e234bfe..2fd3aa5 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -103,6 +103,8 @@ protected: [[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; void update_vertex_normals_only(); -- cgit v1.2.3 From 849f4aa735352704995ffb51bf23dadf795bb119 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Tue, 13 Feb 2024 01:36:42 +0000 Subject: Include face handle in intersectRay result --- game/geoData.cpp | 8 ++++---- game/geoData.h | 6 ++++-- test/test-geoData.cpp | 2 +- ui/builders/freeExtend.cpp | 6 +++--- ui/builders/straight.cpp | 6 +++--- 5 files changed, 15 insertions(+), 13 deletions(-) diff --git a/game/geoData.cpp b/game/geoData.cpp index ae43f3f..0dbc0ac 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -213,16 +213,16 @@ GeoData::positionAt(const PointFace & p) const return positionOnTriangle(p.point, triangle<3>(p.face(this))); } -[[nodiscard]] std::optional +[[nodiscard]] GeoData::IntersectionResult GeoData::intersectRay(const Ray & ray) const { return intersectRay(ray, findPoint(ray.start)); } -[[nodiscard]] std::optional +[[nodiscard]] GeoData::IntersectionResult GeoData::intersectRay(const Ray & ray, FaceHandle face) const { - std::optional out; + GeoData::IntersectionResult out; walkUntil(PointFace {ray.start, face}, ray.start.xy() + GlobalPosition2D(ray.direction.xy() * RelativePosition2D(upperExtent.xy() - lowerExtent.xy())), @@ -231,7 +231,7 @@ GeoData::intersectRay(const Ray & ray, FaceHandle face) const RelativeDistance dist {}; const auto t = triangle<3>(face); if (ray.intersectTriangle(t.x, t.y, t.z, bari, dist)) { - out = t * bari; + out.emplace(t * bari, face); return true; } return false; diff --git a/game/geoData.h b/game/geoData.h index 2fd3aa5..f599552 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -74,8 +74,10 @@ public: [[nodiscard]] FaceHandle findPoint(GlobalPosition2D, FaceHandle start) const; [[nodiscard]] GlobalPosition3D positionAt(const PointFace &) const; - [[nodiscard]] std::optional intersectRay(const Ray &) const; - [[nodiscard]] std::optional intersectRay(const Ray &, FaceHandle start) const; + using IntersectionLocation = std::pair; + using IntersectionResult = std::optional; + [[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; diff --git a/test/test-geoData.cpp b/test/test-geoData.cpp index efe845c..f8437c3 100644 --- a/test/test-geoData.cpp +++ b/test/test-geoData.cpp @@ -114,7 +114,7 @@ BOOST_DATA_TEST_CASE(findRayIntersect, }), p, d, i) { - BOOST_CHECK_EQUAL(fixedTerrtain.intersectRay({p, d}).value(), i); + BOOST_CHECK_EQUAL(fixedTerrtain.intersectRay({p, d})->first, i); } BOOST_AUTO_TEST_CASE(boundaryWalk) diff --git a/ui/builders/freeExtend.cpp b/ui/builders/freeExtend.cpp index 47356c3..db127e6 100644 --- a/ui/builders/freeExtend.cpp +++ b/ui/builders/freeExtend.cpp @@ -19,7 +19,7 @@ BuilderFreeExtend::move( candidateLinks.objects = network->candidateJoins(*p1, p->pos); } else if (const auto p = geoData->intersectRay(ray)) { - candidateLinks.objects = network->candidateExtend(*p1, *p); + candidateLinks.objects = network->candidateExtend(*p1, p->first); } else { candidateLinks.removeAll(); @@ -42,8 +42,8 @@ BuilderFreeExtend::click( p1 = p->pos; } else if (const auto p = geoData->intersectRay(ray)) { - network->addExtend(*p1, *p); - p1 = *p; + network->addExtend(*p1, p->first); + p1 = p->first; } } else { diff --git a/ui/builders/straight.cpp b/ui/builders/straight.cpp index 0c4a3e2..43f5ec8 100644 --- a/ui/builders/straight.cpp +++ b/ui/builders/straight.cpp @@ -16,7 +16,7 @@ BuilderStraight::move( { if (p1) { if (const auto p = geoData->intersectRay(ray)) { - candidateLinks.objects = network->candidateStraight(*p1, *p); + candidateLinks.objects = network->candidateStraight(*p1, p->first); } else { candidateLinks.removeAll(); @@ -32,12 +32,12 @@ BuilderStraight::click( case SDL_BUTTON_LEFT: if (const auto p = geoData->intersectRay(ray)) { if (p1) { - create(network, *p1, *p); + create(network, *p1, p->first); candidateLinks.removeAll(); p1.reset(); } else { - p1 = p; + p1 = p->first; } } return; -- cgit v1.2.3 From 6535a9c7f4e8fec978c079d45c0349a004b73241 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Wed, 14 Feb 2024 02:04:44 +0000 Subject: Fix getting cartesian coords from triangle baripos --- game/geoData.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/game/geoData.h b/game/geoData.h index f599552..6c6ae26 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -66,7 +66,7 @@ public: { const auto & t {*this}; return t[0] + GlobalPosition(RelativePosition(t[1] - t[0]) * bari.x) - + GlobalPosition(RelativePosition(t[2] - t[1]) * bari.y); + + GlobalPosition(RelativePosition(t[2] - t[0]) * bari.y); } }; -- cgit v1.2.3 From 861c046ed527474a18a1358246a818ce70bb0b75 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Wed, 14 Feb 2024 02:07:04 +0000 Subject: Check ray intersects triangle 'in front' of start --- lib/ray.h | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/lib/ray.h b/lib/ray.h index e1f43c3..67fdd12 100644 --- a/lib/ray.h +++ b/lib/ray.h @@ -47,11 +47,11 @@ public: RelativeDistance & distance) const { if constexpr (std::is_floating_point_v) { - return glm::intersectRayTriangle(start, direction, t0, t1, t2, bary, distance); + return glm::intersectRayTriangle(start, direction, t0, t1, t2, bary, distance) && distance >= 0.F; } else { const RelativePosition3D t0r = t0 - start, t1r = t1 - start, t2r = t2 - start; - return glm::intersectRayTriangle({}, direction, t0r, t1r, t2r, bary, distance); + return glm::intersectRayTriangle({}, direction, t0r, t1r, t2r, bary, distance) && distance >= 0.F; } } -- cgit v1.2.3 From 72b8e6d0b1f9ceb1fc7bd87aa71aa0dd5a15322a Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Thu, 22 Feb 2024 01:09:37 +0000 Subject: Fix calculation of texture coords of terrain While we still use this... --- game/terrain.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/game/terrain.cpp b/game/terrain.cpp index d2c8593..7f59b6c 100644 --- a/game/terrain.cpp +++ b/game/terrain.cpp @@ -34,7 +34,7 @@ Terrain::generateMeshes() [this, &vertexIndex](const GeoData::VertexHandle v) { vertexIndex.emplace(v, vertexIndex.size()); const auto p = geoData->point(v); - return Vertex {p, p / 10000, geoData->normal(v)}; + return Vertex {p, RelativePosition2D(p) / 10000.F, geoData->normal(v)}; }); std::for_each( geoData->faces_begin(), geoData->faces_end(), [this, &vertexIndex, &indices](const GeoData::FaceHandle f) { -- cgit v1.2.3 From 3770b101cfc5ad37a069850b422f0098ade7fc08 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Thu, 22 Feb 2024 01:16:29 +0000 Subject: First cut of terrain deformation This "works" for some definition of works... But it's flawed in many ways, not least the following: * It's glitchy for no obvious reason * It's unreliable; fails if you tweak the parameters * The sides of the modified area are triangulated in the dumbest possible fashion, which results in ill-formed polygons * Probably other things, but... It works, remember... --- game/geoData.cpp | 166 ++++++++++++++++++++++++++++++++++++++++++++++++++ game/geoData.h | 2 + test/test-geoData.cpp | 60 ++++++++++++++++++ 3 files changed, 228 insertions(+) diff --git a/game/geoData.cpp b/game/geoData.cpp index 0dbc0ac..86b9152 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -1,7 +1,10 @@ #include "geoData.h" +#include "collections.h" #include #include +#include #include +#include GeoData GeoData::loadFromAsciiGrid(const std::filesystem::path & input) @@ -375,3 +378,166 @@ GeoData::triangleContainsTriangle(const Triangle<2> & a, const Triangle<2> & b) { return triangleContainsPoint(a.x, b) && triangleContainsPoint(a.y, b) && triangleContainsPoint(a.z, b); } + +void +GeoData::setHeights(const std::span triangleStrip) +{ + std::set nosplit; + // Create new vertices + std::vector newVerts; + newVerts.reserve(newVerts.size()); + std::transform(triangleStrip.begin(), triangleStrip.end(), std::back_inserter(newVerts), [this](const auto tsVert) { + return add_vertex(tsVert); + }); + // Create new faces + std::vector newFaces; + newFaces.reserve(newVerts.size() - 2); + std::transform(strip_begin(newVerts), strip_end(newVerts), std::back_inserter(newFaces), + [this, &nosplit](const auto & newVert) { + const auto [a, b, c] = newVert; + auto faceHandle = add_face(a, b, c); + std::copy(fe_begin(faceHandle), fe_end(faceHandle), std::inserter(nosplit, nosplit.end())); + return faceHandle; + }); + std::vector boundary; + boundaryWalk( + [out = std::back_inserter(boundary)](const auto boundaryHeh) mutable { + out = boundaryHeh; + }, + *voh_begin(newVerts.front())); + + // Extrude corners + std::set cutpoints; + std::vector> extrusionExtents; + std::vector extrusionVertices; + std::transform(boundary.begin(), boundary.end(), std::back_inserter(extrusionExtents), + [this, &nosplit, &cutpoints, &extrusionVertices](const auto boundaryHeh) { + const auto vectorNormal + = [](const glm::vec<2, T, Q> & v) -> glm::vec<2, T, Q> { + return {-v.y, v.x}; + }; + + const auto p0 = point(from_vertex_handle(prev_halfedge_handle(boundaryHeh))); + const auto p1 = point(from_vertex_handle(boundaryHeh)); + const auto p2 = point(to_vertex_handle(boundaryHeh)); + const auto e0 = glm::normalize(vectorNormal(RelativePosition2D(p1 - p0))); + const auto e1 = glm::normalize(vectorNormal(RelativePosition2D(p2 - p1))); + const auto mid = glm::normalize((e0 + e1) / 2.F); + const auto doExtrusion = [mid, p1, this, &nosplit, &cutpoints, &extrusionVertices]( + RelativeDistance vert, GlobalDistance limit) { + const auto extrusionDir = glm::normalize(mid || vert); + + if (const auto intersect = intersectRay({p1, extrusionDir})) { + auto splitVertex = split(intersect->second, intersect->first); + cutpoints.insert(splitVertex); + extrusionVertices.push_back(splitVertex); + std::copy(ve_begin(splitVertex), ve_end(splitVertex), std::inserter(nosplit, nosplit.end())); + } + + const auto extrusion + = extrusionDir * std::max(0.F, RelativeDistance(limit - p1.z) / extrusionDir.z); + return p1 + GlobalPosition3D(extrusion); + }; + return std::make_pair(doExtrusion(-2, lowerExtent.z - 100), doExtrusion(2, upperExtent.z + 100)); + }); + + // Cut existing terrain + extrusionExtents.emplace_back(extrusionExtents.front()); // Circular next + extrusionVertices.emplace_back(extrusionVertices.front()); + std::vector> boundaryFaces; + std::transform(boundary.begin(), boundary.end(), std ::back_inserter(boundaryFaces), + [ex = extrusionExtents.begin(), exv = extrusionVertices.begin(), this, &nosplit]( + const auto boundaryHeh) mutable { + const auto fromVertex = from_vertex_handle(boundaryHeh); + const auto p0 = point(fromVertex); + auto toVertex = to_vertex_handle(boundaryHeh); + const auto p1 = point(toVertex); + const auto nex = ex + 1; + const auto nexv = exv + 1; + const std::array, 4> triangles {{ + {p0, ex->first, nex->first}, + {p0, p1, nex->first}, + {p0, ex->second, nex->second}, + {p0, p1, nex->second}, + }}; + + std::vector sideVerts {fromVertex, *exv}; + for (auto currentVertex = *exv; + std::any_of(voh_begin(currentVertex), voh_end(currentVertex), [&](const auto currentVertexOut) { + const auto next = next_halfedge_handle(currentVertexOut); + const auto nextVertex = to_vertex_handle(next); + const auto startVertex = from_vertex_handle(next); + if (nextVertex == *++sideVerts.rbegin()) { + // This half edge goes back to the previous vertex + return false; + } + if (nextVertex == *nexv) { + // The next half edge goes to the termination point + return false; + } + const auto edge = edge_handle(next); + if (nosplit.contains(edge)) { + // This edge should not be split (for some reason, maybe no longer applies) + return false; + } + const auto ep0 = point(startVertex); + const auto ep1 = point(nextVertex); + const auto diff = RelativePosition3D(ep1 - ep0); + const auto length = glm::length(diff); + const auto dir = diff / length; + const Ray r {ep0, dir}; + return std::any_of(triangles.begin(), triangles.end(), [&](const auto & triangle) { + BaryPosition bary; + RelativeDistance dist {}; + + if (r.intersectTriangle(triangle.x, triangle.y, triangle.z, bary, dist) + && dist <= length - 1 && dist >= 1) { + const auto splitPos = triangle * bary; + currentVertex = sideVerts.emplace_back(split(edge, splitPos)); + return true; + } + return false; + }); + });) { + ; + } + sideVerts.emplace_back(*nexv); + sideVerts.emplace_back(toVertex); + ex = nex; + exv++; + return sideVerts; + }); + + // Remove old faces + std::set visited; + auto removeOld = [&](auto & self, const auto face) -> void { + if (visited.insert(face).second) { + std::vector neighbourFaces; + std::for_each(fh_begin(face), fh_end(face), [&](const auto fh) { + if (std::none_of(boundaryFaces.begin(), boundaryFaces.end(), [fh, this](const auto & bf) { + return std::find(bf.begin(), bf.end(), from_vertex_handle(fh)) != bf.end() + && std::find(bf.begin(), bf.end(), to_vertex_handle(fh)) != bf.end(); + })) { + neighbourFaces.emplace_back(opposite_face_handle(fh)); + } + }); + + delete_face(face, false); + std::for_each(neighbourFaces.begin(), neighbourFaces.end(), [&self](const auto nextFace) { + if (nextFace.is_valid()) { + self(self, nextFace); + } + }); + } + }; + removeOld(removeOld, findPoint(triangleStrip.front())); + + std::for_each(boundaryFaces.begin(), boundaryFaces.end(), [&](auto & boundaryFace) { + std::reverse(boundaryFace.begin(), boundaryFace.end()); + add_face(boundaryFace); + }); + + // Tidy up + garbage_collection(); + update_vertex_normals_only(); +} diff --git a/game/geoData.h b/game/geoData.h index 6c6ae26..4d8e11c 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -89,6 +89,8 @@ public: [[nodiscard]] HalfedgeHandle findEntry(const GlobalPosition2D from, const GlobalPosition2D to) const; + void setHeights(const std::span triangleStrip); + [[nodiscard]] auto getExtents() const { diff --git a/test/test-geoData.cpp b/test/test-geoData.cpp index f8437c3..6602b05 100644 --- a/test/test-geoData.cpp +++ b/test/test-geoData.cpp @@ -1,7 +1,12 @@ #define BOOST_TEST_MODULE terrain +#include "game/terrain.h" +#include "test/testMainWindow.h" +#include "test/testRenderOutput.h" #include "testHelpers.h" +#include "ui/applicationBase.h" #include #include +#include #include #include @@ -199,3 +204,58 @@ BOOST_DATA_TEST_CASE(findEntries, { BOOST_CHECK_EQUAL(fixedTerrtain.findEntry(from, to).idx(), heh); } + +BOOST_AUTO_TEST_CASE(setTriangle, *boost::unit_test::timeout(5)) +{ + auto gd = std::make_shared(GeoData::createFlat({0, 0}, {1000000, 1000000}, 100)); + std::array points { + GlobalPosition3D {70100, 123000, 6000}, + GlobalPosition3D {50100, 52300, 6000}, + GlobalPosition3D {191000, 283000, 8000}, + GlobalPosition3D {241000, 123330, -2000}, + }; + BOOST_CHECK_NO_THROW(gd->setHeights(points)); + + ApplicationBase ab; + TestMainWindow tmw; + TestRenderOutput tro {{1792, 1024}}; + + SceneRenderer ss {tro.size, tro.output}; + ss.camera.setView({-90000, -90000, 300000}, glm::normalize(glm::vec3 {1, 1, -1.5F})); + + struct TestTerrain : public SceneProvider { + explicit TestTerrain(std::shared_ptr gd) : terrain(std::move(gd)) { } + + const Terrain terrain; + + void + content(const SceneShader & shader) const override + { + glPolygonMode(GL_FRONT_AND_BACK, GL_LINE); + terrain.render(shader); + glPolygonMode(GL_FRONT_AND_BACK, GL_FILL); + } + + void + environment(const SceneShader &, const SceneRenderer & sr) const override + { + sr.setAmbientLight({0.1, 0.1, 0.1}); + sr.setDirectionalLight({1, 1, 1}, south + down, *this); + } + + void + lights(const SceneShader &) const override + { + } + + void + shadows(const ShadowMapper & shadowMapper) const override + { + terrain.shadows(shadowMapper); + } + }; + + TestTerrain t {gd}; + BOOST_CHECK_NO_THROW(ss.render(t)); + Texture::save(tro.outImage, "/tmp/geoData.tga"); +} -- cgit v1.2.3 From 0d706975e88125c4468bb3468024e1b9d946401e Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 24 Feb 2024 02:08:12 +0000 Subject: Remove the nosplit list Not required now we don't randomly wonder into the new edges range --- game/geoData.cpp | 46 +++++++++++++++++++--------------------------- 1 file changed, 19 insertions(+), 27 deletions(-) diff --git a/game/geoData.cpp b/game/geoData.cpp index 1f6768a..8c635a0 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -381,8 +381,7 @@ GeoData::triangleContainsTriangle(const Triangle<2> & a, const Triangle<2> & b) void GeoData::setHeights(const std::span triangleStrip) { - std::set nosplit; - // Create new vertices + // Create new vertices std::vector newVerts; newVerts.reserve(newVerts.size()); std::transform(triangleStrip.begin(), triangleStrip.end(), std::back_inserter(newVerts), [this](const auto tsVert) { @@ -391,11 +390,10 @@ GeoData::setHeights(const std::span triangleStrip) // Create new faces std::vector newFaces; newFaces.reserve(newVerts.size() - 2); - std::transform(strip_begin(newVerts), strip_end(newVerts), std::back_inserter(newFaces), - [this, &nosplit](const auto & newVert) { + std::transform( + strip_begin(newVerts), strip_end(newVerts), std::back_inserter(newFaces), [this](const auto & newVert) { const auto [a, b, c] = newVert; auto faceHandle = add_face(a, b, c); - std::copy(fe_begin(faceHandle), fe_end(faceHandle), std::inserter(nosplit, nosplit.end())); return faceHandle; }); std::vector boundary; @@ -410,7 +408,7 @@ GeoData::setHeights(const std::span triangleStrip) std::vector> extrusionExtents; std::vector extrusionVertices; std::transform(boundary.begin(), boundary.end(), std::back_inserter(extrusionExtents), - [this, &nosplit, &cutpoints, &extrusionVertices](const auto boundaryHeh) { + [this, &cutpoints, &extrusionVertices](const auto boundaryHeh) { const auto vectorNormal = [](const glm::vec<2, T, Q> & v) -> glm::vec<2, T, Q> { return {-v.y, v.x}; @@ -422,21 +420,20 @@ GeoData::setHeights(const std::span triangleStrip) const auto e0 = glm::normalize(vectorNormal(RelativePosition2D(p1 - p0))); const auto e1 = glm::normalize(vectorNormal(RelativePosition2D(p2 - p1))); const auto mid = glm::normalize((e0 + e1) / 2.F); - const auto doExtrusion = [mid, p1, this, &nosplit, &cutpoints, &extrusionVertices]( - RelativeDistance vert, GlobalDistance limit) { - const auto extrusionDir = glm::normalize(mid || vert); - - if (const auto intersect = intersectRay({p1, extrusionDir})) { - auto splitVertex = split(intersect->second, intersect->first); - cutpoints.insert(splitVertex); - extrusionVertices.push_back(splitVertex); - std::copy(ve_begin(splitVertex), ve_end(splitVertex), std::inserter(nosplit, nosplit.end())); - } - - const auto extrusion - = extrusionDir * std::max(0.F, RelativeDistance(limit - p1.z) / extrusionDir.z); - return p1 + extrusion; - }; + const auto doExtrusion + = [mid, p1, this, &cutpoints, &extrusionVertices](RelativeDistance vert, GlobalDistance limit) { + const auto extrusionDir = glm::normalize(mid || vert); + + if (const auto intersect = intersectRay({p1, extrusionDir})) { + auto splitVertex = split(intersect->second, intersect->first); + cutpoints.insert(splitVertex); + extrusionVertices.push_back(splitVertex); + } + + const auto extrusion + = extrusionDir * std::max(0.F, RelativeDistance(limit - p1.z) / extrusionDir.z); + return p1 + extrusion; + }; return std::make_pair(doExtrusion(-2, lowerExtent.z - 100), doExtrusion(2, upperExtent.z + 100)); }); @@ -445,8 +442,7 @@ GeoData::setHeights(const std::span triangleStrip) extrusionVertices.emplace_back(extrusionVertices.front()); std::vector> boundaryFaces; std::transform(boundary.begin(), boundary.end(), std ::back_inserter(boundaryFaces), - [ex = extrusionExtents.begin(), exv = extrusionVertices.begin(), this, &nosplit]( - const auto boundaryHeh) mutable { + [ex = extrusionExtents.begin(), exv = extrusionVertices.begin(), this](const auto boundaryHeh) mutable { const auto fromVertex = from_vertex_handle(boundaryHeh); const auto p0 = point(fromVertex); auto toVertex = to_vertex_handle(boundaryHeh); @@ -475,10 +471,6 @@ GeoData::setHeights(const std::span triangleStrip) return false; } const auto edge = edge_handle(next); - if (nosplit.contains(edge)) { - // This edge should not be split (for some reason, maybe no longer applies) - return false; - } const auto ep0 = point(startVertex); const auto ep1 = point(nextVertex); const auto diff = RelativePosition3D(ep1 - ep0); -- cgit v1.2.3 From 848fc7fe1349c36c839b3642f9607ba80ffe4e8e Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Mon, 26 Feb 2024 01:42:26 +0000 Subject: Make terrain deformation test a data test Easily test multiple deformations and view them from different angles --- test/test-geoData.cpp | 48 +++++++++++++++++++++++++++++++++++------------- 1 file changed, 35 insertions(+), 13 deletions(-) diff --git a/test/test-geoData.cpp b/test/test-geoData.cpp index ac1d668..e1f8fce 100644 --- a/test/test-geoData.cpp +++ b/test/test-geoData.cpp @@ -205,23 +205,41 @@ BOOST_DATA_TEST_CASE(findEntries, BOOST_CHECK_EQUAL(fixedTerrtain.findEntry(from, to).idx(), heh); } -BOOST_AUTO_TEST_CASE(setTriangle, *boost::unit_test::timeout(5)) +using DeformTerrainData + = std::tuple, std::vector, const char *>>>; + +template +std::ostream & +operator<<(std::ostream & s, const Ray & ray) +{ + return s << "Ray" << std::make_pair(ray.start, ray.direction); +} + +BOOST_DATA_TEST_CASE(setTriangle, + boost::unit_test::data::make({ + {{ + {70100, 123000, 6000}, + {50100, 52300, 6000}, + {191000, 283000, 8000}, + {241000, 123330, -2000}, + }, + { + {{{20000, 20000, 90000}, glm::normalize(Direction3D {1, 1, -1.5F})}, + "/tmp/geoData0.tga"}, + {{{30000, 164000, 90000}, glm::normalize(Direction3D {1, -1, -1.5F})}, + "/tmp/geoData1.tga"}, + {{{288000, 162000, 90000}, glm::normalize(Direction3D {-1, -1, -1.5F})}, + "/tmp/geoData2.tga"}, + }}, + }), + points, cams) { auto gd = std::make_shared(GeoData::createFlat({0, 0}, {1000000, 1000000}, 100)); - std::array points { - GlobalPosition3D {70100, 123000, 6000}, - GlobalPosition3D {50100, 52300, 6000}, - GlobalPosition3D {191000, 283000, 8000}, - GlobalPosition3D {241000, 123330, -2000}, - }; BOOST_CHECK_NO_THROW(gd->setHeights(points)); ApplicationBase ab; TestMainWindow tmw; - TestRenderOutput tro {{1792, 1024}}; - - SceneRenderer ss {tro.size, tro.output}; - ss.camera.setView({-90000, -90000, 300000}, glm::normalize(glm::vec3 {1, 1, -1.5F})); + TestRenderOutput tro {{640, 480}}; struct TestTerrain : public SceneProvider { explicit TestTerrain(std::shared_ptr gd) : terrain(std::move(gd)) { } @@ -256,6 +274,10 @@ BOOST_AUTO_TEST_CASE(setTriangle, *boost::unit_test::timeout(5)) }; TestTerrain t {gd}; - BOOST_CHECK_NO_THROW(ss.render(t)); - Texture::save(tro.outImage, "/tmp/geoData.tga"); + SceneRenderer ss {tro.size, tro.output}; + std::for_each(cams.begin(), cams.end(), [&ss, &t, &tro](const auto & cam) { + ss.camera.setView(cam.first.start, cam.first.direction); + BOOST_CHECK_NO_THROW(ss.render(t)); + Texture::save(tro.outImage, cam.second); + }); } -- cgit v1.2.3 From 52fe8fddaf36fe3c1472fa04c1bed0da848770ac Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Mon, 26 Feb 2024 22:18:48 +0000 Subject: Support extra arguments in SelectionV::make_s --- lib/persistence.h | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/lib/persistence.h b/lib/persistence.h index c53ff99..75f578e 100644 --- a/lib/persistence.h +++ b/lib/persistence.h @@ -81,11 +81,11 @@ namespace Persistence { return make_s>(value); } - template + template [[nodiscard]] static SelectionPtr - make_s(T & value) + make_s(T & value, Extra &&... extra) { - return std::make_unique(value); + return std::make_unique(value, std::forward(extra)...); } T & v; -- cgit v1.2.3 From 1511e3f3faadc61b462577ccc9c740157982b867 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Mon, 26 Feb 2024 22:26:10 +0000 Subject: Add read persistence support for tuple and pair --- lib/persistence.h | 59 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 59 insertions(+) diff --git a/lib/persistence.h b/lib/persistence.h index 75f578e..3c95a00 100644 --- a/lib/persistence.h +++ b/lib/persistence.h @@ -331,6 +331,65 @@ namespace Persistence { } }; + template struct SelectionT> : public SelectionV> { + using V = std::tuple; + using SelectionV::SelectionV; + + struct Members : public SelectionV { + template + explicit Members(V & v, std::integer_sequence) : + SelectionV {v}, members {SelectionV>::make(std::get(v))...} + { + } + + void + beforeValue(Stack & stk) override + { + stk.push(std::move(members[idx++])); + } + + std::size_t idx {0}; + std::array> members; + }; + + void + beginArray(Stack & stk) override + { + stk.push(this->template make_s( + this->v, std::make_integer_sequence>())); + } + }; + + template struct SelectionT> : public SelectionV> { + using V = std::pair; + using SelectionV::SelectionV; + + struct Members : public SelectionV { + explicit Members(V & v) : + SelectionV {v}, members { + SelectionV::make(v.first), + SelectionV::make(v.second), + } + { + } + + void + beforeValue(Stack & stk) override + { + stk.push(std::move(members[idx++])); + } + + std::size_t idx {0}; + std::array members; + }; + + void + beginArray(Stack & stk) override + { + stk.push(this->template make_s(this->v)); + } + }; + template struct MapByMember : public Persistence::SelectionT { MapByMember(Map & m) : Persistence::SelectionT {s}, map {m} { } -- cgit v1.2.3 From 6c13527020d65c410ee8daef18ee8273cdf8e827 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Mon, 26 Feb 2024 22:48:37 +0000 Subject: Add helper for loading fixtures for data tests from fixture JSON --- test/testHelpers.h | 11 +++++++++++ 1 file changed, 11 insertions(+) diff --git a/test/testHelpers.h b/test/testHelpers.h index f2b0901..58e4372 100644 --- a/test/testHelpers.h +++ b/test/testHelpers.h @@ -2,11 +2,22 @@ #include #include +#include +#include #include // IWYU pragma: keep std::setprecision +#include #include std::unique_ptr uasprintf(const char * fmt, ...) __attribute__((format(printf, 1, 2))); +template +decltype(auto) +loadFixtureJson(const std::filesystem::path & path) +{ + std::ifstream in {FIXTURESDIR / path}; + return Persistence::JsonParsePersistence {}.loadState>(in); +} + #define BOOST_CHECK_CLOSE_VEC(a_, b_) \ { \ const auto a {a_}, b {b_}; \ -- cgit v1.2.3 From aa07f1bdd607a6dead9cdec59ff950f6e9a5c28c Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Mon, 26 Feb 2024 23:47:39 +0000 Subject: Load terrain deform fixture data from JSON --- test/Jamfile.jam | 2 +- test/fixtures/geoData/deform/1.json | 73 +++++++++++++++++++++++++++++++++++++ test/test-geoData.cpp | 34 +++-------------- 3 files changed, 79 insertions(+), 30 deletions(-) create mode 100644 test/fixtures/geoData/deform/1.json diff --git a/test/Jamfile.jam b/test/Jamfile.jam index 733ef05..1b07b5a 100644 --- a/test/Jamfile.jam +++ b/test/Jamfile.jam @@ -46,7 +46,7 @@ lib test : [ glob *.cpp : test-*.cpp perf-*.cpp ] ; run test-collection.cpp ; run test-maths.cpp ; run test-lib.cpp ; -run test-geoData.cpp : -- : fixtures/height/SD19.asc : test ; +run test-geoData.cpp : -- : [ sequence.insertion-sort [ glob-tree $(fixtures)/geoData : *.json ] fixtures/height/SD19.asc ] : test ; run test-network.cpp : : : test ; run test-persistence.cpp : -- : [ sequence.insertion-sort [ glob-tree $(fixtures)/json : *.json ] ] : test ; run test-text.cpp : -- : test-glContainer : test ; diff --git a/test/fixtures/geoData/deform/1.json b/test/fixtures/geoData/deform/1.json new file mode 100644 index 0000000..33ac86d --- /dev/null +++ b/test/fixtures/geoData/deform/1.json @@ -0,0 +1,73 @@ +[ + [ + [ + [ + 70100, + 123000, + 6000 + ], + [ + 50100, + 52300, + 6000 + ], + [ + 191000, + 283000, + 8000 + ], + [ + 241000, + 123330, + -2000 + ] + ], + [ + [ + [ + [ + 20000, + 20000, + 90000 + ], + [ + 1, + 1, + -1.5 + ] + ], + "/tmp/geoData0.tga" + ], + [ + [ + [ + 30000, + 164000, + 90000 + ], + [ + 1, + -1, + -1.5 + ] + ], + "/tmp/geoData1.tga" + ], + [ + [ + [ + 288000, + 162000, + 90000 + ], + [ + -1, + -1, + -1.5 + ] + ], + "/tmp/geoData2.tga" + ] + ] + ] +] diff --git a/test/test-geoData.cpp b/test/test-geoData.cpp index e1f8fce..36d008b 100644 --- a/test/test-geoData.cpp +++ b/test/test-geoData.cpp @@ -205,34 +205,10 @@ BOOST_DATA_TEST_CASE(findEntries, BOOST_CHECK_EQUAL(fixedTerrtain.findEntry(from, to).idx(), heh); } -using DeformTerrainData - = std::tuple, std::vector, const char *>>>; +using DeformTerrainData = std::tuple, + std::vector, std::string>>>; -template -std::ostream & -operator<<(std::ostream & s, const Ray & ray) -{ - return s << "Ray" << std::make_pair(ray.start, ray.direction); -} - -BOOST_DATA_TEST_CASE(setTriangle, - boost::unit_test::data::make({ - {{ - {70100, 123000, 6000}, - {50100, 52300, 6000}, - {191000, 283000, 8000}, - {241000, 123330, -2000}, - }, - { - {{{20000, 20000, 90000}, glm::normalize(Direction3D {1, 1, -1.5F})}, - "/tmp/geoData0.tga"}, - {{{30000, 164000, 90000}, glm::normalize(Direction3D {1, -1, -1.5F})}, - "/tmp/geoData1.tga"}, - {{{288000, 162000, 90000}, glm::normalize(Direction3D {-1, -1, -1.5F})}, - "/tmp/geoData2.tga"}, - }}, - }), - points, cams) +BOOST_DATA_TEST_CASE(deform, loadFixtureJson("geoData/deform/1.json"), points, cams) { auto gd = std::make_shared(GeoData::createFlat({0, 0}, {1000000, 1000000}, 100)); BOOST_CHECK_NO_THROW(gd->setHeights(points)); @@ -276,8 +252,8 @@ BOOST_DATA_TEST_CASE(setTriangle, TestTerrain t {gd}; SceneRenderer ss {tro.size, tro.output}; std::for_each(cams.begin(), cams.end(), [&ss, &t, &tro](const auto & cam) { - ss.camera.setView(cam.first.start, cam.first.direction); + ss.camera.setView(cam.first.first, glm::normalize(cam.first.second)); BOOST_CHECK_NO_THROW(ss.render(t)); - Texture::save(tro.outImage, cam.second); + Texture::save(tro.outImage, cam.second.c_str()); }); } -- cgit v1.2.3 From 421ae75fa94a05b71c03255af4ad597a60fc8ed9 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Fri, 8 Mar 2024 01:17:11 +0000 Subject: Rework stream support to work with any collection --- lib/stream_support.h | 16 ++++------------ test/test-static-stream_support.cpp | 21 +++++++++++++++------ 2 files changed, 19 insertions(+), 18 deletions(-) diff --git a/lib/stream_support.h b/lib/stream_support.h index fa536f1..57d82a1 100644 --- a/lib/stream_support.h +++ b/lib/stream_support.h @@ -11,17 +11,16 @@ template concept stringlike = requires(const S & s) { s.substr(0); }; template -concept spanable = std::is_constructible_v, T> && !stringlike - && !std::is_same_v, T>; +concept NonStringIterableCollection + = std::is_same_v().begin()), decltype(std::declval().end())> && !stringlike; namespace std { - template std::ostream & - operator<<(std::ostream & s, const span v) + operator<<(std::ostream & s, const NonStringIterableCollection auto & v) { s << '('; for (const auto & i : v) { - if (&i != &v.front()) { + if (&i != &*v.begin()) { s << ", "; } s << i; @@ -43,13 +42,6 @@ namespace std { return (s << std::span {&v[0], L}); } - template - std::ostream & - operator<<(std::ostream & s, const T & v) - { - return (s << std::span {v}); - } - template std::ostream & operator<<(std::ostream & s, const std::pair & v) diff --git a/test/test-static-stream_support.cpp b/test/test-static-stream_support.cpp index 3002ccc..6bf9ea4 100644 --- a/test/test-static-stream_support.cpp +++ b/test/test-static-stream_support.cpp @@ -1,11 +1,20 @@ #include "stream_support.h" #include +#include +#include #include -static_assert(spanable>); -static_assert(spanable>); -static_assert(spanable>); -static_assert(spanable>); -static_assert(!spanable); -static_assert(!spanable); +static_assert(NonStringIterableCollection>); +static_assert(NonStringIterableCollection>); +static_assert(NonStringIterableCollection>); +static_assert(NonStringIterableCollection>); +static_assert(NonStringIterableCollection>); +static_assert(NonStringIterableCollection>); +static_assert(!NonStringIterableCollection); +static_assert(!NonStringIterableCollection); + +static_assert(requires(std::vector i, std::ostream & o) { o << i; }); +static_assert(requires(std::array i, std::ostream & o) { o << i; }); +static_assert(requires(std::set i, std::ostream & o) { o << i; }); +static_assert(requires(std::map i, std::ostream & o) { o << i; }); -- cgit v1.2.3 From e7e30f489171a8f3a019f8ca35d691938e546e7b Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Fri, 8 Mar 2024 01:19:22 +0000 Subject: Bail out early if the input does not define an area --- game/geoData.cpp | 4 ++++ 1 file changed, 4 insertions(+) diff --git a/game/geoData.cpp b/game/geoData.cpp index 8c635a0..9a08a89 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -381,6 +381,10 @@ GeoData::triangleContainsTriangle(const Triangle<2> & a, const Triangle<2> & b) void GeoData::setHeights(const std::span triangleStrip) { + if (triangleStrip.size() < 3) { + return; + } + // Create new vertices std::vector newVerts; newVerts.reserve(newVerts.size()); -- cgit v1.2.3 From 567477ab8b4b09111d942039c4b2587b25fc2fe2 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Fri, 8 Mar 2024 20:41:37 +0000 Subject: Rewrite most of setHeights Accounts for sensible corners and fixes quite a few bugs and edge cases... introduces a few more, is still a bit glitchy in places --- game/geoData.cpp | 236 ++++++++++++++++++++---------------- test/fixtures/geoData/deform/1.json | 53 +++++++- 2 files changed, 186 insertions(+), 103 deletions(-) diff --git a/game/geoData.cpp b/game/geoData.cpp index 9a08a89..ac2f035 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -2,7 +2,6 @@ #include "collections.h" #include #include -#include #include #include @@ -381,6 +380,8 @@ GeoData::triangleContainsTriangle(const Triangle<2> & a, const Triangle<2> & b) void GeoData::setHeights(const std::span triangleStrip) { + static const RelativeDistance MAX_SLOPE = 1.5F; + if (triangleStrip.size() < 3) { return; } @@ -391,7 +392,7 @@ GeoData::setHeights(const std::span triangleStrip) std::transform(triangleStrip.begin(), triangleStrip.end(), std::back_inserter(newVerts), [this](const auto tsVert) { return add_vertex(tsVert); }); - // Create new faces + // Create new faces std::vector newFaces; newFaces.reserve(newVerts.size() - 2); std::transform( @@ -408,121 +409,152 @@ GeoData::setHeights(const std::span triangleStrip) *voh_begin(newVerts.front())); // Extrude corners - std::set cutpoints; - std::vector> extrusionExtents; - std::vector extrusionVertices; - std::transform(boundary.begin(), boundary.end(), std::back_inserter(extrusionExtents), - [this, &cutpoints, &extrusionVertices](const auto boundaryHeh) { - const auto vectorNormal - = [](const glm::vec<2, T, Q> & v) -> glm::vec<2, T, Q> { - return {-v.y, v.x}; - }; - - const auto p0 = point(from_vertex_handle(prev_halfedge_handle(boundaryHeh))); - const auto p1 = point(from_vertex_handle(boundaryHeh)); - const auto p2 = point(to_vertex_handle(boundaryHeh)); - const auto e0 = glm::normalize(vectorNormal(RelativePosition2D(p1 - p0))); - const auto e1 = glm::normalize(vectorNormal(RelativePosition2D(p2 - p1))); - const auto mid = glm::normalize((e0 + e1) / 2.F); - const auto doExtrusion - = [mid, p1, this, &cutpoints, &extrusionVertices](RelativeDistance vert, GlobalDistance limit) { - const auto extrusionDir = glm::normalize(mid || vert); - - if (const auto intersect = intersectRay({p1, extrusionDir})) { - auto splitVertex = split(intersect->second, intersect->first); - cutpoints.insert(splitVertex); - extrusionVertices.push_back(splitVertex); - } - - const auto extrusion - = extrusionDir * std::max(0.F, RelativeDistance(limit - p1.z) / extrusionDir.z); - return p1 + extrusion; - }; - return std::make_pair(doExtrusion(-2, lowerExtent.z - 100), doExtrusion(2, upperExtent.z + 100)); - }); + struct Extrusion { + VertexHandle boundaryVertex, extrusionVertex; + GlobalPosition3D lowerLimit, upperLimit; + }; + + std::vector extrusionExtents; + std::for_each(boundary.begin(), boundary.end(), [this, &extrusionExtents](const auto boundaryHeh) { + const auto vectorNormal = [](const glm::vec<2, T, Q> & v) -> glm::vec<2, T, Q> { + return {-v.y, v.x}; + }; + + const auto boundaryVertex = from_vertex_handle(boundaryHeh); + const auto p0 = point(from_vertex_handle(prev_halfedge_handle(boundaryHeh))); + const auto p1 = point(boundaryVertex); + const auto p2 = point(to_vertex_handle(boundaryHeh)); + const auto e0 = glm::normalize(vectorNormal(RelativePosition2D(p1 - p0))); + const auto e1 = glm::normalize(vectorNormal(RelativePosition2D(p2 - p1))); + + const auto doExtrusion = [this](VertexHandle & extrusionVertex, Direction2D direction, + GlobalPosition3D boundaryVertex, RelativeDistance vert, GlobalDistance limit) { + const auto extrusionDir = glm::normalize(direction || vert); + + if (!extrusionVertex.is_valid()) { + if (const auto intersect = intersectRay({boundaryVertex, extrusionDir})) { + auto splitVertex = split(intersect->second, intersect->first); + extrusionVertex = splitVertex; + } + else if (const auto intersect + = intersectRay({boundaryVertex + GlobalPosition3D {1, 1, 0}, extrusionDir})) { + auto splitVertex = split(intersect->second, intersect->first); + extrusionVertex = splitVertex; + } + else if (const auto intersect + = intersectRay({boundaryVertex + GlobalPosition3D {1, 0, 0}, extrusionDir})) { + auto splitVertex = split(intersect->second, intersect->first); + extrusionVertex = splitVertex; + } + } + + const auto extrusion + = extrusionDir * std::max(0.F, RelativeDistance(limit - boundaryVertex.z) / extrusionDir.z); + return boundaryVertex + extrusion; + }; + // Previous half edge end to current half end start arc tangents + const Arc arc {p1, p1 + (e0 || 0.F), p1 + (e1 || 0.F)}; + const auto limit = std::floor((arc.second - arc.first) * 5.F / pi); + const auto inc = (arc.second - arc.first) / limit; + for (float step = 1; step < limit; step += 1.F) { + const auto direction = sincosf(arc.first + (step * inc)); + VertexHandle extrusionVertex; + extrusionExtents.emplace_back(boundaryVertex, extrusionVertex, + doExtrusion(extrusionVertex, direction, p1, -MAX_SLOPE, lowerExtent.z - 10), + doExtrusion(extrusionVertex, direction, p1, MAX_SLOPE, upperExtent.z + 10)); + assert(extrusionVertex.is_valid()); + } + // Half edge start/end tangents + for (const auto p : {p1, p2}) { + VertexHandle extrusionVertex; + extrusionExtents.emplace_back(boundaryVertex, extrusionVertex, + doExtrusion(extrusionVertex, e1, p, -MAX_SLOPE, lowerExtent.z - 10), + doExtrusion(extrusionVertex, e1, p, MAX_SLOPE, upperExtent.z + 10)); + assert(extrusionVertex.is_valid()); + } + }); - // Cut existing terrain + // Cut existing terrain extrusionExtents.emplace_back(extrusionExtents.front()); // Circular next - extrusionVertices.emplace_back(extrusionVertices.front()); std::vector> boundaryFaces; - std::transform(boundary.begin(), boundary.end(), std ::back_inserter(boundaryFaces), - [ex = extrusionExtents.begin(), exv = extrusionVertices.begin(), this](const auto boundaryHeh) mutable { - const auto fromVertex = from_vertex_handle(boundaryHeh); - const auto p0 = point(fromVertex); - auto toVertex = to_vertex_handle(boundaryHeh); - const auto p1 = point(toVertex); - const auto nex = ex + 1; - const auto nexv = exv + 1; - const std::array, 4> triangles {{ - {p0, ex->first, nex->first}, - {p0, p1, nex->first}, - {p0, ex->second, nex->second}, - {p0, p1, nex->second}, - }}; - - std::vector sideVerts {fromVertex, *exv}; - for (auto currentVertex = *exv; - std::any_of(voh_begin(currentVertex), voh_end(currentVertex), [&](const auto currentVertexOut) { - const auto next = next_halfedge_handle(currentVertexOut); - const auto nextVertex = to_vertex_handle(next); - const auto startVertex = from_vertex_handle(next); - if (nextVertex == *++sideVerts.rbegin()) { - // This half edge goes back to the previous vertex - return false; - } - if (nextVertex == *nexv) { - // The next half edge goes to the termination point - return false; - } - const auto edge = edge_handle(next); - const auto ep0 = point(startVertex); - const auto ep1 = point(nextVertex); - const auto diff = RelativePosition3D(ep1 - ep0); - const auto length = glm::length(diff); - const auto dir = diff / length; - const Ray r {ep0, dir}; - return std::any_of(triangles.begin(), triangles.end(), [&](const auto & triangle) { - BaryPosition bary; - RelativeDistance dist {}; - - if (r.intersectTriangle(triangle.x, triangle.y, triangle.z, bary, dist) - && dist <= length - 1 && dist >= 1) { - const auto splitPos = triangle * bary; - currentVertex = sideVerts.emplace_back(split(edge, splitPos)); - return true; - } - return false; - }); - });) { + std::adjacent_find(extrusionExtents.begin(), extrusionExtents.end(), + [this, &boundaryFaces](const auto & first, const auto & second) { + const auto p0 = point(first.boundaryVertex); + std::vector> triangles { + {p0, first.lowerLimit, second.lowerLimit}, {p0, first.upperLimit, second.upperLimit}}; + const auto p1 = point(second.boundaryVertex); + if (first.boundaryVertex != second.boundaryVertex) { + triangles.emplace_back(p0, p1, second.lowerLimit); + triangles.emplace_back(p0, p1, second.upperLimit); + } + + auto & out = boundaryFaces.emplace_back(); + out.emplace_back(first.boundaryVertex); + out.emplace_back(first.extrusionVertex); + for (auto currentVertex = first.extrusionVertex; + std::none_of(voh_begin(currentVertex), voh_end(currentVertex), + [&](const auto currentVertexOut) { + // The next half edge goes to the termination point + const auto next = next_halfedge_handle(currentVertexOut); + const auto nextVertex = to_vertex_handle(next); + return (nextVertex == second.extrusionVertex); + }) + && std::any_of( + voh_begin(currentVertex), voh_end(currentVertex), [&](const auto currentVertexOut) { + const auto next = next_halfedge_handle(currentVertexOut); + const auto nextVertex = to_vertex_handle(next); + const auto startVertex = from_vertex_handle(next); + if (nextVertex == *++out.rbegin()) { + // This half edge goes back to the previous vertex + return false; + } + const auto edge = edge_handle(next); + const auto ep0 = point(startVertex); + const auto ep1 = point(nextVertex); + const auto diff = RelativePosition3D(ep1 - ep0); + const auto length = glm::length(diff); + const auto dir = diff / length; + const Ray r {ep0, dir}; + return std::any_of(triangles.begin(), triangles.end(), [&](const auto & triangle) { + BaryPosition bary; + RelativeDistance dist {}; + + if (r.intersectTriangle(triangle.x, triangle.y, triangle.z, bary, dist) + && dist <= length - 1 && dist >= 1) { + const auto splitPos = triangle * bary; + currentVertex = out.emplace_back(split(edge, splitPos)); + return true; + } + return false; + }); + });) { ; } - sideVerts.emplace_back(*nexv); - sideVerts.emplace_back(toVertex); - ex = nex; - exv++; - return sideVerts; + out.emplace_back(second.extrusionVertex); + if (first.boundaryVertex != second.boundaryVertex) { + out.emplace_back(second.boundaryVertex); + } + return false; }); - // Remove old faces + // Remove old faces std::set visited; auto removeOld = [&](auto & self, const auto face) -> void { if (visited.insert(face).second) { - std::vector neighbourFaces; std::for_each(fh_begin(face), fh_end(face), [&](const auto fh) { - if (std::none_of(boundaryFaces.begin(), boundaryFaces.end(), [fh, this](const auto & bf) { - return std::find(bf.begin(), bf.end(), from_vertex_handle(fh)) != bf.end() - && std::find(bf.begin(), bf.end(), to_vertex_handle(fh)) != bf.end(); - })) { - neighbourFaces.emplace_back(opposite_face_handle(fh)); + const auto b1 = to_vertex_handle(fh); + const auto b2 = from_vertex_handle(fh); + if (opposite_face_handle(fh).is_valid() + && std::none_of(boundaryFaces.begin(), boundaryFaces.end(), [b2, b1](const auto & bf) { + return std::adjacent_find(bf.begin(), bf.end(), [b2, b1](const auto v1, const auto v2) { + return b1 == v1 && b2 == v2; + }) != bf.end(); + })) { + self(self, opposite_face_handle(fh)); } }); delete_face(face, false); - std::for_each(neighbourFaces.begin(), neighbourFaces.end(), [&self](const auto nextFace) { - if (nextFace.is_valid()) { - self(self, nextFace); - } - }); } }; removeOld(removeOld, findPoint(triangleStrip.front())); diff --git a/test/fixtures/geoData/deform/1.json b/test/fixtures/geoData/deform/1.json index 33ac86d..2854e64 100644 --- a/test/fixtures/geoData/deform/1.json +++ b/test/fixtures/geoData/deform/1.json @@ -19,7 +19,7 @@ [ 241000, 123330, - -2000 + 2000 ] ], [ @@ -69,5 +69,56 @@ "/tmp/geoData2.tga" ] ] + ], + [ + [ + [ + 3000, + 1000, + 500 + ], + [ + 3000, + 2000, + 500 + ], + [ + 2000, + 1000, + 500 + ] + ], + [ + [ + [ + [ + -1000, + -3000, + 7000 + ], + [ + 1, + 1, + -1.5 + ] + ], + "/tmp/geoData3.tga" + ], + [ + [ + [ + 1800, + 2500, + 800 + ], + [ + 1, + -0.2, + -0.5 + ] + ], + "/tmp/geoData4.tga" + ] + ] ] ] -- cgit v1.2.3 From 0490055e5eae70fb13a9ff91319d63ba6ca39251 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Fri, 8 Mar 2024 22:57:45 +0000 Subject: Set linkflags -z defs --- Jamroot.jam | 1 + 1 file changed, 1 insertion(+) diff --git a/Jamroot.jam b/Jamroot.jam index de27053..7a2fe16 100644 --- a/Jamroot.jam +++ b/Jamroot.jam @@ -17,6 +17,7 @@ lib OpenMeshCore ; variant coverage : debug ; project : requirements 20 + -Wl,-z,defs release:on profile:on coverage:on -- cgit v1.2.3 From 0275b4d1ce7c2ea3dbbe31ebc71db5395722bdc9 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 9 Mar 2024 12:05:37 +0000 Subject: Add timeout to deformation unit test --- test/test-geoData.cpp | 2 ++ 1 file changed, 2 insertions(+) diff --git a/test/test-geoData.cpp b/test/test-geoData.cpp index 36d008b..2d6b1aa 100644 --- a/test/test-geoData.cpp +++ b/test/test-geoData.cpp @@ -208,6 +208,8 @@ BOOST_DATA_TEST_CASE(findEntries, using DeformTerrainData = std::tuple, std::vector, std::string>>>; +BOOST_TEST_DECORATOR(*boost::unit_test::timeout(2)); + BOOST_DATA_TEST_CASE(deform, loadFixtureJson("geoData/deform/1.json"), points, cams) { auto gd = std::make_shared(GeoData::createFlat({0, 0}, {1000000, 1000000}, 100)); -- cgit v1.2.3 From cfe9b339b401eaf5c049981bbfc50ac13ce1def9 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 9 Mar 2024 12:08:24 +0000 Subject: Fix non-64bit upgrade wrapper for crossProduct --- lib/maths.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/lib/maths.h b/lib/maths.h index 5886326..adf2158 100644 --- a/lib/maths.h +++ b/lib/maths.h @@ -111,7 +111,7 @@ template inline constexpr glm::vec<3, T, Q> crossProduct(const glm::vec<3, T, Q> a, const glm::vec<3, T, Q> b) { - return crossProduct(a, b); + return crossProduct(a, b); } template -- cgit v1.2.3 From 4c05a12cf1c30eadcd5edd61f75b8fc92d3dbd7c Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 9 Mar 2024 12:10:17 +0000 Subject: Add deformation test case with lower spec --- test/fixtures/geoData/deform/1.json | 36 ++++++++++++++++++++++++++++++++++++ 1 file changed, 36 insertions(+) diff --git a/test/fixtures/geoData/deform/1.json b/test/fixtures/geoData/deform/1.json index 2854e64..fb45ce4 100644 --- a/test/fixtures/geoData/deform/1.json +++ b/test/fixtures/geoData/deform/1.json @@ -120,5 +120,41 @@ "/tmp/geoData4.tga" ] ] + ], + [ + [ + [ + 3000, + 1000, + 10 + ], + [ + 3000, + 2000, + 10 + ], + [ + 2000, + 1000, + 10 + ] + ], + [ + [ + [ + [ + -500, + -1500, + 3000 + ], + [ + 1, + 1, + -1.5 + ] + ], + "/tmp/geoData5.tga" + ] + ] ] ] -- cgit v1.2.3 From 9c7286466a1da04f45f633af9086e543d99c7df5 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Thu, 14 Mar 2024 00:38:30 +0000 Subject: Simplify cut loop and termination case search Looks for a halfedge from current vertex to end vertex. --- game/geoData.cpp | 66 ++++++++++++++++++++++++++------------------------------ 1 file changed, 30 insertions(+), 36 deletions(-) diff --git a/game/geoData.cpp b/game/geoData.cpp index ac2f035..c48881f 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -492,43 +492,37 @@ GeoData::setHeights(const std::span triangleStrip) out.emplace_back(first.boundaryVertex); out.emplace_back(first.extrusionVertex); for (auto currentVertex = first.extrusionVertex; - std::none_of(voh_begin(currentVertex), voh_end(currentVertex), - [&](const auto currentVertexOut) { - // The next half edge goes to the termination point - const auto next = next_halfedge_handle(currentVertexOut); - const auto nextVertex = to_vertex_handle(next); - return (nextVertex == second.extrusionVertex); - }) - && std::any_of( - voh_begin(currentVertex), voh_end(currentVertex), [&](const auto currentVertexOut) { - const auto next = next_halfedge_handle(currentVertexOut); - const auto nextVertex = to_vertex_handle(next); - const auto startVertex = from_vertex_handle(next); - if (nextVertex == *++out.rbegin()) { - // This half edge goes back to the previous vertex - return false; + !find_halfedge(currentVertex, second.extrusionVertex).is_valid();) { + auto n = std::any_of( + voh_begin(currentVertex), voh_end(currentVertex), [&](const auto currentVertexOut) { + const auto next = next_halfedge_handle(currentVertexOut); + const auto nextVertex = to_vertex_handle(next); + const auto startVertex = from_vertex_handle(next); + if (nextVertex == *++out.rbegin()) { + // This half edge goes back to the previous vertex + return false; + } + const auto edge = edge_handle(next); + const auto ep0 = point(startVertex); + const auto ep1 = point(nextVertex); + const auto diff = RelativePosition3D(ep1 - ep0); + const auto length = glm::length(diff); + const auto dir = diff / length; + const Ray r {ep0, dir}; + return std::any_of(triangles.begin(), triangles.end(), [&](const auto & triangle) { + BaryPosition bary; + RelativeDistance dist {}; + + if (r.intersectTriangle(triangle.x, triangle.y, triangle.z, bary, dist) + && dist <= length - 1 && dist >= 1) { + const auto splitPos = triangle * bary; + currentVertex = out.emplace_back(split(edge, splitPos)); + return true; } - const auto edge = edge_handle(next); - const auto ep0 = point(startVertex); - const auto ep1 = point(nextVertex); - const auto diff = RelativePosition3D(ep1 - ep0); - const auto length = glm::length(diff); - const auto dir = diff / length; - const Ray r {ep0, dir}; - return std::any_of(triangles.begin(), triangles.end(), [&](const auto & triangle) { - BaryPosition bary; - RelativeDistance dist {}; - - if (r.intersectTriangle(triangle.x, triangle.y, triangle.z, bary, dist) - && dist <= length - 1 && dist >= 1) { - const auto splitPos = triangle * bary; - currentVertex = out.emplace_back(split(edge, splitPos)); - return true; - } - return false; - }); - });) { - ; + return false; + }); + }); + assert(n); } out.emplace_back(second.extrusionVertex); if (first.boundaryVertex != second.boundaryVertex) { -- cgit v1.2.3 From 5248847bf08df213f574761455d12673ec1d2ac7 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Thu, 14 Mar 2024 01:09:28 +0000 Subject: Fix generation of halfedge extrusion extents --- game/geoData.cpp | 11 ++++++----- 1 file changed, 6 insertions(+), 5 deletions(-) diff --git a/game/geoData.cpp b/game/geoData.cpp index c48881f..293cd2b 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -421,9 +421,10 @@ GeoData::setHeights(const std::span triangleStrip) }; const auto boundaryVertex = from_vertex_handle(boundaryHeh); + const auto nextBoundaryVertex = to_vertex_handle(boundaryHeh); const auto p0 = point(from_vertex_handle(prev_halfedge_handle(boundaryHeh))); const auto p1 = point(boundaryVertex); - const auto p2 = point(to_vertex_handle(boundaryHeh)); + const auto p2 = point(nextBoundaryVertex); const auto e0 = glm::normalize(vectorNormal(RelativePosition2D(p1 - p0))); const auto e1 = glm::normalize(vectorNormal(RelativePosition2D(p2 - p1))); @@ -465,11 +466,11 @@ GeoData::setHeights(const std::span triangleStrip) assert(extrusionVertex.is_valid()); } // Half edge start/end tangents - for (const auto p : {p1, p2}) { + for (const auto p : {boundaryVertex, nextBoundaryVertex}) { VertexHandle extrusionVertex; - extrusionExtents.emplace_back(boundaryVertex, extrusionVertex, - doExtrusion(extrusionVertex, e1, p, -MAX_SLOPE, lowerExtent.z - 10), - doExtrusion(extrusionVertex, e1, p, MAX_SLOPE, upperExtent.z + 10)); + extrusionExtents.emplace_back(p, extrusionVertex, + doExtrusion(extrusionVertex, e1, point(p), -MAX_SLOPE, lowerExtent.z - 10), + doExtrusion(extrusionVertex, e1, point(p), MAX_SLOPE, upperExtent.z + 10)); assert(extrusionVertex.is_valid()); } }); -- cgit v1.2.3 From c0ff72c1aef7f1ad502b838af899cb0a9be35263 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Mon, 18 Mar 2024 00:04:18 +0000 Subject: Add Ray::intersectPlane --- lib/ray.h | 12 ++++++++++++ 1 file changed, 12 insertions(+) diff --git a/lib/ray.h b/lib/ray.h index 67fdd12..a831270 100644 --- a/lib/ray.h +++ b/lib/ray.h @@ -42,6 +42,18 @@ public: }) != positions.end(); } + bool + intersectPlane(const PositionType orig, const Direction3D norm, RelativeDistance & distance) const + { + if constexpr (std::is_floating_point_v) { + return glm::intersectRayPlane(start, direction, orig, norm, distance) && distance >= 0.F; + } + else { + const RelativePosition3D origr = orig - start; + return glm::intersectRayPlane({}, direction, origr, norm, distance) && distance >= 0.F; + } + } + bool intersectTriangle(const PositionType t0, const PositionType t1, const PositionType t2, BaryPosition & bary, RelativeDistance & distance) const -- cgit v1.2.3 From 1dc1e08222f346d4434c52e524d199b4b8eeac1f Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Mon, 18 Mar 2024 00:18:09 +0000 Subject: Add non-default constructor to GeometricPlaneT --- lib/geometricPlane.h | 8 ++++++-- 1 file changed, 6 insertions(+), 2 deletions(-) diff --git a/lib/geometricPlane.h b/lib/geometricPlane.h index 3b1a0e4..d4b803d 100644 --- a/lib/geometricPlane.h +++ b/lib/geometricPlane.h @@ -16,13 +16,17 @@ public: template class GeometricPlaneT : public GeometricPlane { public: + GeometricPlaneT() = default; + + GeometricPlaneT(PositionType origin, Normal3D normal) : origin(std::move(origin)), normal(normal) { } + struct DistAndPosition { PositionType::value_type dist; PositionType position; }; - PositionType origin; - Normal3D normal; + PositionType origin {}; + Normal3D normal {}; [[nodiscard]] inline PlaneRelation getRelation(PositionType point) const -- cgit v1.2.3 From 8f1a9a5f0f36ade0df3b6c923ec297faa8091a9a Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Mon, 18 Mar 2024 00:22:12 +0000 Subject: Switch to using planes instead of triangles for deformaton cut Removes the hacky need for going a bit too far to account for rounding errors... which didn't really work anyway. --- game/geoData.cpp | 71 +++++++++++++++++++++++++++++++++++--------------------- 1 file changed, 45 insertions(+), 26 deletions(-) diff --git a/game/geoData.cpp b/game/geoData.cpp index 293cd2b..bf3192e 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -1,5 +1,6 @@ #include "geoData.h" #include "collections.h" +#include "geometricPlane.h" #include #include #include @@ -429,7 +430,7 @@ GeoData::setHeights(const std::span triangleStrip) const auto e1 = glm::normalize(vectorNormal(RelativePosition2D(p2 - p1))); const auto doExtrusion = [this](VertexHandle & extrusionVertex, Direction2D direction, - GlobalPosition3D boundaryVertex, RelativeDistance vert, GlobalDistance limit) { + GlobalPosition3D boundaryVertex, RelativeDistance vert) { const auto extrusionDir = glm::normalize(direction || vert); if (!extrusionVertex.is_valid()) { @@ -449,8 +450,7 @@ GeoData::setHeights(const std::span triangleStrip) } } - const auto extrusion - = extrusionDir * std::max(0.F, RelativeDistance(limit - boundaryVertex.z) / extrusionDir.z); + const auto extrusion = extrusionDir * 1000.F * MAX_SLOPE; return boundaryVertex + extrusion; }; // Previous half edge end to current half end start arc tangents @@ -461,16 +461,15 @@ GeoData::setHeights(const std::span triangleStrip) const auto direction = sincosf(arc.first + (step * inc)); VertexHandle extrusionVertex; extrusionExtents.emplace_back(boundaryVertex, extrusionVertex, - doExtrusion(extrusionVertex, direction, p1, -MAX_SLOPE, lowerExtent.z - 10), - doExtrusion(extrusionVertex, direction, p1, MAX_SLOPE, upperExtent.z + 10)); + doExtrusion(extrusionVertex, direction, p1, -MAX_SLOPE), + doExtrusion(extrusionVertex, direction, p1, MAX_SLOPE)); assert(extrusionVertex.is_valid()); } // Half edge start/end tangents for (const auto p : {boundaryVertex, nextBoundaryVertex}) { VertexHandle extrusionVertex; - extrusionExtents.emplace_back(p, extrusionVertex, - doExtrusion(extrusionVertex, e1, point(p), -MAX_SLOPE, lowerExtent.z - 10), - doExtrusion(extrusionVertex, e1, point(p), MAX_SLOPE, upperExtent.z + 10)); + extrusionExtents.emplace_back(p, extrusionVertex, doExtrusion(extrusionVertex, e1, point(p), -MAX_SLOPE), + doExtrusion(extrusionVertex, e1, point(p), MAX_SLOPE)); assert(extrusionVertex.is_valid()); } }); @@ -481,13 +480,26 @@ GeoData::setHeights(const std::span triangleStrip) std::adjacent_find(extrusionExtents.begin(), extrusionExtents.end(), [this, &boundaryFaces](const auto & first, const auto & second) { const auto p0 = point(first.boundaryVertex); - std::vector> triangles { - {p0, first.lowerLimit, second.lowerLimit}, {p0, first.upperLimit, second.upperLimit}}; const auto p1 = point(second.boundaryVertex); - if (first.boundaryVertex != second.boundaryVertex) { - triangles.emplace_back(p0, p1, second.lowerLimit); - triangles.emplace_back(p0, p1, second.upperLimit); - } + const auto make_normal = [](auto x, auto y, auto z) { + const auto cp = crossProduct(z - x, y - x); + const auto rcp = RelativePosition3D(cp); + const auto nrcp = glm::normalize(rcp); + return nrcp; + }; + const auto normals = ((first.boundaryVertex == second.boundaryVertex) + ? std::array {make_normal(p0, first.lowerLimit, second.lowerLimit), + make_normal(p0, first.upperLimit, second.upperLimit), + } + : std::array { + make_normal(p0, second.lowerLimit, p1), + make_normal(p0, second.upperLimit, p1), + }); + assert(normals.front().z > 0.F); + assert(normals.back().z > 0.F); + const auto planes = normals * [p0](const auto & normal) { + return GeometricPlaneT {p0, normal}; + }; auto & out = boundaryFaces.emplace_back(); out.emplace_back(first.boundaryVertex); @@ -500,28 +512,35 @@ GeoData::setHeights(const std::span triangleStrip) const auto nextVertex = to_vertex_handle(next); const auto startVertex = from_vertex_handle(next); if (nextVertex == *++out.rbegin()) { - // This half edge goes back to the previous vertex + // This half edge goes back to the previous vertex return false; } const auto edge = edge_handle(next); const auto ep0 = point(startVertex); const auto ep1 = point(nextVertex); + if (planes.front().getRelation(ep1) == GeometricPlane::PlaneRelation::Below + || planes.back().getRelation(ep1) == GeometricPlane::PlaneRelation::Above) { + return false; + } const auto diff = RelativePosition3D(ep1 - ep0); const auto length = glm::length(diff); const auto dir = diff / length; - const Ray r {ep0, dir}; - return std::any_of(triangles.begin(), triangles.end(), [&](const auto & triangle) { - BaryPosition bary; + const Ray r {ep1, -dir}; + const auto dists = planes * [r](const auto & plane) { RelativeDistance dist {}; - - if (r.intersectTriangle(triangle.x, triangle.y, triangle.z, bary, dist) - && dist <= length - 1 && dist >= 1) { - const auto splitPos = triangle * bary; - currentVertex = out.emplace_back(split(edge, splitPos)); - return true; + if (r.intersectPlane(plane.origin, plane.normal, dist)) { + return dist; } - return false; - }); + return INFINITY; + }; + const auto dist = *std::min_element(dists.begin(), dists.end()); + const auto splitPos = ep1 - (dir * dist); + if (dist <= length) { + currentVertex = split(edge, splitPos); + out.emplace_back(currentVertex); + return true; + } + return false; }); assert(n); } -- cgit v1.2.3 From 46fc283494027fe1e2aaf5eae457a2be1c65efab Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Mon, 18 Mar 2024 01:04:42 +0000 Subject: maybe_unused return from cut point search Only asserted --- game/geoData.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/game/geoData.cpp b/game/geoData.cpp index bf3192e..e29fb93 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -506,7 +506,7 @@ GeoData::setHeights(const std::span triangleStrip) out.emplace_back(first.extrusionVertex); for (auto currentVertex = first.extrusionVertex; !find_halfedge(currentVertex, second.extrusionVertex).is_valid();) { - auto n = std::any_of( + [[maybe_unused]] const auto n = std::any_of( voh_begin(currentVertex), voh_end(currentVertex), [&](const auto currentVertexOut) { const auto next = next_halfedge_handle(currentVertexOut); const auto nextVertex = to_vertex_handle(next); -- cgit v1.2.3 From e513257354cfc53adef0f5f4e8dd896acd184f16 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Mon, 18 Mar 2024 02:42:19 +0000 Subject: Simplify creation of planes Uses limit directions instead of fake triangles --- game/geoData.cpp | 30 ++++++++++++------------------ 1 file changed, 12 insertions(+), 18 deletions(-) diff --git a/game/geoData.cpp b/game/geoData.cpp index e29fb93..f4d9f65 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -412,7 +412,7 @@ GeoData::setHeights(const std::span triangleStrip) // Extrude corners struct Extrusion { VertexHandle boundaryVertex, extrusionVertex; - GlobalPosition3D lowerLimit, upperLimit; + Direction3D lowerLimit, upperLimit; }; std::vector extrusionExtents; @@ -450,8 +450,7 @@ GeoData::setHeights(const std::span triangleStrip) } } - const auto extrusion = extrusionDir * 1000.F * MAX_SLOPE; - return boundaryVertex + extrusion; + return extrusionDir; }; // Previous half edge end to current half end start arc tangents const Arc arc {p1, p1 + (e0 || 0.F), p1 + (e1 || 0.F)}; @@ -481,25 +480,20 @@ GeoData::setHeights(const std::span triangleStrip) [this, &boundaryFaces](const auto & first, const auto & second) { const auto p0 = point(first.boundaryVertex); const auto p1 = point(second.boundaryVertex); - const auto make_normal = [](auto x, auto y, auto z) { - const auto cp = crossProduct(z - x, y - x); - const auto rcp = RelativePosition3D(cp); - const auto nrcp = glm::normalize(rcp); - return nrcp; + const auto bdir = RelativePosition3D(p1 - p0); + const auto make_plane = [p0](auto y, auto z) { + return GeometricPlaneT {p0, crossProduct(y, z)}; }; - const auto normals = ((first.boundaryVertex == second.boundaryVertex) - ? std::array {make_normal(p0, first.lowerLimit, second.lowerLimit), - make_normal(p0, first.upperLimit, second.upperLimit), + const auto planes = ((first.boundaryVertex == second.boundaryVertex) + ? std::array {make_plane(second.lowerLimit, first.lowerLimit), + make_plane(second.upperLimit, first.upperLimit), } : std::array { - make_normal(p0, second.lowerLimit, p1), - make_normal(p0, second.upperLimit, p1), + make_plane(bdir, second.lowerLimit), + make_plane(bdir, second.upperLimit), }); - assert(normals.front().z > 0.F); - assert(normals.back().z > 0.F); - const auto planes = normals * [p0](const auto & normal) { - return GeometricPlaneT {p0, normal}; - }; + assert(planes.front().normal.z > 0.F); + assert(planes.back().normal.z > 0.F); auto & out = boundaryFaces.emplace_back(); out.emplace_back(first.boundaryVertex); -- cgit v1.2.3 From 49cfebf74e97ccc88d2d6a459172cb2a17e545b8 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Thu, 21 Mar 2024 20:05:56 +0000 Subject: vector_yaw only needs 2 dimensions --- lib/maths.cpp | 2 +- lib/maths.h | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-) diff --git a/lib/maths.cpp b/lib/maths.cpp index 68662fc..bf17204 100644 --- a/lib/maths.cpp +++ b/lib/maths.cpp @@ -76,7 +76,7 @@ rotate_yp(Rotation2D a) } float -vector_yaw(const Direction3D & diff) +vector_yaw(const Direction2D & diff) { return std::atan2(diff.x, diff.y); } diff --git a/lib/maths.h b/lib/maths.h index adf2158..ce18b3f 100644 --- a/lib/maths.h +++ b/lib/maths.h @@ -84,7 +84,7 @@ glm::mat4 rotate_pitch(float); glm::mat4 rotate_yp(Rotation2D); glm::mat4 rotate_ypr(Rotation3D); -float vector_yaw(const Direction3D & diff); +float vector_yaw(const Direction2D & diff); float vector_pitch(const Direction3D & diff); float round_frac(const float & v, const float & frac); -- cgit v1.2.3 From 31f73b6f44f3deac749af41e84435f5bc9b037f2 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Thu, 21 Mar 2024 20:09:34 +0000 Subject: Make arc_length a member function --- game/network/link.cpp | 2 +- game/network/rail.cpp | 2 +- lib/maths.h | 12 ++++++------ 3 files changed, 8 insertions(+), 8 deletions(-) diff --git a/game/network/link.cpp b/game/network/link.cpp index 122eaf4..248fe7d 100644 --- a/game/network/link.cpp +++ b/game/network/link.cpp @@ -62,7 +62,7 @@ LinkCurve::intersectRay(const Ray & ray) const const auto & e1p {ends[1].node->pos}; const auto slength = round_frac(length / 2.F, 5.F); const auto segs = std::round(15.F * slength / std::pow(radius, 0.7F)); - const auto step {glm::vec<2, RelativeDistance> {arc_length(arc), e1p.z - e0p.z} / segs}; + const auto step {glm::vec<2, RelativeDistance> {arc.length(), e1p.z - e0p.z} / segs}; auto segCount = static_cast(std::lround(segs)) + 1; std::vector points; diff --git a/game/network/rail.cpp b/game/network/rail.cpp index 34cbceb..e342224 100644 --- a/game/network/rail.cpp +++ b/game/network/rail.cpp @@ -118,7 +118,7 @@ RailLinkCurve::RailLinkCurve( RailLinkCurve::RailLinkCurve(NetworkLinkHolder & instances, const Node::Ptr & a, const Node::Ptr & b, GlobalPosition3D c, const Arc arc) : Link({a, normalize(arc.first + half_pi)}, {b, normalize(arc.second - half_pi)}, - glm::length(RelativePosition3D(a->pos - c)) * arc_length(arc)), + glm::length(RelativePosition3D(a->pos - c)) * arc.length()), LinkCurve {c, glm::length(RelativePosition3D(ends[0].node->pos - c)), 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/lib/maths.h b/lib/maths.h index ce18b3f..20a397b 100644 --- a/lib/maths.h +++ b/lib/maths.h @@ -19,6 +19,12 @@ struct Arc : public std::pair { { return i ? second : first; } + + [[nodiscard]] constexpr inline float + length() const + { + return second - first; + } }; constexpr const RelativePosition3D up {0, 0, 1}; @@ -171,12 +177,6 @@ operator%=(glm::vec & p, const glm::mat & mutation) return p = p % mutation; } -constexpr inline float -arc_length(const Arc & arc) -{ - return arc.second - arc.first; -} - float normalize(float ang); template -- cgit v1.2.3 From 4571ce1b4cac2ab9bf2454ed06d0d787604d62fa Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Thu, 21 Mar 2024 20:23:44 +0000 Subject: Add helper constructors to Arc * Two angles, wraps logic ensuring b after a * Two vector directions * Centre and two endpoints, in at least 2 dimensions, uses .xy() --- game/geoData.cpp | 2 +- game/network/rail.cpp | 10 ++++------ lib/maths.cpp | 5 +++++ lib/maths.h | 28 +++++++++------------------- test/Jamfile.jam | 1 + 5 files changed, 20 insertions(+), 26 deletions(-) diff --git a/game/geoData.cpp b/game/geoData.cpp index f4d9f65..aaa2548 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -453,7 +453,7 @@ GeoData::setHeights(const std::span triangleStrip) return extrusionDir; }; // Previous half edge end to current half end start arc tangents - const Arc arc {p1, p1 + (e0 || 0.F), p1 + (e1 || 0.F)}; + const Arc arc {e0, e1}; const auto limit = std::floor((arc.second - arc.first) * 5.F / pi); const auto inc = (arc.second - arc.first) / limit; for (float step = 1; step < limit; step += 1.F) { diff --git a/game/network/rail.cpp b/game/network/rail.cpp index e342224..fd07ace 100644 --- a/game/network/rail.cpp +++ b/game/network/rail.cpp @@ -95,9 +95,8 @@ round_sleepers(const float v) return round_frac(v, sleepers); } -RailLinkStraight::RailLinkStraight( - NetworkLinkHolder & instances, const Node::Ptr & a, const Node::Ptr & b) : - RailLinkStraight(instances, a, b, b->pos - a->pos) +RailLinkStraight::RailLinkStraight(NetworkLinkHolder & instances, const Node::Ptr & a, + const Node::Ptr & b) : RailLinkStraight(instances, a, b, b->pos - a->pos) { } @@ -109,9 +108,8 @@ 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 || 0, 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, {c, a->pos, b->pos}) { } diff --git a/lib/maths.cpp b/lib/maths.cpp index bf17204..51e27fe 100644 --- a/lib/maths.cpp +++ b/lib/maths.cpp @@ -4,6 +4,11 @@ #include #include +Arc::Arc(const RelativePosition2D & dir0, const RelativePosition2D & dir1) : + Arc {vector_yaw(dir0), vector_yaw(dir1)} { } + +Arc::Arc(const Angle anga, const Angle angb) : pair {anga, (angb < anga) ? angb + two_pi : angb} { } + glm::mat4 flat_orientation(const Direction3D & diff) { diff --git a/lib/maths.h b/lib/maths.h index 20a397b..656fefd 100644 --- a/lib/maths.h +++ b/lib/maths.h @@ -8,11 +8,16 @@ #include #include -struct Arc : public std::pair { - using std::pair::pair; +struct Arc : public std::pair { + template + requires(Lc >= 2, Le >= 2) + Arc(const glm::vec & centre, const glm::vec & e0p, const glm::vec & e1p) : + Arc {RelativePosition2D {e0p.xy() - centre.xy()}, RelativePosition2D {e1p.xy() - centre.xy()}} + { + } - template - Arc(const glm::vec<3, T, Q> & centre3, const glm::vec<3, T, Q> & e0p, const glm::vec<3, T, Q> & e1p); + Arc(const RelativePosition2D & dir0, const RelativePosition2D & dir1); + Arc(const Angle angb, const Angle anga); auto operator[](bool i) const @@ -244,21 +249,6 @@ midpoint(const std::pair & v) return std::midpoint(v.first, v.second); } -template -Arc::Arc(const glm::vec<3, T, Q> & centre3, const glm::vec<3, T, Q> & e0p, const glm::vec<3, T, Q> & e1p) : - Arc([&]() -> Arc { - const auto diffa = e0p - centre3; - const auto diffb = e1p - centre3; - const auto anga = vector_yaw(diffa); - const auto angb = [&diffb, &anga]() { - const auto angb = vector_yaw(diffb); - return (angb < anga) ? angb + two_pi : angb; - }(); - return {anga, angb}; - }()) -{ -} - // Conversions template inline constexpr auto diff --git a/test/Jamfile.jam b/test/Jamfile.jam index 1b07b5a..cce4513 100644 --- a/test/Jamfile.jam +++ b/test/Jamfile.jam @@ -12,6 +12,7 @@ project : requirements BOOST_TEST_DYN_LINK RESDIR=\\\"$(res)/\\\" FIXTURESDIR=\\\"$(fixtures)/\\\" + GLM_FORCE_SWIZZLE debug:pedantic debug:on debug:-Wnon-virtual-dtor -- cgit v1.2.3 From c6c0d8005880d73b8560bcb10c34a6e8b2da703e Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 23 Mar 2024 18:04:57 +0000 Subject: Extract vector_normal helper into lib --- game/geoData.cpp | 8 ++------ lib/maths.h | 7 +++++++ 2 files changed, 9 insertions(+), 6 deletions(-) diff --git a/game/geoData.cpp b/game/geoData.cpp index aaa2548..4273be6 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -417,17 +417,13 @@ GeoData::setHeights(const std::span triangleStrip) std::vector extrusionExtents; std::for_each(boundary.begin(), boundary.end(), [this, &extrusionExtents](const auto boundaryHeh) { - const auto vectorNormal = [](const glm::vec<2, T, Q> & v) -> glm::vec<2, T, Q> { - return {-v.y, v.x}; - }; - const auto boundaryVertex = from_vertex_handle(boundaryHeh); const auto nextBoundaryVertex = to_vertex_handle(boundaryHeh); const auto p0 = point(from_vertex_handle(prev_halfedge_handle(boundaryHeh))); const auto p1 = point(boundaryVertex); const auto p2 = point(nextBoundaryVertex); - const auto e0 = glm::normalize(vectorNormal(RelativePosition2D(p1 - p0))); - const auto e1 = glm::normalize(vectorNormal(RelativePosition2D(p2 - p1))); + const auto e0 = glm::normalize(vector_normal(RelativePosition2D(p1 - p0))); + const auto e1 = glm::normalize(vector_normal(RelativePosition2D(p2 - p1))); const auto doExtrusion = [this](VertexHandle & extrusionVertex, Direction2D direction, GlobalPosition3D boundaryVertex, RelativeDistance vert) { diff --git a/lib/maths.h b/lib/maths.h index 656fefd..63b752a 100644 --- a/lib/maths.h +++ b/lib/maths.h @@ -98,6 +98,13 @@ glm::mat4 rotate_ypr(Rotation3D); float vector_yaw(const Direction2D & diff); float vector_pitch(const Direction3D & diff); +template +glm::vec<2, T, Q> +vector_normal(const glm::vec<2, T, Q> & v) +{ + return {-v.y, v.x}; +}; + float round_frac(const float & v, const float & frac); template -- cgit v1.2.3 From 74b3c72ec3478e391bab02625a3d1f4400af4818 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 23 Mar 2024 18:06:52 +0000 Subject: Remove boundary collection We can simply walk the boundary as required --- game/geoData.cpp | 109 +++++++++++++++++++++++++++---------------------------- 1 file changed, 53 insertions(+), 56 deletions(-) diff --git a/game/geoData.cpp b/game/geoData.cpp index 4273be6..c6f7902 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -402,12 +402,6 @@ GeoData::setHeights(const std::span triangleStrip) auto faceHandle = add_face(a, b, c); return faceHandle; }); - std::vector boundary; - boundaryWalk( - [out = std::back_inserter(boundary)](const auto boundaryHeh) mutable { - out = boundaryHeh; - }, - *voh_begin(newVerts.front())); // Extrude corners struct Extrusion { @@ -416,58 +410,61 @@ GeoData::setHeights(const std::span triangleStrip) }; std::vector extrusionExtents; - std::for_each(boundary.begin(), boundary.end(), [this, &extrusionExtents](const auto boundaryHeh) { - const auto boundaryVertex = from_vertex_handle(boundaryHeh); - const auto nextBoundaryVertex = to_vertex_handle(boundaryHeh); - const auto p0 = point(from_vertex_handle(prev_halfedge_handle(boundaryHeh))); - const auto p1 = point(boundaryVertex); - const auto p2 = point(nextBoundaryVertex); - const auto e0 = glm::normalize(vector_normal(RelativePosition2D(p1 - p0))); - const auto e1 = glm::normalize(vector_normal(RelativePosition2D(p2 - p1))); - - const auto doExtrusion = [this](VertexHandle & extrusionVertex, Direction2D direction, - GlobalPosition3D boundaryVertex, RelativeDistance vert) { - const auto extrusionDir = glm::normalize(direction || vert); - - if (!extrusionVertex.is_valid()) { - if (const auto intersect = intersectRay({boundaryVertex, extrusionDir})) { - auto splitVertex = split(intersect->second, intersect->first); - extrusionVertex = splitVertex; - } - else if (const auto intersect - = intersectRay({boundaryVertex + GlobalPosition3D {1, 1, 0}, extrusionDir})) { - auto splitVertex = split(intersect->second, intersect->first); - extrusionVertex = splitVertex; + boundaryWalk( + [this, &extrusionExtents](const auto boundaryHeh) { + const auto boundaryVertex = from_vertex_handle(boundaryHeh); + const auto nextBoundaryVertex = to_vertex_handle(boundaryHeh); + const auto p0 = point(from_vertex_handle(prev_halfedge_handle(boundaryHeh))); + const auto p1 = point(boundaryVertex); + const auto p2 = point(nextBoundaryVertex); + const auto e0 = glm::normalize(vector_normal(RelativePosition2D(p1 - p0))); + const auto e1 = glm::normalize(vector_normal(RelativePosition2D(p2 - p1))); + + const auto doExtrusion = [this](VertexHandle & extrusionVertex, Direction2D direction, + GlobalPosition3D boundaryVertex, RelativeDistance vert) { + const auto extrusionDir = glm::normalize(direction || vert); + + if (!extrusionVertex.is_valid()) { + if (const auto intersect = intersectRay({boundaryVertex, extrusionDir})) { + auto splitVertex = split(intersect->second, intersect->first); + extrusionVertex = splitVertex; + } + else if (const auto intersect + = intersectRay({boundaryVertex + GlobalPosition3D {1, 1, 0}, extrusionDir})) { + auto splitVertex = split(intersect->second, intersect->first); + extrusionVertex = splitVertex; + } + else if (const auto intersect + = intersectRay({boundaryVertex + GlobalPosition3D {1, 0, 0}, extrusionDir})) { + auto splitVertex = split(intersect->second, intersect->first); + extrusionVertex = splitVertex; + } + } + + return extrusionDir; + }; + // Previous half edge end to current half end start arc tangents + const Arc arc {e0, e1}; + const auto limit = std::floor((arc.second - arc.first) * 5.F / pi); + const auto inc = (arc.second - arc.first) / limit; + for (float step = 1; step < limit; step += 1.F) { + const auto direction = sincosf(arc.first + (step * inc)); + VertexHandle extrusionVertex; + extrusionExtents.emplace_back(boundaryVertex, extrusionVertex, + doExtrusion(extrusionVertex, direction, p1, -MAX_SLOPE), + doExtrusion(extrusionVertex, direction, p1, MAX_SLOPE)); + assert(extrusionVertex.is_valid()); } - else if (const auto intersect - = intersectRay({boundaryVertex + GlobalPosition3D {1, 0, 0}, extrusionDir})) { - auto splitVertex = split(intersect->second, intersect->first); - extrusionVertex = splitVertex; + // Half edge start/end tangents + for (const auto p : {boundaryVertex, nextBoundaryVertex}) { + VertexHandle extrusionVertex; + extrusionExtents.emplace_back(p, extrusionVertex, + doExtrusion(extrusionVertex, e1, point(p), -MAX_SLOPE), + doExtrusion(extrusionVertex, e1, point(p), MAX_SLOPE)); + assert(extrusionVertex.is_valid()); } - } - - return extrusionDir; - }; - // Previous half edge end to current half end start arc tangents - const Arc arc {e0, e1}; - const auto limit = std::floor((arc.second - arc.first) * 5.F / pi); - const auto inc = (arc.second - arc.first) / limit; - for (float step = 1; step < limit; step += 1.F) { - const auto direction = sincosf(arc.first + (step * inc)); - VertexHandle extrusionVertex; - extrusionExtents.emplace_back(boundaryVertex, extrusionVertex, - doExtrusion(extrusionVertex, direction, p1, -MAX_SLOPE), - doExtrusion(extrusionVertex, direction, p1, MAX_SLOPE)); - assert(extrusionVertex.is_valid()); - } - // Half edge start/end tangents - for (const auto p : {boundaryVertex, nextBoundaryVertex}) { - VertexHandle extrusionVertex; - extrusionExtents.emplace_back(p, extrusionVertex, doExtrusion(extrusionVertex, e1, point(p), -MAX_SLOPE), - doExtrusion(extrusionVertex, e1, point(p), MAX_SLOPE)); - assert(extrusionVertex.is_valid()); - } - }); + }, + *voh_begin(newVerts.front())); // Cut existing terrain extrusionExtents.emplace_back(extrusionExtents.front()); // Circular next -- cgit v1.2.3 From 7a8c0a1ac626a394a90a0a41b8a42a9c743aba8e Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 23 Mar 2024 18:46:18 +0000 Subject: Create extents purely from corner arcs --- game/geoData.cpp | 18 ++++++------------ 1 file changed, 6 insertions(+), 12 deletions(-) diff --git a/game/geoData.cpp b/game/geoData.cpp index c6f7902..80a4eba 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -412,9 +412,11 @@ GeoData::setHeights(const std::span triangleStrip) std::vector extrusionExtents; boundaryWalk( [this, &extrusionExtents](const auto boundaryHeh) { + const auto prevBoundaryHeh = prev_halfedge_handle(boundaryHeh); + const auto prevBoundaryVertex = from_vertex_handle(prevBoundaryHeh); const auto boundaryVertex = from_vertex_handle(boundaryHeh); const auto nextBoundaryVertex = to_vertex_handle(boundaryHeh); - const auto p0 = point(from_vertex_handle(prev_halfedge_handle(boundaryHeh))); + const auto p0 = point(prevBoundaryVertex); const auto p1 = point(boundaryVertex); const auto p2 = point(nextBoundaryVertex); const auto e0 = glm::normalize(vector_normal(RelativePosition2D(p1 - p0))); @@ -445,9 +447,9 @@ GeoData::setHeights(const std::span triangleStrip) }; // Previous half edge end to current half end start arc tangents const Arc arc {e0, e1}; - const auto limit = std::floor((arc.second - arc.first) * 5.F / pi); - const auto inc = (arc.second - arc.first) / limit; - for (float step = 1; step < limit; step += 1.F) { + const auto limit = std::ceil(arc.length() * 5.F / pi); + const auto inc = arc.length() / limit; + for (float step = 0; step <= limit; step += 1.F) { const auto direction = sincosf(arc.first + (step * inc)); VertexHandle extrusionVertex; extrusionExtents.emplace_back(boundaryVertex, extrusionVertex, @@ -455,14 +457,6 @@ GeoData::setHeights(const std::span triangleStrip) doExtrusion(extrusionVertex, direction, p1, MAX_SLOPE)); assert(extrusionVertex.is_valid()); } - // Half edge start/end tangents - for (const auto p : {boundaryVertex, nextBoundaryVertex}) { - VertexHandle extrusionVertex; - extrusionExtents.emplace_back(p, extrusionVertex, - doExtrusion(extrusionVertex, e1, point(p), -MAX_SLOPE), - doExtrusion(extrusionVertex, e1, point(p), MAX_SLOPE)); - assert(extrusionVertex.is_valid()); - } }, *voh_begin(newVerts.front())); -- cgit v1.2.3 From f380b20ddf1ead6447a6ee6e137a14c4aa226c12 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 23 Mar 2024 21:41:10 +0000 Subject: Handle and test concave surface boundaries --- game/geoData.cpp | 19 ++++++++++++----- test/fixtures/geoData/deform/1.json | 41 +++++++++++++++++++++++++++++++++++++ 2 files changed, 55 insertions(+), 5 deletions(-) diff --git a/game/geoData.cpp b/game/geoData.cpp index 80a4eba..30c382c 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -446,11 +446,20 @@ GeoData::setHeights(const std::span triangleStrip) return extrusionDir; }; // Previous half edge end to current half end start arc tangents - const Arc arc {e0, e1}; - const auto limit = std::ceil(arc.length() * 5.F / pi); - const auto inc = arc.length() / limit; - for (float step = 0; step <= limit; step += 1.F) { - const auto direction = sincosf(arc.first + (step * inc)); + if (const Arc arc {e0, e1}; arc.length() < pi) { + const auto limit = std::ceil(arc.length() * 5.F / pi); + const auto inc = arc.length() / limit; + for (float step = 0; step <= limit; step += 1.F) { + const auto direction = sincosf(arc.first + (step * inc)); + VertexHandle extrusionVertex; + extrusionExtents.emplace_back(boundaryVertex, extrusionVertex, + doExtrusion(extrusionVertex, direction, p1, -MAX_SLOPE), + doExtrusion(extrusionVertex, direction, p1, MAX_SLOPE)); + assert(extrusionVertex.is_valid()); + } + } + else { + const auto direction = normalize(e0 + e1) / sinf((arc.length() - pi) / 2.F); VertexHandle extrusionVertex; extrusionExtents.emplace_back(boundaryVertex, extrusionVertex, doExtrusion(extrusionVertex, direction, p1, -MAX_SLOPE), diff --git a/test/fixtures/geoData/deform/1.json b/test/fixtures/geoData/deform/1.json index fb45ce4..6930238 100644 --- a/test/fixtures/geoData/deform/1.json +++ b/test/fixtures/geoData/deform/1.json @@ -156,5 +156,46 @@ "/tmp/geoData5.tga" ] ] + ], + [ + [ + [ + 1500, + 2000, + 800 + ], + [ + 3000, + 2000, + 800 + ], + [ + 5000, + 4000, + 800 + ], + [ + 3500, + 700, + 800 + ] + ], + [ + [ + [ + [ + -1000, + -3000, + 7000 + ], + [ + 1, + 1, + -1.5 + ] + ], + "/tmp/geoData6.tga" + ] + ] ] ] -- cgit v1.2.3 From e844a8f4499d55430490e8382002a6a0f1dced4a Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 23 Mar 2024 22:04:14 +0000 Subject: Dedupe addition of extrusions --- game/geoData.cpp | 65 ++++++++++++++++++++++++++++---------------------------- 1 file changed, 32 insertions(+), 33 deletions(-) diff --git a/game/geoData.cpp b/game/geoData.cpp index 30c382c..544fae2 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -422,49 +422,48 @@ GeoData::setHeights(const std::span triangleStrip) const auto e0 = glm::normalize(vector_normal(RelativePosition2D(p1 - p0))); const auto e1 = glm::normalize(vector_normal(RelativePosition2D(p2 - p1))); - const auto doExtrusion = [this](VertexHandle & extrusionVertex, Direction2D direction, - GlobalPosition3D boundaryVertex, RelativeDistance vert) { - const auto extrusionDir = glm::normalize(direction || vert); - - if (!extrusionVertex.is_valid()) { - if (const auto intersect = intersectRay({boundaryVertex, extrusionDir})) { - auto splitVertex = split(intersect->second, intersect->first); - extrusionVertex = splitVertex; + const auto addExtrusionFor = [this, &extrusionExtents, boundaryVertex, p1](Direction2D direction) { + const auto doExtrusion = [this](VertexHandle & extrusionVertex, Direction2D direction, + GlobalPosition3D boundaryVertex, RelativeDistance vert) { + const auto extrusionDir = glm::normalize(direction || vert); + + if (!extrusionVertex.is_valid()) { + if (const auto intersect = intersectRay({boundaryVertex, extrusionDir})) { + auto splitVertex = split(intersect->second, intersect->first); + extrusionVertex = splitVertex; + } + else if (const auto intersect + = intersectRay({boundaryVertex + GlobalPosition3D {1, 1, 0}, extrusionDir})) { + auto splitVertex = split(intersect->second, intersect->first); + extrusionVertex = splitVertex; + } + else if (const auto intersect + = intersectRay({boundaryVertex + GlobalPosition3D {1, 0, 0}, extrusionDir})) { + auto splitVertex = split(intersect->second, intersect->first); + extrusionVertex = splitVertex; + } } - else if (const auto intersect - = intersectRay({boundaryVertex + GlobalPosition3D {1, 1, 0}, extrusionDir})) { - auto splitVertex = split(intersect->second, intersect->first); - extrusionVertex = splitVertex; - } - else if (const auto intersect - = intersectRay({boundaryVertex + GlobalPosition3D {1, 0, 0}, extrusionDir})) { - auto splitVertex = split(intersect->second, intersect->first); - extrusionVertex = splitVertex; - } - } - return extrusionDir; + return extrusionDir; + }; + + VertexHandle extrusionVertex; + extrusionExtents.emplace_back(boundaryVertex, extrusionVertex, + doExtrusion(extrusionVertex, direction, p1, -MAX_SLOPE), + doExtrusion(extrusionVertex, direction, p1, MAX_SLOPE)); + assert(extrusionVertex.is_valid()); }; - // Previous half edge end to current half end start arc tangents if (const Arc arc {e0, e1}; arc.length() < pi) { + // Previous half edge end to current half end start arc tangents const auto limit = std::ceil(arc.length() * 5.F / pi); const auto inc = arc.length() / limit; for (float step = 0; step <= limit; step += 1.F) { - const auto direction = sincosf(arc.first + (step * inc)); - VertexHandle extrusionVertex; - extrusionExtents.emplace_back(boundaryVertex, extrusionVertex, - doExtrusion(extrusionVertex, direction, p1, -MAX_SLOPE), - doExtrusion(extrusionVertex, direction, p1, MAX_SLOPE)); - assert(extrusionVertex.is_valid()); + addExtrusionFor(sincosf(arc.first + (step * inc))); } } else { - const auto direction = normalize(e0 + e1) / sinf((arc.length() - pi) / 2.F); - VertexHandle extrusionVertex; - extrusionExtents.emplace_back(boundaryVertex, extrusionVertex, - doExtrusion(extrusionVertex, direction, p1, -MAX_SLOPE), - doExtrusion(extrusionVertex, direction, p1, MAX_SLOPE)); - assert(extrusionVertex.is_valid()); + // Single tangent bisecting the difference + addExtrusionFor(normalize(e0 + e1) / sinf((arc.length() - pi) / 2.F)); } }, *voh_begin(newVerts.front())); -- cgit v1.2.3 From ee598b61e65e5af588f2cf577845f95f4fce9546 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 30 Mar 2024 13:47:54 +0000 Subject: Handle almost straight edges with a simple bisect --- game/geoData.cpp | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) diff --git a/game/geoData.cpp b/game/geoData.cpp index 544fae2..2339195 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -382,6 +382,7 @@ void GeoData::setHeights(const std::span triangleStrip) { static const RelativeDistance MAX_SLOPE = 1.5F; + static const RelativeDistance MIN_ARC = 0.01F; if (triangleStrip.size() < 3) { return; @@ -453,7 +454,10 @@ GeoData::setHeights(const std::span triangleStrip) doExtrusion(extrusionVertex, direction, p1, MAX_SLOPE)); assert(extrusionVertex.is_valid()); }; - if (const Arc arc {e0, e1}; arc.length() < pi) { + if (const Arc arc {e0, e1}; arc.length() < MIN_ARC) { + addExtrusionFor(normalize(e0 + e1) / cosf(arc.length() / 2.F)); + } + else if (arc.length() < pi) { // Previous half edge end to current half end start arc tangents const auto limit = std::ceil(arc.length() * 5.F / pi); const auto inc = arc.length() / limit; -- cgit v1.2.3 From 944100110d8f168db3a26d26d3757819f463fdbc Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 31 Mar 2024 12:15:47 +0100 Subject: Don't save original face handles Not required, likely to change anyway. --- game/geoData.cpp | 12 ++++-------- 1 file changed, 4 insertions(+), 8 deletions(-) diff --git a/game/geoData.cpp b/game/geoData.cpp index 2339195..af7d006 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -395,14 +395,10 @@ GeoData::setHeights(const std::span triangleStrip) return add_vertex(tsVert); }); // Create new faces - std::vector newFaces; - newFaces.reserve(newVerts.size() - 2); - std::transform( - strip_begin(newVerts), strip_end(newVerts), std::back_inserter(newFaces), [this](const auto & newVert) { - const auto [a, b, c] = newVert; - auto faceHandle = add_face(a, b, c); - return faceHandle; - }); + std::for_each(strip_begin(newVerts), strip_end(newVerts), [this](const auto & newVert) { + const auto [a, b, c] = newVert; + add_face(a, b, c); + }); // Extrude corners struct Extrusion { -- cgit v1.2.3 From cbc270c1df38e37f608d9786a88c019ff30f2191 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 31 Mar 2024 12:52:34 +0100 Subject: Split faces with two large boundary sides --- game/geoData.cpp | 25 +++++++++++++++++++++++++ 1 file changed, 25 insertions(+) diff --git a/game/geoData.cpp b/game/geoData.cpp index af7d006..d179c47 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -383,6 +383,14 @@ GeoData::setHeights(const std::span triangleStrip) { static const RelativeDistance MAX_SLOPE = 1.5F; static const RelativeDistance MIN_ARC = 0.01F; + static const RelativeDistance MAX_EDGE_LENGTH = 20'000.F; + + auto diff = [this](const auto heh) { + return RelativePosition3D(point(to_vertex_handle(heh)) - point(from_vertex_handle(heh))); + }; + auto hehlength = [diff](const auto heh) { + return glm::length(diff(heh)); + }; if (triangleStrip.size() < 3) { return; @@ -399,6 +407,23 @@ GeoData::setHeights(const std::span triangleStrip) const auto [a, b, c] = newVert; add_face(a, b, c); }); + // Split faces with two large boundary sides + boundaryWalk( + [this, hehlength](const auto boundaryHeh) { + const auto nextHeh = next_halfedge_handle(boundaryHeh); + const auto faceHandle = opposite_face_handle(boundaryHeh); + if (faceHandle != opposite_face_handle(nextHeh)) { + return; + } + if (hehlength(boundaryHeh) < MAX_EDGE_LENGTH || hehlength(nextHeh) < MAX_EDGE_LENGTH) { + return; + } + + const auto t = triangle<3>(faceHandle); + const auto centre = t * RelativePosition2D {.3F, .3F}; + split(faceHandle, centre); + }, + *voh_begin(newVerts.front())); // Extrude corners struct Extrusion { -- cgit v1.2.3 From ac71ff90e86baa549904794375ebb2f9245d92b2 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 31 Mar 2024 20:31:15 +0100 Subject: Split long boundary edges --- game/geoData.cpp | 16 ++++++++++++++++ 1 file changed, 16 insertions(+) diff --git a/game/geoData.cpp b/game/geoData.cpp index d179c47..931eb6a 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -391,6 +391,9 @@ GeoData::setHeights(const std::span triangleStrip) auto hehlength = [diff](const auto heh) { return glm::length(diff(heh)); }; + auto hehcentre = [this, diff](const auto heh) { + return point(from_vertex_handle(heh)) + (diff(heh) / 2.F); + }; if (triangleStrip.size() < 3) { return; @@ -424,6 +427,19 @@ GeoData::setHeights(const std::span triangleStrip) split(faceHandle, centre); }, *voh_begin(newVerts.front())); + // Split long boundary edges + while ([hehlength, hehcentre, this, start = *voh_begin(newVerts.front())]() { + size_t countSplit = 0; + boundaryWalk( + [this, &countSplit, hehlength, hehcentre](const auto boundaryHeh) { + if (hehlength(boundaryHeh) > MAX_EDGE_LENGTH) { + split(edge_handle(boundaryHeh), hehcentre(boundaryHeh)); + ++countSplit; + } + }, + start); + return countSplit; + }() > 0) { } // Extrude corners struct Extrusion { -- cgit v1.2.3 From 6810d01af98a67f39a7698f7d16339eb58dbef25 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 31 Mar 2024 21:58:18 +0100 Subject: Factor out some helper lambdas into members --- game/geoData.cpp | 40 ++++++++++++++++++++++++---------------- game/geoData.h | 3 +++ 2 files changed, 27 insertions(+), 16 deletions(-) diff --git a/game/geoData.cpp b/game/geoData.cpp index 931eb6a..ccad9e0 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -352,6 +352,24 @@ GeoData::findBoundaryStart() const }); } +[[nodiscard]] RelativePosition3D +GeoData::difference(const HalfedgeHandle heh) const +{ + return point(to_vertex_handle(heh)) - point(from_vertex_handle(heh)); +} + +[[nodiscard]] RelativeDistance +GeoData::length(const HalfedgeHandle heh) const +{ + return glm::length(difference(heh)); +} + +[[nodiscard]] GlobalPosition3D +GeoData::centre(const HalfedgeHandle heh) const +{ + return point(from_vertex_handle(heh)) + (difference(heh) / 2.F); +} + void GeoData::update_vertex_normals_only() { @@ -385,16 +403,6 @@ GeoData::setHeights(const std::span triangleStrip) static const RelativeDistance MIN_ARC = 0.01F; static const RelativeDistance MAX_EDGE_LENGTH = 20'000.F; - auto diff = [this](const auto heh) { - return RelativePosition3D(point(to_vertex_handle(heh)) - point(from_vertex_handle(heh))); - }; - auto hehlength = [diff](const auto heh) { - return glm::length(diff(heh)); - }; - auto hehcentre = [this, diff](const auto heh) { - return point(from_vertex_handle(heh)) + (diff(heh) / 2.F); - }; - if (triangleStrip.size() < 3) { return; } @@ -412,13 +420,13 @@ GeoData::setHeights(const std::span triangleStrip) }); // Split faces with two large boundary sides boundaryWalk( - [this, hehlength](const auto boundaryHeh) { + [this](const auto boundaryHeh) { const auto nextHeh = next_halfedge_handle(boundaryHeh); const auto faceHandle = opposite_face_handle(boundaryHeh); if (faceHandle != opposite_face_handle(nextHeh)) { return; } - if (hehlength(boundaryHeh) < MAX_EDGE_LENGTH || hehlength(nextHeh) < MAX_EDGE_LENGTH) { + if (length(boundaryHeh) < MAX_EDGE_LENGTH || length(nextHeh) < MAX_EDGE_LENGTH) { return; } @@ -428,12 +436,12 @@ GeoData::setHeights(const std::span triangleStrip) }, *voh_begin(newVerts.front())); // Split long boundary edges - while ([hehlength, hehcentre, this, start = *voh_begin(newVerts.front())]() { + while ([this, start = *voh_begin(newVerts.front())]() { size_t countSplit = 0; boundaryWalk( - [this, &countSplit, hehlength, hehcentre](const auto boundaryHeh) { - if (hehlength(boundaryHeh) > MAX_EDGE_LENGTH) { - split(edge_handle(boundaryHeh), hehcentre(boundaryHeh)); + [this, &countSplit](const auto boundaryHeh) { + if (length(boundaryHeh) > MAX_EDGE_LENGTH) { + split(edge_handle(boundaryHeh), centre(boundaryHeh)); ++countSplit; } }, diff --git a/game/geoData.h b/game/geoData.h index 5671954..88eb304 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -109,6 +109,9 @@ protected: [[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; + [[nodiscard]] RelativeDistance length(const HalfedgeHandle) const; + [[nodiscard]] GlobalPosition3D centre(const HalfedgeHandle) const; void update_vertex_normals_only(); -- cgit v1.2.3 From a4b3f04803aceb9c750d4317a3e7cf3e56996518 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Mon, 1 Apr 2024 20:07:00 +0100 Subject: Replace face 4-way split Fixes integer rounding issue and returns the new face handles --- game/geoData.cpp | 56 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ game/geoData.h | 3 +++ 2 files changed, 59 insertions(+) diff --git a/game/geoData.cpp b/game/geoData.cpp index ccad9e0..059b03d 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -396,6 +396,62 @@ GeoData::triangleContainsTriangle(const Triangle<2> & a, const Triangle<2> & b) return triangleContainsPoint(a.x, b) && triangleContainsPoint(a.y, b) && triangleContainsPoint(a.z, b); } +std::array +GeoData::split(FaceHandle _fh) +{ + // Collect halfedges of face + const HalfedgeHandle he0 = halfedge_handle(_fh); + const HalfedgeHandle he1 = next_halfedge_handle(he0); + const HalfedgeHandle he2 = next_halfedge_handle(he1); + + const EdgeHandle eh0 = edge_handle(he0); + const EdgeHandle eh1 = edge_handle(he1); + const EdgeHandle eh2 = edge_handle(he2); + + // Collect points of face + const VertexHandle p0 = to_vertex_handle(he0); + const VertexHandle p1 = to_vertex_handle(he1); + const VertexHandle p2 = to_vertex_handle(he2); + + // Calculate midpoint coordinates + const Point new0 = centre(he0); + const Point new1 = centre(he1); + const Point new2 = centre(he2); + + // Add vertices at midpoint coordinates + const VertexHandle v0 = add_vertex(new0); + const VertexHandle v1 = add_vertex(new1); + const VertexHandle v2 = add_vertex(new2); + + const bool split0 = !is_boundary(eh0); + const bool split1 = !is_boundary(eh1); + const bool split2 = !is_boundary(eh2); + + // delete original face + delete_face(_fh, false); + + // split boundary edges of deleted face ( if not boundary ) + if (split0) { + split(eh0, v0); + } + + if (split1) { + split(eh1, v1); + } + + if (split2) { + split(eh2, v2); + } + + // Retriangulate + return { + add_face(v0, p0, v1), + add_face(p2, v0, v2), + add_face(v2, v1, p1), + add_face(v2, v0, v1), + }; +} + void GeoData::setHeights(const std::span triangleStrip) { diff --git a/game/geoData.h b/game/geoData.h index 88eb304..6dacd9a 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -115,6 +115,9 @@ protected: void update_vertex_normals_only(); + using OpenMesh::TriMesh_ArrayKernelT::split; + std::array split(FaceHandle); + private: GlobalPosition3D lowerExtent {}, upperExtent {}; }; -- cgit v1.2.3 From d384c5dc548cf6d6a0cce0db744fc3b168d7be96 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Mon, 1 Apr 2024 20:08:56 +0100 Subject: Add lots of simple triangle property helpers --- game/geoData.h | 70 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 68 insertions(+), 2 deletions(-) diff --git a/game/geoData.h b/game/geoData.h index 6dacd9a..03bc159 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -61,11 +61,69 @@ public: }); } + [[nodiscard]] glm::vec operator*(BaryPosition bari) const { - const auto & t {*this}; - return t[0] + (RelativePosition(t[1] - t[0]) * bari.x) + (RelativePosition(t[2] - t[0]) * bari.y); + return p(0) + (difference(p(0), p(1)) * bari.x) + (difference(p(0), p(2)) * bari.y); + } + + [[nodiscard]] + auto + area() const + requires(Dim == 3) + { + return glm::length(crossProduct(difference(p(0), p(1)), difference(p(0), p(2)))) / 2.F; + } + + [[nodiscard]] + Normal3D + normal() const + requires(Dim == 3) + { + return crossProduct(difference(p(0), p(1)), difference(p(0), p(2))); + } + + [[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); } }; @@ -110,6 +168,14 @@ protected: [[nodiscard]] static bool triangleContainsTriangle(const Triangle<2> &, const Triangle<2> &); [[nodiscard]] HalfedgeHandle findBoundaryStart() const; [[nodiscard]] RelativePosition3D difference(const HalfedgeHandle) const; + + template + [[nodiscard]] static RelativePosition + difference(const GlobalPosition a, const GlobalPosition b) + { + return b - a; + } + [[nodiscard]] RelativeDistance length(const HalfedgeHandle) const; [[nodiscard]] GlobalPosition3D centre(const HalfedgeHandle) const; -- cgit v1.2.3 From 3d2f9a86e56f16b2111822802aa49e28367d851e Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Mon, 1 Apr 2024 21:02:57 +0100 Subject: Boundary edge and one time split with repeated 4-way split of large faces --- game/geoData.cpp | 42 +++++++++++------------------------------- 1 file changed, 11 insertions(+), 31 deletions(-) diff --git a/game/geoData.cpp b/game/geoData.cpp index 059b03d..1d11fda 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -457,7 +457,6 @@ GeoData::setHeights(const std::span triangleStrip) { static const RelativeDistance MAX_SLOPE = 1.5F; static const RelativeDistance MIN_ARC = 0.01F; - static const RelativeDistance MAX_EDGE_LENGTH = 20'000.F; if (triangleStrip.size() < 3) { return; @@ -474,36 +473,17 @@ GeoData::setHeights(const std::span triangleStrip) const auto [a, b, c] = newVert; add_face(a, b, c); }); - // Split faces with two large boundary sides - boundaryWalk( - [this](const auto boundaryHeh) { - const auto nextHeh = next_halfedge_handle(boundaryHeh); - const auto faceHandle = opposite_face_handle(boundaryHeh); - if (faceHandle != opposite_face_handle(nextHeh)) { - return; - } - if (length(boundaryHeh) < MAX_EDGE_LENGTH || length(nextHeh) < MAX_EDGE_LENGTH) { - return; - } - - const auto t = triangle<3>(faceHandle); - const auto centre = t * RelativePosition2D {.3F, .3F}; - split(faceHandle, centre); - }, - *voh_begin(newVerts.front())); - // Split long boundary edges - while ([this, start = *voh_begin(newVerts.front())]() { - size_t countSplit = 0; - boundaryWalk( - [this, &countSplit](const auto boundaryHeh) { - if (length(boundaryHeh) > MAX_EDGE_LENGTH) { - split(edge_handle(boundaryHeh), centre(boundaryHeh)); - ++countSplit; - } - }, - start); - return countSplit; - }() > 0) { } + for (auto start = faces_sbegin(); std::any_of(start, faces_end(), [this, &start](const auto fh) { + static constexpr auto MAX_FACE_AREA = 100'000'000.F; + if (triangle<3>(fh).area() > MAX_FACE_AREA) { + split(fh); + start = FaceIter {*this, FaceHandle(fh), true}; + return true; + } + return false; + });) { + ; + } // Extrude corners struct Extrusion { -- cgit v1.2.3 From 2865ce32bc00e6c05c2686215880085b23aecabf Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Tue, 2 Apr 2024 20:37:23 +0100 Subject: Tests for triangle helpers --- test/test-geoData.cpp | 17 +++++++++++++++++ 1 file changed, 17 insertions(+) diff --git a/test/test-geoData.cpp b/test/test-geoData.cpp index 2d6b1aa..0a2de8d 100644 --- a/test/test-geoData.cpp +++ b/test/test-geoData.cpp @@ -192,6 +192,23 @@ BOOST_DATA_TEST_CASE(walkTerrainUntil, BOOST_CHECK_EQUAL_COLLECTIONS(visited.begin(), visited.end(), visits.begin(), visits.end()); } +BOOST_AUTO_TEST_CASE(triangle_helpers) +{ + constexpr static GeoData::Triangle<3> t {{0, 0, 0}, {5, 0, 0}, {5, 5, 0}}; + + BOOST_CHECK_EQUAL(t.nnormal(), up); + BOOST_CHECK_CLOSE(t.angle(0), quarter_pi, 0.01F); + BOOST_CHECK_CLOSE(t.angleAt({0, 0, 0}), quarter_pi, 0.01F); + BOOST_CHECK_CLOSE(t.angle(1), half_pi, 0.01F); + BOOST_CHECK_CLOSE(t.angleAt({5, 0, 0}), half_pi, 0.01F); + BOOST_CHECK_CLOSE(t.angle(2), quarter_pi, 0.01F); + BOOST_CHECK_CLOSE(t.angleAt({5, 5, 0}), quarter_pi, 0.01F); + + BOOST_CHECK_CLOSE(t.angleAt({0, 1, 0}), 0.F, 0.01F); + + BOOST_CHECK_CLOSE(t.area(), 12.5F, 0.01F); +} + using FindEntiesData = std::tuple; BOOST_DATA_TEST_CASE(findEntries, -- cgit v1.2.3 From 666f4603ee94148e41b4433a7f7a02d2f79d4651 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Thu, 4 Apr 2024 19:57:41 +0100 Subject: Update normals only as required --- game/geoData.cpp | 22 ++++++++++++++++------ game/geoData.h | 1 + 2 files changed, 17 insertions(+), 6 deletions(-) diff --git a/game/geoData.cpp b/game/geoData.cpp index 1d11fda..9211369 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -373,11 +373,19 @@ GeoData::centre(const HalfedgeHandle heh) const void GeoData::update_vertex_normals_only() { - for (auto vh : all_vertices()) { - Normal3D n; - calc_vertex_normal_correct(vh, n); - this->set_normal(vh, glm::normalize(n)); - } + update_vertex_normals_only(vertices_sbegin()); +} + +void +GeoData::update_vertex_normals_only(VertexIter start) +{ + 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)); + } + }); } bool @@ -462,6 +470,8 @@ GeoData::setHeights(const std::span triangleStrip) return; } + const auto initialVertexCount = static_cast(n_vertices()); + // Create new vertices std::vector newVerts; newVerts.reserve(newVerts.size()); @@ -653,6 +663,6 @@ GeoData::setHeights(const std::span triangleStrip) }); // Tidy up + update_vertex_normals_only(VertexIter {*this, vertex_handle(initialVertexCount), true}); garbage_collection(); - update_vertex_normals_only(); } diff --git a/game/geoData.h b/game/geoData.h index 03bc159..021b4c7 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -180,6 +180,7 @@ protected: [[nodiscard]] GlobalPosition3D centre(const HalfedgeHandle) const; void update_vertex_normals_only(); + void update_vertex_normals_only(VertexIter start); using OpenMesh::TriMesh_ArrayKernelT::split; std::array split(FaceHandle); -- cgit v1.2.3 From 352b00a1eeefba9cb1fddbb43d8d7d4fa94f3e25 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Thu, 4 Apr 2024 20:04:13 +0100 Subject: Don't garbage collect the terrain mesh Use skipping iterators instead, GC would be implicit during save/load --- game/geoData.cpp | 9 ++++----- game/terrain.cpp | 4 ++-- 2 files changed, 6 insertions(+), 7 deletions(-) diff --git a/game/geoData.cpp b/game/geoData.cpp index 9211369..ed4303b 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -107,11 +107,11 @@ GeoData::createFlat(GlobalPosition2D lower, GlobalPosition2D upper, GlobalDistan OpenMesh::FaceHandle GeoData::findPoint(GlobalPosition2D p) const { - return findPoint(p, *faces_begin()); + return findPoint(p, *faces_sbegin()); } GeoData::PointFace::PointFace(const GlobalPosition2D p, const GeoData * mesh) : - PointFace {p, mesh, *mesh->faces_begin()} + PointFace {p, mesh, *mesh->faces_sbegin()} { } @@ -135,7 +135,7 @@ GeoData::PointFace::face(const GeoData * mesh, FaceHandle start) const GeoData::FaceHandle GeoData::PointFace::face(const GeoData * mesh) const { - return face(mesh, *mesh->faces_begin()); + return face(mesh, *mesh->faces_sbegin()); } namespace { @@ -347,7 +347,7 @@ GeoData::triangleContainsPoint(const GlobalPosition2D p, FaceHandle face) const GeoData::HalfedgeHandle GeoData::findBoundaryStart() const { - return *std::find_if(halfedges_begin(), halfedges_end(), [this](const auto heh) { + return *std::find_if(halfedges_sbegin(), halfedges_end(), [this](const auto heh) { return is_boundary(heh); }); } @@ -664,5 +664,4 @@ GeoData::setHeights(const std::span triangleStrip) // Tidy up update_vertex_normals_only(VertexIter {*this, vertex_handle(initialVertexCount), true}); - garbage_collection(); } diff --git a/game/terrain.cpp b/game/terrain.cpp index 7f59b6c..91a228f 100644 --- a/game/terrain.cpp +++ b/game/terrain.cpp @@ -30,14 +30,14 @@ Terrain::generateMeshes() std::vector vertices; vertices.reserve(geoData->n_vertices()); std::map vertexIndex; - std::transform(geoData->vertices_begin(), geoData->vertices_end(), std::back_inserter(vertices), + std::transform(geoData->vertices_sbegin(), geoData->vertices_end(), std::back_inserter(vertices), [this, &vertexIndex](const GeoData::VertexHandle v) { vertexIndex.emplace(v, vertexIndex.size()); const auto p = geoData->point(v); return Vertex {p, RelativePosition2D(p) / 10000.F, geoData->normal(v)}; }); std::for_each( - geoData->faces_begin(), geoData->faces_end(), [this, &vertexIndex, &indices](const GeoData::FaceHandle f) { + 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](const GeoData::VertexHandle v) { return vertexIndex[v]; -- cgit v1.2.3 From 1fd3c4baf8b8acf97e343a0cd01455d23f2e9daf Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Thu, 4 Apr 2024 20:06:27 +0100 Subject: Remove wireframe mode from test renders --- test/test-geoData.cpp | 2 -- 1 file changed, 2 deletions(-) diff --git a/test/test-geoData.cpp b/test/test-geoData.cpp index 0a2de8d..fb9aba0 100644 --- a/test/test-geoData.cpp +++ b/test/test-geoData.cpp @@ -244,9 +244,7 @@ BOOST_DATA_TEST_CASE(deform, loadFixtureJson("geoData/deform/ void content(const SceneShader & shader) const override { - glPolygonMode(GL_FRONT_AND_BACK, GL_LINE); terrain.render(shader); - glPolygonMode(GL_FRONT_AND_BACK, GL_FILL); } void -- cgit v1.2.3