From dbd181a9e49b3b32400eb812ff224074413d2ef4 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Tue, 12 Nov 2024 20:19:03 +0000 Subject: Add linesIntersectAt function 2 dimensional line intersection point --- lib/maths.h | 29 +++++++++++++++++++++++++++++ test/test-maths.cpp | 8 ++++++++ 2 files changed, 37 insertions(+) diff --git a/lib/maths.h b/lib/maths.h index 14a29d1..f6130e7 100644 --- a/lib/maths.h +++ b/lib/maths.h @@ -5,6 +5,7 @@ #include #include #include +#include #include #include @@ -326,6 +327,34 @@ normalize(T ang) return ang; } +template using CalcType = std::conditional_t, T, int64_t>; + +template +[[nodiscard]] constexpr std::optional> +linesIntersectAt(const glm::vec<2, T, Q> Aabs, const glm::vec<2, T, Q> Babs, const glm::vec<2, T, Q> Cabs, + const glm::vec<2, T, Q> Dabs) +{ + using CT = CalcType; + using CVec = glm::vec<2, CT, Q>; + // Line AB represented as a1x + b1y = c1 + const CVec Brel = Babs - Aabs; + const CT a1 = Brel.y; + const CT b1 = -Brel.x; + + // Line CD represented as a2x + b2y = c2 + const CVec Crel = Cabs - Aabs, Del = Dabs - Aabs; + const CT a2 = Del.y - Crel.y; + const CT b2 = Crel.x - Del.x; + const CT c2 = (a2 * Crel.x) + (b2 * Crel.y); + + const auto determinant = (a1 * b2) - (a2 * b1); + + if (determinant == 0) { + return std::nullopt; + } + return Aabs + CVec {(b1 * c2) / -determinant, (a1 * c2) / determinant}; +} + template std::pair, bool> find_arc_centre(glm::vec<2, T, Q> start, Rotation2D startDir, glm::vec<2, T, Q> end, Rotation2D endDir) diff --git a/test/test-maths.cpp b/test/test-maths.cpp index f7f34b3..b9d08bb 100644 --- a/test/test-maths.cpp +++ b/test/test-maths.cpp @@ -333,3 +333,11 @@ BOOST_DATA_TEST_CASE(rayLineDistance, BOOST_CHECK_LE(Ray(c, direction).distanceToLine(n1, n2), 0.01F); } } + +static_assert(linesIntersectAt(glm::ivec2 {10, 10}, {40, 40}, {10, 80}, {20, 40}).value().x == 24); +static_assert(linesIntersectAt(glm::vec2 {10, 10}, {40, 40}, {10, 80}, {20, 40}).value().y == 24); +static_assert(linesIntersectAt(GlobalPosition2D {311000100, 491100100}, {311050000, 491150000}, {312000100, 491200100}, + {311000100, 491100100}) + .value() + == GlobalPosition2D {311000100, 491100100}); +static_assert(!linesIntersectAt(glm::dvec2 {0, 1}, {0, 4}, {1, 8}, {1, 4}).has_value()); -- cgit v1.2.3 From 2fc952be58133c2fa5608e17c2f1ae535efa4b33 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Wed, 13 Nov 2024 00:00:35 +0000 Subject: First version rewrite of terrain deformation, much still to do --- game/geoData.cpp | 281 ++++++++++++++++++------------------------------------- 1 file changed, 93 insertions(+), 188 deletions(-) diff --git a/game/geoData.cpp b/game/geoData.cpp index d212651..c228e2a 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -464,212 +464,117 @@ GeoData::split(FaceHandle _fh) add_face(v2, v0, v1); } +static constexpr RelativeDistance MAX_SLOPE = .5F; + void -GeoData::setHeights(const std::span triangleStrip, const Surface & newFaceSurface) +GeoData::setHeights(const std::span triangleStrip, const Surface &) { - static const RelativeDistance MAX_SLOPE = 1.5F; - static const RelativeDistance MIN_ARC = 0.01F; - if (triangleStrip.size() < 3) { return; } + const auto stripMinMax = std::ranges::minmax(triangleStrip, {}, &GlobalPosition3D::z); + lowerExtent.z = std::min(upperExtent.z, stripMinMax.min.z); + upperExtent.z = std::max(upperExtent.z, stripMinMax.max.z); const auto initialVertexCount = static_cast(n_vertices()); - // Create new vertices + // New vertices for each vertex in triangleStrip 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 - const auto initialFaceCount = static_cast(n_faces()); - std::for_each(strip_begin(newVerts), strip_end(newVerts), [this](const auto & newVert) { - const auto [a, b, c] = newVert; - add_face(a, b, c); - }); - for (auto fhi = FaceIter {*this, FaceHandle {initialFaceCount}, true}; fhi != faces_end(); fhi++) { - static constexpr auto MAX_FACE_AREA = 100'000'000.F; - const auto fh = *fhi; - if (triangle<3>(fh).area() > MAX_FACE_AREA) { - split(fh); - } - } - std::vector newFaces; - std::copy_if(FaceIter {*this, FaceHandle {initialFaceCount}, true}, faces_end(), std::back_inserter(newFaces), - [this](FaceHandle fh) { - return !this->status(fh).deleted(); + std::transform( + triangleStrip.begin(), triangleStrip.end(), std::back_inserter(newVerts), [this](const auto tsPoint) { + return split(findPoint(tsPoint), tsPoint); }); - // Extrude corners - struct Extrusion { - VertexHandle boundaryVertex, extrusionVertex; - Direction3D lowerLimit, upperLimit; + // Create temporary triangles from triangleStrip + std::vector> strip; + std::transform( + strip_begin(triangleStrip), strip_end(triangleStrip), std::back_inserter(strip), [](const auto & newVert) { + const auto [a, b, c] = newVert; + return Triangle<3> {a, b, c}; + }); + auto getTriangle = [&strip](const auto point) -> const Triangle<3> * { + if (const auto t = std::ranges::find_if(strip, + [point](const auto & triangle) { + return triangleContainsPoint(point, triangle); + }); + t != strip.end()) { + return &*t; + } + return nullptr; }; - 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(prevBoundaryVertex); - 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 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; - } - } - - 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()); - }; - 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; - for (float step = 0; step <= limit; step += 1.F) { - addExtrusionFor(sincos(arc.first + (step * inc))); - } - } - else { - // Single tangent bisecting the difference - addExtrusionFor(normalize(e0 + e1) / sinf((arc.length() - pi) / 2.F)); - } - }, - *voh_begin(newVerts.front())); - - // Cut existing terrain - extrusionExtents.emplace_back(extrusionExtents.front()); // Circular next - std::vector> boundaryFaces; - for (const auto & [first, second] : extrusionExtents | std::views::adjacent<2>) { - const auto p0 = point(first.boundaryVertex); - const auto p1 = point(second.boundaryVertex); - const auto bdir = RelativePosition3D(p1 - p0); - const auto make_plane = [p0](auto y, auto z) { - return GeometricPlaneT {p0, crossProduct(y, z)}; - }; - const auto planes = ((first.boundaryVertex == second.boundaryVertex) - ? std::array {make_plane(second.lowerLimit, first.lowerLimit), - make_plane(second.upperLimit, first.upperLimit), - } - : std::array { - make_plane(bdir, second.lowerLimit), - make_plane(bdir, second.upperLimit), - }); - assert(planes.front().normal.z > 0.F); - assert(planes.back().normal.z > 0.F); - - auto & out = boundaryFaces.emplace_back(); - out.emplace_back(first.boundaryVertex); - out.emplace_back(first.extrusionVertex); - for (auto currentVertex = first.extrusionVertex; - !find_halfedge(currentVertex, second.extrusionVertex).is_valid();) { - [[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); - 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); - 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 {ep1, -dir}; - const auto dists = planes * [r](const auto & plane) { - RelativeDistance dist {}; - if (r.intersectPlane(plane.origin, plane.normal, dist)) { - return dist; - } - 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); + // Cut along each edge of triangleStrip AB, AC, BC, BD, CD, CE etc + std::map *> boundaryTriangles; + auto doBoundaryPart + = [this, &boundaryTriangles](VertexHandle start, VertexHandle end, const Triangle<3> & triangle) { + boundaryTriangles.emplace(start, &triangle); + const auto endPoint = point(end); + while (std::any_of(voh_begin(start), voh_end(start), [&](const auto & outHalf) { + const auto next = next_halfedge_handle(outHalf); + if (next == end) { + return false; + } + const auto startPoint = point(start); + const auto nextStartPoint = point(from_vertex_handle(next)); + const auto nextEndPoint = point(to_vertex_handle(next)); + if (linesCross(startPoint, endPoint, nextStartPoint, nextEndPoint)) { + if (const auto intersection = linesIntersectAt( + startPoint.xy(), endPoint.xy(), nextStartPoint.xy(), nextEndPoint.xy())) { + start = split(edge_handle(next), positionOnTriangle(*intersection, triangle)); + boundaryTriangles.emplace(start, &triangle); return true; } - return false; - }); - assert(n); + } + return false; + })) { } + }; + auto doBoundary = [&doBoundaryPart, triangle = strip.begin()](const auto & verts) mutable { + const auto & [a, b, c] = verts; + doBoundaryPart(a, b, *triangle); + doBoundaryPart(a, c, *triangle); + triangle++; + }; + std::ranges::for_each(newVerts | std::views::adjacent<3>, doBoundary); + doBoundaryPart(newVerts.back(), *++newVerts.rbegin(), *strip.rbegin()); + + std::set done; + std::set todo; + auto todoOutHalfEdges = [&todo, &done, this](const VertexHandle v) { + std::copy_if(voh_begin(v), voh_end(v), std::inserter(todo, todo.end()), [&done](const auto & h) { + return !done.contains(h); + }); + }; + std::ranges::for_each(newVerts, todoOutHalfEdges); + while (!todo.empty()) { + const auto heh = todo.extract(todo.begin()).value(); + const auto fromVertex = from_vertex_handle(heh); + const auto toVertex = to_vertex_handle(heh); + const auto & fromPoint = point(fromVertex); + auto & toPoint = point(toVertex); + auto toTriangle = getTriangle(toPoint); + if (!toTriangle) { + if (const auto boundaryVertex = boundaryTriangles.find(toVertex); + boundaryVertex != boundaryTriangles.end()) { + toTriangle = boundaryVertex->second; + } } - out.emplace_back(second.extrusionVertex); - if (first.boundaryVertex != second.boundaryVertex) { - out.emplace_back(second.boundaryVertex); + if (toTriangle) { // point within the new strip, adjust vertically by triangle + toPoint.z = positionOnTriangle(toPoint, *toTriangle).z; + todoOutHalfEdges(toVertex); } - } - - // Remove old faces - std::set visited; - auto removeOld = [&](auto & self, const auto face) -> void { - if (visited.insert(face).second) { - std::for_each(fh_begin(face), fh_end(face), [&](const auto 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); + else if (!toTriangle) { // point without the new strip, adjust vertically by limit + const auto maxOffset = static_cast(MAX_SLOPE * glm::length(difference(heh).xy())); + const auto newHeight = std::clamp(toPoint.z, fromPoint.z - maxOffset, fromPoint.z + maxOffset); + if (newHeight != toPoint.z) { + toPoint.z = newHeight; + std::copy_if(voh_begin(toVertex), voh_end(toVertex), std::inserter(todo, todo.end()), + [this, &boundaryTriangles](const auto & heh) { + return !boundaryTriangles.contains(to_vertex_handle(heh)); + }); + } } - }; - 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 + done.insert(heh); + } update_vertex_normals_only(VertexIter {*this, vertex_handle(initialVertexCount), true}); - - std::for_each(newFaces.begin(), newFaces.end(), [&newFaceSurface, this](const auto fh) { - property(surface, fh) = &newFaceSurface; - }); } -- cgit v1.2.3 From e63a70d1b0f947e581d206188700ac170a52ec91 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Thu, 14 Nov 2024 01:03:32 +0000 Subject: Reverse order of last boundary part addition It's the manual last end, shame it has to be weird. --- game/geoData.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/game/geoData.cpp b/game/geoData.cpp index c228e2a..bf9aee0 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -536,7 +536,7 @@ GeoData::setHeights(const std::span triangleStrip, const triangle++; }; std::ranges::for_each(newVerts | std::views::adjacent<3>, doBoundary); - doBoundaryPart(newVerts.back(), *++newVerts.rbegin(), *strip.rbegin()); + doBoundaryPart(*++newVerts.rbegin(), newVerts.back(), *strip.rbegin()); std::set done; std::set todo; -- cgit v1.2.3 From 272f46f548506680af212187ff420918241670fe Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Thu, 14 Nov 2024 01:12:42 +0000 Subject: Fix do bounary part iteration Exit when current vertex is adjacent to the end --- game/geoData.cpp | 34 ++++++++++++++++------------------ 1 file changed, 16 insertions(+), 18 deletions(-) diff --git a/game/geoData.cpp b/game/geoData.cpp index bf9aee0..f84f4e2 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -510,24 +510,22 @@ GeoData::setHeights(const std::span triangleStrip, const = [this, &boundaryTriangles](VertexHandle start, VertexHandle end, const Triangle<3> & triangle) { boundaryTriangles.emplace(start, &triangle); const auto endPoint = point(end); - while (std::any_of(voh_begin(start), voh_end(start), [&](const auto & outHalf) { - const auto next = next_halfedge_handle(outHalf); - if (next == end) { - return false; - } - const auto startPoint = point(start); - const auto nextStartPoint = point(from_vertex_handle(next)); - const auto nextEndPoint = point(to_vertex_handle(next)); - if (linesCross(startPoint, endPoint, nextStartPoint, nextEndPoint)) { - if (const auto intersection = linesIntersectAt( - startPoint.xy(), endPoint.xy(), nextStartPoint.xy(), nextEndPoint.xy())) { - start = split(edge_handle(next), positionOnTriangle(*intersection, triangle)); - boundaryTriangles.emplace(start, &triangle); - return true; - } - } - return false; - })) { } + while (!std::ranges::contains(vv_range(start), end) + && std::ranges::any_of(voh_range(start), [&](const auto & outHalf) { + const auto next = next_halfedge_handle(outHalf); + const auto startPoint = point(start); + const auto nextStartPoint = point(from_vertex_handle(next)); + const auto nextEndPoint = point(to_vertex_handle(next)); + if (linesCross(startPoint, endPoint, nextStartPoint, nextEndPoint)) { + if (const auto intersection = linesIntersectAt(startPoint.xy(), endPoint.xy(), + nextStartPoint.xy(), nextEndPoint.xy())) { + start = split(edge_handle(next), positionOnTriangle(*intersection, triangle)); + boundaryTriangles.emplace(start, &triangle); + return true; + } + } + return false; + })) { } }; auto doBoundary = [&doBoundaryPart, triangle = strip.begin()](const auto & verts) mutable { const auto & [a, b, c] = verts; -- cgit v1.2.3 From 692d569eae8f199cad609dbde8161998e8586ede Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Thu, 14 Nov 2024 02:53:00 +0000 Subject: Reuse existing vertices when processing boundary parts --- game/geoData.cpp | 50 +++++++++++++++++++++++++++++--------------------- 1 file changed, 29 insertions(+), 21 deletions(-) diff --git a/game/geoData.cpp b/game/geoData.cpp index f84f4e2..fcaea64 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -506,27 +506,35 @@ GeoData::setHeights(const std::span triangleStrip, const // Cut along each edge of triangleStrip AB, AC, BC, BD, CD, CE etc std::map *> boundaryTriangles; - auto doBoundaryPart - = [this, &boundaryTriangles](VertexHandle start, VertexHandle end, const Triangle<3> & triangle) { - boundaryTriangles.emplace(start, &triangle); - const auto endPoint = point(end); - while (!std::ranges::contains(vv_range(start), end) - && std::ranges::any_of(voh_range(start), [&](const auto & outHalf) { - const auto next = next_halfedge_handle(outHalf); - const auto startPoint = point(start); - const auto nextStartPoint = point(from_vertex_handle(next)); - const auto nextEndPoint = point(to_vertex_handle(next)); - if (linesCross(startPoint, endPoint, nextStartPoint, nextEndPoint)) { - if (const auto intersection = linesIntersectAt(startPoint.xy(), endPoint.xy(), - nextStartPoint.xy(), nextEndPoint.xy())) { - start = split(edge_handle(next), positionOnTriangle(*intersection, triangle)); - boundaryTriangles.emplace(start, &triangle); - return true; - } - } - return false; - })) { } - }; + auto doBoundaryPart = [this, &boundaryTriangles]( + VertexHandle start, VertexHandle end, const Triangle<3> & triangle) { + boundaryTriangles.emplace(start, &triangle); + const auto endPoint = point(end); + while (!std::ranges::contains(vv_range(start), end) + && std::ranges::any_of(voh_range(start), [&](const auto & outHalf) { + const auto next = next_halfedge_handle(outHalf); + const auto startPoint = point(start); + const auto nextStartPoint = point(from_vertex_handle(next)); + const auto nextEndPoint = point(to_vertex_handle(next)); + if (linesCross(startPoint, endPoint, nextStartPoint, nextEndPoint)) { + if (const auto intersection = linesIntersectAt( + startPoint.xy(), endPoint.xy(), nextStartPoint.xy(), nextEndPoint.xy())) { + const auto distS = glm::length(difference(*intersection, nextStartPoint.xy())); + const auto distE = glm::length(difference(*intersection, nextEndPoint.xy())); + if (const auto mdist = std::min({distS, distE}); mdist < 500.F) { + start = (mdist == distS) ? from_vertex_handle(next) : to_vertex_handle(next); + point(start) = positionOnTriangle(*intersection, triangle); + } + else { + start = split(edge_handle(next), positionOnTriangle(*intersection, triangle)); + } + boundaryTriangles.emplace(start, &triangle); + return true; + } + } + return false; + })) { } + }; auto doBoundary = [&doBoundaryPart, triangle = strip.begin()](const auto & verts) mutable { const auto & [a, b, c] = verts; doBoundaryPart(a, b, *triangle); -- cgit v1.2.3 From e75b8bc4b8494c1295a29dbafa6c7876a2bec0ce Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 16 Nov 2024 00:32:18 +0000 Subject: Reuse existing vertices when processing strip vertices --- game/geoData.cpp | 20 +++++++++++++++++--- 1 file changed, 17 insertions(+), 3 deletions(-) diff --git a/game/geoData.cpp b/game/geoData.cpp index fcaea64..f070391 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -481,9 +481,23 @@ GeoData::setHeights(const std::span triangleStrip, const // New vertices for each vertex in triangleStrip std::vector newVerts; newVerts.reserve(newVerts.size()); - std::transform( - triangleStrip.begin(), triangleStrip.end(), std::back_inserter(newVerts), [this](const auto tsPoint) { - return split(findPoint(tsPoint), tsPoint); + std::transform(triangleStrip.begin(), triangleStrip.end(), std::back_inserter(newVerts), + [this, &newVerts](const auto tsPoint) { + const auto face = findPoint(tsPoint); + if (const auto nearest = std::ranges::min(std::views::iota(fv_begin(face), fv_end(face)) + | std::views::filter([&newVerts](const auto v) { + return !std::ranges::contains(newVerts, *v); + }) + | std::views::transform([this, &tsPoint](const auto v) { + return std::make_pair( + *v, glm::length(difference(this->point(*v).xy(), tsPoint.xy()))); + }), + {}, &std::pair::second); + nearest.second < 500.F) { + point(nearest.first) = tsPoint; + return nearest.first; + } + return split(face, tsPoint); }); // Create temporary triangles from triangleStrip -- cgit v1.2.3 From e0532b80c340a704726d585f038fa88abc96c5e7 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 23 Nov 2024 12:14:24 +0000 Subject: Share code between boundary and strip edge node reuse --- game/geoData.cpp | 42 +++++++++++++++++++++++------------------- 1 file changed, 23 insertions(+), 19 deletions(-) diff --git a/game/geoData.cpp b/game/geoData.cpp index f070391..fef7c34 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -478,22 +478,22 @@ GeoData::setHeights(const std::span triangleStrip, const const auto initialVertexCount = static_cast(n_vertices()); + const auto vertexDistFrom = [this](GlobalPosition2D p) { + return [p, this](const VertexHandle v) { + return std::make_pair(v, glm::length(difference(this->point(v).xy(), p))); + }; + }; + // New vertices for each vertex in triangleStrip std::vector newVerts; newVerts.reserve(newVerts.size()); std::transform(triangleStrip.begin(), triangleStrip.end(), std::back_inserter(newVerts), - [this, &newVerts](const auto tsPoint) { + [this, &newVerts, &vertexDistFrom](const auto tsPoint) { const auto face = findPoint(tsPoint); if (const auto nearest = std::ranges::min(std::views::iota(fv_begin(face), fv_end(face)) - | std::views::filter([&newVerts](const auto v) { - return !std::ranges::contains(newVerts, *v); - }) - | std::views::transform([this, &tsPoint](const auto v) { - return std::make_pair( - *v, glm::length(difference(this->point(*v).xy(), tsPoint.xy()))); - }), + | std::views::transform(vertexDistFrom(tsPoint)), {}, &std::pair::second); - nearest.second < 500.F) { + nearest.second < 500.F && !std::ranges::contains(newVerts, nearest.first)) { point(nearest.first) = tsPoint; return nearest.first; } @@ -520,7 +520,7 @@ GeoData::setHeights(const std::span triangleStrip, const // Cut along each edge of triangleStrip AB, AC, BC, BD, CD, CE etc std::map *> boundaryTriangles; - auto doBoundaryPart = [this, &boundaryTriangles]( + auto doBoundaryPart = [this, &boundaryTriangles, &newVerts, &vertexDistFrom]( VertexHandle start, VertexHandle end, const Triangle<3> & triangle) { boundaryTriangles.emplace(start, &triangle); const auto endPoint = point(end); @@ -528,15 +528,19 @@ GeoData::setHeights(const std::span triangleStrip, const && std::ranges::any_of(voh_range(start), [&](const auto & outHalf) { const auto next = next_halfedge_handle(outHalf); const auto startPoint = point(start); - const auto nextStartPoint = point(from_vertex_handle(next)); - const auto nextEndPoint = point(to_vertex_handle(next)); - if (linesCross(startPoint, endPoint, nextStartPoint, nextEndPoint)) { - if (const auto intersection = linesIntersectAt( - startPoint.xy(), endPoint.xy(), nextStartPoint.xy(), nextEndPoint.xy())) { - const auto distS = glm::length(difference(*intersection, nextStartPoint.xy())); - const auto distE = glm::length(difference(*intersection, nextEndPoint.xy())); - if (const auto mdist = std::min({distS, distE}); mdist < 500.F) { - start = (mdist == distS) ? from_vertex_handle(next) : to_vertex_handle(next); + const auto nexts = std::array {from_vertex_handle(next), to_vertex_handle(next)}; + const auto nextPoints = nexts | std::views::transform([this](const auto v) { + return std::make_pair(v, this->point(v)); + }); + if (linesCross(startPoint, endPoint, nextPoints.front().second, nextPoints.back().second)) { + if (const auto intersection = linesIntersectAt(startPoint.xy(), endPoint.xy(), + nextPoints.front().second.xy(), nextPoints.back().second.xy())) { + if (const auto nextDist + = std::ranges::min(nexts | std::views::transform(vertexDistFrom(*intersection)), + {}, &std::pair::second); + nextDist.second < 500.F && !boundaryTriangles.contains(nextDist.first) + && !std::ranges::contains(newVerts, nextDist.first)) { + start = nextDist.first; point(start) = positionOnTriangle(*intersection, triangle); } else { -- cgit v1.2.3 From 1523401911b46d220ddc597c136fe279324d600b Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 23 Nov 2024 14:04:28 +0000 Subject: Remove split face specialisation --- game/geoData.cpp | 54 ------------------------------------------------------ game/geoData.h | 3 --- 2 files changed, 57 deletions(-) diff --git a/game/geoData.cpp b/game/geoData.cpp index fef7c34..a63e03b 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -410,60 +410,6 @@ 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::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 - add_face(v0, p0, v1); - add_face(p2, v0, v2); - add_face(v2, v1, p1); - add_face(v2, v0, v1); -} - static constexpr RelativeDistance MAX_SLOPE = .5F; void diff --git a/game/geoData.h b/game/geoData.h index ed1734c..5daa7a4 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -185,9 +185,6 @@ protected: void update_vertex_normals_only(); void update_vertex_normals_only(VertexIter start); - using OpenMesh::TriMesh_ArrayKernelT::split; - void split(FaceHandle); - private: GlobalPosition3D lowerExtent {}, upperExtent {}; }; -- cgit v1.2.3 From 2be260117a757288d419cf1564ccd6b91794399e Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 23 Nov 2024 14:18:56 +0000 Subject: Pass setHeights options as a struct with defaults --- game/geoData.cpp | 15 +++++++-------- game/geoData.h | 11 ++++++++++- test/test-geoData.cpp | 2 +- 3 files changed, 18 insertions(+), 10 deletions(-) diff --git a/game/geoData.cpp b/game/geoData.cpp index a63e03b..cc9a056 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -410,10 +410,8 @@ GeoData::triangleContainsTriangle(const Triangle<2> & a, const Triangle<2> & b) return triangleContainsPoint(a.x, b) && triangleContainsPoint(a.y, b) && triangleContainsPoint(a.z, b); } -static constexpr RelativeDistance MAX_SLOPE = .5F; - void -GeoData::setHeights(const std::span triangleStrip, const Surface &) +GeoData::setHeights(const std::span triangleStrip, const SetHeightsOpts & opts) { if (triangleStrip.size() < 3) { return; @@ -434,12 +432,12 @@ GeoData::setHeights(const std::span triangleStrip, const std::vector newVerts; newVerts.reserve(newVerts.size()); std::transform(triangleStrip.begin(), triangleStrip.end(), std::back_inserter(newVerts), - [this, &newVerts, &vertexDistFrom](const auto tsPoint) { + [this, &newVerts, &vertexDistFrom, &opts](const auto tsPoint) { const auto face = findPoint(tsPoint); if (const auto nearest = std::ranges::min(std::views::iota(fv_begin(face), fv_end(face)) | std::views::transform(vertexDistFrom(tsPoint)), {}, &std::pair::second); - nearest.second < 500.F && !std::ranges::contains(newVerts, nearest.first)) { + nearest.second < opts.nearNodeTolerance && !std::ranges::contains(newVerts, nearest.first)) { point(nearest.first) = tsPoint; return nearest.first; } @@ -466,7 +464,7 @@ GeoData::setHeights(const std::span triangleStrip, const // Cut along each edge of triangleStrip AB, AC, BC, BD, CD, CE etc std::map *> boundaryTriangles; - auto doBoundaryPart = [this, &boundaryTriangles, &newVerts, &vertexDistFrom]( + auto doBoundaryPart = [this, &boundaryTriangles, &newVerts, &vertexDistFrom, &opts]( VertexHandle start, VertexHandle end, const Triangle<3> & triangle) { boundaryTriangles.emplace(start, &triangle); const auto endPoint = point(end); @@ -484,7 +482,8 @@ GeoData::setHeights(const std::span triangleStrip, const if (const auto nextDist = std::ranges::min(nexts | std::views::transform(vertexDistFrom(*intersection)), {}, &std::pair::second); - nextDist.second < 500.F && !boundaryTriangles.contains(nextDist.first) + nextDist.second < opts.nearNodeTolerance + && !boundaryTriangles.contains(nextDist.first) && !std::ranges::contains(newVerts, nextDist.first)) { start = nextDist.first; point(start) = positionOnTriangle(*intersection, triangle); @@ -534,7 +533,7 @@ GeoData::setHeights(const std::span triangleStrip, const todoOutHalfEdges(toVertex); } else if (!toTriangle) { // point without the new strip, adjust vertically by limit - const auto maxOffset = static_cast(MAX_SLOPE * glm::length(difference(heh).xy())); + const auto maxOffset = static_cast(opts.maxSlope * glm::length(difference(heh).xy())); const auto newHeight = std::clamp(toPoint.z, fromPoint.z - maxOffset, fromPoint.z + maxOffset); if (newHeight != toPoint.z) { toPoint.z = newHeight; diff --git a/game/geoData.h b/game/geoData.h index 5daa7a4..51bb28b 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -142,7 +142,16 @@ public: [[nodiscard]] HalfedgeHandle findEntry(const GlobalPosition2D from, const GlobalPosition2D to) const; - void setHeights(const std::span triangleStrip, const Surface &); + struct SetHeightsOpts { + static constexpr auto DEFAULT_NEAR_NODE_TOLERANACE = 500.F; + static constexpr auto DEFAULT_MAX_SLOPE = 0.5F; + + const Surface & surface; + RelativeDistance nearNodeTolerance = DEFAULT_NEAR_NODE_TOLERANACE; + RelativeDistance maxSlope = DEFAULT_MAX_SLOPE; + }; + + void setHeights(std::span triangleStrip, const SetHeightsOpts &); [[nodiscard]] auto getExtents() const diff --git a/test/test-geoData.cpp b/test/test-geoData.cpp index 35d6bae..17e1741 100644 --- a/test/test-geoData.cpp +++ b/test/test-geoData.cpp @@ -232,7 +232,7 @@ BOOST_DATA_TEST_CASE(deform, loadFixtureJson("geoData/deform/ Surface surface; surface.colorBias = RGB {0, 0, 1}; auto gd = std::make_shared(GeoData::createFlat({0, 0}, {1000000, 1000000}, 100)); - BOOST_CHECK_NO_THROW(gd->setHeights(points, surface)); + BOOST_CHECK_NO_THROW(gd->setHeights(points, {.surface = surface})); ApplicationBase ab; TestMainWindow tmw; -- cgit v1.2.3 From eee7e7ae1e91e42561e1a2b5bec448f04c2b2298 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 24 Nov 2024 00:46:03 +0000 Subject: Add Triangle::centroid --- game/geoData.h | 13 +++++++++++-- 1 file changed, 11 insertions(+), 2 deletions(-) diff --git a/game/geoData.h b/game/geoData.h index 51bb28b..c28dd14 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -53,7 +53,8 @@ public: }; template struct Triangle : public glm::vec<3, glm::vec> { - using base = glm::vec<3, glm::vec>; + using Point = glm::vec; + using base = glm::vec<3, Point>; using base::base; template Triangle(const GeoData * m, Range range) @@ -64,12 +65,20 @@ public: }); } - [[nodiscard]] glm::vec + [[nodiscard]] Point operator*(BaryPosition bari) const { return p(0) + (difference(p(0), p(1)) * bari.x) + (difference(p(0), p(2)) * bari.y); } + [[nodiscard]] Point + centroid() const + { + return [this](std::integer_sequence) { + return Point {(p(0)[axis] + p(1)[axis] + p(2)[axis]) / 3 ...}; + }(std::make_integer_sequence()); + } + [[nodiscard]] auto area() const requires(Dim == 3) -- cgit v1.2.3 From 2a2271fa0f60279a94c0218026cd296fe5b4aee1 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 24 Nov 2024 01:45:31 +0000 Subject: Surface walk to set face surface property --- game/geoData.cpp | 14 ++++++++++++++ 1 file changed, 14 insertions(+) diff --git a/game/geoData.cpp b/game/geoData.cpp index cc9a056..cd0be29 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -545,5 +545,19 @@ GeoData::setHeights(const std::span triangleStrip, const } done.insert(heh); } + + auto surfaceStripWalk = [this, &getTriangle, &opts](const auto & surfaceStripWalk, const auto & face) -> void { + if (!property(surface, face)) { + property(surface, face) = &opts.surface; + std::ranges::for_each( + ff_range(face), [this, &getTriangle, &surfaceStripWalk](const auto & adjacentFaceHandle) { + if (getTriangle(this->triangle<2>(adjacentFaceHandle).centroid())) { + surfaceStripWalk(surfaceStripWalk, adjacentFaceHandle); + } + }); + } + }; + surfaceStripWalk(surfaceStripWalk, findPoint(strip.front().centroid())); + update_vertex_normals_only(VertexIter {*this, vertex_handle(initialVertexCount), true}); } -- cgit v1.2.3 From 2e1a91564c4765dbdc3f633ba0ff8a4af7164503 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Wed, 27 Nov 2024 02:50:06 +0000 Subject: Update new/moved vertex normals --- game/geoData.cpp | 43 ++++++++++++++++++++++++++++--------------- game/geoData.h | 5 +++-- test/test-geoData.cpp | 11 ++++++----- 3 files changed, 37 insertions(+), 22 deletions(-) diff --git a/game/geoData.cpp b/game/geoData.cpp index cd0be29..f43e231 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -66,7 +66,7 @@ GeoData::loadFromAsciiGrid(const std::filesystem::path & input) }); } } - mesh.update_vertex_normals_only(); + mesh.updateAllVertexNormals(); return mesh; }; @@ -105,7 +105,7 @@ GeoData::createFlat(GlobalPosition2D lower, GlobalPosition2D upper, GlobalDistan } } - mesh.update_vertex_normals_only(); + mesh.updateAllVertexNormals(); return mesh; } @@ -377,23 +377,28 @@ GeoData::centre(const HalfedgeHandle heh) const } void -GeoData::update_vertex_normals_only() +GeoData::updateAllVertexNormals() { - update_vertex_normals_only(vertices_sbegin()); + updateAllVertexNormals(vertices()); } +template void -GeoData::update_vertex_normals_only(VertexIter start) +GeoData::updateAllVertexNormals(const R & range) { - std::for_each(start, vertices_end(), [this](const auto vh) { - if (normal(vh) == Normal3D {}) { - Normal3D n; - calc_vertex_normal_correct(vh, n); - this->set_normal(vh, glm::normalize(n)); - } + std::ranges::for_each(range, [this](const auto vertex) { + updateVertexNormal(vertex); }); } +void +GeoData::updateVertexNormal(VertexHandle vertex) +{ + Normal3D n; + calc_vertex_normal_correct(vertex, n); + set_normal(vertex, glm::normalize(n)); +} + bool GeoData::triangleOverlapsTriangle(const Triangle<2> & a, const Triangle<2> & b) { @@ -420,14 +425,18 @@ GeoData::setHeights(const std::span triangleStrip, const lowerExtent.z = std::min(upperExtent.z, stripMinMax.min.z); upperExtent.z = std::max(upperExtent.z, stripMinMax.max.z); - const auto initialVertexCount = static_cast(n_vertices()); - const auto vertexDistFrom = [this](GlobalPosition2D p) { return [p, this](const VertexHandle v) { return std::make_pair(v, glm::length(difference(this->point(v).xy(), p))); }; }; + std::set newOrChangedVerts; + auto addVertexForNormalUpdate = [this, &newOrChangedVerts](const VertexHandle vertex) { + newOrChangedVerts.emplace(vertex); + std::ranges::copy(vv_range(vertex), std::inserter(newOrChangedVerts, newOrChangedVerts.end())); + }; + // New vertices for each vertex in triangleStrip std::vector newVerts; newVerts.reserve(newVerts.size()); @@ -443,6 +452,7 @@ GeoData::setHeights(const std::span triangleStrip, const } return split(face, tsPoint); }); + std::ranges::for_each(newVerts, addVertexForNormalUpdate); // Create temporary triangles from triangleStrip std::vector> strip; @@ -464,7 +474,7 @@ GeoData::setHeights(const std::span triangleStrip, const // Cut along each edge of triangleStrip AB, AC, BC, BD, CD, CE etc std::map *> boundaryTriangles; - auto doBoundaryPart = [this, &boundaryTriangles, &newVerts, &vertexDistFrom, &opts]( + auto doBoundaryPart = [this, &boundaryTriangles, &newVerts, &vertexDistFrom, &opts, &addVertexForNormalUpdate]( VertexHandle start, VertexHandle end, const Triangle<3> & triangle) { boundaryTriangles.emplace(start, &triangle); const auto endPoint = point(end); @@ -491,6 +501,7 @@ GeoData::setHeights(const std::span triangleStrip, const else { start = split(edge_handle(next), positionOnTriangle(*intersection, triangle)); } + addVertexForNormalUpdate(start); boundaryTriangles.emplace(start, &triangle); return true; } @@ -530,6 +541,7 @@ GeoData::setHeights(const std::span triangleStrip, const } if (toTriangle) { // point within the new strip, adjust vertically by triangle toPoint.z = positionOnTriangle(toPoint, *toTriangle).z; + addVertexForNormalUpdate(toVertex); todoOutHalfEdges(toVertex); } else if (!toTriangle) { // point without the new strip, adjust vertically by limit @@ -537,6 +549,7 @@ GeoData::setHeights(const std::span triangleStrip, const const auto newHeight = std::clamp(toPoint.z, fromPoint.z - maxOffset, fromPoint.z + maxOffset); if (newHeight != toPoint.z) { toPoint.z = newHeight; + addVertexForNormalUpdate(toVertex); std::copy_if(voh_begin(toVertex), voh_end(toVertex), std::inserter(todo, todo.end()), [this, &boundaryTriangles](const auto & heh) { return !boundaryTriangles.contains(to_vertex_handle(heh)); @@ -559,5 +572,5 @@ GeoData::setHeights(const std::span triangleStrip, const }; surfaceStripWalk(surfaceStripWalk, findPoint(strip.front().centroid())); - update_vertex_normals_only(VertexIter {*this, vertex_handle(initialVertexCount), true}); + updateAllVertexNormals(newOrChangedVerts); } diff --git a/game/geoData.h b/game/geoData.h index c28dd14..71ec85f 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -200,8 +200,9 @@ protected: [[nodiscard]] RelativeDistance length(const HalfedgeHandle) const; [[nodiscard]] GlobalPosition3D centre(const HalfedgeHandle) const; - void update_vertex_normals_only(); - void update_vertex_normals_only(VertexIter start); + void updateAllVertexNormals(); + template void updateAllVertexNormals(const R &); + void updateVertexNormal(VertexHandle); private: GlobalPosition3D lowerExtent {}, upperExtent {}; diff --git a/test/test-geoData.cpp b/test/test-geoData.cpp index 17e1741..2f3d215 100644 --- a/test/test-geoData.cpp +++ b/test/test-geoData.cpp @@ -31,11 +31,9 @@ BOOST_AUTO_TEST_CASE(loadSuccess) BOOST_AUTO_TEST_CASE(normalsAllPointUp) { - BOOST_CHECK_EQUAL(std::count_if(vertices_begin(), vertices_end(), - [this](auto && vh) { - return normal(vh).z > 0; - }), - n_vertices()); + BOOST_CHECK(std::ranges::all_of(vertices(), [this](auto && vertex) { + return normal(vertex).z > 0; + })); } BOOST_AUTO_TEST_CASE(trianglesContainsPoints) @@ -233,6 +231,9 @@ BOOST_DATA_TEST_CASE(deform, loadFixtureJson("geoData/deform/ surface.colorBias = RGB {0, 0, 1}; auto gd = std::make_shared(GeoData::createFlat({0, 0}, {1000000, 1000000}, 100)); BOOST_CHECK_NO_THROW(gd->setHeights(points, {.surface = surface})); + BOOST_CHECK(std::ranges::all_of(gd->vertices(), [&gd](auto && vertex) { + return gd->normal(vertex).z > 0; + })); ApplicationBase ab; TestMainWindow tmw; -- cgit v1.2.3 From 2d1efc4ff2e8b4bd517fbe0cf5fb1637007dd488 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Fri, 29 Nov 2024 19:58:30 +0000 Subject: Constrained Arithmatic type concept --- lib/maths.h | 46 +++++++++++++++++++++++++--------------------- 1 file changed, 25 insertions(+), 21 deletions(-) diff --git a/lib/maths.h b/lib/maths.h index f6130e7..3959896 100644 --- a/lib/maths.h +++ b/lib/maths.h @@ -9,8 +9,11 @@ #include #include +template +concept Arithmetic = std::is_arithmetic_v; + struct Arc : public std::pair { - template + 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()}} @@ -119,7 +122,7 @@ namespace { } // Helper to lookup into a matrix given an xy vector coordinate - template + template constexpr auto & operator^(glm::mat & matrix, const glm::vec<2, I> rowCol) { @@ -201,7 +204,7 @@ rotate_yp(const glm::vec<2, T, Q> & angles) return rotate_yp(angles.y, angles.x); } -template +template requires(D >= 2) constexpr auto vector_yaw(const glm::vec & diff) @@ -209,7 +212,7 @@ vector_yaw(const glm::vec & diff) return std::atan2(diff.x, diff.y); } -template +template requires(D >= 3) constexpr auto vector_pitch(const glm::vec & diff) @@ -217,7 +220,7 @@ vector_pitch(const glm::vec & diff) return std::atan(diff.z); } -template +template constexpr glm::vec<2, T, Q> vector_normal(const glm::vec<2, T, Q> & vector) { @@ -231,7 +234,7 @@ round_frac(const T value, const T frac) return std::round(value / frac) * frac; } -template +template requires requires(T value) { value * value; } constexpr auto sq(T value) @@ -264,14 +267,15 @@ crossProduct(const glm::vec<3, T, Q> & valueA, const glm::vec<3, T, Q> & valueB) return glm::cross(valueA, valueB); } -template +template constexpr auto ratio(const Ta valueA, const Tb valueB) { - return (static_cast(valueA) / static_cast(valueB)); + using Common = std::common_type_t; + return static_cast((static_cast(valueA) / static_cast(valueB))); } -template +template constexpr auto ratio(const glm::vec<2, T, Q> & value) { @@ -285,14 +289,14 @@ perspective_divide(const glm::vec<4, T, Q> & value) return value / value.w; } -template +template constexpr glm::vec operator||(const glm::vec valueA, const glm::vec valueB) { return {valueA, valueB}; } -template +template constexpr glm::vec operator||(const glm::vec valueA, const T valueB) { @@ -327,9 +331,9 @@ normalize(T ang) return ang; } -template using CalcType = std::conditional_t, T, int64_t>; +template using CalcType = std::conditional_t, T, int64_t>; -template +template [[nodiscard]] constexpr std::optional> linesIntersectAt(const glm::vec<2, T, Q> Aabs, const glm::vec<2, T, Q> Babs, const glm::vec<2, T, Q> Cabs, const glm::vec<2, T, Q> Dabs) @@ -355,7 +359,7 @@ linesIntersectAt(const glm::vec<2, T, Q> Aabs, const glm::vec<2, T, Q> Babs, con return Aabs + CVec {(b1 * c2) / -determinant, (a1 * c2) / determinant}; } -template +template std::pair, bool> find_arc_centre(glm::vec<2, T, Q> start, Rotation2D startDir, glm::vec<2, T, Q> end, Rotation2D endDir) { @@ -368,7 +372,7 @@ find_arc_centre(glm::vec<2, T, Q> start, Rotation2D startDir, glm::vec<2, T, Q> throw std::runtime_error("no intersection"); } -template +template std::pair, bool> find_arc_centre(glm::vec<2, T, Q> start, Angle entrys, glm::vec<2, T, Q> end, Angle entrye) { @@ -378,7 +382,7 @@ find_arc_centre(glm::vec<2, T, Q> start, Angle entrys, glm::vec<2, T, Q> end, An return find_arc_centre(start, sincos(entrys + half_pi), end, sincos(entrye - half_pi)); } -template +template Angle find_arcs_radius(glm::vec<2, T, Q> start, Rotation2D ad, glm::vec<2, T, Q> end, Rotation2D bd) { @@ -403,7 +407,7 @@ find_arcs_radius(glm::vec<2, T, Q> start, Rotation2D ad, glm::vec<2, T, Q> end, / (2 * (sq(X) - 2 * X * Z + sq(Z) + sq(Y) - 2 * Y * W + sq(W) - 4)); } -template +template std::pair find_arcs_radius(glm::vec<2, T, Q> start, Angle entrys, glm::vec<2, T, Q> end, Angle entrye) { @@ -413,7 +417,7 @@ find_arcs_radius(glm::vec<2, T, Q> start, Angle entrys, glm::vec<2, T, Q> end, A return {getrad(-half_pi), getrad(half_pi)}; } -template +template auto midpoint(const std::pair & v) { @@ -421,7 +425,7 @@ midpoint(const std::pair & v) } // std::pow is not constexpr -template +template requires requires(T n) { n *= n; } constexpr T pow(const T base, std::integral auto exp) @@ -434,14 +438,14 @@ pow(const T base, std::integral auto exp) } // Conversions -template +template constexpr auto mph_to_ms(T v) { return v / 2.237L; } -template +template constexpr auto kph_to_ms(T v) { -- cgit v1.2.3 From d982157ee2711f2a28a8ca0dc5f882424626217c Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 1 Dec 2024 14:06:28 +0000 Subject: Remove GeoData::difference for points, use global version --- game/geoData.cpp | 4 ++-- game/geoData.h | 13 +++---------- 2 files changed, 5 insertions(+), 12 deletions(-) diff --git a/game/geoData.cpp b/game/geoData.cpp index f43e231..a5fc4ef 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -361,7 +361,7 @@ GeoData::findBoundaryStart() const [[nodiscard]] RelativePosition3D GeoData::difference(const HalfedgeHandle heh) const { - return point(to_vertex_handle(heh)) - point(from_vertex_handle(heh)); + return ::difference(point(to_vertex_handle(heh)), point(from_vertex_handle(heh))); } [[nodiscard]] RelativeDistance @@ -427,7 +427,7 @@ GeoData::setHeights(const std::span triangleStrip, const const auto vertexDistFrom = [this](GlobalPosition2D p) { return [p, this](const VertexHandle v) { - return std::make_pair(v, glm::length(difference(this->point(v).xy(), p))); + return std::make_pair(v, glm::length(::difference(p, this->point(v).xy()))); }; }; diff --git a/game/geoData.h b/game/geoData.h index 71ec85f..dcc28e0 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -68,7 +68,7 @@ public: [[nodiscard]] Point operator*(BaryPosition bari) const { - return p(0) + (difference(p(0), p(1)) * bari.x) + (difference(p(0), p(2)) * bari.y); + return p(0) + (::difference(p(1), p(0)) * bari.x) + (::difference(p(2), p(0)) * bari.y); } [[nodiscard]] Point @@ -83,14 +83,14 @@ public: area() const requires(Dim == 3) { - return glm::length(crossProduct(difference(p(0), p(1)), difference(p(0), p(2)))) / 2.F; + return glm::length(crossProduct(::difference(p(1), p(0)), ::difference(p(2), p(0)))) / 2.F; } [[nodiscard]] Normal3D normal() const requires(Dim == 3) { - return crossProduct(difference(p(0), p(1)), difference(p(0), p(2))); + return crossProduct(::difference(p(1), p(0)), ::difference(p(2), p(0))); } [[nodiscard]] Normal3D @@ -190,13 +190,6 @@ protected: [[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 f9e6220bf8b17681cb2f395ab64851a72659a070 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 1 Dec 2024 16:56:14 +0000 Subject: Move GeoData::Triangle to global lib --- game/geoData.h | 89 ++++------------------------------------- lib/triangle.h | 108 ++++++++++++++++++++++++++++++++++++++++++++++++++ test/test-geoData.cpp | 2 +- 3 files changed, 117 insertions(+), 82 deletions(-) create mode 100644 lib/triangle.h diff --git a/game/geoData.h b/game/geoData.h index dcc28e0..79924d3 100644 --- a/game/geoData.h +++ b/game/geoData.h @@ -4,6 +4,7 @@ #include "config/types.h" #include "ray.h" #include "surface.h" +#include "triangle.h" #include #include #include @@ -52,85 +53,7 @@ public: mutable FaceHandle _face {}; }; - template struct Triangle : public glm::vec<3, glm::vec> { - using Point = glm::vec; - using base = glm::vec<3, Point>; - using base::base; - - template Triangle(const GeoData * m, Range range) - { - assert(std::distance(range.begin(), range.end()) == 3); - std::transform(range.begin(), range.end(), &base::operator[](0), [m](auto vh) { - return m->point(vh); - }); - } - - [[nodiscard]] Point - operator*(BaryPosition bari) const - { - return p(0) + (::difference(p(1), p(0)) * bari.x) + (::difference(p(2), p(0)) * bari.y); - } - - [[nodiscard]] Point - centroid() const - { - return [this](std::integer_sequence) { - return Point {(p(0)[axis] + p(1)[axis] + p(2)[axis]) / 3 ...}; - }(std::make_integer_sequence()); - } - - [[nodiscard]] auto - area() const - requires(Dim == 3) - { - return glm::length(crossProduct(::difference(p(1), p(0)), ::difference(p(2), p(0)))) / 2.F; - } - - [[nodiscard]] Normal3D - normal() const - requires(Dim == 3) - { - return crossProduct(::difference(p(1), p(0)), ::difference(p(2), p(0))); - } - - [[nodiscard]] Normal3D - nnormal() const - requires(Dim == 3) - { - return glm::normalize(normal()); - } - - [[nodiscard]] auto - angle(glm::length_t c) const - { - return Arc {P(c), P(c + 2), P(c + 1)}.length(); - } - - template - [[nodiscard]] auto - angleAt(const GlobalPosition pos) const - requires(D <= Dim) - { - for (glm::length_t i {}; i < 3; ++i) { - if (GlobalPosition {p(i)} == pos) { - return angle(i); - } - } - return 0.F; - } - - [[nodiscard]] inline auto - p(const glm::length_t i) const - { - return base::operator[](i); - } - - [[nodiscard]] inline auto - P(const glm::length_t i) const - { - return base::operator[](i % 3); - } - }; + template using Triangle = ::Triangle; [[nodiscard]] FaceHandle findPoint(GlobalPosition2D) const; [[nodiscard]] FaceHandle findPoint(GlobalPosition2D, FaceHandle start) const; @@ -178,9 +101,13 @@ public: protected: template [[nodiscard]] Triangle - triangle(FaceHandle f) const + triangle(FaceHandle face) const { - return {this, fv_range(f)}; + Triangle triangle; + std::ranges::transform(fv_range(face), triangle.begin(), [this](auto vertex) { + return point(vertex); + }); + return triangle; } [[nodiscard]] static bool triangleContainsPoint(const GlobalPosition2D, const Triangle<2> &); diff --git a/lib/triangle.h b/lib/triangle.h new file mode 100644 index 0000000..812bfab --- /dev/null +++ b/lib/triangle.h @@ -0,0 +1,108 @@ +#pragma once + +#include "config/types.h" +#include "maths.h" +#include + +template +struct Triangle : public glm::vec<3, glm::vec> { + using Point = glm::vec; + using Base = glm::vec<3, glm::vec>; + using Base::Base; + + [[nodiscard]] constexpr Point + operator*(BaryPosition bari) const + { + return p(0) + (sideDifference(1) * bari.x) + (sideDifference(2) * bari.y); + } + + [[nodiscard]] constexpr Point + centroid() const + { + return [this](std::integer_sequence) { + return Point {(p(0)[Axis] + p(1)[Axis] + p(2)[Axis]) / 3 ...}; + }(std::make_integer_sequence()); + } + + [[nodiscard]] constexpr auto + area() const + requires(Dim == 3) + { + return glm::length(crossProduct(sideDifference(1), sideDifference(2))) / T {2}; + } + + [[nodiscard]] constexpr Normal3D + normal() const + requires(Dim == 3) + { + return crossProduct(sideDifference(1), sideDifference(2)); + } + + [[nodiscard]] constexpr Normal3D + nnormal() const + requires(Dim == 3) + { + return glm::normalize(normal()); + } + + [[nodiscard]] constexpr auto + sideDifference(glm::length_t side) const + { + return difference(p(side), p(0)); + } + + [[nodiscard]] constexpr auto + angle(glm::length_t corner) const + { + return Arc {P(corner), P(corner + 2), P(corner + 1)}.length(); + } + + template + [[nodiscard]] constexpr auto + angleAt(const glm::vec pos) const + requires(D <= Dim) + { + for (glm::length_t i {}; i < 3; ++i) { + if (glm::vec {p(i)} == pos) { + return angle(i); + } + } + return 0.F; + } + + [[nodiscard]] constexpr auto + p(const glm::length_t idx) const + { + return Base::operator[](idx); + } + + [[nodiscard]] constexpr auto + P(const glm::length_t idx) const + { + return Base::operator[](idx % 3); + } + + [[nodiscard]] constexpr Point * + begin() + { + return &(Base::x); + } + + [[nodiscard]] constexpr const Point * + begin() const + { + return &(Base::x); + } + + [[nodiscard]] constexpr Point * + end() + { + return begin() + 3; + } + + [[nodiscard]] constexpr const Point * + end() const + { + return begin() + 3; + } +}; diff --git a/test/test-geoData.cpp b/test/test-geoData.cpp index 2f3d215..bd1ff87 100644 --- a/test/test-geoData.cpp +++ b/test/test-geoData.cpp @@ -40,7 +40,7 @@ BOOST_AUTO_TEST_CASE(trianglesContainsPoints) { const auto face = face_handle(0); - BOOST_TEST_CONTEXT(GeoData::Triangle<2>(this, fv_range(face))) { + BOOST_TEST_CONTEXT(this->triangle<2>(face)) { BOOST_CHECK(triangleContainsPoint(GlobalPosition2D {xllcorner, yllcorner}, face)); BOOST_CHECK(triangleContainsPoint(GlobalPosition2D {xllcorner + cellsize, yllcorner + cellsize}, face)); BOOST_CHECK(triangleContainsPoint(GlobalPosition2D {xllcorner, yllcorner + cellsize}, face)); -- cgit v1.2.3