陳是權(quán)

0 引言

光線追蹤，是一種將真實(shí)三維物體顯示在二維屏幕上的方法，它由 Appel在1968年提出。光線追蹤的優(yōu)點(diǎn)在于其真實(shí)地模擬光線的傳播方式，從而能夠產(chǎn)生照片級逼真的渲染效果。而其最大的缺點(diǎn)在于其性能。

本文介紹的就是基于硬件的兩種并行加速方法，一種是線程級別的多核并行，這是基于Intel的TBB的編程工程。而另一種則是指令級別的并行，即SIMD (Single Instruction Multiple Data，單指令多數(shù)據(jù)流)。

1 光線追蹤原理

1.1 光線追蹤的介紹

如圖1所示：

圖1 光線追蹤原理圖

光線追蹤的原理，是由人眼到屏幕的每個(gè)像素點(diǎn)發(fā)出光線，找出這條光線與物體表面的相交點(diǎn)P0，并找出影響P0點(diǎn)光強(qiáng)的所有光源，從而算出P0點(diǎn)上精確的光線強(qiáng)度，最后結(jié)合P0點(diǎn)表面的材質(zhì)算出屏幕上像素點(diǎn)的像素值。

1.2 光線追蹤核心計(jì)算

由后面的2.1節(jié)可以看出，光線追蹤的核心在于計(jì)算射線(以人眼為原點(diǎn)，人眼到像素點(diǎn)為方向)與場景中的物體是否相交并求出相交點(diǎn)的坐標(biāo)(參照參考文獻(xiàn)[1])。在計(jì)算圖形學(xué)中，物體的表示方式以三角形面片最為普遍。所以判斷射線與物體是否相交的核心，實(shí)際上可以演變?yōu)榕袛嗌渚€與三角形是否相交。

圖2 三角形的重心坐標(biāo)表示方法

一個(gè)三角形可以用三個(gè)點(diǎn)a、b、c表示，如果這3個(gè)點(diǎn)不在一條線上或重合的話，則這3個(gè)點(diǎn)可組成一個(gè)面，此面上的任一點(diǎn)則可表示為(參照參考文獻(xiàn)[2])，如圖2所示：而三角形內(nèi)部的點(diǎn)則當(dāng)0<α< 1， 0<β< 1， 0<γ<1，簡化為一個(gè)參數(shù)：P (β,γ) =α +β (b-a) +γ(c-a)其中β+γ < 1， 0<β，0<γ。同理，射線可表示為P (t) = o +td（o為原點(diǎn)，d為方向），其中t＞0。求相交實(shí)際上則是求方程P(β,γ) = P (t), 即

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

其中A為

算出t,β,γ則根據(jù)條件判斷，如果t＞0, 0<β,0<γ,0<β+γ<1則射線與三角形相交， 并將t代入o + td求出相交點(diǎn)。注：如果射線與三角形的某條邊或頂點(diǎn)相交，則仍計(jì)為不相交。

2 加速實(shí)現(xiàn)

2.1 并行加速

2.1.1 TBB加速

TBB （Thread Building Blocks, 線程構(gòu)建模塊）是Intel公司開發(fā)的并行編程開發(fā)的工具。TBB能充分利用CPU的多核特點(diǎn)進(jìn)行有效的并行計(jì)算。如果一個(gè)核心已經(jīng)完成其工作，而其它核心仍然有相當(dāng)數(shù)量的工作在它們的隊(duì)列中，TBB會(huì)重新分配一些工作繁忙的核心之一給閑置的核。從射線與三角形相交的算法我們可以看出：每根射線與三角形簇求交實(shí)際上是獨(dú)立的，這就為我們提供了線程算法優(yōu)化的可能。我們將每根射線與三角形簇求交作為一個(gè)單獨(dú)的任務(wù)，然后利用TBB將這些獨(dú)立的任務(wù)，分配到機(jī)器的多個(gè)CPU,即多核上來運(yùn)行。核心算法偽代碼如下：

2.1.2 SIMD加速

SIMD（Single Instruction Multiple Data，單指令多數(shù)據(jù)流）是一組能夠復(fù)制多個(gè)操作數(shù)，并把它們打包在大型寄存器的指令集中。借助 SIMD，我們可以一次處理4個(gè)單精度浮點(diǎn)值(參照參考文獻(xiàn)[3]58頁)。

使用 SIMD的優(yōu)勢還在于可以同時(shí)對4個(gè)三角形和 4條射線進(jìn)行運(yùn)算。在這里我們需要定義一個(gè)triangle4和ray4的類型：

Triangle4實(shí)際在內(nèi)存中的數(shù)據(jù)表達(dá)，如表1所示：

表1 內(nèi)存中的數(shù)據(jù)表達(dá)

Ray4實(shí)際在內(nèi)存中的數(shù)據(jù)表達(dá)，如表2所示：

表2 內(nèi)存中的數(shù)據(jù)表達(dá)

它將進(jìn)行SIMD操作如_mm_sub_ps(t0_v0x, t0_v1x)，則實(shí)際的結(jié)果是進(jìn)行了4次減操作，得到的結(jié)果為：

將其代入三角形射線求交算法中：

3 結(jié)論

本論文中共測試了4組數(shù)據(jù)，并在3種類型的機(jī)器上試驗(yàn)過。4組數(shù)據(jù)主要區(qū)別在和射線與三角形數(shù)目的不同，如表3所示：

表3 數(shù)據(jù)表達(dá)

測試的機(jī)器主要包括單核、雙核、以及8核的機(jī)器，如表4所示：

表4 測試的機(jī)器

測試結(jié)果數(shù)據(jù)(單位：秒(s) )，如表5所示：

表5 測試結(jié)果

結(jié)論：從以上數(shù)據(jù)可以看出在雙核的情況下，利用本文的加速算法，可以使射線與三角形相交的算法提高1.5倍速度以上，核越多則提高得越明顯，如圖3、圖4、圖5所示：

圖3 機(jī)器1

圖4 機(jī)器2

圖5 機(jī)器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].第十屆中國科協(xié)年會(huì)論文集, 2008.