rectangle-pack

一个通用、确定性的箱装程序，旨在适应任何二维或三维用例。

rectangle-pack 是一个库，专注于将任意数量的较小矩形（包括二维和三维矩形棱柱）排列在任意数量的较大矩形内。

rectangle-pack 提供了一个 API，允许消费者控制矩形的装箱方式，从而可以根据其特定用例定制装箱。

虽然 rectangle-pack 最初是为纹理图集相关用例设计的 - 但库本身没有图像的概念，可以在任何矩形装箱场景中使用。

快速入门

# 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();

完整 API 文档

背景/初始动机

no_std

矩形打包支持 no_std，通过禁用 std 功能来实现。

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

禁用 std 功能具有以下作用。

• BTreeMap 在原本使用 HashMap 的地方被内部使用。

功能

• 将任意数量的2D/3D矩形放入任意数量的2D/3D目标箱子中。

  • 通过基于宽度+高度+深度的API支持三维矩形。

• 通用的API，尽可能将功能推入用户空间，以实现最大的灵活性。

• 当需要确保某些矩形总是共享同一个箱子时，可以使用通用的组ID来分组矩形。

• 支持二维矩形（深度=1）。

• 用户提供的启发式算法，可以对打包算法进行完全控制。

• 零依赖性，使其更容易嵌入到更特定用例的库中，而不会引入冗余。

• 确定性打包。

  • 使用相同的启发式算法和相同大小的目标箱子对相同的输入进行打包，将始终导致相同的布局。
    • 这在需要可重复构建的地方很有用，例如生成基于内容哈希进行缓存的纹理图集。

• 能够移除放置的矩形并合并相邻的空闲空间。

未来工作

rectangle-pack 的第一个版本是为了满足我的个人需求而设计的。

因此，有一些可能很有用的功能，由于我没有需要，所以没有探索。

以下是一些未来可能有用的功能。

三维输入矩形旋转

当尝试将矩形放入最小的可用箱子部分时，我们可能希望旋转矩形以查看哪种方向最适合。

这可以通过以下方式实现：

1. API为每个传入的矩形公开了三个布尔值，分别是 allow_global_x_axis_rotation、allow_global_y_axis_rotation、allow_global_z_axis_rotation。

2. 假设这三个都启用了。在尝试放置矩形/箱子时，我们应该尝试所有6种可能的方向，然后选择最佳放置（基于 ComparePotentialContainersFn 启发式）。

3. 向调用者返回有关哪个轴被旋转的信息。

互斥组

例如，确保某些矩形组不放入同一箱子。

也许你有两个盘子（箱子）和两组奶酪（矩形），一组给Alice，一组给Bob。

在打包时，你希望确保这些奶酪组各自进入不同的盘子，因为Alice和Bob不喜欢共享。

关于箱子打包的统计信息

例如，浪费的空间量等，这允许调用者比较不同目标箱子大小和启发式算法组合的结果，以查看哪个打包得最有效。

如果你有不受支持的用例，请直接提交问题或发送拉取请求。

打包算法

我们从 rectpack2D 中描述的算法开始，然后进行了一些调整，以支持我们灵活支持所有用例的目标。

• 启发式算法由调用者提供，而不是由 rectangle-pack 决定用户提供的启发式算法。

• 当将一个bin的可用部分分割成两个新的bin部分时，我们不会任意决定分割方式。相反，我们依据用户提供的more_suitable_containers启发式函数来决定。

• 这里有一个第三维度。

在野外

以下是一些已知的rectangle-pack生产用户。

• Akigi使用rectangle-pack来支持其运行时纹理分配策略的部分。

• Bevy使用rectangle-pack来创建纹理图集。

贡献

如果您有一个不受支持的用例、一个问题、一个补丁或其他任何东西，请直接打开一个问题或提交一个拉取请求。

测试

运行测试套件。

# Clone the repository
git clone [email protected]:chinedufn/rectangle-pack.git
cd rectangle-pack

# Run tests
cargo test

参见

• rectpack2D
  • 我们的初始实现受到的启发部分