一種面向孔洞修復的三角網格復雜孔洞分割方法

張善輝 武偉 魏威 邊靜

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

1 引言

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

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

圖1：單孔洞與連續套洞的示例圖

圖2：單孔洞與連續套洞的識別流程

圖3：連續套洞的分割流程

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

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

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

2 單孔洞與連續套洞

2.1 單孔洞與連續套洞的特點

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

圖6：某商業軟件的孔洞識別效果

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

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

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

2.2 單孔洞與連續套洞的識別方法

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

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

3 連續套洞的分割方法

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

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

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

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

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

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

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

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

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

4 系統實現與驗證

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

5 總結

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