厲夫兵，蘇永琪，陳文劍

(1.北京信息科技大學(xué) 信息與通信工程學(xué)院，北京 100101； 2.哈爾濱工程大學(xué) 水聲工程學(xué)院，黑龍江 哈爾濱 150001)

0 引 言

射線追蹤法[1]在通信與計(jì)算機(jī)領(lǐng)域具有很廣泛的應(yīng)用。通信領(lǐng)域中，利用射線追蹤法可以分析目標(biāo)的散射特性。計(jì)算機(jī)領(lǐng)域中，通過射線追蹤可以使二維平面圖像呈現(xiàn)更真實(shí)的三維效果，常用于圖像渲染?？臻g剖分技術(shù)和并行計(jì)算可以運(yùn)用于射線追蹤計(jì)算過程中，解決射線追蹤效率低下的問題。1980年J. Bentley提出KD-Tree空間剖分技術(shù)，已被運(yùn)用于射線追蹤靜態(tài)場(chǎng)景的計(jì)算中，旨在將射線追蹤計(jì)算過程的時(shí)間復(fù)雜度降低[2，3]。此外，隨著GPU架構(gòu)技術(shù)的不斷發(fā)展，GPU逐漸展現(xiàn)出了強(qiáng)大的并行計(jì)算能力。NVIDIA公司提出的統(tǒng)一計(jì)算設(shè)備體系結(jié)構(gòu)(CUDA)[4]作為開發(fā)環(huán)境，可以將大量數(shù)據(jù)進(jìn)行合理分配后，交由GPU進(jìn)行并行計(jì)算。射線追蹤過程中會(huì)面對(duì)大量射線數(shù)據(jù)，因此GPU并行計(jì)算可以有效提高射線追蹤計(jì)算效率。

本文針對(duì)傳統(tǒng)射線追蹤計(jì)算效率低下的問題，首先對(duì)目標(biāo)場(chǎng)景進(jìn)行三角剖分建模，其次采用KD-Tree數(shù)據(jù)結(jié)構(gòu)對(duì)場(chǎng)景空間進(jìn)行合理劃分，并且通過添加線索指針的方式實(shí)現(xiàn)KD-Tree的無堆棧遍歷，以此避免大部分無效的求交運(yùn)算[5]，最后在CUDA平臺(tái)下設(shè)計(jì)射線追蹤在CPU-GPU異構(gòu)計(jì)算的實(shí)現(xiàn)方案，合理分配計(jì)算資源，將射線追蹤過程并行化[6]。通過KD-Tree與并行計(jì)算結(jié)合，改善射線追蹤的計(jì)算時(shí)間。

1 KD-Tree的創(chuàng)建

KD-Tree是二叉空間剖分樹的一種，它是利用平面的定策性質(zhì)，使用一個(gè)平面將目標(biāo)模型的空間劃分為兩部分，之后再遞歸地對(duì)已經(jīng)劃分好的空間進(jìn)行分割，直到達(dá)到提前設(shè)定的條件[7]。

目前構(gòu)建KD-Tree的一種方法是通過表面積啟發(fā)式(surface area heuristic，SAH)[8]選取合適的剖分面，遞歸將目標(biāo)場(chǎng)景剖分為若干個(gè)軸對(duì)齊長(zhǎng)方體包圍盒。但當(dāng)包圍盒內(nèi)三角面元數(shù)量較多時(shí)使用SAH算法計(jì)算代價(jià)值會(huì)出現(xiàn)誤差，因此本文結(jié)合目標(biāo)空間每一維度的方差與維度上面元坐標(biāo)的中心點(diǎn)來確定剖分的維度與剖分面。創(chuàng)建KD-Tree的具體步驟如下：

(1)基于仿真模型上的三角面元和節(jié)點(diǎn)信息構(gòu)建包圍盒，作為KD-Tree的根節(jié)點(diǎn)。

(2)選取合適的分割軸與剖分平面，切割根包圍盒生成左右子節(jié)點(diǎn)。為選擇合適的分割軸，需要計(jì)算節(jié)點(diǎn)內(nèi)各個(gè)面元的中心點(diǎn)坐標(biāo)分別在x，y，z維上的方差。任一維度方差的計(jì)算公式如式(1)所示

(1)

式中：centeri表示某一維度上的每個(gè)面元中心點(diǎn)坐標(biāo)的值，mean表示某一維度上所有面元中心點(diǎn)坐標(biāo)的平均值，F(xiàn)aceNumberInNode表示當(dāng)前節(jié)點(diǎn)內(nèi)三角面元的數(shù)量。

在確定分割軸后，可以對(duì)分割維度上三角面元的中心點(diǎn)進(jìn)行排序，選取中間值作為剖分面。

(3)對(duì)于新生成的節(jié)點(diǎn)重復(fù)步驟(2)的內(nèi)容，直到節(jié)點(diǎn)內(nèi)的三角面元數(shù)量達(dá)到提前設(shè)定的閾值，節(jié)點(diǎn)不可再分割。

自此，KD-Tree構(gòu)建完成，剖分過程中所形成的節(jié)點(diǎn)是KD-Tree的中間節(jié)點(diǎn)，剖分結(jié)束后的不可再分割節(jié)點(diǎn)是KD-Tree的葉子節(jié)點(diǎn)。

腔體模型的剖分示例和分割模型生成的KD-Tree如圖1所示。根包圍盒為N0，面L0將N0切割為N1，N2兩個(gè)節(jié)點(diǎn)，面L1，L2分別將N1，N2切割為N3，N4，N5，N6這4個(gè)節(jié)點(diǎn)，為節(jié)省內(nèi)存開銷，在將節(jié)點(diǎn)分割后將模型的面元信息與點(diǎn)信息都保存至生成的子節(jié)點(diǎn)中，因此最終模型的信息都會(huì)保存在葉子節(jié)點(diǎn)中[9]。由于模型剖分的密度不同，每次切割并不能保證左右子節(jié)點(diǎn)中的面元數(shù)量相同，因此每個(gè)葉子節(jié)點(diǎn)中的三角面元的數(shù)量會(huì)隨著剖分的不同而不同。對(duì)于完全處于包圍盒內(nèi)的面元，如圖1(a)中的2號(hào)與4號(hào)面元，它們分別只屬于N4，N5節(jié)點(diǎn)；而對(duì)于屬于分割平面上的面元，例如1號(hào)面元既屬于N3節(jié)點(diǎn)又屬于N4節(jié)點(diǎn)，3號(hào)面元既屬于N5節(jié)點(diǎn)又屬于N6節(jié)點(diǎn)。

圖1 模型分割及二叉樹生成

2 KD-Tree的遍歷

2.1 KD-Tree節(jié)點(diǎn)線索的生成

為實(shí)現(xiàn)KD-Tree的無堆棧遍歷，本文通過線索指針的方式建立節(jié)點(diǎn)之間的索引。Popov等提出了一種KD-Tree的線索創(chuàng)建算法，該方法現(xiàn)常被用于KD-Tree的無堆棧遍歷[10]，文獻(xiàn)[11]根據(jù)其算法思想進(jìn)行了一定程度的簡(jiǎn)化與改進(jìn)，提出了一個(gè)節(jié)點(diǎn)間線索建立算法。“線索”實(shí)際上是KD-Tree節(jié)點(diǎn)之間的指向關(guān)系。線索建立的過程分為“繼承”和“更新”，“繼承”是指節(jié)點(diǎn)首先要繼承其父節(jié)點(diǎn)的所有線索信息，“更新”是指更新節(jié)點(diǎn)分割軸方向上的指向關(guān)系。平面包圍盒剖分結(jié)果及射線過程如圖2(a)所示，下面通過圖2(a)介紹傳統(tǒng)與改進(jìn)后建立線索的方式。以3號(hào)與6號(hào)節(jié)點(diǎn)為例，通過傳統(tǒng)方式建立線索時(shí)，3號(hào)節(jié)點(diǎn)首先繼承其父節(jié)點(diǎn)1號(hào)節(jié)點(diǎn)的線索信息，即x軸正向索引(以下簡(jiǎn)稱x+)、x軸負(fù)向索引(以下簡(jiǎn)稱x-)、y軸正向索引(以下簡(jiǎn)稱y+)、y軸負(fù)向索引(以下簡(jiǎn)稱y-)均為NULL，其次由于1號(hào)節(jié)點(diǎn)的分割軸為x軸，因此根據(jù)包圍盒的位置關(guān)系將3號(hào)節(jié)點(diǎn)的x-更新為2號(hào)節(jié)點(diǎn)，至此3號(hào)節(jié)點(diǎn)線索信息更新完畢；6號(hào)節(jié)點(diǎn)首先繼承其父節(jié)點(diǎn)3號(hào)節(jié)點(diǎn)的線索信息，即x-為2號(hào)節(jié)點(diǎn)，x+、y+、y-均為NULL；其次6號(hào)節(jié)點(diǎn)的父節(jié)點(diǎn)分割軸為y軸，所以將6號(hào)節(jié)點(diǎn)的y-更新為7號(hào)節(jié)點(diǎn)，6號(hào)節(jié)點(diǎn)的線索信息也更新完畢。

圖2 平面模型中射線追蹤路徑

傳統(tǒng)方式建立線索是在分割形成節(jié)點(diǎn)的同時(shí)就將節(jié)點(diǎn)線索隨之建立，當(dāng)其相鄰節(jié)點(diǎn)再度進(jìn)行分割后，分割信息無法及時(shí)反饋至先前節(jié)點(diǎn)中，因此無法達(dá)到最優(yōu)的線索指向關(guān)系。改進(jìn)后的方法優(yōu)化步驟主要在“更新”的過程中，每個(gè)節(jié)點(diǎn)在建立線索時(shí)需要了解其相鄰節(jié)點(diǎn)的完整分割信息，因此建立線索的過程需要在建樹完成后進(jìn)行。通過改進(jìn)方法建立線索時(shí)，3號(hào)節(jié)點(diǎn)依舊要先“繼承”1號(hào)節(jié)點(diǎn)的所有線索關(guān)系，在“更新”過程中，需要判斷3號(hào)節(jié)點(diǎn)的兄弟節(jié)點(diǎn)(2號(hào)節(jié)點(diǎn))的分割軸(x軸)與其父節(jié)點(diǎn)(1號(hào)節(jié)點(diǎn))的分割軸(x軸)是否相同，若相同則將3號(hào)節(jié)點(diǎn)的x-更新為2號(hào)節(jié)點(diǎn)的右孩子節(jié)點(diǎn)(5號(hào)節(jié)點(diǎn))，隨后繼續(xù)更新。更新完成的條件一是直到3號(hào)節(jié)點(diǎn)的x-為葉子節(jié)點(diǎn)，二是x-指向節(jié)點(diǎn)的分割軸與3號(hào)節(jié)點(diǎn)父節(jié)點(diǎn)(1號(hào)節(jié)點(diǎn))的分割軸不再相同。由于5號(hào)節(jié)點(diǎn)的分割軸仍與1號(hào)節(jié)點(diǎn)相同，因此最終3號(hào)節(jié)點(diǎn)的x-更新為9號(hào)節(jié)點(diǎn)；6號(hào)節(jié)點(diǎn)直接繼承3號(hào)節(jié)點(diǎn)索引，x-為9號(hào)節(jié)點(diǎn)，其余方向索引均為NULL，在更新過程中，由于6號(hào)節(jié)點(diǎn)的父節(jié)點(diǎn)(3號(hào)節(jié)點(diǎn))的分割軸為y軸，因此將6號(hào)節(jié)點(diǎn)y-更新為7號(hào)節(jié)點(diǎn)，更新結(jié)束。

對(duì)比之下，傳統(tǒng)方法建立線索時(shí)6號(hào)節(jié)點(diǎn)的x-指向的是2號(hào)節(jié)點(diǎn)，改進(jìn)后6號(hào)節(jié)點(diǎn)的x-指向的是9號(hào)節(jié)點(diǎn)，改進(jìn)后的方法得到了更優(yōu)的線索指向。

2.2 KD-Tree的遍歷過程

射線追蹤的過程實(shí)際上是射線遍歷線索KD-Tree尋找葉子節(jié)點(diǎn)并與節(jié)點(diǎn)內(nèi)三角面元進(jìn)行相交檢測(cè)的過程。圖2(a)演示了一條射線在平面模型中反射的路徑示意：

(1)射線通過入射位置定位到6號(hào)葉子節(jié)點(diǎn)，再通過Moller-Trumbore方法與節(jié)點(diǎn)內(nèi)部的三角面元遍歷求交，求出交點(diǎn)后更新射線為反射射線[12]；

(2)反射射線確定出射位置后查找線索確定下一個(gè)待遍歷節(jié)點(diǎn)為9號(hào)節(jié)點(diǎn)，遍歷節(jié)點(diǎn)內(nèi)面元求交，繼續(xù)更新反射射線，并通過出射位置查找對(duì)應(yīng)線索指向節(jié)點(diǎn)為8號(hào)節(jié)點(diǎn)，射線在8號(hào)節(jié)點(diǎn)內(nèi)繼續(xù)遍歷；

(3)在8號(hào)節(jié)點(diǎn)內(nèi)求得交點(diǎn)與反射射線后，射線進(jìn)入4號(hào)節(jié)點(diǎn)中遍歷后并未與節(jié)點(diǎn)中的三角面元發(fā)生相交，并且出射位置指向的線索為NULL，該條射線射出模型，遍歷結(jié)束。

因此，單根射線遍歷過程就是射線與葉子節(jié)點(diǎn)內(nèi)面元求交后，通過線索信息查找到下一個(gè)待遍歷的節(jié)點(diǎn)繼續(xù)求交，直到射線在某節(jié)點(diǎn)出射位置的線索指向NULL時(shí)，遍歷結(jié)束。射線在KD-Tree中的遍歷過程如圖2(b)所示，圖2(b)中虛線(實(shí)線)表示傳統(tǒng)(改進(jìn))線索建立方式下射線遍歷線索KD-Tree的過程，由圖可見，改進(jìn)后明顯減少了部分中間節(jié)點(diǎn)的遍歷，節(jié)省了開銷。

3 射線追蹤并行計(jì)算

傳統(tǒng)串行計(jì)算中，未進(jìn)行追蹤的單根射線需要等待在其之前的射線追蹤完畢后，方可執(zhí)行計(jì)算，而每根射線在與三角面元求交時(shí)都會(huì)產(chǎn)生巨大的時(shí)間開銷，使得串行計(jì)算效率低下。單根射線在追蹤過程中都是相互獨(dú)立的，因此很適合采用GPU對(duì)射線追蹤計(jì)算過程進(jìn)行并行加速，提高計(jì)算效率。

3.1 CUDA并行編程模型

CUDA是一種CPU與GPU相結(jié)合的異構(gòu)運(yùn)算平臺(tái)，它將CUDA C語(yǔ)言作為編程語(yǔ)言，并由CPU負(fù)責(zé)處理邏輯關(guān)系復(fù)雜的事務(wù)，GPU負(fù)責(zé)處理需要高度計(jì)算的事務(wù)。相應(yīng)的，CPU一般被稱作主機(jī)端(Host)，GPU一般被稱作設(shè)備端(Device)[13]。在CUDA編程中，運(yùn)行在GPU端的程序需要通過核函數(shù)(Kernel)“標(biāo)識(shí)”出來。

核函數(shù)的啟動(dòng)需要調(diào)度網(wǎng)格(Grid)、線程塊(Block)及線程(Thread)，這三者最高可組織為三維形式。三者二維類型的層次結(jié)構(gòu)如圖3所示：一個(gè)Grid中包含多個(gè)Block，一個(gè)Block中包含多個(gè)Thread[14]。其中Thread是執(zhí)行計(jì)算的單位，因此并行計(jì)算的過程實(shí)際上是每個(gè)Thread各自執(zhí)行Kernel的過程。

圖3 CUDA線程層次結(jié)構(gòu)

由于計(jì)算量的不同，在進(jìn)行并行計(jì)算時(shí)需要選擇合適的計(jì)算資源，即選取合適數(shù)量的Thread進(jìn)行計(jì)算，程序?qū)用嫔希ㄟ^線程塊數(shù)量(BlockperGrid)指定執(zhí)行計(jì)算的線程塊數(shù)量，通過塊內(nèi)線程數(shù)量(ThreadperBlock)指定每個(gè)線程塊中執(zhí)行計(jì)算的線程數(shù)量，分配的線程總數(shù)量通過線程塊數(shù)量與塊內(nèi)線程數(shù)量相乘得到。本文為進(jìn)行并行計(jì)算資源的合理分配，設(shè)置線程總數(shù)量與射線的數(shù)量保持接近，由于一般情況下BlockperGrid和ThreadperBlock都設(shè)置為32的倍數(shù)，為同時(shí)滿足這兩個(gè)條件，一些情況下射線數(shù)量會(huì)略大于線程總數(shù)量，這時(shí)需要少數(shù)線程執(zhí)行兩根射線的計(jì)算過程。

CUDA架構(gòu)可以調(diào)用GPU內(nèi)存資源對(duì)數(shù)據(jù)進(jìn)行處理，GPU內(nèi)存包括全局內(nèi)存、共享內(nèi)存、常量?jī)?nèi)存、紋理內(nèi)存等，各個(gè)存儲(chǔ)器的位置與特性不都相同。由于共享內(nèi)存讀寫速度快，但空間較小，而常量?jī)?nèi)存與紋理內(nèi)存只能進(jìn)行讀操作，因此本文將數(shù)據(jù)全部存至設(shè)備端全局內(nèi)存中，每個(gè)線程直接在全局內(nèi)存中進(jìn)行讀寫操作。

3.2 射線追蹤并行化過程

串行計(jì)算的全部過程在CPU上執(zhí)行，每條射線依次遍歷線索KD-Tree計(jì)算其在場(chǎng)景中的傳播路徑。將串行計(jì)算程序改為并行計(jì)算程序一般有兩種方法，一是整個(gè)過程直接由GPU完成，二是將需要高度計(jì)算的部分由GPU完成，其它的部分仍由CPU完成[15]。

在射線追蹤過程中，每條射線在場(chǎng)景中進(jìn)行彈射時(shí)是相互獨(dú)立的，因此將射線追蹤的計(jì)算過程進(jìn)行并行化的核心思想是將單根射線分配至GPU的單個(gè)核心進(jìn)行射線的路徑計(jì)算，對(duì)射線追蹤進(jìn)行并行化實(shí)現(xiàn)的方案如圖4所示，并行化過程中，構(gòu)建線索KD-Tree的任務(wù)邏輯比較復(fù)雜，因此由CPU完成；而射線遍歷線索KD-Tree的過程存在大量射線與節(jié)點(diǎn)內(nèi)三角面元的求交計(jì)算，因此需要由GPU并行完成。

圖4 射線追蹤并行化實(shí)現(xiàn)方案

由于CPU與GPU無法互相直接讀取存儲(chǔ)在對(duì)方內(nèi)存里的數(shù)據(jù)，因此需要進(jìn)行數(shù)據(jù)傳輸以完成計(jì)算。需要傳輸?shù)臄?shù)據(jù)分為兩部分：一部分是射線集合，一部分是線索KD-Tree節(jié)點(diǎn)。射線集合是預(yù)設(shè)條件，在CPU中靜態(tài)存儲(chǔ)，因此可以通過cudaMemcpy函數(shù)直接由CPU端拷貝至GPU端；本文在第1節(jié)末描述了構(gòu)成模型的三角面元都將分別存儲(chǔ)在各個(gè)葉子節(jié)點(diǎn)中，且剖分后每個(gè)葉子節(jié)點(diǎn)中面元數(shù)量并不相同，因此葉子節(jié)點(diǎn)指針需要?jiǎng)討B(tài)分配內(nèi)存，這造成KD-Tree無法直接通過cudaMemcpy函數(shù)進(jìn)行傳輸，本文通過計(jì)算建樹完成后每個(gè)葉子節(jié)點(diǎn)的內(nèi)存信息，并在GPU端開辟相同大小的內(nèi)存將其逐一拷貝，以實(shí)現(xiàn)葉子節(jié)點(diǎn)內(nèi)面元數(shù)據(jù)的傳輸。而對(duì)于根節(jié)點(diǎn)和中間節(jié)點(diǎn)，由于其內(nèi)的面元數(shù)據(jù)已被釋放，因此仍按照靜態(tài)存儲(chǔ)方式進(jìn)行拷貝。

數(shù)據(jù)傳輸完成后，由一個(gè)線程(Thread)負(fù)責(zé)一條射線的追蹤，多條射線并行進(jìn)行追蹤，得到每條射線的彈射次數(shù)及每次反射時(shí)發(fā)生相交的三角面元編號(hào)，最終將計(jì)算結(jié)果回傳至CPU。

4 仿真結(jié)果與討論

本文實(shí)驗(yàn)數(shù)據(jù)通過一臺(tái)計(jì)算機(jī)仿真得到，該計(jì)算機(jī)操作系統(tǒng)為Windows 10，CPU型號(hào)為Intel(R)Core(TM)i5-10210U CPU @ 1.60 GHz，GPU型號(hào)為NVIDIA GeForce MX350，編譯環(huán)境為Microsoft Visual Studio 2019(CPU端)，CUDA toolkit 11.4(GPU端)。

為對(duì)算法有效性進(jìn)行驗(yàn)證，本文模擬射線在T型腔內(nèi)進(jìn)行彈射，并對(duì)其軌跡進(jìn)行追蹤。腔體及發(fā)射源如圖5所示，圖5(a)為通過ANSYS Mechanical APDL 16.0對(duì)腔體表面進(jìn)行三角網(wǎng)格剖分，剖分后三角面元總數(shù)為9478，圖5(b)為腔體模型在y軸方向上的長(zhǎng)度為4.5 m，x軸、z軸方向上的長(zhǎng)度分別為通過1 m、0.5 m，腔體的3個(gè)開口面邊長(zhǎng)均為0.5 m。x軸方向上的腔體開口0.05 m處設(shè)置0.5 m×0.5 m的虛擬散點(diǎn)面，射線源點(diǎn)與散點(diǎn)面上的散點(diǎn)構(gòu)成射線集合。射線可以通過出射面射出。實(shí)際應(yīng)用中，射線一般是電磁波、聲波等，多次反射后會(huì)有能量衰減，因此設(shè)置射線在腔體內(nèi)的彈射次數(shù)最多不超過30次。

圖5 腔體及發(fā)射源

表1對(duì)比了在射線數(shù)目為1500，KD-Tree樹高為6，節(jié)點(diǎn)總數(shù)為63、其中葉子節(jié)點(diǎn)總數(shù)為32時(shí)，線索建立方式改進(jìn)前后遍歷節(jié)點(diǎn)數(shù)量的變化及串行、并行計(jì)算所耗費(fèi)的時(shí)間，由表1可以看出，改進(jìn)后的線索建立方式比改進(jìn)前遍歷節(jié)點(diǎn)數(shù)量減少了4832，減少了射線查找KD-Tree尋找葉子節(jié)點(diǎn)過程的開銷。從運(yùn)行時(shí)間上看，無論是串行計(jì)算還是并行計(jì)算，改進(jìn)后算法的程序執(zhí)行效率比改進(jìn)前都有一定程度的提高。

表1 不同線索建立方式計(jì)算時(shí)間

實(shí)際情況中，運(yùn)用射線追蹤算法對(duì)目標(biāo)進(jìn)行特性分析時(shí)，為了得到精確的計(jì)算結(jié)果，往往需要發(fā)射大量射線進(jìn)行追蹤，因此本文討論了射線數(shù)量成倍增長(zhǎng)的情況下并行計(jì)算相比于串行計(jì)算的效率提升。當(dāng)KD-Tree樹高為6，線程塊與塊內(nèi)線程數(shù)同為128，射線數(shù)目變化的情況下，CPU、GPU端的計(jì)算時(shí)間見表2。從表2中的時(shí)間及加速比可以得知，射線數(shù)目數(shù)量級(jí)增長(zhǎng)時(shí)，加速效果越來越好，當(dāng)射線數(shù)目達(dá)到十萬(wàn)數(shù)量級(jí)時(shí)，加速比達(dá)到20倍左右。實(shí)際場(chǎng)景中的射線數(shù)目往往更加巨大，因此，通過GPU并行計(jì)算得到的效率提升會(huì)越來越明顯。

表3給出了在射線數(shù)目為15 000，線程塊與塊內(nèi)線程數(shù)同為128時(shí)，KD-Tree構(gòu)建不同時(shí)的程序運(yùn)行時(shí)間，從表中可以看出，對(duì)于串行計(jì)算來說，樹高越高程序運(yùn)行速核度越快，這是由于CPU適合處理KD-Tree這類邏輯結(jié)構(gòu)較強(qiáng)的事務(wù)，葉子節(jié)點(diǎn)數(shù)量越多，內(nèi)部三角面元數(shù)量越少，射線遍歷節(jié)點(diǎn)的速度越快；對(duì)于并行計(jì)算來說，GPU核心處理復(fù)雜邏輯事務(wù)的能力相比CPU較差，分支過多時(shí)，運(yùn)行時(shí)間部分花費(fèi)在遍歷樹尋找節(jié)點(diǎn)的過程中，但分支過少時(shí)又會(huì)有大量的無效求交計(jì)算，因此在樹高太高、太低時(shí)都會(huì)對(duì)程序的執(zhí)行效率造成影響。

表2 射線數(shù)目變化對(duì)運(yùn)行時(shí)間的影響

表3 KD-Tree層高對(duì)運(yùn)行時(shí)間的影響

函數(shù)參數(shù)配置對(duì)程序運(yùn)行效率也有一定影響，合理的參數(shù)配置更容易使得資源得到合理利用。核函數(shù)參數(shù)配置主要體現(xiàn)在線程塊數(shù)量(BlockperGrid)以及塊內(nèi)線程數(shù)量(ThreadperBlock)，表4是在射線數(shù)目為15 000、KD-Tree層高為6時(shí)，BlockperGrid和ThreadperBlock不同的情況下程序的運(yùn)行時(shí)間。由表可知，當(dāng)BlockperGrid和ThreadperBlock都設(shè)置為128時(shí)程序運(yùn)行效果最好。其中ThreadperBlock對(duì)程序運(yùn)行時(shí)間影響更大，這是由于線程是執(zhí)行計(jì)算的單位，程序會(huì)將一些寄存器分配給每個(gè)線程，寄存器的讀寫速度比全局內(nèi)存快，如果ThreadperBlock設(shè)置太大容易造成可分配寄存器數(shù)量不足，線程將從全局內(nèi)存讀取數(shù)據(jù)，全局內(nèi)存的訪問延遲高于寄存器因此會(huì)造成運(yùn)行時(shí)間增多；而ThreadperBlock設(shè)置太小又會(huì)造成一些寄存器資源浪費(fèi)，同樣會(huì)對(duì)運(yùn)行時(shí)間造成影響。

表4 核函數(shù)參數(shù)配置對(duì)運(yùn)行時(shí)間的影響

5 結(jié)束語(yǔ)

本文首先介紹了一種KD-Tree線索建立方式，并進(jìn)行了有效性驗(yàn)證，其次針對(duì)傳統(tǒng)的基于線索KD-Tree的射線追蹤串行計(jì)算進(jìn)行并行化實(shí)現(xiàn)，并對(duì)改變前后的運(yùn)行時(shí)間進(jìn)行了對(duì)比，實(shí)驗(yàn)數(shù)據(jù)表明并行算法使得計(jì)算效率得到提高，計(jì)算時(shí)間大大減少，此外還探討了KD-Tree的構(gòu)建質(zhì)量以及核函數(shù)參數(shù)的設(shè)置對(duì)于程序執(zhí)行效率的影響。在以后的研究中，還需要考慮以下問題，GPU全局內(nèi)存的讀寫速度相比于其它內(nèi)存較慢，可以將模型數(shù)據(jù)在不同內(nèi)存區(qū)進(jìn)行合理的規(guī)劃分配，進(jìn)一步提高計(jì)算效率。