基于截面輪廓線人機交互三維地質體建模

何 畏,吳文鸝

(中國地質科學院 地球物理地球化學勘查研究所,河北廊坊 065000)

0 前言

目前,地球物理數據解釋以二維剖面為主[1、2],而實際地質體在空間賦存為三維結構。為了深入認識地質體的構造特征,需要將二維剖面信息轉化為三維信息來完成地質體的推斷解釋,即利用連接截面輪廓線模擬實際地質體的幾何形狀[9、10],從而提高數據處理、分析,以及解釋工作的效率與準確性。

自 1993年 Simon WHoulding[5]提出三維地質建模這一概念以來,其實現方式已呈現多樣化,如基于 Delaunay四面體模型、剖面模型、三角形多面體模型等建模方式[6～8],輪廓線三維地質建模方式也應用到了地質領域。

對于眾多輪廓線建模的研究成果,由 H.Fuchs提出的“最小表面積”和 E.Kepple主張的“最大體積”連接算法[3、4]最為有名。針對以往重構表面算法的復雜、計算量大等不利因素,作者在文中提出了最優路徑 (optimalpath,OP)算法,從而實現了三角形多面體截面輪廓線三維地質體建模。

1 輪廓線建模原理

輪廓線建模的基本思想是,用一系列彼此不相交,互相不重疊的三角面片,將相鄰截面的輪廓線連接起來的方法。H.Fuchs[3]指出,只有滿足下列二個條件的三角面片集合,連接才是合理的。

(1)由于每一個輪廓線的線段必須并且只能在一個基本三角面片中出現。因此,二輪廓線連接的三維表面模型包括 m+n個基本三角形 (m、n分別為二輪廓線上節點數)。

(2)如果一個跨距在某一基本三角面中為左跨距,則該跨距是而且僅是另一基本三角面片的右跨距,如下頁圖 1(a)所示。

見下頁,圖 1(a)是位于不同平面的 P、Q二輪廓線頂點按一定規則連接形成的三維形體效果圖,圖 1(b)為輪廓線上點列連接關系有向圖。假設圖 1(a)上、下二輪廓線點列分別為 P0,P1,…,Pm-1及 Q0,Q1,…,Qn-1,則可以用一個 m行、n列的有向圖來表示點列之間的連接關系。如有向圖G(V,E)(如圖 1(b)所示 ),其中 Vij表示點 Pi與點Qj之間的跨距,Eij表示點 Pi與點 Qj之間對應的邊。

圖1 輪廓線連接和矩陣圖Fig.1 Map of contour data connection and matrix

從圖 1(b)中可以看出,一種輪廓線建模的三角形連接方式對應于從點 V00到點 Vm-1,n-1的一條路徑,因此可以滿足上述二個條件的連接表面總數等于由點 V00到 Vm-1,n-1時可能存在的路徑總數,記為A[m,n]。

由式 (1)知,代表路徑總數的 A[m,n]隨著m、n的增加而快速增加[11],然而在這些路徑中,并不是所有路徑對應的連接方式都能滿足連接要求。為了從圖 1(b)中找到合適的路徑來滿足連接要求,H.Fuchs采用最小表面積,E.Kepple主張最大體積法來搜索全局最優路徑,并取得了較為理想的連接效果。

2 OP算法設計

從理論上講,在圖 1(b)中采用窮舉搜索法,一定可以找出一條可以接受且滿足輪廓線連接要求的全局最優路徑,但當二輪廓線節點較多或多輪廓線連接時,搜索時間必然大幅增加,這勢必降低工作效率。

作者在本文提出的 OP算法,具有局部計算和決策啟發式特點,能解決上述出現的不足。該算法不要求實現全局最優,而是基于局部計算來決定當前的選擇。OP算法的“最優”主要體現以下二個方面:①二輪廓線的初始連接節點是所有跨距最短的兩節點;②在輪廓線節點矩陣圖中,由“最短對角線法則”來決定連接路徑的下一節點。具體算法描述如下:

(1)賦予圖 1(b)中節點 Nij的初值為 Vij,Vij表示點 Pi與點 Qj之間的跨距 (i=0,1,…,m-1;j=0,1,…,n-1),求出 V中的最小值 Vopti_i,opti_j,并將Vopti_i,opti_j作為新的V′00值,在P、Q輪廓線上按逆時針對節點排序,形成新的有向路徑圖 G′(由于 G和G′形式一樣,故將圖 1(b)作為新的有向路徑圖G′)和節點跨距 V′ij。該步保證了在 P、Q輪廓線上第一條連接線直線距離最短,實現局部最優。

(2)對 G′中的每個節點賦一方向屬性,對第 m-1行節點賦“向右”屬性,對第 n-1列節點賦“向下 ”屬性 ,對 V′m-1,n-1節點賦“終止 ”屬性 ,其余節點賦“向右”和“向下”屬性。

(3)根據 G′中節點 N′ij的方向屬性,獲取V ′i+1,j和 V ′i,j+1,并比較二者大小 ,將較小值對應的節點作為路徑的下一節點 (如下頁圖 2(a)所示),將 P、Q相應節點編號存入容器 V_P、V_Q中,以備后續三角形連接使用 (如下頁圖 2(b)所示)。該步遵循了“最短對角線”局部最優原則。

(4)判斷執行步驟 (3)后的新路徑節點是否為終止節點V′m-1,n-1,如果為“真”則轉至步驟(5);如果為“假”則轉向步驟 (3),根據節點的方向屬性,判斷其“向右”或“向下”節點的 V′值。重復步驟(3)～步驟(4),直至路徑終止節點V′m-1,n-1。

(5)將在上述過程中裝入容器 V_P或 V_Q中的節點編號,與下一位置中的節點編號做“相等”判斷,并根據判斷結果,選擇 PPQ或 PQQ形式形成輪廓線之間的連接三角面片,算法結束。

此外,根據 V_P和 V_Q容器形成的三角形個數比二輪廓線側面所需連接三角面片個數少二個的特點,需要在步驟 (5)的基礎上追加二個三角形。

最優路徑 (OP)算法的特點,是基于連接的二條輪廓線大小、形狀和中心距相差不遠時,會取得滿意的連接效果。但當二輪廓線不滿足其特點時,可能會造成連接失敗,如圖 3所示出現連接失敗形成二棱錐體的情況。對于這種情況,作者給出如下二種解決方案。

圖2 最短對角線連接及節點編號存儲圖Fig.2 Map of the shortest diagonal connection and storageof node number

圖3 最優算法連接失敗示意圖Fig.3 Sketch map of the failure of op timal algorithmconnection

(1)在連接失敗的二截面之間,增加一個或多個截面,使截面輪廓線中心差減小,從而滿足 OP算法的特點?；蛘呃萌藱C交互方式移動二輪廓線上的節點及邊,使二輪廓線所形成區域的形狀、面積大小盡可能的接近,使中心差減小,最終取得較好的建模效果。

(2)在構造三角面片之前,將該 P、Q輪廓線變換至以同一原點為中心的單位正方形之內,從而保證在單位正方形內二輪廓線大小和形狀相近,并使對中情況較好[12]。由于將二輪廓線變換至單位正方形內,OP算法調用以及將各輪廓線變換到原來位置的反變換所需工作量大,所以本方案有時間復雜度較大的特點。

本文的算法在 C++編程環境下,借助于 Open-GL圖形庫,編寫了基于截面輪廓線人機交互的建模程序。

圖4 截面輪廓線三維建模示意圖Fig.4 Sketch map of 3D modeling of cross - sectioncontour data

3 建模實例

圖 4為六個截面 (在從左到右方向上,第二個截面只剩下透鏡體的截面,其余地質屬性體截面已刪去)的部份輪廓線調用最優路徑 (OP)算法形成的三維地質體模型。圖 4(a)是六個截面形成的3D效果圖,每個截面由三種不同灰度的區域構成,其中某區域含有一個透鏡體截面 (在三維空間中,Z方向為垂直方向,X方向為東西方向,Y軸所在平面為水平面)。在圖 4(b)中,某透鏡體在第一截面和第六截面 (在從左到右方向上)上處于尖滅狀態,“透鏡體輪廓線連接圖”是對透鏡體截面輪廓線調用OP算法的三維建模圖,取得了較為理想的三角形連接效果,形象地模擬了透鏡體在巖層中的空間分布。

4 結束語

三維截面輪廓線人機交互建模是 3D建模的發展方向,雖然研究難度較大,但它可以在人與數據、人與圖形之間進行“對話”,特別是與地球物理正演、反演技術結合,可提高地質數據的處理、解釋效率,具有很好的應用前景。

[1] 丁艷紅,夏東嶺,李志勇,等.對二維地震剖面的解釋與成圖方法的認識 [J].石油物探,2002,41(2):211.

[2] 張亞敏,張書法.二維地震疊加偏移剖面“二步法偏移”地質解釋方法[J].西安石油大學學報 (自然科學版),2009,24(1):34.

[3] FUCHS H, KEDEM ZM, USELTON S P. Op timal Surface Reconstruction from Planar Contours[ J ]. Communicationof the ACM, 1977, 20 (10) : 693.

[4] KEPPEL E. App roximating Comp lex Surface by Triangulation of Contour L ines [ J ]. IBM Journal Res Develop1975, 1: 2.

[5] HOULD ING SW. 3D GeosciencesModeling - Computer Techniques for Geological Characterization [M ]. BerlinHeidelberg: Sp ringer– Verlag, 1994.

[6]V ICTOR JD TSA I. Delaunay Triangulations in TIN Creation:An overview and a linear - time algorithm [ J ]. International Journal of Geographical Information Systems,1993, 7 (6) : 501

[7] 屈紅剛,潘懋,王勇,等.基于含拓撲剖面的三維地質建模[J].北京大學學報 (自然科學版),2006,42(6):717.

[8] 吳文鸝,管志寧,高艷芳,等.重磁異常數據三維人機聯作模擬[J].物探化探計算技術,2005,27(3):227.

[9] 李光亮,肖海紅,徐遵義,等.平行輪廓線構建復雜斷層地質模型研究[J].煤田地質與勘探,2007,35(2):22.

[10]陳華根,吳健生,王家林,等.剖面疊置思想在地球物理反演建模中的應用 [J].同濟大學學報,2003,31(11):1309.

[11]唐澤圣.三維數據場可視化 [M].北京:清華大學出版社,2000.

[12]CHR ISTIANSEN H N, SEDERBERG TW. Conversion of Comp lex Contour L ine Definitions into Polygonal ElementMosaics [ J ]. Computer Graphics, 1978, 12 ( 2 ) :187.