Faster Sprite Rendering Through Texture Packing


Last week, I talked about measuring performance. Now, I can tell you why.

Before doing any sort of performance optimization, it’s important to have an accurate benchmark so you can make sure your optimization actually works. Now that I have my measurement system ready, I can talk about optimizing performance. The optimization for this week is speeding up sprite batch rendering by packing your images into one texture.

App Hub has a good sample illustrating how you can import multiple images into the XNA content pipeline and pack them into a single texture at build-time. I decided to take a slightly different approach by writing code that would pack multiple Texture2Ds together at runtime.

Why would I go out of my way to do texture packing at runtime instead as an offline build process? Well, packing textures at build time is great when you have a static list of assets you know you’ll need for a given scenario. In cases where you don’t know exactly what will need to be loaded at runtime, build-time texture packing won’t really help you. Consider a scenario where players can mix-and-match what their characters wear in-game. In this case, with runtime packing, you can generate a sprite sheet of just the images for the equipment that a character is using and have the performance benefit of fewer texture switches without loading unnecessary data.

So, on to the code. First, I begin with the heightmap renderer from a previous article. Now, this renderer is particularly inefficient because it simply draws all heightmap tiles regardless of whether or not they’re on screen. It will do however in illustrating performance changes when rendering large numbers of sprites. Also, I modified the renderer to use a few more texture patterns than before to further exacerbate the performance cost of texture switching. Running it on my MacBook Pro bootcamped into Windows 7, I get the following frame drawtime:

~5.1 ms to draw a frame. Not great.

So, now I take the tile textures and, instead of using them as loaded, I pass them through my texture packing function to generate a packed texture and a list of coordinates into the texture for each sprite.

public struct TileSprite
{
	public Texture2D Texture;
	public Rectangle? SourceRect;

	public TileSprite(Texture2D _texture, Rectangle? _sourceRect)
	{
		Texture = _texture;
		SourceRect = _sourceRect;
	}
}

protected override void LoadContent()
{
	base.LoadContent();

	//Standard sprite loading
	/*_midTile = new TileSprite(Game.Content.Load<Texture2D>("Texture/PlanetCute/Grass Block"), null);
	_lowTile = new TileSprite(Game.Content.Load<Texture2D>("Texture/PlanetCute/Water Block"), null);	
	_highTile = new TileSprite(Game.Content.Load<Texture2D>("Texture/PlanetCute/Dirt Block"), null);
	_midHighTile = new TileSprite(Game.Content.Load<Texture2D>("Texture/PlanetCute/Plain Block"), null);
	_midLowTile = new TileSprite(Game.Content.Load<Texture2D>("Texture/PlanetCute/Brown Block"), null);*/

	//Texture atlas sprite loading
	List<Texture2D> textures = new List<Texture2D>();
	textures.Add(Game.Content.Load<Texture2D>("Texture/PlanetCute/Grass Block"));
	textures.Add(Game.Content.Load<Texture2D>("Texture/PlanetCute/Water Block"));
	textures.Add(Game.Content.Load<Texture2D>("Texture/PlanetCute/Dirt Block"));
	textures.Add(Game.Content.Load<Texture2D>("Texture/PlanetCute/Plain Block"));
	textures.Add(Game.Content.Load<Texture2D>("Texture/PlanetCute/Brown Block"));
	List<Rectangle> spriteRects = new List<Rectangle>();
	Texture2D packedTexture = TexturePacker.PackSprites(Game.GraphicsDevice, textures, spriteRects);

	_midTile = new TileSprite(packedTexture, spriteRects[0]);
	_lowTile = new TileSprite(packedTexture, spriteRects[1]);
	_highTile = new TileSprite(packedTexture, spriteRects[2]);
	_midHighTile = new TileSprite(packedTexture, spriteRects[3]);
	_midLowTile = new TileSprite(packedTexture, spriteRects[4]);
}

With the packed texture loading in place, I run the program again to see the results.

Ah, that’s just what I wanted to see. Same image, but running ~1.5 ms faster.

You can grab the code for the runtime texture packer (which I based heavily on the aforementioned App Hub sample) here:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;

namespace ProceduralWorldLib
{
    public static class TexturePacker
    {
        /// <summary>
        /// Internal helper class keeps track of a sprite while it is being arranged.
        /// </summary>
        class ArrangedSprite
        {
            public int Index;

            public int X;
            public int Y;

            public int Width;
            public int Height;
        }

        public static Texture2D PackSprites(GraphicsDevice graphics, IList<Texture2D> sourceSprites,
                                                ICollection<Rectangle> outputSprites)
        {
            // Build up a list of all the sprites needing to be arranged.
            List<ArrangedSprite> sprites = new List<ArrangedSprite>();

            for (int i = 0; i < sourceSprites.Count; i++)
            {
                ArrangedSprite sprite = new ArrangedSprite();

                // Include a single pixel padding around each sprite, to avoid
                // filtering problems if the sprite is scaled or rotated.
                sprite.Width = sourceSprites[i].Width + 2;
                sprite.Height = sourceSprites[i].Height + 2;

                sprite.Index = i;

                sprites.Add(sprite);
            }

            // Sort so the largest sprites get arranged first.
            sprites.Sort(CompareSpriteSizes);

            // Work out how big the output bitmap should be.
            int outputWidth = GuessOutputWidth(sprites);
            int outputHeight = 0;
            int totalSpriteSize = 0;

            // Choose positions for each sprite, one at a time.
            for (int i = 0; i < sprites.Count; i++)
            {
                PositionSprite(sprites, i, outputWidth);

                outputHeight = Math.Max(outputHeight, sprites[i].Y + sprites[i].Height);

                totalSpriteSize += sprites[i].Width * sprites[i].Height;
            }

            // Sort the sprites back into index order.
            sprites.Sort(CompareSpriteIndices);

            return CopySpritesToOutput(graphics, sprites, sourceSprites, outputSprites,
                                       outputWidth, outputHeight);
        }

        /// <summary>
        /// Once the arranging is complete, copies the bitmap data for each
        /// sprite to its chosen position in the single larger output bitmap.
        /// </summary>
        static Texture2D CopySpritesToOutput(GraphicsDevice graphics, 
                                                List<ArrangedSprite> sprites,
                                                 IList<Texture2D> sourceSprites,
                                                 ICollection<Rectangle> outputSprites,
                                                 int width, int height)
        {
            SpriteBatch spriteBatch = new SpriteBatch(graphics);

            RenderTarget2D renderTarget = new RenderTarget2D(graphics, width, height);
            graphics.SetRenderTarget(renderTarget);
            graphics.Clear(Color.Transparent);

            spriteBatch.Begin();
            foreach (ArrangedSprite sprite in sprites)
            {
                int x = sprite.X;
                int y = sprite.Y;

                int w = sourceSprites[sprite.Index].Width;
                int h = sourceSprites[sprite.Index].Height;

                spriteBatch.Draw(sourceSprites[sprite.Index], new Vector2(x + 1, y + 1), Color.White);

                // Copy a border strip from each edge of the sprite, creating
                // a one pixel padding area to avoid filtering problems if the
                // sprite is scaled or rotated.
                spriteBatch.Draw(sourceSprites[sprite.Index], new Rectangle(x, y + 1, 1, h), new Rectangle(0, 0, 1, h), Color.White);
                spriteBatch.Draw(sourceSprites[sprite.Index], new Rectangle(x + w + 1, y + 1, 1, h), new Rectangle(w - 1, 0, 1, h), Color.White);
                spriteBatch.Draw(sourceSprites[sprite.Index], new Rectangle(x + 1, y, w, 1), new Rectangle(0, 0, w, 1), Color.White);
                spriteBatch.Draw(sourceSprites[sprite.Index], new Rectangle(x + 1, y + h + 1, w, 1), new Rectangle(0, h - 1, w, 1), Color.White);

                // Copy a single pixel from each corner of the sprite,
                // filling in the corners of the one pixel padding area.
                spriteBatch.Draw(sourceSprites[sprite.Index], new Rectangle(x, y, 1, 1), new Rectangle(0, 0, 1, 1), Color.White);
                spriteBatch.Draw(sourceSprites[sprite.Index], new Rectangle(x + w + 1, y, 1, 1), new Rectangle(w - 1, 0, 1, 1), Color.White);
                spriteBatch.Draw(sourceSprites[sprite.Index], new Rectangle(x, y + h + 1, 1, 1), new Rectangle(0, h - 1, 1, 1), Color.White);
                spriteBatch.Draw(sourceSprites[sprite.Index], new Rectangle(x + w + 1, y + h + 1, 1, 1), new Rectangle(w - 1, h - 1, 1, 1), Color.White);

                outputSprites.Add(new Rectangle(x + 1, y + 1, w, h));
            }
            spriteBatch.End();

            graphics.SetRenderTarget(null);
            return renderTarget;
        }

        /// <summary>
        /// Works out where to position a single sprite.
        /// </summary>
        static void PositionSprite(List<ArrangedSprite> sprites,
                                   int index, int outputWidth)
        {
            int x = 0;
            int y = 0;

            while (true)
            {
                // Is this position free for us to use?
                int intersects = FindIntersectingSprite(sprites, index, x, y);

                if (intersects < 0)
                {
                    sprites[index].X = x;
                    sprites[index].Y = y;

                    return;
                }

                // Skip past the existing sprite that we collided with.
                x = sprites[intersects].X + sprites[intersects].Width;

                // If we ran out of room to move to the right,
                // try the next line down instead.
                if (x + sprites[index].Width > outputWidth)
                {
                    x = 0;
                    y++;
                }
            }
        }


        /// <summary>
        /// Checks if a proposed sprite position collides with anything
        /// that we already arranged.
        /// </summary>
        static int FindIntersectingSprite(List<ArrangedSprite> sprites,
                                          int index, int x, int y)
        {
            int w = sprites[index].Width;
            int h = sprites[index].Height;

            for (int i = 0; i < index; i++)
            {
                if (sprites[i].X >= x + w)
                    continue;

                if (sprites[i].X + sprites[i].Width <= x)
                    continue;

                if (sprites[i].Y >= y + h)
                    continue;

                if (sprites[i].Y + sprites[i].Height <= y)
                    continue;

                return i;
            }

            return -1;
        }

        /// <summary>
        /// Comparison function for sorting sprites by size.
        /// </summary>
        static int CompareSpriteSizes(ArrangedSprite a, ArrangedSprite b)
        {
            int aSize = a.Height * 1024 + a.Width;
            int bSize = b.Height * 1024 + b.Width;

            return bSize.CompareTo(aSize);
        }

        /// <summary>
        /// Comparison function for sorting sprites by their original indices.
        /// </summary>
        static int CompareSpriteIndices(ArrangedSprite a, ArrangedSprite b)
        {
            return a.Index.CompareTo(b.Index);
        }


        /// <summary>
        /// Heuristic guesses what might be a good output width for a list of sprites.
        /// </summary>
        static int GuessOutputWidth(List<ArrangedSprite> sprites)
        {
            // Gather the widths of all our sprites into a temporary list.
            List<int> widths = new List<int>();

            foreach (ArrangedSprite sprite in sprites)
            {
                widths.Add(sprite.Width);
            }

            // Sort the widths into ascending order.
            widths.Sort();

            // Extract the maximum and median widths.
            int maxWidth = widths[widths.Count - 1];
            int medianWidth = widths[widths.Count / 2];

            // Heuristic assumes an NxN grid of median sized sprites.
            int width = medianWidth * (int)Math.Round(Math.Sqrt(sprites.Count));

            // Make sure we never choose anything smaller than our largest sprite.
            return Math.Max(width, maxWidth);
        }
    }
}
Share this Article:
  • Digg
  • StumbleUpon
  • del.icio.us
  • Facebook
  • Yahoo! Buzz
  • Twitter
  • Google Bookmarks
  • Print

2 thoughts on “Faster Sprite Rendering Through Texture Packing

  1. Pingback: Spatial Indexing for Fun and Performance | Game Dev Without a Cause

  2. Pingback: Spritesheets, Spritesheets Everywhere | Game Dev Without a Cause

Comments are closed.