劉 平 ，何雪明

1.江蘇省食品先進(jìn)制造裝備技術(shù)重點(diǎn)實驗室，江蘇 無錫 214122

2.江南大學(xué) 機(jī)械工程學(xué)院，江蘇 無錫 214122

1 引言

在人工智能、數(shù)控加工、實體造型和科學(xué)可視化等方面曲面求交技術(shù)應(yīng)用十分廣泛[1-2]。在基于逆向工程模型重建的過程中，高精度曲面求交是相鄰曲面成功拼接的前提，參數(shù)曲面間常用的求交方法[3]有網(wǎng)格離散法[4-5]、分割法[6-7]、迭代法和追蹤法[8]四種。其中網(wǎng)格離散法使用范圍較廣，通用性強(qiáng)，但求交過程中需要將整張曲面細(xì)密劃分，若曲面較大，計算耗時增加明顯；分割法是對網(wǎng)格離散法做出優(yōu)化，將其求交過程中整張曲面的網(wǎng)格劃分轉(zhuǎn)變?yōu)閮H對曲面間需要求交的部分進(jìn)行劃分，求交時間顯著縮短。迭代法不能單使用，必須存在交點(diǎn)初值且該值必須盡可能的準(zhǔn)確，初值選擇不恰當(dāng)會導(dǎo)致收斂不及時從而無法得到滿足精度要求的交點(diǎn)，導(dǎo)致穩(wěn)定性較差。追蹤法是已知一個交點(diǎn)的確切位置，將其作為追蹤起點(diǎn)，根據(jù)交線的幾何性質(zhì)，按照一定的步長繼續(xù)搜索追蹤下一個交點(diǎn)，不斷重復(fù)這個的追蹤過程，直到追蹤到整條交線。相比其他方法進(jìn)行曲面求交，追蹤法[9]是一種人們普遍認(rèn)為曲面求交的有效方法，追蹤法的難點(diǎn)在于初始點(diǎn)獲取困難、容易漏交、不好確定合理追蹤步長。針對以上難點(diǎn)，國內(nèi)外學(xué)者進(jìn)行了大量研究。劉麗萍[10]采用包圍盒測試的方法，在分割法的基礎(chǔ)上得到了較為精確的初始點(diǎn)。史永豐[11]提出一種改進(jìn)的基于微分方程的跟蹤算法，選擇邊界點(diǎn)和拐點(diǎn)作為跟蹤的起點(diǎn)，解決了漏交問題。涂海寧[12]采用拋物線逼近交線，求取拋物線滿足條件的最大弦長，并以此弦長作為追蹤步長求取交線，但此方法只適用于具有二階連續(xù)的曲面，適用受到限制。為了保證求交精度，一般最簡單的做法是取較小的固定步長值[9]，但計算量會顯著增加，導(dǎo)致計算速度變慢。

本文提出步長可自適應(yīng)變化的優(yōu)化追蹤法，不同于傳統(tǒng)的追蹤法，該方法采用五次非均勻B樣條曲線擬合交點(diǎn)，將步長與交線末端的曲率進(jìn)行關(guān)聯(lián)，得到可依據(jù)實際求交的曲面特征而實時變化追蹤步長，適用范圍廣，求交穩(wěn)定且速度快。

2 追蹤法的基本原理

2.1 確定追蹤起點(diǎn)

追蹤起點(diǎn)選取是追蹤法求交的第一步，求取初始交點(diǎn)首先需要將兩個參數(shù)曲面轉(zhuǎn)化成一組等參數(shù)曲線和一參數(shù)曲面[13]，把參數(shù)曲面間的求交問題轉(zhuǎn)化為容易求解的參數(shù)曲線與參數(shù)曲面求交的問題。計算跟蹤起點(diǎn)，現(xiàn)以一組曲面為例，如圖1所示。

圖1 確定追蹤起點(diǎn)

在U、V方向上定義兩個參數(shù)曲面，分別為S1=S1(u1,v1)與S2=S1(u2,v2)。把曲面S1上的一條U向等參數(shù)曲線定義為C(u)，其方程可表示為C(u)=S1(u1,vˉ1)，其中參數(shù)vˉ1表示該參數(shù)是固定值。c0=S1(u10,vˉ1)是曲面S1等參數(shù)線C(u)上的一點(diǎn)，同時q0=S2(u20,v20)是參數(shù)曲面S2上的一點(diǎn)。將c0與q0之間的矢量距離表示為τ0=c0-q0，倘若設(shè)定一個精度閾值ε，當(dāng) |τ0|≤ε時，即兩個初始點(diǎn)之間的距離足夠小時，則認(rèn)為兩曲面上的兩個點(diǎn)c0與q0重合，即為兩曲面的交點(diǎn)。

等參數(shù)線C(u)=S1(u1,vˉ1)的變量為u1，曲面S2對應(yīng)的變量為u2和v2。求等參數(shù)線與曲面的交點(diǎn)，令：

對τ0=c0-q0用泰勒公式展開，忽略高次項可以得：

對上式進(jìn)行賦范空間投影，在等式兩邊分別點(diǎn)乘S1u、S2u和S2v，則可以得到三個線性方程：

對方程組進(jìn)行求解，可以求出△u1、△u2和△v2。此方程組由于系數(shù)矩陣正定，所以不會出現(xiàn)分母為0和不收斂的現(xiàn)象。將u10+△u1、u20+△u2和v20+△v2代入式（2）中，如此反復(fù)迭代計算，直到 |τ0|≤ε，則可以求得U向參數(shù)線C(u)與曲面S2的交點(diǎn)。通過對點(diǎn)c0采用泰勒公式展開，并依據(jù)賦范空間投影法進(jìn)行迭代[14]。若C(u)和S2存在交點(diǎn)，c0將會在該交點(diǎn)處收斂。若C(u)和S2不存在交點(diǎn)，則點(diǎn)c0收斂于靠近S2距離最短的曲線C(u)上的一點(diǎn)，此時，尋找初始交點(diǎn)，應(yīng)選取其余等參數(shù)線。

2.2 求取下一個交點(diǎn)

在求得初始交點(diǎn)后，接下來就要進(jìn)行下一交點(diǎn)的求取，如此進(jìn)行下去，就可以求得一系列交點(diǎn)，從而得到整條交線。進(jìn)行下一個交點(diǎn)的求取，就必須知道該空間點(diǎn)的特征參數(shù)，需要對空間曲線上一點(diǎn)的幾何結(jié)構(gòu)進(jìn)行分析。

2.2.1 空間曲線在一點(diǎn)的幾何結(jié)構(gòu)

了解空間曲線上一點(diǎn)的幾何結(jié)構(gòu)，有利于精確下一個交點(diǎn)的位置。假設(shè)空間曲線c=c(s)為2 階參數(shù)連續(xù)曲線，c0=c(s0)是曲線c上的一點(diǎn)，s是弧長參數(shù)，則c0鄰近點(diǎn)可由泰勒公式展開表示為：

在微分幾何學(xué)中有：

其中，α、β和k為空間曲線c在點(diǎn)c0處的切矢、主法矢和曲率。依據(jù)切矢α和主法矢β可得到密切平面，記為Σ，進(jìn)而得到空間曲線上點(diǎn)c0的幾何結(jié)構(gòu)[15]，如圖2所示。

圖2 空間曲線上點(diǎn)的幾何特征

將式（5）代入（4）的表達(dá)式中，舍掉高次項，可以求出c(s0+Δs)的近似值，記作c′(s0+△s)：

上面式子移項則等價于：

2.2.2 追蹤下一個交點(diǎn)

在密切平面Σ上，將c0作為原點(diǎn)建立正交坐標(biāo)系，α和β矢量方向作為互相垂直的坐標(biāo)軸。在坐標(biāo)系[c0,α0,β0] 中，把c0定義為起點(diǎn)，則有：弧長參數(shù)s0=0 ；步長△s=s，相鄰點(diǎn)的坐標(biāo)可表示為：

這樣，就可以在密切平面上的正交坐標(biāo)系內(nèi)分析曲線上某一點(diǎn)處的結(jié)構(gòu)特征。從式（8）看出，計算c′(s)的值，需要求出追蹤步長s和等參數(shù)線上該點(diǎn)處的曲率k。

因為交線既在參數(shù)曲面S1中，也在參數(shù)曲面S2中，也因此可以借助兩個參數(shù)曲面的幾何特性間接獲得交線的特征。c0選定后，便可計算出兩個曲面在此點(diǎn)處的法矢，記為n1和n2，則相交線在點(diǎn)c0處的法平面就是法矢n1和n2組成的平面。相交線的切矢α垂直于法平面，可表示為：

因為交線主法矢β垂直于切矢方向，所以主法矢β一定處于由法矢n1和n2組成的法平面上。令曲率向量k=kβ=an1+bn2，取cos θ=n1·n2，兩曲面的法曲率記為，曲率方程兩邊分別乘以向量n1和n2，則：

將a和b分別用表示，則：

所以：

根據(jù)曲面的第一基本形式可得：

兩邊分別點(diǎn)乘Su和Sv，可以列出：

其中，E、F、G是曲面的第一類基本量。求解上式可以得到：

將式（16）代入式（13）中，可以求出曲面的法曲率。根據(jù)式（12），可以求出曲率向量k。根據(jù)曲率向量表達(dá)式可以求出主法矢β。曲線的曲率的大小為k的長度：

因此，可以分別求出曲率k、切矢α和主法矢β并和步長值s一起代入式（8）中，可求出下一個交點(diǎn)的近似位置。需要注意的是，想要得到該點(diǎn)的精確位置，還需要進(jìn)一步迭代。

3 步長可自適應(yīng)的追蹤法求交

設(shè)定合理的步長值，可以得到較準(zhǔn)確的交線位置和較高的求交效率。傳統(tǒng)追蹤法追蹤步長都是固定值，步長大小根據(jù)經(jīng)驗均是人為設(shè)定，在針對復(fù)雜曲面求交時不夠靈活方便，不夠穩(wěn)定。基于步長自適應(yīng)的追蹤法在求交過程中將追蹤步長與交線末端的曲率半徑相關(guān)聯(lián)，使步長可根據(jù)曲面真實特征實時變化。

3.1 確定初始插值點(diǎn)

節(jié)點(diǎn)矢量的分布可以決定B 樣條基函數(shù)的變化情況[16]。實驗發(fā)現(xiàn)插值曲線的階次為五次時，測量精度要高于三次和四次，而采用六次和七次曲線進(jìn)行插值會產(chǎn)生振蕩現(xiàn)象，反而測量精度降低。根據(jù)節(jié)點(diǎn)的變化規(guī)律[17]，五次非均勻B 樣條曲率具有連續(xù)性，其擬合的曲線平滑且符合常規(guī)產(chǎn)品的曲面特性[18]，所以本文采用五次非均勻B樣條曲線擬合交線上的點(diǎn)。

3.2 計算曲線末端曲率

若將五次非均勻B 樣條曲線方程定義為C(u)，則C(u)的末端點(diǎn)即為參數(shù)u=1 時所對應(yīng)的點(diǎn)，曲線的曲率計算公式為：

其中，C′(u)、C′(u)分別為曲線的一階、二階導(dǎo)數(shù)。當(dāng)kr ＜0 時擬合曲線沿前進(jìn)方向順時針彎曲；kr ＞0 時擬合曲線沿前進(jìn)方向逆時針彎曲。曲線某點(diǎn)處的曲率半徑可表示為：

3.3 確定自適應(yīng)追蹤步長s

值得注意的是：較小的追蹤步長可以提高求交精度，但同時計算量增加；較大的追蹤步長可以提高求交效率，但會影響求交精度，所以討論合理的自適應(yīng)追蹤步長取值具有重要意義。

先按照固定步長求取六個交點(diǎn)，將六個點(diǎn)依次定義為Q0、Q1、Q2、Q3、Q4、Q5，然后采用五次非均勻B樣條進(jìn)行擬合。將固定追蹤步長求取的六個交點(diǎn)插值為五次非均勻B 樣條曲線后，如圖3 所示，在曲線末端點(diǎn)Qp處以曲率半徑r，構(gòu)造該點(diǎn)處的曲率圓O1，連接O1Qp，給定一個跨距角θ，得到圓上的一點(diǎn)Qp+1，即為下一個追蹤點(diǎn)，弦長QpQp+1即為跨距S，也就是自適應(yīng)追蹤步長值。確定自適應(yīng)步長S的值后，也就確定了下一個追蹤點(diǎn)Qp+1的大致位置。

圖3 確定自適應(yīng)步長原理圖

AB為圓弧QpQp+1與弦QpQp+1的最大距離，當(dāng)圓弧QpQp+1上的點(diǎn)到弦QpQp+1上的距離不超過閾值e，即AB＜e時，可以用弦QpQp+1來近似表示圓弧QpQp+1，如下方程所示：

當(dāng)θ=2×arccos(1-e×kr) 時 ，交 線 上 的 點(diǎn) 到 弦QpQp+1的距離為最大值e。根據(jù)上式可知，曲率kr越小，θ的值同時也會越小，AB值越大，自適應(yīng)追蹤步長的值就會越大；反之，當(dāng)曲率kr越大時，θ值就越大，AB值越小，自適應(yīng)追蹤步長值就會越小。其中e的大小由測量精度要求決定，精度要求越高，e的值就越小，求交得到交點(diǎn)的數(shù)量就越多，一般取精度閾值e=0.01 mm。如圖3所示，把自適應(yīng)追蹤步長S表示為：

確定曲率kr，即基本確定了自適應(yīng)步長S的值。

3.4 基于自適應(yīng)追蹤步長曲面求交過程

需要注意的是根據(jù)自適應(yīng)步長確定的下一個追蹤點(diǎn)，得到的曲面交點(diǎn)位置并不精確，需要采用迭代法求出該交點(diǎn)的精確位置[19]。首先，分別在兩參數(shù)曲面S1和S2上選取距點(diǎn)c′(s)較近的兩個點(diǎn)，分別記為p1和p2，p1屬于參數(shù)曲面S1，p2屬于參數(shù)曲面S2。若有p1和p2收斂于鄰近點(diǎn)c(s)，則該點(diǎn)符合設(shè)定的精度要求：|p1-p2|≤ε。若p1和p2在鄰近點(diǎn)處無法收斂，則將p2定義為交點(diǎn)的近似點(diǎn)，不斷重復(fù)上述的計算過程。然后以迭代求取的精確點(diǎn)c(s)作為初始交點(diǎn)，繼續(xù)計取下一個交點(diǎn)的位置，直至追蹤到參數(shù)曲面的邊界。追蹤步長可自適應(yīng)曲面求交過程的算法流程，如圖4所示。

圖4 追蹤步長可自適應(yīng)曲面求交過程

4 實例驗證

為驗證基于步長自適應(yīng)追蹤法求交相比傳統(tǒng)追蹤法求交的優(yōu)越性性，提出對具有不同特征的曲面進(jìn)行多組求交實驗。將曲面在步長自適應(yīng)和固定步長兩種方式下進(jìn)行求交，對比求交結(jié)果。需要說明的是：為方便求交結(jié)果的對比，以下所有求交試驗均設(shè)置交點(diǎn)精度閾值ε為0.001 mm。

4.1 平面和自由曲面求交

為了驗證五次非均勻B 樣條曲線曲率連續(xù)自適應(yīng)步長跟蹤求交算法的可行性，結(jié)合C++面向?qū)ο箝_發(fā)語言和OpenGL 等圖像數(shù)學(xué)函數(shù)，以平面與曲面、曲面與曲面求交為例，對曲面求交進(jìn)行可視化。

如圖5所示，為兩個在逆向系統(tǒng)軟件中重構(gòu)出來的相交曲面，根據(jù)重構(gòu)點(diǎn)云獲取曲面邊界信息，如圖6 所示，曲面的U向跨距為12 mm，V向跨距為34.05 mm；平面的U向跨距為12 mm，V向跨距為32.1 mm。根據(jù)曲面邊界信息，設(shè)置曲面U向、V向等參數(shù)線數(shù)量，如圖7 所示，跟蹤步長選擇為自適應(yīng)步長，精度閾值設(shè)為0.001 mm。求交結(jié)果如圖8所示，藍(lán)色的曲線即為平面與曲面的交線。

圖5 平面與曲面相交模型

圖7 跟蹤步長設(shè)置

圖8 平面與曲面求交結(jié)果

4.2 兩個自由曲面間求交

平面與曲面求交實驗驗證了該求交方法的可行性，為了進(jìn)一步驗證該求交方法的通用性，選取更具代表性的自由曲面進(jìn)行求交實驗，如圖9所示。與平面和自由曲面求交參數(shù)設(shè)置一樣，先根據(jù)曲面邊界信息設(shè)置等參數(shù)線數(shù)量，然后設(shè)置步長和精度閾值，這里依然選用的自適應(yīng)步長，精度閾值設(shè)為0.001 mm，求交結(jié)果如圖10 所示，結(jié)果驗證了自由曲面與自由曲面求交的可行性。

通過平面與曲面求交、曲面與曲面求交實驗驗證了自適應(yīng)求交算法的可行性后，為了進(jìn)一步驗證該求交算法的可靠性以及優(yōu)越性，將自適應(yīng)步長求交算法與固定步長求交算進(jìn)行對比，并對其求交誤差和求交速度進(jìn)行分析。

圖9 自由曲面相交模型

圖10 自由曲面求交結(jié)果

實驗分別以自適應(yīng)步長、固定步長3 mm、5 mm、10 mm、15 mm 以及 20 mm 進(jìn)行對如圖9 所示的兩自由曲面進(jìn)行求交實驗，求取不同步長下的交線，交線求取結(jié)果如圖11 所示，從圖中可以看出，當(dāng)步長不斷增大時，所求得的交線與實際交線偏移量越大，求交誤差不斷增加。

圖11 不同步長求交結(jié)果

為了更好地反映誤差與跟蹤步長之間的變化關(guān)系，在imageware 軟件中對誤差進(jìn)行了量化，分別繪制了自適應(yīng)步長以及不同固定步長所求交線的誤差云圖，如圖12所示。

圖12 不同步長曲面求交誤差

圖12 中藍(lán)色線條表示所求交線，其他顏色線條用來反應(yīng)所求交線與實際交線的偏離程度，其中最大偏離誤差用MAX表示，最小偏離誤差用MIN表示?？梢钥闯?，在曲線曲率較大的地方，誤差明顯增大。為了更直觀地展現(xiàn)誤差與跟蹤步長之間的關(guān)系，量化誤差。將誤差進(jìn)行數(shù)據(jù)統(tǒng)計得到表1。

從表1 可以看出，跟蹤步長為3 mm 時交線的最大誤差為5.588E-06 mm，最小誤差為0 mm，平均誤差為2.79E-06 mm，求交精度高；步長為5 mm 時，最大誤差為0.340 5 mm，最小誤差為3.725E-06 mm，平均誤差為0.170 mm，求交精度一般；當(dāng)步長為10、15、20 mm，平均誤差為毫米級，求交誤差較大，無法達(dá)到精度要求；采用自適應(yīng)步長時，交線的最大誤差為6.909E-05 mm，最小誤差為0 mm，平均誤差為3.45E-05，與步長為3 mm 時求交的精度接近，但是計算次數(shù)比步長為3 mm 時減少了43%左右，計算量減幅較大，計算量較小；與步長為5 mm時的求交相比，計算次數(shù)基本一致，計算量基本相同，但精度高出4個數(shù)量級。

表1 多種步長下的交線誤差

4.3 圓錐面與圓柱面間求交

找到含有規(guī)則曲面的實物，如圖13所示，利用實驗室已有設(shè)備CMM 對實物中標(biāo)記的兩個曲面進(jìn)行點(diǎn)云采集。

圖13 含有規(guī)則曲面的實物

將采集到的點(diǎn)云數(shù)據(jù)在SurfaceReverse 中顯示，如圖14所示。并進(jìn)行曲面重構(gòu)延伸相交，如圖15所示。

圖14 點(diǎn)云數(shù)據(jù)

圖15 重構(gòu)曲面延伸相交

設(shè)定精度閾值ε=0.001 mm，步長值取5 mm、14 mm及自適應(yīng)步長，求交結(jié)果如圖16所示。

為了更好地反映誤差與追蹤步長之間的變化關(guān)系，將自主研發(fā)的逆向系統(tǒng)SurfaceReverse 求取的交線與UG NX 求取的交線進(jìn)行對比分析，將誤差數(shù)據(jù)制作成表2。

從表2 可以看出，自適應(yīng)追蹤步長求得交點(diǎn)數(shù)為48，相比追蹤步長為5 mm時計算次數(shù)減少了36.8%，但是兩者誤差相差不大，精度在同一個量級，均符合要求；步長為14 mm的曲面相交誤差比較大，超過了誤差許可范圍。

圖16 取不同步長值下的曲面求交結(jié)果

表2 不同追蹤步長下的交線誤差

通過對表1、表2的數(shù)據(jù)進(jìn)行分析可以發(fā)現(xiàn)，對于傳統(tǒng)追蹤法求交，追蹤步長越小，計算次數(shù)會顯著增加，求取的交點(diǎn)數(shù)也會越多，計算量增多，求取交線的效率會降低很多，但求取的交線精度很高。相比之下，步長可自適應(yīng)變化的追蹤法求交，在滿足同等求交精度的情況下，依舊可以保持較高的求交效率。結(jié)果表明：這種相交算法速度較快。

5 結(jié)論

（1）在求交過程中將追蹤步長與交線末端的曲率半徑相關(guān)聯(lián)，得到可自適應(yīng)變化的追蹤步長。對具有不同特征的復(fù)雜曲面在步長自適應(yīng)方式下進(jìn)行求交試驗，結(jié)果表明，在同一個誤差許可范圍內(nèi)，相比傳統(tǒng)的固定步長追蹤方法，采用步長可自適應(yīng)變化的追蹤法進(jìn)行曲面求交的交線平均誤差均μm級，求交誤差小，精度高。

（2）對同一組曲面在步長自適應(yīng)和固定步長兩種方式下進(jìn)行求交試驗，對比發(fā)現(xiàn)，固定步長過小，精度可明顯提高，但計算量過大，耗時增加；固定步長過大，誤差明顯增加，得到結(jié)果不夠精確。試驗結(jié)果表明，基于步長自適應(yīng)的追蹤法求取到的交點(diǎn)不僅能隨曲面特征合理分布而且具有更高求交效率。