3 files changed, 156 insertions, 0 deletions
diff --git a/assetFactory/texturePacker.cpp b/assetFactory/texturePacker.cpp
new file mode 100644
index 0000000..31c9a0e
--- /dev/null
+++ b/assetFactory/texturePacker.cpp
@@ -0,0 +1,77 @@
+#include "texturePacker.h"
+#include <algorithm>
+#include <cstdio>
+#include <numeric>
+#include <ostream>
+#include <set>
+
+TexturePacker::TexturePacker(std::vector<Image> in) : inputImages {std::move(in)}
+{
+	std::sort(inputImages.rbegin(), inputImages.rend(), [](const auto & a, const auto & b) {
+		return area(a) < area(b);
+	});
+}
+
+TexturePacker::Result
+TexturePacker::pack() const
+{
+	return pack(minSize());
+}
+
+TexturePacker::Result
+TexturePacker::pack(Size size) const
+{
+	using Spaces = std::set<Space>;
+	Spaces spaces {{{}, size}};
+
+	Positions result;
+	for (const auto & image : inputImages) {
+		if (const auto spaceItr = std::find_if(spaces.begin(), spaces.end(),
+					[image](const Space & s) {
+						return image.x <= s.size.x && image.y <= s.size.y;
+					});
+				spaceItr != spaces.end()) {
+			auto space = *spaceItr;
+			result.push_back(space.position);
+			spaces.erase(spaceItr);
+			if (space.size.x > image.x) {
+				spaces.emplace(Position {space.position.x + image.x, space.position.y},
+						Size {space.size.x - image.x, image.y});
+			}
+			if (space.size.y > image.y) {
+				spaces.emplace(Position {space.position.x, space.position.y + image.y},
+						Size {space.size.x, space.size.y - image.y});
+			}
+		}
+		else {
+			if (size.x < size.y) {
+				return pack({size.x * 2, size.y});
+			}
+			else {
+				return pack({size.x, size.y * 2});
+			}
+		}
+	}
+
+	return {result, size};
+}
+
+TexturePacker::Size
+TexturePacker::minSize() const
+{
+	return std::accumulate(inputImages.begin(), inputImages.end(), Size {1}, [](Size size, const Image & i) {
+		while (size.x < i.x) {
+			size.x *= 2;
+		}
+		while (size.y < i.y) {
+			size.y *= 2;
+		}
+		return size;
+	});
+}
+
+decltype(TexturePacker::Size::x)
+TexturePacker::area(const Size & size)
+{
+	return size.x * size.y;
+}
diff --git a/assetFactory/texturePacker.h b/assetFactory/texturePacker.h
new file mode 100644
index 0000000..8e2061b
--- /dev/null
+++ b/assetFactory/texturePacker.h
@@ -0,0 +1,36 @@
+#pragma once
+
+#include <glm/vec2.hpp>
+#include <span>
+#include <vector>
+
+class TexturePacker {
+public:
+	using Position = glm::uvec2;
+	using Size = glm::uvec2;
+
+	struct Area {
+		Position position;
+		Size size;
+		bool
+		operator<(const Area & other) const
+		{
+			return area(size) < area(other.size);
+		}
+	};
+	using Image = Size;
+	using Space = Area;
+	using Positions = std::vector<Position>;
+	using Result = std::pair<Positions, Size>;
+
+	TexturePacker(std::vector<Image>);
+
+	Result pack(Size) const;
+	Result pack() const;
+
+	Size minSize() const;
+	static decltype(Size::x) area(const Size & size);
+
+private:
+	std::vector<Image> inputImages;
+};
diff --git a/test/test-assetFactory.cpp b/test/test-assetFactory.cpp
index 204ffb3..ad62a93 100644
--- a/test/test-assetFactory.cpp
+++ b/test/test-assetFactory.cpp
@@ -7,6 +7,7 @@
 
 #include "assetFactory/assetFactory.h"
 #include "assetFactory/object.h"
+#include "assetFactory/texturePacker.h"
 #include "game/vehicles/railVehicle.h"
 #include "game/vehicles/railVehicleClass.h"
 #include "gfx/gl/sceneRenderer.h"
@@ -125,3 +126,45 @@ BOOST_AUTO_TEST_CASE(parseX11RGB)
 	BOOST_CHECK_CLOSE_VEC(parsedColours.at("slategrey"), AssetFactory::Colour(0.44F, 0.5, 0.56F));
 	BOOST_CHECK_CLOSE_VEC(parsedColours.at("lightsteelblue1"), AssetFactory::Colour(0.79, 0.88, 1));
 }
+
+BOOST_AUTO_TEST_CASE(texturePacker)
+{
+	TexturePacker tp {{
+			{10, 10},
+			{10, 10},
+			{10, 10},
+			{100, 10},
+			{10, 200},
+			{5, 5},
+	}};
+	BOOST_CHECK_EQUAL(TexturePacker::Size(128, 256), tp.minSize());
+	const auto result = tp.pack();
+}
+
+BOOST_AUTO_TEST_CASE(texturePacker_many, *boost::unit_test::timeout(5))
+{
+	std::vector<TexturePacker::Image> images(256);
+	std::fill(images.begin(), images.end(), TexturePacker::Image {32, 32});
+	const auto totalSize = std::accumulate(images.begin(), images.end(), 0U, [](auto t, const auto & i) {
+		return t + TexturePacker::area(i);
+	});
+	TexturePacker tp {images};
+	BOOST_CHECK_EQUAL(TexturePacker::Size(32, 32), tp.minSize());
+	const auto result = tp.pack();
+	BOOST_CHECK_EQUAL(result.first.size(), images.size());
+	BOOST_CHECK_GE(TexturePacker::area(result.second), TexturePacker::area(images.front()) * images.size());
+	BOOST_CHECK_EQUAL(totalSize, TexturePacker::area(result.second));
+}
+
+BOOST_AUTO_TEST_CASE(texturePacker_many_random, *boost::unit_test::timeout(5))
+{
+	std::vector<TexturePacker::Image> images(2048);
+	std::mt19937 gen(std::random_device {}());
+	std::uniform_int_distribution<> dim {1, 10};
+	std::generate(images.begin(), images.end(), [&dim, &gen]() {
+		return TexturePacker::Image {2 ^ dim(gen), 2 ^ dim(gen)};
+	});
+	TexturePacker tp {images};
+	const auto result = tp.pack();
+	BOOST_CHECK_EQUAL(result.first.size(), images.size());
+}