Scalar and Hermite subdivision schemes

A criterion of convergence for stationary nonuniform subdivision schemes is provided. For periodic subdivision schemes, this criterion is optimal and can be applied to Hermite subdivision schemes which are not necessarily interpolatory. For the Merrien family of Hermite subdivision schemes which involve two parameters, we are able to describe explicitly the values of the parameters for which the Hermite subdivision scheme is convergent.     

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.     

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.     

A constructive algebraic strategy for interpolatory subdivision schemes induced by bivariate box splines

This paper describes an algebraic construction of bivariate interpolatory subdivision masks induced by three-directional box spline subdivision schemes. Specifically, given a three-directional box spline, we address the problem of defining a corresponding interpolatory subdivision scheme by constructing an appropriate correction mask to convolve with the three-directional box spline mask. The proposed approach is based on the analysis of certain polynomial identities in two variables and leads to interesting new interpolatory bivariate subdivision schemes.     

基于逼近型细分的诱导细分格式

利用逼近型细分构造插值型细分是细分领域中的一个重要问题,目前可以给出插值型细分生成函数的研究还非常少.本文给出一个生成函数的统一公式,该公式由逼近型细分的生成函数与一个子生成函数构成.该公式对应一个插值型细分或者逼近型细分,这个取决于子生成函数的选取.该公式在理论和实际中都很重要.首先,这个公式适用于任意伸缩矩阵的多元基本型细分;其次,不论是一元细分还是多元细分,推导这个统一公式都不需要求解线性方程组;再次,这个公式具有显著的几何意义,应用方便;最后,从理论上分析诱导细分的零条件和多项式再生性,本文发现这些性质不仅与逼近型细分的零条件有关,而且与逼近型细分的多项式再生性有关,从而对细分格式的构造有指导意义.本文给出3个例子来说明这个统一公式.     

基于一种新的集合插值的非凸紧集的细分概型

对A rtstein给出的度量平均的定义作了改进,给出一种新的集合插值,并基于这种新的集合插值,对相应的关于一般紧集的样条细分和插值细分分别作了研究,并给出了细分的收敛性性质.与此同时,将这种新的集合插值与基于度量平均的插值及基于M inkow sk i平均的插值分别作了比较,可以看出新的集合插值在某些方面具有更好的物理性质.     

Finite Difference Method with Nonuniform Meshes for Quasilinear Parabolic Systems

1.lnthestudyoftheprobleminphysics,mechanics,chemicalreactions,biologyandotherpracticalsciences,thelinearandnonlinearparabolicequationsandsystemsareappearedveryfrequently.Manynumericalinvestigationsinscientificandengineeringproblemsespeciallyinthelargescalecomputationalproblemsoftencontainthenumer-icalsolutionsofparabolicequationsandsystems.ThemethodwithunequalmeshstePSisnotavoidableinthesecomputations.Manyunexpectedandselfcontradictoryphe-nomenonraisingfromtheuseofunequalmeshstepscallourgreata…     

Noninterpolatory Hermite subdivision schemes

Bivariate interpolatory Hermite subdivision schemes have recently been applied to build free-form subdivision surfaces. It is well known to geometric modelling practitioners that interpolatory schemes typically lead to ``unfair" surfaces--surfaces with unwanted wiggles or undulations--and noninterpolatory (a.k.a. approximating in the CAGD community) schemes are much preferred in geometric modelling applications. In this article, we introduce, analyze and construct noninterpolatory Hermite subdivision schemes, a class of vector subdivision schemes which can be applied to iteratively refine Hermite data in a not necessarily interpolatory fashion. We also study symmetry properties of such subdivision schemes which are crucial for application in free-form subdivision surfaces.

A key step in our mathematical analysis of Hermite type subdivision schemes is that we make use of the strong convergence theory of refinement equations to convert a prescribed geometric condition on the subdivision scheme--namely, the subdivision scheme is of Hermite type--to an algebraic condition on the subdivision mask. The latter algebraic condition can then be used in a computational framework to construct specific schemes.

     

Exact evaluation of limits and tangents for interpolatory subdivision surfaces at rational points

This paper presents a new method for exact evaluation of a limit surface generated by stationary interpolatory subdivision schemes and its associated tangent vectors at arbitrary rational points. The algorithm is designed on the basis of the parametric m-ary expansion and construction of the associated matrix sequence. The evaluation stencil of the control points on the initial mesh is obtained, through computation, by multiplying the finite matrices in a sequence corresponding to the expansion sequence and eigendecomposition of the contractive matrix related to the period of rational numbers. The method proposed in this paper works for other non-polynomial subdivision schemes as well.     

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.     

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.     

Decompositions of trigonometric polynomials with applications to multivariate subdivision schemes

We study multivariate trigonometric polynomials satisfying the “sum-rule” conditions of a certain order. Based on the polyphase representation of these polynomials relative to a general dilation matrix, we develop a simple constructive method for a special type of decomposition of such polynomials. These decompositions are of interest in the analysis of convergence and smoothness of multivariate subdivision schemes associated with general dilation matrices. The approach presented in this paper leads directly to constructive algorithms, and is an alternative to the analysis of multivariate subdivision schemes in terms of the joint spectral radius of certain operators. Our convergence results apply to arbitrary dilation matrices, while the smoothness results are limited to two classes of dilation matrices.     

Totally positive functions through nonstationary subdivision schemes

In this paper a new class of nonstationary subdivision schemes is proposed to construct functions having all the main properties of B-splines, namely compact support, central symmetry and total positivity. We show that the constructed nonstationary subdivision schemes are asympotically equivalent to the stationary subdivision scheme associated with a B-spline of suitable degree, but the resulting limit function has smaller support than the B-spline although keeping its regularity.     

Families of univariate and bivariate subdivision schemes originated from quartic B-spline

Families of parameter dependent univariate and bivariate subdivision schemes are presented in this paper. These families are new variants of the Lane-Riesenfeld algorithm. So the subdivision algorithms consist of both refining and smoothing steps. In refining step, we use the quartic B-spline based subdivision schemes. In smoothing step, we average the adjacent points. The bivariate schemes are the non-tensor product version of our univariate schemes. Moreover, for odd and even number of smoothing steps, we get the primal and dual schemes respectively. Higher regularity of the schemes can be achieved by increasing the number of smoothing steps. These schemes can be nicely generalized to contain local shape parameters that allow the user to adjust locally the shape of the limit curve/surface.     

Smoothness of Stationary Subdivision on Irregular Meshes

We derive necessary and sufficient conditions for tangent plane and C ^k -continuity of stationary subdivision schemes near extraordinary vertices. Our criteria generalize most previously known conditions. We introduce a new approach to analysis of subdivision surfaces based on the idea of the universal surface . Any subdivision surface can be locally represented as a projection of the universal surface, which is uniquely defined by the subdivision scheme. This approach provides us with a more intuitive geometric understanding of subdivision near extraordinary vertices. February 16, 1998. Date revised: January 27, 1999. Date accepted: April 2, 1999.     

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

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

W_p,r(R^s)上的稳定细分格式

细分格式是计算机图形学和小波分析中的一个重要工具．该文考虑犠狆，狉（犚狊）空间上的犕伸缩的细分格式，犕为一个狊×狊的整数矩阵，满足ｌｉｍ狀→ ∞犕－狀＝０．作者用与细分面具相关的犿（＝｜犕｜）个矩阵的联合谱半径来刻画犠狆，狉（犣狊）上的细分格式的收敛性，得到了收敛性的充分与必要条件．     

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.     

On spectral-like resolution properties of fourth-order accurate symmetric bicompact schemes

A dispersion analysis is conducted for bicompact schemes of fourth-order accuracy in space, namely, for a semidiscrete scheme and a second-order accurate scheme in time. It is shown that their numerical group velocity is positive for all dimensionless wavenumbers. It is proved that the dispersion properties of the bicompact schemes are preserved on highly nonuniform meshes. A comparison reveals that the fourth-order bicompact schemes have a higher spectral resolution than not only other same-order compact schemes, but also some sixth-order ones. Two numerical examples are presented that demonstrate the ability of the bicompact schemes to adequately simulate wave propagation on highly nonuniform meshes over long time intervals.