魯 強，席鵬翰*，朱俊誠，王智廣，劉 鑫

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

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

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

1 海量地表離散點的處理

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

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

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

2 嵌套四叉樹

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

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

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

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

圖1中表示的三維點在空間的分布形態(tài)不規(guī)則，可為直線狀、曲線狀或環(huán)狀等，所以單純的以x軸坐標值或y軸坐標值作為查詢基準不能實現(xiàn)點的精確檢索，若同時用x、y坐標值進行查詢則會造成空間的浪費.由于每根線上點的編號唯一，且按遞增的規(guī)則從第0個點開始一直計數(shù)至最后一個點，故可將點的編號作為檢索基準，進行區(qū)間劃分，實現(xiàn)索引結(jié)構(gòu).區(qū)間劃分的過程與建立區(qū)間樹類似，通常在建立區(qū)間樹結(jié)點時，對所有區(qū)間按照左端點(或者右端點)進行排序，然后逐層確定單元邊數(shù)目的中位數(shù)，將該位置的值作為各級結(jié)點的關(guān)鍵字[6].為了更好的適應(yīng)點數(shù)據(jù)特征，記錄每個區(qū)間中第一個點的編號及該區(qū)間中點的個數(shù).在進行三維點查詢時，需要先確定這個點所在的線.由于同一種類型各線的編號都不一樣，所以可通過兩個map結(jié)構(gòu)分別將對這兩類線的索引進行組織，map的key為線的編號，value為這根線的索引記錄PointLineIndex.在建立線的索引數(shù)據(jù)時，通過兩個不同的文件流同時將點的坐標值和索引數(shù)據(jù)寫入兩個不同的文件中，三維點的坐標數(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ù)量超大時，有效地實現(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記錄了這根線上起始點的x、y軸坐標值，m_endPoint記錄了這根線上終止點的x、y軸坐標值，m_ptNumBlockVect記錄了每個區(qū)間中點的個數(shù)，m_blockStartPosVect記錄了每個區(qū)間中第一個點的編號.在這個數(shù)據(jù)結(jié)構(gòu)中，最為關(guān)鍵的是m_ptNumBlockVect和m_blockStartPosVect.因為若只記錄這根線的編號，以及起始點坐標和終止點坐標，雖然節(jié)省了一定的內(nèi)存空間，但是在查詢某一點時，仍要將整根線的數(shù)據(jù)全部讀出做比較，會造成時間和內(nèi)存空間的浪費；若將線上點編號全部記錄在索引中，雖然能夠很快的定位到某一個點，但是當整個點集的規(guī)模很大時，必定會占用很大一部分內(nèi)存.而合理的劃分塊大小，記錄每一個塊的起始點編號，通過比較待查詢點編號與各個塊的起始點編號，能夠快速定位待查詢的點所在區(qū)間塊號.這樣既節(jié)省了一定的內(nèi)存空間，又能提高查詢的效率.

當線中的點全部寫入文件后，這根線的索引數(shù)據(jù)也全部完成并寫入相應(yīng)索引文件中，同時在內(nèi)存中保存著線索引數(shù)據(jù)結(jié)構(gòu).這樣給出線的編號、類型及線上一個點的編號，實現(xià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為待查詢點.

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

2.2 基于線索引的四叉樹

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

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

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

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

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為待查詢點.

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

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

3 交互操作

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

3.1 點的交互操作

3.1.1 刪除點

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

3.1.2 插入點

當某一地形區(qū)域中的點分布稀疏，而又要準確地獲取這一地區(qū)的詳細信息，可在已有的點之間再插入多個點，根據(jù)地形數(shù)據(jù)中的z值實時計算出這些點的高程值，使之緊貼地表.可先選中當前區(qū)域中的一根線，在此線上某兩點之間插入一個點.為了保證交互的實時性，在插入點時直接計算出新插入點的坐標值及編號進行實時繪制顯示.給出插入的點，待插入線的類型及編號，插入單點的算法實現(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);

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

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

3.1.3 移動點

當?shù)匦紊铣霈F(xiàn)一些障礙物，如高樓、山峰等時，可將原先在此區(qū)域中的點移至其它區(qū)域.給出待移動點，此點所在線的編號和類型及移動的距離，移動單點的算法實現(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);

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

圖5 單點的交互操作效果圖Fig.5 Interactive operate of single point

3.2 線的交互操作

3.2.1 刪除線

當無效區(qū)域范圍很大時，可能整根線上的點都在無效區(qū)域中，此時可將這根線刪除.刪除線可以看作是刪除多個點，給出待刪除線的編號及類型，刪除單根線的算法實現(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ù)線索引讀出此線上的全部點，將每個點的x、y、z軸的坐標值更新為-99999并再次寫回數(shù)據(jù)文件中；第3步將內(nèi)存中的這根線索引記錄清除，并同步更新至外存線索引文件，重寫其中內(nèi)容；第4步則是根據(jù)線經(jīng)過四叉樹節(jié)點索引，獲取所有包含此線的節(jié)點并更新，將其中對應(yīng)的線索引記錄清除.整個過程將數(shù)據(jù)的更新與線索引、四叉樹索引的更新分開，簡潔明了，如果按照傳統(tǒng)四叉樹的方法，則需要更改最底層中包含此線的每個節(jié)點里相關(guān)點數(shù)據(jù)，過程相對復雜.圖6(a)中白色線為選中線，圖6(b)中則將選中的線刪除.

3.2.2 移動線

若線的初始位置不合適時，可選中線并將整根線移動至合適的位置.給出移動線的編號及類型，移動的距離，移動單根線的算法實現(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步先獲取線索引并更新線索引記錄中的起始點坐標、終止點坐標；第2步是根據(jù)線編號找出所有包含此線的四叉樹節(jié)點，依次更新每個節(jié)點中的數(shù)據(jù)，因為線中的點移動后，可能會超出原節(jié)點extents范圍，故根據(jù)節(jié)點中對應(yīng)的線索引獲取此節(jié)點范圍內(nèi)的點并更改坐標值，判斷是否需要更新索引數(shù)值；第3步則根據(jù)線索引按塊將線上點數(shù)據(jù)讀出，修改x、y軸坐標值，z軸上的值則在繪制顯示時實時計算；第4步為寫回更新后的點數(shù)據(jù).圖6(c)中則將選中的線向右移動了一定距離.

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

3.3 區(qū)域操作

3.3.1 區(qū)域刪除

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

3.3.2 區(qū)域移動

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

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

4 結(jié)果分析

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

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

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

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

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

5 結(jié)束語

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

由于在構(gòu)建嵌套四叉樹的過程時，為了精確計算每個節(jié)點的范圍及其包含的線和點，使得當四叉樹的高度增加時，建樹所消耗的時間會大幅度增長.未來，將進一步研究在保證數(shù)據(jù)準確性的情況下，提高構(gòu)建四叉樹的效率；同時還可以對索引數(shù)據(jù)結(jié)構(gòu)做更多的優(yōu)化，有利于增加其他類型的交互操作，實現(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.