馬 鈞 霆，陳 鎖 忠，劉 歡，張 潔

(南京師范大學(xué)虛擬地理環(huán)境教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210023)

?

一種前沿推進(jìn)的自適應(yīng)三角網(wǎng)生成算法

馬 鈞 霆，陳 鎖 忠*，劉 歡，張 潔

(南京師范大學(xué)虛擬地理環(huán)境教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210023)

現(xiàn)有前沿推進(jìn)算法在利用前沿推進(jìn)法對(duì)二維平面區(qū)域進(jìn)行自適應(yīng)三角網(wǎng)剖分時(shí)，由于前沿邊形態(tài)包含復(fù)雜的幾何特征，導(dǎo)致網(wǎng)格單元質(zhì)量不高、算法速度慢、魯棒性低。該文提出一種兼顧三角單元質(zhì)量及魯棒性的三角網(wǎng)生成算法。首先，將前沿邊內(nèi)向推進(jìn)過(guò)程中的所有形態(tài)歸納為4種類型；然后利用候選網(wǎng)格點(diǎn)試探算法構(gòu)建最優(yōu)三角單元，并通過(guò)相鄰前沿線段內(nèi)夾角搜索閾值分級(jí)讓步的方式維護(hù)算法魯棒性。實(shí)驗(yàn)表明：該算法能夠快速識(shí)別并處理復(fù)雜的前沿邊形態(tài)特征，生成單元疏密過(guò)渡均勻且質(zhì)量較高的自適應(yīng)三角網(wǎng)。

前沿推進(jìn)法；自適應(yīng)三角網(wǎng)；讓步算法；網(wǎng)格質(zhì)量

在諸多網(wǎng)格生成算法中，前沿推進(jìn)法[1,2]對(duì)邊界擬合性能優(yōu)越，生成網(wǎng)格質(zhì)量好、網(wǎng)格單元疏密過(guò)渡平滑，是較為主流的網(wǎng)格生成算法之一。長(zhǎng)期以來(lái)，對(duì)其研究主要圍繞兩方面：一為AFT算法提供尺寸信息的背景網(wǎng)格的構(gòu)建方法[3,4]；二是復(fù)雜形態(tài)前沿邊影響下候選網(wǎng)格點(diǎn)最優(yōu)位置計(jì)算方法及單元構(gòu)建策略[5,6]。對(duì)于背景網(wǎng)格構(gòu)建問題，現(xiàn)有許多研究指出，可通過(guò)模擬介質(zhì)的幾何特征自動(dòng)識(shí)別算法構(gòu)建背景網(wǎng)格[7,8]；也有學(xué)者提出可采用調(diào)和函數(shù)作為背景網(wǎng)格的基本信息[4]；而對(duì)于候選網(wǎng)格點(diǎn)的位置計(jì)算方法，多在傳統(tǒng)前沿推進(jìn)算法的基礎(chǔ)上，依據(jù)經(jīng)驗(yàn)對(duì)單元構(gòu)建策略進(jìn)行完善和改進(jìn)，在背景網(wǎng)格尺寸變異較大區(qū)域，往往導(dǎo)致網(wǎng)格出現(xiàn)無(wú)法收斂的情況[9]。為此，本文充分考慮前沿邊復(fù)雜形態(tài)影響下網(wǎng)格單元質(zhì)量的受損機(jī)制及最優(yōu)單元構(gòu)建策略，提出了一種兼顧三角單元質(zhì)量及魯棒性的自適應(yīng)網(wǎng)格生成算法，該算法能夠快速識(shí)別并處理復(fù)雜的前沿邊形態(tài)特征，生成單元疏密過(guò)渡均勻且質(zhì)量較高的自適應(yīng)三角網(wǎng)。

1 算法概述

基于現(xiàn)有前沿推進(jìn)法的基本過(guò)程[10]，提出如下改進(jìn)的算法：1)邊界離散和前沿邊的初始化；2)選取一條前沿線段，從背景網(wǎng)格中提取期望單元尺寸，結(jié)合選中前沿線段長(zhǎng)度計(jì)算最優(yōu)網(wǎng)格單元尺寸[11]；3)計(jì)算候選網(wǎng)格節(jié)點(diǎn)，依據(jù)其與前沿邊的拓?fù)潢P(guān)系及當(dāng)前所選線段與相鄰線段之間夾角大小，自動(dòng)識(shí)別當(dāng)前的前沿邊形態(tài)類型；4)調(diào)用單元構(gòu)建策略，形成有效網(wǎng)格單元，更新前沿邊及網(wǎng)格的拓?fù)潢P(guān)系；5)判斷前沿邊中所包含前沿線段數(shù)量是否為0，若為0即完成網(wǎng)格的生成，否則執(zhí)行步驟2。

與傳統(tǒng)前沿推進(jìn)法相比，本算法引入了前沿邊形態(tài)類型自動(dòng)識(shí)別算法，所設(shè)計(jì)的最優(yōu)單元構(gòu)建策略模塊可被快速檢索與調(diào)用以生成自適應(yīng)網(wǎng)格。

2 前沿邊形態(tài)類型與單元構(gòu)建策略

2.1 基本形態(tài)與策略分析

隨著前沿線段的推進(jìn)，新建單元邊與前沿邊出現(xiàn)交叉或距離太近的情況。此時(shí)，通過(guò)數(shù)次減小最優(yōu)單元尺寸的方式[12]，重新嘗試構(gòu)建網(wǎng)格單元。若多次減小單元尺寸后依然無(wú)法形成有效的網(wǎng)格單元，考慮如下單元構(gòu)建策略：1)判斷當(dāng)前所選線段與相鄰前沿線段之間的內(nèi)夾角大??；2)若為銳角，則連接內(nèi)夾角的兩個(gè)非公共點(diǎn)構(gòu)建新三角單元，若新單元內(nèi)部不包含其他網(wǎng)格點(diǎn)，則為有效單元，單元構(gòu)建完成；3)若為鈍角，如圖1，作該鈍角的角平分線，設(shè)為AD，長(zhǎng)度為最優(yōu)單元尺寸h0，將鈍角分為兩銳角，分別連接CD、BD，在判斷單元有效性的基礎(chǔ)上，形成新單元；4)若兩個(gè)內(nèi)夾角均大于180°，此時(shí)需進(jìn)一步分析前沿邊形態(tài)特征，尋找可行的單元構(gòu)建方案。為此，提出單元試探構(gòu)建算法。

圖1 夾角為鈍角時(shí)的單元構(gòu)建策略示意

Fig.1 Element construction strategy for obtuse angle situation

2.2 形態(tài)變更驅(qū)動(dòng)的單元試探構(gòu)建算法

針對(duì)傳統(tǒng)前沿推進(jìn)算法可能引發(fā)前沿邊斷裂的問題[11]，提出通過(guò)更改前沿邊形態(tài)的方式，驅(qū)動(dòng)當(dāng)前被選中前沿線段與其相鄰線段之間拓?fù)潢P(guān)系發(fā)生改變，并試探改變后的前沿邊形態(tài)是否支持構(gòu)建有效單元。具體過(guò)程如圖2所示：線段AB為當(dāng)前前沿線段，依據(jù)單元構(gòu)建策略，無(wú)法形成有效單元；此時(shí)，以90°為閾值，遍歷前沿線段，搜尋到一個(gè)小于90°的夾角(∠ACE)；連接AE，更新前沿邊，重復(fù)調(diào)用單元構(gòu)建策略，此時(shí)前沿線段AB可與AE直接相連形成有效單元，完成單元構(gòu)建。

上述算法可保證以當(dāng)前線段為底邊形成有效單元。但若前沿邊包含的所有內(nèi)夾角均大于給定閾值，依據(jù)上述算法，其形態(tài)將不發(fā)生變更，導(dǎo)致算法鎖死，故閾值不能設(shè)為定值。但不同的閾值對(duì)前沿邊形態(tài)的改變?cè)斐刹煌绊?，因此需要設(shè)計(jì)閾值的動(dòng)態(tài)調(diào)整策略。

圖2 前沿邊形態(tài)變更驅(qū)動(dòng)的單元構(gòu)建方法

Fig.2 Element construction method driven by the front-line morphology changes

2.3 網(wǎng)格的發(fā)散與閾值分級(jí)讓步機(jī)制

前沿邊形態(tài)的改變與內(nèi)夾角的搜索閾值有著密切關(guān)系。一般情況下，當(dāng)搜索閾值為銳角時(shí)，新得前沿線段的長(zhǎng)度與兩個(gè)作為夾角邊的前沿線段的平均長(zhǎng)度相差不大，從而保證了新形成的單元尺寸的穩(wěn)定性與收斂性。而當(dāng)搜索閾值為鈍角時(shí)，則容易導(dǎo)致網(wǎng)格的發(fā)散效應(yīng),圖3所示為搜索閾值為較大的鈍角時(shí)出現(xiàn)的網(wǎng)格“發(fā)散”效應(yīng)。

圖3 鈍角三角單元的“發(fā)散”效應(yīng)

Fig.3 Obtuse triangle element “divergence” effect

為抑制這種“發(fā)散”效應(yīng)，提出閾值的分級(jí)讓步機(jī)制：設(shè)定初始閾值為銳角，遍歷前沿邊包含內(nèi)夾角；一次遍歷完成后，前沿邊形態(tài)如未發(fā)生任何變動(dòng)，則將搜索角度閾值增加一個(gè)微小量，重復(fù)搜索過(guò)程，直到前沿邊形態(tài)發(fā)生有效變更。

2.4 前沿邊形態(tài)類型劃分

前沿邊形態(tài)變化較為復(fù)雜，但前沿邊與候選網(wǎng)格點(diǎn)之間的拓?fù)潢P(guān)系變化則有明顯規(guī)律，為規(guī)范算法框架，對(duì)其形態(tài)進(jìn)行分類。分類思路為：針對(duì)一種前沿邊形態(tài)，首先依據(jù)傳統(tǒng)AFT算法構(gòu)建新單元，若可形成有效單元，則視作理想的前沿邊類型；若無(wú)法形成有效單元，則依次嘗試不同備選策略構(gòu)建新單元，將前沿邊形態(tài)劃分為4種類型(圖4)：類型一：候選網(wǎng)格點(diǎn)滿足有效性要求；類型二：候選網(wǎng)格點(diǎn)未通過(guò)有效性檢驗(yàn)，但當(dāng)前所選線段與相鄰前沿邊線段之間內(nèi)夾角為銳角，且連接該角度非公共點(diǎn)可形成有效三角單元；類型三：當(dāng)前所選線段與其相鄰前沿邊之間內(nèi)夾角為鈍角，通過(guò)做該鈍角的角平分線構(gòu)建的單元為有效3角單元；類型四：前3種情況下均無(wú)法得到有效單元，此時(shí)采用單元試探構(gòu)建算法和閾值分級(jí)讓步算法完成有效單元的構(gòu)建。

以上4種類型涵蓋了所有可能出現(xiàn)的形態(tài)類型。所用備選策略的適用性依次增加，而構(gòu)建格網(wǎng)單元質(zhì)量依次降低。前沿推進(jìn)過(guò)程中，大多數(shù)前沿邊形態(tài)屬于類型一和類型二，僅在背景網(wǎng)格中尺寸變異性較大或前沿邊交匯處，常見類型三或類型四的前沿邊形態(tài)。因此網(wǎng)格整體質(zhì)量損耗得到了有效控制。

圖4 前沿邊形態(tài)分類示意

Fig.4 Front line geometric feature type diagram

3 自適應(yīng)網(wǎng)格生成算法流程

前沿邊更新一般包括原有沿邊線段的刪除、插入及拓?fù)潢P(guān)系的重構(gòu)三部分?？刹捎盟牟鏄鋄13]或Alternative Digital Tree(ADT)[14]的數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲(chǔ)，以提高更新效率。理論上講，前沿邊上任何一個(gè)前沿線段均可作為當(dāng)前前沿線段被選取出來(lái)以構(gòu)建網(wǎng)格單元，但一些文獻(xiàn)[15,16]已證明：每次選取長(zhǎng)度最小的前沿線段時(shí)，所得網(wǎng)格過(guò)渡性更好。因此，本文選取長(zhǎng)度最短邊作為當(dāng)前前沿線段，網(wǎng)格生成算法具體步驟如下：

步驟1：?jiǎn)卧叽绫尘熬W(wǎng)格構(gòu)建，區(qū)域邊界離散、前沿邊的初始化。

步驟2：選中當(dāng)前前沿邊上的最短線段，計(jì)算其中點(diǎn)位置處的最優(yōu)網(wǎng)格單元尺寸和候選網(wǎng)格點(diǎn)位置。最優(yōu)單元尺寸的計(jì)算公式[5]為：

(1)

(2)

式中：S為三角形單元面積，a、b、c表示三角單元三邊長(zhǎng)度，s為三角形單元的實(shí)際尺寸，ρ為三角形單元在中點(diǎn)位置處從背景網(wǎng)格中提取的尺寸，α反映了三角形的形態(tài)質(zhì)量[17]，α取值范圍為(0,1)，其值越接近1，三角形形態(tài)越接近正三角形，質(zhì)量越好(表1)。

表1 三角單元形態(tài)及其α值示例

Table 1 Triangles quality and their α-quality

單元形態(tài)單元形態(tài)質(zhì)量α1．00．980．720．45

圖5 候選節(jié)點(diǎn)N的最優(yōu)單元尺寸h示意

Fig.5OptimaloffsetheighthofcandidatepointN

求取待構(gòu)建單元的最佳尺寸，令f=h/d，k=H/d，此時(shí)由式(2)可得：

(3)

F(f)=f3+2.25f-3k=0

(4)

取f0= 0，F(xiàn)(f0)=-3k，根據(jù)牛頓迭代法有：

(5)

(6)

由式(5)和式(6)經(jīng)過(guò)數(shù)次迭代后，解得f的近似值，即得單元實(shí)際尺寸h0=f×d。依據(jù)h0所構(gòu)建的單元能夠在單元的自適應(yīng)性和形態(tài)質(zhì)量之間取得最優(yōu)平衡，h0即為構(gòu)建網(wǎng)格單元的最優(yōu)尺寸。

步驟3：若候選網(wǎng)格點(diǎn)所構(gòu)建單元為無(wú)效單元，令h0 = 0.8×h0，重新計(jì)算候選網(wǎng)格點(diǎn)位置，并在h0 > |AB|/2的前提下，判斷能否形成有效單元。如能形成有效單元，則執(zhí)行步驟8，否則執(zhí)行步驟4。

步驟4：如當(dāng)前選中線段與相鄰線段之間內(nèi)夾角為銳角，且通過(guò)連接夾角非公共點(diǎn)可形成有效單元，則執(zhí)行步驟8，否則執(zhí)行步驟5。

步驟5：如當(dāng)前選中線段與相鄰線段之間內(nèi)夾角為鈍角，且通過(guò)作該夾角角平分線可形成有效單元，則執(zhí)行步驟8，否則執(zhí)行步驟6。

步驟6：設(shè)定閾值，遍歷前沿邊包含內(nèi)夾角，搜尋角度小于閾值的內(nèi)夾角，若嘗試連接該夾角的非公共點(diǎn)能形成有效單元，且改變后的前沿邊形態(tài)支持連接當(dāng)前選中線段與其相鄰線段非公共點(diǎn)而形成有效單元，則執(zhí)行步驟8，否則執(zhí)行步驟7。

步驟7：給閾值增加一微小量，通常為5°或10°，執(zhí)行步驟6。

步驟8：構(gòu)建新的網(wǎng)格單元，更新前沿邊和網(wǎng)格的拓?fù)潢P(guān)系，判斷前沿邊中包含前沿線段個(gè)數(shù)，如大于0則執(zhí)行步驟2，如等于0則完成網(wǎng)格的生成，退出算法。

4 網(wǎng)格的優(yōu)化與平滑

提出鄰域多邊形最優(yōu)原則。如圖6，ΔABC為形態(tài)質(zhì)量較低、待刪除的三角形單元，其最短邊BC周圍所有相鄰的三角形共同組成了多邊形AP1P2……P5，如多邊形內(nèi)角均小于180°且銳角數(shù)目不大于3，即是凸多邊形，此時(shí)約定ΔABC滿足鄰域多邊形最優(yōu)原則。鄰域最優(yōu)基礎(chǔ)上，刪除與待優(yōu)化單元相鄰的三角單元，計(jì)算該單元最短邊中點(diǎn)，將其與多邊形各頂點(diǎn)相連，構(gòu)建新的三角單元，完成單元的優(yōu)化。如果該鄰域多邊形非凸，還應(yīng)對(duì)其凸化(圖7)：搜索第一個(gè)大于180°的角，提取其兩相鄰邊記為L(zhǎng)i、Lj；連接Li、Lj的非公共節(jié)點(diǎn)，形成新邊Ln；用Ln取代Li和Lj，更新鄰域多邊形邊拓?fù)潢P(guān)系；循環(huán)以上過(guò)程直至鄰域多邊形為凸。

圖6 狹長(zhǎng)三角形單元的優(yōu)化過(guò)程示意

Fig.6Longnarrowtriangleelementoptimizationdiagram

圖7 鄰域多邊形優(yōu)化算法示意

Fig.7Adjacentpolygonoptimizationalgorithmdiagram

5 算法分析與實(shí)例

5.1 算法效率分析

設(shè)網(wǎng)格邊界包含初始前沿邊線段Nb個(gè)，算法執(zhí)行過(guò)程中，在每嘗試構(gòu)建一個(gè)新單元時(shí)，都包含線段的交叉檢驗(yàn)或遍歷整個(gè)前沿邊的搜索操作，該步驟算法時(shí)間復(fù)雜度為O(Nb)；在計(jì)算單元尺寸ρ時(shí)，需要判斷M點(diǎn)處于背景網(wǎng)格的哪一個(gè)網(wǎng)格單元中，設(shè)背景網(wǎng)格包含NEb個(gè)單元，該步驟算法時(shí)間復(fù)雜度為O(NEb)；設(shè)最終生成網(wǎng)格包含Ne個(gè)單元，由于每個(gè)單元均需要從背景網(wǎng)格中提取尺寸信息，因此有：O(Ne)=O(NEb)>O(Nb)，可得整個(gè)網(wǎng)格構(gòu)建算法時(shí)間復(fù)雜度為O(Ne2)。引入ADT數(shù)據(jù)結(jié)構(gòu)[14]存儲(chǔ)背景網(wǎng)格信息，背景網(wǎng)格尺寸提取的搜索算法時(shí)間復(fù)雜度變?yōu)镺(log2(NEb))，由于O(log2(NEb))

5.2 算例

基于OpenGL可視化引擎，使用VC語(yǔ)言開發(fā)有限元自適應(yīng)網(wǎng)格生成系統(tǒng)，對(duì)本文算法進(jìn)行檢驗(yàn)。網(wǎng)格整體質(zhì)量作為衡量生成網(wǎng)格優(yōu)劣的標(biāo)準(zhǔn)，其計(jì)算公式為：

(7)

式中：Q表示網(wǎng)格整體質(zhì)量；Ne表示該網(wǎng)格中包含單元個(gè)數(shù)；αi表示第i個(gè)三角單元的形態(tài)質(zhì)量，其計(jì)算方法見式(1)。

圖8、圖9為采用本文算法生成的自適應(yīng)三角網(wǎng)，其單元尺寸由左圖中的背景網(wǎng)格提供。左圖中明暗程度代表該位置處網(wǎng)格單元期望尺寸,右圖為對(duì)應(yīng)的自適應(yīng)三角網(wǎng)。結(jié)果表明：生成的網(wǎng)格與背景網(wǎng)格擬合度較高、網(wǎng)格單元過(guò)渡性平滑、單元整體質(zhì)量較高，背景網(wǎng)格能靈活控制網(wǎng)格的自適應(yīng)方式。

圖8 橢圓形區(qū)域的背景網(wǎng)格及自適應(yīng)離散結(jié)果(算例1)

Fig.8Backgroundsizegridandgeneratedadaptivemeshofanovalarea

圖9 不規(guī)則多邊形區(qū)域的背景網(wǎng)格及自適應(yīng)離散結(jié)果(算例2)

Fig.9Backgroundsizegridandgeneratedadaptivemeshofanarbitrarypolygonarea

5.3 算例效率分析

表2顯示上述算例在執(zhí)行網(wǎng)格生成、優(yōu)化與平滑步驟時(shí)所需的時(shí)間數(shù)據(jù)。由表2可見：算法執(zhí)行優(yōu)化操作時(shí)，需要進(jìn)行多次全局判斷，耗時(shí)超過(guò)15s，效率低下。優(yōu)化后網(wǎng)格單元整體質(zhì)量提升程度有限，這是由于算法所得到的網(wǎng)格本身具備較高的網(wǎng)格質(zhì)量；相對(duì)而言，網(wǎng)格的生成與平滑過(guò)程耗時(shí)不超過(guò)1s，算法效率較高,且所構(gòu)建網(wǎng)格優(yōu)化前的平均質(zhì)量接近0.9。

表2 自適應(yīng)網(wǎng)格單元生成耗時(shí)數(shù)據(jù)

Table2Adaptivemeshgenerationtimeconsumingdata

實(shí)例單元數(shù)總體耗時(shí)(s)生成耗時(shí)(s)優(yōu)化耗時(shí)(s)平滑耗時(shí)(s)優(yōu)化前網(wǎng)格質(zhì)量?jī)?yōu)化后網(wǎng)格質(zhì)量算例1467615．8320．46715．0230．340．8990．914算例2459138．3780．61237．4860．280．8920．913

5.4 網(wǎng)格質(zhì)量分析

圖10為基于同樣的背景網(wǎng)格，使用傳統(tǒng)的前沿推進(jìn)法[18,19]得到的網(wǎng)格結(jié)果，表3給出了本算法和傳統(tǒng)算法所構(gòu)建網(wǎng)格的質(zhì)量數(shù)據(jù)。結(jié)果表明：本文算法形態(tài)質(zhì)量在0.4以下的單元個(gè)數(shù)所占百分比小于5%(少數(shù)質(zhì)量小于0.4的單元，一般是由前沿邊推進(jìn)過(guò)程中發(fā)生交匯導(dǎo)致)；對(duì)于邊界形狀較規(guī)則、尺寸變異平緩區(qū)域，前沿邊推進(jìn)過(guò)程中交匯次數(shù)少，該類型單元數(shù)目相應(yīng)減少。較之于傳統(tǒng)的前沿推進(jìn)法，本文所提算法耗時(shí)較短，生成的自適應(yīng)網(wǎng)格質(zhì)量較優(yōu)，具有良好的過(guò)渡性與自適應(yīng)性。

圖10 使用傳統(tǒng)前沿推進(jìn)算法得到的自適應(yīng)網(wǎng)格

Fig.10 Adaptive triangular mesh generated by traditional AFT algorithm

表3 自適應(yīng)網(wǎng)格質(zhì)量數(shù)據(jù)

Table 3 Adaptive mesh quality data

實(shí)例方法T(s)NeQQtQbP(Qe<0．4)P(0．40．9)算例1算例2本文算法0．4646760．891．00．262．69%27．1%70．1%傳統(tǒng)算法0．8446360．831．00．022．02%34．8%63．0%本文算法0．6145910．891．00．104．8%24．6%70．4%傳統(tǒng)算法1．0645770．821．00．044．2%34．3%61．3%

注：T表示計(jì)算時(shí)間，Ne表示網(wǎng)格含單元數(shù)量,Q表示網(wǎng)格整體質(zhì)量，Qt表示最優(yōu)形態(tài)單元質(zhì)量，Qb表示最差形態(tài)單元質(zhì)量，P表示單元質(zhì)量滿足某數(shù)值的單元所占百分比，Qe表示單個(gè)單元形態(tài)質(zhì)量。

6 結(jié)語(yǔ)

本文充分研究了前沿邊推進(jìn)的形態(tài)變化特征，對(duì)前沿邊形態(tài)進(jìn)行分類并設(shè)計(jì)相應(yīng)的網(wǎng)格單元構(gòu)建策略；在前沿邊形態(tài)特征復(fù)雜區(qū)域，采用閾值分級(jí)讓步算法維護(hù)網(wǎng)格的單元質(zhì)量與收斂性；通過(guò)前沿邊形態(tài)變更驅(qū)動(dòng)的單元構(gòu)建試探法避免冗余操作，維護(hù)網(wǎng)格生成算法在尺寸變異復(fù)雜區(qū)域的通用性；對(duì)于前沿交匯處網(wǎng)格質(zhì)量下降問題，提出鄰域多邊形最優(yōu)原則的網(wǎng)格優(yōu)化算法對(duì)單元質(zhì)量進(jìn)行彌補(bǔ)。將以上方法融入傳統(tǒng)前沿推進(jìn)算法，提出一種可以兼顧算法魯棒性和網(wǎng)格單元質(zhì)量的網(wǎng)格生成算法。實(shí)驗(yàn)結(jié)果表明該算法效率較高，生成網(wǎng)格疏密過(guò)渡平滑且質(zhì)量較優(yōu)，能夠根據(jù)背景網(wǎng)格的尺寸做出自適應(yīng)調(diào)整、滿足實(shí)際的應(yīng)用要求。

本算法雖對(duì)傳統(tǒng)的前沿推進(jìn)法做出了一些改進(jìn)，但對(duì)于前沿邊交匯處單元質(zhì)量不高的問題未能給出完善的解決方案。如何進(jìn)一步提升網(wǎng)格優(yōu)化的效率，降低前沿邊“交匯”效應(yīng)，是后續(xù)研究有待解決的一個(gè)關(guān)鍵問題。

[1] LO S H.A New mesh generation scheme for arbitrary planar domains[J].International Journal for Numerical Methods in Engineering，1985，21：1403-1426.

[2] CAVENDISH J C.Automatic triangulation of arbitrary planar domains for the finite element method[J].International Journal for Numerical Methods in Engineering，1974,11:1041-1043.

[3] 葉正寅,楊永年.非結(jié)構(gòu)網(wǎng)格生成技術(shù)中一種直接提供背景信息的方法[J].西北工業(yè)大學(xué)學(xué)報(bào),1999,17(1):1-5.

[4] 武潔，馮晉利.三角形網(wǎng)格生成方法中一種提供背景信息的方法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)報(bào)，1999，11(4):300-303

[5] FRYKESTIG J.Advancing front mesh generation techniques with application to the finite element method[D].Chalmers University of Technology，Gothenburg Sweden，1994.

[6] 孫力勝，鄭建靖，陳建軍,等.二維自適應(yīng)前沿推進(jìn)網(wǎng)格生成[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(3):146-148.

[7] 黃曉東，杜群貴，葉邦彥,等.二維幾何特征自適應(yīng)有限元網(wǎng)格生成[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)報(bào)，2004,16(7):923-927.

[8] 梁義，陳建軍，陳立崗,等.幾何自適應(yīng)參數(shù)曲面網(wǎng)格生成[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)報(bào)，2010,22(2):327-334.

[9] 劉懷輝，楊興強(qiáng).平面區(qū)域有限元三角網(wǎng)格剖分算法研究[D].濟(jì)南：山東大學(xué)，2007.37-39.

[10] 修榮榮，徐明海.一種改進(jìn)的二維平面區(qū)域三角形化的前沿推進(jìn)法[J].石油大學(xué)學(xué)報(bào)(自然科學(xué)版)，2003,27(5):73-80.

[11] LEE C K， HOBBS R E.Automatic adaptive finite element mesh generation over arbitrary two dimensional domain using advancing front technique[J].Computer and Structures，1999，71:19-34.

[12] FREY W H.Selective refinement:A new strategy for automatic node placement in graded triangular meshes[J].International Journal for Numerical Methods in Engineering,1987,24:2183-2200.

[13] FAN N M,ZHANG Z F.An algorithm for large-scale terrain generation based on quad-tree[J].Advanced Research in Material Science and Mechanical Engineering,2014(446):946-990.

[14] BONET J,PERAIRE J.An alternating digital tree(ADT) algorithm for 3D geometric searching and inter-section problems[J].International Journal for Numerical Methods in Engineering,1991,31(1):1-17.

[15] SONG S H，WAN M.Robust and quality boundary constrained tetrahedral mesh generation[J].Communications in Computational Physics,2009,14(5):1304-1321.

[16] GEOGRE P L,HEEHT F E.Automatic mesh generation with specified boundary[J].Computer Methods in Applied Mechanics and Engineering,1991,92:269-288.

[17] DIMITRAKOPOULOS M,GRAF R.An efficient method for discretizing 3D fractured media for subsurface flow and transport simulations[J].International Journal for Numerical Methods in Fluids,2011,67:651-670.

[18] 劉春太，楊曉東，陳靜波,等.任意平面區(qū)域的變尺寸有限元網(wǎng)格劃分[J].計(jì)算力學(xué)學(xué)報(bào),2000,17(1):105-108.

[19] 宋超，關(guān)振群，顧元憲.二維自適應(yīng)網(wǎng)格生成的改進(jìn)AFT 與背景網(wǎng)格法[J].計(jì)算力學(xué)學(xué)報(bào),2005,22(6):694-698.

Front Advancing Adaptive Triangular Mesh Generation Algorithm

MA Jun-ting,CHEN Suo-zhong,LIU Huan，ZHANG Jie

(KeyLaboratoryofVirtualGeographicEnvironment，MinistryofEducation，NanjingNormalUniversity，Nanjing210023，China)

The front line morphology contains relatively complex geometrical characteristics as the front advancing inside the domain to be triangulated when using advancing front technique.Current AFT algorithms lead to a low quality generated mesh.In this paper,a mesh generation algorithm concerning both element quality and algorithm robustness is proposed.Firstly， all the possibly occurred front line geometric features are taken into consideration and summarized into four types.And then,in order to construct the triangular mesh element with best quality,a candidate point test algorithm is proposed and realized,and the algorithm′s robustness is maintained by using a compromise method that gradually increases the value threshold of searching angle between two adjacent front segments.The experiments demonstrate that the proposed mesh generator is capable of identifying and dealing with complex front line morphology,and discretizing the planar domain into a well-graded,high quality adaptive mesh with element size compatible with the user specification.

advancing front technique;adaptive triangular mesh;compromise algorithm;mesh quality

2015-03-31；

2015-05-14

江蘇省高校自然科學(xué)研究重大項(xiàng)目(10KJA170028)

馬鈞霆(1987-)，男，博士研究生，研究方向?yàn)榈叵滤當(dāng)?shù)值模擬與可視化方法。*通訊作者E-mail:junted_m@163.com

10.3969/j.issn.1672-0504.2015.05.004

P208

A

1672-0504(2015)05-0014-06