基于改進(jìn)波前法的曲面網(wǎng)格生成算法

覃先云+張見(jiàn)明

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

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

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

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

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

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

1AFM的改進(jìn)

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

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

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

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

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

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

（2）生成初始活動(dòng)前沿.

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

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

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

③生成新單元：

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

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

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

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

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

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

3算例和分析

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

3.1算例1：kD樹(shù)加速AFM

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

4結(jié)論

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

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

參考文獻(xiàn)：

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

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

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

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

[5]杜群貴， 劉勝， 黃曉東. 閉曲面有限元網(wǎng)格生成的邊界預(yù)調(diào)整方法[J]. 華南理工大學(xué)學(xué)報(bào)： 自然科學(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ì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)， 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. 計(jì)算幾何：算法與應(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]. 長(zhǎng)沙： 湖南大學(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.

（編輯武曉英）

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

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

參考文獻(xiàn)：

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

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

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

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

[5]杜群貴， 劉勝， 黃曉東. 閉曲面有限元網(wǎng)格生成的邊界預(yù)調(diào)整方法[J]. 華南理工大學(xué)學(xué)報(bào)： 自然科學(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ì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)， 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. 計(jì)算幾何：算法與應(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]. 長(zhǎng)沙： 湖南大學(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.

（編輯武曉英）

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

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

參考文獻(xiàn)：

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

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

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

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

[5]杜群貴， 劉勝， 黃曉東. 閉曲面有限元網(wǎng)格生成的邊界預(yù)調(diào)整方法[J]. 華南理工大學(xué)學(xué)報(bào)： 自然科學(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ì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)， 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. 計(jì)算幾何：算法與應(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]. 長(zhǎng)沙： 湖南大學(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.

（編輯武曉英）