《電子技術應用》
您所在的位置：首頁 > 嵌入式技術 > 設計應用 > 基于半邊結構的STL文件快速拓撲算法
基于半邊結構的STL文件快速拓撲算法
2020年電子技術應用第1期
武小超，陳 鴻
中北大學 儀器與電子學院，山西 太原030051
摘要： 針對三維模型轉換為STL文件后會丟失三角面間的拓撲關系，在對STL格式文件進行讀取和分析時，提出了一種基于半邊結構和哈希表的快速拓撲重構算法。在讀取數(shù)據(jù)過程中，通過哈希表建立無重復位置信息的點表，并在其中維護一個未添加鄰接面的半邊集合。依據(jù)該集合和拓撲算法完善面的拓撲關系，實現(xiàn)在讀取數(shù)據(jù)的過程中快速建立面的拓撲關系。
中圖分類號： TN06；P301.6
文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.190962
中文引用格式： 武小超，陳鴻. 基于半邊結構的STL文件快速拓撲算法[J].電子技術應用，2020，46(1)：92-95，99.
英文引用格式： Wu Xiaochao，Chen Hong. Fast topology algorithm for STL files based on half-edges structure[J]. Application of Electronic Technique，2020，46(1)：92-95，99.
Fast topology algorithm for STL files based on half-edges structure
Wu Xiaochao，Chen Hong
School of Instrument and Electronics，North University of China，Taiyuan 030051，China
Abstract： In order to solve the problem that the topological relationship between the triangular facets is lost when the 3D model is converted to STL files，in the process of reading and analyzing STL files, a fast topology reconstruction algorithm based on half-edges structure and hash table is proposed. In the process of reading data, a point table without repeat position information is established through a hash table, and a collection containing half-edges in which no adjacency facets are added is maintained therein. According to the set and topology algorithm, the topological relationship of the facets is improved, and the topological relationship of the facets is quickly established in the process of reading data.
Key words : STL file；half-edges structure；hash table；topology algorithm

0 引言

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

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

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

1 STL文件

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

jsj1-t1.gif

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

2 采用半邊結構的拓撲數(shù)據(jù)結構

2.1 半邊的二元組表示

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

jsj1-t2.gif

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

2.2 拓撲數(shù)據(jù)結構

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

jsj1-t3.gif

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

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

2.3 點表和面表

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

     jsj1-gs1-2.gif

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

jsj1-t4.gif

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

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

3.1 冗余信息剔除

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

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

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

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

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

jsj1-t5.gif

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

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

jsj1-t6.gif

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

jsj1-t7.gif

    (3)新面片的3個頂點與現(xiàn)存頂點有兩個相同，此時又可分為兩種情況，新添加面均為(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數(shù)組中添加序號2，向面(D，A，C)的border_meshs數(shù)組中添加半邊CA所在面序號1，而后刪除點C中的半邊CA并添加半邊CD，即half-edges刪除[1，3]，添加[2，3]，便完成了新面的添加和拓撲關系的建立，此時兩面均存在一個鄰接面，所有點均包含一個半邊。

jsj1-t8.gif

    (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半邊刪除，完善面的鄰接信息后即完成面的添加和鄰接拓撲信息構建。

jsj1-t9.gif

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

jsj1-t10.gif

4 測試實例及性能分析

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

jsj1-b1.gif

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

5 結論

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

參考文獻

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

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

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

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

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

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

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

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

[9] 張應中，謝馥香，羅曉芳，等.采用半邊編碼的三角網(wǎng)格拓撲數(shù)據(jù)結構[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] 謝馥香.面向三角網(wǎng)格分割體的設計特征重構[D].大連：大連理工大學，2015.




作者信息:

武小超，陳  鴻

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

此內容為AET網(wǎng)站原創(chuàng)，未經(jīng)授權禁止轉載。