并行计算在光线追踪中的应用

陈是权

0 引言

光线追踪，是一种将真实三维物体显示在二维屏幕上的方法，它由 Appel在1968年提出。光线追踪的优点在于其真实地模拟光线的传播方式，从而能够产生照片级逼真的渲染效果。而其最大的缺点在于其性能。

本文介绍的就是基于硬件的两种并行加速方法，一种是线程级别的多核并行，这是基于Intel的TBB的编程工程。而另一种则是指令级别的并行，即SIMD (Single Instruction Multiple Data，单指令多数据流)。

1 光线追踪原理

1.1 光线追踪的介绍

如图1所示：

图1 光线追踪原理图

光线追踪的原理，是由人眼到屏幕的每个像素点发出光线，找出这条光线与物体表面的相交点P0，并找出影响P0点光强的所有光源，从而算出P0点上精确的光线强度，最后结合P0点表面的材质算出屏幕上像素点的像素值。

1.2 光线追踪核心计算

由后面的2.1节可以看出，光线追踪的核心在于计算射线(以人眼为原点，人眼到像素点为方向)与场景中的物体是否相交并求出相交点的坐标(参照参考文献[1])。在计算图形学中，物体的表示方式以三角形面片最为普遍。所以判断射线与物体是否相交的核心，实际上可以演变为判断射线与三角形是否相交。

图2 三角形的重心坐标表示方法

一个三角形可以用三个点a、b、c表示，如果这3个点不在一条线上或重合的话，则这3个点可组成一个面，此面上的任一点则可表示为(参照参考文献[2])，如图2所示：而三角形内部的点则当0<α< 1， 0<β< 1， 0<γ<1，简化为一个参数：P (β,γ) =α +β (b-a) +γ(c-a)其中β+γ < 1， 0<β，0<γ。同理，射线可表示为P (t) = o +td（o为原点，d为方向），其中t＞0。求相交实际上则是求方程P(β,γ) = P (t), 即

o + td = a +β (b-a) +γ(c-a) 展开整理得：

其中A为

算出t,β,γ则根据条件判断，如果t＞0, 0<β,0<γ,0<β+γ<1则射线与三角形相交， 并将t代入o + td求出相交点。注：如果射线与三角形的某条边或顶点相交，则仍计为不相交。

2 加速实现

2.1 并行加速

2.1.1 TBB加速

TBB （Thread Building Blocks, 线程构建模块）是Intel公司开发的并行编程开发的工具。TBB能充分利用CPU的多核特点进行有效的并行计算。如果一个核心已经完成其工作，而其它核心仍然有相当数量的工作在它们的队列中，TBB会重新分配一些工作繁忙的核心之一给闲置的核。从射线与三角形相交的算法我们可以看出：每根射线与三角形簇求交实际上是独立的，这就为我们提供了线程算法优化的可能。我们将每根射线与三角形簇求交作为一个单独的任务，然后利用TBB将这些独立的任务，分配到机器的多个CPU,即多核上来运行。核心算法伪代码如下：

2.1.2 SIMD加速

SIMD（Single Instruction Multiple Data，单指令多数据流）是一组能够复制多个操作数，并把它们打包在大型寄存器的指令集中。借助 SIMD，我们可以一次处理4个单精度浮点值(参照参考文献[3]58页)。

使用 SIMD的优势还在于可以同时对4个三角形和 4条射线进行运算。在这里我们需要定义一个triangle4和ray4的类型：

Triangle4实际在内存中的数据表达，如表1所示：

表1 内存中的数据表达

Ray4实际在内存中的数据表达，如表2所示：

表2 内存中的数据表达

它将进行SIMD操作如_mm_sub_ps(t0_v0x, t0_v1x)，则实际的结果是进行了4次减操作，得到的结果为：

将其代入三角形射线求交算法中：

3 结论

本论文中共测试了4组数据，并在3种类型的机器上试验过。4组数据主要区别在和射线与三角形数目的不同，如表3所示：

表3 数据表达

测试的机器主要包括单核、双核、以及8核的机器，如表4所示：

表4 测试的机器

测试结果数据(单位：秒(s) )，如表5所示：

表5 测试结果

结论：从以上数据可以看出在双核的情况下，利用本文的加速算法，可以使射线与三角形相交的算法提高1.5倍速度以上，核越多则提高得越明显，如图3、图4、图5所示：

图3 机器1

图4 机器2

图5 机器3

[1]Tomas Nikodym (June).Ray Tracing Algorithm For Interactive Applications[D].Czech Technical University,FEE, 2010.

[2]Keith Morley.RealisticRayTracing [M].2009.

[3]Reinders, James.Intel Threading Building Blocks:Outfitting C++ for Multi-core Processor Parallelism(Paperback) [S].2007.

[4]刘刚, 梁晓庚.基于SIMD硬件指令加速的并行光线跟踪算法[J].第十届中国科协年会论文集, 2008.