As we all do at some point in our lives, I needed to build texture atlases computationally. Filling up a large image with lots of smaller ones in an optimal way is NP-Complete, aka unsolvable. It’s the 2D equivalent of the knapsack filling problem. So I packed my approximation bags and boarded the heuristic express to guess-ville. It turns out you can get great results with even a very simple algorithm.
I start with a set of images and have one large image, or ‘atlas’ to place them all in to. I don’t try to find the best atlas size here, I just have a predefined atlas size and want to fit as much on to it as I can. The commonly suggested method is using BSP trees to partition free atlas space. That’s similar to the approach I took, but I simplified the tree structure away. Here’s what I did.
The first step is this sort of situation is always going to be sorting the target images in terms of awkwardness. We want to place the most difficult to place images first so that we don’t waste space. What makes an image ‘hard to place’?
- Larger images are more difficult because they use more empty space.
- Squarer images are more difficult because they don’t fit well in to spare space in the atlas.
The largest, squarest images are hardest. Large images have a large area (= w * h), and squarer images have a smaller perimeter (= 2w + 2h) than equally sized counterparts. A good ranking value is area divided by perimeter, or ((w * h) / (2w + 2h)). Multiplying by 2 cancels out the constants in the denominator. This is a very simple and very effective way of estimating an image’s placement difficulty: ((w * h) / (w + h)). I started by sorting my images with this ranking, with the first image scoring the highest and the last image scoring the least.
At this stage, there is another simplification that could be performed. That is to transform all images to portrait (or landscape) form. Just loop through each and if you find that w < h, rotate the image by ninety degrees and remember to correct the uv coordinates later. That way every image will have the precondition that w >= h and it might make the placement easier. I never bothered doing this because I’m a little lazy.
To place the images, I made a list of rectangles of free space in the atlas. Initially I placed the full area of the atlas in to this list. For each image I needed to place, I searched the list of free rectangles for the best fit. How did I calculate the best fit? I picked the rectangle that had the snuggest fit, which wasn’t a particularly clever heuristic but it did a good enough job. It’s just the minimum axis of the rectangle size minus the image size. If it’s less than zero, it means the image will not fit in this rectangle.
I copied the image in to the best fitting rectangle, and stored its uv coordinates. I removed the rectangle from the list and then added in up to two extra rectangles of unused space to the list of free rectangles. If the fit was snug, it may not leave two rectangles of free space, it could leave one or zero. To divide up the rectangle, I picked the cuts that leaves the largest rectangle.
I kept doing this until all images were placed or until space ran out, which is also known as “the bad ending”. The results were very good. A few tweaks here and there might improve it, but even this naive implementation is getting >90% coverage, as you can see in this slightly faked-out real world example:
And that was good enough for me.