基于四叉树法和波前法的混合网格划分算法的研究和实现

《基于四叉树法和波前法的混合网格划分算法的研究和实现》由会员分享，可在线阅读，更多相关《基于四叉树法和波前法的混合网格划分算法的研究和实现（49页珍藏版）》请在装配图网上搜索。

1、-基于四叉树法和波前法的混合网格划分算法的研究和实现 南京航空航天大学 硕士学位论文 姓名：郝跃宏 申请学位级别：硕士 专业：航空宇航制造工程 指导教师：陈文亮 20070101 南京航空航天大学硕士学位论文 摘 要 随着计算机技术和信息技术的广泛应用和飞速发展，网格生成技术已成功应用于计算力学、流体力学、有限元分析等工程领域，成为解决数值解析与模拟等复杂问题的强有力手段。 本文对网格生成的相关技术进行了研究与探讨，内容主要包括： ? 对现有曲面网格划分技术进行了研究比较，主要分析探讨了映射法、Delaunay 三角剖分法、铺砌法、四叉树法、波前法和三角合成法等常用算法。 ? 将四叉树法、波前

2、法和三角合成法相结合，在映射法的基础上设计并实现了一 种新的网格划分方法。该方法首先将裁剪曲面边界离散成多边形，然后使用四叉树法对待划分裁剪参数曲面按细分要求进行递归分解，最终生成规则的栅格点，再利用波前法的原理生成三角形网格，通过三角合成法生成三角形与四边形混合网格。 ? 针对网格划分算法的具体实现细节，采用了一些可以增强算法稳定性和可靠 性，提高算法效率的措施。 ? 在上述技术研究的基础上，将该曲面自动网格划分算法成功应用于板料成形模 拟的CAE软件中，该算法具有自适应能力强，网格生成速度快，稳定可靠等优点。 关键词：有限元网格，混合网格，四叉树法，波前法，三角合成法 i 基于四叉树法和波

3、前法的曲面网格剖分算法的研究与实现 ABSTRACT With the rapid development of computer technology and information industry, mesh technique is implemented to solve complicated numerical analytics and simulation in engineering fields, such as calculative mechanics, hydrodynamics, and finite element analysis. Correlative m

4、esh is deeply researched in this thesis which mainly emphasizes on: ? Several techniques about surface meshing are researched including mapping, Delaunay, paving, quadtree, advancing front technique and triangle tranformations. ? Integrated with present meshing techniques of quadtree, advancing fron

5、t technique and triangle tranformations, a new mesh generating method is proposed and designed which is based on the mapping method. The boundaries of trimmed surface are firstly discreted into polygons. And then the parametric surfaces are recursively decomposed with the refined requirement by the

6、quadtree method, subsequently get a set of regular points. Then triangular meshes are generated by the principle of advancing front technique. At last hybrid mesh is obtained by merging those appropriate triangular meshes. ? Focusing on the details of the method, some measures are proposed to streng

7、then the reliability and steadiness and enhance the efficiency of the algorithm. The discrete optimization of boundary curve and the optimization of polygon clipping are discussed ? On the basis of the above research, this surface automatic mesh generation has applied to CAE software successfully wh

8、ich can create high quality element. The method is steady and reliable. The speeding of the meshing is good. Keywords: finite element mesh, hybrid mesh, quadtree, advancing front technique, triangle tranformations ii 南京航空航天大学硕士学位论文 图、表清单 图1.1 结构化网格和非结构化网格.4 图2.1 网格重叠与网格锥度.9 图2.2 网格扭曲与网格死锁.10 图2.3 参考

9、网格与真实区域网格之间的映射关系.12 图2.4 点集的Voronoi图（虚线）及其Delaunay三角剖分（实线）.14 图2.5 Lawson法加点示意图.15 图2.6 Paving原理图.16 图2.7 四叉树示意图.18 图2.8 波前法原理示意图.20 图2.9 三角合成法示意图.21 图3.1 复杂曲面网格划分流程.24 图3.2 环的面积计算.26 图3.3 曲线离散化处理.27 图3.4 曲线离散误差条件.28 图3. 5 弦高误差示意图.28 图3.6 四叉树划分过程.29 图3.7 四叉树多层细分与结点处理.29 图3.8 最大距离示意图.31 图3.9 结点外法矢夹角示

10、意图.31 图3.10 曲面离散误差条件.32 图3.11 四叉树细分示意图.32 图3.12 双向细分与单向细分比较.33 图3.13 曲面离散细分类别.34 图3.14 结合Upm和Vpm示意图.34 图3.15 曲面上离散数据点与裁剪边界位置示意图.35 图3.16 前沿示意图.37 图3.17 单元与前沿相交示意图.37 图3.18 几种典型的三角形值.38 图3.19 四边形形状控制参数的定义.39 v 承诺书 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作所取得的成果。尽我所知，除文中已经注明引用的内容外，本学位论文的研究成果不包含任何他人享有著作权的内容。对

11、本论文所涉及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。 本人授权南京航空航天大学可以有权保留送交论文的复印件，允许论文被查阅和借阅,可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段保存论文。 (保密的学位论文在解密后适用本承诺书) 作者签名： 日 期： 南京航空航天大学硕士学位论文 第一章 绪论 1.1 引言 网格生成技术，最早起源于20世纪50年代的有限元分析，是为了简化偏微分方程数值问题，而把一个物理区域划分成一些小单元的过程，这实际上就是定义了一个能很好的描述几何区域的形状特征的节点和单元的集合，并且这些节点和单元符合各种不同的形

12、状和尺寸标准。一般情况下，平面或曲面区域被划分成三角形单元或四边形单元，而三维几何体主要被划分成四面体单元或六面体单元，理想的情况下，三角形和四边形单元分别为正三角形和正四方形单元，而四面体和六面体单元分别为正四面体和正六面体单元。 网格生成是有限元方法的先决条件。对于尺寸很大或几何形状复杂的计算域，构建一个有效的网格是一项费时、繁琐、甚至极其困难的工作。网格自动生成技术不但节省了大量的时间，而且减少了差错，带来了计算的高效性和可靠性。 1.2 网格生成技术的工程背景 有限元法1FEM(Finite Element Method)是近40年来工程计算方法领域中的一项重大成就，是结构或多自由度体

13、系分析的有力工具。随着科学技术的发展，有限元法在工程分析领域占据着越来越重要的位置，它已部分甚至完全取代了传统的分析设计思想及手段，使分析设计的周期相应地缩短，可靠性相应地增加，设计成本大大减少。 有限元法是求解复杂工程问题的一种近似数值分析方法，用有限元法进行工程分析的过程主要包括三个阶段：有限元模型的建立和数据的输入；进行工程计算；分析结果的判读和评定。而其中，模型的建立是有限元分析的主要困难。若用手工建立有限元模型不仅需要花费大量时间，工作效率很低，容易出错，而且模型的复杂程度受到很大的限制，有些复杂的模型甚至很难用手工来建立。根据经验，有限元分析各阶段所用时间为：40%45%用于模型的

14、建立和数据输入，50%55%用于分析结果的判读和评定，而分析计算只占5%左右。因此，模型建立的时间和效率代价已成为有限元分析得以更广泛应用的瓶颈之一。 随着计算机技术的发展和普及，为了克服上述问题，利用计算机和交互式图形显示技术来自动建立有限元模型并完成数据输入，我们称这一过程为有限元分析的前置处 1 基于四叉树法和波前法的混合网格划分算法的研究与实现 理。采用这种方法将显著减少建立有限元模型和数据输入所需的人力和时间。有限元的前置处理包括：选择所采用的单元类型，网格划分，确定各节点和单元的编号及坐标，确定载荷类型，边界条件，材料性质等，其中最耗时、最难实现自动化的是网格划分。特别是当结构复杂

15、，计算精度要求较高时，单元网格的划分就很细，所需时间显著增加，网格质量也很难保证，这对整个有限元分析都是不利的。因此，网格生成的自动化是使有限元前处理软件能够成功应用的十分重要的前提条件。 1.3 网格生成技术的研究历史 网格生成技术的起始时间应当追溯到二十世纪五十年代后期有限元法诞生之时2，在六十年代以前都是采用手工操作，在六十年代出现了自动生成算法。有很多人对于网格自动生成方法做了综述3-7。最早出现的自动网格生成算法是映射法。Zienkiewicz和Philips8在1971年首先提出了用映射法来产生平面或曲面网格。他们采用的是等参坐标的方法，但由于插值的原因，产生的网格误差较大。R.E

16、.Bamhill9在1973年提出的把超限插值应用于网格生成的算法改进了这个方法，生成的网格得到一定的改善。随后 C.A.Hall10在这方面也做了一些工作。F.T.Tracy11提出了保角映射法，但单元形状及网格密度难以控制。对于复杂区域，用映射法要对区域进行手工划分，因此映射法属于半自动方法。T.K.H.Ham12用整数规划的方法给出了区域划分后各区域边界的结点数的一种方法，该方法使得映射法的自动化程度有所提高。 在七十年代有突破性的方法不多，1972年Suhara和Fukuda13提出了结点连元法，Cavendish14使用随机的结点生成技术进行了改进。1977年Lawson15和198

17、1年Dave Watson16分别给出了Delaunay三角化一个点集的算法，Timothy Baker17、Watherill和Hassan18利用它分别给出了网格生成算法。1976年Herrman19给出的带权的Laplace光顺方法，对于网格的优化处理起了重要作用。 到了八十年代，由于计算几何理论的成熟，出现了一大批具有突破性的算法。1980年和1984年Wordenweber的两篇文章20, 21给出了拓扑分解法，从分解的角度对区域进行网格划分。该方法的最重要的贡献是引入了算子的概念。R.Haber221981年提出的离散形式的超限映射法对原有的映射法做了极大的改进，所得网格有了很大的

18、改善。Heighway23在1983年通过把两个相邻三角形合并成一个四边形给出了三角形单元向四边形单元转化的一种技术。1980年由Thacker、Gonzalez和Putland24提出的基于网格的方法为以后的四叉树和八叉树奠定了基础。Kikuchi25把这种方法扩展到用四边形生成四边形占优的网格。Yerry和Shephard26就此给出了著名的四叉树方法，该算法的基本思想是把包含着几何区域的长方形重复细分直到子长方形的大小满足要求为止，然后， 2 南京航空航天大学硕士学位论文 再在内部的小长方形单元内按一定的原则构造三角形单元。Samet27给出了实现四叉树的数据结构。1983年Bykat2

19、8用递归的方法给出了几何分解的思想，其基本思想是：先把区域初始化为凸集，然后对凸集从中间进行递归分解直到成为三角形为止。1985年S.H.Lo29对于结点连元技术给出了非随机的技术，对区域内部布点的方法加以简化，效率得到提高，结点分布更加合理。在八十年代中后期，网格的生成方法向三维方向发展。Wordenber把他的二维生成网格的拓扑分解法拓展到三维的情形。Woo和Thomasma30也给出了一种三维的拓扑分解法。拓扑分解法理论简单，易于处理，但是也有其缺点：由于没有考虑到几何因素，因此得到的网格形状并不太好。另外对于含有曲面的实体难于处理。在结点连元的算法推广中，Nguyen-van-Phai

20、和Cavendish分别在不同的方面把二维问题进行推广。其中Cavendish用Delaunay三角化来产生四面体网格的方法是目前实体产生方法中最常用的一个方法，在三维情形下，空圆特性变为空球特性。八叉树法是对四叉树的推广，Yerry、Shephard等人在这方面做了不少贡献32,34。J.Amresh31在1986年把几何分解法推广到三维情形，通过寻找一个分割面，把区域递归地分成两个子体积，依次类推，直到所有的子体都变为四面体为止。后来的中面法也是几何分解法的一种变形形式。 到了九十年代，各种方法都处于快速发展阶段。由于用三角形网格进行有限元计算没有四边形网格的精度高，因此很多人对三角形网格

21、向四边形转化开始了大量研究。Johnston32于1991年给出了三角形网格向四边形转化的算法，两相邻三角形能化为四边形的就合并为四边形，剩余的三角形通过分裂传播法消除。 1991年国际工程中的数值方法杂志推出一期网格生成专辑，其中有两篇重要的文章提出的两种直接法，成为目前最为流行的网格生成方法。一篇是Zhu和Zienkiewicz33提出的波前法生成四边形网格。它首先在边界产生初始结点，再利用波前法生成三角形网格，然后再合并三角形成为一个四边形。这篇文章的意义在于提出了波前法产生三角形，并且给出了三角形网格向四边形网格转化的一种方便的做法。波前法的思想最初是由Peraire34提出的。另一个

22、是由Blacker和Stephenson提出的Paving算法35，该法是直接由外向内生成成排的四边形单元。这两种方法有些类似，都是结点和单元同时生成，只是一个生成三角形单元，一个生成四边形单元。以这两种方法为基本思想，出现了许多用于曲面和实体生成的方法。在曲面网格生成方面，S.H.Lo36, 37把波前法推广到曲面上，Cass38把Paving方法推广到了曲面上。这两种方法都给出了一套寻找新生成结点的方法。另外Plaster35, 39方法也是仿照二维平铺的方式，从外层向里层前进，并且处理了内部缝接问题。但由于缝接在有些情况是很难解决的，因此又产生了六面体和四面体混合网格的生成算法。Tuch

23、insky40给出了用四面体填充缝隙的方法。 3 基于四叉树法和波前法的混合网格划分算法的研究与实现 九十年代中期，每年一届的国际网格圆桌会议（International Mesh Roundtable）的出现为网格生成领域的研究人员提供了一个论坛。该国际会议的举行对网格的发展起到了极大的推动作用。 1.4 网格生成技术的研究现状 有限元网格从复杂性来说，可分为二维平面和三维实体网格，介于二维平面与三维实体之间的是曲面网格。最通常的二维平面和三维曲面网格单元是：三角形单元、四边形单元。三维实体网格中，三角形单元和四边形单元分别被扩展为：四面体单元、六面体单元。 根据Ken Ho-Lo5等人的研

24、究，从拓扑结构上区分，可以把有限元网格分为两大类：结构化（structured mesh）网格和非结构化（unstructured mesh）网格，如图1.1所示。 图1.1 结构化网格和非结构化网格 图1.1（a）所示为结构化网格，是指区域内部所有的网格结点都拥有相同数目的相邻单元。结构化网格速度快、效率高，且有许多优化措施，对于形状简单的物体，结构化网格划分是一种好的方法。 但结构化网格要求待划分区域的几何形状不能太复杂，而大量的工程问题中，需要网格划分的区域边界往往比较复杂，所以，非结构化方法的优越性就能得以体现。 图1.1（b）所示为非结构化网格，该类型网格对网格的拓扑结构没有统一要求

25、，每个结点周围可以有不同的单元数量。舍去了网格结点的结构性限制，结点和单元的分布是任意的，易于控制网格单元的大小、形状和网格结点的位置，可以比较灵活，自适应计算，合理分布网格的疏密，提高计算精度。但为了描述网格的拓扑结构，非结构化网格需要比结构化网格大得多的存储空间，且结构化网格中存在许多成熟的快速算法，难以应用到非结构网格上。在应用中，非结构化网格的形式多种多样，主要有三角形、四 4 南京航空航天大学硕士学位论文 边形、四面体、六面体网格。非结构化网格生成方法有很多，主要有Delaunay三角化法、推进阵面法、修正的四叉树、八叉树法等。 经过多年的发展，作为有限元法走向工程应用的桥梁的有限元

26、网格生成技术获得了源源不断的外在动力；另一方面，计算机硬件运算能力的不断提高容许人们对工程和科学计算的规模、复杂度、效率、精度等方面提出更高的要求。但是，有限元网格生成算法中的某些难点问题始终未能获得真正意义上的解决，它们的研究解决对于有限元分析或模拟软件的推广应用具有重要的实际价值。 1.5 选题依据及章节安排 近年来，板料冲压成形技术的数值模拟研究取得了巨大进步。以有限元法为代表的数值模拟系统与CAD/CAM系统相结合，形成了模具设计、分析与加工一体化的CAD/CAE/CAM集成化系统，目的在于减少模具的设计与调试周期、降低模具加工成本，提高产品质量与市场竞争力。 1.5.1 选题依据 作

27、为重要的工程数值分析方法，有限元方法在许多工程领域得到了广泛应用，以其为理论和方法而开发的有限元分析或模拟软件在实际应用中显示出了极大的应用价值。网格划分作为有限元建模的关键环节其重要性更是不言而喻。虽然网格划分技术取得了很多研究成果，但是随着工程问题复杂度的增加，对网格生成的速度和质量要求也越来越高，网格划分技术仍是制约有限元建模技术发展的关键因素。所以，如何快速、全自动地生成高质量的有限元网格仍是当今有限元建模技术的研究热点之一。 从20世纪70年代后期开始，板料成形CAE分析技术逐渐走向成熟，已形成了商品化的CAE分析软件，得到了许多工业部门的重视和应用。其中由美国工程技术联合公司（En

28、gineering Technology Associates Inc.）开发的DYNAFORM是一款专业的板料成形CAE分析软件，该软件被广泛应用于汽车碰撞、乘员安全性、水下爆炸、板料成形等领域，产生了很好的经济效益。为了深入研究高效的有限元网格划分技术，南京航空航天大学与美国工程技术联合公司开展了国际合作，对有限元分析模块中的曲面网格自动划分技术做进一步研究，以提高完善DYNAFORM软件的有限元前置处理功能。 1.5.2 章节安排 本文的研究内容主要是实现一种快速可靠的曲面混合网格生成算法，并对其相关关键技术进行了深入研究。 5 基于四叉树法和波前法的混合网格划分算法的研究与实现 本文共

29、分五章，各章内容安排如下： 第一章 绪论 主要讲述了网格生成技术的工程背景，以及网格生成技术的发展历史及研究现状。简要介绍了论文的选题依据及章节安排。 第二章 复杂曲面的常用网格生成算法 介绍了网格划分所涉及的曲线曲面基本概念定义，对目前常用的几种网格生成算法进行分析与评价，阐述了各算法的基本思想，并对各网格生成算法进行了综合比较。 第三章 基于四叉树法与波前法的混合网格划分算法 主要详细阐述了一种快速可靠的混合网格划分算法，包括算法的设计思想、具体划分步骤和划分过程中的一些算法实现。 第四章 算法实现的关键技术及其软件开发 着眼于划分算法的细节处理，详细介绍了一些关键技术的实现，以保证算法的

30、可靠性和运行效率。还对曲面混合网格软件、开发平台及技术进行了简要介绍，给出了用本文算法实现的曲面混合网格划分应用实例。 第五章 总结与展望 总结了本文的研究工作，展望了研究发展前景。 6 南京航空航天大学硕士学位论文 第二章 复杂曲面的常用网格生成算法 2.1 引言 自五十年代起，有限元分析在航空、水利、土木建筑、机械、结构分析、电磁学、热力学、弹性力学等工程设计和工程分析领域得到了广泛的应用。有限元分析用大量几何形状简单的单元（如三角形、四边形等）的组合来近似描述整体结构，将形体结构离散成简单单元的组合，称为有限元网格划分。手工生成网格工作量大、乏味费时、容易出错。网格数据的输入占有限元分析

31、工作量的一半以上，因此人们着重研究计算机辅助的半自动或全自动的网格划分方法。网格自动划分一直是国内外研究和应用的热点，迄今为止已经产生了很多不同的算法。本章主要介绍网格划分所涉及的基础理论和基本概念并详细分析介绍了现有的曲面网格划分的典型算法。 2.2 有限元网格的划分要求及质量评价 网格划分算法很多，一些新思想和新算法也在不断出现，为了更好地比较和评价曲面网格划分算法，本节主要介绍有限元网格划分要求及质量评价。 2.2.1 有限元网格划分要求 网格划分是建立有限元模型的一个重要环节，它要求考虑的问题较多，需要的工作量较大，所划分的网格形式对计算精度和计算规模将产生直接影响。为建立正确、合理的

32、有限元模型，划分网格时应满足以下基本要求： ? 合法性。每个单元的节点不能落入其它单元内部，单元边界上的节点均应作为单 元的节点，不可丢弃，不能从一个元素的边或面的内部产生另一元素的顶点； ? 相容性。单元必须落在待分区域内部，不能落在原区域之外，也不能使原区域边 界内出现空洞，单元之间不能相互重叠，要与原物体的占有空间相容； ? 逼近精确性。所有原来模型的顶点都应取成单元的顶点，所有网格的表面顶点都 应落在原域表面上，所有原域的边和面都被单元的边和面逼近； ? 良好的单元形状。每个单元应尽量趋近于正多边形或正多面体，不能出现面积很 小的二维尖角元或体积很小的三维薄元； 7 基于四叉树法和波前

33、法的混合网格划分算法的研究与实现 ? 良好的剖分过渡性。单元之间过渡应相对平稳，否则，将影响计算结果的精确性， 甚至使有限元计算无法进行下去； ? 网格剖分的自适应性。在几何尖角处、应力温度等变化大处网格应密，其它部位 应较稀疏，这样可保证计算解精确可靠。 2.2.2 网格质量评价 由于根据CAD模型生成的网格质量将直接影响到求解时间及求解结果的正确性，因此，有限元网格的生成质量是非常重要的。 一般的，网格质量用以下的两类方法来定义：一类是将网格质量定义为所有单元质量的总和或某种平均值，另一类是以网格中质量最差的一个单元的质量来表示整个网格的质量。这两类定义方式都有一定的缺陷。第一类方法存在的

34、问题是：一，由于所采用的单元质量量度是连续的，合格单元的质量量度值也根据形状的好坏而有所不同，根据所有网格单元质量求和然后取平均的结果，可能导致全部网格单元合格但形状并不是特别好的单元所组成的网格模型，其质量还不如由部分特别好和部分特别差的网格单元所组成的网格模型，这显然是不合理的。二，忽略了网格中质量特别差的网格单元对网格质量的决定性影响。第二类方法存在的问题是：过分强调最差单元的作用，这也是不合理的。不可否认，最差单元对计算精度的影响很大，然而误差主要出现在该单元附近，而实际上，在一些计算模型中，由于几何边界的限制，在个别角点单元会有很小的内角，这个角点往往是整个网格中的最差单元，然而结构

35、内部有可能产生大量不合格单元的情况，显然这不能由这个最差单元表示出来，特别是这种小角度边界角点在不受载荷作用和无支承边界条件的情况下，往往是零应力状态，真正决定计算精度的应该是其它所有的不合格单元。 有限元计算模型的网格化是整个有限元分析过程中最重要，也是难度最大的环节。单元划分的合理性直接影响计算误差和计算时间，网格单元的质量必须严格控制。考察网格质量主要局限于以下几个方面：细长比，偏斜度，重合，法矢一致性，尺寸度，锥度，歪斜度，死锁。 （1）细长比（Aspect Ratio）：是指单元最长边边长与最短边边长之比，它反映外观边界差异。对于理想单元，该值为1。 （2）偏斜度：偏斜度反映单元夹角

36、的偏斜程度，对于四边形单元而言，理想夹角为90，对于三角形单元，理想夹角为60。偏斜度的计算表达式为： |90?a| i=0i4 对于四边形单元 8 南京航空航天大学硕士学位论文 |60?a| i=0i3 对于三角形单元 上式中i为单元夹角。理想单元的偏斜度为零。这种网格的外在表现就是带有一个或者两个尖角网格单元。 （3）重合（Overlap）：指两个网格单元发生节点共用的情况，也就是网格单元的部分重合，如图2.1（a），网格单元ABCE及单元ABDE有部分重合。这会引起有限元分析结果的不准确。通过判断两个网格单元是否共享三个或者三个以上的节点，就可以知道该网格单元是否重合。 图2.1 网格重

37、叠与网格锥度 （4）法矢一致性：指所有网格单元的法矢方向是否一致。有限元分析的过程要求所有的网格单元其法矢应保证具有相同的方向。而在自动生成的网格模型中往往会存在这种法矢方向不一致的问题，或者，经过软件用户对有限元网格的多次修改后，造成法矢方向的不一致。 （5）尺寸度（Size）：指网格单元中最大网格单元的面积与最小网格单元的面积比。通常要求网格模型中网格单元的大小尽可能的均匀，因此，要求网格单元的尺寸的大小比例应该符合有限元分析中的要求值。 （6）锥度：同上面所述的狭长网格单元一样，在有限元分析的过程中，带有锥度的狭长网格单元在网格模型中也是必须被除掉的。它反映单元由二对角线形成的四个三角形

38、面积的差异程度。通过储存在网格单元中有关网格边界的信息，比较最长边和最短边之间的比例，就可以找到这种类型的网格单元如图2.1（b）所示。 9 基于四叉树法和波前法的混合网格划分算法的研究与实现 （7）翘曲度（Warping）：翘曲度主要由翘曲因子或翘曲角来表示，它反映单元的扭曲程度。翘曲因子为单元对角线的最短距离d与单元面积之比，如图2.2（a）。翘曲角为单元对角线分割的两三角形垂直法矢量b和c间的夹角。对于翘曲度太大的网格单元，通常是把它拆分成两个三角网格单元。 （8）死锁：指网格模型在冲压方向上的重合现象。在有限元分析以及钣金零件的冲压过程中，必须避免网格死锁。如图2.2（b）中网格的标注

39、部分。网格死锁将导致部分零件冲压模拟过程难以进行。 图2.2 网格扭曲与网格死锁 对于整个网格模型来说，还有网格连续性方面的要求。由于网格划分的合理性直接影响有限元分析的计算误差和计算耗时，所以必须控制好网格单元的质量，避免出现不可靠的分析结果。 2.3 曲线曲面的基本概念及定义 在对模型进行网格划分时，以模型整体结构几何数据为基础，然后对几何形体实施自动划分，生成有限元模型，因此网格划分的方法与模型的几何描述有着密切的关系。下面简要介绍曲面网格划分所涉及到的曲线曲面基本概念： 曲面实体造型的几何描述有多种方法，NURBS方法是当前自由曲线和曲面描述的最为流行的技术，因为它可以统一表示初等解析

40、曲线、曲面以及有理与非理Bezier、非有理B样条曲线、曲面。在对该方法的研究不断深入的同时，越来越多的商用CAD/CAM系统也在开发、扩充NURBS功能，使之迅速转化为现实生产力。国际标准化组织（ISO）发布的STEP标准，也选用NURBS作为定义几何描述的唯一数学方法。 10 南京航空航天大学硕士学位论文 给定三维空间控制顶点di，及相应的权因子wi（i = 0,1,2,，n），则在三维空间定 义了一条k次有理B样条曲线，如式2.1所示。 uv p(u)=uvwdiiNi,k(u)n i=0 n （2.1） wNi i=0i,k(u) i = 0,1,n分别与控制顶点di，i = 0,1,

41、n相联系。首末权因子w0， 其中权因子wi， wn>0，其余wi0，以防止分母为零，保留凸包性质及曲线不至于因权因子而退化为一 点。Ni,k(u)是k次规范B样条基函数。对于非周期NURBS曲线，常将两端节点的重复度取为k+1，曲线定义域u 0，1。 NURBS曲面是曲线的推广，由双参数变量分段有理多项式定义的NURBS曲面如式2.2所示， uv p(u,v)=mi=0 muvwi,jdi,jNi,k(u)Nj,l(v)nj=0n i,j （2.2） w i=0j=0Ni,k(u)Nj,l(v) uv式中，di,j为控制顶点，i = 0,1,m , j = 0,1,n呈拓扑矩形阵列，形成

42、一个控制网格。wi,j（i = 0,1,，m; j = 0,1,，n）为相应控制点权因子，规定四角顶点处用正权因子即w0,0，wm,0，w0,n，wm,n0,其余wi,j0。Ni,k(u)，i = 0,1,m和Nj,l(v),j = 0,1,，n 分 别为u向k次和v向l次的规范B样条基。 在实际工程应用中，形成零件或模具通常采用一组曲面来表达。曲面一般表示为参数形式。 设有n个参数曲面Si(u,v)，i = 0,1,2,n-1，第i个参数曲面方程为： Si(u,v)=xi(u,v),yi(u,v),zi(u,v) （2.3） 当参数曲面未被裁剪时，有界曲面的参数域为矩形域ui0，ui1、vi

43、0，vi1。一般地，参数曲面被裁剪，其参数域为此矩形域的子域，这个子域又称为裁剪区域。裁剪区域的边界曲线称为裁剪曲线，裁剪区域的所有裁剪曲线围成了裁剪区域，这些裁剪曲线组成了裁剪区域的内环和外环，裁剪区域在外环之内，所有的内环之外。外环有且只有一个，内环可以有多个，也可以没有，内环在外环之内。设第i个参数曲面的裁剪区域由li个环围成，第i个参数曲面的裁剪区域的第j个由mij条裁剪曲线组合而成，第i个曲面的 第j个环的第k个裁剪曲线方程是： Ci,j(t)=ui,j(t),vi,j(t)， tt0，t1 （2.4） 11 基于四叉树法和波前法的混合网格划分算法的研究与实现 则这条裁剪曲线对应的曲

44、面上的曲线方程是： Si(u,v)=xi(u,v),yi(u,v),zi(u,v)=xi(uik,(jt),vik,(jt),yi(uik,(jt),vik,(jt),zi(uik,(jt),vik,(jt)， tt0，t1 （2.5） 同样裁剪参数曲面的所有曲面上的曲线界定了裁剪参数曲面，这些曲线组成了裁剪参数曲面的内环和外环。 2.4 曲面网格生成的常用算法及其优缺点 有限元网格的自动生成，是建立有限元模型的重要技术。但目前还没有提出一种通用的自动生成有限元网格的方法。现有的方法，多数是只适用于某一类单元或某几类单元，而且基本上是局部网格自动生成与交互式控制相结合的处理方式。当前已发表的网

45、格划分的文献非常多，以下分别介绍应用于曲面网格划分的常用算法及各自的优缺点41, 42, 43, 44 ： 2.4.1 映射法 映射法是一种半自动网格生成方法，根据映射函数的不同，主要可分为超限映射和等参映射。因前一种映射在几何逼近精度上比后一种高，故被广泛采用。映射单元法是最早使用并在商品化产品中占主导地位的方法，Martins P A F，Partrick K N U PP，杨名生等人对此进行了研究。“映射”方法的基本思想是：利用映射函数，构造剖分区域到简单区域的映射关系，通过简单区域剖分逆映射到原复杂区域上。主要步骤是：首先人为地把分析域分成一个个简单可映射的子域，每个子域为三角形或四边

46、形，然后根据网格密度的需要，定义每个子域边界上的节点数，再根据这些信息，在子域中利用线性或二次插值划分网格，再把规则区域节点通过逆变换生成对应的空间节点，同时保留节点间的 拓扑关系。 图2.3 参考网格与真实区域网格之间的映射关系 它根据形体边界的参数方程，把一个参考网格通过映射方程从参数域映射到实际的区域上。这个参考网格是预先给定的，基本原理如下：考虑一个区域?，其形状接近于四边形，如图2.3所示。假设位于两对边的点的数目相等。给定一个单位正方形，定义正方形的四条边上点的数目与区域?对应边上的点的数目相等。 12 南京航空航天大学硕士学位论文 设F为真实区域和单位正方形之间的映射函数。目前函

47、数F主要有两种选择，一种是： F=pi(u,v)ai （2.6） 其中ai为四边形区域的四个角点的坐标，前面的系数pi分别为 p1(u,v)=(1?u)(1?v) p2(u,v)=u(1?v) i=14 p3(u,v)=uv p4(u,v)=(1?u)v 其中u和v分别为参数空间坐标，且0u1，0v1。这种方法是由Zienkiewicz等在1971年提出的45，它生成的网格有时不能精确地模拟区域的边界。 F的第二种选择为 F(u,v)=(1?v)f1(u)+uf2(v)+vf3(u)+(1?u)f4(v)? (1?u)(1?v)a1+u(1?v)a2+uva3+(1?u)va4) （2.7）

48、其中fi为四边形区域的四条边界，ai为四边形区域的四个顶点，0u1，0v1。这种方法是由Gorden和Hall提出的46，它生成的网格可以精确地模拟区域的边界。 映射法对物体的边界要求非常严格，物体边界的对边必须有相同个数的等分，而且相对面的表面网格数也必须具有完全相同的拓扑结构。近年来，美国CUBIT项目的研究者把特征识别技术和映射法相结合，试图自动对边界进行满足映射法条件的分解。从 CUBIT能够自动对那些不满足映射条源表面切割物体直到目的表面，即可形成六面体。 件的几何体进行子分，并且允许一次映射的过程中存在多个源表面和目的表面。 映射法的优点在于每一子域内网格生成可以得到相当好地控制，

49、能够用以进行曲面网格的生成。但其最大的弊端在于要求事先根据所要产生的网格类型将目标域分割成一系列可映射的子区域。而这一工作通常需人工来完成，因而自动化程度低，不适合于全自动网格的生成；对于不规则形体产生的网格质量很差，不提供局部修改功能，过去大部分有限元计算模型并不依赖于实体造型系统(Solid Modeling System,简称为SMS)，所以往往可以根据可映射的补丁反过来定义目标域。Lin研究了映射法生成正交网格。Crawford研究了复合映射法，用单元密度函数来控制单元大小的分布。Blacker试图用知识推理自动将二维复杂域分解为四边形区域。但这些尝试都未根本上改变映射法固有的缺陷。随

50、着计算机实体造型系统的出现，通过与其它方法相结合，这一类方法的自动化程度也逐渐得到提高。 13 基于四叉树法和波前法的混合网格划分算法的研究与实现 2.4.2 Delaunay三角剖分法 这是目前最广泛流行的方法。当给定的结点分布中不存在四点或四点以上共圆时，Delaunay三角剖分有唯一的最优解，即所有三角形单元中最小角之和可达到最大值。Delaunay的具体构造过程为，设平面域内有N个结点P1,P2, ,PN。对每个结点Pi划定一个区域Vi，1iN，Vi区域内任何一点到Pi的距离都比距其他任何一结点Pi要小，即 Vi=x:d(x?Pi)<d(x?Pj),ji （2.8） Vi是一凸多

51、边形，称作Voronoi多边形，它的边界由Pi与相邻结点连线的中垂线所构成。每个Voronoi多边形内只包含一个结点。Voronoi多边形的集合ViiN=1称作Dirichlet图。连接每两个相邻Voronoi多边形中的结点可以形成三角形网格，这就是Delaunay剖分。 Delaunay三角剖分法是一种利用离散点集生成网格的方法。图2.4给出了一个由8个点组成的平面点集S，虚线表示该平面点集的Voronoi图。二维Voronoi图是由一些凸多边形组成，且具有以下性质：1）点集中的任一结点与凸多边形V(pi)一一对应；2）V(pi)内部任意点均以pi为“最近邻” ；3）三个或更多的凸多边形可交

52、于一点，这些点 称为Voronoi顶点；4）外部的Voronoi多边形为开的，而内部的多边形均为闭的。如果两个结点相邻，则它们的Voronoi多边形必然相邻。连接所有Voronoi多边形中的结点，即为Delaunay三角剖分。 图2.4 点集的Voronoi图（虚线）及其Delaunay三角剖分（实线） Sibson47证明了平面任意给定点集的Delaunay三角剖分的结果具有整体优化的性质，它满足“最大最小角”原则（即所有三角形的最小内角之和最大）。与“最大最小角”准则等价的条件是“外接圆”准则，即对于Delaunay三角剖分的每个三角形，没有一个结点落到其外接圆的内部，而只能位于其外接圆之上或外部。 已经出现了大量的不同算法。一般可将