皮克斯动画里的数学

作者 | 橘子老君

来源 | 橘子数学（ID：mathcrowd）

引言

当观看皮克斯出品的动画电影时，你是否被里面制作精细的3D人物造型所惊艳到?那些丰富的细节到底是如何制作出来的呢？橘子老君将在本文中为你揭示其背后的数学奥秘：计算机图形学(Computer Graphics)中几何建模(Geometric Modeling)的基础——曲线(面)细分(Subdivision)。

橘子老君将用高中生也能读懂的方式来讲解曲线细分技术，其中涉及如何用递推数列及矩阵乘法描述细分的过程，以及如何用数学方法得到最终的光滑曲线，希望大家喜欢。

曲线(面)细分

——让线条及表面变得更光滑

上面四张图展示了《怪兽大学》中的一个画面场景的制作流程，从最简单的分镜脚本(a)，到网格状的原型(b)、再到平面着色的预览图(c)、最终得到具有更多纹理和阴影的极具真实感的画面。

要完成一部动画电影的制作，显然是浩大的工程，涉及到很多专业技术，其中就包括我们今天要介绍的曲线(面)细分技术(以下简称 细分 技术)，这是一种通过不断分割不断调整的方式，使线条及表面变得更光滑的技术。

上图是皮克斯在1997年制作的动画短片《Geri's Game》中主角的一只手。实际上，在当时短片的制作过程中，是由该片的导演，恰好也是一位雕塑家，先雕刻出一个模型扫描进电脑(a)，然后再通过 细分 技术得到更真实的效果(b)。

本文为了简单起见将重点介绍曲线细分，空间曲面细分所用的原理与思想方法与平面曲线大致是相同，但是实现起来就要复杂一点。

如下图所示，不难想像一条连接正方形四个顶点的封闭曲线通过 细分 变为了一条光滑的类似内切圆的封闭曲线(实际上并不是内切圆)，而另一条不太规则的封闭曲线所围成的多边形通过 细分 变为了一条大致保留原来轮廓的光滑曲线。

下面橘子老君就来揭示上面所采用的 细分 技术的具体实施步骤(算法)。

细分：分割与平均

如上面动画所演示的，首先我们有一些点组成的有序列表(以下简称 点列 )，并用线段连接相邻两点，即得到一条初始曲线(为了回避对曲线边界情况的处理，本文仅讨论封闭曲线的情况，即认为点列首尾相邻)。 然后不断重复下述两个步骤。

• 分割

作出原曲线上各条线段的中点插入到原有的 点列 ,即完成对原曲线的分割。 此时 点列 中点的个数变为原来的两倍。

• 平均

计算 点列 中所有相近的一些点的加权平均，得到新的 点列 。比如计算所有相邻两个点的平均即中点，这些中点即组成新的点列。然后连结其中所有相邻两点得到调整后的新曲线。此时 点列 中点的个数并未发生改变，只是其中的点发生了改变(移动)。

当曲线完成一次 分割 、 平均 操作，也被称为曲线完成了一次 细分 。

具体地，请看上面的示意图，我们用蓝色标记点列中的点。从上左图到上右图完成了 分割 ，点列由原来正方形的四个端点变为八个点；从上右图到左下图完成了 平均 ，点列中的点即上右图中八个点相邻两点的中点。而右下图是重复多次 细分 操作后所得的曲线，不难想象在经过无穷多次操作后即会得到一条光滑曲线(多边形的边长无限趋近于0)。

上述 平均 的操作被称为“ 1-1法则 ”，另外还有“ 1-2-1法则 ”，即调整了参与加权平均操作点的个数及权重，变为由所有两两相邻的3个点参与权重为1,2,1的加权平均。

细分与递推数列

我们不妨把 个点组成的原始点列记为 ，经过一次 分割 后，将中点插入后得到 ，经过一次 平均 后得到 。

为了记号的简洁，接下来我们使用以下点的加法和数乘运算，

现有点 和点 ，我们定义:

• 

• 

显然，点的加法和数乘运算同样满足实数中的运算性质。 故我们可以得到点列 、 、 间的递推关系。

采用 1-1法则 ，综合两式可得，

一般地，我们把经过 次“分割-平均”后得到的曲线记作 ，则有

注意，当 时代入上式会出现 不存在的情况。由于本文讨论的是闭合曲线，我们可以补充定义 。一般地，我们可以补充定义 ，其中 为点列中点的个数。

通过观察 与 的递推关系可知， 中的点是 对应曲线上所有线段的靠近两端的两个四等分点。由此，在 所对应的曲线上，任意线段的中点都会落在 内，在下文中我们会给出证明。

细分与矩阵乘法

为了记号的简洁，我们把初始点列记作 ，经过一次 平均 后的点列记作 ，再经过一次 分割 后得到的点列记作 。

相信看过markov系列文章的读者，应该对类似递推数列与矩阵乘法的关系比较熟悉 ¹ ,为了帮助还不太熟悉矩阵乘法的读者迅速发现其中的联系，我们列出一些 分割 操作中点列 与点列 的递推式，

故得到

注意，这里的矩阵并不是方阵，而是 行 列的矩阵。

同理可得，采取 1-1法则 ，经过 平均 操作，点列 与 的关系。

利用矩阵乘法的结合律，得到 与 的递推关系。

其中

无穷多次细分后的极限

之前我们提到在经过无穷多次细分后，我们会得到一条光滑曲线。 当我们已知 平均 的规则后，其实并不需要利用计算机进行无穷多次递推或矩阵乘法计算来得到光滑曲线，相反多次计算会造成很大的累计误差。通过对矩阵的特征值分析，我们得到矩阵 次方，即递推数列的通项，也就是最终光滑曲线的精确解。

橘子老君并不想在本文中对矩阵的特征值和特征向量展开，所以会在不影响总体理解的情况下于下文中尽可能回避它们。

为了控制所研究问题的规模，我们这里可以仅考虑找到光滑曲线上一点的方法。而我们已经知道采用“ 1-1法则 ”的细分，每次都是作出原曲线所有线段的两个四等分点，下面我们来证明曲线上任意一条线段的中点都会落在极限位置。

设 、 是曲线上某线段的两个端点，那么经过一次细分后，该线段上两个四等分点 、 落在新曲线上，同时线段 仍然在线段 。经过 次细分后，我们就能得到点列 和 。要证明 、 的中点落在极限位置，即要证明 。

证明: 由递推关系，

两式相加，得到

两式相减，得到

故

由极限的运算性质解得，

得证。

其实我们研究一条线段上两个点的变化即等价于我们研究矩阵 前两行、前两列。显然上面这个问题太过简单，根本无法满足读者的胃口，所以我们再举一个采用“1-2-1法则”细分曲线的例子。这次我们目标同样是找到极限光滑曲线上的一点。如图(a)我们来看曲线上一个由相邻三点组成的局部，

如图，经过一次分割得到 、 ，而 、 、 经过取加权平均得到 ，即

代换等式右边的 、 得，其中 。

而 、 、 经过一次加权平均后仍然落在 位置，同理 也在平均后的曲线上。

此时即得到经过一次细分的曲线上的三点 、 、 。重复上述操作可得 、