帶約束的B樣條曲線曲面延伸技術(shù)

徐 進(jìn)

（浙江科技學(xué)院機(jī)械與汽車工程學(xué)院，浙江 杭州 310023）

帶約束的B樣條曲線曲面延伸技術(shù)

徐 進(jìn)

（浙江科技學(xué)院機(jī)械與汽車工程學(xué)院，浙江 杭州 310023）

論文提出了一種帶光滑有序點(diǎn)列約束的 B樣條曲線延伸方法。該算法能夠根據(jù)約束點(diǎn)列的情況對(duì)曲線延伸部分所對(duì)應(yīng)的節(jié)點(diǎn)值進(jìn)行優(yōu)化，通過(guò)插值盡量少的約束點(diǎn)，使得延伸曲線與約束點(diǎn)列之間的最大距離小于預(yù)先給定的誤差值，并且延伸曲線與原始曲線之間自然達(dá)到最大階連續(xù)。該方法也同樣適用于帶曲線約束的 B樣條曲面延伸。實(shí)例表明，所提出的算法是可行且有效的。

B樣條；延伸；有序點(diǎn)列約束；節(jié)點(diǎn)修正

在幾何建模的過(guò)程中，許多針對(duì)B樣條曲線的算法和操作被廣泛地研究和使用，如曲線的擬合（包括插值和逼近）、光順、組合、變形等。在許多CAD系統(tǒng)中，B樣條曲線的延伸也是常用的算法之一，通常是將曲線延伸到某一個(gè)目標(biāo)點(diǎn)或是延伸一個(gè)特定的距離。為了補(bǔ)充曲線曲面構(gòu)造特征的不足。需要對(duì)曲線曲面進(jìn)行操作處理（如裁剪和延伸）。它可用于不相交的曲面求交及曲面在圓角的過(guò)渡。目前，曲線延伸普遍采用的方法是在B樣條曲線延伸端的端點(diǎn)和目標(biāo)點(diǎn)之間構(gòu)造一條Bézier曲線，使得Bézier曲線與原B樣條曲線在連接處達(dá)到G1連續(xù)，然后將兩段曲線組合成一條曲線，并用B樣條進(jìn)行表達(dá)。周元峰等[1]通過(guò)極小化目標(biāo)函數(shù)實(shí)現(xiàn)了G2連續(xù)約束下三次Bezier曲線向一點(diǎn)的延伸，并且曲線的形狀可以調(diào)整，但是該方法并不適用于B樣條。余正生等[2]詳細(xì)推導(dǎo)了非均勻有理B樣條(NURBS)曲線曲面延伸且滿足切平面連續(xù)和曲率連續(xù)的數(shù)學(xué)表達(dá)式；Shetty等[3]提出了一種既直接又實(shí)用的方法對(duì)有理B樣條曲線和曲面進(jìn)行延伸，且在延伸過(guò)程中不改變?cè)€或曲面的形狀和參數(shù)值。然而，采用這種方法得到的延伸曲線的節(jié)點(diǎn)矢量在內(nèi)部存在多重節(jié)點(diǎn)的情況，因此，在通用CAD系統(tǒng)中并不被廣泛采用。Chivate等[4]利用曲線和曲面在延伸端的一階導(dǎo)數(shù)信息將曲線和曲面延伸至定義域之外，但是，由于在延伸過(guò)程中改變了原曲線和曲面的形狀，因此，在很大程度上限制了該方法的應(yīng)用。Hu等[5]利用B樣條曲線的端點(diǎn)松弛算法和de Boor遞推公式將B樣條曲線延伸至一個(gè)或多個(gè)目標(biāo)點(diǎn)，曲線延伸部分與原曲線在連接處達(dá)到最大的連續(xù)階（即連續(xù)階等于原B樣條曲線的次數(shù)減1）。但是，由該方法得到的延伸曲線形狀是唯一的，因此，常常不能滿足要求。

本文提出了一種帶光滑有序點(diǎn)列約束的 B樣條曲線延伸算法。所有約束點(diǎn)被劃分為兩大類：插值點(diǎn)集和逼近點(diǎn)集。首先，將有序約束點(diǎn)列中的最末點(diǎn)作為唯一的插值點(diǎn)加入到插值點(diǎn)集中，將其余點(diǎn)加入到逼近點(diǎn)集中，并在算法每次迭代過(guò)程中增加一個(gè)插值點(diǎn)，相應(yīng)地減少一個(gè)逼近點(diǎn)。對(duì)于給定數(shù)目的插值點(diǎn)，運(yùn)用B樣條曲線端點(diǎn)松弛算法和de Boor遞推算法的逆過(guò)程將原B樣條曲線進(jìn)行延伸，使得延伸曲線插值于插值點(diǎn)集內(nèi)的每一個(gè)點(diǎn)。然后通過(guò)求解一個(gè)非線性優(yōu)化問(wèn)題對(duì)曲線延伸部分所對(duì)應(yīng)的節(jié)點(diǎn)矢量值進(jìn)行優(yōu)化，使得曲線延伸部分能夠更加貼近逼近點(diǎn)集中的所有點(diǎn)。經(jīng)過(guò)數(shù)次迭代后，最終使得延伸曲線在小于預(yù)先給定的容差值的前提下插值盡可能少的約束點(diǎn)。

1 B樣條曲線端點(diǎn)松弛算法

在幾何建模中，通常采用端點(diǎn)夾持型的B樣條曲線來(lái)表示自由曲線模型。一條p次的端點(diǎn)夾持型B樣條曲線可表示為：

其中Pi為曲線的控制頂點(diǎn)，為定義在規(guī)范化非均勻節(jié)點(diǎn)矢量上的p次B樣條基函數(shù)。若是任意一組大于 1的遞增實(shí)數(shù)序列，即則可以為新的節(jié)點(diǎn)矢量將曲線 P(u)在末端點(diǎn)處進(jìn)行松弛化處理。將端點(diǎn)松弛化后的曲線記為：

其中：

2 帶光滑有序點(diǎn)列約束的B樣條曲線延伸

2.1 插值點(diǎn)數(shù)目一定時(shí)的B樣條曲線延伸

即使約束點(diǎn)列較光滑，在曲線延伸過(guò)程中如果要求延伸曲線插值每一個(gè)約束點(diǎn)，可能會(huì)使得延伸曲線出現(xiàn)局部波動(dòng)或扭曲現(xiàn)象，所以沒有必要使得延伸曲線嚴(yán)格插值每一個(gè)約束點(diǎn)，其中一部分約束點(diǎn)只需要逼近即可。將光滑有序約束點(diǎn)列記為W={R1, R2,…, RM}，若延伸曲線插值了其中t個(gè)約束點(diǎn)，則可將W分解為兩個(gè)子集：插值點(diǎn)集和逼近點(diǎn)集 WA= W -WI，其中。如果賦予每一個(gè)插值點(diǎn)一個(gè)參數(shù)值si，并將si作為延伸后曲線節(jié)點(diǎn)矢量中的一個(gè)節(jié)點(diǎn)值，則延伸以后曲線的節(jié)點(diǎn)矢量將由 U0變?yōu)椋呵已由旌蟮那€可表示為如下形式：

各插值點(diǎn)處的參數(shù)值 si可由下面的方法計(jì)算得到：

其中，||?||表示歐氏距離。

圖1所示為B樣條曲線的de Boor求值算法的計(jì)算過(guò)程，圖2為相應(yīng)的控制頂點(diǎn)遞推示意圖。從圖1和圖2可以看出，當(dāng)未知時(shí)，整個(gè)計(jì)算過(guò)程中只有未知。如果令，運(yùn)用de Boor求值公式（7）可以計(jì)算得到的值。類似地，當(dāng)和已知時(shí)，可以計(jì)算得到的值。不斷地往回遞推計(jì)算，最終可以得到的值，此即為需要求的控制頂點(diǎn)

圖1 B樣條曲線的de Boor求值算法

圖2 de Boor求值算法中控制頂點(diǎn)的遞推過(guò)程

如果插值點(diǎn)的個(gè)數(shù)大于曲線P(u)的次數(shù)，即t>p，則在計(jì)算得到所有新的節(jié)點(diǎn)值si(i=1, 2…, t)之后，以

為新的節(jié)點(diǎn)矢量，將曲線P(u)在末端進(jìn)行端點(diǎn)松弛化處理，延伸曲線控制頂點(diǎn)的計(jì)算方法與前述相同。

2.2 節(jié)點(diǎn)修正

節(jié)點(diǎn)矢量的選擇對(duì)B樣條曲線的形狀起著非常重要的作用，使用B樣條的關(guān)鍵之一就是是否能確定好的節(jié)點(diǎn)矢量[7]。不合理的節(jié)點(diǎn)矢量會(huì)使B樣條曲線的形狀發(fā)生波動(dòng)或扭曲，從而使得其形狀不能滿足要求。對(duì)于曲線的插值，節(jié)點(diǎn)矢量的配置相對(duì)比較容易直接。然而，對(duì)于曲線逼近來(lái)說(shuō)，要確定節(jié)點(diǎn)矢量的位置和數(shù)量則是相當(dāng)困難的一件事情[8]。

在帶光滑有序點(diǎn)列約束的B樣條曲線延伸過(guò)程中，同時(shí)存在著插值和逼近。一旦插值點(diǎn)被選定之后，新節(jié)點(diǎn)的數(shù)量和位置都已經(jīng)確定，但是，如何確定這些節(jié)點(diǎn)的值仍是一個(gè)相當(dāng)棘手的問(wèn)題。通常情況下，由式(6)計(jì)算得到的新的節(jié)點(diǎn)值并不是最佳值，因?yàn)樵撚?jì)算方法并沒有把逼近點(diǎn)考慮進(jìn)去。因此，若以此節(jié)點(diǎn)矢量將原曲線進(jìn)行延伸之后，雖然延伸曲線能夠插值所有的插值點(diǎn)，但是曲線的延伸部分可能偏離逼近點(diǎn)較大的距離，如圖3(b)所示，甚至可能會(huì)發(fā)生扭曲的現(xiàn)象，如圖3(e)所示。這使得延伸曲線無(wú)法滿足誤差和光順性要求，而且還會(huì)影響到算法的效率和穩(wěn)定性。眾所周知，一條p次的B樣條曲線的形狀由它的控制頂點(diǎn)和節(jié)點(diǎn)矢量唯一確定。由式(3)、式(4)和式(7)可知，與曲線延伸部分對(duì)應(yīng)的控制頂點(diǎn)由延伸后曲線的節(jié)點(diǎn)矢量和原曲線端點(diǎn)松弛化后的部分控制頂點(diǎn)共同確定。因此，可以將新的節(jié)點(diǎn)看作變量并對(duì)其進(jìn)行修正來(lái)控制延伸部分曲線的形狀。為討論方便，本文只考慮p=3時(shí)的情形，當(dāng)曲線的次數(shù)為其它值時(shí)情況是類似的。

圖3 有無(wú)節(jié)點(diǎn)修正對(duì)帶點(diǎn)列約束的B-樣條曲線延伸結(jié)果的影響

2.2.1 單個(gè)插值點(diǎn)的情況

如果只有一個(gè)插值點(diǎn)RM，則延伸后曲線Q(u)的節(jié)點(diǎn)矢量為：U5={0,0,0,0,u4,...,un,1,s1, s1, s1, s1}，其中，s1由式(6)計(jì)算求得，此時(shí)控制頂點(diǎn)與點(diǎn)RM重合。由式(3)和式(4)可知，當(dāng)s1發(fā)生改變時(shí)，控制頂點(diǎn)中只有和會(huì)受到影響而發(fā)生相應(yīng)地改變，需要重新計(jì)算其位置，而其余的控制頂點(diǎn)均保持不變。在只有一個(gè)插值點(diǎn)的情況下，曲線延伸部分的形狀完全由s1決定，因此，如果能用一個(gè)更優(yōu)的節(jié)點(diǎn)值w1來(lái)替換s1便可以改善曲線延伸部分的形狀。所以，特別地將w1表示為如下形式：

其中k1>0稱作修正系數(shù)。以U5為新的節(jié)點(diǎn)矢量用上節(jié)的方法對(duì)原曲線P(u)進(jìn)行延伸，并將曲線延伸部分的弧長(zhǎng)記為S1，若將所有約束點(diǎn)的弦長(zhǎng)總和記為C1，即：

則有：

由于約束點(diǎn)的形狀可能千差萬(wàn)別，所以，試圖找到一個(gè)通用的計(jì)算公式來(lái)計(jì)算k1的值是不現(xiàn)實(shí)的。所以，宜采用迭代的方法來(lái)近似計(jì)算最優(yōu)的k1值，從而得到近似最優(yōu)的節(jié)點(diǎn)值w1。

以U5為新的節(jié)點(diǎn)矢量對(duì)原曲線P(u)進(jìn)行延伸后，如果約束點(diǎn)到延伸曲線Q(u)的最大距離大于給定的容差E，則令：

2.2.2 多個(gè)插值點(diǎn)的情況

則最優(yōu)化問(wèn)題式(14)可轉(zhuǎn)換為如下形式：

最優(yōu)化問(wèn)題式(15)為帶線性約束的非線性最優(yōu)化問(wèn)題的標(biāo)準(zhǔn)形式，可采用投影梯度法[9]來(lái)求解該問(wèn)題。將作為問(wèn)題式(15)的初始可行解，由于初始可行解通常距離最優(yōu)解較近，并且在帶光滑點(diǎn)列約束的曲線延伸過(guò)程中插值點(diǎn)的個(gè)數(shù)通常不多，所以，該求解過(guò)程通常能在較少的迭代次數(shù)之后終止。在本文作者所測(cè)試的例子中，求解過(guò)程都能夠收斂。

2.3 算法描述

給定一條光滑的 B樣條曲線以及一光滑有序約束點(diǎn)列，首先，以約束點(diǎn)列中的最末點(diǎn)作為唯一的插值點(diǎn)將B樣條曲線進(jìn)行延伸。計(jì)算約束點(diǎn)列中各點(diǎn)到延伸曲線的距離，如果最大距離大于預(yù)先給定的閾值，則將點(diǎn)列中與延伸曲線距離最大的點(diǎn)作為下一個(gè)插值點(diǎn)加入到插值點(diǎn)集中，并以新的插值點(diǎn)集將原 B樣條曲線重新進(jìn)行延伸。重復(fù)這一過(guò)程，不斷地加入新的插值點(diǎn)，直到最大距離小于給定的閾值或者所有的約束點(diǎn)都被選為插值點(diǎn)為止。帶光滑點(diǎn)列約束的B樣條曲線延伸的算法流程如圖4所示。

圖5給出了一些帶光滑點(diǎn)列約束的曲線延伸的例子，并用黑點(diǎn)標(biāo)出的約束點(diǎn)為最終的插值點(diǎn)。從誤差的角度出發(fā)，當(dāng)插值點(diǎn)的個(gè)數(shù)逐漸增多時(shí)，延伸曲線與約束點(diǎn)列之間的最大距離是不斷減小的。但是，隨著插值點(diǎn)個(gè)數(shù)不斷增多，延伸曲線的形狀將會(huì)出現(xiàn)波動(dòng)或扭曲的現(xiàn)象，而且也會(huì)影響到算法效率。但對(duì)于光滑的約束點(diǎn)列，通常只需插值少數(shù)幾個(gè)點(diǎn)便可使得延伸后的曲線滿足誤差要求。

3 帶曲線約束的B樣條曲面延伸

帶光滑點(diǎn)列約束的 B樣條曲線延伸算法可以推廣到帶B樣條曲線列約束的B樣條曲面延伸。一張p×q次的B樣條曲面可表示為如下形式：

圖4 帶光滑有序點(diǎn)列約束的B樣條曲線延伸算法流程圖

圖5 帶點(diǎn)列約束的三次B-樣條曲線延伸實(shí)例

為方便起見，本文只討論曲面S(u, v)沿v向的約束延伸問(wèn)題，沿u向的延伸完全類似。設(shè)B樣條曲線約束為Tl(u)(l=1,2,..., M)，不失一般性，這里假設(shè)所有約束曲線的次數(shù)均為p，并且節(jié)點(diǎn)矢量都為U0（如若不相同，可以采用升階算法和節(jié)點(diǎn)插入算法使得所有約束曲線的次數(shù)和節(jié)點(diǎn)矢量相同）。將曲線 Tl(u)的控制頂點(diǎn)記為，約束曲線中的插值曲線集記為，與其相對(duì)應(yīng)的v向參數(shù)值記為{s1,s2,...,st}，并將{s1,s2,...,st}作為延伸后曲面的v向節(jié)點(diǎn)值，則曲面S(u,v)沿v向延伸后的新節(jié)點(diǎn)矢量將變成：

將曲面S(u,v)沿v向在邊界S(u,1)處進(jìn)行松弛化之前，必須先計(jì)算{s1,s2,...,st}的值。這里，仍采用式(6)來(lái)計(jì)算si的值，但此時(shí)需用兩條B樣條曲線之間的“距離”來(lái)取代兩點(diǎn)之間的距離。將相鄰的兩條約束曲線之間的“距離”定義為：

圖6 帶曲線約束的B樣條曲面延伸實(shí)例

4 結(jié) 論

本文提出了一種帶光滑有序點(diǎn)列約束的 B樣條曲線延伸算法，并將該算法推廣到了帶B樣條曲線約束的B樣條曲面延伸。運(yùn)用該算法得到的延伸曲線與原曲線之間能夠自然達(dá)到所允許的最高階連續(xù)，且原曲線在整個(gè)延伸過(guò)程中始終保持不變。但是當(dāng)約束點(diǎn)列不夠光滑或存在波動(dòng)時(shí)，所需的插值點(diǎn)個(gè)數(shù)會(huì)增多，從而影響到該算法的效率以及延伸曲線的品質(zhì)，下一步將對(duì)此進(jìn)行重點(diǎn)研究。

[1] 周元峰, 張彩明. G2連續(xù)約束下三次 Bézier曲線的延拓[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2005, 17(3): 425-430.

[2] 余正生, 雷 毅. NURBS曲線曲面延伸[J]. 工程圖學(xué)學(xué)報(bào), 1997, 18(1): 7-18.

[3] Shetty S, White P R. Curvature-continuous extensions for rational B-spline curves and surfaces [J]. Computer-Aided Design, 1991, 23(7): 484-491.

[4] Chivate P N, Puntambekar N V, Jablokow A G. Extending surfaces for reverse engineering solid model generation [J]. Computers in Industry, 1999, 38(3): 285-294.

[5] Hu Shimin, Tai Chiewlan, Zhang Songhai. An extension algorithm for B-splines by curve unclamping [J]. Computer-Aided Design, 2002, 34(5): 415-419.

[6] Piegl L A, Tiller W. The NURBS book [M]. New York: Springer-Verlag, 1997: 572-580.

[7] Farin G. Curves and surfaces for CAGD [M]. San Francisco: Morgan Kaufmann, 2002

[8] Li Weishi, Xu Shuhong, Zhao Gang, et al. Adaptive knot placement in B-spline curve approximation [J]. Computer-Aided Design, 2005, 37: 791-797.

[9] Hadley G. Nonlinear and Dynamic Programming [M]. Massachusetts: Addison-Wesley Publishing Company, Inc, 1964: 315-323.

B-spline Curves and Surfaces Extension with Constraints

Xu Jin
( School of Mechanical and Automative Engineering, Zhejiang University of Science and Technology, Hangzhou Zhejiang 310023, China )

An algorithm for extending B-spline curves with a sequence of ordered points constraint is presented based on the curve unclamping algorithm. The most important feature of this algorithm is the ability to optimize the knots of the extended curve segment according to the ordered points. Thus, with minimum number of interpolation points, the maximum deviation of the extended curve segment from the ordered points is less than the given tolerance. The extended curve segment connects to the original curve with maximum continuity intrinsically. Further more, this algorithm can be applied to the extension of B-spline surfaces with the constraints of a sequence of B-spline curves. Several experimental results have shown the validity and applicability of the proposed algorithm.

B-spline; extension; ordered points constraints; knots modification

TP 391

A

2095-302X (2013)03-0036-07

2012-06-23；定稿日期：2012-09-24

浙江省教育廳資助項(xiàng)目（Y201119634）；浙江省自然科學(xué)基金資助項(xiàng)目（LQ13E050015）

徐 進(jìn)（1981-），男，江西上饒人，講師，博士，主要研究方向?yàn)槟嫦蚬こ獭AD、CAGD。E-mail：xujin206@126.com