From 582ac127f763f512c45f35e17b768487e3b51796 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 4 Nov 2023 17:07:58 +0000 Subject: Rename TerrainMesh to GeoData to drop inplace --- game/geoData.cpp | 340 +++++++++++++++++++++++++++++-------------------------- 1 file changed, 182 insertions(+), 158 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index 34a1030..d32bf8c 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -1,214 +1,238 @@ #include "geoData.h" -#include "gfx/image.h" -#include -#include -#include -#include +#include #include -#include -#include #include -#include -#include -#include -#include -#include - -GeoData::GeoData(Limits l, float s) : - limit {std::move(l)}, size {(limit.second - limit.first) + 1}, scale {s}, nodes {[this]() { - return (static_cast(size.x * size.y)); - }()} -{ -} -void -GeoData::generateRandom() +GeoData +GeoData::loadFromAsciiGrid(const std::filesystem::path & input) { - // We acknowledge this is terrible :) - - // Add hills - std::mt19937 gen(std::random_device {}()); - std::uniform_int_distribution<> rxpos(limit.first.x + 2, limit.second.x - 2), - rypos(limit.first.y + 2, limit.second.y - 2); - std::uniform_int_distribution<> rsize(10, 30); - std::uniform_real_distribution rheight(1, 3); - for (int h = 0; h < 500;) { - const glm::ivec2 hpos {rxpos(gen), rypos(gen)}; - const glm::ivec2 hsize {rsize(gen), rsize(gen)}; - if (const auto lim1 = hpos - hsize; lim1.x > limit.first.x && lim1.y > limit.first.y) { - if (const auto lim2 = hpos + hsize; lim2.x < limit.second.x && lim2.y < limit.second.y) { - const auto height = rheight(gen); - const glm::ivec2 hsizesqrd {hsize.x * hsize.x, hsize.y * hsize.y}; - for (auto y = lim1.y; y < lim2.y; y += 1) { - for (auto x = lim1.x; x < lim2.x; x += 1) { - const auto dist {hpos - glm::ivec2 {x, y}}; - const glm::ivec2 distsqrd {dist.x * dist.x, dist.y * dist.y}; - const auto out {ratio(sq(x - hpos.x), sq(hsize.x)) + ratio(sq(y - hpos.y), sq(hsize.y))}; - if (out <= 1.0F) { - auto & node {nodes[at({x, y})]}; - const auto m {1.F / (7.F * out - 8.F) + 1.F}; - node.height += height * m; - } - } - } - h += 1; - } + size_t ncols = 0, nrows = 0, xllcorner = 0, yllcorner = 0, cellsize = 0; + std::map properties { + {"ncols", &ncols}, + {"nrows", &nrows}, + {"xllcorner", &xllcorner}, + {"yllcorner", &yllcorner}, + {"cellsize", &cellsize}, + }; + std::ifstream f {input}; + while (!properties.empty()) { + std::string property; + f >> property; + f >> *properties.at(property); + properties.erase(property); + } + std::vector vertices; + vertices.reserve(ncols * nrows); + GeoData mesh; + mesh.lowerExtent = {xllcorner, yllcorner, std::numeric_limits::max()}; + mesh.upperExtent + = {xllcorner + (cellsize * ncols), yllcorner + (cellsize * nrows), std::numeric_limits::min()}; + for (size_t row = 0; row < nrows; ++row) { + for (size_t col = 0; col < ncols; ++col) { + float height = 0; + f >> height; + mesh.upperExtent.z = std::max(mesh.upperExtent.z, height); + mesh.lowerExtent.z = std::min(mesh.lowerExtent.z, height); + vertices.push_back(mesh.add_vertex({xllcorner + (col * cellsize), yllcorner + (row * cellsize), height})); } } -} + if (!f.good()) { + throw std::runtime_error("Couldn't read terrain file"); + } + 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_face_normals(); + mesh.update_vertex_normals(); -void -GeoData::loadFromImages(const std::filesystem::path & fileName, float scale_) -{ - const Image map {fileName.c_str(), STBI_grey}; - size = {map.width, map.height}; - limit = {{0, 0}, size - glm::uvec2 {1, 1}}; - const auto points {size.x * size.y}; - scale = scale_; - nodes.resize(points); - - std::transform(map.data.data(), map.data.data() + points, nodes.begin(), [](auto d) { - return Node {(d * 0.1F) - 1.5F}; - }); -} + return mesh; +}; -GeoData::Quad -GeoData::quad(glm::vec2 wcoord) const +GeoData +GeoData::createFlat(glm::vec2 lower, glm::vec2 upper, float h) { - constexpr static const std::array corners {{{0, 0}, {0, 1}, {1, 0}, {1, 1}}}; - return transform_array(transform_array(corners, - [coord = (wcoord / scale)](const auto c) { - return glm::vec2 {std::floor(coord.x), std::floor(coord.y)} + c; - }), - [this](const auto c) { - return (c * scale) || nodes[at(c)].height; - }); -} + GeoData mesh; -glm::vec3 -GeoData::positionAt(const glm::vec2 wcoord) const -{ - const auto point {quad(wcoord)}; - const glm::vec2 frac = (wcoord - !point.front()) / scale; - auto edge = [&point, &frac](auto offset) { - return point[offset].z + ((point[offset + 2].z - point[offset].z) * frac.x); - }; - const auto heightFloor = edge(0U), heightCeil = edge(1U), - heightMid = heightFloor + ((heightCeil - heightFloor) * frac.y); + 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}); + + mesh.add_face(ll, uu, lu); + mesh.add_face(ll, ul, uu); - return wcoord || heightMid; + mesh.update_face_normals(); + mesh.update_vertex_normals(); + + return mesh; } -GeoData::RayTracer::RayTracer(glm::vec2 p0, glm::vec2 p1) : RayTracer {p0, p1, glm::abs(p1)} { } -GeoData::RayTracer::RayTracer(glm::vec2 p0, glm::vec2 p1, glm::vec2 d) : - RayTracer {p0, d, byAxis(p0, p1, d, 0), byAxis(p0, p1, d, 1)} +OpenMesh::FaceHandle +GeoData::findPoint(glm::vec2 p) const { + return findPoint(p, *faces_begin()); } -GeoData::RayTracer::RayTracer( - glm::vec2 p0, glm::vec2 d_, std::pair xdata, std::pair ydata) : - p {glm::floor(p0)}, - d {d_}, error {xdata.second - ydata.second}, inc {xdata.first, ydata.first} +GeoData::PointFace::PointFace(const glm::vec2 p, const GeoData * mesh) : PointFace {p, mesh, *mesh->faces_begin()} { } + +GeoData::PointFace::PointFace(const glm::vec2 p, const GeoData * mesh, FaceHandle start) : + PointFace {p, mesh->findPoint(p, start)} { } -std::pair -GeoData::RayTracer::byAxis(glm::vec2 p0, glm::vec2 p1, glm::vec2 d, glm::length_t axis) +GeoData::FaceHandle +GeoData::PointFace::face(const GeoData * mesh, FaceHandle start) const { - using Limits = std::numeric_limits; - static_assert(Limits::has_infinity); - if (d[axis] == 0) { - return {0, Limits::infinity()}; - } - else if (p1[axis] > 0) { - return {1, (std::floor(p0[axis]) + 1.F - p0[axis]) * d[1 - axis]}; + if (_face.is_valid()) { + assert(mesh->triangleContainsPoint(point, _face)); + return _face; } else { - return {-1, (p0[axis] - std::floor(p0[axis])) * d[1 - axis]}; + return (_face = mesh->findPoint(point, start)); } } -glm::vec2 -GeoData::RayTracer::next() +GeoData::FaceHandle +GeoData::PointFace::face(const GeoData * mesh) const { - const glm::vec2 cur {p}; + return face(mesh, *mesh->faces_begin()); +} + +namespace { + [[nodiscard]] constexpr inline bool + pointLeftOfLine(const glm::vec2 p, const glm::vec2 e1, const glm::vec2 e2) + { + return (e2.x - e1.x) * (p.y - e1.y) > (e2.y - e1.y) * (p.x - e1.x); + } - static constexpr const glm::vec2 m {1, -1}; - const int axis = (error > 0) ? 1 : 0; - p[axis] += inc[axis]; - error += d[1 - axis] * m[axis]; + static_assert(pointLeftOfLine({1, 2}, {1, 1}, {2, 2})); + static_assert(pointLeftOfLine({2, 1}, {2, 2}, {1, 1})); + static_assert(pointLeftOfLine({2, 2}, {1, 2}, {2, 1})); + static_assert(pointLeftOfLine({1, 1}, {2, 1}, {1, 2})); - return cur; + [[nodiscard]] constexpr inline bool + linesCross(const glm::vec2 a1, const glm::vec2 a2, const glm::vec2 b1, const glm::vec2 b2) + { + return pointLeftOfLine(a2, b1, b2) && pointLeftOfLine(a1, b2, b1) && pointLeftOfLine(b1, a1, a2) + && pointLeftOfLine(b2, a2, a1); + } + + static_assert(linesCross({1, 1}, {2, 2}, {1, 2}, {2, 1})); } -std::optional -GeoData::intersectRay(const Ray & ray) const +OpenMesh::FaceHandle +GeoData::findPoint(glm::vec2 p, OpenMesh::FaceHandle f) const { - if (glm::length(!ray.direction) <= 0) { - return {}; - } - RayTracer rt {ray.start / scale, ray.direction}; - while (true) { - const auto n {rt.next() * scale}; - try { - const auto point = quad(n); - for (auto offset : {0U, 1U}) { - glm::vec2 bary; - float distance; - if (glm::intersectRayTriangle(ray.start, ray.direction, point[offset], point[offset + 1], - point[offset + 2], bary, distance)) { - return point[offset] + ((point[offset + 1] - point[offset]) * bary[0]) - + ((point[offset + 2] - point[offset]) * bary[1]); + ConstFaceVertexIter vertices; + while (f.is_valid() && !triangleContainsPoint(p, vertices = cfv_iter(f))) { + for (auto next = cfh_iter(f); next.is_valid(); ++next) { + f = opposite_face_handle(*next); + if (f.is_valid()) { + const auto e1 = point(to_vertex_handle(*next)); + const auto e2 = point(to_vertex_handle(opposite_halfedge_handle(*next))); + if (pointLeftOfLine(p, e1, e2)) { + break; } } - } - catch (std::range_error &) { - const auto rel = n / !ray.direction; - if (rel.x > 0 && rel.y > 0) { - return {}; - } + f.reset(); } } + return f; +} - return {}; +glm::vec3 +GeoData::positionAt(const PointFace & p) const +{ + glm::vec3 out {}; + Triangle<3> t {this, fv_range(p.face(this))}; + glm::intersectLineTriangle(p.point ^ 0.F, up, t[0], t[1], t[2], out); + return p.point ^ out[0]; } -unsigned int -GeoData::at(glm::ivec2 coord) const +[[nodiscard]] std::optional +GeoData::intersectRay(const Ray & ray) const { - if (coord.x < limit.first.x || coord.x > limit.second.x || coord.y < limit.first.y || coord.y > limit.second.y) { - throw std::range_error {"Coordinates outside GeoData limits"}; - } - const glm::uvec2 offset = coord - limit.first; - return offset.x + (offset.y * size.x); + return intersectRay(ray, findPoint(ray.start)); } -unsigned int -GeoData::at(int x, int y) const +[[nodiscard]] std::optional +GeoData::intersectRay(const Ray & ray, FaceHandle face) const { - return at({x, y}); + std::optional out; + walkUntil(PointFace {ray.start, face}, ray.start + (ray.direction * 10000.F), [&out, &ray, this](FaceHandle face) { + glm::vec2 bari {}; + float dist {}; + Triangle<3> t {this, fv_range(face)}; + if (glm::intersectRayTriangle(ray.start, ray.direction, t[0], t[1], t[2], bari, dist)) { + out = t * bari; + return true; + } + return false; + }); + return out; } -GeoData::Limits -GeoData::getLimit() const +void +GeoData::walk(const PointFace & from, const glm::vec2 to, const std::function & op) const { - return limit; + walkUntil(from, to, [&op](const auto & fh) { + op(fh); + return false; + }); } -float -GeoData::getScale() const +void +GeoData::walkUntil(const PointFace & from, const glm::vec2 to, const std::function & op) const +{ + assert(from.face(this).is_valid()); // TODO replace with a boundary search + auto f = from.face(this); + FaceHandle previousFace; + while (f.is_valid() && !op(f)) { + for (auto next = cfh_iter(f); next.is_valid(); ++next) { + f = opposite_face_handle(*next); + if (f.is_valid() && f != previousFace) { + const auto e1 = point(to_vertex_handle(*next)); + const auto e2 = point(to_vertex_handle(opposite_halfedge_handle(*next))); + if (linesCross(from.point, to, e1, e2)) { + previousFace = f; + break; + } + } + f.reset(); + } + } +} + +bool +GeoData::triangleContainsPoint(const glm::vec2 p, const glm::vec2 a, const glm::vec2 b, const glm::vec2 c) { - return scale; + const auto det = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); + + return det * ((b.x - a.x) * (p.y - a.y) - (b.y - a.y) * (p.x - a.x)) >= 0 + && det * ((c.x - b.x) * (p.y - b.y) - (c.y - b.y) * (p.x - b.x)) >= 0 + && det * ((a.x - c.x) * (p.y - c.y) - (a.y - c.y) * (p.x - c.x)) >= 0; } -glm::uvec2 -GeoData::getSize() const +bool +GeoData::triangleContainsPoint(const glm::vec2 p, FaceHandle face) const { - return size; + return triangleContainsPoint(p, cfv_iter(face)); } -std::span -GeoData::getNodes() const +bool +GeoData::triangleContainsPoint(const glm::vec2 p, ConstFaceVertexIter vertices) const { - return nodes; + return triangleContainsPoint(p, point(*vertices++), point(*vertices++), point(*vertices++)); } -- cgit v1.2.3 From 5ed36466b48aa347277c70422eb00bee264a5c8b Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 4 Nov 2023 17:07:58 +0000 Subject: Simplify some logic with the triangle construct --- game/geoData.cpp | 26 ++++++++++---------------- 1 file changed, 10 insertions(+), 16 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index d32bf8c..5e49c94 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -135,8 +135,7 @@ namespace { OpenMesh::FaceHandle GeoData::findPoint(glm::vec2 p, OpenMesh::FaceHandle f) const { - ConstFaceVertexIter vertices; - while (f.is_valid() && !triangleContainsPoint(p, vertices = cfv_iter(f))) { + while (f.is_valid() && !triangleContainsPoint(p, triangle<2>(f))) { for (auto next = cfh_iter(f); next.is_valid(); ++next) { f = opposite_face_handle(*next); if (f.is_valid()) { @@ -156,7 +155,7 @@ glm::vec3 GeoData::positionAt(const PointFace & p) const { glm::vec3 out {}; - Triangle<3> t {this, fv_range(p.face(this))}; + const auto t = triangle<3>(p.face(this)); glm::intersectLineTriangle(p.point ^ 0.F, up, t[0], t[1], t[2], out); return p.point ^ out[0]; } @@ -174,7 +173,7 @@ GeoData::intersectRay(const Ray & ray, FaceHandle face) const walkUntil(PointFace {ray.start, face}, ray.start + (ray.direction * 10000.F), [&out, &ray, this](FaceHandle face) { glm::vec2 bari {}; float dist {}; - Triangle<3> t {this, fv_range(face)}; + const auto t = triangle<3>(face); if (glm::intersectRayTriangle(ray.start, ray.direction, t[0], t[1], t[2], bari, dist)) { out = t * bari; return true; @@ -216,23 +215,18 @@ GeoData::walkUntil(const PointFace & from, const glm::vec2 to, const std::functi } bool -GeoData::triangleContainsPoint(const glm::vec2 p, const glm::vec2 a, const glm::vec2 b, const glm::vec2 c) +GeoData::triangleContainsPoint(const glm::vec2 p, const Triangle<2> & t) { - const auto det = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); + const auto mul = [](const glm::vec2 a, const glm::vec2 b, const glm::vec2 c) { + return (a.x - b.x) * (c.y - b.y) - (a.y - b.y) * (c.x - b.x); + }; + const auto det = mul(t[1], t[0], t[2]); - return det * ((b.x - a.x) * (p.y - a.y) - (b.y - a.y) * (p.x - a.x)) >= 0 - && det * ((c.x - b.x) * (p.y - b.y) - (c.y - b.y) * (p.x - b.x)) >= 0 - && det * ((a.x - c.x) * (p.y - c.y) - (a.y - c.y) * (p.x - c.x)) >= 0; + return det * mul(t[1], t[0], p) >= 0 && det * mul(t[2], t[1], p) >= 0 && det * mul(t[0], t[2], p) >= 0; } bool GeoData::triangleContainsPoint(const glm::vec2 p, FaceHandle face) const { - return triangleContainsPoint(p, cfv_iter(face)); -} - -bool -GeoData::triangleContainsPoint(const glm::vec2 p, ConstFaceVertexIter vertices) const -{ - return triangleContainsPoint(p, point(*vertices++), point(*vertices++), point(*vertices++)); + return triangleContainsPoint(p, triangle<2>(face)); } -- cgit v1.2.3 From f53816a8fd9ec15ef03b5bf45472eda46e53c1ad Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 4 Nov 2023 21:05:35 +0000 Subject: Refactor to further simplify line/point operations Adds another perf test --- game/geoData.cpp | 18 +++++++++--------- 1 file changed, 9 insertions(+), 9 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index 5e49c94..c58658a 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -111,12 +111,16 @@ GeoData::PointFace::face(const GeoData * mesh) const } namespace { - [[nodiscard]] constexpr inline bool - pointLeftOfLine(const glm::vec2 p, const glm::vec2 e1, const glm::vec2 e2) + template typename Op> + [[nodiscard]] constexpr inline auto + pointLineOp(const glm::vec2 p, const glm::vec2 e1, const glm::vec2 e2) { - return (e2.x - e1.x) * (p.y - e1.y) > (e2.y - e1.y) * (p.x - e1.x); + return Op {}((e2.x - e1.x) * (p.y - e1.y), (e2.y - e1.y) * (p.x - e1.x)); } + constexpr auto pointLeftOfLine = pointLineOp; + constexpr auto pointLeftOfOrOnLine = pointLineOp; + static_assert(pointLeftOfLine({1, 2}, {1, 1}, {2, 2})); static_assert(pointLeftOfLine({2, 1}, {2, 2}, {1, 1})); static_assert(pointLeftOfLine({2, 2}, {1, 2}, {2, 1})); @@ -217,12 +221,8 @@ GeoData::walkUntil(const PointFace & from, const glm::vec2 to, const std::functi bool GeoData::triangleContainsPoint(const glm::vec2 p, const Triangle<2> & t) { - const auto mul = [](const glm::vec2 a, const glm::vec2 b, const glm::vec2 c) { - return (a.x - b.x) * (c.y - b.y) - (a.y - b.y) * (c.x - b.x); - }; - const auto det = mul(t[1], t[0], t[2]); - - return det * mul(t[1], t[0], p) >= 0 && det * mul(t[2], t[1], p) >= 0 && det * mul(t[0], t[2], p) >= 0; + return pointLeftOfOrOnLine(p, t[0], t[1]) && pointLeftOfOrOnLine(p, t[1], t[2]) + && pointLeftOfOrOnLine(p, t[2], t[0]); } bool -- cgit v1.2.3 From 04078dbb3fe4acd09d150e016c2b2e0d5d036950 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 5 Nov 2023 13:07:32 +0000 Subject: Add methods to walk the boundary of the terrain mesh --- game/geoData.cpp | 45 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 45 insertions(+) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index c58658a..f9c11bf 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -218,6 +218,43 @@ GeoData::walkUntil(const PointFace & from, const glm::vec2 to, const std::functi } } +void +GeoData::boundaryWalk(const std::function & op) const +{ + boundaryWalk(op, findBoundaryStart()); +} + +void +GeoData::boundaryWalk(const std::function & op, HalfedgeHandle start) const +{ + assert(is_boundary(start)); + boundaryWalkUntil( + [&op](auto heh) { + op(heh); + return false; + }, + start); +} + +void +GeoData::boundaryWalkUntil(const std::function & op) const +{ + boundaryWalkUntil(op, findBoundaryStart()); +} + +void +GeoData::boundaryWalkUntil(const std::function & op, HalfedgeHandle start) const +{ + assert(is_boundary(start)); + if (!op(start)) { + for (auto heh = next_halfedge_handle(start); heh != start; heh = next_halfedge_handle(heh)) { + if (op(heh)) { + break; + } + } + } +} + bool GeoData::triangleContainsPoint(const glm::vec2 p, const Triangle<2> & t) { @@ -230,3 +267,11 @@ GeoData::triangleContainsPoint(const glm::vec2 p, FaceHandle face) const { return triangleContainsPoint(p, triangle<2>(face)); } + +GeoData::HalfedgeHandle +GeoData::findBoundaryStart() const +{ + return *std::find_if(halfedges_begin(), halfedges_end(), [this](const auto heh) { + return is_boundary(heh); + }); +} -- cgit v1.2.3 From eb5dea3d035c61327543d7ab527d897ef3768570 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 5 Nov 2023 14:21:14 +0000 Subject: Fix and split linesCross Previous tested they crossed in a specific direction, which is wrong but useful. Adds linesCrossLtR for this use case. --- game/geoData.cpp | 15 +++++++++++++-- 1 file changed, 13 insertions(+), 2 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index f9c11bf..78f753f 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -128,12 +128,23 @@ namespace { [[nodiscard]] constexpr inline bool linesCross(const glm::vec2 a1, const glm::vec2 a2, const glm::vec2 b1, const glm::vec2 b2) + { + return (pointLeftOfLine(a2, b1, b2) == pointLeftOfLine(a1, b2, b1)) + && (pointLeftOfLine(b1, a1, a2) == pointLeftOfLine(b2, a2, a1)); + } + + static_assert(linesCross({1, 1}, {2, 2}, {1, 2}, {2, 1})); + static_assert(linesCross({2, 2}, {1, 1}, {1, 2}, {2, 1})); + + [[nodiscard]] constexpr inline bool + linesCrossLtR(const glm::vec2 a1, const glm::vec2 a2, const glm::vec2 b1, const glm::vec2 b2) { return pointLeftOfLine(a2, b1, b2) && pointLeftOfLine(a1, b2, b1) && pointLeftOfLine(b1, a1, a2) && pointLeftOfLine(b2, a2, a1); } - static_assert(linesCross({1, 1}, {2, 2}, {1, 2}, {2, 1})); + static_assert(linesCrossLtR({1, 1}, {2, 2}, {1, 2}, {2, 1})); + static_assert(!linesCrossLtR({2, 2}, {1, 1}, {1, 2}, {2, 1})); } OpenMesh::FaceHandle @@ -208,7 +219,7 @@ GeoData::walkUntil(const PointFace & from, const glm::vec2 to, const std::functi if (f.is_valid() && f != previousFace) { const auto e1 = point(to_vertex_handle(*next)); const auto e2 = point(to_vertex_handle(opposite_halfedge_handle(*next))); - if (linesCross(from.point, to, e1, e2)) { + if (linesCrossLtR(from.point, to, e1, e2)) { previousFace = f; break; } -- cgit v1.2.3 From acca54f3a12225454633dca2d56506c0dcebb653 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 5 Nov 2023 15:37:13 +0000 Subject: Fix calculating extents --- game/geoData.cpp | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index 78f753f..781b41e 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -25,8 +25,8 @@ GeoData::loadFromAsciiGrid(const std::filesystem::path & input) vertices.reserve(ncols * nrows); GeoData mesh; mesh.lowerExtent = {xllcorner, yllcorner, std::numeric_limits::max()}; - mesh.upperExtent - = {xllcorner + (cellsize * ncols), yllcorner + (cellsize * nrows), std::numeric_limits::min()}; + mesh.upperExtent = {xllcorner + (cellsize * (ncols - 1)), yllcorner + (cellsize * (nrows - 1)), + std::numeric_limits::min()}; for (size_t row = 0; row < nrows; ++row) { for (size_t col = 0; col < ncols; ++col) { float height = 0; -- cgit v1.2.3 From 58402765133fab24d08b64f3752553bd2b8393b9 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 5 Nov 2023 15:52:02 +0000 Subject: Fix todo for handling a terrain walk from outside the mesh --- game/geoData.cpp | 22 ++++++++++++++++++++-- 1 file changed, 20 insertions(+), 2 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index 781b41e..61dedda 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -210,8 +210,10 @@ GeoData::walk(const PointFace & from, const glm::vec2 to, const std::function & op) const { - assert(from.face(this).is_valid()); // TODO replace with a boundary search auto f = from.face(this); + if (!f.is_valid()) { + f = opposite_face_handle(findEntry(from.point, to)); + } FaceHandle previousFace; while (f.is_valid() && !op(f)) { for (auto next = cfh_iter(f); next.is_valid(); ++next) { @@ -241,7 +243,7 @@ GeoData::boundaryWalk(const std::function & op, HalfedgeHa assert(is_boundary(start)); boundaryWalkUntil( [&op](auto heh) { - op(heh); + op(heh); return false; }, start); @@ -266,6 +268,22 @@ GeoData::boundaryWalkUntil(const std::function & op, Halfe } } +GeoData::HalfedgeHandle +GeoData::findEntry(const glm::vec2 from, const glm::vec2 to) const +{ + HalfedgeHandle entry; + boundaryWalkUntil([this, from, to, &entry](auto he) { + const auto e1 = point(to_vertex_handle(he)); + const auto e2 = point(to_vertex_handle(opposite_halfedge_handle(he))); + if (linesCrossLtR(from, to, e1, e2)) { + entry = he; + return true; + } + return false; + }); + return entry; +} + bool GeoData::triangleContainsPoint(const glm::vec2 p, const Triangle<2> & t) { -- cgit v1.2.3 From 685b33980cc7a346574b24732464f0cbe3115a1f Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Wed, 15 Nov 2023 01:29:24 +0000 Subject: Switch to millimeters for spatial units Mostly a case of changing far too many magic numbers, something else to fix I guess. I probably missed something. Also there's some hackery when loading 3D models, which are still assumed to be in metres. --- game/geoData.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index 76550cc..da067f7 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -31,7 +31,7 @@ GeoData::generateRandom() std::uniform_int_distribution<> rxpos(limit.first.x + 2, limit.second.x - 2), rypos(limit.first.y + 2, limit.second.y - 2); std::uniform_int_distribution<> rsize(10, 30); - std::uniform_real_distribution rheight(1, 3); + std::uniform_real_distribution rheight(1000, 3000); for (int h = 0; h < 500;) { const glm::ivec2 hpos {rxpos(gen), rypos(gen)}; const glm::ivec2 hsize {rsize(gen), rsize(gen)}; -- cgit v1.2.3 From 0aa665c3648d788755b00c9e431c872d57fddbb8 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 25 Nov 2023 16:28:39 +0000 Subject: Model positions as integers Introduces test failure in arcs due to rounding, but I don't want to create a complicated fix as link positions are still floats and hopefully that'll go away... somehow --- game/geoData.cpp | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index da067f7..ec990ea 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -73,7 +73,7 @@ GeoData::loadFromImages(const std::filesystem::path & fileName, float scale_) } GeoData::Quad -GeoData::quad(glm::vec2 wcoord) const +GeoData::quad(Position2D wcoord) const { constexpr static const std::array corners {{{0, 0}, {0, 1}, {1, 0}, {1, 1}}}; return transform_array(transform_array(corners, @@ -154,7 +154,7 @@ GeoData::intersectRay(const Ray & ray) const try { const auto point = quad(n); for (auto offset : {0U, 1U}) { - glm::vec2 bary; + BaryPosition bary; float distance; if (glm::intersectRayTriangle(ray.start, ray.direction, point[offset], point[offset + 1], point[offset + 2], bary, distance)) { -- cgit v1.2.3 From 3abe940a22d99939b666bd806214c8b986cb3ed9 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 26 Nov 2023 14:20:28 +0000 Subject: Calculate vertex normals only Doesn't require half edge normals or face normals, which uses Newell's method, which results in integer overflow... Not to mention we don't need all the other normals. --- game/geoData.cpp | 16 ++++++++++++---- 1 file changed, 12 insertions(+), 4 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index 7710efe..70133a9 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -57,8 +57,7 @@ GeoData::loadFromAsciiGrid(const std::filesystem::path & input) }); } } - mesh.update_face_normals(); - mesh.update_vertex_normals(); + mesh.update_vertex_normals_only(); return mesh; }; @@ -77,8 +76,7 @@ GeoData::createFlat(GlobalPosition2D lower, GlobalPosition2D upper, GlobalDistan mesh.add_face(ll, uu, lu); mesh.add_face(ll, ul, uu); - mesh.update_face_normals(); - mesh.update_vertex_normals(); + mesh.update_vertex_normals_only(); return mesh; } @@ -317,3 +315,13 @@ GeoData::findBoundaryStart() const return is_boundary(heh); }); } + +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)); + } +} -- cgit v1.2.3 From 0f56b13766fc6d8b45dabc4febf378756620ab32 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 2 Dec 2023 12:26:36 +0000 Subject: Replace positionAt with pure integer version --- game/geoData.cpp | 15 +++++++++++---- 1 file changed, 11 insertions(+), 4 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index 70133a9..d092d00 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -155,6 +155,16 @@ namespace { static_assert(linesCrossLtR({1, 1}, {2, 2}, {1, 2}, {2, 1})); static_assert(!linesCrossLtR({2, 2}, {1, 1}, {1, 2}, {2, 1})); + + constexpr GlobalPosition3D + positionOnTriangle(const GlobalPosition2D point, const GeoData::Triangle<3> & t) + { + const glm::vec<3, int64_t> a = t[1] - t[0], b = t[2] - t[0]; + const auto n = crossInt(a, b); + return {point, ((n.x * t[0].x) + (n.y * t[0].y) + (n.z * t[0].z) - (n.x * point.x) - (n.y * point.y)) / n.z}; + } + + static_assert(positionOnTriangle({7, -2}, {{1, 2, 3}, {1, 0, 1}, {-2, 1, 0}}) == GlobalPosition3D {7, -2, 3}); } OpenMesh::FaceHandle @@ -179,10 +189,7 @@ GeoData::findPoint(GlobalPosition2D p, OpenMesh::FaceHandle f) const GlobalPosition3D GeoData::positionAt(const PointFace & p) const { - RelativePosition3D out {}; - const auto t = triangle<3>(p.face(this)); - glm::intersectLineTriangle({p.point, 0}, up, t[0], t[1], t[2], out); - return {p.point, out[0]}; + return positionOnTriangle(p.point, triangle<3>(p.face(this))); } [[nodiscard]] std::optional -- cgit v1.2.3 From 0ec5b3f7ee049a45fa6a87101813ea9717eecbbb Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 2 Dec 2023 16:25:27 +0000 Subject: Extend ray for intersect walk to cover the extents of the map --- game/geoData.cpp | 24 +++++++++++++----------- 1 file changed, 13 insertions(+), 11 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index d092d00..6c6f1df 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -202,17 +202,19 @@ GeoData::intersectRay(const Ray & ray) const GeoData::intersectRay(const Ray & ray, FaceHandle face) const { std::optional out; - walkUntil(PointFace {ray.start, face}, ray.start + (ray.direction * 10000.F), [&out, &ray, this](FaceHandle face) { - BaryPosition bari {}; - float dist {}; - const auto t = triangle<3>(face); - if (glm::intersectRayTriangle( - ray.start, ray.direction, t[0], t[1], t[2], bari, dist)) { - out = t * bari; - return true; - } - return false; - }); + walkUntil(PointFace {ray.start, face}, + ray.start.xy() + (ray.direction.xy() * RelativePosition2D(upperExtent.xy() - lowerExtent.xy())), + [&out, &ray, this](FaceHandle face) { + BaryPosition bari {}; + float dist {}; + const auto t = triangle<3>(face); + if (glm::intersectRayTriangle( + ray.start, ray.direction, t[0], t[1], t[2], bari, dist)) { + out = t * bari; + return true; + } + return false; + }); return out; } -- cgit v1.2.3 From 826a380710261961eb339d12d44f1c45fc384131 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 2 Dec 2023 16:36:11 +0000 Subject: Handle the case where the ray never enters the map --- game/geoData.cpp | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index 6c6f1df..e2b7f66 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -232,7 +232,11 @@ GeoData::walkUntil(const PointFace & from, const GlobalPosition2D to, const std: { auto f = from.face(this); if (!f.is_valid()) { - f = opposite_face_handle(findEntry(from.point, to)); + const auto entryEdge = findEntry(from.point, to); + if (!entryEdge.is_valid()) { + return; + } + f = opposite_face_handle(entryEdge); } FaceHandle previousFace; while (f.is_valid() && !op(f)) { -- cgit v1.2.3 From f3f926c97efe365afecd54d06d830961376bae30 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 17 Dec 2023 18:56:23 +0000 Subject: Use new calc types in geoData --- game/geoData.cpp | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) (limited to 'game/geoData.cpp') diff --git a/game/geoData.cpp b/game/geoData.cpp index e2b7f66..97f4a26 100644 --- a/game/geoData.cpp +++ b/game/geoData.cpp @@ -120,7 +120,8 @@ namespace { [[nodiscard]] constexpr inline auto pointLineOp(const GlobalPosition2D p, const GlobalPosition2D e1, const GlobalPosition2D e2) { - return Op {}(int64_t(e2.x - e1.x) * int64_t(p.y - e1.y), int64_t(e2.y - e1.y) * int64_t(p.x - e1.x)); + return Op {}(CalcDistance(e2.x - e1.x) * CalcDistance(p.y - e1.y), + CalcDistance(e2.y - e1.y) * CalcDistance(p.x - e1.x)); } constexpr auto pointLeftOfLine = pointLineOp; @@ -159,7 +160,7 @@ namespace { constexpr GlobalPosition3D positionOnTriangle(const GlobalPosition2D point, const GeoData::Triangle<3> & t) { - const glm::vec<3, int64_t> a = t[1] - t[0], b = t[2] - t[0]; + const CalcPosition3D a = t[1] - t[0], b = t[2] - t[0]; const auto n = crossInt(a, b); return {point, ((n.x * t[0].x) + (n.y * t[0].y) + (n.z * t[0].z) - (n.x * point.x) - (n.y * point.y)) / n.z}; } -- cgit v1.2.3