面向錯(cuò)位裝配體的自動(dòng)曲面嵌入算法

劉智偉，楊 洋，陳建軍，*，鄭 澎，夏一帆

(1. 浙江大學(xué) 航空航天學(xué)院，杭州 310027；2. 中國(guó)工程物理研究院 高性能數(shù)值模擬軟件中心，北京 100088)

0 引 言

數(shù)值模擬前，用戶通常先定義CAD 模型，然后生成計(jì)算網(wǎng)格，最后設(shè)置邊界條件、材料和求解參數(shù)，這一過程被統(tǒng)稱為前處理[1]。實(shí)際應(yīng)用中，前處理過程用戶交互頻繁，易錯(cuò)且耗時(shí)長(zhǎng)，是數(shù)值模擬的主要瓶頸[2]，研究前處理自動(dòng)化算法是解決這一瓶頸的關(guān)鍵，亟待解決的難題包括網(wǎng)格自動(dòng)生成、模型自動(dòng)修復(fù)和清理等[3-5]。

本文研究由多個(gè)部件“組裝”而成的裝配體模型的自動(dòng)修復(fù)算法。隨著軟硬件性能的不斷提高，以裝配體模型為輸入的多部件耦合數(shù)值模擬已成為發(fā)展趨勢(shì)。相比傳統(tǒng)的單部件模擬，這類模擬可以系統(tǒng)性和綜合性地考慮不同部件之間的幾何物理耦合關(guān)系，實(shí)現(xiàn)更高精度的數(shù)值模擬結(jié)果。當(dāng)裝配體模型具有成百上千、乃至更多數(shù)目部件時(shí)，為降低建模難度，普遍采用分部件建模的方式，導(dǎo)致部件和部件之間的共享區(qū)域在不同部件中存在多份幾何表征。調(diào)用網(wǎng)格生成算法后，共享區(qū)域的網(wǎng)格也相應(yīng)存在多份幾何和拓?fù)渖隙疾患嫒莸谋碚鳎瑹o法在共享區(qū)域生成保形的網(wǎng)格，也即不能作為常規(guī)數(shù)值模擬的輸入。

為此，本文提出利用“曲面嵌入”技術(shù)消除裝配體不同部件交疊部分存在的多重定義。以圖1 所示兩部件裝配體為例，若直接在該模型的原始邊界表征（如圖1（a））上生成網(wǎng)格，曲面1 和曲面2 的網(wǎng)格不兼容，不符合數(shù)值模擬的需要；執(zhí)行曲面嵌入操作后（如圖1（b）），曲面2 一分為二，部件2 （Volume2）和部件1 （Volume1）重疊部分直接引用曲面1，其余部分定義為新曲面2（含圓形孔洞的長(zhǎng)方形）。顯然，曲面嵌入消除了原曲面1 和曲面2 重疊區(qū)域的多重定義，在執(zhí)行嵌入操作后獲得的模型上可生成符合常規(guī)數(shù)值模擬輸入要求的計(jì)算網(wǎng)格。

圖1 曲面嵌入操作示意Fig. 1 Illustration for surface imprinting operation

已有曲面嵌入算法分兩類：一類基于連續(xù)曲面，另一類基于離散曲面。連續(xù)曲面類算法其結(jié)果幾何精度高，但幾何計(jì)算復(fù)雜，數(shù)值穩(wěn)定性差[6-8]。離散曲面類算法幾何計(jì)算為線性計(jì)算，運(yùn)算速度快，但其結(jié)果幾何精度較低[9-14]。此外，離散曲面表征只涉及面片相鄰等低層拓?fù)洌瑧?yīng)用于需高層拓?fù)渲С值牟僮鲿r(shí)，需構(gòu)造連續(xù)曲面模型中常用的邊界表征（B-rep）[15]。其中，第一類算法的代表有CADfix[16]，其通過人工交互方式在連續(xù)B-rep 直接進(jìn)行相關(guān)的嵌入操作；第二類算法比較典型的如libigl[17]，其提供在離散三角形網(wǎng)格上處理三角形相交的算法，此外，TetWild[18]提供一種通過四面體優(yōu)化的方法來完成模型嵌入及修復(fù)的方法，其本質(zhì)依然是一種基于離散面片的方法。

在前期研究中，陳建軍等[3-4]提出一類將曲面連續(xù)表征和離散表征有機(jī)融為一體的曲面表征新方法，定義其為曲面的混合表征。本文針對(duì)錯(cuò)位裝配體中幾何重復(fù)表征問題，提出基于連續(xù)-離散混合曲面造型的裝配體模型自動(dòng)曲面嵌入算法。與前期研究工作[3-4]不同的是，該算法不僅消除曲面間曲線交纏等錯(cuò)誤，更進(jìn)一步消除模型實(shí)體間的曲面重疊、相交、錯(cuò)位等錯(cuò)誤。

1 算法流程

圖2 給出了本文所提面向錯(cuò)位裝配體自動(dòng)曲面嵌入算法的流程，該算法輸入錯(cuò)位的裝配體幾何模型，輸出曲面嵌入后可用于生成計(jì)算網(wǎng)格的B-rep 幾何。

圖2 算法流程圖Fig. 2 The workflow of the algorithm

本文所提算法主要包含如下步驟：

1）構(gòu)建混合曲面表征。建立裝配體模型的離散-連續(xù)表征數(shù)據(jù)結(jié)構(gòu)，利用B-rep 表征連續(xù)曲面模型，采用輻射邊表征離散曲面模型，同時(shí)維護(hù)連續(xù)模型和離散模型兩者之間的映射關(guān)系。

2）離散曲面嵌入。通過檢測(cè)并計(jì)算離散模型上的共享邊界區(qū)域相交，將邊界線段嵌入相關(guān)的離散曲面中，進(jìn)而在離散層面上計(jì)算出離散邊界相交環(huán)圖；而后通過拓?fù)洳僮饕瞥渌麉^(qū)域的相交，完成在離散曲面嵌入。同時(shí)，在嵌入的過程中，同步更新離散-連續(xù)曲面表征的映射關(guān)系。

3）連續(xù)曲面嵌入。根據(jù)邊界相交圖、離散模型嵌入結(jié)果及維護(hù)的連續(xù)-離散映射關(guān)系，在自主的幾何引擎中設(shè)計(jì)相應(yīng)的嵌入、合并操作，自底向上依次完成曲線嵌入、曲面嵌入，生成共享區(qū)域表征一致的B-rep。

執(zhí)行曲面嵌入算法后輸出的裝配體模型B-rep 其不同部件邊界曲面交疊部分不再存在多重定義問題，以其為輸入，順序執(zhí)行單元尺寸計(jì)算[19-20]、曲面網(wǎng)格生成[21]和實(shí)體網(wǎng)格生成[22-23]等算法，即可最終獲得符合通用數(shù)值模擬分析的計(jì)算網(wǎng)格模型。

2 算法實(shí)現(xiàn)

本文算法在連續(xù)-離散混合曲面表征上進(jìn)行曲面嵌入操作，需首先建立模型的混合曲面表征：給定CAD模型輸入，將CAD 模型逐條曲線、逐張曲面離散，繼而根據(jù)離散模型和CAD 模型的對(duì)偶關(guān)系建立初始的混合曲面表征[3]。

模型的連續(xù)-離散混合表征建立后，繼而需解決離散模型的幾何相交問題及求得邊界相交圖，同時(shí)更新連續(xù)曲面模型的B-rep。下文2.1 節(jié)和2.2 節(jié)分別介紹上述兩個(gè)步驟的實(shí)現(xiàn)。為方便理解，文中引用圖3 所示的典型錯(cuò)位裝配體展現(xiàn)本文算法各個(gè)過程中的處理效果，圖3 為模型的離散化形式，在曲面0 和曲面7 處發(fā)生重疊導(dǎo)致相交。

圖3 典型的錯(cuò)位裝配體Fig. 3 Typical misaligned assembly

本文中，離散模型中端點(diǎn)為B-rep 中幾何頂點(diǎn)離散對(duì)應(yīng)的網(wǎng)格點(diǎn)，邊界線段指代由B-rep 中的曲線離散而成的網(wǎng)格邊，而三條網(wǎng)格邊中一條或者多條為邊界線段的三角形被稱為邊界三角形。

2.1 離散曲面嵌入

離散曲面嵌入的目標(biāo)有兩個(gè)：一是計(jì)算邊界相交圖；二是移除三角形相交。

2.1.1 計(jì)算邊界相交圖

邊界相交圖為一個(gè)曲面的邊界（曲線）與其重疊的曲面求交形成的新的邊界環(huán)圖。如圖4（a）所示，曲面A 和B 重疊于共享區(qū)域C，其邊界相交圖為圖4（b），求交得到的交點(diǎn)及曲線形成新區(qū)域C 的邊界。

圖4 邊界相交圖示意Fig. 4 Intersected graph of boundary

本文嵌入算法通過求解邊界線段-三角形處相交以求得離散層面上的邊界相交圖，計(jì)算過程主要包括三個(gè)步驟：1）檢測(cè)三角形相交；2）嵌入邊界線段；3）邊界線段一致化處理。

以圖4 中所示情形為例，詳細(xì)介紹離散邊界相交的計(jì)算，圖5（a）為該情形的離散表征。

1）檢測(cè)相交三角形相交。本文模型中的單個(gè)部件間不存在自相交問題，所有的三角形相交都存在于部件與部件的相鄰處，所以本文通過計(jì)算部件相鄰區(qū)域處的三角形距離來檢測(cè)三角形相交。距離計(jì)算分為兩類：第一類通過精確的三角形相交檢測(cè)得到距離為零的三角形集合及其對(duì)應(yīng)的曲面索引對(duì)；第二類針對(duì)相鄰部件間在相鄰曲面處存在細(xì)縫的情況，通過對(duì)部件、曲面、對(duì)應(yīng)的面片集合層層進(jìn)行誤差 ε范圍內(nèi)的包圍盒相交測(cè)試，不斷縮小范圍至可能相交的三角面片，最后通過精確的解析計(jì)算三角形間的距離，若兩個(gè)三角形間的距離小于設(shè)定誤差ε，則認(rèn)為三角形相交。其中，誤差 ε的設(shè)置與模型相關(guān)，本文建議選取模型最小特征長(zhǎng)度的1/10。如圖5（b）所示，紅色線段所圍成的三角形即為相交的三角形，根據(jù)離散-連續(xù)映射關(guān)系可得知曲面A和B為相交索引對(duì)。

2）嵌入邊界線段。根據(jù)相交檢測(cè)得到相交曲面索引對(duì)，提取各自曲面的邊界三角形上相交邊界線段（圖5（b）中紅色較粗線段），將曲面B的邊界線段通過線段-三角形求交嵌入進(jìn)曲面A，同樣，將曲面A中的邊界線段嵌入進(jìn)曲面B，結(jié)果分別如圖5（c）和5（d）所示。

3）邊界線段一致化處理。在相交曲面索引對(duì)中邊界線段的嵌入過程中，因嵌入過程各自獨(dú)立，此過程中可能產(chǎn)生圖5（c）和5（d）中邊界線段不一致的情形，因此在嵌入過程中需要追蹤原始邊界線段的分裂狀態(tài)，在對(duì)應(yīng)的邊界線段上插入點(diǎn)使得相交曲面各自的邊界線段一致，如圖5（e）所示，通過插入點(diǎn)（空心點(diǎn)）得到一致的邊界線段。

圖5 離散邊界相交圖計(jì)算Fig. 5 Computational process of intersection graph

步驟2 中線段-三角形相交計(jì)算中具體的相交形式可分類為5 種：點(diǎn)點(diǎn)相交、點(diǎn)邊相交、點(diǎn)面相交、邊邊相交、邊面相交。除點(diǎn)點(diǎn)相交外，其余4 類相交均存在退化情形，如點(diǎn)是邊的端點(diǎn)、點(diǎn)是面片的端點(diǎn)、兩條邊相交于其中一條邊的端點(diǎn)、邊和面片相交于邊或面片的端點(diǎn)等。但是，若按照上文所列順序依次處理上述相交情形時(shí)，相應(yīng)退化情形會(huì)預(yù)先得到處理。例如，點(diǎn)邊相交的退化情形（點(diǎn)是邊的端點(diǎn)）在點(diǎn)點(diǎn)相交時(shí)已處理完畢，因此，檢測(cè)和解除點(diǎn)邊相交時(shí)只需考慮點(diǎn)對(duì)邊的投影位于邊的中間這一非退化情形。同理，邊面相交中，邊和面片相交于邊或面片的端點(diǎn)，這一退化情形會(huì)在點(diǎn)點(diǎn)相交、點(diǎn)邊相交或點(diǎn)面相交對(duì)應(yīng)的操作中得到處理；邊和面片相交于面片的邊界線段這一退化情形，會(huì)在邊邊相交對(duì)應(yīng)的操作中得到處理。因此，在實(shí)現(xiàn)相交的檢測(cè)和解除算法時(shí)，只要按順序處理，就無需考慮退化情形，相應(yīng)算法的實(shí)現(xiàn)得到大幅度簡(jiǎn)化。這里需要注意的是，處理相交的全過程中，我們需要及時(shí)更新和維護(hù)對(duì)應(yīng)的混合曲面表征?；谏鲜鏊悸罚? 的算法1 給出了處理所列5 種相交以獲得正確的邊界離散曲面拓?fù)涞乃惴鞒?。注意，因本文所考慮的輸入不存在邊界上邊面相交情形，算法1 并未包含邊面相交情形的處理。另外，同一個(gè)點(diǎn)可能與多個(gè)點(diǎn)、邊、面相交，邊和面也類似。

表1 算法1 線段-三角形相交Table 1 Algorithm 1 segment-triangle intersections

2.1.2 移除三角形相交

求得離散邊界相交圖后，在相交曲面的重疊區(qū)域形成了一致的邊界線段（圖5（c、e）），然而在共享區(qū)域內(nèi)部，三角形-三角形相交依然存在。本文在維護(hù)好的離散-連續(xù)映射關(guān)系的輔助下，通過拓?fù)潢P(guān)系移除共享區(qū)域的三角形相交。該拓?fù)浞椒ū苊饬藢?shí)際的三角形-三角形求交計(jì)算，也不存在浮點(diǎn)誤差范圍內(nèi)面片求交的健壯性問題。移除共享區(qū)域的三角形相交在離散層面形成一致的幾何表征，不僅可有效輔助后續(xù)的連續(xù)曲面上的嵌入及合并操作，而且可以將該離散表征直接作為文獻(xiàn)[19]中定義尺寸函數(shù)的背景網(wǎng)格，與連續(xù)B-rep 一起作為網(wǎng)格生成的兩個(gè)完整的輸入。

本文通過拓?fù)浞绞揭瞥切?三角形相交主要分為兩步：

1）遍歷所有曲面，對(duì)單個(gè)曲面的三角面片根據(jù)邊界線段進(jìn)行“染色”，并根據(jù)染色結(jié)果進(jìn)行區(qū)域劃分。圖6（a）和圖6（b）分別展示了對(duì)圖5（c）和圖5（e）中三角面片進(jìn)行區(qū)域劃分的結(jié)果。

圖6 移除三角形相交Fig. 6 Removal of triangle-triangle intersections

2）對(duì)相交曲面對(duì)中的區(qū)域進(jìn)行拓?fù)浔葘?duì)，若兩個(gè)區(qū)域擁有相同的邊界線段，則該區(qū)域視為重疊區(qū)域，然后刪掉一個(gè)區(qū)域內(nèi)的一個(gè)三角面片，移除三角形相交，同時(shí)更新離散-連續(xù)映射關(guān)系。如圖6 所示，通過拓?fù)鋵?duì)比可得知，區(qū)域2 與區(qū)域3 有著相同的邊界線段，因此這兩個(gè)區(qū)域?yàn)楣蚕韰^(qū)域，圖6（c）中刪掉了區(qū)域3 中三角面片，移除了重疊區(qū)域的三角形相交。圖6（d）為更新后的連續(xù)曲面表征示意，區(qū)域2 處為原始曲面A和B的重疊區(qū)域，因此該區(qū)域三角面片對(duì)應(yīng)的連續(xù)曲面索引為A、B。

圖7 展示了圖3 例子經(jīng)邊界相交圖計(jì)算和三角形相交移除后，在曲面0 和曲面7 相交區(qū)域的離散結(jié)果。圖7（b）為嵌入后的結(jié)果，該區(qū)域三角形相交已被正確移除，曲面0 中的邊界線段也已成功嵌入新的曲面中。

圖7 離散曲面嵌入結(jié)果Fig. 7 Results of discrete imprinting

2.2 連續(xù)曲面嵌入

本文算法意在獲取一個(gè)完成曲面嵌入的連續(xù)B-rep，以支持后續(xù)的網(wǎng)格生成算法。離散曲面嵌入完成后，還需在連續(xù)B-rep 上完成相應(yīng)的自動(dòng)曲面嵌入。

連續(xù)B-rep 的曲面嵌入主要涉及兩種基本操作：分裂與合并。其中分裂又分為曲線分裂和曲面分裂；合并分為頂點(diǎn)合并、曲線合并及曲面合并。根據(jù)離散曲面嵌入過程中得到的邊界相交圖及在重疊區(qū)域獲得的一致的離散表征，在離散-連續(xù)映射關(guān)系的輔助下，本文設(shè)計(jì)了相應(yīng)的分裂及合并操作，自底向上完成連續(xù)B-rep 的自動(dòng)曲面嵌入。本文中的連續(xù)幾何采用文獻(xiàn)[1]中具有完全自主知識(shí)產(chǎn)權(quán)的簡(jiǎn)化的幾何引擎所提供的B-rep 表征，其核心為基于Ferguson曲線和Conns 曲面的裁剪曲面。本文所設(shè)計(jì)的分裂與合并操作均為拓?fù)洳僮?，完全保留曲線/曲面的嚴(yán)格數(shù)學(xué)表達(dá)，故而能夠最大程度地保留嵌入過程中的幾何精度，也為后續(xù)的網(wǎng)格生成提供了精度保證。

2.2.1 分裂操作

曲線分裂：對(duì)于一條曲線，遍歷其對(duì)應(yīng)的邊界線段，若其對(duì)應(yīng)的邊界線段中包含多于2 個(gè)端點(diǎn)，則根據(jù)這些端點(diǎn)對(duì)該曲線進(jìn)行分裂。如圖8（a）所示，曲線1 對(duì)應(yīng)的邊界線段中包含有3 個(gè)端點(diǎn)（黑色實(shí)心點(diǎn)），因此根據(jù)邊界線段中間的端點(diǎn)對(duì)曲線1 進(jìn)行分裂，得到圖8（b）中新的曲線1 和曲線2，并同時(shí)更新離散-連續(xù)映射關(guān)系。

圖8 曲線分裂過程Fig. 8 Splitting of a curve

曲面分裂：對(duì)于一個(gè)曲面，首先對(duì)其所對(duì)應(yīng)的三角面片根據(jù)其屬性（曲面索引）進(jìn)行分類，若該曲面包含多個(gè)種類的三角面片，則根據(jù)面片分類結(jié)果對(duì)該曲面進(jìn)行分裂。分裂過程中，曲面的支撐曲面保持不變，根據(jù)分類的三角面片中包含的邊界線段所對(duì)應(yīng)的曲線屬性形成新的環(huán)，完成曲面的分裂。圖9 為圖3例子在重疊區(qū)域的曲面分裂過程，原始曲面7 中包含有兩種屬性的三角面片，分別為屬性7 和屬性0、7，根據(jù)不同種類三角面片上邊界線段對(duì)應(yīng)的曲線索引，保持支撐曲面不變的情況下形成新的環(huán)，分裂為新的曲面7 和曲面8，其B-rep 如圖9（b）所示，并同時(shí)更新離散-連續(xù)映射關(guān)系。

圖9 曲面分裂過程Fig. 9 Splitting of a surface

此外，在曲面分裂的過程中可能出現(xiàn)截?cái)嗟亩鄥^(qū)域情形，如圖10，曲面A和曲面B重疊于曲面AB區(qū)域（橙色），在三角面片分類過程中，曲面A中的面片將被分為三部分，共享區(qū)域AB和互不連通的兩個(gè)A區(qū)域。鑒于此種情形，本文算法對(duì)每一類三角面片進(jìn)行廣度優(yōu)先遍歷（BFS），二次分類互不連通的同一屬性的三角面片，之后完成曲面分裂。

圖10 多區(qū)域情況Fig. 10 Situation of multiple regions

2.2.2 合并操作

頂點(diǎn)合并：若多個(gè)幾何頂點(diǎn)對(duì)應(yīng)同一個(gè)端點(diǎn)，則刪除多余頂點(diǎn)，只留一個(gè)頂點(diǎn)完成頂點(diǎn)合并。

曲線合并：若多條曲線對(duì)應(yīng)同一個(gè)邊界線段集合，則刪掉多余曲線，只留一條曲線完成曲線合并。

曲面合并：若多個(gè)曲面對(duì)應(yīng)同一個(gè)三角面片集合，則刪掉多余曲面，只留一個(gè)曲面完成曲面合并。

在分裂及合并的基本操作的輔助下，本文采用自底向上的方法完成自動(dòng)嵌入。根據(jù)表2 中的算法2，從低維到高維依次完成頂點(diǎn)的合并、曲線的分裂及合并、曲面的分裂及合并、部件的曲面索引更新，最終完成連續(xù)曲面的自動(dòng)嵌入，得到用于網(wǎng)格生成的連續(xù)B-rep 模型。

表2 算法2 自底向上自動(dòng)嵌入Table 2 Algorithm 2 bottom-up imprinting

圖11 展示了以嵌入后的B-rep 作為輸入，在其幾何上生成的網(wǎng)格結(jié)果，以驗(yàn)證本文嵌入方法的有效性?？梢娗? 已被正確嵌入進(jìn)曲面7，并保持了曲面0 中的邊界線段，生成了一致的保形網(wǎng)格。

圖11 網(wǎng)格細(xì)節(jié)Fig. 11 Details of the generated meshes

3 數(shù)值驗(yàn)證

3.1 曲面嵌入及網(wǎng)格結(jié)果

本文選取了某型號(hào)火箭、靶球和大壩三個(gè)典型裝配體CAD 模型對(duì)算法進(jìn)行數(shù)值驗(yàn)證，其分別包含13 個(gè)、115 個(gè)和1 884 個(gè)部件，模型網(wǎng)格如圖12 所示。分部件建模獲得的模型在不同部件的交界面處存在嚴(yán)重的幾何重疊及錯(cuò)位，本文算法正確地消除了這些幾何干涉，輸出了幾何、拓?fù)湟恢碌哪Ｐ停⒃诖四Ｐ蜕仙闪烁哔|(zhì)量的計(jì)算網(wǎng)格。

圖12 典型的裝配體模型Fig. 12 Typical assembly geometry

圖13 展示了各模型曲面嵌入及網(wǎng)格生成結(jié)果的局部細(xì)節(jié)。其中，火箭模型中，共檢測(cè)出1 656 處相交，曲面嵌入算法花費(fèi)時(shí)間34 s；靶球模型檢測(cè)處15 177 處相交，曲面嵌入算法花費(fèi)時(shí)間1 047 s；大壩模型中，共檢測(cè)出35 174 處相交，曲面嵌入算法花費(fèi)時(shí)間1 553 s。其中，連續(xù)曲面嵌入過程中只涉及到拓?fù)洳僮?，所耗費(fèi)時(shí)間基本可以忽略（大壩例子所耗時(shí)間最多，但亦不足1 s）。

圖13 曲面嵌入及網(wǎng)格細(xì)節(jié)Fig. 13 Details of imprinting and meshes

本文方法時(shí)間花費(fèi)主要在于離散曲面嵌入中的相交檢測(cè)及相交處理過程（邊界線段嵌入和邊界一致化處理）中，表3 統(tǒng)計(jì)了各個(gè)模型中此兩個(gè)過程中所耗費(fèi)時(shí)間數(shù)據(jù)。大壩例子中因其最多的部件以及更多的錯(cuò)位情形，其相交檢測(cè)時(shí)間花費(fèi)占比也最高，約為25%左右，而另外兩個(gè)例子的占比分別約為6%和7%。

表3 時(shí)間統(tǒng)計(jì)Table 3 Statistics of time performance

曲面嵌入算法中涉及到曲面的分裂及合并操作，這些操作會(huì)引起模型曲面和曲線數(shù)量的變化。如圖3 情形中，將有發(fā)生1 次分裂、1 次合并，則曲面總數(shù)不變；如圖4 情形中則發(fā)生2 次分裂，1 次合并則會(huì)導(dǎo)致曲面數(shù)量上升。若是曲面完全重復(fù)情形，則只發(fā)生合并操作，則其導(dǎo)致曲面數(shù)量下降。本文中，輸入的火箭模型執(zhí)行曲面嵌入算法后曲面和曲線數(shù)量保持不變，仍為124 張曲面和248 條曲線；靶球模型執(zhí)行曲面嵌入算法后，曲面數(shù)由1 952 張曲面和4 739條曲線減少到1 768 張曲面和4 464 條曲線；大壩模型曲面數(shù)由14 322 減少到12 861，曲線數(shù)由31 676 減少到22 029。

以執(zhí)行曲面嵌入后的CAD 模型以及適應(yīng)模型幾何特征與用戶參數(shù)自動(dòng)計(jì)算的單元尺寸函數(shù)為輸入，即可生成幾何與拓?fù)湔_、單元形態(tài)和分布合理的高質(zhì)量計(jì)算網(wǎng)格模型。針對(duì)火箭模型，測(cè)試中生成的曲面網(wǎng)格包含57 930 個(gè)三角形單元，實(shí)體網(wǎng)格包含102 569 個(gè)四面體單元；靶球模型的曲面網(wǎng)格和實(shí)體網(wǎng)格則分別包含5 146 056 和19 542 658 個(gè)單元；而大壩模型的對(duì)應(yīng)數(shù)據(jù)為6 294 823 和45 620 136 個(gè)單元。

3.2 對(duì)比討論

如引言所述，曲面嵌入可分為直接在連續(xù)曲面Brep 上嵌入和在離散三角形網(wǎng)格上進(jìn)行曲面嵌入，其相應(yīng)代表有CADfix、libigl 及TetWild 等。本節(jié)中，我們將所提方法與上述程序進(jìn)行了相關(guān)的對(duì)比以及討論。

CADfix 所提供的自動(dòng)嵌入操作不能處理圖3 中這種部分嵌入的情況，需要通過布爾及分裂等操作完成最后的嵌入，該過程需要手工操作，對(duì)于圖3 所示簡(jiǎn)單例子可迅速完成，但對(duì)于大壩和靶球這種復(fù)雜例子，所涉及繁瑣的手工操作往往令人難以忍受，因此本文算法的自動(dòng)化具有明顯優(yōu)勢(shì)。libigl 提供了一個(gè)在浮點(diǎn)誤差內(nèi)比較穩(wěn)定健壯的三角形相交算法，但無法引入誤差，在一些有狹小縫隙的地方無法完成嵌入，當(dāng)然在相交中引入誤差本身是個(gè)十分棘手的難題。如圖14 與之相比，本文通過在邊界相交圖的計(jì)算中引入誤差，在曲面內(nèi)部通過拓?fù)浔容^去除三角形相交，即可以正確完成在這些區(qū)域的自動(dòng)嵌入。

圖14 本文方法與libigl 嵌入對(duì)比Fig. 14 Comparison of imprinting between the proposed method and libigl

TetWild 通過四面體優(yōu)化的方法來完成模型的嵌入及修復(fù)功能，并在該過程中引入誤差，控制修復(fù)的精度，該方法亦可適用于本文所選取模型，但是存在著兩個(gè)缺陷。其一，TetWild 的相交運(yùn)算是在有理數(shù)的輔助下完成的，遠(yuǎn)比浮點(diǎn)運(yùn)算速度慢，另外四面體優(yōu)化迭代過程也耗時(shí)較多；其二，TetWild 修復(fù)僅僅基于離散表征，其網(wǎng)格結(jié)果中可能出現(xiàn)“鋸齒”現(xiàn)象，使得網(wǎng)格精度降低。表4 統(tǒng)計(jì)了TetWild 和本文算法處理3 個(gè)模型所耗時(shí)間。對(duì)比表明，本文算法所耗時(shí)間明顯小于TetWild，且隨著模型規(guī)模的增大，本文算法時(shí)間優(yōu)勢(shì)越來越凸顯，對(duì)于3 個(gè)測(cè)試樣例，TetWild 所耗時(shí)間是本文算法的2 倍以上。

表4 時(shí)間對(duì)比Table 4 Comparison of computational time

此外，在火箭和大壩模型（誤差設(shè)置分別為0.5 mm和0.1 mm）中TetWild 出現(xiàn)了“鋸齒”現(xiàn)象，見圖15，而本文算法通過連續(xù)-離散的雙重表征，嵌入過程中保留了連續(xù)幾何精確的數(shù)學(xué)表達(dá)而僅僅改變了B-rep的拓?fù)?，?yán)格保證了模型的幾何精度。

圖15 本文方法與TetWild 在“鋸齒”處對(duì)比Fig. 15 Comparison between the proposed method and TetWild in zigzag region

4 結(jié) 論

本文針對(duì)錯(cuò)位裝配體在部件間重疊區(qū)域的多份表征問題，應(yīng)用連續(xù)-離散混合曲面造型方法，開發(fā)了適用于分部件建模獲得的裝配體模型的自動(dòng)曲面嵌入算法。在離散曲面上，通過引入誤差計(jì)算邊界線段-三角形相交以求得邊界相交圖，而后通過拓?fù)洳僮饕瞥溆嗳切蜗嘟粏栴}，完成離散曲面嵌入；之后根據(jù)邊界相交圖及離散嵌入結(jié)果，在簡(jiǎn)化的幾何引擎上設(shè)計(jì)了相應(yīng)的曲線曲面分裂合并等操作，并在離散-連續(xù)映射關(guān)系的輔助下自動(dòng)完成連續(xù)曲面B-rep上的自動(dòng)曲面嵌入。在典型算例下用嵌入后的B-rep為輸入，以其網(wǎng)格生成結(jié)果驗(yàn)證了該自動(dòng)曲面嵌入算法的有效性。通過與其他嵌入方法的對(duì)比，展示了本文算法在自動(dòng)化程度、嵌入有效性、精度保證及時(shí)間上的優(yōu)勢(shì)。本文算法的主要優(yōu)點(diǎn)有：

1）曲面嵌入中的幾何計(jì)算基于線性的離散模型，通過線段-三角形相交計(jì)算邊界相交圖，并運(yùn)用拓?fù)浔葘?duì)移除三角形相交；

2）在離散-連續(xù)曲面的映射關(guān)系輔助下，根據(jù)邊界相交圖，在模型B-rep 上完成嵌入和合并操作，該過程不更改模型B-rep 的數(shù)學(xué)表達(dá)而只改變其拓?fù)洌捎行ПＷC嵌入后模型的幾何精度；

3）保證修復(fù)后裝配體模型B-rep 的正確性和一致性，可直接復(fù)用已有的基于B-rep 的主流曲面網(wǎng)格生成算法，生成保形的曲面網(wǎng)格。

本文算法目前尚不支持部件間互相貫穿的情形，在后續(xù)的工作中我們將嘗試在B-rep 上設(shè)置約束條件以處理貫穿情形下的曲面嵌入。