基于采样数据线性变换的曲线变形方法

何振华

摘 要： 基于采样数据的线性变换，提出了一种曲线变形的思想；设计一种以Lagrange插值为基础的曲线变形算法，并进行算法复杂度分析。该方法能实现代数曲线间的变形处理，具有普遍的适用性和较高的计算精度。通过给出数值实例，验证了算法的有效性和可行性，该算法提供了曲线变形的一种有效途径。

关键词： 采样数据； 线性变换； 曲线变形； 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]，首次将变形方法引入到几何造型领域，该方法能够进行常规变形。1986年Sederberg和Parry提出了自由变形（FFD）的方法[2]，该方法将变形操作用于物体所嵌入的变形空间，嵌入其中的物体形状随之发生变化，但该方法计算量比较大，时间复杂度为O（n3）。随后所提出的EFFD[3]、NFFD[4]、DFFD[5-7]、RFFD[8]都对FFD方法进行了改进和补充。

对比这些变形方法发现，这些变形方法的主要局限是：计算量大、理论分析复杂等。如DFFD控制顶点的反求是通过计算伪逆矩阵实现、轴变形方法在计算最近点时会产生二义性等等。本文提出的曲线变形算法对曲线上的离散采样数据作线性变换，以Lagrange插值为基础，利用采样数据对之间的转换实现两条曲线的互相变换，数值实例表明该算法计算简单，具有普遍的适用性及较高的计算精度。

1 采样数据线性变换

1.1 算法原理

给定两条代数曲线：

设想将曲线C1（或C2）变形为曲线C2（或C1）。

直接实现曲线C1，C2之间的相互转换往往是困难的，这里寻求间接的曲线变形方法。

分别对两条曲线作离散采样，得两组数据：

首先考虑实现这两组数据之间的相互转换。

对于给定的一对数据

，

假设存在线性变换：

y=mx+n ⑴

使得

⑵

根据Cramer法则，只要

即：

可得关于m，n的惟一解

⑶

这说明，通过线性变换可以实现采样数据对之间的转换。

要实现曲线C1，C2之间的相互转换，只需由采样数据重建曲线C1（或C2）即可。这里可以考虑采用Lagrange插值方法实现。

1.2 算法描述

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

[C1][线性变换][采样][重建] [C2] [y=mx+n][采样][重建]

图1 算法流程图

需要说明的是，算法要求两条曲线上的采样数据点个数相同，同时要满足，但对采样方法没有限制，等距采样和非等距采样不影响算法的实施，为保证重建后的曲线具有良好的光滑性质，采样数据可以综合考虑采样点处的导数信息。

2 以Lagrange插值为基础的曲线变形方法

在将曲线C1的采样数据经过线性变换转化为曲线C2的采样数据以后，余下的问题就是根据C2的采样点重建曲线C2。考虑到Lagrange插值具有计算复杂度较低的特点，这里给出基于Lagrange插值的曲线变形方法。

2.1 两段二次曲线之间的变形

⑴ 算法描述

给定两条二次曲线段：

分别在这两条曲线段上作离散采样，得两组三对数据

通过三个线性变换

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

其中

⑸

将采样点

变换为对应的采样点

根据离散点，利用二次Lagrange插值方法的容易得到曲线C2的方程。

⑹

根据代数插值理论，n次Lagrange插值结果对次数不高于n次的多项式是准确的，因此，式⑹的结果对于二次曲线段是准确的。

⑵ 算法的时间复杂度

采样过程最多用到2×3×3=18次乘法，采样点变换过程最多用到3×5=15次乘法，重建过程最多用到3×3×3=27次乘法，整个变形过程最多用到18+15+27=60次乘法。

2.2 复杂曲线间的变形处理

⑴ 算法描述及算法复杂度

对于复杂或高次曲线段之间的变形处理，拟采取如下策略：分别将曲线C1，C2按照凹凸性进行分段，在每个分段区间上，以二次曲线描述每一条曲线段，其实质是按照曲线的凹凸区间用分段二次插值表示曲线C1，C2，然后移植二次曲线段变形算法，在对应的分段区间上作变形处理。

依据前述二次曲线段变形算法的结论，上述算法在每个凹凸区间上可以实现C1，C2之间的准确变形，从而可以在曲线的整个定义域上取得良好的变形效果。

显然，如果将复杂曲线分割为n段， 则整个曲线变形所需乘法次数为60n。

⑵ 数值实例

给定曲线（如图2、图3所示）：

⑺

⑻

图2 曲线C1

图3 曲线C2

设想通过采样数据的线性变换将曲线C1变形为曲线C2，依据曲线的凹凸性对两条曲线的定义域进行分割：

在曲线C1，C2对应的第一分段区间[-0.4，-0.1714]和[-0.5，-0.1803]上分别采样得到对应的三对数据点：

（-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）

根据⑷和⑸计算得出三个线性变换为

（11）

通过上述线性变换，可以成功地将数据⑼转换为数据（10）。

现在，由数据点（10）重建曲线C2的第一段，即位于区间[-0.5，-0.1803]上的部分，根据式⑹得

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

完全类似地，可以将曲线C1的第二、三两段变形为曲线C2的对应部分，变形后的结果为（如图4，图5，图6和图7所示）：

比较图3和图7不难发现，变形效果是非常理想的。

⑶ 几点说明

① 上述例子的两条曲线的分割段数是相等的，对于两条曲线按凹凸性分割段数不相等的情形，可以对分割段数较少的曲线的分段区间重复计数，即同一区间多次计数，使得两条曲线的分割段数相等，其实质是将分割段数较少的曲线的某一分段变换为分割段数较多的曲线的几个不同分段部分。

② 对于曲线段的退化情形即直线段之间的变形，以及直线段和曲线段之间的变形，算法同样有效。

3 结束语

本文从曲线的离散采样数据出发，详细地讨论了一种以Lagrange插值为基础的曲线变形算法，该算法的实质是在代数曲线的分段区间移植二次曲线段的变形算法，从而实现对代数曲线的变形处理。该算法避免了复杂的理论分析，计算简单，数值实例表明算法的变形效果较好，可以考虑将其推广至几何造型、计算机动画等领域。

参考文献：

[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