Динамическая генерация текстурных атласов

Давно задумываюсь: "А не попытаться ли перевести Flixel на Stage3D?" Сам автор движка обещал, что когда новая версия flash-плеера с аппаратной поддержкой 3D получит достаточно широкое распространение, то он добавит эту фичу. Но новостей от него пока не слышно; тема на форуме фликселя, посвященная планам по разработке новой версии, тоже довольно давно не обновлялась. Поэтому и мысли такие. Кроме того, в сети появилось несколько очень хороших уроков по stage3D, в которых рассматривается использование нового API для разработки двумерных игр. Из них можно вынести очень полезные сведения, связанные с оптимизацией графики:

• необходимо минимизировать количество вызовов метода drawTriangles(), т.к. он довольно ресурсоемок;
• также следует использовать как можно меньше текстур, т.к. размеры текстур могут иметь строго определенные значения (64х64, 128х128, 256х256, 512х512, 1024х1024 или 2048х2048). И если в Вашей игре используется множество маленьких изображений, для каждого из которых Вы будете создавать новую текстуру, то видеопамять будет расходоваться нерационально (в каждой такой текстуре будет много "пустого места") и довольно быстро закончится.

 Для решения этих проблем рекомендуется использовать "пакетный рендеринг" (не знаю, правильный ли я использую термин, на английском он пишется batch-rendering), при котором мы за один вызов метода drawTriangles() пытаемся отрисовать все полигоны, использующие одну и ту же текстуру. Для этого нам и понадобится генерация текстурных атласов, вынесенная в заголовок статьи и позволяющая значительно уменьшить количество текстур (о пакетном рендеринге я скорее всего напишу в следующей статье). Суть его в следующем: на входе мы имеем множество мелких изображений, а на выходе -- одно (это в идеале) большое. На русском языке уже есть, по крайней мере, одна статья от flash-сообщества, посвященная этому вопросу -- класс для генерации текстурных атласов, в ней дается исходник класса, использующий рекурсивный метод построения атласа. Данный класс мне показался не слишком понятным, а так хотелось самому разобраться в алгоритме, благо что в статье приведена ссылка на англоязычную статью по данному вопросу, из которой и становится ясен общий принцип.
Для хранения данных о субтекстурах (вставляемых в атлас изображениях) строится специальное дерево, в узлах (объекты класса Node) которого хранятся размеры, положение и прочая нужная информация. При этом каждый узел может иметь не более двух поддеревьев (левое и правое). Первоначально, когда наше дерево пустое, в нем имеется только один пустой корневой узел root. При попытке добавить в дерево новое изображение производится проверка, не превышает ли размер вставляемого изображения размера всего атласа. Затем осуществляется поиск подходящего по размерам пустого узла, в который мы можем вставить новую картинку, для этого должны выполняться 2 условия: узел должен быть "пустым" (не содержать в себе изображение и не иметь вложенных в него других узлов -- т.е. вставлять картинку мы можем только в "листья" дерева) и его размеры не должны быть меньше вставляемого изображения. Поиск таких узлов ведется с помощью нисходящего обхода в глубину, данный метод отличается тем, что он не является рекурсивным. О данном методе я прочитал в книге А.А. Кубенского "Структуры и алгоритмы обработки данных...", эта книга, к сожалению, уже нигде не продается (я бы купил себе эту книгу только ради диска с исходниками, которых не найти), но в сети можно легко найти отсканированный вариант. Поиск в дереве начинается с корневого узла и опускается ниже к "листьям", при этом приоритет отдается левым поддеревьям нашего дерева. Если в дереве находится отвечающий условиям поиска узел, то с ним проводятся следующие действия:

1. В него вставляются два узла, общий размер которых равен размеру данного (родителя). При этом, как мы понимаем, узел может делится или по горизонтали, или по вертикали. Для того чтобы решить, как нам делить узел, мы находим разницу между ширинами и высотами этого узла и вставляемого изображения. Если разница по ширине окажется больше, то узел мы делим по горизонтали, в противном случае -- по вертикали (как на иллюстрации ниже).
2. Берем первый из вставленных таким образом узлов и делим его снова на два узла. Размер первого такого "внука" будет равен размеру вставляемого изображения, а второй "внук" будет занимать оставшееся место (также см. иллюстрацию).

Вставка нового изображения в атлас

В общем, алгоритм не сложен, но требует понимания базовых структур данных и принципов работы с ними. Так что крайне рекомендую почитать какой-нибудь из соответствующих учебников.

Мою реализацию текстурного атласа (на as3) можно скачать здесь.