Create AxisAlignedBoundingBox

Used to define the extents of GeoData mesh

6 files changed, 68 insertions, 15 deletions

diff --git a/game/geoData.cpp b/game/geoData.cpp
index 4291a64..5cea4dd 100644
--- a/game/geoData.cpp
+++ b/game/geoData.cpp
@@ -35,16 +35,16 @@ GeoData::loadFromAsciiGrid(const std::filesystem::path & input)
 	std::vector<VertexHandle> vertices;
 	vertices.reserve(ncols * nrows);
 	GeoData mesh;
-	mesh.lowerExtent = {xllcorner, yllcorner, std::numeric_limits<GlobalDistance>::max()};
-	mesh.upperExtent = {xllcorner + (cellsize * (ncols - 1)), yllcorner + (cellsize * (nrows - 1)),
-			std::numeric_limits<GlobalDistance>::min()};
+	mesh.extents = {{xllcorner, yllcorner, std::numeric_limits<GlobalDistance>::max()},
+			{xllcorner + (cellsize * (ncols - 1)), yllcorner + (cellsize * (nrows - 1)),
+					std::numeric_limits<GlobalDistance>::min()}};
 	for (size_t row = 0; row < nrows; ++row) {
 		for (size_t col = 0; col < ncols; ++col) {
 			float heightf = 0;
 			f >> heightf;
 			const auto height = static_cast<GlobalDistance>(std::round(heightf * 1000.F));
-			mesh.upperExtent.z = std::max(mesh.upperExtent.z, height);
-			mesh.lowerExtent.z = std::min(mesh.lowerExtent.z, height);
+			mesh.extents.max.z = std::max(mesh.extents.max.z, height);
+			mesh.extents.min.z = std::min(mesh.extents.min.z, height);
 			vertices.push_back(mesh.add_vertex({xllcorner + (col * cellsize), yllcorner + (row * cellsize), height}));
 		}
 	}
@@ -78,8 +78,7 @@ GeoData::createFlat(GlobalPosition2D lower, GlobalPosition2D upper, GlobalDistan
 	assert((upper - lower) % GRID_SIZE == GlobalPosition2D {});
 	GeoData mesh;
 
-	mesh.lowerExtent = {lower, h};
-	mesh.upperExtent = {upper, h};
+	mesh.extents = {{lower, h}, {upper, h}};
 
 	std::vector<VertexHandle> vertices;
 	for (GlobalDistance row = lower.x; row <= upper.x; row += GRID_SIZE) {
@@ -120,7 +119,7 @@ GeoData::intersectRay(const Ray<GlobalPosition3D> & ray, FaceHandle face) const
 {
 	GeoData::IntersectionResult out;
 	walkUntil(PointFace {ray.start, face},
-			ray.start.xy() + (ray.direction.xy() * RelativePosition2D(upperExtent.xy() - lowerExtent.xy())),
+			ray.start.xy() + (ray.direction.xy() * ::difference(extents.max.xy(), extents.min.xy())),
 			[&out, &ray, this](const auto & step) {
 				BaryPosition bari {};
 				RelativeDistance dist {};
@@ -325,9 +324,9 @@ GeoData::setHeights(const std::span<const GlobalPosition3D> triangleStrip, const
 	if (triangleStrip.size() < 3) {
 		return {};
 	}
-	const auto stripMinMax = std::ranges::minmax(triangleStrip, {}, &GlobalPosition3D::z);
-	lowerExtent.z = std::min(upperExtent.z, stripMinMax.min.z);
-	upperExtent.z = std::max(upperExtent.z, stripMinMax.max.z);
+	for (const auto & vertex : triangleStrip) {
+		extents += vertex;
+	}
 
 	class SetHeights {
 	public:
diff --git a/game/geoData.h b/game/geoData.h
index b2a75bd..a504f9b 100644
--- a/game/geoData.h
+++ b/game/geoData.h
@@ -2,6 +2,7 @@
 
 #include "collections.h" // IWYU pragma: keep IterableCollection
 #include "geoDataMesh.h"
+#include "gfx/aabb.h"
 #include "surface.h"
 #include <filesystem>
 #include <glm/vec2.hpp>
@@ -57,10 +58,10 @@ public:
 
 	std::set<FaceHandle> setHeights(std::span<const GlobalPosition3D> triangleStrip, const SetHeightsOpts &);
 
-	[[nodiscard]] auto
+	[[nodiscard]] auto &
 	getExtents() const
 	{
-		return std::tie(lowerExtent, upperExtent);
+		return extents;
 	}
 
 	template<typename HandleT>
@@ -80,5 +81,5 @@ protected:
 	virtual void afterChange();
 
 private:
-	GlobalPosition3D lowerExtent {}, upperExtent {};
+	AxisAlignedBoundingBox extents;
 };
diff --git a/game/water.cpp b/game/water.cpp
index 94a8596..527e85a 100644
--- a/game/water.cpp
+++ b/game/water.cpp
@@ -82,7 +82,7 @@ Water::generateMeshes()
 						const auto pos = (p * TILE_SIZE) + GlobalPosition2D {x, y};
 						const auto v = vertexIndex.emplace(pos, vertices.size());
 						if (v.second) {
-							const auto cpos = glm::clamp(pos, std::get<0>(extents).xy(), std::get<1>(extents).xy());
+							const auto cpos = glm::clamp(pos, extents.min.xy(), extents.max.xy());
 							vertices.emplace_back(geoData->positionAt(cpos));
 						}
 						*out++ = static_cast<unsigned int>(v.first->second);
diff --git a/gfx/aabb.cpp b/gfx/aabb.cpp
new file mode 100644
index 0000000..862dacb
--- /dev/null
+++ b/gfx/aabb.cpp
@@ -0,0 +1,24 @@
+#include "aabb.h"
+#include <algorithm>
+#include <tuple>
+
+AxisAlignedBoundingBox
+AxisAlignedBoundingBox::fromPoints(const std::span<const GlobalPosition3D> points)
+{
+	using Limits = std::numeric_limits<GlobalDistance>;
+	static constexpr const auto INITIAL
+			= std::make_pair(GlobalPosition3D {Limits::max()}, GlobalPosition3D {Limits::min()});
+	return std::make_from_tuple<AxisAlignedBoundingBox>(
+			std::ranges::fold_left(points, INITIAL, [](const auto & prev, const auto & point) {
+				auto & [min, max] = prev;
+				return std::make_pair(glm::min(min, point), glm::max(max, point));
+			}));
+}
+
+AxisAlignedBoundingBox &
+AxisAlignedBoundingBox::operator+=(const GlobalPosition3D & point)
+{
+	min = glm::min(min, point);
+	max = glm::max(max, point);
+	return *this;
+}
diff --git a/gfx/aabb.h b/gfx/aabb.h
new file mode 100644
index 0000000..568e91a
--- /dev/null
+++ b/gfx/aabb.h
@@ -0,0 +1,17 @@
+#pragma once
+
+#include "config/types.h"
+#include <span>
+
+class AxisAlignedBoundingBox {
+public:
+	AxisAlignedBoundingBox() = default;
+
+	AxisAlignedBoundingBox(const GlobalPosition3D & min, const GlobalPosition3D & max) : min {min}, max {max} { }
+
+	AxisAlignedBoundingBox & operator+=(const GlobalPosition3D & point);
+
+	[[nodiscard]] static AxisAlignedBoundingBox fromPoints(std::span<const GlobalPosition3D> points);
+
+	GlobalPosition3D min, max;
+};
diff --git a/test/test-lib.cpp b/test/test-lib.cpp
index 17c0f63..8dadc70 100644
--- a/test/test-lib.cpp
+++ b/test/test-lib.cpp
@@ -6,6 +6,7 @@
 #include <stream_support.h>
 
 #include <collections.h>
+#include <gfx/aabb.h>
 #include <glArrays.h>
 #include <glad/gl.h>
 #include <set>
@@ -110,3 +111,14 @@ BOOST_DATA_TEST_CASE(mergeCloseInts,
 			tolerance)));
 	BOOST_CHECK_EQUAL_COLCOL(mutableCollection, expected);
 }
+
+BOOST_AUTO_TEST_CASE(aabb_from_points)
+{
+	const auto aabb = AxisAlignedBoundingBox::fromPoints(std::vector<GlobalPosition3D> {
+			{1, 2, 3},
+			{4, 2, 1},
+			{9, 1, 7},
+	});
+	BOOST_CHECK_EQUAL(aabb.min, GlobalPosition3D(1, 1, 1));
+	BOOST_CHECK_EQUAL(aabb.max, GlobalPosition3D(9, 2, 7));
+}