From 6a1bd528719d19c24f9c4a1fb9e10c6481105556 Mon Sep 17 00:00:00 2001
From: Dan Goodliffe <dan@randomdan.homeip.net>
Date: Sun, 23 Feb 2025 14:55:31 +0000
Subject: Less allocy/work set based surface/recursive height setting

---
 game/geoData.cpp | 101 ++++++++++++++++++++++++++++++++-----------------------
 1 file changed, 59 insertions(+), 42 deletions(-)

(limited to 'game/geoData.cpp')

diff --git a/game/geoData.cpp b/game/geoData.cpp
index cf61f20..bdd1a9b 100644
--- a/game/geoData.cpp
+++ b/game/geoData.cpp
@@ -447,56 +447,72 @@ GeoData::setHeights(const std::span<const GlobalPosition3D> triangleStrip, const
 			doBoundaryPart(*++newVerts.rbegin(), newVerts.back(), strip.back(), nearNodeTolerance);
 		}
 
-		void
-		setHeights(const std::vector<VertexHandle> & newVerts, RelativeDistance maxSlope)
+		using HeightSetTodo = std::multimap<VertexHandle, VertexHandle>;
+
+		HeightSetTodo
+		setSurfaceHeights(const std::span<const VertexHandle> newVerts)
 		{
-			std::set<HalfedgeHandle> done;
-			std::set<HalfedgeHandle> todo;
-			auto todoOutHalfEdges = [&todo, &done, this](const VertexHandle v) {
-				std::ranges::copy_if(geoData->voh_range(v), std::inserter(todo, todo.end()), [&done](const auto & h) {
-					return !done.contains(h);
-				});
-			};
-			std::ranges::for_each(newVerts, todoOutHalfEdges);
-			auto setHalfedgeToHeight = [this, &todoOutHalfEdges, maxSlope, &done](
-											   const auto & setHalfedgeToHeight, const HalfedgeHandle heh) -> void {
-				const auto [fromVertex, toVertex] = geoData->toVertexHandles(heh);
-				auto & toPoint = geoData->point(toVertex);
-				auto toTriangle = getTriangle(toPoint);
-				if (!toTriangle) {
-					if (const auto boundaryVertex = boundaryTriangles.find(toVertex);
+			HeightSetTodo out;
+			auto setSurfaceVertexHeight = [this, &out](const auto & setSurfaceVertexHeight, const VertexHandle vertex,
+												  const VertexHandle previousVertex) -> void {
+				if (surfaceVerts.contains(vertex)) {
+					return;
+				}
+				auto & point = geoData->point(vertex);
+				auto triangle = getTriangle(point);
+				if (!triangle) {
+					if (const auto boundaryVertex = boundaryTriangles.find(vertex);
 							boundaryVertex != boundaryTriangles.end()) {
-						toTriangle = boundaryVertex->second;
+						triangle = boundaryVertex->second;
 					}
 				}
-				if (toTriangle) { // point within the new strip, adjust vertically by triangle
-					toPoint.z = toTriangle->positionOnPlane(toPoint).z;
-					todoOutHalfEdges(toVertex);
+				if (triangle) { // point within the new strip, adjust vertically by triangle
+					point.z = triangle->positionOnPlane(point).z;
+					newOrChangedVerts.emplace(vertex);
+					surfaceVerts.emplace(vertex);
+					for (const auto nextVertex : geoData->vv_range(vertex)) {
+						setSurfaceVertexHeight(setSurfaceVertexHeight, nextVertex, vertex);
+					}
 				}
-				else { // point without the new strip, adjust vertically by limit
-					const auto maxOffset = static_cast<GlobalDistance>(maxSlope * geoData->length<2>(heh));
-					const auto fromHeight = geoData->point(fromVertex).z;
-					const auto newHeight = std::clamp(toPoint.z, fromHeight - maxOffset, fromHeight + maxOffset);
-					if (newHeight != toPoint.z) {
-						toPoint.z = newHeight;
-						std::ranges::for_each(geoData->voh_range(toVertex), [&setHalfedgeToHeight](const auto heh) {
-							setHalfedgeToHeight(setHalfedgeToHeight, heh);
-						});
+				else if (previousVertex.is_valid()) {
+					out.emplace(vertex, previousVertex);
+				}
+			};
+			for (const auto vertex : newVerts) {
+				setSurfaceVertexHeight(setSurfaceVertexHeight, vertex, VertexHandle {});
+			}
+			return out;
+		}
+
+		void
+		setHeightsAsRequired(HeightSetTodo starts, RelativeDistance maxSlope)
+		{
+			auto setHalfedgeToHeight = [this, maxSlope](HeightSetTodo & nexts, const VertexHandle vertex,
+											   const VertexHandle previousVertex) -> void {
+				const auto & fromPoint = geoData->point(previousVertex);
+				auto & point = geoData->point(vertex);
+				const auto maxOffset
+						= static_cast<GlobalDistance>(std::round(maxSlope * ::distance<2>(fromPoint.xy(), point.xy())));
+				const auto newHeight = std::clamp(point.z, fromPoint.z - maxOffset, fromPoint.z + maxOffset);
+				if (newHeight != point.z) {
+					point.z = newHeight;
+					newOrChangedVerts.emplace(vertex);
+					for (const auto nextVertex : geoData->vv_range(vertex)) {
+						if (nextVertex != previousVertex && !boundaryTriangles.contains(nextVertex)) {
+							nexts.emplace(nextVertex, vertex);
+						}
 					}
 				}
-				done.insert(heh);
 			};
-			while (!todo.empty()) {
-				setHalfedgeToHeight(setHalfedgeToHeight, todo.extract(todo.begin()).value());
+			while (!starts.empty()) {
+				HeightSetTodo nexts;
+
+				for (const auto & start : starts) {
+					const auto & [toVertex, previousVertex] = start;
+					setHalfedgeToHeight(nexts, toVertex, previousVertex);
+				}
+				starts = std::move(nexts);
 			}
-			std::ranges::for_each(done, [this](const auto heh) {
-				const auto ends = geoData->toVertexHandles(heh);
-				newOrChangedVerts.emplace(ends.first);
-				newOrChangedVerts.emplace(ends.second);
-			});
-#ifndef NDEBUG
-			geoData->sanityCheck();
-#endif
 		}
 
 		std::vector<FaceHandle>
@@ -526,7 +542,7 @@ GeoData::setHeights(const std::span<const GlobalPosition3D> triangleStrip, const
 		{
 			const std::vector<VertexHandle> newVerts = createVerticesForStrip(opts.nearNodeTolerance);
 			cutBoundary(newVerts, opts.nearNodeTolerance);
-			setHeights(newVerts, opts.maxSlope);
+			setHeightsAsRequired(setSurfaceHeights(newVerts), opts.maxSlope);
 			const auto out = setSurface(opts.surface);
 
 			geoData->expandVerts(newOrChangedVerts);
@@ -541,6 +557,7 @@ GeoData::setHeights(const std::span<const GlobalPosition3D> triangleStrip, const
 		const std::span<const GlobalPosition3D> triangleStrip;
 		const std::vector<Triangle<3>> strip;
 		std::set<VertexHandle> newOrChangedVerts;
+		std::set<VertexHandle> surfaceVerts;
 		std::map<VertexHandle, const Triangle<3> *> boundaryTriangles;
 	};
 
-- 
cgit v1.2.3