ＳＴＬ文件錯誤的快速修復
2009-01-01 00:00:00賀強張樹生白曉亮
計算機應用研究 2009年5期
(西北工業大學 現代集成制造教育部重點實驗室 西安 710072)
摘 要：為了修復使用的STL文件中的一些錯誤，首先根據錯誤的特點進行分類，然后利用半邊數據結構快速建立STL文件的實體模型。以邊的檢測作為STL文件錯誤檢測的基礎，建立了導入STL文件、無結構網格、流行網格、錯誤檢測、錯誤修復、更新錯誤信息等基本修復步驟。二叉平衡樹的使用加快了算法的遍歷速度。實例驗證了該算法的有效性。該方法可作為預處理模塊運用于快速成型和逆向工程等領域。
關鍵詞：無結構網格； 流行網格； 錯誤修復
中圖分類號：TP391文獻標志碼：A
文章編號：1001-3695(2009)05-1983-02
Fast repairing errors in STL files
HE Qiang ZHANG Shu-sheng BAI Xiao-liang
( Key Laboratory of Contemporary Design Integrated Manufacturing Technology for Ministry of Education Northwestern Polytechnical University Xi’an 710072 China)
Abstract:The main problem of STL files is their various 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 unstructured 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 field as a pre-process module.
Key words：unstructured mesh; popular mesh; errors repairing
0 引言
快速原型制造技術是采用基于離散/堆積的方式快速制造零件原型的工藝方法，能直接從CAD實體數據模型生成三維產品模型。STL文件則為CAD系統與快速原型系統之間數據交換格式的事實上的標準。逆向工程是從實物樣件獲取產品數字化模型的技術，測量的實體模型可以STL數據文件方式導出以進行再設計，如先進的光學測量系統Atos就可以導出測量模型的STL數據文件。由于系統間容錯、轉換方法和逆向測量過程的不完美等原因 STL文件中存在大量的錯誤，由STL重構的實體有很多錯誤。修復這些錯誤對后續處理具有重要意義。要檢測和修復這些缺陷，拓撲關系重建是必需的。本文首先分析了STL文件中常見的幾種錯誤，然后采用半邊數據結構進行快速的拓撲重建，深入分析錯誤特點的基礎上，系統高效地實現了STL文件錯誤的修復。
1 STL文件常見錯誤分析
根據STL文件錯誤的特點，可大致將錯誤分成以下幾類：
a)孔洞，如圖1(a)所示。主要是CAD實體表面三角化時缺少足量的數據造成的。
b)頂點錯位，如圖1(b)所示。三角形的邊沒有被兩個三角形共享，也沒有出現裂縫。
c)法向量錯誤，如圖1(c)所示。三角片的旋向有錯誤，即違反了STL文件的取向規則，產生的原因主要是生成STL文件時頂點記錄順序混亂。
d)多余，如圖1(d)所示。正常的網格拓撲結構的基礎上多出了一些獨立的面片。
2 STL實體的快速拓撲重建
要修復STL文件中的錯誤必須借助拓撲關系。拓撲關系不僅用于修復缺陷，也用于后續處理。例如逆向工程中的區域分割、曲面擬合等。本文采用半邊數據結構表示實體的拓撲關系。在數據結構中有五類節點：網格(CPolyMesh)、三角形(triangle)、邊(edge)、半邊(halfedge)、頂點(vertex)。所有的節點都各自組成一個雙向鏈表。實體拓撲關系建立之后，可以直接實現：a)由一個CPolyMesh可以遍歷它包含的所有triangles；b)由一個triangle可以找到構成它的三條halfedge；c)由一個triangle可以找到前后的鄰接三角形；d)由一個vertex關聯其生成的半邊，且一條edge由兩條半邊構成，屬于一條邊的兩條半邊之間可以相互查找。當實體模型存在缺陷時，會出現只有一條半邊的邊。拓撲重建主要包括兩個步驟：無結構三角網格的建立和流形網格的生成。
2.1 無結構三角網格的建立
導入STL數據文件，由每個頂點生成一條半邊，同一三角形的三個頂點生成的三條半邊構成一個triangle，將triangle加入到CPolyMesh鏈表中。同時建立關聯頂點和其生成的半邊集合的二叉平衡樹。二叉平衡樹能自動將原本為一個頂點，但在STL文件中卻多次出現的頂點合并成一個頂點，這樣才能正確地建立實體的拓撲關系。導入文件結束后，生成的三角形相互間沒有鄰接關系，故稱之為無結構網格。
2.2 流行網格的生成
通過上述步驟，每個頂點都生成了一條或多條半邊，每個頂點屬于一個或多個三角形，但三角形之間沒有鄰接關系。本文通過半邊匹配的方式完成三角形鄰接關系的建立。半邊匹配是查找與當前半邊的兩個端點都相同的另一條半邊，找到后將這兩條半邊生成一條邊。由2.1節建立的二叉平衡樹可得到每個頂點的半邊集合，因此查找對應半邊時只需從半邊集合中尋找，大大縮小了查找范圍。圖2為半邊匹配簡圖。其中：F1為已輸入的三角形；Fn為當前讀入的三角形。顯然H6將與H1匹配，從頂點V1的半邊表中可以直接找到H1。
3 錯誤修復
考慮到不同錯誤的特點及修復方法，基本的修復步驟為：
a)遍歷網格(CPolyMesh)中所有triangles，找出每個triangle的三條半邊中匹配的半邊為空的半邊，由這樣的半邊集合建立一個新的鏈表VS。如果VS為空，基本可以認為這個實體模型沒有缺陷，程序結束。
b)由VS中的半邊建立半邊與頂點關聯的集合vs_in(半邊是指向頂點的)、vs_out(半邊是背向頂點的)。在vs_in中取出一個頂點和其關聯的半邊集合，利用該頂點獲得vs_out中該頂點的半邊集合。在這兩個半邊集合中，尋找每對方向相反的半邊。若存在這樣的半邊對，則該錯誤屬于頂點錯位的情況，將半邊對存入集合vs_repair中，轉c）；若找不到這樣的半邊對，轉e)。
c)對vs_repair中的每對錯誤半邊，計算半邊邊長，在長半邊所在的三角形中新生成一個與短半邊匹配的三角形。同時刪除集合VS、vs_in和vs_out中已經消除錯誤的半邊和頂點，加入新增加錯誤半邊和頂點，稱之為錯誤更新。如圖3所示，虛線表示新生成三角形的邊。修復完成后，清空vs_repair。
d)重復執行b），直至集合vs_repair中半邊對數量為零，轉e)。
e)從VS中取出一條半邊，進行孔洞檢測算法。若存在孔洞，轉步驟f)，并刪除屬于VS中的所有孔洞半邊；否則轉g)。
孔洞檢測算法如下：
(a)首先從VS中取出一條半邊e，檢測出CPolyMesh總與之相鄰的一條沒有匹配的半邊，并將其標記。
(b)根據半邊匹配關系，檢測出與前一步驟找出的不匹配半邊相鄰的另一條孔洞的半邊，將其標記。
(c)重復步驟(b)直到檢測的半邊為e時停止。單個孔洞就是由這些首尾相連的半邊集合構成的。
(d)重復(a)~(c)就可以檢測出所有的孔洞，注意重復步驟(a)時，CPolyMesh中的半邊必須是沒有標記的，這樣才能保證孔洞的不重復檢測。
f)對每個檢測到的孔洞，獲取孔洞的每個頂點，計算頂點的法矢量，再采用Marching Cubes算法對每個孔洞進行三角化。
孔洞頂點法矢量的計算如下：
三角網格模型上孔洞任意頂點vi的法矢量可以根據過該點的三角形法矢量的加權平均來計算，一般取三角形的面積為權值。過vi點有n個三角形，分別記為Tj，三角形的法矢記為Nj，面積記為Aj，則三角網格中點vi的法矢量為
ni=∑nj=1AjNj/∑nj=1Aj
g)若VS中半邊數量不再減少且不為空，這是由于有少量的非典型錯誤，程序很難判斷，可由用戶進行人工交互修復。采用本文算法開發的軟件系統提供了一些輔助功能，如鼠標拾取邊、三角形、頂點、刪除邊、三角形、向實體中添加邊、三角形等。
h)整個修復過程結束，由修復后的實體模型生成正確的STL文件。
4 修復實驗
為了驗證本算法的有效性和實用性，在VS2005平臺上實現了汽車外形STL文件的快速實體模型重建和錯誤修復。實驗結果如圖4所示。其中(a)為通過本算法快速建立的實體模型；(b)為局部頂點錯位的實體模型；(c)為采用本算法修復結果；(d)為局部孔洞；(e)為局部孔洞修復結果。
5 結束語
本文分析了STL文件的常見錯誤，利用半邊數據結構完成了STL文件的快速實體模型重建，并在此基礎.
