何振華

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

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

中圖分類號：TP301.6 文獻標志碼：A 文章編號：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 引言

曲線曲面變形方法在幾何造型、計算機動畫、圖像Morphing技術中有著廣泛的應用。

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

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

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

1.1 算法原理

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

設想將曲線C1（或C2）變形為曲線C2（或C1）。

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

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

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

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

，

假設存在線性變換：

y=mx+n ⑴

使得

⑵

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

即：

可得關于m，n的惟一解

⑶

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

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

1.2 算法描述

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

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

圖1 算法流程圖

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

2 以Lagrange插值為基礎的曲線變形方法

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

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

⑴ 算法描述

給定兩條二次曲線段：

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

通過三個線性變換

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

其中

⑸

將采樣點

變換為對應的采樣點

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

⑹

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

⑵ 算法的時間復雜度

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

2.2 復雜曲線間的變形處理

⑴ 算法描述及算法復雜度

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

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

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

⑵ 數(shù)值實例

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

⑺

⑻

圖2 曲線C1

圖3 曲線C2

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

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

（-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ù)⑷和⑸計算得出三個線性變換為

（11）

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

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

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

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

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

⑶ 幾點說明

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

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

3 結束語

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

參考文獻：

[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權因子調整的FFD直接操作[J].計算機學

報，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