一種基于外存的海量地表離散點(diǎn)的交互編輯算法

魯 強(qiáng)，席鵬翰*，朱俊誠，王智廣，劉 鑫

(1 中國石油大學(xué)(北京)地球物理與信息工程學(xué)院，北京 102249；2 中國石油化工股份有限公司石油勘探開發(fā)研究院，北京 100086

隨著航拍、激光掃描等三維遙測技術(shù)的日益發(fā)展，獲取的地形數(shù)據(jù)體規(guī)模也隨之增大，基于內(nèi)存的繪制顯示技術(shù)已經(jīng)不能滿足要求，因此出現(xiàn)了大量的基于外存的繪制算法，有效解決了內(nèi)存大小對海量地形數(shù)據(jù)的限制.基于外存的算法是對這些數(shù)據(jù)進(jìn)行有效地組織，建立索引機(jī)制以支持后續(xù)的數(shù)據(jù)分析、實(shí)時交互操作等.

為了獲取更多的地表信息，在地形表面上按照一定規(guī)律再以離散點(diǎn)的形式增加顯示一層數(shù)據(jù)，點(diǎn)的規(guī)模大，且分布范圍任意，可布及整個地表，也可只占地表中的一部分.此時，需要對地形數(shù)據(jù)和點(diǎn)數(shù)據(jù)同時進(jìn)行繪制顯示，并且還要能對這些點(diǎn)進(jìn)行交互操作以滿足工業(yè)要求.本文通過對增加的離散點(diǎn)數(shù)據(jù)進(jìn)行分析，定義了合適的索引數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)了與地形數(shù)據(jù)統(tǒng)一調(diào)度的算法，并在此基礎(chǔ)上實(shí)現(xiàn)交互操作，滿足了實(shí)際應(yīng)用的要求.

1 海量地表離散點(diǎn)的處理

海量點(diǎn)數(shù)據(jù)處理的關(guān)鍵就是找出點(diǎn)之間的關(guān)系，通過一定的數(shù)據(jù)組織方式建立相應(yīng)的空間索引結(jié)構(gòu)，同時存儲相關(guān)特征信息，有助于數(shù)據(jù)的查詢.常見空間索引一般為自頂向下逐級劃分的結(jié)構(gòu)，比較有代表性的包括KD樹、R樹系列、四叉樹和八叉樹等，而在這些結(jié)構(gòu)中，四叉樹在二維平面點(diǎn)數(shù)據(jù)中應(yīng)用較為廣泛，KD樹和八叉樹常用于三維點(diǎn)數(shù)據(jù)組織中.

四叉樹是由Raphael Finkel與J.L.Bentley在1974年提出來的一種樹狀數(shù)據(jù)結(jié)構(gòu)，其結(jié)構(gòu)比較簡單，當(dāng)空間數(shù)據(jù)對象分布比較均勻時，具有較高的空間數(shù)據(jù)插入和查詢效率.KD樹是一種面向k維空間點(diǎn)的二叉樹結(jié)構(gòu)，是一種較為有效的k維空間點(diǎn)數(shù)據(jù)組織結(jié)構(gòu)，在涉及高維空間查找領(lǐng)域具有自身獨(dú)特優(yōu)勢.八叉樹是由Hunter在1978年首次提出的一種數(shù)據(jù)結(jié)構(gòu)，是四叉樹在三維空間上的擴(kuò)展.Surfels和QSplat[1，2]系統(tǒng)則是在八叉樹的基礎(chǔ)上提出了基于點(diǎn)的多分辨率表示，Surfels根據(jù)固定間隔的采樣點(diǎn)構(gòu)成八叉樹，而QSplat是基于包圍球構(gòu)成八叉樹，但是這兩個系統(tǒng)都不能有效的支持動態(tài)修改.Wand等人[3]介紹了一種實(shí)現(xiàn)海量點(diǎn)交互的算法，在八叉樹非葉子節(jié)點(diǎn)中保存一個量化后的網(wǎng)格，網(wǎng)格中用一個三維坐標(biāo)點(diǎn)來表示當(dāng)前節(jié)點(diǎn)所包含的所有三維坐標(biāo)點(diǎn).為了便于交互，給網(wǎng)格中的坐標(biāo)點(diǎn)一個權(quán)值，當(dāng)有交互操作時更新權(quán)值.該系統(tǒng)使用了將近三倍于實(shí)際坐標(biāo)點(diǎn)數(shù)據(jù)大小的磁盤空間，數(shù)據(jù)多次重復(fù)，造成了很大的浪費(fèi).Claus等人通過使用一種基于嵌套八叉樹[4，5]結(jié)構(gòu)的算法，減少了內(nèi)存消耗并實(shí)現(xiàn)了海量點(diǎn)的快速渲染繪制，實(shí)現(xiàn)了點(diǎn)的添加、刪除等交互操作.但上述兩種算法中的數(shù)據(jù)結(jié)構(gòu)都不足以支持更為復(fù)雜的交互操作.根據(jù)實(shí)驗(yàn)離散點(diǎn)的特征，即所有點(diǎn)都平鋪在地形表面上，每個點(diǎn)的z軸坐標(biāo)值在繪制時通過獲取地形數(shù)據(jù)中與此點(diǎn)x、y軸坐標(biāo)值一致或者鄰近的點(diǎn)，再進(jìn)行插值計(jì)算得出，故在未使用z軸坐標(biāo)值之前，可將這樣的三維點(diǎn)集視為二維坐標(biāo)點(diǎn)集，通過四叉樹對之進(jìn)行劃分，降低了數(shù)據(jù)結(jié)構(gòu)的復(fù)雜性.點(diǎn)按作用類型又可分為兩類，且這兩類點(diǎn)分別組成多根線.以線為單位，對線上的點(diǎn)進(jìn)行操作可作為一維空間的操作，而一維空間的數(shù)據(jù)檢索可通過區(qū)間樹與二分查找算法來實(shí)現(xiàn).

綜上，借鑒嵌套數(shù)據(jù)結(jié)構(gòu)的思想，對四叉樹和區(qū)間樹做相應(yīng)的改進(jìn)，實(shí)現(xiàn)一個復(fù)合嵌套結(jié)構(gòu)對海量地表離散點(diǎn)進(jìn)行組織，形成兩級索引，有效地解決了上述問題，同時也更好地實(shí)現(xiàn)了實(shí)時繪制和交互操作.

2 嵌套四叉樹

嵌套四叉樹的數(shù)據(jù)結(jié)構(gòu)便于存儲、檢索以及實(shí)時交互操作的實(shí)現(xiàn).先將整個離散點(diǎn)集以線為單位建立索引，每根線劃分成多個塊進(jìn)行讀寫，再當(dāng)構(gòu)建四叉樹結(jié)構(gòu)時，根據(jù)節(jié)點(diǎn)區(qū)域范圍保存相關(guān)線的索引數(shù)據(jù)，不再保存當(dāng)前節(jié)點(diǎn)范圍內(nèi)所有點(diǎn)的坐標(biāo)值.下面將逐一介紹每一部分的設(shè)計(jì)與實(shí)現(xiàn).

2.1 改進(jìn)的區(qū)間樹索引

通過對實(shí)驗(yàn)三維點(diǎn)數(shù)據(jù)分析，這些點(diǎn)組成大量的三維空間線.在整個三維點(diǎn)集中查詢一個點(diǎn)可分解為查詢某一根線，再從這根線查詢這個點(diǎn).故對此三維點(diǎn)集合建立合適的線索引，既能快速地檢索到線，又能通過線的索引數(shù)據(jù)加快點(diǎn)的查詢.利用二分查找算法在一維空間中查找點(diǎn)的優(yōu)勢，對區(qū)間樹作一定的修改，實(shí)現(xiàn)所要的線索引結(jié)構(gòu)，該結(jié)構(gòu)圖如圖1所示.

圖1 線索引示意圖Fig.1 Schematic diagram of line index

圖1中表示的三維點(diǎn)在空間的分布形態(tài)不規(guī)則，可為直線狀、曲線狀或環(huán)狀等，所以單純的以x軸坐標(biāo)值或y軸坐標(biāo)值作為查詢基準(zhǔn)不能實(shí)現(xiàn)點(diǎn)的精確檢索，若同時用x、y坐標(biāo)值進(jìn)行查詢則會造成空間的浪費(fèi).由于每根線上點(diǎn)的編號唯一，且按遞增的規(guī)則從第0個點(diǎn)開始一直計(jì)數(shù)至最后一個點(diǎn)，故可將點(diǎn)的編號作為檢索基準(zhǔn)，進(jìn)行區(qū)間劃分，實(shí)現(xiàn)索引結(jié)構(gòu).區(qū)間劃分的過程與建立區(qū)間樹類似，通常在建立區(qū)間樹結(jié)點(diǎn)時，對所有區(qū)間按照左端點(diǎn)(或者右端點(diǎn))進(jìn)行排序，然后逐層確定單元邊數(shù)目的中位數(shù)，將該位置的值作為各級結(jié)點(diǎn)的關(guān)鍵字[6].為了更好的適應(yīng)點(diǎn)數(shù)據(jù)特征，記錄每個區(qū)間中第一個點(diǎn)的編號及該區(qū)間中點(diǎn)的個數(shù).在進(jìn)行三維點(diǎn)查詢時，需要先確定這個點(diǎn)所在的線.由于同一種類型各線的編號都不一樣，所以可通過兩個map結(jié)構(gòu)分別將對這兩類線的索引進(jìn)行組織，map的key為線的編號，value為這根線的索引記錄PointLineIndex.在建立線的索引數(shù)據(jù)時，通過兩個不同的文件流同時將點(diǎn)的坐標(biāo)值和索引數(shù)據(jù)寫入兩個不同的文件中，三維點(diǎn)的坐標(biāo)數(shù)值按照x、y、z軸的順序依次寫入，且此時z值為0，索引數(shù)據(jù)按照map結(jié)構(gòu)一一對應(yīng)寫入文件.同時在內(nèi)存中也保存了這個map結(jié)構(gòu)，使內(nèi)外存結(jié)構(gòu)相一致，以便在數(shù)據(jù)量超大時，有效地實(shí)現(xiàn)內(nèi)外存數(shù)據(jù)的讀寫，用來建立瓦片四叉樹.

圖2 線索引數(shù)據(jù)結(jié)構(gòu)Fig.2 Data structure of line index

線索引的數(shù)據(jù)結(jié)構(gòu)定義如圖2所示，其中isHLine用于區(qū)分線的類型，m_lineID為線的編號，m_lineOffset為這根線在數(shù)值文件中開始記錄的偏移位置，m_lineBlockNum是這根線分成的區(qū)間個數(shù)，m_startPoint記錄了這根線上起始點(diǎn)的x、y軸坐標(biāo)值，m_endPoint記錄了這根線上終止點(diǎn)的x、y軸坐標(biāo)值，m_ptNumBlockVect記錄了每個區(qū)間中點(diǎn)的個數(shù)，m_blockStartPosVect記錄了每個區(qū)間中第一個點(diǎn)的編號.在這個數(shù)據(jù)結(jié)構(gòu)中，最為關(guān)鍵的是m_ptNumBlockVect和m_blockStartPosVect.因?yàn)槿糁挥涗涍@根線的編號，以及起始點(diǎn)坐標(biāo)和終止點(diǎn)坐標(biāo)，雖然節(jié)省了一定的內(nèi)存空間，但是在查詢某一點(diǎn)時，仍要將整根線的數(shù)據(jù)全部讀出做比較，會造成時間和內(nèi)存空間的浪費(fèi)；若將線上點(diǎn)編號全部記錄在索引中，雖然能夠很快的定位到某一個點(diǎn)，但是當(dāng)整個點(diǎn)集的規(guī)模很大時，必定會占用很大一部分內(nèi)存.而合理的劃分塊大小，記錄每一個塊的起始點(diǎn)編號，通過比較待查詢點(diǎn)編號與各個塊的起始點(diǎn)編號，能夠快速定位待查詢的點(diǎn)所在區(qū)間塊號.這樣既節(jié)省了一定的內(nèi)存空間，又能提高查詢的效率.

當(dāng)線中的點(diǎn)全部寫入文件后，這根線的索引數(shù)據(jù)也全部完成并寫入相應(yīng)索引文件中，同時在內(nèi)存中保存著線索引數(shù)據(jù)結(jié)構(gòu).這樣給出線的編號、類型及線上一個點(diǎn)的編號，實(shí)現(xiàn)在點(diǎn)集中檢索點(diǎn)的算法如下：

Algorithm: Find_The_Point_In_Line()

Input:LineID = lid, bool isHLine = true, PointID = pid;

1) PointLineIndex plidx = GetPLIdxByLineID(true, lid);

2) int m = binarySearch(pid, plidx.m_blockStartPosVect);

3) std::vector*Ps = readBlocks(m, m, plidx);

4) Point p = FindSP(Ps, pid);

Output: p，p為待查詢點(diǎn).

由此算法可知，第一步根據(jù)線的類型和編號，通過鍵值映射直接獲取索引，第二步由索引中每個區(qū)間塊首點(diǎn)編號與待查點(diǎn)的編號，使用二分查找算法來確定區(qū)間塊號，第三步是根據(jù)確定的區(qū)間塊號讀出個區(qū)間塊中的數(shù)據(jù)，最后再通過二分查找算法在這個區(qū)間塊中找出該點(diǎn).由于每根線上點(diǎn)的個數(shù)都不一定相同，在生成線索引時會使線索引記錄長度不一致.為了更好的解析線索引記錄，對每根線索引再建立了一個索引，記錄此線索引的線編號，索引記錄在索引文件中的起始偏移及索引長度.

2.2 基于線索引的四叉樹

在建立四叉樹時，根據(jù)離散點(diǎn)集的x、y軸方向上的平面范圍及欲建立的四叉樹層數(shù)，自頂向下進(jìn)行規(guī)則劃分.以一個四叉樹節(jié)點(diǎn)為例，節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)中包含多個屬性值.可以通過當(dāng)前節(jié)點(diǎn)的編號先計(jì)算出占據(jù)的二維平面范圍.為了保證每個節(jié)點(diǎn)中數(shù)據(jù)的準(zhǔn)確性，需要通過遍歷每一根線上的點(diǎn)，確定出當(dāng)前節(jié)點(diǎn)范圍包含了哪些點(diǎn)數(shù)據(jù).遍歷時，記錄所包含的線編號，以及每根線在這個節(jié)點(diǎn)平面范圍內(nèi)經(jīng)過的第一個點(diǎn)和最后一個點(diǎn)，根據(jù)這兩個點(diǎn)的編號通過線索引確定當(dāng)前節(jié)點(diǎn)范圍包含的區(qū)間塊號，圖3為四叉樹索引與線索引的關(guān)系圖.這樣建立起的四叉樹索引中，每個節(jié)點(diǎn)都保存了所包含線的區(qū)間塊編號和點(diǎn)的編號.四叉樹節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)定義如圖4所示，其中m_tID為四叉樹節(jié)點(diǎn)的編號，extents[4]記錄當(dāng)前節(jié)點(diǎn)的x、y軸平面的最大、最小值，ptsNum為此節(jié)點(diǎn)范圍內(nèi)包含的點(diǎn)的總個數(shù)，sample是顯示當(dāng)前節(jié)點(diǎn)時要用的采樣間隔，hlNum為此節(jié)點(diǎn)包含的第一類線的個數(shù)，hlidx為此節(jié)點(diǎn)中包含第一類線的每個線索引記錄，每根線的索引記錄包含了這根線的編號，這根線在此節(jié)點(diǎn)范圍內(nèi)的起始點(diǎn)編號、終止點(diǎn)編號以及這兩個點(diǎn)所在的區(qū)間塊號，vlNum與vlidx表示為第二類線的個數(shù)及索引.

圖3 四叉樹與線索引關(guān)系圖Fig.3 Schematic of quad-tree and line index

圖4 四叉樹節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)Fig.4 Data structure of quad-tree node

當(dāng)整個四叉樹建好之后，查詢整個點(diǎn)集中的一個點(diǎn)可縮小至查詢某個節(jié)點(diǎn)范圍內(nèi)的一個點(diǎn).這樣給出一個節(jié)點(diǎn)的編號，以及選中的線編號及類型和待查詢點(diǎn)編號，查詢算法如下：

Algorithm: Find_The_Point_In_Tile()

Input:Tile_ID = tid, LineID = lid, bool isHLine = true,PointID = pid;

1) TileIndex tidx = GetTileIdxByID(tid);

2) if(isHLine == true)

int m = GetBlockNum(tidx.hlidx[lid], pid)

3) std::vector* Ps = readBlocks(m, m, plidx);

4) Point p = FindSP(Ps, pid);

Output: p，p為待查詢點(diǎn).

由這個查詢算法可知，通過節(jié)點(diǎn)編號獲取該節(jié)點(diǎn)的索引數(shù)據(jù)，再由線的編號在此節(jié)點(diǎn)索引中找出相應(yīng)的線索引數(shù)據(jù).因?yàn)楣?jié)點(diǎn)中的線索引已經(jīng)縮小了范圍，越是底層節(jié)點(diǎn)，該范圍就越小，從而減小了查詢的難度.最后在確定的區(qū)間范圍里，通過二分查找算法獲取該查詢點(diǎn)數(shù)值.

由于常用地形數(shù)據(jù)集的大小遠(yuǎn)遠(yuǎn)超出了內(nèi)存大小，通過四叉樹對之進(jìn)行組織處理，使視域范圍內(nèi)的地形塊根據(jù)視點(diǎn)移動產(chǎn)生的視距變化而不斷更新.而地表上的離散點(diǎn)經(jīng)過四叉樹的劃分后，每個節(jié)點(diǎn)可根據(jù)自身的extents范圍值求出相應(yīng)的最近、最遠(yuǎn)可視距離，此可視距離與地形數(shù)據(jù)集的可視距離相匹配，實(shí)現(xiàn)兩者的統(tǒng)一調(diào)度.為了更好地實(shí)現(xiàn)交互操作，在建立四叉樹索引時記錄了每根線所經(jīng)過的全部四叉樹節(jié)點(diǎn)，將之作為一個單獨(dú)的索引結(jié)構(gòu)寫入文件，同時在內(nèi)存中構(gòu)造與之相對應(yīng)的數(shù)據(jù)結(jié)構(gòu).當(dāng)出現(xiàn)刪除一根線的交互操作時，可直接通過待刪除線的編號直接查找出全部與之相關(guān)的四叉樹節(jié)點(diǎn)，再依次更新這些節(jié)點(diǎn)中的線索引，若沒有這樣的數(shù)據(jù)結(jié)構(gòu)，則需要一一遍歷每個四叉樹節(jié)點(diǎn)，查詢節(jié)點(diǎn)中是否包含這根線，浪費(fèi)大量的內(nèi)存空間和時間.

3 交互操作

滿足顯示要求后，可對離散點(diǎn)數(shù)據(jù)進(jìn)行交互操作.交互操作按操作的對象可分為點(diǎn)、線、區(qū)域這三類，按操作的類別可分為選中、刪除、添加、移動這四種.下面則按操作的對象依次分析各操作的流程.

3.1 點(diǎn)的交互操作

3.1.1 刪除點(diǎn)

由于地形數(shù)據(jù)的范圍很大，會出現(xiàn)一些無效區(qū)域，如河流、峽谷等，分布在這些區(qū)域中的點(diǎn)則為無效點(diǎn).將這些無效點(diǎn)刪除時，將點(diǎn)的x、y、z軸的坐標(biāo)值都更改為-99999，當(dāng)再次讀取到這些點(diǎn)時，可根據(jù)坐標(biāo)值判斷而過濾掉這些點(diǎn)，使之不再繪制顯示出來.這個方法不需要更改線索引和四叉樹節(jié)點(diǎn)索引，降低了操作的復(fù)雜度，節(jié)省了時間和內(nèi)存空間.圖5(a)為單點(diǎn)刪除的效果圖，黃色矩形框中原本為五個藍(lán)色點(diǎn)，從左往右刪除了第二個藍(lán)色點(diǎn).

3.1.2 插入點(diǎn)

當(dāng)某一地形區(qū)域中的點(diǎn)分布稀疏，而又要準(zhǔn)確地獲取這一地區(qū)的詳細(xì)信息，可在已有的點(diǎn)之間再插入多個點(diǎn)，根據(jù)地形數(shù)據(jù)中的z值實(shí)時計(jì)算出這些點(diǎn)的高程值，使之緊貼地表.可先選中當(dāng)前區(qū)域中的一根線，在此線上某兩點(diǎn)之間插入一個點(diǎn).為了保證交互的實(shí)時性，在插入點(diǎn)時直接計(jì)算出新插入點(diǎn)的坐標(biāo)值及編號進(jìn)行實(shí)時繪制顯示.給出插入的點(diǎn)，待插入線的類型及編號，插入單點(diǎn)的算法實(shí)現(xiàn)如下：

Algorithm: Insert_Single_Point()

Input: Point sp, LineID = lid, isHLine = true;

1) PointLineIndex plidx = GetPLIdxByLineID(true, lid);

2) int m = binarySearch(sp.pid, plidx.m_blockStartPosVect);

updateLineidx(lineid);

3) std::vector tiles = getTiles(lineid);

for(inti=0; i

if(tiles(i).extents.isContain(sp.xy()))

updateTileIndex(tiles(i));

4) std::vector* Ps = readBlocks(m, m, plidx);

Ps.insert(sp);

5) writeBlocks(lineid, m, m, Ps);

由插入點(diǎn)算法可知，第1步找出該線的索引數(shù)據(jù)；第2步確定待插入點(diǎn)所在區(qū)間塊號并更新此區(qū)間塊中點(diǎn)的個數(shù)；第3步通過線經(jīng)過四叉樹節(jié)點(diǎn)的索引找出所在線對應(yīng)的全部節(jié)點(diǎn)，判斷每個節(jié)點(diǎn)的extents范圍是否包含新插入的點(diǎn)，若包含這個點(diǎn)則需要更新節(jié)點(diǎn)的ptsNum值，若不包含則無需更新；第4步則是讀出此線該區(qū)間里的全部數(shù)據(jù)，并將新加點(diǎn)按照編號插入其中；第5步則將更新后的區(qū)間點(diǎn)數(shù)據(jù)重新寫回?cái)?shù)據(jù)文件中.圖5(b)為插入單點(diǎn)的效果圖，黃色矩形框中有一白色點(diǎn)為選中點(diǎn)，在其右下方為新插入的紅色點(diǎn).

在首次寫入三維點(diǎn)集數(shù)據(jù)時，每一個數(shù)據(jù)塊分成相等的兩部分，一部分為區(qū)間塊中的點(diǎn)坐標(biāo)值，另一部分為空白區(qū)域，所以一個區(qū)間中可最多插入與區(qū)間點(diǎn)數(shù)同樣多的點(diǎn)，且readBlocks()與writeBlocks()函數(shù)都是以數(shù)據(jù)塊為最小單元實(shí)現(xiàn)讀寫.由于索引與數(shù)據(jù)的更新實(shí)現(xiàn)分離，有利于場景實(shí)時繪制.當(dāng)有多次相同交互操作時，通過后臺線程先實(shí)時更新索引，滿足一定交互次數(shù)后，再將更新后的數(shù)據(jù)寫回文件.

3.1.3 移動點(diǎn)

當(dāng)?shù)匦紊铣霈F(xiàn)一些障礙物，如高樓、山峰等時，可將原先在此區(qū)域中的點(diǎn)移至其它區(qū)域.給出待移動點(diǎn)，此點(diǎn)所在線的編號和類型及移動的距離，移動單點(diǎn)的算法實(shí)現(xiàn)如下：

Algorithm: Move_Single_Point()

Input: Point sp, int offset, LineID = lineid, isHLine = true;

1) Point nsp;

nsp += offset;

2) tileID = CaculateTID(sp)

3) for(int l=tileID.level; l>=0; l--)

ptileID = getParent(l);

if(Tile[ptileID].extents.isContain(nsp)==false)

updateTileIndex(Tile[ptileID]);

4) PointLineIndex plidx = GetPLIdxByLineID(true, lid);

int m = binarySearch(sp.pid, Lidx.m_blockStartPosVect);

5) std::vector* Ps = readBlocks(m, m, plidx);

if(Ps[j] = sp.ID)

Ps[j] = nsp;

6) wrtieBlocks(lineid, m, m, Ps);

由移動點(diǎn)算法可知，第1步創(chuàng)建一個點(diǎn)的新實(shí)例對象，將移動后的新坐標(biāo)值賦值給新的點(diǎn)對象；第2步根據(jù)原坐標(biāo)值確定其屬于四叉樹最底層的哪個節(jié)點(diǎn)；第3步由最底層節(jié)點(diǎn)開始，向上依次找出四叉樹每一層中最底層節(jié)點(diǎn)的父節(jié)點(diǎn)，并判斷父節(jié)點(diǎn)是否包含移動后的點(diǎn)，如果包含則無需修改該節(jié)點(diǎn)的索引，如果不包含則需要更新該節(jié)點(diǎn)的索引，主要為更新該節(jié)點(diǎn)的extents范圍值；第4～6步則是將移動后的點(diǎn)坐標(biāo)值重新寫入文件.整個過程只更新相應(yīng)四叉樹節(jié)點(diǎn)索引，降低了難度.當(dāng)有多次移動點(diǎn)的操作時，也可先更新內(nèi)存中的四叉樹節(jié)點(diǎn)索引，最后再將更改后的坐標(biāo)數(shù)值全部寫入數(shù)據(jù)文件中.圖5(c)為移動單點(diǎn)的效果圖，黃色矩形框中本為5個在一條直線上的藍(lán)色點(diǎn)，從左往右將第二個藍(lán)色點(diǎn)移動至左上方.

圖5 單點(diǎn)的交互操作效果圖Fig.5 Interactive operate of single point

3.2 線的交互操作

3.2.1 刪除線

當(dāng)無效區(qū)域范圍很大時，可能整根線上的點(diǎn)都在無效區(qū)域中，此時可將這根線刪除.刪除線可以看作是刪除多個點(diǎn)，給出待刪除線的編號及類型，刪除單根線的算法實(shí)現(xiàn)如下：

Algorithm: Delete_Single_Line()

Input: LineID = lineid, isHLine = true;

1) PointLineIndex plidx = GetPLIdxByLineID(true, lid);

2) std::vector* Ps = readBlocks(0, plidx.blockNum-1, plidx);

for(int j=0; j

Ps[j]= -99999;

writeBlocks(lineid,0, Lidx.blockNum-1,Ps);

3) updateLineIndex(Lidx);

4) std::vector tids = getIDsByLine(lineid);

for(int i=0; i

updateTileIndex(tids[i]);

由刪除線的算法可知，第1步根據(jù)線的編號檢索出對應(yīng)的線索引；第2步則根據(jù)線索引讀出此線上的全部點(diǎn)，將每個點(diǎn)的x、y、z軸的坐標(biāo)值更新為-99999并再次寫回?cái)?shù)據(jù)文件中；第3步將內(nèi)存中的這根線索引記錄清除，并同步更新至外存線索引文件，重寫其中內(nèi)容；第4步則是根據(jù)線經(jīng)過四叉樹節(jié)點(diǎn)索引，獲取所有包含此線的節(jié)點(diǎn)并更新，將其中對應(yīng)的線索引記錄清除.整個過程將數(shù)據(jù)的更新與線索引、四叉樹索引的更新分開，簡潔明了，如果按照傳統(tǒng)四叉樹的方法，則需要更改最底層中包含此線的每個節(jié)點(diǎn)里相關(guān)點(diǎn)數(shù)據(jù)，過程相對復(fù)雜.圖6(a)中白色線為選中線，圖6(b)中則將選中的線刪除.

3.2.2 移動線

若線的初始位置不合適時，可選中線并將整根線移動至合適的位置.給出移動線的編號及類型，移動的距離，移動單根線的算法實(shí)現(xiàn)如下：

Algorithm: Move_Single_Line()

Input: LineID = lineid, isHLine = true, int offset;

1) PointLineIndex plidx = GetPLIdxByLineID(true, lid);

updateLineIndex(Lidx);

2) std::vector tids = getIDsByLine(lineid);

for(int i=0; i

updateTileIndex(tids[i]);

3) std::vector* Ps = readBlocks(0, Lidx.blockNum-1, Lidx);

for(int j=0; j

Ps[j] += offset;

4) writeBlocks(lineid,0, Lidx.blockNum-1, Ps);

由算法流程可知，第1步先獲取線索引并更新線索引記錄中的起始點(diǎn)坐標(biāo)、終止點(diǎn)坐標(biāo)；第2步是根據(jù)線編號找出所有包含此線的四叉樹節(jié)點(diǎn)，依次更新每個節(jié)點(diǎn)中的數(shù)據(jù)，因?yàn)榫€中的點(diǎn)移動后，可能會超出原節(jié)點(diǎn)extents范圍，故根據(jù)節(jié)點(diǎn)中對應(yīng)的線索引獲取此節(jié)點(diǎn)范圍內(nèi)的點(diǎn)并更改坐標(biāo)值，判斷是否需要更新索引數(shù)值；第3步則根據(jù)線索引按塊將線上點(diǎn)數(shù)據(jù)讀出，修改x、y軸坐標(biāo)值，z軸上的值則在繪制顯示時實(shí)時計(jì)算；第4步為寫回更新后的點(diǎn)數(shù)據(jù).圖6(c)中則將選中的線向右移動了一定距離.

圖6 線的交互操作效果圖Fig.6 Interactive operate of single line

3.3 區(qū)域操作

3.3.1 區(qū)域刪除

選中一片區(qū)域內(nèi)的點(diǎn)，刪除區(qū)域點(diǎn)操作分解為多次刪除單點(diǎn).將這些點(diǎn)的坐標(biāo)數(shù)值更改為-99999，作為無效點(diǎn)，無需改變?nèi)魏嗡饕龜?shù)據(jù).圖7(a)為選中區(qū)域點(diǎn)圖，白色為選中點(diǎn)；圖7(b)為刪除區(qū)域點(diǎn)圖.

3.3.2 區(qū)域移動

選中一片區(qū)域內(nèi)的點(diǎn)，拖拽移動至任意位置，實(shí)時更新這些點(diǎn)的坐標(biāo)數(shù)據(jù).采取的算法策略是將這片區(qū)域點(diǎn)分解成每一個點(diǎn)的移動操作，更新內(nèi)存索引數(shù)據(jù)后將新的坐標(biāo)數(shù)據(jù)寫回文件.圖7(c)為移動區(qū)域點(diǎn)圖.

圖7 區(qū)域點(diǎn)交互操作圖Fig.7 Interactive operate of area points

4 結(jié)果分析

對本文提出的算法加以實(shí)現(xiàn)，應(yīng)用于地震勘探中三維地形與三維觀測系統(tǒng)，實(shí)現(xiàn)了快速瀏覽顯示和實(shí)時交互.測試平臺為DELL PrecisionT3500，CPU Intel(R) Xeon(R)W3503，內(nèi)存6.00G，硬盤ST31000524AS 1TB 7200r/s，顯卡NVIDIA Quadro600，Windows7 64位系統(tǒng).測試中生成兩組實(shí)驗(yàn)數(shù)據(jù)，如表1所示.

表1 驗(yàn)數(shù)據(jù)屬性表Tab.1 The attribute of experimental data

由表1中兩組數(shù)據(jù)可見，第一組中生成了約30萬個點(diǎn)，建立6層的四叉樹；第二組中生成了約134萬個點(diǎn)，建立8層四叉樹.每一組數(shù)據(jù)都生成6個二進(jìn)制文件，其中炮檢點(diǎn)數(shù)據(jù)文件僅保存點(diǎn)的三維坐標(biāo)信息，第二組此文件大小約為第一組的4倍，這與點(diǎn)數(shù)之間的倍數(shù)一致；線索引文件記錄了線的索引信息，第二組的此文件大小也是第一組此文件大小的4倍；線索引的索引文件記錄了每一根線的編號、在線索引文件中的起始位置和偏移長度，故每根線在此文件中的記錄長度相同，通過對線索引文件再做一個索引后，再次讀取線索引文件時就能更快的解析其中的內(nèi)容；四叉樹索引文件是記錄了每一個節(jié)點(diǎn)中的信息，第二組中的此文件比第一組的大很多，因?yàn)楫?dāng)四叉樹層數(shù)增加時，節(jié)點(diǎn)個數(shù)是呈幾何級數(shù)增長；四叉樹索引的索引文件是只記錄了每一個節(jié)點(diǎn)的編號、在四叉樹索引文件中的起始位置和偏移長度，故每個節(jié)點(diǎn)在此文件中的記錄長度一致，其作用與線索引的索引文件一樣，為了更快的解析四叉樹索引文件；線經(jīng)過節(jié)點(diǎn)索引為四叉樹索引的一個逆向索引，因?yàn)樗牟鏄涔?jié)點(diǎn)索引結(jié)構(gòu)中保存了該節(jié)點(diǎn)包含的線記錄，此索引則記錄每根線所經(jīng)過四叉樹節(jié)點(diǎn)，更有利于交互操作的實(shí)現(xiàn).第一組數(shù)據(jù)生成這6個文件用時3288ms，第二組數(shù)據(jù)用時307859ms，時間增長幅度較大.因?yàn)槲闹袨榱耸姑總€節(jié)點(diǎn)都能獲取準(zhǔn)確的數(shù)據(jù)信息，每個節(jié)點(diǎn)索引都遍歷一次全局點(diǎn)數(shù)據(jù)的方法，故四叉樹層數(shù)越高，節(jié)點(diǎn)數(shù)越多，從而花費(fèi)的時間也就越長.再分別對上面兩組數(shù)據(jù)進(jìn)行相關(guān)的交互操作，并記錄交互操作所用的時間，數(shù)據(jù)如表2所示.

表2 交互操作用時表Tab.2 Time of the interactive operate

由表2中數(shù)據(jù)可知，當(dāng)點(diǎn)的規(guī)模大幅度增加時，不同類型的交互操作所用時間并未出現(xiàn)明顯增加，表明了文中提出的數(shù)據(jù)結(jié)構(gòu)在交互操作中保持了良好的穩(wěn)定性，不會因數(shù)據(jù)量的增長而降低交互操作的實(shí)時性，可見嵌套四叉樹的三維觀測數(shù)據(jù)組織策略有效提高了炮檢點(diǎn)渲染的實(shí)時性，而且為整個系統(tǒng)節(jié)約了大量的資源用于處理其它事務(wù).

5 結(jié)束語

本文對基于外存海量地表離散點(diǎn)的交互操作算法進(jìn)行了深入的論述，在區(qū)間樹、四叉樹索引的基礎(chǔ)上提出了一種新的數(shù)據(jù)結(jié)構(gòu)，即二者相結(jié)合的嵌套四叉樹.該數(shù)據(jù)結(jié)構(gòu)有效地解決了外存數(shù)據(jù)的快速存取、實(shí)時繪制以及實(shí)時修改難以同時實(shí)現(xiàn)的問題，尤其在進(jìn)行交互操作時，通過先對內(nèi)存索引和數(shù)據(jù)進(jìn)行實(shí)時更新，再根據(jù)一定的策略更新外存數(shù)據(jù)，在不影響用戶體驗(yàn)的情況下，大大簡化了數(shù)據(jù)的計(jì)算流程.最后將該算法應(yīng)用于地震三維觀測系統(tǒng)平臺，對算法進(jìn)行了有效地檢驗(yàn)，證明了算法的可行性.

由于在構(gòu)建嵌套四叉樹的過程時，為了精確計(jì)算每個節(jié)點(diǎn)的范圍及其包含的線和點(diǎn)，使得當(dāng)四叉樹的高度增加時，建樹所消耗的時間會大幅度增長.未來，將進(jìn)一步研究在保證數(shù)據(jù)準(zhǔn)確性的情況下，提高構(gòu)建四叉樹的效率；同時還可以對索引數(shù)據(jù)結(jié)構(gòu)做更多的優(yōu)化，有利于增加其他類型的交互操作，實(shí)現(xiàn)操作的多樣性，以滿足更多的用戶要求.

參 考 文 獻(xiàn)

[1] Pfister H, Zwicker M,Baar J V, et al. Surfels:surface elements as rendering primitives[C]//ACM SIGGRAPH. Proc SIGGRAPH′00(2000).Louisiana:ACM SIGGRAPH,2000:335-342.

[2] Rusinkiewicz S, Levoy M. Qsplat: a multi-resolution point rendering system for large meshes[C]//ACM SIGGRAPH. Proc SIGGRAPH′00(2000).Louisiana:ACM SIGGRAPH,2000:343-352.

[3] Wand M, Berner A,Bokeloh M, et al. Interactive editing of large point clouds[C]//Eurographics.Symposium on Point-Based Graphics. Prague: Eurographics Association,2007:37-45.

[4] Scheiblauer C, Wimmer M. Out-of-core selection and editing of huge point clouds[J].Computers & Graphics,2011,35:342-351.

[5] Wimmer M, Scheiblauer C. Instant points:fast readering of unprocessed point clauds[C]//Eurographics.Proceeding SPBG′06 Proceedings of 3rdEurographics.Massachusetts:Eurographics Association,2006:129-136.

[6] Kreveld M V. Efficient methods for isoline extraction from a TIN[J]. Interational Joumal of GIS,1996, 10: 523-540.