• Advertisement
Sign in to follow this  

Unity Finding objects in image

This topic is 3422 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
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
Sign in to follow this  

  • Advertisement
  • Advertisement
  • Popular Tags

  • Advertisement
  • Popular Now

  • Similar Content

    • By Innoc uous
      I'm working on a space game, and I suck at art. I would love to get some help from someone who is more skilled than me. Things I need include modular space ship parts and GUI elements. Nothing too fancy, just functional so I can get a prototype put together. This could potentially become a serious project, but for now this is just a hobby project.
       
      In this video, you can see a few things I already completed
      :2018-02-24 20-08-13.flv2018-02-24 20-08-13.flv
    • By Innoc uous
      If you want to incorporate noise into your shaders, the Turbulance Library has you covered. Using code I gathered from this library, I made a cginc file that contains all you need to easily implement noise into your unity shaders. Who knows how this stuff works, but man, does it work well!
       
      https://pastebin.com/LLCUpJut
       
      Here is an example of what you can create using these noise functions.
       
    • By Nio Martinez
      I'll be buying a new laptop as my workstation for building games, Mostly 3D but not hard core. 
       
      I'm stuck at choosing between these 2 specs below. Does this really matter and if so, can some one tell my how and why it matters. 
      Choice1:
      Intel core i5-8250U (8th gen Kabylake refresh)(6 MB Smart Cache, 1.6 GHz Base with Turbo Boost up to 3.4 GHz) 4 cores 8 threads
      RAM 8 GB DDR4 (2400 MHz)
      GPU 2 GB DDR5 Nvidia MX150 256 bit
      SSD: yes
      Choice2:
      Intel core i7-7500U 2.70GHz Base Processor (4M Cache, up to 3.50 GHz Boost) 2 Cores, 4 Threads
      RAM 4 GB DDR4 (1800 MHz)
      GPU 2 GB DDR5 Nvidia GeForce 940MX 256 bit
      SSD: No
       
    • By Manuel Berger
      Hello fellow devs!
      Once again I started working on an 2D adventure game and right now I'm doing the character-movement/animation. I'm not a big math guy and I was happy about my solution, but soon I realized that it's flawed.
      My player has 5 walking-animations, mirrored for the left side: up, upright, right, downright, down. With the atan2 function I get the angle between player and destination. To get an index from 0 to 4, I divide PI by 5 and see how many times it goes into the player-destination angle.

      In Pseudo-Code:
      angle = atan2(destination.x - player.x, destination.y - player.y) //swapped y and x to get mirrored angle around the y axis
      index = (int) (angle / (PI / 5));
      PlayAnimation(index); //0 = up, 1 = up_right, 2 = right, 3 = down_right, 4 = down

      Besides the fact that when angle is equal to PI it produces an index of 5, this works like a charm. Or at least I thought so at first. When I tested it, I realized that the up and down animation is playing more often than the others, which is pretty logical, since they have double the angle.

      What I'm trying to achieve is something like this, but with equal angles, so that up and down has the same range as all other directions.

      I can't get my head around it. Any suggestions? Is the whole approach doomed?

      Thank you in advance for any input!
       
    • By devbyskc
      Hi Everyone,
      Like most here, I'm a newbie but have been dabbling with game development for a few years. I am currently working full-time overseas and learning the craft in my spare time. It's been a long but highly rewarding adventure. Much of my time has been spent working through tutorials. In all of them, as well as my own attempts at development, I used the audio files supplied by the tutorial author, or obtained from one of the numerous sites online. I am working solo, and will be for a while, so I don't want to get too wrapped up with any one skill set. Regarding audio, the files I've found and used are good for what I was doing at the time. However I would now like to try my hand at customizing the audio more. My game engine of choice is Unity and it has an audio mixer built in that I have experimented with following their tutorials. I have obtained a great book called Game Audio Development with Unity 5.x that I am working through. Half way through the book it introduces using FMOD to supplement the Unity Audio Mixer. Later in the book, the author introduces Reaper (a very popular DAW) as an external program to compose and mix music to be integrated with Unity. I did some research on DAWs and quickly became overwhelmed. Much of what I found was geared toward professional sound engineers and sound designers. I am in no way trying or even thinking about getting to that level. All I want to be able to do is take a music file, and tweak it some to get the sound I want for my game. I've played with Audacity as well, but it didn't seem to fit the bill. So that is why I am looking at a better quality DAW. Since being solo, I am also under a budget contraint. So of all the DAW software out there, I am considering Reaper or Presonus Studio One due to their pricing. My question is, is investing the time to learn about using a DAW to tweak a sound file worth it? Are there any solo developers currently using a DAW as part of their overall workflow? If so, which one? I've also come across Fabric which is a Unity plug-in that enhances the built-in audio mixer. Would that be a better alternative?
      I know this is long, and maybe I haven't communicated well in trying to be brief. But any advice from the gurus/vets would be greatly appreciated. I've leaned so much and had a lot of fun in the process. BTW, I am also a senior citizen (I cut my programming teeth back using punch cards and Structured Basic when it first came out). If anyone needs more clarification of what I am trying to accomplish please let me know.  Thanks in advance for any assistance/advice.
  • Advertisement