【Euro Graphics 2012】Iterative Im

2021-01-26 本文已影响0人离原春草

今天给大家分享的是EuroGraphics 2012年上发表的一篇利用多帧之间的数据关联来降低渲染消耗的技术方案，这里是原文传送。

0. Abstract

图形渲染中，通常每一帧都是完全从零开始绘制的，并没有对前面多帧的一些数据进行重用，但实际上由于多帧之间的连贯性，其实是可以通过对前面多帧的数据进行重用来提升渲染性能的。这篇文章介绍的就是这样一种被称之为Fixed Point Iteration（简称FPI）的技术方案，根据应用场景的不同，这里提出了具有两种不同性能表现的实现方案，且这种方案已经通过应用于生成VR另一视角的图像将帧率从30提升到了60证明了其相对于此前已有方案的优越性。

1. Introduction

现有多种利用前面多帧的信息来对当前帧渲染进行加速的方法，但是这些方法要么就是需要对geometry进行沉重的计算处理，要么就是需要对现有的渲染管线进行大尺寸的改造，都有着不小的代价。

而这篇文章则尝试通过图像处理的方法来对之前多帧的数据进行重用，提出了一种新的图像处理方法，用一个较小的代价来实现数据的重用，这种方法不需要对现有管线进行改造，影响非常有限。

2. Background

这里介绍了前人工作中的一些弊端与不足，细节就直接跳过了，对此有兴趣的请移步原文。

3. Method

这里的主要工作就是将原始某个视角下的framebuffer贴图 $I_s$ 转换成另外一个视角下的输出贴图 $I_w$ (warped image)，这一章的后面部分会详细介绍相关的实现细节。

3.1 Image Warp Definition

这一节主要介绍技术实施相关的术语。

$V:R^2 \rightarrow R^2$ 表示的是将某张2D贴图中的像素数据转换到另一张2D贴图中的变换向量，对于原始贴图中的某个点 $x_s$ ，经过这个变换后可以变成目标贴图中的某个点 $x_w$ ，这个转换过程可以用如下的公式来表示：
$x_w = x_s+V(x_s) ~~~~~~~~~~~~~~~~~~~~~~ (1)$

对于目标贴图中的某个点 $x_w$ ，我们希望能够在原始贴图中找到一个对应的点，当存在多个满足条件的源点时，我们会采用最小深度原则 $(z(x_s)$ 挑选出距离相机最近的那个点来使用。

Temporal Reprojectjion
时域上的reprojection向量通常是由motion vector（运动向量）来表示，运动向量通常是通过有限差分来模拟微分运算从而计算得到，这个向量可以通过如下的公式来表示：
$V_{temporal}(x_s, t) = tM(x_s) ~~~~~~~~~~~~~~~~~~~~~~ (2)$

其中， $M(x_s)$ 就是运动向量，而 $t$ 则是reprojection对应的时间差，根据二阶有限差分关系，我们可以使用泰勒展式得到近似的加速度向量 $A$ ，从而得到非线性运动的时域reprojection关系：
$V_{nonlinear}(x_s, t) = tM(x_s)+\frac{t^2}{2}A(x_s) ~~~~~~~~~~~~~~~~~~~~~~ (3)$

Spatial Reprojection
空域Reprojection对应的就是相机的移动导致的视点之间的映射关系，对于垂直于视线方向的移动而言，这个映射可以通过在图像上沿着反方向移动得到，整个计算过程给出如下：
$V_{spatial}(x_s,u,v) = (\frac{-u\lambda_{u}}{z(x_s)}, \frac{-v\lambda_{v}}{z(x_s)}) ~~~~~~~~~~~~~~~~~~~~~~ (4)$

其中(u,v)对应的是水平与垂直方向上viewport的移动距离，而 $(\lambda_u, \lambda_v)$ 则是投影矩阵对角线上的第一与第二个元素， $z$ 表示的则是当前像素的深度值。

General Warp Field
这里没有对Warp向量进行限制，唯一的约束在于能实时完成，因此可以很方便应用其他类似的向量Reprojection（没看懂这里想要表达什么）。

3.2 Fixed Point Iteration（FPI）

在这一节中，我们会重点介绍迭代类方法尤其是FPI是如何使用的，此外可以很清楚的看到FPI在这个问题上可以很快的收敛，在介绍相关的应用之前，我们会先介绍一下一些基本的行为模式（basic modes of behavior）。

Fixed Point Iteration Definition
为了表述方便，这里定义一个新的函数 $G:R^2 \rightarrow R^2$ ：
$G(x_s) = x_w-V(x_s) ~~~~~~~~~~~~~~~~~~~~~~ (5)$

用这个公式对公式1进行重写，得到：
$x_s = G(x_s) ~~~~~~~~~~~~~~~~~~~~~~ (6)$

凡是满足公式6的点 $x_s = x^*$ 就对应于函数G的一个fixed point（看起来就是函数与y=x函数的交点），按照下面的公式通过一系列的迭代就可以得到一系列的fixed points：
$x_{i+1} = G(x_i) ~~~~~~~~~~~~~~~~~~~~~~ (7)$

迭代的初始值为 $x_0$ ，经过一系列的迭代，可以生成一系列逼近fixed point的点，下一节会仔细介绍FPI方案的表现。

Iteration Behavior

Figure 1

Figure 1中给出了一个测试场景，在这个场景中一个球体会在一个静止的背景之前水平移动，出于简化考虑，我们这里先考虑球体水平方向的移动，此时 $y=y_w$ （如（c）所示），对应的运动向量见下半图所示。

具体的迭代行为表现跟点所在的水平坐标x有关系，对应不同的横坐标，其表现不一样，详细迭代过程见(d), (e), (f)子图（先随便找一个 $x_0$ ，之后取 $x_1 = G(x_0)$ ，以此类推，直到找到 $x_{i+1} \approx G(X_i)$ ），这几个子图中的 $G(x)$ 函数是按照公式5计算得到的。

因为 $x_w$ 不同，G函数也是不同的，因此会出现1d，1e，1f三种情况的G函数不同的表现。

这种迭代之所以有效是因为，当G函数处于y=x函数之上时，此时下一个迭代点会右移，否则会左移，这两种表现才是使得迭代不断靠近的原因。

Unique solution
当 $x_w$ 处于球体的左侧时，如图1d所示，不论 $x_0$ 在哪个位置，最终都会收敛到唯一的fixed point上

No Solutions
当 $x_w$ 处于球体上时，如图1e所示，此时y=x函数与G函数相交于G垂直下降的位置，此时没有准确解，此时迭代过程会一直在不连贯区域来回震荡。

Multiple Solutions
当 $x_w$ 处于球体右侧时，此时与y=x函数存在三个相交点，其中一个位于球体上，另一个位于球体右侧，还有一个位于不连贯位置，这种情况下，最终得到的解就与初始点 $x_0$ 有关了。

3.3 Iterative Warping with Heuristics

Figure 2

如果直接选择目标点 $x_w$ 作为起始点，对应上图a中#3情况的话，就会导致超出原始图像中球体区域的track丢失，如上图b所示。对于这种问题的一个简单的解决方案是将起始点向左移动 $\delta x$ 个像素（这个是手动设定的一个数值？这个数值取决于原始贴图与目标贴图中球体的重叠区域，对VR中的另一视角而言，这个数值可以通过深度与相机距离计算得到；对于时域变化的帧率提升应用场景而言，这个数值可以认为是对于所有像素固定的，取决于帧间视差的大小），使得初始点越过 $x^*$ 到达球体上，从而得到如c图所示的结果。

In-Painting
对于此前分析过的，当目标点位于球体上时，就找不到目标解，此时取不连贯区域的左右像素作为近似解，就有可能得到前景与背景两种答案，通过对深度进行比对，可以得到背景解，其结果可能就呈现出对周边像素的一个简单复制，对于不同位置的目标点，得到的背景解结果也会有所不同。

这种做法得到的效果的好坏取决于多个因素，包括不连贯区域的尺寸，受影响区域的视觉特点以及背景贴图的视觉特点等，在测试场景中得到的结果如上图中的d图所示。

当然，这其实是填洞算法的一种，如果认为这种方式不合适，还可以考虑对目标区域进行重绘这种极端的填洞算法。

3.4 Robust Iterative Warping

与前面介绍的诱发式初始点选择算法不同，这里来介绍一下在特定的情景下肯定能够保证FPI的收敛性的结果（？）并据此剔除一种鲁棒的迭代式贴图变换算法。

Fixed Point 定理
假设函数G在靠近某个解 $x^*$ 的某个凸区域R时的的斜率幅度小于1，且假设迭代起始点选在R中某点，那么FPI肯定可以收敛到 $x^*$ 。

对G函数的斜率的限制可以保证不会出现Figure1 f图中 $x_1^*$ 的情况，同时虽然会出现e图中 $x*$ 的交点，但是不会像e图中一样那么陡峭。（没太看懂这段话）

这里将G函数的斜率用收敛项 $\rho$ 来表示，附录A中提供了一个更为准确的定义，将之推广到2D中，可以得到如下的公式：
$\rho = max_i{(|\lambda_i| < 1)} ~~~~~~~~~~~~~~~~~~~~~~ (8)$

其中 $\lambda_i$ 指的是G函数Jacobian矩阵的特征值（2x2矩阵的偏微分），后面章节我们会以 $\rho < 1$ 作为收敛条件。

Figure 3

上图给出了实际情况中这种收敛条件的一个结果展示，这里的场景中有两个运动的球体，背景是静止的，这两个球体最后会重叠起来，由于重叠的原因，部分目标点可能会对应于多个解，cdef图对应的就是多个解的位置描述。

为了清晰的辨认，这里将斜率小于1的区域标注为绿色，其他区域标注为红色，根据前面的定理，绿色区域只要选好初始点肯定是可以收敛的。

Sampling Strategy
虽然cubic spline插值采样能够得到更高的精度，但是出于简单考虑，这里选择的是bilinear插值算法。

在不连贯区域（比如物体几何边缘）进行插值目的是为了填补孔洞，在离散信号中对这种不连贯区域进行识别本身就是比较困难的事情，有人给出了一种利用如法线深度等几何信息来进行识别的方法，不过这里选择的是前面所说的收敛条件（即斜率），如果有4个像素（连续的？）都不满足这个条件的话，那么FPI肯定是不能收敛到一个可用解的，Figure 4给出了一维情况下的重建方案。

Figure 4

对于图a中 $x_1, ~ x_2$ 直接连接，会导致斜率超过1，这就不满足之前的收敛条件，为了解决这个问题，这里直接通过外插值将两点轨迹往外做一点延伸，如图b所示。

Robust Warp

Figure 5

上面这张图给出了鲁棒迭代（Robust iteration）Warp的实现过程，原始贴图按照四叉树的方式不断细分，直到细分后的每个四边形都不会包括（原文是straddle，跨越）Figure 1f中的垂直上升/下降这种不符合斜率小于1条件的区域（总会有个quad包括？最小化到一个像素为止），划分结果如图a所示；之后进行reprojection的时候，会对warped图像进行光栅化，如图b所示，对于光栅化后的每个像素，其起始迭代位置 $x_0$ 是通过当前像素在quad中的位置插值而来（没懂这句话的意思，插值的结果不就是 $x_w$ 所在位置？），最终迭代的结果如红色箭头所示，是肯定可以收敛到目标点 $x^*$ 上的，对于那些无法收敛的像素就直接扔掉不要了。

Adaptive Subdivision
最开始为原始贴图设置一些粗糙的quad划分，之后对这些quad进行不断细分，知道所有quad都不包含斜率超过1的部分，整个过程是放在geometry shader中实现的。为了实现对大块像素区域的快速查询（是否存在超出1的斜率部分），会预先对 $\rho$ 进行处理，进行数据简化（类似于mesh减面？）

Quad Warping
为了避免warped图像在quad边缘出现裂缝，就需要保证quad要大到能够完全包裹住像素对应的warped position（？），一种做法是对warped position（目标贴图数据）建立层级boundingbox，之后使用层级bb作为替代primitive，不过这里发现，直接计算quad的每个顶点的warped position，之后使用这些position组成的bb作为warped quad一样可以得到不错的表现，3.4节所讨论的采样策略以及Figure 4中描述的插值算法依然适用。

4. Implementation

Figure 6

这是用这篇文章的方法渲染的某个赛车游戏的VR视图，此外还是用这种方法成功将某个游戏的帧率从30hz提升到60hz，这两个应用场景中，都将迭代的次数限定为3，此外移除了收敛阈值的条件判断，并将这个迭代循环展开，最终给出了一个高性价比的表现。

warp field用的是3.1节中各种运动（物体运动+相机运动等）的线性组合，出于鲁棒variant的考虑，这个算法是很通用的，允许为每个图像设定一个warping kernel，且这个kernel还是与warp field解耦的（现在还是碎片化的，很难串起来），整个实现过程没有涉及到shader代码的优化等技术，因此还有进一步的性能提升空间。

前面介绍的时候，warping跟quad拆分是耦合在一起的，但是实际上是可以将quad拆分单独出来做成一个预处理过程，生成对应的几何信息，后面warping的时候直接取用的。在这种情况下，为了确保quad已经被拆分得足够充分了，这里使用reprojection范围内所有参数的最大值作为最终的收敛参数：
$\rho_{max}=max_{t,u,v} \rho ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(9)$

Algorithm 1 Complete Reprojection Pipeline

1: Obtain input data (colors, depths, motion vectors, ...)
2: Compute per-pixel converge terms ρ
3: Perform max-reductions to build convergence term hierarchy
4: Subdivide quad geometry
5: for each reprojected view parameters (t,u,v) do
6:   Clear temporary render target and depth buffer
7:   Bind FPI fragment program to GPU
8:   Warp and rasterize quad geometry
9:   Accumulate result onto final render target
10: end for

上面给出了warping处理的伪代码，由于GPU state的不兼容（累加需要alpha blend，而reprojection需要关闭blend以确保重叠区域能够正确的进行多次处理），这里会将reprojection的结果塞入到一个临时的RT中进行累加。

5. Results and Analysis

PlayStation 3， NVIDIA RSX GPU中720p (1280×720)分辨率，单个reprojection pass大概需要花费0.85ms，下表给出了其他在NVIDIA GeForce GTX580 GPU上720p的渲染结果，总共进行了64次统计，取了平均值，每个reprojection pass消耗大概是0.2ms。

Table 1

整个场景被分割成500万个polygon，并且在PS中添加了Perlin噪声（目的何在？），最终渲染消耗15.29ms，相对而言，同行的方法在处理阶段就花费了6.64ms，主要是因为geometry处理比较费劲。此外类似的warp方法消耗也要高到2.5ms，同样也是受限于geometry的处理，而本文方法中，单个reprojection只需要花费0.7ms，相对而言，速度提升了3.5倍。

Figure 8

上图给出了测试场景中各点的误差结果，在这个场景中既存在空间运动（水平+垂直），同时也有时间运动，具体结论就是本文给出的方法相对于前人方法没有变差，在一些特定情况下表现更好。

Figure 9

上图展示了多次迭代之后的误差变化。

Figure 10

上图给出了本文所介绍的方法在非线性运动情况下的表现，展示出了一定的非线性运动处理能力。

6. Discussion and Future Work

对前面内容的总结，略。