面向臟幾何的曲面網(wǎng)格自動生成算法

孟祥橋，劉智偉，劉陶然，陳建軍

(浙江大學 航空航天學院，杭州 310027)

0 引 言

由于建模誤差、格式轉換等一系列問題，模型往往存在法向錯誤、穿插、狹縫、貼合等一系列問題，我們將這類無法直接應用于數(shù)值計算的幾何模型稱為臟幾何[1]。因此，在傳統(tǒng)的網(wǎng)格生成流程中，網(wǎng)格生成前往往需要對幾何進行清理操作，用戶需要識別所有的幾何錯誤，并依次修復[2]。這一修復過程往往需要大量人工交互，并借助復雜的圖形界面，如CADfix[3]等專業(yè)的幾何處理軟件，且十分依賴于操作人員的經(jīng)驗。對于大量部件組成的復雜模型，人工修復的成本是難以忍受的。

Shephard 等提出了一種基于八叉樹的全自動網(wǎng)格生成方法[4]，基于八叉樹的網(wǎng)格生成方法可以一定程度上容忍幾何錯誤，但仍存在一些固有的缺陷。模型的幾何特征并非初始構造，該方法需要向基網(wǎng)格嵌入特征，使網(wǎng)格逼近真實幾何[5]，基網(wǎng)格的質量嚴重影響幾何特征嵌入的效果。在嵌入過程中，往往需要引入大量的單元來捕捉細小的幾何特征，導致單元數(shù)目的大幅上升。

劉等人基于混合曲面表征[2,6-7]實現(xiàn)了裝配體的“曲面嵌入”，可以解決多個部件之間可能存在的相交和重疊問題。其方法是在離散曲面上計算邊界相交圖，得到離散嵌入結果，之后根據(jù)連續(xù)-離散的映射關系完成連續(xù)曲面邊界表征上的曲面自動嵌入[3]。該算法具有較高的時間效率，也保證了計算結果的幾何精度，但其適用范圍有限，魯棒性不足，針對模型貫穿的問題，由于貫穿處缺少邊界表征，曲面嵌入失效。

Hu 等通過將三角形-三角形求交升維至四面體-三角形求交，在初始三角形表面約束下生成純四面體網(wǎng)格，并在有理數(shù)范圍內實現(xiàn)了精確求交[8]。這種方法在一定程度上可以解決臟幾何模型中出現(xiàn)的相交問題，但其局限性亦存在。一是相交計算十分耗時，二是此類方法僅能設定全局容差值，當縫隙間距大于其允許的容差值時，使用此方法不僅無法消除幾何誤差，反而可能急劇影響性能和網(wǎng)格質量，而容差值過大時，幾何特征不能被完全保留。劉[9]也采用四面體化的方法來完成臟幾何的網(wǎng)格生成，并創(chuàng)新性地引入了邊界恢復算法[10]，從而大幅減少相交計算量。兩者的四面體化方法中均要求輸入邊界法向正確，對于存在法向錯誤的幾何，仍然需要大量的手工交互調整輸入模型的法向。

本文針對臟幾何中可能出現(xiàn)的法向錯誤、穿插、狹縫、貼合問題，通過四面體化方法自動修復臟幾何，并生成高質量的曲面網(wǎng)格。其核心思想是一個有效的四面體網(wǎng)格的表面一定是一個有效的曲面網(wǎng)格。本文在輸入模型的離散表征的基礎上直接生成四面體網(wǎng)格，通過離散邊界切割四面體解決了模型中存在的穿插問題，基于四面體優(yōu)化解決狹縫和貼合問題，此時該四面體網(wǎng)格的表面便是有效的曲面網(wǎng)格，提取該表面并應用曲面網(wǎng)格重構提升表面網(wǎng)格質量，得到最終的曲面網(wǎng)格。

相較于八叉樹方法，本方法具有更高的幾何精度，可以生成貼體的曲面網(wǎng)格；相較于基于混合曲面表征的曲面嵌入方法，本方法具有更強的普適性和健壯性；相較于Hu 等的四面體化方法，本方法的主要優(yōu)點有：

1）應用基于視圖采樣的方法完成法向修復，允許輸入的臟幾何中存在法向錯誤；

2）實現(xiàn)了基于容差場的局部修復與特征保持，避免四面體優(yōu)化導致的特征丟失或修復不完全；

3）實現(xiàn)了基于多級Hausdorff 距離[11]的網(wǎng)格重構技術，可以在修復的曲面網(wǎng)格的基礎上進行高精度的網(wǎng)格重構，避免網(wǎng)格重構導致的表面自相交。

1 算法流程

圖1 和圖2 給出了本文所提出的基于四面體化方法的面向臟幾何曲面網(wǎng)格生成算法流程，該算法的輸入為臟幾何模型，輸出為保形的高質量曲面網(wǎng)格。該算法主要包含以下步驟：

圖1 算法流程簡圖Fig. 1 Diagram for the algorithm illustration

圖2 算法流程圖Fig. 2 Flow chat of the algorithm

1）構建混合曲面表征。建立模型的離散-連續(xù)表征數(shù)據(jù)結構[2]，采用B-rep 表示模型的連續(xù)表征，采用三角網(wǎng)格表示模型的離散表征，同時維護連續(xù)模型和離散模型之間的映射關系。得到離散表征后，我們采用基于視圖采樣的方法，完成法向調整。

2）初始四面體化。本文采用Bowyer-Watson 方法[6,12]完成四面體化，我們提取離散表征中的所有點，作為B-W 算法的輸入，構造一個Delaunay 三角化。單次B-W 增量插點的過程為：（1）在當前Delaunay 三角化中找到包含待插入點的基單元；（2）利用單元的相鄰關系在基單元附近快速搜索所有打破外接圓準則的單元；（3）刪除所有（2）中的單元，形成空腔，連接待插入點與空腔邊界頂點，形成新的Delaunay 三角化。

3）邊界恢復與相交計算。初始四面體化中并不保證包含所有的原始曲面邊界，不能包含的邊界單元可分為兩類。第一類是由于Delaunay 三角化只能保證點存在于三角化中，不能保證網(wǎng)格邊和網(wǎng)格面也都存在于三角化中，這類邊界可以通過邊界恢復[9-10,13-14]的策略來找回原始邊界，第二類是由于臟幾何模型本身存在相交或重疊的情形，得到的三角化必然無法包含此類邊界，如圖1（c）所示藍色區(qū)域，這類邊界需要通過相交計算對四面體進行裁剪以找回邊界。

4）四面體網(wǎng)格質量優(yōu)化。相交計算僅能解決部件相交的問題，但模型中仍可能存在狹縫等不必要的特征。我們采用四面體網(wǎng)格質量優(yōu)化的方法，在容差范圍內抹除此類特征。

5）曲面網(wǎng)格重構。提取上述四面體網(wǎng)格的表面得到修復后的表面網(wǎng)格，修復后的表面網(wǎng)格解決了原始模型的一系列錯誤，但網(wǎng)格質量與網(wǎng)格密度均難以達到數(shù)值計算的要求，因此需要對4）中得到的表面網(wǎng)格進行重構。

2 算法實現(xiàn)

2.1 法向調整

本文算法的核心思想是生成有效的四面體網(wǎng)格，提取其表面得到最終有效的曲面網(wǎng)格。如圖1 所示，我們在輸入模型的外部加入包圍盒，在整個包圍盒區(qū)域內生成四面體網(wǎng)格，我們計算每個四面體單元相對輸入表面的繞卷數(shù)[15]，篩選得到內部的四面體單元，從而方便地提取出有效的表面。繞卷數(shù)計算正確的前提是輸入表面的法向是正確的，此外，在曲面網(wǎng)格重構中，也需要保持每個面上單元的法向一致。因此在完成混合曲面表征的構造后，我們需要對離散表征的面法向進行修復。

若離散表征中所有的三角單元都是相連的，即兩個三角單元之間存在一條共享邊，我們可以通過BFS 算法[16]完成面法向調整，即鎖定某一個三角單元的法向，以該單元為起點，不斷搜索其鄰居，使與其相連的單元的法向調整為與該起點單元同向。但考慮最壞情況下，若幾乎所有的面片均不存在與其他面片的拓撲連接，此時我們無法通過BFS 算法快速地完成法向調整。為了盡可能地解決臟幾何中可能出現(xiàn)的法向問題，我們采用基于視圖采樣的法向調整策略。通過繪制該離散模型在各個方向上的視圖，可以計算該模型中任意一個面片法向的可能性。理想情況下，我們在任意一個觀測點v觀察該模型，對于觀察到的某一個三角形中的某一點p，視線方向 (v-p)與該三角形的法向n應 滿足 (v-p)·n≤0。

定義三角面片ti的 法向正確的概率為P(ti)。我們對該模型建立一個包圍球，從包圍球上均勻選取N個觀測點對該模型進行繪制，得到N張1 024×1 024的圖像。定義O+(ti) 為三角面片ti在所有視圖中法向與視線夾角大于90°的像素點數(shù)，O-(ti) 為三角面片ti在所有視圖中法向與視線夾角小于90°的像素點數(shù)。最終可計算得到三角面片ti法向正確的概率為：

若P(ti)＞0.5，將保持該面片的法向，否則將該三角面片的法向翻轉。在實際應用中，首先采用BFS 算法盡可能地將面片組合，然后采用上述視圖采樣法向調整策略完成法向的全局調整。對于單張視圖，我們采用掃描線Z 緩沖器算法[17]，完成視圖的快速繪制。圖3 為法向調整前后的對比，其中綠色表示該三角面片的法向指向體的內部。

圖3 法向調整效果Fig. 3 Meshes before and after the normal adjustment

2.2 曲面求交

為了恢復模型的所有原始邊界，我們使用原始邊界的三角面片所在的平面來切割四面體。非退化情況下四面體單元被原始表面單元所在平面切割如圖4 所示，被切割的四面體單元的側面將會被截斷為一個四邊形和一個三角形，該四面體單元將形成一個四面體單元和一個五面體單元。首先對側面的三個四邊形分別進行Delaunay 三角化，再對該五面體單元進行分割，在其重心處插入新點，與側面的新三角形頂點連接后形成分裂后的新四面體單元。貼合問題將產(chǎn)生零體積的四面體單元，本算法中的三角形求交計算全部采用基于GMP 的高精度有理數(shù)計算[18]，退化情況下舍棄零體積的新單元即可?；诰_的求交計算，我們可以保證輸入模型中的所有自相交問題可以得到修復。

圖4 四面體單元切割的非退化情形Fig. 4 Non-degenerate case of tetrahedral cutting

圖5 展示了利用原始邊界切割四面體解決相交問題，圖5（a）中紅色四面體與藍色的原始邊界出現(xiàn)相交，圖5（b）為該四面體的底面。利用原始邊界切割四面體，其結果如圖5（c）和圖5（d）所示。

圖5 曲面求交過程Fig. 5 Surface intersection process

2.3 四面體網(wǎng)格優(yōu)化

上述四面體-平面求交可以在有理數(shù)的范圍內修復臟幾何的自相交問題，但模型仍可能存在狹縫等不必要的細小特征。由于前述步驟已經(jīng)完成了輸入模型原始表面的恢復，那么在狹縫處必然存在狹窄甚至是退化的四面體單元，因此優(yōu)化此處的四面體單元質量，即可抹除此類特征。圖6 展示了通過四面體優(yōu)化解決狹縫的詳細過程。圖示兩圓柱之間存在狹縫需要被抹除，經(jīng)過初始四面體化后，如圖6（b）所示，狹縫處產(chǎn)生了圖示紅色的四面體單元，這類四面體單元的質量較差，經(jīng)過四面體質量提升后，這類單元被抹去，得到的表面如圖6（c）所示。

圖6 四面體網(wǎng)格優(yōu)化解決狹縫問題Fig. 6 Tetrahedral mesh optimization for slits

2.3.1 四面體質量提升

四面體單元質量的提升主要操作為邊分裂、邊折疊、面交換與點優(yōu)化四種局部操作[19]，其示意圖如圖7 所示。本文通過循環(huán)執(zhí)行這四種局部操作來逐步優(yōu)化四面體單元。

圖7 四面體單元質量提升Fig. 7 Quality improvement of tetrahedral elements

本文采用Rabinovich 等[8,20]提出的能量函數(shù)作為四面體單元的質量標準，該函數(shù)具有天然的各向同性，可以有效地甄別出各向異性的和負體積的四面體單元，公式如下：

其中，Jt是 將單元t轉化為正單元（三維時為正四面體）的雅可比矩陣，D為網(wǎng)格維度，衡量四面體單元質量時取3。當某一單元的能量函數(shù)值大于臨界值時，將被視為差單元，并通過上述質量提升操作提升單元質量。

四面體網(wǎng)格質量優(yōu)化的目的是解決狹縫或重疊處產(chǎn)生的狹窄的或退化的四面體單元，對于空間中的四面體，其質量評判標準不同。為了加速優(yōu)化效率，我們采用了多級能量閾值判別方案，即每個四面體單元優(yōu)化的目標能量值不同，這里我們采用四面體單元至邊界的距離來計算該單元的能量閾值。我們令原始表面附近的單元的目標能量值為Ets，該三角化中允許的最大能量值為kEts，則空間中某一四面體的目標優(yōu)化質量Et可以通過線性插值得到，即：

其中，ds為該四面體與輸入表面的最短距離?？拷砻娴乃拿骟w單元，其目標能量值較小，而遠離所有表面的四面體單元，其目標能量值較大，我們允許在距離表面遠處產(chǎn)生較差的四面體單元。

2.3.2 包絡檢測與容差場

上述四面體網(wǎng)格質量優(yōu)化方法中，邊折疊與點優(yōu)化涉及網(wǎng)格點的位移操作，若網(wǎng)格點的偏移量過大，可能導致網(wǎng)格與輸入模型之間產(chǎn)生較大的偏差，我們將禁止這樣的邊折疊與點優(yōu)化操作。為了確保本算法生成的表面網(wǎng)格與輸入模型之間的誤差在可控范圍內，每次邊折疊與點優(yōu)化的操作執(zhí)行后，需要進行包絡檢測以確保生成保形的表面網(wǎng)格，包絡檢測的方法如下。

圖8 包絡檢測的采樣點Fig. 8 Sampling points for the envelope detection

容差 ε的設置將會影響包絡檢測的時間效率與精確性，同時也會影響模型缺陷的修復效果。若要修復模型中的狹縫，那么此處的容差值應當大于狹縫的寬度，但其它區(qū)域應當盡可能地保證邊界不發(fā)生改變。因此，我們定義了基于離散表征的容差場，任意一點處的容差分為兩部分，全局容差值 ε0與局部容差值εp，該點處的容差值取兩者中較小的一個。某一部件的 ε0為該部件的包圍盒對角線長度的千分之一，局部容差值 εp需根據(jù)模型需求，在需要修復的狹縫區(qū)域設置較大的容差值，在必須嚴格保持的特征處設置較小的容差值。如圖9 所示，我們通過設置楔形體脊邊處的容差值為一個較小的容差值，實現(xiàn)特征保持的效果。

圖9 局部容差實現(xiàn)特征保持Fig. 9 Feature preserving based on local tolerance

曲面求交與四面體質量提升兩個環(huán)節(jié)中均可能產(chǎn)生新的邊界點，新的邊界點都是由邊分裂形成的，故新邊界點的容差值應取其邊分裂前的兩端點處容差值的最小值。

2.4 曲面網(wǎng)格重構

本文中采用經(jīng)典的網(wǎng)格重構策略完成曲面網(wǎng)格重構，其核心算法與四面體網(wǎng)格重構相同，對需要優(yōu)化的單元依次執(zhí)行邊分裂、邊折疊、邊交換與點優(yōu)化操作，直至所有的表面網(wǎng)格均滿足質量要求。

為了生成保形的表面網(wǎng)格，我們希望在重構過程中由于邊分裂產(chǎn)生的新點、點優(yōu)化后的點都能盡可能地貼近原始表面。網(wǎng)格重構中的誤差估計通過計算Hausdorff 距離[11-21]來衡量，我們要求所有的網(wǎng)格點距離輸入邊界的Hausdorff 距離均小于hmax。由于表面網(wǎng)格優(yōu)化中存在點優(yōu)化的操作，在狹窄的區(qū)域有可能出現(xiàn)網(wǎng)格自相交的情況。為了避免這種情況，我們采用多級誤差來避免由表面網(wǎng)格重構引起的表面自相交。在執(zhí)行完畢一次曲面網(wǎng)格重構后，檢測所有的表面網(wǎng)格是否存在自相交的情況，對于存在自相交的表面，令h′max=hmax/2，重新進行曲面網(wǎng)格重構，直至表面不存在自相交的區(qū)域。

3 數(shù)值驗證

本算法采用C++語言實現(xiàn)，借助GMP 庫完成基于有理數(shù)的精確計算。測試平臺為Intel Core i7-6700，3.4 GHz，內存24 GB。

3.1 網(wǎng)格生成效果

本文選取了靶球、格柵鰭、F-16 戰(zhàn)斗機、AIM-54 導彈、Ford 發(fā)動機和某壓氣機六個典型的臟幾何模型作為實驗對象，模型網(wǎng)格如圖10 所示。

圖10 典型臟幾何模型Fig. 10 Typical models for dirty geometries

為驗證本文算法的有效性，這里詳細展示三個復雜臟幾何的網(wǎng)格生成結果，分別為：靶球模型、格柵鰭模型和F-16 戰(zhàn)斗機模型。

圖11 展示了靶球模型的幾何及其生成結果，該模型包含115 個體部件，存在15 177 處相交，圖11（a）為曲面離散后的局部放大結果，可以明顯地看出該處存在部件之間的相交問題，經(jīng)過本文的四面體化方法修復的表面網(wǎng)格如圖11（b）所示，部件之間的相交問題已經(jīng)得到處理。

圖11 靶球模型及其網(wǎng)格生成結果Fig. 11 Target ball model and its mesh generation

圖12 展示了格柵鰭模型的幾何及其網(wǎng)格生成結果，該模型的各片格柵鰭之間存在大量的貫穿問題，如圖12（a）所示，對于此類模型，曲面嵌入的算法由于貫穿處缺少對應的邊界表征，故無法支持部件之間互相貫穿的情形。而本文算法由于不依賴原始的邊界表征，可以很好地解決這一問題，網(wǎng)格生成結果如圖12（b）所示。

圖12 格柵鰭模型及其網(wǎng)格生成結果Fig. 12 Grid fin model and its mesh generation

圖13 展示了F-16 戰(zhàn)斗機模型的幾何及其網(wǎng)格生成結果，該模型由8 個部件組裝而成，部件之間存在相交與狹縫等問題。如圖13（a）展示了該模型存在的部件之間的相交問題，粉色尾鰭與淡藍色機身之間存在部件相交問題，圖13（b）為該處網(wǎng)格的生成結果。圖13（c）展示了該模型部件之間存在的狹縫問題，深藍色為該模型機翼，淡藍色區(qū)域為該模型機身，機翼與機身之間存在狹縫，圖13（d）為該處網(wǎng)格生成結果，可以看出狹縫已經(jīng)被抹除。

圖13 F-16 模型及其網(wǎng)格生成結果Fig. 13 F-16 aircraft model and its mesh generation

F-16 戰(zhàn)斗機模型中存在一些特殊的幾何特征在網(wǎng)格生成中需要得到保留，如圖14 所示機翼后緣，我們希望在此處能夠保留直線特征，后緣處應用2.3.2 節(jié)所述的局部容差可以實現(xiàn)該處的特征保留，在機翼后緣處設置較小的容差值，實現(xiàn)了該處特征保持的效果，TetWild[8]在此處生成的網(wǎng)格如圖14（a）所示，無法保留此類特征。

圖14 F-16 戰(zhàn)斗機局部特征保持對比Fig. 14 Comparison of local feature preservation for the F-16 fighter

此外，由于本文算法的網(wǎng)格重構過程中引入了尺寸場[21]，可以根據(jù)曲率特征實現(xiàn)網(wǎng)格的局部加密，即在曲率較大的區(qū)域自動生成較密的網(wǎng)格，圖14（b）中的機翼前后緣區(qū)域的網(wǎng)格受曲率特征的控制，網(wǎng)格尺寸較小，這一特征也使得該網(wǎng)格更能滿足后續(xù)數(shù)值分析的需要。

AIM-54 導彈、Ford 發(fā)動機和某壓氣機的部分模型錯誤與修復結果如圖15 所示。圖15（a）中AIM-54 的機翼與機身之間，圖15（c）中Ford 發(fā)動機紅圈處存在貼合錯誤，其修復結果如圖15（b）和15（d）所示。圖15（e）中壓氣機存在狹縫，修復結果如圖15（f）所示。

圖15 AIM-54、Ford 發(fā)動機、壓氣機模型與網(wǎng)格Fig. 15 Models and meshes of AIM-54, a Ford engine and a compressor

3.2 對比與數(shù)據(jù)統(tǒng)計

常用的網(wǎng)格生成算法均不具備表面修復的能力，Hu 等完成的TetWild[8]旨在任意離散表面上生成四面體網(wǎng)格，具備一定的表面修復能力，3.1 節(jié)中的結果表明，本文算法具有更好的修復效果，并且由于本文加入了曲面網(wǎng)格重構的策略，可以在保形的基礎上盡可能地生成高質量的表面網(wǎng)格。

我們將前述6 個典型的臟幾何模型作為實驗對象，與TetWild[8]進行網(wǎng)格質量與時間效率對比。由于TetWild 只能接受離散輸入，且無法處理法向錯誤的情況，我們將混合曲面表征中已經(jīng)完成法向調整的離散表征結果作為TetWild 的輸入。

我們選用平均最小角度和平均最大邊長比作為網(wǎng)格質量對比項，平均最小角度為該網(wǎng)格所有單元中每個單元的最小角度的平均值，平均最大邊長比為該網(wǎng)格所有單元中每個單元的最大邊長比的平均值。前述6 個模型分別采用TetWild 與本文算法處理所得網(wǎng)格的質量統(tǒng)計與對比結果如表1 所示。對比表明，本文算法生成的網(wǎng)格的平均最小角度與平均最大邊長比均優(yōu)于TetWild。

表1 網(wǎng)格質量對比Table 1 Comparison of mesh quality

前述6 個模型分別采用TetWild 與本文算法處理所耗時間的數(shù)據(jù)統(tǒng)計與對比結果如表2 所示。對比表明，TetWild 所耗時間是本文算法的3 倍及以上，本文算法在時間效率上領先TetWild。

表2 時間效率對比Table 2 Comparison of time efficiency

4 結 論

本文針對臟幾何存在的法向錯誤、穿插、狹縫、貼合問題，應用基于四面體化的曲面網(wǎng)格修復方法，開發(fā)了適用于臟幾何的自動網(wǎng)格生成算法。本算法實現(xiàn)了以往四面體化方法無法完成的法向修復；應用邊界恢復算法，可以大幅減少參與求交的三角形數(shù)量，提高求交性能；應用分級的誤差檢測，可以大幅提高包絡檢測精度，從而保證生成保形的曲面網(wǎng)格；引入容差場，實現(xiàn)了特征保持與特征消除；應用多級誤差估計，避免曲面網(wǎng)格重構產(chǎn)生自相交，最終生成了高質量的表面網(wǎng)格。上述對比實驗也展示了本算法在修復效果、時間效率與網(wǎng)格質量上的優(yōu)勢。

本文算法需要手動設置容差，從而達到好的修復效果，未來將持續(xù)探索更加簡便與自動化的容差設置方式。此外，本文算法針對存在破洞的幾何尚無法完成修復，需要進一步研究補面的算法。