虚拟现实光线跟踪加速方法研究

王彦成++田宏安

摘 要：介绍了虚拟现实技术中的光线跟踪技术，总结了不同种类的加速技术和方法，分析了这些技术的原理、特征及应用这些技术时的建议或限制因素。成像屏幕低采样类型的技术通过减少每帧射出的主光线数目的方法缩短计算时间，次级光线局部裁剪与阴影测试技术通过减少每幅图像跟踪主光线数目的方法缩短渲染时间，光线与场景快速相交优化技术通过改进光线跟踪算法内核加快渲染速度。三类方法各有优缺点，适用于不同的环境和场景，并随着虚拟现实技术的发展而不断发展。

关键词：光线跟踪；次级光线；阴影测试；相交测试

中图分类号：TP391.41 文献标识码：A DOI：10.15913/j.cnki.kjycx.2016.14.110

计算机图形学已从纯学术理论发展成一个具有实践性的重要的商业领域，促进这一发展的原动力来自诸如虚拟现实和可视化应用、照相和电影工业以及方兴未艾的游戏和娱乐工业。今天，建立在计算机图形学上的基础应用主要有两种，即高质量的离线计算机图形应用和交互式图形应用。

目前，在游戏和虚拟现实等应用中使用的交互式计算机图形学几乎全部由三角形光栅化方法支配（比如OpenGL和DirectX），并运行在速度极快、越来越精致的商业图像芯片上。由于三角形光栅化的一些限制，交互式计算机图形学通常不得不依赖近似方法，达不到物理正确性的要求。离线渲染方法用于高质量的图形和正确的物理渲染中，它在设计、动画、电影工业有许多用处。这一方法能创造几乎与真实照片毫无区别的计算机图像。由于严格的质量和正确性要求，这些应用绝大多数建立在光线跟踪方法上。

“光线跟踪”概念多出现于计算机图形领域，通常需要投射大量的光线（一般为百万级），用在光线投射上的计算时间占很大比例。自光线跟踪技术出现以来，找到一种加速光线跟踪的方法极其重要。经深入研究，人们提出了许多不同的加速技术。可将这些技术粗略地划分为三类，即通过低采样率重构图像的技术、通过减少每个采样中被跟踪的光线数目的技术和改进光线跟踪算法内核的技术。

1 成像平面低采样技术

在成像平面上以低采样率重构图像的技术，是基于渲染一帧的时间与该帧的总像素数紧密联系在一起的原理，通过减少每帧射出的主光线数目的方法缩短计算时间。该技术主要包括适应性采样图像平面方法、定点跟踪方法和渲染缓存方法等。

1.1 适应性采样图像平面方法

适应性采样图像平面方法不是对每个像素跟踪一条光线，而是以某个固定间隔采样图像平面。采用启发方法中间像素的颜色或4个角上像素的插值，或者图像位置上的采样密度适应性增加。重复这一过程，直到可以执行插值或所有像素都已被跟踪为止。适应性采样图像平面方法适合渲染非常大的场景。对于高细节几何体或高频特征（比如纹理），该方法几乎不可避免地导致某些细节特征丢失。除了不重要的场景外，该方法中止得非常快，容易引起人为失真。

1.2 顶点跟踪方法

顶点跟踪方法不是对每个单独像素跟踪主光线，而是将光线直接投射到可见三角形的顶点，用递归光线跟踪计算顶点颜色，用图形硬件执行顶点间插值。为避免额外插值，顶点跟踪通常采用一些启发式方法。如果满足某些条件，则进行适应性三角形划分（同时生成新光线跟踪新出现的顶点）。另外，光线仅投射到显示“光线跟踪物体”的物体上，光栅化硬件负责其他物体的渲染。如果被光线跟踪的物体特别简单（比如仅有几个可见顶点），该方法能极大地减少必须跟踪的光线数目，甚至能在PC工作站上达到交互式更新速率。顶点跟踪的光线数目与划分三角形的顺序有关。

1.3 渲染缓存方法

采用渲染缓存方法维护前面的一些帧采样得到的旧图像缓存，并将这些图像重新投影到每个新生成的帧上。重新投景采样是对成像平面的稀疏采样。然后通过某些启发式方法解决遮挡、开裂和采样点之间的插值，最后重构完整的图像。为了提高性能，渲染缓存用启发式方法决定成像平面的哪些区域需要更多的采样，以在这些区域生成更好的采样。新采样进入渲染缓存数据结构，并替代已经陈旧的采样。渲染缓存将采样生成速度和帧率分开，因此在非常低的渲染器中也能保证交互帧率。重新投影和图像重构步骤代价巨大，仅能由极其昂贵的渲染器使用，同时，即使渲染缓存使用上结启发式方法处理最糟糕的情况，也不能避免所有人为失真，经常出现某些物体或区域欠采样、过时采样、过多的模糊。

2 次级光线局部裁剪与阴影测试技术

除了每帧的主光线数目外，影响总渲染时间的另一个因素是每个像素对应的平均光线数目。因为这两者的乘积决定了每帧投射的光线总数。

实际渲染中，每个像素对应的次级光线数目可能非常大，特别是在场景中有很多光源和大量镜面物体时更是如此。由于投射进场景的每条光线（除次级光线之外的主光线）都会发射阴影光线到每个光源，因此，光源数目以接近线性的方式影响渲染时间。在实际场景（通常包含主光源、镜面物体）中，每个像素对应的光线数目将非常大，减少这一数目将会有效缩短渲染时间。在实践中，广泛采用的方法主要有阴影缓存方法、局部光照环境方法和修剪光线树方法等。

2.1 阴影缓存方法

阴影缓存方法的基本假设是，每条主光线或次级光线通常会引起很多阴影光线，所以在光线跟踪器中的光线主要是阴影光线。但对于阴影光线而言，找出任一遮挡物体，以确认遮挡就足够了，而且许多阴影光线都非常相似（比如所有阴影光线射向同一点光源），也经常与同一物体相交。因此，阴影缓存通过保留该光源最后一次遮挡体的信息，每条新阴影光线首先与被缓存的遮挡体求交。如果其中任何一个物体有正的相交距离，则确认阴影光线发生遮挡。此时，将不再跟踪阴影光线。对于高度遮挡、多光源场景，采用阴影缓存法能极大地减少阴影光线数目，而且不需要任何近似，不产生任何失真，也与其他大多数技术正交（很容易与其他技术结合）。但如果主光线与阴影光线不连贯，则因阴影缓存失效导致整个算法失效，特别是对存在面光源的场景和全局光照算法。

2.2 局部光照环境方法

局部光照环境方法是针对阴影光线更进一步的优化，它将场景分隔成“体元”的集合，每个体元存储着不同光源对该体元区域的影响方式，比如完全遮挡的光源列表、完全可见的光源列表、部分可见光源列表等。用这些信息能有效减少阴影光线的数目，不必再去考虑某体元对应的完全遮挡的光源，而完全可见光源则可以不必再跟踪任何阴影光线，只有部分可见光源需要发射阴影光线。采用局部光照环境方法时，可以仅跟踪阴影光线中的很小一部分，尤其是对于有很多光源的场景，能有效缩短渲染时间。

2.3 修剪光线树方法

修剪光线树方法的基本假设是，光线跟踪需要计算反射和折射，如果每个表面着色器投射多于一条的次级光线（比如一条反射光加一条折射光），那么次级光线的数目将随递归层数呈指数增长，容易导致在每帧投射出巨大数目的光线，即所谓的“光线树爆炸”。但在实际渲染时，次级光线往往带有反射和折射权重系数（由表面性质和入射光线方向等决定），可能会变得很小，而且在衰减因素与远处表面相交的综合作用下，很多光线对像素贡献微乎其微。为避免跟踪这些“不重要”的光线，根据跟踪每条光线的像素贡献修剪光线树，一旦像素贡献低于某一阈值就立即终止递归。

3 光线与场景快速相交优化技术

除了减少投射出的光线数目外，另一加速光线跟踪的明显方法是改进光线跟踪算法内核，使之更快地跟踪光线。

3.1 相交测试优化方法

通常，光线跟踪中一大部分时间都花在光线与元素相交上，95%的计算时间都花在了求交运算上。任何一种元素与光线求交都有多种方法。这些不同的算法有不同的性质，诸如浮点运算、整数运算、判断运算的次数，存储器开销，数据精度等，不同的应用有不同的偏好性质，同时，各种不同硬件的特性（比如快速浮点单元）进一步改变相应的优点和缺点。实际上，对于每种元素，各个光线跟踪系统都有各自特有的实现算法。

对于支持复杂元素类型（比如参数曲面）的光线跟踪器，通过紧密包围这些耗时元素的边界体可以避免过高的计算开销。边界体是一种能快速求交的简单几何元素（通常是盒子或球）。如果光线与边界体不相交（这是开销非常小的检查），则它必定不与边界体对应的复杂元素相交。只有与边界体相交的光线需要再次与原来的元素进行测试。在光线跟踪中，边界体是一项标准技术，但只对复杂元素有效。

3.2 场景的空间划分和层次划分

通常，加速光线跟踪最成功的方法是减少光线-元素求交运算的数目，通过建立一种索引数据结构，允许快速找出接近给定光线的元素，并跳过过熟光线的元素。在遍历这种加速结构时，只对潜在的候选者执行求交，因此能显著减少求交运算的数目。

一般情况下，存在许多不同的加速结构，比如均匀、非均匀、递归、层次网格和BSP树（或KD-树），甚至更高维、定向技术，比如光线分类。在层次边界体中，每个元素在层次中仅存储一次。通常，这种结构占用可预计的存储，并保证在遍历层次时每个元素仅执行一次相差（通常空间划分技术达不到此要求）。另外，层次的不同部分可能在空间中占用同一区域，导致诸如错误的求交次序或多次遍历同一空间等无效率的遍历。

在空间划分技术中，将三维空间划分成有限的、不互相重叠的体积元素（体元voxels），每个体元维护一个与该体元重叠的所有元素的列表。光线遍历空间加速结构，依次重复穿过与光线相交的所有体元，进而与体元中的元素相交。如果这种遍历以“从前至后”的次序执行，空间分隔技术允许早期光线终止。一旦沿光线以下距离内的相交被验证，所有位于此距离之外的体元就无需计算，立即跳过。空间分隔存在一个缺点——如果体元很小，光线遇到元素的数目大量减少，要求具备大量存储器，而且元素通过与许多不同的体元重叠。这不仅进一步增加了存储开销，还经常导致跟踪一条光线时多次重复遇到相同的元素。

3.3 算法具体实现的变体和优化

快速相交优化类型的加速技术主要是概念上的差别，实际上，在固定一种数据结构的情况下，构造和遍历这一数据结构的确切方法仍显著影响着算法的性能。

尽管不同的遍历算法确定的遍历同一体元（因而与同一元素相交），遍历算法本身通常要占用很大一部分计算时间。因此，不同的遍历算法可能显著地影响性能。目前，每种不同的加速结构都有一些不同的遍历算法，各自优缺点并存。虽然这些变体的绝大多数不改变基础的数据结构，但有一些方法也要求作一些轻微的改变，例如通过增加相邻链接加速从一个体元到其相邻体元的遍历。

除了遍历算法外，对加速结构的性能有显著影响的是建立数据结构的算法。因为遍历算法本身一般不改变光线遇到的体元数目或阶数，所以遍历步骤和原始的求交次数通常取决于建立加速数据结构的方法（比如体元的数目、尺寸或组织）。实际上，很难确定最优的网格分辨率，只能用某些启发式方法近似猜测。由于大多数光线跟踪应用中投射最多的光线是阴影光线，因此这项优化特别有效，大多数可用的光线跟踪系统都要实现它。

要想使光线跟踪更快，关键在于开发不同的、更强大的硬件设备。这类的例子有在高并行超级计算机上的光线跟踪，其采用目前大多数CPU具备的SIMD-扩展，可编程GPU上的光线跟踪，开发更一般的可编程设备，最终使用专门为光线跟踪设计的硬件。

4 总结

虚拟现实光线跟踪加速技术中，层次划分这一类方法是最重要的。因为这些方法可将计算复杂度从O（N）降低到O（logN）。大体上而言，其他方法仅能改进光线跟踪算法的“常数项”。因而，任何重要的光线跟踪系统都使用本文讨论的某种场景划分和遍历技术。

虽然相关人员普遍认为所有这些加速方法都具有O（NlogN）的计算复杂度，但实际上随场景、实现、硬件平台和应用（比如光线分布）的不同，相应的性能也各不相同。尽管最早的一些光线跟踪涉及八叉树，但目前实际使用最普遍的技术不是均匀网格就是KD-树。网格（尤其均匀网格）的优点是简单，因而适宜在限制编程模型的硬件结构上实现（比如GPU）。另外，KD-树能很好地适应不同场景的复杂性。如果能正确使用，通常可以达到优质性能。

除更快的相交测试和层次划分外，其他技术（比如以这样或那样的方法减少光线数目）则各有限制，只能用于一些特殊情况和应用中，在一个用于一般情况的光线跟踪系统中，这些技术的使用是受限的。

〔编辑：刘晓芳〕