《GPU光线跟踪算法加速结构研究》由会员分享，可在线阅读，更多相关《GPU光线跟踪算法加速结构研究（7页珍藏版）》请在金锄头文库上搜索。
1、GPU光线跟踪算法加速构造研究摘要：基于gpu的光线跟踪算法是当前图形学研究的一个热点，也是将来用于广告、电影、游戏等娱乐产业的关键技术。本文阐述了如何对基于gpu的光线跟踪算法进展实现，以及利用各种加速构造，加速算法实现，进步算法执行效率，并对各种加速构造的效果进展了比拟研究。关键词：gpgpu光线跟踪bvhkd-tree1引言近年来，pu无论在运算才能，还是在可编程性上都得到了大幅的进步，gpu已经在需要大量运算的密集运算领域发挥了举足轻重的作用。各种基于pu的密集运算被移植到gpu上，以利用gpu宏大的运算才能，加速整个算法的运算过程。光线跟踪算法是生成真实感图形的一种非常重要的方法，在
2、电影、游戏、广告等产业，获得广泛的应用，而光线跟踪算法也是典型的密集运算算法，利用原始的基于pu的光线跟踪渲染一幅图片是非常耗时的操作。因此，假如可以将pu上的光线跟踪算法，映射到pu上，加速光线跟踪算法的执行时间，将会带来宏大的经济效益。因此，基于pu的光线跟踪算法已成为国内外科研人员的研究热点。2基于gpu的光线跟踪2.1相关工作当前，主要由两种方法利用pu来加速光线跟踪算法。第一种是arr等人提出来的，将pu转换为一个蛮力的执行光线一三角形求交的计算器，而将任何的光线生成以及着色过程在pu上完成。这就需要pu仍然执行绝大局部的渲染工作。arr等人指出，在atiraden8500上，每秒最
3、快可以执行1亿2千万次的光线一三角形求交。同时，作者也指出，由于gpu的单精度浮点的限制，图片上仍然存在一些不太真实的地方。第二种方法由purell等人提出的，改种方法将整个光线跟踪器都移植到pu上进展实现。从光线的产生，加速构造的遍历，到最后的着色过程都在gpu上执行。此后，有很多一样的工程都是基于purell的模型上进展的。2.2gpu上的光线跟踪算法的映射方式将传统的pu上执行的光线跟踪算法，映射成为一个gpu协助的，或者基于gpu的光线跟踪器有众多方法。下面重点介绍purell提出的映射模型，以及在本文的实现中提出的一个基于pu的hitted模型的光线跟踪器。该光线跟踪器的布局如图2.
4、1所示：在purell的论文中，它将光线一三角形求交，以及遍历过程别离成两个独立的遍历内核和求交内核。本文的实现中，也按照上述模型图，将光线跟踪算法分解成光线生成，光线一三角形求交，着色这三个步骤。在对光线进展跟踪之前，需要生成从视点指向屏幕的原始光线(priaryray)。在一个gpu上，可以使用光栅器的插值的才能，在一个单一的内核调用中，产生所有的原始光线。给定观察矩形被采样用于产生图片的投影平面的一局部的四个角，以及视点，首先计算出这个视锥体的四条边线。假如让光栅器在这4条光线之间，按照512512规格，在这四条光线之间按照方向进展插值，最终就可以获得可以产生一幅512512图片一个像素
5、一个采样点的所有原始光线的方向。同时可以将这些方向存储在一个纹理里，并把它作为求交内核的输入。所有的原始光线具有一样的起始点，但是仍然把它存储在一个同方向纹理具有一样维度的纹理内。因为当生成阴影光线或者反射光线的时候，光线的原点会发生改变。求交内核把光线的原点，方向，以及场景的描绘作为输入数据。在内核被调用数次之后，我们对于每一个像素输出一个击中记录。假如一条光线击中了场景中的某个三角形，返回击中点的3个重心坐标，以及相关的被击中的三角形。此外，还将输出被发现的交点沿光线的间隔 ，以及被击中三角形的材质。这就需要使用5个浮点数值组成一个击中记录。纹理只可以支持4个颜色通道(rba)，所以，假如
6、能把击中记录裁减到4个值，那么将是非常有益的。观察发现，只需要3个重心坐标的两个，因为在三角形内部，它们相加的和总是1。这就使得在一个单独的rgba纹理中存储交点记录是可行的，并且它的维度同其它两个光线纹理的维度一样。ller和trubre提出了一个高效的光线一三角形求交算法，使用这个算法，并利用pu在向量计算上的优势来进展求交计算。下面列出了求交的代码，这个代码也展示了如何利用向量指令来进步效率。当所有的原始光线都已经计算出了相交的状态的时候，就可以查询着色过程所需要的外表法线和材质的信息。每一个击中记录都存储了一个指向材质纹理的索引，这个材质纹理包含了三角形的法线，材质颜色以及类型。三个顶
7、点的法线根据击中记录的中心坐标进展了插值。最终的颜色可以按(n-l)进展计算，此处是法线，l是光源的方向，g是三角形的颜色。如今根据击中的三角形所具有的材质的类型漫反射材质，或者镜面反射材质，需要产生二次光线，以此来计算阴影和反射。1)假如一条光线射出场景之外，像素就被赋予全局的背景颜色。2)假如一条光线击中了一个漫反射材质外表，就发射一条阴影射线(shdray)。这些光线的起始点在击中点，方向为从击中点指向光源。3)假如一条光线击中了一个镜面反射材质外表。就发射一条镜面反射光线。镜面发射光线的起始点也在击中点，但是它的方向是在击中点处关于入射光线和插值后的法线对称的方向。一个真正的hitte
8、d类型的光线跟踪器也支持透明材质，从而可以产生折射光线。但由于主要是研究加速构造，所以在本文的实现中，没有考虑折射光线。4)假如阴影光线击中了某个几何体，这就说明在光源和击中点之间，存在某个几何体，所以这个像素就应该是黑色处于阴影中。当跟踪阴影光线的时候，不关心最近的那个击中点，更加关心的是是否存在这样的击中点。因此，当有一个交点被发现，就可以停顿整个求交过程，从而加速算法的处理过程。在本文的实现中，以一样的方式跟踪阴影光线和反射光线，因此，就没有使用到这个优化策略。已经对每一个像素产生了正确二次光线，假如需要，就可以执行另外一趟遍历/求交过程，对上述的二次光线进展跟踪。每一次调用着色程序就可
9、以对每一个像素返回一个颜色值和一条新的光线。着色内核也可以将前一次着色程序的输出当作本次着色程序的输入。这就使得可以在跟踪连续的光线的时候合并这些连续的镜面反射的颜色。同arr等人的程序不同，本文所采用的程序不存在浮点精度太低的问题，因为efre7300在整个管线中支持真正的32位浮点操作。3加速构造的实现和比拟3.1均匀栅格均匀栅格是第一个在gpu上实现的加速构造。purell给出了很多项选择择均匀栅格作为加速构造的理由，但是purell没有详细的说明为什么均匀网格对于硬件实现而言比其它的加速构造要更加的简单。当在讨论了均匀栅格的一些主要特性的时候，更加明晰的知道了均匀栅格为什么会成为一个好
10、的gpu机速构造。首先，只用使用简单的算术运算，就可以对于每个体素的遍历在常量时间能被定位和存龋这就消除了对树的遍历的需要，以及重复的纹理查找工作，而纹理查找是相当耗时的。其次，体素的遍历是通过递增算术运算来完成的。这就消除了对堆栈的需要，使得我们可以从光线的起始点开场，以间隔 递增的顺序访问体素成为可能。再其次，由于对于体素的访问是沿着光线，以间隔 递增的方式遍历的，所以，一旦在一个被访问的体素中报道发现有一个交点，就可以停顿这条光线对体素的遍历过程，从而进步整个遍历过程的速度。最后，用于遍历的代码非常合适用向量编写，而向量形式的编码风格又非常合适gpu的指令集。然而，均匀栅格的缺点就是由于
11、它是空间细分构造的一种特殊情况，多个体素可能包含一样三角形的多个引用。由于无法使用ailbx技术，这就意味着需要对于一样的光线和三角形之间进展不止一次的相交测试。3.2kd-tree最近，havran等人对基于pu的光线跟踪算法的加速构造进展了比拟，得出的结论是对于众多不同类型的测试场景，平均而言，kd-tree是最快的。所以，有必要考察一下对于基于kd-tree的gpu光线跟踪算法，是否也会有相似的结论。就像均匀栅格一样，kd-tree也是一种空间细分构造。同均匀网格不同的是，kd-tree利用一个二叉树将场景表示成一个层次构造。在二叉树中，我们将内部节点和叶子节点区分开。叶子节点用来表示体
12、素和与之相关的保存在该体素内的三角形的引用。一个内部节点用来表示空间区域的某个局部。所以，内部节点包含一个分裂面的两个子树的引用，而叶子节点只包含一个三角形列表。kd-tree的创立过程从上而下，根据一个评价函数，通过放置一个别离平面，递归的将场景别离成两个体素。我们可以以递归的方式遍历kd-tree，但是由于gpu没有堆栈构造，所以无法应用递归的策略。取而代之的是，我们可以通过记住我们沿着光线前进了多远来向上或者向下遍历树。这种策略消除了需要堆栈的限制，使得用pu来完成对kd-tree构造的遍历成为可能。当使用gpu对kd-tree进展遍历的时候，kd-tree像均匀栅格那样被表示成一个纹理
13、的集合。这就意味着有一个保存树数据的纹理，一个保存三角形列表的纹理，和一个保存实际的三角形数据的纹理。gpu的遍历首先调用一个初始化内核，然后按照需要，屡次调用合并后的遍历和求交内核。3.3包围体层次(bvh)给定一些随机的光线，通过计算遍历包围体层次的平均花费，就可以测量出该包围体层次的质量。迄今为止，还没有构建最优的包围体层次的算法，也就是说，如何准确的测量一个包围体层次的平均遍历时间还不是很明显。gldsith和saln提出了一个评价函数，通常被称为外表积启发式函数。他们通过父节点和孩子节点的外表积之比来形式化的表述这个关系，此评价函数如下所示：此处，hit(n)是光线击中节点n的情况，
14、sn是节点n的外表积，和p分别表示父节点和孩子节点。这个评价函数给出了，当用一条随机的光线同层次构造求交的时候，本钱上的估计。由于没有最优的方法去有效的构造一个最优的bvh，提出了不同的构造技巧。下面，将列出比拟通用的方法。在理论中，对于包围体应用的最广泛的就是轴对齐包围盒(aabb)。aabb易于实现，并且同光线的求交测试非常快。大多数有关bvh的论文在描绘bvh的创立的时候，通常分别以kay和kajiya，或者gldsith和saln这两种根本的想法为基矗kay和kajiaya建议以自上而下递归的方式进展bvh的创立。gldsith和saln提出了一个更加复杂的自底向上的构造方式。glds
15、ith和saln指出，bvh的质量同作为输入传人的三角形的顺序有关。因此，他们建议在构造bvh之前，随机打乱三角形的顺序。下述算法就是利用kay/kajiya的思想创立某个场景的包围体层次的方法：4完毕语本文成功的在gpu上实现了用于光线跟踪算法中的各种加速构造，并对这些加速构造在gpu上的加速效果进展了比拟。均匀栅格作为第一个在pu上实现的光线跟踪器的加速构造，也被证明是最慢的，除非是只包含一个单独的物体的场景的情况。均匀栅格不合适几何体的密度非常高的场景。另外，对于均匀栅格的pu上的遍历表示，也需要大量的数据。fley和sugeran认为，对于大多数场景，kd-tree的效率要比均匀栅格高。但是，在kd-tree的遍历过程中，无论是重置阶段还是回退阶段，片元程序都非常的复杂，但这种复杂性也使得其可以在场景的几何体的密度改变的时候做出适当的调整。本文实现的bvh被证明在加速效果上要超过均匀栅格和kd-tree，在现阶段，bvh是在gpu上实现的最快的加速构造。并且在gpu上实现bvh加速构造要比实现其他加速构造更加的简单。参考文献：1randiafead编，姚勇，王小琴译gpu精粹一实时图形编程的技术，技巧和技艺北京：人民邮电出版社，2022.2attpharr编著，龚敏敏译.gpu精粹2-高性能图形芯片和通用计算编程技巧.北京：
