视锥之内的故事(III):插值入门、线性插值、凸和重心插值


世界是连续的,数字系统是离散的。如何使用离散的系统模拟连续的世界?插值法(Interpolation)提供了一种可能。

基础

什么是插值?在纸上任给若干个点,然后用笔将它们平滑连接,这就是一种插值。连接若干点的方法无穷,而插值的方法也是无穷的。计算机擅长计算加减法和乘法,我们也喜欢多项式,所以多项式常常用于插值法。插值就是在寻找一个适合所有点的多项式空间正交基的线性组合,而组合的个数是无穷的。

关于多项式空间正交基的问题,我们在讨论一种曲线插值方法:非均匀有理B样条(NURBS)的时候会进一步说明。

用更数学一些的角度来说,我们是在把n维空间中的离散点集用一维输入的向量值函数来表示,把多维空间中的曲线降到一维表示。例如,考虑 $\mathbb{R}^2$ 中两个点 $(0,0)$ 和 $(1,1)$。向量值函数

$$\vec{f}(t) : \left\{\begin{aligned} x=t \\ y=t \end{aligned}\right.$$

就是这两个点的插值函数。其中t是一维的。

线性插值(Linear Interpolation)

给定空间任意两个点(这里用向量来表示)$\vec{a}$ 和 $\vec{b}$,我们用直线把他们连起来,就完成了线性插值。在这里,我们约定插值起始点对应的一维坐标为0,插值终点对应的一维坐标为1。那么我们可以得到线性插值的基本公式:

$$\vec{f}(t) = (1-t) \vec{a} + t \vec{b} \rm \qquad (III. 1)$$

如果我们要取得两个点之间的值,我们可以进一步规定 $t \geq 0$ ,这实际上蕴含了 $0 \leq t \leq 1$ 。又有$(1-t) + t = 1$,我们发现,这实际上是两个点的加权平均值!注意到,当t分别等于0和1时,我们能得到边界处的值(事实上这也是插值的必要条件:经过离散点)。

凸(Convex)

几乎没有教程在讲插值的时候突然莫名其妙地引入一个“凸”,但“凸”其实不仅相当重要,而且和插值有紧密的联系。我们先了解几个“黑话”:

III. 1 仿射组合(Affine Combination):我们称 $\sum_{i}^n b_i \vec{a_i}$ ,其中$\sum_{i}^n b_i = 1$ 为 $\vec{a_1}, \vec{a_2}, … \vec{a_n}$ 的一个仿射组合。

III. 2 凸组合(Convex Combination):我们称 $\sum_{i}^n b_i \vec{a_i}$ ,其中$\sum_{i}^n b_i = 1$ $b_i \geq 0, \forall b_i$ 为 $\vec{a_1}, \vec{a_2}, … \vec{a_n}$ 的一个仿射组合。凸组合就是加权平均值。

III. 3 凸集(Convex Set):凸集有很多定义,这里用一个最简单的。集合 $A$ 是凸集当且仅当对于 $\forall \vec{a}, \vec{b} \in A$ 都有 $\vec{a}$ 和 $\vec{b}$ 的凸组合在凸集中。也就是凸集关于凸组合封闭。

用直白一点的话说,在凸集中连接两个点的线条不可能穿出凸集。一些常见的凸集有:空间中的三角形、半空间、球和空间中的线段等。

III. 4 凸包(Convex Hull):包含空间中给定离散点的最小凸集称为凸包。

这样,我们就可以很简洁地说线性插值就是两个点的凸组合。

复合线性插值

观察一番 $\rm (III. 1)$ ,我们注意到其实曲线就是一个函数输出。那么我们可以轻易的把这个函数和一个新函数 $t = g(\theta)$ 复合。得到

$$\vec{f}(g(\theta)) = (1-g(\theta)) \vec{a} + g(\theta) \vec{b} \rm \qquad (III. 2)$$

注意,这里的g头部没有带箭头,因为g是 $\mathbb{R}$ 到 $\mathbb{R}$ 的映射。

通过复合线性插值,我们可以调整权重的变化趋势。这一点在后来的菲涅尔反射中会用到。

三角形的重心插值法(Barycentric Interpolation)

我们给线段加两条边得到一个三角形。三角形的三个顶点分别具有坐标,我们应该如何得到三角形内部某点的坐标?

先从三角形所在平面说起,三角形的三个顶点 $\vec{a}, \vec{b}, \vec{c}$ 确定了一个平面。我们不妨这样构建三角形:先确定一个顶点,然后以这个顶点为原点向平面上延申成三角形(类比之前的仿射空间思想)。用数学语言描述就是:

$$P(\beta, \gamma) = \vec{a} + \beta (\vec{b} – \vec{a}) + \gamma (\vec{c} – \vec{a}), \quad 0 \leq \beta \leq 1, 0 \leq \gamma \leq 1, \beta + \gamma \leq 1 \rm \qquad (III. 3)$$

对这个式子做变形,引入 $\alpha = 1-(\beta + \gamma)$ 。我们得到三角形上的任意点的坐标是这三个顶点的凸组合。

$$P(\alpha,\beta,\gamma) = \alpha \vec{a} + \beta \vec{b} + \gamma \vec{c}, \quad \alpha+\beta+\gamma = 1, \alpha, \beta, \gamma \geq 0 \rm \qquad (III. 4)$$

事实上,这个坐标不仅可以是三角形顶点本身的坐标,也可以代表颜色空间中的坐标。在世界空间中,如果我们已知三角形三个顶点的颜色,要让三角形内部的颜色随着空间而平滑变化,我们只要保留相同的 $\alpha, \beta, \gamma$,然后对颜色坐标进行凸组合即可。

结合凸集解释:由于三角形是一个凸集,这些凸组合自然而然地落在三角形内部。我们分别令$\alpha, \beta, \gamma = 0$,就可以得到顶点处的值。插值成立。

这个式子不仅可以用于插值,由于可以用它确定三角形内部点的坐标,在以后的光线投射(Ray casting)和光线追踪(Ray tracing)中也大有用处。


Leave a Reply

Your email address will not be published.