基于二分法的3D打印切片數據精簡

潘成鋼，吳婷，陳廷豪，吳建，包涵，吳廣慶

（嘉興學院 機電工程學院，浙江 嘉興 314001）

0 引言

3D打印技術出現于20世紀90年代中期，也稱快速成型技術，可通過逐層打印高效地將數字化的三維模型構造成具體物體。3D打印將傳統的減材制造模式轉變為增材制造模式，不僅完全打破了物體結構復雜性的限制，也促進了個性化服務與生產社會化的發展，更加推動了3D數字化相關技術的發展與創新[1]，被廣泛應用于工業設計、汽車、航空航天和醫療等領域[2]。

目前，3D打印處理的主流對象模型是STL三角網格模型，由于STL模型表面由大量三角面片組成，這些三角面片會導致模型的各層切片輪廓產生許多微小線段，大量的微小線段不僅會占用較大的存儲空間，也會造成打印噴頭的不斷振動，最終影響3D打印的效率和平穩性[3]。因此，在打印加工前需要對這些切片輪廓進行優化精簡處理，以提高模型制造的效率和精度。

數據精簡是一種剔除冗余信息的數據處理方法，其目的在于盡可能利用最少的數據點完整而準確地表達物體的原有信息，并在此基礎上達到更高的運行效率[4]。傳統數據精簡的方法包括最大（小）距離法、弦高法、角度偏差法和曲率法等。目前，已有眾多學者改進了現有的數據精簡算法，取得了一定的研究成果。俞毅等[4]提出一種改進的角度偏差數據精簡方法，該方法利用數據點的曲率變化，將角度閾值變成一個能隨數據點曲率自動調整的函數，并聯合最小距離法設定距離閾值，對大于閾值的數據點進行保留。吳鳳和等[5]通過分析物體輪廓曲線的曲率變化，提出一種曲率弦高精簡方法，該方法通過相鄰數據點間的曲率比，建立變化的弦高閾值函數，從而更好地保留曲率較大位置處的特征點。李新等[6]改進了傳統的角度弦高聯合方法，該方法將掃描線上某個數據點的角度和弦高都小于閾值的點判斷為冗余點，并在進行下一個數據點的判斷時，重新計算該冗余點到新基準的角度和弦高，以進一步精判斷，從而防止累計誤差的產生。Liu等[7]提出離散曲率光順的方法，通過分析二維點集離散曲率和一階曲率差分的性質來識別缺陷點，并通過構造能量函數來修改缺陷點的幾何位置。

本文在已有數據精簡方法的基礎上，提出基于二分迭代的角度弦高數據精簡方法。該方法以曲線上數據點之間的角度和弦高為依據，通過二分迭代，確定所需要保留的數據點，以此加快數據精簡的效率。

1 算法原理

1.1 傳統角度弦高法

角度法與弦高法通過確立測量點的基線，求得測量點與基線的角度和垂直距離，來衡量相鄰輪廓數據點的方向和曲率變化程度。如圖1所示，在判定一條輪廓上某點Pi是否為冗余點時，將其與前后的兩點Pi-1、Pi+1相連，組成一個三角形，計算點Pi到基線Pi-1Pi+1的高hi及角度αi，若hi和αi小于設定的閾值，則可將Pi視為冗余點。在判斷下一個點Pi+1時，為避免產生累積誤差，若Pi為冗余點，則除了計算點Pi+1的弦高hi+1_1和角度αi+1_1，還應計算冗余點Pi到新基線的弦高hi+1_2和角度αi+1_2，若這些值均小于閾值，則Pi+1才能被視為冗余點。

圖1 傳統角度弦高法基本原理

可以看出，這種方法在計算待測點的角度和弦高時，需要利用待測點前后的數據點，因此需要反復計算待測點和冗余點到基線的弦高與角度。對于3D打印工藝而言，這一方法的計算量大，不適應具有大量切片與復雜輪廓的數據精簡。

1.2 二分法

二分法，也叫折半查找法，是一種在指定數據區間內查找指定元素的搜索算法。它通過不斷對分數據區間，將不可能的解集排除在外，來得到滿足誤差條件的近似解[8]。假設函數f(x)在區間[a, b]內單調遞增，若需要查找指定元素X，使得f(X)=Y，則首先將區間[a, b]進行對分，從[a, b]的中點c開始搜索，若f(c)=Y，則查找成功，即c=X；若f(c)＜Y，則在前半段的區間[a, c]里查找；若f(c)＞Y，則在后半段的區間[c, b]里查找，重復上述步驟，直到找到近似解為止。

1.3 本文方法

3D打印切片層數較多，因此對切片輪廓數據的精簡不僅要考慮到算法的運行效率，也要考慮到閾值參數的方便設定?；谡`差擬合的方法耗時較多，而基于曲率的方法，不同輪廓曲率閾值的設定較為困難。因此，根據切片輪廓數據分布特點和減少計算過程迭代次數的原則，本文提出一種將曲線的角度、弦高與二分法相結合的方法，即二分迭代的角度弦高精簡方法。該方法將切片輪廓數據上若干個連續數據點作為一個簇，在這個簇中計算各數據點的角度與弦高，通過對簇的點數不斷進行二分迭代來確定保留的數據點。

對于切片輪廓上排列有序的數據點集，如圖2所示，以某一點Pi為基點，將數據點{Pi, Pi+1,…, Pi+w-1}作為一個簇，以PiP(i+w-1)為基線，計算簇內的每個點到基線PiPi+w-1的角度和弦高，求出這些角度和弦高的最大值αmax、hmax。若hmax和αmax均 小于閾值，則Pi和Pi+w-1為保留點，并以點Pi+w-1為基點，繼續進行下一個簇的判斷；若hmax和αmax有一個大于閾值，則將此簇的點個數w通過二分法重新聚類，即

圖2 本文方法精簡原理圖

其中，[]為向上取整運算，然后對二分后的簇內數據點的角度和弦高重新進行計算。

本文方法的整個流程如圖3所示。

圖3 本文算法流程圖

步驟1：讀取切片輪廓數據{P1,P2, …,PN}，設定角度閾值Δα和弦高閾值Δh，以及每組簇的初始點個數w0。

步驟2：選取輪廓數據中的第一個數據點P1為起點，定義i的初始值i=1。

步驟3：判斷i＞Nw0+1是否成立，若成立，則令w=N-i+1，否則，令w=w0。

步驟4：將數據點{Pi,Pi+1,…,Pi+w-1}作為一個簇，并將線段PiPi+w-1作為基線，計算簇內的每個點Pj（j=i+1,i+2, …,i+w-2）到基線的角度αj和弦高hj。

步驟5：計算角度的最大值αmax=max{αj}和弦高的最大值hmax=max{hj}。

步驟6：判斷αmax＜Δα和hmax＜Δh是否同時成立，若成立，則Pi和Pi+w-1為保留點，該簇內的其余點為冗余點，并令i=i+w-1后，轉步驟7；否則，令w=[w/2]后，轉步驟4。

步驟7：判斷是否滿足條件i＜N，若滿足，轉步驟3；否則，該層切片輪廓線上的所有數據點均處理完畢，將所有保留的數據點作為精簡后的數據輸出。

2 實例驗證

為驗證本文算法的有效性，選取一梅花形狀的切片輪廓進行精簡測試。原始梅花輪廓數據點共有628個點，通過控制每組簇內點個數w0、角度閾值Δα和弦高閾值Δh，從精簡率、重構曲線平均誤差等指標來對簡化結果進行評價。

在每組簇內點個數w0=20，不同角度閾值Δα和弦高閾值Δh的參數條件下，精簡效果如圖4所示。從精簡后的曲線圖可以發現，本文方法能夠在高曲率變化處保留較多的數據點，而且在低曲率片段中也能保留較多細節的特征點，可見本文方法能夠利用較少的離散點較好地表示復雜原有輪廓信息，總體結果疏密有秩，精簡效果較好。另外可以發現，隨著Δα和Δh的減小，精簡后的數據點會不斷增多。當Δα=5°、Δh=0.05時，精簡率為76%，重構曲線平均誤差為0.012；當Δα=2°、Δh=0.02時，精簡率為58%，重構曲線平均誤差為0.0032。因此，通過控制Δα和Δh的大小，可以控制精簡結果。

圖4 數據精簡效果對比

圖5顯示了在Δα=5°、Δh=0.05的條件下，簇內點個數w0大小的變化對精簡率和算法執行時間的影響?？梢钥闯觯?≤w0≤10時，精簡率呈上升趨勢，當w0≥15，精簡率結果趨于穩定；而算法耗時隨w0的增大而增大。因此，在實際應用中，考慮到算法的執行效率，w0取值范圍在10～20時較為合適。

圖5 簇大小對精簡率和耗時的影響

3 結論

本文提出基于二分法的數據精簡方法，有效實現了3D打印切片輪廓的數據精簡。該方法以曲線上相鄰點之間的角度與弦高為依據，通過簇內點數的二分法迭代來確定需要保留的數據點，完成數據的精簡工作。實驗測試結果表明，該方法能夠較高效且穩定地完成切片輪廓的數據精簡，其結果疏密有致，精簡效果較好。