基于多索引樹的陰影光線遍歷算法

梁 曉，黃 韻

基于多索引樹的陰影光線遍歷算法

梁 曉1，黃 韻2

(1. 西南石油大學計算機科學學院，四川 成都 610500；2.西南石油大學材料科學與工程學院，四川 成都 610500)

陰影光線求交計算是光線跟蹤的重要計算瓶頸。然而，構(gòu)造一棵能有效剔除陰影光線冗余求交計算的標準樹結(jié)構(gòu)仍然十分困難。為區(qū)分遮擋和非遮擋的陰影光線，提出一種基于多索引樹的遍歷方法，在節(jié)點中增加提升遍歷速度的索引。首先，針對遮擋光線為盡快與圖元相交的遍歷特征，選擇性的將位于葉節(jié)點上、對光線遮擋概率高的圖元索引到中間節(jié)點，促使光線提前在樹中層停止搜索。其次，針對非遮擋光線為盡快搜索最鄰近節(jié)點的遍歷特征，為底層節(jié)點建立鄰接索引，減少節(jié)點搜索空間。利用幀間相關(guān)性預(yù)測遮擋類型，采用相應(yīng)遍歷方法進行針對性的加速。相比專有樹結(jié)構(gòu)的遍歷算法，該算法將遍歷時效率提升20%以上，具有更好的遍歷性能，且預(yù)計算時間更少。

光線跟蹤；陰影光線遍歷；層次加速結(jié)構(gòu)；分支預(yù)測

光線跟蹤，是當前應(yīng)用最廣泛的真實感繪制方法之一，廣泛應(yīng)用于影視特效、工業(yè)設(shè)計、游戲等領(lǐng)域。其原理是通過遞歸的追蹤從視點投射到三維虛擬場景中的主光線、陰影光線、二次光線，以產(chǎn)生高級光照效果。其中，陰影能有效反映物體的形狀、空間關(guān)系、光源位置等信息，被認為是最重要的全局光照效果之一。對于復(fù)雜場景，陰影光線數(shù)量占到了場景中所有光線的絕大部分，即使采用加速結(jié)構(gòu)，例如KD-Tree[1]、BVH[2]，陰影光線的快速求交計算仍然是光線跟蹤領(lǐng)域的重要難題。

經(jīng)典的陰影光線遍歷算法中存在大量冗余的求交計算。陰影光線僅需計算與場景的“任意交點”，而經(jīng)典算法按照光線方向從前向后的順序最終計算的是與場景的“最近交點”。通常，最近的圖元并不一定是求交計算量最小的圖元。

陰影光線遍歷的加速方法可分為：①基于已有樹結(jié)構(gòu)的分支預(yù)測遍歷方法[3-4]。該方法與主光線、二次光線共用加速結(jié)構(gòu)，評估子樹的遍歷代價，并讓光線優(yōu)先與預(yù)測代價更小、或具有更低深度的子樹求交。但僅能提前終止遮擋陰影光線的遍歷過程，無法減少非遮擋陰影光線的冗余計算，通常后者比前者的計算量更大。②針對陰影加速而設(shè)計的專有樹結(jié)構(gòu)[5]，用于陰影光線遍歷。盡管可同時降低2類陰影光線的求交計算量，卻需要額外產(chǎn)生新的樹結(jié)構(gòu)，預(yù)計算時間非常長，內(nèi)存開銷增加顯著。

以上2類方法都是在標準樹結(jié)構(gòu)上計算求交測試更少的遍歷路徑，其本質(zhì)是相同的。標準樹結(jié)構(gòu)是一棵二叉樹，為便于自上而下、逐步求精的遍歷，中間節(jié)點記錄直接子節(jié)點索引，葉節(jié)點記錄圖元索引。然而，對于陰影光線遍歷，構(gòu)造一棵能有效剔除冗余求交計算的標準樹結(jié)構(gòu)，不僅預(yù)計算量大，而且十分困難。因為樹中節(jié)點僅具有一種索引類型，并用于描述嚴格的層次包含關(guān)系，本身僅適用于減少以求“最近交點”為目的的光線求交計算。實際上，陰影光線分為遮擋和非遮擋光線2類，前者以盡快與圖元相交為目的，后者需要造訪整個樹空間，以盡快搜索最鄰近節(jié)點為目的。因此，若在現(xiàn)有樹結(jié)構(gòu)中，以索引的形式增加提升遍歷速度的多類節(jié)點關(guān)系描述，不僅能夠剔除冗余的求交計算，并且具有較小的計算量。

本文提出一種基于多索引樹的陰影光線遍歷算法，利用遮擋和非遮擋陰影光線各自的遍歷特征，分別為節(jié)點增加圖元索引和鄰接索引來降低冗余求交測試。對于遮擋陰影光線，選擇性的將位于葉節(jié)點上、對光線遮擋概率高的圖元索引到中間節(jié)點，促使光線提前在樹中層停止搜索。對于非遮擋陰影光線，為節(jié)點建立鄰接索引，用于訪問最近鄰節(jié)點，大幅度降低節(jié)點的搜索空間；并按需建立鄰接索引，減少索引產(chǎn)生的內(nèi)存開銷。同時利用幀間相關(guān)性預(yù)測光線的遮擋類型，使用對應(yīng)的遍歷加速算法，降低相交測試開銷。實驗顯示，對于復(fù)雜場景，算法在陰影光線遍歷時效率提升20%以上。相比專有樹結(jié)構(gòu)算法，具有更好的遍歷性能，且預(yù)計算時間和內(nèi)存開銷僅是后者的21%和48%。

1 相關(guān)工作

1.1 加速結(jié)構(gòu)的構(gòu)建

在樹結(jié)構(gòu)中，選擇節(jié)點分割平面是影響加速結(jié)構(gòu)質(zhì)量的重要因素。通常，預(yù)測光線的遍歷代價，即光線與節(jié)點、圖元的相交代價，作為產(chǎn)生最優(yōu)分割平面的指導(dǎo)。最具代表性的是表面積啟發(fā)式代價模型(surface area heuristic，SAH)[6]。SAH算法對場景進行了若干簡化假設(shè)，包括光線在空間均勻分布，不會因為與圖元相交而終止傳播等。給定節(jié)點，其遍歷代價表示為

其中，c和c分別為節(jié)點、圖元相交測試代價；n和n為左、右節(jié)點N和N的圖元數(shù)目；()為包圍盒表面積。在構(gòu)建時，算法在候選分割平面集合中選擇具有最小代價值的平面作為當前的最優(yōu)劃分，并產(chǎn)生子節(jié)點。

SAH算法計算量很大，文獻[7]在分割軸開區(qū)間進行離散采樣來近似遍歷代價。此外，基于多核CPU[8]、基于GPU的構(gòu)建算法[9]解決節(jié)點計算負載均衡、局部訪存等問題，從不規(guī)則層次構(gòu)建算法的并行化中來獲取大量性能提升。

SAH算法中的諸多簡化假設(shè)降低了預(yù)測代價的準確性。為此，研究者分別對KD-Tree和BVH提出了不同的高質(zhì)量樹構(gòu)建方法。文獻[10]采用模擬退火思想搜索最優(yōu)分割平面，避免局部最小值。對于BVH，通常采用“快速構(gòu)建，逐步優(yōu)化”的思想提高樹質(zhì)量。文獻[11]搜索構(gòu)建質(zhì)量較低的節(jié)點，并旋轉(zhuǎn)節(jié)點來更新結(jié)構(gòu)。文獻[12]選擇低質(zhì)量節(jié)點及分支，并在全局空間中搜索新插入位置。

為減少陰影光線遍歷代價，文獻[5]提出陰影光線代價模型(shadow ray distribution heuristic，SRDH)，建立一棵面向陰影光線遍歷的專用樹結(jié)構(gòu)，能夠減少遮擋和非遮擋2類光線的冗余測試，卻伴隨著巨大的時間和內(nèi)存開銷。

1.2 加速結(jié)構(gòu)的遍歷

針對GPU內(nèi)存存儲限制，文獻[13]提出無棧遍歷算法—KD-Restart和KD-Backtrack，通過增加大量冗余的節(jié)點訪問操作來移除對棧的依賴。文 獻[14]實現(xiàn)了基于KD-Tree的短棧遍歷方法，對共享分割面的中間節(jié)點創(chuàng)建鄰接索引，遍歷效率提高了17%以上，但內(nèi)存增加3倍以上。文獻[15]在BVH上實現(xiàn)短棧遍歷，利用重啟跟蹤降低入口點搜索的代價。

陰影光線的遍歷不受“從前向后”的順序約束，分支預(yù)測方法能快速搜索遮擋圖元。文獻[3]建立陰影光線代價模型，總是優(yōu)先遍歷代價較小的節(jié)點。文獻[4]提出表面積遍歷策略組合(surface area traversal order，SATO)算法，將遍歷序列優(yōu)先分配給有特殊幾何特征的節(jié)點，特征包括包圍盒表面積、圖元面積和數(shù)目。該算法預(yù)計算快，遍歷速度優(yōu)于其他啟發(fā)式算法，但每種策略有不同的適應(yīng)場景。以上算法僅能降低遮擋光線的遍歷代價，而本文修改了樹結(jié)構(gòu)，使用較少的預(yù)計算，同時降低了遮擋和非遮擋光線的遍歷代價。

2 本文算法

在標準樹結(jié)構(gòu)上，陰影光線從樹根節(jié)點出發(fā)，自頂向下的搜索遮擋圖元。一旦與圖元相交，遍歷過程立即停止，判定為遮擋陰影光線(簡稱遮擋光線)；若遍歷完樹空間都沒有與任何圖元相交，判定為非遮擋陰影光線(簡稱非遮擋光線)。然而，2類光線具有不同的求交特征，其在標準樹結(jié)構(gòu)上進行遍歷時均存在冗余相交。本文提出一種基于多索引樹的陰影光線遍歷算法，利用2類光線的遍歷特征，為節(jié)點增加圖元索引和鄰接索引來降低冗余的求交測試，如圖1所示。

(a) 場景劃分與虛擬 3D網(wǎng)格(b) 圖元索引和 鄰接索引

對于遮擋光線，提出一種基于圖元索引的遍歷方法。從葉節(jié)點選擇光線相交概率大的圖元直接索引到適當?shù)闹虚g節(jié)點，使遮擋光線提前在樹中層終止搜索。該圖元稱為中間圖元。如圖1所示，給定子樹，t、2為葉節(jié)點上的圖元，并相對于其他圖元具有更高的相交率。將圖元t、t直接索引在節(jié)點和，使得進入到該類節(jié)點光線與t和t相交而提前終止搜索。

對于非遮擋光線，為底層相鄰節(jié)點添加鄰接索引，使光線利用鄰接索引直接進入下一個節(jié)點，避免了大量自頂向下的搜索測試。其中，為每個節(jié)點添加鄰接索引將大幅度增加內(nèi)存開銷。然而，與其他類光線不同，陰影光線的分布是不均勻的。如圖1所示，光源位于節(jié)點，若節(jié)點是主光線不可見的，并不會產(chǎn)生陰影光線。因此，節(jié)點的所有鄰接索引對陰影光線遍歷沒有貢獻。為此，從光源所在節(jié)點出發(fā)，逆向的為相鄰節(jié)點建立索引。

2.1 基于圖元索引的遍歷方法

為使遮擋光線在遍歷過程中提前與潛在相交圖元進行測試，本文算法選擇圖元并索引在中間節(jié)點。中間圖元的選擇以及新的索引位置，對遍歷代價的影響非常關(guān)鍵。所有進入帶圖元中間節(jié)點的光線都將與該圖元進行相交測試。若大部分相交測試失敗，產(chǎn)生額外的相交代價將大于遍歷收益。為此，在不同索引位置評估候選索引圖元引入的遍歷開銷差，以選擇合適的子樹來索引圖元。

(1) 選擇候選圖元。理想的候選圖元能夠與更多的光線相交。直觀的、在光線均勻分布情況下，圖元相對光源的空間角越大，可能遮擋的光線就越多。為此，本文算法設(shè)置包圍盒表面積閾值，若圖元的包圍盒表面積與場景平均圖元包圍盒表面積之比超過閾值，加入候選圖元隊列。閾值取值隨場景圖元形狀的規(guī)則影響，通常設(shè)為[0.45~0.60]。

(2) 給定子樹和候選圖元，算法評估新增圖元在子樹產(chǎn)生的遍歷代價。新增圖元索引后，子樹的遍歷代價主要包括與中間圖元相交、并終止搜索的光線遍歷代價，和與中間圖元沒有相交、并需要進入下層子樹并繼續(xù)測試的遍歷代價，即

其中，()為新增圖元后的遍歷代價；()為圖元與光線相交的概率，由圖元包圍盒和節(jié)點包圍盒表面積之比表示；(T)和(T)分別為左、右子樹的遍歷代價，并使用SAH模型計算。

由于式(2)計算的是本地代價，不能用來選擇最佳索引位置。在此基礎(chǔ)上，用圖元索引前、后的遍歷代價之比，來評估圖元在不同子樹中的遍歷代價降低率?？紤]到圖元索引的深度越低，對全局遍歷代價的影響越大，且影響是非線性的。引入受索引深度變化的指數(shù)曲線來描述遍歷代價降低率，即

其中，通常取值為0.6；為索引深度。由于索引位置過高或過低，不會大幅度降低遍歷代價，通常將索引深度控制在樹的中間層內(nèi)。

為減少中間圖元產(chǎn)生的額外圖元相交測試，本文算法謹慎的選擇圖元并索引中間節(jié)點。對每個候選圖元，利用式(3)自底向上的評估遍歷代價降低率，從中選擇具有最大收益的節(jié)點作為其最佳索引位置，當收益率大于預(yù)定法閾值，將圖元索引到對應(yīng)節(jié)點上。本文算法仍然為中間圖元保留了樹底層的索引，以降樹結(jié)構(gòu)修改的代價；并為光線記錄了已經(jīng)執(zhí)行過測試的中間圖元，以避免冗余測試。文獻[16]算法也將圖元索引在樹中，但本文與其不同之處在于：圖元索引的目的不同，前者用于降低內(nèi)存開銷，而本文旨在提高遮擋光線遍歷效率；圖元選擇的方法不同，前者需要大量的重構(gòu)計算來選擇最佳圖元以及索引位置。

2.2 基于鄰接索引的遍歷方法

本文為底層節(jié)點建立鄰接索引，用于訪問下一個節(jié)點。鄰接關(guān)系是指2個節(jié)點的軸對齊包圍盒具有共面關(guān)系。鄰接關(guān)系是指2個節(jié)點的軸對齊包圍盒具有共面關(guān)系。然而，為每個節(jié)點創(chuàng)建鄰接關(guān)系會導(dǎo)致樹結(jié)構(gòu)增加3~4倍以上。由于陰影光線的起點以及光源位置是已知的，利用陰影光線分布，按需建立鄰接索引以減少冗余的索引關(guān)系。

步驟1.標記主光線可見區(qū)域。標記底層節(jié)點的可見性，若包含可見的圖元，該區(qū)域是可見的。

步驟2.建立虛擬網(wǎng)格作為輔助結(jié)構(gòu)，將可見區(qū)域映射到網(wǎng)格中，判斷2個可見區(qū)域是否具有鄰接關(guān)系。如圖1(a)所示，將每個可見區(qū)域包圍盒所在平面映射到網(wǎng)格，得到體素集合。體素1包含的節(jié)點和，體素2包含節(jié)點和。當且僅當2個節(jié)點在同一體素時，則存在潛在的鄰接關(guān)系。

步驟3.從每個光源所在節(jié)點開始搜索，逆向的建立節(jié)點間的鄰接索引。首先將光源所在節(jié)點加入到隊列中；其次，取出隊列中的首節(jié)點，對所有鄰接節(jié)點按照步驟4判定鄰接面，并將該所有鄰接節(jié)點加入到隊列尾部；直到隊列為空。

步驟4.比較2個節(jié)點的軸對齊包圍盒的最值，判定產(chǎn)生鄰接關(guān)系的包圍盒面，并將對方節(jié)點地址記錄到相應(yīng)的索引分量上。例如相鄰節(jié)點和包圍盒的最值有如下關(guān)系，若min.和min.相同，的right面與的left面共面。

若幀間變化劇烈，部分區(qū)域的鄰接索引可能并不完整。如圖1(a)所示，若第幀中節(jié)點不可見，其鄰接索引為空；在第+1幀中，若是可見的，出射的陰影光線與右側(cè)面相交后，將沒有鄰接索引用于直接訪問下一個最近節(jié)點。對此類情況，需要從根節(jié)點開始進行遞歸測試。然而，實驗數(shù)據(jù)顯示，此類區(qū)域和光線非常少，并不影響遍歷性能。

2.3 基于多索引樹的遍歷方法

利用幀間和空間相關(guān)性，預(yù)測光線遮擋類型，調(diào)用相應(yīng)方法進行針對性的遍歷加速。將屏幕劃分為×區(qū)域，在第幀中，每個區(qū)域選擇1條光線跟蹤并記錄是否與圖像相交的遍歷結(jié)果；在第+1幀中，查詢上一幀在當前子區(qū)域的采樣結(jié)果，用于選擇遍歷算法。由于是先預(yù)測類型再進行遍歷，可能存在對非遮擋光線使用了圖元索引遍歷，對遮擋光線使用了鄰接索引遍歷。前者不會增加計算步驟；后者可能會帶來更多的遍歷步驟。若預(yù)測準確，這類光線非常少，并不會影響整體遍歷性能。

3 實驗結(jié)果與分析

實現(xiàn)了基于多索引樹的陰影光線遍歷算法，用于基于KD-Tree的光線跟蹤繪制。測試平臺為Intel(R) i5-3230 CPU，8 G內(nèi)存，NVIDIA GeForce GTS 450圖形顯卡。本文算法與標準遍歷算法、SATO[4]和SRDH[5]3種算法進行對比。選擇具有不同幾何特征以及陰影光線遮擋率的測試場景，如圖2所示，并以1024×1024分辨率進行繪制。

為衡量算法對遍歷代價的影響，分別測試了遮擋和非遮擋光線的相交測試數(shù)，見表1，標準遍歷算法是測試基準。SATO算法沒有改變非遮擋光線的節(jié)點、圖元相交測試數(shù)，本文算法沒有改變非遮擋光線的圖元相交測試數(shù)，其對應(yīng)測試項均標記為空。

(1) 評估算法對遮擋光線遍歷性能的影響。由表1可知，本文算法降低了所有場景的相交測試數(shù)，節(jié)點、圖元相交測試數(shù)分別減少了18.5%~31.7%和0.4%~33%。與SATO算法相比，本文算法在2項相交測試數(shù)上均能夠獲得更高的降低率。當且僅當最近圖元位于更深子樹時，SATO算法將優(yōu)先與其他分支上、遍歷代價更少的圖元進行測試，其減少的遍歷代價來自于2個分支的深度差產(chǎn)生節(jié)點相交測試計算量。若場景不滿足此條件，并不能明顯的降低遍歷效率。而本文算法并不受最近圖元分布的影響，將潛在相交圖元提前索引在樹中層，剔除了索引位置所在節(jié)點以下子樹的相交測試，減少的計算量通常大于前者。此外，與SRDH算法相比，本文算法仍然能夠獲得近似甚至更高的降低率。

(a) Bedroom(4個點光源，光線數(shù)為3.9 M，遮擋率為74.3%，圖元數(shù)為361 754)(b) Sponza(1個面光源，采樣率為4，光線數(shù)為4.1 M，遮擋率為72.2%，圖元數(shù)為66 450)(c) Conference(1個面光源，光線數(shù)為8.3 M，遮擋率為34.3%，圖元數(shù)為282 755)(d) FairyForest(2個面光源，采樣率為2，光線數(shù)為4.7 M，遮擋率為81.3%，圖元數(shù)為174 117)

表1 陰影光線遍歷性能對比

場景算法遮擋光線非遮擋光線遍歷時間(s)預(yù)計算時間(s)內(nèi)存開銷(M) 節(jié)點相交測試數(shù)/光線圖元相交測試數(shù)/光線節(jié)點相交測試數(shù)/光線圖元相交測試數(shù)/光線 Bedroom標準54.247.961.739.62.21–– SATO52.0 (–4.1%)41.0 (–14.4%)––2.020.19– SRDH44.0 (–18.8%)38.2 (–20.3%)58.0 (–6.0%)37.0 (–6.6%)1.931.4713.7 本文37.0 (–31.7%)32.1 (–33.0%)39.0 (–36.8%)–1.710.30(52%) Sponza標準32.627.348.841.82.09–– SATO39.0 (+19.5%)32.5 (+19.1%)––2.130.05– SRDH30.0 (–8%)23.0 (–15.8%)46.0 (–5.7%)40.0 (–4.3%)1.870.333.06 本文23.0 (–29.4%)19.0 (–30.4%)35.0 (–28.3.0%)–1.670.10(48%) Conference標準32.039.724.422.03.20–– SATO29.0 (–9.4%)36.7 (–7.6%)––3.070.17– SRDH30.0 (–6.3%)31.0 (–21.9%)24.0 (–1.6%)20.0 (–9.1%)2.821.136.89 本文24.0 (–25%)29.0 (–27%)17.0 (–30.3%)2.500.28(67%) FairyForest標準57.725.960.041.82.60–– SATO57.0 (–1.2%)24.7 (–4.6%)––2.420.12– SRDH49.0 (–14%)22.0 (–15.1%)55.0 (–8.3%)36.0 (–13.9%)2.160.746.99 本文47.0 (–18.5%)23.2 (–10.4%)41.0 (–31.7%)–2.210.32(105%)

為進一步分析中間圖元的選擇和索引位置的合理性，圖3描述了中間圖元的索引深度對遍歷代價的影響。通常，越多的遮擋光線與在較高層次的中間圖元相交，剔除的子樹空間越大。對于大部分場景，光線終止遍歷的深度位于樹的中上層，即范圍在10~19之間，與預(yù)期相符合，說明圖元的選擇機制是有效的。

(2) 本文算法對非遮擋光線遍歷性能的影響，見表1。在節(jié)點相交測試數(shù)方面，SRDH算法降低了5.7%~8.3%，本文算法為28.3%~36.8%，具有更顯著的降低率。盡管，SRDH算法重新劃分了場景，對非遮擋光線，僅能夠略微改變光線所經(jīng)過的葉節(jié)點上的圖元數(shù)，其對圖元相交測試的影響并不大。而節(jié)點相交測試，SRDH算法依賴于自頂向下的遍歷。本文算法通過鄰接索引直接計算最近鄰接點，剔除了大量自頂向下的搜索過程，減少了更多的子樹相交測試開銷。

圖3 中間圖元的索引深度對遍歷代價的影響

本文利用幀間相關(guān)性預(yù)測光線的遮擋類型，以調(diào)用更適合的遍歷算法。對部分非遮擋光線，不可避免的仍然使用的是標準自頂向下的遍歷算法。而見表1中此類光線數(shù)目非常少，并不會對非遮擋光線的遍歷性能提升有明顯影響。此外，本文算法對場景Bedroom和Sponza提高了20%的遍歷性能。

(3) 本文算法產(chǎn)生的預(yù)計算時間開銷和內(nèi)存開銷，見表1，括號內(nèi)值為相對于SRDH算法的內(nèi)存開銷減少量。在時間開銷方面，本文算法遠低于SRDH算法。盡管，相對于遍歷時間，在預(yù)計算上減少的絕對時間并不明顯。然而，目前的遍歷算法是跟蹤單根光線，若使用光束跟蹤，遍歷時間會進一步顯著降低。此時，預(yù)計算時間在整幀繪制時間中占更高比例，降低預(yù)計算時間的作用更明顯。相對于SATO算法，本文算法的預(yù)計算時間略高。但本文算法能同時提高2類光線的遍歷效率，總體遍歷性能明顯優(yōu)于SATO算法，并能夠適應(yīng)更多場景。因此，預(yù)計算時間的適當增加是能夠接受的。在內(nèi)存開銷方面，以SRDH算法作為測試基準。由于僅存儲可見區(qū)域底層節(jié)點的鄰接索引，本文算法產(chǎn)生的開銷僅是SRDH算法的48%~105%。

4 結(jié) 論

本文提出了一種基于多索引樹的陰影光線遍歷算法，通過增加圖元索引和鄰接索引，促使更多的遮擋光線在中間節(jié)點提前終止搜索；并減少非遮擋光線節(jié)點測試遍歷代價。陰影光線的幀內(nèi)相關(guān)性較強，利用SIMD指令進行光束跟蹤，通常會獲得比單根光線跟蹤更好的性能提升。對于動態(tài)光源，可進一步挖掘樹中節(jié)點關(guān)系，建立更靈活的訪問關(guān)系來提高遍歷效率。

[1] BENTLEY J L. Multidimensional binary search trees used for associative searching [J]. Communications of the ACM, 1975, 18(9): 509-517.

[2] RUBIN S M, WHITTED T. A 3-dimensional representation for fast rendering of complex scenes [J]. ACM SIGGRAPH Computer Graphics, 1980, 14(3): 110-116.

[3] IZE T, HANSEN C. RTSAH traversal order for occlusion rays [J]. Computer Graphics Forum, 2011, 30(2): 297-305.

[4] NAH J H, MANOCHA D. SATO: Surface area traversal order for shadow ray tracing [J]. Computer Graphics Forum, 2014, 33(6): 167-177.

[5] FELTMAN N, LEE M, FATAHALIAN K. SRDH: Specializing BVH construction and traversal order using representative shadow ray sets [C]//Proceedings of the 4th ACM SIGGRAPH/Eurographics conference on High-Performance Graphics. Goslar: Eurographics Association, 2012: 49-55.

[6] MACDONALD J D, BOOTH K S. Heuristics for ray tracing using space subdivision [J]. The Visual Computer, 1990, 6(3): 153-166.

[7] SHEVTSOV M, SOUPIKOV A, KAPUSTIN A. Highly parallel fast KD-tree construction for interactive ray tracing of dynamic scenes [J]. Computer Graphics Forum, 2007, 26(3): 395-404.

[8] CHOI B, KOMURAVELLI R, LU V, et al. Parallel SAH k-D tree construction [C]//Proceedings of the Conference on High Performance Graphics. Goslar: Eurographics Association, 2010: 77-86.

[9] PéRARD-GAYOT A, KALOJANOV J, SLUSALLEK P. GPU ray tracing using irregular grids [J]. Computer Graphics Forum, 2017, 36(2): 477-486.

[10] 過潔, 徐曉旸, 潘金貴. 虛擬場景的一種快速優(yōu)化Kd-Tree構(gòu)造方法[J]. 電子學報, 2011, 39(8): 1811-1817.

[11] KENSLER A. Tree rotations for improving bounding volume hierarchies [C]//2008 IEEE Symposium on Interactive Ray Tracing. New York: IEEE Press, 2008: 73-76.

[12] BITTNER J, MEISTER D. T-SAH: Animation optimized bounding volume hierarchies [J]. Computer Graphics Forum, 2015, 34(2): 527-536.

[13] Foley T. KD-tree acceleration structures for a GPU raytracer [C]//Proceedings of the ACM SIGGRAPH/ Eurographics Conference on Graphics hardware. New York: ACM, 2005: 15-22.

[14] POPOV S, GüNTHER J, SEIDEL H P, et al. Stackless KD-tree traversal for high performance GPU ray tracing [J]. Computer Graphics Forum, 2007, 26(3): 415-424.

[15] LAINE S. Restart trail for stackless BVH traversal [C]// HPG′10 Proceedings of the Conference on High Performance Graphics. Goslar: Eurographics Association, 2010: 107-111.

[16] CHOI B, CHANG B, IHM I. Improving memory space efficiency of kd-tree for real-time ray tracing [J]. Computer Graphics Forum, 2013, 32(7): 335-344.

A Shadow Ray Traversal Algorithm Based on Multiple-Index Tree

LIANG Xiao1, HUANG Yun2

(1. School of Computer Science, Southwest Petroleum University, Chengdu Sichuan 610500, China;2. School of Materials Science and Engineering, Southwest Petroleum University, Chengdu Sichuan 610500, China)

Shadow ray traversal is abig computation bottleneck in ray tracing. However, constructing an efficient tree to cull down redundant intersections is quite difficult. We propose a Multiple-index Tree based on shadow ray traversal algorithm, which adds indexes for nodes to accelerate traversal with acceptable pre-computation. First, since occluded rays try to intersect with primitive, we select primitives with high intersection probability from leaf nodes to store in inner nodes, which aims to stop traversal in upper tree. Second, since un-occluded rays try to find the nearest node, we create adjacency indexes between nodes in bottom tree, and use the indexes to access next node along ray direction directly. During traversal, by exploiting frame coherence, we estimate the occlusion type of rays and use corresponding method to reduce traversal cost. The experimental result suggest that the algorithm can improve traversal performance more than 20% for complex scenes. Even compared with tree reconstruction method, our method outperforms in reducing more intersections and only consumes 21% pre-computation time.

ray tracing; shadow ray traversal; hierarchy acceleration structure; branch decision

TP 391

10.11996/JG.j.2095-302X.2019030513

A

2095-302X(2019)03-0513-06

2018-11-15；

2018-12-02

西南石油大學啟航計劃項目(2015QHZ022)

梁 曉(1983-)，女，四川成都人，講師，博士，碩士生導(dǎo)師。主要研究方向為計算機圖形學、真實感繪制等。E-mail：xiaoliang.edu@foxmail.com