Объединение мелких изображений в атлас

При разработке графических приложений (например, игр или web-приложений) часто возникает ситуация, когда есть множество файлов рисунков небольших размеров, либо файлы спрайтов анимации, которые было бы целесообразно поместить в один большой графический файл, так называемый "атлас". Атлас - это большое изображение, содержащее некоторое множество изображений меньшего размера, которые можно выбирать методом клиппинга прямоугольного региона. Какие преимущества дает использования атласов? Во-первых, сокращение количества файлов рисунков ускоряет загрузку приложения (что особенно акткально для веб-приложений). Во-вторых, если изображения содержат прозрачные области, то их можно удалить, съэкономив тем самым некоторое количество видеопамяти за счет более плотной упаковки элементов графики (актуально для игр и анимации с участим спрайтов разных размеров).

Создание атласов вручную - занятие слишком кропотливое и трудоемкое, кроме того, вручную не всегда удается получить оптимальный результат (т.е., минимальную площадь рисунка-атласа на выходе). При автоматизации процесса мы сталкиваемся с задачей оптимальной компановки множества прямоугольных объектов внутри прямоугольного объекта большего размера (причем, оптимальный размер рисунка-атласа так же неизвестен).

Итак, постановка задачи: нужна программа для максимально компактной автоматизированной упаковки спрайтов в атлас. Предполагается компоновать спрайты графики и анимации игр, программа нужна вместе с исходным кодом, т.к. ее предполагается встраивать в игровой фреймворк. Язык для написания - java. Особого быстродействия от алгоритма не требуется, приоритет качество компоновки и минимизацию времени разработки программы.

Посколько готовых алгоритмов с для решения этой задачи с приемлимым качеством результата и доступным исходным кодом мне найти не удалось, пришлось пытаться "допилить" имеющиеся решения. В качестве основы был взят этот алгоритм и его java-имплементация от Michael Ludwig (которую можно найти в Сети). Данный алгоритм умеет компоновать набор прямоугольников в прямоугольном контейнере. Причем, ширину этого контейнер как и порядок следования объектов для получения максимально плотной компоновки он определять не умеет. Первое приходящее в голову решение - варьировать ширину контейнера и порядок размещения спрайтов перебором.

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

• в порядке убывания их площади
• в порядке убывания ширины
• в порядке убывания высоты

Размеры рисунка при этом варьируются от размеров максимального спрайта до значения (ширина + высота исходного изображения) х 10. Затем, из этих трех вариантов отбирается один с минимальной площадью. Далее, делается попытка оптимизировать эту компановку перестановками местами пар случайно выбранных спрайтов. В результате программа сохряняет файл скомпонованнрго изображения и xml-файл с координатами спрайтов в нем, их размерами и смещениями (обусловленными удалением пустого пространства).

Синтаксис вызова утилиты:

java -jar framepacker.jar <source_image> <frame_width>x<frame_height> <output_image> [options]

Первый аргумент определяет имя исходного файла, второй - размеры рисунка в спрайтах, третий - имя результирующего изображения и генерируемого xml-файла. В качестве единственной опции можно передать параметр -t, определяющий порог прозрачности пикселов для обрезания. Например, опция -t=25 означает, что пикселы с прозрачностью от 0 до 25 будут считаться полностью прозрачными и удаляться. По умолчанию этот параметр равен нулю, т.е. программа удаляет только полностью прозрачные пикселы.

Пример вызова:

java -jar framepacker.jar particles.png 10x8 particles_out.png -t=15

В завершении несколько примеров работы утилиты (на игровой графике):

Исходное изображение, размеры 72x72:

Упакованое изображение для -t=0, размеры 28х52, сокращение на 3757 пикселей (27%):

Исходное изображение, размеры 88x55:

Упакованое изображение для -t=0, размеры 64х51, сокращение на 1657 пикселей (65%):

Исходное изображение, размеры 200x150:

Упакованое изображение для -t=5, размеры 147х197, сокращение на 1279 пикселей (95%):

Упакованое изображение для -t=15, размеры 128х185, сокращение на 8313 пикселей (75%):

Сгенерированная xml-карта в этом случае:

<frame x="49" y="98" width="31" height="30" anchorX="-10" anchorY="-10" />
<frame x="0" y="146" width="41" height="39" anchorX="-4" anchorY="-7" />
<frame x="80" y="48" width="48" height="47" anchorX="-1" anchorY="-3" />
<frame x="0" y="0" width="49" height="49" anchorX="-1" anchorY="-1" />
<frame x="48" y="49" width="31" height="31" anchorX="-10" anchorY="-10" />
<frame x="41" y="146" width="39" height="39" anchorX="-7" anchorY="-8" />
<frame x="80" y="0" width="48" height="48" anchorX="-2" anchorY="-1" />
<frame x="0" y="49" width="48" height="49" anchorX="0" anchorY="0" />
<frame x="49" y="0" width="31" height="32" anchorX="-11" anchorY="-10" />
<frame x="80" y="143" width="43" height="41" anchorX="-4" anchorY="-5" />
<frame x="80" y="95" width="47" height="48" anchorX="-2" anchorY="-2" />
<frame x="0" y="98" width="49" height="48" anchorX="-1" anchorY="-1" />

Описывает позицию исходных спрайтов в сгенерированном файле изображения. Атрибуты anchorX и anchorY задают "якорь" - смещение для вывода на экран сжатых спрайтов чтобы они попали в ту же позицию, что и исходные.

Утилиту можно скачать по ссылке ниже. Исходный код доступен на гитхабе.

Файлы:
framepacker.jar