0 引言

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

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

    基于以上算法的研究，本文提出一種基于哈希表的、利用半邊結構的數據存儲和三角面拓撲算法，在讀取數據過程中，一方面剔除冗余數據，一方面快速建立面的拓撲關系，每讀入一個三角面信息，進行數據存放的同時，在點表中維護一個未添加鄰接面的半邊集合。當數據讀取完成后，建立無重復數據的點表和面表，完善三角面間的拓撲關系。

1 STL文件

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

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

2 采用半邊結構的拓撲數據結構

2.1 半邊的二元組表示

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

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

2.2 拓撲數據結構

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

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

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

2.3 點表和面表

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

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

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

3 STL文件拓撲信息重建流程

3.1 冗余信息剔除

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

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

    (2)若該地址存在數據，由于不相同的兩點也可能計算出相同的哈希地址，因此需要對比新添加的頂點坐標和已存頂點的坐標是否相同。若相同，則說明該點為重復的舊點，不需要進行添加，進行下一個點的處理；若不同，則該點為新點，同樣構建并添加半邊信息后，鏈式添加點解決沖突。例如：讀入新點V₁，計算得到哈希地址為2，但發現該地址已經存在頂點數據且與V₁不同，則需要在該地址處添加指向新點的指針，形成鏈表來解決哈希地址沖突。

3.2 添加三角面并生成拓撲信息

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

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

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

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

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

    (4)新面片的3個頂點與現存頂點均相同，此時又可以又可分為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半邊刪除，完善面的鄰接信息后即完成面的添加和鄰接拓撲信息構建。

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

4 測試實例及性能分析

    將上述數據結構和快速拓撲算法通過OpenGL和Qt Creator編程實現，同時，使用文獻[8]中的拓撲算法與本文的算法對5個STL模型進行拓撲重建實驗，實驗環境為Windows 10操作系統，處理器主頻為2.6 GHz，4.0 GB內存，獲得同一個STL模型在兩種算法下的拓撲關系構建時間。表1為兩種算法運行時間對比。

    由于本文算法在進行STL文件存儲的同時便完成了面片拓撲關系的建立，相比于文獻[8]的算法，不需要存儲數據后再對面表遍歷并進行大量比對尋找鄰接面，節省了大量的時間，從測試結果中也可看出本算法具有更高的效率。

5 結論

    本文提出半邊結構的快速拓撲算法，將半邊信息以鍵值對的形式存入點中，每讀入一個面片，存儲數據的同時，以較快的效率更新未添加鄰接面的半邊集合和面表中的鄰接面數組，STL模型讀取完畢后，面的拓撲信息也同時完善，有效縮短了面片拓撲關系建立的時間，為模型后續的支撐添加和切片處理帶來了極大的便利。

參考文獻

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

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

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

[4] 徐敬華，盛紅升，張樹有，等.基于鄰接拓撲的流形網格模型層切多連通域構建方法[J].計算機輔助設計與圖形學學報，2018，30(1)：180-190.

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

[6] 王增波.STL格式文件的快速拓撲重建算法[J].計算機應用，2014，34(9)：2720-2724.

[7] 王彥云，陳鴻，謝明師，等.基于哈希表的STL格式文件拓撲重建的算法[J].現代制造工程，2015(12)：61-64.

[8] 錢乘，李震，江本赤，等.基于哈希表的STL文件拓撲關系快速重建算法[J].新鄉學院學報，2018，35(6)：36-39，51.

[9] 張應中，謝馥香，羅曉芳，等.采用半邊編碼的三角網格拓撲數據結構[J].計算機輔助設計與圖形學學報，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] 謝馥香.面向三角網格分割體的設計特征重構[D].大連：大連理工大學，2015.

作者信息:

武小超，陳  鴻

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