徐萬銀，劉勝蘭

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

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

徐萬銀，劉勝蘭

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

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

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

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

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

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

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

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

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

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

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

1.1 數(shù)據(jù)點(diǎn)編碼

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2.3 生成鄰節(jié)點(diǎn)

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

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

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

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

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

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

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

圖2 八叉樹的父表和子表

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

表1 GPU八叉樹和CPU八叉樹算法時(shí)間

3 結(jié)束語

本文在GPU上實(shí)現(xiàn)了用Morton碼創(chuàng)建線性八叉樹。實(shí)驗(yàn)表明，在GPU上構(gòu)建的線性八叉樹，在效率方面相對(duì)CPU而言確實(shí)有較大的提高，在某種程度上反映了GPU硬件平臺(tái)進(jìn)行并行運(yùn)算的優(yōu)越性。因此對(duì)于數(shù)據(jù)量大的算法可考慮在GPU硬件平臺(tái)上實(shí)現(xiàn)，但對(duì)于GPU運(yùn)算能力來說，本文八叉樹構(gòu)建時(shí)間稍有點(diǎn)長(zhǎng)，可考慮進(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é)碩士研究生，主要研究方向?yàn)镃AD/CAM。