summaryrefslogtreecommitdiff
path: root/game
diff options
context:
space:
mode:
Diffstat (limited to 'game')
-rw-r--r--game/geoData.cpp218
-rw-r--r--game/geoData.h12
-rw-r--r--game/terrain.cpp2
3 files changed, 220 insertions, 12 deletions
diff --git a/game/geoData.cpp b/game/geoData.cpp
index 359e8c0..1f6768a 100644
--- a/game/geoData.cpp
+++ b/game/geoData.cpp
@@ -1,7 +1,10 @@
#include "geoData.h"
+#include "collections.h"
#include <fstream>
#include <glm/gtx/intersect.hpp>
+#include <math.h>
#include <maths.h>
+#include <set>
GeoData
GeoData::loadFromAsciiGrid(const std::filesystem::path & input)
@@ -62,6 +65,8 @@ GeoData::loadFromAsciiGrid(const std::filesystem::path & input)
return mesh;
};
+template<typename T> constexpr static T GRID_SIZE = 10'000;
+
GeoData
GeoData::createFlat(GlobalPosition2D lower, GlobalPosition2D upper, GlobalDistance h)
{
@@ -70,11 +75,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<VertexHandle> vertices;
+ for (GlobalDistance row = lower.x; row < upper.x; row += GRID_SIZE<GlobalDistance>) {
+ for (GlobalDistance col = lower.y; col < upper.y; col += GRID_SIZE<GlobalDistance>) {
+ 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<size_t>(std::ceil(float(upper.x - lower.x) / GRID_SIZE<RelativeDistance>));
+ const auto ncols = static_cast<size_t>(std::ceil(float(upper.y - lower.y) / GRID_SIZE<RelativeDistance>));
+ 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();
@@ -193,16 +216,16 @@ GeoData::positionAt(const PointFace & p) const
return positionOnTriangle(p.point, triangle<3>(p.face(this)));
}
-[[nodiscard]] std::optional<GlobalPosition3D>
+[[nodiscard]] GeoData::IntersectionResult
GeoData::intersectRay(const Ray<GlobalPosition3D> & ray) const
{
return intersectRay(ray, findPoint(ray.start));
}
-[[nodiscard]] std::optional<GlobalPosition3D>
+[[nodiscard]] GeoData::IntersectionResult
GeoData::intersectRay(const Ray<GlobalPosition3D> & ray, FaceHandle face) const
{
- std::optional<GlobalPosition3D> out;
+ GeoData::IntersectionResult out;
walkUntil(PointFace {ray.start, face},
ray.start.xy() + (ray.direction.xy() * RelativePosition2D(upperExtent.xy() - lowerExtent.xy())),
[&out, &ray, this](FaceHandle face) {
@@ -210,7 +233,7 @@ GeoData::intersectRay(const Ray<GlobalPosition3D> & 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;
@@ -338,3 +361,182 @@ 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);
+}
+
+void
+GeoData::setHeights(const std::span<const GlobalPosition3D> triangleStrip)
+{
+ std::set<EdgeHandle> nosplit;
+ // Create new vertices
+ std::vector<VertexHandle> 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<FaceHandle> 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<HalfedgeHandle> boundary;
+ boundaryWalk(
+ [out = std::back_inserter(boundary)](const auto boundaryHeh) mutable {
+ out = boundaryHeh;
+ },
+ *voh_begin(newVerts.front()));
+
+ // Extrude corners
+ std::set<VertexHandle> cutpoints;
+ std::vector<std::pair<GlobalPosition3D, GlobalPosition3D>> extrusionExtents;
+ std::vector<VertexHandle> extrusionVertices;
+ std::transform(boundary.begin(), boundary.end(), std::back_inserter(extrusionExtents),
+ [this, &nosplit, &cutpoints, &extrusionVertices](const auto boundaryHeh) {
+ const auto vectorNormal
+ = []<typename T, glm::qualifier Q>(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 + 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<std::vector<VertexHandle>> 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<Triangle<3>, 4> triangles {{
+ {p0, ex->first, nex->first},
+ {p0, p1, nex->first},
+ {p0, ex->second, nex->second},
+ {p0, p1, nex->second},
+ }};
+
+ std::vector<VertexHandle> 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<FaceHandle> visited;
+ auto removeOld = [&](auto & self, const auto face) -> void {
+ if (visited.insert(face).second) {
+ std::vector<FaceHandle> 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 15143e8..5671954 100644
--- a/game/geoData.h
+++ b/game/geoData.h
@@ -65,7 +65,7 @@ public:
operator*(BaryPosition bari) const
{
const auto & t {*this};
- return t[0] + (RelativePosition<Dim>(t[1] - t[0]) * bari.x) + (RelativePosition<Dim>(t[2] - t[1]) * bari.y);
+ return t[0] + (RelativePosition<Dim>(t[1] - t[0]) * bari.x) + (RelativePosition<Dim>(t[2] - t[0]) * bari.y);
}
};
@@ -73,8 +73,10 @@ public:
[[nodiscard]] FaceHandle findPoint(GlobalPosition2D, FaceHandle start) const;
[[nodiscard]] GlobalPosition3D positionAt(const PointFace &) const;
- [[nodiscard]] std::optional<GlobalPosition3D> intersectRay(const Ray<GlobalPosition3D> &) const;
- [[nodiscard]] std::optional<GlobalPosition3D> intersectRay(const Ray<GlobalPosition3D> &, FaceHandle start) const;
+ using IntersectionLocation = std::pair<GlobalPosition3D, FaceHandle>;
+ using IntersectionResult = std::optional<IntersectionLocation>;
+ [[nodiscard]] IntersectionResult intersectRay(const Ray<GlobalPosition3D> &) const;
+ [[nodiscard]] IntersectionResult intersectRay(const Ray<GlobalPosition3D> &, FaceHandle start) const;
void walk(const PointFace & from, const GlobalPosition2D to, const std::function<void(FaceHandle)> & op) const;
void walkUntil(const PointFace & from, const GlobalPosition2D to, const std::function<bool(FaceHandle)> & op) const;
@@ -86,6 +88,8 @@ public:
[[nodiscard]] HalfedgeHandle findEntry(const GlobalPosition2D from, const GlobalPosition2D to) const;
+ void setHeights(const std::span<const GlobalPosition3D> triangleStrip);
+
[[nodiscard]] auto
getExtents() const
{
@@ -102,6 +106,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();
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) {