Sign in to follow this  
gusso

Unity Finding objects in image

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
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
Quote:
Original post by gusso
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?


Flood fill article explains non-recursive versions. They are applicable to boundary fill as well.

Share this post


Link to post
Share on other sites
Yes, but they use a "queue"... I tried to implement it and I'm getting errors due to the queue array getting out of bounds; it's pretty much the same deal as if I were using the recursive version and running out of stack space!

Any ideas on a more efficient algorithm?, I don't need speed but it has to be memory efficient and not a PITA to implement, perhaps I'm asking for too much :p

It's just that with simple images it runs fine but when I get to bigger images with tons of areas to fill, it just gets out of bounds or it runs out of stack, depending on the routine I choose.


Share this post


Link to post
Share on other sites
You may want to divide larger images into smaller chunks first and process them one by one, then linking up the results afterwards.

As for queue array getting out of bounds, I assume you're allocating a static array beforehand? Why not allocate as much space as you need, based on the size of the image, or are we talking about really huge images here?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

  • Announcements

  • Forum Statistics

    • Total Topics
      628350
    • Total Posts
      2982211
  • Similar Content

    • By koto
      Hello,

      I'm developing a roguelike game. Currently it's in a playable state and I think it's a high time to show it and hopefully get some feedback.

      The game has following features:
      - turn based
      - procedurally generated levels
      - tons of loot
      - spells system
      - trading system
      - some quests
      - some limited crafting
      - door/key/lever mechanics
      - quite a lot of different (look/behaviour) monsters

      Trailer:
      Demo: http://kotogames.com/wp-content/uploads/2017/11/OuaD_demo.zip
      Regards,
      Tom
       
    • By Afambus
      Hello,
      I have a full experienced team that looking for a composer and another 3d designer, im expecting as much from you there are other people in this server that can help you we have a determined team, we have done many things in our game there is more information in the discord about everyone and there skills there region and about the game, if you join the discord pm asap
      https://discord.gg/b2teN3m
    • By BAG Labs
      Mobile SoS

      Platform: Android
      Genre: Board
      Link: Google Play
       
      This games sharpen memory and test your strategies to place S-O-S pattern within time limit and serve 3 difficulties as Easy, Normal, and Hard.

      Goals of the game is to put S-O-S words in patterns (Horizontal, Vertical, and Diagonal) alternately with enemy.
       
      Features:
      Single Player Multiplayer Achievements Leaderboards  
       
      Screenshot:

       

       

       
      Link: Google Play
       
      Please help us improve this game with review
    • By abarnes
      Hello!
      I am a game development student in my second year of a three year program and I would like to start building my portfolio. I was thinking of creating some games to show what I can do to potential employers since I wont have any work related experience when I graduate. But as I'm sure you all know there are tons of ways to approach developing/designing a game and I'm curious if anyone had any insight as to any "standards" that come with this? Is it okay to use game engines like Unity, Unreal, Game Maker etc? Or would it be better to make a game from scratch to better show case your skills? Any and all advice will be greatly appreciated!
    • By Hilster
      Hello 2D Artists,
      I've started making a 2D Puzzle Adventure game for mobile and I'm looking for someone who would want in on creating assets for the game. The core of the programming is pretty much complete, you can walk within the grid laid out and push boxes, when there is an object on top of a pressure pad it will activate the linked objects or if there is one object with multiple linked pressure pads it requires you to activate all points for the object to become active. 

      The level iteration for the game is quick and simple, a Photoshop file that is made of individual pixels that represents objects is put into the game and it creates the level out of those pixels with the assigned objects.
      The objects that need sprites created so far is the character, box, pressure pad, door, trap door, the walls, the stairs and the tiled background.
      I intend to add more objects so the amount I'd like to add will be extended.
      My motivations for posting here is to have something that looks nice to be able to display on my portfolio, so if you're looking for a working game that you can place your art into and improve the look of your portfolio then we're in business.
      Please reply with a few past examples of your art below and I'll be in touch!
  • Popular Now