Lib.rs

一个用 Rust 编写的矩形打包器，用于将许多矩形压缩进一个更大的矩形中。它主要考虑精灵打包（例如，创建精灵图集或 CSS 图像表）。

支持每个项目 90° 旋转。

打包了 1200 个矩形，覆盖率约为 ~99%

示例

use crunch::{pack, Rect, Item, Rotation};
use std::iter::*;

fn main() {
    // The 15x15 container we'll be packing our items into
    let container = Rect::of_size(15, 15);

    // Our items to pack. The user-data here are chars,
    // but could be any copyable type
    let items = [
        Item::new('A', 2, 9, Rotation::Allowed),
        Item::new('B', 3, 8, Rotation::Allowed),
        Item::new('C', 4, 7, Rotation::Allowed),
        Item::new('D', 5, 6, Rotation::Allowed),
        Item::new('E', 6, 5, Rotation::Allowed),
        Item::new('F', 7, 4, Rotation::Allowed),
        Item::new('G', 8, 3, Rotation::Allowed),
        Item::new('H', 9, 2, Rotation::Allowed),
    ];

    // Now we can try to pack all the items into this container
    let result = pack(container, items);
    let packed = match result {
        Ok(all_packed) => all_packed,
        Err(some_packed) => some_packed,
    };

    // To display the results, let's create a 15x15 grid of '.' characters
    let mut data : Vec<char> =
        repeat(repeat('.').take(container.w).chain(once('\n')))
        .take(container.h)
        .flatten()
        .collect();

    // We can iterate through each (rect, data) pair that was packed
    for item in &packed {
        for x in item.rect.x..item.rect.right() {
            for y in item.rect.y..item.rect.bottom() {
                data[y * (container.w + 1) + x] = item.data;
            }
        }
    }

    // The items packed very efficiently, using 90% of the 15x15
    // container's space. You'll notice that some ('H', for example)
    // were able to rotate to fit.
    println!("{}", String::from_iter(data));

    // EEEEEEDDDDDDBBB
    // EEEEEEDDDDDDBBB
    // EEEEEEDDDDDDBBB
    // EEEEEEDDDDDDBBB
    // EEEEEEDDDDDDBBB
    // FFFFCCCCHHAABBB
    // FFFFCCCCHHAABBB
    // FFFFCCCCHHAABBB
    // FFFFCCCCHHAA...
    // FFFFCCCCHHAA...
    // FFFFCCCCHHAA...
    // FFFFCCCCHHAA...
    // GGGGGGGGHHAA...
    // GGGGGGGGHHAA...
    // GGGGGGGG.......
}

如果你正在打包纹理，你也可以使用 pack_into_po2() 辅助函数，它将找到可以装入项目的最小 2 的幂矩形（如果你的渲染系统关心这一点，这很好）。

它是如何工作的？

解释起来有点复杂，但算法使用了一个 节点 树。根节点是初始容器矩形。当第一个项目打包时，它会将容器分割成 0-4 个可能的子容器，或 叶节点。每次我们插入一个新项目时，每个叶节点都会根据其将项目打包的效率（使用空间）给每个叶节点一个 分数，然后我们将项目插入到得分最高的叶节点中。然后那个叶节点被分割。

算法的技巧在于节点树是如何分割自己的。基本上，项目被装入到分配给它打包的叶节点的左上角。然后，我们沿着树向下 碰撞 该矩形，从根节点开始。然后分割与新打包的矩形重叠的每个叶节点，而不仅仅是矩形打包的节点。

分割的工作方式是，给定节点与打包项目的重叠，我们从它中创建尽可能多的角适配矩形。例如

┏━┱───┐              ┌─┲━━━┓     ┌─────┐
┃ ┃   │              │ ┃   ┃     │     │
┡━┛   │              │ ┃   ┃     ┢━━━━━┪
│     │ splits into: │ ┃   ┃ and ┃     ┃
│     │              │ ┃   ┃     ┃     ┃
│     │              │ ┃   ┃     ┃     ┃
└─────┘              └─┺━━━┛     ┗━━━━━┛

这些分裂节点允许重叠，所以我们并不是在逐个细分根节点，而是在创建新的潜在包装路径。由于它们可以重叠，节点分裂可能会在树的上层节点内完全包含一个叶节点。当这种情况发生时，我们不会创建那个叶节点，因为树上的节点已经完全占据了那个空间。

随着我们包装越来越多的矩形，这些评分检查和碰撞检查变得越来越昂贵，因为叶节点的数量迅速增加。你可能会发现叶节点的数量是你要包装的项目数量的2倍或更多。

树结构是我们能够如此高效地完成工作的原因，而且在包装之前预先对物品进行排序，以便首先包装最大的物品。在发生碰撞时，我们可以逐个检查分裂处的碰撞，并且树的每一层都会防止我们不得不检查大量叶节点的重叠。我之前版本的这种方法只是扫描整个扁平的叶节点列表，...它要慢得多。

贡献

如果你找到了使其更快或更节省内存的方法，我很乐意接受pull请求。如果你有一个不太明显的速度改进变更，我会很感激你提供基准测试，这样我可以看到效果。