張俊峰, 許德合, 王小東
(1.華北水利水電大學資源與環(huán)境學院,河南鄭州450045;2.成都理工大學國土資源部地學空間信息技術(shù)重點實驗室,四川成都610059)
顧及自適應(yīng)多細節(jié)層次的八叉樹點云管理算法
張俊峰1,2, 許德合1, 王小東1
(1.華北水利水電大學資源與環(huán)境學院,河南鄭州450045;2.成都理工大學國土資源部地學空間信息技術(shù)重點實驗室,四川成都610059)
為了解決大規(guī)模點云不易有效組織、動態(tài)可視化時冗余度大,且較難實現(xiàn)自適應(yīng)顯示的問題,提出顧及細節(jié)層次(levels of detail,LOD)的八叉樹點云管理算法.該算法基于八叉樹索引將掃描點限定在每個結(jié)點范圍內(nèi),利用自上而下空間分割和自下而上參數(shù)計算相結(jié)合的預(yù)處理策略,減少實時階段計算量,通過構(gòu)建保守性模擬誤差,使場景各處均可自動滿足可視要求,并輔之以高效加速方法,實現(xiàn)了點云的有效組織和自適應(yīng)流暢顯示.實驗研究表明,在優(yōu)化的預(yù)處理和輔助加速策略支持下,與經(jīng)典R樹算法相比,該算法實時階段計算量小,每幀自適應(yīng)漫游平均時間在0.04 s以內(nèi).
點云;八叉樹;模擬誤差;可見性裁剪;細節(jié)層次
最新的激光掃描儀可動態(tài)獲取厘米級精度的點云數(shù)據(jù),前所未有的數(shù)據(jù)采集速度和精度對激光點云數(shù)據(jù)的有效組織和可視化提出了嚴峻考驗[1].在計算機圖形學領(lǐng)域,針對大數(shù)據(jù)量,發(fā)展了多種相關(guān)的數(shù)據(jù)組織和快速調(diào)度技術(shù),但多關(guān)注于單目標點云,不易進行復雜場景的有效管理和可視化.基于點云數(shù)據(jù)的海量性、柵格性、原始性和高精度性等特點,一種有效的處理策略是顧及細節(jié)層次(levels of detail,LOD)的數(shù)據(jù)組織和多分辨率顯示[2-4],但費時的預(yù)處理過程和不平衡的樹深嚴重影響了其使用感受和細節(jié)查詢效率.
在空間信息科學領(lǐng)域,目前適用于大規(guī)模點云的空間索引方法主要有規(guī)則格網(wǎng)、二叉樹、四叉樹、八叉樹、R樹等及其變種[5-9],這些方法多基于單個點對象和空間目標的最小包圍盒展開,其索引粒度較小,同樣不適用于海量點云三維模型.另外,傳統(tǒng)的點云LOD算法多采用靜態(tài)模型,在實時顯示時根據(jù)視距動態(tài)調(diào)用不同層次[10-11],盡管簡單,但切換過程中會出現(xiàn)明顯視覺跳躍感以及模型分辨率在單一時刻處處相同,冗余度較大.
作者采用八叉樹模型,提出一種顧及細節(jié)層次的點云管理算法.該算法對所有站點的點云數(shù)據(jù)進行自上而下的八叉樹孤立分割,通過設(shè)定閾值將每個點約束在各個葉結(jié)點中,再自下而上重構(gòu)各級結(jié)點,并計算結(jié)點誤差;實時顯示時,依據(jù)基于視點的保守性模型誤差,可自適應(yīng)地選擇符合精度要求的結(jié)點繪制整個場景,并利用各種有針對性的輔助加速算法提高幀速.
針對地面三維激光掃描儀所獲取的多場景點云數(shù)據(jù)展開,算法總體上分為預(yù)處理和實時顯示兩部分,算法流程如圖1所示.1.1節(jié)闡述點云數(shù)據(jù)組織、八叉樹空間索引構(gòu)建、細節(jié)層次模型設(shè)計和模擬誤差計算屬于預(yù)處理階段;1.2節(jié)闡述實時顯示的細節(jié)層次選擇根據(jù)結(jié)點精度評價標準展開;1.3節(jié)闡述保守可見性判斷和增量更新為輔助加速方法.
圖1 算法流程Fig.1 Algorithm flow
1.1 細節(jié)層次模型構(gòu)建和模擬誤差計算
針對地面三維激光掃描儀獲取的多場景點云數(shù)據(jù),采用場景內(nèi)八叉樹分割、場景間R樹索引根結(jié)點機制進行組織,精度判斷則采用基于視點的模擬誤差.對每個單場景,首先遍歷其所有點獲取最大和最小坐標(x,y,z),由此構(gòu)成的最小包圍盒作為根結(jié)點“0”,然后按照雙隊列模式進行八叉樹自上而下的層次分割,并要求每個結(jié)點內(nèi)的點數(shù)目大于或等于閾值ε,分割完成后,每層的最大結(jié)點數(shù)為8k-1(k=1,2,…,l,l為當前層深).為了減少存儲量,每個非葉結(jié)點不需要存儲其父結(jié)點和各個子結(jié)點指針,結(jié)點之間的層次關(guān)系可根據(jù)編號快速判斷.
為了實現(xiàn)點云在三維空間中的多尺度表達,算法從分割得到的葉結(jié)點出發(fā),向上追溯父結(jié)點,并從各子結(jié)點中按一定比例抽取部分點匯至父結(jié)點,以重構(gòu)各結(jié)點,搭建細節(jié)層次模型.具體來說,自適應(yīng)細節(jié)層次八叉樹結(jié)點構(gòu)建流程如下:
(1)構(gòu)建數(shù)組L1和L2,將所有葉結(jié)點置入L2中.
(2)依次從L2中取出一個結(jié)點N,設(shè)其層深為c,包含的點數(shù)目為m.
(3)根據(jù)結(jié)點N的編號獲取其父結(jié)點Np,檢查L1中是否包含Np,如果包含,轉(zhuǎn)(4);否則將Np置入L1中,轉(zhuǎn)(4).
(4)從N中抽取m(c-1)/c個點作為父結(jié)點Np中的點,轉(zhuǎn)(2).
(5)L2遍歷完成后,檢查L1中的結(jié)點個數(shù),若為1說明已遍歷至根結(jié)點,退出;否則將L1中的結(jié)點置入L2中,清空L1,轉(zhuǎn)(2).
該過程完成后,每個非葉結(jié)點包含的點數(shù)目均占其所有子結(jié)點中點總數(shù)的(c-1)/c,如圖2所示.圖2中各層結(jié)點數(shù)目僅為示意,非真實八叉樹分割,且層深越大,抽取比例越高,細節(jié)表達越詳細.后續(xù)誤差控制下的自適應(yīng)多細節(jié)顯示即為基于重構(gòu)后的結(jié)點展開.
實時顯示時,模擬誤差是判斷顯示細節(jié)的重要指標,因此,當所有結(jié)點重構(gòu)后,再按照自上而下的順序計算該值以確定當前的表達精度.文中的模擬誤差定義為采用當前結(jié)點與采用所有葉結(jié)點表達場景之間的起伏度差值.每個非葉結(jié)點的模擬誤差en各不相同.
圖2 八叉樹結(jié)點細節(jié)層次構(gòu)建Fig.2 LOD building of octree nodes
式中:er為原始場景的起伏度;
es為采用當前結(jié)點表達場景的起伏度.
式中:Zi為當前結(jié)點內(nèi)的掃描點的高程值;
ˉZ為對應(yīng)葉結(jié)點中所有掃描點的平均高程值;
n為當前結(jié)點內(nèi)的點數(shù)目.
式中:Zij為當前結(jié)點對應(yīng)的葉結(jié)點中掃描點的高程值;
p為對應(yīng)的葉結(jié)點數(shù)目;
q為每個葉結(jié)點中掃描點的數(shù)目.
由于當前結(jié)點不一定處于葉結(jié)點的上一層次,因此,p≥8,其值由8(s-c)確定,s為樹的總深度,c為當前結(jié)點層深.
實時漫游時,若利用較高層次結(jié)點,因其包含的掃描點較少,模擬誤差較大.隨著分割層次的加深,(c-1)/c逐漸增大,結(jié)點中包含的掃描點也就越多,表達精度相應(yīng)提高,直到采用葉結(jié)點時模擬誤差為0,因此,可以看出,模擬誤差單調(diào)遞減,具有保守性.
1.2 結(jié)點精度評價標準
場景自適應(yīng)顯示時,需要一個評價標準以確定結(jié)點是否需要繼續(xù)分割,從3個方面進行考慮:
(1)當前結(jié)點的模擬誤差;
(2)視點到結(jié)點中心的距離;
(3)結(jié)點所覆蓋場景的大小.
通常來說,距離視點越近,表達越精細,場景覆蓋范圍越大,需要表達的細節(jié)越多,同時,可視誤差應(yīng)控制在一定范圍內(nèi).精度評價標準可由式(4)計算:
式中:l為結(jié)點邊長平均值;
d為視距;
λ為精度控制因子.
在預(yù)處理中獲得l和en.據(jù)式(4)可知,在λ一定的情況下,當前結(jié)點覆蓋面積越廣,模擬誤差越大,距視點越近,越需要繼續(xù)分割以提高顯示細節(jié),同時,λ越小,要求的顯示精度越高.
實時顯示時,每幀按廣度優(yōu)先原則自上而下逐層判斷每個可見結(jié)點是否達到顯示精度,如滿足式(4),將其包含的所有點交給GPU渲染,否則將其8個子結(jié)點置于待判斷集合,等待下一層次的精度評價,直至葉結(jié)點.另外,獨立進行每個結(jié)點的精度判斷,其分割層次不受相鄰結(jié)點分割情況的影響,因此場景各區(qū)域均可自適應(yīng)地滿足可視要求.
1.3 自適應(yīng)表達的輔助加速算法
點云數(shù)據(jù)量往往很大,少則數(shù)萬,多則幾百萬,甚至上千萬,因此,必須考慮海量數(shù)據(jù)與常規(guī)計算機處理能力有限的矛盾.結(jié)合八叉樹結(jié)點構(gòu)建方法,提出一系列與之相關(guān)的輔助加速算法.
(1)八叉樹結(jié)點的保守可見性判斷
在某具體時刻,視點可見區(qū)域是有限的,因此不在該范圍內(nèi)的數(shù)據(jù)不需要調(diào)入內(nèi)存或渲染.文中利用結(jié)點外接球和視錐體的空間關(guān)系進行可見性判斷,且由于八叉樹結(jié)點具有良好的層次結(jié)構(gòu),可確保判斷的保守性.具體來說,若將某結(jié)點外接球和視錐體沿視線方向剖開,二者空間關(guān)系如圖3所示.
圖3中,E為當前視點所在位置,AB和CD分別為前后裁剪線,α為垂直視角大小,Ld和Lf為視點E距前后裁剪線的距離,圓O為某結(jié)點N外接球的剖面圓,r為半徑,β等于視角α的1/2,Le為圓心到視點E的距離,n為視線方向的單位向量.根據(jù)空間關(guān)系,結(jié)點可見的充分必要條件是圓O被梯形ABDC包含或二者相交,可從水平和垂直方向分別考慮二者的關(guān)系.
圖3 結(jié)點外接球和視錐體的空間關(guān)系Fig.3 The spatial relationship between node circumscribed sphere and view frustum
從結(jié)點N的外接球剖面圓中心到視點E的水平方向考慮.SEO為E到O的矢量,由幾何原理知
因此圓O被視錐體包含或二者相交的第1個必要條件是
若不能滿足式(5),說明當前結(jié)點不可見,其包含的所有子結(jié)點也不可見.
從垂直方向考慮,可得
因此圓O被視錐體包含或二者相交的第2個必要條件是
若同時滿足式(5)和(6),說明當前結(jié)點N可見,若滿足但未達到精度要求,還需進一步判斷其各個子結(jié)點的可見性.
利用結(jié)點外接球和視錐體的空間關(guān)系進行可見性判斷非常簡單,且Ld、Lf和r均在預(yù)處理中提前計算,不會增加實時階段工作量.該算法極大減輕了傳統(tǒng)方法中根據(jù)6個裁剪面進行可見性判斷的巨大計算量[12],且精度較高,可見結(jié)點的冗余度很低.另外,該方法也適用于場景自身可見性的判斷,從而可在整體上保證場景結(jié)構(gòu)的完整性.
(2)視域拓展的多線程增量更新
實時顯示時,內(nèi)外存將頻繁交互數(shù)據(jù),因此需要設(shè)置合理的調(diào)度策略,使預(yù)可見數(shù)據(jù)盡可能地常駐內(nèi)存,并卸載長期不用或遠離視點的數(shù)據(jù)[13-15].基于此,提出基于視域拓展的多線程增量更新算法.可視區(qū)域和擴展區(qū)域如圖4所示,設(shè)各場景所覆蓋范圍的長寬平均值為w,E為某時刻視點位置,α為垂直視角,AB為后裁剪面所在位置,則視錐體在平面上的剖面為EAB,將與此相交或在其內(nèi)的場景定義為可見區(qū)域.
為了減少內(nèi)外存交互,采用“后撤視點,前移裁剪面,擴大視角”的策略,將視點E沿視線反方向移動距離w至E′,并將后裁剪面AB沿視線方向移動距離w至A′B′,同時擴大垂直視角α至β,從而構(gòu)建一個拓展區(qū)域E′A′B′.此時,將與E′A′B′相交或被包含而又不屬于可見區(qū)域的場景定義為擴展區(qū)域,該區(qū)域包含當前可見范圍的各個方向,因此,無論視點如何移動,通過可見區(qū)域和擴展區(qū)域的有限切換,均可保證顯示的流暢性.
細節(jié)層次簡化主線程和數(shù)據(jù)塊調(diào)度子線程通過視域切換實現(xiàn)同步.在初始階段,主線程根據(jù)視點和可視參數(shù)載入所需數(shù)據(jù)塊,然后確定每個結(jié)點的可見性,并將符合精度要求的結(jié)點交給GPU進行渲染.當視點切換時,主線程還需預(yù)測下一幀的可見數(shù)據(jù),若不在內(nèi)存中,將其編號按照優(yōu)先順序置入待加載隊列.數(shù)據(jù)調(diào)度子線程依據(jù)加載隊列中的編號依次載入數(shù)據(jù),并按照最近最常使用原則卸載無用數(shù)據(jù).在整個漫游過程中,可見區(qū)域和擴展區(qū)域動態(tài)切換,相鄰幀間的緩慢過渡決定了數(shù)據(jù)塊調(diào)度是增量更新的,因此瞬時載入量非常有限.
圖4 可視區(qū)域和擴展區(qū)域Fig.4 The visible area and extended area
為了驗證算法的有效性,作者在筆記本電腦上采用OpenGL API實現(xiàn)了該算法.算法實現(xiàn)的硬件條件是Inter Core i5-2430U處理器,2 GB內(nèi)存,NVIDIA NVS 4200M顯卡.
實驗1 不同精度控制因子下的點云自適應(yīng)LOD表達
精度控制因子λ決定了三維表達的速度和逼真度,λ越小,精度要求越高,繪制的掃描點越多.作者基于已有的包含77 874個掃描點的單場景,通過設(shè)置不同的控制因子,得到對應(yīng)的自適應(yīng)表達結(jié)果,如圖5所示.
表1為運行參數(shù)對比.從表1可以看出,隨著λ的減小,繪制的點數(shù)目越來越多,說明表達精度不斷提高,更多區(qū)域需要細分到葉結(jié)點才能達到精度要求,但自適應(yīng)LOD可確保每幀繪制的點數(shù)據(jù)量有限,能夠保證場景的流暢漫游,這從單幀運行時間可以看出.
另外,需要注意的是,盡管較小λ可獲得更高的表達精度,但這是以運行效率為代價的,因此,選擇合適的控制因子也是非常必要的.
實驗2 大規(guī)模點云的自適應(yīng)LOD表達
實驗采用包含6 672 962個掃描點的多場景點云數(shù)據(jù),利用八叉樹空間分割和保守可見性判斷、增量更新等加速算法,實現(xiàn)了自適應(yīng)LOD表達,如圖6所示.圖6中的第1、2和3幀并非漫游時的連續(xù)幀,而是為了更好體現(xiàn)算法效果而選擇的獨立幀.
表2為相關(guān)運行參數(shù).在運行初始階段需要一次性載入當前視點參數(shù)下可見的較多數(shù)據(jù),因此第1幀等待時間較長,不過,由于連續(xù)幀間具有較大重疊,因此后續(xù)各幀只需調(diào)入少量數(shù)據(jù),并適時切換可見區(qū)域和擴展區(qū)域即可.另外,對每幀來說,視域裁剪不但可以快速確定每一場景的可見性,也可判斷場景內(nèi)每一結(jié)點的保守可見性,以最大限度地減少實時繪制量,因此,每幀繪制的點數(shù)目僅占原始數(shù)據(jù)的很少一部分,每幀的自適應(yīng)漫游平均時間可維持在0.04 s以內(nèi).
圖5 不同控制因子下的點云自適應(yīng)表達Fig.5 Adaptive expression of point-cloud data under different control factors
表1 不同控制因子下的點云自適應(yīng)表達參數(shù)Tab.1 Parameters of adaptive expression of point-cloud data under different control factors
圖6 大規(guī)模點云自適應(yīng)表達Fig.6 Adaptive expression of large-scale point-cloud data
表2 大規(guī)模點云自適應(yīng)表達參數(shù)Tab.2 Parameters of adaptive expression of large-scale point-cloud data
采用八叉樹空間索引,結(jié)合有針對性的數(shù)據(jù)組織和加速策略,實現(xiàn)了大規(guī)模點云的多細節(jié)流暢顯示,解決了傳統(tǒng)方法中不易管理海量數(shù)據(jù),且較難實現(xiàn)自適應(yīng)表達的問題,得到以下主要結(jié)論:
(1)利用八叉樹高效的數(shù)據(jù)索引結(jié)構(gòu),結(jié)合自上而下分割和自下而上計算的預(yù)處理策略構(gòu)建結(jié)點的細節(jié)層次,可實現(xiàn)點云自適應(yīng)多分辨率表達.
(2)保守可見性判斷和增量更新方法簡單高效,使內(nèi)存占用率很低,且交互量很少,極大壓縮了實時階段繪制量.
(3)結(jié)合八叉樹結(jié)點細節(jié)層次模型和輔助加速算法,實時階段計算量和數(shù)據(jù)冗余度都很小,能夠滿足大規(guī)模點云的自適應(yīng)流暢顯示,每幀的自適應(yīng)平均漫游時間可維持在0.04 s以內(nèi).
[1] 李德仁.論地球空間信息的三維可視化:基于圖形還是基于影像[J].測繪學報,2010,39(2):111-114.LI Deren.3D visualization of geospatial information:graphics based or imagery based[J].Acta Geodaeticaet Cartographica Sinic,2010,39(2):111-114.
[2] 張帆,黃先鋒,李德仁.基于球面投影的單站地面激光掃描點云構(gòu)網(wǎng)方法[J].測繪學報,2009,38(1):48-54.ZHANG Fan,HUANG Xianfeng,LI Deren.Spherical projection based triangulation for one station terrestrial laser scanning point cloud[J].Acta Geodaetica et Cartographica Sinica,2009,38(1):48-54.
[3] 張俊峰,姚志宏.基于四叉樹孤立分割和屏幕誤差的地形LOD算法[J].西南交通大學學報,2013,48(4):666-671.ZHANG Junfeng,YAO Zhihong.LOD algorithm of terrain based on conservative screen error and isolated division of quad-tree[J].Journal of Southwest Jiaotong University,2013,48(4):666-671.
[4] MANDOW A,MARTINEZ J L,REINA A,et al.Fast range-independent spherical subsampling of 3D laser scanner points and data reduction performance evaluation for scene registration[J].Pattern Recognition Letters,2010,31(11):1239-1250.
[5] 鄭坤,朱良峰,吳信才,等.三維GIS空間索引技術(shù)研究[J].地理與地理信息科學,2006,22(4):35-39.ZHENG Kun,ZHU Liangfeng,WU Xincai,et al.Study on spatial indexing techniques for 3D GIS[J].Geography and Geo-information Science,2006,22(4):35-39.
[6] 史文中,吳立新,李清泉,等.三維空間信息系統(tǒng)模型與算法[M].北京:電子工業(yè)出版社,2007:216-218.
[7] ZHU Qing,GONG Jun,ZHANG Yeting.An efficient 3D R-tree spatial index method for virtual geographic environment[J].ISPRS Journal of Photogrammetry&Remote Sensing,2007,62(3):217-224.
[8] 龔俊,朱慶,張葉廷,等.顧及多細節(jié)層次的三維R-索引擴展方法[J].測繪學報,2014,40(2):249-255.GONG Jun,ZHU Qing,ZHANG Yeting,et al.An efficient 3D R-tree extension method concerned with levels of detail[J].Acta Geodaetica et Cartographica Sinica,2011,40(2):249-255.
[9] 龔俊,朱慶,章漢武,等.基于R樹索引的三維場景細節(jié)層次自適應(yīng)控制方法[J].測繪學報,2011,40(4):531-534.GONG Jun,ZHU Qing,ZHANG Hanwu,et al.An adaptive control method of LODs for 3D scene based on R-tree index[J].Acta Geodaetica et Cartographica Sinica,2011,40(4):531-534.
[10] PFFIFFR N.A subdivision algorithm for smooth 3D terrain models[J].ISPRS Journal of Photogrammetry&Remote Sensing,2005,59(3):115-127.
[11] RENATO P.Fastmesh:efficient view-dependent meshing[C]∥Proceedings of 2001 International Conference on Computer Graphics&Applications.Washington D C:IEEE Computer Society,2001:22-30.
[12] 李清泉,楊必勝,史文中,等.三維空間數(shù)據(jù)的實時獲取、建模與可視化[M].武漢:武漢大學出版社,2003:198-204.
[13] LIU R,PFISTER H,ZWICKER M.Object space EWA surface splatting:a hardware accelerated approach to high quality point rendering[J].Computer Graphics Forum,2002,21(3):461-470.
[14] MA Hongchao,WANG Zongyue.Distributed data organization and parallel data retrieval methods for huge laser scanner point clouds[J].Computers&Geosciences,2011,37(2):193-201.
[15] WAND M,BERNER A,BOKELOH M,et al.Processing and interactive editing of huge point clouds from 3D scanners[J].Computers&Graphics,2008,32(2):204-220.
(中文編輯:秦萍玲 英文編輯:蘭俊思)
Management Algorithm of Point-Cloud Data Based on Octree Concerned with Adaptive Levels of Detail
ZHANG Junfeng1,2, XU Dehe1, WANG Xiaodong1
(1.School of Resource and Environment,North China University of Water Resources and Electric Power,Zhengzhou 450045,China;2.Key Laboratory of Geo-special Information Technology,Ministry of Land and Resources,Chengdu University of Technology,Chengdu 610059,China)
Large-scale point-cloud data are not easy to organize effectively and have great redundancy at dynamic visualization,and it is hard to realize the adaptive display.Aiming at these problems,a new algorithm concerned with the levels of detail(LOD)of point-cloud expression on the basis of octree structure was proposed.The algorithm assigned every scanning point into an octree node,and integrated top-down division with down-top calculation as the pretreatment strategy to reduce the amount of real-time calculation.Then it made any region meet the accuracy requirement and display speed automatically by building conservative simulation-error evaluation criteria.Furthermore,with the help of acceleration methods,large-scale point-cloud data could be organized effectively and expressed smoothly with little data redundancy.Preliminary experiments show that the algorithm has abilities to overcome the shortcoming of the classical R-tree methods;meanwhile,with the support of optimized pretreatment and assistant acceleration methods,the amount of real-time calculation is small and the time of each frame can hold within 0.04 s easily.
point cloud;octree;simulation error;visibility culling;levels of detail
P208
A
0258-2724(2016)01-0078-07
10.3969/j.issn.0258-2724.2016.01.012
2014-08-19
國土資源部地學空間信息技術(shù)重點實驗室開放基金(KLGSIT2014-02);河南省教育廳科學技術(shù)研究重點項目(14A420001);地理信息工程國家測繪地理信息局重點實驗室開放基金(201318)
張俊峰(1982—),男,講師,博士,研究方向為地理信息智能化處理與可視化,電話:13673355837,E-mail:zh-junfeng@163.com
張俊峰,許德合,王小東.顧及自適應(yīng)多細節(jié)層次的八叉樹點云管理算法[J].西南交通大學學報,2016,51(1):78-84.