基于二分法的3D打印切片數(shù)據(jù)精簡

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

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

0 引言

3D打印技術(shù)出現(xiàn)于20世紀90年代中期，也稱快速成型技術(shù)，可通過逐層打印高效地將數(shù)字化的三維模型構(gòu)造成具體物體。3D打印將傳統(tǒng)的減材制造模式轉(zhuǎn)變?yōu)樵霾闹圃炷Ｊ?，不僅完全打破了物體結(jié)構(gòu)復雜性的限制，也促進了個性化服務與生產(chǎn)社會化的發(fā)展，更加推動了3D數(shù)字化相關(guān)技術(shù)的發(fā)展與創(chuàng)新[1]，被廣泛應用于工業(yè)設(shè)計、汽車、航空航天和醫(yī)療等領(lǐng)域[2]。

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

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

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

1 算法原理

1.1 傳統(tǒng)角度弦高法

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

圖1 傳統(tǒng)角度弦高法基本原理

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

1.2 二分法

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

1.3 本文方法

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

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

圖2 本文方法精簡原理圖

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

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

圖3 本文算法流程圖

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

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

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

步驟4：將數(shù)據(jù)點{Pi,Pi+1,…,Pi+w-1}作為一個簇，并將線段PiPi+w-1作為基線，計算簇內(nèi)的每個點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為保留點，該簇內(nèi)的其余點為冗余點，并令i=i+w-1后，轉(zhuǎn)步驟7；否則，令w=[w/2]后，轉(zhuǎn)步驟4。

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

2 實例驗證

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

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

圖4 數(shù)據(jù)精簡效果對比

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

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

3 結(jié)論

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