Упаковка статических карт освещения

Данная задача встает перед разработчиком программы для расчета карт освещенности, или просто упаковки множества маленьких текстур в одну.

Недавно, нашел описание подхода [1], все бы хорошо, но есть пару но:
Слишком уж заумно написано и не совсем понятный алгоритм, возможно автор упустил, что-то в коде, хотя пример лежит в интернете довольно долго, может, я чего-то не понял, в итоге я на него вскоре забил.

Итак, поступим проще:

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

Рис.1 Графическое отображение алгоритма построения дерева

На рис.1. приведена графическая интерпретация алгоритма. Суть его в следующем: первым делом мы помещаем наш лайтмап в крайний левый угол. Далее при добавлении следующей текстуры, мы смотрим можно ли ее добавить справа, высотой не более hA и длиной не более W-wA, если она не входит по размерам, то смотрим можно ли ее добавить ниже длиной W и высотой H-ha.

Рис. 2 Графическое отображение алгоритма шаг второй

Продолжаем упаковывать лайтмапы таким же образом, пока не израсходуем их все или не закончатся размеры текстуры. Вполне просто, ниже я приведу кусок кода (слегка не оптимален, зато более понятен, я же не для гуру пишу (). Ну что, пристегнули ремни, поехали….

struct Rectangle
{
  Rectangle() {};
  ~ Rectangle() {};
  int w; //абсолютная длина текстуры
  int h; // абсолютная высота текстуры
  int sw; // начало квадратика по ширине
  int sh; // начало по высоте
};
Class CNode // наш класс
{
  CNode() {IsUsed=false;}; // конструктор
  ~CNode() {}; // деструктор
  child *CNode[2];
  bool IsUsed;
  Rectangle rect;
  bool insert(Rectangle Img);
  void init();
  void init(Rectangle rect); // еще возможный вариант инициализации
};

CNode myLmapPacker; // структура для запаковки в текстуру
int H=256,W=256; // размеры текстуры

// здесь рекурсивный алгоритм сортировки
bool CNode ::insert(Rectangle Img)
{
  // проверим узел уже занят текстурой?
  If(this->IsUsed!=true)
  {
   if(Img.hrect.h && Imh.wrect.w)
   {
     // создадим узел справа
     child[0] = new CNode;
     child[0]->rect.h=this->rect.h;
     child[0]->rect.sh=this->rect.sh;
     child[0]->rect.w=W-this->rect.w-this->rect.sw;
     child[0]->rect.sw=this->sw+this->w;
     // создадим узел ниже
     child[1] = new CNode;
     child[1]->rect.h=H-this->rect.h-this->rect.sh;
     child[1]->rect.sh=this->rect.sh+this->rect.h;
     child[1]->rect.w=W-this->rect.sw;
     child[1]->rect.sw=this->sw;
     this->IsUsed=true;
     return true;
     } return false; //«облом», не влезла
    }else // пройдем по детям
     for(int I=0;I<2;I++) if(this->child[I]!=NULL)
       if(this->child[I].insert(Img)==true)
          return true;
   return false; // увы «облом»
};

// необходимо вызвать для инициализации самого первого узла,
// можно проинициализировать и по другому…
void CNode::init()
{
  // все что хотим проинициализировать
  this->rect.sw=0;
  this->rect.sh=0;
  this->rect.h=H;
  this->rect.w=W; // первому узлу принадлежит вся текстура, не так ли?
};

// можно использовать к примеру в функции insert()
void init(Rectangle rect)
{
  // что-то вроде…
  this->rect=rect;
};

Вот господа и усе, с вами был капитан корабля, полет прошел быстро и без осложнений! Вызывается функция для добавления текстурки следующим образом:

…
for i все лайтмапы do
MyLightmapPacker.insert(лайтмап[I].Rect);
…

Для увеличения числа текстур код необходимо слегка модифицировать, это не сложно.