Introduction of Interpolation


通常而言,数据会被安排在一个规则的网格上(数据值被写在二维或三维网格的顶点位置)或一条线上(对于一维数据的情形)。然而,一般来说程序需要处理网格上任意位置的值。如果采样位置本来就是网格顶点,我们可以直接使用对应位置的值,但如果采样位置落在其他的位置(一个格里的某个位置),考虑到那里并没有数据,我们需要用存储在那个格(Cell)的顶点位置的值做平均,为采样位置计算一个值出来。这种技术被称为插值,其关键的思想在于去“插”网格上固定位置的已有值,以计算出网格上任意位置的值。

在二维中,这种技术叫双线性插值,对应的三维中的版本被称为三线性插值。这两个名词中都有“线性”这一字眼,因为这些技术可以仅通过使用线性插值来实现。线性插值是这类方程:

\[a(1-t)+bt, \quad 0 \le t \le 1\]

这种方法很简单,仅仅需要两个值(\(a\) 与 \(b\))和少量的简单运算。然而,线性插值产生的“视觉”模式并不总是可接受的。可以使用更高阶的插值方法来提供更为平滑的结果,为了实现这种插值,往往需要考虑采样点周围多于一个格(Cell)的四个顶点的位置。这样一来,可以提供更好的结果,但由于考虑了更大的点集,使用了更加高阶的函数,其计算开销也会更高。用于“插”规则网格上的值的函数被称为 interpolant

当我们需要知道二维规则网格上任意位置的值的时候,可以使用双线性插值。这种网格可以是图像或者是 texture map。

举例来说,如果我们对绿色的点 c 位置处的值感兴趣,为了计算 c 处的值,我们首先在 \(x\) 方向上分别进行两次线性插值以得到 a 处和 b 处的值。然后,我们在 \(y\) 方向上插值得到 c 处的值。实际上,双线性插值不是线性过程,而是两个线性函数之积。如果采样点位于网格的边沿上,那么确实是线性过程,但对于其他位置而言都是二次过程。

双线性插值是一个模板,所以你可以插任何类型的数据(浮点数,颜色等等)。下面的例子中,给出了双线性插值的一个实现,该函数对图像的像素值(颜色)进行插值。

float bilinearInterp(const float& tx, const float& ty,
                     const Vec3f& c00, const Vec3f& c10,
                     const Vec3f& c01, const Vec3f& c11) {
    
    // linear interpolation along the x axis
    float a = c00 * (1 - tx) + c10 * tx;
    float b = c01 * (1 - tx) + c11 * tx;
    
    // the last linear interpolation along the y axis
    return a * (1 - ty) + b * ty;
}

双线性插值的好处是速度快,而且实现起来很简单。然而,它产生的结果可能不是我们真正需要的,这种时候可以考虑使用高阶的插值方法,例如使用 smoothstep 函数产生程序噪声(Procedural Noise)的技术。

三线性插值是双线性插值的直接扩展,它可以被看作两次双线性插值的一次线性插值。其中,对于这两次双线性插值,一次是对正面做的,一次是对背面做,为了计算 e 和 f 处的值,分别使用双线性插值进行计算。最后,在 \(z\) 方向上再做一次线性插值,即可得到 g 位置上的对应值。

至此,已经大致了解了线性插值,双线性插值,三线性插值的基本原理。这里需要额外补充的是,在实践中,具体的实现往往直接写成顶点数据的加权和形式。以上述的双线性插值为例,其实现也可以是:

float bilinearInterp(const float& tx, const float& ty,
                     const Vec3f& c00, const Vec3f& c10,
                     const Vec3f& c01, const Vec3f& c11) {
    return (1 - tx) * (1 - ty) * c00 +
           tx * (1 - ty) * c10 +
           (1 - tx) * ty * c01 +
           tx * ty * c11;
}