STL文件錯誤的快速修復(fù)-精選資料

1、STL文件錯誤的快速修復(fù)Fast repairing errors in STL filesHE Qiang ZHANG Shu-sheng BAI Xiao-liang( Key Laboratory of Contemporary Design & Integrated Manufacturing Technology for Ministry of Education Northwestern Polytechnical University Xi'an 710072China):The main problem of STL files is their various

2、 errors.In order to repair them this paper firstly classified the errors according to their characteristics then modeled the files by half edge data structure. Employed detecting edges as the basis for STL files errors detection. Proposed a basic fill process step-by-step ordered by importing STL un

3、structured mesh popular mesh errors detection errors filling update errors information. The algorithm performs fast by using balanced binary trees. The experimental result demonstrates the effectiveness of this proposed algorithm. This method can be applied to rapid form and reverse engineering fiel

4、d as a pre-process module.0 引言 快速原型制造技術(shù)是采用基于離散 / 堆積的方式快速制造零件原型的工藝方法，能直接從CAD實體數(shù)據(jù)模型生成三維產(chǎn)品模 型。STL文件則為CAD系統(tǒng)與快速原型系統(tǒng)之間數(shù)據(jù)交換格式的 事實上的標(biāo)準(zhǔn)。 逆向工程是從實物樣件獲取產(chǎn)品數(shù)字化模型的技 術(shù)，測量的實體模型可以 STL數(shù)據(jù)文件方式導(dǎo)出以進行再設(shè)計， 如先進的光學(xué)測量系統(tǒng) Atos就可以導(dǎo)出測量模型的 STL數(shù)據(jù)文 件。由于系統(tǒng)間容錯、 轉(zhuǎn)換方法和逆向測量過程的不完美等原因 STL文件中存在大量的錯誤，由 STL重構(gòu)的實體有很多錯誤。修 復(fù)這些錯誤對后續(xù)處理具有重要意義。要檢測和修復(fù)這

5、些缺陷， 拓?fù)潢P(guān)系重建是必需的。本文首先分析了 STL文件中常見的幾種 錯誤，然后采用半邊數(shù)據(jù)結(jié)構(gòu)進行快速的拓?fù)渲亟ǎ?深入分析錯 誤特點的基礎(chǔ)上，系統(tǒng)高效地實現(xiàn)了STL文件錯誤的修復(fù)。1 STL 文件常見錯誤分析根據(jù)STL文件錯誤的特點，可大致將錯誤分成以下幾類：a) 孔洞，如圖1(a)所示。主要是CAD實體表面三角化時缺 少足量的數(shù)據(jù)造成的。b) 頂點錯位，如圖1(b)所示。三角形的邊沒有被兩個三角 形共享，也沒有出現(xiàn)裂縫。c) 法向量錯誤，如圖 1(c) 所示。三角片的旋向有錯誤，即 違反了 STL文件的取向規(guī)則，產(chǎn)生的原因主要是生成 STL文件時 頂點記錄順序混亂。d) 多余，如圖1(

6、d)所示。正常的網(wǎng)格拓?fù)浣Y(jié)構(gòu)的基礎(chǔ)上多 出了一些獨立的面片。2 STL 實體的快速拓?fù)渲亟ㄒ迯?fù)STL文件中的錯誤必須借助拓?fù)潢P(guān)系。拓?fù)潢P(guān)系不僅用于修復(fù)缺陷，也用于后續(xù)處理。例如逆向工程中的區(qū)域分割、 曲面擬合等。 本文采用半邊數(shù)據(jù)結(jié)構(gòu)表示實體的拓?fù)潢P(guān)系。 在數(shù) 據(jù)結(jié)構(gòu)中有五類節(jié)點：網(wǎng)格 (CPolyMesh) 、三角形 (triangle) 、 邊(edge)、半邊(halfedge)、頂點(vertex)。所有的節(jié)點都各自 組成一個雙向鏈表。實體拓?fù)潢P(guān)系建立之后，可以直接實現(xiàn)： a) 由一個 CPolyMesh可以遍歷它包含的所有 triangles ； b)由一個 triangle 可以

7、找到構(gòu)成它的三條 halfedge ； c) 由一個 triangle 可以找到前后的鄰接三角形；d)由一個vertex關(guān)聯(lián)其生成的半 邊，且一條 edge 由兩條半邊構(gòu)成，屬于一條邊的兩條半邊之間 可以相互查找。 當(dāng)實體模型存在缺陷時， 會出現(xiàn)只有一條半邊的 邊。拓?fù)渲亟ㄖ饕▋蓚€步驟： 無結(jié)構(gòu)三角網(wǎng)格的建立和流形 網(wǎng)格的生成。2.1 無結(jié)構(gòu)三角網(wǎng)格的建立導(dǎo)入STL數(shù)據(jù)文件，由每個頂點生成一條半邊，同一三角 形的三個頂點生成的三條半邊構(gòu)成一個 triangle ，將 triangle 加入到CPolyMesh鏈表中。同時建立關(guān)聯(lián)頂點和其生成的半邊集 合的二叉平衡樹。二叉平衡樹能自動將原本為

8、一個頂點，但在 STL文件中卻多次出現(xiàn)的頂點合并成一個頂點，這樣才能正確地 建立實體的拓?fù)潢P(guān)系。 導(dǎo)入文件結(jié)束后， 生成的三角形相互間沒 有鄰接關(guān)系，故稱之為無結(jié)構(gòu)網(wǎng)格。2.2 流行網(wǎng)格的生成通過上述步驟， 每個頂點都生成了一條或多條半邊， 每個頂 點屬于一個或多個三角形， 但三角形之間沒有鄰接關(guān)系。 本文通 過半邊匹配的方式完成三角形鄰接關(guān)系的建立。 半邊匹配是查找 與當(dāng)前半邊的兩個端點都相同的另一條半邊， 找到后將這兩條半 邊生成一條邊。 由 2.1 節(jié)建立的二叉平衡樹可得到每個頂點的半 邊集合， 因此查找對應(yīng)半邊時只需從半邊集合中尋找， 大大縮小 了查找范圍。圖2為半邊匹配簡圖。其中：F

9、1為已輸入的三角 形；Fn為當(dāng)前讀入的三角形。顯然 H6將與H1匹配，從頂點V1 的半邊表中可以直接找到 H1。3 錯誤修復(fù) 考慮到不同錯誤的特點及修復(fù)方法，基本的修復(fù)步驟為：a）遍歷網(wǎng)格 （CPolyMesh） 中所有 triangles, 找出每個 triangle 的三條半邊中匹配的半邊為空的半邊，由這樣的半邊集合建立一個新的鏈表 VS如果VS為空，基本可以認(rèn)為這個實 體模型沒有缺陷，程序結(jié)束。b）由VS中的半邊建立半邊與頂點關(guān)聯(lián)的集合vsn（半邊是指向頂點的 ） 、 vs_out（ 半邊是背向頂點的 ） 。在 vs_in 中取出一 個頂點和其關(guān)聯(lián)的半邊集合，利用該頂點獲得 vs_out

10、 中該頂點 的半邊集合。在這兩個半邊集合中，尋找每對方向相反的半邊。 若存在這樣的半邊對， 則該錯誤屬于頂點錯位的情況， 將半邊對 存入集合vs_repair中，轉(zhuǎn)c）；若找不到這樣的半邊對， 轉(zhuǎn)e）。c) 對 vs_repair 中的每對錯誤半邊，計算半邊邊長，在長半邊所在的三角形中新生成一個與短半邊匹配的三角形。 同時 刪除集合 VS、 vs_in 和 vs_out 中已經(jīng)消除錯誤的半邊和頂點， 加入新增加錯誤半邊和頂點，稱之為錯誤更新。如圖 3 所示，虛 線表示新生成三角形的邊。修復(fù)完成后，清空 vs_repair 。d) 重復(fù)執(zhí)行b),直至集合vs_repair中半邊對數(shù)量為零，轉(zhuǎn) e

11、) 。e) 從 VS 中取出一條半邊， 進行孔洞檢測算法。 若存在孔洞，轉(zhuǎn)步驟f)，并刪除屬于VS中的所有孔洞半邊；否則轉(zhuǎn) g)。 孔洞檢測算法如下：(a) 首先從VS中取出一條半邊 e，檢測出CPolyMesh總與之 相鄰的一條沒有匹配的半邊，并將其標(biāo)記。(b) 根據(jù)半邊匹配關(guān)系，檢測出與前一步驟找出的不匹配半 邊相鄰的另一條孔洞的半邊，將其標(biāo)記。(c) 重復(fù)步驟(b)直到檢測的半邊為e時停止。單個孔洞就是 由這些首尾相連的半邊集合構(gòu)成的。(d) 重復(fù)(a)(c)就可以檢測出所有的孔洞，注意重復(fù)步驟(a) 時，CPolyMesh中的半邊必須是沒有標(biāo)記的，這樣才能保證孔洞 的不重復(fù)檢測。f)

12、對每個檢測到的孔洞， 獲取孔洞的每個頂點， 計算頂點的 法矢量，再采用 Marching Cubes算法對每個孔洞進行三？腔？?？锥错旤c法矢量的計算如下：三角網(wǎng)格模型上孔洞任意頂點 vi 的法矢量可以根據(jù)過該點 的三角形法矢量的加權(quán)平均來計算，一般取三角形的面積為權(quán) 值。過vi點有n個三角形，分別記為Tj ,三角形的法矢記為Nj, 面積記為 Aj ，則三角網(wǎng)格中點 vi 的法矢量為ni=刀 nj=1AjNj/ 刀 nj=1Ajg) 若VS中半邊數(shù)量不再減少且不為空，這是由于有少量的 非典型錯誤，程序很難判斷，可由用戶進行人工交互修復(fù)。采用 本文算法開發(fā)的軟件系統(tǒng)提供了一些輔助功能，如鼠標(biāo)拾取邊、 三角形、頂點、刪除邊、三角形、向?qū)嶓w中添加邊、三角形等。h) 整個修復(fù)過程結(jié)束，由修復(fù)后的實體模型生成正確的STL文件。4 修復(fù)實驗為了驗證本算法的有效性和實