Packing Lightmaps

Pop Quiz: You have 765,618 lightmaps for a scene and very few of them have power of 2 dimensions, what do you do? If your answer was to rescale them and call CreateTexture 765,618 times please slap yourself. If your answer had anything to do with glTexImage2D, you might want to leave now. What you really want to do is smush them all into a couple larger textures, and this text will show you one way of doing it.

What we'll do is recursively divide the larger texture into empty and filled regions. We start off with an empty texture and after inserting one lightmap we get this:

Here we've split the texture in half by line A then split the upper half by B and inserted the first lightmap to the left of B. When we go to insert the next one, we'll first check if it can fit above A and if it can we check to see if it can fit left of B, nope full, then right of B. If it fits there we split B exactly how we split the original texture, otherwise we insert and split below A. After inserting a second lightmap the texture becomes:

Pretty basic. The implementation of the tree is straightforward. Here it is in a C++ pseudocode hybrid:

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] )

The insert function traverses the tree looking for a place to insert the lightmap. It returns the pointer of the node the lightmap can go into or null to say it can't fit. Note that you really don't have to store the rectangle for each node, really all you need is a split direction and coordinate like in a kd-tree, but it's more convenient with them.

The code that calls Insert can then use the rectangle from the returned node to figure out where to place the lightmap in the texture and then update the node's imageID to use as a handle for future use.

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
        pnode->imageID = new handle
    else
       return INVALID_HANDLE

Once the lightmap is in the larger texture, you'll want to go through any meshes that use it and adjust their texture coordinates based on the lightmap's rectangle in the larger texture.

And now your moment of zen:

Pretty eh? These are some lightmaps from the Near Death Experience tech demo. I've padded each lightmap with white so you can see the separations. Other examples without padding.

Keep in mind that you can apply this same technique not just to lightmaps, but to packing any textures you want into larger ones. For example, the algorithm works like a charm for building font textures.

Anyhow, if you have any questions or comments email jimscott@blackpawn.com. Thanks for reading.