張善輝 武偉 魏威 邊靜

（1.山東大學(xué)控制科學(xué)與工程學(xué)院 山東省濟南市 250061 2.山東山大華天軟件有限公司 山東省濟南市 250101）

1 引言

三角網(wǎng)格具有簡潔、直觀、描述能力強的特點，是一種應(yīng)用十分廣泛的幾何模型表達形式，逐漸成為3D 打印技術(shù)的重要應(yīng)用基礎(chǔ)。但是，在網(wǎng)格模型的構(gòu)建和獲取過程中，經(jīng)常會產(chǎn)生各類網(wǎng)格模型的孔洞，嚴重影響了3D 打印模型的外觀和質(zhì)量。因此，三角網(wǎng)格模型中孔洞的識別和修復(fù)成為提高3D 打印質(zhì)量的關(guān)鍵。

目前，國內(nèi)外許多學(xué)者對三角網(wǎng)格模型的孔洞修復(fù)方法進行了深入研究，其中比較典型的修復(fù)方法為：根據(jù)孔洞的點分布，計算特征平面，將孔洞點投影到特征面上進行分元，然后采用隱式函數(shù)[1]、徑向基函數(shù)[2,3]、波前法[4]等，將特征面上的點映射到三維模型上。該類方法得到的填孔面的形態(tài)往往比較理想，但適用場景較為苛刻，在簡單孔洞形態(tài)下能夠獲取理想的效果，但對復(fù)雜孔洞形態(tài)可能出現(xiàn)映射失敗或者映射錯誤的情況，導(dǎo)致填孔效果差。學(xué)者Jun[5]提出一種將復(fù)雜孔洞剖分為簡單孔洞再進行修補的算法，解決了投影過程中具有自相交邊界的孔洞剖分和修補，但在處理其他類型復(fù)雜孔洞及修補效果方面，特別是非投影過程的自相交邊界問題，并不是很理想。學(xué)者溫佩芝提出一種缺陷孔洞自動識別與孔洞區(qū)域細節(jié)特征保持的曲面修復(fù)方法，但方法僅適用于單連通區(qū)域的缺陷孔洞修復(fù)，忽略了復(fù)雜缺失區(qū)域的拓撲結(jié)構(gòu)，且算法的時間復(fù)雜度也較高[6]。Chao Feng 提出一種根據(jù)三角網(wǎng)格孔洞頂點的規(guī)模進行孔洞分類的方法，并分別采用不同的修復(fù)方法，可以實現(xiàn)快速孔洞修復(fù)，但分類方法中僅僅考慮孔洞大小，忽略了孔洞的復(fù)雜拓撲形態(tài)，不能很好的解決復(fù)雜孔洞的修復(fù)效果[7]。

圖1：單孔洞與連續(xù)套洞的示例圖

圖2：單孔洞與連續(xù)套洞的識別流程

圖3：連續(xù)套洞的分割流程

圖4：外部孔洞線下一邊界點的判斷

圖5：單孔洞的識別與輸出

綜上所述，當(dāng)前的三角網(wǎng)格模型修復(fù)大多集中于修復(fù)方法的研究，在對復(fù)雜孔洞的分割處理方面還存在欠缺。因此，為實現(xiàn)復(fù)雜孔洞的修復(fù)，本文從各類孔洞的拓撲形態(tài)出發(fā)，首先解決復(fù)雜孔洞的識別與分割問題，將其劃分為單孔洞和連續(xù)套洞兩類，并針對形態(tài)復(fù)雜的連續(xù)套洞嵌套、交叉特點，提出一種對三角網(wǎng)格模型孔洞進行檢測、識別和分割的方法，將連續(xù)套洞剖分為單孔洞，彌補了各類孔洞修復(fù)方法在復(fù)雜孔洞修復(fù)中的不足。

2 單孔洞與連續(xù)套洞

2.1 單孔洞與連續(xù)套洞的特點

通過統(tǒng)計和分析三角網(wǎng)格模型中各類孔洞修復(fù)的失敗案例發(fā)現(xiàn)，修復(fù)失敗現(xiàn)象常常發(fā)生在多個孔洞相鄰的情況下，易造成各類孔洞映射失敗或者映射錯誤，進而導(dǎo)致修復(fù)效果不理想。為解決這一問題，需要分析此類孔洞的特點，總結(jié)其與單孔洞的差別。通過大量案例的分析，發(fā)現(xiàn)單孔洞與此類孔洞的主要區(qū)別為：是否存在多個孔洞線的公共點。為此，定義如下兩類孔洞：

圖6：某商業(yè)軟件的孔洞識別效果

圖7：案例示意圖——背包

定義1：單孔洞——孔洞線上的點可以依次連接組成一條唯一解的閉環(huán)。如圖1(a)所示。

定義2：連續(xù)套洞——由多個單孔洞組成，且它們的孔洞線上的點存在公共點，導(dǎo)致其具有多種表示各個單獨閉環(huán)的方法。如圖1(b)所示，連續(xù)套洞的A、B、C、D 四點均為多條孔洞線的公共點，以逆時針方向為正，可以識別出此連續(xù)套洞的孔洞邊界為A-P1-AB-P5-B-C-P6-P4-C-P3-D-P2-D-A。

2.2 單孔洞與連續(xù)套洞的識別方法

由于單孔洞和連續(xù)套洞在三角網(wǎng)格模型孔洞修復(fù)中的難度差異較大，采取的修復(fù)方法各不相同。因此，對所有的孔洞進行分類識別，確定其是否為單孔洞或連續(xù)套洞，這是孔洞修復(fù)的必要步驟。在識別之前，需要對輸入的三角網(wǎng)格模型進行預(yù)處理，快速建立模型的面片、邊和頂點的拓撲結(jié)構(gòu)；根據(jù)三角網(wǎng)格模型的面片與邊的連接關(guān)系，獲取三角網(wǎng)格模型的所有單連通區(qū)域，將每個單連通區(qū)域視為一個部件；對每個部件查找自由邊，根據(jù)邊與點之間的連接關(guān)系，將所有的自由邊首尾連接，得到孔洞線，即獲得所有孔洞的基本信息，包括孔洞線、孔洞方向和孔洞與部件之間的關(guān)聯(lián)關(guān)系。其中，自由邊是指僅連接一個面片的邊；孔洞線是指在保持原始三角網(wǎng)格模型拓撲關(guān)系的基礎(chǔ)上，將每個集合中自由邊的首尾連接，所形成的閉合線。

在此基礎(chǔ)上，構(gòu)建了單孔洞與連續(xù)套洞的識別流程，如圖2 所示。首先，通過所有獲取孔洞的基本信息，查找孔洞線的所有自由邊；查找自由邊的集合，根據(jù)各條邊和頂點的拓撲結(jié)構(gòu)關(guān)系，計算自由邊中的所有點與邊的連接關(guān)系；從任一點出發(fā)，依據(jù)連接關(guān)系，查找閉合邊界線；隨后，判斷閉合邊界線是否存在公共點，如果不存在公共點，則輸出單孔洞，如果存在公共點，則為連續(xù)套洞，輸出其對應(yīng)的邊界信息，為后續(xù)的連續(xù)套洞的分割提供服務(wù)。

3 連續(xù)套洞的分割方法

為方便三角網(wǎng)格模型的修復(fù)，必須把復(fù)雜的連續(xù)套洞分割為簡單的單孔洞，提高各單孔洞修復(fù)算法的準(zhǔn)確率和修復(fù)質(zhì)量。由于連續(xù)套洞存在孔洞線的嵌套和連接，容易造成多個孔洞的分解存在誤差或錯誤。為此，研究提出了一種基于公共點的連續(xù)套洞孔洞線的分解和重構(gòu)方法。具體步驟如圖3 所示。

第一步，檢測連續(xù)套洞邊界。根據(jù)孔洞識別的信息，檢測連續(xù)套洞的孔洞邊界，按照逆時針方向，形成對應(yīng)的孔洞線。例如圖1(b)中的邊界為A-P1-A-B-P5-B-C-P6-P4-C-P3-D-P2-D-A，識別出相同的面片點索引，即為公共點，如圖1(b)中的A、B、C、D 四點。

第二步，分割邊界線。根據(jù)連續(xù)套洞的公共點，將連續(xù)套洞的內(nèi)部區(qū)域分割為若干個獨立的孔。例如圖1(b)中的連續(xù)套洞邊界，可分割邊界線得到五個單獨的孔洞，分別為A-P1-A、B-P5-B、C-P6-P4-C、D-P2-D、A-B-C-P3-D-A。

第三步，判斷內(nèi)部孔或外部孔。將孔洞線上的點投影到平面上，根據(jù)點與多邊形的內(nèi)外關(guān)系，計算各個孔洞的內(nèi)外位置關(guān)系；如果某一孔洞L1 的點均在另一孔洞L2 外部，則認為是L1 在L2 外。如果一條孔洞線不在任一個孔洞線內(nèi)部，則該孔洞線為外部孔，如果一條孔洞線在某一個孔洞線內(nèi)部，則該孔洞線為內(nèi)部孔。

第四步，條件判斷——是否為外部孔。如果外部孔不包含內(nèi)部孔，則跳轉(zhuǎn)到第七步；否則，繼續(xù)執(zhí)行第五步。判斷可知，圖1(b)的連續(xù)套洞中外部孔有A-P1-A、B-P5-B、D-P2-D、A-B-C-P3-D-A，內(nèi)部孔有C-P6-P4-C，它被A-B-C-P3-D-A 外部孔包含。

第五步，判斷并確定新的邊界點。對于包含內(nèi)部孔的外部孔，查找其孔洞線中的公共點，計算公共點和公共點連接的其它孔洞的索引點連線與公共點和當(dāng)前外部孔洞線的前一索引點連線的夾角，選擇夾角最小的這一索引點作為新的邊界點。例如圖4 中的C 點，通過計算夾角可知，∠1C2 小于∠1C3，判斷其下一邊界點為射線C2 方向，即P6 方向，而不是P4 方向。

第六步，形成新的邊界線。從新的邊界點開始，將內(nèi)部孔上的點按照邊界上的連接順序全部插入外部孔的邊界線中，合并孔洞外邊線和內(nèi)邊線。即示例中，將內(nèi)部孔C-P6-P4-C 插入到外部孔A-BC-P3-D-A 中，得到新的邊界線為A-B-C-P6-P4-C-P3-D-A。

第七步，輸出單孔洞。將所有滿足條件的孔洞作為一個單孔洞輸出，并給出邊界線。根據(jù)此方法，示例中輸出四個單孔洞，邊界線分別為A-P1-A、B-P5-B、D-P2-D、A-B-C-P6-P4-C-P3-D-A。如圖5 所示的填充區(qū)域，即為四條邊界線所圍成的四個單孔洞。

對比傳統(tǒng)的孔洞識別方法和軟件，此案例的孔洞容易將C-P6-P4-C 識別為單孔洞，并輸出。依據(jù)此種結(jié)果填充后，所得模型將不是期望的結(jié)果，并且會產(chǎn)生大量的自相交面片。如圖6 所示，綠色孔洞線和紅色孔洞線均為識別的單孔洞，但是內(nèi)部的紅色孔洞線在修復(fù)時會與外部的孔洞線發(fā)生自相交，這顯然與實際孔洞不符。

4 系統(tǒng)實現(xiàn)與驗證

通過上述對三角網(wǎng)格模型孔洞的識別及連續(xù)套洞的分割方法的研究，采用效率更高的C++語言，開發(fā)實現(xiàn)了相應(yīng)的孔洞分割功能，為后續(xù)的模型修復(fù)提供更加簡便的單孔洞，便于模型修復(fù)準(zhǔn)確性和效果的提升。此功能也已經(jīng)成功在某模型修復(fù)組件中進行了應(yīng)用，達到了處理復(fù)雜孔洞分割的目的。例如圖7 中的背包模型，具有復(fù)雜的孔洞類型，包含了多個單孔洞和復(fù)雜的連續(xù)套洞。通過孔洞識別方法可以識別出所有的單孔洞和連續(xù)套洞。圖中，紅色線條代表連續(xù)套洞，綠色線條代表單孔洞。背包中共識別出兩組連續(xù)套洞，即點畫線所包圍的區(qū)域。借助連續(xù)套洞的分割方法，可以將上部的連續(xù)套洞合并為一個完整的單孔洞，下部的連續(xù)套洞可以分割為5個單孔洞。由此可以驗證，本方法可以適用于復(fù)雜孔洞的識別和分割，為后續(xù)的孔洞修復(fù)提供了有效的模型預(yù)處理功能。

5 總結(jié)

從三角網(wǎng)格模型孔洞修復(fù)效果不佳的角度出發(fā)，發(fā)現(xiàn)了孔洞形態(tài)對修復(fù)效果的影響。通過分析各類孔洞的特點，將孔洞劃分為單孔洞和連續(xù)套洞，并給出了對應(yīng)的孔洞識別方法；針對連續(xù)套洞孔洞線的嵌套和連接特點，提出了一種基于公共點的連續(xù)套洞孔洞線的分解和重構(gòu)方法，解決了連續(xù)套洞輸出為單孔洞的問題，避免了孔洞修復(fù)中常見的自相交面片的出現(xiàn)。通過實例和軟件驗證，此識別和分割方法可以對三角網(wǎng)格模型的復(fù)雜孔洞進行預(yù)處理，極大的提高了模型修復(fù)的效果和質(zhì)量，可以廣泛應(yīng)用于3D 打印模型修復(fù)業(yè)務(wù)中。