Класс для генерации текстурных атласов

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

Решил писать свой генератор атласов. И самое важное тут — правильно расположить текстуры, чтобы они занимали как можно меньше места. Поиск выдал статью, где описывается алгоритм и даже даётся псевдокод (автор, убей себя за такой невнятный псевдокод). Эта статья и легла в основу моего класса (передрал подчистую, как только понял, что имел в виду автор своим кривым псевдокодом).

Хочу поделиться с вами этим классом, возможно он сэкономит кому-то время и нервы.

package  {
  import flash.geom.Rectangle;
  /**
  * ...
  * @author Makar Osokin (elmortem@gmail.com)
  */
  public class AtlasNode {
    public var childs:Vector.<AtlasNode>;
    public var rect:Rectangle;
    public var data:Object;
                
    public function AtlasNode() {
      childs = new Vector.<AtlasNode>();
      rect = new Rectangle();
      data = null;
    }
                
    public function insert(width:Number, height:Number, data:Object):AtlasNode {
      if(childs.length > 0) {
        var newNode:AtlasNode = childs[0].insert(width, height, data);
        if (newNode != null) return newNode;
        
        return childs[1].insert(width, height, data);
      } else {
        if (this.data != null) return null;
        
        if (width > rect.width || height > rect.height) return null;
                                
        if (width == rect.width && height == rect.height) {
          this.data = data;
          return this;
        }
        
        childs.push(new AtlasNode());
        childs.push(new AtlasNode());
        
        var dw:Number = rect.width - width;
        var dh:Number = rect.height - height;
        
        if (dw > dh) {
          childs[0].rect = new Rectangle(rect.left, rect.top, width, rect.height);
          childs[1].rect = new Rectangle(rect.left + width, rect.top, rect.width-width, rect.height);
        } else {
          childs[0].rect = new Rectangle(rect.left, rect.top, rect.width, height);
          childs[1].rect = new Rectangle(rect.left, rect.top + height, rect.width, rect.height-height);
        }
                                
        return childs[0].insert(width, height, data);
      }
    }
  }

}

Используется данный класс очень просто:

var atlas:AtlasNode = new AtlasNode(); // создаём наш атлас
atlas.rect.width = 1024; // задаём размер
atlas.rect.height = 1024;
// финальный массив для хранения областей на атласе
var atlasArr:Array/*AtlasNode*/ = [];
// массив картинок или любых других объектов у которых есть размер
var bmpArr:Array/*BitmapData*/... 
// сортируем для лучшего качества упаковки
bmpArr.sortOn(['width', 'height'], Array.NUMERIC | Array.DESCENDING);

for(var i:int = 0; i < bmpArr.length; i++) {
  // пытаемся вставить картинку в атлас
  var n:AtlasNode = atlas.insert(bmpArr[i].width, bmpArr[i].height, bmpArr[i]);
  if(n != null) {
    // нам это удалось
    atlasArr.push(n); // сохраняем область в финальный массив
  } else {
    // места не хватает
    throw("Размер атласа надо увеличить!");
  }
}

Теперь нам осталось только отрисовать все картинки из atlasArr[x].data в координаты atlasArr[x].rect.

Если надо сделать бордюры между текстурами, то просто вставляйте объект добавляя к его ширине и высоте двойной размер бордюра, а затем при отрисовке картинок в атлас смещайте картинки на размер бордюра.

P.S. Stage3D рулез! (: