錢　乘，李　震，江本赤，王　剛

（安徽工程大學 機械與汽車工程學院，安徽 蕪湖 241000）

STL（surface tesselation language）文件格式是美國3D SYSTEMS公司于1988年制定的一個接口協(xié)議［1］。STL文件由逼近三維模型表面的多個三角形面片構(gòu)成，但它已經(jīng)丟失了原有的拓撲關(guān)系，且所記錄的每個三角形頂點都至少被記錄4次，平均被記錄6次，造成了數(shù)據(jù)大量冗余。STL文件三角形間無拓撲關(guān)系且存在數(shù)據(jù)極大冗余，造成后續(xù)切片處理效率低，模型整體打印時間長。因此，構(gòu)建合理的數(shù)據(jù)結(jié)構(gòu)去除冗余數(shù)據(jù)，根據(jù)數(shù)據(jù)結(jié)構(gòu)建立拓撲結(jié)構(gòu)極其重要。

目前，研究人員已提出了多種STL文件拓撲關(guān)系的重建算法。張應(yīng)中等［2］構(gòu)造半邊編碼的三角網(wǎng)格拓撲數(shù)據(jù)結(jié)構(gòu)實現(xiàn)拓撲重構(gòu)，但構(gòu)造該數(shù)據(jù)結(jié)構(gòu)時程序復(fù)雜且拓撲重建運算效率較低；侯聰聰?shù)龋?］構(gòu)造鏈表數(shù)據(jù)結(jié)構(gòu)重建拓撲關(guān)系，但在去除冗余數(shù)據(jù)時，遍歷整體鏈表會降低算法效率；陳萍等［4］利用三角形間半邊拓撲結(jié)構(gòu)遍歷所構(gòu)建的紅黑樹實現(xiàn)拓撲重構(gòu)，但建樹與檢測平衡性在一定程度上降低了算法效率；楊晟院等［1］構(gòu)建平衡二叉樹的數(shù)據(jù)結(jié)構(gòu)進行頂點聚合去除冗余數(shù)據(jù)，采用虛平衡二叉樹進行快速鄰邊搜索實現(xiàn)拓撲重建，但當數(shù)據(jù)量較大時，建樹與調(diào)整平衡需要花費時間，會降低算法效率；王增波［5］及王彥云等［6］構(gòu)建哈希表實現(xiàn)冗余數(shù)據(jù)的去除以及快速的拓撲重建，但忽略了不同坐標可能存在相同關(guān)鍵字的情況，造成冗余數(shù)據(jù)去除與拓撲關(guān)系重建錯誤。

考慮到哈希表算法結(jié)構(gòu)簡單且時間復(fù)雜度較低，在冗余數(shù)據(jù)剔除與三角形間拓撲關(guān)系重建上具有較高效率，我們提出了基于哈希表的STL文件拓撲關(guān)系快速重建算法。算法主要是在分析STL文件信息的基礎(chǔ)上，采用除留余數(shù)法與鏈地址法建立哈希表，在建立哈希表的同時完成對冗余數(shù)據(jù)的剔除、點表的建立及面表中的點索引值的建立，通過面表中記錄的每個三角形的3個頂點坐標索引值的兩兩組合，得到點表中記錄的共同三角形面片的索引值，根據(jù)共同面片索引值對面表中鄰接面進行賦值，進行快速拓撲關(guān)系重建。

1　STL文件信息存儲特點

STL文件中每個三角形面片的定義都包括三角形3個頂點的坐標以及單位法向量。三角形頂點坐標按照逆時針順序存儲，單位法向量方向指向模型外部。STL文件有兩種格式：ASCII格式與二進制格式。二進制格式是采用固定字節(jié)給出三角形面片幾何信息的，包含80 B的頭文件信息、4 B的三角形面片個數(shù)信息、50 B描述三角形面片的信息。ASCII格式則以關(guān)鍵字為標志逐行給出三角形面片幾何信息，數(shù)據(jù)格式如圖1所示。ASCII格式與二進制格式相比更具可讀性和直觀性，方便對數(shù)據(jù)進行進一步處理。

圖1　STL文件的ASCII格式結(jié)構(gòu)

2　哈希表及STL文件拓撲重建

2.1　哈希表的建立

哈希表是可以根據(jù)關(guān)鍵字直接進行訪問的數(shù)據(jù)結(jié)構(gòu)。它采用函數(shù)映射的思想，將關(guān)鍵字映射到表中某個位置來訪問記錄，可以加快查找速度。映射函數(shù)叫作哈希函數(shù)，存放記錄的數(shù)據(jù)叫作哈希表［7］。哈希表的建立需要兩個關(guān)鍵步驟：哈希函數(shù)的設(shè)計與哈希沖突的解決方法。

2.1.1哈希函數(shù)的設(shè)計

哈希函數(shù)的設(shè)計目標主要有兩個：一是使關(guān)鍵字的哈希地址在連續(xù)內(nèi)存單元地址上盡可能地均勻分布，一是運算過程盡可能簡單以提高哈希地址的計算速度。哈希函數(shù)的設(shè)計方法有直接定址法、數(shù)字分析法和除留余數(shù)法等［7］。我們選用除留余數(shù)法設(shè)計哈希函數(shù)。

根據(jù)歐拉方程

可知，哈希表的長度可設(shè)定為

這里Nvertex、Nfacet和Nedge分別為STL模型實際頂點、三角形面片的數(shù)量和邊的數(shù)量，Nvertex＇為STL文件記錄的頂點數(shù)目［8］。

假設(shè)頂點坐標為（vx，vy，vz），則關(guān)鍵字為

除留余數(shù)法就是用關(guān)鍵字 ki（0≤i≤Nvertex＇-1）除以不大于哈希表長度m的整數(shù)p所得余數(shù)作為哈希地址的方法。除留余數(shù)法建立的哈希函數(shù)為

其中：mod為求余運算；p取最接近m的素數(shù)，以減少哈希沖突的可能性。

2.1.2哈希沖突的解決方法

哈希表的建立過程中會出現(xiàn)這樣的問題：不同的關(guān)鍵字 ki與 kj（i≠j）會存在相同的哈希地址 h（ki）=h（kj），這種現(xiàn)象稱為哈希沖突。哈希沖突的解決方法有開放地址法、再哈希法和鏈地址法等［7］。由于鏈地址法具有處理沖突簡單、無堆積現(xiàn)象等優(yōu)勢，我們采用鏈地址法處理哈希沖突。鏈地址法將具有哈希沖突的關(guān)鍵字ki鏈接在該哈希地址對應(yīng)的鏈表中。采用鏈地址法建立的鏈表結(jié)構(gòu)如圖2所示。

圖2　哈希表數(shù)據(jù)結(jié)構(gòu)

2.2　點表與面表數(shù)據(jù)結(jié)構(gòu)

三角形間拓撲關(guān)系的重建是先通過面表中記錄的頂點坐標索引值的兩兩組合得到點表中記錄的共同三角形面片的索引值，再根據(jù)共同面片索引值對面表中鄰接面進行賦值?？梢?，建立合理的點表與面表數(shù)據(jù)格式非常重要。

2.2.1點表的結(jié)構(gòu)

在建立點表時，可以將每個點的數(shù)據(jù)結(jié)構(gòu)看作點表中的單元。每個單元包含點坐標的索引值、點坐標和所屬三角形面片索引值。關(guān)鍵字在哈希表中的地址作為點坐標的索引值。點表單元結(jié)構(gòu)如圖3所示。

圖3　點表單元結(jié)構(gòu)

2.2.2面表的結(jié)構(gòu)

在建立面表時，可以將每個面的數(shù)據(jù)結(jié)構(gòu)看作面表中的單元。面表單元結(jié)構(gòu)如圖4所示。每個單元包含三角形面片的索引值、3個頂點坐標的索引值、每條邊的鄰接三角形面片索引值。為方便后續(xù)切片，將邊的順序按照逆時針方向分為第一、第二、第三條邊（在圖4中用英文單詞表示），然后獲取每條邊的鄰接三角形面片索引值。

圖4　面表單元結(jié)構(gòu)

2.3　拓撲重建算法

在建立哈希表的同時，以不完整的哈希表作為查找表進行冗余坐標的剔除。在STL文件中，由于數(shù)據(jù)量龐大，建立哈希表時可能存在相同關(guān)鍵字對應(yīng)不同點坐標的情況。因此，我們將冗余坐標的判斷條件定為關(guān)鍵字相同且該關(guān)鍵字對應(yīng)的坐標值也相同。STL文件中三角形間拓撲關(guān)系的重建，實際上是根據(jù)STL模型三角形間的共邊規(guī)則進行拓撲重建。拓撲關(guān)系重建算法步驟如下：

1）順序讀取一個三角形面片的頂點坐標。

2）根據(jù)式（4）與式（5）變換頂點坐標，得到關(guān)鍵字及哈希地址。

3）在該哈希地址對應(yīng)的鏈表中查找。若未查到該關(guān)鍵字的記錄，就將該關(guān)鍵字存入鏈表中，建立該頂點的點單元數(shù)據(jù)；若查到該關(guān)鍵字的記錄，轉(zhuǎn)到4）。

4）將該頂點坐標與已記錄的坐標進行比較。若坐標值相同，則視為冗余數(shù)據(jù)，在已存在的點表單元數(shù)據(jù)中記錄該頂點所屬面片的索引值；若坐標值不同，則將該關(guān)鍵字存入鏈表中，建立該頂點的點單元數(shù)據(jù)。

5）在面表中記錄該頂點的索引值。

6）若三角形面片頂點坐標讀取完成，則轉(zhuǎn)到步驟7）；若未完成，則轉(zhuǎn)到 1）。

7）順序讀取面表中面單元結(jié)構(gòu)頂點索引值數(shù)據(jù)。

8）將3個頂點坐標索引值以逆時針方向兩兩組合，得到點表中2個點單元數(shù)據(jù)共同所屬三角形面片的索引值，然后去除所讀取的三角形面片索引值，以余留三角形面片索引值對面表單元數(shù)據(jù)中的鄰接面進行賦值。

9）檢查面表中面表單元是否被完全讀取。若未完全讀取，則轉(zhuǎn)到7）；否則，結(jié)束程序。

3　實驗及結(jié)果分析

為了驗證STL文件拓撲關(guān)系重建算法的可靠性與可行性，給出如圖5所示的模型。圖5（a）為三維模型，圖5（b）為利用拓撲重建算法建立的STL模型。通過對比圖 5（a）與圖 5（b）模型，可觀察到 STL模型與三維模型表面完全符合，且STL模型中三角形拓撲關(guān)系沒出現(xiàn)拓撲混亂的情況。

在圖5（a）三維模型的STL文件中，三角形面片數(shù)為394、頂點數(shù)為1 182、占用存儲空間為112 KB。在利用哈希表對STL文件中坐標信息進行處理后，去除冗余頂點的數(shù)目為989、占用存儲空間為34 KB?？梢?，利用哈希表刪除STL文件中的冗余坐標可大幅度降低STL文件占用的存儲空間。

對于圖5（b）STL模型，利用本文拓撲重建算法重建時間為0.015 s，文獻［4］的拓撲重建算法重建時間為0.118 s，文獻［6］拓撲重建算法重建時間為0.013 s。文獻［6］的拓撲重建時間雖然小于本文拓撲重建算法，但文獻［6］在通過哈希表建立三角形拓撲關(guān)系時，忽略了不同坐標可能存在相同關(guān)鍵字的情況，易造成冗余數(shù)據(jù)去除與拓撲關(guān)系重建錯誤。

在圖5（a）所示三維模型的 STL文件中任意給定一個三角形，如圖6（a）所示面表中索引值為35的三角形面片［即圖5（b）模型中箭頭指向處］，利用拓撲重建算法可迅速查找到與其鄰接的三角形面片，按照逆時針規(guī)則分別為三角形面片20、80和21。圖6（b）為利用本文拓撲重建算法建立該三角形的局部拓撲關(guān)系的示意圖。可以看出，使用本算法能更清晰地觀察三角形間拓撲關(guān)系，說明算法在STL文件拓撲關(guān)系的重建上具有較好的效果。

圖5　STL模型的拓撲重建效果圖

圖6　STL模型的局部拓撲重建效果圖

4　結(jié)論

在建立哈希表的同時以不完整的哈希表作為查找表，進行冗余坐標的剔除，可以有效減少STL文件占用的存儲空間，方便文件傳輸以及后續(xù)數(shù)據(jù)處理。通過點表與面表中點索引值的運用，高效建立STL文件三角形間拓撲關(guān)系，提高了切片效率，可降低模型的整體打印時間。