自3D打印技術(shù)問世之后,，憑借其復(fù)雜性低、成本低廉,、軟件開源,、易于推廣等特點在國內(nèi)外得到了迅速的發(fā)展^[1]。STL(Stereo Lithography)文件是由美國3D System公司于1987年制定的接口協(xié)議,，由于其格式簡單,、讀寫便利，成為3D打印過程中最常用的數(shù)據(jù)存儲格式^[2],。STL文件由離散的三角面片組成,，存放了模型的點云的位置信息和三角面片的法向量，但其丟失了面與面之間的拓?fù)潢P(guān)系,，同時,，單個點被多次記錄，造成了大量的數(shù)據(jù)冗余^[3],。在快速成型過程中,，待支撐位置查詢、模型分層切片等操作均需要三角面間的拓?fù)潢P(guān)系^[4],，因此,，建立合理的數(shù)據(jù)結(jié)構(gòu)剔除冗余信息，采用高效的算法建立拓?fù)潢P(guān)系就顯得尤為重要,。

    針對STL文件讀寫的局限,，國內(nèi)外專家提出多種解決方案。侯聰聰?shù)?sup>[5]提出基于鏈表的數(shù)據(jù)存儲和拓?fù)浣Y(jié)構(gòu),，建立點,、邊、面表進(jìn)行數(shù)據(jù)存儲,，雖剔除了STL文件中的重復(fù)點，但每次建立拓?fù)潢P(guān)系時,，均對整個邊表進(jìn)行遍歷,，算法性能較低；王增波^[6]采用哈希表作為基礎(chǔ)結(jié)構(gòu),，將有效數(shù)據(jù)僅保存一次,，提升了數(shù)據(jù)的添加和查找速度,，幾乎可以在常數(shù)時間內(nèi)快速完成，但建立拓?fù)潢P(guān)系時,，依舊是對已存數(shù)據(jù)進(jìn)行遍歷,，不僅效率較低，還存在部分?jǐn)?shù)據(jù)查找遺漏的現(xiàn)象,；王彥云等^[7]優(yōu)化了哈希表的沖突解決方案,，采用二分查找的方法對相同key值的鏈表進(jìn)行查找，提升了查表速度,，但拓?fù)渌惴?/a>效率依舊較低,；錢乘等^[8]也采用哈希表進(jìn)行數(shù)據(jù)存儲，存儲數(shù)據(jù)的同時對每個點記錄其所屬三角面片,，全部存儲完畢后,，再對所有面片進(jìn)行遍歷，建立拓?fù)潢P(guān)系,，不存在遺漏,，但讀取完成后，需要再次遍歷面表尋找鄰接面,；張應(yīng)中等^[9]利用半邊結(jié)構(gòu)進(jìn)行拓?fù)潢P(guān)系建立,，巧妙地將點與面的信息存入邊，利用三角面中頂點的存放順序來保存邊的信息,，精簡了存儲結(jié)構(gòu),，但拓?fù)渌惴◤?fù)雜，并且需要在讀入全部頂點的情況下建立拓?fù)潢P(guān)系,。

    基于以上算法的研究,，本文提出一種基于哈希表的、利用半邊結(jié)構(gòu)的數(shù)據(jù)存儲和三角面拓?fù)渌惴?，在讀取數(shù)據(jù)過程中,，一方面剔除冗余數(shù)據(jù)，一方面快速建立面的拓?fù)潢P(guān)系,，每讀入一個三角面信息,，進(jìn)行數(shù)據(jù)存放的同時，在點表中維護(hù)一個未添加鄰接面的半邊集合,。當(dāng)數(shù)據(jù)讀取完成后,，建立無重復(fù)數(shù)據(jù)的點表和面表，完善三角面間的拓?fù)潢P(guān)系,。

1 STL文件

    STL格式文件分為ASCII碼和二進(jìn)制兩種,，其中，二進(jìn)制格式的文件數(shù)據(jù)結(jié)構(gòu)如圖1所示,，與ASCII相比存儲更加緊湊,，占用空間較小,，會在文件起始位置記錄三角面片總數(shù)Num，在后續(xù)建立哈希表時也能依據(jù)此選擇更加合適的表長,。

    由歐拉公式可知,，存儲正確的三角網(wǎng)格文件，三角面的數(shù)量約為頂點的2倍^[10],，而在STL文件中,，每存儲一次面片信息，都會重復(fù)存儲3個點的位置坐標(biāo),，使得存的儲頂點數(shù)量是面片數(shù)量的3倍^[11],。由此可得，每個頂點在STL文件中平均記錄了6次,，所以在進(jìn)行拓?fù)潢P(guān)系建立前,，需要先對冗余信息進(jìn)行辨別和剔除，使每個頂點僅存儲一次,，減少數(shù)據(jù)存儲量,，提升算法效率。

2 采用半邊結(jié)構(gòu)的拓?fù)鋽?shù)據(jù)結(jié)構(gòu)

2.1 半邊的二元組表示

    本文采用文獻(xiàn)[9]提出的精簡半邊結(jié)構(gòu)作為基礎(chǔ),，使用三角面的標(biāo)志和半邊在面中的序號來表示半邊,。如圖2所示，頂點A,、B,、C、A按照逆時針順序連線構(gòu)成面M₁,；頂點D,、A、C,、D連線構(gòu)成面M₂,，半邊L₂可以表示為[M₁，2],，即M₁面中的第2條半邊,，半邊L₆可以表示為[M₂，3],，即M₂面中的第3條半邊,。

    當(dāng)兩個半邊頂點相同且邊的起點與終點相互調(diào)換時，兩半邊互為反向半邊,，這時,，兩半邊所屬三角面互為鄰接面。如圖2所示,，L₃和L₅為反向半邊,，M₁與M₂為鄰接三角面。使用二元法表示半邊可以精簡高效地建立點,、邊,、面的關(guān)系，當(dāng)兩半邊為反向半邊時,，可立即得到該半邊所在面,，從而建立面的拓?fù)潢P(guān)系。

2.2 拓?fù)鋽?shù)據(jù)結(jié)構(gòu)

    基于STL文件的特點和半邊二元組的表示,，綜合考慮空間和效率需求,，本文提出如下的基于半邊結(jié)構(gòu)的三角面拓?fù)鋽?shù)據(jù)結(jié)構(gòu)。如圖3所示,，STL文件的幾何信息通過頂點和三角面描述,，半邊信息定義在頂點類中，使用鍵值對存入Map容器中,；臨接面信息通過在三角面類中定義一個包含3個元素的數(shù)組對其進(jìn)行存儲,。

    (1)頂點類(Class Vertex)。頂點數(shù)據(jù)包括頂點位置坐標(biāo)和一個用來存儲半邊信息的Map容器,。該Map容器以紅黑樹為底層,，存放以該頂點為起點的半邊，半邊信息通過將上文中的二元組轉(zhuǎn)化為鍵值對進(jìn)行存儲,。使用紅黑樹作為底層數(shù)據(jù)結(jié)構(gòu),，可以避免使用連續(xù)內(nèi)存，并將以該點為起點的半邊信息全部保存,，其搜索時間復(fù)雜度為O(lgn),，在增加刪除半邊時，不會對頂點存放的Hash表產(chǎn)生額外影響,，同時仍具有較快的速度,。

    (2)三角面類(Class Mesh)。面數(shù)據(jù)包含3個指向頂點的指針, 采用一維數(shù)組存放,，指針存儲順序同時隱性包含了半邊順序,，即：頂點V₁與V₂形成序號為1的半邊，頂點V₂與V₃形成序號為2的半邊,，頂點V₃與V₁形成序號為3的半邊,；此外，將法向量坐標(biāo)存入normal_vector數(shù)組,，面片的3個臨接面存入border_meshs數(shù)組,。

2.3 點表和面表

    存儲頂點數(shù)據(jù)時，需要快速判斷該頂點是否已經(jīng)保存,，鑒于哈希表查找時較低的時間復(fù)雜度,，采用哈希表對頂點數(shù)據(jù)進(jìn)行保存,。本文哈希函數(shù)如下：

其中，x,、y,、z為頂點坐標(biāo)的3個分量值，m為哈希表的長度,，h(k)為計算出的哈希地址,。由于STL文件數(shù)據(jù)精度較高，使得各點的值較為接近,，因此對k進(jìn)行一定程度放大,。STL文件滿足歐拉關(guān)系，即三角網(wǎng)格模型的頂點總數(shù)是其總?cè)敲嫫瑪?shù)的1/2,，所以m取值為與Num/2最接近的素數(shù),，以減少散列地址的沖突。存儲頂點的哈希表如圖4所示,。

    因為面數(shù)據(jù)不存在重復(fù),，所以直接使用面對象數(shù)組作為面表，一方面可以在O(1)的時間復(fù)雜度內(nèi)找到對應(yīng)面片,，修改面片信息,；另一方面，將數(shù)組的下標(biāo)加1,，便可作為面片的標(biāo)志,，可以快速定位半邊位置。

3 STL文件拓?fù)湫畔⒅亟鞒?/strong>

3.1 冗余信息剔除

    當(dāng)開始進(jìn)行STL文件讀取后,，會依次讀入所有三角面片的頂點和法向量信息,，法向量信息待3個點均讀入后存入面對象，將頂點的3個坐標(biāo)帶入式(1),、式(2),，計算得到哈希地址，即該點存入點表的位置,，而后分為以下兩種情況：

    (1)若該地址內(nèi)沒有數(shù)據(jù),，說明該點首次出現(xiàn)，依據(jù)該點所在的三角面片的序號和點在面中的位置構(gòu)建半邊,，并將其以鍵值對的形式存入點的half-edges,，便完成新點添加。例如,，依次讀入第4個面片的3個頂點V₁,、V₂、V₃，由于V₂是第2個讀入的點,，則構(gòu)建二元組為[4,，2]，即第4個面片中的第2個半邊,，半邊方向由V₂指向V₃,。

    (2)若該地址存在數(shù)據(jù)，由于不相同的兩點也可能計算出相同的哈希地址,，因此需要對比新添加的頂點坐標(biāo)和已存頂點的坐標(biāo)是否相同。若相同,，則說明該點為重復(fù)的舊點,，不需要進(jìn)行添加，進(jìn)行下一個點的處理,；若不同,，則該點為新點，同樣構(gòu)建并添加半邊信息后,，鏈?zhǔn)教砑狱c解決沖突,。例如：讀入新點V₁，計算得到哈希地址為2,，但發(fā)現(xiàn)該地址已經(jīng)存在頂點數(shù)據(jù)且與V₁不同,，則需要在該地址處添加指向新點的指針，形成鏈表來解決哈希地址沖突,。

3.2 添加三角面并生成拓?fù)湫畔?/strong>

    依次讀取并存儲3個頂點信息后,，依據(jù)讀取的三角面的序號，更新面表內(nèi)所對應(yīng)面的頂點和法向量信息,，即vertex數(shù)組和 normal_vector數(shù)組,。第一個面片讀取完成后，點表中的半邊信息如圖5所示,，點A,、B、C所存半邊信息依次為[1,，1],、[1，2],、[1,，3]，即AB,、BC,、CA半邊，此時border_meshs數(shù)組內(nèi)暫無鄰接面信息。

    后續(xù)繼續(xù)添加面片信息時存在多種情況,，以下分別討論：

    (1)新面片的3個頂點與現(xiàn)存頂點均不相同,。即3頂點均為第一次讀取，構(gòu)建面數(shù)據(jù)并將其加入面表后,，半邊信息如圖6所示,，其中(A，B,，C)為已存面,，(D，E,，F(xiàn))為新添加面,所有點目前僅保存一個半邊,，所有面不存在鄰接面。

    (2)新面片的3個頂點與現(xiàn)存頂點有一個相同,，構(gòu)建面數(shù)據(jù)并將其加入面表后,，半邊信息如圖7(a)所示，其中(A,，B,，C)為已存面，(D,，C,，E)為新添加面，由于點C不是首次讀取,，因此點中已經(jīng)存有指向點A的半邊,，需將C指向點E的半邊也存入其中，即構(gòu)建[2,，2]半邊存入點C的half-edges,，此時點C中存有兩個半邊信息，添加后的半邊信息如圖7(b)所示,。此時點C中存有兩個半邊信息,，兩個已存面均無鄰接面信息。

    (3)新面片的3個頂點與現(xiàn)存頂點有兩個相同,，此時又可分為兩種情況,，新添加面均為(D，A,，C),。①情況1如圖8(a)所示，A,、C兩點為已存點,，由于C點已存半邊CE與AC半邊不是反向半邊,，因此兩面不是鄰接面，構(gòu)建AC,、CD兩半邊分別存入點A,、C中即可，此時A,、C,、E 3點均存有兩個半邊信息；②情況2如圖8(b)所示,，A,、C兩點為已存點，由于C點包含指向A點的半邊CA,，與新添加面中的AC半邊互為反向半邊,，說明兩三角面互為鄰接面，向面(A,，B，C)的border_meshs數(shù)組中添加序號2,，向面(D,，A，C)的border_meshs數(shù)組中添加半邊CA所在面序號1,，而后刪除點C中的半邊CA并添加半邊CD,，即half-edges刪除[1，3],，添加[2,，3]，便完成了新面的添加和拓?fù)潢P(guān)系的建立,，此時兩面均存在一個鄰接面,，所有點均包含一個半邊。

    (4)新面片的3個頂點與現(xiàn)存頂點均相同,，此時又可以又可分為4種情況,，新加入的面均為(D，A,，C),。①情況1如圖9(a)所示，不存在新的鄰接邊,，將D,、A、C 3點均添加新的半邊即可,；②情況2如圖9(b)所示,，有一條新的鄰接邊,，添加DA、CD半邊,，刪除CA半邊,，并在兩面中添加鄰接面即可；③情況3如圖9(c)所示,，有兩條新的鄰接邊,，添加DA半邊，將CA,、DC半邊刪除,，并完善鄰接面信息；④情況4如圖9(d)所示,，3條邊均為新的鄰接邊,，將AD、DC,、CA半邊刪除,，完善面的鄰接信息后即完成面的添加和鄰接拓?fù)湫畔?gòu)建。

    綜上,，面片的添加與拓補過程與重合點數(shù)量相關(guān)需分情況討論,。若不存在舊點，則默認(rèn)構(gòu)建即可,；若存在一個,，給該點添加新的半邊；若存在兩個以上,，3點按讀入順序,，每兩點組成一個新半邊，依次判斷3個半邊的半邊,，即是否存在新的鄰接面,。若不存在，則為半邊的起點添加新半邊,；若存在,，則在面表內(nèi)添加新的鄰接面，并刪除起點的原有半邊,。注意,，若3點中僅有兩點為已存點，則需要為刪除半邊的點添加新的,、基于新添加面片的半邊(如圖8(b)所示),。整個拓?fù)淞鞒倘鐖D10所示。

4 測試實例及性能分析

    將上述數(shù)據(jù)結(jié)構(gòu)和快速拓?fù)渌惴ㄍㄟ^OpenGL和Qt Creator編程實現(xiàn),，同時,，使用文獻(xiàn)[8]中的拓?fù)渌惴ㄅc本文的算法對5個STL模型進(jìn)行拓?fù)渲亟▽嶒?，實驗環(huán)境為Windows 10操作系統(tǒng)，處理器主頻為2.6 GHz,，4.0 GB內(nèi)存,，獲得同一個STL模型在兩種算法下的拓?fù)潢P(guān)系構(gòu)建時間。表1為兩種算法運行時間對比,。

    由于本文算法在進(jìn)行STL文件存儲的同時便完成了面片拓?fù)潢P(guān)系的建立,，相比于文獻(xiàn)[8]的算法，不需要存儲數(shù)據(jù)后再對面表遍歷并進(jìn)行大量比對尋找鄰接面,，節(jié)省了大量的時間,，從測試結(jié)果中也可看出本算法具有更高的效率。

5 結(jié)論

    本文提出半邊結(jié)構(gòu)的快速拓?fù)渌惴?，將半邊信息以鍵值對的形式存入點中,，每讀入一個面片，存儲數(shù)據(jù)的同時,，以較快的效率更新未添加鄰接面的半邊集合和面表中的鄰接面數(shù)組,，STL模型讀取完畢后，面的拓?fù)湫畔⒁餐瑫r完善,，有效縮短了面片拓?fù)潢P(guān)系建立的時間,，為模型后續(xù)的支撐添加和切片處理帶來了極大的便利。

參考文獻(xiàn)

[1] 宋廷強,，邢照合.一種彩色FDM型3D打印機(jī)的設(shè)計與實現(xiàn)[J].電子技術(shù)應(yīng)用，2017,，43(4)：69-71,，75.

[2] 楊晟院，陳瑤,，易飛,，等.基于2維流形的STL曲面網(wǎng)格重建算法[J].軟件學(xué)報，2017,，28(12)：3358-3366.

[3] 王彥云,，陳鴻，謝明師,，等.FDM快速成型支撐結(jié)構(gòu)自動生成算法的研究[J].電子技術(shù)應(yīng)用,，2015，41(8)：146-148.

[4] 徐敬華,，盛紅升,，張樹有，等.基于鄰接拓?fù)涞牧餍尉W(wǎng)格模型層切多連通域構(gòu)建方法[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報,，2018,，30(1)：180-190.

[5] 侯聰聰,，南琳，張磊.基于分組的STL模型快速切片算法[J].制造業(yè)自動化,，2014,，36(9)：12-15.

[6] 王增波.STL格式文件的快速拓?fù)渲亟ㄋ惴╗J].計算機(jī)應(yīng)用，2014,，34(9)：2720-2724.

[7] 王彥云,，陳鴻，謝明師,，等.基于哈希表的STL格式文件拓?fù)渲亟ǖ乃惴╗J].現(xiàn)代制造工程,，2015(12)：61-64.

[8] 錢乘，李震,，江本赤,，等.基于哈希表的STL文件拓?fù)潢P(guān)系快速重建算法[J].新鄉(xiāng)學(xué)院學(xué)報，2018,，35(6)：36-39,，51.

[9] 張應(yīng)中，謝馥香,，羅曉芳,，等.采用半邊編碼的三角網(wǎng)格拓?fù)鋽?shù)據(jù)結(jié)構(gòu)[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2016,，28(2)：328-334.

[10] BOTSCH M,，KOBBELT L，PAULY M,，et al.Polygon mesh processing[M].Natick：A K Peters,，2010：1-2.

[11] 謝馥香.面向三角網(wǎng)格分割體的設(shè)計特征重構(gòu)[D].大連：大連理工大學(xué)，2015.

作者信息:

武小超,，陳  鴻

(中北大學(xué) 儀器與電子學(xué)院,，山西 太原030051)