发现帮助计算机绘制复杂的二维动画

大约60年前，贝尔实验室的计算机科学家露丝·韦斯发表了一种开创性的算法，可以将三维物体从任何角度转换为二维图形。但她在描绘轮廓时遇到了问题——这个问题几十年来一直是计算几何学的一个谜。随着当今计算机动画的普及，“隐藏线问题”现在变得更加紧迫。

在计算机动画的关键步骤中，渲染3D模型为2D，最棘手的部分是轮廓这个看似简单的问题：3D物体的2D视觉轮廓。在理想的世界中，轮廓可以无限精确地描绘——但现实世界需要有限的值。因此，现代算法首先用微小的三角形“瓦片”覆盖整个3D模型，然后确定每个瓦片是面向观看者还是背向观看者。接下来，算法使用这些瓦片构建作为轮廓的线段。但是，当在程式化的动画中使用时，结果可能会产生错误的、闪烁的线条——研究人员不确定原因。

关于支持科学新闻报道

如果您喜欢这篇文章，请考虑通过以下方式支持我们屡获殊荣的新闻报道 订阅。通过购买订阅，您正在帮助确保有关当今塑造我们世界的发现和思想的有影响力的故事的未来。

事实证明，生成足够精细的三角形网格以避免每种此类错误是不可能的。正如 Meta Reality Labs 研究员 Stéphane Grabli（奥斯卡视觉效果奖提名者）解释说，“感觉上，通过足够细分，应该可以创建一个网格，从而可以对这些轮廓进行精确的可见性计算。事实证明这是错误的。” Grabli 补充说，由此产生的错误限制了非真实感插图风格的复杂性。

现在，在ACM Transactions on Graphics中，不列颠哥伦比亚大学计算机科学家陈曦和她的同事提出了一种名为 ConTesse 的算法解决方案，该方案专注于修复轮廓而不是网格。通过将算法生成的轮廓放大 1,600 倍，Liu 发现了轮廓线错误地相互交叉的小扭曲——因此，瓦片无法始终如一地识别为面向或背向观看者。“我用许多表面进行了实验，发现该算法在大多数表面上都失败了，”她说。

研究人员的新算法首先用线段追踪 3D 形状的边缘，然后将这个近似轮廓压缩到 2D，并尝试用三角形平铺其内部。在内部网格错误地自身交叉的任何地方，算法都会修改轮廓的该部分，例如通过解开扭曲或添加更精细的线段。然后，该算法使用修复后的轮廓重新生成网格，并将其全部投影回 3D 对象以进行最终的可见性检查。

该团队的创新之处在于意识到问题出在轮廓本身。Liu 说，以前不清楚这种无效轮廓甚至有可能存在，因此修复措施处理的是闪烁症状，而不是原因。未参与这项新研究的 Grabli 对此表示赞同：“该论文证明了早期解决方案为何无法奏效。”