Texture packing algorithm

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);
    }
}