Упаковка прямоугольных данных изображения в квадратную текстуру

Question

У меня есть N элементов данных 2D-изображения, которые будут прямоугольными, и я хочу максимально эффективно упаковать их в одну текстуру степени 2.

Простую неэффективную и наивную реализацию алгоритма для упаковки этих ректов было бы легко заметить, но я уверен, что люди придумали алгоритмы, чтобы сделать это как можно более эффективно. Я нашел различные ссылки на упаковку карты освещения, которая похожа на то, что я ищу, но алгоритмы создания карты света обычно принимают во внимание непрямоугольные изображения, что на самом деле усложняет вещи больше, чем мне нужно.

У кого-нибудь есть подсказки? Названия алгоритмов или авторов статьи мне гуглить?

Спасибо.

Answer 1

Мне нужно было сделать именно то, что вы описываете.

Это код Python, который я использовал, рецепт в Кулинарной книге Python:

Рецепт 442299: упаковка нескольких изображений разных размеров в одно изображение

Answer 2

Ваша проблема в 1D называется Bin Packing. Возможно, это хорошее начало для вашего поиска.

Обратите внимание, что проблема, которую вы хотите решить, действительно сложна (это NP-сложная задача). Так что вам не нужно искать оптимальное решение, а какой-то умный эвристический алгоритм.

Я думаю, что динамическое программирование снизу вверх возможно для упаковки 1D, но не для 2D случая.

Можно подумать об упрощении вашей проблемы, решив только одномерную задачу, ограничив ее, например, разрезанием текстур на несколько кусков (переменного размера) в одном измерении.

Другая возможность - использовать метаэвристическую оптимизацию, например, эволюционные алгоритмы или оптимизацию роя частиц.

Answer 3

Очень хороший и простой алгоритм упаковки можно найти здесь: http://www.blackpawn.com/texts/lightmaps/

Его реализация занимает всего 200 строк C ++, не более (я полагаю, у вас уже есть процедуры манипуляции с битовой картой).

Для теории есть вступление Юкки Юлянки. (ищите «Тысячу способов упаковать мусорное ведро»).

Автор статьи предоставляет библиотеку C ++, которая с моей точки зрения действительно раздутая, но, с другой стороны, у нее много опций и она хорошо документирована.

Answer 4

У меня была похожая проблема, но я упаковывал квадраты. Попробуйте это: http://www.mrashid.info/blog/stacking-squares-problem.php

Код на C ++ не очень элегантен, но, по крайней мере, вы получите основную идею о том, как решить эту проблему.