楊 峰 廖文和 戴 寧 董光雷 韓厚年 郭保蘇 孫玉春

1.南京航空航天大學，南京，210016 2.北京大學口腔醫(yī)學院，北京，100081

0 引言

近年來，隨著制造技術(shù)的飛速發(fā)展與物質(zhì)產(chǎn)品的日益豐富，如何將CAD/CAM等現(xiàn)代制造技術(shù)用于生命本身質(zhì)量的提高，逐漸得到人們更多的關(guān)注。在生物醫(yī)學領(lǐng)域，需要采用人工方法修復(fù)病損組織器官的案例日益增多，常見的需要修復(fù)的生物體有人工關(guān)節(jié)、顱頜面修復(fù)體、口腔修復(fù)體、整形外科植入體等。由于人體組織器官結(jié)構(gòu)的復(fù)雜性和臨床醫(yī)學個性化需求的多樣性，要保證修復(fù)體與病人病損部位的精確匹配，就必須進一步提高CAD/CAM的設(shè)計與制造精度。為適應(yīng)上述發(fā)展和要求，本文提出一種基于累積曲率的離散刀軌環(huán)點云數(shù)據(jù)預(yù)處理優(yōu)化算法。

1 生物修復(fù)體的數(shù)據(jù)采集、建模及制造

1.1 離散網(wǎng)格曲面與網(wǎng)格數(shù)及點云數(shù)的關(guān)系

修復(fù)體的制作主要包括三維數(shù)據(jù)采集、模型構(gòu)建和加工制造三個步驟。數(shù)據(jù)采集中得到的是許多離散的點云數(shù)據(jù)，為了提高匹配精度，在模型構(gòu)建階段往往采用離散網(wǎng)格去逼近實體模型，而在加工制造階段，為了減小因曲面造型產(chǎn)生的逼近誤差，往往直接對網(wǎng)格曲面生成刀位軌跡。離散網(wǎng)格曲面是許多空間多邊形面片對實體模型的線性逼近，多邊形面片的疏密決定了逼近精度的高低，同時會影響精確刀位軌跡的質(zhì)量和生成效率。離散網(wǎng)格曲面通常采用截面線法直接生成刀位軌跡［1－2］，該方法以曲面每一層的二維截面輪廓點云數(shù)據(jù)為基本元素，通過對其進行等距、連接、過渡等幾何處理得到刀位軌跡。在模型構(gòu)建時，為了更精準地表示實物模型的細節(jié)信息，總是希望多邊形面片密度越大越好，這樣在二維截面輪廓生成過程中，就會獲取到大量的高精度點云數(shù)據(jù)。圖1a中的牙齒模型由6312個三角面片構(gòu)成，可以很好地反映實體模型的細節(jié)信息；圖1b中的牙齒模型由631個三角面片組成，基本可以反映實體模型的整體信息，但部分細節(jié)信息已經(jīng)失真；圖1c為該模型某二維截面輪廓；圖1d為圖1c的細節(jié)放大圖，其中點云數(shù)據(jù)分布非常密，很多點都是冗余的。然而，龐大的輪廓點云數(shù)據(jù)量會給輪廓曲線的等距、過渡等后續(xù)處理及刀位數(shù)據(jù)輸出帶來嚴峻的挑戰(zhàn)，最終造成許多較短的、不規(guī)則的加工路徑出現(xiàn)，導(dǎo)致加工過程中的頻繁抬刀及刀具在軌跡突變處的振動，勢必降低加工精度和效率，這一點在高速加工中尤其顯著。圖2所示為點云數(shù)據(jù)對等距的影響。圖2a為原始輪廓數(shù)據(jù)的等距效果圖，圖2b為圖2a的局部放大圖，不難看出，過密的點云等距后會出現(xiàn)很多難處理的自交等不規(guī)則現(xiàn)象?？梢?，高密度的點云數(shù)據(jù)并不總是必要的，相反，稠密的點云數(shù)據(jù)不僅會影響后續(xù)相關(guān)幾何處理的精度和效率，而且會造成加工中的許多問題。因此，計算機輔助制造模塊在生成二維截面輪廓后，為提高精度，需要適當?shù)貜慕孛孑喞c云數(shù)據(jù)中抽取對模型加工有用的信息，并按照一定的原則對輪廓曲線進行光順處理，才能生成較好的刀位軌跡，從而滿足加工要求。

圖1 網(wǎng)格數(shù)量對離散網(wǎng)格曲面的影響

圖2 點云數(shù)據(jù)對等距的影響

1.2 離散網(wǎng)格曲面點云數(shù)簡化方法

有關(guān)點云數(shù)據(jù)簡化的方法很多，主要有：包圍盒法、平均距離法、基于曲率的簡化方法、三維柵格細分法。大部分簡化方法都用于曲面造型中，而對于二維截面輪廓點云數(shù)據(jù)的簡化，最常用的是基于曲率的簡化方法。Teh等［3］用計算點的離散曲率來刪除冗余點，直接以點到對邊的距離h除以對邊的長度L作為近似曲率。該方法可有效去除冗余點，但當原始曲線變化比較緩慢時，有可能會誤刪除一些有效的特征點而產(chǎn)生過大的累積誤差或者錯誤。Hamann等［4］在簡化平面圖形和數(shù)字化模型的基礎(chǔ)上，提出將圖形中的曲線因子進行分段，通過計算局部區(qū)域的曲線曲率值來選取保留的數(shù)據(jù)。該方法的缺點是點云數(shù)據(jù)簡化的效率受選取的點云數(shù)目制約，也和最終的誤差閾值有關(guān)。Martin等［5］采用先把所得的數(shù)據(jù)點進行均勻網(wǎng)格劃分，再從每個網(wǎng)格中提取樣本點組成優(yōu)化點云鏈的方法實現(xiàn)數(shù)據(jù)精簡。該方法精簡效率高，但對物體外形尺寸和曲率變化不敏感。平均距離精簡法［6］容易丟失細節(jié)信息，一般用于掃描線形式的點云數(shù)據(jù)。

1.3 離散網(wǎng)格曲面曲線光順方法

傳統(tǒng)的曲線光順方法大致分為整體光順法和局部光順法。Liu等［7］給出了不帶約束的全局優(yōu)化光順法，而文獻［8］給出了帶約束的全局優(yōu)化光順法。全局優(yōu)化光順方法的優(yōu)點是可以一次完成對曲線的光順，缺點是一次光順的點太多，計算量大，難以保證個別壞點的特殊修正。同簡化方法類似，光順處理大多基于CAD研究，因計算繁冗，故二維截面輪廓的光順多采用局部光順法。Liu等［9］提出了一種離散曲率（D－curvature）光順算法，并開發(fā)了相應(yīng)的自適應(yīng)算法。該方法利用尋優(yōu)函數(shù)的約束確定壞點的修正量，但因其沒有限制修正量的閾值，故其曲率難以滿足加工精度的要求。Farin等［10］用繪制曲線曲率圖的辦法，人為地判斷曲線的光順程度，并指出需要修改的點，該方法直觀易行，但人工交互繁雜耗時，且受屏幕分辨率的影響較大。Renz［11］用直接計算點列的一階和二階差分方法人為地判斷壞點，并對其進行光順，該方法的不足是沒有考慮點的均布問題。

2 離散曲率的相關(guān)技術(shù)定義

2.1 點云數(shù)據(jù)的離散曲率

平面曲線的曲率計算公式為

本文把曲率計算轉(zhuǎn)化為三角形內(nèi)邊的計算，并提出通過直線方程判斷曲率正負號的離散曲率計算方法。如圓逼近法求曲率，是通過相鄰3個點Pi－1，Pi，Pi＋1的圓來近似Pi點的密切圓，如圖3所示。圓的曲率Ki為

圖3 點的離散曲率計算

因由離散點列組成的曲線有凹凸之分，所以點的離散曲率也有正負之分。由于式（2）中的分子部分是把點Pi的坐標直接代入對邊Pi－1Pi＋1的方程所得，所以是有正負的，且其正負直接決定點Pi的離散曲率正負。

2.2 二階中心差分、差商光順

設(shè)給定型值點列｛Pi｝（i＝0，1，…，n），則Pi的二階中心差分、差商分別為

式中，Li為由P1到Pi的累積弦長。

適用于二階差分光順和差商光順的點云分布條件如下：

（1）若點云數(shù)據(jù)分布比較均勻，則采用二階差分法光順點云數(shù)據(jù)。對于型值點Pi，調(diào)整其位置，使得Δ2Pi＝0，則可得Pi點的新位置：

（2）若點云數(shù)據(jù)分布不均勻，則需要用差商法代替差分法才能達到較好的光順效果。對于型值點Pi，調(diào)整其位置，使得f（Pi－1，Pi，Pi＋1）＝ 0，則可得Pi點的新位置：

2.3 基于光順算子和簡化算子的誤差帶控制

由于本文的研究對象是二維截面輪廓點云數(shù)據(jù)，而經(jīng)過等距、連接和過渡等幾何處理后的輪廓數(shù)據(jù)將直接作為刀位路徑用于實際加工中，所以，二維輪廓點云數(shù)據(jù)優(yōu)化的最大誤差應(yīng)控制在允許的加工誤差范圍內(nèi)。為滿足加工精度要求，提高加工效率，本文取Pi優(yōu)化后的位置為原來位置和理想位置的組合，并提出圖4所示的加工誤差帶容差δ概念。

優(yōu)化后Pi點的新位置為

圖4 加工誤差帶示意圖

式中，α為簡化算子，α∈ ［0，1］；β為光順算子，β∈ ［0，1］。

要確保加工精度，就必須使

式（6）中的容差δ由實際加工中的精度要求確定。

在優(yōu)化過程中，所有點必須在誤差帶控制范圍內(nèi)，即在圖4的優(yōu)化過程中，二維輪廓點云數(shù)據(jù)的誤差應(yīng)該控制在內(nèi)外兩條實線組成的封閉輪廓范圍內(nèi)。如果新生成的點P″i不能滿足式（6），則修改光順算子α，采用遞歸的方式，直到P″i滿足誤差帶控制要求為止。

圖5為二維截面輪廓點云數(shù)據(jù)優(yōu)化的整體示意圖，可以看出，優(yōu)化過程主要分為兩步，即先簡化，后光順。簡化分為粗簡化和精簡化兩步：如果粗簡化滿足條件，則直接進入光順處理，如果不能滿足，需要精簡化后進入光順處理。整個處理過程都在誤差帶控制范圍內(nèi)。

圖5 二維截面輪廓點云數(shù)據(jù)優(yōu)化示意圖

3 基于累積曲率的二維截面輪廓點云數(shù)據(jù)的簡化算法

理想的簡化算法總是希望用最少的點云數(shù)據(jù)表達最必要的信息，但在實際處理過程中通常根據(jù)某種簡化原則來進行。對于一個給定的點云數(shù)據(jù)，在不同的應(yīng)用領(lǐng)域有多種簡化準則，主要包括：保留數(shù)據(jù)點的個數(shù)比重、數(shù)據(jù)點間的空間距離、曲率、密度及重建誤差等準則。對于二維截面輪廓點云數(shù)據(jù)，由于優(yōu)化后的數(shù)據(jù)直接用于生成刀軌環(huán)，所以僅僅靠保留數(shù)據(jù)點的個數(shù)比重和密度等準則是難以保證其加工精度和效率的。點的離散曲率能夠較好地反映曲線的真實形狀特征，而且計算簡單直觀，可以很容易地設(shè)定曲率閾值，并和加工精度建立聯(lián)系，所以，本文算法首先引入點云數(shù)據(jù)的離散曲率作為判斷和刪除冗余點的依據(jù)。

3.1 冗余點分類

根據(jù)輪廓環(huán)等距和刀位軌跡規(guī)劃要求，二維截面輪廓中的冗余點主要分為以下兩類：

（1）中間冗余點。如果圖3中的αi→180°，即稱為中間冗余點。

（2）線段較短，短到加工精度以內(nèi)。

如圖6所示，點2、點9與相鄰兩點組成的線段所成的角接近180°，點4和相鄰點在同一條直線上，這3個點統(tǒng)稱為第一類冗余點；點5、點11、點12和相鄰兩點的距離小于加工精度值，為第二類冗余點。

圖6 冗余點分類實例

3.2 冗余點判斷準則

為滿足加工精度要求，減少優(yōu)化誤差，本文算法規(guī)定冗余點判斷準則包括基于加工精度的粗判斷和基于曲率閾值的精判斷兩步。其判斷過程如下：首先把h和加工精度δ的關(guān)系作為粗判斷條件，即如果hi＞δ，則說明該點是特征點，不能去除，因此不需進行精判斷。若hi≤δ，則進入精判斷。在精判斷中，為了有效地去除圖6中的兩類冗余點，引入曲率閾值ε的概念，若｜Ki｜＞ε，則說明該點是特征點，不能去除；反之，則說明該點是冗余點，需要去除?？梢?，使用粗精判斷相結(jié)合的準則，圖6中的兩類冗余點就可以合并為一類來處理。

3.3 累積曲率的引入和計算

二維截面輪廓是由一系列小直線段組成的曲線，當點的離散曲率變化比較緩慢時，采用3.2節(jié)的方法有可能會去除一系列連續(xù)的點，從而誤刪除有效的特征點，產(chǎn)生過大的累積誤差，造成錯誤的結(jié)果。圖7為基于離散曲率的點的簡化圖示。圖7a為原始圖，其封閉輪廓半環(huán)由11個點組成，除了起點和終點外，其他點分布均勻，即K2＝K3＝ …＝K10，假設(shè)該曲率值滿足｜Ki｜＜ε，如果采用直接判斷離散曲率的方法，則會出現(xiàn)圖4的簡化效果。圖7b為去除了前3個點的效果圖，由圖可見，這時曲線已經(jīng)偏移了原始輪廓。當遍歷到最后一個點時（圖7c），原始輪廓就變成了只有起點和終點組成的一條線段，中間所有的點都被刪除了，簡化結(jié)果明顯錯誤。

圖7 基于離散曲率的點的簡化圖示

為了避免這種由于累積誤差導(dǎo)致的簡化錯誤，本文提出累積曲率ρ的概念，把離散曲率轉(zhuǎn)化為累積曲率。當某個點確定為冗余點被去除時，其曲率累加到累積曲率中，當計算下一個點時，直接用累積曲率去和曲率閾值作比較，直到該累積曲率值滿足點被去除的條件時，ρ清零。在累加曲率過程中，曲率要加入符號位，和曲率閾值比較時，取絕對值對比。

表1是圖7a中11個點云數(shù)據(jù)的離散曲率和累積曲率計算結(jié)果，刪除標記默認值設(shè)為“1”，累積曲率默認值設(shè)為“0”，當某點被刪除時，置刪除標記位為“0”，累積曲率為累積曲率和當前點離散曲率的累加，直到累積曲率值超過曲率閾值時，當前點保留，累積曲率清零。如圖8所示，設(shè)當前曲率閾值為0.1，若只計算離散曲率，則點2到點9全部被刪除，若用累積曲率代替離散曲率，則只有點2、4、6、8、10被刪除。

表1 離散曲率和累積曲率的關(guān)系

3.4 算法描述

本文提出的基于累積曲率的點云數(shù)據(jù)簡化算法的具體實現(xiàn)步驟如下：

（1）導(dǎo)入二維截面輪廓點云原始數(shù)據(jù)Pi（i＝1，2，…，n），設(shè)累積曲率初始值ρ＝0。

圖8 離散曲率與累積曲率

（2）規(guī)定起始點為P1，此點定義為定點，定義i的初始值為i＝2，分別計算Δi，hi，li±1，Ki，ρ＝ρ＋Ki。

（3）比較hi和δ的關(guān)系，若hi≥δ，βi＝0，ρ＝0，i←i＋1，轉(zhuǎn)（2），否則，轉(zhuǎn)（4）。

（4）比較｜ρ｜和ε的關(guān)系，若｜ρ｜＞ε，則該點不是冗余點，保留，βi＝0，ρ＝0，i←i＋1，轉(zhuǎn)（2），否則，轉(zhuǎn)（5）。

（5）去除冗余點Pi，βi＝1。i←i＋1，轉(zhuǎn)（2）。

（6）i＝n時，遍歷到最后一個點，程序結(jié)束。

4 差分差商自適應(yīng)光順算法

簡化處理減少了二維截面輪廓點云數(shù)據(jù)的數(shù)量，減少了輪廓曲線在等距、連接、過渡等幾何處理中可能出現(xiàn)的一系列不規(guī)則問題，有效提高了刀位軌跡生成的速度和質(zhì)量，降低了實際加工過程中的空走刀、刀具振動等頻率。但是，僅僅從數(shù)量上對點云數(shù)據(jù)進行優(yōu)化是不夠的，因為點云數(shù)據(jù)的分布形態(tài)對刀軌生成和實際加工還有重要影響。例如，如果點云數(shù)據(jù)分布曲率波動較大，很容易造成等距等幾何處理后點云排列不均勻，容易產(chǎn)生多處自交等不規(guī)則現(xiàn)象，從而不能保證刀軌生成的質(zhì)量。因此，還需要對簡化后的二維截面輪廓點云數(shù)據(jù)做光順處理，以使輪廓在加工精度范圍內(nèi)滿足光順要求。

差分差商方法主要是針對點云數(shù)據(jù)的分布均勻與否來使用的。由于加工對象的形態(tài)各異，二維截面輪廓中點云數(shù)據(jù)的均布程度都是未知的，結(jié)合差分差商在曲線光順中的應(yīng)用，本文提出差分差商自適應(yīng)光順算法。記

式中，Ln為由P1到Pn的累積弦長為P1到Pn的累積弦長的平均值。

對于Pi（i＝0，1，…，n），記

式中，σi為定義的點云數(shù)據(jù)均布系數(shù)，σi越小，說明型值點分布越均勻。

加入判斷條件，若σi＜σ，則采用差分法計算點云數(shù)據(jù)的新位置；若σi≥σ，則采用差商法計算點云數(shù)據(jù)的新位置。其中，σ為定義的均布因子，本文取σi的中值作為σ。

二維截面輪廓點云數(shù)據(jù)差分差商自適應(yīng)光順算法的流程如圖9所示。首先給定點云數(shù)據(jù)并定義點的坐標Pi，計算相鄰點的弦長li、所有點的累積弦長Ln以及平均值，然后計算各點的均布系數(shù)σi，并依據(jù)此均布系數(shù)確定所有點的均布因子σ，比較σi和σ，若σi＜σ，代入式（3）計算新位置點，反之，代入式（4）計算新位置點，并通過式（5）求得差分或差商計算后新位置點的坐標P″i。最后代入式（6），判斷新點是否滿足誤差帶容差δ，如果不滿足，修改光順算子α，重新代入式（5），直到滿足給定的光順容差，程序結(jié)束。

圖9 差分差商自適應(yīng)算法流程圖

5 實例分析

本文算法已應(yīng)用于Dental Engineer軟件中，用圖10中的磨牙冠模型（12.2mm×11.4mm×5.7mm）驗證該算法的有效性。分別取其3個不同高度的二維截面輪廓為研究對象，對其上的點進行優(yōu)化，并分別繪制了原始輪廓、優(yōu)化效果圖、10次等距后的效果圖，以及簡化及優(yōu)化后點的離散曲率輸出圖。表2分別記錄了3個輪廓環(huán)優(yōu)化前后點的個數(shù)、等距一次產(chǎn)生的自交點及等距10次所用的時間。

在圖11的二維截面輪廓的簡化和等距效果圖中，圖11a－1、圖11b－1、圖11c－1分別是磨牙冠模型z＝2.136、z＝2.413、z＝1.986的原始二維截面輪廓圖，圖11a－2、圖11b－2、圖11c－2分別是ε＝0.01時的優(yōu)化效果圖，可見，優(yōu)化后點的數(shù)目明顯減少，曲線變得更加光滑。圖11a－3、圖11b－3、圖11c－3分別是原始輪廓優(yōu)化后連續(xù)等距10次之后對應(yīng)的效果圖，可見，優(yōu)化等距后的輪廓質(zhì)量明顯提高，刀軌環(huán)變得更加光滑。

圖10 磨牙冠模型及3個截平面

圖11 二維截面輪廓的簡化和等距效果圖

圖12 二維截面輪廓簡化、優(yōu)化離散曲率輸出圖

圖12為二維截面輪廓簡化、優(yōu)化離散曲率輸出圖。圖12a－1、圖12b－1、圖12c－1分別是3個二維截面輪廓在ε＝0.02時的優(yōu)化效果圖，通過和圖11對比可以看出，ε越小，刪除的冗余點越少。圖12a－2、圖12b－2、圖12c－2分別是3個輪廓簡化及優(yōu)化后點的離散曲率輸出圖，可見：優(yōu)化算法使點的離散曲率變化更加均勻，多余奇異點和拐點基本消失，曲率極值點減少，保證了輪廓數(shù)據(jù)二階導(dǎo)數(shù)的連續(xù)性，從而確保了加工過程中走刀的穩(wěn)定性和光順性。

令α＝0.1，δ＝0.15，ε＝0.02，表2示出了優(yōu)化前后各輪廓環(huán)點的數(shù)目、等距1次需要去除的自交點的個數(shù)和等距10次的時間。由表2的試驗結(jié)果可見：通過優(yōu)化處理，使得輪廓環(huán)點云的數(shù)目明顯減少，需要去除的自交點的數(shù)目也減少，節(jié)省約一半的等距時間，有效提高了等距等后續(xù)處理的效率，從而提高了刀軌環(huán)的生成和加工效率。

表2 優(yōu)化前后二維截面輪廓數(shù)據(jù)對比

6 結(jié)論

本文提出了基于累積曲率的離散刀軌環(huán)預(yù)處理優(yōu)化算法。該算法將累積曲率的簡化分為粗簡化和精簡化兩步，粗簡化保證簡化不超出規(guī)定的誤差帶，精簡化則確保有效去除冗余點，避免因累積誤差導(dǎo)致的非冗余點的誤刪除。簡化算法使二維截面輪廓點的數(shù)量大大減少，節(jié)省了刀位軌跡生成時間，提高了加工效率。差分差商自適應(yīng)光順算法在誤差帶控制范圍內(nèi)實現(xiàn)二維截面輪廓點的離散曲率均勻化，并保證其二階導(dǎo)數(shù)的連續(xù)性，減少了等距過程中自交點分布不均等不規(guī)則現(xiàn)象，縮短了計算及處理自交區(qū)域的時間，提高了刀位軌跡的質(zhì)量，改善了產(chǎn)品的加工性能。

［1］Park S C.Sculptured Surface Machining Using Triangular Mesh Slicing［J］.Computer Aided Design，2004，36（3）：279－288.

［2］Reb Y F，Yan H T，Lee Y S.Clean－up Tool Path Generation by Contraction Tool Method for Machining Complex Polyhedral Models［J］.Computers in Industry，2004，54（1）：17－33.

［3］Teh C H，Chin R T.On the Detection of Dominant Points on Digital Curves［J］.IEEE Trans.Pattern Anal.Mach.Intell.，1989，11（8）：859－872.

［4］Hamann B，Chen J.Data Point Selection for Piecewise Linear Curve Approximation［J］.Journal of Computer Aided Geometric Design，1994，11：289－301.

［5］Martin R R，Stroud I A，Marshall A D.Data Reduction for Reverse Engineering RECCAD Deliverable Document 1.COPERUNICUS Project［J］.Computer and Automation Institute of Hungarian Academy of Science，1996，1068：63－69.

［6］劉德平，陳建軍.逆向工程中數(shù)據(jù)精簡技術(shù)的研究［J］.西安電子科技大學學報（自然科學版），2008，35（2）：334－339.

［7］Liu L，Tai C L，Ji Z，et al.Non－iterative Approach for Globle Meth Optimization［J］.Computer Aided Design，2007，39（9）：772－782.

［8］Hildebrandt K，Polthier K.Constraint－based Fairing of Surface Meshes［C］//Proceedings of the Fifth Eurographics Symposium on Geometry Processing.Barcelona，2007：50－62.

［9］Liu G H，Wong Y S，Zhang Y F.Adaptive Fairing of Digitized Point Data with Discrete Curvature［J］.Computer Aided Design，2002，34：309－320.

［10］Farin G，Spaidis N.Curvature and the Fairness of Curves and Surfaces［J］.IEEE Computer Graphics Applications，1989，9（2）：52－57.

［11］Renz W.Interactive Smoothing of Digitized Point Data［J］.Computer Aided Design，1982，14：267－269.