# Texture packing algorithm

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

• 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

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.

• 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
• Thanks for algo description + the admitted fail + the source code. Great post. – Calvin1602 Aug 22 '10 at 18:03
• The reason it got larger after compression is probably because of the compression algorithm. Since compression often relies on hashing and finding binary patterns, if the algorithm can identify enough patterns it'll generate a whole bunch of them which can cause the size to expand. a great way to test this it to simply re-zip a file over and over again and eventually it'll start getting bigger again due to the lack of patterns. – Hanna Jun 3 '13 at 17:09
• 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 '14 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 deﬁned 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 ﬁrst 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 Christoﬁdes 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, deﬁned 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.

• This algorithm assumes that textures are of rectangular shape, is that right? – user1767754 Apr 28 '19 at 6:49

If anyone is still interested, I have completely rewritten the rectpack2D library so that it is way more efficient.

It works by keeping a std::vector of empty spaces in the atlas, beginning with some initial maximum size (typically, the maximum allowed texture size on a particular GPU), splitting the first viable empty space and saving the splits back to the vector.

The performance breakthrough came with just using a vector, instead of keeping an entire tree, like it was previously done.

The procedure is described in detail in the README.

The library is under MIT, so I'm happy for you if you find it useful!

## Example results:

Tests were conducted on a Intel(R) Core(TM) i7-4770K CPU @ 3.50GHz. The binary was built with clang 6.0.0, using an -03 switch.

### Arbitrary game sprites + Japanese glyphs: 3264 subjects in total.

Runtime: 4 milliseconds
Wasted pixels: 15538 (0.31% - equivalent of a 125 x 125 square)

Output (2116 x 2382):

In color:
(black is wasted space)

### Japanese glyphs + some GUI sprites: 3122 subjects.

Runtime: 3.5 - 7 ms
Wasted pixels: 9288 (1.23% - equivalent of a 96 x 96 square)

Output (866 x 871):

In color:
(black is wasted space)

• I've downloaded your code. Just reading the struct definitions: WHAT IS THIS MONSTROSITY?! It looks like code golf. – akaltar Aug 15 '15 at 22:29
• Still, it works, and it helped, so thanks. I didn't want to be rude. – akaltar Aug 15 '15 at 23:20
• Not sure why I skipeed this answer since it is even faster and more good packer than my own algorithm O_O thanks – CoffeDeveloper Aug 19 '15 at 18:59
• @akaltar I can imagine that, I was still learning the language during the time :) – Patryk Czachurski May 7 '16 at 15:23
• Fairly simple approach that's quick to implement and gets good results, thanks :) – FlintZA May 9 '16 at 9:07

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]


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.

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.

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

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

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.