Analysis of stationary subdivision schemes for curve design based on radial basis function interpolation

This paper provides a large family of interpolatory stationary subdivision schemes based on radial basis functions (RBFs) which are positive definite or conditionally positive definite. A radial basis function considered in this study has a tension parameter λ>0 such that it provides design flexibility. We prove that for a sufficiently large , the proposed 2L-point (L∈N) scheme has the same smoothness as the well-known 2L-point Deslauriers-Dubuc scheme, which is based on 2L-1 degree polynomial interpolation. Some numerical examples are presented to illustrate the performance of the new schemes, adapting subdivision rules on bounded intervals in a way of keeping the same smoothness and accuracy of the pre-existing schemes on R. We observe that, with proper tension parameters, the new scheme can alleviate undesirable artifacts near boundaries, which usually appear to interpolatory schemes with irregularly distributed control points.     

Non-uniform interpolatory curve subdivision with edge parameters built upon compactly supported fundamental splines

In this paper we present a family of Non-Uniform Local Interpolatory (NULI) subdivision schemes, derived from compactly supported interpolatory fundamental splines with non-uniform knots (NULIFS). For this spline family, the knot-partition is defined by a sequence of break points and by one additional knot, arbitrarily placed along each knot-interval. The resulting refinement algorithms are linear and turn out to contain a set of edge parameters that, when fixed to a value in the range [0,1], allow us to achieve special shape features by simply moving each auxiliary knot between the break points. Among all the members of this new family of schemes, we will then especially analyze the NULI 4-point refinement. This subdivision scheme has all the fundamental features of the quadratic fundamental spline basis it is originated from, namely compact support, C ¹ smoothness, second order polynomials reproduction and approximation order 3. In addition the NULI 4-point subdivision algorithm has the possibility of setting consecutive edge parameters to simulate double and triple knots—that are not considered by the authors of the corresponding spline basis—thus allowing for limit curves with crease vertices, without using an ad hoc mask. Numerical examples and comparisons with other methods will be given to the aim of illustrating the performance of the NULI 4-point scheme in the case of highly non-uniform initial data.     

一类新的(2n-1)点二重动态逼近细分

利用正弦函数构造了一类新的带有形状参数ω的(2n-1)点二重动态逼近细分格式.从理论上分析了随n值变化时这类细分格式的C~k连续性和支集长度;算法的一个特色是随着细分格式中参数ω的取值不同,相应生成的极限曲线的表现张力也有所不同,而且这一类算法所对应的静态算法涵盖了Chaikin,Hormann,Dyn,Daniel和Hassan的算法.文末附出大量数值实例,在给定相同的初始控制顶点,且极限曲线达到同一连续性的前提下和现有几种算法做了比较,数值实例表明这类算法生成的极限曲线更加饱满,表现力更强.     

Nonlinear Subdivision Schemes on Irregular Meshes

The present article deals with convergence and smoothness analysis of geometric, nonlinear subdivision schemes in the presence of extraordinary points. We discuss when the existence of a proximity condition between a linear scheme and its nonlinear analogue implies convergence of the nonlinear scheme (for dense enough input data). Furthermore, we obtain C ¹ smoothness of the nonlinear limit function in the vicinity of an extraordinary point over Reif’s characteristic parametrization. The results apply to the geometric analogues of well-known subdivision schemes such as Doo–Sabin or Catmull–Clark schemes.     

Stationary binary subdivision schemes using radial basis function interpolation

A new family of interpolatory stationary subdivision schemes is introduced by using radial basis function interpolation. This work extends earlier studies on interpolatory stationary subdivision schemes in two aspects. First, it provides a wider class of interpolatory schemes; each 2L-point interpolatory scheme has the freedom of choosing a degree (say, m) of polynomial reproducing. Depending on the combination (2L,m), the proposed scheme suggests different subdivision rules. Second, the scheme turns out to be a 2L-point interpolatory scheme with a tension parameter. The conditions for convergence and smoothness are also studied. Dedicated to Prof. Charles A. Micchelli on the occasion of his 60th birthday Mathematics subject classifications (2000) 41A05, 41A25, 41A30, 65D10, 65D17. Byung-Gook Lee: This work was done as a part of Information & Communication fundamental Technology Research Program supported by Ministry of the Information & Communication in Republic of Korea. Jungho Yoon: Corresponding author. Supported by the Korea Science and Engineering Foundation grant (KOSEF R06-2002-012-01001).     

Analysis of subdivision schemes for nets of functions by proximity and controllability

In this paper we develop tools for the analysis of net subdivision schemes, schemes which recursively refine nets of bivariate continuous functions defined on grids of lines, and generate denser and denser nets. Sufficient conditions for the convergence of such a sequence of refined nets, and for the smoothness of the limit function, are derived in terms of proximity to a bivariate linear subdivision scheme refining points, under conditions controlling some aspects of the univariate functions of the generated nets. Approximation orders of net subdivision schemes, which are in proximity with positive schemes refining points are also derived. The paper concludes with the construction of a family of blending spline-type net subdivision schemes, and with their analysis by the tools presented in the paper. This family is a new example of net subdivision schemes generating C¹ limits with approximation order 2.     

Smoothing nonlinear subdivision schemes by averaging

In the theory of linear subdivision algorithms, it is well-known that the regularity of a linear subdivision scheme can be elevated by one order (say, from C ^k to C ^k+1) by composing it with an averaging step (equivalently, by multiplying to the subdivision mask a(z) a (1 + z) factor. In this paper, we show that the same can be done to nonlinear subdivision schemes: by composing with it any nonlinear, smooth, 2-point averaging step, the lifted nonlinear subdivision scheme has an extra order of regularity than the original scheme. A notable application of this result shows that the classical Lane-Riesenfeld algorithm for uniform B-Spline, when extended to Riemannian manifolds based on geodesic midpoint, produces curves with the same regularity as their linear counterparts. (In particular, curvature does not obstruct the nonlinear Lane-Riesenfeld algorithm to inherit regularity from the linear algorithm.) Our main result uses the recently developed technique of differential proximity conditions.     

Palindromic Matrices of Order Two and Three-Point Subdivision Schemes

We introduce a family of three-point subdivision schemes related to palindromic pairs of matrices of order 2. We apply the Mößner theorem on palindromic matrices to the C ⁰ convergence of these subdivision schemes. We study the Hölder regularity of their limit functions. The Hölder exponent which is found in the regular case is sharp for most limit functions. In the singular case, the modulus of continuity of the limit functions is of order δlogδ. These results can be used for studying the C ¹ convergence of the Merrien family of Hermite subdivision schemes.     

Polynomial-based non-uniform interpolatory subdivision with features control

Starting from a well-known construction of polynomial-based interpolatory 4-point schemes, in this paper we present an original affine combination of quadratic polynomial samples that leads to a non-uniform 4-point scheme with edge parameters. This blending-type formulation is then further generalized to provide a powerful subdivision algorithm that combines the fairing curve of a non-uniform refinement with the advantages of a shape-controlled interpolation method and an arbitrary point insertion rule. The result is a non-uniform interpolatory 4-point scheme that is unique in combining a number of distinctive properties. In fact it generates visually-pleasing limit curves where special features ranging from cusps and flat edges to point/edge tension effects may be included without creating undesired undulations. Moreover such a scheme is capable of inserting new points at any positions of existing intervals, so that the most convenient parameter values may be chosen as well as the intervals for insertion.Such a fully flexible curve scheme is a fundamental step towards the construction of high-quality interpolatory subdivision surfaces with features control.     

Convergent Vector and Hermite Subdivision Schemes

Hermite subdivision schemes have been studied by Merrien, Dyn, and Levin and they appear to be very different from subdivision schemes analyzed before since the rules depend on the subdivision level. As suggested by Dyn and Levin, it is possible to transform the initial scheme into a uniform stationary vector subdivision scheme which can be handled more easily.With this transformation, the study of convergence of Hermite subdivision schemes is reduced to that of vector stationary subdivision schemes. We propose a first criterion for C⁰-convergence for a large class of vector subdivision schemes. This gives a criterion for C¹-convergence of Hermite subdivision schemes. It can be noticed that these schemes do not have to be interpolatory. We conclude by investigating spectral properties of Hermite schemes and other necessary/sufficient conditions of convergence.     

A family of non-oscillatory 6-point interpolatory subdivision schemes

In this paper we propose and analyze a new family of nonlinear subdivision schemes which can be considered non-oscillatory versions of the 6-point Deslauries-Dubuc (DD) interpolatory scheme, just as the Power _p schemes are considered nonlinear non-oscillatory versions of the 4-point DD interpolatory scheme. Their design principle may be related to that of the Power _p schemes and it is based on a weighted analog of the Power _p mean. We prove that the new schemes reproduce exactly polynomials of degree three and stay ’close’ to the 6-point DD scheme in smooth regions. In addition, we prove that the first and second difference schemes are well defined for each member of the family, which allows us to give a simple proof of the uniform convergence of these schemes and also to study their stability as in [19, 22]. However our theoretical study of stability is not conclusive and we perform a series of numerical experiments that seem to point out that only a few members of the new family of schemes are stable. On the other hand, extensive numerical testing reveals that, for smooth data, the approximation order and the regularity of the limit function may be similar to that of the 6-point DD scheme and larger than what is obtained with the Power _p schemes.     

Matrix-valued symmetric templates for interpolatory surface subdivisions: I. Regular vertices

The objective of this paper is to introduce a general procedure for deriving interpolatory surface subdivision schemes with “symmetric subdivision templates” (SSTs) for regular vertices. While the precise definition of “symmetry” will be clarified in the paper, the property of SSTs is instrumental to facilitate application of the standard procedure for finding symmetric weights for taking weighted averages to accommodate extraordinary (or irregular) vertices in surface subdivisions, a topic to be studied in a continuation paper. By allowing the use of matrices as weights, the SSTs introduced in this paper may be constructed to overcome the size barrier limited to scalar-valued interpolatory subdivision templates, and thus avoiding the unnecessary surface oscillation artifacts. On the other hand, while the old vertices in a (scalar) interpolatory subdivision scheme do not require a subdivision template, we will see that this is not the case for the matrix-valued setting. Here, we employ the same definition of interpolation subdivisions as in the usual scalar consideration, simply by requiring the old vertices to be stationary in the definition of matrix-valued interpolatory subdivisions. Hence, there would be another complication when the templates are extended to accommodate extraordinary vertices if the template sizes are not small. In this paper, we show that even for C² interpolatory subdivisions, only one “ring” is sufficient in general, for both old and new vertices. For example, for 1-to-4 split C² interpolatory surface subdivisions, we obtain matrix-valued symmetric interpolatory subdivision templates (SISTs) for both triangular and quadrilateral meshes with sizes that agree with those of the Loop and Catmull–Clark schemes, respectively. Matrix-valued SISTs of similar sizes are also constructed for C² interpolatory and subdivision schemes in this paper. In addition to small template sizes, an obvious feature of matrix-valued weights is the flexibility for introducing shape-control parameters. Another significance is that, in contrast to the usual scalar setting, matrix-valued SISTs can be formulated in terms of the coefficient sequence of some vector refinement equation of interpolating bivariate C² splines with small support. For example, by modifying the spline function vectors introduced in our previous work [C.K. Chui, Q.T. Jiang, Surface subdivision schemes generated by refinable bivariate spline function vectors, Appl. Comput. Harmon. Anal. 15 (2003) 147–162; C.K. Chui, Q.T. Jiang, Refinable bivariate quartic and quintic C²-splines for quadrilateral subdivisions, Preprint, 2004], C² symmetric interpolatory subdivision schemes associated with refinement equations of C² cubic and quartic splines on the 6-directional and 4-directional meshes, respectively, are also constructed in this paper.     

Subdivision Schemes of Sets and the Approximation of Set-Valued Functions in the Symmetric Difference Metric

In this work we construct subdivision schemes refining general subsets of ? ⁿ and study their applications to the approximation of set-valued functions. Differently from previous works on set-valued approximation, our methods are developed and analyzed in the metric space of Lebesgue measurable sets endowed with the symmetric difference metric. The construction of the set-valued subdivision schemes is based on a new weighted average of two sets, which is defined for positive weights (corresponding to interpolation) and also when one weight is negative (corresponding to extrapolation). Using the new average with positive weights, we adapt to sets spline subdivision schemes computed by the Lane–Riesenfeld algorithm, which requires only averages of pairs of numbers. The averages of numbers are then replaced by the new averages of pairs of sets. Among other features of the resulting set-valued subdivision schemes, we prove their monotonicity preservation property. Using the new weighted average of sets with both positive and negative weights, we adapt to sets the 4-point interpolatory subdivision scheme. Finally, we discuss the extension of the results obtained in metric spaces of sets, to general metric spaces endowed with an averaging operation satisfying certain properties.     

Approximation order of interpolatory nonlinear subdivision schemes

Linear interpolatory subdivision schemes of C^r smoothness have approximation order at least r+1. The present paper extends this result to nonlinear univariate schemes which are in proximity with linear schemes in a certain specific sense. The results apply to nonlinear subdivision schemes in Lie groups and in surfaces which are obtained from linear subdivision schemes. We indicate how to extend the results to the multivariate case.     

Shape Preserving Interpolatory Subdivision Schemes for Nonuniform Data

This article is concerned with a class of shape preserving four-point subdivision schemes which are stationary and which interpolate nonuniform univariate data {(x_i, f_i)}. These data are functional data, i.e., x_i≠x_j if i≠j. Subdivision for the strictly monotone x-values is performed by a subdivision scheme that makes the grid locally uniform. This article is concerned with constructing suitable subdivision methods for the f-data which preserve convexity; i.e., the data at the kth level, {x^(k)_i, f_i(k)} is a convex data set for all k provided the initial data are convex. First, a sufficient condition for preservation of convexity is presented. Additional conditions on the subdivision methods for convergence to a C¹ limit function are given. This leads to explicit rational convexity preserving subdivision schemes which generate continuously differentiable limit functions from initial convex data. The class of schemes is further restricted to schemes that reproduce quadratic polynomials. It is proved that these schemes are third order accurate. In addition, nonuniform linear schemes are examined which extend the well-known linear four-point scheme to the case of nonuniform data. Smoothness of the limit function generated by these linear schemes is proved by using the well-known smoothness criteria of the uniform linear four-point scheme.     

Hermite subdivision on manifolds via parallel transport

We propose a new adaption of linear Hermite subdivision schemes to the manifold setting. Our construction is intrinsic, as it is based solely on geodesics and on the parallel transport operator of the manifold. The resulting nonlinear Hermite subdivision schemes are analyzed with respect to convergence and C ¹ smoothness. Similar to previous work on manifold-valued subdivision, this analysis is carried out by proving that a so-called proximity condition is fulfilled. This condition allows to conclude convergence and smoothness properties of the manifold-valued scheme from its linear counterpart, provided that the input data are dense enough. Therefore the main part of this paper is concerned with showing that our nonlinear Hermite scheme is “close enough”, i.e., in proximity, to the linear scheme it is derived from.     

Single Basepoint Subdivision Schemes for Manifold-valued Data: Time-Symmetry Without Space-Symmetry

This paper establishes smoothness results for a class of nonlinear subdivision schemes, known as the single basepoint manifold-valued subdivision schemes, which shows up in the construction of wavelet-like transform for manifold-valued data. This class includes the (single basepoint) Log–Exp subdivision scheme as a special case. In these schemes, the exponential map is replaced by a so-called retraction map f from the tangent bundle of a manifold to the manifold. It is known that any choice of retraction map yields a C ² scheme, provided the underlying linear scheme is C ² (this is called “C ² equivalence”). But when the underlying linear scheme is C ³, Navayazdani and Yu have shown that to guarantee C ³ equivalence, a certain tensor P _f associated to f must vanish. They also show that P _f vanishes when the underlying manifold is a symmetric space and f is the exponential map. Their analysis is based on certain “C ^k  proximity conditions” which are known to be sufficient for C ^k  equivalence. In the present paper, a geometric interpretation of the tensor P _f is given. Associated to the retraction map f is a torsion-free affine connection, which in turn defines an exponential map. The condition P _f =0 is shown to be equivalent to the condition that f agrees with the exponential map of the connection up to the third order. In particular, when f is the exponential map of a connection, one recovers the original connection and P _f vanishes. It then follows that the condition P _f =0 is satisfied by a wider class of manifolds than was previously known. Under the additional assumption that the subdivision rule satisfies a time-symmetry, it is shown that the vanishing of P _f implies that the C ⁴ proximity conditions hold, thus guaranteeing C ⁴ equivalence. Finally, the analysis in the paper shows that for k≥5, the C ^k  proximity conditions imply vanishing curvature. This suggests that vanishing curvature of the connection associated to f is likely to be a necessary condition for C ^k equivalence for k≥5.     

A unified three point approximating subdivision scheme

In this paper,we propose a three point approximating subdivision scheme,with three shape parameters,that unifies three different existing three point approximating schemes.Some sufficient conditions for subdivision curve C0 to C3 continuity and convergence of the scheme for generating tensor product surfaces for certain ranges of parameters by using Laurent polynomial method are discussed.The systems of curve and surface design based on our scheme have been developed successfully in garment CAD especially for clothes modelling.     

Hermite subdivision with shape constraints on a rectangular mesh

In 1999, Dubuc and Merrien introduced a Hermite subdivision scheme which gives C ¹-interpolants on a rectangular mesh. In this paper a two parameter version of this scheme is analyzed, and C ¹-convergence is proved for a range of the two parameters. By introducing a control grid the parameters in the scheme can be chosen so that the interpolant inherits positivity and/or directional monotonicity from the initial data. Several examples are given showing that a desired shape can be achieved even if only very crude estimates for the initial slopes are used. AMS subject classification (2000) 65D05, 65D17     

Non-stationary subdivision for exponential polynomials reproduction

In this paper we develop a novel approach to construct non-stationary subdivision schemes with a tension control parameter which can reproduce functions in a finite-dimensional subspace of exponential polynomials. The construction process is mainly implemented by solving linear systems for primal and dual subdivision schemes respectively, which are based on different parameterizations. We give the theoretical basis for the existence, uniqueness, and refinement rules of schemes proposed in this paper. The convergence and smoothness of the schemes are analyzed as well. Moreover, conics reproducing schemes are analyzed based on our theory, and a new idea that the tensor parameter ωk of the schemes can be adjusted for conics generation is proposed.