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

梁 曉，黃 韻

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

梁 曉1，黃 韻2

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

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

光線跟蹤；陰影光線遍歷；層次加速結構；分支預測

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

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

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

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

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

1 相關工作

1.1 加速結構的構建

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

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

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

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

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

1.2 加速結構的遍歷

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

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

2 本文算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實驗結果與分析

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

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

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

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

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

場景算法遮擋光線非遮擋光線遍歷時間(s)預計算時間(s)內存開銷(M) 節點相交測試數/光線圖元相交測試數/光線節點相交測試數/光線圖元相交測試數/光線 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之間，與預期相符合，說明圖元的選擇機制是有效的。

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

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

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

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

4 結 論

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

[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] 過潔, 徐曉旸, 潘金貴. 虛擬場景的一種快速優化Kd-Tree構造方法[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-)，女，四川成都人，講師，博士，碩士生導師。主要研究方向為計算機圖形學、真實感繪制等。E-mail：xiaoliang.edu@foxmail.com