Sequencing in Transformation of Rasterized 3D Models
一句话看懂本论文把由体素、乐高积木或链式立方体构成的结构的“变形”转化为机器可执行的动作序列，在满足构件抓取、放置与折叠约束的同时，使总工作量尽量小。
问题背景
栅格化三维结构由离散、等大的构件组成，就像图片由像素组成：在计算机中是体素，在现实中可以是立方块、砖块，甚至罐头。这类构件便于作为数据处理，易于复用，也适合批量生产。本论文关注的问题是：如何把一个这样的结构变成另一个。论文将其表述为从源结构到目标结构的变换，目标是找到一条机器可以执行的高效操作序列，效率由与应用相关的代价函数衡量。用原料堆搭建结构是其中的特例，此时源结构就是原料堆。
难点在于问题是离散的。仅仅决定哪个构件放到哪里就是一个组合问题：n 个构件共有 n! 种指派方式。而且代价最低的指派未必能执行：吸盘夹爪只能抓取顶面上的构件；乐高积木被其他积木压住或包围时无法取出；放置时也不能让积木悬空。因此，排序需要在总工作量与物理可行性之间权衡，对积木而言还要兼顾源结构构件的复用程度。
方法原理
论文研究了三个案例，用论文自己的话说，它们代表了栅格化结构变换与成形中的大多数排序问题：同质体素的抓放（第 3 章）、异质乐高积木的抓放（第 4 章），以及体素链的折叠（第 5 章）。下面的演示逐步重现论文中的体素算例，最后并列给出另外两个案例。
对齐与分类。 两个网格模型先被栅格化为体素。假设二者在竖直方向已经对齐、且只允许平移，在水平面内穷举搜索即可找到重叠最大的对齐位置。只属于源结构的体素为待移体素（M），只属于目标结构的为空位（V），重叠的体素原地保留。若 M 与 V 数量不等，多出的体素放入一个线形料堆，或从中取用。
为每次移动定价。 代价函数模拟一台三轴直角坐标机器，它只在安全平面 zmax 上做水平移动：把待移体素 i 移入空位 j 的代价为 cij = |xj − xi| + |yj − yi| + 2zmax − zi − zj。以最小总代价把每个 M 配给一个 V 是一个指派问题，匈牙利算法可在 O(n3) 时间内求解，而无需比较 n! 种方案。
满足顶部抓取约束。 使用真空吸盘夹爪时，只有顶面上的体素才能被抓取或放置。一次性对全部 M 和 V 求最优配对（全局优化策略 GOS）能给出代价下界，但这些配对可能陷入死锁。局部优化策略（LOS）只用当前可达的 M 和 V 构造代价矩阵，用匈牙利算法求配对并执行这些移动。
更新并重复。 每一轮之后顶面发生变化，于是重新构造代价矩阵，重复上述过程，直到所有 M 都放入空位。在该算例中，LOS 的总代价为 27，与 GOS 下界相同。论文还比较了两种更简单的基线：每步只移动当前代价最小的一对可达体素的贪心策略（GSS），以及随机策略（RSS）。
推广到积木与链。 积木（乐高）。 体素被逐层合并为积木。刚性方法（RT）在变换前就生成源、目标两套积木布局；柔性方法（FT）在变换过程中实时生成目标布局，优先采用源结构上可取出的积木类型。每种方法再与三种经由缓存区和库存调度积木的策略组合（见下图），共得到六种算法，即 RT1–RT3 和 FT1–FT3，名称由方法和策略编号组成。
算法用三个指标评价：代价（抓放次数）、复用率（源结构积木最终用于目标结构的比例），以及综合性能（复用率越高、代价越低，该值越高）。
链。 对链式结构，先在形状的体素中寻找一条哈密顿路径，把形状转化为一维的链；为使哈密顿路径存在，可以删补体素，也可以把每个体素细分为 4 个（二维）或 8 个（三维）子体素。随后根据初始与目标关节角之差规划折叠过程。
实验结果
体素策略在八个模型上测试（wall、pyramid、starfish、cube、igloo、castle、stairs 和 Eiger 山体），每个模型栅格化为 2,250 至 2,550 个体素，并两两相互变换。GOS 的代价始终最低，但本身并不给出可行的序列，而且耗时最长，因为它要在一个很大的代价矩阵上运行一次匈牙利算法。LOS 的代价次之，GSS 略差，RSS 明显更差但速度最快。工作量取决于 M-V 对的数量，而不是模型大小：wall → pyramid 需要 1,643 对，而形状更相近的 pyramid → igloo 只需 325 对。在不同栅格化分辨率下，总代价大致随 M-V 对数线性增长，LOS 的耗时也是如此，尽管匈牙利算法本身的复杂度为 O(n3)。LOS 因在代价与计算时间之间取得良好平衡而脱颖而出。论文指出的局限是顶部抓取约束，它使悬挑结构无法搭建；而像乐高这样能相互扣合的积木可以形成悬挑，这正是乐高一章的出发点。
在乐高实验中，八个三角网格模型被转换为积木模型。对所有两两变换取平均，代价随模型规模线性增长，策略 1、2、3 的代价依次降低。策略 1 和策略 2 的复用率非常接近，因此论文认为一开始就把源结构完全拆散并不值得。FT 比 RT 复用更多积木，但所用积木往往小于最合适的尺寸，导致结构内部存在滑移面、强度较弱，目标结构的积木数也更多。FT3 的复用率可与最好的 RT 算法相当；在由一个模型变换到其余七个模型的测试中，它以低得多的代价达到了与 FT1、FT2 相近的复用率。加入颜色信息后（共 114 种颜色，外表面积木的颜色和形状都必须匹配），复用率有所下降，但并未降到零，因为内部积木可以是任意颜色。论文指出，综合性能只是一个经验指标；在对代价有不同定义的场景中，各算法的相对排序可能改变。
论文留下两个未来方向：引入有限元分析等受力分析，使最终结构和各中间结构都保持稳定；以及在模块层面（把一组构件作为整体移动）而非单个构件层面进行变换，论文预期这能同时改善复用率和代价。
引用
@phdthesis{pan2018sequencing,
title={Sequencing in Transformation of Rasterized 3D Models},
author={Pan, Wei},
year={2018},
school={Singapore University of Technology and Design}
}