Transformation of LEGO Models

问题背景

集装箱堆垛引出一个实际问题：如何高效地把集装箱从一个堆垛移到另一个堆垛？本文借助乐高研究一个与之有一定关联的问题：利用现有乐高模型上拆下的积木搭建一个新的乐高模型。把三维形状转换成乐高模型的算法已有很多，但用另一个模型的积木来搭建乐高模型，此前尚未见于公开文献。这一任务有两个相互制约的目标：每次拾放（pick-and-place，PnP）一块积木都计为一次移动成本；同时，源模型的积木应尽可能多地用到目标模型上。

物理约束使移动顺序变得关键。完全或部分压在其他积木下面的积木无法拾取，积木也不能放在悬空的位置。此外，位于顶面但四周被其他积木完全包围的积木，作者也视为不可移动，因为要取出它需要额外的拾放操作。

方法原理

源模型自上而下逐层拆解，目标模型自下而上逐层搭建。两种基本方法（刚性变换 RT 与柔性变换 FT）决定目标模型使用哪些积木，三种策略决定每块积木的来源：直接取自源模型、取自存放已拆下积木的缓冲区，或取自供应无限的库存。两者组合得到 RT1–RT3 和 FT1–FT3 共六种算法，使用七种形状的积木。

1. 移动与约束。 每拾放一块积木（源模型到缓冲区、源模型到目标、缓冲区到目标或库存到目标）计成本 1。只有可移动的积木才能被拾取，即上方没有积木、且未被四周完全包围的积木。
2. 刚性目标或柔性目标。 刚性变换（RT）在变换开始前生成目标乐高模型，每层优先使用大积木。柔性变换（FT）则在变换过程中由中间体素模型即时生成目标：评分规则按源模型当前可提供的某类可移动积木的数量为该类积木加权，从而优先使用源模型上的积木。
3. 策略 1。 先把源模型全部拆到缓冲区，再用缓冲区中的积木搭建目标，缓冲区缺少的积木由库存补足。
4. 策略 2。 源模型上的可移动积木直接移到目标。若没有匹配的积木，就到缓冲区中查找；缓冲区也没有时，再把源模型拆下一层放入缓冲区，露出新的积木。只有源模型拆完后才使用库存。
5. 策略 3。 不使用缓冲区。源模型上有匹配的可移动积木就直接移到目标，否则由库存提供。

算法用三项指标评价：成本 C，即搭建目标所需的拾放次数；复用率 R = N_r/N_s，即源模型 N_s 块积木中最终用到目标上的比例；以及综合性能 P = V·R/C，其中 V 是目标模型的体素数。

实验结果

测试使用八个转换为乐高的三角网格模型。第一项测试把模型 A 分别变换为其余七个模型，每个模型约 2500 个体素。第二项测试在七种模型尺寸下让八个模型两两互变。成本随模型尺寸线性增长，在每种模型尺寸下，策略 1、2、3 的成本都依次递减。FT 算法的成本高于对应的 RT 算法，因为 FT 搭出的目标模型积木更多。FT3 的复用率与最好的 RT 算法相当。RT3 的复用率明显低于 RT1 和 RT2：目标积木事先确定、又没有缓冲区时，很难在源模型上找到匹配的积木，平均一半以上的目标积木来自库存。模型尺寸超过每模型 1700 个体素后，复用率对尺寸变化不太敏感；模型更小时复用率会下降。

第三项测试加入颜色：外表面积木必须与表面颜色一致，内部积木可以是任意颜色。在球变小屋的例子中，RT1 和 RT2 的复用率分别为 61.9% 和 59.9%，RT3 仅为 9.2%（图 9）。作者也指出了其中的取舍：FT 的复用率更高，但使用的积木更多、更小，结构内部存在滑移面，强度较弱；综合性能只是一个经验指标，其他场景可能对成本有不同的权衡。本研究每次只移动一块积木，把一组积木作为模块整体复用留待未来工作；其结论也未必能直接用于货运集装箱堆垛等具体的工业应用。