一種基于子域分解的表面混合網格生成方法

汪 攀 韓 磊 鞠傳明 池寶濤 張見明

湖南大學汽車車身先進設計制造國家重點實驗室，長沙,410082

一種基于子域分解的表面混合網格生成方法

汪 攀 韓 磊 鞠傳明 池寶濤 張見明

湖南大學汽車車身先進設計制造國家重點實驗室，長沙,410082

提出了一種新的基于子域分解的混合網格生成方法。該方法首先用映射法生成結構化背景網格，并確定實體表面上包含的小孔、鍵槽等小特征在背景網格中的位置，然后刪除這些小特征覆蓋的背景網格，并在這些區(qū)域內生成三角形網格，最后將剩余的背景網格和生成的三角形網格合并，得到整個目標域的網格。該算法綜合了映射法效率高、網格質量好、四邊形網格計算精度高，以及三角形網格幾何適應能力強的優(yōu)勢。數值實驗表明，針對復雜的實體表面，新方法能夠全自動地生成質量較好的混合網格，生成的網格質量及算法效率均優(yōu)于傳統(tǒng)的推進波前法和鋪磚法。

混合網格; 背景網格; 網格生成; 子域分解

0 引言

在求解各類工程和科學計算問題時，有限元法或邊界元法[1-2]已成為最有效的數值分析方法，其中，網格的劃分直接影響計算精度和計算效率。在表面網格剖分方法中，三角形網格的自動生成技術已經相當成熟，如Delaunay三角剖分算法[3-4]、前沿推進法(advancingfrontmethod,AFM)[5]等。在實際應用中，結構化的四邊形網格在計算精度和計算效率上都優(yōu)于三角形網格，但是相對于三角形網格的自動生成，四邊形網格的自動生成算法不是很成熟。常見的四邊形網格生成算法有映射法[6]、Q-Morph算法[7-8]、鋪磚法[9-10]，這些算法往往比較復雜，效率低，或者生成的網格質量不好。

在機械產品中，有許多含有小孔、鍵槽等小特征的零部件，若忽略這些小特征，則有一部分零部件的實體表面可以用映射法或子域映射法生成質量非常好的結構化四邊形網格，可是由于這些小特征的存在，無法用映射法生成結構化網格。為了解決這一問題，本文提出了一種新的基于子域分解的混合網格生成方法。該方法首先將復雜的目標域分解為多個簡單的子域，然后在各個子域上進行網格剖分，最后將各個子域的網格數據進行組裝，從而得到整個目標域的網格。對于帶小孔、鍵槽等小特征的表面，可將目標域的網格分為兩塊，第一塊是背景網格中刪除小孔覆蓋的區(qū)域后剩余的網格，這一部分區(qū)域不需要進行網格劃分，取有效的背景網格即可；第二塊是包含小特征的一個矩形空腔，這一部分區(qū)域相對狹小且無規(guī)則，對這一子塊進行網格剖分的時候，可以選用健壯性較好的算法生成非結構化的三角形網格。本文生成的網格用于邊界元軟件開發(fā)的前處理過程，由于邊界元法特殊的優(yōu)勢，面與面之間的網格可以不連續(xù)。

1 四邊形質量因子

網格質量直接影響計算精度，本文采用幾何準則對生成的網格質量進行評價。圖1所示的四邊形ABCD中，連接其對角線AC、BD，得到4個三角形△ABC、△ABD、△CDB、△CDA，先計算這4個三角形的質量因子，然后根據這4個質量因子，得到四邊形ABCD的質量因子。

三角形的質量因子α就是三角形的面積與邊長的平方和之比，即

α越大表示質量越好。令4個三角形△ABC、△ABD、△CDB、△CDA的質量因子依次為α1、α2、α3、α4，假設α1≥α2≥α3≥α4，則四邊形ABCD的質量因子β為

2 算法原理

本文提出的算法是一種基于子域分解的網格生成方法，該方法將一個復雜實體表面分解為多個子域，然后在子域上進行網格劃分，最后將子域網格合并，得到整個目標域的網格，其主要步驟如下:

(1)生成背景網格。以外邊界為基礎，用映射或子域映射法生成結構化的四邊形網格。結構化網格有很多優(yōu)點：網格生成的速度快，網格生成的質量高，數據結構簡單，算法效率高。

(2)確定小孔的位置。點在背景網格中的位置用參數Ncol、Nrow表示，其中Ncol為列數，Nrow為行數。為了確定小孔的位置，首先離散小孔邊界得到一系列的點，然后計算這些點對應的Ncol、Nrow，最后通過這些點在背景網格中的位置來確定小孔的位置。

(3)生成三角形網格。去除小孔覆蓋的背景網格，得到一個空腔，將此空腔和空腔包含的小孔作為前沿，運用其他健壯性較強的網格生成算法(本文采用推進波前法)生成三角形網格。

(4)數據的組裝。將有效的結構化四邊形網格和非結構化三角形網格組裝起來，得到整個目標域的網格數據。

3 算法實現過程

3.1 確定小孔在背景網格中的位置

小孔在背景網格中的位置由NcolL、NcolR、NrowD、NrowU4個參數確定，其中NcolL、NcolR表示矩形框的左右列數，NrowU、NrowD表示矩形框的上下行數。具體方法如下：首先將小孔的邊界離散，得到一系列的點，在參數空間計算每一個點在背景網格中的位置Ncol、Nrow。在圖2所示的背景網格中，假設點P在參數空間的坐標為(u,v)，第1行1列的點設為基準點，即圖2所示的(u0,v0)，設U向離散段數為NU，V向離散段數為NV，則Ncol和Nrow可以通過下式計算：

Ncol=(u-u0)/(Umax-Umin)NU
Nrow=(v-v0)/(Vmax-Vmin)NV

圖2 點在背景網格1中的位置Fig.2 The point location in background mesh 1

在圖3所示的背景網格中，由于參數空間相鄰的節(jié)點不是等距的，所以不能用圖2中的方法求Ncol和Nrow。此時應按如下方法計算：假設背景網格總行數為N+1，總列數為M+1，標記背景網格中任意一個節(jié)點的坐標為(um,vn)，其中m表示列數，n表示行數，假定P點的坐標為(u,v)，首先確定P點所在的列，若P點在(um,v0)、(um+1,v0)、(um+1,vN)、(um,vN)所構成的矩形框內，則有Ncol=m，然后確定P點位于哪一行，若點P在(um,vn)、(um+1,vn)、(um+1,vn+1)、(um,vn+1)所構成的矩形框內，則有Nrow=n，此時點在背景網格中的位置坐標(Ncol,Nrow)為(m,n)。

圖3 點在背景網格2中的位置Fig.3 The point location in background mesh 2

在實際操作中，可以根據需要適當擴大空腔，避免因空腔與小孔邊界構成的區(qū)域過于狹長而導致生成的三角形網格質量不理想。

3.2 確定有效的背景網格

小孔覆蓋的背景網格是無效的，這一部分的網格數據需要去除，如何快速定位這些無效的網格數據，將在很大程度上影響網格生成的效率。假設小孔在背景網格中的位置參數(NcolL、NcolR、NrowD、NrowU)已確定，則小孔覆蓋的無效節(jié)點在存儲節(jié)點的一維數組Node[·]中的位置可以通過下式計算：

for(i=NrowD+1；i

for(j=NcolL+1；j

Node[k]=NU*i+j

確定了無效節(jié)點后，通過結構化網格的拓撲關系搜索到與無效節(jié)點連接的邊，標記這些搜索到的邊為無效邊，小孔覆蓋的無效單元在存儲單元的一維數組Cell[·]的位置可以用下式計算：

for(i=NrowD；i

for(j=NcolL；j

Cell[k]=(NU-1)*i+j

在背景網格中，去除這些無效的節(jié)點、邊、單元之后，得到一個空腔。相對于整個目標域，此空腔相對狹小，在此狹小的空腔內，本文采用比較成熟且自適應能力較強的推進波前法生成非結構化的三角形網格。

3.3 得到前沿

用合適的尺寸對小孔進行離散，得到一系列的離散點，這一系列的點以及空腔的邊界，即為新的前沿。將新的前沿加入到前沿鏈表中，作為推進波前法的初始前沿，在基于八叉樹以及自適應尺寸場共同作用的尺寸控制方式下，可以生成質量良好且過渡均勻的非結構化三角形網格。由于每次輸入推進波前法的空腔以及空腔內包含的小孔必須一一對應，因此，當實體表面上包含多個小孔時，應對其小孔進行循環(huán)。每次輸入一個空腔以及其包含的小孔，若小孔所對應的空腔有重疊，會導致前沿相交，無法形成封閉的前沿，此時應對空腔進行特殊的處理，將重疊的空腔合并，得到一個連續(xù)封閉的環(huán)，并將其加入前沿鏈表。合并前后的空腔前沿如圖4所示。

(a)合并前 (b)合并后圖4 空腔前沿Fig.4 The front of cavities

3.4 邊界處網格質量的改善

實際計算中，邊界處的網格質量尤為重要，本文采用的推進波前法可以在邊界處生成質量較好且過渡均勻的三角形網格，但是在同等條件下，其計算精度和效率還是低于質量較好的結構化四邊形網格。為了改善小孔附近的網格質量，可以在小孔邊界處以按層推進的方式鋪設結構化四邊形網格，推進的層數由小孔邊界與空腔的最近距離決定。假設推進的層數為N，小孔邊界與空腔的最近距離為Dmin，網格尺寸為ksize，則有N=Dmin/ksize-2，其中減2的幾何意義是預留2層，使得這部分過渡區(qū)域能夠用推進波前法生成質量相對較好的三角形網格。當鋪設好的四邊形網格邊界與空腔邊界較近時，即使自適應能力較強的推進波前法也無法生成質量較好的三角形網格。圖5所示為小孔邊界推進層數為2的網格劃分。圖6所示為小孔的邊界與空腔邊界距離較小，推進的層數為0的網格劃分。

圖5 邊界推進層數為2的網格劃分Fig.5 The mesh generation with the layer of 2 boundary advancing

圖6 邊界推進層數為0的網格劃分Fig.6 The mesh generation with the layer of 0 boundary advancing

當出現小孔理想的離散尺寸遠小于全局的網格尺寸的情況時，為滿足計算精度，小孔附近的網格尺寸不宜過大；但由于網格連續(xù)性，會導致網格數目的增加。為了解決這個問題，本文引入了過渡單元，使小孔附近較小的網格尺寸保證了計算精度，且背景網格較大的網格尺寸減少了網格數目。網格劃分如圖7所示。

圖7 添加過渡模塊后的網格劃分Fig.7 The mesh generation with transition template

綜上所述，實現此算法的流程如下：

(1)用映射法或子域映射法生成結構化的四邊形背景網格。

(2)確定每個小孔在背景網格中的位置，然后刪除這些小孔覆蓋的背景網格。

(3)根據小孔在背景網格中的位置，對小孔進行分組，將空腔重疊的小孔分為一組，并對其空腔進行合并操作，假設小孔分為N組。

(4)for(i=0;i

{

得到小孔對應的空腔的前沿；

離散小孔，得到實體邊界的前沿；

根據實體邊界前沿與空腔的距離，選取合成的推進層數，生成結構化四邊形網格；

將上述前沿輸入推進波前法生成三角形網格；

}

(5)將有效的背景網格和生成的三角形網格進行組裝，得到整個目標域的網格數據，組裝后的網格在三角形和四邊形的交界處滿足網格連續(xù)性。

4 算例

本文給出4個常見的機械零部件模型的混合網格劃分實例，分別為帶孔洞的墊片(圖8a)、法蘭盤(圖8b)、階梯軸(圖8c)、帶焊縫的鋼架(圖9)。

(a)墊片 (b)法蘭盤

(c)階梯軸圖8 混合網格劃分Fig.8 The hybrid meshe generation

圖9 帶焊縫的鋼架的混合網格劃分Fig.9 The hybrid mesh generation of steel frame with welds

由圖8、圖9可知，本文提出的新方法在實際應用中具有可行性，從網格分布來說大部分區(qū)域具有結構化四邊形網格，少部分區(qū)域具有非結構化三角形網格。需要特別指出的是，對于帶焊縫的鋼架模型，由于系統(tǒng)誤差或布爾操作等原因，使得CAD數據中存在著小短邊、窄面和不光滑邊界等常見人工特征[11]。這些特征使得生成的網格質量較差，甚至會導致網格劃分失敗(如用鋪磚法生成四邊形網格)。對經過拓撲修復后的鋼架模型，用傳統(tǒng)的推進波前法則對鋼架進行網格劃分，會生成43 576個節(jié)點、 73 786個單元；采用本文介紹的新方法，會生成36 518個節(jié)點、43 267個單元。由此可見，新方法較大幅度地減小了生成網格的規(guī)模。

為了進一步說明新方法的優(yōu)越性，將法蘭盤和階梯軸中用新方法進行網格劃分的實體表面分別用推進波前法和鋪磚法進行網格劃分，網格劃分結果如圖10、圖11所示。對其生成的網格數量、質量及效率進行對比，結果如表1所示。

由表1可知，相對于推進波前法，新方法生成的網格數量減少了近1/2。對于法蘭盤和階梯軸，用新方法的耗時分別為推進波前法的1/5和1/3左右。相對于鋪磚法，新方法較大程度地提高了生成網格的質量，且耗時分別為鋪磚法的1/18和1/5。

(a)三角形網格 (b)四邊形網格圖10 法蘭盤的網格劃分Fig.10 The mesh generation of flange

(a)三角形網格 (b)四邊形網格圖11 階梯軸的網格劃分Fig.11 The mesh generation of stepped shaft

表1 網格數量、質量及三種方法效率的對比

5 結論

(1)本文提出的新方法生成的網格由絕大部分區(qū)域的結構化四邊形網格和少數區(qū)域的三角形網格組成，整個目標域的網格質量較好。

(2)新方法充分利用了映射法算法簡單、效率高、生成的網格好等優(yōu)勢，同時利用了推進波前法幾何自適應能力強的優(yōu)勢。

(3)數值實驗表明，本文提出的算法能夠針對復雜實體的表面全自動地生成質量較好的混合網格，且算法效率較高。

[1]ZHANGJianming,QINXianyun,HANXu.ABoundaryFaceMethodforPotentialProblemsinThreeDimensions[J].InternationalJournalforNumericalMethodinEngineering, 2009, 80(3): 320-337.

[2]DONGYunqiao,ZHANGJianming,XIEGuizhong,etal.AGeneralAlgorithmfortheNumericalEvaluationofDomainIntegralsin3DBoundaryElementMethodforTransientHeatConduction[J].EngineeringAnalysiswithBoundaryElements, 2015, 51(3): 30-36.

[3]SUT,WANGW,LVZ,etal.RapidDelaunayTriangulationforRandomlyDistributedPointCloudDataUsingAdaptiveHilbertCurve[J].Computers&Graphics, 2015, 54(C):65-74.

[4]BEDREGALC,RIVARAMC.NewResultsonLEPP-delaunayAlgorithmforQualityTriangulations[J].ProcediaEngineering, 2015, 124:317-329.

[5] 覃先云. 邊界面法的單元實現及其在復雜結構分析中的應用[D]. 長沙: 湖南大學, 2012.QINXianyun.AnElementImplementationoftheBoundaryFaceMethodandItsApplicationinAnalysisofComplexStructures[D].Changsha:HunanUniversity, 2012.

[6]RUIZ-GIRONSE,SARRATEJ.GenerationofStructuredMeshesinMultiplyConnectedSurfacesUsingSubmapping[J].AdvancesinEngineeringSoftware, 2010, 41(2):379-387.

[7] 李毅, 鮑勁松, 金燁,等. 二維域多約束四邊形有限元網格生成算法[J]. 計算機輔助設計與圖形學學報, 2008, 20(4):488-493.LIYi,BAOJinsong,JINYe,etal.QuadrilateralMeshGenerationAlgorithmforPlanarDomainwithMulti-constraints[J].JournalofComputer-AidedDesign&ComputerGraphics, 2008, 20(4):488-493.

[8]MERHOFD,GROSSR,TREMELU,etal.AnisotropicQuadrilateralMeshingGeneration:AnindirectApproach[J].EngineeringComputationalTechnology, 2007, 38(11/12): 860-867.

[9] 梅中義, 范玉青. 一種用于自動生成二維全四邊形有限元網格的改進的鋪設算法[J]. 計算機輔助設計與圖形學學報, 2000，12 (6)：428-434.MEIZhongyi,FANYuqing.AModifiedPavingTechniqueforQuadrilateralMeshGenerationinPlanarRegions[J].JournalofComputer-AidedDesign&ComputerGraphics,2000,12(6):428-434.

[10] 郭新強. 邊界面法四邊形網格生成研究與應用[D]. 長沙: 湖南大學, 2011.GUOXinqiang.StudyonQuadrilateralMeshGenerationfortheBoundaryFaceMethodandTheirImplementation[D].Changsha:HunanUniversity, 2011.

[11]BEALMW,WALSHJ,SHEPHARDMS.AccessingCADGeometryforMeshGeneration[J].InternationalMeshingRoundtableSandiaNationalLaboratories, 2003:33-42.

(編輯 王旻玥)

A New Surface Hybrid Mesh Generation Method Based on Subdomain Decomposition

WANG Pan HAN Lei JU Chuanming CHI Baotao ZHANG Jianming

State Key Laboratory of Advanced Design and Manufacturing for Vehicle Body,Hunan University,Changsha，410082

A new hybrid mesh generation method was proposed based on subdomain decomposition. First, the structured background meshes were generated by mapping method and the locations of small features such as hole and keyway were determined. Then, the meshes which covered by small features were eliminated from background meshes, and unstructured triangular meshes were generated in this region. Finally, the meshes of target domain were obtained by combining the background meshes and the unstructured triangular meshes. It is capable of preserving the advantages of mapping’s high efficiency and high quality of the meshes, high computational accuracy of quadrangle meshes and the powerful geometric adaptive capacity of triangle meshes. Numerical experiments show that the proposed method may generate high quality hybrid meshes for complex surfaces automatically, the quality of resulting meshes and the algorithm efficiency are superior to traditional methods such as advancing front method and paving.

hybrid mesh; background mesh; mesh generation; subdomain decomposition

2016-07-11

國家自然科學基金資助項目(11472102)

TP391DOI：10.3969/j.issn.1004-132X.2017.06.008

汪 攀，男，1987年生。湖南大學汽車車身先進設計制造國家重點實驗室博士研究生。主要研究方向為有限元網格劃分技術。韓 磊，男，1988年生。湖南大學汽車車身先進設計制造國家重點實驗室博士研究生。鞠傳明，男，1991年生。湖南大學汽車車身先進設計制造國家重點實驗室博士研究生。池寶濤，男，1991年生。湖南大學汽車車身先進設計制造國家重點實驗室博士研究生。張見明(通信作者)，男，1965年生。湖南大學汽車車身先進設計制造國家重點實驗室教授、博士研究生導師。E-mail:zhangjm@hnu.edu.cn。