poster461

皮克斯动画里的数学:曲线细分术

5598
1
本文主要揭示动画制作中精细的人物造型背后的数学奥秘:计算机图形学中的曲线细分技术.
皮克斯动画里的数学:曲线细分术
8 人挑战成功
返回挑战
challenge-problem-icon

完成本期挑战需要达到:

本科数学水平

8 / 11 读者挑战成功
题目

现有区间,计算,得到区间,将这一过程称为对区间做了一次“分割” ;

计算,得到区间,将这一过程称为对区间的一次“平均”.

同时,称区间是区间经过次“细分”后得到的结果.

经过次细分后得到的区间,那么当时,区间的右端点的极限是__________.

选项

跳过看答案

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

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

曲线(面)细分——让线条及表面变得更光滑

image

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

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

image

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

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

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

image

image

下面我们就来揭示上面所采用的细分技术的具体实施步骤(算法).

细分:分割与平均

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

  • 分割

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

  • 平均

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

当曲线完成一次分割平均操作, 也被称为曲线完成了一次细分.

image

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

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

下面我们将这个细分过程数学化, 写出每一步操作前后点列之间的递推关系.

细分与递推数列

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

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

现有点和点, 我们定义:

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

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

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

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

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

细分与矩阵乘法

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

下面我们列出一些分割操作中点列与点列的递推式,

故得到

注意, 这里的矩阵并不是方阵, 而是列的矩阵.

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

利用矩阵乘法的结合律, 得到的递推关系.

其中

无穷多次细分后的极限

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

本文不对矩阵的特征值和特征向量展开, 所以会在不影响总体理解的情况下于下文中尽可能回避它们.

按照“1-1法则”的细分

为了控制所研究问题的规模, 我们这里可以仅考虑找到光滑曲线上一点的方法. 而我们已经知道采用“1-1法则”的细分, 每次都是作出原曲线所有线段的两个四等分点, 那么就有这样一个结论:

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

证明:

由递推关系,

两式相加, 得到

两式相减, 得到

由极限的运算性质解得,

得证.

其实我们研究一条线段上两个点的变化即等价于我们研究矩阵前两行、前两列. 显然上面这个问题太过简单, 根本无法满足读者的胃口, 所以我们再举一个采用“1-2-1法则”细分曲线的例子.

按照“1-2-1法则”的细分

这次我们目标同样是找到极限光滑曲线上的一点. 如图(a)我们来看曲线上一个由相邻三点组成的局部,

image

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

代换等式右边的得, 其中.

经过一次加权平均后仍然落在位置, 同理 也在平均后的曲线上.

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

故得到递推关系如下,

其中

利用特征值分析, 我们可以得到当时,

即得到, 当时,

是极限光滑曲线上的点.

我们也可以通过递推关系代入计算验证得到,

同理可得,