A header-only, very efficient 2D rectangle packing library.
A header-only 2D rectangle packing library written in modern C++.
This is a refactored and highly optimized version of the original library.
It was originally developed for the needs of Hypersomnia, a free and open-source multiplayer shooter.
Tests were conducted on a Intel(R) Core(TM) i7-4770K CPU @ 3.50GHz
.
The binary was built with clang 6.0.0
, using an -03 switch.
Runtime: 0.8 ms
Wasted pixels: 10982 (0.24% - equivalent of a 105 x 105 square)
Output (1896 x 2382):
In color:
(black is wasted space)
Runtime: 4 ms
Wasted pixels: 15538 (0.31% - equivalent of a 125 x 125 square)
Output (2116 x 2382):
In color:
(black is wasted space)
Runtime: 3.5 - 7 ms
Wasted pixels: 9288 (1.23% - equivalent of a 96 x 96 square)
Output (866 x 871):
In color:
(black is wasted space)
This is a header-only library.
Just include the src/finders_interface.h
and you should be good to go.
For an example use, see example/main.cpp
.
From the repository's folder, run:
mkdir build
cd build
cmake -G "Visual Studio 15 2017 Win64" ..
Then just build the generated .sln
file using the newest Visual Studio Preview.
From the repository's folder, run:
cmake/build_example.sh Release gcc g++
cd build/current
ninja run
Or, if you want to use clang, run:
cmake/build_example.sh Release clang clang++
cd build/current
ninja run
The library started as an implementation of this algorithm:
http://blackpawn.com/texts/lightmaps/default.html
The current version somewhat derives from the concept described there -
however, it uses just a vector of empty spaces, instead of a tree - this turned out to be a performance breakthrough.
Given
struct rect_xywh {
int x;
int y;
int w;
int h;
};
Let us create a vector and call it empty_spaces.
std::vector<rect_xywh> empty_spaces;
Given a user-specified initial bin, which is a square of some size S, we initialize the first empty space.
empty_spaces.push_back(rect_xywh(0, 0, S, S));
Now, we'd like to insert the first image rectangle.
To do this, we iterate the vector of empty spaces backwards and look for an empty space into which the image can fit.
For now, we only have the S x S square: let's save the index of this candidate empty space,
which is candidate_space_index = 0;
If our image is strictly smaller than the candidate space, we have something like this:
The blue is our image rectangle.
We now calculate the gray rectangles labeled as "bigger split" and "smaller split",
and save them like this:
// 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);
Notice that we push the smaller split after the bigger one.
This is fairly important, because later the candidate images will encounter the smaller splits first,
which will make better use of empty spaces overall.
To see the complete, modular procedure for calculating the splits (along with the corner cases), see this source.
If the insertion fails, we also try the same procedure for a flipped image.
Now we know how to insert individual images into a bin of a given initial size S.
discard_step
.
discard_step = 1
yields the highest accuracy. discard_step = 128
will yield worse packings, but will be a lot faster, etc.max(w, h) / min(w, h) * w * h