徐萬銀，劉勝蘭

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

散亂點云線性八叉樹結構在GPU中的實現

徐萬銀，劉勝蘭

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

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

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

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

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

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

1 線性八叉樹的GPU實現

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

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

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

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

1.1 數據點編碼

Morton碼是一種實現多維數據到一維映射的有效方法，它通過交叉存儲多個維數的位產生一個數。本文中將深度為M層的八叉樹節(jié)點的Morton碼記為:x1y1z1x2y2z2…xMyMzM。深度為M層的八叉樹Morton碼有3M位，本文中規(guī)定Morton碼是32位的，因此可表示的八叉樹的最大深度為10，其中未用到的位(31，32位)設為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é)點中心可根據包圍盒的大小來計算，具體算法流程為:

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

1.2.1 節(jié)點數據結構

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

節(jié)點的數據結構為:

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

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

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

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

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

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

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

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

1.2.3 生成鄰節(jié)點

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

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

子表:子表Tablechild為二維數組，表示鄰節(jié)點在該鄰節(jié)點父節(jié)點中的索引。對當前節(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］。

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

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

2 實驗結果

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

圖2 八叉樹的父表和子表

圖3 八叉樹構建圖

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

3 結束語

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

［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—)，女，江蘇鹽城人，南京航空航天大學碩士研究生，主要研究方向為CAD/CAM。