Crate etagere

Dynamic texture atlas allocation using the shelf packing algorithm.

Texture atlas allocation

The goal of a texture atlas allocator is to pack multiple rectangles into a larger one. When rendering 2D or 3D graphics on the GPU, this packing important for draw call batching.

This crate provides two implementations of the shelf packing algorithm for dynamic texture atlas allocation (dynamic here means supporting both allocation and deallocation).

A thousand ways to pack the bin is a good resource to learn about rectangle packing algorithms, although it does not not cover deallocation which complicates the problem space a fair bit.

The shelf packing algorithm is explained in the above document. It isn't the most efficient packing strategy, however its simplicity makes it possible to support reasonably fast deallocation. Note that the guillotiere crate implements a similar API using the guillotine packing algorithm and may or may not provide better results depending on the type of workload.

Two allocators

• AtlasAllocator Tracks allocations for each individual item and does a reasonable job of dealing with fragmentation, at a runtime cost.
• BucketedAtlasAllocator groups items by buckets and only reclaim the space occupied by a bucket when all of its items are deallocated. In addition, it has limited support for merging consecutive empty shelves. These limitations allow faster allocation and deallocation, making it an appealing option when the atlas is expected to hold a very large amount of small items.

Both allocators support:

• Requiring an alignment for the items.
• Packing into vertical shelves instead of horizontal ones (might provide a better output for some workloads).
• Splitting the allocator into multiple columns in order to make shelves smaller and allow more of them.
• Dumping the content of the atlas in SVG format for easy debugging.

See AllocatorOptions

In addition, this repository contains a command-line application to experiment with and test the implementations interactively.

Example

use etagere::*;

let mut atlas = AtlasAllocator::new(size2(1000, 1000));

let a = atlas.allocate(size2(100, 100)).unwrap();
let b = atlas.allocate(size2(900, 200)).unwrap();
println!("Allocated {:?} and {:?}", a.rectangle, b.rectangle);

atlas.deallocate(a.id);

let c = atlas.allocate(size2(300, 200)).unwrap();

atlas.deallocate(c.id);
atlas.deallocate(b.id);

License

Licensed under either of

• Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

Re-exports

pub extern crate euclid;

Structs

AllocId	ID referring to an allocated rectangle.
Allocation	The AllocId and Rectangle resulting from an allocation.
AllocatorOptions	Options to tweak the behavior of the atlas allocator.
AtlasAllocator	A shelf-packing dynamic texture atlas allocator tracking each allocation individually and with support for coalescing empty shelves.
BucketedAtlasAllocator	A faster but less precise Shelf-packing dynamic texture atlas allocator, inspired by https://github.com/mapbox/shelf-pack/

Constants

DEFAULT_OPTIONS

Functions

point2	Shorthand for Point2D::new(x, y).
size2	Shorthand for Size2D::new(w, h).

Type Definitions

Point
Rectangle
Size