渲染

Real-time Rendering 第十九章 加速算法(上)

Spread the love

关于计算机的一个伟大传奇是,有一天我们将有足够的处理能力。即使在相对简单的应用程序(如文字处理)中,我们也发现附加的功能可以应用于各种功能,如即时拼写和语法检查、反别名文本显示和听写。

在实时渲染中,我们至少有四个性能目标:每秒更多的帧数,更高的分辨率和采样率,更真实的材料和灯光,以及增加几何复杂度。通常认为每秒60-90帧的速度已经足够快了。即使运动模糊可以降低图像质量所需的帧速率,但在与场景交互时仍然需要一个快速的速率来最小化延迟[1849]。

今天,我们有4k显示器,分辨率3840×2160;现有分辨率为7680×4320的8k显示器,但尚未普及。4k显示器通常每英寸约有140-150个点(DPI),有时也称为每英寸像素(PPI)。手机显示屏的分辨率最高可达400 DPI。目前,许多打印机公司提供的分辨率为1200 DPI,是4k显示器像素的64倍。即使在屏幕分辨率有限的情况下,反走样也会增加生成高质量图像所需的样本数量。正如在第23.6节中所讨论的,每个颜色通道的比特数也可以增加,这就需要更高的精度(因此也更昂贵)的计算。

正如前面几章所示,描述和计算对象的材质可能在计算上很复杂。光和表面相互作用的建模可以吸收任意高的计算能力。这是真的,因为一幅图像最终应该是由从光源到眼睛的无数条路径上的光的贡献所形成的。

帧速率、分辨率和阴影总是可以变得更加复杂,但是增加其中任何一种都会导致收益递减。然而,场景复杂度并没有真正的上限。一架波音777飞机的渲染图包括13.25万独特部件和300多万个紧固件,生成一个包含5亿多个多边形的多边形模型[310]。参见图19.1。即使这些物体由于体积小或位置小而没有被看到,也必须做一些工作来确定情况是否如此。如果不使用技术来减少所需的计算量,z缓冲和光线跟踪都无法处理此类模型。我们的结论是:加速算法总是需要的。

在这一章中,我们提供了一种加速计算机图形绘制的算法,特别是大量几何图形的绘制。许多这类算法的核心是基于空间数据结构的,下一节将对此进行描述。基于这些知识,我们继续使用筛选技术。这些算法试图快速确定哪些对象是可见的,需要进一步处理。LOD技术降低了呈现剩余对象的复杂性。本章末尾,我们讨论了渲染大型模型的系统,包括虚拟纹理、流、转码和地形渲染。

19.1 空间数据结构 Spatial Data Structures

空间数据结构是在n维空间中组织几何结构的结构。本书只使用了二维和三维结构,但是这些概念通常可以很容易地扩展到更高的维度。这些数据结构可用于加速关于几何实体是否重叠的查询。这种查询用于各种各样的操作,例如筛选算法、相交测试和光线跟踪,以及碰撞检测。

空间数据结构的组织通常是分层的。这意味着,粗略地说,最顶层包含一些子元素,每个元素定义自己的空间卷,而空间卷又包含自己的子元素。因此,结构是嵌套的,具有递归性质。这个层次结构中的一些元素引用了几何学。使用层次结构的主要原因是,不同类型的查询得到更快,通常一个进步从O (n) O (log n)。也就是说,与其搜索所有n对象,我们访问一小部分在执行操作,比如寻找最接近的对象在一个给定的方向。空间数据结构的构建时间可能很昂贵,并且取决于数据结构中几何结构的数量和所需的数据结构质量。然而,该领域的重大进展大大缩短了构建时间,在某些情况下可以实时完成。通过延迟评估和增量更新,可以进一步缩短构建时间。

BSP树和八叉树(octrees)是基于空间细分的数据结构。这意味着场景的整个空间被细分并编码在数据结构中。例如,所有叶子节点的空间的并集等于场景的整个空间。通常,叶节点的卷不会重叠,只有一些不太常见的结构(如松散的八叉树)例外。BSP树的大多数变体都是不规则的,这意味着空间可以被更任意地细分。八叉树是规则的,这意味着空间以统一的方式分割。尽管有更多的限制,但这种一致性通常可以成为效率的一个来源。另一方面,包围体层次结构不是空间细分结构。相反,它包围了几何对象周围的空间区域,因此BVH不需要在每一层包围所有空间。

下面将介绍BVHs、BSP树和八叉树,以及场景图,场景图是一种更关注模型关系而不是高效渲染的数据结构。

19.1.1 Bounding Volume Hierarchies(BVH)

Bounding Volume 卷(BV)是包含一组对象的体积。BV的概念是它应该是一个比包含的对象简单得多的几何形状,因此使用BV的测试可以比使用对象本身快得多。BVs的例子有球体、轴向对齐的边界框(aabb)、定向边界框(obb)和k-DOPs。定义见第22.2节。BV不会对渲染的图像做出视觉上的贡献。相反,它被用作代替有界对象的代理,以加速渲染、选择、查询和其他计算。

对于三维场景的实时渲染,层次视图截锥剔除通常使用包围体层次结构(章节19.4)。场景以层次树结构组织,由一组连接的节点组成。最上面的节点是根,它没有父节点。内部节点有指向其子节点(即其他节点)的指针。因此,根是一个内部节点,除非它是树中的唯一节点。叶子节点持有要呈现的实际几何图形,它没有任何子节点。树中的每个节点(包括叶子节点)都有一个包围体,该包围体将几何图形包围在其整个子树中。您还可以决定将bv排除在叶子节点之外,而将它们包含在每个叶子节点之上的内部节点中。这个设置就是名称包围卷层次结构的起源。每个节点的BV包含子树中所有叶节点的几何形状。这意味着根节点有一个包含整个场景的BV。图19.2显示了BVH的一个示例。注意,一些较大的边界圆可以做得更紧,因为每个节点只需要在其子树中包含几何图形,而不需要包含后代节点的bv。对于包围圆(或球体),形成这种更紧密的节点可能很昂贵,因为子树中的所有几何形状都必须由每个节点进行检查。在实践中,节点的BV通常通过树的“自底向上”形成,方法是生成一个包含其子节点BV的BV。

BVH的底层结构是树,在计算机科学领域,关于树数据结构的文献非常丰富。这里只提到几个重要的结果。如需更多信息,请参见Cormen等人的《算法导论》[292]一书。

考虑一个k-ary树,即每个内部节点都有k个子节点的树。只有一个节点(根)的树的高度为0。根的叶节点的高度为1,以此类推。平衡树是指所有叶节点都位于h或h – 1高度的树。一般来说,高度h,平衡树的⌊logk n⌋,其中n是节点的总数在树上(内部和树叶)。注意,k值越高,树的高度就越低,这意味着遍历树需要的步骤越少,但是在每个节点上也需要做更多的工作。二叉树通常是最简单的选择,并且能够提供合理的性能。然而,有证据表明更高的k(例如,k = 4或k = 8)对于某些应用程序具有更好的性能[980,1829]。使用k = 2、k = 4或k = 8可以简化树的构造;只要沿着k = 2的最长轴,k = 4的最长轴,k = 8的所有轴再细分。其他的k值更难构成性能良好的树。更高数字的树,例如,k = 8,每个节点的子节点往往喜欢从性能的角度而言,因为他们减少平均树深度和间接的数量(从父节点到子节点的指针)。

BVHs非常适合执行各种查询。例如,假设一条射线应该与一个场景相交,并且应该返回找到的第一个交集,就像阴影射线的情况一样。要为此使用BVH,测试从根开始。如果射线错过了它的BV,那么射线就错过了BVH中包含的所有几何形状。否则,测试将继续递归地进行,即测试根的子节点的bv。一旦射线错过了BV,测试就可以终止在BVH的子树上。如果射线击中叶节点的BV,则根据该节点的几何形状对射线进行测试。性能的提高部分来自于用BV测试ray的速度很快。这就是为什么像球体和盒子这样的简单物体被用作BVs。另一个原因是BVs的嵌套,它允许我们避免测试由于树的早期终止而导致的大区域空间。

通常最接近的交叉点,而不是第一个发现的交叉点,才是人们想要的。唯一需要的额外数据是遍历树时发现的最近对象的距离和标识。当前最近的距离也用于在遍历过程中剔除树。如果一个BV是相交的,但是它的距离超过了目前发现的最近的距离,那么BV可以被丢弃。在检查父框时,我们将所有子bv交叉,并找到最近的。如果在这个BV的后代中发现一个交集,则使用这个新的最近距离来剔除是否需要遍历其他子节点。可以看到,与BVHs提供的这种粗略排序相比,BSP树比普通BVHs有一个优势,即它可以保证前后顺序。

BVHs也可以用于动态场景[1465]。当BV中包含的对象移动时,只需检查它是否仍然包含在其父BV中。如果是,那么BVH仍然有效。否则,将删除对象节点并重新计算父节点的BV。然后递归地将节点从根节点插入到树中。另一种方法是增长父节点的BV,以便根据需要递归地将子节点保持在树上。无论使用哪种方法,随着执行的编辑越来越多,树都可能变得不平衡和效率低下。另一种方法是将BV设置为物体在一段时间内运动的极限。这称为时间边界卷(temporal bounding volume)[13]。例如,一个钟摆可以有一个包围被它的运动扫出的整个体积的包围盒。还可以执行自底向上的重新编译[136],或者选择树的某些部分重新适应或重新构建[928,981,1950]。

要创建BVH,首先必须能够计算围绕一组对象的紧BV。本主题将在第22.3节中讨论。然后,必须创建BVs的实际层次结构。有关BV构建策略的更多信息,请参见realtimerendering.com的碰撞检测章节。

19.1.2 BSP树—— BSP Trees

二进制空间分区树,简称BSP树,在计算机图形学中存在两个明显不同的变体,我们称之为轴向对齐和多边形对齐。树的创建方法是使用一个平面将空间分成两部分,然后将几何图形分成这两个空间。这个除法是递归地做的。一个有价值的特性是,如果以某种方式遍历BSP树,则可以从任何角度对树的几何内容进行前后排序。这种排序对于轴向对齐的bsp是近似的,对于多边形对齐的bsp是精确的。注意,轴向对齐的BSP树也称为k-d树

轴对称BSP树——Axis-Aligned BSP Trees (k-D Trees)

创建一个轴向对齐的BSP树,如下所示。首先,整个场景被封装在一个轴向对齐的包围框(AABB)中。然后递归地将这个框细分为更小的框。现在,考虑任意递归级别的框。选择盒子的一个轴,生成一个垂直的平面,将空间分成两个盒子。有些方案固定了这个划分平面,这样就可以将盒子精确地分成两半;另一些则允许切面改变位置。通过改变平面位置,称为非均匀细分,得到的树可以变得更加平衡。对于一个固定的平面位置,称为均匀细分,节点在内存中的位置由其在树中的位置隐式给出。

与平面相交的物体可以用多种方法处理。例如,它可以存储在树的这一层,或者成为两个子框的成员,或者被平面真正分割为两个单独的对象。在树级存储的优点是树中只有一个对象的副本,这使得对象删除非常简单。然而,被分割平面相交的小对象会停留在树的上层,这往往是低效的。将交叉的对象放置到两个子对象中可以为较大的对象提供更紧密的边界,因为所有对象都渗透到一个或多个叶子节点,但只有那些它们重叠的叶子节点。每个子框都包含一些对象,并且重复这个平面分割过程,递归地细分每个AABB,直到满足某个条件来停止该过程。有关轴向对齐的BSP树的示例,请参见图19.3。

粗略的前后排序是如何使用轴向对齐的BSP树的一个例子。这对于遮挡剔除算法(第19.7节和23.7节)以及通过最小化像素覆盖来降低像素着色器的开销都是有用的。假设当前遍历一个名为N的节点。这里,N是遍历开始时的根。检查N的分割平面,并在观察者所在平面的一侧递归地继续树遍历。因此,只有当整个树的一半被遍历之后,我们才开始遍历另一边。由于叶节点的内容没有被排序,而且对象可能位于树的许多节点中,所以这个遍历不会给出精确的前后排序。然而,它给出了一个粗略的排序,这通常是有用的。通过在节点平面的另一侧开始遍历,并与观察者的位置进行比较,可以获得粗略的前后排序。这对于透明排序非常有用。BSP遍历也可以用来根据场景几何进行射线检测。光线的来源只是简单地交换了观察者的位置。

多边形对称的BSP树——Polygon-Aligned BSP Trees

另一种类型的BSP树是多边形对齐的形式[4,500,501]。这种数据结构对于以精确排序的顺序渲染静态或刚体几何图形特别有用。这种算法在像《毁灭战士》(2016)这样的游戏中很流行,当时还没有硬件z缓冲区。它仍然偶尔使用,如碰撞检测和交叉测试。

在这个方案中,选择一个多边形作为分割器,将空间分成两半。也就是说,在根节点上,选择一个多边形。多边形所在的平面用于将场景中的其余多边形分成两组。任何被分度平面相交的多边形沿着交点线被分成两个单独的部分。现在在剖分平面的每个半空间中,选择另一个多边形作为剖分器,它只剖分半空间中的多边形。这是递归地完成的,直到所有多边形都位于BSP树中。创建一个高效的多边形对齐的BSP树是一个耗时的过程,通常计算一次并存储这些树以便重用。这种类型的BSP树如图19.4所示。一般来说,最好是形成一棵平衡的树,即,其中每个叶节点的深度相同,或者最多相差1。

多边形对齐的BSP树具有一些有用的特性。一个是,对于给定的视图,结构可以严格地从后向前遍历(或从前向后遍历)。这与按轴对齐的BSP树相比,后者通常只给出一个粗略的排序顺序。确定相机位于根平面的哪一侧。这个平面远侧的多边形集合就超出了近侧的多边形集合。现在有了远侧的多边形集合,取下一层的划分平面,确定相机在哪一侧。远端的子集也是离摄像机最远的子集。通过递归地继续,这个过程建立了严格的前后顺序,画家的算法可以用来渲染场景。画家的算法不需要z缓冲区。如果所有对象都是按前后顺序绘制的,则每个较近的对象都是在其后面的对象前面绘制的,因此不需要z-depth比较。

例如,考虑图19.4中的查看器v所看到的内容。不管观察方向和截锥体,v是左边的分裂面形成的,所以C、F和G B, D和e v C的分裂面比较,我们发现G的对面这个平面,所以它显示。对B平面的测试确定E应该显示在d之前。然后,前后顺序是G、C、F、A、E、B、D。相反,它提供了一个严格的闭塞顺序,一个细微的差别。例如,多边形F比多边形E更接近于v,尽管它在遮挡顺序上更靠后。

19.1.3 八叉树 Octrees

八叉树类似于轴向对齐的BSP树。一个盒子沿着三个轴同时被分割,分割点必须是盒子的中心。这将创建8个新框—因此命名为八叉树。这使得结构更加规则,从而使一些查询更加有效。

八叉树是通过将整个场景封装在一个最小的轴向对齐框中来构造的。该过程的其余部分本质上是递归的,并在满足停止条件时结束。与轴向对齐的BSP树一样,这些标准可以包括达到最大递归深度,或者在一个框中获得一定数量的原语[1535,1536]。如果满足条件,则算法将原语绑定到框中并终止递归。否则,它使用三个平面沿着主轴细分盒子,从而形成八个大小相同的盒子。每一个新盒子都要经过测试,并可能再细分为2×2×2个小盒子。在图19.5中,数据结构被称为四叉树,这在二维中得到了说明。四叉树是八叉树的二维等价,忽略第三个轴。在沿所有三个轴对数据进行分类几乎没有优势的情况下,它们非常有用。

八叉树可以以与轴对齐的BSP树相同的方式使用,因此可以处理相同类型的查询。实际上,BSP树可以提供与八叉树相同的空间划分。如果第一个空间的中间,x轴,然后两个子空间沿中间分割、y轴,最后那些子空间被划分在中间沿z, 8个大小相同的细胞形成的一样由一个应用程序是一个八叉树分裂。八叉树的一个效率来源是它不需要存储更灵活的BSP树结构所需的信息。例如,分裂平面位置是已知的,因此不需要显式地描述。这种更紧凑的存储方案还通过在遍历期间访问更少的内存位置来节省时间。轴向对齐的BSP树仍然可以更有效,因为由于需要检索分割平面的位置,额外的内存成本和遍历时间可以被更好的平面布局所节省的空间所抵消。没有整体最佳效率方案;这取决于底层几何结构的性质、如何访问结构的使用模式以及运行代码的硬件的体系结构等因素。通常,内存布局的缓存友好性的位置和级别是最重要的因素。这是下一节的重点。

在上面的描述中,对象总是存储在叶子节点中。因此,某些对象必须存储在多个叶子节点中。另一个选项是将对象放在包含整个对象的最小的框中。例如,图中的星形物体应该放在从左边开始的第二个插图的右上角框中。这有一个明显的缺点,例如,位于八叉树中心的(小)对象将放在最上面(最大)节点中。这是低效的,因为一个小对象被包围整个场景的盒子所包围。一种解决方案是拆分对象,但这会引入更多的原语。另一种方法是在每个叶子框中都放一个指向对象的指针,这会降低效率,增加八叉树编辑的难度。

Ulrich提出了第三种解决方案,松散八叉树loose octrees[1796]。松散八叉树的基本思想与普通八叉树相同,但是每个框的大小的选择是宽松的。如果一个普通盒子的边长是l,那么用kl代替,其中k > 1。图19.6显示了k = 1.5时的情况,并与普通八叉树进行了比较。注意,这些框的中心点是相同的。通过使用更大的框,可以减少跨越一个分裂平面的对象的数量,这样就可以将对象放置在更深层的八叉树中。对象总是只插入到一个八叉树节点中,因此从八叉树中删除对象是很简单的。使用k = 2可以获得一些优势。首先,对象的插入和删除是O(1)。知道对象的大小意味着立即知道它可以成功插入的八叉树的级别,完全适应一个松散的框。在实践中,有时可能将对象推到八叉树中更深的框中。同样,如果k < 2,如果不合适,对象可能必须被推到树上。

对象的质心决定将其放入哪个松散的八叉树框中。由于这些属性,这种结构很适合绑定动态对象,但代价是牺牲了一些BV效率,并且在遍历结构时失去了强排序顺序。而且,一个对象在帧与帧之间的移动通常只是轻微的,因此前一个框在下一帧中仍然有效。因此,松散八叉树中只有一小部分动画对象需要更新每一