一種面向移動(dòng)終端地理場(chǎng)景點(diǎn)云在線可視化的集成型索引

邱波 ，張豐 *，杜震洪 ，劉仁義 ，張書瑜 ，范心儀

（1.浙江大學(xué)浙江省資源與環(huán)境信息系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，浙江杭州310028；2.浙江大學(xué)地理信息科學(xué)研究所，浙江 杭州 310027）

0 引 言

點(diǎn)云數(shù)據(jù)作為三維GIS（地理信息系統(tǒng)，geographic information system）重要的數(shù)據(jù)來(lái)源之一，具有獲取方便、精度高等特點(diǎn)，實(shí)現(xiàn)大規(guī)模點(diǎn)云數(shù)據(jù)的快速可視化對(duì)地理場(chǎng)景的建立與表達(dá)具有重要意義，而可視化的基礎(chǔ)是高效的點(diǎn)云數(shù)據(jù)組織管理方法。

目前，已有大量學(xué)者對(duì)點(diǎn)云數(shù)據(jù)的組織管理方法展開(kāi)了研究，這些研究多以樹形結(jié)構(gòu)為基礎(chǔ)，可以細(xì)分為基于單一樹形索引和基于集成型樹形索引2種。（1）在單一樹形索引的研究中，國(guó)內(nèi)外研究者大多針對(duì)該樹形結(jié)構(gòu)問(wèn)題做優(yōu)化，如四叉樹與Hilbert曲線融合以減少索引構(gòu)建時(shí)的I/O開(kāi)銷［1］、支持點(diǎn)云LOD（多細(xì)節(jié)層次，levels of details）模型擴(kuò)展的八叉樹［2-6］、改進(jìn)結(jié)點(diǎn)編碼與解決數(shù)據(jù)分配不均衡的八 叉 樹［7-8］、節(jié) 省 內(nèi) 存 占 用 的 線 性 KD 樹（kdimensional樹）［9］等。（2）集成型樹形索引往往能充分發(fā)揮各樹形結(jié)構(gòu)的優(yōu)點(diǎn)，在現(xiàn)有點(diǎn)云數(shù)據(jù)索引研究上具有重要地位，并呈主流發(fā)展趨勢(shì)，如加強(qiáng)了三維坐標(biāo)點(diǎn)匹配搜索能力的“規(guī)則八叉樹&平衡二叉樹”集成型索引［10］、提升了R樹在點(diǎn)云組織管理中創(chuàng)建效率的“八叉樹 &R樹”集成型索引［11］、滿足自適應(yīng)點(diǎn)云數(shù)據(jù)管理的“四叉樹&R樹”集成型索引［12］、針對(duì)公路工程激光雷達(dá)點(diǎn)云數(shù)據(jù)特點(diǎn)設(shè)計(jì)的“四叉樹&KD樹”集成型索引［13］、提升索引在各應(yīng)用場(chǎng)景下魯棒性的“KD樹&八叉樹”集成型索引［14］等。

上述研究雖然給出了解決點(diǎn)云數(shù)據(jù)組織管理的有效方案，但均集中于面向桌面或Web端的可視化應(yīng)用，缺乏對(duì)移動(dòng)端網(wǎng)絡(luò)帶寬、計(jì)算與渲染能力、內(nèi)外存空間等性能特點(diǎn)的考慮；缺乏針對(duì)移動(dòng)端的數(shù)據(jù)索引組織方法的深入研究［15-16］。針對(duì)上述問(wèn)題，本文在深度考慮以上移動(dòng)終端特性的基礎(chǔ)上，對(duì)面向移動(dòng)端點(diǎn)云在線可視化應(yīng)用的點(diǎn)云數(shù)據(jù)索引內(nèi)容進(jìn)行了總結(jié)：

（1）數(shù)據(jù)的相對(duì)關(guān)聯(lián)性?？梢暬税l(fā)起的數(shù)據(jù)請(qǐng)求往往會(huì)出現(xiàn)大范圍數(shù)據(jù)重疊的情況，點(diǎn)云數(shù)據(jù)之間的空間關(guān)聯(lián)度較低，為減少移動(dòng)端網(wǎng)絡(luò)資源的浪費(fèi)，加快渲染速度，需考慮數(shù)據(jù)空間的關(guān)聯(lián)性建設(shè)，以支持對(duì)點(diǎn)云數(shù)據(jù)間關(guān)系的判斷。

（2）數(shù)據(jù)在網(wǎng)絡(luò)上傳輸?shù)目煽啃耘c在移動(dòng)端渲染的快速性。數(shù)據(jù)是應(yīng)用的基礎(chǔ)，移動(dòng)端發(fā)起一次數(shù)據(jù)請(qǐng)求后，須保證該次請(qǐng)求結(jié)果集在網(wǎng)絡(luò)上傳輸?shù)姆€(wěn)定性，同時(shí)也要保證移動(dòng)端能夠依靠有限的計(jì)算渲染資源完成該份數(shù)據(jù)的快速解析與渲染工作。

（3）數(shù)據(jù)的多層次細(xì)節(jié)模型。移動(dòng)端的硬件資源有限，而點(diǎn)云地理場(chǎng)景開(kāi)闊、精度高、數(shù)據(jù)量大，如果為移動(dòng)端提供的點(diǎn)云場(chǎng)景數(shù)據(jù)都具有相同的可視化精度等級(jí)，顯然會(huì)出現(xiàn)非重要對(duì)象占用過(guò)多渲染資源的問(wèn)題。因此，從后續(xù)移動(dòng)端的可視化效果角度出發(fā)，點(diǎn)云數(shù)據(jù)的組織方法在構(gòu)建之初，就要求能支持點(diǎn)云數(shù)據(jù)的多細(xì)節(jié)層次表達(dá)。

基于以上分析，在點(diǎn)云數(shù)據(jù)索引研究方向逐漸趨向集成型索引的背景下，本文充分利用KD樹的平衡性與優(yōu)秀的空間劃分能力、八叉樹簡(jiǎn)單的算法邏輯與較低的計(jì)算機(jī)資源開(kāi)銷等優(yōu)點(diǎn)，結(jié)合優(yōu)化后的集成型樹形索引的管理結(jié)構(gòu)，提出了面向移動(dòng)點(diǎn)云在線可視化應(yīng)用的DKD-tree（動(dòng)態(tài)KD樹，dynamic KD-tree）&LLOctree（ 鏈 線 八 叉 樹 ，linked_linear octree）集成型點(diǎn)云數(shù)據(jù)管理方法。首先，利用考慮了移動(dòng)終端網(wǎng)絡(luò)帶寬與計(jì)算渲染能力的DKD-tree對(duì)原始點(diǎn)云數(shù)據(jù)實(shí)現(xiàn)均衡劃分與編碼；然后，利用優(yōu)化后的二級(jí)樹組織結(jié)構(gòu)，形成了便于管理且支持點(diǎn)云數(shù)據(jù)LOD模型的LLOctree；最后，通過(guò)自然數(shù)編碼，聯(lián)接DKD-tree與LLOctree的內(nèi)層組織，形成〈1 DKD-tree：1 LLOctree〉的集成型點(diǎn)云數(shù)據(jù)索引。該方法能為移動(dòng)端提供基于LOD的高效率渲染方案、支持從數(shù)據(jù)塊層面完成點(diǎn)云數(shù)據(jù)的空間關(guān)系判斷、支持移動(dòng)端對(duì)數(shù)據(jù)的多線程請(qǐng)求以及對(duì)數(shù)據(jù)請(qǐng)求的動(dòng)態(tài)合并。

1 DKD-tree & LLOctree集成型索引

集成型索引的整體結(jié)構(gòu)：首先使用DKD-tree完成數(shù)據(jù)的劃分與重組織，然后再利用LLOctree對(duì)DKD-tree劃分后的數(shù)據(jù)進(jìn)行二次組織。

1.1 基于DKD-tree的點(diǎn)云數(shù)據(jù)重組織方法

1.1.1 DKD-tree的構(gòu)建參數(shù)

DKD-tree是對(duì)KD樹的改進(jìn)，兩者都屬于二叉查找樹在多維空間應(yīng)用上的擴(kuò)展，內(nèi)部結(jié)點(diǎn)均擁有“空間劃分域”與“空間劃分域值”屬性。在選擇方式上，DKD-tree的空間劃分域與空間劃分域值由數(shù)據(jù)的分布情況動(dòng)態(tài)確定，而非靜態(tài)設(shè)定。DKD-tree的葉結(jié)點(diǎn)具有“分割粒度”屬性與“編碼”值。實(shí)際上，KD樹也具有分割粒度屬性，該值為1，即葉結(jié)點(diǎn)的數(shù)據(jù)存儲(chǔ)量為1。

對(duì)于一棵深度為H、分割粒度為S的DKD-tree，用 D（i，j，d，v）表示該 DKD-tree中第 i層第 j個(gè)結(jié)點(diǎn)。D所對(duì)應(yīng)的空間劃分域?yàn)閐，v表示點(diǎn)云數(shù)據(jù)在該空間劃分域下的分割超平面的取值，即空間劃分域值。

由于KD樹具有使用單個(gè)結(jié)點(diǎn)存儲(chǔ)單一k維數(shù)據(jù)的特性，在管理大規(guī)模點(diǎn)云數(shù)據(jù)時(shí)，會(huì)浪費(fèi)較多的內(nèi)存資源，并且采用交替方法設(shè)定空間劃分域較為機(jī)械，不能保證空間劃分尺度的均衡性。針對(duì)KD樹的這些缺點(diǎn)，筆者對(duì)其做了以下改進(jìn)：

（1）空間劃分域d。對(duì)任意非葉結(jié)點(diǎn)D（i，j，d，v），在i相同的情況下d的取值可以不同（i=1，2，…，H-1）。d的取值取決于D結(jié)點(diǎn)下的點(diǎn)云數(shù)據(jù)集在對(duì)應(yīng)三維空間中最長(zhǎng)的坐標(biāo)軸，與點(diǎn)云數(shù)據(jù)其他維度無(wú)關(guān)。非葉結(jié)點(diǎn)情況下，d的取值為0，1或2，分別對(duì)應(yīng)x、y、z坐標(biāo)軸；葉結(jié)點(diǎn)情況下，d的取值為-1，表示無(wú)空間劃分域。

（2）空間劃分域值v。v的取值為D結(jié)點(diǎn)下的點(diǎn)云數(shù)據(jù)集在空間劃分域d上的中值。

（3）葉結(jié)點(diǎn)的“分割粒度”S。DKD-tree不再使用葉結(jié)點(diǎn)來(lái)維護(hù)僅僅一條k維空間數(shù)據(jù)；對(duì)任意葉結(jié)點(diǎn) D（H，index，dindex，vindex），其中 index=0，1，2，…，2H-1-1，當(dāng)點(diǎn)云數(shù)據(jù)量最接近“分割粒度”S的設(shè)定值時(shí)，DKD-tree停止對(duì)當(dāng)前葉結(jié)點(diǎn)的剖分。

（4）DKD-tree葉節(jié)點(diǎn)的編碼index。對(duì)每一個(gè)葉節(jié)點(diǎn) D（H，index，dindex，vindex）設(shè)定編碼 index，其中index=0，1，2，…，2H-1-1。

由以上改進(jìn)可知，DKD-tree是一棵滿二叉樹。由改進(jìn)（1）與（2）知，DKD-tree葉結(jié)點(diǎn)所對(duì)應(yīng)的點(diǎn)云數(shù)據(jù)量近似相等。任一葉結(jié)點(diǎn)所對(duì)應(yīng)的點(diǎn)云數(shù)據(jù)的最小外包長(zhǎng)方體，經(jīng)一定操作后理論上接近正方體。以上特點(diǎn)保證了點(diǎn)云空間與數(shù)據(jù)劃分粒度的均衡性。由改進(jìn)（3）知，DKD-tree的深度由分割粒度決定，分割粒度值直接影響點(diǎn)云數(shù)據(jù)傳輸?shù)目煽啃耘c速度、移動(dòng)端的渲染速度以及后續(xù)篩選查詢的效率，最終影響移動(dòng)可視化端的用戶體驗(yàn)。因此，分割粒度值S是構(gòu)建DKD-tree的關(guān)鍵。

移動(dòng)端可視化應(yīng)用基于“在線獲取數(shù)據(jù)，即時(shí)渲染呈現(xiàn)”的工作模式，因此，在有限網(wǎng)絡(luò)帶寬的情況下，要使移動(dòng)端能秒級(jí)響應(yīng)場(chǎng)景渲染請(qǐng)求，須考慮以下情況：DKD-tree某一葉結(jié)點(diǎn)D對(duì)應(yīng)的點(diǎn)云數(shù)據(jù)完全滿足用戶需求，均須給移動(dòng)端提供解析和渲染（不考慮數(shù)據(jù)壓縮、LOD分級(jí)以及多線程請(qǐng)求的情況）。針對(duì)上述情況，為了使該結(jié)點(diǎn)下的數(shù)據(jù)通過(guò)網(wǎng)絡(luò)穩(wěn)定傳輸，也須保證在移動(dòng)端的硬件條件下被快速地解析和渲染。綜上，以秒級(jí)響應(yīng)作為參考標(biāo)準(zhǔn)，得到“分割粒度”S以及“分割粒度”S與深度H的大致關(guān)系：

式（1）中，count表示在某格式的點(diǎn)云下1MByte可以存儲(chǔ)的點(diǎn)云數(shù)量；speednetwork表示移動(dòng)端網(wǎng)絡(luò)帶寬條件下最小的數(shù)據(jù)下載速度，speedrendering表示移動(dòng)端能夠秒級(jí)渲染呈現(xiàn)的點(diǎn)云數(shù)據(jù)大小；speednetwork與speedrendering都以 MByte·s-1為單位；式（2）中的 M 為原點(diǎn)云數(shù)據(jù)總量。

作為在開(kāi)放式網(wǎng)絡(luò)環(huán)境下工作的移動(dòng)終端，speednetwork值應(yīng)以移動(dòng)通信網(wǎng)絡(luò)的帶寬閾值為參考標(biāo)準(zhǔn)（封閉式內(nèi)部網(wǎng)絡(luò)環(huán)境除外）；speedrendering值應(yīng)以主流設(shè)備的計(jì)算與渲染能力為參考進(jìn)行測(cè)算。

1.1.2 本地點(diǎn)云數(shù)據(jù)的重組織方法

如果每次構(gòu)建點(diǎn)云數(shù)據(jù)索引時(shí)都需要對(duì)原始點(diǎn)云數(shù)據(jù)重新讀取和處理，會(huì)造成時(shí)間和計(jì)算機(jī)資源的大量浪費(fèi)。因此，將索引構(gòu)建的基礎(chǔ)建立在經(jīng)重新組織的點(diǎn)云數(shù)據(jù)上，可有效提升構(gòu)建效率。本文依據(jù)DKD-tree參數(shù)設(shè)定完成對(duì)原始點(diǎn)云數(shù)據(jù)的重組織工作，以提升后續(xù)構(gòu)建DKD-tree的效率。

對(duì)任一點(diǎn)云數(shù)據(jù)，由1.1.1節(jié)，可計(jì)算在其基礎(chǔ)上構(gòu)建的DKD-tree的分割粒度值S與深度值H。若重組織操作中生成的某一點(diǎn)云文件具有劃分深度h的屬性值，則表示該文件由原始點(diǎn)云文件經(jīng)（h-1）次二分操作得到。DKD-tree的深度值與重組織操作的最大劃分深度對(duì)應(yīng)，原始點(diǎn)云文件的劃分深度為1?；谝陨显O(shè)定，點(diǎn)云數(shù)據(jù)重組織方法的具體過(guò)程如下：

輸入：本地原始點(diǎn)云數(shù)據(jù)文件的路徑Path；重組織操作的最大劃分深度H。

（1）如果H≤1，進(jìn)入步驟（3）；如果H＞1，設(shè)定h=1，進(jìn)入步驟（2）。

（2）①依據(jù)文件名獲取Path路徑下劃分深度為h的文件集合｛file0，file1，file2，…，file2h-1-1｝。②對(duì)于集合中每一份點(diǎn)云文件filei（i=0，1，…，2h-1-1）內(nèi)的數(shù)據(jù)，計(jì)算其在x、y、z維度上的最長(zhǎng)軸di（d取0，1或2，分別對(duì)應(yīng)x、y與z軸），并基于桶統(tǒng)計(jì)思想計(jì)算其在軸 di上的中值 vi，以 di，vi為 filei生成左右子文件，子文件的文件名分別在filei.name的基礎(chǔ)上添加（di，vi，“l(fā)eft”）、（di，vi，“right”）信息。③h++。④如果h＜H，繼續(xù)步驟（2）；如果h≥H，進(jìn)入步驟（3）。

（3）點(diǎn)云數(shù)據(jù)的重組織過(guò)程結(jié)束。

根據(jù)以上點(diǎn)云數(shù)據(jù)的重組織方法，任意點(diǎn)云數(shù)據(jù)最終都會(huì)得到2H-1個(gè)劃分深度為H的子點(diǎn)云文件。圖1（a）為點(diǎn)云數(shù)據(jù)data.txt執(zhí)行了劃分深度為3后的過(guò)程，劃分深度為1的文件即為原始點(diǎn)云文件data.txt。data.txt生成了2份劃分深度為2的子文件，解析這2份子文件的文件名可以得到本次劃分操作的信息：數(shù)據(jù)劃分的依據(jù)是z軸、數(shù)據(jù)在z軸上的中值是z=0.5的超平面。同理，對(duì)以上2份劃分深度為2的點(diǎn)云文件分別進(jìn)行劃分操作，將產(chǎn)生4份新的子文件，其文件名同時(shí)包含第1次劃分與本次劃分的屬性。至此，點(diǎn)云文件data.txt的重組織過(guò)程結(jié)束。

圖1 點(diǎn)云文件劃分示例及在其基礎(chǔ)上構(gòu)建的DKD-treeFig.1 The example of file partition on point clouds and the DKD-tree constructed on it

通過(guò)分析點(diǎn)云數(shù)據(jù)的重組織方法可知，對(duì)某一點(diǎn)云數(shù)據(jù)進(jìn)行重組織的過(guò)程，即為依據(jù)該份數(shù)據(jù)第一次構(gòu)建DKD-tree的過(guò)程。重組織方法的數(shù)據(jù)劃分軸與DKD-tree的空間劃分域?qū)?yīng)，數(shù)據(jù)在劃分軸上的中值與DKD-tree的空間劃分域值對(duì)應(yīng)，生成的每一份文件都與DKD-tree中的一個(gè)結(jié)點(diǎn)對(duì)應(yīng)，其中，2H-1個(gè)劃分深度為H的子點(diǎn)云文件與DKD-tree的葉結(jié)點(diǎn)對(duì)應(yīng)。

1.1.3 DKD-tree的構(gòu)建方法

基于重組織后的點(diǎn)云數(shù)據(jù)，可以快速構(gòu)建DKD-tree。此時(shí)，僅通過(guò)解析本文1.2節(jié)中劃分深度為H的2H-1個(gè)子點(diǎn)云文件的文件名，就可以快速構(gòu)建一棵深度為H的DKD-tree。具體構(gòu)建方法如下：

輸入：DKD-tree深度H。

（1）獲取劃分深度為H的點(diǎn)云文件集合｛file0，file1，file2，…，file｝。

（2）①對(duì)集合中的每一份點(diǎn)云文件filei（i=0，1，…，2H-1-1）的文件名進(jìn)行字符串解析，更新或從根結(jié)點(diǎn)到葉結(jié)點(diǎn) D（H，i，di，vi）的簡(jiǎn)單路徑上生成每個(gè)結(jié)點(diǎn)信息。②為葉結(jié)點(diǎn)D（H，i，di，vi）設(shè)定唯一編碼i，并將文件filei的數(shù)據(jù)委托葉結(jié)點(diǎn)D管理。

（3）構(gòu)樹完成。

基于圖1（a）中最終生成的4份點(diǎn)云數(shù)據(jù)的文件名，可以構(gòu)建如圖1（b）所示的DKD-tree。除只含有編碼標(biāo)記的葉結(jié)點(diǎn)外，其他每個(gè)結(jié)點(diǎn)都包含了每次的空間劃分信息：左右子樹位置、空間劃分域，空間劃分域值。

1.2 基于LLOctree的點(diǎn)云數(shù)據(jù)管理方法

如果僅使用DKD-tree作為服務(wù)端數(shù)據(jù)服務(wù)的基礎(chǔ)，當(dāng)移動(dòng)在線應(yīng)用平臺(tái)需要提供精細(xì)的點(diǎn)云數(shù)據(jù)時(shí)，通過(guò)遍歷相應(yīng)葉結(jié)點(diǎn)內(nèi)所有數(shù)據(jù)完成深度查詢操作顯然會(huì)降低索引的效率。若對(duì)DKD-tree葉結(jié)點(diǎn)繼續(xù)進(jìn)行剖分操作，降低葉結(jié)點(diǎn)的分割粒度，導(dǎo)致以DKD-tree葉結(jié)點(diǎn)為請(qǐng)求單位的移動(dòng)端必須請(qǐng)求多倍的細(xì)粒度數(shù)據(jù)，造成大量網(wǎng)絡(luò)資源浪費(fèi)，甚至導(dǎo)致信令風(fēng)暴，同時(shí)，較小的分割粒度值增加了DKD-tree深度，數(shù)據(jù)查詢效率也會(huì)相應(yīng)下降。綜上所述，在保證索引原有效率的基礎(chǔ)上，為了應(yīng)對(duì)數(shù)據(jù)深度查詢的需求，為每個(gè)DKD-tree葉結(jié)點(diǎn)內(nèi)的數(shù)據(jù)建立二級(jí)索引非常必要。

本文在對(duì)每一份葉結(jié)點(diǎn)數(shù)據(jù)進(jìn)行LOD建模的基礎(chǔ)上，用LLOctree作為二級(jí)索引來(lái)存放LOD模型。

1.2.1 點(diǎn)云數(shù)據(jù)LOD模型的構(gòu)建方法

LOD（levels of details）技術(shù)指根據(jù)物體模型的結(jié)點(diǎn)在顯示環(huán)境中所處的位置和重要度，決定物體渲染的資源分配，降低非重要物體的細(xì)節(jié)度，從而獲得高效率的渲染運(yùn)算。對(duì)于大規(guī)模點(diǎn)云數(shù)據(jù)，移動(dòng)應(yīng)用沒(méi)必要更沒(méi)能力一次性完成點(diǎn)云場(chǎng)景繪制；即使在面向桌面級(jí)應(yīng)用的相關(guān)研究中，點(diǎn)云數(shù)據(jù)的LOD建模方法也是研究的重點(diǎn)之一。

通常在基于任意對(duì)象構(gòu)建的多層次可視化精度描述中，除了“最精細(xì)”外，還包含臨界層次“接近最精細(xì)”與“最粗糙”及兩者的中間層次。對(duì)于“接近最精細(xì)”與“最粗糙”兩項(xiàng)可視化精度描述，在本文的LOD建模方法中分別代表2項(xiàng)具有實(shí)際意義的參數(shù)：最大可視化精度比VPR_Max（maximum visual precision ratio）與最小可視化精度比VPR_Min（minimum visualprecision ratio） 。VPR_Max是點(diǎn)云數(shù)據(jù)LOD建模是否合格的判定條件；VPR_Min是在當(dāng)前點(diǎn)云數(shù)據(jù)LOD模型下，為移動(dòng)端提供的LOD數(shù)據(jù)是否達(dá)到可視化精度要求的判定條件。確定VPR_Max與VPR_Min的方法為：對(duì)任意場(chǎng)景下的點(diǎn)云數(shù)據(jù)，分別隔n個(gè)點(diǎn)進(jìn)行粗采樣繪制（n=2，3，…），通過(guò)對(duì)比原渲染效果，在視覺(jué)效果差別非常小的情況下，采樣的數(shù)據(jù)占原數(shù)據(jù)的比例為VPR_Max；能基本分辨對(duì)象的情況下，采樣數(shù)據(jù)占原數(shù)據(jù)的比例為VPR_Min。筆者對(duì)多份不同來(lái)源、不同場(chǎng)景的點(diǎn)云數(shù)據(jù)進(jìn)行了測(cè)試與驗(yàn)證，發(fā)現(xiàn)VPR_Max值通常在1/2，VPR_Min值在1/10。

圖2 點(diǎn)云數(shù)據(jù)LOD建模方法在二維空間下的示例Fig.2 A example of the LOD modeling method on point cloud in the case of 2D

圖2 使用二維圖方式描述了三維空間下點(diǎn)云數(shù)據(jù)的LOD建模方式。設(shè)定空間中每個(gè)點(diǎn)具有l(wèi)evel屬性，表示該點(diǎn)在LOD模型中所處的層次。圖2（a）表示原始點(diǎn)云數(shù)據(jù)集（黑色點(diǎn)簇）及其最小外包矩形grid（三維空間下對(duì)應(yīng)最小外包長(zhǎng)方體）；計(jì)算并標(biāo)記距離grid中心（紫色菱形點(diǎn)）最近的點(diǎn)為紅色，level賦值為 0；圖 2（b）中首先移除圖 2（a）已被處理的紅色點(diǎn)，然后對(duì)grid實(shí)現(xiàn)金字塔劃分，得到4個(gè)child_gridi（i=0，1，2，3），同樣，計(jì)算得到每個(gè)child_grid中距離該child_grid中心最近的點(diǎn)，并將這些點(diǎn)的顏色標(biāo)記為橙色、level賦值為1；對(duì)于剩余的未經(jīng)處理的5個(gè)黑點(diǎn)，level賦值為2。處理結(jié)果如圖2（c）所示，統(tǒng)計(jì)圖2（c）中各點(diǎn)信息，得到的相關(guān)數(shù)據(jù)如表1所示。

以VPR_Min=1/10為例，LOD層次level為0時(shí)點(diǎn)數(shù)據(jù)占總數(shù)的比例滿足level0。ratio≥VPR_Min，對(duì)于該點(diǎn)簇，level0下的點(diǎn)集已經(jīng)達(dá)到識(shí)別該點(diǎn)簇的可視化精度要求。當(dāng)移動(dòng)端請(qǐng)求該點(diǎn)簇?cái)?shù)據(jù)用于渲染時(shí)，LOD模型至少需要為移動(dòng)端應(yīng)用提供level0下的數(shù)據(jù)，以滿足用戶的可視化精度需求。

表1 圖2（c）中的點(diǎn)信息統(tǒng)計(jì)Table 1 Statistics of point information in Fig.2（c）

2次LOD建模操作后，level0與level1的數(shù)據(jù)集合占數(shù)據(jù)總量的50%。如果對(duì)當(dāng)前點(diǎn)簇進(jìn)行1次或3次LOD建模操作，非最大level（最高level值為L(zhǎng)OD建模操作次數(shù)加1）下的LOD數(shù)據(jù)占比不及當(dāng)前情況下接近VPR_Max。因此，當(dāng)前點(diǎn)云數(shù)據(jù)合理的LOD模型層級(jí)應(yīng)當(dāng)設(shè)定為0～2；level0與level1的點(diǎn)數(shù)據(jù)集，具有較好的點(diǎn)云對(duì)象可視化效果。而對(duì)于剩余的占比50%、level=2的點(diǎn)數(shù)據(jù)，其重要程度相對(duì)較低，在移動(dòng)端渲染壓力與網(wǎng)絡(luò)壓力不太大的情況下，可考慮請(qǐng)求并繪制數(shù)據(jù)。

上文對(duì)點(diǎn)云LOD建模方法的基礎(chǔ)流程進(jìn)行了闡述，值得注意的是，對(duì)于每一個(gè)DKD-tree葉結(jié)點(diǎn)下的點(diǎn)云數(shù)據(jù)集，均須在相同的LOD層級(jí)上進(jìn)行模型構(gòu)建；每個(gè)數(shù)據(jù)集的最小外包長(zhǎng)方體無(wú)論是否為正方體，都需要在x，y，z維度上進(jìn)行等分。

設(shè)在LOD模型層次為0～k的點(diǎn)云數(shù)據(jù)集中，非最低重要度的數(shù)據(jù)占原數(shù)據(jù)的比值為真實(shí)最大可視化精度比（real maximum visualization precision ratio）：

若LOD模型層級(jí)的構(gòu)建基于0～k-1或0～k+1時(shí)的真實(shí)最大可視化精度比為RVPR_Max’，則有

1.2.2 LLOctree的構(gòu)建方法

通常情況下，對(duì)2H-1個(gè)DKD-tree的葉結(jié)點(diǎn)進(jìn)行LOD建模后，也會(huì)構(gòu)建2H-1棵二級(jí)索引存儲(chǔ)LOD模型，并與DKD-tree的葉結(jié)點(diǎn)一一對(duì)應(yīng)，形成基于〈1一級(jí)樹：N二級(jí)樹〉管理結(jié)構(gòu)的集成型樹形索引，見(jiàn)圖3。很明顯，〈1一級(jí)樹：N二級(jí)樹〉的索引結(jié)構(gòu)增加了二級(jí)索引的管理復(fù)雜度，同時(shí)造成內(nèi)存資源的浪費(fèi)。本文利用具有算法邏輯簡(jiǎn)單、計(jì)算機(jī)資源開(kāi)銷較小等優(yōu)點(diǎn)的八叉樹作為存儲(chǔ)LOD模型的數(shù)據(jù)結(jié)構(gòu)，為避免〈1一級(jí)樹：N二級(jí)樹〉索引結(jié)構(gòu)帶來(lái)的問(wèn)題，融合了DKD-tree下2H-1個(gè)葉結(jié)點(diǎn)對(duì)應(yīng)的2H-1棵八叉樹生成一棵LLOctree，實(shí)現(xiàn)了〈1一級(jí)樹：1二級(jí)樹〉的集成型樹形索引管理框架。

圖3 常見(jiàn)集成型樹形索引的框架結(jié)構(gòu)Fig.3 The structure of common integrated index

LLOctree具有如下特性：樹內(nèi)結(jié)點(diǎn)間關(guān)系使用指針維護(hù)，每個(gè)結(jié)點(diǎn)內(nèi)使用線性數(shù)據(jù)結(jié)構(gòu)分層存儲(chǔ)信息，在其第N個(gè)結(jié)點(diǎn)的第M內(nèi)層結(jié)構(gòu)上，存儲(chǔ)了DKD-tree下第M棵八叉樹的第N個(gè)結(jié)點(diǎn)信息。綜上所述，對(duì)任一DKD-tree的葉結(jié)點(diǎn)D（H，index，dindex，vindex），可 通 過(guò) 自 然 數(shù) 編 碼 index與LLOctree建立聯(lián)系，然后對(duì)自己映射的點(diǎn)云LOD模型進(jìn)行數(shù)據(jù)的存取操作?；贚OD數(shù)據(jù)模型的LLOctree構(gòu)建方法較為簡(jiǎn)單，具體步驟如下：

輸入：設(shè)定LLOctree的深度height、LLOctree層級(jí)與LOD層次的映射關(guān)系。

（1）按height生成一顆滿LLOctree，根據(jù)點(diǎn)云數(shù)據(jù)塊初始化每個(gè)結(jié)點(diǎn)下每個(gè)內(nèi)層的最小外包長(zhǎng)方體信息。

（2）為DKD-tree葉結(jié)點(diǎn)編碼為index數(shù)據(jù)構(gòu)建LOD模型。

（3）按照映射關(guān)系將數(shù)據(jù)模型存儲(chǔ)在LLOctree的第index內(nèi)層。

（4）構(gòu)樹完成。

映射關(guān)系描述了LOD某一細(xì)節(jié)層次數(shù)據(jù)存放在LLOctree中的層級(jí)位置，例如：映射關(guān)系（（1→0，1））表示LLOctree的第1層存儲(chǔ)了某點(diǎn)云數(shù)據(jù)LOD模型第0級(jí)與第1級(jí)的細(xì)節(jié)數(shù)據(jù)。由上可知，LLOctree的查詢深度僅與可視化端的精度需求掛鉤，而每一結(jié)點(diǎn)的數(shù)據(jù)量有限，LLOctree的深度往往較低，從而可有效避免樹的深度與查詢效率間的矛盾。

1.3 混合空間索引的搜索策略

本文的集成型樹形索引的整體結(jié)構(gòu)為：DKD-tree用作數(shù)據(jù)塊的初步定位，僅為葉結(jié)點(diǎn)保留編碼數(shù)據(jù)，本身不存儲(chǔ)任何點(diǎn)云數(shù)據(jù)；LLOctree存放了經(jīng)DKD-tree重組織后的點(diǎn)云數(shù)據(jù)LOD模型，并用作數(shù)據(jù)的深度查詢，LLOctree的入口是DKD-tree葉結(jié)點(diǎn)編碼。因此，DKD-tree&LLOctree集成型索引的空間查詢分為DKD-tree與LLOctree兩部分，具體查詢算法如下：

1.3.1 DKD-tree部分

（1）確定待查詢視域空間，以及視域最小外包長(zhǎng)方體在各坐標(biāo)軸上投影的最大、最小值range［xmax，xmin，ymax，ymin，zmax，zmin］，然后進(jìn)入 DKD-tree的根結(jié)點(diǎn)D（1，0，d0，v0）。若移動(dòng)端采用基于透視投影的渲染模型，則可將視椎體擴(kuò)展為長(zhǎng)方體后再計(jì)算range［xmax，xmin，ymax，ymin，zmax，zmin］，如圖 4 所示。

（2）若當(dāng)前待處理結(jié)點(diǎn)D不為葉結(jié)點(diǎn)，進(jìn)入步驟（3）；若為葉結(jié)點(diǎn)，進(jìn)入步驟（4）。

（3）獲取當(dāng)前結(jié)點(diǎn)的空間劃分域d與空間劃分域值v，取得range在當(dāng)前空間劃分域d所映射的坐標(biāo)軸上的最大值A(chǔ)xismax與最小值A(chǔ)xismin（Axis=x，y，z），進(jìn)而計(jì)算空間劃分域值 v與（Axismin，Axismax）的關(guān)系。

圖4 本文鄰域查詢模式下的視椎體擴(kuò)展結(jié)構(gòu)Fig.4 Extended structure of viewing frustum in neighbor query mode of this paper

①v＜Axismin，進(jìn)入當(dāng)前結(jié)點(diǎn)D的右子結(jié)點(diǎn)；

②v＞Axismax，進(jìn)入當(dāng)前結(jié)點(diǎn)D的左子結(jié)點(diǎn)；

③ Axismin≤v≤Axismax，同時(shí)進(jìn)入當(dāng)前結(jié)點(diǎn)D的左子結(jié)點(diǎn)與右子結(jié)點(diǎn)。

執(zhí)行步驟（2）。

（4）在結(jié)果集合Index Array中加入當(dāng)前結(jié)點(diǎn)D的索引編號(hào)index。

1.3.2 Octree部分

（5）對(duì)于每一個(gè) index=Index Array［i］，由 index在LLOctree相應(yīng)內(nèi)層下的遞歸情況搜索各結(jié)點(diǎn)在range空間范圍內(nèi)的數(shù)據(jù)，然后根據(jù)移動(dòng)在線應(yīng)用的需求將過(guò)濾后的數(shù)據(jù)返回。

DKD-tree混合LLOctree的空間索引模型以及LLOctree的結(jié)點(diǎn)結(jié)構(gòu)如圖5所示，其中顏色箭頭指向表示1次搜索過(guò)程。DKD-tree的第2H-1-1個(gè)葉結(jié)點(diǎn)會(huì)根據(jù)自身編碼進(jìn)入LLOctree的相應(yīng)內(nèi)層，然后執(zhí)行后續(xù)數(shù)據(jù)查詢?nèi)蝿?wù)。

圖5 DKD-tree與LLOctree集成的混合空間索引結(jié)構(gòu)Fig.5 Structure of the spatial index integrated with DKD-tree and LLOctree

1.4 本文索引支持下的移動(dòng)端數(shù)據(jù)獲取方法

面向移動(dòng)在線應(yīng)用的索引方法最終要以服務(wù)的形式為移動(dòng)終端提供數(shù)據(jù)支持?；诒疚乃饕龢?gòu)建的點(diǎn)云數(shù)據(jù)服務(wù)，除索引本身支持的LOD數(shù)據(jù)請(qǐng)求方法外，還有以下幾種移動(dòng)端數(shù)據(jù)獲取方法：

（1）多線程請(qǐng)求。移動(dòng)端可視化應(yīng)用，首先根據(jù)視域范圍從服務(wù)端DKD-tree查詢到點(diǎn)云結(jié)果集的編碼集合。然后，根據(jù)編碼集合，利用多線程請(qǐng)求方法從服務(wù)端的LLOctree中查詢到真正的數(shù)據(jù)結(jié)果。

（2）數(shù)據(jù)請(qǐng)求的動(dòng)態(tài)合并。移動(dòng)端的網(wǎng)絡(luò)狀態(tài)可能存在與服務(wù)端DKD-tree分割粒度不對(duì)等的情況，如移動(dòng)端處于4G移動(dòng)網(wǎng)絡(luò)條件下，而DKD-tree構(gòu)建的依據(jù)是3G移動(dòng)網(wǎng)絡(luò)。針對(duì)以上情況，移動(dòng)端可依據(jù)網(wǎng)絡(luò)狀態(tài)，實(shí)時(shí)、動(dòng)態(tài)地完成數(shù)據(jù)請(qǐng)求的合并操作，減少不必要的網(wǎng)絡(luò)請(qǐng)求帶來(lái)的硬件與時(shí)間資源的浪費(fèi)。

（3）緩存與預(yù)取。在移動(dòng)端硬件條件允許的情況下，利用視點(diǎn)預(yù)測(cè)算法，預(yù)先獲取可能視域下的點(diǎn)云數(shù)據(jù)，以提升移動(dòng)端點(diǎn)云場(chǎng)景漫游時(shí)的界面響應(yīng)速度。

對(duì)于獲/預(yù)取得到的數(shù)據(jù)，如果某一點(diǎn)云數(shù)據(jù)塊完全處于視域范圍內(nèi)，通過(guò)〈編碼，數(shù)據(jù)塊〉鍵值對(duì)方式，完成該數(shù)據(jù)塊的磁盤緩存或內(nèi)存緩存，供后續(xù)需要時(shí)使用，以降低數(shù)據(jù)的網(wǎng)絡(luò)請(qǐng)求頻率，提升界面響應(yīng)速度。

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

為驗(yàn)證本文針對(duì)移動(dòng)端點(diǎn)云在線可視化應(yīng)用提出的DKD-tree&LLOctree集成型空間索引是否具有實(shí)用性與有效性，用了Robotic 3D Scan Repository網(wǎng)站上公開(kāi)的德國(guó)不來(lái)梅Schlachte城（鎮(zhèn)）部分激光點(diǎn)云數(shù)據(jù)（約12 000 000個(gè)點(diǎn)）作為測(cè)試數(shù)據(jù)，選擇KD樹與八叉樹作為實(shí)驗(yàn)的對(duì)比對(duì)象。為避免八叉樹構(gòu)建時(shí)摻雜人為因素，如內(nèi)部結(jié)點(diǎn)是否存儲(chǔ)數(shù)據(jù)、樹的深度值設(shè)定、結(jié)點(diǎn)的扇出值設(shè)定等，本文參照LLOctree的特點(diǎn)對(duì)八叉樹設(shè)定了構(gòu)建規(guī)則：（1）八叉樹的非葉結(jié)點(diǎn)與LLOctree一樣也存儲(chǔ)數(shù)據(jù)。（2）八叉樹每個(gè)結(jié)點(diǎn)的扇出值（即分割粒度，超過(guò)該值則將結(jié)點(diǎn)剖分為8個(gè)子結(jié)點(diǎn)）參考DKD-tree的分割粒度值。

本節(jié)將從三方面展開(kāi)討論，服務(wù)端硬件環(huán)境為：處理器 Core（TM）i7-6700 CPU@3.40GHz；內(nèi)存8GB；操作系統(tǒng) Windows 10 64位?？蛻舳说挠布h(huán)境為：設(shè)備名稱 EVA-AL10（華為P9）；處理器Hisilicon Kirin 995；內(nèi)存 4 GB；操作系統(tǒng) EMUI 5.0（Android 7.0）。

2.1 索引構(gòu)建效率

執(zhí)行隔點(diǎn)采樣操作，得到10份實(shí)驗(yàn)樣本數(shù)據(jù)，樣本數(shù)據(jù)量分別為100萬(wàn)，200萬(wàn)，300萬(wàn)，…，1 000萬(wàn)，隔點(diǎn)采樣方法保證了各樣本數(shù)據(jù)的空間分布范圍與密度比例基本一致。

由圖6的對(duì)比結(jié)果可知，八叉樹索引的構(gòu)建效率最優(yōu)，這與自身簡(jiǎn)單的邏輯結(jié)構(gòu)緊密相關(guān)。KD樹索引使用〈1結(jié)點(diǎn)：1數(shù)據(jù)〉的數(shù)據(jù)存儲(chǔ)方式，易導(dǎo)致大量?jī)?nèi)存資源浪費(fèi)，甚至在數(shù)據(jù)量較大時(shí)導(dǎo)致建樹困難。實(shí)驗(yàn)結(jié)果表明，KD樹索引的構(gòu)建并不穩(wěn)定，總體而言，KD樹索引不適合大規(guī)模地理場(chǎng)景點(diǎn)云數(shù)據(jù)的組織管理。本文的DKD-tree&LLOctree集成型索引方法的構(gòu)建效率較八叉樹索引低，主要原因在于該索引方法擴(kuò)展了對(duì)數(shù)據(jù)LOD模型存儲(chǔ)管理的支持，消耗了一定時(shí)間。在索引構(gòu)建上，本文方法較KD樹方法可靠性高。

圖6 本文方法、KD樹與八叉樹索引的構(gòu)建性能比較Fig.6 Building performance of the integrated spatial index，KD-tree and Octree

2.2 空間查詢效率

依據(jù)實(shí)驗(yàn)數(shù)據(jù)構(gòu)建生成的DKD-tree&LLOctree集成型索引的具體參數(shù)如下：滿二叉樹DKD-tree的深度H為11，“分割粒度”S為15 000（以移動(dòng)3G網(wǎng)絡(luò)的帶寬閾值作為參考），葉結(jié)點(diǎn)編號(hào)依次為0～1 023，為每一葉結(jié)點(diǎn)的數(shù)據(jù)構(gòu)建了8個(gè)層級(jí)的LOD數(shù)據(jù)模型，1 024個(gè)LOD模型最終的RVPR_Max值為 0.589 1；LLOctree的深度 height為5，結(jié)點(diǎn)內(nèi)層數(shù)為1 024，LLOctree層級(jí)與LOD模型層次兩者的映射關(guān)系為（（1→0，1），（2→2，3），（3→4，5），（4→6），（5→7））。參考 DKD-tree，將八叉樹結(jié)點(diǎn)的扇出值設(shè)定為15 000。由2.1節(jié)的實(shí)驗(yàn)內(nèi)容可知，無(wú)法基于原始數(shù)量的點(diǎn)云數(shù)據(jù)構(gòu)建KD樹，因此，通過(guò)對(duì)實(shí)驗(yàn)數(shù)據(jù)隔點(diǎn)采樣得到半份數(shù)據(jù)約6 000 000個(gè)點(diǎn)，構(gòu)建KD樹。

圖7 本文方法、KD樹與八叉樹索引的空間查詢性能比較Fig.7 Query efficiency of the integrated spatial index，KD-tree and Octree

圖8 本文方法、KD樹與八叉樹索引的單點(diǎn)查詢性能比較Fig.8 Query efficiency of single node of the integrated spatial index，KD-tree and Octree

圖7為各索引在不同的查詢范圍內(nèi)，空間查詢操作所耗時(shí)間的數(shù)據(jù)對(duì)比。圖8為對(duì)圖7實(shí)驗(yàn)數(shù)據(jù)進(jìn)一步處理的結(jié)果，表示各索引在空間查詢操作中的單點(diǎn)耗時(shí)情況。本實(shí)驗(yàn)的查詢空間為正方體，邊長(zhǎng)用實(shí)驗(yàn)數(shù)據(jù)的單位表達(dá)。

由以上實(shí)驗(yàn)結(jié)果可知，即使基于半份數(shù)據(jù)構(gòu)建而成的KD樹索引，在數(shù)據(jù)查詢效率上仍與八叉樹、本文方法存在差距，這是因?yàn)樵趯?duì)數(shù)據(jù)量大的點(diǎn)云數(shù)據(jù)執(zhí)行空間查詢操作時(shí)，KD樹在鄰域關(guān)系重建環(huán)節(jié)上浪費(fèi)了大量的計(jì)算資源，致使空間查詢效率較低，進(jìn)一步證明其不適合大規(guī)模點(diǎn)云數(shù)據(jù)的組織與管理。八叉樹作為一種結(jié)構(gòu)簡(jiǎn)單的樹形索引，空間查詢效率保持中等水平。本文提出的DKD-tree&LLOctree集成型點(diǎn)云數(shù)據(jù)管理方法，在空間查詢效率上較KD樹索引與八叉樹索引優(yōu)勢(shì)明顯，單點(diǎn)查詢耗時(shí)約為4.0×10-5ms，較KD樹索引與八叉樹索引降低了一個(gè)數(shù)量級(jí)。

圖9為各索引在不同數(shù)據(jù)量下每次查詢操作的耗時(shí)。結(jié)果顯示，KD樹索引與八叉樹索引的空間查詢耗時(shí)基本與查詢結(jié)果集點(diǎn)數(shù)呈指數(shù)關(guān)系。無(wú)論本文的集成型方法是否采用LOD數(shù)據(jù)查詢策略，空間查詢耗時(shí)基本都與查詢結(jié)果集點(diǎn)數(shù)呈正比，表現(xiàn)出非常好的穩(wěn)定性。

2.3 數(shù)據(jù)的傳輸成功率

為驗(yàn)證依據(jù)KD樹索引、八叉樹索引以及本文集成型索引搭建的點(diǎn)云數(shù)據(jù)服務(wù)是否支持移動(dòng)端穩(wěn)定、快速地獲取查詢結(jié)果，基于2.2節(jié)內(nèi)容搭建了HTTP服務(wù)進(jìn)行實(shí)驗(yàn)驗(yàn)證，以JSON作為移動(dòng)端與服務(wù)端的數(shù)據(jù)交換格式。

圖9 本文方法、KD樹與八叉樹索引空間查詢穩(wěn)定性對(duì)比Fig.9 Query stability of the integrated spatial index，KD-tree and Octree

實(shí)驗(yàn)結(jié)果如下：基于KD樹索引與八叉樹索引構(gòu)建的數(shù)據(jù)服務(wù)，在將結(jié)果集重組織為JSON格式時(shí)均耗時(shí)過(guò)長(zhǎng)，導(dǎo)致移動(dòng)端數(shù)據(jù)請(qǐng)求發(fā)生錯(cuò)誤?；诒疚募尚退饕臄?shù)據(jù)服務(wù)，移動(dòng)端可在服務(wù)端DKD-tree查詢返回的編碼集合基礎(chǔ)上，使用多線程方式進(jìn)一步向數(shù)據(jù)服務(wù)端的LLOctree請(qǐng)求具體的點(diǎn)云數(shù)據(jù)，在以上多線程請(qǐng)求與LLOctree端LOD模型的保障下，移動(dòng)端以100%的成功率獲取數(shù)據(jù)服務(wù)端的全部結(jié)果集。

導(dǎo)致以上結(jié)果的原因如下：

（1）基于KD樹與八叉樹搭建的數(shù)據(jù)服務(wù)不支持移動(dòng)端的多線程查詢操作，只能將查詢結(jié)果一次性提供給移動(dòng)端，但查詢結(jié)果的數(shù)據(jù)量對(duì)數(shù)據(jù)服務(wù)器造成壓力，導(dǎo)致重組織耗時(shí)過(guò)長(zhǎng)。

（2）基于KD樹與八叉樹搭建的數(shù)據(jù)服務(wù)不支持點(diǎn)云數(shù)據(jù)的空間關(guān)聯(lián)性判斷，因此無(wú)法實(shí)現(xiàn)對(duì)結(jié)果集的規(guī)則性劃分。如果移動(dòng)端與服務(wù)端配合實(shí)現(xiàn)查詢結(jié)果的分段獲取，那么服務(wù)端必須對(duì)每次分段請(qǐng)求執(zhí)行查詢操作，顯然會(huì)造成服務(wù)端計(jì)算資源與時(shí)間資源的巨大浪費(fèi)，使移動(dòng)端應(yīng)用困難。該方法不具可操作性。如果由服務(wù)端緩存每次查詢結(jié)果，供移動(dòng)端分段請(qǐng)求，那么，在移動(dòng)端設(shè)備較多的情況下，會(huì)很快消耗完服務(wù)端的內(nèi)存資源，造成服務(wù)崩潰。

圖10為基于該DKD-tree與LLOctree數(shù)據(jù)服務(wù)在移動(dòng)端實(shí)現(xiàn)的點(diǎn)云場(chǎng)景可視化效果圖，圖11為某視點(diǎn)下的LOD可視化效果圖。

3 結(jié) 語(yǔ)

點(diǎn)云技術(shù)的發(fā)展和應(yīng)用的推廣，所產(chǎn)生的點(diǎn)云數(shù)據(jù)量和復(fù)雜度隨之增大，如何高效實(shí)現(xiàn)對(duì)大規(guī)模點(diǎn)云數(shù)據(jù)的組織與管理，為移動(dòng)GIS下的點(diǎn)云可視化應(yīng)用平臺(tái)提供可靠、高效的數(shù)據(jù)支持，是三維GIS發(fā)展過(guò)程中面臨的難題之一。

圖10 移動(dòng)端點(diǎn)云場(chǎng)景可視化效果圖Fig.10 Visualization of point clouds on mobile

圖11 移動(dòng)端點(diǎn)云多細(xì)節(jié)層次描述的效果圖Fig.11 LOD representation of point clouds on mobile

本文提出了一種面向移動(dòng)點(diǎn)云在線可視化應(yīng)用的DKD-tree&LLOctree集成型索引方法。首先，使用考慮了移動(dòng)終端網(wǎng)絡(luò)帶寬與計(jì)算渲染能力雙重特性的滿二叉樹DKD-tree，完成原始點(diǎn)云的均衡劃分與重組織，其次，完成對(duì)每個(gè)點(diǎn)云數(shù)據(jù)塊的LOD模型構(gòu)建，然后，使用LLOctree實(shí)現(xiàn)對(duì)點(diǎn)云LOD模型的存儲(chǔ)與管理，最后，通過(guò)DKD-tree的葉結(jié)點(diǎn)編碼連接LLOctree的內(nèi)層組織，形成最終的索引結(jié)構(gòu)。該方法能為移動(dòng)端提供基于LOD的高效率渲染方案，同時(shí)支持服務(wù)端或移動(dòng)端從數(shù)據(jù)塊層面完成點(diǎn)云數(shù)據(jù)的空間關(guān)系判斷，支持移動(dòng)端對(duì)數(shù)據(jù)的多線程查詢以及對(duì)數(shù)據(jù)請(qǐng)求的動(dòng)態(tài)合并。實(shí)驗(yàn)與分析證明，與傳統(tǒng)點(diǎn)云數(shù)據(jù)索引相比，本文方法構(gòu)建效率穩(wěn)定、空間查詢性能優(yōu)秀，同時(shí)可提高移動(dòng)端點(diǎn)云在線可視化應(yīng)用的效率，提供可靠的數(shù)據(jù)支持，具有較好的實(shí)用性與可擴(kuò)展性。

如何提取點(diǎn)云數(shù)據(jù)中的對(duì)象，以及以對(duì)象為單位進(jìn)行點(diǎn)云數(shù)據(jù)的組織與管理，將是下一步需要解決的問(wèn)題。