閆濤

（南通大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南通 226019）

STL（Stereolithogrphy Interface）文件格式是由美國3DSystem公司于1987年定制的，其使用三角形面片來表示三維實(shí)體模型，己成為眾多CAD軟件的標(biāo)準(zhǔn)數(shù)據(jù)輸入和輸出模塊，也被視為正、逆向工程設(shè)計(jì)轉(zhuǎn)換到快速原型的一種公認(rèn)的標(biāo)準(zhǔn)，當(dāng)模型由CAD或逆行工程軟件建成后，即可直接輸出到快速原型系統(tǒng)構(gòu)建實(shí)體模型。

STL文件必須遵循一定的規(guī)范才能正確地描述三維實(shí)體模型，包括：1）共頂點(diǎn)規(guī)則，每一個(gè)三角面片必須與其相鄰的每一個(gè)面片共兩個(gè)頂點(diǎn)；2）取向規(guī)則，單個(gè)面片法向量符合右手法則且其法向量必須指向?qū)嶓w外面；3）充滿規(guī)則，小三角面片必須布滿三維模型的所有表面，不得有任何遺漏。但是，在實(shí)際的應(yīng)用中，STL文件會(huì)存在各種不同的錯(cuò)誤，常見的錯(cuò)誤主要有：孔洞、重疊、錯(cuò)位和不共頂點(diǎn)等?？锥词荢TL文件中最常見的一種錯(cuò)誤，主要是在對(duì)多個(gè)大曲率曲面相交構(gòu)成的表面模型三角化過程中，進(jìn)行拼接時(shí)有小的曲面丟失而造成的。這些孔洞的存在會(huì)影響許多后續(xù)的操作，如快速原型制造、有限元分析等。國內(nèi)外許多學(xué)者對(duì)此都進(jìn)行了研究。但由于大多數(shù)算法在構(gòu)造新三角片時(shí)僅僅采用原有的孔洞多邊形頂點(diǎn)，而沒有增加新的頂點(diǎn)，難以獲得較好的用于填補(bǔ)孔洞的三角片形狀，修補(bǔ)效果不夠理想。

筆者在研究原有算法的基礎(chǔ)之上，針對(duì)封閉式STL三角網(wǎng)格模型中存在的孔洞，根據(jù)實(shí)際的需求來添加新的頂點(diǎn)，從而獲得新的三角形面片，算法主要包括孔洞邊界的提取及非獨(dú)立孔洞的分裂，確定孔洞邊界點(diǎn)的平滑度，構(gòu)造新的三角形面片。

1 孔洞邊界的提取

對(duì)于封閉式的STL三角網(wǎng)格曲面，如果網(wǎng)格曲面中沒有孔洞，那么該曲面中的每一條邊都有兩個(gè)鄰接三角片，則這樣的邊稱之為內(nèi)部邊。如果存在某條邊只有一個(gè)鄰接三角片，那么這條邊稱之為邊界邊，則該條邊是構(gòu)成孔洞多邊形的一條邊，而邊界邊的兩個(gè)端點(diǎn)稱之為邊界點(diǎn)。邊界點(diǎn)所在的三角形則稱為邊界三角形。如圖1所示，所有相互連接的邊界邊就構(gòu)成了一個(gè)完整的孔洞。

圖1 孔洞基本信息Fig.1 Basic information of Holes

根據(jù)STL三角網(wǎng)格模型的取向規(guī)則，每個(gè)三角形面片的三個(gè)頂點(diǎn)的排列必須符合右手法則，即沿著平面片法矢相反的方向觀察，三個(gè)頂點(diǎn)應(yīng)該是逆時(shí)針排列。因此，按逆時(shí)針方向，如圖2所示，將每條邊的兩個(gè)端點(diǎn)分別定義為起點(diǎn)和端點(diǎn)。那么，在一個(gè)獨(dú)立孔洞邊界的提取過程中先識(shí)別到一條邊界邊，以該邊為起始邊，然后在該邊終點(diǎn)所在的其他邊中查找以該終點(diǎn)為起點(diǎn)的邊界邊，以此類推，直到一條邊界邊的終點(diǎn)為起始邊的起點(diǎn)，那么，一個(gè)孔洞的邊界提取就此結(jié)束[1]。如圖3所示，如果以孔洞內(nèi)部為觀察點(diǎn)，那么孔洞的邊界按順時(shí)針排列。

圖2 三角形邊的定義Fig.2 Definition of the triangle edge

圖3 孔洞邊界的排列Fig.3 Arrangement of the Hole boundary

而對(duì)于非獨(dú)立的孔洞，如圖4（a）所示，共頂點(diǎn)屬于兩個(gè)不同孔洞的邊界點(diǎn)。那么將共頂點(diǎn)再作為另一個(gè)孔洞的起始點(diǎn)，任選一條以共頂點(diǎn)為起點(diǎn)的邊界邊，繼續(xù)查找，此時(shí)會(huì)出現(xiàn)兩種情況：1）如果找到原始的起始點(diǎn)，一個(gè)孔洞邊界提取結(jié)束；2）如果找到了以共頂點(diǎn)為新起始點(diǎn)的起始點(diǎn)，那么一個(gè)新的孔洞邊界提取結(jié)束。再選另外以共頂點(diǎn)為起點(diǎn)的邊界邊開始另一個(gè)孔洞邊界的提取。這樣就可以將非獨(dú)立孔洞分裂為多個(gè)獨(dú)立孔洞，如圖4（b）所示。

圖4 孔洞的分裂Fig.4 Hole split

2 孔洞邊界點(diǎn)平滑度的確定

孔洞常會(huì)出現(xiàn)在三角網(wǎng)格模型的特征線上，為了使修補(bǔ)后的孔洞區(qū)域和原有的區(qū)域盡量保持原有的特征，本文在對(duì)孔洞修補(bǔ)之前先確定孔洞邊界點(diǎn)的平滑度，然后計(jì)算孔洞邊界點(diǎn)的平均平滑度，在修補(bǔ)時(shí)對(duì)小于平均平滑度的頂點(diǎn)先行修補(bǔ)。

如圖5所示，在三角網(wǎng)格模型中，頂點(diǎn)的平滑度可以通過該頂點(diǎn)所在的三角形的夾角的平均值來確定，如果夾角的平均值越小，就表明該點(diǎn)所在的區(qū)域越趨于平滑[2]。三角形的單位法向量可以根據(jù)三角形的3個(gè)頂點(diǎn)來計(jì)算，即：

鄰接三角形的夾角可以通過它們的外法矢來計(jì)算[3]，公式如下：

圖5 頂點(diǎn)鄰接的三角形的法矢Fig.5 Vertex adjacent of the triangles’normals

3 孔洞中新三角形的添加

本文在孔洞中添加新的三角形主要是從孔洞的邊界點(diǎn)和其鄰接的兩條邊界邊的夾角來考慮[4]。

如圖6所示，內(nèi)角θ會(huì)有下面幾種情況：

圖6 孔洞相鄰邊的內(nèi)角Fig.6 Angles of adjacent edges in the holes

對(duì)于孔洞的內(nèi)角按下面的方式處理[5]：

1）如果θ≥180°，將不對(duì)其處理，再尋求下一個(gè)頂點(diǎn)。

2）如果θ≤90°，那么連接θ兩條邊的兩個(gè)端點(diǎn)，生成新的三角形。如圖7所示，新生成的三角形的3條邊的方向根據(jù)STL三角網(wǎng)格模型的規(guī)則，按逆時(shí)針方向排列。為了保持孔洞的完整性，新三角形其中新添加的邊將作為孔洞的一條邊，而另外兩條邊則從孔洞中刪除。

圖7 θ≤90°的處理Fig.7 Processing of angles less than or equal 90°

3） 如果 90°＜θ＜180°，那么計(jì)算由連接 θ兩條邊的兩個(gè)端點(diǎn)生成的新三角形的外心，分別連接外心和θ以及其兩條邊的端點(diǎn)，生成兩個(gè)新的三角形。如圖8所示，同樣按照STL三角網(wǎng)格模型的規(guī)則，新增的兩個(gè)三角形的邊按逆時(shí)針方向排列，其中外心同θ的連線是兩個(gè)新三角形的鄰接邊，它的方向在兩個(gè)三角形中按各自的方形排列。而在保持孔洞的完整性中，將原來的兩條邊刪除，將外心和原來兩條邊的端點(diǎn)所構(gòu)成的邊加入孔洞的邊中。

圖8 90°＜θ＜180°的處理Fig.8 Processing of angles between 90°to 180°

三角形的外心到其各個(gè)頂點(diǎn)的距離相等，如圖9展示了三角形的外心，針對(duì)3D空間，三角形的外心計(jì)算如下：

圖9 三角形的外心Fig.9 Circumcenter of the triangle

設(shè)三角形的 3 個(gè) 頂 點(diǎn) 為 v1（x1，y1，z1），v2（x2，y2，z2），v3（x3，y3，z3），則：

那么外心的坐標(biāo)為：

4 新增頂點(diǎn)的合法性驗(yàn)證

如果新增加的頂點(diǎn)不在孔洞所構(gòu)成的多邊形之內(nèi)，那么構(gòu)成的新三角形將會(huì)和原有的三角形發(fā)生重疊[6]。對(duì)其合法性驗(yàn)證的方法是：如圖10所示，假設(shè)P為新增加的頂點(diǎn)，為孔洞的一條邊，計(jì)算（P-A）×（B-A）的叉積，如果結(jié)果為0，說明 P點(diǎn)和邊共線；如果結(jié)果為正，說明點(diǎn) P在邊的順時(shí)針方向；如果結(jié)果為負(fù)，說明點(diǎn)P在邊的向量在向量的逆時(shí)針方向。按照孔洞邊的排列方向，計(jì)算P點(diǎn)和所有孔洞邊的位置，如果和所有邊界邊的方向相同，則表明P點(diǎn)是合法的，否則其不合法。

圖10 新增點(diǎn)的位置Fig.10 Location of the new point

5 應(yīng)用實(shí)例

在上述算法設(shè)計(jì)和研究的基礎(chǔ)上，作者在Visual Studio.Net 2008集成環(huán)境下，采用C#作為開發(fā)語言，結(jié)合CsGL開發(fā)了一個(gè)原型系統(tǒng)。在此系統(tǒng)中采用交互的方式，人為地挖出仿真孔洞，然后運(yùn)用設(shè)計(jì)的算法對(duì)其進(jìn)行了修補(bǔ)。圖11為一個(gè)足部的三角網(wǎng)格模型的原始圖及孔洞修補(bǔ)后的效果圖的對(duì)比，在原型系統(tǒng)中以面片的形式顯示。圖12對(duì)孔洞區(qū)域放大后原始圖與孔洞修補(bǔ)后效果圖的對(duì)比，以線的形式顯示。

圖11 原始圖及修補(bǔ)效果的對(duì)比Fig.11 Original graphics and comparison of the effect of repair

圖12 孔洞區(qū)域的放大Fig.12 Enlarged the hole area

6 結(jié) 論

作者在認(rèn)真研究和分析眾多學(xué)者的研究成果的基礎(chǔ)之上，提出了一種針對(duì)STL三角網(wǎng)格模型孔洞修補(bǔ)的算法。該算法考慮孔洞區(qū)域的平滑度，并根據(jù)實(shí)際情況增加新的三角片的頂點(diǎn)，因此獲得了被修補(bǔ)區(qū)域三角片形狀較為優(yōu)化的修補(bǔ)結(jié)果。 通過實(shí)踐證明該算法比較穩(wěn)定可靠，能夠滿足實(shí)踐中的需求。

[1]Liu H，Hu Q，Li L，et al.A study of the method of reconstructing the bionic scaffold for repairing defective bone based on tissue engineering[C]//Proceedings of PROLAMAT 2006，IFIP TC5 International Conference，Shanghai，2006（207）：650-657.

[2]袁天然.三角網(wǎng)格模型光順、簡化和縫補(bǔ)技術(shù)的研究及應(yīng)用[D].南京:南京航空航天大學(xué)，2007.

[3]Botsch M，Pauly M，Rossl C，et al.Geometric modeling based on triangle meshes[R].New York：ACM，2006.

[4]ZHAO Wei，GAO Shu-ming，LIN Hong-wei.A robust holefilling algorithm for triangular mesh[J].Visual Computer，2007，23（2）:987-997.

[5]杜佶，張麗艷，王宏濤，等.基于徑向基函數(shù)的三角網(wǎng)格曲面孔洞修補(bǔ)算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2005，17（9）:1976-1982.DU Jie，ZHANG Li-yan，WANG Hong-tao，et al.Hole repairing in triangulai meshes based on radial basis function[J].Journal of Compuyer-aided&Computer Graphics，2005，17（9）:1976-1982.

[6]成欣，周明全，耿國華，等.空間三角網(wǎng)格曲面的補(bǔ)洞方法[J].計(jì)算機(jī)應(yīng)用研究，2006，23（6）:158-160.CHENG Xin，ZHOU Ming-quan，GENG Guo-hua，et al.Holefilling method for reconstruction of trianglar mesh[J].Application Research of Computer，2006，23（6）:158-160.