自3D打印技術(shù)問世之后，憑借其復(fù)雜性低、成本低廉、軟件開源、易于推廣等特點(diǎn)在國內(nèi)外得到了迅速的發(fā)展^[1]。STL(Stereo Lithography)文件是由美國3D System公司于1987年制定的接口協(xié)議，由于其格式簡單、讀寫便利，成為3D打印過程中最常用的數(shù)據(jù)存儲格式^[2]。STL文件由離散的三角面片組成，存放了模型的點(diǎn)云的位置信息和三角面片的法向量，但其丟失了面與面之間的拓?fù)潢P(guān)系，同時(shí)，單個(gè)點(diǎ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)，建立點(diǎn)、邊、面表進(jìn)行數(shù)據(jù)存儲，雖剔除了STL文件中的重復(fù)點(diǎn)，但每次建立拓?fù)潢P(guān)系時(shí)，均對整個(gè)邊表進(jìn)行遍歷，算法性能較低；王增波^[6]采用哈希表作為基礎(chǔ)結(jié)構(gòu)，將有效數(shù)據(jù)僅保存一次，提升了數(shù)據(jù)的添加和查找速度，幾乎可以在常數(shù)時(shí)間內(nèi)快速完成，但建立拓?fù)潢P(guān)系時(shí)，依舊是對已存數(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ù)的同時(shí)對每個(gè)點(diǎn)記錄其所屬三角面片，全部存儲完畢后，再對所有面片進(jìn)行遍歷，建立拓?fù)潢P(guān)系，不存在遺漏，但讀取完成后，需要再次遍歷面表尋找鄰接面；張應(yīng)中等^[9]利用半邊結(jié)構(gòu)進(jìn)行拓?fù)潢P(guān)系建立，巧妙地將點(diǎn)與面的信息存入邊，利用三角面中頂點(diǎn)的存放順序來保存邊的信息，精簡了存儲結(jié)構(gòu)，但拓?fù)渌惴◤?fù)雜，并且需要在讀入全部頂點(diǎn)的情況下建立拓?fù)潢P(guān)系。

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

1 STL文件

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

    由歐拉公式可知，存儲正確的三角網(wǎng)格文件，三角面的數(shù)量約為頂點(diǎn)的2倍^[10]，而在STL文件中，每存儲一次面片信息，都會重復(fù)存儲3個(gè)點(diǎn)的位置坐標(biāo)，使得存的儲頂點(diǎn)數(shù)量是面片數(shù)量的3倍^[11]。由此可得，每個(gè)頂點(diǎn)在STL文件中平均記錄了6次，所以在進(jìn)行拓?fù)潢P(guān)系建立前，需要先對冗余信息進(jìn)行辨別和剔除，使每個(gè)頂點(diǎ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所示，頂點(diǎn)A、B、C、A按照逆時(shí)針順序連線構(gòu)成面M₁；頂點(diǎn)D、A、C、D連線構(gòu)成面M₂，半邊L₂可以表示為[M₁，2]，即M₁面中的第2條半邊，半邊L₆可以表示為[M₂，3]，即M₂面中的第3條半邊。

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

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

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

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

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

2.3 點(diǎn)表和面表

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

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

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

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

3.1 冗余信息剔除

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

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

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

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

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

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

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

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

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

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

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

4 測試實(shí)例及性能分析

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

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

5 結(jié)論

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

參考文獻(xiàn)

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

[2] 楊晟院，陳瑤，易飛，等.基于2維流形的STL曲面網(wǎng)格重建算法[J].軟件學(xué)報(bào)，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ì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2018，30(1)：180-190.

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

[6] 王增波.STL格式文件的快速拓?fù)渲亟ㄋ惴╗J].計(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é)報(bào)，2018，35(6)：36-39，51.

[9] 張應(yīng)中，謝馥香，羅曉芳，等.采用半邊編碼的三角網(wǎng)格拓?fù)鋽?shù)據(jù)結(jié)構(gòu)[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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è)計(jì)特征重構(gòu)[D].大連：大連理工大學(xué)，2015.

作者信息:

武小超，陳  鴻

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