Psycho-rebased branch deform-terrain on top of main

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) {