一種面向孔洞修復(fù)的三角網(wǎng)格復(fù)雜孔洞分割方法

張善輝 武偉 魏威 邊靜

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

1 引言

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

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

圖1：?jiǎn)慰锥磁c連續(xù)套洞的示例圖

圖2：?jiǎn)慰锥磁c連續(xù)套洞的識(shí)別流程

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

圖4：外部孔洞線(xiàn)下一邊界點(diǎn)的判斷

圖5：?jiǎn)慰锥吹淖R(shí)別與輸出

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

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

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

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

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

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

定義1：?jiǎn)慰锥础锥淳€(xiàn)上的點(diǎn)可以依次連接組成一條唯一解的閉環(huán)。如圖1(a)所示。

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

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

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

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

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

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

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

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

第三步，判斷內(nèi)部孔或外部孔。將孔洞線(xiàn)上的點(diǎn)投影到平面上，根據(jù)點(diǎn)與多邊形的內(nèi)外關(guān)系，計(jì)算各個(gè)孔洞的內(nèi)外位置關(guān)系；如果某一孔洞L1 的點(diǎn)均在另一孔洞L2 外部，則認(rèn)為是L1 在L2 外。如果一條孔洞線(xiàn)不在任一個(gè)孔洞線(xiàn)內(nèi)部，則該孔洞線(xiàn)為外部孔，如果一條孔洞線(xiàn)在某一個(gè)孔洞線(xiàn)內(nèi)部，則該孔洞線(xiàn)為內(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 外部孔包含。

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

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

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

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

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

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

5 總結(jié)

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