Journal of Computer Science and Technology ›› 2022, Vol. 37 ›› Issue (2): 487-504.doi: 10.1007/s11390-020-0183-1

Special Issue: Artificial Intelligence and Pattern Recognition; Computer Graphics and Multimedia

• Regular Paper • Previous Articles    

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.

PDF (PC)

9

Supplement

1

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.
[1] Yun-Cen Huang, Jie-Qing Feng, Matthias NieBner, Yuan-Min Cui, Baoguang Yang . Feature-Adaptive Rendering of Loop Subdivision Surfaces on Modern GPUs [J]. , 2014, 29(6): 1014-1025.
[2] Fu-Hua (Frank) Cheng, Feng-Tao Fan, Shu-Hua Lai, Cong-Lin Huang, Jia-Xi Wang, and Jun-Hai Yong. Loop Subdivision Surface Based Progressive Interpolation [J]. , 2009, 24(1 ): 39-46 .
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] Lian Lin; Zhang Yili; Tang Changjie;. A Non-Recursive Algorithm Computing Set Expressions[J]. , 1988, 3(4): 310 -316 .
[2] Zhou Quan; Wei Daozheng;. A Complete Critical Path Algorithm for Test Generation of Combinational Circuits[J]. , 1991, 6(1): 74 -82 .
[3] Wang Ke;. Polynomial Tests of Normal Forms and Some Related Results[J]. , 1992, 7(1): 75 -82 .
[4] Wang Yihe; Hong Jiarong;. AECAM:An Extension Matrix Algorithm on a Cellular Automata Machine[J]. , 1992, 7(1): 88 -91 .
[5] Wu Xindong;. Inductive Learning[J]. , 1993, 8(2): 22 -36 .
[6] Sui Yuefei;. Bounded Recursively Enumerable Sets and Degrees[J]. , 1993, 8(3): 15 -18 .
[7] Luo Gang;. 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] Hu Shimin;. A Subdivision Scheme for Rational Triangular Bézier Surfaces[J]. , 1996, 11(1): 9 -16 .
[10] Liu Dayou; Zhong Shaochun;. Necessary Conditions of Two-Level Uncertainty Reasoning Model (URM) and the Improvement on It[J]. , 1996, 11(2): 171 -180 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

 Home
Editorial Board
Author Guidelines
Subscription		 Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved