Ink & Switch Programmable Ink Lab Notes

约束系统

发布日期：2023年秋季

作者：relax-pk 工作总结

在第二阶段开始时，我们不确定如何处理约束。根据过去的探索，约束似乎很有前景，但出了名的不可靠。一个好的约束系统可以统一并加强我们所寻求的动态媒介的许多关键方面。它将允许机械构造，如绳索和滑轮，感觉在物理上是正确的。它将允许一种计算模型，在代数公式和有形对象之间架起桥梁，例如根据参数表中的编辑而变化的建筑图纸。它将允许真正的双向计算，而不是我们在 Crosscut 中拥有的有限/有偏差的计算。

但是约束系统很难实现。它们往往会遇到以下问题：

在本阶段的早期，Alex 乐观地认为，通过一些努力，这些问题是可以克服的。几周后，他能够展示出非常有希望的结果。这种早期的成功建立在他早期关于 [propagation of knowns] 的工作基础上，以减少必须由求解器确定值的变量数量。然后，通过利用相等约束（更一般地，变量之间的任何线性关系 —— y=mx+b，其中 m 不为零），他进一步减少了求解器需要考虑的维度数量。

例如，考虑一个“导出”两个变量的角度约束：一个变量的值是角度的度数，另一个变量的值是弧度。虽然这些变量中的任何一个或两个都可能被其他约束引用或被用户调整，但就求解器而言，它们会折叠为一个变量——毕竟，一旦你知道其中一个的值，你就可以计算出另一个的值。

这种技术不仅仅是一种优化，使求解器能够更快地收敛到解决方案；它通常使求解器能够找到本来无法找到的解决方案。它还通过消除由重复状态导致的“漂浮感 (Floaty-ness)”，改善了我们原型的手感。更重要的是，这种技术还使我们能够避免在将重复或“不均匀”的约束添加到模型时发生崩溃 (blow-ups)。

为了说明这一点，假设用户在点 A 和 B 之间添加了一个角度约束，该约束引入了一个变量 θAB。现在考虑当用户添加另一个涉及相同点的角度约束时会发生什么，但这次方向相反。这种情况可能会导致不稳定的结构。我们的新约束系统会检测到这一点，并且不会添加第二个角度约束，而是引入变量 θBA 和线性关系 θBA = θAB + π。因此，对于求解器来说，没有任何变化：仍然只有一个变量 (θAB) 需要求解，并且只有一个约束需要满足。但对于用户来说，看起来有两个独立的角度约束。他们可以进一步约束 θBA，或者稍后在他们愿意时删除第二个角度约束。（我们很高兴地报告，我们在 第一阶段记录的所有不稳定结构 在我们的新约束系统中都是完全稳定的。）

我们为约束系统开发的另一个有用的技术是我们称之为“聚类 (clustering)”的技术，即将约束及其操作的变量划分为可以独立求解的 集群 (clusters)。（正如 Avi 指出的那样，这类似于某些物理引擎中的 模拟岛屿 (simulation islands) 的概念。）通过将求解器的工作负载分解为集群 (clusters)，我们减少了它需要考虑的维度数量，这导致了收敛方面的显着改进。聚类 (clustering) 还为我们并行化求解器提供了可能性 —— 这是我们在开始构建需要更好性能的更大项目/模型时可以探索的东西。

虽然这些分析和技术是我们约束系统的重要组成部分，但它们并不与特定的求解器选择相关联。这使我们可以自由地插入更好的选项，因为它们变得可用。除了 Alex 基于松弛的求解器之外，我们还尝试了几种基于梯度下降的求解器，这些求解器产生了更好的收敛性。第一个是来自 numericjs 的 uncmin。后来，我们找到了 Guillermo Webster 为他的 g9 项目修改的 uncmin 版本，这给了我们更好的结果。我们希望最终尝试 @Avi Bryant 的新求解器，该求解器使用自动微分（而不是数值微分）和 WebAssembly 来提高性能和稳定性。

通过重新构建系统中值的表示方式，可以获得进一步的收益。例如，与其将位置关系表示为发生在笛卡尔空间中（使用 x/y 坐标），不如将关系表示在极坐标空间中（使用角度/距离坐标）。