计算机科学技术学报 ›› 2022,Vol. 37 ›› Issue (2): 487-504.doi: 10.1007/s11390-020-0183-1

所属专题: Artificial Intelligence and Pattern Recognition Computer Graphics and Multimedia

• • 上一篇    

用于Loop和Catmull-Clark细分曲面插值的共轭梯度渐进迭代逼近

  

  • 收稿日期:2019-11-18 修回日期:2020-08-14 接受日期:2020-08-20 出版日期:2022-03-31 发布日期:2022-03-31

Conjugate-Gradient Progressive-Iterative Approximation for Loop and Catmull-Clark Subdivision Surface Interpolation

Yusuf Fatihu Hamza1 and Hong-Wei Lin1,2,* (蔺宏伟), Member, CCF        

  1. 1School of Mathematical Science, Zhejiang University, Hangzhou 310027, China
    2State Key Laboratory of CAD & CG, Zhejiang University, Hangzhou 310058, China
  • Received:2019-11-18 Revised:2020-08-14 Accepted:2020-08-20 Online:2022-03-31 Published:2022-03-31
  • Contact: Hong-Wei Lin E-mail:hwlin@zju.edu.cn
  • About author:Hong-Wei Lin received his B.Sc. degree in applied mathematics from the Department of Applied Mathematics at Zhejiang University, Hangzhou, in 1996, and his Ph.D. degree in applied mathematics from Department of Mathematics at Zhejiang University, Hangzhou, in 2004. He is a professor in the School of Mathematical Science and State Key Laboratory of CAD & CG, Zhejiang University, Hangzhou. His current research interests include geometric design, computer graphics, and topology data analysis.
  • Supported by:
    This work is supported by the National Natural Science Foundation of China under Grant Nos. 61872316 and 61932018.

1、 研究背景(context):渐进迭代逼近是一种有效的数据插值方法,在细分曲面拟合、参数曲线曲面拟合等领域有广泛应用。经典的渐进迭代逼近是一种梯度下降法,收敛速度较慢。加权渐进迭代逼近虽然可以在一定程度上加速收敛,但它仍然是一种梯度下降算法。因此,如何发展新方法对渐进迭代逼近进行较大程度的加速,成为渐进迭代研究中一个迫切需要解决的问题。
2、 目的(Objective):本文的研究目的是设计一种比经典渐进迭代逼近和加权渐进迭代逼近收敛更快的算法。由于经典渐进迭代逼近和加权渐进迭代逼近都属于梯度下降法,而共轭梯度法比梯度下降法收敛更快,因此,本文基于共轭梯度法设计一种新型渐进迭代逼近算法(CG-PIA),收敛速度快于经典渐进迭代逼近和加权渐进迭代逼近。
3、 方法(Method):本文提出的CG-PIA是一种迭代方法,在每一步迭代中,交替更新控制网格和梯度网格的网格顶点,而不改变控制网格拓扑连接关系。利用矩阵分析工具,可以证明CG-PIA迭代的收敛性。在本文中,CG-PIA方法在Loop和Catmull-Clark细分曲面拟合中,展示它的有效性和效率。
4、 结果(Result & Findings):理论分析证明,当系数矩阵是正定矩阵时,CG-PIA迭代法收敛。数值实验表明,虽然CG-PIA每次迭代计算时间要多于经典渐进迭代和加权渐进迭代,但是,达到相同的拟合精度,CG-PIA的迭代步数要远少于经典渐进迭代和加权渐进迭代。

5、 结论(Conclusions):CG-PIA可以应用于使得系数矩阵正定的细分曲面拟合问题,包括Loop细分和Catmull-Clark细分。CG-PIA生成的细分曲面,不但保持了原始网格的形状,还不改变原网格的连接关系。与经典渐进迭代和加权渐进迭代相比,CG-PIA的收敛速度要快的多。


关键词: 渐进迭代逼近;Loop细分;Catmull-Clark细分, 共轭梯度法

Abstract:

Loop and Catmull-Clark are the most famous approximation subdivision schemes, but their limit surfaces do not interpolate the vertices of the given mesh. Progressive-iterative approximation (PIA) is an efficient method for data interpolation and has a wide range of applications in many fields such as subdivision surface fitting, parametric curve and surface fitting among others. However, the convergence rate of classical PIA is slow. In this paper, we present a new and fast PIA format for constructing interpolation subdivision surface that interpolates the vertices of a mesh with arbitrary topology. The proposed method, named Conjugate-Gradient Progressive-Iterative Approximation (CG-PIA), is based on the Conjugate-Gradient Iterative algorithm and the Progressive Iterative Approximation (PIA) algorithm. The method is presented using Loop and Catmull-Clark subdivision surfaces. CG-PIA preserves the features of the classical PIA method, such as the advantages of both the local and global scheme and resemblance with the given mesh. Moreover, CG-PIA has the following features. 1) It has a faster convergence rate compared with the classical PIA and W-PIA. 2) CG-PIA avoids the selection of weights compared with W-PIA. 3) CG-PIA does not need to modify the subdivision schemes compared with other methods with fairness measure. Numerous examples for Loop and Catmull-Clark subdivision surfaces are provided in this paper to demonstrate the efficiency and effectiveness of CG-PIA.


Key words: progressive-iterative approximation, Loop subdivision, Catmull-Clark subdivision, conjugate-gradient method

[1] Loop C. Smooth subdivision surfaces based on triangles ['s Thesis]. Department of Mathematics, University of Utah, 1987.
[2] Catmull E, Clark J. Recursively generated B-spline surfaces on arbitrary topological meshes. Computer-Aided Design, 1978, 10(6): 350-355. DOI: 10.1016/0010-4485(78)90110-0.
[3] Doo D, Sabin M. Behaviour of recursive division surfaces near extraordinary points. Computer-Aided Design, 1978, 10(6): 356-360. DOI: 10.1016/0010-4485(78)90111-2.
[4] Dyn D, Levine J, Gregory J A. A butterfly subdivision scheme for surface interpolation with tension control. ACM Transactions on Graphics, 1990, 9(2): 160-169. DOI: 10.1145/78956.78958.
[5] Zorin D, Schröder P, Sweldens W. Interpolating subdivision for meshes with arbitrary topology. In Proc. the 23rd Annual Conference on Computer Graphics and Interactive Techniques, August 1996, pp.189-192. DOI: 10.1145/237170.237254.
[6] Kobbelt L. Interpolatory subdivision on open quadrilateral nets with arbitrary topology. Computer Graphics Forum, 1996, 15(3): 409-420. DOI: 10.1111/1467-8659.1530409.
[7] Hoppe H, DeRose T, Duchamp T, Halstead M, Jin H, McDonald J, Schweitzer J, Stuetzle W. Piecewise smooth surface reconstruction. In Proc. the 21st Annual Conference on Computer Graphics and Interactive Techniques, July 1994, pp.295-302. DOI: 10.1145/192161.192233.
[8] Nasri A H. Polyhedral subdivision methods for free-form surfaces. ACM Transactions on Graphics, 1987, 6(1): 29-73. DOI: 10.1145/27625.27628.
[9] Brunet P. Including shape handles in recursive subdivision surfaces. Computer Aided Geometric Design, 1988, 5(1): 41-50. DOI: 10.1016/0167-8396(88)90019-2.
[10] Halstead M, Kass M, DeRose T. Efficient, fair interpolation using Catmull-Clark surfaces. In Proc. the 20th Annual Conference on Computer Graphics and Interactive Techniques, August 1993, pp.35-44. DOI: 10.1145/166117.166121.
[11] Zheng J, Cai Y. Interpolation over arbitrary topology meshes using a two-phase subdivision scheme. IEEE Transactions on Visualization and Computer Graphics, 2006, 12(3): 301-310. DOI: 10.1109/TVCG.2006.49.
[12] Litke N, Levin A, Schröder P. Fitting subdivision surfaces. In Proc. the 12th IEEE Visualization Conference, October 2001, pp.319-324. DOI: 10.1109/VISUAL.2001.964527.
[13] Zheng J, Cai Y. Making Doo-Sabin surface interpolation always work over irregular meshes. The Visual Computer, 2005, 21(4): 242-251. DOI: 10.1007/s00371-005-0285-3.
[14] Deng C, Yang X. A simple method for interpolating meshes of arbitrary topology by Catmull-Clark surfaces. The Visual Computer, 2010, 26(2): 137-146. DOI: 10.1007/s00371-009-0393-6.
[15] Deng C, Wang G. Interpolating triangular meshes by Loop subdivision scheme. Science China Information Sciences, 2010, 53(9): 1765-1773. DOI: 10.1007/s11432-010-4049-y.
[16] Deng C. Interpolating closed triangular meshes by approximation \sqrt{3} subdivision scheme. Journal of Computer-Aided Design & Computer Graphics, 2010, 22(2): 312-317. (in Chinese)
[17] Chen Z, Luo X, Tan L, Ye B, Chen J. Progressive interpolation based on Catmull-Clark subdivision surfaces. Computer Graphics Forum, 2008, 27(7): 1823-1827. DOI: 10.1111/j.1467-8659.2008.01328.x.
[18] Wang Z, Li Y, Ma W, Deng C. Gauss-Seidel progressive iterative approximation (GS-PIA) for Loop surface interpolation. In Proc. the 26th Pacific Conference on Computer Graphics and Applications, October 2018, pp.73-76. DOI: 10.2312/pg.20181284.
[19] Cheng F H, Fan F T, Lai S H, Huang C L, Wang J X, Yong J H. Loop subdivision surface based progressive interpolation. Journal of Computer Science and Technology, 2009, 24(1): 39-46. DOI: 10.1007/s11390-009-9199-2.
[20] Deng C, Ma W. Weighted progressive interpolation of Loop subdivision surfaces. Computer-Aided Design, 2012, 44(5): 424-431. DOI: 10.1016/j.cad.2011.12.001.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 练林; 张一立; 唐常杰;. A Non-Recursive Algorithm Computing Set Expressions[J]. , 1988, 3(4): 310 -316 .
[2] 周权; 魏道政;. A Complete Critical Path Algorithm for Test Generation of Combinational Circuits[J]. , 1991, 6(1): 74 -82 .
[3] 王克;. Polynomial Tests of Normal Forms and Some Related Results[J]. , 1992, 7(1): 75 -82 .
[4] 王义和; 洪家荣;. AECAM:An Extension Matrix Algorithm on a Cellular Automata Machine[J]. , 1992, 7(1): 88 -91 .
[5] 吴信东;. Inductive Learning[J]. , 1993, 8(2): 22 -36 .
[6] 眭跃飞;. Bounded Recursively Enumerable Sets and Degrees[J]. , 1993, 8(3): 15 -18 .
[7] 罗钢;. Generating Conformance Tests for Nondeterministic Protocol Machines[J]. , 1994, 9(4): 289 -301 .
[8] $Hock C. Chan;. Translational Semantics for a Conceptual Level Query Language[J]. , 1995, 10(2): 175 -187 .
[9] 胡事民;. A Subdivision Scheme for Rational Triangular Bézier Surfaces[J]. , 1996, 11(1): 9 -16 .
[10] 刘大有; 钟绍春;. Necessary Conditions of Two-Level Uncertainty Reasoning Model (URM) and the Improvement on It[J]. , 1996, 11(2): 171 -180 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持:support@magtech.com.cn
总访问量: