（计算数学专业论文）带边三角网格曲面的四边形分割.pdf

大连理工大学硕士学位论文 摘要 近年来，随着计算机技术的飞速发展，有限元方法已经成为复杂工程问题求解中最 强大的数值分析方法之一。而使用该方法的第一步，就是对给定目标区域的离散，即网 格的生成另外，数值模拟结果的准确性和分析速度都直接受到网格质量的影响，所以 研究高质量网格的快速生成，对数值模拟技术而言，具有非常重要的意义 有限元中常用的两种平面或三维曲面网格是三角形网格和四边形网格，其中四边 形网格无论是在计算精度上还是在收敛速度上，都要优于三角网格尽管三角网格被广 泛的应用于计算机图形学中，但是在很多实际应用也需要四边形网格，例如流体动力 学中的p d e ( p a r t i a ld i f f e r e n t i a le q u a t i o n ) 问题，图形处理( 包括分析、比对、修改) ， 几何设计( 包括逆向工程) 以及细分曲面等因此从上个世纪八十年代四边形网格生成开 始受到人们的重视通过很多工程技术人员和学者的不懈努力，涌现出了大量有关四边 形网格生成的方法 本文首先对四边形网格的发展现状做了一个简单的综述，同时介绍了几种比较典 型的四边形网格生成方法随后介绍了网格质量的评价准则，定义限制条件，并说明了 提出这种限制的合理性据此，本文提出了对亏格为g 边界为h 的三角网格曲面在拟正 则条件和适当条件的限制下的四边形分割对于一个给定的三角网格，先将曲面分割成 柱面和裤子面的并，然后分别将柱面和裤子面分割成四边形，最后构造出整个网格曲面 的四边形分割且满足得到较少的四边形的片数，片数大约为一个固定常数的2 倍在文章 最后给出双环面四边形网格生成的数值实例 关键词：四边形分割；带边三角网格；柱面；裤子面；限制条件 带边三角网格曲面的四边形分割 q u a d r a n g u l a t i o no v e rt r i a n g u l a rm e s h e sw i t hb o u n d a r y a b s t r a c t i nr e c e n ty e a r s ，w i t ht h ef a s td e v e l o p m e n to fc o p m u t e rt e c h n o l o g y ，t h ef i n i t ee l e m e n t m e t h o d ( f e m ) h a sb e c o m eo n eo ft h em o s tp o w e r f u la n a l y s i st o o l si ns o l v i n gc o m p l e x e n g i n e e r i n gp r o b l e m s w h i l et h ef i r s ts t e po ft h em e t h o di st h ed i s c r e t i z a t i o no ft h eo b j e c t r e g i o n ，i e t h eg e n e r a t i o no ft h em e s h i na d d i t i o n ，t h er e s u l to fn u m e r i a ls i m u l a t i o na n dt h e s p e e do f t h ea n a l y s i sa r es t r o n g l yr e l a t e dt ot h eq u a l i t yo f t h em e s h t h e ni ti sv e r yi m p o r t a n tt o s t u d yt h ef a s tg e n e r a t i o no fh i g h t q u a l i t ym e s hi nt h en u m e r i c a ls i m u l a t i o nf i e l d at r i a n g u l a rm e s ha n daq u a d r i l a t e r a lm e s ha r cc o m m o n l yu s e df o r2 dp l a n ea n d3 d c u r v e ds u r f a c ei nt h ef e m q u a d r i l a t e r a lm e s hi ng e n e r a lh a sb e t t e rp r e c i s i o na n dc o n v e r g e s f a s t e rt h a nt h et r i a n g u l a rm e s h a l t h o u g ht r i a n g u l a rm e s h e sh a v eb e e nw i d e l yu s e di nc o m p u t e r g r a p h i c sc o m m u n i t y ，q u a d r i l a t e r a lm e s h e sa r em o r ed e s i r e di ns o m ea p p l i c a t i o n s ，s u c ha sp d e ( p a r t i a ld i f f e r e n t i a le q u a t i o n ) p r o b l e m si nh y d r o k i n e t i c s ，i m a g ep r o c e s s i n g ( i n c l u d i n ga n a l y s i s ， c o m p a r i s i o na n dm o d i f i c a t i o n ) ，g e o m e t r yd e s i g n ( i n c l u d i n g r e v e r s ee n g i n e e r ) a n dt h e s u b d i v i s i o ns u r f a c e ，e t c t h e r e f o r e ，l o t so fe n g i n e e r sa n ds c h o l a r sh a v ea t t a t c h e dg r e a t i m p o r t a n c eo n t h eq u a d r i l a t e r a lm e s hg e n e r a t i o ns i n c et h e19 8 0 s al a r g en u m b e r o f a p p r o a c h e s h a v eb e e np r o p o s e di nt h i sf i e l d i nt h i sp a p e rw ef i r s t l yg i v eas i m p l es u r v e yo ft h ed e v e l o p m e n to ft h eq u a d r i l a t e r a lm e s h g e n e r a t i o n a n dt h e ns e v e r a lt y p i c a lq u a d r i l a t e r a lm e s hg e n e r a t i o na p p r o a c h e sw i l l b e p r e s e n t e d a f t e rt h a t ，w ei n t r o d u c et h ep r i n c i l p e so fm e s hq u a l i t y ，t h ed e f i n i t i o no f c o n s t r a i n e d c o n d i t i o na n dt h er a t i o n a l i t yo ft h ed e f i n i t i o n a c c o r d i n gt ot h i s ，w ep r o p o s eam e t h o dt o r e m e s ht r i a n g u l a rm e s h e sw i t hgg e n e r aa n dhb o u n d e r i e si n t oq u a d r i l a t e r a lm e s h e su n d e rt h e c o n s t r a i n e dc o n d i t i o n s g i v e na t r i a n g u l a rm e s h e s ，w ef i r s tp a r t i t i o nt h es u r f a c ei n t ot h eu n i o n o f c y l i n d e ra n dp a n t s ，a n dt h e np a r t i t i o nc y l i n d e ra n dp a n t si n t oq u r d r a n g l e si n d e p e n d e n t l y t h e f i n a lq u a d r i l a t e r a lm e s hi sg e n e r a t e dw i t ht h en u m b e ro ft h eq u a d r a n g l ea b o u tt w i c eo fa c o n s t a n t a tt h ee n do ft h ec h a p t , n u m e r i c a lt e s to fq u a d r a n g u l a t i o no f d o u b l et o m si sg i v e n k e yw o r d s ：q u a d r a n g u l a rr e m e s h i n g ；t r i a n g u l a rm e s h e sw i t hb o u n d a r y ；c y l i n d e r ； p a n t s ；c o n s t r a i n e dc o n d i t i o n 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意 若有不实之处，本人愿意承担相关法律责任 学位论文题目：整堕三鱼旦丝堕垂鱼咝亟复勤 作者签名：墓兰日期：盟虹月j 生日 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅学校有权 保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将本 学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印、或扫描等复制手段保存和汇编本学位论文 学位论文题目： 鲎丝三鱼璺丝! 竺鱼鱼竺壁型复勤 善糍；乏一篡墨竺圭詈 大连理工大学硕士学位论文 1 绪论 1 1网格以及其应用背景 网格化是2 0 世纪下半叶兴起的一项新技术n 2 】，网格化是指将一个几何区域离散化 为一些简单的几何形状，如二维中的三角形和四边形，三维中的四面体和六面体三角 网格又称非结构化网格( u n s t r u c t u r e dm e s h ) ，具有复杂域逼近效果好，易于密度控制以及 细分和缩减的特点目前已有许多成熟的三角形单元网格的生成算法，如d e l a u n a y t r i a n g u l a t i o n ，c o n s t r a i n e dd e l a u n a yt r i a n g u l a t i o n _ ；f d q u a d t r e e s 四边形网格又称结构化网 格( s t r u c t u r e dm e s h ) ，它结构简单，计算效率高，占用计算机资源少，它的生成算法虽 已有许多，但由于网格本身拓扑关系的特殊性，生成时单元之间互相限制，对复杂区 域的适应性差，自动化程度不高 随着计算机技术的飞速发展，网格化在数值模拟、有限元技术中起到越来越重要 的作用，已广泛地应用于各领域例如在地形显示中，它可以给出复杂地形的简洁表 示；在计算机图形学中，几乎所有的物体在渲染前都会转为网格表示形式，从而加快 其渲染速度：各种物理和工程问题，如热传导、电磁场、固体力学、流体力学等均可 用一组偏微分方程( p a r t i a ld i f f e r e n t i a le q u a t i o n s ) 的形式加以描述，用有限元法( f i n i t e e l e m e n tm e t h o d ) 迸行求解，而网格可以提高其求解精度和速度网格化是建立有限元模 型的一个重要环节，也是制约其进一步发展的主要因素之一它要求考虑的问题较多， 需要的工作量较大，最终的网格质量( 单元数量、网格疏密、网格几何质量) 对计算精度 和计算规模将产生直接的影响在二十世纪七十年代，网格是在方格纸上人工绘制得 到，因而有限元方法也仅限于分析形状简单的结构；随着计算机的发展，到了八十年 代，人们运用计算机图形技术生成网格；直到最近，提出了许多非结构化网格生成技 术，大大减少了人力耗费但网格在生成过程中仍需要人为干预，因此如何快速、全自 动地生成高质量的有限元二维和三维网格仍是当今有限元建模技术的研究热点之一 1 2 网格的类型 在工程应用中，有限元网格主要有两种：一种是结构化网格( s t r u c t u r e dm e s h ) ， 另一种是非结构化网格( u n s t r u c t u r e dm e s h ) 从严格意义上讲，在结构化网格中，所有内部节点都有相同数量的邻近节点和相 同数量的邻近单元，即所有的内部节点都具有相同的度在平面和空间曲面网格生成 中，有代表性的结构化有限元网格是由四边形单元构成的网格在三维实体网格生成 中，有代表性的结构化网格是由六面体单元构成的网格在结构化有限元网格生成方法 带边三角网格曲面的四边形分割 中，映射法是典型和通用的方法，它既可以被用来生成结构化的四边形单元网格，也 可以被用来生成结构化的六面体单元网格 结构化网格的优点是：它可以很容易地实现区域的边界拟合；网格生成的速度 快，质量好；数据结构简单它的最大的缺点是适用的范围比较窄，对于比较复杂的区 域或者物体表面很难生成高质量的计算网格目前高效的全自动结构化网格生成方法还 正在研究当中 在非结构化网格中，对节点放松了要求，允许任意数量的单元在一个节点处交 汇，即所有内部节点的度都可能不同在平面和空间曲面的有限元网格生成中，非结构 化有限元网格的典型代表是三角形网格在三维实体有限网格生成中，非结构化有限元 网格的典型代表是四面体网格 非结构化网格生成方法的一个突出的优点是它可以适应任意复杂的几何形体，与 几何形体的形状关系不大结合一定的控制方法，可以生成质量很高的单元，而且利用 非结构化网格生成算法可以实现区域网格生成的自动化 值得一提的是，三角形单元和四面体单元并不是非结构化有限元网格的唯一选 择，由四边形单元或六面体单元构成的有限元网格只要节点的度有所不同，此时的有 限元网格仍然是非结构化网格 1 3 四边形网格的应用 随着计算机技术的发展，网格的生成在有限元、几何设计以及图形图像起着关键 性的作用常用的网格有三角形网格和四边形网格两种形式三角形网格易于实现，但是 编辑修改困难，存储和传输量都很大近年来越来越多的技术人员提出了基于二维流形 的四边形分割技术四边形分割方法更加有效的简化了曲面，在有限元、几何设计、反 向工程和计算机图形图像中等方面有着重要的应用 有限元是工程界应用最为广泛的一种数值模拟方法，划分网格是建立有限元模型 的一个重要环节，且所划分的网格形式对计算精度和计算规模将产生直接影响因此， 通用性强、自动程度高且能产生高质量网格的方法对有限元计算来说非常重要，它不仅 关系到有限元计算是否能成功地进行到底，而且对计算的精度也有很大的影响，因此 必须选择合适的方法对计算区域进行更加合理的划分以前工作集中在对计算区域的三 角形网格的划分上面，但是三角形网格划分在很多的时候会产生退化的情形而四边形 分割的方法能够更好的对计算区域进行划分，使得划分所生成的四边形片较少，角度 比较均匀，且不容易产生狭长的地带 大连理工大学硕士学位论文 在几何设计方面的应用主要表现在几何模型的生成技术、数字几何处理等方面， 例如n u r b s 模型、3 d s 模型等等由于具有构造灵活、适应性强等特点，三角形网格已 成为散乱数据点集网格重建的主流，但是对三角形网格进行c a t m u l l c l a r k 细分的时候 可能会得到不可预见的不规则网格另一方面，若对三角形网格采用l o o p 等模式细分， 则会产生大量的三角形网格三角网格模型没有固定的拓扑结构，对顶点数量巨大、结 构复杂的三角网格模型要进行整体的光滑样条曲面拟合十分困难而四边形分割则具有 固定的拓扑结构，从而在细分过程中得到可预知的结果构造参数域、规范化映射与基 函数的基本方法，可以在优化后得到规则的四边形分割因此四边形分割的提出，对数 字几何处理，几何模型的构建起着关键的作用 反向工程，是国内外近几年随着c a d c a m c a e ( 计算机辅助设计席8 造压程) 的 迅速普及而发展起来的崭新的信息科学领域实际工程中经常需要将物理实体转化为数 字模型，以便用计算机进行处理实现这一过程的科学方法，就是所谓的反向工程反 向工程在娱乐、工业设计和加工、医学、仿真与虚拟现实及网络等领域具有广泛的应 用反向工程有两个主要的研究内容：一是实物模型表面数据获取技术；二是曲面重构 技术目前，反向工程的处理过程可以大致分为以下几个主要步骤： 1 提取样本点 2 由点云形成多面体模型( p o l y g o nm o d e l ) 3 形成( 空间) 四边形剖分( 四边形的边不必是直线) ，即将多面体模型分解为 满足一定条件的( 空间) 四边形的并，进一步将其适当参数化 4 在第3 步的基础上形成n u r b s ( 非均匀有理b 样条) 曲面模型 从而四边形分割在反向工程中起着关键的作用，它是进行参数化以及形成曲面模型的基 础 四边形分割技术作为计算机图形学应用( 如细分，纹理映射、网格变形、数字几何 处理等) 的关键技术，一直是计算机图形学的一个重要研究方向，也是目前图形学领域 内的研究热点之一目前已经有了大量的研究成果，但是不完善不成熟，具体应用的软 件不多三角网格通常是由3 d 扫描仪获取复杂表面采样点的几何信息，并通过拓扑重建 得到在三角网格模型上建立四边形分割会使计算机图形得到简化随着计算机图形显示 对于真实性、实时性和交互性要求的日益提高，曲面分割在网格细分和纹理映射中备 受关注，在曲面四边形分割可以利用低层到高层网格的变化规律，只需存储一个简单 的初始网格和若干细分规则，有利于网格的分层采集、分层编辑和分层传输目前对细 分曲面的研究已有诸多成果，但是让细分曲面融入造型系统依然还有大量工作要做纹 理映射的主要思想是将一给定的纹理函数映射到物体表面上，在对物体表面进行光亮度 带边三角网格曲面的四边形分割 计算时，可采用相应的纹理函数作为物体表面的漫反射光亮度代入光照模型进行计算 纹理映射涉及纹理空间、景物空间和屏幕空间3 个空间之间的映射，四边形分割会使得 纹理映射的得到优化，对物体模型的交互式，仿真都得到很好的发展 1 4 本文的主要工作综述 本论文主要在下述几个方面进行了相关的研究和讨论： ( 1 ) 综述四边形网格分割的研究现状 本论文首先分析了四边形网格分割的研究现状，对目前几种主要的方法进行了简 要的介绍和总结，分析了各种算法的优缺点 ( 2 ) 拟正则条件和适当条件的定义 介绍了四边形网格质量的判定准则，分别从拓扑准则、几何准则以及组合最优的准 则等进行深入的讨论，给出限制条件定义的合理性 ( 3 ) 提出了一种在限制条件下带边三角网格曲面的四边形分割的方法 在拟正则条件和适当条件的限制下，给出了一种四边形分割的方法这里的分割得 到的四边形的片数较少大约是一个固定常数的2 倍先将曲面分割成柱面和裤子面的 并，然后再分别将柱面和裤子面分割成四边形，最后构造出整个网格曲面的四边形分 害1 1 大连理工大学硕士学位论文 2 四边形网格分割方法的介绍 2 1四边形网格生成方法综述 前面我们已经提到，四边形网格的生成从上个世纪八十年代以后逐渐成为人们研 究的热点经过国内外无数学者和工程技术人员的共同努力，涌现出了很多算法按照 生成原理大致可以分为直接方法和间接方法下面我们就从这两方面对国内外四边形网 格生成的研究进展进行简单的综述 2 1 1 直接方法 直接方法就是在给定的几何区域上直接生成四边形网格，直接方法按照网格的生 成过程大致可以分成两大类： 第一类方法是几何分解法，即把一个区域分解成一些简单的凸子区域或者是可映 射的子区域，然后在这些子区域上生成四边形网格b a e h m a n n 阳1 等人首先把四又树方法 应用于区域分解，在经过初始分解后，根据区域局部的情况将二维空间分解成一棵四叉 树四边形网格在各叶子节点生成，调整节点位置使其可以更好地拟和边界t a l b e r t 和 p a r k i n s o n h 3 等人随后又引入了另外一种分解技术，将区域递归地分解为简单的多边形区 域，当这些多边形满足一定的模板时，就可以通过剖分这些模板来实现整个区域的四 边形网格生成，且p l o o p i n g 方法国内刘阳璩3 借用p a v i n g 算法的边界拟和好的优点在边界 处生成一圈单元来改善l o o p i n g 方法生成网格在边界处的质量郭晓霞等人一1 对该方法 生成四边形网格中的边界偏移、最优分割线确定等关键技术作了改进t a m 随1 等人则引入 了中轴( m e d i a la x i s ) 技术这类方法可以生成全四边形网格，网格质量也比较高，但是 需要较多的人工干预，自动化程度不高 第二类方法是利用推进前沿技术( a d v a n c i n gf r o n tt e c h n i q u e ) ，即从边界开始向 内部逐个或逐层生成四边形网格z h u 仁等人阳3 是最先把该技术应用到四边形网格生成的 学者之一该方法首先在边界上布点，然后利用边界向内部投影的方法生成三角形网 格，每生成两个三角形网格就将其合并，从而得到一个四边形网格但是该方法得到的 四边形质量缺乏保证，因为两个高质量三角形单元合并以后得到的四边形单元质量并 不一定好“训该方法中最著名的要数b l a c k e r 等人n 妇的p a v i n g 方法，即从区域边界向内部 逐个生成四边形单元，在网格生成过程中要不断进行冲突检测，交叉和特殊情况的处 理直至生成全四边形网格该方法生成的网格具有边界敏感性和方位不敏感性的优点， 并且能极大地减少网格中的不规则点但是当目标区域边界非常复杂时，很容易出现大 量交叉，而交叉判断和处理既复杂又耗时，处理不好还会造成算法的不稳定c a s s 和 带边三角网格曲面的四边形分割 b e n z l e n 羽则将p a v i n g 方法推广到3 d 曲面的情形随后w h i t e 和k i n n e y n 加又通过每次生成 一行单元而非逐个单元生成，以提高算法的稳定性p a v i n g 方法目前已经被应用在一些 商用软件中，如m s cp a t r a n ，f l u e n t sg a m b i t 仁n 钉等 2 1 2 间接方法 间接方法就是首先在给定的几何区域上生成三角网格，这可以利用任何一种已经 很成熟的三角形网格生成方法，如d e l a u n a yt r i a n g u l a t i o n ，a d v a n c i n gf r o n t t e c h n i q u e 等，然后再将该三角网格转化为四边形网格此类方法主要有简单拆分方法 和合并法 拆分方法如图2 1 所示，就是取每个三角形的重心和三边中点的连线把每个三角形 分成三个四边形该方法虽然实现了全四边形网格的自动生成，但是由于产生了大量度 为三的不规则节点，因此最终得到的网格质量很差 图2 i 简单拆分法 f i g 2 1 t h em e t h o do f s i m p l es p l i t t i n g 另一种方法就是合并法如图2 2 所示，即将两个或多个相邻的三角形合并成一个四 边形l o 明首先给出了一个简单的合并方法，得到了一个既有三角形网格又有四边形网 格的混合网格j o h n s o n n 6 1 等人通过引入局部网格的拆分( s p l j t t i n g ) 和交换( s w a p p i n g ) 策略来进一步提高四边形的数量和质量l o 和l e e u 刀则通过引入系统合并技术 ( s y s t e m a t i c a lm e r g i n gt e c h n i q u e ，s m t ) 来生成全四边形网格结合s m t 和p a v i n g 方法， o v e n 等人n 羽提出了全四边形网格自动生成的q - m o r p h 方法，该方法是目前间接方法中最 好的一个，并被应用在商用软件中，如f e a 等l e ey k 和l e ec k u 吼2 0 1 给出了各向异性四边 形网格的生成国内阂卫东瞻订等人计算每条非边界边被删除后所形成的四边形的0 值， 将其作为该边的权值然后每次删除权值最大的边，这样得到了一个收敛速度为线形的 大连理工大学硕士学位论文 分级合并算法然而最后得到的网格是四边形与三角形的混合网格顾元宪n 们等人通过 改进网格生成的布点方法，首先生成三角形网格，然后再将其转化为四边形网格由于 在生成三角形网格时就考虑到了将来得到的四边形的质量，因此可以提高生成四边形 网格的质量，但网格质量仍然有待提高赵熠陋：，等人针对传统前沿方法的缺点提出了泛 前沿侧的概念，即对前沿概念的更高层次上的抽象，不但避免了前沿拆分和合并带来 的不稳定，而且使得前沿操作起来更简单有效但是最后仍然有一些残余三角形，需要 通过移动和拆分来处理不但增加了算法的复杂性，而且也影响了网格的质量胡向红 比3 ，等人则提出了区域增长算法 图2 2 合并法 f i g 2 1 t h em e t h o do fc o r n b i n a t i o n 间接方法由于所有操作都是局部的，不像有些直接方法那样需要进行全局交叉检 测，因此网格生成速度很快结合了比较成熟的三角网格生成方法，可以实现对任意复 杂区域的四边形网格生成缺点是有很多不规则节点产生，而且即使不规则节点很少时 也不能保证具有很好的边界拟和性，而这在有些应用中是很重要的因此网格的质量不 如直接方法好，需要通过一些额外的优化方法来提高其质量 总之，通过上述简单的综述我们可以看出：直接方法和间接方法各有优缺点，因此 四边形网格生成方法与比较成熟的三角形网格生成方法相比，还有很长的路要走这需 要无数工程技术人员和学者的不懈努力 2 2 主要方法介绍 下面我们对四边形网格生成中的一些典型算法进行简单介绍 带边三角网格曲面的四边形分割 2 2 1 m a p pin g 方法 映射法又称为参数变换法，是研究最早也是比较成熟的一种网格生成方法它的主 要思想是将具有一定拓扑关系的区域变换为规则区域，在规则区域中利用线性或二次 捅值划分网格，再把规则区域的节点通过逆变换生成对应的空间节点，同时保留节点 间的拓扑关系，如图2 3 所示该方法的关键技术就是映射函数的选择映射法又分为映 射单元法( m a p p e de l e m e n ta p p r o a c h ) 和保角映射法窿钔( c o n f o r m a lm a p p i n ga p p r o a c h ) 早期的映射单元法要求将目标区域手工分成许多有利于映射操作的简单子域现通常用 所谓超映射技术来获得过渡比较光滑的网格保角映射法能直接处理单连通问题，但是 因为该法难于控制单元形状和单元密度，所以很少采用 图2 3m a p p i n g 方法生成网格 f i g 2 3g e n e r a t i n gm e s h e sw i 廿lt h em a p p i n gm e t h o d m a p p i n g 方法的优点在于在每一子域内网格生成可以得到相当好地控制，能够用以 进行曲面网格的生成，得到的网格质量也比较高但其最大的弊端在于要求事先根据所 要产生的网格类型将目标域分割成一系列可映射的子区域而这一工作通常需人工来完 成，因而自动化程度低，不适合四边形网格的自动生成 2 2 2 基于栅格方法 基于栅格法乜明( g r i d - b a s e da p p r o a c h ) ，又称反p a v i n g 方法，该方法首先将一完全 包含目标区域的正则栅格( 一般为矩形) 放置在目标区域上面，除去落在目标区域之外 的栅格单元，并对与物体边界相交的栅格单元进行调整或剪裁以便更准确地逼近目标 区域，再将这些栅格单元按一定的样式分成一定数量的网格单元，之后通过光滑技术 处理即得到最后的网格该方法分为以下几步： ( 1 ) 用均匀矩形网格覆盖图形，如图2 4 ( a ) 所示 大连理工大学硕士学位论文 ( 2 )只保留在图形内部的栅格，而将在图形之外的及与图形相交的栅格删除， 如图2 4 ( b ) 所示 图2 4 f i g 2 4 ( 3 ) 对外部边界和内部栅格边界之间的缝隙进行d e 1 a u n a yt r i a n g u l a t i o n 如图 2 4 ( c ) 所示然后对一些三角形网格进行合并，如图2 5 ( a ) 所示最后将每 个残余的三角形拆分成三个小四边形，为了保持网格的相容性，需要对一 些相邻的四边形进行处理，如图2 5 ( b ) 所示 图2 5 f i g 2 5 d 带边三角网格曲面的四边形分割 ( 4 ) 对需要网格密集的区域进行加密处理，如图2 5 ( c ) 所示 ( 5 )局部光滑处理，如图2 5 ( d ) 所示 该方法生成的栅格越密，所得网格质量将越好对于生成大量网格，其效率一般也 要高于其他方法，如p a v i n g 方法等其不足之处就是所生成的网格与所选择的初始栅格 及其取向有关，网格边界单元质量差这种方法在原理上相当简单，也易于扩充到三维， 对于相对规则的问题区域不失为一种简单有效的方法 2 2 3 l o o p i n g 方法 l o o p i n g h l 方法属于几何分解方法，该方法通过一定的规则逐步分解所要剖分的区 域，直至子区域均己分解成为简单区域，然后根据简单区域的类型采取合适的剖分方 式，最终实现区域的全四边形剖分下面我们对该方法的一些关键步骤进行介绍： 1 最优分割线的确定 分割线是连接区域或子区域边界上两点的线段，该线段可把区域一分为二该方法 的关键技术就是分割线的确定实际上，边界上任两个点的连线并不一定都可以把区域 一分为二另外分割线的选择还会影响最终生成的四边形网格的质量，因此在选择分割 线时要特别慎重，下面是确定最优分割线的一些规则心嵋 ( 1 ) 用最短的边分割出最大的面积如图2 6 所示，其度量函数可用式( 2 1 ) 来表 示， 厂( ) = 1 2 a ( 2 1 ) 其中4 = a r e a ( f 2 ) ，a = m i n ( a t ，4 ) ( 2 ) 用最短的边分割出最大边长，其度量函数可用式2 2 表示 ， 厂饵) = 二 ( 2 2 ) 。 c 其中c f 为q ，的周长，c = m i n ( c 。，c 2 ) ( 3 ) 添加分割线e 后新生成的角应尽量接近于州2 或7 我们用、壬，来表示这个度 量，使其满足当e 垂直于边界时，甲取得最小值 接下来采用加权组合的方式来定义分解规则由于上述度量值的实际大小范围较 大，在此先定义两个缩放变换： g l ( x ) = a r e t a n ( x ) ，9 2 ( x ) = 1 一e x p ( 一x 2 ) ( 2 3 ) 则得到如下的优化问题的目标函数： 大连理工大学硕士学位论文 ( e ) - - - - t z ! 瓯( j ) + 口：既可1 ) + 口，仃( 仍，仍) ) ( 2 4 ) 其中，r ，z 1 ，2 口，为用户给定的参数，默认情况下，q = 1 ，z = 1 即 1 2 厂( e ) = 嘲岛) + a r c u m ( u ) + a r c t a n ( 甲( 缈j ，晚) ) ( 2 5 ) 选择剖分线的过程就是在几何区域e 求解该目标函数的离散化最优问题 图2 6 最短的边分割出最大的面积 f i g 2 6 g a i n i n gt h el a r g e s ta r e av i t ht h es h o r t e s te d g e 2 剖分线上新节点的布置 在剖分线上合理地布置新节点，是网格生成算法中关键的一步这是因为节点的位 置和间距反应了单元尺寸信息在剖分区域上的分布，直接影响最后形成网格的疏密分 布和质量剖分线上新节点的布置，必须满足以下两个条件陆1 ： ( 1 ) 在剖分线上布置节点的个数，应该保证形成的两个子区域的边界节点个数为偶 数 ( 2 ) 新节点在剖分线上的间隔值必须均匀分布，以保证单元尺寸渐变过渡 带边三角网格曲面的四边形分割 首先，按照剖分线两端的单元尺寸，计算剖分线上所需布置新节点的数目假设剖 分线两端的单元尺寸为元，以，不妨假设吒以剖分线长度为，则定义割分线上的 节点间隔值d ( x ) 为线性函数 d ( x ) = 以+ ( 叱一九) x l ， o z 1( 2 6 ) d ( x ) 是分段线性连续函数，则所需布置的节点数目为： 矿= 高= 取，使得n - i n n ，则即为分割线上所需的节点数记而= 0 ，x n = ，然后 在【0 ，】中插入一1 个内节点为，而，x n - 】，于是，与h 的间隔度为7 0 ，= n ，如果节 点在剖分线上的分布是渐变的，那么【o ，】中相邻节点都应该取相同的问隔度7 = n 所以五的坐标应该满足： f 去= 纱 ( 刚( 2 8 ) 记口= 以，= ( 以一九) ，计算出工，的分布如下： 五：j 芳( p 脚一1 ) ， o ( o s f )( 2 9 ) i l a y ，= 0 如果计算得到的节点数目为奇数，最简单的作法是令n = + 1 以满足奇偶性的 要求 3 六节点子区域的处理 在最后剩下六节点区域时，如果对其仍旧用区域递归分解算法进行剖分，则最后 生成的单元质量较差，需要进行复杂的网格优化才能得到质量较好的网格而对六节点 子区域进行分类，对每一种情况给出剖分方法，则可以避免这种情况的发生下面是一 些六节点子区域的剖分模板1 ： ( 1 ) 当六节点子区域的节点处的内角没有一个接近万时，如图2 7 ( a ) ，( b ) 所示， 可以分为两个或者3 个四边形如果有一个节点内角接近万时，可以使用2 7 ( c ) 所示的 方法剖分 大连理工大学硕士学位论文 圆仓 厂_ f i g 2 7 t h ep a r t i t i o nt e m p l a t e1o fs i x - n o d e ss u b a r e a ( 2 )当六节点子区域上的节点的内角有两个接近万时，可以根据节点的位置使 用下面的方法剖分如图2 8 ( a ) ，( b ) ，( c ) 所示 图2 8 六节点子区域剖分模板2 f i g 2 8 t h ep a r t i t i o nt e m p l a t e2o fs i x - n o d e ss u b a r e a ( 3 )当六节点子区域上的节点的内角有三个接近7 7 时，根据情况可以按下面的方 法剖分成四边形，如图2 9 ( a ) ，( b ) ，( c ) 所示 ab 图2 9 六节点子区域剖分模板3 f i g 2 9 t h ep a r t i t i o nt e m p l a t e3o fs i x n o d e ss u b a r e a c 带边三角网格曲面的四边形分割 2 2 4p a yin g 方法 p a v i n g 方法是一种直接的全四边形网格生成方法，该方法的输入是区域边界离散 所形成的边界环它们被称为永久边界，即在内部网格生成的过程中，它们不许变动 永久边界又分为内边界和外边界：一般外边界仅有一个，它包含了生成网格的区域( 对于 连通区域) ；而内部边界则定义了区域内部的洞外部边界节点按逆时针顺序排列，内部 边界节点按顺时针顺序排列内部的节点和单元会随着四边形网格的生成而动态的计算 出来p a v i n g 方法生成的网格质量高，边界灵敏性好，内部不规则网格节点数较少，但 是在网格生成过程中要进行大量的交叉判断和处理，因此计算量很大特别当目标区域 比较复杂时，极容易产生大面积的网格交叉，对其进行处理需要大量的计算，处理不 好还会造成算法不稳定 如图2 1 0 所示，处于永久边界上的点称为固定节点( f i x e dn o d e ) ，不在永久边界 上的点都称为浮动节点( f l o a r i n gn o d e ) 当前边界上的节点内角口定义为：该节点与前 一节点之间的线段与该节点与下一节点之间的线段之间的夹角 f i g 2 10p a v i n gm o t h e d p a v i n g 方法的一些主要步骤如下翻： 1 层的选择( r o wc h o i c e ) 寻找产生下一层单元的第一个和最后一个节点，这有助于减少不规则节点的数量 为此将节点按照该点的内角口的大小进行分类： 大连理工大学硕士学位论文 口2 # 3 ， 则称该节点为终止节点( r o we n d ) 2 z 3 口4 z 3 ，则称该节点为边节点( r o ws i d e ) 4 z 3 1 1 万6 ， 则称该节点为转节点( r o wr e v e r s a l ) 不同类型的节点，网格的生成方法也不一样 2 结束检查( c l o s u r ec h e c k ) 如果最后边界上的浮动节点数为零时，则结束操作。当为2 时，则进行缝( s e a m ) 操作 ( 见后面) 如果为4 ，则最后形成一个四边形并结束如果最后剩下6 个节点，则进行以 下闭合操作如图2 1 l 所示 r z c t e a r g l h佩l 幻砒 s e x i c i r c l e c i r c l e 图2 1 1 六节点边界的闭合处理 f i g 2 1l t h ec l o s u r eo p e r a t i o no fs i x n o d e sb o u n d a r y 3 内部单元的生成( r o wg e n e r a t i o n ) 根据不同的节点类型，生成新节点及单元的方式也不同下面是具体的生成算法： 3 1以边节点和终止节点为基点的新单元生成 如图2 1 2 ( a ) 所示，由h 。，以，三点生成一个新的节点，连接新旧节点组 成一个新的单元，y 与向量瓦砭的夹角为竺2 ，令4 = 0 瓦l i ，畋= 0 瓦0 ，则有： 州：盟业 ( 2 1 0 ) 一 s i n ( a 2 ) 3 2 以角节点为基点的新单元生成 带边三角网格曲面的四边形分割 如图2 1 2 ( b ) 所示，此时由- i ，m ，+ 。三点生成三个新的节点m ，m ， 连接新旧节点，组成两个新单元，巧，圪，巧与瓦的夹角分别为竺3 ，詈，了2 a ，则有： 卜端l ，| 略压l 巧| ，i v , l - i 圪l ( 2 1 1 ) ( a 口 i 图2 1 2 新节点的生成 f i g 2 12 t h eg e n e r a t i o no f n e wn o d e ( b ) 3 3以角节点为基点的新单兀生成 如图2 1 3 所示，此时由h 。，“。三点生成五个新的节点，m ，川，虬，m 连接新旧节点，组成三个新单元，圪，巧，匕，圪与j 以，的夹角分别为 一t x ，一3 t r ，竺，丝，一3 c t ，则有： 4s284 卜苗筹i = 压阶州巧i ，i 圪，州巧i ( 2 1 2 ) 一1 6 大连理工大学硕士学位论文 图2 1 3 新节点的生成 f i g 2 13 t h eg e n e r a t i o no f n e wn o d e 图2 1 4 长度光滑 f i g 2 14 l e n g t hs m o o t h 4 1 碉格光滑 在网格生成的过程中，由于一些局部操作，如缝合处理，交叉处理等，很容易使 生成的网格和p a v i n g 边界变形，从而影响网格的质量，因此需要对其进行光滑操 作b l a c k e r 等人n 1 3 给出了先进行边界光滑，然后进行内部节点光滑，最后再进行边界 光滑的光滑方法下面首先看边界光滑 4 1 边界光滑 边界光滑就是对除