基于STL格式文件的全四边形网格生成方法

1、基于STL格式文件的全四边形网格生成方法”陈寿高晖李光耀（汽车车身先进设计制造国家重点实验室湖南大学长沙410082）摘要：提出一种以STL格式文件所描述的离散几何模型为基础，使用改进的铺路法自动生成全四边形网格的方法。重建STL文件的拓扑结构数据，而后进行模型的内外边界搜索及初始化布点。算法依次向模型内部加入新的节点以生成新的四边形网格单元，直至把模型内部全部覆盖。原始几何模型中的特征线被提取出来，并在网格生成阶段将其作为内部孔洞处理，减小了生成网格模型所导致的离散误差，在特征所在区域生成质量较佳的网格。使用一种联合Laplacian方法与小种群遗传算法（0A）的网格光顺方法,可以有效地纠正

2、反转单元、退化单元等形态质量很差的单元。多个算例验证了本文提出方法的有效性。关键词：STL;网格剖分；特征提取；网格光顺；小种群遗传算法0.引言随着汽车碰撞有限元仿真分析在国际上各大汽车公司的广泛应用，对有限元网格模型的要求也越来越高。一方面，CAD模型中大量的细节需要在网格模型中得以保留，以便更加真实的模拟汽车碰撞过程；另一方面，为了提高碰撞仿真计算精度，保证求解的稳定性，要求网格模型中的单元具有更高的质量。目前在主流CAD（ComputerAidedDesign计算机辅助设计）软件使用NURBS（非均匀有理b样条）作为几何建模内核，商业化网格生成软件需要通过接口软件从软件中获取模型进行网格

3、剖分。但通过接口软件进行数据交换时常常会产生数据丢失或数据错误，严重影响了网格剖分的进行。近年来,面片格式的几何模型表述方式得到了广泛应用，逐渐成为NURBS表述的一种替代方式，如在快速原型制造领域使用的STL（Stereolithography）文件格式，它使用三角形来表述几何模型，格式简单且不易出错，因此更多的研究者把倾向于使用面片模型作为网格剖分的输入模型1。在汽车碰撞和薄板冲压等强非线性问题的有限元仿真计算中，优先使用四边形单元，因为相比于三角形单元，四边形单元具有更高的求解精度和计算效率。非结构化四边形网格的生成方法分为直接法和间接法两大类2。直接法包括影射法、铺路法、前沿*国家97

4、3计划（2004CB719402）和教育部跨世纪优秀人才计划资助项目*联系作者：陈涛Email:danielchen2005推进法、四叉树法等；间接法则首先将待划分的区域划分为三角形单元，接着用不同的算法将三角形单元转换成四边形单元。Blacker在1991年提出铺路法（Paving）属于直接法，具有适用性强，生成网格模型的质量高等优点，现已被广泛运用到商业化有限元分析软件的前处理程序中，如Ansys、HyperMesh等。提出一种以STL格式几何模型的全四边形网格生成算法。克服了使用NURBS几何模型时所遇到的繁琐的模型修补问题。针对三角面片的特点，改进了原有的铺路算法，并能够更有效的控制网

5、格单元尺寸的疏密过渡。原始几何模型中的重要几何特征在网格模型中均能够较好的保留。本文提出联合使用Laplacian方法与小种群遗传算法（四GA）的网格光顺方法，在合理的计算时间内，大幅提高了模型的单元质量。1.STL文件的拓扑重建和特征提取STL格式的数据文件中包含的三角面片，并不能满足有限元计算要求。从图1可以看到，模型包含有大量的狭长的三角形，无法满足碰撞仿真计算的精度要求。因此在本文所进行的研究中，三角面片模型仅作为生成四边形网格所需的背景网格。B6chet2使用STL格式的数据文件生成了满足有限元计算要求的三角形网格，而本文的研究关注于全四边形网格的生成。图1某车型行李箱盖面片模型1.

6、 1模型的拓扑重建与边界初始化STL格式的数据文件中提供了每个三角形的三个顶点的坐标和三角形的法向矢量。从模型的拓扑层次结构上看，STL格式中只有顶点一面片两个拓扑层次，二者之间也仅仅存在从属关系（顶点从属于某个单元）。进行STL模型拓扑重构的目的是要建立顶点一边一面片的拓扑层次结构，并提取拓扑实体之间的从属、相邻关系。依次从文件中读取三角面片，记录它的三个顶点的坐标和法向，并搜寻已存储的节点中是否存在重叠顶点，如果有则进行合并。由此建立顶点与顶点、面片与面片之间的相邻关系。读入完成之后，根据面片之间的相邻关系创建边，建立顶点一边一面片的完整拓扑层次结构关系。模型的边界包括内边界（指模型内部的

7、孔洞）和外边界。边界由仅从属于一个三角形的边组成的。边界搜索分三步进行：1 .首先搜索出模型中所有的仅从属于一个三角形中的边；2 .将它们按照首尾相接的顺序排列，构成一条或多条边链，每一条链代表一个边界；3 .最后要正确区别内外边界。假定模型的法向是Z轴正向，则外部边界链是逆时针方向的，而内部孔洞是顺时针方向的。铺路算法需要首先对所有的边界布上偶数个点，并且点与点之间的距离直接的控制内部网格单元尺寸大小。因此需要根据目标网格的尺寸要求，在所有边界上布点。1. 2模型中的特征识别与特征提取车身零部件的结构大都比较复杂，包含很多的特征，这些特征需要在网格模型中保留。在以STL格式表述的几何模型中，

8、由于拓扑层次较低，只能识别特征边(FeatureEdge)。这里使用二面角(dihedralangle)特征边的判断依据。首先对所有的边计算二面角以搜索出所有的特征边，并按照首尾相接的顺序完成排序，构成特征线。根据二面角的大小，将特征线分为强特征线(StrongFeatureLine)和弱特征线(WeakFeatureLine)。经多个算例测试，当边的二面角大于0.7弧度时应作为强特征，介于0.5弧度和0.7弧度之间时作为弱特征，小于0.5弧度的特征无需作专门的处理。图2所示的模型中，蓝色线表示强特征线，红色线表示若特征线。图2模型中的强特征与弱特征在后续的网格生成中，两者使用不同的处理方式。

9、对于强特征线，算法将其视作一个面积为0的内部孔，并作与其他边界一样的布点处理。铺路算法的一个突出优点是可以在模型的边界附近生成质量极高的网格单元。采用这种对内部特征的处理方法，可以在特征周围得到高质量的网格。对于弱特征线的处理，则通过在网格生成过程中，将位于其邻近的节点移至特征线上，并且在后续的网格光顺中限制这些节点在特征线上移动以保持特征。2.改进的四边形网格生成铺路算法铺路法由Blacker3在1991年最先提出，原始的铺路法只适用于二维，Casd4把它从二维推广到三维，White5对算法的健壮性作了进一步的改进。该方法可用图34说明,算法的输入是代表边界(包括内部边界和外部边界)的节点链

10、，为了生成全四边形单元，每条边界节点链上必须的节点数必须是偶数。算法从边界节点开始，选择最适合生成四边形单元的节点作为一行的开始，加入一个单元，该行其他单元根据各点处的节点内角的大小加入。随着铺路面（Paving）的向内部推进，最终会碰到自身或者其他的铺路面（有多个边界的情形下）。在每加入一行后要进行相交检查（Intersectionchecking）,根据相交的具体情况做缝合处理。在铺路面向内部的逐层推进的过程中，不断使用局部的平滑（smoothing）操作，调整单元中的节点位置以保证单元的质量，控制单元的尺寸。使用“收缩（tucking）”和“加楔子（wedging）”操作，调整凹凸区域的

11、铺路面边界，减少不规则单元的产生。当整个区域都被加入了四边形单元，对整个网格模型使用光顺操作。2. 1使用背景网格计算节点以生成全四边形网格。以图3为输入模型中的三角形面片可以直接作为背景网格,例说明如何利用背景网格来生成新的节点。H1+J图3.新节点计算假定Ng、Ni和Ni+1位于当前的铺路面上，计算由这三点共同确定的新节点Nj的位置。首先找出N邻近的背景三角形网格的集合STi,T2,Tn,将Ni依次投影到它们所在的平面上，寻找投影点落在三角形内的三角形Ti。设Ti所确定平面为9,将Ng、Ni和Ni+1都投影到日上，得到投影点Pi-1、Pi和Pi+1。计算向量PiPi_1和PiPi+；的夹角

12、a,新节点Nj在切平面上的投影点Pj位于a的角平分线上。而点Pj距离Pi的距离为向量PiPi二和PiPi+1长度之和的平均值，由此确定位于Pj的位置。计算得到的Pj仍位于Ni切平面日上，因此需要计算几何模型上距离该点最近的点。''这里使用二角形单兀形函数，计算出Pj在原始模型上的近似点Nj。步骤如下：1,对三角形丁的每一条边，利用Hermitian插值，求出该边的中点，分别为P4,P5,P6；2.使用标准的三角形单元形函数，见（1）式，计算出pj的近似点。x=i(21-1)X12(22-1)X23(23-1)X3412X4423X5431X6上式中，X1,X2,，X6分别是三角

13、形顶点Pi,P2,P3和三角形边的中点P4,P5,P6的坐标，3,&是Pj在该三角形中的面积坐标。2. 2改进的局部单元尺寸调节方法铺路算法的一个主要缺点对内部单元控制力较弱，单元距离边界越远，单元尺寸与边界处确定的理想尺寸的偏差也就越大。在网格生成过程中进行的相交、缝合、光顺操作等都会使单元尺寸偏离设定值。利用输入的三角面片建立覆盖整个问题区域的尺寸场，如果某处的网格单元尺寸与该处的理想尺寸不一致，即进行单元尺寸调节。铺路算法中对局部单元尺寸调节均在铺路面上完成，主要的手段是“收缩（tucking）和“加楔子（wedging）”操作。图4所示为加入楔子的情形，再沿铺路面对单元进行检查

14、时，如果碰到连续三个或三个以上满足加入楔子条件的单元，就在它们的中间位置加入一个楔子单元。该方法的缺点是当单元尺寸变化剧烈时，难以满足要求；同时楔子单元的加入会使位置附近的单元质量大幅降低，而且这种影响会随着铺路面向模型内部的推进而继续。本文提出一种新的方法，使用SchneiderF提出网格细分过渡模版进行网格尺寸调节，如图5所示。在单元密度由稀疏向密集变化时，使用类似网格粗化的手段实现过渡；单元由密集向稀疏过渡时，采用与网格加密相似的方法使过渡更加平滑。这一方法的优点在于尺寸调节的能力更强，调节也仅对相邻的少数单元的质量产生影响，不会对其他网格的质量产生影响。图4,加入楔子控制单元尺寸图5新

15、的铺路面单元尺寸调节方法3. Laplacian方法与小种群遗传算法结合的网格光顺方法网格生成完成后，通常都包含有相当数量的形态质量较差的单元，如狭长单元、退化单元甚至反转单元，需要对网格质量进行调整。提高单元质量的最重要手段是网格光顺方法。最常用的网格光顺方法是Laplacian方法，它对网格内部的每个顶点定义一个拉普拉斯算子（Laplacian）来确定一个调整方向，通过沿调整方向以一定的速度移动顶点来调整网格。其优点是计算简单，收敛快，缺点是如果初始网格包含有扭曲的单元，该方法难以处理。Canann7提出了一种Laplacian与基于优化方法相结合的光顺方法，在一定程度上解决Laplaci

16、an方法难以处理反转单元的问题。但是这一类基于梯度的常规优化方法易于陷入局部最优，并且要求描述单元质量的目标函数至少有一阶导数。Holdert8提出一种基于遗传算法的网格光顺方法，克服了常规优化算法的缺点，但如果针对模型中的所有网格均使用这种优化方法，计算耗费会很大，收敛速度较慢。遗传算法由Holland根据达尔文的进化思想提出，其突出优点是具有全局优化搜索能力。Krishnakumar9提出了小种群遗传算法（GA）,采用二进制编码和一致交叉、竞争选择、最优保留的机制。A的特点是不进行变异操作和种群的个体较少，收敛速度快，在保留最优个体的同时随机生成新的种群。它克服传统遗传算法在搜索进行的后续

17、阶段收敛速度很慢，并且每代的种群数过大的缺点。本文提出一种Laplacian方法与GA相结合的组合网格光顺方法，其主要思想是：首先对模型中质量很差的少数单元（如反转单元和退化单元等）实施基于遗传算法的光顺，而后再剩余的大部分单元实施常规的Laplacian光顺。在使用遗传算法作网格光顺时，为进一步提高算法运行效率，采取以下措施：1 .为了减小搜索空间以提高收敛速度，将待优化节点坐标的搜索空间限制在由该节点的相邻单元所构成的局部区域内；2 .为了克服遗传算法共有的搜索的后续阶段收敛较慢的缺点，对每一个使用遗传算法作优化的单元，一旦该单元的形态质量有显著提高（如原来的反转单元转变为正常单元，或者退

18、化的四边形单元转变为正常单元），即提前结束遗传算法的搜索，转而进行Laplacian光顺。4.算例A.完成网格剖分的模型C.完成网格光顺的模型图6行李箱盖的网格剖分应用本文提出的算法，开发出网格剖分软件STLQUAD。第一个算例是前面给出的某新概念车行李箱盖的，网格剖分和光顺后的结果如图6所示。可以看出，网格模型中保留了原始几何模型中的主要特征，并且在特征周围的网格非常规则，这对有限元求解非常有利。完成后的网格模型共包含有9457个四边形单元，9625个节点，最小的单元内角是32.29度，网格质量可满足仿真要求。另一个算例是汽车碰撞吸能部件，几何模型见图2。模型中包含有大量的孔洞、强特征和弱特

19、征，使用本文提出方法进行网格剖分和光顺处理，结果模型分别如图7a和7b所示，共包含2351个四边形单元。原始模型中重要几何特征基本被保留下来，网格单元尺寸过渡均匀。表一给出了未作网格光顺和完成光顺后的网格质量的对比。从该表可以看出，本文提出的网格光顺方法可以有效地提高网格质量。表1,光顺处理前后的网格质量对比取大角（单位度）最小角（单位度）最小单元尺寸最大单兀尺寸单元长宽比Jacobian翘曲光顺前359.441.690.03827.21221.37-0.62180光顺后157.427.981.9312.582.570.2725.65图7a未作光顺的网格模型图7b光顺后的网格模型5.结论本文提

20、出一种使用STL格式三角面片模型直接生成全四边网格的方法，克服了传统的基于NURBS几何模型的网格剖分方法，经常遇到的模型容易出错的缺点。对模型中的重要几何特征，使用特征识别和特征提取予以保留，并在特征位置生成形态质量较好的网格，这对于有限元计算，特别是对网格质量非常敏感的汽车碰撞仿真是非常有利的。联合使用Laplacian与pGA相结合的网格光顺方法，既有效地提高单元的形态质量，又能够在合理的时间内完成处理。参考文献1 E.BChet,J.C.Cuilliere,F.Trochu,GenerationofafiniteelementMESHfromstereolithography（STL）

21、files”.ComputerAidedDesign,vol34,1-17,20022 Owen,StevenJ,"ASurveyofUnstructuredMeshGenerationTechnology",Proceedings,7thInternationalMeshingRoundtable,SandiaNationalLab,pp.239-267,October19983 TedD.Blacker,M.Stephenson,Paving:ANewApproachToAutomatedQuadrilateralMeshGenerationw,Internationa

22、lJournalForNumericalMethodsinEngineering,Vol32,811-847,19914 Cass,RogerJ."Generalized3DPaving:AnAutomatedQuadrilateralSurfaceMeshGenerationAlgorithm",InternationalJournalForNumericalMethodsInEngineering,JohnWiley&Sons,Vol39,pp.1475-1489,19965 White,DavidR.andPaulKinney,"Redesignof

23、thePavingAlgorithm:RobustnessEnhancementsthroughElementbyElementMeshing",Proceedings,6thInternationalMeshingRoundtable,SandiaNationalLaboratories,pp.323-335,October19976 Schneiders,R,"RefiningQuadrilateralandHexahedralElementMeshes",5thInternationalConferenceonNumericalGridGenerationi

24、nComputationalFieldSimulations,MississippiStateUniversity,pp.679-688,April19967 Canann,ScottA.,JosephR.Tristano,MatthewL.Staten."AnApproachtoCombinedLaplacianandOptimization-BasedSmoothingforTriangular,Quadrilateral,andQuad-DominantMesheswProceedings,7thInternationalMeshingRoundtable,SandiaNati

25、onalLab,19988 MHolder,JRichardson,GeneticAlgorithms,AnotherToolforQuadMeshOptimization?”,Proceedings,7thInternationalMeshingRoundtable,SandiaNationalLab,pp.497-504,October19989 Krishnakumar,K.,"Micro-GeneticAlgorithmsforStationaryandNon-stationaryFunctionOptimization"SPIE'sIntelligentControlandAdaptiveSystemsConf.,PA,1196-32,1989All-QuadMeshGenerationfromStereolithography(STL)FilesChenTao+,GaoHui,LiGuangyao(StateKeyLaboratoryofAdvancedDesignand