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

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

0 引言

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

1 STL文件

1.1 STL文件格式

STL(surface tesselation language)文件格式是由美國3D SYSTEMS公司開發(fā)的接口協(xié)議，常被用于服務(wù)快速成型制造[3]，由于它具有存儲(chǔ)形式結(jié)構(gòu)簡單、普適性好的優(yōu)點(diǎn)，市面上大多數(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種存儲(chǔ)格式，本文選用ASCII格式的STL文件用于研究。ASCII格式的STL文件(見表1)逐行給出面片的幾何信息，首先會(huì)以關(guān)鍵字solid開頭，之后依次對各三角面片信息進(jìn)行記錄，在文件信息全部定義結(jié)束后以關(guān)鍵字endsolid結(jié)尾。每個(gè)三角面片信息都有7行數(shù)據(jù)，第1行數(shù)據(jù)的關(guān)鍵字facet normal后給出該三角面片法向量的3個(gè)分量，且規(guī)定法向量朝向三維模型外側(cè)。關(guān)鍵字outerloop和endloop之間用三行數(shù)據(jù)來對此法向量所對應(yīng)的三角面片頂點(diǎn)坐標(biāo)進(jìn)行表示，并規(guī)定頂點(diǎn)的排列順序?yàn)榉ㄏ蛄糠较蛏系哪鏁r(shí)針。

表1 ASCII文件格式

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

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

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

F+V-E=2

(1)

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

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

E=3F/2

(2)

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

V=0.5F+2≈0.5F

(3)

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

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

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

ASCII格式的STL文件結(jié)構(gòu)能通過特定關(guān)鍵詞來識別，又由于其是按行存儲(chǔ)，每行都有指定的關(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)從第一個(gè)三角面片開始，遍歷文件中所有的三角面片，提取法向量和坐標(biāo)的信息，并進(jìn)行紀(jì)錄存儲(chǔ)。

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

3 哈希去冗

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

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

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

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

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

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

(4)

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

H(k)=kmodp

(5)

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

3.2 哈希沖突

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

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

圖1 哈希去冗流程圖

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

圖2 鏈地址法處理沖突時(shí)的哈希表

4 測試實(shí)驗(yàn)及分析

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

表2 實(shí)驗(yàn)結(jié)果

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

5 結(jié)語

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