基于采樣數(shù)據(jù)線性變換的曲線變形方法

何振華

摘 要： 基于采樣數(shù)據(jù)的線性變換，提出了一種曲線變形的思想；設(shè)計(jì)一種以Lagrange插值為基礎(chǔ)的曲線變形算法，并進(jìn)行算法復(fù)雜度分析。該方法能實(shí)現(xiàn)代數(shù)曲線間的變形處理，具有普遍的適用性和較高的計(jì)算精度。通過給出數(shù)值實(shí)例，驗(yàn)證了算法的有效性和可行性，該算法提供了曲線變形的一種有效途徑。

關(guān)鍵詞： 采樣數(shù)據(jù)； 線性變換； 曲線變形； Lagrange插值； 算法

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2014）10-51-03

Curve deformation based on linear transformation of sampling data

He Zhenhua

（School of Information， Hangzhou Science & Technology Vocational Technical College， Hangzhou， Zhejiang 311402， China）

Abstract： The solution to the problem of curve deformation by the linear transformation of sampling data is put forward. The algorithm based on the Lagrange interpolation is designed. The complexity of the algorithm is discussed. The deformation method is researched in details. The result can be used to carry out the deformation of algebraic curves. The feasibility and validity of the algorithm is demonstrated by numerical experiment. The practice has proved that it provided an efficient approach to the problem of curve deformation.

Key words： sampling data； linear transformation； curve deformation； lagrange interpolation； algorithm

0 引言

曲線曲面變形方法在幾何造型、計(jì)算機(jī)動(dòng)畫、圖像Morphing技術(shù)中有著廣泛的應(yīng)用。

相關(guān)的研究工作已取得了不少成果。1984年Barr首先提出了整體與局部的變形方法[1]，首次將變形方法引入到幾何造型領(lǐng)域，該方法能夠進(jìn)行常規(guī)變形。1986年Sederberg和Parry提出了自由變形（FFD）的方法[2]，該方法將變形操作用于物體所嵌入的變形空間，嵌入其中的物體形狀隨之發(fā)生變化，但該方法計(jì)算量比較大，時(shí)間復(fù)雜度為O（n3）。隨后所提出的EFFD[3]、NFFD[4]、DFFD[5-7]、RFFD[8]都對(duì)FFD方法進(jìn)行了改進(jìn)和補(bǔ)充。

對(duì)比這些變形方法發(fā)現(xiàn)，這些變形方法的主要局限是：計(jì)算量大、理論分析復(fù)雜等。如DFFD控制頂點(diǎn)的反求是通過計(jì)算偽逆矩陣實(shí)現(xiàn)、軸變形方法在計(jì)算最近點(diǎn)時(shí)會(huì)產(chǎn)生二義性等等。本文提出的曲線變形算法對(duì)曲線上的離散采樣數(shù)據(jù)作線性變換，以Lagrange插值為基礎(chǔ)，利用采樣數(shù)據(jù)對(duì)之間的轉(zhuǎn)換實(shí)現(xiàn)兩條曲線的互相變換，數(shù)值實(shí)例表明該算法計(jì)算簡(jiǎn)單，具有普遍的適用性及較高的計(jì)算精度。

1 采樣數(shù)據(jù)線性變換

1.1 算法原理

給定兩條代數(shù)曲線：

設(shè)想將曲線C1（或C2）變形為曲線C2（或C1）。

直接實(shí)現(xiàn)曲線C1，C2之間的相互轉(zhuǎn)換往往是困難的，這里尋求間接的曲線變形方法。

分別對(duì)兩條曲線作離散采樣，得兩組數(shù)據(jù)：

首先考慮實(shí)現(xiàn)這兩組數(shù)據(jù)之間的相互轉(zhuǎn)換。

對(duì)于給定的一對(duì)數(shù)據(jù)

，

假設(shè)存在線性變換：

y=mx+n ⑴

使得

⑵

根據(jù)Cramer法則，只要

即：

可得關(guān)于m，n的惟一解

⑶

這說明，通過線性變換可以實(shí)現(xiàn)采樣數(shù)據(jù)對(duì)之間的轉(zhuǎn)換。

要實(shí)現(xiàn)曲線C1，C2之間的相互轉(zhuǎn)換，只需由采樣數(shù)據(jù)重建曲線C1（或C2）即可。這里可以考慮采用Lagrange插值方法實(shí)現(xiàn)。

1.2 算法描述

上述算法流程以框圖形式描述，如圖1所示。

[C1][線性變換][采樣][重建] [C2] [y=mx+n][采樣][重建]

圖1 算法流程圖

需要說明的是，算法要求兩條曲線上的采樣數(shù)據(jù)點(diǎn)個(gè)數(shù)相同，同時(shí)要滿足，但對(duì)采樣方法沒有限制，等距采樣和非等距采樣不影響算法的實(shí)施，為保證重建后的曲線具有良好的光滑性質(zhì)，采樣數(shù)據(jù)可以綜合考慮采樣點(diǎn)處的導(dǎo)數(shù)信息。

2 以Lagrange插值為基礎(chǔ)的曲線變形方法

在將曲線C1的采樣數(shù)據(jù)經(jīng)過線性變換轉(zhuǎn)化為曲線C2的采樣數(shù)據(jù)以后，余下的問題就是根據(jù)C2的采樣點(diǎn)重建曲線C2?？紤]到Lagrange插值具有計(jì)算復(fù)雜度較低的特點(diǎn)，這里給出基于Lagrange插值的曲線變形方法。

2.1 兩段二次曲線之間的變形

⑴ 算法描述

給定兩條二次曲線段：

分別在這兩條曲線段上作離散采樣，得兩組三對(duì)數(shù)據(jù)

通過三個(gè)線性變換

y=mkx+nk，k=0，1，2 ⑷

其中

⑸

將采樣點(diǎn)

變換為對(duì)應(yīng)的采樣點(diǎn)

根據(jù)離散點(diǎn)，利用二次Lagrange插值方法的容易得到曲線C2的方程。

⑹

根據(jù)代數(shù)插值理論，n次Lagrange插值結(jié)果對(duì)次數(shù)不高于n次的多項(xiàng)式是準(zhǔn)確的，因此，式⑹的結(jié)果對(duì)于二次曲線段是準(zhǔn)確的。

⑵ 算法的時(shí)間復(fù)雜度

采樣過程最多用到2×3×3=18次乘法，采樣點(diǎn)變換過程最多用到3×5=15次乘法，重建過程最多用到3×3×3=27次乘法，整個(gè)變形過程最多用到18+15+27=60次乘法。

2.2 復(fù)雜曲線間的變形處理

⑴ 算法描述及算法復(fù)雜度

對(duì)于復(fù)雜或高次曲線段之間的變形處理，擬采取如下策略：分別將曲線C1，C2按照凹凸性進(jìn)行分段，在每個(gè)分段區(qū)間上，以二次曲線描述每一條曲線段，其實(shí)質(zhì)是按照曲線的凹凸區(qū)間用分段二次插值表示曲線C1，C2，然后移植二次曲線段變形算法，在對(duì)應(yīng)的分段區(qū)間上作變形處理。

依據(jù)前述二次曲線段變形算法的結(jié)論，上述算法在每個(gè)凹凸區(qū)間上可以實(shí)現(xiàn)C1，C2之間的準(zhǔn)確變形，從而可以在曲線的整個(gè)定義域上取得良好的變形效果。

顯然，如果將復(fù)雜曲線分割為n段， 則整個(gè)曲線變形所需乘法次數(shù)為60n。

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

給定曲線（如圖2、圖3所示）：

⑺

⑻

圖2 曲線C1

圖3 曲線C2

設(shè)想通過采樣數(shù)據(jù)的線性變換將曲線C1變形為曲線C2，依據(jù)曲線的凹凸性對(duì)兩條曲線的定義域進(jìn)行分割：

在曲線C1，C2對(duì)應(yīng)的第一分段區(qū)間[-0.4，-0.1714]和[-0.5，-0.1803]上分別采樣得到對(duì)應(yīng)的三對(duì)數(shù)據(jù)點(diǎn)：

（-0.4，0.2351），（-0.25，0.25），（-0.1714，0.1510） ⑼

和

（-0.5.-0.8438），（-0.25，-0.7012），（-0.1803，-0.8095） （10）

根據(jù)⑷和⑸計(jì)算得出三個(gè)線性變換為

（11）

通過上述線性變換，可以成功地將數(shù)據(jù)⑼轉(zhuǎn)換為數(shù)據(jù)（10）。

現(xiàn)在，由數(shù)據(jù)點(diǎn)（10）重建曲線C2的第一段，即位于區(qū)間[-0.5，-0.1803]上的部分，根據(jù)式⑹得

C21：y=-1.38915-4.41287x-6.64436x2

完全類似地，可以將曲線C1的第二、三兩段變形為曲線C2的對(duì)應(yīng)部分，變形后的結(jié)果為（如圖4，圖5，圖6和圖7所示）：

比較圖3和圖7不難發(fā)現(xiàn)，變形效果是非常理想的。

⑶ 幾點(diǎn)說明

① 上述例子的兩條曲線的分割段數(shù)是相等的，對(duì)于兩條曲線按凹凸性分割段數(shù)不相等的情形，可以對(duì)分割段數(shù)較少的曲線的分段區(qū)間重復(fù)計(jì)數(shù)，即同一區(qū)間多次計(jì)數(shù)，使得兩條曲線的分割段數(shù)相等，其實(shí)質(zhì)是將分割段數(shù)較少的曲線的某一分段變換為分割段數(shù)較多的曲線的幾個(gè)不同分段部分。

② 對(duì)于曲線段的退化情形即直線段之間的變形，以及直線段和曲線段之間的變形，算法同樣有效。

3 結(jié)束語

本文從曲線的離散采樣數(shù)據(jù)出發(fā)，詳細(xì)地討論了一種以Lagrange插值為基礎(chǔ)的曲線變形算法，該算法的實(shí)質(zhì)是在代數(shù)曲線的分段區(qū)間移植二次曲線段的變形算法，從而實(shí)現(xiàn)對(duì)代數(shù)曲線的變形處理。該算法避免了復(fù)雜的理論分析，計(jì)算簡(jiǎn)單，數(shù)值實(shí)例表明算法的變形效果較好，可以考慮將其推廣至幾何造型、計(jì)算機(jī)動(dòng)畫等領(lǐng)域。

參考文獻(xiàn)：

[1] BarrA H. Global and local deformations of solid p rimitives[J].

Computers & Graphics，1984.18（3）：21-30

[2] Sederberg TW， Parry S R. Free2form deformation of solid

geometric models[J]. Computer Graphics，1986.20（4）：151-160

[3] Coquillart S. Extended free-form deformation： A sculpting

geometric modeling[J].Computer Graphics，1990.24（4）：187-196

[4] Lamousin H J， Waggenspack W N. NURBS-based free-form

deformation[J]. IEEE Computer Graphics and Applications，1994.14（6）：59-65

[5] Hus W M，Hughes J F，Kaufman H.Direct manipulation of freeform

deformation[J]. Computer Graphics，1992.26（2）：177-184

[6] Hu S M，Zhang H，Tai C L et al.Direct manipulation of FFD：Efficient

explicit solutions and decomposable multiple point constraints，The Visual Computer，2001.17（6）：177-184

[7] 張慧，孫家廣.基于NURBS權(quán)因子調(diào)整的FFD直接操作[J].計(jì)算機(jī)學(xué)

報(bào)，2002.25（9）：910-915

[8] Kalra P，Mangil A，Thalmann N M，et al.Simulation of facial muscle

action based on rational free-form deformation[J].Computer Graphics Forum，1992.11（3）：59-69