基于哈希表的3D打印模型冗余頂點優化

黃韞青，王磊磊，許明澤，侯沛正，嚴海峰

(河北工程大學機械與裝備工程學院，河北 邯鄲 056038)

0 引言

隨著科技的快速發展，3D打印技術已經成為推動我國制造業高質量發展的一股重要力量。在3D打印過程中，一般由設備掃描、計算機建模等方式獲取三維模型文件，后續再轉換為供切片軟件計算和處理的數據。作為切片分層的預處理環節，模型的讀取和數據的優化必不可少[1-2]。STL 文件是由三角面片離散地對三維模型近似表示，在存儲過程中每個三角形頂點都被多次紀錄，造成了數據大量冗余，不利于后期處理。因此，為了解決STL文件多余存儲的問題，需要設計一種合理的冗余數據去除方案，提高后續處理效率，節省內存空間。考慮到哈希表結構簡單且時間復雜度低，本文提出了一種基于哈希表的數據優化方案，實現對元素高效率的搜索和刪除。該方案首先對STL文件信息進行分析，接著采用除留余數法與鏈地址法相結合建立哈希表，剔除冗余的頂點數據。

1 STL文件

1.1 STL文件格式

STL(surface tesselation language)文件格式是由美國3D SYSTEMS公司開發的接口協議，常被用于服務快速成型制造[3]，由于它具有存儲形式結構簡單、普適性好的優點，市面上大多數的建模軟件都可以導出STL文件。在經過多年的改進與發展后，STL文件格式已經成為3D打印的標準模型格式被普遍接受，由于STL標準文件格式的生成與建模方式無關，所以它在數控加工、逆向工程、文物保護、醫學成像和有限元分析等領域都廣泛適用[4]。

STL文件格式有二進制和ASCII 2種存儲格式，本文選用ASCII格式的STL文件用于研究。ASCII格式的STL文件(見表1)逐行給出面片的幾何信息，首先會以關鍵字solid開頭，之后依次對各三角面片信息進行記錄，在文件信息全部定義結束后以關鍵字endsolid結尾。每個三角面片信息都有7行數據，第1行數據的關鍵字facet normal后給出該三角面片法向量的3個分量，且規定法向量朝向三維模型外側。關鍵字outerloop和endloop之間用三行數據來對此法向量所對應的三角面片頂點坐標進行表示，并規定頂點的排列順序為法向量方向上的逆時針。

表1 ASCII文件格式

1.2 STL冗余數據

在ASCII格式的STL文件中，鄰近三角面片存在共用頂點的情況，這容易導致頂點的多次存儲，造成數據冗余。大量冗余數據的產生不僅占用內存空間，也不利于后續的計算處理。因此，在不影響成型質量和精度的基礎上，剔除冗余數據，能夠減少計算時間，提高打印的效率。

由于三維實體模型是由無數個三角面片封閉圍成的，模型的各頂點同屬于多個三角面片，由歐拉公式可得：

F+V-E=2

(1)

其中：F，E，V分別是面片數，邊數和實際頂點數。

實際上STL模型每個三角面片都有3個頂點，因此，STL模型中的頂點數V′=3F。又由于每2個三角面片都公用1條邊，其邊數與面片數的關系為：

E=3F/2

(2)

式(1)和式(2)可得：

V=0.5F+2≈0.5F

(3)

通過對比V′和V可知，在STL文件中紀錄的頂點數大概有實際頂點數的6倍之多，這造成內存的大量浪費。實際上，每個STL文件都保存有海量的數據信息，如果對所有數據都進行提取，會產生多余數據，不利于開展后期處理和計算的工作。所以為了提高處理效率，縮短打印時間，需要采取合理有效的方法來剔除冗余的頂點數據。

2 數據導入

在目前3D打印技術中，由于ASCII格式的數據結構清晰直觀，解讀和修改相對容易，因此，該存儲格式在現行的數據處理中最為常見，本課題也選用ASCII文件格式進行算法研究。

ASCII格式的STL文件結構能通過特定關鍵詞來識別，又由于其是按行存儲，每行都有指定的關鍵字引導，因此能夠通過逐行讀取數據的方式來定義文件。導入模型數據后，具體的讀取方法如下。

1)打開STL模型文件。

2)判斷是否為正確的.STL文件。若是，讀取文件信息；若否，結束讀取。

3)讀取數據，根據文件起始關鍵字是否為Solid判斷文件格式，若是，繼續讀取并進行后續處理；若否，判斷為二進制格式，結束讀取。

4)從第一個三角面片開始，遍歷文件中所有的三角面片，提取法向量和坐標的信息，并進行紀錄存儲。

5)判斷STL文件所有信息是否全部讀取，若是，讀取結束；若否，跳轉至步驟3。

3 哈希去冗

3.1 構建哈希函數

哈希表(Hash table)作為一種特殊數據結構，具有高效查找的功能。它對于元素的快速插入與搜索，是通過哈希函數來實現。本文濾除STL文件冗余節點依據的是三角面片的頂點坐標，即哈希表所用元素的關鍵字為坐標頂點的值，計算得到的頂點坐標索引值存儲在構建的哈希表中。

在利用哈希表去冗時，將逐一訪問STL模型中每個面片的頂點值，通過哈希函數來計算其所對應的哈希值。當該哈希值在表中的位置為空，則將頂點信息存入所建立的面表，點表以及哈希表之中。面表中每個面的數據結構都同時存儲了面片索引值，面片3個頂點的索引值以及各邊相鄰連接的面片索引[5]。點表中每個點的數據結構則同時存儲了點坐標索引值以及點坐標與所屬面片的索引值。

常見的哈希函數構造方法有直接定址法、數字分析法、平方取中法、分段折疊法以及除留余數法[6]。其中除留余數法是使用最普遍的一種哈希函數構造方法，這種方法會取關鍵字為除數，被除數為一個不大于哈希表長m的最大素數p，將計算結果的余數作為最后的哈希地址。該方法的構造方式如下。

假定(x，y，z)為面片的頂點坐標，可得其關鍵字為：

k=|intx|+|inty|+|intz|

(4)

則所構建的哈希函數為：

H(k)=kmodp

(5)

其中：p為小于m的最大素數，m為頂點數的1/6，mod為取模運算[7]。

3.2 哈希沖突

在運用除留余數法計算哈希值的過程中會出現哈希地址已被占用的問題，即不同的關鍵字和，映射到了同一哈希地址，這種現象就是哈希沖突。哈希沖突會影響去冗的效率，產生數據的堆積。而在實際應用中該沖突是不可避免的，但可以設法減少該現象的發生頻率。

在發生哈希沖突時，從點表中取出該哈希值所在位置的各個索引值所對應的頂點，將其與即將存入的頂點比較，若頂點重復，執行冗余去除不必重復存入。若頂點不同，就為該頂點分配點索引值，并將索引值記錄，最后在點表中存入該頂點元素信息。通過這種方法既完成了頂點的存儲，同時也保證了點表中不存在重復頂點。哈希去冗流程如圖 1 所示。

圖1 哈希去冗流程圖

對于哈希沖突常見的處理方法有開放定址法、鏈地址法、再哈希法、建立公共溢出區。因鏈地址法操作簡單，使用方便。尤其在執行刪除時，只需要簡單地刪去對應節點就能實現操作。因此本文將采用鏈地址法處理哈希沖突。鏈地址法處理沖突時的哈希表如圖2所示。

圖2 鏈地址法處理沖突時的哈希表

4 測試實驗及分析

為了驗證算法的可行性，在完成理論分析后，利用Visual Studio 2019實現模型數據讀取和頂點數據去冗。選取多個不同面片數的STL模型文件來進行實驗，實驗結果如表2所示。

表2 實驗結果

在對實驗前后頂點數據進行分析后，得出所構建的哈希表可以實現16.7%的頂點去冗，能夠達到理想的實驗結果。

5 結語

在對STL文件存儲格式和數據冗余情況進行分析后，采用除留余數法構建哈希函數，利用鏈地址法減少哈希沖突的發生。實驗證明，采用上述方法，能夠實現理想的去冗效果，為后續的切片處理提供了方便，能夠縮短模型的打印時間，提高整體的打印效率。