徐 進

（浙江科技學院機械與汽車工程學院，浙江 杭州 310023）

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

徐 進

（浙江科技學院機械與汽車工程學院，浙江 杭州 310023）

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

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

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

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

1 B樣條曲線端點松弛算法

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

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

其中：

2 帶光滑有序點列約束的B樣條曲線延伸

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

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

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

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

圖1所示為B樣條曲線的de Boor求值算法的計算過程，圖2為相應的控制頂點遞推示意圖。從圖1和圖2可以看出，當未知時，整個計算過程中只有未知。如果令，運用de Boor求值公式（7）可以計算得到的值。類似地，當和已知時，可以計算得到的值。不斷地往回遞推計算，最終可以得到的值，此即為需要求的控制頂點

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

圖2 de Boor求值算法中控制頂點的遞推過程

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

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

2.2 節(jié)點修正

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

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

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

2.2.1 單個插值點的情況

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

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

則有：

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

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

2.2.2 多個插值點的情況

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

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

2.3 算法描述

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

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

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

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

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

圖5 帶點列約束的三次B-樣條曲線延伸實例

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

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

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

4 結(jié) 論

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

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

[2] 余正生, 雷 毅. NURBS曲線曲面延伸[J]. 工程圖學學報, 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

浙江省教育廳資助項目（Y201119634）；浙江省自然科學基金資助項目（LQ13E050015）

徐 進（1981-），男，江西上饒人，講師，博士，主要研究方向為逆向工程、CAD、CAGD。E-mail：xujin206@126.com