自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ù)渌惴ǎ瑢脒呅畔⒁枣I值對的形式存入點中，每讀入一個面片，存儲數(shù)據(jù)的同時，以較快的效率更新未添加鄰接面的半邊集合和面表中的鄰接面數(shù)組，STL模型讀取完畢后，面的拓?fù)湫畔⒁餐瑫r完善，有效縮短了面片拓?fù)潢P(guān)系建立的時間，為模型后續(xù)的支撐添加和切片處理帶來了極大的便利。

參考文獻(xiàn)

[1] 宋廷強，邢照合.一種彩色FDM型3D打印機的設(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].計算機輔助設(shè)計與圖形學(xué)學(xué)報，2018，30(1)：180-190.

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

[6] 王增波.STL格式文件的快速拓?fù)渲亟ㄋ惴╗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].計算機輔助設(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)