I was exporting some textures from an old game, and needed an algorithm to pack many small textures into a texture atlas. I found a very nicely explained algorithm on this page and wanted to share, if someone might need something like this:
http://www.blackpawn.com/texts/lightmaps/default.html
There are some other interesting articles from the same guy here:
http://www.blackpawn.com/texts
The packing algorithm is so simple, I didn't think it would work. You just create a node with the output texture size and loop trough your images and call Insert() with individual texture's width and height. The node recursively splits itself if its size doesn't match the input, and calls Insert() of the child nodes. The node that gets returned holds the final [x,y] position, and if it returns NULL it means the image couldn't fit.
The grey lines mark individual textures and animations that I grouped together in code, so it doesn't all get mixed, but that is another story.
Tip 1.
In the example above I sorted my images according to their size(width*height) before I started to call Insert().
Tip 2.
If you look at the examples from the link, you will see the images are stored in an upside-down L pattern starting from top left, so if your output image is too big the input images will be positioned in the L pattern and the rest of the space(bottom right) is left unused. To avoid that;
- I sum the size of all the textures and set node width and height to sqrt(sum), so I have a minimum square output.
- Then I check if some image has width higher than that, if so I take that value for the final node width, so it can fit.
- The final height is some arbitrary huge value. While calling Insert() I keep track of where the bottom corners of the images end up and take the maximum value when creating the actual output image, which, after all this mess, should be more or less a square.
C++
Here is my implementation in C++ to spare you 2 minutes of converting the pseudocode. Unfortunately Blogger doesn't have code tags or something to format it properly.
#include <vector>
class AR_Node
{
public:
std::vector<AR_Node> child; //child nodes
int x, y, w, h; //position and node size
bool image; //image stored in the node
AR_Node* Insert(int img_w, int img_h);
AR_Node()
{
this->x = y = w = h = 0;
this->image = false;
}
};
AR_Node* AR_Node::Insert(int img_w, int img_h)
{
//if we are not a leaf then
if(!this->child.empty())
{
//try inserting into first child
AR_Node *newNode = this->child[0].Insert(img_w,img_h);
if(newNode!=NULL) return newNode;
//no room in first child, insert into second
return this->child[1].Insert(img_w,img_h);
}
else
{
//if there is already a image here, return
if(this->image) return NULL;
//if image doesn't fit, return
if(this->w<img_w || this->h<img_h) return NULL;
//if we're just right, accept
if(this->w==img_w && this->h==img_h)
{
this->image = true;
return this;
}
//otherwise split this node and create some children
this->child.push_back(AR_Node());
this->child.push_back(AR_Node());
//decide which way to split
int dw = this->w - img_w;
int dh = this->h - img_h;
if(dw>dh)
{
//vertical split
//left
this->child[0].x = this->x;
this->child[0].y = this->y;
this->child[0].w = img_w;
this->child[0].h = this->h;
//right
this->child[1].x = this->x + img_w;
this->child[1].y = this->y;
this->child[1].w = this->w - img_w;
this->child[1].h = this->h;
}
else
{
//horizontal split
//up
this->child[0].x = this->x;
this->child[0].y = this->y;
this->child[0].w = this->w;
this->child[0].h = img_h;
//down
this->child[1].x = this->x;
this->child[1].y = this->y + img_h;
this->child[1].w = this->w;
this->child[1].h = this->h - img_h;
}
//insert into first child we created
return this->child[0].Insert(img_w,img_h);
}
}
