summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDan Goodliffe <dan@randomdan.homeip.net>2024-03-08 20:41:37 +0000
committerDan Goodliffe <dan@randomdan.homeip.net>2024-03-08 20:41:37 +0000
commit567477ab8b4b09111d942039c4b2587b25fc2fe2 (patch)
tree7a5ae3d951d68d0ba8c41519e8c5584f0f400ebb
parentBail out early if the input does not define an area (diff)
downloadilt-567477ab8b4b09111d942039c4b2587b25fc2fe2.tar.bz2
ilt-567477ab8b4b09111d942039c4b2587b25fc2fe2.tar.xz
ilt-567477ab8b4b09111d942039c4b2587b25fc2fe2.zip
Rewrite most of setHeights
Accounts for sensible corners and fixes quite a few bugs and edge cases... introduces a few more, is still a bit glitchy in places
-rw-r--r--game/geoData.cpp236
-rw-r--r--test/fixtures/geoData/deform/1.json53
2 files changed, 186 insertions, 103 deletions
diff --git a/game/geoData.cpp b/game/geoData.cpp
index 9a08a89..ac2f035 100644
--- a/game/geoData.cpp
+++ b/game/geoData.cpp
@@ -2,7 +2,6 @@
#include "collections.h"
#include <fstream>
#include <glm/gtx/intersect.hpp>
-#include <math.h>
#include <maths.h>
#include <set>
@@ -381,6 +380,8 @@ GeoData::triangleContainsTriangle(const Triangle<2> & a, const Triangle<2> & b)
void
GeoData::setHeights(const std::span<const GlobalPosition3D> triangleStrip)
{
+ static const RelativeDistance MAX_SLOPE = 1.5F;
+
if (triangleStrip.size() < 3) {
return;
}
@@ -391,7 +392,7 @@ GeoData::setHeights(const std::span<const GlobalPosition3D> triangleStrip)
std::transform(triangleStrip.begin(), triangleStrip.end(), std::back_inserter(newVerts), [this](const auto tsVert) {
return add_vertex(tsVert);
});
- // Create new faces
+ // Create new faces
std::vector<FaceHandle> newFaces;
newFaces.reserve(newVerts.size() - 2);
std::transform(
@@ -408,121 +409,152 @@ GeoData::setHeights(const std::span<const GlobalPosition3D> triangleStrip)
*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, &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, &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);
- }
-
- 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));
- });
+ struct Extrusion {
+ VertexHandle boundaryVertex, extrusionVertex;
+ GlobalPosition3D lowerLimit, upperLimit;
+ };
+
+ std::vector<Extrusion> extrusionExtents;
+ std::for_each(boundary.begin(), boundary.end(), [this, &extrusionExtents](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 boundaryVertex = from_vertex_handle(boundaryHeh);
+ const auto p0 = point(from_vertex_handle(prev_halfedge_handle(boundaryHeh)));
+ const auto p1 = point(boundaryVertex);
+ 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 doExtrusion = [this](VertexHandle & extrusionVertex, Direction2D direction,
+ GlobalPosition3D boundaryVertex, RelativeDistance vert, GlobalDistance limit) {
+ 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;
+ }
+ }
+
+ const auto extrusion
+ = extrusionDir * std::max(0.F, RelativeDistance(limit - boundaryVertex.z) / extrusionDir.z);
+ return boundaryVertex + extrusion;
+ };
+ // Previous half edge end to current half end start arc tangents
+ const Arc arc {p1, p1 + (e0 || 0.F), p1 + (e1 || 0.F)};
+ const auto limit = std::floor((arc.second - arc.first) * 5.F / pi);
+ const auto inc = (arc.second - arc.first) / limit;
+ for (float step = 1; step < limit; step += 1.F) {
+ const auto direction = sincosf(arc.first + (step * inc));
+ VertexHandle extrusionVertex;
+ extrusionExtents.emplace_back(boundaryVertex, extrusionVertex,
+ doExtrusion(extrusionVertex, direction, p1, -MAX_SLOPE, lowerExtent.z - 10),
+ doExtrusion(extrusionVertex, direction, p1, MAX_SLOPE, upperExtent.z + 10));
+ assert(extrusionVertex.is_valid());
+ }
+ // Half edge start/end tangents
+ for (const auto p : {p1, p2}) {
+ VertexHandle extrusionVertex;
+ extrusionExtents.emplace_back(boundaryVertex, extrusionVertex,
+ doExtrusion(extrusionVertex, e1, p, -MAX_SLOPE, lowerExtent.z - 10),
+ doExtrusion(extrusionVertex, e1, p, MAX_SLOPE, upperExtent.z + 10));
+ assert(extrusionVertex.is_valid());
+ }
+ });
- // Cut existing terrain
+ // 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](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);
- 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;
- });
- });) {
+ std::adjacent_find(extrusionExtents.begin(), extrusionExtents.end(),
+ [this, &boundaryFaces](const auto & first, const auto & second) {
+ const auto p0 = point(first.boundaryVertex);
+ std::vector<Triangle<3>> triangles {
+ {p0, first.lowerLimit, second.lowerLimit}, {p0, first.upperLimit, second.upperLimit}};
+ const auto p1 = point(second.boundaryVertex);
+ if (first.boundaryVertex != second.boundaryVertex) {
+ triangles.emplace_back(p0, p1, second.lowerLimit);
+ triangles.emplace_back(p0, p1, second.upperLimit);
+ }
+
+ auto & out = boundaryFaces.emplace_back();
+ out.emplace_back(first.boundaryVertex);
+ out.emplace_back(first.extrusionVertex);
+ for (auto currentVertex = first.extrusionVertex;
+ std::none_of(voh_begin(currentVertex), voh_end(currentVertex),
+ [&](const auto currentVertexOut) {
+ // The next half edge goes to the termination point
+ const auto next = next_halfedge_handle(currentVertexOut);
+ const auto nextVertex = to_vertex_handle(next);
+ return (nextVertex == second.extrusionVertex);
+ })
+ && 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);
+ 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 = out.emplace_back(split(edge, splitPos));
+ return true;
+ }
+ return false;
+ });
+ });) {
;
}
- sideVerts.emplace_back(*nexv);
- sideVerts.emplace_back(toVertex);
- ex = nex;
- exv++;
- return sideVerts;
+ out.emplace_back(second.extrusionVertex);
+ if (first.boundaryVertex != second.boundaryVertex) {
+ out.emplace_back(second.boundaryVertex);
+ }
+ return false;
});
- // Remove old faces
+ // 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));
+ 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);
- std::for_each(neighbourFaces.begin(), neighbourFaces.end(), [&self](const auto nextFace) {
- if (nextFace.is_valid()) {
- self(self, nextFace);
- }
- });
}
};
removeOld(removeOld, findPoint(triangleStrip.front()));
diff --git a/test/fixtures/geoData/deform/1.json b/test/fixtures/geoData/deform/1.json
index 33ac86d..2854e64 100644
--- a/test/fixtures/geoData/deform/1.json
+++ b/test/fixtures/geoData/deform/1.json
@@ -19,7 +19,7 @@
[
241000,
123330,
- -2000
+ 2000
]
],
[
@@ -69,5 +69,56 @@
"/tmp/geoData2.tga"
]
]
+ ],
+ [
+ [
+ [
+ 3000,
+ 1000,
+ 500
+ ],
+ [
+ 3000,
+ 2000,
+ 500
+ ],
+ [
+ 2000,
+ 1000,
+ 500
+ ]
+ ],
+ [
+ [
+ [
+ [
+ -1000,
+ -3000,
+ 7000
+ ],
+ [
+ 1,
+ 1,
+ -1.5
+ ]
+ ],
+ "/tmp/geoData3.tga"
+ ],
+ [
+ [
+ [
+ 1800,
+ 2500,
+ 800
+ ],
+ [
+ 1,
+ -0.2,
+ -0.5
+ ]
+ ],
+ "/tmp/geoData4.tga"
+ ]
+ ]
]
]