基于八叉樹鄰域分析的光線跟蹤加速算法

張文勝， 解 騫， 鐘 瑾， 劉俊平， 郝 青， 郭廣利

（1. 石家莊鐵道大學交通運輸學院，河北 石家莊 050043；2. 河北省交通安全與控制重點實驗室，河北 石家莊 050043；3. 石家莊市中醫(yī)院放射科，河北 石家莊 050011；4. 河北醫(yī)科大學第四醫(yī)院，河北 石家莊 050011）

基于八叉樹鄰域分析的光線跟蹤加速算法

張文勝1,3， 解 騫1,2， 鐘 瑾3， 劉俊平3， 郝 青4， 郭廣利3

（1. 石家莊鐵道大學交通運輸學院，河北 石家莊 050043；2. 河北省交通安全與控制重點實驗室，河北 石家莊 050043；3. 石家莊市中醫(yī)院放射科，河北 石家莊 050011；4. 河北醫(yī)科大學第四醫(yī)院，河北 石家莊 050011）

八叉樹是加速光線跟蹤常用的層次劃分結構，為加快八叉樹跟蹤光線的過程，論文研究了運用八叉樹鄰域分析提高光線與八叉樹節(jié)點之間的碰撞檢測速度的方法，提出了一種結構簡單、計算效率更高的八叉樹節(jié)點的鄰域分析算法。運用該算法可由現(xiàn)碰撞節(jié)點快速計算出下一碰撞節(jié)點，避免了采用大量遞歸搜索計算，從而提高了圖像的渲染速度。實驗結果表明，使用論文提出的鄰域分析進行碰撞檢測，效率比傳統(tǒng)算法提高了3倍以上，大大提高了光線跟蹤的速度。

光線跟蹤；八叉樹；鄰域分析；加速算法

將三維空間中復雜的三維場景投影到二維空間的視平面一直是計算機圖形學的研究熱點，其目的是為更加真實的渲染出受到光照、陰影和物體之間的反射光等因素影響的三維環(huán)境[1]。視平面上每個像素點的顏色都是由光線在三維空間中經(jīng)過若干次反射計算得出，跟蹤每條光線的路徑涉及到大量光線與物體之間的碰撞檢測[2]。為加速光線跟蹤的計算過程，人們提出了如空間網(wǎng)格法、層次包圍法等多種方法[3-4]。八叉樹結構是層次包圍法主要采用的一種層次劃分結構，它將三維空間分成具有一定層次性的空間單元。光線與空間單元進行初步碰撞檢測，若空間單元與光線不發(fā)生碰撞，則空間單元內的物體不再與光線做進一步碰撞檢測，可提高光線跟蹤的速度。

在初步檢測光線與八叉樹的碰撞時，需對八叉樹子節(jié)點進行遍歷，逐一判斷子節(jié)點是否與光線碰撞。由于圖形處理器(graphic processing unit, GPU)無法直接實現(xiàn)遞歸，限制了圖像顯示速度[5]。為此，Samet[6-7]提出了基于八叉樹鄰域分析的光線追蹤算法。該算法不再遍歷整個樹，而是搜索最小公共祖節(jié)點找到與光線相交的一系列相鄰節(jié)點來跟蹤光線。雖然該算法避免了搜索整個樹，但仍在小范圍內自下而上地搜索最小公共祖節(jié)點，沒能避免遞歸計算。Schrack[8]和肖樂斌[9]提出八叉樹鄰域節(jié)點的直接算法，通過研究八叉樹的位置編碼，發(fā)現(xiàn)八叉樹編碼規(guī)律與特性，對位置編碼加、減常數(shù)得出鄰域節(jié)點的編碼。但算法中加減的常數(shù)決定于節(jié)點的位置和計算方向等因素，涉及到另外一套復雜的計算方法，不能有效地加速光線追蹤。Voros[10]研究出了一種矩陣算法，將八叉樹的位置編碼轉化為矩陣，通過矩陣的計算得出鄰域節(jié)點，但矩陣的計算量會隨著矩陣階數(shù)的增加急劇增大，增加了光線跟蹤的空間復雜度。Sarah和Ronald[11]采用規(guī)則八叉樹的記錄方式，記下每個節(jié)點的父節(jié)點、子節(jié)點、坐標以及大小，以此計算出八叉樹鄰域節(jié)點。采用坐標計算鄰域節(jié)點的方法簡便直觀，但是規(guī)則八叉樹的儲存方式會大大增加節(jié)點的存儲空間，不利于發(fā)揮出八叉樹在節(jié)省柵格空間上的優(yōu)勢。Yoder和Bloniarz[12]發(fā)明了一張八叉樹鄰域分析表，根據(jù)表上的迭代方法，可計算不同方向的鄰域節(jié)點。這種方法非常實用，但同時受鄰域分析表的限制，無法在其基礎上改進利用，因此該方法也不適合應用于光線追蹤。近幾年，關于八叉樹鄰域分析未有突破性的研究成果，進而在加速光線跟蹤方面也沒有較大的發(fā)展。

本文從光線跟蹤出發(fā)，提出一種八叉樹鄰域分析新算法——0-1互換鄰域分析算法，只需對0、1編碼進行簡單的互換，即可得出6個方向的鄰域節(jié)點。因此，在加速光線跟蹤中，只根據(jù)光線在當前節(jié)點的穿出平面，就可直接計算出下個碰撞節(jié)點，最終無需采用搜索算法并能依次找出與光線碰撞的節(jié)點。同時在計算過程中高效地利用了三維空間中的坐標系，將0-1互換同三維坐標結合起來，提高了光線跟蹤的計算效率。

1 光線跟蹤與八叉樹

1.1 光線跟蹤

如圖 1所示，三維渲染中視點接收的每條光線，都是在場景中進行若干次反射，穿過視平面，射入視點。光線跟蹤則是沿著光線逆向檢測與之發(fā)生碰撞的物體，根據(jù)光線在物體表面的反射和折射光線確定視平面上像素點的顏色。用這種方法確定出視平面上每一個像素點的顏色，以生成三維場景的渲染圖像。

圖1 光線跟蹤示意圖

1.2 八叉樹

八叉樹是一種三維空間層次結構的劃分方案。構造一個能包含全部場景的最小軸對齊立方體，定義為最初根節(jié)點。將最初根節(jié)點沿軸向等分成8個子節(jié)點，將子節(jié)點遞歸等分，當八叉樹結構達到最大深度或子節(jié)點中包含的物體面片數(shù)少于某個預定值時，八叉樹層次空間構造結束。一般采用八進制的 Morton碼記錄劃分結束后每個節(jié)點的位置，如圖2所示，用0、1、2、3、4、5、6、7共8個數(shù)字來表示每次分裂后產生8個節(jié)點的標號，在逐級分割中，節(jié)點編碼的位數(shù)不斷增加[13]。

圖2 八叉樹劃分

1.3 八叉樹加速光線跟蹤

八叉樹結構廣泛應用于光線跟蹤的加速計算。如圖3所示，當光線在場景中行進時，也同時穿過八叉樹節(jié)點，根據(jù)八叉樹節(jié)點與場景中物體間的組織關系，將光線與物體的碰撞檢測簡化為先與八叉樹節(jié)點進行碰撞檢測，找到與光線發(fā)生碰撞的節(jié)點，再與節(jié)點內包含的物體進行碰撞檢測，能減少與不必要的物體進行碰撞檢測。因此，八叉樹結構對加快光線與物體之間的碰撞檢測具有重要意義。

圖3 光線碰撞檢測

2 基于鄰域分析的光線跟蹤算法

2.1 光線跟蹤與八叉樹鄰域分析

雖然使用八叉樹能夠加速光線跟蹤的計算，但在與八叉樹節(jié)點進行碰撞檢測中還是需要遍歷整個八叉樹，而遞歸計算是限制圖像顯示的一個主要因素。為此本文研究了采用八叉樹鄰域分析進行光線與八叉樹節(jié)點的碰撞檢測。如圖3所示，光線穿過的八叉樹節(jié)點是一系列相鄰節(jié)點（由節(jié)點1到2或由節(jié)點3到4再到5），因此采用八叉樹鄰域分析算法，由初始碰撞節(jié)點逐步計算光線所穿過的節(jié)點，能避免采用遞歸計算，進而加速光線追蹤的計算。

如圖4(a)所示，光線可看做從源點O發(fā)出、方向為單位向量d的射線，則光線上任一點P的參數(shù)化方程可表示為：P=O+td

圖4 光線與八叉樹節(jié)點碰撞求交

將光線與八叉樹的最初根節(jié)點求交，光線與最初根節(jié)點有兩個交點，根據(jù)交點的參數(shù)值t的大小，可明顯看出t值小的為光線與場景的初始碰撞點P0。根據(jù)P0點坐標計算出P0所在的葉子節(jié)點，即為初始碰撞節(jié)點N1。

將光線方程寫成函數(shù)形式：

其中，(x0, y0, z0)為源點O坐標，(i, j, k)表示光線方向d。

由N1的編碼計算出初始碰撞節(jié)點所構成的包圍盒，用xmin，ymin，zmin，xmax，ymax，zmax表示。令光線方程中x=xmin，x=xmax，y=ymin，y=ymax，z=zmin，z=zmax，求出光線與構造出N1包圍盒的6個平面的交點，再采用下面的不等式限制交點坐標在包圍盒內：

xmin≤x≤xmax

ymin≤y≤ymax

zmin≤z≤zmax

求出光線與包圍盒的兩個交點，其中一點與初始碰撞交點P0相同，定義為進盒交點P1，另一點定義為出盒交點 P2，如圖 4(b)所示。當光線從 P2穿出后，將進入下一節(jié)點，可看出P2是光線跟蹤從現(xiàn)節(jié)點到下一節(jié)點的橋梁。因此，如何不采用遍歷搜索方法，由P2直接求出下一碰撞節(jié)點是提高光線跟蹤效率的關鍵。P2是 N1所構成的包圍盒上的一點，根據(jù)P2的坐標和包圍盒的參數(shù)比較，容易看出P2從包圍盒6個方向（X+、X-、Y+、Y-、Z+、Z-）中哪個方向穿出，則下一節(jié)點就是 N1在穿出方向上的相鄰節(jié)點。

本文研究出一種求八叉樹相鄰節(jié)點的新算法——0-1互換算法，將八叉樹編碼中的八進制數(shù)轉換成只有0、1的二進制數(shù)，只對0、1進行變換即能求出光線穿出方向的下一碰撞節(jié)點，規(guī)避了遞歸求交，加速了光線跟蹤過程。

2.2 0-1互換鄰域分析光線跟蹤加速算法

為加速光線跟蹤的計算，本文放棄采用傳統(tǒng)的遍歷方式進行碰撞檢測，而是采用八叉樹鄰域分析，根據(jù)光線從現(xiàn)碰撞節(jié)點的穿出方向，求出下一碰撞節(jié)點。

如圖5所示，本文將圖2中八叉樹的編碼分為6個方向，X+={0,1,2,3}，X-={4,5,6,7}，Y+={2,3,6,7}，Y-={0,1,4,5}，Z+={0,2,4,6}，Z-={1,3,5,7}?？梢钥闯?，每個方向包含4個編碼，每個編碼屬于3個方向?；鶞氏虻膭澐质?-1互換算法用于光線跟蹤，分析各方向相鄰節(jié)點的基礎。

圖5 八叉樹基準向劃分

設跟蹤光線到節(jié)點N1，其八叉樹Morton碼為：

u1u2…uk

根據(jù)P2在N1包圍盒面的方位決定光線的穿出方向，光線跟蹤則是要求求出 N1在該方向的鄰域節(jié)點。N1有6個方向的鄰域節(jié)點：X+、X-、Y+、Y-、Z+、Z-，為求出不同方向的鄰域節(jié)點，本文將Morton碼中的八進制數(shù)轉化為二進制編碼(bx, by, bz)，二進制碼中的bx, by, bz分別賦予圖2中所規(guī)定的X, Y, Z軸向，對bx, by或bz做0-1互換則求出相應軸向上的鄰域節(jié)點。

算法具體如下：

(1) 提取出N1節(jié)點Morton碼的最后一位uk。

(2) 將提取出的八進制標號轉化為二進制編碼(bx, by, bz)，uk=4bx+2by+bz, bx、by、bz=0或1。

(3) 假設求 X+、X-向的鄰域節(jié)點，則對 bx做0-1互換：

假若bx=1，則bx=0

如果bx=0，則bx=1

若求Y、Z向的鄰域節(jié)點，同理對by，bz做0-1互換。

(4) 將互換后的二進制編碼再轉回八進制數(shù)vk，用vk替換掉Morton碼中的uk。

(5) 判斷vk在X軸上的基準向與鄰域分析方向是否相同。若不同，則提取出uk前一位標號uk-1，轉入步驟(2)；若相同，則計算結束。

以圖6中節(jié)點“255”為例：光線從“255”的Z+方向穿出，則要求出 Z+向鄰域節(jié)點。提取末位編碼“5”轉化為二進制編碼，得出(1,0,1)，將二進制編碼中代表 Z軸向的末位數(shù)“1”換成“0”，得出(1,0,0)，轉回八進制數(shù)得“4”，“4”屬于Z+向，與分析方向相同，計算結束，得出鄰域節(jié)點“254”。

圖6 光線與八叉樹碰撞示意圖

使用上述算法，發(fā)現(xiàn)計算出的鄰域節(jié)點與現(xiàn)碰撞節(jié)點大小相同，不能完全滿足跟蹤到下一節(jié)點的要求（如圖6中“254”節(jié)點到“61”節(jié)點），需對通過0-1互換計算出的鄰域節(jié)點進一步處理。

使用0-1互換計算出的鄰域節(jié)點存在不是光線跟蹤的下一節(jié)點的可能性，為此采用了如下的處理方法。首先判斷計算出的鄰域節(jié)點是否為八叉樹的葉子節(jié)點，若是，則說明計算出的鄰域節(jié)點即為下一碰撞節(jié)點。若不是，則再次判斷計算出的鄰域節(jié)點是否為八叉樹的枝節(jié)點，若不是枝節(jié)點，說明八叉樹在這一枝上沒有分割到計算出的鄰域節(jié)點的層次，下一節(jié)點是計算出的鄰域節(jié)點的父節(jié)點，需逐個減少鄰域節(jié)點編碼的末位標號，判斷減少標號后的節(jié)點是否為八叉樹的葉子節(jié)點，直到得出的是葉子節(jié)點，即為下一碰撞節(jié)點為止。若計算出的鄰域節(jié)點是八叉樹的枝節(jié)點，則下一節(jié)點是計算出的鄰域節(jié)點的子節(jié)點，提取出鄰域節(jié)點這一枝下的部分葉子節(jié)點，提取的條件是：在鄰域節(jié)點編碼后加上的標號所屬的基準向必須與計算鄰域節(jié)點的方向相反，比如計算的是Z+向的鄰域節(jié)點，則其編碼后所加的標號都屬于Z-向{1, 3, 5, 7}，其目的是確保提取出的葉子節(jié)點與上一碰撞節(jié)點相鄰。計算提取出的每個葉子節(jié)點所構成包圍盒的范圍，依次判斷穿出交點P2的坐標是否在包圍盒內，滿足條件的葉子節(jié)點即是下一碰撞節(jié)點。如圖6，假設光線從“61”節(jié)點X+向穿出，通過0-1互換計算出的鄰域節(jié)點是“25”，經(jīng)過判斷“25”是八叉樹的枝節(jié)點，提取在“25”編碼后只加X-向標號{4, 5, 6, 7}的葉子節(jié)點：“254”、“255”。判斷穿出交點 P2是否在“254”和“255”的范圍，確定出下一碰撞節(jié)點“254”。

光線跟蹤加速算法通過一種簡單的鄰域分析找出了光線跟蹤的下一碰撞節(jié)點，該鄰域分析算法只對 0、1編碼進行互換，即能找出各方向的鄰域節(jié)點，即避免了遞歸算法遍歷所有節(jié)點，又沒有采用復雜的鄰域分析算法增加碰撞檢測的復雜度，最大限度地提高了光線跟蹤的速度。

3 實驗結果

運用OPENGL對上述算法進行了實現(xiàn)，跟蹤了場景中的某條光線，并采用0-1互換算法提取出與碰撞的八叉樹葉子節(jié)點。圖7(a)是導入初始三維場景，根據(jù)場景的大小構造出初始包圍盒，作為八叉樹根節(jié)點；圖 7(b)是將導入的三維場景采用層次分割成了八叉樹結構，圖中每個包圍盒是一個八叉樹葉子節(jié)點；圖7(c)導入光線，穿過三維場景；圖7(d)采用0-1互換算法提取出與光線碰撞的八叉樹節(jié)點。

圖8為測試算法跟蹤光線的效率，本文采用了Samet算法、Schrack算法和0-1互換3種不同算法，在不同場景中進行了光線與八叉樹葉子節(jié)點的碰撞檢測實驗。從表1中測試統(tǒng)計數(shù)據(jù)可以看出0-1互換算法比 Samet算法的效率高出十多倍，并且Samet算法由于是一種類搜索算法，其碰撞檢測的耗時會隨著八叉樹節(jié)點的增加而增加，而0-1互換算法沒有；由于0-1互換算法不涉及復雜的計算過程，在實驗場景中的耗時與Schrack算法相比，效率最小，提高了3.97倍，最大提高了6.12倍，多數(shù)場景中效率提高了4～5倍。

圖7 使用0-1互換鄰域分析的碰撞檢測圖

圖8 效率比較的實驗場景

表1 不同算法效率比較

4 結 論

八叉樹作為加速光線跟蹤主要采用的一種層次劃分結構，是光線跟蹤加速算法的重要研究方向。本文采用鄰域分析直接計算碰撞節(jié)點，避免了使用遞歸方法遍歷整個八叉樹，加快了碰撞檢測的速度。提出了八叉樹鄰域分析的新算法：0-1互換鄰域分析算法，簡化了鄰域分析的計算步驟，極大增強了八叉樹鄰域分析在加速光線跟蹤中的效率與作用。

[1] Suffer K. 光線跟蹤算法技術[M]. 劉天慧, 譯. 北京:清華大學出版社, 2011: 1-3.

[2] Cosson B, Schmidt F, Maoult Y L, et al. Infrared heating stage simulation of semi-transparent media (PET) using ray tracing method [J]. International Journal of Material Forming, 2011, 4(1): 1-10.

[3] 李 靜, 王文成, 吳恩華. 基于空盒自適應生成的動態(tài)場景光線跟蹤計算[J]. 計算機學報, 2009, 32(6): 1172-1182.

[4] 蔡 鵬, 尹寶才, 孔德慧. 基于最近離散點的光線跟蹤[J]. 圖學學報, 2013, 34(3): 1-6.

[5] Gunther J, Friedrich H, Seidel H. Interactive ray tracing of skinned animations [J]. Visual Computer, 2006, 22(9-11): 785-792.

[6] Samet H. Neighbor finding in image represented by octrees [J]. Computer Graphics and Image Processing, 1989, 46(3): 367-386.

[7] Samet H. Implementing ray tracing with octrees and neighbor finding [J]. Computers & Graphics, 1989, 13(4): 445-460.

[8] Schrack G. Finding neighbors of equal size in linear quadtrees and octrees in constant time [J]. CVGIP: Image Understanding, 1992, 55(3): 221-230.

[9] 肖樂斌. 基于柵格框架的三維GIS集成數(shù)據(jù)模型與空間分析研究[D]. 北京: 中國科學院地理研究所, 1999.

[10] Voros J. A strategy for repetitive neighbor finding in octree representations [J]. Image and Vision Computing, 2000, 18(14): 1085-1091.

[11] Sarah F F, Ronald N P. Simple and efficient traversal methods for quadtrees and octrees [J]. Journal of Graphics Tools, 2002, 7(3): 1-11.

[12] Yoder R, Bloniarz P A. A practical algorithm for computing neighbors in quadtrees, octrees, and hyperoctrees [C]//Proceedings of the 2006 International Conference on, Lasvegas, Nevada, USA, 2006: 249-255.

[13] Armin H, Kal M W, Maren B, et al. OctoMap: an efficient probabilistic 3D mapping framework based on octrees [J]. Auton Robot, 2013, 34(3): 189-206.

Acceleration Algorithm in Ray Tracing by the Octree Neighbor Finding

Zhang Wensheng1,3, Xie Qian1,2, Zhong Jin3, Liu Junping3, Hao Qing4, Guo Guangli3

(1.Shijiazhuang Tiedao University Transportation Institute, Shijiazhuang Hebei 050043, China; 2. Traffic Safety and Control Key Laboratory of Hebei Province, Shijiazhuang Hebei 050043, China; 3. Radiology Department of Shijiazhuang Hospital of TCM, Shijiazhuang Hebei 050011, China; 4. The Fourth Hospital of Hebei Medical University, Shijiazhuang Hebei 050011, China)

Octree is a kind of hierarchy structure, and is often used to accelerate ray tracing. In order to speed up the process of ray tracing, a method which used octree neighbor finding to improve the speed of collision detection between ray and octree nodes is provided. This method proposes a octree neighbor finding algorithm which has simple structure and high computational efficiency. Using this algorithm, the next collision node can be calculated by current collision node quickly, which improves the image rendering speed. The experimental results show that the efficiency increased at least 3 times if the collision detection using the neighbor finding rather than the traditional algorithm, and the proposed algorithm can greatly accelerate the ray tracing.

ray tracing; octree; neighbor finding; acceleration algorithm

TP 391

A

2095-302X(2015)03-0339-06

2014-08-14；定稿日期：2014-11-14

國家自然科學基金資助項目(51308358)；河北省交通廳科研計劃資助項目(J-20130438)；石家莊市科技支撐計劃資助項目(141462353, 133130074A，157130036A)

張文勝(1971-)，男，寧夏隆德人，教授，博士。主要研究方向為信息技術研究。E-mail：zws163@163.com