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

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

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

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

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

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

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

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

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

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

1 光線跟蹤與八叉樹

1.1 光線跟蹤

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

圖1 光線跟蹤示意圖

1.2 八叉樹

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

圖2 八叉樹劃分

1.3 八叉樹加速光線跟蹤

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

圖3 光線碰撞檢測(cè)

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

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

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

如圖4(a)所示，光線可看做從源點(diǎn)O發(fā)出、方向?yàn)閱挝幌蛄縟的射線，則光線上任一點(diǎn)P的參數(shù)化方程可表示為：P=O+td

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

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

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

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

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

xmin≤x≤xmax

ymin≤y≤ymax

zmin≤z≤zmax

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

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

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

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

如圖5所示，本文將圖2中八叉樹的編碼分為6個(gè)方向，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}?？梢钥闯?，每個(gè)方向包含4個(gè)編碼，每個(gè)編碼屬于3個(gè)方向。基準(zhǔn)向的劃分是0-1互換算法用于光線跟蹤，分析各方向相鄰節(jié)點(diǎn)的基礎(chǔ)。

圖5 八叉樹基準(zhǔn)向劃分

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

u1u2…uk

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

算法具體如下：

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

(2) 將提取出的八進(jìn)制標(biāo)號(hào)轉(zhuǎn)化為二進(jìn)制編碼(bx, by, bz)，uk=4bx+2by+bz, bx、by、bz=0或1。

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

假若bx=1，則bx=0

如果bx=0，則bx=1

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

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

(5) 判斷vk在X軸上的基準(zhǔn)向與鄰域分析方向是否相同。若不同，則提取出uk前一位標(biāo)號(hào)uk-1，轉(zhuǎn)入步驟(2)；若相同，則計(jì)算結(jié)束。

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果

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

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

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

圖8 效率比較的實(shí)驗(yàn)場(chǎng)景

表1 不同算法效率比較

4 結(jié) 論

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

[1] Suffer K. 光線跟蹤算法技術(shù)[M]. 劉天慧, 譯. 北京:清華大學(xué)出版社, 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] 李 靜, 王文成, 吳恩華. 基于空盒自適應(yīng)生成的動(dòng)態(tài)場(chǎng)景光線跟蹤計(jì)算[J]. 計(jì)算機(jī)學(xué)報(bào), 2009, 32(6): 1172-1182.

[4] 蔡 鵬, 尹寶才, 孔德慧. 基于最近離散點(diǎn)的光線跟蹤[J]. 圖學(xué)學(xué)報(bào), 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]. 北京: 中國科學(xué)院地理研究所, 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

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

張文勝(1971-)，男，寧夏隆德人，教授，博士。主要研究方向?yàn)樾畔⒓夹g(shù)研究。E-mail：zws163@163.com