Nonlinear Weighted Subdivision Schemes

Abstract

In this paper, we present new variants of both the de Casteljau subdivision algorithm for curves and Doo–Sabin subdivision algorithm for surfaces. Our subdivision schemes are built on nonlinear weighted averaging rules which are induced by monotonic functions. These averaging rules are used instead of midpoint averaging rule in the mentioned well-known subdivision algorithms. The analysis shows that the smoothness of the subdivision schemes for curves is inherited from the smoothness of the function which induces the averaging rule used in the refinement of the schemes. The results show that with our subdivision schemes, both convex surfaces and concave surfaces can be generated by the same scheme. This happens by only interchanging the weights of two adjacent points when computing the edge points in the subdivision refinement. This is an advantage since a designer can adjust the limit shape according to his interests.

Keywords

Subdivision curves / Subdivision surfaces / Nonlinear weighted average / De Casteljau algorithm / Doo–Sabin algorithm

References

[1] Amat S, Donat R, Liandrat J, Trillo JC. Analysis of a new nonlinear subdivision scheme. applications in image processing. Found. Comput. Math.. 2006, 6 2 193-225

[2] Andersson L-E, Stewart NF. Introduction to the Mathematics of Subdivision Surfaces. 2010 Philadelphia: SIAM

[3] Casteljau, P.: Mathématiques et cao. vol. 2, formes à pôles. Hermes (1985)

[4] Catmull E, Clark J. Recursively generated b-spline surfaces on arbitrary topological meshes. Comput. Aided Des.. 1978, 10 6 350-355

[5] Chaikin GM. An algorithm for high-speed curve generation. Comput. Graphics Image Process.. 1974, 3 4 346-349

[6] Chena Q, Prautzscha H. Subdivision by waves-weighted averaging schemes. Proc. DWCAA12. 2013, 6 9-19

[7] Cohen E, Lyche T, Riesenfeld R. Discrete b-splines and subdivision techniques in computer-aided geometric design and computer graphics. Comput. Graphics Image Process.. 1980, 14 2 87-111

[8] Conti, C., Donatelli, M., Romani, L., Novara, P.: Convergence and normal continuity analysis of nonstationary subdivision schemes near extraordinary vertices and faces. Construct. Approx. 1–40 (2019)

[9] Crouch P, Kun G, Leite FS. The de Casteljau algorithm on lie groups and spheres. J. Dyn. Control Syst.. 1999, 5 3 397-429

[10] Cucker F, Pinkus A, Todd MJ. Foundations of Computational Mathematics, Hong Kong 2008. 2009 Cambridge: Cambridge University Press

[11] de Rham G. Sur une courbe plane. J. Math. Pares Appl.. 1956, 35 25-42

[12] Deslauriers G, Dubuc S. Symmetric Iterative Interpolation Processes. 1989 Berlin: Springer. 49-68

[13] Doo, D.: A subdivision algorithm for smoothing down irregular shaped polyhedra. In: Proc Conf Interactive Technique in CAD, pp. 156–165 (1978)

[14] Doo D, Sabin M. Behaviour of recursive division surfaces near extraordinary points. Comput. Aided Des.. 1978, 10 6 356-360

[15] Duchamp T, Xie G, Yu T. Smoothing nonlinear subdivision schemes by averaging. Numer. Algorithms. 2018, 77 2 361-379

[16] Dyn N, Oswald P. Univariate Subdivision and Multi-scale Transforms: The Nonlinear Case. 2009 Berlin: Springer. 203-247

[17] Dyn N, Levin D, Gregory JA. A 4-point interpolatory subdivision scheme for curve design. Comput. Aided Geomet. Design. 1987, 4 4 257-268

[18] Dyn N, Levin D, Liu D. Interpolatory convexity-preserving subdivision schemes for curves and surfaces. Comput. Aided Des.. 1992, 24 4 211-216

[19] Floater, M.S., Micchelli, C.A.: Nonlinear Means in Geometric Modeling. IBM Thomas J. Watson Research Division (1997)

[20] Goldman R, Vouga E, Schaefer S. On the smoothness of real-valued functions generated by subdivision schemes using nonlinear binary averaging. Comput. Aided Geomet. Design. 2009, 26 2 231-242

[21] Grohs P. Smoothness analysis of subdivision schemes on regular grids by proximity. SIAM J. Numer. Anal.. 2008, 46 4 2169-2182

[22] Halstead, M., Kass, M., DeRose, T.: Efficient, fair interpolation using Catmull-Clark surfaces. In: Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques, pp. 35–44 (1993)

[23] Hameed, R., Mustafa, G.: Construction and analysis of binary subdivision schemes for curves and surfaces originated from Chaikin points. Int. J. Anal. 2016 (2016)

[24] Huang, Z., Wang, F., Wang, G.: Extended Doo–Sabin surfaces. J. Inf. Comput. Sci. 8(12), 2239–2247

[25] Huang Z, Wang G. Non-uniform recursive Doo–Sabin surfaces. Comput. Aided Des.. 2011, 43 11 1527-1533

[26] Jakubiak J, Leite FS, Rodrigues RC. A two-step algorithm of smooth spline generation on Riemannian manifolds. J. Comput. Appl. Math.. 2006, 194 2 177-191

[27] Jena MK, Shunmugaraj P, Das P. A non-stationary subdivision scheme for generalizing trigonometric spline surfaces to arbitrary meshes. Comput. Aided Geomet. Design. 2003, 20 2 61-77

[28] Lane JM, Riesenfeld RF. A theoretical development for the computer generation and display of piecewise polynomial surfaces. IEEE Trans. Pattern Anal. Mach. Intell.. 1980, 1 35-46

[29] Li G, Ma W. A method for constructing interpolatory subdivision schemes and blending subdivisions. Comput. Graphics Forum. 2007, 26 185-201

[30] Loop, C.: Smooth subdivision surfaces based on triangles. Master’s thesis, University of Utah, Department of Mathematics (1987)

[31] Miura, K.T., Masuda, H.: Selective non-uniform subdivision. In: Pacific Conference on Computer Graphics and Applications, pp. 457–459 (2002)

[32] Müller K, Reusche L, Fellner D. Extended subdivision surfaces: building a bridge between nurbs and Catmull–Clark surfaces. ACM Trans. Graphics (TOG). 2006, 25 2 268-292

[33] Noakes L. Nonlinear corner-cutting. Adv. Comput. Math.. 1998, 8 3 165-177

[34] Pan J, Lin S, Luo X. A combined approximating and interpolating subdivision scheme with c2 continuity. Appl. Math. Lett.. 2012, 25 12 2140-2146

[35] Park, F., Ravani, B.: Bézier curves on Riemannian manifolds and lie groups with kinematics applications (1995)

[36] Qin, K., Wang, H.: Eigenanalysis and continuity of non-uniform Doo–Sabin surfaces. In: Proceedings. In: 7th Pacific Conference on Computer Graphics and Applications (Cat. No. PR00293), pp. 179–186 (1999). IEEE

[37] Riesenfeld RF. On chaikin’s algorithm. Comput. Graphics Image Process.. 1975, 4 3 304-310

[38] Schaefer S, Vouga E, Goldman R. Nonlinear subdivision through nonlinear averaging. Comput. Aided Geomet. Design. 2008, 25 3 162-180

[39] Sederberg, T.W., Zheng, J., Sewell, D., Sabin, M.: Non-uniform recursive subdivision surfaces. In: Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques, pp. 387–394 (1998)

[40] Uwitije, R., Wang, X., Qarariyah, A., Deng, J.: Nonlinear weighted average and blossoming. Commun. Math. Stat. (2020)

[41] Wallner J. Smoothness analysis of subdivision schemes by proximity. Constr. Approx.. 2006, 24 3 289-318

[42] Wallner J, Dyn N. Convergence and c1 analysis of subdivision schemes on manifolds by proximity. Comput. Aided Geomet. Design. 2005, 22 7 593-622

[43] Xie, G.: Smoothness of subdivision schemes in nonlinear and geometric settings. Ph.D. thesis, Rensselaer Polytechnic Institute (2006)

[44] Xie G, Yu TP-Y. Smoothness equivalence properties of manifold-valued data subdivision schemes based on the projection approach. SIAM J. Numer. Anal.. 2007, 45 3 1200-1225

Funding

National Key R &D Program of China(2022YFA1005201/2022YFA1005200)

National Natural Science Foundation of China(61772167)

CAS-TWAS President’s Fellowship for International PhD Students(12171453)