基于 FFT 的无互锁的装箱算法

在 3D 打印领域, 如何在打印机的工作空间 (通常是一个长方体) 中摆放物体是一个极为重要的问题. 首先, 装箱问题本身是一个 NP-Hard 的问题; 其次, 求解这一问题的过程中需要进行大规模的碰撞检测, 而非凸物体的碰撞检测没有特别高效的算法; 最后, 如何检测摆放好的物体之间是否会互相锁定 (也就是说在打印完成后是否能够分开) 也是一个重要的问题, 这一问题目前也没有有效的算法能解决.

本文将介绍一篇名为《Dense, Interlocking-Free and Scalable Spectral Packing of Generic 3D Objects》¹的文章, 它提出了一种基于快速傅里叶变换（FFT）的装箱算法. 这篇文章的主要贡献在于将 FFT 应用于基于体素的碰撞检测, 极大地提高了检测速度, 并通过这一算法提供了一种判断物体是否能够分离的方法.

基于 FFT 的碰撞检测

说到快速傅里叶变换, 就让人想到卷积. 这篇文章正是通过将碰撞检测表示为一个卷积, 来利用 FFT 实现高效的碰撞检测.

我们考虑将物体 $A$ 放置到打印机的工作空间中的过程, 此时其中有之前已经摆放好的若干物体, 记为 $\Omega$. 用示性函数来表示这两个物体:

$$ s_A(\mathbf{x}) = \begin{cases} 1, \text{ if } \mathbf{x} \in A, \\ 0, \text{ if } \mathbf{x} \notin A. \\ \end{cases} ~ s_\Omega(\mathbf{x}) = \begin{cases} 1, \text{ if } \mathbf{x} \in \Omega, \\ 0, \text{ if } \mathbf{x} \notin \Omega. \\ \end{cases} $$

那么我们可以将 $A$ 与 $\Omega$ 重叠部分的体积表示为一个积分:

$$ \int s_A(\mathbf{x}) s_\Omega(\mathbf{x}) \mathrm{d} \mathbf{x}. $$

进一步地, 如果我们对 $A$ 作一个平移 $q$, 就能得到 $A$ 位于 $q$ 时与 $\Omega$ 重叠部分的体积, 我们将其写成 $q$ 的函数:

$$ \zeta_{A, \Omega}(\mathbf{q})=\int s_A(\mathbf{x}-\mathbf{q}) s_{\Omega}(\mathbf{x}) \mathrm{d} \mathbf{x} $$

不难注意到这就是 $s_A$ 与 $s_\Omega$ 的卷积. 将全空间内的体素个数记为 $n$, 那么计算卷积的时间复杂度为 $O(n^2)$, 但如果我们使用快速傅里叶变换, 就能将时间复杂度降低到 $O(n \operatorname{log} n)$.

上图中示意了用快速傅里叶变换计算卷积的过程, 包括了将原函数变换到频域 (时间复杂度 $O(n \operatorname{log} n)$), 进行逐点相乘 ($O(n)$), 再从频域变换到时域 ($O(n \operatorname{log} n)$) 的过程. 最后一张图中 $\zeta_{A, \Omega} = 0$ 的点就是使得 $A$ 与 $\Omega$ 不重叠的位置.

装箱策略

该文章中给出的装箱算法是基于一种启发式的贪心策略: 将物体按照包围盒的体积从大到小依次放入打印机的工作空间中, 每次摆放一个物体的时候都让它与已经摆放好的物体尽可能紧密, 并且尽可能总高度较小.

我们这样来描述物体 $A$ 是否摆放得足够紧密:

$$ \rho_{A, \Omega}(\mathbf{q})=\int s_A(\mathbf{x}-\mathbf{q}) d(\mathbf{x}, \Omega) \mathbf{d} \mathbf{x} $$

其中 $d(\mathbf{x}, \Omega)$ 是 $\mathbf{x}$ 到 $\Omega$ 的距离. 这实际上就是 $A$ 中的点到 $\Omega$ 的距离的平均, 当 $A$ 距离 $\Omega$ 越近的时候自然有 $\rho_{A, \Omega}$ 越小. 此外, 这也是一个可以通过 FFT 来快速计算的卷积运算, 因此它的计算也非常快.

这样我们就能得到一个目标函数:

$$ \sigma_{A, \Omega}(\mathbf{q})=\rho_{A, \Omega}(\mathbf{q})+h(\mathbf{q}) $$

其中 $h(\mathbf{t})=p \mathbf{q}_z^3$ 是高度的惩罚项, $q$ 和 $3$ 都是由实验给出的常数.

在放置每一个物体 $A$ 时, 只需寻找 $\mathbf{q}^*=\underset{\mathbf{q}}{\arg \min }\left\{\sigma_{A, \Omega}(\mathbf{q}) \mid \zeta_{A, \Omega}(\mathbf{q})=0\right\}$ 即可. 此外, 可以将 $A$ 旋转几次 (用欧拉角进行采样) 并重复以上过程, 以得到更好的结果.

检测物体之间的互相锁定

Flood-Fill 分离

如下图所示, 根据 $\zeta_{A,\Omega}$ 的值, 可以确定我们能在哪些位置摆放物体 $A$, 我们将这些位置的集合记为 $\mathcal{R}$. 如果对于某一个可行的点 $\mathbf{q} \in \mathcal{R}$, 存在一条 $\mathcal{R}$ 中的道路通向打印机工作空间的边界, 那么我们就可以将摆放在 $\mathbf{q}$ 的 $A$ 沿着这条道路移出工作空间.

寻找这条路径的方法就是写在算法名字的字面上: 用水灌满整个工作空间 (广度优先遍历), 最后水能到达的地方就是存在一条路径的地方.

不难注意到, 这一算法检测的条件仅仅是一个充分条件, 它只支持检测是否能通过平移来分离物体, 而不支持旋转操作. 论文作者声称这并不是一个缺点, 因为这避免了过于复杂的分离方式 (避免了造出一个鲁班锁的情形).

Ray-Casting 分离

在实验中, 作者观察到很大一部分的物体都可以通过一次沿坐标轴方向的平移来分离, 因此采用了这一算法来检测这样的物体.

这一算法来自于《DESIA: A General Framework for Designing Interlocking Assemblies》. 这篇文章中提出了用有向遮挡图 (Directional Blocking Graph) 来检测互锁的方法. 如下的示意图来自文章作者在中科大的《计算机图形学前沿》课程所作的报告.

如下图所示, 有向遮挡图是指, 对于一个固定的方向, 和摆放好的几个物体, 如果两个物体之间有直接的遮挡关系, 那么就有在前的物体指向被遮挡的物体的一条边, 这样的边构成了一张有向遮挡图.

在这样的一张图中, 强连通分量 (Strongly Connected Component) 中的物体就是无法沿着这一方向被分离的一组物体. 反之, 如果一个强连通分量中恰有一个结点, 那么就意味着这一物体可以被沿着这一方向分离.

例如下图中, $+x$ 方向上, 整张图内只有一个强连通分量, 因此谁也不能和其它的分离; $+y$ 方向上, P5 和其它的物体分别是两个强连通分量, 因此我们能也仅能将 P5 分离.

总结

这篇文章提出的算法, 可以说是一个非常优秀又非常直观的算法. 此外, 用碰撞检测的结果来检测互锁也是相当厉害且自然的做法. 不过, 这个算法的核心算是比较简单的, 这样简单的算法在 2023 年才被发表, 实在是有些令人惊讶.