Sprite Atlas

A sprite atlas is a collection of sprites that are stored in a single image which becomes a single texture when rendering using OpenGL.

By storing many sprites in one texture we gain significant performance benefits as switching textures is a costly operation. We saw how we can render sprites out of a sprite atlas in the animation tutorial but we did so in an ad-hoc way for illustration purposes. Sprite atlases are central to our 2D engine so here we will define a proper data structure for them. This is the atlas definition in AGL:

type Atlas struct {
    atlasImage          *image.RGBA
    coverageImage       *image.Gray
    spriteBoundingBoxes []math.Box2D[int]
    atlasTexture        uint32 // OpenGL texture of Atlas
}

Lets go over the fields. Field atlasImage is the atlas image in CPU space, loaded from disk using Go’s image package. Field spriteBoundingBoxes is a list of bounding boxes given as a pair of points (lower-left and upper right). For reference, here is what a Box2D looks like.

type Box2D struct {
    P1, P2 Vector2[int]
}

These bounding boxes correspond to the location of sprites on the image.

In this example the image is $48\times32$. The sprite in the blue border will have an entry in spriteBoundingBoxes with the values P1:{0,0}, P2:{16,16}. The sprite in the green border will have P1:{32,16}, P2:{48,32}. These values are useful to create uv (texture) coordinates for rendering.

Field atlasTexture is the OpenGL texture that stores atlasImage. We keep the OpenGL texture here so that we can update it when we update atlasImage. The final field, coverageImage is a helper image used when adding sprites to the atlas (more on that in a bit).

Loading a Pre-built Atlas

There are two ways to build an atlas. The simplest (code-wise) is to create the atlas image in an external program and then load it into the Atlas struct. In code¹ this looks like this:

func NewAtlas(atlasImage *image.RGBA, spriteBoundingBoxes []math.Box2D[int]) *Atlas {
    st := Atlas{
        atlasImage:          atlasImage,
        spriteBoundingBoxes: spriteBoundingBoxes,
    }
    var err error
    st.atlasTexturetextureFromRGBA(st.atlasImage)
    return &st
}

The code simply loads the required data into the struct and then builds the OpenGL texture using textureFromRGBA which we have used before. If we are loading the atlas from disk, the bounding boxes are given in JSON form:

func NewAtlasFromFiles(atlasImage, spriteBoundingBoxes string) *Atlas {
    bboxes := []math.Box2D[int]{}
    dat,_ := ioutil.ReadFile(spriteBoundingBoxes)
    json.Unmarshal(dat, bboxes)
    img,_ := RgbaFromFile(atlasImage)
    return NewAtlas(img, bboxes)
}

This process relies on us having an external program that packs sprites into an image and keeps track of sprite bounding boxes in the format that our program requires. There are various programs for creating sprite sheets, such as Libresprite, which does export sprite bounding boxes in JSON format. Although its format doesn’t match ours, writing a converter wouldn’t take more than a few lines of code.

Creating the Atlas Automatically

The other way to build the atlas is to load each sprite one by one. This is desirable if the user has a collection of images that they want to use as sprites but they haven’t arranged them in a sprite atlas. We can create the atlas automatically with a little bit of bookkeeping.

First lets see how to create an empty atlas using our constructor:

NewAtlas(image.NewRGBA(image.Rect(0, 0, 1024, 1024)), nil)

This allocates space for an empty $1024 \times 1024$ atlas. We can then copy images into the atlas using Go’s draw package:

rect := image.Rectangle{p1, p2}
draw.Draw(atlasImage, rect, img, image.Point{}, draw.Src)

This would copy img into our atlasImage at the image location given by the rectangle rect which specifies a bounding box like our own math.Box2D. We then need a way to find empty spots on the atlas where we can place our new sprites. This is where the auxiliary coverageImage comes in. This is a black and white image where where black pixels signify empty space and white pixels signify that the space is taken by a sprite. To find a place we iterate over all pixels in the coverage until we find a black pixel.

for y := 0; y < s.coverageImage.Bounds().Max.Y; y++ {
    for x := 0; x < s.coverageImage.Bounds().Max.X; x++ {
        if s.coverageImage.At(x, y) == white {
            continue
        }
        // found empty pixel at (x,y)
    }
}

When we find an empty pixel we need to check that there is enough space to fit the sprite we are inserting. We could do that by checking each pixel starting from (x,y) and spanning the size of the sprite we are about to insert (x+sprite.width, y+sprite.height). If all pixels in that region are black (empty) then we are good to place our sprite there. If any pixel is white we can’t and need to move forward to check other pixels. Alternatively, we can check the bounding boxes in our atlas. If none of our bounding boxes overlaps the box given by the points (x,y) and (x+sprite.width, y+sprite.height) we are free to place our sprites there. Both approaches are valid. Checking pixel by pixel is better if the inserted sprite has less pixels than the number of bounding boxes in the atlas. If sprites are large and the number of bounding boxes small, checking the bounding boxes is faster. In AGL we chose to use the second approach.

func (s *Atlas) checkCoverageSpot(x, y, w, h int) bool {
    box := math.Box2D[int]{}.New(x, y, x+w, y+h)
    for _, b := range s.spriteBoundingBoxes {
        if b.Overlaps(box) {
            return false
        }
    }
    return true
}

Checking if two boxes overlap is done with this piece of code. Take a moment (and possibly a pen and paper) to check this code’s correctness.

func (b Box2D) Overlaps(other Box2D) bool {
    return b.P1.X < other.P2.X &&
        b.P2.X > other.P1.X &&
        b.P1.Y < other.P2.Y &&
        b.P2.Y > other.P1.Y
}

With this, the complete code for finding an empty spot becomes:

p1 := image.Point{-1, -1}

for y := 0; y < s.coverageImage.Bounds().Max.Y; y++ {
    done := false
    for x := 0; x < s.coverageImage.Bounds().Max.X; x++ {
        if s.coverageImage.At(x, y) == white {
            continue
        }
        if s.checkCoverageSpot(x, y, img.Bounds().Dx(), img.Bounds().Dy()) {
            p1 = image.Point{x, y}
            done = true
            break
        }
    }
    if done {
        break
    }
}

Once we find a spot we copy (draw) the sprite to the atlas.

p2 := p1.Add(spriteToAdd.Rect.Max) 
rect := image.Rectangle{p1, p2} // bounding box of sprite
draw.Draw(s.atlasImage, rect, spriteToAdd, image.Point{}, draw.Src)

We also update the coverage image, painting the spot where we added the sprite white so the next insertion will know not to place anything there.

draw.Draw(s.coverageImage, rect, image.NewUniform(white), image.Point{}, draw.Src)

Finally, we create an entry for the bounding box of the newly added sprite.

s.spriteBoundingBoxes = append(s.spriteBoundingBoxes, math.Box2D[int]{
    P1: math.Vector2[int]{p1.X, p1.Y}, P2: math.Vector2[int]{p2.X, p2.Y},
})
s.UpdateGPUAtlas()

We also update the OpenGL texture so we are ready to render the new sprite. This is not ideal, as updating the texture is costly and the user is likely to add a bunch of sprites in a row (e.g when loading a folder full of sprites into the atlas) in which case we would only want to update the texture after the last sprite has been added. For this reason, in AGL we provide an AddImages function that does that.

An Example

Lets look at an example of how the process works. We have the following ‘sprites’ that we want to add in an empty atlas:

When we add the first sprite, our atlas and coverage images are empty so our search for an empty spot will stop at the first pixel of the atlas $(0,0)$ and the first sprite will be placed there. The coverage image is painted white to indicate where the sprite was placed.

For the next sprite, the search will skip the first row of white pixels and find an empty spot right next to the first sprite:

For the third sprite, the search will find an empty pixel next to the second sprite but the sprite we are adding doesn’t fit there. In the example code above we don’t test for this scenario but the AGL implementation does. As a result, the search will continue past the area occupied by sprite two.

The fourth sprite fits under sprite three.

And the final sprite fits next to sprite two. Notice that we start searching from pixel $(0,0)$ every time which allows us to reuse space that was previously discarded.

As you might imagine, the order that we add the sprites affects the outcome. Here are the same sprites added in another order:

The code used to create these images can be found here.

Optimized Packing

The order in which we add sprites will affects how tightly packed the atlas is. This might be important for saving space on the atlas, especially if we are storing larger sprites together with smaller ones. We can spend a good bit of time devising heuristics to achieve this², but a simple one is to sort the sprites by descending area:

For transparent sprites there exist more elaborate packing strategies that let sprites be placed inside other sprite’s bounding boxes (occupying the other sprite’s transparent regions). Even more gains can be achieved if we are willing to rotate sprites and segment them with complex polygons instead of boxes. Here is an example of TexturePacker’s³ polygon algorithm:

AGL only supports square sprites, which is what is used in most 2D games anyway. The simple packing approach described here gets us 90% of the performance with 10% of the effort required for implementing the more fancy packing methods out there.