Hello, first of all I'd like to mention that I've been reading gd topics for a long while now and I find the community quite fascinating to say the least. Lots of topics involved and tons of solutions, its always nice to come and read; learn something new for a change. I'm just starting with game development and one thing I'd like to have in my game is packed sprites, because I don't want to load 10s of separate images; so to save resources I'd like to pack this sprites into one POT texture. My problem: I don't know of any efficient algorithms to do this. Could someone please point me to the right direction regarding this subject?. I'd like to pack the images offline (ie. not in realtime) so computational cost is not an issue to me, but the efficiency in which the objects are packed is indeed of concern. Ideally I would like to input an image and output a list of rect structures. I have a few constants, for instance my background is always of the same color (RGB 255,0,255) and objects never overlap. Having this list of rects I'd be able to easily create the packed image and save it later on... I just can't find a good solution, also, what's the name of this operation? I know it's not packing since that comes later on after I've got the list of objects... Well enough chatting for me :) Any help will be appreciated, thanks. gusso

This topic is usually called "texture packing". Doing a search for that on the forum should turn up a few good hits include this thread which contains actual source.

Hi SiCrane, thanks for the link.

However, this assumes I already have my list of objects, right?. And what I'm looking for is actually detecting the different objects in an image so I can later on pack them into the final image.

I don't know if it makes sense but the artist usually draws the sprites on a huge canvas and they are fairly ordered alright, but there is a lot of wasted space, if he exports the sprites one by one then I'd be wasting resources by loading them, one by one. That's why I would like to simply get the huge image, find out the amount / placement of each "object" and then pack it up into the final POT texture.

Yes, I'm ok with non-trivial reasoning of how it _could_ be done, but I'm wondering if there is already an algorithm that does it, what's the name of it, where can I read about it?, etc.

I usually implement things in my way of thinking but funny enough, it's rarely the best way around.

While searching Google for "texture packing algorithm" and "rectangle packing" and similar turns up some academic papers on the topic, some rather dry, I think you might just want to skip the work and use already developed tools for the job. One such tool is available in this forum, actually.

Thanks, I'll take a look on that tool.

However I'm still very much interested on learning about the internals, so I'd still like to program it.

The problem with that tool (by just watching at the screenshot) is that it takes several images and packs them... My problem is: my images are all inside one big image, I want to programatically split the images (or at least find their bounds).

Well, I didn't read carefully enough it seems :-) Sorry about that.

You do say that you have the option of having the artist export the images one by one. That seems like the easiest solution - just get him to give you the images separately, then pack them using a utility program like the one I linked. No resources will be wasted since the end result is one packed texture.

If you do want to work with the original image, I can't really help you further than dmatter already did. I imagine that once you hit an image pixel, you'll have to swarm out from it in all directions in order to determine the entire set of pixels that make up that separate image. You can then determine the minimum and maximum x and y values in that set, and that's your axis-aligned minimum bounding rectangle for that image. I'm not sure if there's any name for such an algorithm or how an optimized implementation looks like. However, since it's for an offline tool, neither memory nor cpu restrictions are really a problem, so you can just implement something that works.

Quote:Yes, I'm ok with non-trivial reasoning of how it _could_ be done, but I'm wondering if there is already an algorithm that does it, what's the name of it, where can I read about it?, etc.

Flood fill.

1) Iterate over image.
2a) If pixel != background_color, perform flood fill by replacing every pixel with background_color
2b) If result of flood fill is rectangle, you've found a sprite
3) continue iteration at 1)

Note that 2b) can be strict or relaxed, so it finds non-rectangular sprites as well.

Thanks! I implemented a boundary fill and it works great, the only problem is that it's recursive and I'm getting the stack to overflow quite easily / randomly as well, any ideas?

I could implement my own stack but... I'd still need a huge one for most of my images, any other way of doing a boundary fill?

Perhaps with 4 loops? or 1 loop and 4 sets of x,y coordinates?