Given a sprite sheet like this:
I would like to write an algorithm that can loop through the pixel data and determine the bounding rectangle of each discreet sprite.
If we assume that for each pixel X, Y that I can pull either true (pixel is not totally transparent) or false (pixel is totally transparent), how would I go about automatically generating the bounding rectangles for each sprite?
The resulting data should be an array of rectangle objects with {x, y, width, height}.
Here's the same image but with the bounds of the first four sprites marked in light blue:
Can anyone give a step-by-step on how to detect these bounds as described above?
How about this? The only downside is that you'll need a writable version of your image to mark visited pixels in, or the floodfill will never terminate.
Process each* scan line in turn
For each scanline, walk from left to right, until you find a non-transparent pixel P.
If the location of P is already inside a known bounded box
Continue to the right of the bounded box
Else
BBox = ExploreBoundedBox(P)
Add BBox to the collection of known bounded boxes
Function ExploreBoundedBox(pStart)
Q = new Queue(pStart)
B = new BoundingBox(pStart)
While Q is not empty
Dequeue the front element as P
Expand B to include P
For each of the four neighbouring pixels N
If N is not transparent and N is not marked
Mark N
Enqueue N at the back of Q
return B
You don't need to process every scanline, you could do every 10th, or every 30th scanline. As long as it doesn't exceed the minimum sprite height.