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

 收稿日期: 2018-04-03; 修回日期: 2018-06-28 基金项目: 国家自然科学基金项目（61472466，61100126）；合肥工业大学校级创新项目（2017CXCY388） 第一作者简介: 张世杰, 1996年生, 男, 合肥工业大学数学与应用数学专业本科生, 主要研究方向为CAGD。E-mail:1144279616@qq.com;于立萍, 女, 讲师, 主要研究方向为CAGD。E-mail:ylphf@hfut.edu.cn;刘文振, 男, 本科生, 主要研究方向为CAGD。E-mail:1414398623@qq.com. 中图法分类号: TP391 文献标识码: A 文章编号: 1006-8961(2018)11-1697-10

# 关键词

Application of the progressive iterative approximation method to curve deformations
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

# 1 PIA格式

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

 ${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)

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

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

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)中被圈出的控制顶点)。

# 2.3 控制顶点的调整

 ${\mathit{\boldsymbol{ \boldsymbol{\varDelta} }}_c}^k = {\mathit{\boldsymbol{P}}_c}^0-{\mathit{\boldsymbol{C}}^k}({t_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$

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

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$

# 2.5 算法流程

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) 实现曲线的局部变形。

# 参考文献

• [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]