Мои мысли и проекты

Создание текстурного атласа: алгоритм+исходник

Навигация
Счетчики
Cпoнcоры

Создание текстурного атласа: алгоритм+исходник


Введение


Перед многими программистами вставала задача объединения некоторого набора текстур (картинок) в одну большую текстуру. Эта большая текстура называется текстурный атлас. Как правило текстурный атлас очень активно используется программистами, работающими с API вывода 3D графики. Связано это с тем, что использование одной большой текстуры вместо большого количества маленьких позволяет уменьшить количество переключений рендера, что сильно увеличивает производительность 3D приложений.
Поиск по Internet-у дал мне следующие ссылки: ссылка 1, ссылка 2. Мой алгоритм является адаптацией приведенных ссылок под мою задачу. Мне понадобился данный алгоритм для создания шрифтов, т.е. в качестве текстур в моем случае выступают отдельные символы шрифта. Алгоритм позволяет не только выделять область в существующей текстуре, но также и освобождать ненужную область для последующего использования. Также в алгоритме предусмотрено использование нескольких текстур, т.к. место на одной текстуре может не хватить.

Описание алгоритма добавления (выделения)


Изначально вся текстура представляет собой один единый контейнер 0 (рисунок 1).

После выделения в контейнере области 00 исходный контейнер можно разбить на 3 области. Есть два варианта такого разбиения рисунок 2a и рисунок 2б.

При разбиении мы будем выбирать тот вариант, при котором образуется контейнер с минимальной диаганалью. В нашем случае более предпочтителен вариант 2б, т.к. при этом контейнер 01 имеет наименьшую диаганаль.
Следующим важным моментом алгоритма является стратегия поиска пустого контейнера для выделения новой области. На шаге 2 у нас имеется два свободных контейнера: 01 и 02. Очевидно, что при поиске пустого контейнера для выделния такой контейнер должен быть больших размеров, чем требуемая область выделения. При этом при наличии двух подхожящих контейнеров более предпочтительнее выбирать наименьший, т.к. больший по размерам контейнер может понадобиться в дальнейшем для выделение области большого размера. Если же каждый раз дробить большие области, то в некоторый момент у нас может не найтись контейнера подходящего размера, но при этом в наличии будет множество контейнеров меньших размеров.
При расмотрении вариантов разбиения мы не рассматривали варианты, когда выделяемая область по размерам равна контейнеру либо по горизонтали или вертикали, либо сразу и по горизонтали и вертикали. С учетом таких разбиений вполне очевидно, что при наличии двух пустых контейнеров нужно выбирать тот, который дает наименьшее количество разбиений. Т.е. мы пришли к следующим выводам: при поиске контейнера нужно выбирать контейнер, который
  1. Дает наименьшее количество разбиений
  2. При одиноковом количестве разбиений тот контейнер, который меньше по размерам

Также при добавлении рекомендуется добавлять (выделять) области в порядке убывания их размеров.

Описание алгоритма удаления (освобождения)


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

Легко можно заметить, что теперь у нас в наличии три пустых контейнера: 00, 01, 02. Однако все эти контейнеры состовляют из себя контейнер 0 и было бы логично удалить три состовляющих контейнера, оставив больший по размеру родительский контейнер. Т.е. при освобождении области мы должны
  1. Если не все дочерние контейнеры пустые, то просто создать новый контейнер по размерам равный освобождаемой (удаляемой) области
  2. Иначе освобождаем текущий контейнер от всех дочерних ( т.е. проводим объединение дочерних контейнеров в один ). После того, как мы освободили текущий контейнер, сделаем проверку: а может родительский контейнер (если он есть) тоже содержит только пустые контейнеры? И если это так, то объединим его. После этого возьмем родительский контейнер родительского контейнера и выполним аналогичную проверку на объединение. Выполняем данную проверку до тех пор, пока имеется факт объединения или пока есть родительский контейнер

Такой подход позволит оптимизировать использование освобожденных ( удаленных ) областей. Рассмотрим рисунок 3б.

На нем у нас занята только область 020. При её освобождении ( удалении ) по описанному выше алгоритму произойдет объединение контейнеров 020+021+022 в контейнер 02, а затем объединение контейнеров 00+01+02 в контейнер 0. Т.е. после освобождения выделенных областей мы вернемся к первоначальному общему контейнеру. И последующие выделения будут более оптимальны.

Примеры


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

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

Использование исходников


Описанный выше алгоритм текстурного атласа реализован в виде шаблона.
Код: c++
template <class UserSurface,typename TYPESIZE,typename BYTE8BIT> class TAtlas

Описание параметров начнем начиная с последнего.
  • BYTE8BIT - восьмибитное целое число для определения компонента цвета. Значение от 0 до 255.
  • TYPESIZE - тип для задания размеров областей и координат областей на поверхности.
  • UserSurface - класс поверхности для конкретной реализации.

Остановимся поподробнее на классе UserSurface. Выделение области памяти на текстурном атласе является универсальной задачей. Однако создание поверхности, чтение и копирование данных на ней зависят от API, на котором мы работаем. Это может быть OpenGL, DirectX или что-то другое. Чтобы шаблон начал работать с нужным вам API требуется реализовать класс UserSurface. Для этого необходимо создать свой класс, сделав его наследником шаблона:
Код: c++
//! Прототип повехности
//  От неё наследуются все поверхности для конкретной реализации
template <typename TYPESIZE,typename BYTE8BIT> class TSurface
{		
	private:
		typedef TContext<TYPESIZE,BYTE8BIT> Context;
	public:
		TSurface()
		{
		};
		virtual ~TSurface()
		{
		};
	public:
		//--------------------------------------------------------------------------------------
		//! Вирутальные фукнции поверхности
		//--------------------------------------------------------------------------------------
		//! Инициализация поверхности
		virtual bool OnInit(TYPESIZE width,TYPESIZE height) { return true; };
		//! Уничтожение поверхности
		virtual void OnDestroy() {  };
		//! Чтение данных с поверхности массив пикселей (из указанной области)
		virtual void OnRead(typename Context::Pixel *pixels,TYPESIZE x,TYPESIZE y,TYPESIZE width,TYPESIZE height) {};
		//! Запись данных на поверхность из массива пикселей (в указанную область)
		virtual void OnWrite(typename const Context::Pixel *pixels,TYPESIZE x,TYPESIZE y,TYPESIZE width,TYPESIZE height) {};
		//! Сохранение поверхности в файл
		virtual void OnSave(const char *filepath,int num) {};
};


В новом классе необходимо переопределить виртуальные функции и объявить свой класс, основанный на шаблоне TAtlas, указав ему в качестве параметра свой класс для работы с поверхностью. Все функции имеют понятные, на мой взгляд, мнемонические имена. Пояснения требует функция OnSave(). В этой виртуальной функции вам необходимо написать код для сохранения поверхности в файл изображения. Такая возможность может вам понадобится при отладке вашего приложения.
В примере имеется реализация класса для Windows, которая находится в файлах AtlasWin.h и AtlasWin.cpp.

Использовать текстурный атлас достаточно просто:
Код: c++
	// Объект атласа
	CAtlasWin oAtlasWin(256);
	// Выделить область размером 32x64
	CAtlasWin::Area *area = oAtlasWin.Alloc(32,64);
	// Заблокировать поверхность для графических операций
	CAtlasWin::Context *context = area->Lock();
	if(context)
	{	// Нарисовать фон
		context->FillRect(0,0,255);
		// Нарисовать прямоугольник
		context->FillRect(10,20,10,30,0,255,0);
		// Поставить точку в углу
		context->SetPixel(0,0,255,0,0);
		// Закончить операцию отрисовки
		area->UnLock(context);
	}
	// Сохранить все атласные поверхности в файл
	oAtlasWin.Save("m:\\.temp");

Не забудьте исправить путь в строке 18 на существующий на вашем компьютере, иначе файлы tex-xxx.bmp, где xxx - номер поверхности не будут создаваться!

Контекст CAtlasWin::Context *context на текущий момент содержит всего два метода для отрисовки:
  • SetPixel - установить точку в заданных координатах
  • FillRect - нарисовать прямоугольник заданным цветом
  • DrawRect - нарисовать прямоугольную рамку заданным цветом

В дальнейшем я планирую расширить функциональность этого объекта для рисования линий, окружностей и других геометрических фигур.

20.10.2011 Доработал исходники по результатам использования в своей программе. Исправил некоторые ошибки.

Категории: Алгоритмы, Программирование