Jump to content
  • Advertisement
Sign in to follow this  
gusso

Unity Finding objects in image

This topic is 3631 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Quote:
Original post by gusso
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.
I think the artist actually creates sprites individually, their 'huge canvas' is just a directory of images. Those images are packed together using a utility program.

If you do have a huge 'loose' canvas of images then you need to be able to find the tightest bounding area for each image. This is a non-trivial process unless there are restraints added, such as if all images are axially aligned and may be approximated by a rectangle. Working on those assumptions you would have to iterate through all the pixels in the image then when you hit one that isn't a background value (or a previously encountered image) you know you have a new image that you need to find the min and max regions of it's bounding rectangle which should be quite easy.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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).


Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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?


Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!