# How to automatically detect and crop individual sprite bounds in sprite sheet?

## Issue

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?

## Solution

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.