泊松方程在地质断层数据的网格化中的应用

2007a43(8) Computer Engineering and Applications 计算机工程与应用 1 引言 近年来a在计算机图形学领域a随着真实感图形生成技术 的发展a人们已可以利用计算机模拟生成许多十分逼真的自然 景物O在飞行模拟器\军事训练模拟器\船舶操纵模拟器等的虚 拟自然环境中a核心技术之一是视景模拟a而三维地形是视景 中最基本的虚拟自然环境景物a 是视景系统的重要组成部分O 由于实际地形起伏千差万别a使得三维真实感地形模拟的数据 量极大a因此在建模和实时显示两方面都对计算机的图形处理 能力提出了很高的 要求 对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗 O 在实际应用中a通常试图通过算法和 软件技术a在现有计算机性能和硬件水平上a综合考虑显示速 度与生成图形效果之间的关系a以生成满足不同几何精度和逼 真度要求的真实感三维地形图形O 如 Hoppe 等人提出基于视 点的层次细节控制和地形绘制 [1-4];de Floriani L 等人提出的基 于三角网格的 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 面绘制 [5-7];P.Cignoni 等人提出的多分辨率的 地形可视化[8a9];王永明等提出的一种快速 DEM 生成算法[15]O 由 于数据量和计算量的关系a 现有的算法一般都会简化地层模 型a只处理等高线而不考虑断层的区域O 以这类方法建立的三 维地形一般没有断层的信息a所以不适用于地下勘探和测量等 领域O 在一般的物体表面的热度场\梯度场以及重量场的一致连 续情况下a泊松方程都能够得到比较好的运用O如苏彬\王大海 等人提出的基于泊松方程的二元翼型网格生成技术 [16]a利用求 解泊松方程的方法来划分计算安装在风洞中的二元翼型网格; Harlow 和Welch 通过在矩形网格上建立流动方程的直接差分 格式发展起来的 MAC 算法求得速度场和压力场; 孙霖等人的 Broyden 算法在薛定谔方程和泊松方程自洽求解中的应用 [17]a 通过自洽求解一维半导体量子线的电子浓度分布和电势分布O 本文就是从这点出发a给出了新的方法a将泊松方程应用在断 层面等不连续的地形的网格化上a解决前面所提到的问题和矛 盾O 下面首先介绍泊松方程求解高度场的数学推导和解法O 2 使用离散泊松方程求解高度场 给定一系列等高线a生成一个高度场O 假定要生成的高度 场是 C1 连续a并且势能最小a那么在整个区域上a每个点都要 满足:diu(gradh(xay))=0 其中ah xay)为高度场函数O 又 gradh (xay)=( !h!x a !h !y )a所以 :diu(gradh(xay))=diu( !h!x a !h !y )= ! 2 h !x 2 a ! 2 h !y 2 O 故在整个区域上a有 ! 2 h !x 2 a ! 2 h !y 2 =0a边界条件:hIBl 其中边界条件即由等高线给定O 这里考虑一个在这个平滑区域的(n+1)*(n+1)网格a其中 d=1/(n+1)是网格的大小a假设 h(ia )是(x i day d)这点的 近似解O 图 1 所示的就是 n 7 的情况O 根据 Taylor 公式: h(i+1a ) h(ia ) !h!i *d d 2 2I ! 2 h !i 2 + d 3 3I * ! 3 h !i 3 +0(d 4 ) 泊松方程在地质断层数据的网格化中的应用 韩 东!张松海 HAN DongaZHANG Song-hai 清华大学 计算机科学与技术系a北京 100084 Department of Computer Science and TechnologyaTsinghua UniversityaBeijing 100084aChina E-mail:han-d03@mails.tsinghua.edu.cn HAN DongaZHANG Song -hai .use poisson eguation to grid faultage datas.computer Engineering and Applicationsa 2007a43(8):242-244. Abstract: Faultage datas include contour lineafault line and fault sectionaand contour line is most important of allabut the faultage data gridding is complicated by the effect of fault line and fault section.To solve this problem efficientlyaconjugate gra- dient method is introduced to evaluate the poisson eguation of terrain in this paperaand the construction algorithm of the faultage datas is given. Key words: poisson eguation;conjugate gradient method;triangulation;rendering 摘 要!地质断层数据包括等高线!断层线!断层截面等数据"其中等高线数据是最为主要的部分"然而由于断层线和断层截面的 影响"增加了地质断层数据网格化的难度和复杂度"所以如何有效!合理的对它进行网格化也是一个难点问题#利用共轭梯度法来 求解高度场的泊松方程"给出地质断层数据高度场的生成算法$ 关键词!泊松方程%共轭梯度法%三角划分%绘制 文章编号!1002-8331(2007)08-0242-03 文献标识码!A 中图分类号!TP39 作者简介!韩东(1976-)a男a硕士a主要从事计算机图形学和三维绘制方面的研究O 242 2007,43 !)! ! ! ! ! ! ! ! ! !Computer Engineering ani Applications 计算机工程与应用 h i, ) i=0 i=l i=2 i=3 i=4 i=5 i=6 i=7 i=8 =8 =7 =6 =5 =4 =3 =2 =l =O y i i x 图 l 8"8 网格示意图 顶视图 侧视图 图 2 均匀网格模型示意图 ! ! ! ! h(i-l, )=h i, )- !h!i *i+ i 2 2! * ! 2 h !i 2 - i 3 3! * ! 3 h !i 3 +0 i 4 ) 所以Z ! 2 h !i 2 = h(i-l, )+h(i+l, )-2*h(i, ) i 2 +0(i 2 ) 同理Z ! 2 h ! 2 = h(i, -l)+h(i, +l)-2*h(i, ) i 2 +0(i 2 ) 所以对于每个采样点(i, ),都有Z h(i-l, )+h(i+l, )+h(i, -l)+h(i, +l)-4*h(i, )=O 对于等高线上的点,则简单的指定Zh(i, )=Ci ,其中 Ci 为 等高线在这一点的高度值O 这样就可以构造出一个方程组Z!"=#, 其中 ! 为 M*N 的 稀疏矩阵," 为 N*l 的向量, 即要求的每个点的高度值,$ 为 M*l 的向量O 其中,M#采样点的数目$等高线上已知离散点的 数目,N#采样点的数目O 而如何解这个方程有多种方法,表 l 是各种方法的比较O 其中Z Dense LUZGaussian elimination,treating P as dense Band LUZGaussian elimination,treating P as zero outside a band of half-width n-l near diagonal Sparse LUZGaussian elimination,exploiting entire zero-structure of P Inv P)*bhatZprecompute and store inverse of P,multiply it by right-hand-side bhat CGZConjugate Gradient method SORZSuccessive Overrelaxation FFTZFast Fourier Transform based method 从算法的复杂度和性能的角度来综合考虑,采用 CG 共轭 梯度法)的算法,具体算法描述如下Z x=initial guess for inv A)*6 r=6-A*x residual,to be made small p=r initial search direction repeat U=A*p a= r!*r)/ p!*U) x=x+a*p compute updated solution new_r=r-a*U compute updated residual g= new_r!*new_r)/ r!*r) p=new_r+g*p compute updated search direction r=new_r until new_r!*new_r small nough) 这个算法的时间复杂度为 O N^3/2),空间复杂度为 O N)O 在上面介绍的泊松方程的建立和解法的基础上,我们给出了地 层数据地层高度场的生成算法O 3 地层数据地层高度场生成算法 这里的输入数据为多层的地层数据,采用 Autocad 常用的 dxf 文件表示O 通过读取 dxf文件,即可取得等高线数据和断层 线数据O 同时,为了方便断层线的处理和匹配,对 dxf文件中断 层线的存储做了如下 规范 编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载 Z 断层线分为两种,无匹配的断层线和有匹配的断层线 即 在同一地层中,两条断层线相互对应,这两条断层线之间的区 域即为断层区域)O 每条断层线单独占用 dxf 文件中的一个层,该层的命名必 须以 FAULTAGE 开头O 对于无匹配的断层线,断层线的命名为 FAULTAGE_ 一 个大写字母),如 FAULTAGE_A,FAULTAGE_BO 对于有匹配的 断层线,两条断层线的命名分别为 FAULTAGE_ 一个大写字 母)l 和 FAULTAGE_ 同一大写字母)2, 并一定成对出现,如 FAULTAGE_Cl 和 FAULTAGE_C2O 不同地层之间,相同名字的断层线自动匹配,如上一地层 中的 FAULTAGE_A 和下一地层中的 FAULTAGE_A 自动匹配, 生成断层截面O 具体算法步骤如下所述Z 3.l 读取数据并建立网格 读取等高线和断层线数据,根据输入数据的包围盒,建立 均匀剖分的网格O均匀网格模型是三维地形模拟中的一种常用 方法,如图 2 所示O 数据通过存储一块方形均匀网格上每一网 格点的高度值来表示;其他位置的高度值通过该位置最近的四 个网格点高度值插值而得到O 3.2 确定断层区域 数字化之后的断层线分两种Z一种没有匹配,如图 3 中红 色的断层线;一种有匹配,如图 3 中其它断层线,均有两条匹配 的相对应;其它线条为等高线O 匹配断层线内的区域即为断层 区域,如图 3 中的绿色斜线区域即为两条绿色的匹配断层线所 确定的断层区域O 3.3 确定网格点的连接关系 两网格端点如果被断层线所隔断,则这两网格点之间的高 度场不会相互影响,其余相邻网格点生成高度时会相互影响O 3.4 求解泊松方程来确定网格点高度值 根据断层区域和网格点的连接关系,可以得到这个高度区 算法名称 Dense LU Band LU Inv(P)*bhat Jacobi Sparse LU CG SOR FFT Multigrid Lower Bound 串行时间 N^3 N^2 N^2 N^2 N^(3/2) N^(3/2) N^(3/2) N*logN N N 并行时间 N N logN N N^(l/2) N^(l/2)*logN N^(l/2) logN (logN)^2 logN 存储 N^2 N^(3/2) N^2 N N*logN N N N N N Procs N^2 N N^2 N N N N N N 表 l 各种方法的比较 韩 东!张松海"泊松方程在地质断层数据的网格化中的应用 243 2007a43(8) Computer Engineering and Applications 计算机工程与应用 图 6 求解泊松方程后绘制出来的效果图 图 5 单层地层的等高线和断层线示意图 断层线 2 断层线 1 图 4 匹配的断层线之间的三角划分 域的泊松方程a然后使用 CG(共轭梯度法>的迭代算法a得到整 个高度区域的高度值O 3.5 多层地层的断层线之间的三角划分 多层地层之间a需要在匹配的断层之间绘制截面O 由于在 不同层的地层之间a已经通过断层线的名称指定好了匹配的断 层线a所以只需在匹配的断层线之间绘制三角面即可O 根据断 层线的长度做合适的三角划分a然后绘制这些三角面即可O 如 图 4 所示a断层线 1 有 5 个顶点a断层线 2 有 3 个顶点a图中的 剖分为一种合适的剖分方法a可用于绘制O 4 绘制的结果和存在的问题 通过上面所述的泊松方程地层高度场生成算法a生成高度 场之后a对于每个网格点a能够知道:该网格点位于断层区域\ 高度场区域还是未定义区域和该网格点的高度值O对于未定义 区域a不予显示;对于断层区域a统一使用一种颜色显示a以标 明该区域为断层区域;对于高度场区域a为表现地层的凹凸感a 使用表面的法向值作为颜色显示O 比较图 5 和图 6a可以看出a绘制出的三维结果和原先的 二维等高线图完全一致a颜色过渡自然\合理a并且能够显示多 层地层之间断层截面的情况O 可以说a通过求解泊松方程来网 格化地层达到了预期的目的a得到了十分满意的效果O 存在的问题:算法有时收敛的比较慢a迭代的次数比较多a 这是因为算法迭代的快慢取决于稀疏矩阵 ! 的最大特征值和 最小特征值的比值的大小;由于算法中都是朝同一个方向三角 化网格a所以绘制的结果中地层的边缘部分不是太平滑O (收稿日期:2006 年 5 月> 参考文献! [1] Hoppe H.Viewdependent refinement of progressive meshes[C]//Turner. ACM SIGGRAPH:SIGGRAPH 97 Conference ProceedingsaAnnuaI Conference Series.[S.l.]:Addison WesIeya1997:189-198. [2] Hoppe H.Smooth viewdependent IeveIofdetaiI controI and its apIi- cations to terrain rendering[C] / / IEEE VisuaIization'98 Confa1998: 35-42. [3] Hoppe H .Optimization of mesh IocaIity for transparent vertex caching [C ] / /Computer Graphics Proc AnnuaI Conf Series (SIG- GRAPH'99>.[S.l.]:ACM Pressa1999:269-276. [4] Levenberg J.fast viewdependent IeveIofdetaiI rendering using cached geometry [C]//IEEE:Proceedings IEEE VisuaIization'02a2002:259- 266. [5] fIoriani L.Surface representations based on trianguIar grids[J].VisuaI Computera1987a3(1>. [6] Tsai V J D.fast topoIogicaI construction of deIaunay trianguIation and vornoni diagrams[J].Computers and Geosciencesa1993a19(10>: 345-350. [7] CohenOr DaLevanoni Y.TemporaI continuity of IeveIs of detaiI in deIaunay trianguIated terrain[C]//IEEE:IEEE VisuaIization'96aOc- tober 1996. [8] Cignoni PaPuppo EaScopigno R.Representation and visuaIization of terrain surfaces at variabIe resoIution [ J ] .The VisuaI Computer a 1997a13(5>:199-217. [9] Puppo E.VariabIe resoIution terrain surfaces[C]//Proceedings Eight Canadian Conference on ComputationaI GeometryaOttawaaCanadaa 1996:202-210. [10] Evans WaKirkpatrick DaTownsend G.Right trianguIated irreguIar networks[J].AIgorithmicaa2001a30(2>:264-286. [11] Ware J M.A procedure for automaticaIIy correcting invaIid fIat triangIes occurring in trianguIated contour data [J].Computers & Geosciencesa1998a24(2>:141-151. [12] LI HuiaSONG You-IiaZHANG Jian-wei.AIgorithms for eIeva- tionreconstruction from eIevation contour [J].JournaI of Image and Graphicsa2002a11(7A>. [13] Li Juan.GIobaI convergence of a cIass of conjugate gradient meth- ods[J].JournaI of CapitaI NormaI Universitya2005(4>. [14] 王永明a林行刚.一种快速 DEM 生成算法[J].计算机应用与软件a 1998a15(4>:28-33. [15] 张登华a刘绍华.值线自动建立拓扑关系算法与快速填充应用[J]. 中国图像图形学报a2001(3>:264-269. [16] 苏彬a王大海.基于泊松方程的二元翼型网格生成技[J].中国民航 飞行学院学报a2002a13. [17] 孙霖.Broyden算法在薛定谔方程和泊松方程自洽求解中的应用[J]. 半导体学报a2005a26. 图 3 等高线和断层线示意图 红 色 断 层 线 其 它 断 层 线 244 泊松方程在地质断层数据的网格化中的应用 作者： 韩东， 张松海， HAN Dong， ZHANG Song-hai 作者单位： 清华大学,计算机科学与技术系,北京,100084 刊名： 计算机工程与应用 英文刊名： COMPUTER ENGINEERING AND APPLICATIONS 年，卷(期)： 2007,43(8) 参考文献(17条) 1.孙霖 Broyden算法在薛定谔方程和泊松方程自洽求解中的应用[期刊 论文 政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载 ]-半导体学报 2005(12) 2.苏彬;王大海 基于泊松方程的二元翼型网格生成技[期刊论文]-中国民航飞行学院学报 2002(4) 3.Puppo E Variable resolution terrain surfaces 1996 4.Cignoni P;Puppo E;Scopiguo R Representation and visualization of terrain surfaces at variable resolution 1997(05) 5.Cohenor D;Levanoni Y Temporal continuity of levels of detail in delaunay triangulated terrain[外文会议] 1996 6.Tsai V J D Fast topological construction of delaunay triangulation and vornoni diagrams 1993(10) 7.Floriani L Surface representations based on triangular grids 1987(01) 8.Levenberg J Fast viewdependent levelofdetail rendering using cached geometry 2002 9.Hoppe H Optimization of mesh locality for transparent vertex caching 1999 10.Hoppe H Smooth viewdependent levelofdetail control and its aplications to terrain rendering[外文会议] 1998 11.张登华;刘绍华 值线自动建立拓扑关系算法与快速填充应用[期刊论文]-中国图象图形学报 2001(03) 12.王永明;林行刚 一种快速DEM生成算法 1998(04) 13.Li Juan Global convergence of a class of conjugate gradient methods 2005(04) 14.LI Hui;SONG You-li;ZHANG Jian-wei Algorithms for elevationreconstruction from elevation contour[期刊论文]-Journal of Image and Graphics 2002(7A) 15.Ware J M A procedure for automatically correcting invalid flat triangles occurring in triangulated contour data[外文期刊] 1998(02) 16.Evans W;Kirkpatrick D;Townsend G Right triangulated irregular networks 2001(02) 17.Hoppe H Viewdependent refinement of progressive meshes 1997 本文链接：http://d.g.wanfangdata.com.cn/Periodical_jsjgcyyy200708074.aspx