覃先云+張見明

摘要： 為提高傳統(tǒng)波前法（Advancing Front Method，AFM）的網(wǎng)格生成效率，利用多維搜索二叉樹數(shù)據(jù)結(jié)構(gòu)實現(xiàn)臨近前沿和節(jié)點的快速查找，使整個網(wǎng)格生成的時間復(fù)雜度接近線性.針對周期曲面網(wǎng)格的生成，提出2種點修正算子，避免傳統(tǒng)算法添加虛邊界導(dǎo)致局部網(wǎng)格單元質(zhì)量較差和虛邊界計算復(fù)雜的問題.網(wǎng)格生成實例表明：多維搜索二叉樹提高網(wǎng)格生成速度，引進(jìn)點修正算子的波前法改善周期曲面網(wǎng)格質(zhì)量.

關(guān)鍵詞： 曲面網(wǎng)格生成； 波前法； 多維搜索二叉樹； 點修正算子； 周期曲面

中圖分類號： O241.82文獻(xiàn)標(biāo)志碼： A

Abstract： To get better efficiency of mesh generation using Advancing Front Method（AFM）， the data structure of multidimensional binary search trees is used to implement fast query of the associative fronts and nodes， and the total meshing time complexity is nearly close to linearity. Two kinds of pointmodification operations are proposed to construct mesh on periodic surfaces， with which the problems generated by constructing additional virtual boundaries are avoided， such as poor local mesh quality and complicated calculation on virtual boundaries. The examples of mesh generation indicate that， the multidimensional binary search trees can improve mesh generation efficiency， and the AFM with pointmodification operations can improve the mesh quality of periodic surfaces.

Key words： surface mesh generation； advancing front method； multidimensional binary search tree； pointmodification operation； periodic surface

0引言

曲面網(wǎng)格生成是工程和科學(xué)計算及計算機(jī)圖形學(xué)等領(lǐng)域的基礎(chǔ)支撐技術(shù).一方面，曲面網(wǎng)格可直接用于板和殼等結(jié)構(gòu)的有限元分析以及作為邊界元分析的實體表面網(wǎng)格，其網(wǎng)格質(zhì)量直接影響數(shù)值計算精度；另一方面，曲面網(wǎng)格是有限元分析前處理三維實體網(wǎng)格生成的基礎(chǔ)，很大程度地決定三維網(wǎng)格質(zhì)量.另外，曲面網(wǎng)格在計算機(jī)圖形學(xué)和地理信息系統(tǒng)等領(lǐng)域也有重要應(yīng)用.[1]由此看來，研究曲面網(wǎng)格生成技術(shù)具有重要意義.

生成曲面網(wǎng)格的方法主要有Delaunay三角剖分算法[23]、波前法（Advancing Front Method， AFM）[410]和四叉樹算法[11]等3種.AFM生成的網(wǎng)格單元質(zhì)量最好，而且容易控制網(wǎng)格尺寸實現(xiàn)自適應(yīng)網(wǎng)格生成，從而成為曲面網(wǎng)格生成技術(shù)的研究熱點.[1，45]AFM的基本流程為：首先將待剖分曲面的邊界離散為首尾相連的若干有向線段，得到初始前沿；然后在前沿集合中選擇一個線段作為當(dāng)前前沿，根據(jù)當(dāng)前前沿插入一個新節(jié)點或連接已有節(jié)點，形成一個新單元；更新前沿，使前沿向待剖分區(qū)域內(nèi)推進(jìn).循環(huán)選擇當(dāng)前前沿、插入節(jié)點（選擇節(jié)點）、生成新單元和更新前沿操作直到前沿為空，網(wǎng)格生成結(jié)束.[1，67]

AFM的基本思想是依靠不斷更新的前沿使網(wǎng)格逐漸向曲面待剖分區(qū)域內(nèi)部生成.AFM不像Delaunay算法那樣具有成熟的理論基礎(chǔ)，但在程序?qū)崿F(xiàn)上相對靈活.當(dāng)然，實現(xiàn)高效的AFM算法需要更多的經(jīng)驗和技巧.為保證網(wǎng)格單元的質(zhì)量和單元之間的正確連接關(guān)系，在新單元生成時需要進(jìn)行大量的相交判斷、包含判斷和距離判斷[1，10]，這些判斷大約消耗AFM整個程序運(yùn)行時間的80%以上.通過精心設(shè)計前沿管理數(shù)據(jù)結(jié)構(gòu)，盡可能減少這些判斷操作所花費的時間，可以大大提高計算效率.由于新單元的生成只受局部區(qū)域的影響，因此只需對單元和位于局部區(qū)域的臨近前沿進(jìn)行各種判斷操作.該局部區(qū)域在曲面參數(shù)空間為一橢圓[1]，為便于實現(xiàn)快速查找，常用矩形代替橢圓[7，10].快速查找位于矩形內(nèi)的前沿、節(jié)點和與矩形相交的前沿是加快整個判斷操作的關(guān)鍵，也是實現(xiàn)高效AFM的一大難點.本文利用多維二叉樹（簡稱kD樹，k為維數(shù)）實現(xiàn)前沿和節(jié)點的快速查找，該數(shù)據(jù)結(jié)構(gòu)由著名的計算機(jī)大師BENTLEY[12]提出.

實現(xiàn)高效AFM的另一大難點是如何提高周期性曲面網(wǎng)格生成質(zhì)量、效率和穩(wěn)定性.為利用常規(guī)的二維AFM對參數(shù)域進(jìn)行剖分，通常對曲面人為地添加虛邊界，使虛邊界和原有曲面邊界封閉整個曲面的參數(shù)空間.虛邊界的引入將AFM擴(kuò)展到各類封閉的周期曲面網(wǎng)格生成中.然而，對于復(fù)雜裁剪的周期曲面，特別是周期起始附近的曲面特征復(fù)雜（如小孔和復(fù)雜裁剪邊界等），如何正確添加虛邊界又成為難點.一般做法是：多次調(diào)用兩線段求交算法，判斷周期起始線與曲面原有邊界是否相交，如果相交，就分割相應(yīng)的邊界，并改變原有邊界的拓?fù)溥B接關(guān)系.新的邊界拓?fù)溥B接關(guān)系的建立很復(fù)雜，而且容易出錯，降低程序的穩(wěn)定性.另外，如果在虛邊界周圍有孔和裁剪邊界等特征，會導(dǎo)致虛邊界附近的單元質(zhì)量較差（即產(chǎn)生“虛邊界問題”[5]），甚至不能用于有限元或邊界元分析.為克服“虛邊界問題”，本文在傳統(tǒng)的AFM中引進(jìn)點的修正算子：在進(jìn)行各種判斷操作時，首先調(diào)用點修正算子使相互判斷的幾何對象（點和線段等）都位于半個參數(shù)周期內(nèi)，然后利用傳統(tǒng)的相交、包含和距離判斷算法.[1]

1AFM的改進(jìn)

1.1快速查找臨近前沿和節(jié)點

實現(xiàn)快速查找常用的數(shù)據(jù)結(jié)構(gòu)是四叉樹和ADT.[10]實踐證明，運(yùn)用這2種數(shù)據(jù)結(jié)構(gòu)可以顯著提高AFM效率.利用四叉樹可以高效查找給定節(jié)點位于哪個樹葉子內(nèi)，其時間復(fù)雜度為O（log n），能夠高效搜索給定節(jié)點的臨近節(jié)點.但是，四叉樹不便于實現(xiàn)任意給定矩形區(qū)域內(nèi)節(jié)點的查詢.ADT是基于二叉樹的數(shù)據(jù)結(jié)構(gòu)，可以提高查找效率[復(fù)雜度為O（log n）].可是，ADT規(guī)定節(jié)點插入準(zhǔn)則，限制網(wǎng)格生成中任意節(jié)點的插入.本文采用基于二叉樹的另一種數(shù)據(jù)結(jié)構(gòu)kD樹實現(xiàn)臨近前沿和節(jié)點的快速查找.在kD樹中，節(jié)點的插入和刪除以及臨近節(jié)點搜索和矩形區(qū)域查詢操作的時間復(fù)雜度都為O（log n）[12]，而且對節(jié)點的插入沒有條件限制，適合任意網(wǎng)格節(jié)點插入樹中.由于網(wǎng)格生成在曲面的二維參數(shù)空間（u， v）中進(jìn)行，因此只需要二維kD樹（取k為2）.

在kD樹中，規(guī)定方向辨別指示坐標(biāo)u和v，在樹的偶數(shù)層比較節(jié)點u值，而在奇數(shù)層比較節(jié)點v值.標(biāo)志層數(shù)的值為方向辨別數(shù).如果當(dāng)前節(jié)點辨別數(shù)為偶數(shù)，那么所有u值小于或等于該節(jié)點u值的節(jié)點都位于該節(jié)點的左子樹中，而所有u值大于該節(jié)點u值的節(jié)點都位于該節(jié)點的右子樹中；如果當(dāng)前節(jié)點辨別數(shù)為奇數(shù)，那么所有v值小于或等于該節(jié)點v值的節(jié)點都位于該節(jié)點的左子樹中，而所有v值大于該節(jié)點v值的節(jié)點都位于該節(jié)點的右子樹中.一棵完整的kD樹構(gòu)造包括節(jié)點插入、刪除和優(yōu)化，這些操作的具體實現(xiàn)見文獻(xiàn)[12]和[13].圖1顯示節(jié)點A，B，C和D依次插入樹的生成過程，對應(yīng)節(jié)點的坐標(biāo)分別為（0.3，0.4），（0.2，0.7），（0.6，0.6）和（0.5，0.8）.由隨機(jī)生成的500個節(jié)點構(gòu)造的一棵優(yōu)化kD樹見圖2.

2改進(jìn)的AFM流程

為方便控制網(wǎng)格生成的方式，把前沿分為3類：活動前沿、非活動前沿和拒絕前沿，分別存放在前沿管理數(shù)據(jù)結(jié)構(gòu)對應(yīng)的鏈表中.在網(wǎng)格生成過程中，只能從活動前沿中選擇一個前沿作為當(dāng)前前沿（基邊）.當(dāng)要求逐層生成單元時，把新生成的前沿存放在非活動前沿鏈表中，若活動前沿為空，則把非活動前沿鏈表中的值導(dǎo)入活動前沿鏈表中.拒絕前沿鏈表存放不能生成合適單元的基邊.此外，為保證整個AFM的成功實施，對新單元的校核分為幾何校核和拓?fù)湫：说?類.幾何校核是檢查單元的形狀質(zhì)量是否滿足給定值，而拓?fù)湫：耸菣z查單元間連接關(guān)系是否正確.綜合前文分析，本文實現(xiàn)AFM的具體步驟如下.

（1）離散曲面邊界，具體離散細(xì)節(jié)見文獻(xiàn)[16].

（2）生成初始活動前沿.

（3）在活動前沿鏈表中依次選擇基邊，并基于該邊生成三角形單元，逐漸剖分整個網(wǎng)格區(qū)域.

①準(zhǔn)備新單元生成.首先在活動前沿中選擇構(gòu)成單元的基邊，然后確定單元的尺寸，最后在參數(shù)空間確定搜索臨近節(jié)點和前沿的矩形區(qū)域.[1， 7， 10]

②利用前文描述的kD樹快速搜索位于矩形區(qū)域的節(jié)點和前沿.

③生成新單元：

（a）由單元尺寸確定理想節(jié)點的位置，使單元盡量在三維空間為等邊三角形.需要注意的是，在確定理想節(jié)點時不僅要考慮單元尺寸，還要考慮附近前沿的分布特征[10].當(dāng)前沿的特征阻止理想節(jié)點的生成時，轉(zhuǎn)到（d）.

（b）判斷搜索區(qū)域內(nèi)是否存在節(jié)點可以生成有效的單元.搜索的節(jié)點為組成新單元的候選節(jié)點，并且依次校核這些節(jié)點的有效性.有效性校核[1]包括：保證由候選節(jié)點和組成基邊的任一節(jié)點形成的新邊沒有跟前沿相交；保證由候選節(jié)點和基邊組成形狀合適的單元；保證候選節(jié)點和新邊距離前沿為有效遠(yuǎn)的距離.其中，第一種稱為拓?fù)湫：?，?種統(tǒng)稱為幾何校核.如果有若干個單元滿足校核，將選擇質(zhì)量最好的單元為新單元，然后轉(zhuǎn)到④；否則轉(zhuǎn)到（c）.

（c）根據(jù)（b）中的校核方法判斷理想節(jié)點與基邊是否組成合適的新單元.如果通過校核，那么生成新的單元后轉(zhuǎn)到④，否則轉(zhuǎn)到（d）.

（d）由理想點和基邊確定若干個候選節(jié)點，同樣用b的方法校核這些節(jié)點組成單元的有效性.如果沒有單元通過校核，那么把該基邊存放在拒絕前沿鏈表中；如果有若干個單元都滿足校核，那么選擇質(zhì)量最好的單元為新單元，然后轉(zhuǎn)到④.

④更新前沿管理數(shù)據(jù).首先刪掉不是前沿中的節(jié)點和邊，然后添加新的節(jié)點和邊到前沿管理數(shù)據(jù)結(jié)構(gòu)中.當(dāng)按層生成單元時，把新節(jié)點和邊存放在非活動前沿鏈表中，否則存放在活動前沿鏈表中；當(dāng)活動前沿鏈表為空時，把非活動前沿鏈表中的值添加到活動前沿鏈表中.如果活動前沿鏈表為非空轉(zhuǎn)到①，否則轉(zhuǎn)到⑤.

⑤如果拒絕前沿鏈表為空，那么網(wǎng)格生成結(jié)束；否則，將拒絕前沿中的值添加到活動前沿鏈表中，再轉(zhuǎn)到①.先重復(fù)1次上面過程，然后考慮拒絕前沿鏈表是否為空，如不為空再到①，直到拒絕前沿鏈表為空為止.只對新單元進(jìn)行拓?fù)湫：?，保證新邊沒有跟前沿相交就生成新單元.

3算例和分析

采用面對象的C++語言實現(xiàn)本文算法，編制C++類將kD樹和前沿管理的實現(xiàn)進(jìn)行封裝.完成算例所用的PC機(jī)配置為雙核CPU，主頻為2.33 Hz，內(nèi)存為3.25 GB.

3.1算例1：kD樹加速AFM

以邊長為2的正方形簡單區(qū)域的網(wǎng)格生成為例，比較采用和不采用kD樹這2種方案網(wǎng)格生成的速度.2種方案對不同數(shù)量的單元所消耗CPU時間見圖5（a）.圖5 （b）所示的網(wǎng)格單元為5 748個.從圖5（a）可以明顯看出，在不采用kD樹時CPU時間消耗隨單元數(shù)量增加呈平方趨勢增長，但在采用kD樹時CPU消耗時間隨單元數(shù)量增加呈近似線性增長.采用kD樹在單元數(shù)量相對較少的情況下優(yōu)勢不明顯，但對大規(guī)模網(wǎng)格生成（10萬個以上）可以明顯提高效率.例如，在生成近60萬個單元時，采用kD樹只需要20 s左右，而不采用kD樹需要多達(dá)130 s.

4結(jié)論

為實現(xiàn)高效、穩(wěn)定的AFM生成曲面網(wǎng)格，對AFM具體實現(xiàn)進(jìn)行改進(jìn).一方面，在AFM前沿數(shù)據(jù)管理中引進(jìn)kD樹以加快臨近前沿和節(jié)點的查找，提高AFM網(wǎng)格生成速度；另一方面，在周期曲面網(wǎng)格生成中提出點修正算子并融入到AFM中，以避免添加虛邊界導(dǎo)致網(wǎng)格質(zhì)量較差和虛邊界計算復(fù)雜的問題，從而改善網(wǎng)格質(zhì)量和提高程序穩(wěn)定性.

為方便控制網(wǎng)格生成方式和提高程序的穩(wěn)定性，把前沿分為活動前沿、非活動前沿和拒絕前沿等3類，在算法中根據(jù)需求實現(xiàn)三者間的數(shù)據(jù)自動交互.對新單元的校核分為拓?fù)湫：撕蛶缀涡：?，以保證整個區(qū)域網(wǎng)格的成功生成.基于這些改進(jìn)，列出AFM實現(xiàn)的詳細(xì)步驟.網(wǎng)格生成實例說明：kD樹能極大地提高AFM網(wǎng)格生成效率，特別是對大規(guī)模網(wǎng)格生成效率更為明顯；加入點修正算子的AFM可極大地改善周期曲面局部網(wǎng)格單元質(zhì)量.

參考文獻(xiàn)：

[1]關(guān)振群， 單菊林， 顧元憲. 基于黎曼度量的復(fù)雜參數(shù)曲面有限元網(wǎng)格生成方法[J]. 計算機(jī)學(xué)報， 2006， 29（10）： 18231833.

[2]熊英， 胡于進(jìn)， 趙建軍. 基于映射法和Delaunay方法的曲面三角網(wǎng)格劃分算法[J]. 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報， 2002， 14（1）： 5660.

[3]孟憲海， 蔡強(qiáng)， 李吉剛， 等. 面向四面體網(wǎng)格生成的曲面Delaunay三角化算法[J]. 工程圖學(xué)學(xué)報， 2006， 27（1）： 7681.

[4]黃曉東， 丁問司， 杜群貴. 基于波前法的參數(shù)曲面有限元網(wǎng)格生成算法[J]. 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報， 2010， 22（1）： 5259.

[5]杜群貴， 劉勝， 黃曉東. 閉曲面有限元網(wǎng)格生成的邊界預(yù)調(diào)整方法[J]. 華南理工大學(xué)學(xué)報： 自然科學(xué)版， 2007， 35（2）：2732.

[6]LOHNER R. Automatic unstructured grid generators[J]. Finite Elements in Analysis and Design， 1997， 25（12）： 111134.

[7]LEE C K. Automatic adaptive metric advancing front triangulation over curved surfaces[J]. Eng Computations， 2000， 17（1）： 4874.

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

[9]WU B， WANG S. Automatic triangulation over threedimensional parametric surface based on advancing front method[J]. Finite Elements Anal & Des， 2005， 41（910）： 892910.

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

[11]LIANG X， EBEIDA M S， ZHANG Y. Guaranteedquality allquadrilateral mesh generation with feature preservation[J]. Comput Methods Appl Mech & Eng， 2010（199）： 20722082.

[12]BENTLEY J. Multidimensional binary search trees used for associative searching[J]. Commun ACM， 1975， 18（9）： 509517.

[13]BERG M D， OTFRIED C， van KREVELD M. 計算幾何：算法與應(yīng)用[M]. 3版. 鄧俊輝，譯. 北京： 清華大學(xué)出版社， 2009.

[14]GUAN Zhenqun， SHAN Hulin， ZHENG Yao， et al. An extended advancing front technique for closed surfaces mesh generation[J]. Int J Numer Methods Eng， 2008， 74（4）： 642667.

[15]郭新強(qiáng). 邊界面法四邊形網(wǎng)格生成研究與應(yīng)用[D]. 長沙： 湖南大學(xué)， 2011.

[16]CUILLIRE J C. A direct method for the automatic discretization of 3D parametric curves[J]. Comput Aided Des， 1997， 29（9）： 639647.

（編輯武曉英）

為實現(xiàn)高效、穩(wěn)定的AFM生成曲面網(wǎng)格，對AFM具體實現(xiàn)進(jìn)行改進(jìn).一方面，在AFM前沿數(shù)據(jù)管理中引進(jìn)kD樹以加快臨近前沿和節(jié)點的查找，提高AFM網(wǎng)格生成速度；另一方面，在周期曲面網(wǎng)格生成中提出點修正算子并融入到AFM中，以避免添加虛邊界導(dǎo)致網(wǎng)格質(zhì)量較差和虛邊界計算復(fù)雜的問題，從而改善網(wǎng)格質(zhì)量和提高程序穩(wěn)定性.

為方便控制網(wǎng)格生成方式和提高程序的穩(wěn)定性，把前沿分為活動前沿、非活動前沿和拒絕前沿等3類，在算法中根據(jù)需求實現(xiàn)三者間的數(shù)據(jù)自動交互.對新單元的校核分為拓?fù)湫：撕蛶缀涡：?，以保證整個區(qū)域網(wǎng)格的成功生成.基于這些改進(jìn)，列出AFM實現(xiàn)的詳細(xì)步驟.網(wǎng)格生成實例說明：kD樹能極大地提高AFM網(wǎng)格生成效率，特別是對大規(guī)模網(wǎng)格生成效率更為明顯；加入點修正算子的AFM可極大地改善周期曲面局部網(wǎng)格單元質(zhì)量.

參考文獻(xiàn)：

[1]關(guān)振群， 單菊林， 顧元憲. 基于黎曼度量的復(fù)雜參數(shù)曲面有限元網(wǎng)格生成方法[J]. 計算機(jī)學(xué)報， 2006， 29（10）： 18231833.

[2]熊英， 胡于進(jìn)， 趙建軍. 基于映射法和Delaunay方法的曲面三角網(wǎng)格劃分算法[J]. 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報， 2002， 14（1）： 5660.

[3]孟憲海， 蔡強(qiáng)， 李吉剛， 等. 面向四面體網(wǎng)格生成的曲面Delaunay三角化算法[J]. 工程圖學(xué)學(xué)報， 2006， 27（1）： 7681.

[4]黃曉東， 丁問司， 杜群貴. 基于波前法的參數(shù)曲面有限元網(wǎng)格生成算法[J]. 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報， 2010， 22（1）： 5259.

[5]杜群貴， 劉勝， 黃曉東. 閉曲面有限元網(wǎng)格生成的邊界預(yù)調(diào)整方法[J]. 華南理工大學(xué)學(xué)報： 自然科學(xué)版， 2007， 35（2）：2732.

[6]LOHNER R. Automatic unstructured grid generators[J]. Finite Elements in Analysis and Design， 1997， 25（12）： 111134.

[7]LEE C K. Automatic adaptive metric advancing front triangulation over curved surfaces[J]. Eng Computations， 2000， 17（1）： 4874.

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

[9]WU B， WANG S. Automatic triangulation over threedimensional parametric surface based on advancing front method[J]. Finite Elements Anal & Des， 2005， 41（910）： 892910.

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

[11]LIANG X， EBEIDA M S， ZHANG Y. Guaranteedquality allquadrilateral mesh generation with feature preservation[J]. Comput Methods Appl Mech & Eng， 2010（199）： 20722082.

[12]BENTLEY J. Multidimensional binary search trees used for associative searching[J]. Commun ACM， 1975， 18（9）： 509517.

[13]BERG M D， OTFRIED C， van KREVELD M. 計算幾何：算法與應(yīng)用[M]. 3版. 鄧俊輝，譯. 北京： 清華大學(xué)出版社， 2009.

[14]GUAN Zhenqun， SHAN Hulin， ZHENG Yao， et al. An extended advancing front technique for closed surfaces mesh generation[J]. Int J Numer Methods Eng， 2008， 74（4）： 642667.

[15]郭新強(qiáng). 邊界面法四邊形網(wǎng)格生成研究與應(yīng)用[D]. 長沙： 湖南大學(xué)， 2011.

[16]CUILLIRE J C. A direct method for the automatic discretization of 3D parametric curves[J]. Comput Aided Des， 1997， 29（9）： 639647.

（編輯武曉英）

為實現(xiàn)高效、穩(wěn)定的AFM生成曲面網(wǎng)格，對AFM具體實現(xiàn)進(jìn)行改進(jìn).一方面，在AFM前沿數(shù)據(jù)管理中引進(jìn)kD樹以加快臨近前沿和節(jié)點的查找，提高AFM網(wǎng)格生成速度；另一方面，在周期曲面網(wǎng)格生成中提出點修正算子并融入到AFM中，以避免添加虛邊界導(dǎo)致網(wǎng)格質(zhì)量較差和虛邊界計算復(fù)雜的問題，從而改善網(wǎng)格質(zhì)量和提高程序穩(wěn)定性.

為方便控制網(wǎng)格生成方式和提高程序的穩(wěn)定性，把前沿分為活動前沿、非活動前沿和拒絕前沿等3類，在算法中根據(jù)需求實現(xiàn)三者間的數(shù)據(jù)自動交互.對新單元的校核分為拓?fù)湫：撕蛶缀涡：?，以保證整個區(qū)域網(wǎng)格的成功生成.基于這些改進(jìn)，列出AFM實現(xiàn)的詳細(xì)步驟.網(wǎng)格生成實例說明：kD樹能極大地提高AFM網(wǎng)格生成效率，特別是對大規(guī)模網(wǎng)格生成效率更為明顯；加入點修正算子的AFM可極大地改善周期曲面局部網(wǎng)格單元質(zhì)量.

參考文獻(xiàn)：

[1]關(guān)振群， 單菊林， 顧元憲. 基于黎曼度量的復(fù)雜參數(shù)曲面有限元網(wǎng)格生成方法[J]. 計算機(jī)學(xué)報， 2006， 29（10）： 18231833.

[2]熊英， 胡于進(jìn)， 趙建軍. 基于映射法和Delaunay方法的曲面三角網(wǎng)格劃分算法[J]. 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報， 2002， 14（1）： 5660.

[3]孟憲海， 蔡強(qiáng)， 李吉剛， 等. 面向四面體網(wǎng)格生成的曲面Delaunay三角化算法[J]. 工程圖學(xué)學(xué)報， 2006， 27（1）： 7681.

[4]黃曉東， 丁問司， 杜群貴. 基于波前法的參數(shù)曲面有限元網(wǎng)格生成算法[J]. 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報， 2010， 22（1）： 5259.

[5]杜群貴， 劉勝， 黃曉東. 閉曲面有限元網(wǎng)格生成的邊界預(yù)調(diào)整方法[J]. 華南理工大學(xué)學(xué)報： 自然科學(xué)版， 2007， 35（2）：2732.

[6]LOHNER R. Automatic unstructured grid generators[J]. Finite Elements in Analysis and Design， 1997， 25（12）： 111134.

[7]LEE C K. Automatic adaptive metric advancing front triangulation over curved surfaces[J]. Eng Computations， 2000， 17（1）： 4874.

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

[9]WU B， WANG S. Automatic triangulation over threedimensional parametric surface based on advancing front method[J]. Finite Elements Anal & Des， 2005， 41（910）： 892910.

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

[11]LIANG X， EBEIDA M S， ZHANG Y. Guaranteedquality allquadrilateral mesh generation with feature preservation[J]. Comput Methods Appl Mech & Eng， 2010（199）： 20722082.

[12]BENTLEY J. Multidimensional binary search trees used for associative searching[J]. Commun ACM， 1975， 18（9）： 509517.

[13]BERG M D， OTFRIED C， van KREVELD M. 計算幾何：算法與應(yīng)用[M]. 3版. 鄧俊輝，譯. 北京： 清華大學(xué)出版社， 2009.

[14]GUAN Zhenqun， SHAN Hulin， ZHENG Yao， et al. An extended advancing front technique for closed surfaces mesh generation[J]. Int J Numer Methods Eng， 2008， 74（4）： 642667.

[15]郭新強(qiáng). 邊界面法四邊形網(wǎng)格生成研究與應(yīng)用[D]. 長沙： 湖南大學(xué)， 2011.

[16]CUILLIRE J C. A direct method for the automatic discretization of 3D parametric curves[J]. Comput Aided Des， 1997， 29（9）： 639647.

（編輯武曉英）