STL模型冗余頂點全域哈希處理算法

李 勇，宋占洋，尚會超，付曉莉

（中原工學院機電學院，河南 鄭州451191）

1 引言

STL文件（Stereolithography，光固化立體造型術的縮寫）作為一種三維模型數據格式，常用于CAD應用程序，例如快速成型系統(tǒng)中［1-2］。STL格式非常簡單，其原理是所有模型的表面都可以看作一個多邊形，多邊形用一組三角面片進行分割，每個三角面片用一組表示其頂點坐標和法向矢量坐標信息的數據保存到文件中，分割模型的三角面片被隨機的存儲，彼此之間沒有任何鄰接關系［3］。

但是在實際應用時，STL格式文件最主要的缺點就是它的存儲形式不包含模型表面結構和拓撲關系。在STL文件的生成算法中，每個頂點至少被6個三角形共有，這個共有的頂點坐標被重復存儲，造成了大量冗余坐標信息［4］。

在進行模型處理時，需要重構三角網格，建立三角面片之間的拓撲關系。這種拓撲關系的建立是通過對每個頂點找到所有包含這個頂點的三角面片。從給定的三角面片集合中重建三角網格具有很大的復雜性，特別是對所含三角面片數量較多的模型文件［5-6］。

重構三角網格時，必須遍歷三角網格上的每個頂點，將他們在一個坐標系中進行排序，刪除重復頂點坐標，建立有規(guī)律的三角網格和鄰接的三角形坐標信息。重構的三角網格中，所有頂點只存儲一次，在計算機中執(zhí)行這種操作的時間復雜度可達O（NlogN），其中N為三角網格中三角面片的個數，如果對于一個106-107量級的三角形面片數量來表達的模型表面，網格重構將會是非常耗時的過程［11］。將哈希算法應用于數據的處理已經在一些研究中進行了應用，其期望時間復雜度為O（1）級。文中介紹一種基于全域哈希算式的模型重構算法，并對其進行理論和實驗性質的比較。

2 哈希算法

2.1 哈希算法

哈希表法又稱為散列表法，它是直接尋址法的改進算法，既保留了直接尋址法操作數據效率高，又解決了直接尋址法中占用內存空間過大，大量直接尋址表中空間被浪費的問題。其基本思想是：將需要操作的每條數據存儲在內存中，每條數據的存儲地址都有一個唯一與之相對應的關鍵字（key），所有需要處理數據的關鍵字組成一個動態(tài)集合S，將S中的每一個元素經過哈希函數運算得到一個函數值，函數值對應的時哈希表中的槽位。

對于哈希算法來說，在進行關鍵字集合的映射運算時，會存在一個潛在的問題，即不同的關鍵字，再經過哈希函數的運算后，會被分配到同一個槽位，我們稱之為“沖突”。為了解決沖突，在哈希表中引入了鏈式存儲結構，即在發(fā)生沖突的槽位中，生成一個數據鏈表，將沖突數據存儲在鏈表中，鏈表法的引入解決了沖突的存儲問題。常用的哈希函數構建方法有：除法散列法、平方取中算法、乘法散列法、加法散列法等。

對于哈希算法的評價原則是：

（1）哈希運算速度快。

（2）減少沖突的發(fā)生。

（3）減小哈希表的裝填因子。

理論上不存在一個哈希函數使得關鍵字集合能夠完全獨立的分布在哈希表中，但是好的哈希函數應該使哈希運算結果能夠盡量滿足簡單均勻哈希假設：每個數據所對應的關鍵字都等可能的映射到哈希表中任何一個槽位中，且該映射于其他數據是否已經映射到此槽位無關，滿足等可能和獨立性要求。

2.2 全域哈希算法

全域哈希算法是哈希函數構建時一種特殊的算法。對于任意一個精心構建的特定數據組的關鍵字，通過哈希運算可能將全部數據映射到同一個槽中，使得操作時間變?yōu)镺（n）。任何一個已經選定的哈希函數都會出現這種最壞運算狀況，為了針對這種情況發(fā)生，在進行哈希運算時，隨機的從全域哈希函數集中選擇一個獨立于數據組的哈希函數，對數據組關鍵字進行哈希運算，這種隨機化的操作，避免了會發(fā)生最壞情況的算例。通過全域哈希算法運算，對于任何一個從全域哈希函數集中選出的函數h（x），將數組中n個數據所對應的關鍵字映射到容量大小為m的哈希函數表中，并用鏈表法解決沖突，對于任何一個關鍵字k，其發(fā)生沖突的期望次數小于n/m。

3 全域哈希數據冗余處理算法的實現

3.1 已有函數分析

在文獻7中，Glassner介紹了三角網格重建的哈希函數算法如式（1）所示。

式中：（int）進行數據類型轉換，將浮點數小數部分刪除；α、β、γ—哈希函數系數，取3、5、7；X、Y、Z是三角面片中頂點的坐標；Q—精度系數，表示取頂點坐標小數點后的位數，例如精度等級取3，Q=103；M—哈希表的大小，通常取2k個，便于快速取余；%—取余操作。

對式（1）進行實驗驗證，設置Q=103（文獻所?。?，程序運行后，結果如圖3所示，得到的鏈表長度非常大。為了實驗算式中所取參數對求解結果的影響，取Q=107進行驗證，結果有了很大的改善（如圖4）。又通過對哈希函數系數α、β、γ的改變和面片數量不同的模型文件進行實驗（圖4、圖5），證明該函數不僅依賴于頂點坐標精度的求解，也依賴于系數的選取和模型數據量的大小。圖3-5為在不同參數和不同數據量模型下哈希表中鏈表長度圖形。通過對上述哈希函數的分析，在算法1函數中，頂點坐標數據精度和系數的選擇對于頂點坐標處理結果有很大影響。

圖4 算法1鏈表長度與數量曲線圖Fig.4 Algorithm-1 Length and Quantity Graph of Linked List

圖5 算法1鏈表長度與數量曲線圖Fig.5 Algorithm-1 Length and Quantity Graph of Linked List

3.2 全域哈希算法設計

3.2.1 頂點坐標求和計算

為了改進算法1存在的不足，在原來函數運算的基礎上，利用全域哈希函數的構造思想，在系統(tǒng)運行時，根據系統(tǒng)當前運行時間，構造一組隨機數列，隨機的在數列中先用一個數，用這個數來構造哈希函數，參與哈希運算，該函數為隨機函數，避免了靜態(tài)哈希函數對特定模型計算中，產生大量沖突的問題，用于對模型數據的處理，減少沖突發(fā)生的概率，提高哈希運算的效率。

式中:X′、Y′、Z′—頂點的轉換坐標；α、β、γ—哈希函數的系數；C—一個比例系數，取232-M，M—哈希表的大小。

3.2.2 坐標變換

如果已知頂點坐標的范圍，那么頂點坐標可以利用下列公式轉換到（0，1）區(qū)間中：

式中：Xmax和Xmin—坐標最大值和最小值，但在實際運算過程中往往是不可知的。對于未知范圍的坐標，使用下列公式：

式中：K—一個參數，它決定了這個變換的非線性，K＞0.

通過上面這個公式，可以把X的任意坐標值轉換到區(qū)間（0，1）中，而不需要為了尋址Xmax和Xmin而遍歷整個模型文件，這個公式也可以用于頂點Y軸和Z軸方向的坐標轉換。

3.2.3 構造哈希函數

根據求得的值Keyvalue作為這個頂點的鍵值，利用全域哈希算法，求得其在哈希表中的索引值。

所利用的一種經典全域哈希構造方法，其構造過程如下：將Keyvalue值分解為r+1位，Keyvalue={k0，k1，…，kr}，其中0≤ki≤m-1。分解的思想是把Keyvalue用m進制表示，算法是不斷讓Keyvalue對m進行取余。ki表示其中的一位，定義k0為最低位。第一次把Keyvalue對m取余，得出第一位，即最低位k0。然后將Keyvalue除以m的商，再用來對m取余，然后再把商除m，依次循環(huán)下去，把Keybalue分解為r+1位。哈希集合的選取取決于隨機數，隨機選取一個數a，將a同樣的用m進制表示為r+1位，即a={a0，a1，a2…ar}，其中0≤ai≤m-1。

哈希函數為：

將Keyvalue的每一位與a的每一位相乘之后再相加，然后再對鏈表長度m取余。將每一個頂點坐標依據此算法進行求解，即可得到每個數據在哈希表中的槽值。其中m為哈希表的長度。

哈希表長度一般取決于需處理模型數據中三角形頂點個數，在STL文件中，每個頂點被存儲約為6次，即頂點數為三角形面片數目N的2倍。為了減少處理模型頂點坐標時發(fā)生沖突的概率，取裝載因子f=0.5，也就意味著鏈表的長度為模型中三角面片數量的一半。根據計算機內部處理數據的原則，一般取哈希表的長度為質數，即哈希表長度N/4≤m≤N/2，這樣可以提高算法的運算效率。

3.3 函數性能測試指標

由于實驗測試中涉及到不同的算法，對算法質量進行評價采用以下指標：

（1）鏈表的平均長度

（2）鏈表最大長度

（3）檢索復雜度—即在對模型文件中頂點坐標數據進行處理時，在鏈表中檢索的總項數。

求上述兩個哈希函數的指標值，特性較好的函數指標應得到較小的值。為了比較算法1（Glassner所提出的函數）和算法2（文中所求的哈希函數）的性能，采用以下相對標準來進行比較：

鏈表平均長度比：用系數ν來表示鏈表平均長度的比值

鏈表最大長度比：用系數η來表示鏈表最大長度的比值

檢索復雜度比：檢索復雜度計算表示的是在哈希表中檢索一個元素所需的時間長度。如果檢索鏈表的長度為i，檢索時，鏈表內所有的元素都倍檢索到，我們就需要訪問鏈表i次，當長度為i的鏈表有Ni個時，那么對這個鏈表所有訪問次數為iNi。

從鏈表中檢索一個頂點有三種可能情況（已確定頂點在哈希表中的槽值）：

（1）鏈表為空，頂點沒有被保存到鏈表中，那么這次操作所消耗的時間Q1=0；

（2）鏈表不為空，且頂點也沒有被保存到鏈表中，需要訪問鏈表中所有數據，因此這次操作所消耗的時間Q2=i。

（3）鏈表不為空，且頂點已經保存到連中，為了找到這個頂點，平均只有一半的鏈表被檢索訪問，此次操作的時間為Q3=i/2。

指標三可表示為：

所以：

式中：imax—最大鏈表長度，i—鏈表長度，Ni—長度為i的鏈表的個數，DV—模型中頂點的數量，與以上兩個指標相比，指標三能更好的反映函數的質量特性。

我們引入δ表示兩個哈希函數檢索復雜度的比值：

4 實驗結果

利用Visual Stadio軟件對算法1和算法2進行C語言編程，對21個頂點數量不同的模型文件進行實驗。其中圖1和圖2是用于測試的典型模型文件。圖1是一個下體殘肢模型文件，圖2文件是一款健身儀器底座模型。表1和表2分別統(tǒng)計了算法1和算法2采用不同參數對這兩個模型的運算結果。本實驗選取K=10作為系數進行運算分析。

圖1 燈罩Fig.1 Lampshade

圖2 機器底座Fig.2 Machine Base

圖7 算法2鏈表長度與數量曲線圖Fig.7 Algorithm-2 Length and Quantity Graph of Linked List

算法1運算實驗結果分析：在表1和圖3、4、5中分別列出了算法1在取不同參數下對不同模型文件進行頂點篩選處理的結果。從以上圖表中可以看出，在算法1的處理結果中，最大鏈表長度和平均鏈表長度分布情況不穩(wěn)定，數值較大，在實際的運行中將會消耗大量的運行時間。

表1 算法1取不同參數對不同模型的運算結果Tab.1 The Results of Algorithm-1 for Different Models With Different Parameters

算法2運算實驗結果分析：表2和圖6、7中分別列出了算法2在取不同參數下對不同模型文件進行頂點篩選處理的結果，鏈表長度與鏈表數量的關系圖，從圖上可以看出，曲線偏差不大，說明α、β、γ的取值對運算結果的影響不大，且鏈表數量隨鏈表長度的增大而減小，線性程度好。

圖6 算法2鏈表長度與數量曲線圖Fig.6 Algorithm-2 Length and Quantity Graph of Linked List

表2 算法2取不同參數對不同模型的運算結果Tab.2 The Results of Algorithm-2 for Different Models With Different Parameters

圖8為算法1和算法2對不同模型數據處理結果中最大鏈表長度和三角面片數量的對應關系圖，并給出了兩種算法下的最佳參數。

圖8 最大鏈表長度與三角面片數量關系圖Fig.8 Graph of Relationship Between Maximum Length of Linked List and Number of Triangular Faces

圖9為兩種算法對不同模型處理結果，從圖中可以看出，在對于不同的模型，算法的運算結果各有優(yōu)劣，但是可以看出算法2在大多數情況下都能得到更好的結果。圖10為兩種算法對不同數據模型檢索復雜度的比值，從圖中可以看出，算法2整體上要優(yōu)于算法1，而且其時間復雜度一直保持在一個穩(wěn)定的范圍內，除去三個異常模型處理結果，可以算出檢索復雜度比值的平均值為1.45.

圖9 指標ν和指標η與三角面片數量關系圖Fig.9 Graph of Relationship Between Indicators ν and η and Number of Triangular Facets

圖10 檢索復雜度比值與三角面片數量關系圖Fig.10 Graph of Relationship Between The Complexity Ratio and The Number of Triangles

從算法1和算法2對21個模型數據的處理結果以及最大鏈表長度、平均鏈表長度和檢索復雜度三個指標的對比結果可以看出，算法2的三個指標變化率很小。

5 結論

針對在STL模型文件重構拓撲關系中，模型文件頂點重復存儲和檢索困難等問題，利用全域哈希算法的思想，設計了一個新的哈希函數，并對比已有的哈希函數進行實驗驗證?？梢缘贸?，設計的算法具有以下優(yōu)點：（1）算法中，所用參數的選取與模型屬性無相互關聯(lián)性。（2）算法運算結果穩(wěn)定，針對不同模型數據，各項指標變化不大。（3）運算結果更快，特別是對于算法1中參數Q未知或者隨機選取的情況下。在算法1中各項參數經過優(yōu)化選擇，算法2的運算結果相對于算法1，其最大鏈表長度比為65%，平均鏈表長度比為82.9%，檢索復雜度比值為1.45。④運算結果中，鏈表數量隨鏈表長度的增大而減小。