rectangle-pack

A general purpose, deterministic bin packer designed to conform to any two or three dimensional use case.

rectangle-pack is a library focused on laying out any number of smaller rectangles (both 2d rectangles and 3d rectangular prisms) inside any number of larger rectangles.

rectangle-pack exposes an API that gives the consumer control over how rectangles are packed - allowing them to tailor the packing to their specific use case.

While rectangle-pack was originally designed with texture atlas related use cases in mind - the library itself has no notions of images and can be used in any rectangle packing context.

Quickstart

# In your Cargo.toml
rectangle-pack = "0.4"

//! A basic example of packing rectangles into target bins

use rectangle_pack::{
    GroupedRectsToPlace,
    RectToInsert,
    pack_rects,
    TargetBin,
    volume_heuristic,
    contains_smallest_box
};
use std::collections::BTreeMap;

// A rectangle ID just needs to meet these trait bounds (ideally also Copy).
// So you could use a String, PathBuf, or any other type that meets these
// trat bounds. You do not have to use a custom enum.
#[derive(Debug, Hash, PartialEq, Eq, Clone, Ord, PartialOrd)]
enum MyCustomRectId {
    RectOne,
    RectTwo,
    RectThree,
}

// A target bin ID just needs to meet these trait bounds (ideally also Copy)
// So you could use a u32, &str, or any other type that meets these
// trat bounds. You do not have to use a custom enum.
#[derive(Debug, Hash, PartialEq, Eq, Clone, Ord, PartialOrd)]
enum MyCustomBinId {
    DestinationBinOne,
    DestinationBinTwo,
}

// A placement group just needs to meet these trait bounds (ideally also Copy).
//
// Groups allow you to ensure that a set of rectangles will be placed
// into the same bin. If this isn't possible an error is returned.
//
// Groups are optional.
//
// You could use an i32, &'static str, or any other type that meets these
// trat bounds. You do not have to use a custom enum.
#[derive(Debug, Hash, PartialEq, Eq, Clone, Ord, PartialOrd)]
enum MyCustomGroupId {
    GroupIdOne
}

let mut rects_to_place = GroupedRectsToPlace::new();
rects_to_place.push_rect(
    MyCustomRectId::RectOne,
    Some(vec![MyCustomGroupId::GroupIdOne]),
    RectToInsert::new(10, 20, 255)
);
rects_to_place.push_rect(
    MyCustomRectId::RectTwo,
    Some(vec![MyCustomGroupId::GroupIdOne]),
    RectToInsert::new(5, 50, 255)
);
rects_to_place.push_rect(
    MyCustomRectId::RectThree,
    None,
    RectToInsert::new(30, 30, 255)
);

let mut target_bins = BTreeMap::new();
target_bins.insert(MyCustomBinId::DestinationBinOne, TargetBin::new(2048, 2048, 255));
target_bins.insert(MyCustomBinId::DestinationBinTwo, TargetBin::new(4096, 4096, 1020));

// Information about where each `MyCustomRectId` was placed
let rectangle_placements = pack_rects(
    &rects_to_place,
    &mut target_bins,
    &volume_heuristic,
    &contains_smallest_box
).unwrap();

Full API Documentation

Background / Initial Motivation

no_std

rectangle-pack supports no_std by disabling the std feature.

rectangle-pack = {version = "0.4", default-features = false}

Disabling the std feature does the following.

• BTreeMaps are used internally in places where HashMaps would have been used.

Features

• Place any number of 2d / 3d rectangles into any number of 2d / 3d target bins.

  • Supports three dimensional rectangles through a width + height + depth based API.

• Generic API that pushes as much as possible into user-land for maximum flexibility.

• Group rectangles using generic group id's when you need to ensure that certain rectangles will always end up sharing a bin with each other.

• Supports two dimensional rectangles (depth = 1).

• User provided heuristics to grant full control over the packing algorithm.

• Zero dependencies, making it easier to embed it inside of a more use case specific library without introducing bloat.

• Deterministic packing.

  • Packing of the same inputs using the same heuristics and the same sized target bins will always lead to the same layout.
    • This is useful anywhere that reproducible builds are useful, such as when generating a texture atlas that is meant to be cached based on the hash of the contents.

• Ability to remove placed rectangles and coalesce neighboring free space.

Future Work

The first version of rectangle-pack was designed to meet my own needs.

As such there is functionality that could be useful that was not explored since I did not need it.

Here are some things that could be useful in the future.

Three-Dimensional Incoming Rectangle Rotation

When attempting to place a Rectangle into the smallest available bin section we might want to rotate the rectangle in order to see which orientation produces the best fit.

This could be accomplished by:

1. The API exposes three booleans for every incoming rectangles, allow_global_x_axis_rotation, allow_global_y_axis_rotation, allow_global_z_axis_rotation.

2. Let's say all three are enabled. When attempting to place the rectangle/box we should attempt it in all 6 possible orientations and then select the best placement (based on the ComparePotentialContainersFn heuristic).

3. Return information to the caller about which axis ended up being rotated.

Mutually exclusive groups

An example of this is the ability to ensure that certain rectqngle groups are not placed in the same bins.

Perhaps you have two plates (bins) and two groups of cheese (rectangles), one for Alice and one for Bob.

When packing you want to ensure that these groups of cheese each end up in a different bin since Alice and Bob don't like to share.

Stats on how the bins were packed

Things such as the amount of wasted space - or anything else that would allow the caller to compare the results of different combinations of target bin sizes and heuristics to see which packed the most efficiently.

If you have a use case that isn't supported, go right ahead and open an issue or submit a pull request.

Packing Algorithm

We started with the algorithm described in rectpack2D and then made some adjustments in order to support our goal of flexibly supporting all use cases.

• The heuristic is provided by the caller instead of having rectangle-pack decide on a user provided heuristic.

• When splitting an available section of a bin into two new sections of a bin - we do not decide on how the split should occur arbitrarily. Instead, we base it on the user provided more_suitable_containers heuristic function.

• There is a third dimension.

In The Wild

Here are some known production users of rectangle-pack.

• Akigi uses rectangle-pack to power parts of its runtime texture allocation strategy.

• Bevy uses rectangle-pack to create texture atlases.

Contributing

If you have a use case that isn't supported, a question, a patch, or anything else, go right ahead and open an issue or submit a pull request.

To Test

To run the test suite.

# Clone the repository
git clone git@github.com:chinedufn/rectangle-pack.git
cd rectangle-pack

# Run tests
cargo test

See Also

• rectpack2D
  • Inspired parts of our initial implementation