Tedd.RectanglePacker 0.1.7

Tedd.RectanglePacker

High-performance rectangle packer and texture-atlas builder for .NET 10 and .NET 11. In the published comparison benchmarks, it is the fastest rectangle packer on the measured size-search workloads; results depend on workload and hardware.

• Packing: MaxRects (best short side, long side, area, bottom-left, contact point) and Skyline (bottom-left, min-waste), with a parallel atlas-size search that finds a small atlas and returns the same result for any thread count.
• Inputs: raw pixel buffers (RawImage: width, height, format, stride, bytes) or Tedd.FIC images (FicImage).
• Outputs: a raw pixel buffer (RawImageBuffer) or a FIC container.
• Padding: optional per-sprite padding filled as Transparent, Extrude (clamp-to-edge), Mirror or Wrap, plus Spacing between sprites and BorderPadding around the atlas.
• Zero allocation: every buffer can be lent by the caller. You can compute the layout first and then compose straight into your own memory (a pooled array, GPU upload buffer, memory-mapped file, ...). Repeated calls on a reused AtlasBuilder allocate nothing, apart from what Tedd.FIC's encoder allocates internally.
• Fast writes: the atlas is written in destination scanline order, so each atlas byte is written once, left to right. Bands of rows are split across threads. A per-sprite block-copy strategy is also available.
• Pixel formats: Gray8, Rgb24, Bgr24, Rgba32, Bgra32, Argb32, Abgr32. Every input may use a different format; pixels are converted while they are written.

Install

dotnet add package Tedd.RectanglePacker

Quick start

using Tedd.RectanglePacker;

var builder = new AtlasBuilder(new AtlasOptions
{
    Padding = 2,                        // pixels around every sprite...
    PaddingMode = PaddingMode.Extrude,  // ...filled by repeating the edge (no bilinear bleeding)
    Spacing = 1,                        // transparent gap between padded sprites
});

RawImage[] sprites =
[
    new RawImage(64, 64, PixelFormat.Rgba32, rgbaBytes),
    new RawImage(32, 48, PixelFormat.Bgra32, bgraBytes, stride: 32 * 4 + 16),
];

RawAtlas atlas = builder.Build(sprites, PixelFormat.Rgba32);
// atlas.Image      -> RawImageBuffer (Width, Height, Format, Stride, Pixels)
// atlas.Layout     -> Width, Height, Rects (content rectangle of sprite i at index i)

Write directly into your own buffer

The size of the atlas is known as soon as the layout is packed. Pass a provider to receive that size and return the memory to write into:

RawAtlas atlas = builder.Build(sprites, PixelFormat.Rgba32,
    output: (width, height, format) => new RawImageBuffer(width, height, format, myStagingMemory, stride: myRowPitch));

Or split the two phases yourself:

AtlasLayout layout = builder.Pack(sprites);                  // sizes only; no pixels touched
var target = new RawImageBuffer(layout.Width, layout.Height, PixelFormat.Rgba32, rentedMemory);
builder.Compose(sprites, layout.Rects.Span, target);        // writes every atlas byte once

Zero-allocation steady state

var rects = new PackedRect[sprites.Length];                  // lent layout storage
RawImageBuffer target = default;
AtlasPixelBufferProvider provider = (w, h, f) =>
    target.Width == w && target.Height == h ? target : (target = RawImageBuffer.Allocate(w, h, f));

for (int frame = 0; ; frame++)
    builder.Build(sprites, PixelFormat.Rgba32, provider, rects);  // no allocations after warm-up

TryPack(ReadOnlySpan<RectSize>, Span<PackedRect>, out w, out h) packs sizes into caller memory without throwing.

Tedd.FIC input and output

FicImage[] inputs = files.Select(bytes => new FicImage(bytes)).ToArray();
RawAtlas raw = builder.Build(inputs, PixelFormat.Rgba32);    // decoded in parallel into pooled (or lent) scratch

FicAtlas fic = builder.BuildFic(sprites, new FicEncodeOptions { Effort = FicEffort.Fast });
File.WriteAllBytes("atlas.fic", fic.Data.ToArray());

FicImage(data) reads the dimensions from the header. For containers with outer compression, reading the header costs a decompression, so pass the dimensions with FicImage(data, width, height, channels) when you already know them. Decode scratch can be lent with the decodeScratch argument (AtlasBuilder.GetDecodeScratchLength). Encoded output can be written into your memory through a FicBufferProvider.

Low-level online packers

For dynamic atlases such as glyph caches, use the fixed-bin packers directly:

var packer = new MaxRectsPacker(1024, 1024);
if (packer.TryInsert(18, 24, MaxRectsHeuristic.BestShortSideFit, out PackedRect slot)) { /* upload glyph at slot */ }
var skyline = new SkylinePacker(1024, 1024);                 // cheaper per insert

Options

Content rectangles (PackedRect) exclude padding. Sprite i occupies rects[i], and its padding ring surrounds that rectangle. The layout is deterministic: the same inputs and options produce the same atlas regardless of thread count.

Performance

These are medians of interleaved runs of AtlasBuilder.Build with default options (MaxRects, Balanced effort, all 32 threads) and lent output buffers, on an AMD Ryzen 9 5950X with .NET 11 RC1. Every layout and atlas byte is identical to the first implementation. Only the speed changed:

On very regular inputs such as tile grids, where every free list holds only a handful of rectangles, the single-threaded packer is about 12% slower than the first implementation. Multi-threaded builds of the same input are still faster.

The main gains come from:

• MaxRects free list: stored as edge arrays and scanned with AVX2. A proven edge-coincidence filter replaces the full containment prune.
• FIC decoding: overlapped with packing.
• Pixel conversion: pshufb kernels.
• Streaming stores: non-temporal stores for atlases larger than the last-level cache.

The research report documents the method, all 30 hypotheses (rejected ones included), the raw data and the reproduction commands.

Documentation and benchmarks

• Project site: https://tedd.github.io/Tedd.RectanglePacker/
• Comparison with other .NET packers and image libraries: https://tedd.github.io/Tedd.RectanglePacker/benchmarks.html. The method, command line and full result tables are in BENCHMARKS.md.
• Research holds the measured optimization investigation behind the current implementation: the benchmark rig, hypothesis ledger, raw results and report.

Build

dotnet build src/Tedd.RectanglePacker.slnx -c Release
dotnet test src/Tedd.RectanglePacker.slnx -c Release

The benchmark harness lives in src/Tedd.RectanglePacker.Benchmarks. Run it with measure, hash or phases, or pass BenchmarkDotNet arguments.

License

MIT