Texture packing algorithm

Question

What is a good texture packing algorithm? Technically, bin packing is NP-hard, so a heuristic is what I'm really after.

Answer 1

I spent a few months at one job coming up with a better texture packing algorithm.

The algorithm we started with was simple. Collect all the input items. Sort them by total pixels consumed, large-to-small. Lay them out in your texture in scanline order, just testing stuff from the topleft pixel to the topright pixel, moving down a line, and repeating, resetting to the topleft pixel after every successful placement.

You either need to hardcode a width or come up with another heuristic for this. In an attempt to preserve squareness, our algorithm would start at 128, then increase by 128s until it came up with a result that wasn't any deeper than it was wide.

So, we had that algorithm, and I decided to improve it. I tried a bunch of wacky heuristics - trying to find objects that fit together, doing some weighting over a bunch of desired space packing properties, rotating and flipping. After all my work, quite literally three months of work, I ended up saving 3% space.

Yeah. 3%.

And after we ran our compression routine over it, it actually ended up larger (which I still can't explain) so we threw the entire thing out and went back to the old algorithm.

Sort items, jam into texture in scanline order. There's your algorithm. It's easy to code, fast to run, and you won't get much better without an amazing amount of work. That work just isn't worthwhile unless your company is at least 50 people large, and probably more.

And as a side note, I just implemented this algorithm (fixed width 512 pixels) for quite literally the exact same application that you're doing (no ftgles, but opengl-rendered freetype glyphs.) Here's the result. It looks blurry because mine is using Valve's distance-field based text rendering algorithm, which also accounts for the extra space between glyphs. Obviously, there's not a lot of empty space left over, and it does a good job of cramming things into open spots.

All the code for this is BSD-licensed and available at github (actual packing code file).

Answer 2

The PhD Thesis of Andrea Lodi is entitled Algorithms for Two Dimensional Bin Packing and Assignment Problems.
The thesis goes over some of the harder forms of this problems. Luckily, texture packing is the easiest version. The best algorithm he found was called Touching Perimeter.

To quote from page 52:

The algorithm, called Touching Perimeter (TPRF ), starts by sorting the items according to nonincreasing area (breaking ties by nonincreasing min{wj , hj } values), and by horizontally orienting them. A lower bound L on the optimal solution value is then computed, and L empty bins are initialized. (The continuous lower bound L0 defined in the previous section is obviously valid for 2BP|R|F as well; better bounds are proposed by Dell’Amico, Martello and Vigo [56].) The algorithm packs one item at a time, either in an existing bin, or by initializing a new one. The first item packed in a bin is always placed in the bottom-left corner. Each subsequent item is packed in a so-called normal position (see Christofides and Whitlock [41]), i.e., with its bottom edge touching either the bottom of the bin or the top edge of another item, and with its left edge touching either the left edge of the bin or the right edge of another item.
The choice of the bin and of the packing position is done by evaluating a score, defined as the percentage of the item perimeter which touches the bin and other items already packed. This strategy favours patterns where the packed items do not “trap” small areas, which may be hard to use for further placements. For each candidate packing position, the score is evaluated twice, for the two item orientations (if both are feasible), and the highest value is selected. Score ties are broken by choosing the bin having the maximum packed area. The overall algorithm is as follows.

touching_perimeter:
  sort the items by nonincreaseing w,h values, and horizontally orient them;
  comment: Phase 1;
  compute a lower bound L on the optimal solution value, and open L empty bins;
  comment: Phase 2;
  for j := 1 to n do
     score := 0;
     for each normal packing position in an open bin do
        let score1 and score2 be scores with tow orientations;
        score := max{score,score1,score2};
     end for;
     if score > 0 then
        pack item j in the bin, position and orientation corresponding to score;
     else
        open a new bin and horizontally pack item j into i;
     end if;
  end for;
end;

Also of interest, the paper describes an algorithm to determine the size of an optimally packed texture map. That would be useful to determine if it's even possible to fit all the textures in one 1024x1024 atlas.

Answer 3

A good heuristic algorithm can be found here. When I was trying something similar recently, I found this referenced as the basic starting point for most implementations I saw.

Works particularly well with either lots of regular shaped, similar sized items, or with a good mix of small and fewer larger images. The best advice to achieve good results is to remember to sort your input in terms of image size, then pack from largest to smallest as the smaller images will pack into the space around the larger images. How you do this sorting up to you and may depend on your goals. I used perimeter rather than area as a 1st order approximation since I took the view that tall+thin / short+wide images (which would have lowish area) are actually very hard to place later on in a pack, so by using perimeter you push these odd shapes towards the front of the order.

Here's a sample visulization of the output for my packer on a random set of images from my website image dump directory :).

The numbers in the squares are the id's of the containing blocks in the tree so give you an idea of the order of the insertions. The first is ID "3" because it is the first leaf node (only leaves contain images) and consequently has 2 parents).

        Root[0]
       /      \
   Child[1]  Child[2]
      |
    Leaf[3]

Answer 4

Something I've used, which works well even for irregular UV maps, is to turn the UV patch into a bitmap mask, and maintain a mask for the texture itself, searching for the first position the UV patch will fit into. I order the blocks according to some simple heuristic (height, width, size, whatever), and I allow rotations of the blocks to minimise or maximise the chosen heuristic. That gives a manageable search-space for brute force.

If you can then iterate that trying several heuristics, and/or apply a random factor in choosing the ordering and iterate until some time limit runs out.

With this scheme you'll get small UV islands packed into the gaps made by large ones, and even in holes left within single UV patches themselves.

Answer 5

Algorithm presented by xan should meet every gamedeving needs. It's very, very efficient, lightweight, and I've myself implemented and debugged it in two days, improving it with searching the best possible sorting function (whether it's by area, perimeter, width, height, max(width, height)) and the best possible bin size so you don't have to hardcode the width/height yourself anymore.

It's also easy to design it so it automatically portions out your rectangles into more bins if one with fixed maximum size is not sufficient, so you probably want to pass all your textures to it and pass a maximum texture size as the value for maximum bins' dimension, and BAM ! You have your texture atlases ready to be uploaded to GPU. Same goes for font packing.

Here's the source code (totally independent .h and .cpp file) with example.cpp if you're interested: http://dl.dropbox.com/u/97953376/vc%202010%20express%20sln.zip

400 random rectangles, automatically divided into 3 bins of maximum 400x400 size:

Answer 6

Personally, I just use a greedy largest-block-that-fits first system. It's not optimal, but it does the trick OK.

Note that, if you have a reasonable amount of texture blocks, you can exhaustively search the best ordering even if the problem itself is NP.

Answer 7

We recently released a python script which will pack textures into multiple image files of a given size.

Quoted from our blog:

"While there are numerous packers that can be found online, our difficulty was in finding any that could handle large numbers of images in multiple directories. Thus, our own atlas packer was born!

As is, our little script will start in the base directory and load all the .PNGs into an atlas. If that atlas is filled, it creates a new one. Then, it will try fitting the rest of the images in all previous atlases before finding a spot in the new one. That way, each atlas is packed as tight as possible. Atlases are named based on the folder that their images are from.

You can change the size of the atlas (line 65), format of the images you want to pack (line 67), the load directory (line 10) and the save directory (line 13) fairly easily with no experience in Python. As a small disclaimer, this was whipped together in a few days to work specifically with our engine. I encourage you to request features, comment with your own variations, and report any errors, but any changes to the script will happen in my free time."

Feel free to check out the full source code here: http://www.retroaffect.com/blog/159/Image_Atlas_Packer/#b

Answer 8

It's pretty easy to pack fonts because all (or the great majority) of the glyph textures are nearly the same size. Do the simplest thing that occurs to you and it will be very close to optimal.

Cleverness becomes more important when you're packing images of very different sizes. Then you want to be able to pack into gaps, etc. Even then, though, a simple algorithm like the scanline order search discussed earlier will produce very reasonable results.

None of the advanced algos are magic. They won't be 50% more effecient than a simpel algo, and you won't get consistent benefits from them unless you have a staggering number of texture sheets. that's because the small improvements that better algorithms make will only be seen in aggregate.

Go simple, and move on to something where your efforts will be better rewarded

Answer 9

If it's specifically for font textures, then you probably do something non-optimal but nice and simple:

Sort characters by height, tallest first

Start at 0,0 Place first character at current coords, advance X, place next one, repeat until we can't fit another

Reset X to 0, advance Y downwards by the height of the tallest character in the row, and fill another row

Repeat until we're out of characters, or can't fit another row.