# rectpack2D packs rectangles into texture atlases with a flat vector of empty spaces

> rectpack2D is a header-only C++ library that packs rectangles into a square bin, using the lightmap insertion algorithm with the space tree replaced by a vector of free rectangles. It ships without releases, so you vendor the header, and the tuning knob that matters is discard_step.

**TeamHypersomnia/rectpack2D** — A header-only, very efficient 2D rectangle packing library. Used in Assassin's Creed, Snapchat and Skydio drones. 2 scientific references.

- Repository: https://github.com/TeamHypersomnia/rectpack2D
- Website: http://gamedev.stackexchange.com/a/34193/16982
- Stars: 668 · Forks: 70
- Language: C++
- License: MIT
- Published: 2026-10-21 · Updated: 2026-10-21 · Language: en
- Canonical page: https://hysenlabs.com/projects/teamhypersomnia-rectpack2d

## A texture atlas packer that grew out of a game engine

rectpack2D is a header-only 2D rectangle packing library written in modern C++. It packs rectangles into a square bin, which is the shape you need when you are building a texture atlas and your graphics API has a maximum texture size.

The origin story explains the design. The library was originally developed for the needs of Hypersomnia, a free and open source multiplayer shooter, and the current version is a refactored and highly optimized version of the original library, which still exists in the repository as a legacy branch.

The stated users are notable. The project page says it is used in Assassin's Creed: Valhalla, that it is used by Snapchat, and that it is used by Skydio, one of the top drone manufacturers. The topics tag it as rectangle, texture, and utility library, which is the right framing: this is a building block for an asset pipeline, not a standalone tool.

The proof of correctness is academic as well as commercial. The project points to two scientific references on Google Scholar under the maintainer's name, and a rectangle packing algorithm that lands in a peer reviewed paper has a stronger guarantee than one that only survived a game jam.

The licence is MIT, the primary language is C++, and the default branch is master. There are no GitHub releases, which is normal for a header-only library that you copy into your tree rather than install from a package manager.

## One header to include, and a CMake example you can build

The usage instructions are short because the library is small.

This is a header-only library. You include the `src/finders_interface.h` header and you are good to go. For an example use, the project points at `example/main.cpp`.

Building the example on Windows takes a Visual Studio generator:

```bash
mkdir build
cd build
cmake -G "Visual Studio 15 2017 Win64" ..
```

Then you build the generated `.sln` file using the newest Visual Studio Preview.

On Linux the configure step passes an option that enables the example build, and the flags differ:

```bash
mkdir build
cd build
cmake -DRECTPACK2D_BUILD_EXAMPLE=1 ..
make
```

After that, `make run` starts the example.

The RECTPACK2D_BUILD_EXAMPLE option is the detail worth noticing, because it tells you the example is not built by default. A library that made the example part of the default build would compile the demo in every consumer's build, and the option keeps that cost off you.

The repository layout is minimal and matches the header-only claim. There is a src directory, a tests directory, an example directory with its own CMakeLists.txt and main.cpp, a CMakeLists.txt and CMakePresets.json at the root, an images directory holding the figures used in the write-up, and a thoughts.md file that appears to hold design notes. There is no packaging infrastructure, no installed CMake target, and no configuration header, which is exactly what a vendored header library looks like.

The practical consequence for adoption is that you copy the src directory into your project and you own the code from that point. There is no upstream to pull a fix from unless you fetch it manually.

## The insertion algorithm, and why a vector beat a tree

The mechanism is a variant of the lightmap packing algorithm, and the project's own account of how it diverges is the most useful thing here.

The library started as an implementation of the algorithm described in the blackpawn lightmaps write-up. The current version somewhat derives from the concept described there, however it uses just a vector of empty spaces, instead of a tree, and the project calls that a performance breakthrough.

The data structure is a plain vector of free rectangles. The rectangle type is simple:

```cpp
struct rect_xywh {
	int x;
	int y;
	int w;
	int h;
};
```

The vector is named `empty_spaces` and starts empty:

```cpp
std::vector<rect_xywh> empty_spaces;
```

Given a user specified initial bin, a square of some size S, the first empty space is initialized to the whole bin:

```cpp
empty_spaces.push_back(rect_xywh(0, 0, S, S));
```

Insertion then iterates the vector of empty spaces backwards and looks for one the image fits into. When the image is strictly smaller than the candidate space, the algorithm computes two remaining rectangles, a bigger split and a smaller split, and the space that was just filled is erased by swapping and popping:

```cpp
// Erase the space that we've just inserted to, by swapping and popping.
empty_spaces[candidate_space_index] = empty_spaces.back();
empty_spaces.pop_back();

// Save the resultant splits
empty_spaces.push_back(bigger_split);
empty_spaces.push_back(smaller_split);
```

The order of those two pushes is deliberate. The smaller split is pushed after the bigger one, which matters because later candidate images encounter the smaller splits first, and that makes better use of empty spaces overall.

The corner cases are spelled out too. If the image dimensions equal the candidate space exactly, the space is deleted and no splits are created. If the image fits but exactly one of its dimensions matches the candidate's corresponding dimension, the space is deleted and a single split is created, for example a 10x40 space from a 20x40 image in a 30x40 space.

If the insertion fails, the same procedure is tried for a flipped image. The complete modular split calculation with the corner cases lives in `src/rectpack2D/insert_and_split.h`.

## discard_step is the knob that trades packing quality for build time

Once you can insert individual images into a bin of a given initial size S, the question becomes what S to pass so the rectangles waste the least space.

The library answers with a binary search. It starts with the size specified by the library user, which is typically the maximum texture size allowed on a particular GPU. If the packing succeeded at the given bin size, it decreases the size and tries again. If the packing failed at the given size, because some rectangles could not be further inserted, it increases the size and tries again.

The search is aborted once a packing has succeeded and the dimensions of the next candidate would differ from the previous by less than `discard_step`. The project explains that this variable exists so that accuracy can easily be traded for a speedup. `discard_step = 1` yields the highest accuracy, and `discard_step = 128` will yield worse packings, but will be a lot faster.

That single parameter is the most important tuning decision in the library, and the project is candid that larger values produce worse packings. A larger discard_step means the search stops considering bin sizes that differ only slightly, so it settles for a bin that is a little bigger than strictly necessary, and the wasted area is the difference.

The search is also performed in stages. First the bin size is decreased by both width and height, keeping it square. Then the same is done but only decreasing width. Then the same but only decreasing height. The reasoning behind that ordering is in the project text, which was cut off in the source I was given, so the full rationale is not available here.

The practical workflow is therefore: pick a starting S that matches your GPU limit, set discard_step to 1 to find the best achievable bin, then raise it until the pack time is acceptable for your build. Since the binary search re-packs the whole set on each candidate size, the cost is a multiple of a single pack, and discard_step is the lever that reduces how many candidates are tried.

## The published benchmarks are three specific sprite sets, not a general claim

The benchmark section is narrow, and reading it carefully is more useful than treating it as a headline.

The tests were conducted on an Intel Core i7-4770K CPU at 3.50GHz, with the binary built using clang 6.0.0 and an -O3 switch. That is a specific, dated machine, which is good practice for a benchmark and also tells you the numbers are not about your hardware.

Three cases are reported. Arbitrary game sprites, 582 subjects, took 0.8 ms and wasted 10982 pixels, which the project expresses as 0.24 percent, equivalent of a 105 x 105 square, in an output of 1896 x 2382. Arbitrary game sprites plus Japanese glyphs, 3264 subjects, took 4 ms and wasted 15538 pixels, 0.31 percent, equivalent of a 125 x 125 square, in an output of 2116 x 2382. Japanese glyphs plus some GUI sprites, 3122 subjects, took 3.5 to 7 ms and wasted 9288 pixels, 1.23 percent, equivalent of a 96 x 96 square, in an output of 866 x 871.

What these numbers actually show is that the wasted area is small on irregular sprite sets, which is the case that matters for a game atlas. The sub-percent waste on the first two cases is the interesting result. The third case, at 1.23 percent, is a set made mostly of uniform glyphs, and uniform rectangles are the case where a guillotine style packer has less freedom to work with.

The spread in the third case, 3.5 to 7 ms, also tells you something. The packing is not deterministic across runs, because the insertion order interacts with how the free space vector happens to be laid out, and a given input can land in a slightly different configuration. For a build pipeline that needs reproducible output, that is worth knowing about before you commit to it.

There is no benchmark for rotation, for very large sets, or for pathological input, and the project does not claim one.

## Where rectpack2D is the wrong tool

Four boundaries are visible from what the project describes.

There is no rotation support in the documented behaviour. The algorithm places rectangles in the orientation they are given, and the fallback when an insertion fails is to try the flipped image, which is a different thing. If your sprites need to be rotated to fit, this library does not do that for you, and you would have to pre-rotate and try both orientations yourself.

The bin is square. The starting size is described as a square of some size S, and the search decreases width and height together first, keeping it square, then varies them separately. If your atlas needs a non-square target, or a fixed bin with a known aspect ratio, that is not the shape this algorithm is built around.

There is no published release stream. The repository has no GitHub releases, so the only way to pick up an upstream change is to fetch the repository and copy the header yourself. For a library with no dependencies, that is a manageable chore, but it means there is no patch channel and no changelog to read, so you are choosing a snapshot.

And the packing quality depends on input ordering. The algorithm is a heuristic, not an exact solver, and the results depend on the order the rectangles are presented in and on the bin size the search lands on. There is no guarantee of an optimal packing, and the discard_step parameter makes that trade explicit. If you need a provably minimal atlas, or a packing that is stable enough to diff between builds, this is the wrong category of tool.

The comparison with a general purpose atlas packer comes down to that. A configurable tool with a GUI or a config file, one that can rotate, pack into non-square bins, and output a fixed layout, will be easier to adopt if your pipeline is a one-off. rectpack2D is easier to embed in code, has no runtime, and gives you the source, which is why it appears inside a game engine and a drone's software rather than in an artist's workflow.

## Conclusion

rectpack2D fits a game or tool developer who needs to bake many small images into one texture atlas and wants a dependency free header it can vendor, especially where the rectangle set is irregular and a general purpose atlas packer would need configuring. It does not fit a pipeline that needs rotation, arbitrary bin shapes, or a stable packaged release stream, since the repository publishes no GitHub releases. Before adopting it, measure your own atlas with discard_step set to 1 to see the quality ceiling, then raise it until the build time is acceptable, because that value trades packing accuracy for speed directly.

## FAQ

### How do I use rectpack2D in a C++ project?

It is a header-only library, so you include the src/finders_interface.h header and link nothing. An example use is provided in example/main.cpp.

### How do I build the rectpack2D example on Linux?

Create a build directory, configure with cmake -DRECTPACK2D_BUILD_EXAMPLE=1 .. so the example is built, then run make and make run.

### What does the discard_step setting do in rectpack2D?

It is the accuracy versus speed trade in the binary search for the smallest bin size. discard_step = 1 yields the highest accuracy, while discard_step = 128 produces worse packings but runs a lot faster.

### What algorithm does rectpack2D use to place rectangles?

It derives from the lightmap packing algorithm but uses a vector of empty spaces instead of a tree, which the project calls a performance breakthrough. Rectangles are inserted into the first fitting free space found while scanning backwards, and the used space is replaced by a bigger and a smaller split.

### Does rectpack2D rotate rectangles when packing?

The documented behaviour does not include rotation. When an insertion fails, the same procedure is tried for a flipped image instead.

## Sources

- [Issues](https://github.com/TeamHypersomnia/rectpack2D/issues)
- [License: MIT](https://github.com/TeamHypersomnia/rectpack2D/blob/master/LICENSE)
- [Project website](http://gamedev.stackexchange.com/a/34193/16982)
- [README](https://github.com/TeamHypersomnia/rectpack2D/blob/master/README.md)
- [TeamHypersomnia/rectpack2D on GitHub](https://github.com/TeamHypersomnia/rectpack2D)

---

Hysen Labs editorial analysis, written from the project's own repository and release notes. Cite the canonical page: https://hysenlabs.com/projects/teamhypersomnia-rectpack2d