張俊峰， 許德合， 王小東

（1．華北水利水電大學(xué)資源與環(huán)境學(xué)院，河南鄭州450045；2．成都理工大學(xué)國土資源部地學(xué)空間信息技術(shù)重點(diǎn)實(shí)驗(yàn)室，四川成都610059）

顧及自適應(yīng)多細(xì)節(jié)層次的八叉樹點(diǎn)云管理算法

張俊峰1，2， 許德合1， 王小東1

（1．華北水利水電大學(xué)資源與環(huán)境學(xué)院，河南鄭州450045；2．成都理工大學(xué)國土資源部地學(xué)空間信息技術(shù)重點(diǎn)實(shí)驗(yàn)室，四川成都610059）

為了解決大規(guī)模點(diǎn)云不易有效組織、動(dòng)態(tài)可視化時(shí)冗余度大，且較難實(shí)現(xiàn)自適應(yīng)顯示的問題，提出顧及細(xì)節(jié)層次（levels of detail，LOD）的八叉樹點(diǎn)云管理算法．該算法基于八叉樹索引將掃描點(diǎn)限定在每個(gè)結(jié)點(diǎn)范圍內(nèi)，利用自上而下空間分割和自下而上參數(shù)計(jì)算相結(jié)合的預(yù)處理策略，減少實(shí)時(shí)階段計(jì)算量，通過構(gòu)建保守性模擬誤差，使場(chǎng)景各處均可自動(dòng)滿足可視要求，并輔之以高效加速方法，實(shí)現(xiàn)了點(diǎn)云的有效組織和自適應(yīng)流暢顯示．實(shí)驗(yàn)研究表明，在優(yōu)化的預(yù)處理和輔助加速策略支持下，與經(jīng)典R樹算法相比，該算法實(shí)時(shí)階段計(jì)算量小，每幀自適應(yīng)漫游平均時(shí)間在0．04 s以內(nèi)．

點(diǎn)云；八叉樹；模擬誤差；可見性裁剪；細(xì)節(jié)層次

最新的激光掃描儀可動(dòng)態(tài)獲取厘米級(jí)精度的點(diǎn)云數(shù)據(jù)，前所未有的數(shù)據(jù)采集速度和精度對(duì)激光點(diǎn)云數(shù)據(jù)的有效組織和可視化提出了嚴(yán)峻考驗(yàn)［1］．在計(jì)算機(jī)圖形學(xué)領(lǐng)域，針對(duì)大數(shù)據(jù)量，發(fā)展了多種相關(guān)的數(shù)據(jù)組織和快速調(diào)度技術(shù)，但多關(guān)注于單目標(biāo)點(diǎn)云，不易進(jìn)行復(fù)雜場(chǎng)景的有效管理和可視化．基于點(diǎn)云數(shù)據(jù)的海量性、柵格性、原始性和高精度性等特點(diǎn)，一種有效的處理策略是顧及細(xì)節(jié)層次（levels of detail，LOD）的數(shù)據(jù)組織和多分辨率顯示［2-4］，但費(fèi)時(shí)的預(yù)處理過程和不平衡的樹深嚴(yán)重影響了其使用感受和細(xì)節(jié)查詢效率．

在空間信息科學(xué)領(lǐng)域，目前適用于大規(guī)模點(diǎn)云的空間索引方法主要有規(guī)則格網(wǎng)、二叉樹、四叉樹、八叉樹、R樹等及其變種［5-9］，這些方法多基于單個(gè)點(diǎn)對(duì)象和空間目標(biāo)的最小包圍盒展開，其索引粒度較小，同樣不適用于海量點(diǎn)云三維模型．另外，傳統(tǒng)的點(diǎn)云LOD算法多采用靜態(tài)模型，在實(shí)時(shí)顯示時(shí)根據(jù)視距動(dòng)態(tài)調(diào)用不同層次［10-11］，盡管簡(jiǎn)單，但切換過程中會(huì)出現(xiàn)明顯視覺跳躍感以及模型分辨率在單一時(shí)刻處處相同，冗余度較大．

作者采用八叉樹模型，提出一種顧及細(xì)節(jié)層次的點(diǎn)云管理算法．該算法對(duì)所有站點(diǎn)的點(diǎn)云數(shù)據(jù)進(jìn)行自上而下的八叉樹孤立分割，通過設(shè)定閾值將每個(gè)點(diǎn)約束在各個(gè)葉結(jié)點(diǎn)中，再自下而上重構(gòu)各級(jí)結(jié)點(diǎn)，并計(jì)算結(jié)點(diǎn)誤差；實(shí)時(shí)顯示時(shí)，依據(jù)基于視點(diǎn)的保守性模型誤差，可自適應(yīng)地選擇符合精度要求的結(jié)點(diǎn)繪制整個(gè)場(chǎng)景，并利用各種有針對(duì)性的輔助加速算法提高幀速．

1 算法設(shè)計(jì)

針對(duì)地面三維激光掃描儀所獲取的多場(chǎng)景點(diǎn)云數(shù)據(jù)展開，算法總體上分為預(yù)處理和實(shí)時(shí)顯示兩部分，算法流程如圖1所示．1．1節(jié)闡述點(diǎn)云數(shù)據(jù)組織、八叉樹空間索引構(gòu)建、細(xì)節(jié)層次模型設(shè)計(jì)和模擬誤差計(jì)算屬于預(yù)處理階段；1．2節(jié)闡述實(shí)時(shí)顯示的細(xì)節(jié)層次選擇根據(jù)結(jié)點(diǎn)精度評(píng)價(jià)標(biāo)準(zhǔn)展開；1．3節(jié)闡述保守可見性判斷和增量更新為輔助加速方法．

圖1 算法流程Fig．1 Algorithm flow

1．1 細(xì)節(jié)層次模型構(gòu)建和模擬誤差計(jì)算

針對(duì)地面三維激光掃描儀獲取的多場(chǎng)景點(diǎn)云數(shù)據(jù)，采用場(chǎng)景內(nèi)八叉樹分割、場(chǎng)景間R樹索引根結(jié)點(diǎn)機(jī)制進(jìn)行組織，精度判斷則采用基于視點(diǎn)的模擬誤差．對(duì)每個(gè)單場(chǎng)景，首先遍歷其所有點(diǎn)獲取最大和最小坐標(biāo)（x，y，z），由此構(gòu)成的最小包圍盒作為根結(jié)點(diǎn)“0”，然后按照雙隊(duì)列模式進(jìn)行八叉樹自上而下的層次分割，并要求每個(gè)結(jié)點(diǎn)內(nèi)的點(diǎn)數(shù)目大于或等于閾值ε，分割完成后，每層的最大結(jié)點(diǎn)數(shù)為8k－1（k＝1，2，…，l，l為當(dāng)前層深）．為了減少存儲(chǔ)量，每個(gè)非葉結(jié)點(diǎn)不需要存儲(chǔ)其父結(jié)點(diǎn)和各個(gè)子結(jié)點(diǎn)指針，結(jié)點(diǎn)之間的層次關(guān)系可根據(jù)編號(hào)快速判斷．

為了實(shí)現(xiàn)點(diǎn)云在三維空間中的多尺度表達(dá)，算法從分割得到的葉結(jié)點(diǎn)出發(fā)，向上追溯父結(jié)點(diǎn)，并從各子結(jié)點(diǎn)中按一定比例抽取部分點(diǎn)匯至父結(jié)點(diǎn)，以重構(gòu)各結(jié)點(diǎn)，搭建細(xì)節(jié)層次模型．具體來說，自適應(yīng)細(xì)節(jié)層次八叉樹結(jié)點(diǎn)構(gòu)建流程如下：

（1）構(gòu)建數(shù)組L1和L2，將所有葉結(jié)點(diǎn)置入L2中．

（2）依次從L2中取出一個(gè)結(jié)點(diǎn)N，設(shè)其層深為c，包含的點(diǎn)數(shù)目為m．

（3）根據(jù)結(jié)點(diǎn)N的編號(hào)獲取其父結(jié)點(diǎn)Np，檢查L(zhǎng)1中是否包含Np，如果包含，轉(zhuǎn)（4）；否則將Np置入L1中，轉(zhuǎn)（4）．

（4）從N中抽取m（c－1）／c個(gè)點(diǎn)作為父結(jié)點(diǎn)Np中的點(diǎn)，轉(zhuǎn)（2）．

（5）L2遍歷完成后，檢查L(zhǎng)1中的結(jié)點(diǎn)個(gè)數(shù)，若為1說明已遍歷至根結(jié)點(diǎn)，退出；否則將L1中的結(jié)點(diǎn)置入L2中，清空L1，轉(zhuǎn)（2）．

該過程完成后，每個(gè)非葉結(jié)點(diǎn)包含的點(diǎn)數(shù)目均占其所有子結(jié)點(diǎn)中點(diǎn)總數(shù)的（c－1）／c，如圖2所示．圖2中各層結(jié)點(diǎn)數(shù)目?jī)H為示意，非真實(shí)八叉樹分割，且層深越大，抽取比例越高，細(xì)節(jié)表達(dá)越詳細(xì)．后續(xù)誤差控制下的自適應(yīng)多細(xì)節(jié)顯示即為基于重構(gòu)后的結(jié)點(diǎn)展開．

實(shí)時(shí)顯示時(shí)，模擬誤差是判斷顯示細(xì)節(jié)的重要指標(biāo)，因此，當(dāng)所有結(jié)點(diǎn)重構(gòu)后，再按照自上而下的順序計(jì)算該值以確定當(dāng)前的表達(dá)精度．文中的模擬誤差定義為采用當(dāng)前結(jié)點(diǎn)與采用所有葉結(jié)點(diǎn)表達(dá)場(chǎng)景之間的起伏度差值．每個(gè)非葉結(jié)點(diǎn)的模擬誤差en各不相同．

圖2 八叉樹結(jié)點(diǎn)細(xì)節(jié)層次構(gòu)建Fig．2 LOD building of octree nodes

式中：er為原始場(chǎng)景的起伏度；

es為采用當(dāng)前結(jié)點(diǎn)表達(dá)場(chǎng)景的起伏度．

式中：Zi為當(dāng)前結(jié)點(diǎn)內(nèi)的掃描點(diǎn)的高程值；

ˉZ為對(duì)應(yīng)葉結(jié)點(diǎn)中所有掃描點(diǎn)的平均高程值；

n為當(dāng)前結(jié)點(diǎn)內(nèi)的點(diǎn)數(shù)目．

式中：Zij為當(dāng)前結(jié)點(diǎn)對(duì)應(yīng)的葉結(jié)點(diǎn)中掃描點(diǎn)的高程值；

p為對(duì)應(yīng)的葉結(jié)點(diǎn)數(shù)目；

q為每個(gè)葉結(jié)點(diǎn)中掃描點(diǎn)的數(shù)目．

由于當(dāng)前結(jié)點(diǎn)不一定處于葉結(jié)點(diǎn)的上一層次，因此，p≥8，其值由8（s－c）確定，s為樹的總深度，c為當(dāng)前結(jié)點(diǎn)層深．

實(shí)時(shí)漫游時(shí)，若利用較高層次結(jié)點(diǎn)，因其包含的掃描點(diǎn)較少，模擬誤差較大．隨著分割層次的加深，（c－1）／c逐漸增大，結(jié)點(diǎn)中包含的掃描點(diǎn)也就越多，表達(dá)精度相應(yīng)提高，直到采用葉結(jié)點(diǎn)時(shí)模擬誤差為0，因此，可以看出，模擬誤差單調(diào)遞減，具有保守性．

1．2 結(jié)點(diǎn)精度評(píng)價(jià)標(biāo)準(zhǔn)

場(chǎng)景自適應(yīng)顯示時(shí)，需要一個(gè)評(píng)價(jià)標(biāo)準(zhǔn)以確定結(jié)點(diǎn)是否需要繼續(xù)分割，從3個(gè)方面進(jìn)行考慮：

（1）當(dāng)前結(jié)點(diǎn)的模擬誤差；

（2）視點(diǎn)到結(jié)點(diǎn)中心的距離；

（3）結(jié)點(diǎn)所覆蓋場(chǎng)景的大?。?/p>

通常來說，距離視點(diǎn)越近，表達(dá)越精細(xì)，場(chǎng)景覆蓋范圍越大，需要表達(dá)的細(xì)節(jié)越多，同時(shí)，可視誤差應(yīng)控制在一定范圍內(nèi)．精度評(píng)價(jià)標(biāo)準(zhǔn)可由式（4）計(jì)算：

式中：l為結(jié)點(diǎn)邊長(zhǎng)平均值；

d為視距；

λ為精度控制因子．

在預(yù)處理中獲得l和en．據(jù)式（4）可知，在λ一定的情況下，當(dāng)前結(jié)點(diǎn)覆蓋面積越廣，模擬誤差越大，距視點(diǎn)越近，越需要繼續(xù)分割以提高顯示細(xì)節(jié)，同時(shí)，λ越小，要求的顯示精度越高．

實(shí)時(shí)顯示時(shí)，每幀按廣度優(yōu)先原則自上而下逐層判斷每個(gè)可見結(jié)點(diǎn)是否達(dá)到顯示精度，如滿足式（4），將其包含的所有點(diǎn)交給GPU渲染，否則將其8個(gè)子結(jié)點(diǎn)置于待判斷集合，等待下一層次的精度評(píng)價(jià)，直至葉結(jié)點(diǎn)．另外，獨(dú)立進(jìn)行每個(gè)結(jié)點(diǎn)的精度判斷，其分割層次不受相鄰結(jié)點(diǎn)分割情況的影響，因此場(chǎng)景各區(qū)域均可自適應(yīng)地滿足可視要求．

1．3 自適應(yīng)表達(dá)的輔助加速算法

點(diǎn)云數(shù)據(jù)量往往很大，少則數(shù)萬，多則幾百萬，甚至上千萬，因此，必須考慮海量數(shù)據(jù)與常規(guī)計(jì)算機(jī)處理能力有限的矛盾．結(jié)合八叉樹結(jié)點(diǎn)構(gòu)建方法，提出一系列與之相關(guān)的輔助加速算法．

（1）八叉樹結(jié)點(diǎn)的保守可見性判斷

在某具體時(shí)刻，視點(diǎn)可見區(qū)域是有限的，因此不在該范圍內(nèi)的數(shù)據(jù)不需要調(diào)入內(nèi)存或渲染．文中利用結(jié)點(diǎn)外接球和視錐體的空間關(guān)系進(jìn)行可見性判斷，且由于八叉樹結(jié)點(diǎn)具有良好的層次結(jié)構(gòu)，可確保判斷的保守性．具體來說，若將某結(jié)點(diǎn)外接球和視錐體沿視線方向剖開，二者空間關(guān)系如圖3所示．

圖3中，E為當(dāng)前視點(diǎn)所在位置，AB和CD分別為前后裁剪線，α為垂直視角大小，Ld和Lf為視點(diǎn)E距前后裁剪線的距離，圓O為某結(jié)點(diǎn)N外接球的剖面圓，r為半徑，β等于視角α的1／2，Le為圓心到視點(diǎn)E的距離，n為視線方向的單位向量．根據(jù)空間關(guān)系，結(jié)點(diǎn)可見的充分必要條件是圓O被梯形ABDC包含或二者相交，可從水平和垂直方向分別考慮二者的關(guān)系．

圖3 結(jié)點(diǎn)外接球和視錐體的空間關(guān)系Fig．3 The spatial relationship between node circumscribed sphere and view frustum

從結(jié)點(diǎn)N的外接球剖面圓中心到視點(diǎn)E的水平方向考慮．SEO為E到O的矢量，由幾何原理知

因此圓O被視錐體包含或二者相交的第1個(gè)必要條件是

若不能滿足式（5），說明當(dāng)前結(jié)點(diǎn)不可見，其包含的所有子結(jié)點(diǎn)也不可見．

從垂直方向考慮，可得

因此圓O被視錐體包含或二者相交的第2個(gè)必要條件是

若同時(shí)滿足式（5）和（6），說明當(dāng)前結(jié)點(diǎn)N可見，若滿足但未達(dá)到精度要求，還需進(jìn)一步判斷其各個(gè)子結(jié)點(diǎn)的可見性．

利用結(jié)點(diǎn)外接球和視錐體的空間關(guān)系進(jìn)行可見性判斷非常簡(jiǎn)單，且Ld、Lf和r均在預(yù)處理中提前計(jì)算，不會(huì)增加實(shí)時(shí)階段工作量．該算法極大減輕了傳統(tǒng)方法中根據(jù)6個(gè)裁剪面進(jìn)行可見性判斷的巨大計(jì)算量［12］，且精度較高，可見結(jié)點(diǎn)的冗余度很低．另外，該方法也適用于場(chǎng)景自身可見性的判斷，從而可在整體上保證場(chǎng)景結(jié)構(gòu)的完整性．

（2）視域拓展的多線程增量更新

實(shí)時(shí)顯示時(shí)，內(nèi)外存將頻繁交互數(shù)據(jù)，因此需要設(shè)置合理的調(diào)度策略，使預(yù)可見數(shù)據(jù)盡可能地常駐內(nèi)存，并卸載長(zhǎng)期不用或遠(yuǎn)離視點(diǎn)的數(shù)據(jù)［13-15］．基于此，提出基于視域拓展的多線程增量更新算法．可視區(qū)域和擴(kuò)展區(qū)域如圖4所示，設(shè)各場(chǎng)景所覆蓋范圍的長(zhǎng)寬平均值為w，E為某時(shí)刻視點(diǎn)位置，α為垂直視角，AB為后裁剪面所在位置，則視錐體在平面上的剖面為EAB，將與此相交或在其內(nèi)的場(chǎng)景定義為可見區(qū)域．

為了減少內(nèi)外存交互，采用“后撤視點(diǎn)，前移裁剪面，擴(kuò)大視角”的策略，將視點(diǎn)E沿視線反方向移動(dòng)距離w至E′，并將后裁剪面AB沿視線方向移動(dòng)距離w至A′B′，同時(shí)擴(kuò)大垂直視角α至β，從而構(gòu)建一個(gè)拓展區(qū)域E′A′B′．此時(shí)，將與E′A′B′相交或被包含而又不屬于可見區(qū)域的場(chǎng)景定義為擴(kuò)展區(qū)域，該區(qū)域包含當(dāng)前可見范圍的各個(gè)方向，因此，無論視點(diǎn)如何移動(dòng)，通過可見區(qū)域和擴(kuò)展區(qū)域的有限切換，均可保證顯示的流暢性．

細(xì)節(jié)層次簡(jiǎn)化主線程和數(shù)據(jù)塊調(diào)度子線程通過視域切換實(shí)現(xiàn)同步．在初始階段，主線程根據(jù)視點(diǎn)和可視參數(shù)載入所需數(shù)據(jù)塊，然后確定每個(gè)結(jié)點(diǎn)的可見性，并將符合精度要求的結(jié)點(diǎn)交給GPU進(jìn)行渲染．當(dāng)視點(diǎn)切換時(shí)，主線程還需預(yù)測(cè)下一幀的可見數(shù)據(jù)，若不在內(nèi)存中，將其編號(hào)按照優(yōu)先順序置入待加載隊(duì)列．?dāng)?shù)據(jù)調(diào)度子線程依據(jù)加載隊(duì)列中的編號(hào)依次載入數(shù)據(jù)，并按照最近最常使用原則卸載無用數(shù)據(jù)．在整個(gè)漫游過程中，可見區(qū)域和擴(kuò)展區(qū)域動(dòng)態(tài)切換，相鄰幀間的緩慢過渡決定了數(shù)據(jù)塊調(diào)度是增量更新的，因此瞬時(shí)載入量非常有限．

圖4 可視區(qū)域和擴(kuò)展區(qū)域Fig．4 The visible area and extended area

2 實(shí)驗(yàn)與分析

為了驗(yàn)證算法的有效性，作者在筆記本電腦上采用OpenGL API實(shí)現(xiàn)了該算法．算法實(shí)現(xiàn)的硬件條件是Inter Core i5-2430U處理器，2 GB內(nèi)存，NVIDIA NVS 4200M顯卡．

實(shí)驗(yàn)1 不同精度控制因子下的點(diǎn)云自適應(yīng)LOD表達(dá)

精度控制因子λ決定了三維表達(dá)的速度和逼真度，λ越小，精度要求越高，繪制的掃描點(diǎn)越多．作者基于已有的包含77 874個(gè)掃描點(diǎn)的單場(chǎng)景，通過設(shè)置不同的控制因子，得到對(duì)應(yīng)的自適應(yīng)表達(dá)結(jié)果，如圖5所示．

表1為運(yùn)行參數(shù)對(duì)比．從表1可以看出，隨著λ的減小，繪制的點(diǎn)數(shù)目越來越多，說明表達(dá)精度不斷提高，更多區(qū)域需要細(xì)分到葉結(jié)點(diǎn)才能達(dá)到精度要求，但自適應(yīng)LOD可確保每幀繪制的點(diǎn)數(shù)據(jù)量有限，能夠保證場(chǎng)景的流暢漫游，這從單幀運(yùn)行時(shí)間可以看出．

另外，需要注意的是，盡管較小λ可獲得更高的表達(dá)精度，但這是以運(yùn)行效率為代價(jià)的，因此，選擇合適的控制因子也是非常必要的．

實(shí)驗(yàn)2 大規(guī)模點(diǎn)云的自適應(yīng)LOD表達(dá)

實(shí)驗(yàn)采用包含6 672 962個(gè)掃描點(diǎn)的多場(chǎng)景點(diǎn)云數(shù)據(jù)，利用八叉樹空間分割和保守可見性判斷、增量更新等加速算法，實(shí)現(xiàn)了自適應(yīng)LOD表達(dá)，如圖6所示．圖6中的第1、2和3幀并非漫游時(shí)的連續(xù)幀，而是為了更好體現(xiàn)算法效果而選擇的獨(dú)立幀．

表2為相關(guān)運(yùn)行參數(shù)．在運(yùn)行初始階段需要一次性載入當(dāng)前視點(diǎn)參數(shù)下可見的較多數(shù)據(jù)，因此第1幀等待時(shí)間較長(zhǎng)，不過，由于連續(xù)幀間具有較大重疊，因此后續(xù)各幀只需調(diào)入少量數(shù)據(jù)，并適時(shí)切換可見區(qū)域和擴(kuò)展區(qū)域即可．另外，對(duì)每幀來說，視域裁剪不但可以快速確定每一場(chǎng)景的可見性，也可判斷場(chǎng)景內(nèi)每一結(jié)點(diǎn)的保守可見性，以最大限度地減少實(shí)時(shí)繪制量，因此，每幀繪制的點(diǎn)數(shù)目?jī)H占原始數(shù)據(jù)的很少一部分，每幀的自適應(yīng)漫游平均時(shí)間可維持在0．04 s以內(nèi)．

圖5 不同控制因子下的點(diǎn)云自適應(yīng)表達(dá)Fig．5 Adaptive expression of point-cloud data under different control factors

表1 不同控制因子下的點(diǎn)云自適應(yīng)表達(dá)參數(shù)Tab．1 Parameters of adaptive expression of point-cloud data under different control factors

圖6 大規(guī)模點(diǎn)云自適應(yīng)表達(dá)Fig．6 Adaptive expression of large-scale point-cloud data

表2 大規(guī)模點(diǎn)云自適應(yīng)表達(dá)參數(shù)Tab．2 Parameters of adaptive expression of large-scale point-cloud data

3 結(jié) 論

采用八叉樹空間索引，結(jié)合有針對(duì)性的數(shù)據(jù)組織和加速策略，實(shí)現(xiàn)了大規(guī)模點(diǎn)云的多細(xì)節(jié)流暢顯示，解決了傳統(tǒng)方法中不易管理海量數(shù)據(jù)，且較難實(shí)現(xiàn)自適應(yīng)表達(dá)的問題，得到以下主要結(jié)論：

（1）利用八叉樹高效的數(shù)據(jù)索引結(jié)構(gòu)，結(jié)合自上而下分割和自下而上計(jì)算的預(yù)處理策略構(gòu)建結(jié)點(diǎn)的細(xì)節(jié)層次，可實(shí)現(xiàn)點(diǎn)云自適應(yīng)多分辨率表達(dá)．

（2）保守可見性判斷和增量更新方法簡(jiǎn)單高效，使內(nèi)存占用率很低，且交互量很少，極大壓縮了實(shí)時(shí)階段繪制量．

（3）結(jié)合八叉樹結(jié)點(diǎn)細(xì)節(jié)層次模型和輔助加速算法，實(shí)時(shí)階段計(jì)算量和數(shù)據(jù)冗余度都很小，能夠滿足大規(guī)模點(diǎn)云的自適應(yīng)流暢顯示，每幀的自適應(yīng)平均漫游時(shí)間可維持在0．04 s以內(nèi)．

［1］ 李德仁．論地球空間信息的三維可視化：基于圖形還是基于影像［J］．測(cè)繪學(xué)報(bào)，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］ 張帆，黃先鋒，李德仁．基于球面投影的單站地面激光掃描點(diǎn)云構(gòu)網(wǎng)方法［J］．測(cè)繪學(xué)報(bào)，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］．西南交通大學(xué)學(xué)報(bào)，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］．地理與地理信息科學(xué)，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］ 龔俊，朱慶，張葉廷，等．顧及多細(xì)節(jié)層次的三維R-索引擴(kuò)展方法［J］．測(cè)繪學(xué)報(bào)，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樹索引的三維場(chǎng)景細(xì)節(jié)層次自適應(yīng)控制方法［J］．測(cè)繪學(xué)報(bào)，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ù)的實(shí)時(shí)獲取、建模與可視化［M］．武漢：武漢大學(xué)出版社，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

國土資源部地學(xué)空間信息技術(shù)重點(diǎn)實(shí)驗(yàn)室開放基金（KLGSIT2014-02）；河南省教育廳科學(xué)技術(shù)研究重點(diǎn)項(xiàng)目（14A420001）；地理信息工程國家測(cè)繪地理信息局重點(diǎn)實(shí)驗(yàn)室開放基金（201318）

張俊峰（1982—），男，講師，博士，研究方向?yàn)榈乩硇畔⒅悄芑幚砼c可視化，電話：13673355837，E-mail：zh-junfeng＠163．com

張俊峰，許德合，王小東．顧及自適應(yīng)多細(xì)節(jié)層次的八叉樹點(diǎn)云管理算法［J］．西南交通大學(xué)學(xué)報(bào)，2016，51（1）：78-84．