Print

发布时间: 2018-11-16
摘要点击次数:
全文下载次数:
DOI: 10.11834/jig.180230
2018 | Volume 23 | Number 11




    计算机图形学    




  <<上一篇 




  下一篇>> 





渐进迭代逼近方法在曲线变形上的应用
expand article info 张世杰, 张莉, 于立萍, 刘文振
合肥工业大学数学学院, 合肥 230009

摘要

目的 随着几何造型、计算机动画等领域的快速发展,曲线的自由变形技术在近年来受到了广泛的关注。为了获得更多有趣、逼真的变形效果,提出基于渐进迭代逼近与主顶点方法的曲线局部变形算法。方法 给定数据点集,首先采用渐进迭代逼近方法或是基于最小二乘的渐进迭代逼近方法产生待变形曲线;其次对待变形区域使用延拓准则,基于主顶点方法与待变形曲线的形状信息选取控制顶点进行调整;最后对调整后的控制顶点运用局部渐进迭代逼近方法生成逼近曲线,得到期望的变形效果。结果 此变形操作借助于局部渐进迭代逼近方法,具有较好的灵活性。通过茶壶、面部轮廓、手等数值实例,表明了该方法可以得到良好的变形效果。进一步地,借助于叠加变形还可以得到整体的、周期的、伸缩的等各类更加丰富的变形效果。结论 本文研究渐进迭代逼近在曲线变形上的应用,将主顶点方法引入曲线的变形之中,把两者相结合提出了基于渐进迭代逼近与主顶点方法的曲线局部变形算法。该算法不仅具备渐进迭代逼近方法的收敛稳定性,且借助于主顶点方法,可以得到较好的变形效果。该方法适用于曲线的局部变形,丰富了曲线的变形效果。

关键词

渐进迭代逼近; 曲线变形; 局部曲率; 变形效果; 计算机辅助设计

Application of the progressive iterative approximation method to curve deformations
expand article info Zhang Shijie, Zhang Li, Yu Liping, Liu Wenzhen
School of Mathematics, Hefei University of Technology, Hefei 230009, China
Supported by: National Natural Science Foundation of China (61472466, 61100126); National Undergraduate Training Program for Innovation (2017CXCY388)

Abstract

Objective Freeform deformation techniques of curves and surfaces have received considerable attention recently with the rapid development of geometric modeling and computer animation. A new local deformation algorithm for curves based on progressive iterative approximation (PIA) and dominant point methods is proposed in this study to acquire interesting and lifelike deformation effects. The new deformation method not only produces various deformation effects but also possesses desirable properties, such as flexibility and convergence, given the PIA method. Method First, the initial deformation curves are obtained using the PIA or least squares PIA method. Second, the dominant points, which include the maximum local curvature points, and two end points are selected from the initial control points by calculating and comparing the curvatures that correspond to the control points. In this phase, we detect the maximum local curvature points using the rule that the curvature of a point must be larger than the curvatures of its neighboring points. Thus, the maximum local curvature points can be selected as the dominant points. Then, an extension rule is constructed on the region expected to be deformed. That is, we extend this region along the curve until it satisfies the two closest dominant points after selecting the region for deformation in accordance with real requirements. Thus, we can obtain a segment that is bounded by two dominant points. We classify the situation into two categories using the abovementioned extension rule on the basis of the number of dominant points in the obtained segment. The control points, which will be adjusted subsequently, are selected in accordance with the dominant points and the shape information of the curves. If the region that is prepared for deformation contains a dominant point, then three dominant points in the segment will be obtained after applying such extension rule. The dominant point in the middle is selected for subsequent adjustment. If the region that is prepared for deformation does not contain any dominant point, then only two dominant points in the segment will be obtained after extension. We select a control point in accordance with the shape information of the curve, which is useful in handling several complex deformation problems. In this situation, we first calculate the shape parameter for each control point in the obtained segment. The shape parameter represents the complexity of the curve and indicates the difference between two adjacent segments. Second, the control point that has the smallest shape parameter is selected for subsequent adjustment after comparing these parameters. We call this procedure the dominant point method. Moreover, if more than one dominant point in the region is expected to be deformed, then we can split the segment in accordance with the distribution of dominant points to ensure that each segment contains less than one dominant point. Then, we can use the abovementioned dominant point method to select the control points. Finally, local progressive iterative approximation (LPIA) method is adopted to generate the final curves after local deformation. Result The proposed deformation method selects the control points on the basis of the complexity of the shapes of the curves. The deformation method is convergent, can be executed flexibly, and can highlight the features of the deformed regions through local iteration because we use the LPIA method to fit the data set after adjustment. Numerical examples, such as teapot, face contour, and hand, show that the proposed method can obtain favorable deformation effects through the B-spline basis, which is the most commonly used basis in geometric design and exhibits excellent local properties. Specifically, the teapot mouth is stretched by adjusting the selected control point. The lips, eyebrows, and earlobes of the face contour are deformed by using the deformation algorithm to generate a fascinating face. The fingers are also stretched to make the hand natural. We also demonstrate the distortion, which occurs when we do not use the deformation method proposed in this study, as illustrated in the teapot example. We can clearly observe that, if we do not adjust the control points generated by the algorithm, then the curve after deformation will be distorted and lack reality. Furthermore, this algorithm can be used repeatedly to generate the global, local, periodic, and elastic deformation effects. Conclusion This study mainly focuses on applying the PIA method to the local curve deformations. First, we discuss the PIA method, which presents an intuitive and straightforward approach to fitting data points and provides flexibility for shape control in data fitting. Second, we introduce the notion of dominant points into the curve deformations. Finally, we propose a new deformation method on the basis of the PIA and dominant point methods by combining the two techniques. The algorithm not only possesses the properties of convergence and stability through the PIA method but also produces various positive deformation effects by selecting dominant points. A user must only select the regions expected to be deformed during the implementation of the deformation method and determine the deformation scales in accordance with his/her requirements, thus guaranteeing the interactivity of this algorithm. In summary, the proposed method significantly enriches the deformation effects of curves.

Key words

progressive iterative approximation; curve deformation; local curvature; deformation effect; computer aided design

0 引言

在计算机图形学和辅助设计中,曲线/曲面的造型变形方法一直是一个十分活跃的研究课题。自由变形方法作为物体变形的核心技术,已经被广泛运用于几何造型、计算机动画等领域。1984年,Barr[1]首先提出整体与局部的变形方法,将对原型的造型变形方法引入计算机辅助设计(CAD)和计算机辅助制造(CAM)领域。该方法及其推广[2]只能够进行一些常规变形(如弯曲、扭曲、尖角等),但要产生任意形状是很难的。1986年,Sederberg等人[3]提出的自由变形(FFD)方法克服了上述缺点。其主要思想是:将变形目标嵌入由若干控制顶点构成的张量积Bézier参数体中,通过移动控制顶点带来参数体的变形,从而将变形传递给内部目标,引起内部目标的变形。此方法被广泛运用于几何造型、计算机动画等领域,但其形变控制不灵活,在变形时难以达到预期的结果。基于自由变形方法,研究者们提出了大量的算法来解决参数曲线/曲面的变形问题,如程仙国等人[4]从物理学的角度,通过求解一个使曲线能量变化量最小的优化问题,控制了B样条曲线的变形; Lazarus等人[5]给出了轴变形方法; Xu等人[6]对此方法进行了推广,通过运用“曲线对”直接进行几何变形并考虑了在变形过程中几何信息的保存; 冯结青等人[7-8]给出了曲面控制的自由变形方法,丰富了曲面变化的形状。这些方法改进了自由变形方法,提高了交互控制的灵活性,但是都需要借助外部辅助工具,如平行六面体和轴线。针对某些特殊曲线/曲面的形状修改问题,研究者们给出了一些方法,但是这些修改技术在理论与计算方面都比较复杂,且只适用于Bézier、B-spline、非均匀有理B样条(NURBS)等特殊的曲线/曲面[9],具有一定的局限性。除此之外,网格变形技术[10]也越来越多地被运用到实际之中。2010年,徐岗等人[11]对20年来自由变形的发展做了详细的综述,对其进行了系统地分类并介绍了相关的应用。

为了找到一种不借助相关辅助变形工具,且能够对一般参数曲线/曲面进行变形的方法,王小平等人[12-13]提出了基于伸缩因子的参数曲线/曲面的自由变形算法。这种方法利用伸缩因子形成变形矩阵,作用于待变形曲线/曲面的表达式,从而达到改变形状的效果。该方法在一定程度上增加了控制精度,对任何形式的参数曲线/曲面均适用,但是变形后的表达式为超越曲线/曲面,需利用逼近方法进行转换。而且伸缩因子仅在一点处取到峰值,很大程度上限制了变形后的形状。为了解决此问题,宋来忠等人[14]构造了一种新的伸缩因子,能够在一段区间上取到峰值。这在一定程度上丰富了变形的多样性,但此方法仅仅针对平面上的2维曲线。为了解决这些问题,张莉等人[15]对于平面和空间参数曲线提出了一种新的带平台伸缩函数。这样构造出的伸缩因子不仅能在单点处达到峰值,而且可以在区域上达到峰值。此方法对于主流参数曲线具有封闭性,并且计算量小,可控性强,丰富了曲线的变形效果。

在几何造型和计算机动画等领域经常需要产生丰富多样的几何、卡通形状。为了进一步使这些几何图形符合人们的美学要求,并且变得更加逼真、有趣,本文提出了基于渐进迭代逼近(PIA)与主顶点的曲线局部变形方法。其基本思想是:给定有序数据点集。首先,通过PIA方法或者基于最小二乘的PIA方法(LSPIA)拟合出待变形曲线; 其次,计算出所有控制顶点在待变形曲线上对应点处的曲率值,寻找主顶点; 接着,对待变形区域使用延拓准则,并通过本文算法选取控制顶点进行调整,得到一组新的控制顶点; 最后,运用局部PIA (LPIA)方法生成逼近曲线,得到变形后的效果。

1 PIA格式

给定区间$\mathit{\boldsymbol{I}}$上的一组非负基函数$\mathit{\boldsymbol{B}} = \{ {B_i}\left(t \right) \ge 0, t \in \mathit{\boldsymbol{I}}\} _{i = 0}^n$,若其满足$\sum\limits_{i = 0}^n {{B_i}\left(t \right)} = 1$$\forall t \in \mathit{\boldsymbol{I}}$则称$\mathit{\boldsymbol{B}}$为混合基。给定$\mathit{\boldsymbol{I}}$上的任意一组单调递增的实数列${t_0} \le {t_1} \le \ldots \le {t_m}$,若$\mathit{\boldsymbol{B}}$在上述参数处的配置矩阵

$ \mathit{\boldsymbol{M}}\left[\begin{array}{l} {B_0}, \ldots, {B_n}\\ {t_0}, \ldots, {t_m} \end{array} \right] = \left[{\begin{array}{*{20}{c}} {{B_0}({t_0})}&{{B_1}({t_0})}& \ldots &{{B_n}({t_0})}\\ {{B_0}({t_1})}&{{B_1}({t_1})}& \ldots &{{B_n}({t_1})}\\ \vdots&\vdots &{}& \vdots \\ {{B_0}({t_m})}&{{B_1}({t_m})}& \ldots &{{B_n}({t_m})} \end{array}} \right] $

是全正(TP)矩阵, 那么称这组基函数是一组规范全正(NTP)基。

给定有序数据点列$\{ {\mathit{\boldsymbol{P}}_i}\} _{i = 0}^n$,每个数据点对应一个参数值${t_i}$, $i$=0, 1, …, $n$,且满足${t_0} \le {t_1} \le \ldots \le {t_m}$。用初始的控制顶点$\{ \mathit{\boldsymbol{P}}_i^0 = {\mathit{\boldsymbol{P}}_i}\} _{i = 0}^n$和一组规范全正基$\{ {B_i}\left(t \right)\} _{i = 0}^n$,可得初始曲线

$ {\mathit{\boldsymbol{C}}^0}\left( t \right) = \sum\limits_{i = 0}^n {\mathit{\boldsymbol{P}}_i^0{B_i}\left( t \right)} $

假设第$k$次迭代时的控制顶点为$\{ \mathit{\boldsymbol{P}}_i^k\} _{i = 0}^n$。首先计算调整向量

$ \mathit{\boldsymbol{ \boldsymbol{\varDelta} }}_i^k = {\mathit{\boldsymbol{P}}_i}-{\mathit{\boldsymbol{C}}^k}({t_i}), i = 0, 1, \ldots, n $

然后将其加到相应的控制顶点上,即

$ {\mathit{\boldsymbol{P}}_i}^{k + 1} = {\mathit{\boldsymbol{ \boldsymbol{\varDelta} }}_i}^k + {\mathit{\boldsymbol{P}}_i}^k, i = 0, 1, \ldots, n $

由这些新的控制顶点$\left\{ {{\mathit{\boldsymbol{P}}_i}^{k + 1}} \right\}_{i = 0}^n$可生成第$k+1$次迭代的曲线

$ {\mathit{\boldsymbol{C}}^{k + 1}}\left( t \right) = \sum\limits_{i = 0}^n {{\mathit{\boldsymbol{P}}_i}^{k + 1}{B_i}\left( t \right)} $

按照上述方法依次迭代下去,可以得到逼近曲线序列$\{ {\mathit{\boldsymbol{C}}^k}\left(t \right), k = 0, 1, 2, \ldots \} $。文献[16]已经证明了当混合曲线的基函数是NTP基时极限曲线会插值于给定的数据点集,即$\mathop {{\rm{lim}}}\limits_{k \to \infty } {\mathit{\boldsymbol{C}}^k}({t_i}) = {\mathit{\boldsymbol{P}}_i}$, $i$=0, 1, …, $n$,这时就称曲线具有PIA性质。

2 基于PIA与主顶点的局部变形算法

采用三次B样条曲线对数据点进行渐进迭代逼近,介绍由PIA方法得到待变形曲线之后,如何根据曲率与曲线的信息选取控制顶点进行调整,最终实现曲线的局部变形。

2.1 主顶点

首先给出主顶点的定义。

定义1  假设给定控制顶点$\{ {\mathit{\boldsymbol{P}}_i}, i = 0, 1, \ldots, n\} $,第$i$个控制顶点${\mathit{\boldsymbol{P}}_i}$在曲线$\mathit{\boldsymbol{C}}\left(t \right) = \sum\limits_{i = 0}^n {{\mathit{\boldsymbol{P}}_i}{B_i}\left(t \right)} $上的对应点${\mathit{\boldsymbol{Q}}_i}$处的曲率为${k_i}$。把满足以下任意条件的控制顶点${\mathit{\boldsymbol{P}}_i}$记为主顶点:

1)${\mathit{\boldsymbol{P}}_i}$为首末两个控制顶点,即${\mathit{\boldsymbol{P}}_0}$${\mathit{\boldsymbol{P}}_n}$

2)${\mathit{\boldsymbol{P}}_i}$在曲线$\mathit{\boldsymbol{C}}\left(t \right)$上的对应点${\mathit{\boldsymbol{Q}}_i}$为局部曲率最大的点。

由定义1可见,主顶点$\{ {\mathit{\boldsymbol{D}}_i}, i = 0, 1, \ldots, m\} $为控制顶点$\{ {\mathit{\boldsymbol{P}}_i}, i = 0, 1, \ldots, n\} $的一个子集。

定义2  给定曲线$\mathit{\boldsymbol{C}}\left(t \right)$,曲线上任意一点${\mathit{\boldsymbol{Q}}_i}$处的曲率${k_i}$定义为[17]

$ {k_i} = \left\| {\mathit{\boldsymbol{\dot C}}({t_i}) \times \mathit{\boldsymbol{\ddot C}}({t_i})} \right\|/{\left\| {\mathit{\boldsymbol{\dot C}}({t_i})} \right\|^3} $ (1)

式中,${\mathit{\boldsymbol{\dot C}}({t_i})}$${\mathit{\boldsymbol{\ddot C}}({t_i})}$分别是曲线$\mathit{\boldsymbol{C}}\left(t \right)$在参数${{t_i}}$处的一阶与二阶导数。

根据式(1)可计算曲线$\mathit{\boldsymbol{C}}\left(t \right)$上每一点${\mathit{\boldsymbol{Q}}_i}$处的曲率值。若${\mathit{\boldsymbol{Q}}_i}$处的曲率${k_i}$同时满足以下两个条件:

1)${k_i} > {k_{i-1}}$

2)${k_{i + 1}} < {k_i}$,则称${\mathit{\boldsymbol{Q}}_i}$为曲线上局部曲率最大的点,其对应的控制顶点${\mathit{\boldsymbol{P}}_i}$即为主顶点。

把所有${\mathit{\boldsymbol{Q}}_i}$处的曲率画成曲率图,曲线$\mathit{\boldsymbol{C}}\left(t \right)$的所有主顶点便与曲率图中的极大值点和首末端点一致。由于待变形曲线是通过PIA方法、LSPIA方法插值或拟合得到的,这样保证了待变形曲线具有一定的光滑性与精确性,因此在待变形曲线上计算与考虑曲率是合理与有效的。

以例1为例说明如何在待变形曲线上寻找主顶点。

例1  用三次B样条曲线对34个数据点进行插值,得到待变形茶壶曲线(如图 1中黑色曲线)。计算每个控制顶点在茶壶曲线上对应处的曲率值,画出曲率图(如图 2)。曲率图中一共找到了12个局部曲率最大的点(图 2中实心的点),其下标分别为4, 6, 9, 12, 14, 17, 20, 23, 25, 27, 30, 32。加上首尾两个控制顶点即得茶壶曲线的所有主顶点(图 1中实心的控制顶点)。

图 1 茶壶轮廓曲线
Fig. 1 Contour curve of teapot
图 2 茶壶曲率图
Fig. 2 Curvature plot of teapot

2.2 控制顶点的选取

通过上述方法可找出待变形曲线$\mathit{\boldsymbol{C}}\left(t \right)$上的所有主顶点。本节讨论如何根据主顶点以及曲线的信息来选取控制顶点进行调整。

首先,通过实际的变形需求确定待变形区域${\mathit{\boldsymbol{S}}_{a, b}}$,其中$a, b$为所选曲线段的两个端点。接着,把$a, b$分别沿着待变形曲线向两边延拓,直到遇到距离$a、b$最近的两个局部曲率最大点${\mathit{\boldsymbol{Q}}_i}$${\mathit{\boldsymbol{Q}}_j}$为止,这样便得到一个以${\mathit{\boldsymbol{Q}}_i}$${\mathit{\boldsymbol{Q}}_j}$为端点的曲线段${\mathit{\boldsymbol{S}}_{i, j}}$。以上称得到曲线段${\mathit{\boldsymbol{S}}_{i, j}}$的过程为延拓准则。

由主顶点的定义易知曲线段${\mathit{\boldsymbol{S}}_{i, j}}$中至少包含3个控制顶点。下面分两种情形说明使用延拓准则后,如何在待变形曲线段${\mathit{\boldsymbol{S}}_{i, j}}$中选取控制顶点进行调整:

情形1) ${\mathit{\boldsymbol{S}}_{i, j}}$中包含3个主顶点。若待变形区域${\mathit{\boldsymbol{S}}_{a, b}}$中已经包含了1个主顶点,那么使用延拓准则后曲线段${\mathit{\boldsymbol{S}}_{i, j}}$中就会存在3个主顶点,即${\mathit{\boldsymbol{Q}}_i}$, ${\mathit{\boldsymbol{Q}}_j}$对应的控制顶点${\mathit{\boldsymbol{P}}_i}$, ${\mathit{\boldsymbol{P}}_j}$以及${\mathit{\boldsymbol{S}}_{a, b}}$中原本包含的主顶点。此时选取${\mathit{\boldsymbol{S}}_{i, j}}$中最中间的主顶点进行调整。

图 3中以$\{ {\mathit{\boldsymbol{P}}_i}\} _{i = 0}^6$为控制顶点,采用PIA方法得到一条三次B样条曲线(图 3中的黑色加粗曲线),$\{ {\mathit{\boldsymbol{Q}}_i}\} _{i = 0}^6$$\{ {\mathit{\boldsymbol{P}}_i}\} _{i = 0}^6$在三次B样条曲线上对应的点。若经过计算得${\mathit{\boldsymbol{Q}}_1}, {\mathit{\boldsymbol{Q}}_3}, {\mathit{\boldsymbol{Q}}_5}$的局部曲率最大,则可得${\mathit{\boldsymbol{P}}_1}, {\mathit{\boldsymbol{P}}_3}, {\mathit{\boldsymbol{P}}_5}$为主顶点。现需要改变${\mathit{\boldsymbol{Q}}_3}$周围的局部区域,不妨选取待变形区域${\mathit{\boldsymbol{S}}_{a, b}}$包含于曲线段${\mathit{\boldsymbol{S}}_{{\rm{2, 4}}}}$。按照延拓准则,把${\mathit{\boldsymbol{S}}_{a, b}}$向两边延拓,便得到以${\mathit{\boldsymbol{Q}}_1}, {\mathit{\boldsymbol{Q}}_5}$为端点的曲线段${\mathit{\boldsymbol{S}}_{{\rm{1, 5}}}}$。此时${\mathit{\boldsymbol{S}}_{{\rm{1, 5}}}}$中包含3个主顶点${\mathit{\boldsymbol{P}}_1}, {\mathit{\boldsymbol{P}}_3}, {\mathit{\boldsymbol{P}}_5}$。在这种情形下就选取最中间的主顶点${\mathit{\boldsymbol{P}}_3}$进行调整。文末的数值实例给出了不按上述操作,调整其他控制顶点后产生的失真情形。

图 3 三次B样条曲线
Fig. 3 Cubic B-spline curve

情形2)${\mathit{\boldsymbol{S}}_{i, j}}$中包含两个主顶点。若待变形区域${\mathit{\boldsymbol{S}}_{a, b}}$中无主顶点,那么使用延拓准则后曲线段${\mathit{\boldsymbol{S}}_{i, j}}$中就只包含两个主顶点,即${\mathit{\boldsymbol{Q}}_i}$, ${\mathit{\boldsymbol{Q}}_j}$对应的控制顶点${\mathit{\boldsymbol{P}}_i}$, ${\mathit{\boldsymbol{P}}_j}$

图 4中,若经过计算得${\mathit{\boldsymbol{Q}}_1}$, ${\mathit{\boldsymbol{Q}}_4}$的局部曲率最大,则可得${\mathit{\boldsymbol{P}}_1}, {\mathit{\boldsymbol{P}}_4}$为主顶点。不妨选取待变形区域${\mathit{\boldsymbol{S}}_{a, b}}$包含于曲线段${\mathit{\boldsymbol{S}}_{{\rm{1, 4}}}}$。按照延拓准则,把${\mathit{\boldsymbol{S}}_{a, b}}$向两边延拓,便得到以${\mathit{\boldsymbol{Q}}_1}$, ${\mathit{\boldsymbol{Q}}_4}$为端点的曲线段${\mathit{\boldsymbol{S}}_{{\rm{1, 4}}}}$。此时${\mathit{\boldsymbol{S}}_{{\rm{1, 4}}}}$中包含两个主顶点${\mathit{\boldsymbol{P}}_1}, {\mathit{\boldsymbol{P}}_4}$

图 4 三次B样条曲线
Fig. 4 Cubic B-spline curve

在此情形下,基于曲线的信息来选取控制顶点进行调整。不妨假设${\mathit{\boldsymbol{S}}_{i, j}}$中包含的两个主顶点分别为${\mathit{\boldsymbol{P}}_i}$, ${\mathit{\boldsymbol{P}}_j}$。考虑如何在片段${\mathit{\boldsymbol{S}}_{i, j}}$的诸多控制顶点中选取${\mathit{\boldsymbol{P}}_c}$进行调整。

定义3[18]  设${\mathit{\boldsymbol{S}}_{i, j}}$为包含控制顶点${\mathit{\boldsymbol{P}}_k}, k = i, i + 1, \ldots, j$的曲线段。定义刻画曲线复杂程度的参数

$ {\lambda _{i, j}} = r\frac{{{K_{i, j}}}}{{{K_{0, m}}}} + \left( {1-r} \right)\frac{{{L_{i, j}}}}{{{L_{0, m}}}} $ (2)

式中,$0 \le r \le 1$${{K_{i, j}}}$为曲线段${\mathit{\boldsymbol{S}}_{i, j}}$的总曲率,${{L_{i, j}}}$为曲线段${\mathit{\boldsymbol{S}}_{i, j}}$的弧长。

用梯形法则(trapezoidal rule)逼近${{K_{i, j}}}$

$ {K_{i, j}} = \sum\limits_{m = i}^{j-1} {(\left| {{k_m}} \right| + \left| {{k_{m + 1}}} \right|)({t_{m + 1}}-{t_m})/2} $ (3)

${{L_{i, j}}}$可以被逼近为

$ {L_{i, j}} = \sum\limits_{m = i}^{j-1} {\left\| {{\mathit{\boldsymbol{Q}}_{m + 1}}-{\mathit{\boldsymbol{Q}}_m}} \right\|} $ (4)

基于待变形曲线的形状信息来确定控制顶点的主要步骤如下:

1) 根据式(2)对曲线段${\mathit{\boldsymbol{S}}_{i, j}}$中包含的每一个控制顶点${\mathit{\boldsymbol{P}}_k}, k = i + 1, \ldots, j-1$计算参数${\lambda _{i, k}}, {\lambda _{k, j}}$

2) 计算值${\lambda _k} = \left| {{\lambda _{i, k}}-{\lambda _{k, j}}} \right|, k = i + 1, \ldots, j-1$

3) 比较${\lambda _k}, k = i + 1, \ldots, j-1$的大小,寻找使得${\lambda _c} = \mathop {{\rm{min}}}\limits_{i < k < j} \left| {{\lambda _{i, k}}-{\lambda _{k, j}}} \right|$的控制顶点${\mathit{\boldsymbol{P}}_c}$。选取${\mathit{\boldsymbol{P}}_c}$进行调整。

通过定义3可知${\lambda _k}$描述了曲线段${\mathit{\boldsymbol{S}}_{i, k}}$${\mathit{\boldsymbol{S}}_{k, j}}$之间的差异程度,因此选取使得${\lambda _k}$最小化的控制顶点${\mathit{\boldsymbol{P}}_c}$进行调整可以有效地根据曲线的信息达到最佳的变形效果。特别是在处理一些复杂的曲线变形问题时,基于曲线复杂程度来选取控制顶点进行调整是有效的。但限于文章篇幅,本文仅用例2说明如何通过曲线的复杂程度选取控制顶点。

例2  用三次B样条曲线对13个数据点进行插值,得到侧脸曲线(图 5(a)),计算曲率并找出所有主顶点(图 5(a)中实心的控制顶点)。若现需对嘴部进行变形,不妨假设执行延拓准则后得到曲线段${\mathit{\boldsymbol{S}}_{{\rm{7, 11}}}}$。下面给出在情形2)下选取控制顶点的具体步骤:

图 5 侧脸曲线及选取的控制顶点
Fig. 5 Contour curve of face profile and the dominant points
((a) contour curve of face profile; (b) dominant points and the chosen control points)

1) 对${\mathit{\boldsymbol{S}}_{{\rm{7, 11}}}}$中包含的每一个控制顶点$\mathit{\boldsymbol{P}}$, $k$=8, 9, 10,根据式(2)计算参数${\lambda _{7, k}}, {\lambda _{k, 11}}$:

对控制顶点${\mathit{\boldsymbol{P}}_8}:{\lambda _{7, 8}} = 0.123\; 2, {\lambda _{8, 11}} = 0.180\; 9$

对控制顶点${\mathit{\boldsymbol{P}}_9}:{\lambda _{7, 9}} = 0.169\; 0, {\lambda _{9, 11}} = 0.135\; 1$

对控制顶点${\mathit{\boldsymbol{P}}_{10}}:{\lambda _{7, 10}} = 0.216\; 1,{\lambda _{10, 11}} = 0.088\; 0$

2) 分别计算${\lambda _k}, k = 8, 9, 10$,得

$ {\lambda _{8}} = 0.057\;7, \;\;{\lambda _{9}} = 0.033\;9, {\lambda _{10}} = 0.128\;1。$

3) 比较${\lambda _8}, {\lambda _9}, {\lambda _{10}}$的大小得${\lambda _9} = {\rm{min}}\{ {\lambda _8}, {\lambda _9}, {\lambda _{10}}\} $。选取控制顶点${\mathit{\boldsymbol{P}}_9}$进行调整(图 5(b)中被圈出的控制顶点)。

在上述两种情形中,待变形区域${\mathit{\boldsymbol{S}}_{a, b}}$中包含的主顶点个数$n$∈{0, 1}。若待变形区域${\mathit{\boldsymbol{S}}_{a, b}}$中包含的主顶点个数$n$>1,则首先把曲线段${\mathit{\boldsymbol{S}}_{a, b}}$根据主顶点分布的特征进行分组,使得分组后的每一部分所包含的主顶点个数${n_i}$∈{0, 1},再分别对应于情形1)和情形2)使用延拓准则,选取控制顶点进行调整。

2.3 控制顶点的调整

对于上述选取的控制顶点${\mathit{\boldsymbol{P}}_c}$,首先计算其调整向量

$ {\mathit{\boldsymbol{ \boldsymbol{\varDelta} }}_c}^k = {\mathit{\boldsymbol{P}}_c}^0-{\mathit{\boldsymbol{C}}^k}({t_c}) $

式中,${\mathit{\boldsymbol{C}}^k}\left(t \right)$为待变形曲线,${\mathit{\boldsymbol{P}}_c}^0$为给定的初始控制顶点中第$c$个控制顶点。接着,根据实际变形的需求把控制顶点${\mathit{\boldsymbol{P}}_c}$沿着调整向量的方向进行拉伸或压缩,得到调整后的控制顶点$\mathit{\boldsymbol{P}}{{\rm{'}}_c}$,即

$ \mathit{\boldsymbol{P}}{\prime _c} = {\mathit{\boldsymbol{P}}_c}^0 + \omega {{\rm{\Delta }}_c}^k 或 \mathit{\boldsymbol{P}}{\prime _c} = {\mathit{\boldsymbol{P}}_c}^0-\omega {\Delta _c}^k $

式中,$ω$为伸缩因子。

当然也可以根据实际需求对控制顶点${\mathit{\boldsymbol{P}}_c}$进行手动调整,来得到新的控制顶点$\mathit{\boldsymbol{P}}{{\rm{'}}_c}$

2.4 用LPIA方法产生变形后的曲线

通过对选取的控制顶点${\mathit{\boldsymbol{P}}_c}$进行调整后,可得到一组新的有序点集$\{ {\mathit{\boldsymbol{P}}_0}, {\mathit{\boldsymbol{P}}_1}, \ldots, \mathit{\boldsymbol{P}}{'_c}, \ldots, {\mathit{\boldsymbol{P}}_n}\} $。把点集$\{ {\mathit{\boldsymbol{P}}_0}, {\mathit{\boldsymbol{P}}_1}, \ldots, \mathit{\boldsymbol{P}}{'_c}, \ldots, {\mathit{\boldsymbol{P}}_n}\} $作为初始的控制顶点,使用局部渐进迭代逼近方法,通过在迭代时只调整控制顶点$\mathit{\boldsymbol{P}}{{\rm{'}}_c}$来产生变形后的图形。

引理[19]:若$\mathit{\boldsymbol{B}} = \{ {b_i}\left(t \right) \ge 0, t \in \mathit{\boldsymbol{I}}\} _{i = 0}^n$为NTP基,且在PIA迭代时只调整某一个控制顶点${\mathit{\boldsymbol{P}}_h}$,其余的控制顶点均保持不变,可以得到以下结论:

1) $\mathop {{\rm{lim}}}\limits_{k \to \infty } {\mathit{\boldsymbol{P}}_h}^k = {\mathit{\boldsymbol{P}}_h}$

2) $\mathop {{\rm{lim}}}\limits_{k \to \infty } {\Delta _l}^k = {\Delta _l}^0-\frac{{{B_h}({t_l})}}{{{B_h}({t_h})}}{\Delta _h}^0$

$l = 0, 1, \ldots, h-1, h + 1, \ldots, n$

上述引理保证了在迭代时通过只调整控制顶点$\mathit{\boldsymbol{P}}{{\rm{'}}_c}$,对变形后的曲线进行局部逼近是收敛的。这样不仅能够提高迭代效率,而且具备一定的灵活性,能够突显变形处的特征。

2.5 算法流程

基于PIA以及主顶点的曲线局部变形算法的具体步骤如下(流程图如图 6所示):

图 6 算法流程图
Fig. 6 Algorithm flowchart of curve deformation

输入:初始数据点集,精度$ε$

输出:满足精度$ε$要求的变形曲线。

1) 采用PIA方法或者是LSPIA方法得到待变形曲线;

2) 计算曲率,寻找主顶点;

3) 根据实际需求确定待变形区域,通过延拓准则得到曲线段${\mathit{\boldsymbol{S}}_{i, j}}$

4)${\mathit{\boldsymbol{S}}_{i, j}}$中包含两个主顶点,转步骤5);${\mathit{\boldsymbol{S}}_{i, j}}$中包含3个主顶点,转步骤6);

5) 计算${\lambda _k}$,选取需要调整的控制顶点;

6) 选取${\mathit{\boldsymbol{S}}_{i, j}}$中最中间的主顶点进行调整;

7) 调整控制顶点,使用LPIA方法对新的控制顶点进行插值,直至满足精度$ε$

8) 实现曲线的局部变形。

3 数值实例

下面通过数值实例来验证本文方法的正确性与有效性。

例3  用三次B样条曲线插值从茶壶轮廓曲线上采集的34个数据点,对壶嘴进行变形。首先运用PIA方法画出待变形茶壶轮廓曲线(如图 7(a)),其中空心的点为所有控制顶点。接着计算曲率值并画出曲率图(如图 7(b)),求得本例中的主顶点为第1, 4, 6, 9, 12, 14, 17, 20, 23, 25, 27, 30, 32, 34个控制顶点(如图 7(c)中所有实心的点)。现选定壶嘴为待变形区域,根据本文算法,选取壶嘴处的主顶点进行调整。图 7(d)(e)分别为$ω$取不同权值所得到的变形结果。图 7(f)展示了若不按照本文算法,选取其他控制顶点进行调整出现的失真情形,可以明显看到壶嘴在调整其他控制顶点后的变形效果与本文算法相比有较大的差距且逼近的效果较差。

图 7 茶壶曲线及其变形
Fig. 7 Contour curve of teapot and its deformation ((a)contour curve of teapot; (b) curvature plot of teapot; (c) dominant points of teapot; (d) contour of teapot after deformation; (e) contour of teapot after deformation; (f) distortion curve after deformation)

例4  用三次B样条曲线拟合出郭德纲的面部轮廓图案(如图 8(a)),分别对其嘴唇、耳朵和眼睛进行局部变形。图 8(b)中空心的点为控制顶点,实心的点分别为嘴唇、耳朵以及眼睛的主顶点。现分别对嘴唇、耳朵以及眼睛进行变形,根据本文算法,分别调整下嘴唇的第2个主顶点、左耳的第4个主顶点、右耳的第3个主顶点以及左右眼的主顶点。调整后的所有控制顶点以及主顶点分布如图 8(c)所示。最终得到的变形效果如图 8(d),可以看到嘴巴明显地张大,耳垂实现了下拉,且双眼的弧度也变得更大。

图 8 郭德纲面部轮廓曲线及其变形
Fig. 8 Contour curve of Guo Degang and its deformation ((a) contour curve of Guo Degang before deformation; (b) dominant points before deformation; (c) dominant points after deformation; (d) contour of Guo Degang after deformation)

例5  用三次B样条曲线拟合出手的轮廓图案(如图 9(a)),对食指、中指、无名指以及小拇指做拉长变形。首先计算曲率值并画出曲率图(如图 9(b))。本例中的主顶点即为图 9(c)中实心的控制顶点。图 9(d)展示了对手指做拉长处理前后的效果对比,其中黑色实线为变形前的手指,黑色虚线为变形后的手指。为了更好地展示变形效果,在变形时就不把控制顶点进行标注。通过对手指的变形进行叠加,最后得到变形后完整的手轮廓曲线(如图 9(e))。

图 9 手轮廓曲线及其变形
Fig. 9 Contour curve of hand and its deformation ((a) contour curve of hand before deformation; (b) curvature plot of hand; (c) dominant points before deformation; (d) comparison of fingers before and after deformation; (e) contour curve of hand after deformation)

4 结论

本文主要介绍了基于渐进迭代逼近与主顶点方法的曲线局部变形算法,给出了曲线变形的一套算法。该方法通过主顶点方法以及曲线的信息选取最优的控制顶点进行调整,利用LPIA方法进行逼近,具有一定的灵活性。文末给出的数值实例表明,基于B样条良好的局部性质以及本文算法对控制顶点的合理选择,曲线的局部变形都达到了较好的效果。此外还说明了不按照本文算法变形后出现的失真状况,验证了本文算法的有效性。若借助于叠加变形,可以进一步实现丰富多样的变形效果。

参考文献

  • [1] Barr A H. Global and local deformations of solid primitives[J]. ACM SIGGRAPH Computer Graphics, 1984, 18(3): 21–30. [DOI:10.1145/964965.808573]
  • [2] Güdükbay U, Özgüç B. Free-form solid modeling using deformations[J]. Computers & Graphics, 1990, 14(3-4): 491–500. [DOI:10.1016/0097-8493(90)90071-5]
  • [3] Sederberg T W, Parry S R. Free-form deformation of solid geometric models[J]. ACM SIGGRAPH Computer Graphics, 1986, 20(4): 151–160. [DOI:10.1145/15886.15903]
  • [4] Cheng X G, Liu W J. Shape modification of B-spline curve via external loads[J]. Journal of Image and Graphics, 2011, 16(5): 898–902. [程仙国, 刘伟军. 外载荷的B样条曲线变形[J]. 中国图象图形学报, 2011, 16(5): 898–902. ] [DOI:10.11834/jig.20110528]
  • [5] Lazarus F, Coquillart S, Jancène P. Axial deformations:an intuitive deformation technique[J]. Computer-Aided Design, 1994, 26(8): 607–613. [DOI:10.1016/0010-4485(94)90103-1]
  • [6] Xu G, Hui K C, Ge W B, et al. Direct manipulation of free-form deformation using curve-pairs[J]. Computer-Aided Design, 2013, 45(3): 605–614. [DOI:10.1016/j.cad.2012.09.004]
  • [7] Feng J Q, Ma L Z, Peng Q S. Free-form deformation through embedding objects into the parametric domain of surface[J]. Journal of Computer Aided Design & Computer Graphics, 1998, 10(3): 208–215. [冯结青, 马利庄, 彭群生. 嵌入参数空间的曲面控制自由变形方法[J]. 计算机辅助设计与图形学学报, 1998, 10(3): 208–215. ] [DOI:10.3321/j.issn:1003-9775.1998.03.003]
  • [8] Feng J Q, Ma L Z, Peng Q S. A new free-form deformation through the control of parametric surfaces[J]. Computers & Graphics, 1996, 20(4): 531–539. [DOI:10.1016/0097-8493(96)00025-8]
  • [9] Sanchez-Reyes J. A simple technique for NURBS shape modification[J]. IEEE Computer Graphics and Applications, 1997, 17(1): 52–59. [DOI:10.1109/38.576858]
  • [10] Dong H W. Survey of mesh deformation[J]. Journal of Image and Graphics, 2011, 16(12): 2095–2104. [董洪伟. 网格变形综述[J]. 中国图象图形学报, 2011, 16(12): 2095–2104. ] [DOI:10.11834/jig.20111201]
  • [11] Xu G, Wang G Z, Chen X D. Free form deformation and its application[J]. Journal of Computer Research and Development, 2010, 47(2): 344–352. [徐岗, 汪国昭, 陈小雕. 自由变形技术及其应用[J]. 计算机研究与发展, 2010, 47(2): 344–352. ]
  • [12] Wang X P, Ye Z L, Meng Y Q, et al. Free-form deformation based on extension factor for parametric curve[J]. Journal of Computer-Aided Design & Computer Graphics, 2002, 14(1): 66–69. [王小平, 叶正麟, 孟雅琴, 等. 基于伸缩因子的参数曲线自由变形[J]. 计算机辅助设计与图形学学报, 2002, 14(1): 66–69. ] [DOI:10.3321/j.issn:1003-9775.2002.01.015]
  • [13] Wang X P, Ye Z L, Meng Y Q, et al. Space deformation of parametric surface based on extension function[J]. International Journal of CAD/CAM, 2002, 1(1): 23–32.
  • [14] Song L Z, Peng G, Yang W Y, et al. A new extension factor for free-form de-formation of parametric curves[J]. Journal of Engineering Graphics, 2009, 30(3): 87–93. [宋来忠, 彭刚, 杨文颖, 等. 用于参数曲线自由变形的新的伸缩因子[J]. 图学学报, 2009, 30(3): 87–93. ] [DOI:10.3969/j.issn.1003-0158.2009.03.015]
  • [15] Zhang L, Yu H F, Tan J Q. Deformation of parametric curves based on platform extension function[J]. Journal of Image and Graphics, 2015, 20(10): 1374–1383. [张莉, 余慧芳, 檀结庆. 带平台伸缩函数的参数曲线变形[J]. 中国图象图形学报, 2015, 20(10): 1374–1383. ] [DOI:10.11834/jig.20151011]
  • [16] Lin H W, Bao H J, Wang G J. Totally positive bases and progressive iteration approximation[J]. Computers & Mathematics with Applications, 2005, 50(3-4): 575–586. [DOI:10.1016/j.camwa.2005.01.023]
  • [17] Hoschek J, Lasser D. Fundamentals of computer aided geometric design[M]. Natick, MA, USA: A. K. Peters, Ltd., 1993.
  • [18] Park H, Lee J H. B-spline curve fitting based on adaptive curve refinement using dominant points[J]. Computer-Aided Design, 2007, 39(6): 439–451. [DOI:10.1016/j.cad.2006.12.006]
  • [19] Lin H W. Local progressive-iterative approximation format for blending curves and patches[J]. Computer Aided Geometric Design, 2010, 27(4): 322–339. [DOI:10.1016/j.cagd.2010.01.003]