基于哈希表的STL文件拓撲關系快速重建算法

錢　乘，李　震，江本赤，王　剛

（安徽工程大學 機械與汽車工程學院，安徽 蕪湖 241000）

STL（surface tesselation language）文件格式是美國3D SYSTEMS公司于1988年制定的一個接口協議［1］。STL文件由逼近三維模型表面的多個三角形面片構成，但它已經丟失了原有的拓撲關系，且所記錄的每個三角形頂點都至少被記錄4次，平均被記錄6次，造成了數據大量冗余。STL文件三角形間無拓撲關系且存在數據極大冗余，造成后續切片處理效率低，模型整體打印時間長。因此，構建合理的數據結構去除冗余數據，根據數據結構建立拓撲結構極其重要。

目前，研究人員已提出了多種STL文件拓撲關系的重建算法。張應中等［2］構造半邊編碼的三角網格拓撲數據結構實現拓撲重構，但構造該數據結構時程序復雜且拓撲重建運算效率較低；侯聰聰等［3］構造鏈表數據結構重建拓撲關系，但在去除冗余數據時，遍歷整體鏈表會降低算法效率；陳萍等［4］利用三角形間半邊拓撲結構遍歷所構建的紅黑樹實現拓撲重構，但建樹與檢測平衡性在一定程度上降低了算法效率；楊晟院等［1］構建平衡二叉樹的數據結構進行頂點聚合去除冗余數據，采用虛平衡二叉樹進行快速鄰邊搜索實現拓撲重建，但當數據量較大時，建樹與調整平衡需要花費時間，會降低算法效率；王增波［5］及王彥云等［6］構建哈希表實現冗余數據的去除以及快速的拓撲重建，但忽略了不同坐標可能存在相同關鍵字的情況，造成冗余數據去除與拓撲關系重建錯誤?！?br>