基于塊段模型的三維ＧＩＳ混合數據結構模型研究

摘要:為了有效地表示三維GIS空間實體，在地質塊段模型的基礎上，提出了基于八叉樹和四面體格網的混合數據結構模型(block octree tetrahedron，BOT模型)#65377;采用BOT模型生成算法對塊段模型進行重新分割，八叉樹作整體描述，四面體格網作局部精確描述，并以不同的灰度值表示不同的單元塊屬性#65377;同時，為節省存儲空間，提出了線性BOT編碼技術#65377;實驗結果表明，BOT模型充分發揮了八叉樹和四面體格網的優點，可以在不增加存儲空間的前提下實現對三維目標更高效#65380;更精確的表達#65377;

關鍵詞:塊段模型; 八叉樹; 四面體格網; Delaunay剖分; 混合數據結構模型

中圖分類號:TP391.9文獻標志碼:A

文章編號:1001-3695(2007)10-0273-03



隨著地理信息系統(geographic information system，GIS)理論#65380;計算機圖形學和計算機軟硬件技術的飛速發展，在二維GIS成功應用的基礎上，三維GIS也得到了廣泛而深入的研究#65377;如何高效地組織管理三維空間數據，構建三維實體模型已成為三維GIS成功應用的關鍵#65377;目前在三維GIS中，可以將三維數據模型分為兩類，即基于面表示的數據模型和基于體表示的數據模型#65377;基于面表示的數據模型主要用來表達空間對象的邊界#65377;基于體表示的數據模型用體信息代替面信息來描述空間對象，它將三維空間物體抽象為一系列鄰接但不交叉的三維體元的集合#65377;在地學領域內常用的實體模型包括塊段模型#65380;四面體格網模型和八叉樹模型等#65377;塊段模型的優點是可以采用隱含定位技術來節省存儲空間和運算時間;但在精確模擬礦體邊界與分割粒度上存在尖銳矛盾#65377;四面體格網模型能夠保存原始觀測數據，具有精確表示目標和表示較為復雜的空間拓撲關系的能力;但其結構復雜，在某些場合數據量較大#65377;八叉樹模型具有結構簡單#65380;操作方便等顯著優點;但隨著分割粒度的提高，數據量將成倍增加，而且八叉樹結構始終是一種近似表示#65377;鑒于此，本文在深入研究上述數據模型的基礎上，針對四面體格網模型和八叉樹模型的特點，提出了基于塊段模型的三維GIS混合數據結構模型(BOT模型)#65377;

1面向地質應用的塊段模型

基于八叉樹和四面體的混合數據結構是在地質塊段模型的基礎上，依據一定的準則，對三維空間對象進行重新分割所得到的#65377;塊段模型是一種傳統的地學構模技術#65377;該技術是把要建立模型的整個立方體空間分割成完備的三維立方網格(grid)集，每一個網格(又稱為塊段)對應一條記錄，如圖1所示#65377;記錄之間是空間相關的，即模型空間中任意一點(并不局限于精確測量的原始數據點)的屬性值可以通過克立格法#65380;距離加權平均法和優勢原則計算得到#65377;塊段模型原理簡單，易于實現，但在精確模擬礦體邊界與分割粒度上存在尖銳矛盾#65377;為了實現利用八叉樹和四面體格網混合數據模型對塊段模型進行重新分割，本文對上述塊段模型作以下說明:

a)模型空間，指包含模型的立方體#65377;從構建模型的角度不考慮空間之外的任何對象#65377;

b)模型約束，指空間操作符和對象的邏輯組合，可以用來控制對塊的選擇，對信息的提取或對其進行屬性值內插#65377;

c)模型區域，模型在x#65380;y#65380;z方向上所覆蓋的區域#65377;

d)塊尺寸，塊在x#65380;y#65380;z方向上的大小，塊的尺寸主要取決于建模的目的#65377;

e)模型每邊最大子塊數，該數目總是2的整數次冪#65377;例如，模型區域為Y=650，X=600，Z=150，塊尺寸為25×25×10，則模型每邊塊數將為26×24×15#65377;容易知道模型基本分辨率為32，基本分辨率大于最大塊數并且是2的某個整數次冪#65377;

2混合數據結構模型理論基礎

2.1八叉樹數據結構

八叉樹表示法是一種層次結構的占有空間計數法，它由圖像處理中的四叉樹結構向三維空間擴展而來，通過用樹結構對模型進行遞歸分割，如圖2所示#65377;

首先將實體所在空間用一個立方體來表示，如果該立方體完全被實體所占有，那么該立方體可表示為實節點;如果該立方體與實體完全不相交，則該立方體表示為空節點;如果該實體占有立方體的部分空間，則將該立方體等分為八個小立方體(圖2(a))，等分的小立方體可按一定規則進行編號(圖2(b))#65377;然后再按上述規則進行檢查，確定為實節點#65380;空節點或灰節點(具有子孫的節點)#65377;如此進行下去，直到全部小立方體均為實節點或空節點，或達到預期的分割粒度要求為止#65377;這種遞歸分割的實體表示形式，可以用八叉樹結構描述(圖2(c))#65377;

八叉樹結構的主要優點在于可以非常方便地實現有廣泛用途的集合運算(可以求兩個物體的并#65380;交#65380;差等運算)，而這些正是其他表示方法難以處理或需要耗費許多計算資源的地方#65377;此外，由于這種方法的有序性及分層性，對顯示精度和速度的平衡#65380;隱線和隱面的消除等，帶來了極大的方便#65377;

運用八叉樹結構很容易對上述塊段模型進行重新分割，實現數據高效重組#65377;按照每個塊段的屬性值(如可以是地質品位等)對塊段進行分類#65377;屬性值大于上限閾值的塊段對應于八叉樹結構中的實節點，屬性值小于下限閾值的塊段對應于八叉樹結構中的空節點，屬性值在下限閾值和上限閾值之間的塊段對應于八叉樹結構中的灰節點，該類塊段需要進行下一級分割#65377;在數據重組過程中，對于屬性值變化劇烈的區域(如地質斷層)，可以利用原始觀測數據構造四面體格網進行局部精確描述#65377;

2.2四面體格網(TEN)

四面體格網是將目標空間用緊密排列但不重疊的不規則四面體構成的格網來表示#65377;其實質是二維TIN結構在三維空間上的擴展#65377;在概念上首先將二維Voronoi格網擴展到三維Voronoi多面體，然后將TIN結構擴展到三維空間形成四面體格網#65377;四面體格網由點#65380;線#65380;面和體四類基本元素組合而成，具有精確表示目標和表示較為復雜的空間拓撲關系的能力，用四面體格網表示三維空間物體及其數據結構如圖3所示#65377;用面向對象語言描述圖3中數據結構如下:

Class Point {

Float X， Y， Z; /* X， Y and Z coordinates of a point*/

String attribute; /* attribute value of a point */};

Class Edge {

Point a; Point b; /* frompoint and topoint*/};

Class Triangle {

Edge t_edge [3]; /* three edges of a triangle*/};

Class Tetrahedron {

Triangle f_triangle[4]; /*four triangles of a tetrahedron */ 

Point circumcenter; /* circumcenter of tetrahedron */

};

在實際應用中一個關鍵的問題是如何生成四面體格網，實現對由三維離散數據點構成的指定區域的剖分#65377;本文給出了基于Delaunay剖分原理的四面體格網生成算法#65377;其特點是剖分結果符合空球準則，即每個剖分成的四面體的外接圓內不包含點集中的任意其他點#65377;這樣使得各四面體盡可能接近正三角錐，盡量避免狹長四面體的存在，而且各離散點對整個數據場的影響盡可能局部化與均勻化#65377;四面體格網生成算法思想是:在數據域中先構成第一個四面體，然后以四面體的某個面向外擴展生成新的四面體，直至全部離散點均已連成網為止#65377;具體算法描述如下:

a)在數據域中選擇最近兩個點連線，作為第一個三角形的一條邊;

b)選擇第三個點構成第一個三角形;

c)選擇第四個點構成第一個四面體;

d)i=1， j=1(i為已構成的四面體個數，j為正擴展的四面體個數);

e)擴展第j個四面體生成新的四面體0~4個;

f)i=i+k(k=0，1，2，4)， j=j+1;

g)如果i≥j則轉向e);

h)算法結束#65377;

在上述算法步驟b)中，選擇第三個點的依據是Delaunay的兩個性質:所選點與原兩點一起所構成圓的圓心到兩點連線的距離最小;所選點與原兩點連線的夾角最大#65377;在步驟c)中，選擇第四個點的依據是所選點與已產生的三角形的三個點一起所構成球面的球心到三角形所構成的面的距離最小#65377;為驗證上述算法，本文取如圖4(a)所示的三維空間數據域，三維剖分結果如圖4(b)所示#65377;

實驗表明，在三維數據點較少的情況下，算法具有較好的剖分效果;對于大數據量而言，算法的效率較低#65377;

3BOT數據結構設計與算法實現

從以上分析中易知，八叉樹數據結構簡單，易于實現實體之間的集合運算，但八叉樹只是空間實體的近似表示，而且隨著分割粒度的增加數據量將成倍增加#65377;四面體格網能夠保存原始觀測數據，具有精確表示目標和表示較為復雜的空間拓撲關系的能力，但其結構復雜，在某些場合數據量較大#65377;

BOT模型數據結構描述如下:在BOT模型中，以八叉樹結構作為對空間對象的整體描述，在結構(或屬性)復雜多變的數據域中以四面體格網結構作局部精確描述#65377;首先，利用原始觀測數據(如鉆孔數據)建立起數據場的地質塊段模型，構造原則如本文第1章所述#65377;作為中間過程，塊段模型數據并不寫入最終數據庫保存，因此在考慮建模目的的基礎上，塊尺寸一般定義為小粒度，采用距離加權平均法和優勢原則計算塊的屬性值#65377;然后，利用八叉樹結構對上述模型空間進行重新分割#65377;由于塊段模型每邊的子塊數和八叉樹每級的節點數都是2的整數次冪，數據重組時能很好地匹配#65377;對每次劃分出的八個子節點，按照節點所占區域內所有子塊數的屬性值的加權平均值確定節點的類型#65377;加權平均值大于上限閾值的節點為實節點，小于下限閾值的為空節點，介于下限閾值和上限閾值之間的為灰節點(該類節點需要進行下一級劃分)#65377;在確定節點類型的同時，計算每個節點所占區域內子塊屬性值的方差#65377;方差大于設定閾值的，表明該節點區域構造復雜，屬性值差異較大，需用四面體格網結構進行局部精確描述#65377;取該區域原始觀測數據，利用本文2.2節給出的基于Delaunay剖分原理的生成算法構造四面體格網#65377;最后對BOT模型進行編碼和屬性賦值#65377;為節省存儲空間，參照線性八叉樹編碼原理，采用線性BOT編碼技術，即只記錄實節點的地址碼#65380;屬性值和一個特殊的指針位#65377;局部四面體格網結構等同于一個實節點，由指針PT定位#65377;BOT模型節點數據結構如圖5所示#65377;

圖5中指針位PT用來引導局部TEN結構#65377;對于一般實節點，屬性值可直接復制塊段模型中對應區域子塊的屬性值，指針位為空;對由TEN結構構成的實節點，屬性值由指針PT定位的TEN結構本身給出#65377;線性BOT編碼由于省去了大量的空節點和指針位(常規編碼方法要記錄九個指針位，一個指向父節點，八個指向子節點)，有效地提高了存儲空間的利用率，降低了操作復雜性#65377;生成BOT模型的算法框圖如圖6所示#65377;

4試驗與分析

為驗證本文提出的BOT模型的有效性，在惠普圖形工作站(HP xw9300)上利用C++語言和開放圖形庫(openGL)技術對河北某礦山局部區域進行仿真試驗，建立指定區域內某種礦石分布的三維實體模型#65377;定義模型空間為150 m×150 m×150 m的立方體區域#65377;該區域內有地質勘探鉆孔和生產勘探鉆孔31個，原始數據包括鉆孔空間數據和對應的地質屬性數據#65377;為降低計算復雜度和節省模型渲染時間，本文只考慮單值屬性(該礦石地質品位)#65377;塊尺寸大小取2 m×2 m×2 m，采用距離加權平均法和優勢原則計算每一子塊的屬性值，建立數據場的地質塊段模型#65377;然后根據BOT模型生成算法對上述塊段模型進行分解#65377;遞歸分解終止條件為分割粒度小于塊尺寸或品位小于閾值#65377;最后加載模型屬性值，利用OpenGL技術，設置模型的材質屬性和表面法線向量;設置光源，計算光照條件，最終生成完整的BOT模型#65377;可視化渲染效果如圖7所示#65377;在圖7中，不同的顏色灰度值代表子塊的不同屬性，相同灰度值的子塊進行聚合#65377;在模型中存在兩個四面體結構(另一個隱含在模型內部)，這與實際中對應區域結構復雜，屬性值變化劇烈相一致，而且四面體結構保存了該區域的原始觀測數據#65377;采用線性BOT編碼技術，本文所建模型存儲量僅為對應塊段模型的67.4%，在保證模型描述精度的前提下，有效地節約了存儲空間#65377;

5結束語

三維空間數據模型是三維GIS研究的核心問題，由于在三維幾何與拓撲方面的復雜性，很難用一種數據結構描述所有三維空間對象#65377;本文在塊段模型的基礎上，運用八叉樹和四面體混合結構構造了BOT模型#65377;仿真試驗表明該模型具有以下特征:a)用子塊和四面體結構描述空間實體，易于實現實體之間的交#65380;并#65380;差等幾何運算;b)生成算法在一定程度上提高了存儲效率，并具有精確表示目標和表示較為復雜的空間拓撲關系的能力;c)采用不同的顏色灰度值表示不同的礦塊屬性，可視化效果好，便于采礦方法的設計與優化#65377;由于地質結構的復雜性，在判斷何時構造四面體結構時，條件過于單一化(本文只考慮了屬性方差)，不足之處還有待于理論和算法的進一步完善#65377;

參考文獻:

[1]DING S， MANNAN M A， POO A N. Oriented bounding box and octree based global interference detection in 5axis machining of freefrom surfaces[J]. ComputerAide Design， 2004，36:81-94.

[2]JUNG Y H， LEE K. Tetrahedronbased octree encoding for automatic mesh generation[J]. ComputerAide Design， 1993，25(3):141152.

[3]LI Qingquan， LI Deren. Algorithms for tetrahedral network(TEN) generation[J]. GeoSpatial Information Science， 2000，3:1116.

[4]李清泉，李德仁.三維空間數據模型集成的概念框架研究[J].測繪學報，1998，27(4):325-330.

[5]徐元斌，赫冀成，李寶寬，等.用八叉樹數據結構自動生成三維網格的算法設計[J].東北大學學報，1997，18(4):351-355.

[6]楊欽.限定Delaunay三角網格剖分技術[M].北京:電子工業出版社，2005:70-98.

[7]薛惠鋒，吳慧欣，解丹蕊.OpenGL圖形程序開發實務[M].西安:西北工業大學出版社，2005:134175.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”