B 樣條曲線的等距算法及應(yīng)用

朱朝艷， 陳小雕

（1. 浙江大學(xué)寧波理工學(xué)院，浙江 寧波 315100； 2. 杭州電子科技大學(xué)計(jì)算機(jī)學(xué)院，浙江 杭州 310018）

等距曲線、曲面的計(jì)算是幾何計(jì)算的一個(gè)重要問題。它除了應(yīng)用于傳統(tǒng)的CNC 加工，還廣泛應(yīng)用于CAD 中的諸如圖案設(shè)計(jì)等領(lǐng)域[1]。等距曲線、曲面的計(jì)算主要有兩大類方法，一種是精確的方法，另一種是近似的方法。Farouki 等人討論了可以用有理形式精確表示的曲線[2-5]。不幸的是，很多曲線的等距曲線是不能用有理形式精確表示的。在近似方法上，有很多文章討論了平面曲線的等距曲線[6-7]。主要有兩類方法，第一種是基于曲線逼近的方法[8,18]，這類方法中，或者用更加簡單曲線，如直線段或圓弧等逼近原始曲線，并借助逼近曲線的等距曲線來近似原始曲線的等距曲線，同時(shí)用來去除等距曲線的自交，降低了求交計(jì)算的復(fù)雜度，但最終得到的等距曲線的段數(shù)較多；另一種則是基于自由曲線控制點(diǎn)的方法[1,9-15,19-20]，這種方法得到的段數(shù)相對(duì)較少，但往往有自交情況，去除自交的計(jì)算量將隨著曲線的復(fù)雜化而變得很大。

保持等距曲線的正確的拓?fù)浣Y(jié)構(gòu)非常重要。在傳統(tǒng)的CNC 加工中，等距曲線的正確拓?fù)浣Y(jié)構(gòu)對(duì)于刀具的路徑設(shè)計(jì)有著決定性的作用。在圖案設(shè)計(jì)等應(yīng)用中，等距曲線的不正確的拓?fù)浣Y(jié)構(gòu)，可能導(dǎo)致最終得到的雙側(cè)等距曲線或者因缺失一段曲線不封閉，或者因多出一段曲線而出現(xiàn)懸邊。圖1 表示了單邊等距曲線的示意圖。圖1(a)中，多出來一段，若繼續(xù)作另一邊的等距曲線，會(huì)導(dǎo)致出現(xiàn)懸邊；圖1(b)中，缺少一段，若繼續(xù)作另一邊的等距曲線，會(huì)導(dǎo)致雙側(cè)的等距曲線不封閉；圖1(c)中的等距曲線具有正確的拓?fù)浣Y(jié)構(gòu)，對(duì)應(yīng)的雙側(cè)等距曲線也是封閉的。

圖 1 等距曲線拓?fù)浣Y(jié)構(gòu)的示意圖

本文討論B樣條曲線的等距曲線的近似計(jì)算方法。首先，用雙圓弧逼近的原始曲線的等距曲線，同時(shí)提出了基于單調(diào)圓序列的方法來計(jì)算等距曲線的近似自交點(diǎn)，并以此為初值迭代到精確的自交點(diǎn)。其次，根據(jù)前面計(jì)算的自交點(diǎn)作為等距曲線上的關(guān)鍵分段點(diǎn)并進(jìn)行各個(gè)分段曲線的取舍。最后，應(yīng)用文獻(xiàn)[14-15]中的方法計(jì)算各個(gè)分段的等距曲線，同時(shí)保持段與段之間的拓?fù)潢P(guān)系，得到最終的等距曲線。本文方法得到的等距曲線可以保持正確的拓?fù)浣Y(jié)構(gòu)，最后得到的B樣條表示的等距曲線具有較少的控制點(diǎn)。

1 求解B 樣條曲線的等距曲線

一般的n 次B 樣條曲線可以表示為

其中 )(tN 為曲線 )(tC 在參數(shù)t 處的單位法 向。一般地，n 次B 樣條的等距曲線不再是n 次B 樣條，甚至不能精確地表示為有理形式，人們 通常用近似的方法求解原始曲線 )(tC 的近似等 距曲線。在CNC 加工中，要求刀具在行進(jìn)的過程中避免干涉，它所要求的結(jié)果等距曲線就是由式子(2)確定的等距曲線上，所有到原始曲線的最近距離恰好等于有向等距距離d 的絕對(duì)值的點(diǎn)的集合

其中 Dis ( Rd(t)，C)表示點(diǎn) Rd(t)到曲線C 的最近距離。這種應(yīng)用下，僅僅去除單側(cè)自交點(diǎn)，可能會(huì)或增加或減少等距曲線段（見圖1）。本文的算法專門針對(duì)式子(3)確定的應(yīng)用，是對(duì)原先等距方法的補(bǔ)充。不失一般性，下面只考慮d＞0的情況，d＜0的情況可以同樣處理。

1.1 樣條曲線的自適應(yīng)離散采樣

在實(shí)際應(yīng)用中，樣條曲線的自適應(yīng)離散采樣，可以采用基于曲率的方法[1]。本文用雙圓弧逼近的方法直接對(duì)相應(yīng)的等距曲線進(jìn)行自適應(yīng)離散采樣。實(shí)踐表明，在給定的精度下，基于圓弧逼近的離散方法，得到的采樣點(diǎn)數(shù)目往往要少于基于折線段逼近離散的方法。本文采用的雙圓弧逼近的方法，主要參考了Yang[16]的算法。實(shí)踐證明，雙圓弧求交得到的近似交點(diǎn)，比用折線段求交得到的交點(diǎn)，更為接近原始曲線的精確交點(diǎn)；基于雙圓弧離散的方法得到的等距曲線上的近似自交點(diǎn)比基于折線段離散的方法得到的相應(yīng)的近似自交點(diǎn)具有更高的精度。

1.2 等距曲線的關(guān)鍵段點(diǎn)的定位與分段的取舍

由上文提及的等距曲線的概念容易得知，最后得到的去掉自交后的結(jié)果等距曲線是由若干段連續(xù)的曲線組成。為了方便起見，本文稱各段 結(jié)果等距曲線段的端點(diǎn)為段點(diǎn)，并記χ 為結(jié)果等距曲線的所有段點(diǎn)的集合，+μ 為原始曲線的正向等距曲線，?μ 為原始曲線的負(fù)向等距曲線，+Ω 為+μ 的所有自交點(diǎn)的集合，?Ω 為所有+μ 與?μ 交點(diǎn)的集合，并記 Ω = Ω+∪Ω?。

定理1 ∈χ Ω 。

根據(jù)定理1，求出Ω 對(duì)應(yīng)的分劃A，并由此決定由A 確定的每一個(gè)小區(qū)間的取舍，最后得到的，就是結(jié)果等距曲線（段）對(duì)應(yīng)在原始曲線的若干個(gè)參數(shù)小區(qū)間，并且這些小區(qū)間對(duì)應(yīng)的等距曲線，不存在自交的現(xiàn)象，可以用已有的各種方法去求解。

首先討論關(guān)鍵段點(diǎn)的定位，并由此得到Ω 對(duì)應(yīng)的分劃A。這個(gè)過程就是求解所有的交點(diǎn)集合Ω 。直接應(yīng)用等距曲線之間求交，一般比較 費(fèi)時(shí)間。利用逼近等距曲線后得到的雙圓弧序列來估計(jì)交點(diǎn)，可以降低求交計(jì)算的復(fù)雜度與計(jì)算量，同時(shí)，得到交點(diǎn)比折線段方法更加接近精確的交點(diǎn)。

本文應(yīng)用單調(diào)列技術(shù)消除圓弧序列的自交問題，并應(yīng)用包圍盒等技術(shù)來求解兩列圓弧序列之間的交。首先，分別依次取所有控制點(diǎn)坐標(biāo)的x 分量與y 分量，得到兩個(gè)坐標(biāo)序列，根據(jù)每列相鄰坐標(biāo)分量的差組成的數(shù)列的變號(hào)數(shù)，選擇變號(hào)數(shù)小的，不妨設(shè)該坐標(biāo)分量為x 分量。然后，對(duì)每段雙圓弧增加點(diǎn)，使得每一段簡單圓弧都是 關(guān)于該坐標(biāo)分量單調(diào)。依次選擇連續(xù)的多個(gè)圓弧組成的，關(guān)于x 分量單調(diào)的子序列，作為一個(gè)單調(diào)列，這樣可以得到若干個(gè)單調(diào)列，并且每一個(gè)單調(diào)列內(nèi)的圓弧，兩兩不相交。

確定分劃A 之后，就需要確定小區(qū)間的取舍。小區(qū)間的準(zhǔn)確取舍，對(duì)于最后等距曲線的拓?fù)浣Y(jié)構(gòu)是至關(guān)重要的。等距曲線上相鄰兩段單調(diào)列的交點(diǎn)，利用向量點(diǎn)積判斷的方法，速度很快，可以用來去除局部環(huán)（如圖2）。但是，該方法去除全局環(huán)，效率是不夠的，容易發(fā)生誤判。利用求解點(diǎn)到逼近折線段，或者點(diǎn)到逼近圓弧的距離，常因?yàn)槎螖?shù)的影響速度變得比較慢，而且由于逼近的誤差，在臨界狀態(tài)下也容易發(fā)生誤判，特別的，當(dāng)所取的點(diǎn)不在精確等距曲線上的時(shí)候，誤判幾率更大。本文綜合了上述這兩種方法的優(yōu)點(diǎn)進(jìn)行了判斷處理。首先，利用向量點(diǎn)積的判斷方法，排除到原始曲線距離明顯小于等距距離的小區(qū)間。在余下的區(qū)間，選取相鄰兩個(gè)交點(diǎn)所確定的小區(qū)間內(nèi)的精確等距曲線上的點(diǎn)作為基準(zhǔn)點(diǎn)，來求解點(diǎn)到原始曲線的距離，避免了逼近誤差引發(fā)的臨界問題。基準(zhǔn)點(diǎn)的選取，可以分為兩種情況，如果相鄰的交點(diǎn)分別屬于不同序號(hào)的雙圓弧，則直接選取兩個(gè)交點(diǎn)之間的雙圓弧的端點(diǎn)作為基準(zhǔn)點(diǎn)；否則，取兩交點(diǎn)對(duì)應(yīng)的參數(shù)的中間值對(duì)應(yīng)在精確等距曲線上的點(diǎn)，作為基準(zhǔn)點(diǎn)。然后，計(jì)算基準(zhǔn)點(diǎn)到原始曲線的最近距離，如果距離在容差的范圍內(nèi)等于d，則保留，否則舍去該小區(qū)間。

圖2 局部環(huán)與全局環(huán)處理結(jié)果

一般的，可以用雙側(cè)等距曲線的封閉性來幫助檢驗(yàn)等距曲線的拓?fù)浞€(wěn)定性。圖3 是一個(gè)樣條曲線雙側(cè)等距的實(shí)例, 其中，3(a)是原始曲線，3(b)是AutoCAD 軟件局部放大的結(jié)果，3(c)是OpenCAD 軟件局部放大的結(jié)果?？梢钥闯?，本文的方法的結(jié)果，有更好的拓?fù)浞€(wěn)定性。當(dāng)自交點(diǎn)的參數(shù)估計(jì)沒收斂到精確自交點(diǎn)（實(shí)例中沒出現(xiàn)這樣的情況），圖4 演示的本文的閉合處理方法也能保證最后得到的雙側(cè)等距曲線是閉合的。

圖3 取舍的實(shí)例與比較

圖4 閉合處理方法的比較

1.3 各個(gè)分段的等距曲線的最后處理

最后結(jié)果樣條的處理上，可以直接用三次樣條插值前面得到的采樣點(diǎn)。這種方法的好處，結(jié)果曲線比較簡單，在精度范圍內(nèi)也能保證插值后各段樣條之間兩兩不相交，同時(shí)還能在全局交點(diǎn)處能保持連續(xù)，這種算法可以應(yīng)用于圖案設(shè)計(jì)。一般地，前面離散過程中得到的采樣點(diǎn)數(shù)目可能比較大，有時(shí)候由于精度等原因，甚至還需要對(duì)采樣點(diǎn)進(jìn)行加密，相應(yīng)的，最后結(jié)果樣條的段數(shù)比較多，這是工程應(yīng)用上的一大忌諱。直接用基于控制點(diǎn)調(diào)整的方法，對(duì)估計(jì)出來的小區(qū)間作等距曲線，段數(shù)相對(duì)來說少一些，但是不能保證插值后各段樣條之間兩兩不相交，特別地，在全局交點(diǎn)處還可能不連續(xù)，這種情況的一個(gè)直接表現(xiàn)是繼續(xù)作另外一側(cè)的等距曲線，兩側(cè)等距曲線在原本應(yīng)該閉合的情況下，不能閉合（見圖4）。用求交的方法可以處理相交的情況，但是比較耗時(shí)間；Lee[8]針對(duì)參數(shù)小區(qū)間端點(diǎn)的參數(shù)值迭代求精的方法，在一定程度上可以改善，但是它依賴于迭代算法收斂的具體狀況。

本文的處理方法，應(yīng)用類似Yang[17]的基于控制點(diǎn)調(diào)整的逼近方法，對(duì)上面估計(jì)得到的參數(shù)小區(qū)間，直接求解等距曲線的逼近曲線。如圖4所示，它預(yù)先指定了每一段逼近曲線的端點(diǎn)，就是上面求解得到的交點(diǎn)，這樣，減少了段數(shù)，同時(shí)也避免了在全局交點(diǎn)處可能不連續(xù)的情況，可以同時(shí)應(yīng)用于圖案設(shè)計(jì)與CNC 等多種工程應(yīng)用。

2 實(shí)例與結(jié)論

將本文的算法應(yīng)用到商業(yè)軟件OpenCAD中，并用 3 個(gè)實(shí)例與同類的國外著名軟件AutoCAD2004, AutoCAD2005 就樣條曲線的雙側(cè)等距功能作比較。為方便起見，分別將AutoCAD2004，AutoCAD2005 以及OpenCAD 分別得到的3 個(gè)結(jié)果簡稱為結(jié)果A2，A4與B。

例1 圖5是針對(duì)閉合的，自交的曲線進(jìn)行雙側(cè)等距的結(jié)果比較，結(jié)果A2, A4分別給出部分等距，B給出了所有的等距曲線段，在視覺上具有更好的美感。曲線為三次樣條曲線，控制點(diǎn)與節(jié)點(diǎn)向量分別為：(456.2347,218.4149)(449.6793,295.0248) (577.9684,484.1168) (964.6972,235.6098) (479.0472,178.5197) (584.1964, 515.6817) (855.0988,486.1700) (996.1325,252.3531) (727.8244,37.1056) (666.6469,449.5623) (1117.0048,489.0262) (1047.2378,-13.7901) (646.8361,-10.8984) (462.4325,145.9829) (456.2347,218.4149)與 {0.0,0.0,0.0,0.0, 230.6695, 474.8459,725.8914, 924.3524,1158.021,1381.021,1572.056,1809.599, 2095.662,2406.339,2813.724,3031.814,3031.814, 3031.814,3031.814}。等距偏移量為20。

圖5 閉合自交曲線雙側(cè)等距結(jié)果曲線比較

例2 圖6是針對(duì)開的，自交的曲線進(jìn)行雙側(cè)等距的結(jié)果比較，結(jié)果A2, A4均漏掉了一段等距曲線段，B給出所有了的等距曲線段。曲線為三次樣條曲線，控制點(diǎn)與節(jié)點(diǎn)向量分別為：

(744.1808,508.8816) (776.7853,617.1998)

(833.3231,805.0285) (1078.0127,477.1051)

(648.0156,613.3402) (904.6993,768.0031)

(1050.8365,683.1869)(1053.8494,416.9693)

(692.1974,641.8598) (1057.0341,807.6433)

(1130.0377,608.4000) (1146.8524,404.0772)

(905.6308,403.5530) (881.9587,626.8380)

(1034.5717,575.1042) (1005.0188,465.7295)

(851.9888,419.3761) (794.0705,602.0181)

(925.0642,738.1799) (708.6746,770.5750)

(679.8814,704.0337) (674.9950,692.7413)與

{0.0,0.0,0.0,0.0,232.64907,403.42409,621.36462,

795.97228,929.19622,1091.2253,1307.7149,

1555.8348,1688.0376,1878.5677,2042.7598,

2179.7761,2274.3395,2341.8718,2459.9235,

2639.7297,2725.5404,2902.8505,2939.0912,

2939.0912,2939.0912,2939.0912}。等距距離為20。

圖6 開自交曲線雙側(cè)等距結(jié)果曲線比較

例3 利用例2 中的數(shù)據(jù)，選取其中兩段等距曲線段進(jìn)行控制點(diǎn)數(shù)目比較，結(jié)果A2, A4得到兩段等距曲線段的控制點(diǎn)數(shù)目分別為68 與74，結(jié)果B 得到的數(shù)目分別為14 與16（見圖7）。

圖7 兩段等距曲線段控制點(diǎn)數(shù)目比較

本文討論了B 樣條曲線的等距算法，提出了基于雙圓弧逼近和單調(diào)圓序列技術(shù)的自交消除算法，同時(shí)綜合了基于控制點(diǎn)調(diào)整的曲線逼近等技術(shù)，并在此基礎(chǔ)上提出了一種關(guān)于B 樣條曲線的統(tǒng)一的、魯棒的等距算法。本文的算法具有保持拓?fù)浞€(wěn)定，以及生成的等距曲線段數(shù)較少等特點(diǎn)。它已應(yīng)用于商業(yè)軟件OpenCAD 中，適用于處理自交，閉合等任意類型的樣條曲線的等距，它還可以應(yīng)用于圖案設(shè)計(jì)等領(lǐng)域。實(shí)例也表明了本文的算法結(jié)果可以具有更精確的拓?fù)浣Y(jié)構(gòu)和較少的段數(shù)。

[1] Piegl L, Tiller W. Computing offsets of nurbs curves and surfaces [J]. Computer-Aided Design, 1999, 31： 147-156.

[2] Farouki R T, Neff C A. Analytic properties of plane offset curves [J]. Computer Aided Geometric Design, 1990, 7(1-4)： 83-99.

[3] Farouki R T, Neff C A. Algebraic properties of plane offset curves [J]. Computer Aided Geometric Design, 1990, 7(1-4)： 101-127.

[4] Farouki R T, Sederberg T W. Analysis of the offset to a parabola [J]. Computer Aided Geometric Design, 1995, 12(6)： 639-645.

[5] Pottmann H. Rational curves and surfaces with rational offsets [J]. Computer Aided Geometric Design, 1995, 12： 175-192.

[6] Pham B. Offset curves and surfaces： A brief survey [J]. Computer-Aided Design, 1992, 24(4)： 223-229.

[7] Maekawa T. An overview of offset curves and surfaces [J]. Computer-Aided Design, 1999, 31： 165-173.

[8] Lee I K, Kim M S, Elber G. Planar curve offset based on circle approximation [J]. Computer-Aided Design, 1996, 28(8)： 617-630.

[9] Hoschek J. Spline approximation of offset curves [J]. Computer Aided Geometric Design, 1988, 5(1)： 33-40.

[10] Meek D S, Walton D J. Offset curves of clothoidal splines [J]. Computer-Aided Design, 1990, 22(4)： 199-201.

[11] Sederberg T W, Buehler D B. Offsets of polynomial Bezier curves： Hermite approximation with error bounds [C]//Lyche T, Schumaker L L, editors. Mathematical Methods in Computer Aided Geometric Design, Volume II, Academic Press, 1992： 549-558.

[12] Coquillart S. Computing offsets of B-spline curves [J]. Computer-Aided Design, 1987, 19(6)： 305-309.

[13] Klass R. An offset spline approximation for plane cubic splines [J]. Computer-Aided Design, 1993, 25(5)： 297-299.

[14] Kumar R, Shastry K G, Prakash B G. Computing constant offsets of a NURBS B-Rep [J]. Computer-Aided Design, 2003, 35： 935-944.

[15] Tiller W, Hanson E G. Offsets of two-dimensional profiles [J]. IEEE Computer Graphics and Applications, 1984, 4(9)： 36-46.

[16] Yang X N. Efficient circular arc interpolation based on active tolerance control [J]. Computer-Aided Design, 2002, 34： 1037-1046.

[17] Yang H P, Wang W P, Sun J G. Control point adjustment for B-spline curve approximation [J]. Computer-Aided Design, 2004, 36(7)： 639-652.

[18] 汪國平, 孫家廣. 平面NURBS 曲線及其Offset 的雙圓弧逼近[J]. 軟件學(xué)報(bào), 2000, 11(10)： 1368-1374.

[19] 劉利剛, 王國瑾. 基于控制頂點(diǎn)偏移的等距曲線最優(yōu)逼近[J]. 軟件學(xué)報(bào), 2002, 13(3)： 398-403.

[20] 汪國平, 陳玉健, 孫家廣. 基于控制頂點(diǎn)擾動(dòng)的平面Offset 曲線的NURBS 逼近[J]. 計(jì)算機(jī)學(xué)報(bào), 1999, 22(12)： 59-66.