基于哈希表的3D打印模型冗余頂點優(yōu)化

黃韞青，王磊磊，許明澤，侯沛正，嚴(yán)海峰

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

0 引言

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

1 STL文件

1.1 STL文件格式

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

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

表1 ASCII文件格式

1.2 STL冗余數(shù)據(jù)

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

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

F+V-E=2

(1)

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

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

E=3F/2

(2)

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

V=0.5F+2≈0.5F

(3)

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

2 數(shù)據(jù)導(dǎo)入

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

ASCII格式的STL文件結(jié)構(gòu)能通過特定關(guān)鍵詞來識別，又由于其是按行存儲，每行都有指定的關(guān)鍵字引導(dǎo)，因此能夠通過逐行讀取數(shù)據(jù)的方式來定義文件。導(dǎo)入模型數(shù)據(jù)后，具體的讀取方法如下。

1)打開STL模型文件。

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

3)讀取數(shù)據(jù)，根據(jù)文件起始關(guān)鍵字是否為Solid判斷文件格式，若是，繼續(xù)讀取并進(jìn)行后續(xù)處理；若否，判斷為二進(jìn)制格式，結(jié)束讀取。

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

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

3 哈希去冗

3.1 構(gòu)建哈希函數(shù)

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

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

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

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

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

(4)

則所構(gòu)建的哈希函數(shù)為：

H(k)=kmodp

(5)

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

3.2 哈希沖突

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

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

圖1 哈希去冗流程圖

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

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

4 測試實驗及分析

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

表2 實驗結(jié)果

在對實驗前后頂點數(shù)據(jù)進(jìn)行分析后，得出所構(gòu)建的哈希表可以實現(xiàn)16.7%的頂點去冗，能夠達(dá)到理想的實驗結(jié)果。

5 結(jié)語

在對STL文件存儲格式和數(shù)據(jù)冗余情況進(jìn)行分析后，采用除留余數(shù)法構(gòu)建哈希函數(shù)，利用鏈地址法減少哈希沖突的發(fā)生。實驗證明，采用上述方法，能夠?qū)崿F(xiàn)理想的去冗效果，為后續(xù)的切片處理提供了方便，能夠縮短模型的打印時間，提高整體的打印效率。