Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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

share|improve this question
    
I was assuming that you are using this for optimizing uv maps, but I am curious what the application is. –  Jonathan Fischoff Aug 16 '10 at 22:06
    
ftgles is library that uses opengl and freetype to render fonts. However each glyph is stored in its own texture. I'd like to pack them into one texture. –  deft_code Aug 16 '10 at 23:30

9 Answers 9

up vote 34 down vote accepted

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.

alt text

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.

share|improve this answer
    
I looked at your texture and thought to myself "I'm sure our texture packer does a bit better than that". And then I went and looked at it, and realised that I broke it some time ago and didn't notice (because once it's working, who looks at the output textures?)... So thanks for posting - wouldn't have found the bug otherwise :) (once I fixed the bug, it looks very similar - maybe a shade better, but it's tricky to tell exactly. "as good" is probably the safest description). –  JasonD Aug 17 '10 at 9:35
    
@JasonD, I'd love to know what your algorithm does, if it gets better output :) Even if it gets roughly equivalent output in a different way. –  ZorbaTHut Aug 17 '10 at 17:39
    
I described it my answer. Essentially I think it's the same as yours, but with a slightly different heuristic. It would be easy for you to try, I think. Change your system to rotate the chars so they're always taller than they are wide, and sort by height rather than area - see what happens. Might be better, might be worse :) As with any heuristic method, there will be good cases and bad cases, but I've generally found that keeping things to be roughly the same shape (by rotating) and sorting by height (which minimises gaps in the initial packing) helps in the average case. –  JasonD Aug 17 '10 at 18:33
    
Thanks for algo description + the admitted fail + the source code. Great post. –  Calvin1602 Aug 22 '10 at 18:03
1  
For how search the latest version of ZorbaTHut's packing code (font_baker.cpp), you can found here: github.com/zorbathut/glorp/blob/… –  mems Mar 27 at 10:17

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.

share|improve this answer

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 :). Packer output

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]
share|improve this answer

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: enter image description here

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.