MIT 6.837:Acceleration Data Structures 光线追踪的加速结构

MIT 6.837:Acceleration Data Structures 光线追踪的加速结构

分布式光线追踪被广泛应用于许多领域,然而单次光线追踪的计算开销已经很大,多次光线追踪更将开销增加至几倍以上。利用加速数据结构优化光线追踪的计算开销是一个重要的方向。

分布式光线追踪

软阴影

39 - MIT 6.837:Acceleration Data Structures 光线追踪的加速结构

对面光源多次采样,得到由面光源造成的真实软阴影效果。

毛玻璃效果

40 - MIT 6.837:Acceleration Data Structures 光线追踪的加速结构

玻璃的表面并不是绝对光滑的,毛玻璃效果实现稍有粗糙的表面,需要用多条反射光线模拟毛玻璃反射的结果。

动态模糊

41 - MIT 6.837:Acceleration Data Structures 光线追踪的加速结构

对所在位置附近的多个不同物体进行追踪,得到动态模糊的效果。

景深

42 - MIT 6.837:Acceleration Data Structures 光线追踪的加速结构

经过真实相机成像得到的画面是通过棱镜折射过的,因此会有景深的效果,只有焦点附近的物体才能看清楚。为了实现这种效果,也需要对每个像素追踪多条光线。

包围盒优化

43 1024x641 - MIT 6.837:Acceleration Data Structures 光线追踪的加速结构

光线与一组三角面求交需要大量开销,如果有光线与它们没有交点,可以通过与包围盒求交先行排除。与轴对齐包围盒(AABB)求交的方法同与立方体求交的方法,在之前已经学习过。

多边形的包围盒可以选为顶点各坐标的最大值、最小值,圆的包围盒可以选择为轴对齐的外接正方体,一组物体的包围盒可以对其包围盒坐标求最大、最小值,而经变换后的物体可以对变换后的包围盒求坐标最值。

44 1024x592 - MIT 6.837:Acceleration Data Structures 光线追踪的加速结构

对于经变换的三角形,可以先求其顶点的变换后坐标再重新计算包围盒,这种包围盒相比上面的一般方法更小,效果更好,而计算包围盒的开销也更小。

加速数据结构

标准网格

将空间划分为若干个大小相同的标准网格,将物体关联到可能包含它的网格中,这样光线先与网格求交,再与物体求交,即可减少求交的计算开销。

利用与 DDA 类似的 3DDDA 算法,我们可以优化与网格求交的过程。

45 1024x522 - MIT 6.837:Acceleration Data Structures 光线追踪的加速结构

以二维网格为例,x 格线和 y 格线上的交点是等间距分布的,其分布距离与射线方向斜率有关。因此,我们分别统计各坐标格线的下一个交点在何处,取最近的交点后,再通过加上一个分布距离得到该坐标下的下一个交点。

自适应网格

场景中的物体/三角面可能集中分布在某一区域,如果使用统一的粒度分割成网格,稀疏的地方并无必要,密集的地方又不能起到很好的优化作用。因此,我们可以对三角面密集区域取更小的网格粒度。

46 1024x510 - MIT 6.837:Acceleration Data Structures 光线追踪的加速结构

例如,可以使用四叉树将空间平分成四份,直到每一份中物体数量小于某一值。尽管这种方法可以自适应地为不同复杂度的场景生成不同粒度的网格,但结构较复杂,求交的开销较大。

边界体积层次结构(Bounding Volume Hierarchy,BVH)

47 - MIT 6.837:Acceleration Data Structures 光线追踪的加速结构

生成 BVH 时,先得到一组物体的包围盒,再将其按空间分布尽量分成两组,分别求包围盒(两组的包围盒可能有交),依次类推直到只剩一个物体。

求交时,需要所有与光线有交的子结构分别求交,返回最近的交点。因为包围盒最近的子结构不一定包含最近的交点,例如下图是一个反例。

48 - MIT 6.837:Acceleration Data Structures 光线追踪的加速结构

BVH 是常用的优化方法,它便于构造和求交,具有二分的结构特征。但生成时需要根据某一判断条件将物体分为两部分,可能难以找到一个好的条件来实现好的效果。

压缩变换结构

连续的组和变换可以被直接应用到场景物体层次结构的末端,减少树的层数,减少求交时的递归开销。

49 1024x573 - MIT 6.837:Acceleration Data Structures 光线追踪的加速结构


发表回复

您的电子邮箱地址不会被公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据