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

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

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

Есть ли у кого намеки? Названия алгоритмов или авторов статей, я должен google?

Спасибо.

Ответы

Ответ 2

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

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

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

Вы могли бы подумать об упрощении своей проблемы, разрешив только проблему 1D, создав такие ограничения, как резка текстур на несколько (размерных) срезов в 1 измерении.

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

Ответ 3

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

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

Для теории позади есть введение Юкки Йыланки (ищите "Тысяча способов, чтобы упаковать корзину" ).

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

Ответ 4

У меня была аналогичная проблема, но я собирал квадраты. Попробуйте следующее: http://www.mrashid.info/blog/stacking-squares-problem.php

Код С++ не очень изящный, но по крайней мере вы получаете основную идею о том, как подойти к этой проблеме.