Cramming the most into a Sprite Atlas - (Bin Packing Problem)

Performance Tuning
#1

Hey all -

I am trying to make a perfectly optimized Sprite atlas. That means, given any collection of small sprites, I want to find (very quickly) a good way to cram them all into a big image with minimal waste. This essentially the same problem as the 2D cutting stock problem, for which I found this paper: http://www.inf.uos.de/papers_html/or_94/cutpaper.html . However, I don’t want to be able to rotate my sprites 90º, so this algorithm doesn’t fit my desires exactly.

So, I was wondering 2 things:

  1. Has anyone implemented this Java before? If so, would you be willing to share source so I can save myself time?
    or
  2. Does anyone have ideas on a good way to do this, given that rotations are not allowed? Genetic and other learning algorithms won’t really do the trick because they take a long time to get up to speed. At most, I want a wait of about 10 seconds for a 1024x1024 Atlas.
#2

Forgive me for asking, but why don’t you want to rotate your images 90 degrees?

In OpenGL you will have exactly the same performance.
In Java2D you can just ‘extract’ your atlas sprites once.

But heck, you might have a very good reason :slight_smile:

#3

It’s all about time. :slight_smile: These are images that exist already in an engine that exists already in a project that is supposed to be done in 10 days. Although it’s obviously easy to rotate in OpenGL and there’s no performance hit, it means another couple of hours of adjusting the SpriteAtlas code to allow for rotated sprites. I’m just trying to avoid the extra work at this juncture. If that’s not an option, then by all means I can go for it.

#4

This sounds more like the bin packing problem (though that usually assumes you’ve been given a fixed bin/image size to work with). A quick search doesn’t turn up any Java code, but here are some discussions on simple greedy approaches: http://www.gamedev.net/community/forums/topic.asp?topic_id=392413

#5

This is basically 2d bin packing which means it’s np-hard so you’re not going to find a ‘perfect’ solution other than the brute-force method of trying every possible combination and taking the best one.

I’ve got a 2d atlas within Rebirth, which is implemented like a container so you could use that if you wanted (check out the Atlas class ).

If you wanted to do it yourself then there’s a few different approaches. The one I settled on is to use a 2d bsp to divide the space, if you combine this with inserting rectangles from largest to smallest you get very little wasted space (since the smaller rectangles tend to fill up the awkward holes left by the bigger sprites).

Example atlas:

http://triangularpixels.com/Junk/packed.png

#6

Ooh, is that algorithm loads better than the one in SPGL? I’ve been wondering about getting a better one.

Cas :slight_smile:

#7

That looks great, although I couldn’t find any source for Atlas to take a look at.

So basically all you do is start with the biggest sprite, make your way to the right with progressively smaller sprites, and simply stick each sprite wherever it will fit at first? And is “2D BSP” a 2D binary-space partitioning tree? I guess the tree is the best way to determine what space is open and what isn’t.

#8

Rebirth is a binary-only library at the moment until I get some distribution and licensing gubbins sorted out. Something I’ve been meaning to do for a while…

[quote]So basically all you do is start with the biggest sprite, make your way to the right with progressively smaller sprites, and simply stick each sprite wherever it will fit at first?
[/quote]
It’s not quite that simple - basically the tree is a bunch of nodes with a ‘first’ and ‘second’ child nodes, which split the parent rect into two (where splitting alternates between horizontal and vertical at each level). To insert you find the first leaf that it can fit within, then split that into two and mark one half as allocated.

Alternative heristics are sorting by largest-edge or sorting by width then height, but I found by area gave the best results for sprite-like rectangles.

#9

Right. I’m trying a sort of quad-tree implementation, like this:

  1. If the added rect has a bigger size than this one, return.
  2. If this one already has something in it, return.
  3. If this one has no children, ether add directly to this node if the size is an exact match, or split this into 4 nodes, using both the horizontal and the vertical to do so, then add to the top-left node (which will be an exact match in size).
  4. If this one has children, try to recursively add to each one in turn.

This seems like it should work fairly well and was quick to implement, but I haven’t tested it thoroughly yet. It will definitely appears like it will be less effective than alternating between vertical and horizontal, but good enough for my purposes. I’ll try the other if this works shittily.

#10

From the sounds of it, I implemented the algorithm that Orangytang is talking about in this thread.

#11

Check out my image packer (originally inspired by the one in SPGL):
http://code.google.com/p/skorpios/source/browse/trunk/skorpios-desktop/tools/com/esotericsoftware/skorpios/tools/ImagePacker.java
It strips transparent space off images and packs them using this algorithm:
http://www.blackpawn.com/texts/lightmaps/default.html
The resulting images and metadata file are loaded with this:
http://code.google.com/p/skorpios/source/browse/trunk/skorpios-common/src/com/esotericsoftware/skorpios/opengl/PackedImages.java
It is super easy to make animations:
http://code.google.com/p/skorpios/source/browse/trunk/skorpios-common/src/com/esotericsoftware/skorpios/opengl/Animation.java
I can take the raw PNG sequence output from particleIllusion, run it through the image packer, and display the animation in my game with no other steps. Eg:
http://n4te.com/temp/explode1.png

The image packer is useful for anyone, the PackedImages and other classes are specific to the Skorpios Android/desktop OpenGL project, but are easily modified for use elsewhere. Eg, it was very easy to port the PackedImages class to the iPhone. It would be even easier to port to a different OpenGL binding in Java.

#12

Thanks so much for the source, bleb and Nate, and thanks for the help everyone. I finished my own implementation unfortunately before I saw your sources, but oh well, that’s the breaks, right?

My next step is to take all the layers in a single PSD file and get the images out of those, then pack them. That would be useful and maybe fun. :slight_smile:

#13

FWIW, PS CS4 comes with an export layers script that can export to PNG. Not quite as cool though. :slight_smile:

#14

That would seem like the least efficient way to go here.

#15

Very true, but in what I’m doing the artists made the Atlases manually in a PSD. But I was more joking, I’m not about to do that unless I have free time (which I don’t).

Here are my two implementations:

  1. Uses the same method as Orangy Tang. Alternates between vertical and horizontal splitting. Does not allow 90 degree rotation.

http://img710.imageshack.us/img710/962/screenshot20091209at311.png

  1. Uses a slightly different method that splits a node into 4 pieces (both vertical and horizontal at the same time). Also does not allow 90 degree rotation.

http://img30.imageshack.us/img30/226/screenshot20091209at317.png

The methods looks to be pretty comparable, surprisingly - it all really depends on the distribution of sprite sizes you’ve got.

#16

Could you try running the same images through my ImagePacker?

#17

Unfortunately, no. The distribution is totally random. :frowning: You’ll notice it’s slightly different in the two screenshots.

#18

Use a Random object and hard-code the seed to get the same random sprites each time.

#19

It’s worth noting that if you’ve got so many sprites you need multiple sprite sheets, that it’s not necessarily the most efficient thing to do to find the best fit in any sheet for any one sprite. Often sprites are used in sequence or in clusters, and if you have each sprite in a sequence spread out over 16 4MB sprite sheets, you run the risk of texture thrashing on lower end cards. Just a thought.

Cas :slight_smile:

#20

Sort sprites by texture?