这是新加坡科技大学宋鹏老师组的项目，获得了 SIGGRAPH 2022 提名奖，在创新上还是非常不错的，也非常的有趣。

宋鹏老师在一月前还参加了 Games 的Webminar 报告，也是讲述的类似的工作，也欢迎大家去了解一下。

谜题与解组装

这是 B 站 Up 主“GM 的秘密基地”关于“圣剑”谜题的解题动画还原，论文中提到的谜题 Puzzle，其实就是指的这些可以在一步步移动后拆解为一块块的个体的过程。

为了方便读者了解相关背景，在这里先科普一些背景知识（来自于宋老师组在Eurographics 2022上的tutorial）。

关于这种谜题，学术界通常将其与组装 Assembly 归为一类问题，并把解开谜题的问题列为解组装问题 disassembly。组装的话每个物块之间有不同的连接方式，按永久性来讲，分为永久和临时的连接；按接触形式来讲，分为用摩擦力固定的连接和支持力固定的连接；按连接方式来讲，临时的连接还分为内在 internal（结构形状决定）和外在 external（使用非连接部件的第三方部件进行连接）……

组装问题中，学术界还会去研究两个物块之间接触面的几何特征，来约束物块之间的相对位移（该工作出自 ZIQI WANG 于 2021 年 SIGGRAPH 的MOCCA 论文，通讯也是宋鹏老师）。

当然上面那篇论文更重要的贡献是在结构稳定与平衡方面。论文对输入的物体给出了设计每个块的方式，使得在组装的时候组装比较容易，这个工作非常有意思。

解组装 Disassembly 问题的常见分类

前四个分类是描述组装问题难度的重要指标，后面的论文中我们还会遇到。而自锁 interlocking 是描述一个组装的重要特征，也是一个重要的分类。

顺序性 Sequentiality

Maximum number of moving sub-assemblies w.r.t one another in any (dis)assembly operation

个人理解的顺序性指的是每个物块（组）可以从整体中按一个方向取下，不存在需要一次性需要两个物块按照不同方向同时用力才能取出的情况。从图片中我们可以看出来，上方的组合可以用两只手解决，而下方的需要三只手（两只手移动下面两块，一只手用来固定）。

单调性 Monotonicity

Need for intermediate placement operations for at least one part of the assembly

个人理解的单调性指的是某块物体的取出需要其他物块的移动，从而在操作顺序上存在了一个偏序关系。从图片中我们可以看到，上面的图片移动蓝色还是绿色都是无阻挡的，而下方的组合需要先把绿色块移走才能把蓝色的块取出来。

线性性 Linearity

All assembly operations involve moving a single part with respect to the rest of the assembly

个人理解的线性性指的是组合可以一块块取出。从图片中我们可以看到，上面的图片中蓝色块和绿色块可以独立取出，而下面的需要把蓝绿两块作为整体取出。

相干性 Coherence

Whether or not each part that is moved will touch the rest of the assembly

个人理解的相干性指的是每个物块的移除对当前状态是有影响的。从图片中我们可以看到，上面的图片由于是一个整体，某块的移除对当前状态自然是影响的，而下面的图中，移除了绿色块后，自然地形成了左右两部分，左边块的移除自然不影响右边的状态，所以这一块是不相干的。

自锁 Interlocking

An assembly is interlocking if only one movable part (key), while all other parts, as well as any subset of the parts, are immobilized

个人理解这里说的自锁描述的是组合可解，而且活动块只有一块，这一块取出后其他块才可以移动取出。从图中我们可以看到，左图中绿色和蓝色都可以直接取出，中间的只有绿色的可以取出，绿色取出钱其他块无法取出，右图中每块都不能正常取出。这也意味着这种结构存在一种稳定性，只要锁住活动块 key，就能保证整个结构是稳定的。

High Level Puzzle

贡献与创新

论文主要有以下几个贡献

• 给出了难度等级的准确定义，并给出了一个求解每个谜题难度计算的算法（虽然是 NP 完全的 BFS 算法）
• 给出了用于构造每一个块的迭代计算算法，并让难度维持在输入的难度上，此外还给出了基于已有迭代结果构造更大难度的 puzzle 算法
• 给出了将非立方体体素的物体进行形状优化，转化为规则体素结构的方法

理论上，pipeline 应该是先把 Mesh 网格进行优化，优化为可以打印的体素表示，再对体素进行分块处理。不过为了与论文同步，我们接下来我们将依次介绍每个贡献。

难度等级与难度计算

那既然叫做 High Level，那怎么去定义一个谜题的 level 呢？论文给出了业界常用的两个计算方法——按第一块取出的最少移动步骤数以及所有块相互分离所需的最小移动步骤数，并选取了前者作为论文所关心的难度指标（毕竟拿掉第一块之后可能后面的块拿出就会简单一些，当然这也确定了论文讨论是满足单调性 Monotonicity 的 puzzle，否则难度就是 1 了）。论文对此进行了详细的描述：

• 无论一次移动几个块，只要是按照一个方向同时移动，记一次移动
• 移除某个块记一次移动
• 一块无论移动多长的距离，记一次移动

而难度计算其实就是一个平凡的 BFS 方法，每一次设置一个状态，以状态和移动的关系构成一张无向图。在图中节点分为根节点（初始状态）、普通节点和目标节点（成功移除一块），而初始状态到目标节点的最短路径的边数正是难度等级数。这里我把论文中的伪代码贴在下方，就不再展开介绍了。

值得注意的是，对于 K 个物块来说，运动超过一半的物块相当于剩下的物块进行移动（运动的相对性），所以在枚举物块数量的时候不需要让单步移动的物块数超过一半$\lceil K / 2 \rceil$。

除了盲目的搜索以外，我们还要考虑到无解的情况，因此论文也给出了一个伪代码来解决问题无解（主要指的是上方 deadlock 的情况）。

谜题构造

如图所示，本节介绍的是迭代生成每个物块的方法。论文对生成的物块有以下的约束：

• 几何连通性：需要保证每一个物块的体素都是六连通的
• 大小均匀：需要保证每一块既不是太大又不是太小，设允许误差为$\delta$，总体素数为$M$，物块数为$K$，则约束每个块大小在$[(1-\delta)\lfloor M/K\rfloor],\...