Упаковка данных прямоугольного изображения в квадратную текстуру
У меня есть N элементов данных 2D-изображения, которые будут прямоугольными, и я хочу максимально эффективно упаковать их в одну текстуру степени 2.
Простую неэффективную и наивную реализацию алгоритма для упаковки этих прямоугольников было бы легко придумать, но я уверен, что люди придумали алгоритмы, чтобы сделать это как можно более эффективно. Я нашел различные ссылки на упаковку карты освещения, которая похожа на то, что я ищу, но алгоритмы отображения света, как правило, принимают во внимание непрямоугольные изображения, что на самом деле усложняет вещи больше, чем мне нужно.
Есть у кого-нибудь подсказки? Названия алгоритмов или авторов статей мне надо гуглить?
Спасибо.
Ответы 4
Ваша проблема в 1D называется Bin Packing. Возможно, это хорошее начало для ваших поисков.
Обратите внимание, что проблема, которую вы хотите решить, действительно сложна (она NP-сложна). Поэтому вам следует искать не оптимальное решение, а какой-то умный эвристический алгоритм.
Я думаю, что восходящее динамическое программирование возможно для одномерной упаковки, но не для двухмерной.
Вы можете подумать об упрощении своей проблемы, решив только одномерную проблему, наложив ограничения, такие как разрезание текстур на несколько (переменного размера) срезов в одном измерении.
Другая возможность - запустить на нем метаэвристическую оптимизацию, такую как эволюционные алгоритмы или оптимизация роя частиц.
Мне нужно было сделать именно то, что вы описываете.
Это код Python, который я использовал, это рецепт из Поваренной книги Python:
Рецепт 442299: упакуйте несколько изображений разного размера в одно изображение
У меня была аналогичная проблема, но я упаковывал квадраты. Попробуйте это: http://www.mrashid.info/blog/stacking-squares-problem.php
Код C++ не очень элегантен, но, по крайней мере, вы получаете базовое представление о том, как подойти к этой проблеме.
Очень хороший и простой алгоритм упаковки можно найти здесь: http://www.blackpawn.com/texts/lightmaps/
Его реализация занимает всего 200 строк C++, не больше (я полагаю, у вас уже есть подпрограммы манипулирования Bitmap).
К теории, лежащей в основе, есть введение Юкки Юлянки. (ищите «Тысячу способов упаковать мусорное ведро»).
Автор статьи предоставляет библиотеку C++, которая, с моей точки зрения, действительно раздута, но, с другой стороны, у нее много возможностей и она очень хорошо документирована.
Этот код не похож на поиск оптимального решения. Также кажется, что хочется упаковать все изображения в одну текстуру.