何 畏,吴文鹂

(中国地质科学院 地球物理地球化学勘查研究所,河北廊坊 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算法的特点。或者利用人机交互方式移动二轮廓线上的节点及边,使二轮廓线所形成区域的形状、面积大小尽可能的接近,使中心差减小,最终取得较好的建模效果。

(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.