Stochastic Geometric Iterative Method for Loop Subdivision Surface Fitting

Abstract

In this paper, we propose a stochastic geometric iterative method (S-GIM) to approximate the high-resolution 3D models by finite loop subdivision surfaces. Given an input mesh as the fitting target, the initial control mesh is generated using the mesh simplification algorithm. Then, our method adjusts the control mesh iteratively to make its finite loop subdivision surface approximate the input mesh. In each geometric iteration, we randomly select part of points on the subdivision surface to calculate the difference vectors and distribute the vectors to the control points. Finally, the control points are updated by adding the weighted average of these difference vectors. We prove the convergence of S-GIM and verify it by demonstrating error curves in the experiment. In addition, compared with existing geometric iterative methods, S-GIM has a shorter running time under the same number of iteration steps.

Keywords

Geometric iterative / Surface fitting / Subdivision surface / Stochastic PIA / Stochastic LSPIA

References

[1] Cesa-Bianchi N. Analysis of two gradient-based algorithms for on-line regression. J. Comput. Syst. Sci.. 1999, 59 3 392-411

[2] Cheng F, Fan F, Lai S, Huang C, Wang J, Yong JH. Loop subdivision surface based progressive interpolation. J. Comput. Sci. Tech-CH.. 2009, 24 03 39-46

[3] Deng C, Lin H. Progressive and iterative approximation for least squares B-spline curve and surface fitting. Comput. Aid. Des.. 2014, 47 32-44

[4] Garland, M., Heckbert, P.: Surface simplification using quadric error metrics. Proceedings of the ACM SIGGRAPH Conference on computer graphics 1997(07) (1997)

[5] Halstead, M., Kass, M., Derose, T.: Efficient, fair interpolation using Catmull-Clark surfaces. Proceedings of the ACM SIGGRAPH Conference on computer graphics 27(12) (2000)

[6] Hoppe, H., Derose, T., Duchamp, T., Halstead, M., Jin, H., McDonald, J., Schweitzer, J., Stuetzle, W.: Piecewise smooth surface reconstruction. Proceedings of the 21st annual conference on Computer graphics and interactive techniques 295–302 (07 1994)

[7] Kivinen J, Smola A J, Williamson R C. Large margin classification for moving targets. In: algorithmic learning theory. 2002 Berlin, Heidelberg: Springer. 113-127

[8] Lin H, Bao H, Wang G. Totally positive bases and progressive iteration approximation. Comput. Math. Appl.. 2005, 50 3–4 575-586

[9] Lin H, Chen W, Wang G. Curve reconstruction based on an interval B-spline curve. Visual Comput.. 2005, 21 07 418-427

[10] Lin, H., Jin, S., Liao, H., Jian, Q.: Quality guaranteed all-hex mesh generation by a constrained volume iterative fitting algorithm. Comput. Aid. Des. (2015)

[11] Lin H, Maekawa T, Deng C. Survey on geometric iterative methods and their applications. Comput. Aid. Des.. 2018, 95 40-51

[12] Lin, H., Zhang, Z.: An efficient method for fitting large data sets using T-splines. SIAM J. Sci. Comput. (2013)

[13] Liu HTD, Kim VG, Chaudhuri S, Aigerman N, Jacobson A. Neural subdivision. ACM Trans. Graph.. 2020, 39 4 124

[14] Loop, C.: Smooth subdivision surfaces based on triangles. Master’s thesis ( 1987)

[15] Lu L, Hu Q, Wang G. An iterative algorithm for degree reduction of Bezier curves. J. Comput. Aid. Des. Comput. Graph.. 2009, 21 12 1689-1693

[16] Ma W, Ma X, Tso SK, Pan Z. A direct approach for subdivision surface fitting from a dense triangle mesh. Comput. Aid. Des.. 2004, 36 6 525-536

[17] Maekawa T, Matsumoto Y, Namiki K. Interpolation by geometric algorithm. Comput. Aid. Des.. 2007, 39 04 313-323

[18] Marinov M, Kobbelt L. Optimization methods for scattered data approximation with subdivision surfaces. Graph. Models. 2005, 67 09 452-473

[19] Marinov M, Kobbelt L. Optimization methods for scattered data approximation with subdivision surfaces. Graph. Models. 2005, 67 5 452-473

[20] Muja, M., Lowe, D.: Flann-fast library for approximate nearest neighbors user manual. University of British Columbia, Vancouver, BC, Canada, Computer Science Department (2009)

[21] Nishiyama, Y., Morioka, M., Maekawa, T.: Loop subdivision surface fitting by geometric algorithms. Poster proceedings of pacific graphics 67–74 (2008)

[22] Sasaki, Y., Takezawa, M., Kim, S., Kawaharada, H., Maekawa, T.: Adaptive direct slicing of volumetric attribute data represented by trivariate b-spline functions. Int. J. Adv. Manuf. Tech. (2017)

[23] Xu C, Lin H, Hu H, He Y. Fast calculation of Laplace-Beltrami eigenproblems via subdivision linear subspace. Comput. Graph.. 2021, 97 236-247

[24] Zhang, T.: Solving large scale linear prediction problems using stochastic gradient descent algorithms (01 2004)

Funding

National Natural Science Foundation of China(61872316)