Rect_Pack is a JAI module to pack rectangles into a bigger one. It implements the same algorithm used in Firefox’s rendered WebRender, plus some extra features. The main difference between this rect packer and most of the available ones (e.g. stb_rect_pack) is that here you can both pack and unpack a rectangle.
Rectangle allocation and deallocation is based on a simple binary tree of either vertical or horizontal splits.
I strongly suggest reading Nicolas Silva’s (Nical) blog post where he explores the same problem while implementing Firefox’s glyph renderer.
In his blog post Nical goes through a shelf allocator which is not currently implemented in this module, if people want it I can totally add that. I have been doing great with the guillotine so far.
Adding rectangles
rect := rect_packer_add(*packer, 32, 15);
The splitting logic supports two algorithms, Guillotine and Slab. Whenever you add a rectangle to the packing the splitting algorithm will partition the space to place your rectangle while minimizing waste of space.
Starting from an empty rectangle as follows:
_________________________
| |
| |
| |
| |
| |
| |
| |
| |
| |
|_________________________|
Based on the splitting algorithm used you will obtain one of the following results when adding a new rectangle to the packing:
Strategy.GUILLOTINE
_________________________
Inserting: | | |
| REC : |
_________ ._._._._._|................
| | | : |
| REC | | : |
|_________| | : |
| : |
| : |
|_________:_______________|
Strategy.SLAB
_________________________
Inserting: | | : |
| REC | : |
_________ |_________| : |
| | | : |
| REC | ...........................
|_________| | : |
| : |
| : |
|____________:____________|
The difference between guillotine and slab is that slab always splits in half, while guillotine splits at exactly the size of the rectangle to insert. So, it also splits a lot less.
There is one extra split-strategy I haven’t mentioned yet which is Strategy.GUILLOTINE_SLAB_SIZE, which follows the same logic as guillotine but before doing it, it rounds up the size of the rectangle to insert to the next power of two. The reason behind this is that hopefully it will be easier to reclaim freed blocks (at the cost of wasting more space).
When inserting in an already populated packing, it’s necessary to pick the best available left-over region. There are many ways to achieve that, this module supports 3 heuristics:
Heuristic.BEST_SHORT_SIDE_FITAmong all available free regions where the new rectangle fits, pick the one that matches the shortest side of the rectangle the best.Heuristic.BEST_AREA_FITAmong all available free regions where the new rectangle fits, pick the one that has the smallest area.Heuristic.BOTTOM_LEFTAlways try to pack everything towards the origin.
If these don’t work for your use-case, this module supports custom heuristic functions. You can pass Heuristic.CUSTOM alongside a heuristic callback to the initialization function (see here). The callback will be invoked for every available free rectangle. The callback is intended to return a score in the form of an integer. The smallest-scored rectangle score will be picked as a target, and eventually split.
Removing rectangles
rect_packer_remove(*packer, rect); // Note that rect is of type *Rect
When a rectangle is removed, if its sibling from a previous split is also free the now free blocks will be collapsed into one. This happens recursively until no more collapses are possible.
This method has some limitations but it’s fast and works in most cases. Here are two illustrations of a case where two siblings can be collapsed and a case where they cannot.
GOOD CASE
_________________________
| A : C | root
| : | AB CD
| FREE : USED | A* B* C D
| : |
........................... |
| B : D | V
| FREE : USED | root
| : | AB CD
|____________:____________| C D
_________________________
| A : C | root
| : | AB CD
| FREE : FREE | A* B C* D
| : |
...........................
| B : D | Cannot collapse siblings
| USED : USED |
| : |
|____________:____________|
Similar libraries
There is a Rust crate that does almost exactly the same thing implemented by Nicas for Firefox, although it supports less customization. You can find it here
How to use:
packer: Rect_Packer;
rect_packer_init(
*packer,
max_width = 1024,
max_height = 1024,
split_strategy = .GUILLOTINE,
heuristic = .BEST_SHORT_SIDE_FIT);
Other possible values for split strategy are GUILLOTINE, GUILLOTINE_SLAB_SIZE, SLAB. The supported heuristics are BEST_SHORT_SIDE_FIT, BEST_AREA_FIT, BOTTOM_LEFT or CUSTOM.
To supply a custom heuristic you can pass two additional parameters to rect_packer_init(): custom_heuristic and user_data.
The heuristic is intended to score a node as a possible candidate to contain a rectangle of size width*height, lower is better.
my_heuristic :: (user_data: *void, node: *Node, width: int, height: int) -> int
{
// This is the implementation of BEST_SHORT_SIDE_FIT
score := min(node.rect.w - width, node.rect.h - height);
return score;
}
rect_packer_init(
*packer,
max_width = 1024,
max_height = 1024,
split_strategy = .GUILLOTINE,
heuristic = .CUSTOM);
custom_heuristic = my_heuristic,
user_data = null
);
After packing a new 32x15 rectangle, we get back a pointer to a rect. The pointer is used to identify the rectangle so that it can also be removed, treat this the same way as you would treat malloc.
rect := rect_packer_add(*packer, 32, 15);
As mentioned previously here’s how you can remove a rectangle from the packing.
rect_packer_remove(*packer, rect);
Finally, if you want to fully reset the packer:
rect_packer_reset(*packer);