曲線(xiàn)插值的一種具有還圓性的細(xì)分方法

韓 靖， 韓旭里

（中南大學(xué)數(shù)學(xué)科學(xué)與計(jì)算技術(shù)學(xué)院，湖南 長(zhǎng)沙 410083）

插值細(xì)分方法是一種離散數(shù)據(jù)插值，是計(jì)算機(jī)輔助幾何設(shè)計(jì)中用于曲線(xiàn)曲面表示的重要方法。由于細(xì)分方法通常沒(méi)有顯式表達(dá)式，僅提供一個(gè)算法描述過(guò)程，具有簡(jiǎn)單、高效等特點(diǎn)，所以特別適用于計(jì)算機(jī)表示。近年來(lái)，細(xì)分方法引起越來(lái)越多的關(guān)注。

傳統(tǒng)細(xì)分方法有切割磨光法和四點(diǎn)插值法，已經(jīng)有許多學(xué)者作了相關(guān)研究[1-10]。切割磨光法是逼近型細(xì)分方法，具有逼近性，光滑性，保凸性等優(yōu)點(diǎn)，其中Chaikin方法已被證明其極限曲線(xiàn)是由已知控制多邊形所定義的二次 B樣條曲線(xiàn)[1-2]，但其極限曲線(xiàn)不經(jīng)過(guò)控制頂點(diǎn)。文獻(xiàn)[3]中的四點(diǎn)插值細(xì)分法，極限曲線(xiàn)可以表示三次B樣條曲線(xiàn)。二次B樣條曲線(xiàn)和三次B樣條曲線(xiàn)作為分段多項(xiàng)式曲線(xiàn)，不能精確表示橢圓曲線(xiàn)。四點(diǎn)插值法是線(xiàn)性細(xì)分方法，簡(jiǎn)單易懂，但沒(méi)有考慮控制多邊形的幾何形狀，單從解析角度構(gòu)造新點(diǎn)，不易對(duì)曲線(xiàn)的幾何形狀進(jìn)行控制[8]，且其極限曲線(xiàn)上可能有多余的拐點(diǎn)等[7]。

近年來(lái)，細(xì)分方法對(duì)保形性作了許多研究。為了使產(chǎn)生的細(xì)分曲線(xiàn)具有更好的保形性，文獻(xiàn)[11]提出了一種基于法向量的細(xì)分方法，可以證明這種方法產(chǎn)生的曲線(xiàn)G1連續(xù)，只要選取合適的參數(shù)，此方法為保形細(xì)分算法，而且具有許多優(yōu)美的性質(zhì)，例如：可以插值在指定點(diǎn)的法向量、可以生成圓錐曲線(xiàn)、直邊等。文獻(xiàn)[12]提出了一種基于切向的幾何插值型保凸細(xì)分方法，在細(xì)分的過(guò)程中，每條邊所對(duì)應(yīng)的新控制頂點(diǎn)由原控制頂點(diǎn)及其切向確定。該方法產(chǎn)生的極限曲線(xiàn)是G1連續(xù)的，且較為美觀(guān)。由于保凸等性質(zhì)對(duì)于線(xiàn)性細(xì)分較難達(dá)到，目前，非線(xiàn)性細(xì)分方法已成為研究的重點(diǎn)內(nèi)容。

本文針對(duì)傳統(tǒng)線(xiàn)性細(xì)分方法不能表示圓等非多項(xiàng)式曲線(xiàn)的情況，基于控制頂點(diǎn)的幾何關(guān)系提出一種新的四點(diǎn)細(xì)分方法，如果初始控制頂點(diǎn)都取自同一個(gè)圓上，那么本方法所得極限曲線(xiàn)就是這個(gè)圓。

1 基于幾何特性的四點(diǎn)細(xì)分法

細(xì)分法是通過(guò)不斷地加入新點(diǎn)構(gòu)造細(xì)分曲線(xiàn)。給定初始點(diǎn)列 {}i，四點(diǎn)插值型細(xì)分方法為

其中G表示一種構(gòu)造，G的選取，也就是如何選擇是插值細(xì)分方法的關(guān)鍵。

我們知道，過(guò)不在同一直線(xiàn)上的相鄰三點(diǎn)可以作一個(gè)圓。這樣，過(guò)相鄰二插值點(diǎn)的圓弧有兩條。我們的方法是取這兩條圓弧的中點(diǎn)，將其加權(quán)平均得到新插值點(diǎn)。

1.1 計(jì)算插值點(diǎn)

對(duì)于第k層的點(diǎn)列{}，若3點(diǎn)i不共線(xiàn)，則它們確定一個(gè)圓，記為。為邊與邊的垂直平分線(xiàn) 的交點(diǎn)，滿(mǎn)足

得到新插值點(diǎn)，其中ω為權(quán)數(shù)，可用于調(diào)整曲線(xiàn)的形狀。

結(jié)合式(2)～(7)即為式(1)中的函數(shù)G。

對(duì)于第k層的點(diǎn)列{，設(shè)第k層節(jié)點(diǎn)總數(shù)是n。當(dāng)要生成封閉曲線(xiàn)時(shí)，點(diǎn)即；點(diǎn)。若要生成的曲線(xiàn)是開(kāi)曲線(xiàn)，計(jì)算時(shí)，可用。這樣保證了方法的可行性，也充分提取了控制頂點(diǎn)的信息。

圖1 計(jì)算插值點(diǎn)

1.2 算法描述

作圖時(shí)，新點(diǎn)的數(shù)量不需要無(wú)窮多，只需達(dá)到曲線(xiàn)在視覺(jué)上連續(xù)即可。定義Δ為任意相鄰兩點(diǎn)間的最大距離（包括初始點(diǎn)和最末點(diǎn)之間的距離）的上限，當(dāng)點(diǎn)列中任意相鄰兩點(diǎn)間的距離都小于Δ時(shí)，曲線(xiàn)即達(dá)到視覺(jué)上連續(xù)，Δ的取值依賴(lài)于顯示設(shè)備。該細(xì)分方法可用如下算法過(guò)程描述：

步 0 給定有0n個(gè)頂點(diǎn)的初始封閉凸多邊形頂點(diǎn)點(diǎn)列及權(quán)數(shù)ω，令 :k= 0。

步 1 若要生成閉曲線(xiàn)，則令

顯然，當(dāng)所有初始控制頂點(diǎn)都取自同一個(gè)圓上時(shí)，新的插值點(diǎn)仍然在這個(gè)圓上，因此，本文的方法具有還圓性。

2 數(shù)值實(shí)例

作數(shù)值實(shí)例分析將本文方法與經(jīng)典的切割磨光法與四點(diǎn)插值法以及文獻(xiàn)[12]提出的基于幾何切向的六點(diǎn)插值細(xì)分法對(duì)比作對(duì)比，其中切割磨光法取 Chaikin算法，即==1/4，細(xì) 分規(guī)則是

其中，N是初始頂點(diǎn)個(gè)數(shù)。四點(diǎn)插值法采用Dubuc格式[9]

文獻(xiàn)[12]提出了一種基于幾何切向的六點(diǎn)插值型細(xì)分方法，具有還圓性，以及保凸性等性質(zhì)。

例1 取初如控制頂點(diǎn)(-1, -1), (0, 0), (0.5, 0),(1.8, 0), (3.2, 0.5), (4, -1)，3點(diǎn)(0,0), (0.5,0), (1.8,0)共線(xiàn)，用本文方法取0.5ω=，曲線(xiàn)見(jiàn)圖2，共線(xiàn)3點(diǎn)之間并非直線(xiàn)。曲線(xiàn)在共線(xiàn)點(diǎn)間的形狀取決于相鄰不共線(xiàn)點(diǎn)的偏離程度，偏離得越近，曲線(xiàn)越趨于直線(xiàn)。

圖2 本文方法例1

例 2 取初始控制頂點(diǎn)(1,0), (0,1), (-1,0),(0,-1)，生成閉曲線(xiàn)。分別用本文方法取0.5ω=和經(jīng)典的切割磨光法與四點(diǎn)插值法的Dubuc格式，曲線(xiàn)見(jiàn)圖3、圖4、圖5?？梢?jiàn)本文的方法可以完整的還圓，這從方法的推導(dǎo)過(guò)程也可得出，若所有初始點(diǎn)都在同一圓上，則相同，進(jìn)而也與相同，都是圓上的點(diǎn)。切割磨光法與四點(diǎn)插值法都不具有還圓性。

圖3 本文方法例2

圖4 切割磨光法例2

圖5 四點(diǎn)插值法例2

例3 取初始控制頂點(diǎn)(0,0), (0.2425,1.3751),(-2.6241,0.9551), (-2.0944,-3.6276), (4.2784,-3.5900),(5.3480,4.4875), (-4.1888,7.2552), (-9.1844,-3.3429),(1.9397,-11.0004)，用本文方法取0.5ω=和切割磨光法繪制開(kāi)曲線(xiàn)，見(jiàn)圖 6、圖 7。本文方法可繪制出曲率半徑變化比較光滑的螺旋，切割磨光法繪制曲線(xiàn)不經(jīng)過(guò)控制頂點(diǎn)，曲線(xiàn)的曲率半徑變化也不光滑，曲線(xiàn)形狀更趨向控制多邊形。

圖6 本文方法例3

圖7 切割磨光法例3

例4 給定初始控制多邊形頂點(diǎn)為(3.0000,0),(0.3090,0.9511), (-0.8090,0.5878), (-0.8090,-0.5878),(0.3090,-0.9511)，采用本文方法取0.2ω=、四點(diǎn)插值法和文獻(xiàn)[12]提出的細(xì)分法繪制曲線(xiàn)，如圖8、圖9所示。與文獻(xiàn)[12]的方法相比，本文方法的極限曲線(xiàn)更靠近控制多邊形。

圖8 本文方法例4

圖9 文獻(xiàn)[12]的方法例4

例 5 設(shè)初始控制頂點(diǎn)(1.0,1.0), (1.2,2.1),(2.0,2.5), (2.5,1.8), (3.0,1.5), (3.4,2.6), (4.0,3.2),(4.4,3.1), (5.0,2.0)，用本文方法，分別取ω=0.3，ω= 0 .7繪制曲線(xiàn)。結(jié)果見(jiàn)圖10、圖11。對(duì)比可知ω取值越小，曲線(xiàn)越靠近控制多邊形，但光滑性不佳；當(dāng)ω增大，曲線(xiàn)遠(yuǎn)離控制多邊形，且較為圓滑。

圖10 例5中ω=0.3

圖11 例5中ω=0.7

3 結(jié) 論

本文針對(duì)傳統(tǒng)細(xì)分方法不能表示圓等非多項(xiàng)式曲線(xiàn)的限制，基于幾何提出了一種含有一個(gè)參數(shù)的四點(diǎn)插值細(xì)分方法。這種方法的推導(dǎo)比較簡(jiǎn)單，給出了插值點(diǎn)計(jì)算公式和算法描述。與切割磨光法和四點(diǎn)插值法相比，本文的方法具有還圓性，可以實(shí)現(xiàn)保凸性，極限曲線(xiàn)較光順。參數(shù)可以控制曲線(xiàn)與控制多邊形的接近程度，參數(shù)取較小值時(shí)曲線(xiàn)靠近控制多邊形。

由于本文提出的計(jì)算公式是一種非線(xiàn)性表示，方法的收斂性，光滑性等證明和與參數(shù)取值的關(guān)系還需要進(jìn)一步研究。參數(shù)為0時(shí)曲線(xiàn)保凸這一條件較為嚴(yán)格，參數(shù)的取值范圍應(yīng)與保凸性具有某種關(guān)系。這些是接下來(lái)工作的重點(diǎn)。

[1]Chaikin G M. An algorithm for high speed curve generation [J]. Computer Graphics and Image Processing, 1974, 3(4): 346-349.

[2]Riesenfeld R F. On Chainik’s algorithm [J]. IEEE Computer Graphices and Applications, 1975, 4(3):304-310.

[3]Catmull E, Clark J. Recursively generated B-spline surfaces on arbitrary topological meshes [J].Computer Aided Design, 1978, 10(6): 350-355.

[4]Hassan M F, Ivrissimitzis I P, Dodgson N A, et al. An interpolating 4-point C2 ternary sationary subdivion scheme [J]. Computer Aided Geometric Design, 2002,19(5): 1-18.

[5]Dyna N, Levina D, Liu D. Interpolatory convexity-preserving subdivision schemes for curves and surfaces [J]. Computer-Aided Design, 1990,24(4): 221-216.

[6]Méhautéa A L, Utreras F I. Convexity-preserving interpolatory subdivision [J]. Computer Aided Geometric Design, 1994, 11(1): 17-37.

[7]Marinov M, Dyn N, Levin D. Geometrically controlled 4-point interpolatory Schemes [C]//Neil D,Michael S F, Malcolm S. Advances in Multiresolution for Geometric Modelling. London:Springer-Verlag, 2005: 301-315.

[8]Dyn N, Levin D, John A. A 4-point interpolatory subdivision scheme for curve design [J]. Computer Aided Geometric Design, 1987, 4(4): 257-268.

[9]Dubuc S. Interpolation through an iterative scheme [J].Journal of Mathematical Analysis and Applications,1986, 114(1): 185-204.

[10]曹 沅. 四點(diǎn)插值細(xì)分算法極限曲線(xiàn)曲面C2連續(xù)的充分必要條件[J]. 計(jì)算機(jī)輔助幾何設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2003, 15(8): 961-966.

[11]Yang Xunnian. Normal based subdivision scheme for curve design [J]. Computer Aided Geometric Design,2006, 23(4): 243-260.

[12]鄧重陽(yáng), 汪國(guó)昭. 曲線(xiàn)插值的一種保凸細(xì)分方法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2009, 21(8):1042-1046.