网格自动生成（精选9篇）
网格自动生成 篇1
自适应有限元分h型、p型、h-p型三种。对于h型自适应有限元,最重要的问题有两个:(1)对现有计算结果进行误差估计,以判断是否进行网格调整并给出网格调整的标准;(2)自动生成符合要求的有限元网格。
网格自动生成的研究一直是一个热点,其中关于四面体单元自动生成的研究进步最为明显。目前国际上流行的四面体生成算法为行波法和Delauney法。应用行波法生成的的四面体网格常有一些形状极差的单元,这对有限元求解的精度和效率都有影响,于是通常一个有效的行波法网格自动生成过程应包括两部分,先形成一个拓扑关系正确的初始网格,然后对其进行优化,以得到一个高质量的网格供计算使用[1]。
经过20多年的发展,h型自适应有限元在机械制造、金属成型等工业领域都有成功运用,近年来也有学者尝试在岩土工程等领域引入自适应有限元分析。本文的主要目的就是结合岩土工程等领域的实际情况,讨论利用行波法生成拓扑关系正确的四面体网格的若干关键问题,至于网格优化的问题可参见论文[2]。
行波法首先对三维物体的轮廓面进行三角形离散以形成初始波前,然后生成四面体,将波前逐渐向里推进。当波前上的活动面数为零,四面体充满整个三维域时行波法终止[3]。在这个过程中,有两个问题对行波法的有效性和效率起重要作用,这两个问题分别是不规则曲面的参数表示和几何搜索问题。
物体轮廓面的三角形离散是一个三维问题,通常的办法是先将轮廓面参数化表示为:
然后在参数面(s,t)与三维曲面之间建立双向映射,将问题转化为二维三角形行波法处理[4]。显然不规则曲面的参数化表示是这个过程的关键,本文的第二部分将讨论利用混合样条插值曲面来解决这个问题。
行波法通过几何搜索寻找在一特定的空间区域的几何对象(点、线、面等),这在四面体生成过程中有重要应用。行波法首先将在波前面上确定一三角形作为活动面Δabc。若此时波前上共有n个点,运用几何搜索过程从这n个点中找出位于Δabc某一规定邻域内的点,然后在这些搜索得出的点中确定一点d,形成四面体Tabcd(另一种生成四面体的方法是新生成一点d',形成四面体Tabcd')。由此可知几何搜索是行波法生成每一个单元都必须处理的问题。如果直接对波前上的每一个点依次进行判断,所需的工作量通常较大,行波法的很大一部分计算时间都被几何搜索占用。为了提高行波法的效率,本文第三部分将讨论利用双叉树型结构进行几何搜索的问题。
2不规则曲面的参数化表示
2.1混合样条插值曲面的引入
岩土工程中存在着大量不规则曲面,如地形面、大规模断层面等,如何将这些曲面参数化表示一直是一个困难的问题。计算机辅助几何设计(CAGD)中一些常用的曲面构造方法(如孔斯曲面(Coons Surface))对上述大尺度且几何信息不充分的曲面往往是不适用的。这些方法往往要求许多面片的角点坐标X、切矢Xs、Xt和扭矢Xst等数据,这些要求显然是实际工程所不能满足的。若采用一些近似方法(如Adini处理),又可能导致曲面较严重的变形。在这种情况下,本文将W.J.Gordon[5]所提出的混和样条插值曲面引入岩土工程领域,以期解决上述问题。
2.2混和样条插值曲面的构造
令R:[a,b][cd]为(s—t)平面内一矩形域,定义于该矩形域的连续曲面记为:
将区间I=(a,b)分为π:a=s1≤s2≤…≤sn=b,将区间I'=(c,d)分为π':c=t1≤t2≤…tn'=d,垂直于(s—t)面的系列平面s=si,t=tj与曲面Z的交线记为:
这n+n'个单参数函数给出了曲面Z上的一套曲线网络。
选定两套2p-1次样条基函数{φi(s)},{φj(t)}。
混和样条插值曲面可表示为
式(8)中对曲面式(2)运用的算符L、M为一线性操作,具体意义可见文献[5]。
2.3混和样条插值曲面在岩土工程中的应用
通过以上叙述可知,混和样条插值曲面对原曲面进行的是一种整体拟合,这从根本上有别于常见的曲面片拼接型的曲面构造,适合于对大尺度曲面进行拟合。同时若令p=2,该曲面保有C2的连续性,这是不规则曲面三角离散所必须的。又曲面边界的切矢条件在岩土工程中并无特别意义,在这里将其忽略:
将式(7)带入式(6),得到新的混和样条插值曲面公式:
式(8)中样条基函数可以作为固定模块直接编入程序,根据不同的n或n'直接调用。如果已知曲线网络式(3)上的一些点,利用三次样条插值曲线便可拟合出n+n'条曲线参数方程fj(s)、gi(t),利用公式(8)便可得到曲面式(2)。将曲面参数方程(1)看作定义于同一矩形域的三个独立的曲面方程,依次用上述方法拟合,从而得到不规则曲面的参数表示。
上述简化处理会使曲面临近边界的区域发生一些变形,但与机械、数控操作等领域所研究的精密几何形体的模拟不同,这些误差在岩土工程中是可以接受的。如果选择一个恰当的辅助面,这种影响还会得到更好地控制[6]。
3行波法中的几何搜索问题
3.1双叉树型结构的基本概念
双叉树型结构是一种数据在存储空间非顺序排列的数据结构。它由许多层状结构构成,其中最基本的层状结构为一个节点(母节点)与其下左右两个节点(子节点)相连接,这种结构方式也称为母节点指向两个子节点。在整个树型结构中,除了最上层节点(根节点),每个节点都被且仅被一个节点所指向。为了充分定义某节点,需三个相关数字,首先是存贮于该节点的数据,然后是该节点两个子节点在存贮空间中的位置,后两个数字记为该节点的左连接、右连接。显然左、右连接或者为零,或者为整数。若一个节点左、右连接均为零,即无子节点与其相连,则该节点称为中断点。
3.2双叉树型结构在几何搜索中的应用
设行波法波前上有n个点,将其存贮于树型结构的n个节点上。利用某种规则确定树型结构,使节点与空间某域建立联系,通过对树型结构节点的访问实现几何搜索[7]。
在N维空间RN中定义一超立方体为ai≤xi≤bi(i=1,…,N),并将该立方体上下界记为(a,b)。在树型结构中定义根节点为“0层点”,其对应空间为(a,b)。与树型结构的分叉与层状结构对应,依次用垂直于坐标轴的平面切分空间(a,b)。设节点K位于第L层,其代表的空间子域为(ck,dk),节点K的左连接对应子节点为P,右连接对应子节点为Q,它们分属的子空间为(ckl,dkl)、(ckr,dkr)。
令j=1+mod (l,N) (9)
P对应的子空间为:
c
c
Q对应的子空间为:
c
c
其中i=1,…,n。
由以上定义可知,K节点的所有子节点存贮的数据均位于K所代表的空间(ck,dk)内。若(ck,dk)与搜索空间不相交,则K所含的所有子节点均可排除,不必一一检验。下面具体给出利用双叉树型结构进行几何搜索的算法,该算法略经修改也可实现对树型结构任一节点的访问。
定义一栈数组stack,栈长度m=0,root=根节点存贮位置。
(a) 访问位于root的节点,检查存贮于该节点的数据xk是否在搜索空间(e,f)中,即检查是否满足ei≤x
(b) 如果root对应的节点右连接right≠0,且(ckr,dkr)与(e,f)相交,即,令n=n+1,stack(n)=right。
(c) 如果root对应的节点左连接left≠0,root=left go to (a) 。
如果left=0,但n≠0,root=stack(n),n=n-1, go to (a) 。
如果left=0, 且n=0,结束程序。
在四面体生成过程中,行波法的波前不断变化,这就要求从树型结构中不断增加或删除节点。利用上述访问节点的算法可以方便地实现这一点。
最简洁的添加节点的方法是从根节点开始由上至下访问树型结构的节点。如果某节点左(右)连接为0,且需添加点坐标位于该连接所代表的空间区域内,令该连接指向需添加节点即可。
至于删除节点,若被删除点为一个中断点,只需指向该节点的连接为0即可。非中断节点的删除较复杂,需从被删除节点所有的子结构中找出一中断点,令指向被删除节点的连接指向该中断点,指向该中断点的连接为0。
4算例
运用上述方法对一边坡洞室开挖问题进行了有限元网格离散。该边坡有不规则地形面和两条相交断层。为了保证计算精度,根据自适应有限元误差估计理论对网格做了优化。
图2、图3给出的是经过两轮优化后的网格,其网格离散误差为12.3%,有四面体单元13 114个。
摘要：网格自动生成是自适应有限元重要组成部分,其中如何有效地对三维物体轮廓面进行参数化表示一直是一个难点。结合岩土工程的实际情况,利用混合样条插值曲面对地形面、大规模断层面等不规则曲面进行了拟合,成功地解决了这个问题。另外还讨论了利用双叉树型结构进行几何搜索的算法,该算法能提高行波法生成四面体的效率。最后用一边坡洞室开挖的算例验证了编制程序的有效性。
关键词：有限元网格,四面体,行波法
参考文献
[1] Dari E A,Buscaglia G C.Mesh optimization:how to obtain good un-structure 3-D finite element meshes with not-so-good mesh generators.Struct Optim,1994;8,181—188
[2] Zavattieri P D,Dari E A, Buscaglia G C. Optimization strategies in unstructured mesh generation. Int J Numer Meth Eng,1996;39:2055—2071
[3] Peraire J,Peiro J.Adaptive remeshing for three-dimensional compres-sible flow computations,Journal of Computational Physics,1992;103:269—285
[4] Moller P,Hansbo P.On advancing front mesh generation in three di-mensions.Int J Numer Methods Eng,1995;38:3551—3569
[5] Gordon W J. Spline-blended surface interpolation through curve net works. J Math Mech,1969;18,931—952
[6] Xia H X,Chen S H.3-D adaptive FEM in rock slope stability analy-sis.The 10th International Conference on Computer Methods and ad-vances in Geomechanics,Arizona,USA,2001:1635—1639
[7] Bonet J, Peraire J. An alternating digital tree(ADT) algorithm for 3D geometric searching and intersection problems. Int J Numer Methods Eng, 31:1—17
网格自动生成 篇2
三维复杂外形的双曲型网格生成方法
应用了从正交性条件和单元体积控制条件得到的.双曲型网格生成格式,采用了隐式算法、椭圆光顺技术和当地拐角处理,以致对于很多三维几何体可快速生成高质量的网格.以生成一机翼和构形复杂的某飞机机身网格为例,检验了本文方法的适用性和优越性.
作 者：李孝伟 乔志德 Li Xiaowei Qiao Zhide 作者单位：西北工业大学刊 名：西北工业大学学报 ISTIC EI PKU英文刊名：JOURNAL OF NORTHWESTERN POLYTECHNICAL UNIVERSITY年，卷(期)：199917(2)分类号：V211.1关键词：双曲型 椭圆光顺 隐式算法
网格计算在动画生成中的应用 篇3
关键词：网格计算,动画生成,监控
1 介绍
随着信息技术的发展, 大量的数据需要被处理。单台计算机不再能满足处理这么大量数据处理的需要。因此, 许多解决方案被提出, 其中一个就是网格并行计算。网格计算是一种管理计算机集合以实现共同任务的技术。与超级计算机相比, 网格技术是松散耦合的, 并且使用网格管理工具包, 很容易构建具有强计算能力的可扩展和安全的网格。网格技术的另一个优点是经济实惠。例如, 公司可以在自己的机器中实现其网格基础架构, 并在机器空闲时向其分配任务。
本文设计了一个用于动画生成的网格架构。第2节将介绍设计目标, 第3节将讨论网格计算结构设计细节, 然后第4节将描述硬件配置及讨论实验结果, 最后在第5节进行总结。
2 设计目标
基于具有一定数量的计算机节点的系统设计, 把pov格式文件存储在系统中的每台计算机里。每台计算机能够从pov文件生成高清晰度图像, 而生成的图像将对网格中的所有计算机可见。在生成图像之后, 任何计算机应该能够将图像逐帧转换为高清晰度动画。但在这种情况下, 在图像或者动画生成期间, CPU和内存资源将会不足。为了解决这个问题, 可通过在该系统中使用网格计算, 并且可以通过添加多个服务器节点以减少CPU和存储器的占用率, 以实现加速处理数据的目标。其中, 网格上的每个节点都应该安装Globus Toolkit工具包。
3 网格计算结构设计
3.1 可扩展性
Globus工具包为网格管理提供了一些组件。Globus资源分配和管理GRAM是使得用户能够定位、提交、监视和取消远程作业的组件之一。此外, 监控和发现服务MDS可提供有关节点的状态和可用性的信息, Grid管理器可以使用这些信息来选择使用资源。
当前网格资源管理有其弱点。公共采用的架构是2层层次资源管理。然而, 在大规模网格网络中使用该架构, 一些资源将变得不可访问。此外, 使用2层架构使得网络QoS较差。
在新的框架中, 我们提供分层资源管理器。资源管理器有三种类型: (1) 管理一个特定资源的个人资源管理器 (IRM) ; (2) 管理集群中的资源的集群资源管理器 (CRM) ; (3) 网格资源管理器 (GRM) , 用于管理整个网格网络中的资源。在4层网格网络中, IRM用在最低层级1中, 中间层采用CRM, 在顶层框架使用GRM进行资源管理。
3.2 安全性
网格的安全性通过以下手段维护: (1) 防火墙:部署防火墙以保护网格免受恶意攻击。防火墙通过检查数据包的源IP地址和目的IP地址来管理网络。恶意和可疑数据包将被防火墙从网关外部过滤。防火墙可以限制从Internet到网格的访问, 它还可以限制从网格计算系统到外部Internet的访问尝试。 (2) Globus工具包:Globus工具包适用于我们的企业动画生成网格系统的设计。它提供了一个称为“Globus安全基础设施” (GSI) 的安全标准和模块。Globus安全基础设施在网格计算环境中的计算机之间提供了秘密的、防篡改的、可委托的通信支持。我们使用非对称加密RSA用于GSI以实现安全和可认证的通信。 (3) 证书:网格上的每个用户和服务都有一个已识别的证书。证书包含主题名称、公钥、证明公钥属于主题的证书颁发机构 (CA) 和CA的数字签名的信息。 (4) 相互认证:GSI使用安全套接字层 (SSL) 进行相互认证。SSL使用1024和2048位密钥长度的RSA算法。当两个单元的网格相互通信时, 他们将首先验证对方的第三方CA。在双重验证成功之后, 然后建立连接。 (5) 密码通信:缺省情况下, GSI不保证双方之间的加密通信。如果请求机密通信, GSI可以提供用于加密和解密的共享密钥。对于我们网格的设计, GSI的这两个特性都用于保护节点和服务器之间的通信。
3.3 外部集成
在我们的实验网格系统中, 需要允许集成外部资源。为了解决这个问题, 我们部署了开放网格服务架构OGSA。OGSA通过分布式异构和动态网格环境提供服务和资源的集成, 无论是在外部资源共享或服务提供方面。我们的设计有一些要求: (1) 全局名称空间:为了容易地访问外部数据和资源, 网格系统应当能够在不考虑位置或复制的安全约束下透明地与其他节点交互。 (2) 元数据服务:我们必须认识到调用和跟踪外部资源是很重要的。我们需要访问和管理跨管理域的实体元数据的权限。 (3) 场地自治性:获取资源的机制需要符合地方控制和政策。 (4) 资源使用数据:这是在网格网络上集成和交换外部资源使用数据的机制和模式。
3.4 监控
数据收集和分布机制的尺度是非常重要的。一个监测机制应建立以监测网格系统的当前性能。当pov文件的大小, 或者动画的质量增加时, 网格系统监控机制应该能够检测相应每个节点的性能。因此, 服务器将能够注意到潜在的资源缺乏并确定节点的数量。通常, 以下特性性能监视信息是系统或程序产生的数据的最重要的部分。
4 硬件配置及实验结果
在我们的实验网格环境中, 我们部署五台计算机, 包括一个服务器和四个客户端节点组成网格网络。在服务器端, 我们部署了英特尔至强服务器。这样的处理器可以满足动画和POV射线软件实现的计算。4GB DDR3内存RAM可为网格计算设备提供高吞吐量。西部数据2TB硬盘为30分钟的动画存储提供足够的空间。AMD HD5630还提供足够的图处理。对于客户端, 主要工作是网格计算, 因此我们上面部署的设备满足要求。
通过对动画的生成演算得到的实验结果, 我们发现4节点下比2节点或1点所消耗的计算时间有所减少, 同时CPU占用率也有所减少, 可见多节点对动画演算是有作用的。
5 结论
并行计算正在成为当代计算机科学中流行和重要的概念。在网格计算的环境中, 如何有效地监视节点信息和应用性能是网格计算中的一个难点问题。本文介绍了一种基于Globus toolkit的网格计算系统组成及共同的动画演算, 并介绍了网格技术研究和设计。设计了基于多节点和多级分布式结构的运算模型。
未来我们的想法是实现自动计算节点选择算法, 并将其集成到我们的集群和网格计算平台中。每个站点中的计算节点被选择为实时提供的运算信息, 软件包还可以针对计算节点的不同速度处理器, 意味着哪个所选计算节点应当执行什么计算在异构集群和网格协定环境中。
参考文献
[1]I.A.Klimonov, V.D.Korneev, V.M.Sveshnikov.Parallelization technologies for solving three-dimensional boundary value problems on quasi-structured grids using the cpu+gpu hybrid computing environment[J].Numerical Methods and Programming, Advanced Computing, 2016, (17) :65-71.
[2]S.Iturriaga, S.Nesmachnow, F.Luna, E.Alba.A parallel local search in cpu/gpu for scheduling independent tasks on large heterogeneous computing systems[J].Journal of Supercomputing, 2015, 71 (2) :648-672.
网格自动生成 篇4
亚跨超CFD软件平台中的网格生成技术
在亚跨超CFD软件平台中,提供了一个网格生成平台.利用它,可以快速生成常规兵器、常规导弹和正常布局的`常规战斗机的计算网格.有多种拓扑结构和多种方法可供选择.结果表明,生成的网格实用,质量令人满意.气动特性的计算结果也是可靠的.
作 者：刘云楚 庞宇飞 陈作斌 Liu yunchu Pang yufei Chen zuobin 作者单位：中国空气动力研究与发展中心,四川绵阳,621000 刊 名：空气动力学学报 ISTIC EI PKU英文刊名：ACTA AERODYNAMICA SINICA 年，卷(期)：2000 18(2) 分类号：V211.3 关键词：CFD软件平台 网格生成 导弹 战斗机网格自动生成 篇5
生成的网格从拓扑结构上分,主要分为结构化网格和非结构化网格。结构化网格数据结构简单,生成速度快。结构化网格在网格边界处通常使用适体坐标法[1],但对于复杂外形的适应性比较差。非结构化网格对于复杂区域的适应性较强,但网格质量不好控制,计算效率相对结构化网格要低。现在非结构网格通常采用带约束的Delaunay三角剖分的方法[2]或四叉树方法[3]。针对不同网格的不同优点及缺点,混合网格应用的也越来越广泛[4]。
为了进一步提升网格生成的计算效率,本文所采用了一种在直角网格上调整顶点来适应边界的生成方法。这样做的优点是:与背景的结构化网格衔接时不需要做特殊处理;在边界附近对被切割的网格分情况讨论去调整网格,利用直角网格生成速度快的优势,避免了复杂度较高的Delaunay三角剖分。
本文的方法主要分为3 个步骤,生成边界网格与计算交点,调整交点位置,生成最终网格,最后以NACA0012 翼型为例,给出网格的生成结果。
1 光滑边界的网格生成
Wenjun Ying和Wei-Cheng Wang的方法[5]可以直接应用到光滑边界的网格生成中。在该方法中,所有边界与网格的交点都被称为控制点。与网格点距离近的称为主要控制点,与网格点距离远的称为次要控制点。所有主要控制点的连线可以作为外形的近似表示,如图1(a)所示。
将结构网格上顶点坐标移动到对应的主要控制点,就完成了网格的调整,如图1(b)的箭头方向所示。
然而这个方法并没有考虑到复杂外形边界上不光滑的尖点。所以本文在此基础上,针对尖点的边界附近的所有情况给出调整方案,把这个调整边界网格的方法推广到复杂的外形上。
2 尖点附近的网格生成
这里的“尖点”是指曲线在该点处,两侧的导数不相等。
2.1尖点附近需要处理的问题
光滑边界的外形所有的点附近都是平滑的,而尖点两侧曲线的切向不同,如果仅仅用交点去近似,会非常不准确。
假设网格足够密,使得外形在3*3的网格范围内最多只有1个尖点。又因为这个顶点两端的切向量不同,所以对于方形结构网格的每个顶点,最多有2 条近似的直线与顶点周围的4条边产生交点。
2条直线与顶点的4条边只有如下6种情况,如图2所示:
针对2.1 中的顶点以及图2 的6 种情况,将会在2.3 分别给出调整的方案。在2.2中先给出了计算前的预处理步骤。
2.2 网格调整前的预处理
初始的网格是与背景网格相同的正方形网格,根据四个顶点在网格的内外的情况,划分出流场网格、物面网格和固体网格。计算区域在现有的物面网格的基础上,向外侧扩展2 层,扩展后的物面网格的外侧顶点会自然地与背景网格衔接起来。之后计算外形与网格线的交点。
2.3直角网格的调整方法
2.3.1尖点的位置调整
对于外形上的尖点,穿过尖点的曲线两侧切向不同,不可能用一条直线近似。所以调整的方式是直接把距离最近的网格点移动到这个尖点处,如图3所示。
2.3.2 不光滑边界6种特殊交点的调整
对于2.1 中图2(a)的情况,不相邻的2 个交点,说明此时外形在这一点附近将流场分成了2个区域。需要在2个交点的位置都设置一个顶点,每一侧的2个网格共用这个顶点,如图4(a)所示。(箭头表示点的位置调整方向)
对于2.1 中图2(b)的情况,同一条边上的2 个交点,也做类似的处理,如图4(b)所示。(箭头表示点的位置调整方向)
对于2.1 中图2(c)和图2(f)的情况,需要在同一直线上2 个交点的位置都设置一个顶点,如图4(d)所示。(此处判断时注意不要与图4(c)的情况混淆)
对于2.1中的图2(d)的情况,4个交点位于2条边上,此时应比较每条边上2个交点离网格顶点的距离和,取较小的。调整结果如图4(e)所示。
对于2.1中图2(e)的情况,4个交点分别位于4条边上,与图2(d)的情况类似,有2种方案选取交点,用同样的方法计算距离和后选取较小的,结果如图4(f)所示。
对于尖点是凹角的情况,可以生成一个三角形网格作为凹角处的网格。从凹角点出发,沿着有交点的顶点进行广度搜索,找到不属于尖点情况的2个交点,连接这2个交点与凹角顶点的三角形,就是描述此处凹角的一个流场网格。如图5 所示。
对网格调整后,最终的生成结果还需要去除内部的网格以及生成三角形网格两步工作。
2.4 去除内部的网格
如果外形没有凹角,4 个点都不在外部即可判为内部网格。允许外形有凹角时,内部网格的判定分为如下几种:
第1种是4个顶点都不在外部,且有2个或2个以上是内部点,一定是内部网格。
第2种是1个顶点在内部,3个顶点在边界上的情况,此时如果网格的2条边在外部,说明部分在内部,应该保留3个边界点形成的三角形;如果网格3条边或4条边都在内部,说明网格是内部网格。
第3种是4个顶点都在边界上的情况。如果网格中心点在内部,说明是内部网格。
2.5 需要变成三角形的网格
需变为三角形的网格分为如下几种。
第1种是上文2.4的第2种情况中提到的,此时应将内部点去掉,留下其余3个顶点变成三角形网格。
第2 种是有且只有1 个顶点在外部,即其它3 个顶点可能在内部或者边界上。此时要做判断,如果不是凹角附近的网格,则将这个外部点以及与它相邻的2 个点构成的三角形,作为此处的网格,如图6(a)所示。
第3 种是2 个对角的顶点在外,另外2 个对角的顶点在内。此时需要分成2个三角形。
后两种情况变成三角形网格之后,需要对网格连接的合法性重新检查,避免三角形网格穿过外形的内部,如图6(b)所示,顶点按照箭头方向调整过后,避免了右上的三角形穿过外形内部。
3 算法的分析
3.1 网格质量
在光滑边界的区域上,根据主要控制点的性质,2个主要控制点的距离最近为倍背景网格边长。在尖点附近,如果四边形网格的4 个顶点中包含有尖点,虽无法保证最短边的长度,但一个网格单元中的尖点只有一个,所以其它3 条边的长度是大于倍边长的。
如果三角形网格有一个顶点就是尖点,最小边的长度至少为1/2倍边长。所以这一方法在一定程度上保证了网格的质量。
3.2网格数量
本文的方法每个正方形网格最多分成2 个三角形网格。网格生成的总数量不超过原始网格的2 倍。且本文的方法仅仅在外形的边界上至边界外2层的范围内进行计算,将需要计算的网格数量减少到最小。
3.3 时间复杂度分析
设边界附近的网格数量为n。
2.1至2.5中的所有操作都是依赖于网格数量的,并且都是O(n)的复杂度。但因为2.3~2.5 的步骤中都需要进行分情况判断,可能复杂度的常系数比较高。
对比Delaunay三角剖分的方法,因为流场的内外边界有约束,所以这里需要用到约束的Delaunay三角剖分方法,时间复杂度最少为O(nlogn)。因此,只要n足够大,本文的方法就会比带约束的Delaunay三角剖分的方法快。
4 算法实例
图7 为NACA0012 翼型在不同角度的网格生成结果,以及在其内部的生成结果。
5 结论
在二维复杂外形的边界生成网格时,本文的方法根据外形与网格边界的交点,分情况讨论,制定出一套网格调整的方案,时间复杂度低于通常使用的Delaunay三角剖分方法。虽然网格的质量达不到最优的,但因为交点的选取策略保证了网格点之间的距离,所以网格的质量通常不会很差。
本文方法的优势是在网格质量可以接受的限度内,用复杂度O(n)的算法快速生成网格。
网格自动生成 篇6
关键词：纹理特征,网格细分,二叉树,三维地形
(一) 引言
地形三维可视化计算近年来一直是相关领域的热点研究问题, 在三维仿真和虚拟地形环境中占有十分重要的地位。关于虚拟环境中三维地形的生成大多数是采用简化算法, 在保留地形细部特征的同时来提高其显示效率, 在简化过程中, 需要对消除裂缝、T型连接和简化模型误差度量等进行计算。本文给出了一种无需考虑消除裂缝和连接计算的三维地形生成方法, 依据地形纹理特征曲线从低精度网格地形向高精度网格细化, 使得平坦的地形区域用少量的三角形网格绘制, 起伏较大的地形区域用较多的三角形网格显示, 也形成一种多分辨地形模型结构, 以提高显示质量和效率。
(二) 方法依据和思路
在三维地形场景中, 虽然地形表现为三维模型, 但表示地形的DEM数据可以等价于由高度场生成的二维灰度纹理图像, 亮度变化小的地方, 表明此区域较为平坦, 亮度变化大的地方, 此地形可能山脉、谷等区域, 而“灰度图像边缘”正可以用来描述纹理图像局部区域亮度变化显著的部分。若能在三维空间中细化“边缘特征曲线”周围的网格正是本方法的关键思路所在, 使得边缘特征曲线周围网格密集, 增强其几何特征。
方法实现基本步骤及思路:
(1) 采用图像处理技术, 对地形高程灰度图像进行边缘检测, 从中提取图像的边缘曲线, 作为下一步网格细分的依据。
(2) 将含有地形特征曲线的图像作为纹理, 映射到一个低精度平面网格上。
(3) 根据三角边与它的纹理特征曲线相交情况来细分网格, 细分后的地形网格存储在二叉树数据层次结构中。
(4) 根据高程图像灰度值为地形网格的每个顶点赋予高度值, 最后绘制二叉树结构中所有叶子数据就是地形最终显示结果。
(三) 方法实现过程
1. 网格模型的定义
三角网格除了是由三维空间中的三角片通过边和顶点连接而成的分片线性曲面外, 我们将纹理图像信息作为曲面描述数据定义在网格模型中, 便于细分网格时作为参考对象, 以及增强显示效果, 所以, 这里网格M可以定义为一个三元组, M= (K, V, U) 。
其中, U={u1, …, um}, uiЄR2表示像素点在二维纹理图像中的坐标。
V={v1, …, vm}, viЄR3表示网格M的顶点在三维空间中的位置。
K为表征网格拓扑结构的单纯复形, 一个单纯复形包含一组单形, 其中{i, j}称为边, 记为L;{i, j, k}称为三角形面, 记为T, 三角形每条边最多只能包含在两个三角片中, 并且一个顶点和一个纹理坐标相对应。
2. 网格三角面拆分过程
网格细分的主要目的是为了增加网格细节层次;在地形网格模型中, 这种细节层次主要表现在地形的起伏特征, 根据地形起伏特征自动调整三角网格绘制数量, 在起伏大的区域, 三角网格数量多, 平坦区域, 三角网格数量少;首先预生成一个规则初始地形网格M0, 将含有地形纹理特征的图像映射到网格M0中, 经过网格n次细分, 生成M=M0→M1→M2…→Mn序列, 设T是M0经第i次细分的网格模型Mi中一个三角形, 对T细分过程如图1所示。
因为每个三角形网格顶点都有一个纹理坐标 (ui, uj) 相对应, 首先沿着三角形的绘制方向判断边和特征曲线是否相交, 那么新的交点与该边对应的顶点连线, 将三角形拆分成两个;在图1中的虚线表示地形纹理图像特征曲线, 图1 (a) 中的v1、v2和v3是三角形与特征曲线交点, 首先边{1, k}将三角形T拆分成T1、T2两个三角形, 然后边{2, 1}将T2拆分成T3、T4, 边{3, 1}将T1拆分成T5、T6。将新的顶点v1、v2和v3映射回三维空间, 依据地形高度场赋予新的高度值。一个三角形可能被拆分成4个、3个、2个三角形或不被拆分4种情况, 这样完成一个三角形的细分, 其它三角形网格采用同样的方法, 最终完成整个地形网格模型的细分, 即Mi→Mi+1。
由上述三角面拆分过程, 可以得到图2所示的二叉树细分层次结构。图中的某一层Mx的叶子或没有子树的根是该层网格模型最终绘制结果, 层次越深, 细化程度越高, 树型分支和叶子数量增多, 导致绘制的三角形网格数量的增多。
网格地形的简化过程, 是细化过程的逆过程, 而且无需判断三角形边的拆分情况, 只需将某一层Mx的三角形网格的子树和叶子删除, 就可以达到简化的目的。
3. 细分规则
由于存在提取的边缘线可能与三角形边有多个交点且细分后的三角形法线方向确定等问题, 约束了细分网格效果, 所以, 为了得到较为理想的生成结果, 需要对网格按照一定的规则细分和绘制。
(1) 为了使细分前和后三角面法线方向一致, 避免绘制三角面空洞现象, 将细分后的三角面绘制方向与上一级的三角面绘制方向应该保持一致, 如:三角面T的绘制方向为vivjvk, 那么拆分后的三角面T1、T2的一种绘制方向分别为viv1vk和v1vjvk。
(2) 在三角面细分过程中, 当新增加的拆分顶点v′与该边的端点很接近时, 造成细分后的某一三角形与细分前的三角形很接近, 分裂前后几乎没有发生变化, 即图3中的T2≌T, 所以应给出ωЄ (0, 0.5) , 当|v'-vi|<ω|vj-vi|或|v'-vj|<ω|vj-vi|时, 则新增加的顶点v′为无效点, 此时三角面T的边{i, j}不被拆分。
(3) 三角面的边可能与边缘线存在多个相交点, 为了保证三角面尽可能地均匀地被拆分, 取三角形边中点最近的交点作为该边的拆分点, 即:拆分点P要满足up={|up-0.5× (ui+uj) |}min。
(4) 按照三角形绘制方向来拆分三角形, 如图1中三角形T的绘制方向为vivjvk, 那它的拆分顺序是边vivj, vjvk, vkvi。
(5) 拆分顶点应与最近被拆分的三角形顶点连线来拆分该三角形, 如图1中 (b) 的拆分顶点v2与最近被拆分的三角形T2顶点v1连线来拆分T2, 而不是与三角形T的顶点vi的连线。
4. 数据结构描述和实现过程
根据上述细分过程, 地形网格细分数据可以采用结构规范、搜索较快的二叉树存储, 将每个网格三角形拆分为两个三角形, 拆分前的三角形作为二叉树的根节点, 拆分后的两个三角形作为根节点的子节点, 若子节点不能够再拆分, 则这两个三角形称之为叶子;这些三角形逻辑上就像一组相连的邻居 (左右邻居) , 在细分完地形后, 就建立了三角网格二叉树型结构, 树的叶节点保存了图形绘制缓冲区中的三角形, 针对二叉树描述地形网格特点, 本文如下描述网格二叉树结构:
随着细分层次的增加, 三角形顶点的数量也不断增加且不固定, 因此顶点可以采用链表结构进行存储, 而变量m_vertexIndices就存储了链表队列中的位置;levelNUM代表了三角形拆分过程中所在的层次, 相当于图2中的M层次位置, 便于细化和简化的判定;canDivide是为了提高细分速度, 用来存储该三角形是否能再次细分, 若不能再细分, 就不用再判断二维纹理中三角形各边与特征曲线相交状态。
首先提取由地形的高度场得到灰度图的特征曲线图形, 将基本网格坐标映射到特征曲线的二维平面中, 那么在二维平面中也构成了网格, 判断网格与特征曲线相交情况, 产生新的顶点和三角形网格, 特征曲线密集的地方, 网格细分程度越高, 从而得到的三维地形中, 在地形平坦的地方以最少的存储空间, 起伏变化大的地方用较多的存储空间;如图3所示。
(四) 方法测试
测试目的:采用基于图像纹理特征网格细分的三维地形生成方法对显示效率、质量的影响和关系。
测试手段:
使用C++语言, 以OpenGL作为底层的图形接口, 在C++Builder6.0编译环境中进行测试。建立了CLand (地形生成类) 、CPicture (图像处理类) 、BST (二叉树类) 、CMath (数学计算类) 、CView (窗口显示类) 等主要类。在PⅣ1.8GHz, 256MB内存, Geforce3 64MB显卡机器上, 在800×600窗口, 水平视角450, 误差限2个像素情况下, 定义初始的规则网格数据M0为30×30×2=1800个三角片;原始网格定义为511×511×2=522242个三角片 (数目是根据高程灰度纹理分辨率定义) , 并赋予高度值;细分程度定义为细分后的三角形数目与原始网格三角形数目的百分比;误差定义为原始网格和细分网格的双边Hausdorff距离与原始网格的包围盒对角线长度的百分比, 其测试数据如表1所示, 绘制效果图4所示。
测试结果:在显示效率不低于30帧/秒时, 其中M3能清楚地描述地形几何特征, 误差较小, 显示效率可以达到32帧/秒, 且地形特征变化明显 (图4的 (a) , (b) 比较) , 从M0~M3误差变化较大, 表明能够迅速收敛于地形细节特征;当显示效率低于30帧/秒时, 地形特征变化并不明显 (图5的 (b) , (c) 比较) , M4~M6误差变化小, 而且显示效率并不理想。所以, 在方法应用中, 通常需要给出x={fFS (Mx) ≥FS}max测试程序, 即在满足显示效率的同时, 最大限度地提高其显示质量, 目的是兼顾3D模型显示效率和显示质量, 其中fFS () 用来测试网格Mx显示效率, FS是预先给定的显示效率常数, 如本文以30帧/秒显示效率作为分界线, x是多层次模型最大细分网格深度, 如本文x=3。在实际程序运行过程中, x会根据给定的FS值, 通过网格细化和简化自动调整其网格绘制深度。
(五) 结论
本文给出了一种基于纹理图像特征网格细分的三维地形生成方法, 方法思路简单且容易实现, 通过提取地形高程特征值作为网格细分依据, 形成多分辨率地形模型结构, 使得显示效率和保留地形细节特征尽可能兼顾。从第3节可知, 由于采用三角边拆分方式, 共享该边的一个三角面被拆分, 另外三角面一定被拆分, 因此, 不存在消除裂缝和连接计算, 在一定程度上减少程序设计的复杂过程。
另外, 该方法还可以结合“视点相关”三维地形显示技术, 在显示效率方面还会进一步提高, 这是今后的主要工作。
参考文献
[1]李偈, 张松海, 刘强.一种基于四叉树结构的动态多分辨率地形模型[J].计算机工程与应用, 2006, 42 (7) :202-204.
[2]杜剑侠, 李凤霞, 战守义.LOD算法研究及其在地形实时显示中的应用.计算机工程与应用, 2005, 41 (13) :211-231.
[3]韩敏, 汤松涛, 李洋.大规模地形实时可视化算法[J].计算机工程, 2008, 34 (13) :270-272.
[4]张立强, 杨崇俊.多进制小波和二叉树实现大规模地形的实时漫游[J].计算机辅助设计与图形学学报, 2005, 17 (1) :467-472.
网格自动生成 篇7
关键词：多分辨率分析,区域分割,网格简化,顶点重要度,半边崩溃,细节层次
多分辨率技术是在不严重损失物体视觉特征的前提下对物体网格模型进行的简化操作, 各种简化算法面对的首要问题就是简化效率和简化质量之间的矛盾。文献[1]对目前多分辨率造型技术的研究现状和数据存储方式做了总结, 小波变换、网格细分、网格简化和细分小波是最常见的四种多分辨率造型方法, 其中小波变换和网格简化是目前最高效的两种方法。近年来, 国内外提出的很多网格简化方法都用在多分辨率三角网格模型生成中, 如Lounsbery等提出的小波分解理论法[2], Rossignac等提的顶点聚类法[3], Schroeder等提的顶点删除法[4], Hoope等提的边收缩法[5], 视点依赖简化法[6]等。顶点删除和三角形删除法简化的速度快, 但这两种方法简化时容易产生网格空洞, 且顶点删除法在低分辨率部分重建时不能保持原有的拓扑结构;边删除法的结果本身就是一种层次结构, 但要确定一个有效的数据结构和存储方式是这类算法的关键, 因为合理数据结构和存储方式直接决定着该类算法的效率、模型重构和拓扑关系的正确性。鉴于此, 又有不少人提出了该类算法的改进算法[7,8]等。纵观上述这些算法, 在构造多分辨率网格时, 判断图元 (点、边、三角形) 取舍的误差测度算法和新图元的生成位置都很复杂, 且难以确定一个合理的数据结构和存储方式。本文提出了一种半边崩溃简化的多分辨率网格生成算法:对原始三角网格先采用区域生长法进行分割后, 以半边崩溃的简化和存储方式对网格的多个区域按比例进行简化以构造多分辨率网格, 用退化三角面片的寿命值作为多分辨率的细节层次。该顶点崩溃算法简单, 多分辨率模型的数据结构是根据简化顺序重新排列的原模型三角形表数据表示的, 故而简单、占用空间小, 各层次细节模型提取用时少。
1 多分辨率网格的表示
网格多分辨率技术是一种将给定的模型逐层分解为高分辨率的细节部分和低分辨率的简单形体过程, 低分辨率部分在某种程度上可以看作是对原始形体的最佳逼近。对模型精度要求较低的部位, 采用低分辨率形体进行逼近, 对精度要求高部位, 通过加入细节信息来得到高精度的形体, 这样在保证视觉效果的前提下可以大大提高模型的处理速度。
1.1 基本的概念
设空间中一组给定的三角形沿公共顶点和公共边相连接构成空间网格, 称其为三角网格, 记为TM。任意一个TM可以表示如下:TM= (V, E, T) , 其中V= (v1, v2, …, vn) 为顶点集, E= (vi, vj) , (i, j∈n, 且i≠j) 为边集合, T= (Ei, Ej, Ek) , (i, j, k∈n, 且i≠j≠k) 为三角面片集。为了描述方便, 给出以下的几个概念:
在TM中, 与顶点vi构成边的所有顶点称为vi相邻顶点, 记为Vv i。
以vi为顶点的三角形称为vi的相关三角形, 记为Tv i。
与三角形Ti具有公共边的三角形称为Ti的相关三角形, 记为TTi。
生长单元:每次区域生长所扩展的图元集。
(1) 边界边:仅属于一个Ti的边, 记为Ef。
(2) 边界顶点:构成边界边的顶点, 记为VEf。
(3) 顶点的重要度:用来衡量顶点对网格模型几何特征的影响程度。
2 三角网格表面区域的分割
三角形网格模型的区域分割原则是: (1) 尽可能分割成大片的连续的区域; (2) 区域间三角形的密度有明显差异; (3) 每个三角形都有所属的区域。常用的区域分割法有阈值方法、梯度检测算子方法、区域生长方法[9,10]等。由于区域生长法可以分割出连续的区域, 因此本文采用该方法对网格模型进行分割。由于三角形网格模型中大片的平滑区域中相邻的三角形的法向量间的夹角较小, 而几何特征明显部分的相邻三角形法向量间的夹角较大。本文对文献[11]中的方法进行了改进, 把传统区域分割中的种子三角形和三角形面片间的夹角相结合, 以三角形间的平坦度作为区域分割的主要依据。
2.1 区域生长分割法的规则及生长条件
本文以三角形作为区域生长算法的种子, 如图1所示, 若T1是区域中的三角形种子, 把与它相关的所有三角形TTi作为将要生长的单元。如果T1与TTi中的某一个三角形TTi间的法向量夹角小于某个给定的值ε, 则将TTi中的这个三角形扩展到T1中。这个夹角越小, 说明两个三角形间越平坦, 否则反之。
生长条件为
式 (1) 中N1、NT i代表三角形T1和TT i中某个三角形的法向量, ε是生长阈值, 它的值是由最初选择的种子三角形T1的所有相关三角形TT i的法向量均值来确定, ε=KN0 (0<K<1) 。因而在不同的区域生长时, 阈值都是不同的, 利用式 (1) 作为生长条件, 有助于模型的特征保持。
2.2 区域分割算法
(1) 计算网格模型中未被扩充的三角形的法矢量, 以其值最大的那个三角形作为区域Ai (i=1, 2, …, n) 的初始种子, 记三角形数目为nAi, 按式 (1) 计算种子三角形与其相关三角形间法向量的夹角θ, 计算该区域的生长阈值ε。
(2) 如果θ<ε, 说明这两个面片间较平坦, 因此将满足条件的三角形扩充到种子三角形区域Ai中, 并给nAi=nAi+1。
(3) 如果网格中所有的三角形都属于某个区域Ai, 则完成分割退出, 否则返回步骤 (1) 继续分割。
3 网格模型的半边崩溃简化
半边崩溃简化[12]操作是边折叠简化的特殊形式, 若一条边 (vi, vj) 半边崩溃到顶点vj, 那么顶点vi要被顶点vj替代, 记为[vi, vj]=vj, 且[vi, vj]被称为崩溃顶点对。该操作最大的优点是原始三角网格的顶点数据和三角面片的数据不会发生改变, 即不产生新的顶点和三角面。使用该方法对模型进行简化构造多分辨率网格, 仅存储崩溃顶点对和模型分辨率即可, 这样可大大降低模型的存储量。本文用顶点重要度对文献[13]中的方法进行了改进, 这样使得对网格模型影响小的顶点被替代, 有助于模型特征的保持。
3.1 区域分割后的简化处理
本文采用崩溃顶点对表示半边崩溃简化操作中的顶点替代关系, 用赋给退化三角面片的寿命值作为多分辨率的细节层次。由于这些崩溃顶点对隐含在原始数据中, 因此构造的多分辨率模型隐含在单分辨率中。用该方法表示多分辨率层次的网格可描述为:假设原始模型经过k次简化后生成最终的简化模型LODk, 赋一个寿命值i给在第i (0≤i<k) 次简化过程中退化的三角形, 将k+1赋给最终在LODk模型中保留下来的每一个三角形, 过程如图2所示。如此, 三角形的寿命值不仅反映了三角形的退化顺序, 还隐含了三角形网格的分辨率层次。按照该方法对原始网格模型进行半边崩溃简化操作, 与原始网格数据相比仅增加了一列三角形寿命值, 与其它多分辨率方法相比节省了很多存储空间。
设以含有7个顶点vi和7个三角面片Ti的网格为初始模型LOD0, 这7个三角形的初始寿命L=0, 假设简化两次达到目的。再设此模型中只有v3、v4为内部顶点, 其余均为边界点, 如图2 (a) 所示来说明本文的简化方法。假设将顶点v3崩溃到顶点v4 (图2 (b) ) , 得到简化模型LOD1, 本次操作替代了一个顶点v3, 退化了一条边 (v3, v4) 和两个三角面片T2、T6, 那么给这两个退化了的三角面片T2、T6赋一个寿命值L=1。若再将顶点v4崩溃到顶点v7[图2 (c) ], 得到简化模型LOD2, 本次操作替代了一个顶点v4, 退化了一条边 (v4, v7) 和两个三角面片T5、T7, 那么给这两个退化的三角面片赋一个寿命值L=2, 给保留下来的三角面片T4、T1、T3的寿命值Life=3。由于崩溃替代具有方向性, 因此由[v3, v4]=v4与[v4, v7]=就可以推出{[v3, v4], v7}=v7, 也就是说, 可以通过L=3这个条件, 直接实现从LOD0到LOD2绘制。当然, 这个性质是可以进一步推广的。若是将边界顶点向内部顶点崩溃[v7, v4]=v4[图2 (d) ], 或者是边界点向边界点[v7, v6]=v6崩溃 (图2 (e) ) , 同样都是替代一个顶点, 一条边, 不同的是前者退化了两个三角面片, 后者只退化一个三角面片T5。比较图2中的 (a) 、 (c) , 不难发现模型的几何形状没有发生太大的改变, 再比较 (a) 、 (d) 或 (a) 、 (e) 就会发现模型间的差异非常大了。为了防止在区域边界上发生崩溃简化操作而引起边界变形和网格空洞的产生, 本文规定边界点不能被崩溃替代。
在确定崩溃顶点对时, 不是任意一条边上的两个点就可以作为崩溃顶点对, 总希望对网格模型影响小的顶点被替代, 而保留下影响大的顶点, 这有助于网格模型的特征保持, 使简化模型最大程度地接近原始模型。使用顶点的重要度作为衡量顶点是否被替代的标准, 对一个顶点vi来说, 它的重要度可定义为
式 (4) 中, NTvj为与顶点vi相关的第j个三角形Tvi的单位法矢量, ATvj为其面积, Nvi为顶点vi的单位法矢量。通过式 (2) 可以看出, Important (vi) 的值是随着顶点vi的法矢量与其第j个相关三角形Tv法矢量间的夹角变化的[见式 (1) ]。当这个夹角变大时, NviNTvj变小, 1-NviNTvj变大, Important (vi) 的值变大, 否则, 反之。Important (vi) 的值越大, 说明顶点vi处越尖锐, 重要度越大;值越小顶点处越平坦, 越平坦就说明该顶点对网格模型的重要度小, 就可以将其用重要度大的顶点来替代。由于三角形网格模型特征区域中含有的三角形数目较多, 平坦区域中含有的数目较少, 要想在简化过程中更好地保持模型特征, 防止个别区域过渡简化, 就要确保不同区域的三角形数量比保持一致。
3.2 半边崩溃算法步骤
本文先采用区域生长法网格模型进行分割, 然后对分割后的区域进行半边崩溃简化操作, 为防止有些区域过度简化, 用区域三角形数目的比值来进行约束, 设Am (1≤m≤n) 为三角形数目最少的区域, 其三角形的个数为nAm, 其他区域的三角形数目为nAi (1≤i≤n, i≠m) , 则为整个曲面化简比值。
(1) 根据式 (3) 、式 (4) 及原始模型给出的顶点信息或法矢量信息计算出网格模型中每个三角形面片的法矢量和面积, 计算出每个三角形各个顶点的法矢量。
(2) 在没有分割的网格区域中, 选取全部三角形中三个顶点法矢量均值最大的那个三角形作为种子, 如果该三角面与其某个相关的三角形Tv的法矢量夹角满足公式 (1) , 则将该相关三角形面扩充到种子三角形区域中, 否则不能扩充。再次选择三角形种子, 进行判断, 直到所有的三角形都属于某一个区域为止。分割结束后, 整个曲面网格模型就被分割成了若干个区域, 记为Filedt (t=1, …, i) , 赋给每个区域一个区域标识Flag, 且Flag=t。
(3) 在分割区域Filedt中, 按照来进行并行半边崩溃化简操作 (即三角形最少区域化简1次, 其余区域则要化简[Ri]次) , 对区域中的某条边 (vi, vj) , 如果顶点vi不是边界顶点, 且Important (vi) <Important (vj) , 那么将顶点vi用顶点vj来替代, 并给退化的三角形赋以相应的寿命值Life=k。
(4) 若一个分割区域中某些顶点的Important (vi) 值都小于给定的阈值δ, 且满足这个比值关系, 则这个区域简化结束, 给这个区域最终保留下来的三角形赋寿命值k+1。若其它区域中还有三角形不满足公式 (4) , 则返回 (3) , 直到所有区域中的所有三角形都满足这个公式模型简化结束。
4 实验结果及分析
4.1 区域生长法对模型的分割
本文实验是在CORE i5 610 M, 内存1 GB的个人计算机上, 先对venus模型 (顶点数为11 121, 面片数22 216) , nefertiti模型 (顶点数为2 504, 面片数为4 952) , bunny模型 (顶点数为34 834, 面片数为69 451) 进行区域分割后进行简化。对venus模型进行分割时, 当K=0.357时, 人体模型被分为10个区域;当K=0.23时, nefertiti模型被分为8个区域, 当k=0.17时, bunny模型被分为23个区域, 这些分割区域相互连通, 之间不存在空洞, 各个分割区域最大化地表现出了模型的基本特征且模型边缘完整, 分割速度快, 能够在1 s时间内分割完毕。分割效果如图3所示。
4.2 半边崩溃法对模型的简化
本文对分割后的venus (半封闭模型) 、nefertiti (不封闭模型) 及bunny (封闭模型) 模型以顶点重要度作为半边崩溃简化的标准, 对模型的各个区域进行简化操作, 如图4所示。将本文方法与传统方法[12]进行比较。图4 (b) 、 (d) 、 (f) 所示为传统方法分别对venus、nefertiti、bunny模型分别进行的简化效果图, 图4 (c) 、 (e) 、 (g) 为利用本文方法对这三个模型进行简化的效果图。
通过比较可以看出, 图4 (f) 、 (g) 这两组图好像没有多大的区别, 这是因为bunny模型是一个几乎完整的封闭网格模型, 边界点很少, 两种方法都能很好地对模型进行简化处理, 达到了较好的简化效果;但通过图4 (b) 、 (c) 和 (d) 、 (e) 这两组图的比较发现, 两种方法都能很好地简化了模型, 但在边缘处, 传统方法明显不如本文方法细腻, 这是因为venus、nefertiti模型不是完全封闭的, 有很多边界点, 而本文算法不对边界顶点做崩溃替代操作, 故而保持了模型的边界式样, 有很好的边界保形效果, 因此, 本文方法适合处理那些不封闭的网格模型。表1为这两种方法的简化数据的统计, 通过其可以看出, 本文方法在时间性能方面比传统方法要好一些, 但在简化相同比例的前提下, 要比传统产生的三角面片多。
4.3 多分辨率网格模型的生成
本文的简化方法多分辨率模型隐含在单分辨率模型里, 因此化简结束后可以通过简化层次直接提取模型的不同细节。若模型的分辨率层次为y (即全部分割网格区域中的三角形最大寿命值) , 要想绘制第y-2层的网格模型, 则将寿命值L≥y-2的三角形全部显示出来即可。图5为从三个原始模型中提取的不同层次 (用life的值来表示, L=0为原始网格模型) 的简化模型。图6给出了三个模型的某几个层次的提取时间的折线图, 从图中可以看出, 若一个模型的下一个细节直接从上一个细节当中提取的话, 会节省不少时间。
5 结论
本文利用半边崩溃简化方法产生多分辨率网格模型。先对网格模型利用种子三角形进行区域分割, 使得模型上具有相近平坦度的三角形都属于某个固定区域, 然后利用半边崩溃的简化方法对模型的多个区域进行化简, 在化简的过程中, 以退化三角面片的寿命值作为多分辨率层次细化的依据, 使得多分辨率层次隐含在单分辨率层次中, 节省了数据的存储空间和模型细节的提取时间。为防止三角形密度少的区域过度化简, 对整个区域采取按比例化简;为防止模型在简化的过程中失真, 则规定边界顶点不能被崩溃替代, 这降低了分割和简化算法的复杂度, 使得整个多分辨率模型在不需要过多存储空间的情况下可以快速实现。
网格自动生成 篇8
1 端面图像预处理
蜂窝陶瓷端面是一个白色蜂窝状的平面图形, 通常以黑色幕为背景, 因此识别算法要处理的是一个平面灰度图像。为消除图像在拍摄和传输中产生的杂质和噪声干扰, 方便后期处理, 需要对原始图像进行预处理。
1.1 图像增强
蜂窝陶瓷生产现场环境复杂, 某些时刻外界光线影响较强, 某些时刻曝光不足, 或者边缘比较暗淡, 拍摄的图像对后续边缘提取和测量存在一定的误差, 因此采用灰度值变换进行图像增强处理。通过增强线性对比度, 边缘清晰度明显增强, 提高了抗干扰能力。本文选择正方形孔型的圆形蜂窝陶瓷进行识别, 图像增强效果如图2所示。
1.2 直方图均衡
直方图均衡化从本质上来说就是构造一个变换函数T, 通过变换函数将原图像的直方图调整为平坦的直方图, 然后用此均衡直方图校正图像, 从而改变图像的特性。直方图均衡化的效果如图3所示。可以看到, 图像直方图均衡方法改变了图像的整体对比度, 较大可能的消除了明暗度对图像的影响, 同时除去了少量的细节部分。
1.3 图像去噪
蜂窝陶瓷端面图像的特征是孔道与孔壁连接部分灰度值变化明显, 因此采用均值滤波算法消除噪声点。采用一个的一个掩码窗口进行遍历, 采用的均值滤波器a.均衡前图像和直方图如式1所示。
与其他滤波方法相似, 滤波时采用了几次平均值, 噪声的方差降低到, 得到了较好的滤波效果, 如图4所示。
2 端面图像的缺陷识别
缺陷识别算法是本系统的关键, 流程如下:对预处理后的图像进行提取边缘, 采用区域生长法求取端面孔道并生成网格图像, 计算网孔面积, 以面积为特征识别缺陷类型。
2.1 边缘提取
通过对多个边缘检测算子进行对比测试, 选择Canny算子作为最适合于蜂窝陶瓷端面图像的边缘检测方法, 将端面图像边缘完整地从背景中区分出来。边缘提取效果如图5所示。
2.2 求取孔道并生成网格图像
经过上述算法的处理, 得到一个已知边缘的灰度图像。在孔道附近的灰度值变化急剧, 灰度值大的像素点是孔道, 灰度值小的是孔壁和边棱。使用区域生长法搜索所有区域, 可以生成一个网格图像。选择某一像素点 (x, y) , 它的像素值G (x, y) 接近黑色点像素值0, 生长准则设计为:
T是一个灰度阀值, 它是根据端面图像灰度直方图中背景区域灰度值与特定区域灰度值之差得到的估值。算法的实现如下:
(1) 从图像的边缘开始进行顺序搜索, 当搜索第一个满足生长准则的像素点, 把该点设置为初始点 (x0, y0) , 创建堆栈, 并将坐标值压入堆栈;
(2) 把 (x0, y0) 当做中心点, 开始第一轮区域生长。搜索其周边4邻域, 当有满足生长准则的点存在时, 将该点坐标 (x, y) 压入堆栈, ;
(3) 从堆栈中取出一个除初始点的像素点作为 (x0, y0) , 执行步骤2;当堆栈为空时, 返回步骤1, 至此, 第一块区域搜索完成。
(4) 重复1-3的步骤, 遍历完图像中的所有像素点, 则生长结束。
最后对网格图像进行二值化, 将已生长区域的像素点灰度值替换为黑色0值, 将非特征区域和边缘外背景像素替换为白色255值。经过区域生长得到了孔道的封闭区域即黑色网孔, 孔壁和边缘变成白色网格, 生成的端面网格图像如图6所示。
2.3 运用网孔面积特征识别缺陷
根据2011年发布的GB/T 25994-2010蜂窝陶瓷国家标准, 端面外观质量缺陷包括表面裂纹、孔道缺陷和边棱缺损, 其中表面裂纹“不允许存在包括端面长度≧8个孔以上的端面裂纹”, 孔道缺陷“在生成过程中引起的产品端面孔道堵塞、并孔及塌陷等缺陷不超过端面总孔数的1%”, 边棱缺损“不允许最大不超过W (50mm) ×r (4mm) ×h (1.5mm) , 每端面不超过3处>1.5mm的缺损”。
分析蜂窝陶瓷端面图像, 发现网格间的独立黑色网孔面积变化明显, 可分为面积偏小黑色网孔、面积规则黑色网孔和面积偏大黑色网孔三类。因此, 选取网孔面积特征进行缺陷分割。设某一独立黑色网孔的面积为, 通过区间判断来定义该网孔的典型特征。面积规则的黑色网孔应该满足:
在网格图像中, 某一独立黑色网孔对应于蜂窝陶瓷端面某一个独立孔道。当孔道堵塞时, 表现出黑色网孔面积偏小;当有并孔或孔壁塌陷时, 表现出黑色网孔面积偏大;当有表面裂纹或边棱缺损时, 表现为黑色网孔严重偏大。因此, 根据式 (3) 对端面所有黑色网孔进行分类, 从而将缺陷识别转化为求取黑色网孔间的数量关系。针对网格图像, 分别统计面积偏小、面积偏大黑色网孔个数, 与面积规则的黑色网孔个数、端面孔道总个数进行比较, 就可以实现端面缺陷的识别, 并直接判断陶瓷端面外观的好坏。缺陷自动识别算法的流程如图7所示。
3 实验效果
针对算法检验的要求, 搭建了端面图像检测装置, 包括工业计算机、面阵CCD相机、图像采集卡、光源和控制器, 如图8所示。图像采集过程为:当待测蜂窝陶瓷到达检测点时, 触发位置传感器, 控制器接收位置信号, 启动位于传送带上方的相机采集一帧顶部图像, 在相机拍摄的同时点亮环形光源。工控机检测软件获得实时图像, 为一张蜂窝陶瓷的端面图。软件运行检测算法进行图像处理运算, 判断当前端面网格图像是否存在缺损, 并在显示器进行结果显示。
以Visual Studio 2010为软件平台进行算法测试。对实际存在端面外观缺陷的蜂窝陶瓷进行识别, 图像处理后的效果如图9所示。图像处理后, 白色网格非常清晰, 网格间黑色封闭区域的面积直接反映了孔道、孔壁和边棱是否完好。从实验可以看出, 基于图像网格特征识别算法的检测系统能有效地识别端面外观缺陷。
4 结论
针对蜂窝陶瓷端面外观缺陷检测要求, 利用面阵CCD相机采集端面图像, 通过图像增强、直方图均衡和均值滤波等处理方法增强图像灰度信息, 采用Canny算子求取图像边缘。在此基础上, 采用区域生长法生成黑色网孔、白色网格的二值化图像, 最后以网孔面积作为特征值对缺陷类型进行判定, 算法取得了良好的识别效果。在图像采集装置的配合下, 可快速、准确进行端面缺陷表面裂纹、孔道缺陷和边棱缺损的缺陷识别, 为蜂窝陶瓷端面外观质量的机器视觉检测打下了基础。
参考文献
[1]刘小云.蜂窝陶瓷载体的孔型结构、性能及其应用[J].佛山陶瓷, 2011 (3) :14-16.
[2]魏泽民, 侯来广.蜂窝陶瓷产品生产过程中废料的产生及再利用[J].陶瓷, 2009 (6) :19-22.
[3]王刚, 谯小华, 杨丽杰.工件偏心距检测方法研究[J].东方电机, 2007[3]:35-38.
[4]刘国栋, 范九伦.一种改进的Canny边缘检测算法[J].微型机与应用, 2011, 32 (22) :32-34.
[5]GB/T 25994-2010.蜂窝陶瓷外观质量标准[Z].中国国家标准化管理委员会, 2011.
网格自动生成 篇9
地下水和溶质在地下的运移过程相当复杂,涉及到气-液-固、热和化学反应、饱和非饱和流动等问题。地下水资源评价和地下水污染防治与管理需要正确了解多相流体中地下水流的运动和溶质的运移,在考虑地下水运动特点的基础上,适当忽略非饱和带水流和气相固相态的运动过程则可大大地将研究问题简化,但很多情况多相流动、饱和非饱和流动不能简化,因此,多相流的数值模拟作为分析水-气-固运动的工具显得尤其重要。
TOUGH2模拟器是多相流模拟软件中最知名、应用最广泛的软件之一,由美国加州大学伯克利分校劳伦斯实验室开发[1,2],它采用积分有限差方法进行空间离散,能进行非等温多组分多相流体数值模拟,可以模拟一维、二维和三维孔隙和裂隙介质中流动,在地下水流、地热、CO2地质封存、天然气水合物等模拟方面应用广泛。其并行版TOUGH2-MP[3]是目前文献中已报道的唯一成功应用于大规模精细模拟(具有几十万到上千万网格的模型)的软件,已成功地应用于多个实际示范和研究工程[4,5]。TOUGH2模拟器的缺点在于它的使用比较困难,需要大量的专业知识和长期的经验才能全面成功应用,本文将针对TOUGH2模拟器应用中最棘手的网格问题提出解决方案,供广大TOUGH2模拟器应用者参考借鉴。
1 已有的网格生成工具评述
TOUGH2从最初20世纪80年代产生到现在,出现了几款网格生成工具,比较代表的程序和软件包括MeshMaker、AMesh、PetraSim、MView和WinGridder等,下面分别进行介绍。
1.1 MeshMaker程序
该网格剖分器最初是嵌在TOUGH2程序中,在后期的TOUGH2版本中,MeshMaker单独成为一个剖分器。它可以将研究区域离散为矩形、同心圆、扇形弧段等网格单元,平面上相邻网格之间的间距可以灵活设置。程序在剖分时还可将不同区域设置为不同的材质代号,方便后期的渗透率等参数的分区赋值,最终程序生成TOUGH2程序运行需要的网格文件,包括ELEME和CONNE数据。正因为MeshMaker程序的这些优点,TOUGH2模拟软件集成了MeshMaker程序,供用户方便进行网格设计。该剖分器对于规则边界和等厚的地质模型具有很好的适用性,但对于不规则边界和复杂的变厚度问题,该剖分器显得无能为力。
1.2 AMesh
它是Haukwa(1999)开发[6]的开放源代码的网格剖分器,能直接生成TOUGH2模拟器运行所需的网格文件。在给定一些点信息或泰森多边形的中心,它可以生成一维、二维和三维网格。缺省的输入文件为IN文件,输出文件包括ELEME、CONNE和SEGMENT文件,前两个输出文件可直接作为TOUGH2模拟器的网格文件,后一个文件可用于后处理的制图。它没有可视化的用户界面,操作起来比较困难。
1.3 PetraSim
PetraSim是用于TOUGH2模拟程序家族的具有图形化界面的商业软件。它以交互式3D环境,包括网格剖分,参数定义和结果展示,使建模者方便应用TOUGH2模拟器的功能。软件集成网格生成、网格和单元格编辑等功能,可自动生成模型的输入文件,操作起来方便,目前版本只能处理规则边界,而且价格昂贵。
1.4 MView
MView软件最初是由Intera公司针对尤卡山(Yucca Mountain)项目开发的TOUGH等系列数值模型前后处理和可视化操作界面,后来扩展到MODFLOW等软件中,集成了钻孔编录、物探、采样分析等野外数据的分析。MView软件目前已成为一款商业化的数值模拟支持系统,包括数据分析和复杂地质数据可视化等功能,包括TOUGH2模拟器的前后处理和可视化工作。
1.5 WinGridder
WinGridder是Pan开发的基于视窗操作系统的网格剖分软件[7],它提供了有效的、友好的界面,集成了网格处理软件,能处理单一连续体和双重连续体。它首先在图形界面下将研究区域划分为二维网格,然后将裂隙和局部区域细化,再拓展为三维网格。输入文件包括域范围、地质层、岩石属性、裂隙和钻孔信息,由基础信息划分网格。软件价格昂贵,而且不容易学。
由上述分析可知,商业软件价格昂贵,而且学习困难。共享软件大多数功能仍不齐全,有必要进行对网格生成进行改进。
2 基于多边形网格的网格生成方法
TOUGH2模拟器的网格可以是任意的,只要按照模型输入文件格式给出网格单元的体积和中心点(图1)。图1(a)和图1(b)显示了典型的TOUGH2模拟器的垂向和平面上网格关系,即必需要知道相邻单元的接触面积和侧面面积等信息。从相邻单元接触面关系来看,很容易想到依据泰森多边形来划分单元,而将研究区域离散为多个三角形网格,然后按照三角形形成泰森多边形,再展开就成为多边形网格,则可满足TOUGH2模拟器网格的特点。TOUGH2模型运行的网格包括ELEME单元和CONNE连结信息,单元可以为5或8字符命名,文件具体格式按固定的输入格式进行如表1所示。
2.1 平面三角网格的生成
对于二维平面三角网格自动生成,从20世纪70年代开始,国内外学者[8,9,10]做了大量的研究,相关技术相当成熟,有Delaunay法、波前推进法、正规法、向量偏移法、有限四(八)叉树法等等。Delaunay法因为方法简便,对于带约束条件的三角剖分更显得灵活自由,同时容易编程实现,适合作为区域三角剖分的方法,然而目前的方法仍不能较好地考虑相邻单元的垂心在单元内,即保证三角形为非钝角三角形。笔者曾对带约束的任意多边形Delaunay三角剖分算法进行了改进,基于结点尺度设计,提出了一种简单的平面区域结点尺度自动确定的方法,在三角单元形成过程中,特别地考虑了三角形状的自动修正和编辑问题[11]。而且大多数有限元软件都有平面三角形网格生成的功能,可完成区域的离散化工作。图2(a)显示了由三角形网格转换为多边形网格的转换。
注:A为字符变量,X为空格,I为整型变量,E为实型数
2.2 多边形网格数据的存储格式
平面上,多边形网格的数据存储信息包括:(1)点信息,为多边形每个顶点的坐标信息,包括x,y,z方向坐标值;(2)每个顶点的侧边结点总数,简记NPSD;(3)每个顶点的侧边结点序号,简记MPSD。而三角形网格的数据存储信息只需要:(1)点信息;(2)组成三角形的各个结点序号及按逆时针排序,即IJK信息。NPSD为一个结点周围的结点总数,MPSD为一个结点按逆时针排列的侧边结点序号,一个多边形由一个NPSD及对应的MPSD组成。NPSD和MPSD的数据信息可由三角网格的IJK结点拓补结构生成。
对于NPSD和MPSD信息的生成,先判断此结点是内结点还是边结点,判断的方法就是按照含此结点的三角形个数与含此三角形的边的个数是否相等,如果两者相等,说明此点为内点;不等则说明此点为边点。如图3(a)所示,对于内结点,先找到一个含此点的边和三角形Ep7,设给定点结点号为O,此边的另一结点号为P1,找到的三角形结点顺序号和OP1序号相应,将边的另一结点号P1作为起始结点序号,对于Ep7单元的结点号P1,设此单元的最后一个结点号为P2,找到与它对边相邻的单元号Ep1,然后将P2作为序列号的第二点;依照这样的方法,找到P3,P4,P5,P6,P7结点号。对于内结点,结点号封闭,此结点的最终Mpsd序号为P1P2P3P4P5P6P7P1。
对于边结点,可采用类似的方法,不同的是先找起始点时,先找到边的一点,如图3(b)所示,有两个边点,P1和P7,对于含O和P7的单元,其单元另一结点号为P6,要求OP7P6逆时针排列,如不是逆时针排列,说明这一点不是要找的边序号起点,从图中可以看出,OP7P6不是逆时针排列,P7不能作为边结点O的起始点;相反,对于P1点,OP1P2逆时针排列,说明P1正好是边结点O的起始点。
平面上生成的多边形网格单元数与结点总数相同,其编号则按结点号编号。垂向上,每层的网格保持相同,按从上层到下层排序,下一层单元编号则在上一层单元编号加上单元总数。而每个单元的平面面积、总体积与相邻单元的接触面积可由图2(b)中的关系计算而成[12],则可生成ELEME和CONNE的单元、面积等信息。
2.3 参数分区及数据生成
模型仍需要介质参数分区文件及辅助的数据生成,可根据介质的水力性质对其进行分区,需要考虑不同岩性的参数分区情况。在介质分区信息生成过程中,设计的分区信息生成的方法是按结点赋值,即在一个封闭的多边形内的结点可统一赋成一个分区号,这些点形成的泰森多边形即为这些点控制的分区区域,离散化的边界只能逼近实际边界,设计的算法是符合TOUGH2模拟器数值计算要求的,如图4所示。
(虚线区域为参数区,灰色区域为格点形成的参数分区)
3 方法的应用
为说明方法的正确性,以北京市平原区地下水流数值模拟为例,将多边形网格生成方法应用于模型中。按照研究区主要水文地质条件以及考虑到实际收集地下水监测信息的代表性[13],将研究区划分为6层水文地质结构,分别为种植土层弱透水层、潜水含水层(砂砾石)、弱透水层(砂粘土、粘土)、第一承压含水层(砂土)、弱透水层(粘土等)、第二承压含水层(砂土),取第四系底为模型底边界。根据已有的钻孔信息,已获知每一模拟层的厚度。
平面上先以北京市平原区为外边界,包括河流、抽水井和观测井点,利用三角网格剖分器或有限元软件FEFLOW[14]将区域离散为多个三角形,然后再通过钝角修正,确保泰森多边形的结点为三角形网络的垂心在三角形之内。平面上离散的泰森多边形为7620个单元,在模型感兴趣重点模拟处进行加密剖分。每个模拟层的网格保持一致,位于地面的多边形网格高程即由已知点的高程信息数据插值而成,插值可借助SURFER软件完成,其它各个模拟层的结点高程也可由上一层结点的高程和该层已知点的厚度信息插值生成,多边形网格实体模型即已完成。
参考北京市多年的地下水研究的水文地质资料可获得每一层水文地质结构的水文地质参数分区信息,以顶层为例,说明参数的生成方法,参数分区如图5所示。结点的数据生成可借助ARCGIS信息平台完成,即对每个分区建立区文件,位于区文件之内的结点赋给对应的岩性分区号;然后对于其它模拟层也采用同样的方法,对于统一的岩性分区给定同样的标识号,在生成ELEME信息时可给出每个结点的岩性分区号,多边形网格和参数分区如图6所示。
(1、2、3、4分别代表种植土、粘泥和黑泥土、细砂土、种植土层和水泥土)
网格及对应参数分区(数字为分区号)
4 结论
TOUGH2模拟器作为强有力的多相流模拟软件,困难的网格生成方法影响了TOUGH2模拟器的方便快捷应用,本研究提出了新的网格生成和参数分区方法,即在三角形网格的基础上,先将三角形转换成多边形网格,然后再利用地理信息系统软件进行参数分区的结点赋值,再利用统计软件SURFER将已知点的高程和厚度信息扩展到模拟层的结点,完成了TOUGH2模拟器运行需要的ELEME和CONNE数据信息。整个过程笔者已在VISUAL C++平台上完成数据生成的集成处理,利用该程序可方便快捷生成网格。本文提出的方法适用于已有三角网格或将研究区域离散为多个三角形的情形,对于四边形或同心圆网格,则需将其转换为三角单元网格方可转换。另外对于三维模型中含孔洞或隧道的剖分问题,需要基于已有的三维网格和剪裁区域进行剪切,本文没有进行深入讨论。
摘要：针对TOUGH2模拟器网格数据较难生成的特点,在总结分析已有的网格生成工具的优缺点基础上,介绍了基于多边形的网格生成方法。该方法先将研究区离散为多个三角形网格,再将其转化为多边形网格。基于水文地质参数分区和地理信息系统软件,可生成各结点的水文地质参数分区信息,再利用统计软件将已知点的高程和厚度信息扩展到模拟层的结点,最终可生成TOUGH2模拟器需要的网格输入文件。以北京市平原区网格生成说明了方法的合理性。这些成果为TOUGH2模拟器的推广应用提供了参考,并将提高TOUGH2的使用效率。