八叉樹空間結(jié)構(gòu)投影的射線物體求交方法

魏瀟然,耿國華,張雨禾

(西北大學 信息科學與技術(shù)學院，陜西 西安 710127)

?

·信息科學·

八叉樹空間結(jié)構(gòu)投影的射線物體求交方法

魏瀟然,耿國華,張雨禾

(西北大學 信息科學與技術(shù)學院，陜西 西安 710127)

為了提高光線投射算法中射線與物體求交速度,提出一種利用八叉樹空間結(jié)構(gòu)在視平面上投影的射線快速求交方法。算法構(gòu)造平行于視平面的八叉樹空間結(jié)構(gòu),將每個八叉樹葉子包圍盒沿視點方向投影在視平面上,將視平面劃分成若干投影區(qū)域。在射線與包圍盒求交時,根據(jù)射線落在視平面上的位置,確定其所屬投影區(qū)域,求出與該射線相交的包圍盒。實驗表明該算法對傳統(tǒng)的光線投射算法效率有較大提升。

射線求交；投影；八叉樹；光線投射

光線投射是圖形學中的常用繪制技術(shù)之一,在體繪制中有著廣泛的應(yīng)用。利用光線投射進行繪制的計算開銷較大,妨礙了其應(yīng)用效率。通過實驗驗證和理論分析可知,這些繪制計算中開銷的絕大部分用于光線與構(gòu)造場景的圖元的求交計算。為此,人們研究了大量的技術(shù)來加快求交計算,其中,通過建立一定的空間組織結(jié)構(gòu)來加速線面求交是這方面的主要研究內(nèi)容之一。大量的空間組織結(jié)構(gòu)被應(yīng)用在線面求交中,如基于物體劃分的層次包圍盒[1]、基于空間劃分的均勻網(wǎng)格[2-3]、八叉樹[4]、k-d 樹[5-6],以及結(jié)合這兩種劃分方式的混合結(jié)構(gòu)[7]等。這些結(jié)構(gòu)各有特點,需要根據(jù)所處理場景的特點及繪制任務(wù)進行相應(yīng)的選用,沒有哪一種能最優(yōu)地處理各種場景。

一般加速空間結(jié)構(gòu)中通常采用包圍盒結(jié)構(gòu)劃分三維場景,首先用射線與包圍盒求交,之后再用射線與包圍盒內(nèi)圖元求交。本文選取八叉樹空間結(jié)構(gòu),針對射線求交過程中大量射線與包圍盒求交計算進行了優(yōu)化,將包圍盒在視平面上的投影,將射線與包圍盒求交計算轉(zhuǎn)換為射線在屏幕上的投影區(qū)域的求交計算,減少了射線求交的計算量。

1 八叉樹投影的射線求交算法原理

首先對本文出現(xiàn)的一些術(shù)語進行定義:視點定義為o,視點坐標為(0,0,0);屏幕所在平面定義為視平面,視平面原點為視點在視平面的投影點,沿屏幕長寬邊分別定義視平面的u方向和v方向,u和v方向正交;八叉樹結(jié)構(gòu)最外層對整個三維場景的包圍盒稱為八叉樹外包圍盒;八叉樹某一葉子節(jié)點上表面所屬平面與八叉樹外包圍盒相交,相交區(qū)域稱為八叉樹的一個截面,如圖1所示。

視點發(fā)出的射線定義為r(t)=o+td,其中o代表射線出發(fā)點,t代表光線沿z軸行駛距離,d為光線的方向向量,l1為視點到視平面的距離。

圖1 術(shù)語說明Fig.1 Terminology illustraion

光線投射原理如圖2所示,從視點發(fā)出射線到視平面的每個像素,穿過視平面到達場景數(shù)據(jù)中,對相交圖元進行采樣,并進一步計算該圖元的顏色信息,從而完成繪制過程。

圖2 光線投射原理圖Fig.2 Principle of ray casting

本文算法對這射線圖元求交過程進行了優(yōu)化,在原有的八叉樹空間加速結(jié)構(gòu)基礎(chǔ)上,將八叉樹每個葉子節(jié)點包圍盒投影到屏幕上,形成一組投影區(qū)域;射線落在屏幕上一點,得到該落點所屬的投影區(qū)域?qū)?yīng)的葉子節(jié)點,射線穿過該葉子節(jié)點包圍盒;若落點屬于多個投影區(qū)域,則落點對應(yīng)多個葉子節(jié)點,射線按照這些葉子節(jié)點與視點的距離,依次穿越這些葉子節(jié)點。

下面對原理進行相關(guān)證明:

證明1 若長方體包圍盒平行于視平面,其上表面在視平面上投影為長方形。

本文構(gòu)建一個平行于視平面的八叉樹外包圍盒,以垂直于視平面方向為八叉樹外包圍盒高方向,視平面上u，v軸方向為八叉樹外包圍盒長、寬方向。

如圖3所示,A2B2C2D2為八叉樹葉子節(jié)點包圍盒的一個上表面,A1B1C1D1區(qū)域為A2B2C2D2沿視點方向向視平面的投影。

|A1B1|=

|A2B2|=

可知|A1B1|/|A2B2|=l1/l2,同理可證|B1C1|/|B2C2|=l1/l2,|C1D1|/|C2D2|=l1/l2,|D1A1|/|D2A2|=l1/l2。

A2B2C2D2為長方形,故A1B1C1D1也是一個長方形,并且與A2B2C2D2長寬成比例,比例為l1∶l2。

故葉子節(jié)點包圍盒上表面在視平面上投影為長方形,并且投影長方形的長寬跟上表面所屬平面到視點的距離成比例。

圖3 葉子節(jié)點包圍盒上表面在屏幕投影Fig.3 Top surface of the leaf bounding volume projection on the screen

證明2 八叉樹葉子包圍盒投影區(qū)域連續(xù)性

圖4a和圖4b所示為八叉樹一葉子包圍盒上下表面到屏幕投影。計算當八叉樹空間中任意一點V1(x0,y0,z0)沿z軸移動δc至V2(x0,y0,z0+δc)時,V1和V2點在投影視平面上的位置U1和U2。

根據(jù)射線公式V1(x0,y0,z0)=o+z0d1,V2(x0,y0,z0+δc)=o+(z0+δc)d2,得到d1=(x0/z0,y0/z0,1),d2=(x0/(z0+δc),y0/(z0+δc,1),V1,V2在視平面的投影U1,U2可以根據(jù)射線公式求得

U1(u0,v0,l1)=o+l1d1=

U2(u1,v1,l1)=o+l1d2=

通過該公式可知,下層一點與上層同位置點(x,y坐標相同)在投影面位移為

δU=U1-U2=

l1*(δc*x0,δc*y0,0)/z0*(z0+δc)。

(1)

八叉樹空間結(jié)構(gòu)中一點沿z軸變化時,位移后投影點(u,v)可以計算如下

(u,v)=l1*(x0,y0)/z0+

(2)

根據(jù)該公式可得g(u)=(x0/y0)v,g(u)為線性方程,故八叉樹任一點V(x0,y0,z0)沿z軸移動,其投影屏幕上的投影點U(u,v)以(x0/y0)的比例向原點以線性連續(xù)方式移動。

八叉樹葉子節(jié)點包圍盒可以看做由上表面所有點沿z軸方向向下移動一定距離生成。由于八叉樹葉子節(jié)點上表面在視平面的投影是一個長寬分別平行于u軸和v軸的長方形,若視平面原點在上表面投影內(nèi)部,則上表面上所有點沿z軸向下移動的投影均向原點移動,整個包圍盒的其他點投影均在上表面內(nèi)部,如圖4a所示,此時投影區(qū)域連續(xù)。若原點不在上表面內(nèi)部,上表面中x/y最大最小點的投影必在其兩個頂點處。八叉樹葉子節(jié)點上平面任意一點在該包圍盒范圍內(nèi)向下移動,其投影均在其上下表面頂點圍成的多邊形內(nèi),如圖4b所示。連接上下表面對應(yīng)頂點后形成的區(qū)域為包圍盒在視平面上的投影,該區(qū)域連續(xù)。

若視點發(fā)出的射線落在投影區(qū)域內(nèi)，則該射線與該八叉樹葉子節(jié)點存在交點。

圖4 八叉樹葉子包圍盒上下表面到屏幕投影Fig.4 Surface of the leaf bounding volume projection on the screen

下面對投影區(qū)域的快速計算法方法進行說明:

設(shè)i為葉子包圍盒深度,視點到視平面距離為l1,視點到葉子節(jié)點上平面距離為l2。由該葉子節(jié)點深度計算得到該葉子節(jié)點包圍盒長寬高分別為a，b，c,利用射線公式計算出八叉樹最上截面上任意一葉子節(jié)點上表面左下角點在屏幕上投影坐標U0(u0,v0),上表面在視平面的投影長寬為a*(l1/l2),b*(l1/l2),可知上表面4頂點坐標;下表面在視平面投影長寬為a*(l1/(l2+c/2i)),b*(l1/(l2+c/2i))。上下表面在視平面上的投影長寬比為(l2+c/2i)/l2,故根據(jù)上層投影長方形的長寬可以計算得到下層投影長方形的長寬。

利用公式1,由上表面左下角點投影坐標計算在下表面的對應(yīng)點的坐標,之后根據(jù)下表面投影長方形的長寬快速計算投影長方形4頂點。之后根據(jù)上下表面的八個投影頂點即可迅速計算出其所圍成的投影區(qū)域。

2 八叉樹投影的射線求交算法實現(xiàn)

本算法實現(xiàn)分為兩部分,第一部分為八叉樹空間結(jié)構(gòu)初始化及八叉樹葉子包圍盒投影圖預(yù)計算,可以細分為構(gòu)造八叉樹數(shù)據(jù)結(jié)構(gòu)、八叉樹葉子包圍盒的視平面投影區(qū)域計算和生成投影區(qū)域圖;第二部分為射線圖元求交,根據(jù)投影圖求出與射線相交的包圍盒,再求出包圍盒內(nèi)與射線相交的圖元。

2.1 構(gòu)造八叉樹數(shù)據(jù)結(jié)構(gòu)

本文算法采用緊八叉樹空間結(jié)構(gòu),劃分的步驟為:

1) 根據(jù)第1節(jié)所述,構(gòu)造長寬平行于視平面的u,v軸,高垂直于視平面的場景外接包圍盒,計算出該包圍盒的最小Vmin和最大Vmax,通過計算Vmin和Vmax得到中間矢量Vinter,Vinter=(Vmax+Vmin)/2;

2)通過Vmin，Vmax，Vinter對場景包圍盒進行八等分,獲得8個子包圍盒;

3)循環(huán)判斷是否有與子包圍盒相交的面片,如果沒有則刪除該包圍盒,如果有則獲得指向相交面片集的指針;

4)判斷是否達到停止剖分條件,如果沒有則繼續(xù)向下剖分8個子包圍盒;

5)滿足停止剖分條件后,將該節(jié)點記錄為八叉樹葉子節(jié)點,并記錄該節(jié)點層次數(shù)。

終止條件采用兩條件共同約束,1)當前包圍盒內(nèi)葉子節(jié)點數(shù)少于閾值N時停止劃分，2)當八叉樹層次超過M層時停止劃分。

在構(gòu)造完成后對八叉樹葉子節(jié)點進行排序編號,以便在后續(xù)投影圖中確定射線進入八叉樹包圍盒的順序。

編號方法如下:

1)首先從八叉樹的最上層截面開始排序,因為該截面在任何情況下都存在一點在包圍盒中距離視點最近,求出視點在該層上的投影點,尋找距離該投影點最近的葉子包圍盒節(jié)點;

2)依照該截面其他包圍盒距該包圍盒的距離排序,同樣距離情況下,深度較深的葉子包圍盒排序在先;

3)尋找下一待排序截面。首先求出所有未排序葉子節(jié)點中上層z坐標最大,該葉子包圍盒的上表面為下一待排序截面;然后獲取該截面所包含的所有葉子節(jié)點包圍盒,對新求出的截面所有葉子節(jié)點包圍盒以步驟2)方法進行排序,序號在之前排序順序后累加;

4)重復步驟3),直到所有葉子節(jié)點均排序完成。

圖5所示為八叉樹一截面的順序編碼,葉子包圍盒0為與視點最接近的包圍盒。利用該方法編號后,一條光線穿過一組包圍盒時,先進入的包圍盒編號必然會小于后進入的包圍盒。

圖5 包圍盒排序編號Fig.5 Sorting of the bounding volume

2.2 計算八叉樹葉子包圍盒到屏幕投影

結(jié)合第1節(jié)中投影八叉樹的性質(zhì)和投影區(qū)域的快速計算方法,采用以下步驟,可以迅速求出八叉樹所有葉子包圍盒到屏幕的投影:

1)計算任意葉子節(jié)點包圍盒上表面左下角點在屏幕的投影,之后根據(jù)該包圍盒深度,求出該包圍盒長寬高,根據(jù)第一節(jié)中節(jié)推論計算出上表面在視平面上的投影;

2)根據(jù)葉子包圍盒的高算出和以葉子包圍盒上表面的投影,結(jié)合第1節(jié)中的上下表面長寬比例公式及位移公式,計算得到下表面的投影區(qū)域;

3)若視平面原點在上表面投影區(qū)域內(nèi),則葉子包圍盒投影區(qū)域為上邊面投影區(qū)域,如圖4a右圖;否則,連接上、下表面對應(yīng)的四頂點,并求外接多邊形,可以得到葉子節(jié)點包圍盒在屏幕的投影區(qū)域,如圖4b右圖;

4)求該葉子的相鄰葉子節(jié)點的投影平面,利用1)中求得出的端點坐標,尋找這些端點的其他葉子包圍盒,之后按照步驟1)～3)求出其投影區(qū)域。

最終，自上而下生成所有葉子包圍盒的投影。

2.3 生成投影區(qū)域圖

由于每個葉子包圍盒都對應(yīng)了一塊投影區(qū)域,整個八叉樹空間結(jié)構(gòu)會存在非常多的葉子包圍盒投影區(qū)域,故需要對這些投影區(qū)域作進一步整合,以加快后續(xù)的求交運算。

可以將若干投影區(qū)域組成一張投影圖?，F(xiàn)舉例說明兩類投影圖組成方式,其中投影圖中坐標與視平面坐標保持一致:

方式1 將所有葉子包圍盒的投影區(qū)域組成一副圖像,以葉子包圍盒的編號對每個投影區(qū)域編號,若多個葉子包圍盒的投影區(qū)域存在相交,則將這些包圍盒的標號全部賦予相交區(qū)域。該方法使用起來比較直接,只需保存一幅圖像,適合用在葉子包圍盒數(shù)量較少的場景。

方式2 將同截面的葉子包圍盒的投影區(qū)域組成一副圖像,以葉子包圍盒的編號對每個投影區(qū)域編號,若多個葉子包圍盒的投影區(qū)域存在相交,則將這些包圍盒的標號全部賦予相交區(qū)域。該方式存儲一組圖像,射線求交時從上到下的順序遍歷所有圖像,即可求出所有相交圖元。該方式適合用在葉子包圍盒數(shù)量較多的場景。

2.4 光線投射算法中的射線圖元求交

光線投射算法需要求出射線穿越的圖元。利用2.3節(jié)生成投影區(qū)域圖判定射線與包圍盒是否相交,之后再求出與射線相交的圖元信息,本文采用方式二生成的多幅投影區(qū)域圖進行求交判斷,具體步驟如下:

1)首先獲取光線與視平面的交點,之后依次搜索投影圖,獲取包含該交點的所有投影區(qū)域,并按區(qū)域中包含的葉子包圍盒編號由小到大順序記錄。

2)根據(jù)編號獲取每個區(qū)域?qū)?yīng)包圍盒,計算包圍盒中與射線相交的圖元。

獲取這些交點信息后,對交點圖元的色彩和透明度進行采樣,并用色彩合成算子進行色彩的累計,獲取該點最終色彩。

按上述方法依次獲取所有所有點的繪制,完成數(shù)據(jù)的繪制。

3 實驗結(jié)果分析

本文算法所采用的實驗環(huán)境如下:CPU采用Intel(R)Core(TM)i7X980,顯卡采用NVIDIAQuadro4000,內(nèi)存為16GB。

實驗取不同射線數(shù)分別進行了測試,并對同一模型八叉樹結(jié)構(gòu)用多種深度分割進行了反復測試,最優(yōu)深度為繪制速度最快時八叉樹的深度，表1中僅列舉最優(yōu)深度時的測試信息,實驗比較了傳統(tǒng)八叉樹包圍盒算法下繪制速度與使用本文算法的繪制速度。本文所用數(shù)據(jù)如圖6所示。實驗結(jié)果如表1所示。

圖6 實驗數(shù)據(jù)Fig.6 Experiment data

表1 傳統(tǒng)光線投射算法和本文算法繪制時間對比Tab.1 The contrast of rendering time of traditional ray casting and the algorithm in this paper

實驗結(jié)果顯示：①利用本文算法,最優(yōu)層次數(shù)增加。這是由于射線包圍盒求交的運算量減少,使得可以劃分更深層次的八叉樹,相應(yīng)的包圍盒內(nèi)的平均圖元數(shù)也減少,使得在求包圍盒內(nèi)與射線相交的圖元時計算量減少;②在光線跟蹤數(shù)量增加的情況下,算法效率有了提升,這主要是由于投影區(qū)域之間存在關(guān)聯(lián)性,編碼時可有效利用這些關(guān)聯(lián)性,減少了計算量;③本文算法所使用的平均繪制時間為傳統(tǒng)算法的47.6%,實驗證明算法可以有效的提升射線圖元求交及光線投射算法的速度。

4 結(jié) 語

本文提出了一種射線與包圍盒求交的快速算法,與已有求交方法相比,算法對八叉樹空間結(jié)構(gòu)進行預(yù)處理，預(yù)先計算八叉樹葉子節(jié)點包圍盒在屏幕上的投影,再利用投影圖進行求交運算,減少了包圍盒與射線求交的計算,將算法應(yīng)用到光線投影中,取得了良好的效果。如何將該算法用在光線跟蹤等其他渲染算法中可以作為下一步研究重點。該算法可以推廣到k-d樹,均勻網(wǎng)格等其他加速空間結(jié)構(gòu)中,這同樣也是未來將拓展的工作。

[1] WALD I, BOULOS S, SHIRLEY P. Ray tracing dynamic scenes using deformable bounding volume hierarchies[J]. ACM Transactions on Graphics, 2007,26(1):1-18.

[2] WALD I, IZE T, KENSLER A, et al. Ray tracing animated scenes using coherent grid traversal[J]. ACM Transactions on graphics, 2006, 25(3): 485-493.

[3] IZE T, WALD I, ROBERTSON C, et al. An evaluation of parallel gird construction for ray tracing dynamic scenes[C]//Proceedings of IEEE Symposium on Interactive Ray Tracing, Salt Lake City, 2006: 47-55.

[4] PENG Q S, ZHU Y N, LIANG Y D. A fast ray tracing algorithm using space indexing techniques[C]//Proceedings of Eurographics′87. North Holland: Elsevier Science Publishers, 1987: 11-23.

[5] RESHETOV A, SOUPIKOV A, HURLEY J. Multi-level ray tracing algorithm[J]. ACM Transactions on Graphics, 2005, 24(3):1176-1185.

[6] WALD I, HAVRAN V. On building fast k-d trees for ray tracing, andDOIng that in O(NlogN)[C]//Proceedings of IEEE Symposium on Interactive Ray Tracing. Salt Lake City: IEEE Press，2006: 61-69.

[7] KLIMASZEWSKI K, SEDERBERG T W. Faster ray tracing using adaptive grids [J]. IEEE Computer Graphics and Applications, 1997, 17(1): 42-51.

[8] STEIN C, LIMPER M, KUIJPER A. Spatial data structures for accelerated 3D visibility computation to enable large model visualization on the web[C]//Proceedings of the Nineteenth International ACM Conference on 3D Web Technologies. New York: ACM Press, 2014: 53-61.

[9] 康健超,康寶生,馮筠,等.基于八叉樹編碼的CUDA光線投射算法[J].西北大學學報(自然科學版)，2012,42(1): 36-41.

(編 輯曹大剛)

A ray intersection method based on octree spatial structure′s projection

WEI Xiao-ran, GENG Guo-hua, ZHANG Yu-he

(Information and Science College, Northwest University， Xi′an 710127， China)

In order to improve ray intersection with the object speed in ray casting. Proposed a fast ray intersection method using octree spatial structure′s projection on the viewing plane. Constructed an octree spatial structure parallel to the viewing plane, then project octree leaves′ bounding volume along the viewing direction to the viewing plane, viewing plane is divided into lots of blocks of the projection area. In the ray intersection with the bounding volume, the ray falls on the viewing plane, determining its respective projection area, and then finding the ray intersects the bounding volume. Experimental results show that the algorithm can speed up the efficiency of the ray intersection compared with the traditional method.

ray intersection; projection; octree; ray casting

2014-11-04

國家自然科學基金資助項目(61373117)

魏瀟然，男，博士生，陜西咸陽人，從事計算機圖形學、虛擬現(xiàn)實、3D打印等研究。

TP391

：ADOI：10.16152/j.cnki.xdxbzr.2015-03-006