Continuing my efforts to improve sprite handling, I’ve implemented a very simple sprite packing algorithm to make better use of the ‘uniform-grid-of-square-images’ sprite atlas class I used to batch the sprite frame images for a single entity class together.
Sprite atlases, revisited
As a refresher, here’s a nice explanation on what a texture atlas (which I will refer to as a ‘sprite atlas’, because that’s just the way I’ve called my atlas class ;-) actually is, and why you’d want to use it. I could of course write a lengthy treatise on sprite atlases myself, but I’d much rather spend that time implementing or using one, so if you want know more, just read the linked article or Google around a bit. The executive summary is that a sprite atlas is basically one big image composed of many different sprite frame images, that can be used as a single texture when rendering, instead of having to create separate small textures for each individual sprite frame. It’s faster, you’ll use less memory, and it can simplify your rendering code since you don’t have to switch between sprite textures all the time or batch your sprites by their current sprite frame or whatever.
Creating a sprite atlas basically comes down to packing the sprite frame images into a rectangular area (the texture atlas) as efficiently as possible. The orientation or position of the image within the texture atlas can be chosen freely (as long as the images fit the texture rectangle, obviously), so sprite frame images may be rotated before packing if this would allow a better packing. Normalized texture coordinates (from 0.0 to 1.0) are calculated for each packed sprite image, which indicate the rectangular area of the texture to use when rendering the sprite frame.
Packing rectangles is an NP-hard combinatorial problem, which means there are no algorithms that can calculate an optimal packing in reasonable (polynomial) time for large input sets (numbers of sprite frames). In practice, this means a trade-off has to be made between packing efficiency (reducing the amount of ‘wasted’ texture space), runtime, and algorithmic complexity (implementation effort). I didn’t set out to create the most efficient, most flexible sprite packer in existence, so for my purpose algorithmic complexity was a relatively important consideration.
Instead of trying to re-invent the wheel, I searched the internet for rectangle packing algorithms, and found this excellent survey of common packing algorithms, which describes packing strategies ranging from extremely naive to elaborate and complex. Various permutations of improvements to the various algorithm are benchmarked for packing efficiency and runtime, which allows for a more-or-less ‘a la carte’ selection of packing algorithm. Based on my performance and implementation effort considerations (reasonable performance, small implementation effort), I picked a variant of a packing algorithm commonly referred to as ‘Guillotine Packing’, which iteratively subdivides the free space of the packing rectangle by splitting it either horizontally or vertically after packing each sprite frame. Besides some kind of heuristic to decide whether to split the free space horizontally or vertically, there are a number of things that affect and improve packing efficiency, such as sorting the sprite frames on their sizes before packing, and merging free rectangles when possible.
My implementation uses a best-area-fit strategy with rectangle merging, and sorts the sprite frame images from largest to smallest area before packing. For a complete description of the algorithm, see section 2.2.1 (Guillotine-Best-Area-Fit) of the linked PDF. The packer currently only supports a single bin, which means it can only output a single texture, and will fail if the set of sprite frame images can not be packed within a single texture of the supplied maximum texture size. In the future, some form of ‘multiple bins with spill-over’ may be required in case the number of sprite frames used for a single planet grows.
Packing results
To make better use of my sprite packer, I adapted the renderer to use a single
sprite atlas containing the sprite frames for all entity types. Before, a
separate sprite atlas was made for each entity type, which doesn’t make much
sense since most entities currently have only a single sprite (only the
K14Ship entity has three). In the future, this could change if some entities
get more different sprite frames, but for now it simplifies the rendering code
as all sprite rendering can be done using the same texture.
The image below shows the texture atlas containing all sprite images for a single planet that uses all current entity types. The packing of the sprites is straightforward for this cause, but it’s reasonably efficient (not much texture space is wasted) and the fact that the packing is done at runtime and should work equally well for other combinations of similarly-sized sprite frames is very convenient. Memory consumption is also reduced compared to the ‘one texture atlas per entity type’ approach I used before, the memory footprint while running ‘planet 1’, which includes all entity types, is about 10 MB (30%) lower.
Other improvements
To liven up the game visuals a little, I re-exported colored versions of
all game sprites, and I added a tint property to K14Planet that determines
the planet surface color. Eventually I’d like to do something smarter with
sprite coloring instead of hard-coding sprite colors in the sprite frame
images, which is inflexible and doesn’t look good when the colors don’t mix
well with the color of the planet surface. A better way to allow configurable
per-planet color palettes would be some form of indexed color rendering,
which could be implemented by replacing sprite colors from inside the fragment
shader.
Not quite a video
Instead of a video, here’s a quick screenshot of the latest version, which shows the colored sprites and planet surface. I’ll be the first to admit the colors aren’t exactly pretty, but this only serves as a work-in-progress example.
Next steps
I think the next thing I to work on should be the scoreboard overlay, which requires some form of text rendering. Text rendering in OpenGL is a pain, because the API itself is basically devoid of anything useful related to text, so you’re stuck with creating bitmaps from you fonts and rendering text using polygons. Fortunately, I have a nice texture atlas and sprite packer now, so most of the work is already done ;-)
Development scoreboard
Total development time for the features discussed above was about 5 hours, which brings total development time to around 152 hours. The texture atlas implementation increased the SLOC count by 136 to a total of 1886.