В статье описан алгоритм упаковки лайтмапов в большие текстуры. Так же он применим для генерации атласных текстур (Atlas texture).
Packing Lightmaps. Упаковка карт освещения.
Викторина: у Вас в сцене 765,618 лайтмапов, и лишь некоторые из них имеют размеры кратные степени двойки. Что Вы будете делать? Если Ваш ответ - масштабировать их и вызывать 765,618 раз CreateTexture, если Ваш ответ имеет какое-либо отношение к glTexImage2D - можете дальше не читать.
Что Вам действительно нужно – это склеить их все в пару больших текстур, и этот текст покажет Вам один из способов как это сделать.
Что мы сделаем – рекурсивно поделим большую текстуру на пустые и заполненные регионы. Мы начинаем с пустой текстуры, и после вставки первого лайтмапа мы получаем:
Здесь мы разделили текстуру линией А, верхнюю половину результата линией B и вставили первый лайтмап слева от B. Когда мы вставляем следующий, мы сначала проверяем, может ли он поместиться выше А, если может, мы смотрим поместится ли он слева от B, если там не заполнено, или cправа. Если проверка проходит, то мы делим область справа(слева) от B так же, как поделили исходную текстуру и вставляем лайтмап туда, иначе вставляем лайтмап ниже A и эту область делим как начальную текстуру. После вставки второго лайтмапа текстура становится такой:
Довольно просто. Реализация дерева прямая. Вот она на гибриде C++ и псевдокода:
struct Node
{
Node* child[2]
Rectangle rc
int imageID
}
Node* Node::Insert(const Image& img)if we're not a leaf then // если мы не лист, то
(try inserting into first child)
(пробуем вставить в первый дочерний элемент)
newNode = child[0]->Insert( img )
if newNode != NULL return newNode
(no room, insert into second)
(не поместился, вставляем во второй)
return child[1]->Insert( img )
else
(if there's already a lightmap here, return)(в нем уже есть лайтмап, выходим)if imageID != NULL return NULL
(if we're too small, return)
(если лайтмап не помещается – выходим)
if img doesn't fit in pnode->rect
return NULL
(if we're just right, accept)
(если помещается – выходим с сылкой на нод)
if img fits perfectly in pnode->rect
return pnode
(otherwise, gotta split this node and create some kids)
(иначе разделить этот узел и создать два потомка)
pnode->child[0] = new Node
pnode->child[1] = new Node
(decide which way to split)
(определяем как разделить)
dw = rc.width - img.width
dh = rc.height - img.height
if dw > dh then
child[0]->rect = Rectangle(rc.left, rc.top,
rc.left+width-1, rc.bottom)
child[1]->rect = Rectangle(rc.left+width, rc.top,
rc.right, rc.bottom)
else
child[0]->rect = Rectangle(rc.left, rc.top,
rc.right, rc.top+height-1)
child[1]->rect = Rectangle(rc.left, rc.top+height,
rc.right, rc.bottom)
(insert into first child we created)
(вставляем в первого созданного потомка)
return Insert( img, pnode->child[0] )
Функция Insert перебирает дерево и ищет место для вставки лайтмапа. Она возвращает указатель на узел, в который лайтмап поместится или пустоту – если такого нет. Заметьте, вам не обязательно хранить прямоугольник для каждого узла, достаточно направления разделения и координат как в kd дереве, просто с ним удобней.
Код, который вызывает Insert, может использовать прямоугольник из возвращенного узла чтобы выяснить где поместить лайтмап в текстуре и затем обновить imageID узла чтобы использовать его потом как handle.
int32 TextureCache::Insert(const Image& img)
pnode = m_root->Insert(img)if pnode != NULL
copy pixels over from img into pnode->rc part of texture
//копируем пикселы из img в область на текстуре в пределах pnode->rc
pnode->imageID = new handle
elsereturn INVALID_HANDLE
После упаковки лайтмапов в большую текстуру Вы захотите перебрать все использующие их меши и установить им текстурные координаты исходя из координат прямоугольника лайтмапа в большой текстуре.
И теперь Ваш момент дзена:
Довольны? Это некоторые лайтмапы из Near Death Experience технологического демо. Я дополнил каждый лайтмап белым цветом, чтобы Вы видели разделение. Другие примеры без дополнения белым:
В этих примерах лайтмапы не дополнены белым цветом чтобы Вы могли видеть эффективность алгоритма. Здесь белые области обозначают потраченное впустую место. Лайтмапы были вставлены в текстуру будучи отсортированными по местоположению в карте и размеру (первыми идут бОльшие лайтмапы). Слева - первая текстура в последовательности, справа - последняя.
Имейте в виду, что Вы можете применить эту ту же самую технику не только к лайтмапам, но и к упаковке любых текстур, которые Вы хотите поместить в большие текстуры. Например, алгоритм отлично подходит для построения текстур шрифта.
