Войти
Антон АксёновСтатьи

Packing Lightmaps. Упаковка карт освещения (перевод)

Автор:

В статье описан алгоритм упаковки лайтмапов в большие текстуры. Так же он применим для генерации атласных текстур (Atlas texture).

8<-------

Packing Lightmaps. Упаковка карт освещения.

Викторина: у Вас в сцене 765,618 лайтмапов, и лишь некоторые из них имеют размеры кратные степени двойки. Что Вы будете делать? Если Ваш ответ - масштабировать их и вызывать 765,618 раз CreateTexture, если Ваш ответ имеет какое-либо отношение к glTexImage2D - можете дальше не читать.
Что Вам действительно нужно – это склеить их все в пару больших текстур, и этот текст покажет Вам один из способов как это сделать.

Что мы сделаем – рекурсивно поделим большую текстуру на пустые и заполненные регионы. Мы начинаем с пустой текстуры, и после вставки первого лайтмапа мы получаем:

coriolis_diag01 | Packing Lightmaps. Упаковка карт освещения (перевод)coriolis_diag02 | Packing Lightmaps. Упаковка карт освещения (перевод)

Здесь мы разделили текстуру линией А, верхнюю половину результата линией B и вставили первый лайтмап слева от B. Когда мы вставляем следующий, мы сначала проверяем, может ли он поместиться выше А, если может, мы смотрим поместится ли он слева от B, если там не заполнено, или cправа. Если проверка проходит, то мы делим область справа(слева) от B так же, как поделили исходную текстуру и вставляем лайтмап туда, иначе вставляем лайтмап ниже A и эту область делим как начальную текстуру. После вставки второго лайтмапа текстура становится такой:

coriolis_diag03 | Packing Lightmaps. Упаковка карт освещения (перевод)coriolis_diag04 | Packing Lightmaps. Упаковка карт освещения (перевод)

Довольно просто. Реализация дерева прямая. Вот она на гибриде 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
    else
       return INVALID_HANDLE

После упаковки лайтмапов в большую текстуру Вы захотите перебрать все использующие их меши и установить им текстурные координаты исходя из координат прямоугольника лайтмапа в большой текстуре.

И теперь Ваш момент дзена:

coriolis_ex110000 | Packing Lightmaps. Упаковка карт освещения (перевод)  coriolis_ex200000 | Packing Lightmaps. Упаковка карт освещения (перевод)

Довольны? Это некоторые лайтмапы из Near Death Experience технологического демо. Я дополнил каждый лайтмап белым цветом, чтобы Вы видели разделение. Другие примеры без дополнения белым:

coriolis_ex3 | Packing Lightmaps. Упаковка карт освещения (перевод)    coriolis_ex4 | Packing Lightmaps. Упаковка карт освещения (перевод)

В этих примерах лайтмапы не дополнены белым цветом чтобы Вы могли видеть эффективность алгоритма. Здесь белые области обозначают потраченное впустую место. Лайтмапы были вставлены в текстуру будучи отсортированными по местоположению в карте и размеру (первыми идут бОльшие лайтмапы). Слева - первая текстура в последовательности, справа - последняя.

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

Оригинал статьи

Если у Вас есть какие-либо вопросы или комментарии - . Спасибо за чтение.
Статью перевёл Coriolis (c) 2006 (Не пинайте пианиста, он играет как умеет).

#atlas, #lightmaps, #maps, #текстуры

23 ноября 2006 (Обновление: 16 фев. 2010)

Комментарии [11]