并行計算在光線追蹤中的應用

陳是權

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.