Alferd Spritesheet Unpacker. [Unpacking Algorithms]

During the end of 2011 I created a sprite sheet app called 'Alferd Spritesheet Unpacker' (you can download it here). It's a spriting tool which takes a single spritesheet bitmap and extracts each individual frame of animation and saves it as a new bitmap.

It looks like this:

I do get emails from users about the app from time to time, and I've had a few asking about the algorithm used in ASU to identify the frames. Rather than reply individually I thought I'd resurrect this blog and outline how it works.

Finding Boxes

1. Firstly ASU iterates over every pixel in the Spritesheet to determine the most frequent colour. This colour then becomes the 'Background colour'.
2. ASU then iterates over every pixel in the Spritesheet moving left to right, top to bottom. 
3. When ASU finds a pixel that is a different colour to the 'Background colour' it creates a box. Fig. 1 below shows a Dan Hibiki sprite you might find in a Spritesheet bitmap.
• The box's top left coordinate is the first non 'Background colour' pixel found during the previous step. 
• ASU then iterates left to right until it finds the next 'Background colour' pixel. The number of pixels iterated becomes the box width. 
• The height of the box is the number of pixels below the top left or top right of the box before we find a 'Background colour' pixel (whichever is greater).  Fig. 2 shows the first box found for this Sprite.
4. ASU then repeats step 2 with the newly created box's top right pixel as the current pixel, until all pixels have been iterated over. (Fig. 3 below shows the progress of ASU having created 4 boxes.)

Creating Frames

1. Once complete ASU now has a great collection of overlapping boxes (see fig. 4). ASU then calls a function which iterates over the collection of boxes until it finds two overlapping. When two overlapping are found they are both removed from the collection and replaced with a single box which covers the area of both. Once two boxes are 'combined' the function returns.
2. If the previous step resulted in two boxes being 'combined' then the function is called again (the net result is this function being called until no two boxes are overlapping).

Once this is complete ASU has a collection of boxes covering every individual frame as in fig. 5.

Some sprite sheets have frames without continuous pixels (fig. 6) so in order to cope with this the function which combines two overlapping boxes doesn't just look for actual overlaps but any boxes which are very close (fig. 7). The default is within three pixels (it can be changed via the 'Distance Between Frames' option).

And that's it. 

Except to say for a quick performance gain this process actually first splits the original spritesheet into smaller tiles. The above process is run against each tile. Once all the tiles have been processed the tiles are re-combined back into a single sheet, and then the 'overlapping' boxes function is run again to combine frames which span multiple tiles.

Disclaimer

I don't present this method as anything close to being optimal. This process is very greedy on resource. I am certain there are a thousand much quicker solutions, but I'm a big hater of Premature optimization. And I was happy with anything under a minute for the sprite sheets I use.