A Chaikin-based variant of Lane-Riesenfeld algorithm and its non-tensor product extension. (English) Zbl 1417.65108
Summary: In this work we present a parameter-dependent Refine-and-Smooth \((RS)\) subdivision algorithm where the refine stage \(R\) consists in the application of a perturbation of Chaikin’s/Doo-Sabin’s vertex split, while each smoothing stage \(S\) performs averages of adjacent vertices like in the Lane-Riesenfeld algorithm [J. M. Lane and R. F. Riesenfeld, IEEE Trans. Pattern Anal. Mach. Intell. 2, 35–46 (1980; Zbl 0436.68063)]. This constructive approach provides a unifying framework for univariate/bivariate primal and dual subdivision schemes with tension parameter and allows us to show that several existing subdivision algorithms, proposed in the literature via isolated constructions, can be obtained as specific instances of the proposed strategy. Moreover, this novel approach provides an intuitive theoretical tool for the derivation of new non-tensor product subdivision schemes that in the regular regions satisfy the property of reproducing bivariate cubic polynomials, thus resulting the natural extension of the univariate family presented in [K. Hormann and M. A. Sabin, Comput. Aided Geom. Des. 25, No. 1, 41–52 (2008; Zbl 1172.65308)].
MSC:
| 65D18 | Numerical aspects of computer graphics, image analysis, and computational geometry |
Keywords:
subdivision; refine-and-smooth; tension parameter; non-tensor product; bivariate cubic precisionReferences:
| [1] | Cashman, T. J.; Hormann, K.; Reif, U., Generalized Lane-riesenfeld algorithms, Comput. Aided Geom. Des., 30, 398-409, (2013) · Zbl 1355.65024 |
| [2] | Catmull, E.; Clark, J., Recursively generated B-spline surfaces on arbitrary topological meshes, Comput. Aided Des., 10, 350-355, (1978) |
| [3] | Chaikin, G. M., An algorithm for high speed curve generation, Comput. Graph. Image Process., 3, 4, 346-349, (1974) |
| [4] | Charina, M.; Conti, C., Polynomial reproduction of multivariate scalar subdivision schemes, J. Comput. Appl. Math., 240, 51-61, (2013) · Zbl 1258.65023 |
| [5] | Charina, M.; Conti, C.; Jetter, K.; Zimmermann, G., Scalar multivariate subdivision schemes and box splines, Comput. Aided Geom. Des., 28, 285-306, (2011) · Zbl 1221.65060 |
| [6] | Charina, M.; Conti, C.; Romani, L., Reproduction of exponential polynomials by multivariate non-stationary subdivision schemes with a general dilation matrix, Numer. Math., 127, 2, 223-254, (2014) · Zbl 1295.65018 |
| [7] | Conti, C.; Hormann, K., Polynomial reproduction for univariate subdivision schemes of any arity, J. Approx. Theory, 163, 413-437, (2011) · Zbl 1211.65022 |
| [8] | Conti, C.; Romani, L., Algebraic conditions on non-stationary subdivision symbols for exponential polynomial reproduction, J. Comput. Appl. Math., 236, 4, 543-556, (2011) · Zbl 1232.65035 |
| [9] | Conti, C.; Romani, L., Dual univariate m-ary subdivision schemes of de Rham-type, J. Math. Anal. Appl., 407, 443-456, (2013) · Zbl 1306.65163 |
| [10] | Deng, C.; Ma, W., Constructing an interpolatory subdivision scheme from doo-sabin subdivision, (12th Intern. Conf. on Computer-Aided Design and Computer Graphics, (2011)), 215-222 |
| [11] | Deslauriers, G.; Dubuc, S., Symmetric iterative interpolation processes, Constr. Approx., 5, 49-68, (1989) · Zbl 0659.65004 |
| [12] | Doo, D.; Sabin, M., Analysis of the behaviour of recursive division surfaces near extraordinary points, Comput. Aided Des., 10, 6, 356-360, (1978) |
| [13] | Dyn, N.; Levin, D., Subdivision schemes in geometric modelling, Acta Numer., 11, 73-144, (2002) · Zbl 1105.65310 |
| [14] | Dyn, N.; Levin, D.; Gregory, J. A., A 4-point interpolatory subdivision scheme for curve design, Comput. Aided Geom. Des., 4, 257-268, (1987) · Zbl 0638.65009 |
| [15] | Dyn, N.; Floater, M.; Hormann, K., A \(C^2\) four-point subdivision scheme with fourth-order accuracy and its extensions, (Dæhlen, M.; Mørken, K.; Schumaker, L. L., Mathematical Methods for Curves and Surfaces, Tromsø, 2004, (2005), Nashboro Press), 145-156 · Zbl 1080.65526 |
| [16] | Dyn, N.; Hormann, K.; Sabin, M. A.; Shen, Z., Polynomial reproduction by symmetric subdivision schemes, J. Approx. Theory, 155, 28-42, (2008) · Zbl 1159.41003 |
| [17] | Floater, M.; Muntingh, G., Exact regularity of pseudo-splines, (2012) |
| [18] | Hormann, K.; Sabin, M. A., A family of subdivision schemes with cubic precision, Comput. Aided Geom. Des., 25, 41-52, (2008) · Zbl 1172.65308 |
| [19] | Lane, J. M.; Riesenfeld, R. F., A theoretical development for the computer generation and display of piecewise polynomial surfaces, IEEE Trans. Pattern Anal. Mach. Intell., 2, 1, 35-46, (1980) · Zbl 0436.68063 |
| [20] | Levin, A., Polynomial generation and quasi-interpolation in stationary non-uniform subdivision, Comput. Aided Geom. Des., 20, 41-60, (2003) · Zbl 1069.41503 |
| [21] | Prautzsch, H.; Chen, Q., Analyzing midpoint subdivision, Comput. Aided Geom. Des., 28, 407-419, (2011) · Zbl 1236.65017 |
| [22] | Reif, U., A unified approach to subdivision algorithms near extraordinary vertices, Comput. Aided Geom. Des., 12, 153-174, (1995) · Zbl 0872.65007 |
| [23] | Stam, J., On subdivision schemes generalizing uniform B-spline surfaces of arbitrary degree, Comput. Aided Geom. Des., 18, 383-396, (2001) · Zbl 0970.68184 |
| [24] | Zorin, D.; Schröder, P., A unified framework for primal/dual quadrilateral subdivision schemes, Comput. Aided Geom. Des., 18, 429-454, (2001) · Zbl 0969.68155 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
