徐萬銀，劉勝蘭

(南京航空航天大學(xué)機電學(xué)院，江蘇南京 210016)

散亂點云線性八叉樹結(jié)構(gòu)在GPU中的實現(xiàn)

徐萬銀，劉勝蘭

(南京航空航天大學(xué)機電學(xué)院，江蘇南京 210016)

為快速建立散亂點云的空間鄰接關(guān)系，研究了更快速構(gòu)建線性八叉樹。采用Morton碼描述八叉樹的節(jié)點，并按照層次順序?qū)θ~節(jié)點進(jìn)行遍歷，通過建立兩個查詢表，實現(xiàn)對節(jié)點相鄰信息的快速查詢。算法利用了GPU架構(gòu)的并行度，實驗表明，該算法有較高的效率。

八叉樹;Morton碼;并行算法;GPU

八叉樹數(shù)據(jù)結(jié)構(gòu)以其結(jié)構(gòu)簡單、易于遍歷、算法實現(xiàn)方便成為建立散亂點云的空間鄰近關(guān)系，是近年來科研人員研究的熱點。其實現(xiàn)方式主要有指針八叉樹、線性八叉樹。指針八叉樹采用一組指針來記錄節(jié)點父子之間的關(guān)系，由于指針高效的隨機訪問特性，用這種方式查詢效率高，但需要大量的指針存儲空間。線性八叉樹只保存葉節(jié)點的空間位置和屬性，其中空間位置通過編碼來表示。查詢過程就是對編碼的遍歷和比較［1］，查詢效率較低，但結(jié)構(gòu)更緊湊，可以直接訪問任一葉節(jié)點。

隨著圖形處理器(GPU)性能的大幅度提高，使得GPU的應(yīng)用受到研究人員的關(guān)注。指針八叉樹中的指針，在GPU中用父節(jié)點對子節(jié)點的索引來記錄指針，利用GPU中的紋理存儲器來存儲這些索引［2］，實現(xiàn)八叉樹的構(gòu)建。線性八叉樹在GPU中實現(xiàn)的關(guān)鍵是如何編碼以及對節(jié)點進(jìn)行訪問，利用Morton碼實現(xiàn)完全在GPU中構(gòu)建并遍歷八叉樹［3］，在GPU中創(chuàng)建八叉樹的節(jié)點、邊、面等信息［4］，并將其應(yīng)用于散亂數(shù)據(jù)的曲面重建。

本文研究一種線性八叉樹在GPU中的實現(xiàn)方法，通過與CPU算法的比較可知，本文利用GPU大大加快了八叉樹建立，提高了查詢的效率。

1 線性八叉樹的GPU實現(xiàn)

本文建立的線性八叉樹算法流程主要包括2個步驟(如圖1所示):

a.對數(shù)據(jù)點進(jìn)行Morton編碼，包括輸入散亂點云，根據(jù)數(shù)據(jù)點云獲得包圍盒，并行計算每個點的Morton碼3個部分。

b.節(jié)點數(shù)組創(chuàng)建，包括排序 Morton碼，壓縮Morton碼，擴(kuò)充八叉樹節(jié)點，生成每層節(jié)點數(shù)組和生成鄰節(jié)點算法。

圖1 線性八叉樹算法流程圖

1.1 數(shù)據(jù)點編碼

Morton碼是一種實現(xiàn)多維數(shù)據(jù)到一維映射的有效方法，它通過交叉存儲多個維數(shù)的位產(chǎn)生一個數(shù)。本文中將深度為M層的八叉樹節(jié)點的Morton碼記為:x1y1z1x2y2z2…xMyMzM。深度為M層的八叉樹Morton碼有3M位，本文中規(guī)定Morton碼是32位的，因此可表示的八叉樹的最大深度為10，其中未用到的位(31，32位)設(shè)為0。

采樣點v在m(1≤m≤M)層的x位的值按如下公式計算:其中cm是點v所在的(m－1)層的節(jié)點的中心，xm即是m層中x的狀態(tài)值，y位和z位在m層的狀態(tài)值即ym，zm也可以按上述方法同樣計算得到。

采用并行方法計算Morton碼，首先計算第一層節(jié)點的中心，直至第M層的中心，其中第一層節(jié)點中心可根據(jù)包圍盒的大小來計算，具體算法流程為:

1.2 節(jié)點數(shù)組創(chuàng)建

1.2.1 節(jié)點數(shù)據(jù)結(jié)構(gòu)

節(jié)點是八叉樹結(jié)構(gòu)中的基本元素，每個節(jié)點(記為t)中包含以下信息:該節(jié)點的Morton碼，節(jié)點的索引號，節(jié)點中包含的采樣點數(shù)量，首個采樣點的索引，節(jié)點的父節(jié)點、子節(jié)點和鄰節(jié)點。這樣就能通過某數(shù)據(jù)點所在節(jié)點，查詢其父節(jié)點、子節(jié)點和鄰節(jié)點中的數(shù)據(jù)點，從而建立散亂無序點云間的拓?fù)潢P(guān)系。

節(jié)點的數(shù)據(jù)結(jié)構(gòu)為:

1.2.2 創(chuàng)建每層節(jié)點數(shù)組

a.Morton碼排序并去除冗余。

根據(jù)散落無序的采樣點獲得的Morton碼是無序的。本文利用 sort［5］將Morton碼按從小到大順序排序，并重新生成數(shù)據(jù)點順序。對重復(fù)的Morton碼進(jìn)行壓縮，生成節(jié)點數(shù)組 UniqueNode。在UniqueNode結(jié)構(gòu)中記錄了每個節(jié)點所包含的點云個數(shù)，同時也保存了每個節(jié)點中第一個點在點數(shù)組中的索引。

b.擴(kuò)充八叉樹節(jié)點。

八叉樹中每個節(jié)點有0個或8個子節(jié)點，因此需要對UniqueNode中某些節(jié)點進(jìn)行擴(kuò)充，保證已有Morton碼節(jié)點的父節(jié)點有8個子節(jié)點。利用scan［6］算法得到對應(yīng)的節(jié)點地址數(shù)組nodeaddress。

c.生成每層的節(jié)點數(shù)組OctreeNode。

算出擴(kuò)充后新增節(jié)點的Morton碼，將這些節(jié)點的ptnumbers設(shè)為0。通過 nodeaddress和3位xMyMzM的Morton碼定位UniqueNode中的每個節(jié)點在OctreeNodeM中的對應(yīng)元素。

根據(jù)第M層節(jié)點數(shù)組，依次建(M－1)層，直至第一層節(jié)點數(shù)組。在OctreeNodeM中，將每個節(jié)點Morton碼中xMyMzM位設(shè)為000，即生成(M －1)層節(jié)點的Morton碼。如同第二步那樣擴(kuò)充節(jié)點，最終生成OctreeNodeM－1。按相同方式依次建立其他層節(jié)點數(shù)組，直至第一層。根據(jù)每層的UniqueNode可以推算出每層節(jié)點的父節(jié)點、子節(jié)點的索引。所有層的節(jié)點數(shù)組組成整個的節(jié)點數(shù)組OctreeNode。

1.2.3 生成鄰節(jié)點

對于節(jié)點數(shù)組OctreeNode，還需要知道每個節(jié)點的26個相鄰節(jié)點，這26個節(jié)點分布在同一父節(jié)點的子節(jié)點和與其父節(jié)點相鄰的子節(jié)點中。本文事先建立兩個查找表來加速鄰近節(jié)點的計算。現(xiàn)將兩個查找表定義如下。

父表:父表Tableparent為二維數(shù)組，表示鄰節(jié)點的父節(jié)點在當(dāng)前節(jié)點的父節(jié)點中的相對索引。對當(dāng)前節(jié)點t，其父節(jié)點為p，如果t的索引在p.children是 i，則節(jié)點 t的第 j個鄰節(jié)點 t.neighs［j］的父節(jié)點索引在 p.neighs是 Tableparent［i］［j］。

子表:子表Tablechild為二維數(shù)組，表示鄰節(jié)點在該鄰節(jié)點父節(jié)點中的索引。對當(dāng)前節(jié)點t，其父節(jié)點為 p，如果t的索引在p.children是i，節(jié)點t的第j個鄰節(jié)點 t.neighs［j］ 的父節(jié)點為 h ，則 t.neighs［j］在 h.children 中 的 索 引 是Tablechild［i］［j］。

子表和父表的數(shù)組大小均為8×27，Tableparent［8］［27］、Tablechild［8］［27］如圖 2 所示。

計算節(jié)點的鄰節(jié)點時，采用從根部開始逐層遍歷的方式遍歷八叉樹，如果節(jié)點t的第j個鄰節(jié)點不存在，將 t.neighs［j］設(shè)為 －1。

2 實驗結(jié)果

將本文的線性八叉樹算法在環(huán)境為Visual Studio 2008，CPU 為奔騰 Dual－Core 2.5GHz，顯卡為NVDIA GeForce 9500GT機器上進(jìn)行實驗。圖3所示為各模型構(gòu)建好的八叉樹圖。將本文的算法與CPU自適應(yīng)的八叉樹算法［7］進(jìn)行比較，該算法在CPU上屬于特別高效的方法，與CPU的高效算法相比(見表1)，從表1中可知，算法效率至少提高了50%。因此，本文的八叉樹構(gòu)建算法是解決海量點云存儲問題的有效方法。

圖2 八叉樹的父表和子表

圖3 八叉樹構(gòu)建圖

表1 GPU八叉樹和CPU八叉樹算法時間

3 結(jié)束語

本文在GPU上實現(xiàn)了用Morton碼創(chuàng)建線性八叉樹。實驗表明，在GPU上構(gòu)建的線性八叉樹，在效率方面相對CPU而言確實有較大的提高，在某種程度上反映了GPU硬件平臺進(jìn)行并行運算的優(yōu)越性。因此對于數(shù)據(jù)量大的算法可考慮在GPU硬件平臺上實現(xiàn)，但對于GPU運算能力來說，本文八叉樹構(gòu)建時間稍有點長，可考慮進(jìn)一步挖掘GPU的并行性，更高效地構(gòu)建八叉樹。

［1］Choi M，Ju E G，Chang J，et al.Linkless octree usingm multilevel perfect hashing［J］.Pacific Graphics，2009，28(7):1773－1780.

［2］Benson D，Davis J.Octree textures［J］.ACM Transactions on Graphics，2002，21(3):785 －790.

［3］Jeroen B，Evghenii G，Simon P .A sparse octree gravitational N-body code that runs entirely on the GPU processor［J］.Journal of Computational Physics，2012，231(7):2825 －2839.

［4］Zhou K，Gong M M，Huang X，et al.Data－parallel octrees for surface reconstruction［J］.IEEE Transactions on Visualization and Computer Graphics，2011，17(5):669 －681.

［5］Harris M，Owens J，Sengupta S，et al.CUDA Data Parallel Primitives Library［EB/OL］.［2012 －03 －14］.http://code.google.com/p/cudpp/.

［6］Sengupta S，Harris M.Scan primitives for GPU computing［C］//GH'07:Proceedings of THE 22ndACM SIGGRAPH/EURGRAPHICS Symposium on Graphics Hardware.Aire－la－Ville(Switzerland)Eurographics Association for computer graphics，2007:97 －106.

［7］Kazhdan M，Bolitho M，Hoppe H.Poisson surface reconstruction［C］.//SGP'06:Proceedings of the 4thEurographics Symposium on Geometry Processing.Aire－la－Ville(Switzerland):Eurographics Association，2006:61 －70.

Realization of linear octree for scattered point cloud on GPU

XU Wanyin，LIU Shenglan
(Nanjing University of Aeronautics＆ Astronautics，Jiangsu Nanjing，210016，China)

In this paper a kind of linear GPU octree is proposed to establish scattered point cloud space adjacent relation fastly.The linear GPU octree uses Morton code for descripting octree node.Moreover，the leaf node are traversed with the hierarchy sequence and two luts are established to query adjacent nodes quickly.The algorithm makes full use of parallelism of GPU structure，which experiments show that，the new algorithm has higher efficiency.

Octree;Morton code;Parallel algorithm;GPU

TP391

A

2095－509X(2013)04－0005－03

10.3969/j.issn.2095 －509X.2013.04.002

2013－01－06

徐萬銀(1989—)，女，江蘇鹽城人，南京航空航天大學(xué)碩士研究生，主要研究方向為CAD/CAM。