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

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

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

1 STL文件

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

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

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

2.1 半邊的二元組表示

    本文采用文獻(xiàn)[9]提出的精簡(jiǎn)半邊結(jié)構(gòu)作為基礎(chǔ)，使用三角面的標(biāo)志和半邊在面中的序號(hào)來(lái)表示半邊,。如圖2所示,，頂點(diǎn)A、B,、C,、A按照逆時(shí)針順序連線(xiàn)構(gòu)成面M₁；頂點(diǎn)D,、A,、C、D連線(xiàn)構(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₂為鄰接三角面,。使用二元法表示半邊可以精簡(jiǎn)高效地建立點(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文件的幾何信息通過(guò)頂點(diǎn)和三角面描述，半邊信息定義在頂點(diǎn)類(lèi)中,，使用鍵值對(duì)存入Map容器中,；臨接面信息通過(guò)在三角面類(lèi)中定義一個(gè)包含3個(gè)元素的數(shù)組對(duì)其進(jìn)行存儲(chǔ)。

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

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

2.3 點(diǎn)表和面表

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

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

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

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

3.1 冗余信息剔除

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

    (1)若該地址內(nèi)沒(méi)有數(shù)據(jù),，說(shuō)明該點(diǎn)首次出現(xiàn),，依據(jù)該點(diǎn)所在的三角面片的序號(hào)和點(diǎn)在面中的位置構(gòu)建半邊,，并將其以鍵值對(duì)的形式存入點(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ì)算出相同的哈希地址，因此需要對(duì)比新添加的頂點(diǎn)坐標(biāo)和已存頂點(diǎn)的坐標(biāo)是否相同,。若相同,，則說(shuō)明該點(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)的指針,，形成鏈表來(lái)解決哈希地址沖突,。

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

    依次讀取并存儲(chǔ)3個(gè)頂點(diǎn)信息后，依據(jù)讀取的三角面的序號(hào),，更新面表內(nèi)所對(duì)應(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)暫無(wú)鄰接面信息,。

    后續(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è)已存面均無(wú)鄰接面信息,。

    (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半邊互為反向半邊,，說(shuō)明兩三角面互為鄰接面,，向面(A，B,，C)的border_meshs數(shù)組中添加序號(hào)2,，向面(D，A,，C)的border_meshs數(shù)組中添加半邊CA所在面序號(hào)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ǔ)過(guò)程與重合點(diǎn)數(shù)量相關(guān)需分情況討論。若不存在舊點(diǎn),，則默認(rèn)構(gòu)建即可,；若存在一個(gè)，給該點(diǎn)添加新的半邊,；若存在兩個(gè)以上,，3點(diǎn)按讀入順序，每?jī)牲c(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 測(cè)試實(shí)例及性能分析

    將上述數(shù)據(jù)結(jié)構(gòu)和快速拓?fù)渌惴ㄍㄟ^(guò)OpenGL和Qt Creator編程實(shí)現(xiàn),，同時(shí)，使用文獻(xiàn)[8]中的拓?fù)渌惴ㄅc本文的算法對(duì)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í)間對(duì)比。

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

5 結(jié)論

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

參考文獻(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)自動(dòng)生成算法的研究[J].電子技術(shù)應(yīng)用，2015，41(8)：146-148.

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

[5] 侯聰聰，南琳,，張磊.基于分組的STL模型快速切片算法[J].制造業(yè)自動(dòng)化,，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] 錢(qián)乘,，李震,，江本赤，等.基于哈希表的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)