1、STL文件錯誤的快速修復FastrepairingerrorsinSTLfilesHEQiangZHANGShu-shengBAIXiao-liang(KeyLaboratoryofContemporaryDesign&IntegratedManufacturingTechnologyforMinistryofEducationNorthwesternPolytechnicalUniversityXi'an710072China):ThemainproblemofSTLfilesistheirvariouserrors.Inordertorepairthemthispaperf

2、irstlyclassifiedtheerrorsaccordingtotheircharacteristicsthenmodeledthefilesbyhalfedgedatastructure.EmployeddetectingedgesasthebasisforSTLfileserrorsdetection.Proposedabasicfillprocessstep-by-steporderedbyimportingSTLunstructuredmeshpopularmesherrorsdetectionerrorsfillingupdateerrorsinformation.Theal

3、gorithmperformsfastbyusingbalancedbinarytrees.Theexperimentalresultdemonstratestheeffectivenessofthisproposedalgorithm.Thismethodcanbeappliedtorapidformandreverseengineeringfieldasapre-processmodule.0引言快速原型制造技術是采用基于離散/堆積的方式快速制造零件原型的工藝方法,能直接從CAC®體數據模型生成三維產品模型.STL文件那么為CAD系統與快速原型系統之間數據交換格式的事實上的標準.

4、逆向工程是從實物樣件獲取產品數字化模型的技術,測量的實體模型可以STL數據文件方式導出以進行再設計,如先進的光學測量系統Atos就可以導出測量模型的STL數據文件.由于系統間容錯、轉換方法和逆向測量過程的不完美等原因STL文件中存在大量的錯誤,由STL重構的實體有很多錯誤.修復這些錯誤對后續處理具有重要意義.要檢測和修復這些缺陷,拓撲關系重建是必需的.本文首先分析了STL文件中常見的幾種錯誤,然后采用半邊數據結構進行快速的拓撲重建,深入分析錯誤特點的根底上,系統高效地實現了STL文件錯誤的修復.1 STL文件常見錯誤分析根據STL文件錯誤的特點,可大致將錯誤分成以下幾類：a)孔洞,如圖1(a)

5、所示.主要是CA喳體外表三角化時缺少足量的數據造成的.b)頂點錯位,如圖1(b)所示.三角形的邊沒有被兩個三角形共享,也沒有出現裂縫.c)法向量錯誤,如圖1(c)所示.三角片的旋向有錯誤,即違反了STL文件的取向規那么,產生的原因主要是生成STL文件時頂點記錄順序混亂.d)多余,如圖1(d)所示.正常的網格拓撲結構的根底上多出了一些獨立的面片2 STL實體的快速拓撲重建拓撲關系不僅要修復STL文件中的錯誤必須借助拓撲關系用于修復缺陷,也用于后續處理.例如逆向工程中的區域分割、曲面擬合等.本文采用半邊數據結構表示實體的拓撲關系.在數據結構中有五類節點：網格(CPolyMesh)、三角形(tria

6、ngle)、邊(edge)、半邊(halfedge)、頂點(vertex).所有的節點都各自組成一個雙向鏈表.實體拓撲關系建立之后,可以直接實現：a)由一個CPolyMesh可以遍歷它包含的所有triangles;b)由一個triangle可以找到構成它的三條halfedge；c)由一個triangle可以找到前后的鄰接三角形；d)由一個vertex關聯其生成的半邊,且一條edge由兩條半邊構成,屬于一條邊的兩條半邊之間可以相互查找.當實體模型存在缺陷時,會出現只有一條半邊的邊.拓撲重建主要包括兩個步驟：無結構三角網格的建立和流形網格的生成.2.1 無結構三角網格的建立導入STL數據文件,由每

7、個頂點生成一條半邊,同一三角形的三個頂點生成的三條半邊構成一個triangle,將triangle參加到CPolyMesh鏈表中.同時建立關聯頂點和其生成的半邊集合的二叉平衡樹.二叉平衡樹能自動將原本為一個頂點,但在STL文件中卻屢次出現的頂點合并成一個頂點,這樣才能正確地建立實體的拓撲關系.導入文件結束后,生成的三角形相互間沒有鄰接關系,故稱之為無結構網格.2.2 流行網格的生成通過上述步驟,每個頂點都生成了一條或多條半邊,每個頂點屬于一個或多個三角形,但三角形之間沒有鄰接關系.本文通過半邊匹配的方式完成三角形鄰接關系的建立.半邊匹配是查找與當前半邊的兩個端點都相同的另一條半邊,找到后將這兩

8、條半邊生成一條邊.由2.1節建立的二叉平衡樹可得到每個頂點的半邊集合,因此查找對應半邊時只需從半邊集合中尋找,大大縮小了查找范圍.圖2為半邊匹配簡圖.其中：F1為已輸入的三角形；Fn為當前讀入的三角形.顯然H6將與H1匹配,從頂點V1的半邊表中可以直接找到H1.3錯誤修復考慮到不同錯誤的特點及修復方法,根本的修復步驟為：a遍歷網格CPolyMesh中所有triangles,找出每個triangle的三條半邊中匹配的半邊為空的半邊,由這樣的半邊集合建立一個新的鏈表VSo如果VS為空,根本可以認為這個實體模型沒有缺陷,程序結束.b由VS中的半邊建立半邊與頂點關聯的集合vs_in半邊是指向頂點的、v

9、s_out半邊是背向頂點的.在vs_in中取出一個頂點和其關聯的半邊集合,利用該頂點獲得vs_out中該頂點的半邊集合.在這兩個半邊集合中,尋找每對方向相反的半邊.假設存在這樣的半邊對,那么該錯誤屬于頂點錯位的情況,將半邊對存入集合vs_repair中,轉c；假設找不到這樣的半邊對,轉ec)對vs_repair中的每對錯誤半邊,計算半邊邊長,在長半邊所在的三角形中新生成一個與短半邊匹配的三角形.同時刪除集合VSvs_in和vs_out中已經消除錯誤的半邊和頂點,參加新增加錯誤半邊和頂點,稱之為錯誤更新.如圖3所示,虛線表示新生成三角形的邊.修復完成后,清空vs_repair.d)重復執行b),

10、直至集合vs_repair中半邊對數量為零,轉e).e)從VS中取出一條半邊,進行孔洞檢測算法.假設存在孔洞,轉步驟f),并刪除屬于VS中的所有孔洞半邊；否那么轉g)o孔洞檢測算法如下：(a)首先從VS中取出一條半邊e,檢測出CPolyMesh總與之相鄰的一條沒有匹配的半邊,并將其標記.(b)根據半邊匹配關系,檢測出與前一步驟找出的不匹配半邊相鄰的另一條孔洞的半邊,將其標記.(c)重復步驟(b)直到檢測的半邊為e時停止.單個孔洞就是由這些首尾相連的半邊集合構成的.(d)重復(a)(c)就可以檢測出所有的孔洞,注意重復步驟(a)時,CPolyMesh中的半邊必須是沒有標記的,這樣才能保證孔洞的不

11、重復檢測.f)對每個檢測到的孔洞,獲取孔洞的每個頂點,計算頂點的法矢量,再采用MarchingCubes算法對每個孔洞進行三？腔？.孔洞頂點法矢量的計算如下：三角網格模型上孔洞任意頂點vi的法矢量可以根據過該點的三角形法矢量的加權平均來計算,一般取三角形的面積為權值.過vi點有n個三角形,分別記為Tj,三角形的法矢記為Nj,面積記為Aj,那么三角網格中點vi的法矢量為ni=Enj=1AjNj/Enj=1Ajg假設VS中半邊數量不再減少且不為空,這是由于有少量的非典型錯誤,程序很難判斷,可由用戶進行人工交互修復.采用本文算法開發的軟件系統提供了一些輔助功能,如鼠標拾取邊、三角形、頂點、刪除邊、三角形、向實體中添加邊、三角形等.h整個修復過程結束,由修復后的實體模型生成正確的STL文件.4修復實驗為了