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

關(guān)鍵詞:網(wǎng)格生成; 四邊形單元; 網(wǎng)格優(yōu)化; 鋪砌法

中圖分類號:TP391.7文獻(xiàn)標(biāo)識碼: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 引 言

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

1 鋪砌法網(wǎng)格生成算法

鋪砌法是一種全自動的網(wǎng)格生成方法，它不要求預(yù)先配置好內(nèi)部節(jié)點，單元和節(jié)點都在網(wǎng)格劃分的過程中自動生成。

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

為了保證在區(qū)域內(nèi)生成的單元全部為四邊形單元，要求初始邊界上的節(jié)點數(shù)目為偶數(shù)個。在鋪砌過程中，首先要在邊界上選擇網(wǎng)格生成的起始點，為了方便生成網(wǎng)格節(jié)點，本文取鋪砌邊界上內(nèi)角最小的節(jié)點為起始點。

1.2 網(wǎng)格單元的生成

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

1.2.1 以邊節(jié)點為基點的生成方法

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

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

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

圖1 邊界點生成法

1.2.2 以角節(jié)點為基點的生成方法

如圖2所示，由Ni-1，Ni，Ni+1生成三個新節(jié)點Nj，Nk，Ni，同時形成了兩個新單元。三個節(jié)點分別由矢量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 以轉(zhuǎn)角節(jié)點為基點的生成方法

如圖3所示，由Ni-1，Ni，Ni+1三點生成五個新節(jié)點Nj，Nk，Nl，Nm，Nn同時形成了三個單元。五個新節(jié)點分別由矢量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 以終止節(jié)點為基點的生成方法

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

圖2 角節(jié)點生成法

圖3 轉(zhuǎn)角節(jié)點生成法

圖4 終止節(jié)點生成法

2 相交處理

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

2.1 相交判斷

在鋪砌過程中，當(dāng)鋪砌邊界與自己或其他鋪砌邊界相交時，則至少存在一對邊相交如圖5(a)所示。通過判斷線段是否相交即可確定鋪砌邊界是否相交，假設(shè)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)

當(dāng)線段AB和CD相交時，則在交點處有:

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

或

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

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

Ax+uBx=Cx+wDx

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

令:

H=Bx -Dx

By -Dy(7)

則存在兩種情況:

當(dāng)H=0，則這兩條線段平行;當(dāng)H≠0，則這兩條線段相交，相交的相對位置由式(7)解得的u，w值而定。有了這些信息，就可以計算出適當(dāng)?shù)姆绞竭M(jìn)行相交處理。

圖5 相交判斷圖示

2.2 相交處理

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

3 縫合處理

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

3.1 小角度縫合處理

當(dāng)浮動邊界上節(jié)點的內(nèi)角小于某一給定的閾值時，將會在網(wǎng)格中形成一道細(xì)縫，此時應(yīng)該進(jìn)行小角度縫合處理，以便于后續(xù)網(wǎng)格的生成和提高網(wǎng)格的質(zhì)量，如圖6所示。

圖6 小角度縫合處理

圖6中:Ne為節(jié)點內(nèi)角頂點處與節(jié)點相連的邊數(shù);α為節(jié)點內(nèi)角;Nn為縫合后與縫合節(jié)點相連的邊數(shù)，其選取準(zhǔn)則是根據(jù)節(jié)點內(nèi)角大小和Ne決定，即:

α≤15°，Ne≥5

α≤30°，其他

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

3.2 過渡縫合處理

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

圖7 過渡縫合處理

4 網(wǎng)格質(zhì)量優(yōu)化

一般情況下，用上述算法生成的網(wǎng)格并不是最優(yōu)的，其中包含有一些質(zhì)量較差的單元，要對其進(jìn)行網(wǎng)格優(yōu)化，以便盡量減少不規(guī)則單元的數(shù)目。網(wǎng)格優(yōu)化技術(shù)大致可分為兩類:拓?fù)鋬?yōu)化和幾何優(yōu)化[8]。幾何優(yōu)化是調(diào)整網(wǎng)格中的節(jié)點位置，提高單元的幾何質(zhì)量，而節(jié)點之間連接關(guān)系保持不變。與此相對，改變節(jié)點之間的連接關(guān)系的網(wǎng)格優(yōu)化技術(shù)則稱為拓?fù)鋬?yōu)化。

4.1 網(wǎng)格拓?fù)鋬?yōu)化

拓?fù)潢P(guān)系是指網(wǎng)格節(jié)點的連接關(guān)系，拓?fù)潢P(guān)系的調(diào)整是指改變節(jié)點之間的連接關(guān)系，也包含通過增加或刪除網(wǎng)格中的節(jié)點[9]。

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

4.1.1 單元刪除

通過刪除某些單元可以改變局部的網(wǎng)格質(zhì)量，單元刪除涉及到三個檢測:節(jié)點檢測、邊檢測和單元檢測。

(1) 節(jié)點檢測。

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

(2) 邊檢測。

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

(3) 單元檢測。

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

圖8 節(jié)點刪除、邊刪除和單元刪除

4.1.2 單元交換

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

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調(diào)換成CD，如圖9(b)所示。

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

圖9 單元交換

4.2 網(wǎng)格幾何優(yōu)化

網(wǎng)格的幾何優(yōu)化處理指網(wǎng)格生成后進(jìn)行的網(wǎng)格調(diào)整，在保證單元尺寸、單元節(jié)點的拓?fù)潢P(guān)系的基礎(chǔ)上，進(jìn)行單元節(jié)點的重新布置。大部分的幾何優(yōu)化算法都是以某種順序遍歷網(wǎng)格中的節(jié)點，逐個調(diào)整節(jié)點位置，提高單元質(zhì)量。在網(wǎng)格幾何優(yōu)化過程中，普遍采用的技術(shù)是拉普拉斯光順處理(Laplacian Smoothing)。

目前為止拉普拉斯光順處理應(yīng)用得最廣泛、最有效，同時也是最成熟的網(wǎng)格優(yōu)化方法[10]。拉普拉斯光順?biāo)惴ǖ幕驹硎潜３志W(wǎng)格拓樸關(guān)系不變，將整個內(nèi)部節(jié)點的位置移動到由其相鄰節(jié)點組成的多邊形形心位置，從而優(yōu)化每個單元的形狀。將這個移動過程遍歷所有內(nèi)部節(jié)點若干次，可較大地提高網(wǎng)格質(zhì)量。拉普拉斯光順式如下:

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

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

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

圖10 網(wǎng)格修勻

5 網(wǎng)格生成實例

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

圖11 網(wǎng)格生成實例

6 結(jié) 語

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

這種方法與自適應(yīng)分析技術(shù)相結(jié)合，將是一種很有前途的有限單元自動生成方法，對船舶板架結(jié)構(gòu)有限元網(wǎng)格劃分起到積極重要的作用。

參考文獻(xiàn)

[1]關(guān)振群， 宋超， 顧元憲， 等. 有限元網(wǎng)格生成方法研究的新進(jìn)展[J]. 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報， 2003， 15(1): 1-14.

[2]李毅， 鮑勁松， 金燁， 等.二維域多約束四邊形有限元網(wǎng)格生成算法[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報， 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]龔光彩，張文宏，孫培雷，等. 網(wǎng)格自動生成技術(shù)進(jìn)展綜論[J]. 建筑熱能通風(fēng)空調(diào)， 2006， 25(1):26-31.

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

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

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

[9]陳立崗，鄭耀，陳建軍，等. 全四邊形有限元網(wǎng)格的拓?fù)鋬?yōu)化策略[J]. 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報， 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.