一種改進的全四邊形網格生成方法及優化

摘 要:在任意二維區域的全四邊形網格生成方法中，鋪砌法是目前較好的一種方法。但是當邊界出現不規則區域時，網格生成完畢后內部會產生一些質量較差的單元，且判斷網格交叉現象是否發生和解決網格交叉問題比較困難。為了提高該方法的適應性和可靠性，提出一種新的改進算法，它對邊界不規則區域網格生成和解決網格交叉問題等關鍵技術進行改進，并加入四邊形網格優化方法，將改進后的鋪砌法應用于船舶有限元網格劃分中，取得了較好的應用效果，最后給出算例進行了驗證。

關鍵詞:網格生成; 四邊形單元; 網格優化; 鋪砌法

中圖分類號:TP391.7文獻標識碼:A

文章編號:1004-373X(2010)08-0119-04

Modified Method and Optimization ofGenerating All-quadrilateral Mesh

LI Xiao-hui， LI Chang-hua

(Information and Control Engineering School， Xi’an University of Architecture and Technology， Xi’an710055， China)

Abstract: The paving method among the quadrilateral mesh generation methods in the arbitrary two-dimensionalis better. However， when irregular area is appeared at the border， some poor meshes are generated in the internal area after mesh generation， and it is difficult to determine cross-border phenomenon in irregular region and resolve the cross-cutting issues. A modifiedalgorithm is proposed to enhance the adaptability and reliability of the method. It improves the key technologies of generating meshes in irregular region and resolving the cross-border problem. In combination withthe quadrilateral mesh optimization algorithm， the improved paving method was applied in the finite element meshing for a ship and a good effect was obtained. An example is given for verifying the efficiency of the proposed method.

Keywords:mesh generation; quadrilateral element; mesh optimization; paving method

0 引 言

隨著計算機科學技術的快速發展，以有限元技術為代表的數值方法得到了廣泛應用。然而，制約其進一步發展的主要因素之一是網格劃分技術和優化技術，特別是在船舶板架的有限元網格劃分中，由于精度和質量上的考慮，要求網格單元盡量是四邊形。目前，網格生成方法[1]主要有Delaunay三角化方法、鋪砌法(Paving)、四(八)叉樹法、行波法等[2]。其中，鋪砌法是由T.D.Blacker 和M.B.Stephenson 提出的[3]，該算法重復地在區域邊界內部放一層或者鋪一層單元，從區域邊界開始向內部形成四邊形單元。White[4]重新設計了鋪砌算法，單元不是生成一排，而是一個接一個的生成，它生成的網格質量和靈活性要優于其他算法，尤其是邊界單元(接近正方形)[5]。方興、張武等[6]在White的基礎上對鋪砌法做了改進，主要是提出一種節點計算方法，但是在復雜區域的相交和縫合處理等方面仍有不足。這里在該方法的基礎上進行了一些改進，即在每個新單元的生成過程中，隨時判斷有無交叉，現象發生，若出現交叉則進行相交和縫合處理，而不是等待層生成完畢再處理，這樣相交判斷和處理就得到了很大的簡化。同時對小角度縫合處理做了改進，增強了邊界適應性。最后加入網格優化模塊，進一步提高了區域內部的網格質量。

1 鋪砌法網格生成算法

鋪砌法是一種全自動的網格生成方法，它不要求預先配置好內部節點，單元和節點都在網格劃分的過程中自動生成。

1.1 輸入初始條件與起始點的選擇

為了保證在區域內生成的單元全部為四邊形單元，要求初始邊界上的節點數目為偶數個。在鋪砌過程中，首先要在邊界上選擇網格生成的起始點，為了方便生成網格節點，本文取鋪砌邊界上內角最小的節點為起始點。

1.2 網格單元的生成

新節點一般是以邊界上相鄰的三點為基礎的，并以一定的角度和方向向區域內部投射而生成。如:新節點的生成是以當前邊界上Ni-1，Ni，Ni+1這3個節點為基礎的，假設節點Ni的內角為α;節點Ni-1到節點Ni的距離為d1;節點Ni到Ni+1的距離為d2，則根據節點夾角α的不同可分為四種類型，即:終止節點:α≤120°+δ;邊界節點:120°+δ<α≤240°+δ;角節點:240°+δ<α≤300°+δ;轉角節點:α>300°+δ。其中，取5°<δ<10°。

1.2.1 以邊節點為基點的生成方法

如圖1(a)所示，由節點Ni-1，Ni，Ni+1組成當前鋪砌邊界，生成新節點Nj，同時這四個節點形成了一個新單元。設新節點是由矢量V所決定的，V平分內角α，長度由下式定義:

|V|=d1+d22sin(α/2)(1)

對于兩節點皆為邊節點的特殊情況下新節點的生成如圖1(b)所示。按照邊節點的生成算法，由節點Ni生成新節點Nj，由節點Ni+1生成新節點Nk，同時這四個節點形成一個新單元。

圖1 邊界點生成法

1.2.2 以角節點為基點的生成方法

如圖2所示，由Ni-1，Ni，Ni+1生成三個新節點Nj，Nk，Ni，同時形成了兩個新單元。三個節點分別由矢量Vj，Vk，Vl決定。矢量Vj，Vk，Vl與Ni-1Ni的夾角分別為α/3，α/2，2α/3，長度由下式定義:

|Vj|=d1+d22sin(α/3)，|Vk|=2|Vj|，|Vl|=|Vj|(2)

1.2.3 以轉角節點為基點的生成方法

如圖3所示，由Ni-1，Ni，Ni+1三點生成五個新節點Nj，Nk，Nl，Nm，Nn同時形成了三個單元。五個新節點分別由矢量Vj，Vk，Vl，Vm，Vn決定。矢量Vj，Vk，Vl，Vm，Vn與Ni-1Ni的夾角分別為α/4，3α/8，α/2，5α/8，3α/4，長度由下式定義:

|Vj|=d1+d22sin(α/4)，|Vk|=2|Vj|，

|Vl|=|Vj|，|Vm|=|Vk|，|Vn|=|Vj|(3)

1.2.4 以終止節點為基點的生成方法

如圖4所示，在網格生成過程中，遇到終止節點時通常不生成新節點，只是通過連接已存在的節點生成一個新節點。如:Ni為終止節點，Ni-1，Ni+1分別為邊界上Ni的前一節點和后一節點。如果Ni-1也為終止節點，則Nj，Ni-1，Ni，Ni+1就構成一個單元。

圖2 角節點生成法

圖3 轉角節點生成法

圖4 終止節點生成法

2 相交處理

在網格生成過程中，本文對邊界相交處理順序進行了調整。在新單元的生成過程中，隨時判斷有無交叉現象的發生，若出現交叉則立即進行相交處理，這樣只是局部個別網格的交叉和重疊，簡化了對交叉重疊問題的處理，也使算法更加穩定可靠。

2.1 相交判斷

在鋪砌過程中，當鋪砌邊界與自己或其他鋪砌邊界相交時，則至少存在一對邊相交如圖5(a)所示。通過判斷線段是否相交即可確定鋪砌邊界是否相交，假設AB與CD為兩條相交線段，A表示為從原點到A點的矢量;B表示為從A點到B點的矢量;C表示為從原點到C點的矢量;D表示為從C點到D點的矢量，則線段AB上P點的位置矢量和線段CD上Q點的位置矢量分別表示為:

P(u)=A+uB， u∈[0，1]

Q(u)=C+wD，w∈[0，1](4)

當線段AB和CD相交時，則在交點處有:

P(u)=Q(u)

或

A+uB=C+wD(5)

由式(5)轉化為線性方程組，可得:

Ax+uBx=Cx+wDx

Ay+uBy=Cy+wDy(6)

令:

H=Bx -Dx

By -Dy(7)

則存在兩種情況:

當H=0，則這兩條線段平行;當H≠0，則這兩條線段相交，相交的相對位置由式(7)解得的u，w值而定。有了這些信息，就可以計算出適當的方式進行相交處理。

圖5 相交判斷圖示

2.2 相交處理

在生成新單元的過程中，一旦判斷到相交情況的發生，就立即轉入相交處理模塊進行相交的處理。根據最近原則重新連接，形成新的鋪砌邊界。如果當前邊界與自己發生相交，則邊界分割后形成兩個新的鋪砌邊界;如果是與其他邊界相交，則兩條邊界連接后合并為一條鋪砌邊界，如圖5(b)所示。但前提是保證新生成的鋪砌邊界上的節點數為偶數，若為奇數，則通過調整相應的參數u和w來調整分割或連接的位置。相交處理完之后要進行縫合和光順處理。

3 縫合處理

網格生成的過程中，可能會出現內角較小的節點，這時可以通過小角度縫合處理來消除此夾角，有時也可能會出現相鄰邊長短懸殊較大的情況，此時可通過過渡縫合處理的辦法使過渡更加均勻化[7]。

3.1 小角度縫合處理

當浮動邊界上節點的內角小于某一給定的閾值時，將會在網格中形成一道細縫，此時應該進行小角度縫合處理，以便于后續網格的生成和提高網格的質量，如圖6所示。

圖6 小角度縫合處理

圖6中:Ne為節點內角頂點處與節點相連的邊數;α為節點內角;Nn為縫合后與縫合節點相連的邊數，其選取準則是根據節點內角大小和Ne決定，即:

α≤15°，Ne≥5

α≤30°，其他

分別采取圖5(a)，(b)的方法。

3.2 過渡縫合處理

當網格生成單元的相鄰邊長比例過大時，在此基礎上生成的網格將會產生畸變。此時可以通過嵌入單元，改變節點連接來處理。如圖7所示，如果兩相鄰邊的長短比值大于設定值(本文取2)時，則應該在長邊插入一個楔形單元來改善相鄰邊的過渡。在長邊中點增加一節點d，且節點d在2/3位置處。

圖7 過渡縫合處理

4 網格質量優化

一般情況下，用上述算法生成的網格并不是最優的，其中包含有一些質量較差的單元，要對其進行網格優化，以便盡量減少不規則單元的數目。網格優化技術大致可分為兩類:拓撲優化和幾何優化[8]。幾何優化是調整網格中的節點位置，提高單元的幾何質量，而節點之間連接關系保持不變。與此相對，改變節點之間的連接關系的網格優化技術則稱為拓撲優化。

4.1 網格拓撲優化

拓撲關系是指網格節點的連接關系，拓撲關系的調整是指改變節點之間的連接關系，也包含通過增加或刪除網格中的節點[9]。

對四邊形網格而言，四邊形單元的最佳形狀是正方形，其內角為90°，因而，其內部節點的相鄰單元個數Ne(節點周圍的單元數目)最好為4，這樣可以使這一結點的周圍單元在此點的平均內角為90°。當某一個內部節點的Ne比4大或小很多時，環繞該節點的單元就會產生很大的畸變，此時，就應該對其調整，主要的調整方法有單元刪除和單元交換。

4.1.1 單元刪除

通過刪除某些單元可以改變局部的網格質量，單元刪除涉及到三個檢測:節點檢測、邊檢測和單元檢測。

(1) 節點檢測。

如果某一節點周圍只有兩個單元，并且該節點不在約束邊界上，則該節點刪除，以該節點為端點的兩條邊也同時刪除，兩個單元合并為一個單元，如圖8(a)所示。通過刪除這些節點，可以很好地刪除對網格質量有重要影響的凹四邊形。

(2) 邊檢測。

如果某一邊的兩個端點周圍都是三個單元，如圖8(b)所示，刪除該邊和兩個單元E1，E2。新四邊形有兩種選擇，取Ne值最小的為最終邊。

(3) 單元檢測。

如果某一四邊形單元E1的對角線上兩端的節點N1，N2周圍都是三個單元，則應該刪除四邊形單元E1應該刪除，同時N1和N2合并為一個節點，如圖8(c)所示。

圖8 節點刪除、邊刪除和單元刪除

4.1.2 單元交換

依次對所有由內部節點連接的單元邊進行檢驗，如圖9(a)所示，若滿足Ne(A)+ Ne(B) ≥ 9，公共邊AB將被調換成CD或者EF，單元邊滿足以下關系:

N1=Ne(A)+Ne(B);N2=Ne(C)+Ne(D);

N3=Ne(E)+Ne(F)

(1) N1≥N2+3且N3≥N2公共邊AB調換成CD，如圖9(b)所示。

(2) N1≥N3+3且N2≥N3公共邊AB調換成EF，如圖9(c)所示。

圖9 單元交換

4.2 網格幾何優化

網格的幾何優化處理指網格生成后進行的網格調整，在保證單元尺寸、單元節點的拓撲關系的基礎上，進行單元節點的重新布置。大部分的幾何優化算法都是以某種順序遍歷網格中的節點，逐個調整節點位置，提高單元質量。在網格幾何優化過程中，普遍采用的技術是拉普拉斯光順處理(Laplacian Smoothing)。

目前為止拉普拉斯光順處理應用得最廣泛、最有效，同時也是最成熟的網格優化方法[10]。拉普拉斯光順算法的基本原理是保持網格拓樸關系不變，將整個內部節點的位置移動到由其相鄰節點組成的多邊形形心位置，從而優化每個單元的形狀。將這個移動過程遍歷所有內部節點若干次，可較大地提高網格質量。拉普拉斯光順式如下:

Xi=1Ni∑Nij=1Xj

Yi=1Ni∑Nij=1Yj(8)

式中:Ni是與節點i相鄰的節點總數;j是與i相連的節點;Xj和Yj是節點j的坐標值。使用這種方法簡單可靠，計算效率高，對網格質量的提高起到了非常重要的作用。但是Laplace修勻同樣也具有準則法所固有的不足，最根本的問題在于不能確定修勻后的網格是否為最優網格。圖10給出網格優化前后的比較。由于鋪砌法由于是從邊界向區域內部生成單元，所以內部單元的質量比較差。圖中經Laplace修勻后，中心的網格質量得到提高。

圖10 網格修勻

5 網格生成實例

圖11給出用上述鋪砌法生成的網格圖。由圖中可以看出，區域邊界幾何形狀復雜，截面變化較大，屬于復雜邊界情況。但從生成的網格來看，不僅邊界擬合良好，而且網格質量較高。

圖11 網格生成實例

6 結 語

通過對鋪砌法進行了的改進，實現了對任意復雜區域全四邊形網格的自動劃分。與原算法相比，本算法的優越性主要體現在:在網格生成之前對初始邊界進行先處理，增強了程序的適應性;原算法中待一層單元生成完畢后再進行相交處理，本文采用邊生成邊進行相交判斷，一旦發現相交情況，立即轉入相交處理模塊，使相交處理極為方便;縫合處理時，對不同小角度進行分組縫合處理，提高了網格單元的質量;最后通過幾何優化和拓撲優化改進了網格質量。由實例可以看出，網格質量良好，尤其是區域內部。

這種方法與自適應分析技術相結合，將是一種很有前途的有限單元自動生成方法，對船舶板架結構有限元網格劃分起到積極重要的作用。

參考文獻

[1]關振群， 宋超， 顧元憲， 等. 有限元網格生成方法研究的新進展[J]. 計算機輔助設計與圖形學學報， 2003， 15(1): 1-14.

[2]李毅， 鮑勁松， 金燁， 等.二維域多約束四邊形有限元網格生成算法[J].計算機輔助設計與圖形學學報， 2008， 20(4): 488-493.

[3]BLACKER T D，STEPHENSON M B. Paving:a new approach to automated quadrilateral mesh generation[J]. International Journal for Numerical Methods in Engineering，1991， 32(4):811-847.

[4]WHITE D R， KINNEY P. Redesign of the paving algorithm: robustness enhancements through element by element meshing[C]//Processings of 6th International Meshing Roundtable\\: \\，1997: 323-335.

[5]龔光彩，張文宏，孫培雷，等. 網格自動生成技術進展綜論[J]. 建筑熱能通風空調， 2006， 25(1):26-31.

[6]方興，張武，唐錦春，等. 一種改進的生成有限元全四邊形網格的鋪砌法[J]. 浙江理工大學學報， 2005， 22(1):70-73.

[7]賈虹，盧炎麟，高發興， 等. 高品質全四邊形有限元網格生成的鋪砌法[J]. 浙江工業大學學報， 2000，28(4): 353-357.

[8]朱寶利，吳麗娟. 四邊形網格優化處理研究[J]. 沈陽師范大學學報， 2007，25(1): 42-45.

[9]陳立崗，鄭耀，陳建軍，等. 全四邊形有限元網格的拓撲優化策略[J]. 計算機輔助設計與圖形學學報， 2007，19(1): 78-83.

[10]LEE K Y， KIM I I， CHO D Y， et al. An algorithm for automatic 2D quadrilateral mesh generation with line cons-traints[J]. Computer Aided Design， 2003， 35(12):1055-1068.