渲染

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效率,并且在遍历结构时失去了强排序顺序。而且,一个对象在帧与帧之间的移动通常只是轻微的,因此前一个框在下一帧中仍然有效。因此,松散八叉树中只有一小部分动画对象需要更新每一帧。Cozzi[302]指出,在将每个对象/原语分配给松散的八叉树之后,可以围绕每个节点中的对象计算一个最小的AABB,该AABB在那时本质上成为一个BVH。这种方法避免了跨节点分割对象。

19.1.4 缓存无关于缓存感知表示—— Cache-Oblivious and Cache-Aware Representations

由于内存系统的带宽与cpu的计算能力之间的差距每年都在增加,因此在设计算法和空间数据结构表示时考虑到缓存是至关重要的。在本节中,我们将介绍缓存相关(cache-aware或cache-conscious)和缓存无关cache-oblivious空间数据结构。缓存感知表示假定缓存块的大小是已知的,因此我们针对特定的体系结构进行优化。相反,缓存无关算法被设计为适用于所有类型的缓存大小,因此是独立于平台的。

要创建一个缓存相关的数据结构,您必须首先了解缓存块的大小对您的体系结构有多大。例如,这可能是64字节。然后尽量减小数据结构的大小。例如,Ericson[435]展示了仅对一个k-d树节点使用32位就足够了。这部分是通过占用节点32位值中最不重要的两个位来实现的。这两个位可以表示四种类型:叶子节点,或者在三个轴上分裂的内部节点。对于叶子节点,上面的30位持有指向对象列表的指针;对于内部节点,这些表示一个浮点分割值(精度稍低)。因此,可以在一个64字节的缓存块中存储一个包含15个节点的四层深度二叉树。第16个节点表示存在哪些子节点以及它们位于何处。详情见他的书。关键思想是,通过确保结构干净地打包以缓存边界,数据访问得到了很大的改进。

一个流行的、简单的、与缓存无关的树排序是van Emde Boas布局[68,422,435]。假设我们有一棵树,高度为h,目标是计算树中节点的缓存无关布局或排序。关键思想是,通过递归地将层次结构拆分成越来越小的块,在某种程度上,一组块将适合缓存。这些块在树中彼此相邻,因此缓存的数据的有效时间将比我们简单地从上到下列出所有节点的有效时间长。这样一个简单的列出会导致内存位置之间的巨大跳跃。

我们用v(T)表示T的van Emde Boas分布。这个结构是递归定义的,树中单个节点的布局就是节点本身。如果有多个节点T,树是分裂的一半高度,⌊h / 2⌋。最顶层⌊h / 2⌋水平放在树表示T0,和子树开始T0的叶节点表示T1,。树的递归性质描述如下:

注意,所有的子树Ti(0≤i≤n)也由上面的递归定义。这意味着,例如,T1必须被分割为它的一半高,以此类推。参见图19.7中的示例。

通常,创建缓存无关的布局由两个步骤组成:集群和集群的排序。对于van Emde Boas布局,集群由子树给出,其顺序在创建顺序中是隐式的。Yoon等人[1948,1949]开发了专门为有效的包围体层次结构和BSP树设计的技术。他们开发了一个概率模型,该模型既考虑了父代和子代之间的位置,也考虑了空间位置。这样做的目的是通过确保访问子节点的开销不高,从而在访问父节点时最小化缓存丢失。此外,相互接近的节点按顺序更紧密地分组。提出了一种聚类概率最大的贪婪算法。在不改变底层算法的情况下,性能得到了大幅度的提高——只是BVH中节点的顺序有所不同。

19.1.5 Scene Graphs —— 场景图

BVHs、BSP树和八叉树都使用某种树作为它们的基本数据结构。不同之处在于它们如何划分空间和存储几何图形。它们还以分层的方式存储几何对象,而不是其他任何东西。然而,渲染一个三维场景不仅仅是几何。动画、可视性和其他元素的控制通常使用场景图执行,在glTF中称为节点层次结构。这是一个面向用户的树形结构,可以使用纹理、转换、细节级别、呈现状态(例如,材质属性)、光源和其他合适的内容来增强。它由一棵树表示,并且按照一定的顺序遍历这棵树来渲染场景。例如,光源可以放在内部节点上,这只影响子树的内容。另一个例子是在树中遇到某种材质。该材质可以应用于该节点子树中的所有几何图形,也可以被子节点的设置覆盖。关于场景图中如何支持不同级别的细节,请参见第861页的图19.34。从某种意义上说,每个图形应用程序都使用某种形式的场景图,即使图只是一个根节点,其中显示一组要显示的子节点。

对象动画的一种方法是对树中内部节点进行变换。然后场景图实现转换该节点子树的全部内容。由于转换可以放在任何内部节点中,所以可以执行分层动画。例如,汽车的轮子可以旋转,汽车作为一个整体可以向前移动。

当多个节点指向同一个子节点时,该树结构称为有向无环图(directacyclic graph, DAG)[292]。术语非循环意味着它必须不包含任何循环或周期。所谓有向,是指当两个节点通过一条边连接时,它们也按一定的顺序连接,例如从父节点到子节点。场景图通常是DAGs,因为它们允许实例化,即。,当我们想要复制一个对象的多个副本(实例)而不复制其几何形状时。图19.8显示了一个示例,其中两个内部节点对其子树应用了不同的转换。使用实例可以节省内存,并且gpu可以通过API调用快速渲染实例的多个副本(第18.4.2节)。

当物体在场景中移动时,场景图必须更新。这可以通过对树结构的递归调用来实现。转换在从根到叶的过程中更新。矩阵在这个遍历中相乘,并存储在相关节点中。然而,当变换被更新时,任何附加的bv都是过时的。因此,bv在从叶子返回到根的过程中会得到更新。过于松散的树结构极大地复杂化了这些任务,因此常常避免DAGs,或者使用有限形式的DAGs,其中只有叶节点是共享的。有关这个主题的更多信息,请参见Eberly的书[404]。还要注意,当使用基于javascript的api(如WebGL)时,将尽可能多的工作转移到GPU而尽可能少的反馈给CPU是非常重要的[876]。

场景图本身可以提供一些计算效率。场景图中的节点通常有一个边界卷,因此与BVH非常相似。场景图中的叶子存储几何图形。重要的是要认识到,完全无关的效率方案可以与场景图一起使用。这就是空间化(spatialization)的概念,在这个概念中,用户的场景图被一个另外的数据结构(例如BSP树或BVH)增强,这个数据结构是为不同的任务创建的,例如更快的筛选或挑选。大多数模型所在的叶节点是共享的,因此额外的空间效率结构的开销相对较低。

19.2 剔除技术——Culling Techniques

cull的意思是“从集群中删除”,在计算机图形学的上下文中,这正是cull技术所做的。flock是我们想渲染的整个场景,删除仅限于场景中那些不被认为对最终图像有贡献的部分。场景的其余部分提交到渲染管道。因此,可见性筛选这个术语也经常在渲染上下文中使用。但是,也可以对程序的其他部分进行筛选。例如碰撞检测(通过对屏幕外或隐藏对象进行不太精确的计算)、物理计算和人工智能。这里只介绍与渲染相关的筛选技术。这类技术的例子有背面剔除、视图截锥剔除和遮挡剔除。如图19.9所示。背面剔除剔除背对观察者的面。视锥剔除消除了视图截锥外的三角形组。遮挡剔除消除了由其他对象组隐藏的对象。这是最复杂的筛选技术,因为它需要计算对象如何相互影响。

实际的剔除在理论上可以发生在渲染管道的任何阶段,对于某些遮挡剔除算法,甚至可以预先计算。对于在GPU上实现的剔除算法,我们有时只能启用/禁用剔除函数,或者设置一些参数。渲染速度最快的三角形是从未发送到GPU的三角形。其次,管道筛选越早进行越好。剔除通常是通过使用几何计算来实现的,但绝不仅限于此。例如,算法也可以使用帧缓冲区的内容。

理想的剔除算法将只通过管道发送图元的精确可见集(exact visible set,EVS)。在本书中,EVS被定义为所有部分或全部可见的图元。其中一个允许理想剔除的数据结构是相位图(aspect graph),给定任何观点,都可以从中提取EVS[532]。创建这样的数据结构在理论上是可能的,但在实践中不可能,因为最糟糕的时间复杂度可能与O(n9)[277]一样糟糕。相反,实际算法试图找到一个集,称为潜在可见集(potentially visible set,PVS),这是对EVS的预测。如果PVS完全包含EVS,那么只丢弃不可见的几何形状,则PVS被认为是保守的。PVS也可能是近似的,其中没有完全包括EVS。因此,这种类型的PVS可能会生成不正确的图像。我们的目标是使这些错误尽可能小。由于保守的PVS总是生成正确的图像,所以通常认为它更有用。通过高估或近似EVS,思想是,PVS可以计算得更快。困难在于如何进行这些评估以获得总体性能。例如,一个算法可以处理不同粒度的几何,即、三角形、整个对象或对象组。当找到PVS时,将使用z-buffer渲染它,这将决定最终的每个像素的可见性。

请注意,有些算法为了提供更好的遮挡剔除,会对网格中的三角形重新排序。,同时减少了overdraw,并改进了顶点缓存位置。虽然这些都与筛选有一定的关系,但是我们会让感兴趣的读者参考参考文献[256,659]。在19.3-19.8节中,我们讨论了背面剔除(backface culling)、视锥剔除(view frustum culling)、portal剔除(portal culling)、细节剔除(detail culling)、遮挡剔除(occlusion culling)和系统剔除(culling systems)。

19.3 背部剔除 —— Backface Culling

假设您在一个场景中看到一个不透明的球体。大约一半的球体将不可见。从这个观察得出的结论是,不可见的东西不需要渲染,因为它对图像没有贡献。因此,不需要处理球体的背面,这就是backface culling背后的思想。这种类型的剔除也可以一次针对整个组进行,因此称为聚集背面剔除(clustered backface culling)。

所有的背面三角形是固体不透明物体的一部分,可以从进一步的处理中剔除,假设相机在外面,不穿透(即,近切面进入),对象。如果已知投影三角形的方向,例如屏幕空间中的顺时针方向,则一致定向的三角形(第16.3节)是朝后的。该测试可以通过计算二维屏幕空间中三角形的有符号面积来实现。负符号区域表示应该剔除三角形。这可以在屏幕映射过程完成后立即实现。

另一种确定三角形是否背对的方法是从三角形所在平面上的任意点(其中一个顶点是最简单的选择)到观察者位置创建一个向量。对于正交投影,眼睛位置的矢量被替换为负的视图方向,这对于场景是恒定的。计算这个向量和三角形法向量的点积。负的点积意味着这两个向量的夹角大于π/ 2弧度,所以三角形不是面对观众。这个测试相当于计算从观察者的位置到三角形平面的带符号距离。如果符号是正的,则三角形是正面朝上的。注意,距离只有在法线被标准化的情况下才会得到,但是这在这里并不重要,因为只对符号感兴趣。或者,应用投影矩阵后,在裁剪空间中形成顶点v = (vx, vy, vw),计算行列式d = |v0, v1, v2|[1317]。如果d≤0,则可剔除该三角形。这些筛选技术如图19.10所示。

Blinn指出,这两个测试在几何上是相同的[165]。从理论上讲,这些测试的不同之处在于计算测试的空间,而不是其他。在实践中,屏幕空间测试通常更安全,因为在视图空间中看起来稍微向后的边缘三角形在屏幕空间中可能稍微向前。这是因为视图空间坐标四舍五入为屏幕空间亚像素坐标。

使用OpenGL或DirectX之类的API,通常用几个函数来控制背面剔除,这些函数要么启用背面剔除,要么启用正面剔除,要么禁用所有剔除。请注意镜像转换(即镜像转换,负缩放操作)将后向三角形转换为前向三角形,反之亦然[165] (第4.1.3节)。最后,可以在像素着色器中找出一个三角形是否是正面的。在OpenGL中,这是通过测试gl front face来实现的,而在DirectX中,它被称为SV IsFrontFace。在此之前,正确显示双面对象的主要方法是渲染两次,首先选择背面,然后选择正面并反转法线。

关于标准的背面剔除的一个常见误解是,它将渲染的三角形数量减少了大约一半。虽然后脸剔除将删除约一半的三角形在许多对象中,它为某些类型的模型提供很少的增益。例如,室内场景的墙壁、地板和天花板通常是面向观众的,所以在这样的场景中,这些类型的背景相对较少。类似地,在地形渲染中,大多数三角形都是可见的,只有那些位于山丘或峡谷背面的三角形才能从这种技术中受益。

虽然背面剔除是一种避免对单个三角形进行栅格化的简单技术,但是如果可以通过一个测试来决定是否可以选择一组三角形,那么速度会更快。这类技术被称为聚集背面剔除算法,其中一些将在这里进行回顾。许多这类算法使用的基本概念是法锥[1630]。对于曲面的某些部分,会创建一个截锥,其中包含所有法线方向和所有点。注意,沿法线的两个距离需要截断圆锥。有关示例,请参见图19.11。可以看到,一个锥形被定义为一个正常的,n,半张角,α,和一个锚点,c,和一些抵消距离沿着正常的截断锥。在图19.11的右侧,显示了一个法锥的截面。Shirman和Abi-Ezzi[1630]证明,如果观察者位于前视锥内,则视锥内的所有面均为面向前方,后视锥亦是如此。Engel[433]使用了一个类似的概念,称为GPU剔除排除体(the exclusion volume for GPU culling)。

对于静态网格,Haar和Aaltonen[625]建议围绕n个三角形计算一个最小的立方体,并将每个立方体面分割为r×r“像素”,每个像素编码一个n位掩码,表示对应的三角形是否在该“像素”上可见。如图19.12所示。如果相机位于立方体的外部,则可以找到相机所在的相应的截锥,并可以立即查找其位掩码并知道哪些三角形是背对的(保守地说)。Haar和Aaltonen每个正方体面只使用一个位掩码,一次编码n = 64个三角形。通过计算位掩码中设置的位的数量,可以有效地为非剔除三角形分配内存。这项工作已用于刺客信条Unity。

接下来,我们将使用一个非截断的向量锥,在对比与图19.11中,所以它只被定义为一个中心点c, n,法线和一个角α。要计算这样一个由若干三角形组成的向量锥,取三角形平面的所有法线,将它们放在相同的位置,在包含所有法线的单位球面上计算一个最小圆[101]。作为第一步,假设我们要从一个点e开始,对锥体中原点相同的所有法线进行背面测试。如果下列条件成立[1883,1884],则法向锥体从e面朝后:

然而,这个测试只有当所有的几何都位于c时才有效。接下来,我们假设所有的几何都在一个圆心为c,半径为r的球体内

其中β= r / | | c−e | |。推导这个测试所涉及的几何关系如图19.13所示。量化法线可以存储在8×4位,这对于某些应用程序来说可能已经足够了。

作为这一节的结尾,我们注意到,对于运动模糊三角形(其中每个顶点在一个帧上都有一个线性运动)的backface剔除并不像人们可能认为的那么简单。随着时间的推移,顶点线性移动的三角形可以在一个帧的开始处向后转,然后向前转,然后再向后转,所有这些都在同一帧内。因此,如果在一个帧的开始和结束时,由于运动模糊的三角形是背对的,而剔除一个三角形,将会产生不正确的结果。Munkberg和Akenine-M¨oller[1246]提出了一种用线性移动三角形顶点替换标准背面测试中的顶点的方法。将试验改写为Bernstein形式,利用B’ezier曲线的凸性作为保守性试验。对于景深,如果整个镜头都在三角形的负半空间内(换句话说,在它的后面),则可以安全地选择三角形。

19.4 视锥剔除——View Frustum Culling

如2.3.3节所示,只需要渲染完全或部分位于视锥内的图元。加速渲染过程的一种方法是将每个对象的包围体与视锥进行比较。如果BV在截锥体之外,那么它所包含的几何图形可以在渲染中省略。相反,如果BV位于锥体内部或与锥体相交,则BV的内容可能是可见的,必须通过渲染管道提交。有关测试各种边界卷和视图截锥之间的交集的方法,请参见第22.14节。

通过使用空间数据结构,这种剔除可以分层应用[272]。对于包围卷层次结构,从根开始的前序遍历[292]就可以完成这项工作。每个具有包围体的节点都将根据截锥体进行测试。如果节点的BV位于截锥体之外,则不进一步处理该节点。树被修剪,因为BV的内容和子元素都在视图之外。如果BV完全位于截锥体内部,则其内容物必须全部位于截锥体内部。遍历继续进行,但是对于这样一个子树的其余部分不需要进一步的截锥测试。如果BV与截锥体相交,则继续遍历,并测试其子元素。当一个叶子节点被发现相交时,它的内容(即,其几何形状)通过管道发送。叶子的图元不能保证位于视图截锥内。图19.14显示了视图截锥剔除的一个示例。也可以对一个对象或单元格使用多个BV测试。例如,如果在单元周围发现一个球体BV与截锥体重叠,如果已知这个盒子比球体小得多,那么也有必要进行更精确(尽管更昂贵)的obb对截锥体测试[1600]。

对于“相交截锥”情况,一个有用的优化方法是跟踪BV完全位于哪个截锥平面内[148]。这些信息通常存储为位掩码,然后可以与相交点一起传递,用于测试这个BV的子节点。这种技术有时被称为平面掩蔽(plane masking),因为只有那些与BV相交的平面才需要对子节点进行测试。根BV最初将在所有6个截锥体平面上进行测试,但是随着后续测试的进行,每个子节点上进行的平面/BV测试的数量将会下降。Assarsson和M¨oller[83]注意到时间一致性也可以利用。剔除BV的截锥平面可以与BV一起存储,然后在下一帧中作为第一个测试剔除的平面。Wihlidal[1883, 1884]指出,如果视图截锥剔除是在CPU的每个对象级别上进行的,那么当在GPU上进行更细粒度的剔除时,就足以对左、右、底部和顶部平面执行视图截锥剔除。此外,为了提高性能,可以使用一个称为顶点点映射(the apex point map)的构造来提供更紧密的包围体。这在第22.13.4节中有更详细的说明。有时雾会在远处使用,以避免物体突然消失在远处的平面上的影响。

对于大型场景或某些相机视图,可能只会看到场景的一小部分,而且只需要通过渲染管道发送这一小部分。在这种情况下,速度的大幅提高是可以预期的。视图截锥剔除技术利用场景中的空间一致性,因为位于彼此附近的对象可以被封闭在一个BV中,而聚集在一起的BV可以分层聚集。

需要注意的是,一些游戏引擎并不使用分层的BVHs,而只是一个线性的BVs列表,每个BVs对应场景中的每个对象[283]。其主要动机是使用SIMD和多线程实现算法更简单,从而提供更好的性能。然而,对于某些应用程序,如CAD,大部分或所有的几何图形都在截锥内,在这种情况下,应该避免使用这些类型的算法。层次视图截锥体剔除仍然可以应用,因为如果一个节点在截锥体内部,它的几何形状可以立即绘制出来。

19.5 入口剔除 —— Portal Culling

对于体系结构模型,有一组以Portal Culling为名的算法。第一个这样的算法是由Airey等人提出的[17,18]。后来,Teller和S ‘ equin[1755, 1756]以及Teller和Hanrahan[1757]构建了更高效、更复杂的Portal Culling算法。所有Portal Culling算法的基本原理是,在室内场景中,墙壁通常充当大型遮挡器。因此,Portal Culling是一种遮挡剔除,将在下一节中讨论。这种遮挡算法通过每个门户(例如门或窗)使用视图截锥剔除机制。当穿过一个入口时,截锥体被缩小到与入口紧密贴合。因此,该算法也可以看作是视图截锥剔除的一种扩展。在视锥之外的门户将被丢弃。

Portal Culling方法以某种方式对场景进行预处理。场景被划分为单元,通常对应于建筑物中的房间和走廊。连接相邻房间的门窗称为portals。单元格中的每个对象和单元格的壁都存储在与单元格关联的数据结构中。我们还将信息存储在相邻单元格和将它们连接在邻接图中的门户上。Teller提出了计算这个图的算法[1756]。虽然这项技术在1992年被引入时就开始使用,但是对于现代复杂场景来说,实现流程的自动化是极其困难的。因此,定义单元格和创建图形目前是手工完成的。

Luebke和Georges[1090]使用了一种只需少量预处理的简单方法。惟一需要的信息是与每个单元关联的数据结构,如上所述。关键思想是,每个门户都定义了房间内外的视图。想象你正透过一扇门看到一间有三扇窗户的房间。门口定义了一个截锥体,您可以使用它来剔除房间中不可见的对象,并呈现那些可以看到的对象。您无法看到通过门口的两个窗口,因此可以忽略通过这些窗口可见的单元格。第三扇窗户是可见的,但部分被门框挡住了。只需要将单元格中的内容通过通道和此窗口发送到管道中。单元格渲染过程依赖于以递归方式跟踪这种可见性。

图19.15通过一个例子说明了Portal Culling算法。观察者或眼睛位于单元格E中,因此与其内容一起渲染。相邻的单元格是C、D和F。原始截锥体看不到单元格D的入口,因此在进一步处理中省略。单元格F是可见的,因此视图截锥体被缩小,以便通过连接到F的门户。然后,F的内容将与缩小的截锥体一起呈现。然后,检查F的邻近单元G在缩小的截锥上不可见,因此省略,而H是可见的。同样,截锥体随着H的入口而缩小,然后呈现H的内容。H没有任何没有访问过的邻居,所以遍历在这里结束。现在,递归返回到单元格C中的portal。将截锥体缩小到适合C的portal,然后使用视锥剔除在C中渲染对象。没有其他可见的portal,因此渲染完成。

每个对象在被渲染时可以被标记,以避免多次渲染对象。例如,如果一个房间有两扇窗户,那么该房间的内容将分别针对每个截锥体进行筛选。如果没有标签,一个通过两个窗口都可见的对象将被渲染两次。这不仅效率低下,还可能导致渲染错误,比如对象是透明的。为了避免必须清除每个帧的标记列表,每个对象在访问时都使用帧号进行标记。只访问存储当前帧号的对象。

一个很值得实现的优化是使用模板缓冲区进行更精确的筛选。实际上,使用AABB高估了portal;真正的portal很可能更小。模板缓冲区可用于屏蔽真实partal之外的呈现。类似地,可以为GPU设置一个围绕门户的剪刀矩形,以提高性能[13]。使用模板和剪刀功能还可以避免执行标记,因为透明对象可能渲染两次,但只会影响每个portal中的可视像素一次。

有关门户使用的另一个视图,请参见图19.16。这种形式的portal culling也可以用于为平面反射修剪内容(第11.6.2节)。左边的图片显示了一个从顶部俯瞰的建筑;白线表示截锥体随每个入口而减少的方式。红线是通过将截锥体反射到镜子上而形成的。实际的视图显示在右边的图像中,其中白色矩形是门户,而镜子是红色的。注意,只有在任何一个平截头内的对象才被渲染。其他转换可以用来创建其他效果,比如简单的折射。

19.6 细节以及简单三角形剔除 —— Detail and Small Triangle Culling

细节剔除是一种为了速度而牺牲质量的技术。细节剔除的基本原理是,当观察者处于运动状态时,场景中的小细节对渲染的图像贡献很少或没有贡献。当观察者停止时,通常禁用细节剔除。考虑一个具有包围体的对象,并将此BV投影到投影平面上。然后以像素为单位估计投影面积,如果像素数低于用户定义的阈值,则在进一步处理中省略该对象。因此,细节筛选有时称为屏幕大小筛选(screen-size culling)。细节剔除也可以在场景图上分层进行。这些类型的技术经常在游戏引擎中使用[283]。

在每个像素的中心有一个样本,小三角形很可能落在样本之间。此外,小三角形的栅格化效率相当低。一些图形硬件实际上会剔除样本之间的三角形,但当使用GPU上的代码进行剔除时(第19.8节),添加一些代码来剔除小三角形可能是有益的。Wihlidal[1883, 1884]提出了一种简单的方法,首先计算三角形的AABB。如果下面是正确的,三角形可以在着色器中剔除:

其中min和max表示三角形周围的二维AABB。如果任何向量分量为真,函数any返回真。还记得像素中心位于(x+0.5, y+0.5),这意味着方程19.4是正确的,如果x-或y坐标,或两者,四舍五入到同一个坐标。图19.17显示了一些示例。

发表评论

电子邮件地址不会被公开。 必填项已用*标注